For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Efficient Analyzing General Dominant Relationship Based on Partial Order Models
Zhenglu YANG Lin LI Masaru KITSUREGAWA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2010/06/01
Online ISSN: 1745-1361
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>>
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.