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.ISAAC.2019.60
URN: urn:nbn:de:0030-drops-115568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11556/
Epa, Narthana S. ;
Gan, Junhao ;
Wirth, Anthony
Result-Sensitive Binary Search with Noisy Information
Abstract
We describe new algorithms for the predecessor problem in the Noisy Comparison Model. In this problem, given a sorted list L of n (distinct) elements and a query q, we seek the predecessor of q in L: denoted by u, the largest element less than or equal to q. In the Noisy Comparison Model, the result of a comparison between two elements is non-deterministic. Moreover, multiple comparisons of the same pair of elements might have different results: each is generated independently, and is correct with probability p > 1/2. Given an overall error tolerance Q, the cost of an algorithm is measured by the total number of noisy comparisons; these must guarantee the predecessor is returned with probability at least 1 - Q. Feige et al. showed that predecessor queries can be answered by a modified binary search with Theta(log (n/Q)) noisy comparisons.
We design result-sensitive algorithms for answering predecessor queries. The query cost is related to the index, k, of the predecessor u in L. Our first algorithm answers predecessor queries with O(log ((log^{*(c)} n)/Q) + log (k/Q)) noisy comparisons, for an arbitrarily large constant c. The function log^{*(c)} n iterates c times the iterated-logarithm function, log^* n. Our second algorithm is a genuinely result-sensitive algorithm whose expected query cost is bounded by O(log (k/Q)), and is guaranteed to terminate after at most O(log((log n)/Q)) noisy comparisons.
Our results strictly improve the state-of-the-art bounds when k is in omega(1) intersected with o(n^epsilon), where epsilon > 0 is some constant. Moreover, we show that our result-sensitive algorithms immediately improve not only predecessor-query algorithms, but also binary-search-like algorithms for solving key applications.
BibTeX - Entry
@InProceedings{epa_et_al:LIPIcs:2019:11556,
author = {Narthana S. Epa and Junhao Gan and Anthony Wirth},
title = {{Result-Sensitive Binary Search with Noisy Information}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {60:1--60:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11556},
URN = {urn:nbn:de:0030-drops-115568},
doi = {10.4230/LIPIcs.ISAAC.2019.60},
annote = {Keywords: Fault-tolerant search, random walks, noisy comparisons, predecessor queries}
}
|
Keywords: |
|
Fault-tolerant search, random walks, noisy comparisons, predecessor queries |
|
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
28.11.2019 |
