2J-4 Efficient General Dominant Relationship Analysis based on Partial Order Models

概要

論文の詳細を見る
Due to the importance of skyline query in many applications, it has been attracted much attention recently. Given a k-dimensional dataset D, a point p is said to dominate another point q if p is better than q in at least one dimension and equal to or better than q in the remaining dimensions. However, in some real applications, users are more interested in the detail of the general dominant relationship in a business model, i.e., a point p dominates how many other points and is dominated by how many others, which is called general dominant relationship (GDR). In this paper, we explore how to efficiently analyze the GDR query. We show that the framework proposed before can not efficiently solve this problem. We find the interrelated connection between the partial order and the dominant relationship. Based on this discovery, we propose efficient algorithms to answer the GDR queries by querying the partialorder representation of spatial datasets. Extensive experiments illustrate the effectiveness and efficiency of our methods.
一般社団法人情報処理学会の論文
2008-03-13