Output-sensitive skyline algorithms in external memory
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited

Other information
AbstractThis paper presents new results in external memory for finding the skyline (a.k.a. maxima) of N points in d-dimensional space. The state of the art uses O((N/B) logM/Bd-2(N/B)) I/Os for fixed d ≥ 3, and O((N/B) logM/B(N/B)) I/Os for d = 2, where M and B are the sizes (in words) of memory and a disk block, respectively. We give algorithms whose running time depends on the number K of points in the skyline. Specifically, we achieve O((N/B) logM/Bd-2(K/B)) expected cost for fixed d ≥ 3, and O((N/B) logM/B(K/B)) worst-case cost for d = 2. As a side product, we solve two problems both of independent interest. The first one, the M-skyline problem, aims at reporting M arbitrary skyline points, or the entire skyline if its size is at most M. We settle this problem in O(N/B) expected time in any fixed dimensionality d. The second one, the M-pivot problem, is more fundamental: given a set S of N elements drawn from an ordered domain, it outputs M evenly scattered elements (called pivots) from S, namely, S has asymptotically the same number of elements between each pair of consecutive pivots. We give a deterministic algorithm for solving the problem in O(N/B) I/Os. Copyright © SIAM.
All Author(s) ListHu X., Sheng C., Tao Y., Yang Y., Zhou S.
Name of Conference24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013
Start Date of Conference06/01/2013
End Date of Conference08/01/2013
Place of ConferenceNew Orleans, LA
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by ACM-SIAM,
Year2013
Month4
Day16
Pages887 - 900
ISBN9781611972511
LanguagesEnglish-United Kingdom

Last updated on 2020-04-09 at 03:19