{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:39:27Z","timestamp":1725496767187},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540402053"},{"type":"electronic","value":"9783540448679"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44867-5_7","type":"book-chapter","created":{"date-parts":[[2007,11,30]],"date-time":"2007-11-30T01:34:45Z","timestamp":1196386485000},"page":"81-96","source":"Crossref","is-referenced-by-count":7,"title":["Search Data Structures for Skewed Strings"],"prefix":"10.1007","author":[{"given":"Pilu","family":"Crescenzi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","unstructured":"A. Acharya, H. Zhu, K. Shen. Adaptive algorithms for cache-efficient trie search. Proc. ALENEX 99. Source code in http:\/\/www.cs.rochester.edu\/~kshen , 1999.","DOI":"10.1007\/3-540-48518-X_18"},{"key":"7_CR2","first-page":"1259","volume":"3","author":"G. M. Adelson-Velskii","year":"1962","unstructured":"G. M. Adel\u2019son-Vel\u2019skii and E. M. Landis. An algorithm for the organization of information. Soviet Mathematics Doklady, 3 (1962), 1259\u20131263.","journal-title":"Soviet Mathematics Doklady"},{"key":"7_CR3","unstructured":"Arianna Search Engine, http:\/\/arianna.libero.it ."},{"key":"7_CR4","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/BF00289509","volume":"1","author":"R. Bayer","year":"1972","unstructured":"R. Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica 1 (1972), 290\u2013306.","journal-title":"Acta Informatica"},{"key":"7_CR5","unstructured":"J. L. Bentley and R. Sedgewick. Fast algorithms for sorting and searching strings. SODA 1997, 360\u2013369 ( http:\/\/www.cs.princeton.edu\/~rs\/strings )."},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0214041","volume":"14","author":"S. W. Bent","year":"1985","unstructured":"S. W. Bent, D. D. Sleator and R. E. Tarjan. Biased search trees. SIAM Journal on Computing 14 (1985), 545\u2013568.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"F. Bonchi, F. Giannotti, C. Gozzi, G. Manco, M. Nanni, D. Pedreschi, C. Renso and S. Ruggieri, Web log data warehousing and mining for intelligent web caching. Data and Knowledge Engineering, to appear.","DOI":"10.1016\/S0169-023X(01)00038-6"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1145\/363958.363987","volume":"7","author":"H. A. Clampett","year":"1964","unstructured":"H. A. Clampett. Randomized binary searching with the tree structures. Communications of the ACM 7 (1964), 163\u2013165.","journal-title":"Communications of the ACM"},{"key":"7_CR9","unstructured":"J. Cl\u00e9ment, Ph. Flajolet and B. Vall\u00e9e. The analysis of hybrid trie structures. SODA 1999."},{"key":"7_CR10","doi-asserted-by":"crossref","first-page":"3139","DOI":"10.1002\/j.1538-7305.1983.tb03469.x","volume":"62","author":"J. Feigenbaum","year":"1983","unstructured":"J. Feigenbaum and R. E. Tarjan. Two new kinds of biased search trees. Bell Systems Technical Journal 62 (1983), 3139\u20133158.","journal-title":"Bell Systems Technical Journal"},{"key":"7_CR11","unstructured":"T. F. Gonzalez. The on-line d-dimensional dictionary problem. SODA 1992, 376\u2013385."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"R. Grossi, G. F. Italiano. Efficient techniques for maintaining multidimensional keys in linked data structures. ICALP 1999, 372\u2013381.","DOI":"10.1007\/3-540-48523-6_34"},{"key":"7_CR13","doi-asserted-by":"crossref","unstructured":"R. H. Gueting and H.-P. Kriegel. Multidimensional B-tree: An efficient dynamic file structure for exact match queries. 10th GI Annual Conference, 375\u2013388.","DOI":"10.1007\/978-3-642-67838-7_35"},{"key":"7_CR14","doi-asserted-by":"crossref","unstructured":"L. J. Guibas and R. Sedgewick. A dichromatic framework for balanced trees. FOCS 1978, 8\u201321.","DOI":"10.1109\/SFCS.1978.3"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"D. Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574931"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00288968","volume":"17","author":"S. Huddleston","year":"1982","unstructured":"S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica 17 (1982), 157\u2013184.","journal-title":"Acta Informatica"},{"key":"7_CR17","unstructured":"D. E. Knuth. The Art of computer programming, Vol. 3: Sorting and Searching. Second edition, Addison-Wesley, 1973, 1998."},{"key":"7_CR18","unstructured":"R. Jenkins, http:\/\/burtleburtle.net\/bob\/hash\/ ."},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1137\/0208014","volume":"8","author":"K. Mehlhorn","year":"1979","unstructured":"K. Mehlhorn. Dynamic binary search. SIAM J. on Computing 8 (1979), 175\u2013198.","journal-title":"SIAM J. on Computing"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. Data structures and algorithms:Searching and sorting, Springer 1984.","DOI":"10.1007\/978-3-642-69900-9"},{"key":"7_CR21","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D. R. Morrison","year":"1968","unstructured":"D. R. Morrison. PATRICIA \u2014 Practical Algorithm To Retrieve Information Coded In Alphanumeric. J. ACM, 15, 514\u2013534, 1968.","journal-title":"J. ACM"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/0202005","volume":"2","author":"J. Nievergelt","year":"1973","unstructured":"J. Nievergelt and E. M. Reingold. Binary search trees of bounded balance. SIAM Journal on Computing 2 (1973), 33\u201343.","journal-title":"SIAM Journal on Computing"},{"key":"7_CR23","unstructured":"J. M. Ockerbloom. The on-line books page. http:\/\/digital.library.upenn.edu\/books\/"},{"key":"7_CR24","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/78973.78977","volume":"33","author":"W. Pugh","year":"1990","unstructured":"W. Pugh. Skip Lists: A probabilistic alternative to balanced trees. Communications of the ACM 33 (1990), 668\u2013676.","journal-title":"Communications of the ACM"},{"key":"7_CR25","unstructured":"W. Pugh. Skip Lists ftp directory. ftp:\/\/ftp.cs.umd.edu\/pub\/skipLists\/ ."},{"key":"7_CR26","unstructured":"R. Sedgewick. Algorithms in C, Addison-Wesley, 1998."},{"key":"7_CR27","doi-asserted-by":"publisher","first-page":"464","DOI":"10.1007\/BF01940876","volume":"16","author":"R. Seidel","year":"1996","unstructured":"R. Seidel and C. R. Aragon. Randomized search trees. Algorithmica 16 (1996), 464\u2013497.","journal-title":"Algorithmica"},{"key":"7_CR28","unstructured":"C. Silverstein. Library call data set. http:\/\/theory.stanford.edu\/~csilvers\/libdata ."},{"key":"7_CR29","unstructured":"C. Silverstein. A practical perfect hash algorithm. Manuscript, 1998."},{"key":"7_CR30","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. Journal of the ACM 32 (1985), 652\u2013686.","journal-title":"Journal of the ACM"},{"key":"7_CR31","doi-asserted-by":"crossref","unstructured":"W. Szpankowski, Average Case Analysis of Algorithms on Sequences, Wiley, 2001.","DOI":"10.1002\/9781118032770"},{"key":"7_CR32","doi-asserted-by":"crossref","unstructured":"R. E. Tarjan. Data structures and network algorithms, SIAM (1983).","DOI":"10.1137\/1.9781611970265"},{"key":"7_CR33","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1109\/TC.1984.1676438","volume":"C-33","author":"V. K. Vaishnavi","year":"1984","unstructured":"V. K. Vaishnavi. Multidimensional height-balanced trees. IEEE Transactions on Computers C-33 (1984), 334\u2013343.","journal-title":"IEEE Transactions on Computers"},{"key":"7_CR34","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1109\/12.30849","volume":"C-38","author":"V. K. Vaishnavi","year":"1989","unstructured":"V. K. Vaishnavi. Multidimensional balanced binary trees. IEEE Transactions on Computers C-38 (1989), 968\u2013985.","journal-title":"IEEE Transactions on Computers"},{"key":"7_CR35","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1006\/jcss.1996.0025","volume":"52","author":"V. K. Vaishnavi","year":"1996","unstructured":"V. K. Vaishnavi. On k-dimensional balanced binary trees. Journal of Computer and System Sciences 52 (1996), 328\u2013348.","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR36","unstructured":"Mark A. Weiss. Data structures and algorithm analysis in C, Addison Wesley, (1997). Source code in http:\/\/www.cs.fiu.edu\/~weiss\/dsaa_c2e\/files.html ."}],"container-title":["Lecture Notes in Computer Science","Experimental and Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44867-5_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T05:36:03Z","timestamp":1557034563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44867-5_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540402053","9783540448679"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-44867-5_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}