{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T00:36:04Z","timestamp":1791419764804,"version":"4.3.3"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Inf Retrieval"],"published-print":{"date-parts":[[2008,8]]},"DOI":"10.1007\/s10791-008-9048-x","type":"journal-article","created":{"date-parts":[[2008,3,3]],"date-time":"2008-03-03T14:52:30Z","timestamp":1204555950000},"page":"269-286","source":"Crossref","is-referenced-by-count":15,"title":["Output-sensitive autocompletion search"],"prefix":"10.1007","volume":"11","author":[{"given":"Holger","family":"Bast","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian W.","family":"Mortensen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ingmar","family":"Weber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2008,3,4]]},"reference":[{"issue":"9","key":"9048_CR1","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"Aggarwal, A., & Vitter, J. S. (1988). The input\/output complexity of sorting and related problems. Communications of the ACM, 31(9), 1116\u20131127.","journal-title":"Communications of the ACM"},{"key":"9048_CR2","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Brodal, G. S., & Rauhe, T. (2000). New data structures for orthogonal range searching. In 41st Symposium on Foundations of Computer Science (FOCS\u201900), pp. 198\u2013207.","DOI":"10.1109\/SFCS.2000.892088"},{"key":"9048_CR3","doi-asserted-by":"crossref","unstructured":"Arge, L., Samoladas, V., & Vitter, J. S. (1999). On two-dimensional indexability and optimal range search indexing. In 18th Symposium on Principles of database systems (PODS\u201999), pp. 346\u2013357.","DOI":"10.1145\/303976.304010"},{"key":"9048_CR4","doi-asserted-by":"crossref","unstructured":"Bast, H., & Weber, I. (2006). Type less, find more: Fast autocompletion search with a succinct index. In 29th Conference on Research and Development in Information Retrieval (SIGIR\u201906).","DOI":"10.1145\/1148170.1148234"},{"key":"9048_CR5","unstructured":"Bast, H., & Weber, I. (2007). Managing helpdesk tasks with CompleteSearch: A case study. In N. Gronau (Ed.), 4th Conference on Professional Knowledge Management (WM\u201907), pp. 101\u2013108. Potsdam, Germany. GITO."},{"key":"9048_CR6","doi-asserted-by":"crossref","unstructured":"Bast, H., Mortensen, C. W., & Weber, I. (2006). Output-sensitive autocompletion search. In 13th Symposium on String Processing and Information Retrieval (SPIRE\u201906), pp. 150\u2013162.","DOI":"10.1007\/11880561_13"},{"key":"9048_CR7","doi-asserted-by":"crossref","unstructured":"Bickel, S., Haider, P., & Scheffer, T. (2005). Learning to complete sentences. In 16th European Conference on Machine Learning (ECML\u201905), pp. 497\u2013504.","DOI":"10.1007\/11564096_47"},{"issue":"3","key":"9048_CR8","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1137\/0217026","volume":"17","author":"B. Chazelle","year":"1988","unstructured":"Chazelle, B. (1988). A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3), 427\u2013462.","journal-title":"SIAM Journal on Computing"},{"key":"9048_CR9","doi-asserted-by":"crossref","unstructured":"Darragh, J. J., Witten, I. H., & James, M. L. (1990). The reactive keyboard: A predictive typing aid. IEEE Computer, pp. 41\u201349.","DOI":"10.1109\/2.60879"},{"key":"9048_CR10","unstructured":"Demaine, E. D., Lopez-Ortiz, A., & Munro, J. I. (2000). Adaptive set intersections, unions, and differences. In 11th Symposium on Discrete Algorithms (SODA\u201900), pp. 743\u2013752."},{"issue":"4","key":"9048_CR11","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1016\/S0022-0000(03)00028-X","volume":"66","author":"P. Ferragina","year":"2003","unstructured":"Ferragina, P., Koudas, N., Muthukrishnan, S., & Srivastava, D. (2003). Two-dimensional substring indexing. Journal of Computer and System Science, 66(4), 763\u2013774.","journal-title":"Journal of Computer and System Science"},{"key":"9048_CR12","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Giancarlo, R., & Manzini, G. (2006). The myriad virtues of wavelet trees. In 33rd International Colloquium on Automata, Languages and Programming (ICALP\u201906), pp. 560\u2013571.","DOI":"10.1007\/11786986_49"},{"key":"9048_CR13","doi-asserted-by":"crossref","unstructured":"Finkelstein, L., Gabrilovich, E., Matias, Y., Rivlin, E., Solan, Z., Wolfman, G., & Ruppin, E. (2001). Placing search in context: The concept revisited. In 10th World Wide Web Conference (WWW\u201910), pp. 406\u2013414.","DOI":"10.1145\/371920.372094"},{"issue":"2","key":"9048_CR14","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1145\/280277.280279","volume":"30","author":"V. Gaede","year":"1998","unstructured":"Gaede, V., & G\u00fcnther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2), 170\u2013231.","journal-title":"ACM Computing Surveys"},{"key":"9048_CR15","doi-asserted-by":"crossref","unstructured":"Grossi, R., & Vitter, J. S. (2000). Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). In 32nd Symposium on the Theory of Computing (STOC\u201900), pp. 397\u2013406.","DOI":"10.1145\/335305.335351"},{"key":"9048_CR16","unstructured":"Grossi, R., Gupta, A., & Vitter, J. (2003). High-order entropy-compressed text indexes. In 14th Symposium on Discrete Algorithms (SODA\u201903), pp. 841\u2013850."},{"key":"9048_CR17","unstructured":"Grossi, R., Gupta, A., & Vitter, J. S. (2004). When indexing equals compression: experiments with compressing suffix arrays and applications. In SODA \u201904: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 636\u2013645, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics."},{"key":"9048_CR18","doi-asserted-by":"crossref","unstructured":"Jakobsson, M. (1986). Autocompletion in full text transaction entry: A method for humanized input. In Conference on Human Factors in Computing Systems (CHI\u201986), pp. 327\u2013323.","DOI":"10.1145\/22627.22391"},{"key":"9048_CR19","unstructured":"M\u00e4kinen, V., & Navarro, G. (2004). New search algorithms and space\/time tradeoffs for succinct suffix arrays. Technical Report C-2004-20, University of Helsinki."},{"key":"9048_CR20","unstructured":"Manber, U., & Myers, G. (1990). Suffix arrays: A new method for on-line string searches. In SODA \u201990: Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, pp. 319\u2013327, Philadelphia, PA, USA. Society for Industrial and Applied Mathematics."},{"issue":"2","key":"9048_CR21","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1137\/0214021","volume":"14","author":"E. M. McCreight","year":"1985","unstructured":"McCreight, E. M. (1985). Priority search trees. SIAM Journal on Computing, 14(2), 257\u2013276.","journal-title":"SIAM Journal on Computing"},{"key":"9048_CR22","doi-asserted-by":"crossref","unstructured":"Munro, J. I. (1996). Tables. In 16th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201996), pp. 37\u201342.","DOI":"10.1007\/3-540-62034-6_35"},{"issue":"2\/3","key":"9048_CR23","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s007990050041","volume":"2","author":"C. G. Nevill Manning","year":"1999","unstructured":"Nevill-Manning, C. G., Witten, I. H., & Paynter, G. W. (1999). Lexically-generated subject hierarchies for browsing large collections. International Journal of Digital Libraries, 2(2\/3), 111\u2013123.","journal-title":"International Journal of Digital Libraries"},{"key":"9048_CR24","doi-asserted-by":"crossref","unstructured":"Paynter, G. W., Witten, I. H., Cunningham, S. J., & Buchanan, G. (2000). Scalable browsing for large collections: A case study. In 5th Conference on Digital Libraries (DL\u201900), pp. 215\u2013223.","DOI":"10.1145\/336597.336666"},{"key":"9048_CR25","doi-asserted-by":"crossref","unstructured":"Puglisi, S. J., Smyth, W. F., & Turpin, A. (2006). Inverted files versus suffix arrays for locating patterns in primary memory. In SPIRE, pp. 122\u2013133.","DOI":"10.1007\/11880561_11"},{"key":"9048_CR26","doi-asserted-by":"crossref","unstructured":"Stocky, T., Faaborg, A., & Lieberman, H. (2004). A commonsense approach to predictive text entry. In Conference on Human Factors in Computing Systems (CHI\u201904), pp. 1163\u20131166.","DOI":"10.1145\/985921.986014"},{"key":"9048_CR27","unstructured":"Voorhees, E. (2004). Overview of the trec 2004 robust retrieval track. In 13th Text Retrieval Conference (TREC\u201904). http:\/\/trec.nist.gov\/pubs\/trec13\/papers\/ROBUST.OVERVIEW.pdf ."},{"key":"9048_CR28","unstructured":"Weber, I. (2007). Efficient index structures for and applications of the CompleteSearch engine. PhD thesis, Max Planck Institut Informatik."},{"key":"9048_CR29","unstructured":"Witten, I. H., Bell, T. C., & Moffat, A. (1999). Managing gigabytes: Compressing and indexing documents and images (2nd ed.). Morgan Kaufmann."}],"container-title":["Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10791-008-9048-x.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T14:37:27Z","timestamp":1557326247000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10791-008-9048-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,4]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9048"],"URL":"https:\/\/doi.org\/10.1007\/s10791-008-9048-x","relation":{},"ISSN":["1386-4564","1573-7659"],"issn-type":[{"value":"1386-4564","type":"print"},{"value":"1573-7659","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3,4]]}}}