Type Less, Find More: Fast Autocompletion Search with a...

Channel:

Google TechTalks

Subscribers:

348,000

Published on October 9, 2007 1:54:58 AM ● Video Link: https://www.youtube.com/watch?v=z2V2mqPao2I

Duration: 47:55

1,148 views

2

Google TechTalks
August 14, 2006

Holger Bast

ABSTRACT
We consider the following full-text search autocompletion feature. Imagine a user of a search engine typing a query. Then with every letter being typed, we would like an instant display of completions of the last query word which would lead to good hits. At the same time, the best hits for any of these completions should be displayed. Known indexing data structures that apply to this problem either incur large processing times for a substantial class of queries, or they use a lot of space. We present a new indexing data structure that uses no more space than a state-of-the-art compressed inverted index, but that yields an order of magnitude...