Track: Search
Paper Title:
Efficient Search in Large Textual Collections with Redundancy
Authors:
Abstract:
Current web search engines focus on searching only the most recent snapshot
of the web. In some cases, however, it would be desirable to search over
collections that include many different crawls and versions of each page.
One important example of such a collection is the Internet Archive, though
there are many others. Since the data size of such an archive is multiple
times that of a single snapshot, this presents us with significant performance
challenges. Current engines use various techniques for index compression
and optimized query execution, but these techniques do not exploit the
significant similarities between different versions of a page, or between
different pages.
In this paper, we propose a general framework for indexing and query processing of archival collections and, more generally, any collections with a significant amount of redundancy. Our approach results in very significant reductions in index size and query processing costs on such collections, and it is orthogonal to and can be combined with the existing techniques. It also supports highly efficient updates, both locally and over a network. Within this framework, we describe and evaluate several different implementations that trade off index size versus CPU cost and other factors, and discuss applications ranging from archival web search to local search of web sites, email archives, or file systems. We present experimental results based on search engine query log and a large collection consisting of multiple crawls.
