Can I read Efficient Skyline Evaluation Over Partially Ordered Domains on EtoBox?

Efficient Skyline Evaluation Over Partially Ordered Domains by Zhang, Shiming; Mamoulis, Nikos; Cheung, David W.; Kao, Ben is a Computer Science article available to read on EtoBox.

What is Efficient Skyline Evaluation Over Partially Ordered Domains about?

Although there has been a considerable body of work on skyline evaluation in multidimensional data with totally ordered attribute domains, there are only a few methods that consider attributes with partially ordered domains. Existing work maps each partially ordered domain to a total order and then adapts algorithms for totally-ordered domains to solve the problem. Nevertheless these methods either use stronger notions of dominance, which generate false positives, or require expensive dominance checks. In this paper, we propose two new methods, which do not have these drawbacks. The first method uses an appropriate mapping of a partial order to a total order, inspired by the lattice theorem and an off-the-shelf skyline algorithm. The second technique uses an appropriate storage and indexing approach, inspired by column stores, which enables efficient verification of whether a pair of objects are incompatible. We demonstrate that both our methods are up to an order of magnitude more efficient than previous work and scale well with different problem parameters, such as complexity of partial orders.

Who reads Efficient Skyline Evaluation Over Partially Ordered Domains?

Author

Zhang, Shiming; Mamoulis, Nikos; Cheung, David W.; Kao, Ben

Publisher

Very Large Data Base Endowment Inc. (ISSN 2150-8097)

Published

2010

Language

EN

Field

Computer Science (Physical Sciences)