TY - GEN
T1 - Simple multi-pass streaming algorithms for skyline points and extreme points
AU - Chan, Timothy M.
AU - Rahul, Saladi
N1 - Publisher Copyright:
© Timothy M. Chan and Saladi Rahul; licensed under Creative Commons License CC-BY 4.0.
PY - 2021/3/1
Y1 - 2021/3/1
N2 - In this paper, we present simple randomized multi-pass streaming algorithms for fundamental computational geometry problems of finding the skyline (maximal) points and the extreme points of the convex hull. For the skyline problem, one of our algorithm occupies O(h) space and performs O(log n) passes, where h is the number of skyline points. This improves the space bound of the currently best known result by Das Sarma, Lall, Nanongkai, and Xu [VLDB'09] by a logarithmic factor. For the extreme points problem, we present the first non-trivial result for any constant dimension greater than two: an O(h logO(1) n) space and O(logd n) pass algorithm, where h is the number of extreme points. Finally, we argue why randomization seems unavoidable for these problems, by proving lower bounds on the performance of deterministic algorithms for a related problem of finding maximal elements in a poset.
AB - In this paper, we present simple randomized multi-pass streaming algorithms for fundamental computational geometry problems of finding the skyline (maximal) points and the extreme points of the convex hull. For the skyline problem, one of our algorithm occupies O(h) space and performs O(log n) passes, where h is the number of skyline points. This improves the space bound of the currently best known result by Das Sarma, Lall, Nanongkai, and Xu [VLDB'09] by a logarithmic factor. For the extreme points problem, we present the first non-trivial result for any constant dimension greater than two: an O(h logO(1) n) space and O(logd n) pass algorithm, where h is the number of extreme points. Finally, we argue why randomization seems unavoidable for these problems, by proving lower bounds on the performance of deterministic algorithms for a related problem of finding maximal elements in a poset.
KW - Convex hull
KW - Extreme points
KW - Multi-pass streaming algorithms
KW - Randomized algorithms
KW - Skyline
UR - http://www.scopus.com/inward/record.url?scp=85115202358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85115202358&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2021.22
DO - 10.4230/LIPIcs.STACS.2021.22
M3 - Conference contribution
AN - SCOPUS:85115202358
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
A2 - Blaser, Markus
A2 - Monmege, Benjamin
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 38th International Symposium on Theoretical Aspects of Computer Science, STACS 2021
Y2 - 16 March 2021 through 19 March 2021
ER -