License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.2
URN: urn:nbn:de:0030-drops-78695
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7869/
Go to the corresponding LIPIcs Volume Portal

Afshani, Peyman ; van Duijn, Ingo

Permuting and Batched Geometric Lower Bounds in the I/O Model

pdf-format:
LIPIcs-ESA-2017-2.pdf (0.5 MB)

Abstract

We study permuting and batched orthogonal geometric reporting problems in the External Memory Model (EM), assuming indivisibility of the input records.
Our main results are twofold. First, we prove a general simulation result that essentially shows that any permutation algorithm (resp. duplicate removal algorithm) that does alpha*N/B I/Os (resp. to remove a fraction of the existing duplicates) can be simulated with an algorithm that does alpha phases where each phase reads and writes each element once, but using a factor alpha smaller block size.

Second, we prove two lower bounds for batched rectangle stabbing and batched orthogonal range reporting queries. Assuming a short cache, we prove very high lower bounds that currently are not possible with the existing techniques under the tall cache assumption.

BibTeX - Entry

@InProceedings{afshani_et_al:LIPIcs:2017:7869,
  author =	{Peyman Afshani and Ingo van Duijn},
  title =	{{Permuting and Batched Geometric Lower Bounds in the I/O Model}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{2:1--2:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7869},
  URN =		{urn:nbn:de:0030-drops-78695},
  doi =		{10.4230/LIPIcs.ESA.2017.2},
  annote =	{Keywords: I/O Model, Batched Geometric Queries, Lower Bounds, Permuting}
}

Keywords: I/O Model, Batched Geometric Queries, Lower Bounds, Permuting
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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