{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:24:51Z","timestamp":1725549891496},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_23","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"238-248","source":"Crossref","is-referenced-by-count":2,"title":["Predecessor Queries in Constant Time?"],"prefix":"10.1007","author":[{"given":"Marek","family":"Karpinski","sequence":"first","affiliation":[]},{"given":"Yakov","family":"Nekrich","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"23_CR1","first-page":"1259","volume":"146","author":"G.M. Adelson-Velskii","year":"1962","unstructured":"Adelson-Velskii, G.M., Landis, E.M.: An algorithm for the organization of information. Dokladi Akademii Nauk SSSR\u00a0146(2), 1259\u20131262 (1962)","journal-title":"Dokladi Akademii Nauk SSSR"},{"issue":"3","key":"23_CR2","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0019-9958(84)80015-7","volume":"63","author":"M. Ajtai","year":"1984","unstructured":"Ajtai, M., Fredman, M.L., Koml\u00f2s, J.: Hash Functions for Priority Queues. Information and Control\u00a063(3), 217\u2013225 (1984)","journal-title":"Information and Control"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: STOC 2001, pp. 476\u2013482 (2001)","DOI":"10.1145\/380752.380842"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Andersson, A.: Sublogarithmic Searching without Multiplications. In: FOCS 1995, pp. 655\u2013663 (1995)","DOI":"10.1109\/SFCS.1995.492667"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Andersson, A.: Faster Deterministic Sorting and Searching in Linear Space. In: FOCS 1996, pp. 135\u2013141 (1996)","DOI":"10.1109\/SFCS.1996.548472"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? In: STOC 1995, pp. 427\u2013436 (1995)","DOI":"10.1145\/225058.225173"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Andersson, A., Thorup, M.: Tight(er) worst-case bounds on dynamic searching and priority queues. In: STOC 2000, pp. 335\u2013342 (2000)","DOI":"10.1145\/335305.335344"},{"key":"23_CR8","unstructured":"Andersson, A., Thorup, M.: Dynamic Ordered Sets with Exponential Search Trees, The Computing Research Repository (CoRR), cs.DS\/0210006: (2002), Available at http:\/\/arxiv.org\/abs\/cs.DS\/0210006"},{"issue":"1","key":"23_CR9","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.E.: Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci.\u00a065(1), 38\u201372 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR10","unstructured":"Brodnik, A., Carlsson, S., Karlsson, J., Munro, J.I.: Worst case constant time priority queue. In: SODA 2001, pp. 523\u2013528 (2001)"},{"issue":"2","key":"23_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"Carter, L., Wegman, M.N.: Universal Classes of Hash Functions. J. Comput. Syst. Sci.\u00a018(2), 143\u2013154 (1979)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"23_CR12","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett.\u00a06(3), 80\u201382 (1977)","journal-title":"Inf. Process. Lett."},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"},{"issue":"3","key":"23_CR14","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1016\/S0022-0000(05)80064-9","volume":"48","author":"M.L. Fredman","year":"1994","unstructured":"Fredman, M.L., Willard, D.E.: Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths. J. Comput. Syst. Sci.\u00a048(3), 533\u2013551 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"23_CR15","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and Searching on the Word RAM. In: STACS 1998, pp. 366\u2013398 (1998)","DOI":"10.1007\/BFb0028575"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Han, Y.: Deterministic sorting in O(n log log n) time and linear space. In: STOC 2002, pp. 602\u2013608 (2002)","DOI":"10.1145\/509907.509993"},{"key":"23_CR17","doi-asserted-by":"crossref","unstructured":"Gum, B., Lipton, R.: Cheaper by the Dozen: Batched Algorithms. In: 1st SIAM International Conference on Data Mining (2001), Available at http:\/\/www.math.grin.edu\/~gum\/papers\/batched\/","DOI":"10.1137\/1.9781611972719.23"},{"key":"23_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69672-5","volume-title":"Data Structures and Algorithms 1: Sorting and Searching","author":"K. Mehlhorn","year":"1984","unstructured":"Mehlhorn, K.: Data Structures and Algorithms 1: Sorting and Searching. Springer, Heidelberg (1984)"},{"key":"23_CR19","unstructured":"Paul, W.J., Simon, S.: Decision Trees and Random Access Machines. In: International Symposium on Logik and Algorithmic, Z\u00fcrich, pp. 331\u2013340 (1980)"},{"issue":"2","key":"23_CR20","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N). Inf. Process. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"23_CR21","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1016\/0022-0000(84)90020-5","volume":"28","author":"D.E. Willard","year":"1984","unstructured":"Willard, D.E.: New Trie Data Structures Which Support Very Fast Search Operations. J. Comput. Syst. Sci.\u00a028(3), 379\u2013394 (1984)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"23_CR22","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C.-C. Yao","year":"1981","unstructured":"Yao, A.C.-C.: Should Tables Be Sorted? J. ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:50:40Z","timestamp":1605642640000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/11561071_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}