License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.22
URN: urn:nbn:de:0030-drops-136674
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13667/
Go to the corresponding LIPIcs Volume Portal

Chan, Timothy M. ; Rahul, Saladi

Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points

pdf-format:
LIPIcs-STACS-2021-22.pdf (0.7 MB)

Abstract

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 log^{O(1)}n) space and O(log^dn) 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.

BibTeX - Entry

@InProceedings{chan_et_al:LIPIcs.STACS.2021.22,
  author =	{Chan, Timothy M. and Rahul, Saladi},
  title =	{{Simple Multi-Pass Streaming Algorithms for Skyline Points and Extreme Points}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13667},
  URN =		{urn:nbn:de:0030-drops-136674},
  doi =		{10.4230/LIPIcs.STACS.2021.22},
  annote =	{Keywords: multi-pass streaming algorithms, skyline, convex hull, extreme points, randomized algorithms}
}

Keywords: multi-pass streaming algorithms, skyline, convex hull, extreme points, randomized algorithms
Collection: 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Issue Date: 2021
Date of publication: 10.03.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI