Scalable skyline computation using a balanced pivot selection technique
SCIE
SCOPUS
- Title
- Scalable skyline computation using a balanced pivot selection technique
- Authors
- Lee, J; Hwang, SW
- Date Issued
- 2014-01
- Publisher
- PERGAMON-ELSEVIER SCIENCE LTD
- Abstract
- Skyline queries have recently received considerable attention as an alternative decision-making operator in the database community. The conventional skyline algorithms have primarily focused on optimizing the dominance of points in order to remove non-skyline points as efficiently as possible, but have neglected to take into account the incomparability of points in order to bypass unnecessary comparisons. To design a scalable skyline algorithm, we first analyze a cost model that copes with both dominance and incomparability, and develop a novel technique to select a cost-optimal point, called a pivot point, that minimizes the number of comparisons in point-based space partitioning. We then implement the proposed pivot point selection technique in the existing sorting- and partitioning-based algorithms. For point insertions/deletions, we also discuss how to maintain the current skyline using a skytree, derived from recursive point-based space partitioning. Furthermore, we design an efficient greedy algorithm for the k representative skyline using the skytree. Experimental results demonstrate that the proposed algorithms are significantly faster than the state-of-the-art algorithms. (C) 2013 Elsevier Ltd. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/13874
- DOI
- 10.1016/J.IS.2013.05.005
- ISSN
- 0306-4379
- Article Type
- Article
- Citation
- INFORMATION SYSTEMS, vol. 39, page. 1 - 21, 2014-01
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.