Document Open Access Logo

Robust and Adaptive Search

Authors Yann Disser, Stefan Kratsch

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.26.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Yann Disser
Stefan Kratsch

Cite As Get BibTex

Yann Disser and Stefan Kratsch. Robust and Adaptive Search. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.26

Abstract

Binary search finds a given element in a sorted array with an optimal number of log n queries. However, binary search fails even when the array is only slightly disordered or access to its elements is subject to errors. We study the worst-case query complexity of search algorithms that are robust to imprecise queries and that adapt to perturbations of the order of the elements. We give (almost) tight results for various parameters that quantify query errors and that measure array disorder. In particular, we exhibit settings where query complexities of log n + ck, (1+epsilon) log n + ck, and sqrt(cnk)+o(nk) are best-possible for parameter value k, any epsilon > 0, and constant c.

Subject Classification

Keywords
  • searching
  • robustness
  • adaptive algorithms
  • memory faults
  • array disorder

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Arne Andersson, Torben Hagerup, Johan Håstad, and Ola Petersson. Tight bounds for searching a sorted array of strings. SIAM J. Comput., 30(5):1552-1578, 2000. URL: http://dx.doi.org/10.1137/S0097539797329889.
  2. Stanislav Angelov, Keshav Kunal, and Andrew McGregor. Sorting and selection with random costs. In Proceedings of the 8th Latin American Symposium on Theoretical Informatics (LATIN), pages 48-59, 2008. URL: http://dx.doi.org/10.1007/978-3-540-78773-0_5.
  3. Javed A. Aslam and Aditi Dhagat. Searching in the presence of linearly bounded errors. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing (STOC), pages 486-493, 1991. Google Scholar
  4. Jérémy Barbay and Gonzalo Navarro. On compressing permutations and adaptive sorting. Theor. Comput. Sci., 513:109-123, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2013.10.019.
  5. Therese C. Biedl, Timothy M. Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai J. Golin, James A. King, and J. Ian Munro. Fun-sort-or the chaos of unordered binary search. Discrete Applied Mathematics, 144(3):231-236, 2004. URL: http://dx.doi.org/10.1016/j.dam.2004.01.003.
  6. Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, and Alessandro Provetti. Adaptive search over sorted sets. J. Discrete Algorithms, 30:128-133, 2015. URL: http://dx.doi.org/10.1016/j.jda.2014.12.007.
  7. Ryan S. Borgstrom and S. Rao Kosaraju. Comparison-based search in the presence of errors. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pages 130-136, 1993. URL: http://dx.doi.org/10.1145/167088.167129.
  8. Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, and Andrew Chi-Chih Yao. Efficient searching using partial ordering. Inf. Process. Lett., 12(2):71-75, 1981. URL: http://dx.doi.org/10.1016/0020-0190(81)90005-3.
  9. Gerth Stølting Brodal, Rolf Fagerberg, Irene Finocchi, Fabrizio Grandoni, Giuseppe F. Italiano, Allan Grønlund Jørgensen, Gabriel Moruz, and Thomas Mølhave. Optimal resilient dynamic dictionaries. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA), pages 347-358, 2007. Google Scholar
  10. F. Warren Burton and Gilbert N. Lewis. A robust variation of interpolation search. Inf. Process. Lett., 10(4/5):198-201, 1980. URL: http://dx.doi.org/10.1016/0020-0190(80)90139-8.
  11. Ferdinando Cicalese. Fault-Tolerant Search Algorithms - Reliable Computation with Unreliable Information. Springer, 2013. URL: http://dx.doi.org/10.1007/978-3-642-17327-1.
  12. Aditi Dhagat, Peter Gacs, and Peter Winkler. On playing "twenty questions" with a liar. In Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 16-22, 1992. Google Scholar
  13. Vladimir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Comput. Surv., 24(4):441-476, 1992. URL: http://dx.doi.org/10.1145/146370.146381.
  14. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with noisy information. SIAM Journal on Computing, 23(5):1001-1018, 1994. Google Scholar
  15. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci., 410(44):4457-4470, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.07.026.
  16. Irene Finocchi and Giuseppe F. Italiano. Sorting and searching in faulty memories. Algorithmica, 52(3):309-332, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9088-4.
  17. Gianni Franceschini and Roberto Grossi. No sorting? better searching! ACM Transactions on Algorithms, 4(1), 2008. URL: http://dx.doi.org/10.1145/1328911.1328913.
  18. Michael L. Fredman. The number of tests required to search an unordered table. Inf. Process. Lett., 87(2):85-88, 2003. URL: http://dx.doi.org/10.1016/S0020-0190(03)00260-6.
  19. Anupam Gupta and Amit Kumar. Sorting and selection with structured costs. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, (FOCS), pages 416-425, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959916.
  20. Donald E. Knuth. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley, 1973. Google Scholar
  21. Philip M. Long. Sorting and searching with a faulty comparison oracle. Technical Report UCSC-CRL-92-15, University of California at Santa Cruz, 1992. Google Scholar
  22. Harry G. Mairson. Average case lower bounds on the construction and searching of partial orders. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 303-311, 1985. URL: http://dx.doi.org/10.1109/SFCS.1985.13.
  23. Kurt Mehlhorn. Sorting presorted files. In Proceedings of the 4th GI-Conference on Theoretical Computer Science, pages 199-212, 1979. URL: http://dx.doi.org/10.1007/3-540-09118-1_22.
  24. Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, volume 1 of EATCS Monographs on Theoretical Computer Science. Springer, 1984. URL: http://www.mpi-sb.mpg.de/~mehlhorn/DatAlgbooks.html.
  25. S. Muthukrishnan. On optimal strategies for searching in the presence of errors. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 680-689, 1994. Google Scholar
  26. Andrzej Pelc. Searching with known error probability. Theoretical Computer Science, 63(2):185-202, 1989. Google Scholar
  27. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theoretical Computer Science, 270(1-2):71-109, 2002. Google Scholar
  28. Ola Petersson and Alistair Moffat. A framework for adaptive sorting. Discrete Applied Mathematics, 59(2):153-179, 1995. URL: http://dx.doi.org/10.1016/0166-218X(93)E0160-Z.
  29. Erez Petrank and Guy N. Rothblum. Selection from structured data sets. Electronic Colloquium on Computational Complexity (ECCC), 2004. TR04-085. URL: http://eccc.hpi-web.de/eccc-reports/2004/TR04-085/index.html.
  30. Ronald L. Rivest, Albert R. Meyer, Daniel J. Kleitman, Karl Winklmann, and Joel Spencer. Coping with errors in binary search procedures. Journal of Computer and System Sciences, 20(3):396-404, 1980. Google Scholar
  31. Robert Sedgewick. Algorithms in C++ - Parts 1-4: Fundamentals, Data Structures, Sorting, Searching. Addison-Wesley-Longman, 1998. Google Scholar
  32. Andrew Chi-Chih Yao. Should tables be sorted? J. ACM, 28(3):615-628, 1981. URL: http://dx.doi.org/10.1145/322261.322274.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact