2026-08-17T12:52:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7869 2024-03-06T10:41:15Z ddc:004 open_access

Permuting and Batched Geometric Lower Bounds in the I/O Model Afshani, Peyman van Duijn, Ingo I/O Model Batched Geometric Queries Lower Bounds Permuting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peyman Afshani and Ingo van Duijn 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.2 urn:nbn:de:0030-drops-78695 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.2 eng https://creativecommons.org/licenses/by/3.0/legalcode