%0 Journal Article %1 keyhere %A Bast, Holger %A Mortensen, Christian %A Weber, Ingmar %D 2008 %J Information Retrieval %K autocompletion output search sensitive %N 4 %P 269--286 %T Output-sensitive autocompletion search %U http://dx.doi.org/10.1007/s10791-008-9048-x %V 11 %X Abstract  We consider the following autocompletion search scenario: imagine a user of a search engine typing a query; then with every keystroke display those completions of the last query word that would lead to the best hits, and also display the best suchhits. The following problem is at the core of this feature: for a fixed document collection, given a set D of documents, and an alphabetical range W of words, compute the set of all word-in-document pairs (w, d) from the collection such that w ∈ W and d ∈ D. We present a new data structure with the help of which such autocompletion queries can be processed, on the average, intime linear in the input plus output size, independent of the size of the underlying document collection. At the same time,our data structure uses no more space than an inverted index. Actual query processing times on a large test collection correlatealmost perfectly with our theoretical bound.

@article{keyhere, abstract = {Abstract  We consider the following autocompletion search scenario: imagine a user of a search engine typing a query; then with every keystroke display those completions of the last query word that would lead to the best hits, and also display the best suchhits. The following problem is at the core of this feature: for a fixed document collection, given a set D of documents, and an alphabetical range W of words, compute the set of all word-in-document pairs (w, d) from the collection such that w ∈ W and d ∈ D. We present a new data structure with the help of which such autocompletion queries can be processed, on the average, intime linear in the input plus output size, independent of the size of the underlying document collection. At the same time,our data structure uses no more space than an inverted index. Actual query processing times on a large test collection correlatealmost perfectly with our theoretical bound.}, added-at = {2009-03-25T15:54:27.000+0100}, author = {Bast, Holger and Mortensen, Christian and Weber, Ingmar}, biburl = {https://www.bibsonomy.org/bibtex/20c580fceea0f62e085df618004b4c95b/touv}, description = {SpringerLink - Article de revue}, interhash = {d202ed1a14a891994ff648268bf1add2}, intrahash = {0c580fceea0f62e085df618004b4c95b}, journal = {Information Retrieval}, keywords = {autocompletion output search sensitive}, month = {#aug#}, number = 4, pages = {269--286}, timestamp = {2009-03-25T18:11:49.000+0100}, title = {Output-sensitive autocompletion search}, url = {http://dx.doi.org/10.1007/s10791-008-9048-x}, volume = 11, year = 2008 }