Search Results

Documents authored by Tyszkiewicz, Jerzy


Document
Aggregating over Dominated Points by Sorting, Scanning, Zip and Flat Maps

Authors: Jacek Sroka and Jerzy Tyszkiewicz

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)


Abstract
Prefix aggregation operation (also called scan), and its particular case, prefix summation, is an important parallel primitive and enjoys a lot of attention in the research literature. It is also used in many algorithms as one of the steps. Aggregation over dominated points in ℝ^m is a multidimensional generalisation of prefix aggregation. It is also intensively researched, both as a parallel primitive and as a practical problem, encountered in computational geometry, spatial databases and data warehouses. In this paper we show that, for a constant dimension m, aggregation over dominated points in ℝ^m can be computed by O(1) basic operations that include sorting the whole dataset, zipping sorted lists of elements, computing prefix aggregations of lists of elements and flat maps, which expand the data size from initial n to n log^{m-1}n. Thereby we establish that prefix aggregation suffices to express aggregation over dominated points in more dimensions, even though the latter is a far-reaching generalisation of the former. Many problems known to be expressible by aggregation over dominated points become expressible by prefix aggregation, too. We rely on a small set of primitive operations which guarantee an easy transfer to various distributed architectures and some desired properties of the implementation.

Cite as

Jacek Sroka and Jerzy Tyszkiewicz. Aggregating over Dominated Points by Sorting, Scanning, Zip and Flat Maps. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 96:1-96:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{sroka_et_al:LIPIcs.ESA.2023.96,
  author =	{Sroka, Jacek and Tyszkiewicz, Jerzy},
  title =	{{Aggregating over Dominated Points by Sorting, Scanning, Zip and Flat Maps}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{96:1--96:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.96},
  URN =		{urn:nbn:de:0030-drops-187497},
  doi =		{10.4230/LIPIcs.ESA.2023.96},
  annote =	{Keywords: Aggregation over dominated points prefix sums sorting flat map range tree parallel algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail