{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:16:04Z","timestamp":1725664564396},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602200"},{"type":"electronic","value":"9783540447474"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60220-8_87","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:53:35Z","timestamp":1330278815000},"page":"482-493","source":"Crossref","is-referenced-by-count":5,"title":["Tables should be sorted (on random access machines)"],"prefix":"10.1007","author":[{"given":"Faith","family":"Fich","sequence":"first","affiliation":[]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"42_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. Aho","year":"1974","unstructured":"A. Aho, J. Hopcroft, and J. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"A.M. Ben-Amram and Z. Galil, Lower bounds for data structure problems on RAMs. In Proc. 32th IEEE Symposium on Foundations of Computer Science, 1991, pages 622\u2013631.","DOI":"10.1109\/SFCS.1991.185428"},{"key":"42_CR3","volume-title":"Programming Pearls","author":"J.L. Bentley","year":"1986","unstructured":"J.L. Bentley, Programming Pearls. Addison-Wesley, Reading, MA, 1986."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"A. Brodnik and J. Ian Munro, Membership in constant time and minimum space. In Proc. 2nd European Symposium on Algorithms 1994, pages 72\u201381.","DOI":"10.1007\/BFb0049398"},{"key":"42_CR5","first-page":"354","volume":"7","author":"S.A. Cook","year":"1973","unstructured":"S.A. Cook and R.A. Reckhow, Time bounded random access machines. JCSS, vol. 7, 1973, pages 354\u2013375.","journal-title":"JCSS"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0222001","volume":"22","author":"A. Fiat","year":"1993","unstructured":"A. Fiat and M. Naor, Implicit O(1) probe search. SIAM J. Computing vol. 22, 1993, pages 1\u201310.","journal-title":"SIAM J. Computing"},{"key":"42_CR7","doi-asserted-by":"publisher","first-page":"764","DOI":"10.1145\/146585.146591","volume":"39","author":"A. Fiat","year":"1992","unstructured":"A. Fiat, M. Naor, J.P. Schmidt, and A. Seigel, Nonoblivious hashing. J. ACM vol. 39, 1992, pages 764\u2013782.","journal-title":"J. ACM"},{"key":"42_CR8","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"M.L. Fredman, J. Koml\u00f2s, and E. Szemer\u00e9di, Storing a sparse table with O(1) worst case access time. J. ACM, vol. 31, 1984, pages 538\u2013544.","journal-title":"J. ACM"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"M.L. Fredman and M.E. Saks, The cell probe complexity of dynamic data structures. In Proc. 21st Ann. ACM Symp. on Theory of Computing, 1989, pages 345\u2013354.","DOI":"10.1145\/73007.73040"},{"key":"42_CR10","volume-title":"The Art of Computer Programming","author":"D.E. Knuth","year":"1973","unstructured":"D.E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973."},{"key":"42_CR11","doi-asserted-by":"crossref","first-page":"1098","DOI":"10.1017\/S002248120002795X","volume":"53","author":"W. Maass","year":"1988","unstructured":"W. Maass, On the use of inaccessible numbers and order indiscernibles in lower bound arguments for random access machines. J. Symbolic Logic, vol. 53, 1988, pages 1098\u20131109.","journal-title":"J. Symbolic Logic"},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"P.B. Miltersen, N. Nisan, S. Safra, and A. Wigderson, On data structures and asymmetric communication complexity. In Proc. 27th ACM Symposium on Theory of Computing, 1995, to appear.","DOI":"10.1145\/225058.225093"},{"key":"42_CR13","unstructured":"W. Paul and J. Simon, Decision trees and random access machines. In Logic and Algorithmic, monograph no. 30 de l'enseignement math\u00e9matique, Univerist\u00e9 de Gen\u00e8ve, 1982."},{"key":"42_CR14","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"D.D. Sleator","year":"1985","unstructured":"D.D. Sleator and R.E. Tarjan, Self-Adjusting Binary Search Trees. J. ACM, vol. 32, 1985, pages 652\u2013686.","journal-title":"J. ACM"},{"key":"42_CR15","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1145\/359168.359175","volume":"22","author":"R.E. Tarjan","year":"1979","unstructured":"R.E. Tarjan and A.C. Yao, Storing a sparse table. C. ACM, vol. 22, 1979, pages 606\u2013611.","journal-title":"C. ACM"},{"key":"42_CR16","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A.C. Yao","year":"1981","unstructured":"A.C. Yao, Should tables be sorted? J. ACM, vol. 28, 1981, pages 615\u2013628.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60220-8_87.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:33:51Z","timestamp":1619573631000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60220-8_87"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602200","9783540447474"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-60220-8_87","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}