Efficient Skyline Computation on Big Data
Authors:
- 16 October 2012
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 25 (11) , 2521-2535
Abstract
Skyline is an important operation in many applications to return a set of interesting points from a potentially huge data space. Given a table, the operation finds all tuples that are not dominated by any other tuples. It is found that the existing algorithms cannot process skyline on big data efficiently. This paper presents a novel skyline algorithm SSPL on big data. SSPL utilizes sorted positional index lists which require low space overhead to reduce I/O cost significantly. The sorted positional index list Lj is constructed for each attribute Aj and is arranged in ascending order of Aj. SSPL consists of two phases. In phase 1, SSPL computes scan depth of the involved sorted positional index lists. During retrieving the lists in a round-robin fashion, SSPL performs pruning on any candidate positional index to discard the candidate whose corresponding tuple is not skyline result. Phase 1 ends when there is a candidate positional index seen in all of the involved lists. In phase 2, SSPL exploits the obtained candidate positional indexes to get skyline results by a selective and sequential scan on the table. The experimental results on synthetic and real data sets show that SSPL has a significant advantage over the existing skyline algorithms.Keywords
This publication has 28 references indexed in Scilit:
- Understanding the meaning of a shifted sky: a general framework on extending skyline queryThe VLDB Journal, 2009
- Efficient Skyline Computation in Structured Peer-to-Peer SystemsIEEE Transactions on Knowledge and Data Engineering, 2008
- Efficient Processing of Metric Skyline QueriesIEEE Transactions on Knowledge and Data Engineering, 2008
- Distributed Skyline Retrieval with Low Bandwidth ConsumptionIEEE Transactions on Knowledge and Data Engineering, 2008
- Online Index Recommendations for High-Dimensional Databases Using Query WorkloadsIEEE Transactions on Knowledge and Data Engineering, 2007
- Efficient Skyline and Top-k Retrieval in SubspacesIEEE Transactions on Knowledge and Data Engineering, 2007
- Algorithms and analyses for maximal vector computationThe VLDB Journal, 2006
- Skyline Cardinality for Relational Processing2004
- Optimal aggregation algorithms for middleware2001
- Bit transposition for very large scientific and statistical databasesAlgorithmica, 1986