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.ESA.2023.96
URN: urn:nbn:de:0030-drops-187497
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18749/
Go to the corresponding LIPIcs Volume Portal

Sroka, Jacek ; Tyszkiewicz, Jerzy

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

pdf-format:
LIPIcs-ESA-2023-96.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/18749},
  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}
}

Keywords: Aggregation over dominated points prefix sums sorting flat map range tree parallel algorithms
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

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