When You're Lost for Words: Faceted Search with Autocompletion
Holger Bast, Ingmar G. Weber, Andrei Broder, Yoelle Maarek · Max Planck Institute for Plasma Physics · 2006
In this paper, we show how the autocompletion data structure of [2] can be used to answer faceted-search queries eciently. Specically , we have built a fully-functional browserbased search engine that can index collections with arbitrary category information and that, after each keystroke from the user, computes and displays the following information: (i) words or phrases that begin with the last query word and would lead to good hits; (ii) the most relevant categories for those hits; (iii) any category names that match the query as typed so far; (iv) the most relevant hits for the query as typed so far. By appropriately rewriting the faceted-search queries as autocompletion queries according to [2], we obtain very fast query processing times, improving those obtained by standard approaches by an order of magnitude. On 11,685 scientic articles from the DBLP collection, with their full text and categorized by author, conference, and year, the average query processing time is about 25 milliseconds, on a single machine and with the index on disk. For the 2,172,832 articles of the latest dump of the English Wikipedia, with their full text and categorized by Wikipedia’s own category labels, we achieve an average query processing time of about 350 milliseconds.