Full Citation
Title: Efficient Skyline Evaluation over Partially Ordered Domains
Citation Type: Journal Article
Publication Year: 2010
ISBN:
ISSN:
DOI:
NSFID:
PMCID:
PMID:
Abstract: Although there has been a considerable body of work on skylineevaluation in multidimensional data with totally ordered attributedomains, there are only a few methods that consider attributes withpartially ordered domains. Existing work maps each partially ordereddomain to a total order and then adapts algorithms for totallyordereddomains to solve the problem. Nevertheless these methodseither use stronger notions of dominance, which generate false positives,or require expensive dominance checks. In this paper, wepropose two new methods, which do not have these drawbacks.The first method uses an appropriate mapping of a partial order to atotal order, inspired by the lattice theorem and an off-the-shelf skylinealgorithm. The second technique uses an appropriate storageand indexing approach, inspired by column stores, which enablesefficient verification of whether a pair of objects are incompatible.We demonstrate that both our methods are up to an order of magnitudemore efficient than previous work and scale well with differentproblem parameters, such as complexity of partial orders.
User Submitted?: No
Authors: Kao, Ben; Mamoulis, Nikos; Cheung, David W.; Zhang, Shiming
Periodical (Full): Proceedings of the VLDB Endowment
Issue: 1
Volume: 3
Pages: 1255-1266
Data Collections: IPUMS USA
Topics: Other
Countries: