{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:57Z","timestamp":1781078217186,"version":"3.54.1"},"reference-count":101,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T00:00:00Z","timestamp":1601251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Millennium Institute for Foundational Research on Data (IMFD), Chile, and by Project CONICYT","award":["3190550"],"award-info":[{"award-number":["3190550"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Comput. Surv."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>predecessor<\/jats:italic>\n            problem is a key component of the fundamental sorting-and-searching core of algorithmic problems. While binary search is the optimal solution in the comparison model, more realistic machine models on integer sets open the door to a rich universe of data structures, algorithms, and lower bounds. In this article, we review the evolution of the solutions to the predecessor problem, focusing on the important algorithmic ideas, from the famous data structure of van Emde Boas to the optimal results of Patrascu and Thorup. We also consider lower bounds, variants, and special cases, as well as the remaining open questions.\n          <\/jats:p>","DOI":"10.1145\/3409371","type":"journal-article","created":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T10:45:25Z","timestamp":1601289925000},"page":"1-35","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Predecessor Search"],"prefix":"10.1145","volume":"53","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[{"name":"Millennium Institute for Foundational Research on Data (IMFD), Department of Computer Science, University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Javiel","family":"Rojas-Ledesma","sequence":"additional","affiliation":[{"name":"Millennium Institute for Foundational Research on Data (IMFD), Department of Computer Science, University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,9,28]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Afshani Peyman","unstructured":"Peyman Afshani , Cheng Sheng , Yufei Tao , and Bryan T. Wilkinson . 2014. Concurrent range reporting in two-dimensional space . In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914) , Chandra Chekuri (Ed.). SIAM, 983--994. Peyman Afshani, Cheng Sheng, Yufei Tao, and Bryan T. Wilkinson. 2014. Concurrent range reporting in two-dimensional space. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914), Chandra Chekuri (Ed.). SIAM, 983--994."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205011"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126797"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80015-7"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380842"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743504"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796252"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875514"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1580"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/646247.684874"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC\u201997)","author":"Arge Lars","year":"1997","unstructured":"Lars Arge , Paolo Ferragina , Roberto Grossi , and Jeffrey Scott Vitter . 1997 . On sorting strings in external memory . In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC\u201997) , Frank Thomson Leighton and Peter W. Shor (Eds.). ACM, 540--548. Lars Arge, Paolo Ferragina, Roberto Grossi, and Jeffrey Scott Vitter. 1997. On sorting strings in external memory. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC\u201997), Frank Thomson Leighton and Peter W. Shor (Eds.). ACM, 540--548."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1822"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.12.011"},{"key":"e_1_2_2_16_1","volume-title":"Encyclopedia of Algorithms. 1605--1611.","author":"Belazzougui Djamal","unstructured":"Djamal Belazzougui . 2016. Predecessor search, string algorithms and data structures . In Encyclopedia of Algorithms. 1605--1611. Djamal Belazzougui. 2016. Predecessor search, string algorithms and data structures. In Encyclopedia of Algorithms. 1605--1611."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496856"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_37"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16321-0_15"},{"key":"e_1_2_2_20_1","unstructured":"Djamal Belazzougui Paolo Boldi and Sebastiano Vigna. 2012. Predecessor search with distance-sensitive query time. CoRR abs\/1209.5441.  Djamal Belazzougui Paolo Boldi and Sebastiano Vigna. 2012. Predecessor search with distance-sensitive query time. CoRR abs\/1209.5441."},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom\u201918)","author":"Belazzougui Djamal","unstructured":"Djamal Belazzougui , Alexis C. Kaporis , and Paul G. Spirakis . 2018. Random input helps searching predecessors . In Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom\u201918) . 106--115. Djamal Belazzougui, Alexis C. Kaporis, and Paul G. Spirakis. 2018. Random input helps searching predecessors. In Proceedings of the 11th International Conference on Random and Exhaustive Generation of Combinatorial Structures (GASCom\u201918). 106--115."},{"key":"e_1_2_2_22_1","article-title":"Optimal lower and upper bounds for representing sequences","volume":"11","author":"Belazzougui Djamal","year":"2015","unstructured":"Djamal Belazzougui and Gonzalo Navarro . 2015 . Optimal lower and upper bounds for representing sequences . ACM Trans. Algor. 11 , 4 (2015), 31:1--31:21. Djamal Belazzougui and Gonzalo Navarro. 2015. Optimal lower and upper bounds for representing sequences. ACM Trans. Algor. 11, 4 (2015), 31:1--31:21.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_10"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u201906)","author":"Bender Michael A.","unstructured":"Michael A. Bender , Martin Farach-Colton , and Bradley C. Kuszmaul . 2006. Cache-oblivious string B-trees . In Proceedings of the 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u201906) , Stijn Vansummeren (Ed.). ACM, 233--242. Michael A. Bender, Martin Farach-Colton, and Bradley C. Kuszmaul. 2006. Cache-oblivious string B-trees. In Proceedings of the 25th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u201906), Stijn Vansummeren (Ed.). ACM, 233--242."},{"key":"e_1_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Mayank Goswami Dzejla Medjedovic Pablo Montes and Kostas Tsichlas. 2020. Batched predecessor and sorting with size-priced information in external memory. CoRR abs\/2004.13197. arxiv:2004.13197.  Michael A. Bender Mayank Goswami Dzejla Medjedovic Pablo Montes and Kostas Tsichlas. 2020. Batched predecessor and sorting with size-priced information in external memory. CoRR abs\/2004.13197. arxiv:2004.13197.","DOI":"10.1007\/978-3-030-61792-9_13"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214041"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917)","author":"Bille Philip","year":"2017","unstructured":"Philip Bille , Mikko Berggren Ettienne , Inge Li G\u00f8rtz , and Hjalte Wedel Vildh\u00f8j . 2017 . Time-space trade-offs for Lempel-Ziv compressed indexing . In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917) . 16:1--16:17. Philip Bille, Mikko Berggren Ettienne, Inge Li G\u00f8rtz, and Hjalte Wedel Vildh\u00f8j. 2017. Time-space trade-offs for Lempel-Ziv compressed indexing. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917). 16:1--16:17."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.08.009"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917)","author":"Bille Philip","year":"2017","unstructured":"Philip Bille , Inge Li G\u00f8rtz , and Frederik Rye Skjoldjensen . 2017 . Deterministic indexing for packed strings . In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917) . 6:1--6:11. Philip Bille, Inge Li G\u00f8rtz, and Frederik Rye Skjoldjensen. 2017. Deterministic indexing for packed strings. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917). 6:1--6:11."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.01.002"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0146-7"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0023445"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.12"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2483699.2483702"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998196.1998198"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Chan Timothy M.","year":"2018","unstructured":"Timothy M. Chan , Yakov Nekrich , Saladi Rahul , and Konstantinos Tsakalidis . 2018 . Orthogonal point location and rectangle stabbing queries in 3D . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . 31:1--31:14. Timothy M. Chan, Yakov Nekrich, Saladi Rahul, and Konstantinos Tsakalidis. 2018. Orthogonal point location and rectangle stabbing queries in 3D. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). 31:1--31:14."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068669X"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917)","author":"Timothy","unstructured":"Timothy M. Chan and Konstantinos Tsakalidis. 2017. Dynamic orthogonal range searching on the RAM, revisited . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917) . 28:1--28:13. Timothy M. Chan and Konstantinos Tsakalidis. 2017. Dynamic orthogonal range searching on the RAM, revisited. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG\u201917). 28:1--28:13."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840440"},{"key":"e_1_2_2_42_1","first-page":"12","article-title":"Minimal indices for predecessor search. Info","volume":"240","author":"Cohen Sarel","year":"2015","unstructured":"Sarel Cohen , Amos Fiat , Moshik Hershcovitch , and Haim Kaplan . 2015 . Minimal indices for predecessor search. Info . Comput. 240 (2015), 12 -- 30 . Sarel Cohen, Amos Fiat, Moshik Hershcovitch, and Haim Kaplan. 2015. Minimal indices for predecessor search. Info. Comput. 240 (2015), 12--30.","journal-title":"Comput."},{"key":"e_1_2_2_43_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , and Clifford Stein . 2009. Introduction to Algorithms ( 3 rd ed.). MIT Press . Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms (3rd ed.). MIT Press.","edition":"3"},{"key":"e_1_2_2_44_1","volume-title":"Proceedings of the 6th Workshop on Algorithm\u00a0Engineering and Experiments (ALENEX\u201904)","author":"Dementiev Roman","year":"2004","unstructured":"Roman Dementiev , Lutz Kettner , Jens Mehnert , and Peter Sanders . 2004 . Engineering a sorted list data structure for 32 bit key . In Proceedings of the 6th Workshop on Algorithm\u00a0Engineering and Experiments (ALENEX\u201904) . 142--151. Roman Dementiev, Lutz Kettner, Jens Mehnert, and Peter Sanders. 2004. Engineering a sorted list data structure for 32 bit key. In Proceedings of the 6th Workshop on Algorithm\u00a0Engineering and Experiments (ALENEX\u201904). 142--151."},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_31"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_2_47_1","volume-title":"On the Number of Bits Required to Implement an Associative Memory","author":"Fano Robert Mario","unstructured":"Robert Mario Fano . 1971. On the Number of Bits Required to Implement an Associative Memory . Massachusetts Institute of Technology , Project MAC. Robert Mario Fano. 1971. On the Number of Bits Required to Implement an Associative Memory. Massachusetts Institute of Technology, Project MAC."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_14"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80064-9"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909)","author":"Grossi Roberto","unstructured":"Roberto Grossi , Alessio Orlandi , Rajeev Raman , and S. Srinivasa Rao . 2009. More haste, less waste: Lowering the redundancy in fully indexable dictionaries . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909) . 517--528. Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. 2009. More haste, less waste: Lowering the redundancy in fully indexable dictionaries. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909). 517--528."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/646513.695510"},{"key":"e_1_2_2_56_1","first-page":"81","article-title":"Improved fast integer sorting in linear space. Info","volume":"170","author":"Han Yijie","year":"2001","unstructured":"Yijie Han . 2001 . Improved fast integer sorting in linear space. Info . Comput. 170 , 1 (2001), 81 -- 94 . Yijie Han. 2001. Improved fast integer sorting in linear space. Info. Comput. 170, 1 (2001), 81--94.","journal-title":"Comput."},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.09.001"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00626-0"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652131"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506312"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.03.004"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_23"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90023-3"},{"key":"e_1_2_2_64_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1973. The Art of Computer Programming, Volume III: Sorting and Searching . Addison-Wesley . Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_2_65_1","volume-title":"Notes on the van Emde Boas Construction of Priority Deques: An Instructive Use of Recursion. Classroom notes","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1977. Notes on the van Emde Boas Construction of Priority Deques: An Instructive Use of Recursion. Classroom notes . Stanford University . Donald E. Knuth. 1977. Notes on the van Emde Boas Construction of Priority Deques: An Instructive Use of Recursion. Classroom notes. Stanford University."},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.79"},{"key":"e_1_2_2_67_1","volume-title":"Introduction to the Design and Analysis of Algorithms","author":"Levitin A.","unstructured":"A. Levitin . 2007. Introduction to the Design and Analysis of Algorithms ( 2 nd ed.). Addison-Wesley . A. Levitin. 2007. Introduction to the Design and Analysis of Algorithms (2nd ed.). Addison-Wesley.","edition":"2"},{"key":"e_1_2_2_68_1","unstructured":"Mingmou Liu and Huacheng Yu. 2020. Lower bound for succinct range minimum query. CoRR abs\/2004.05738.  Mingmou Liu and Huacheng Yu. 2020. Lower bound for succinct range minimum query. CoRR abs\/2004.05738."},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90022-P"},{"key":"e_1_2_2_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174139"},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195415"},{"key":"e_1_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703436722"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_2_2_75_1","volume-title":"Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201996)","author":"Munro J. Ian","year":"1996","unstructured":"J. Ian Munro . 1996 . Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201996) . 37--42. J. Ian Munro. 1996. Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201996). 37--42."},{"key":"e_1_2_2_76_1","volume-title":"Comparing integer data structures for 32- and 64-bit keys. ACM J. Exper. Algor. 15","author":"Nash Nicholas","year":"2010","unstructured":"Nicholas Nash and David Gregg . 2010. Comparing integer data structures for 32- and 64-bit keys. ACM J. Exper. Algor. 15 ( 2010 ). Nicholas Nash and David Gregg. 2010. Comparing integer data structures for 32- and 64-bit keys. ACM J. Exper. Algor. 15 (2010)."},{"key":"e_1_2_2_78_1","volume-title":"Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Patrascu Mihai","year":"2008","unstructured":"Mihai Patrascu . 2008 . Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908) . 305--313. Mihai Patrascu. 2008. Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201908). 305--313."},{"key":"e_1_2_2_79_1","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904)","author":"Patrascu Mihai","unstructured":"Mihai Patrascu and Erik D. Demaine . 2004. Tight bounds for the partial-sums problem . In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904) , J. Ian Munro (Ed.). SIAM, 20--29. Mihai Patrascu and Erik D. Demaine. 2004. Tight bounds for the partial-sums problem. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201904), J. Ian Munro (Ed.). SIAM, 20--29."},{"key":"e_1_2_2_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447256"},{"key":"e_1_2_2_81_1","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906)","author":"Patrascu Mihai","year":"2006","unstructured":"Mihai Patrascu and Mikkel Thorup . 2006 . Time-space trade-offs for predecessor search . In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906) . 232--240. Mihai Patrascu and Mikkel Thorup. 2006. Time-space trade-offs for predecessor search. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC\u201906). 232--240."},{"key":"e_1_2_2_82_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907)","author":"Patrascu Mihai","year":"2007","unstructured":"Mihai Patrascu and Mikkel Thorup . 2007 . Randomization does not help searching predecessors . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907) . 555--564. Mihai Patrascu and Mikkel Thorup. 2007. Randomization does not help searching predecessors. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201907). 555--564."},{"key":"e_1_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_2_2_84_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Patrascu Mihai","year":"2010","unstructured":"Mihai Patrascu and Emanuele Viola . 2010 . Cell-probe lower bounds for succinct partial sums . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 117--122. Mihai Patrascu and Emanuele Viola. 2010. Cell-probe lower bounds for succinct partial sums. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 117--122."},{"key":"e_1_2_2_85_1","volume-title":"Hennessy","author":"Patterson David A.","year":"2012","unstructured":"David A. Patterson and John L . Hennessy . 2012 . Computer Organization and Design\u2014The Hardware\/Software Interface (5th ed.). Academic Press . David A. Patterson and John L. Hennessy. 2012. Computer Organization and Design\u2014The Hardware\/Software Interface (5th ed.). Academic Press."},{"key":"e_1_2_2_86_1","first-page":"331","article-title":"Decision trees and random access machines","volume":"30","author":"Paul W.","year":"1980","unstructured":"W. Paul and Janos Simon . 1980 . Decision trees and random access machines . Logic Algor. 30 (1980), 331 -- 340 . W. Paul and Janos Simon. 1980. Decision trees and random access machines. Logic Algor. 30 (1980), 331--340.","journal-title":"Logic Algor."},{"key":"e_1_2_2_87_1","volume-title":"Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917)","author":"Pibiri Giulio Ermanno","year":"2017","unstructured":"Giulio Ermanno Pibiri and Rossano Venturini . 2017 . Dynamic Elias-Fano representation . In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917) . 30:1--30:14. Giulio Ermanno Pibiri and Rossano Venturini. 2017. Dynamic Elias-Fano representation. In Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM\u201917). 30:1--30:14."},{"key":"e_1_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_2_89_1","doi-asserted-by":"publisher","DOI":"10.5555\/647258.720797"},{"key":"e_1_2_2_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_2_91_1","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP\u201908)","author":"Ruzic Milan","year":"2008","unstructured":"Milan Ruzic . 2008 . Constructing efficient dictionaries in close to sorting time . In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP\u201908) . 84--95. Milan Ruzic. 2008. Constructing efficient dictionaries in close to sorting time. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP\u201908). 84--95."},{"key":"e_1_2_2_92_1","article-title":"Making deterministic signatures quickly","volume":"5","author":"Ruzic Milan","year":"2009","unstructured":"Milan Ruzic . 2009 . Making deterministic signatures quickly . ACM Trans. Algor. 5 , 3 (2009), 26:1--26:26. Milan Ruzic. 2009. Making deterministic signatures quickly. ACM Trans. Algor. 5, 3 (2009), 26:1--26:26.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_2_93_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.016"},{"key":"e_1_2_2_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808752"},{"key":"e_1_2_2_96_1","volume-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998)","author":"Thorup Mikkel","year":"1998","unstructured":"Mikkel Thorup . 1998 . Faster deterministic sorting and priority queues in linear space . In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998) . 550--555. Mikkel Thorup. 1998. Faster deterministic sorting and priority queues in linear space. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201998). 550--555."},{"key":"e_1_2_2_97_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Thorup Mikkel","year":"2003","unstructured":"Mikkel Thorup . 2003 . On AC0 implementations of fusion trees and atomic heaps . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903) . 699--707. Mikkel Thorup. 2003. On AC0 implementations of fusion trees and atomic heaps. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 699--707."},{"key":"e_1_2_2_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314692"},{"key":"e_1_2_2_99_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(77)90031-X"},{"key":"e_1_2_2_100_1","volume-title":"Proceedings of the 2nd International Symposium on Computing in Informatics and Mathematics (ICSIM\u201913)","author":"van Emde Boas Peter","year":"2013","unstructured":"Peter van Emde Boas . 2013 . Thirty nine years of stratified trees . In Proceedings of the 2nd International Symposium on Computing in Informatics and Mathematics (ICSIM\u201913) . 1--14. Peter van Emde Boas. 2013. Thirty nine years of stratified trees. In Proceedings of the 2nd International Symposium on Computing in Informatics and Mathematics (ICSIM\u201913). 1--14."},{"key":"e_1_2_2_101_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683268"},{"key":"e_1_2_2_102_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"},{"key":"e_1_2_2_103_1","doi-asserted-by":"publisher","DOI":"10.5555\/337729.337809"},{"key":"e_1_2_2_104_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3409371","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3409371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:40Z","timestamp":1750199920000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3409371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,28]]},"references-count":101,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3409371"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3409371","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,28]]},"assertion":[{"value":"2019-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}