Efficient Analyzing General Dominant Relationship Based on Partial Order Models

Zhenglu YANG  Lin LI  Masaru KITSUREGAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.6   pp.1394-1402
Publication Date: 2010/06/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.1394
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Info-Plosion)
Category: Information Retrieval
skyline query,  algorithm,  dominant relationship analysis,  performance evaluation,  

Full Text: PDF>>
Buy this Article

Skyline query is very important because it is the basis of many applications, e.g., decision making, user-preference queries. Given an N-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. In this paper, we study a generalized problem of skyline query that, users are more interested in the details of the dominant relationship in a dataset, i.e., a point p dominates how many other points and whom they are. We show that the existing framework proposed in 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 a new data structure, ParCube, which concisely represents the dominant relationship. We propose some effective strategies to construct ParCube. Extensive experiments illustrate the efficiency of our methods.