Thorup, Mikkel ;
Zamir, Or ;
Zwick, Uri
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps
Abstract
We consider word RAM data structures for maintaining ordered sets of integers whose select and rank operations are allowed to return approximate results, i.e., ranks, or items whose rank, differ by less than Delta from the exact answer, where Delta=Delta(n) is an error parameter. Related to approximate select and rank is approximate (onedimensional) nearestneighbor. A special case of approximate select queries are approximate min queries. Data structures that support approximate min operations are known as approximate heaps (priority queues). Related to approximate heaps are soft heaps, which are approximate heaps with a different notion of approximation.
We prove the optimality of all the data structures presented, either through matching cellprobe lower bounds, or through equivalences to well studied static problems. For approximate select, rank, and nearestneighbor operations we get matching cellprobe lower bounds. We prove an equivalence between approximate min operations, i.e., approximate heaps, and the static partitioning problem. Finally, we prove an equivalence between soft heaps and the classical sorting problem, on a smaller number of items.
Our results have many interesting and unexpected consequences. It turns out that approximation greatly speeds up some of these operations, while others are almost unaffected. In particular, while select and rank have identical operation times, both in comparisonbased and word RAM implementations, an interesting separation emerges between the approximate versions of these operations in the word RAM model. Approximate select is much faster than approximate rank. It also turns out that approximate min is exponentially faster than the more general approximate select. Next, we show that implementing soft heaps is harder than implementing approximate heaps. The relation between them corresponds to the relation between sorting and partitioning.
Finally, as an interesting byproduct, we observe that a combination of known techniques yields a deterministic word RAM algorithm for (exactly) sorting n items in O(n log log_w n) time, where w is the word length. Even for the easier problem of finding duplicates, the best previous deterministic bound was O(min{n log log n,n log_w n}). Our new unifying bound is an improvement when w is sufficiently large compared with n.
BibTeX  Entry
@InProceedings{thorup_et_al:LIPIcs:2019:10671,
author = {Mikkel Thorup and Or Zamir and Uri Zwick},
title = {{Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {95:195:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10671},
URN = {urn:nbn:de:0030drops106712},
doi = {10.4230/LIPIcs.ICALP.2019.95},
annote = {Keywords: Order queries, word RAM, lower bounds}
}
2019
Keywords: 

Order queries, word RAM, lower bounds 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 