Inverted files for text search engines

By Justin Zobel, Alistair Moffat. 2006

1,298 citations recorded by the source corpus.

The technology underlying text search engines has advanced dramatically in the past decade. The development of a family of new index representations has led to a wide range of innovations in index storage, index construction, and query evaluation. While some of these developments have been consolidated in textbooks, many specific techniques are not widely known or the textbook descriptions are out of date. In this tutorial, we introduce the key techniques in the area, describing both a core implementation and how the core can be enhanced through a range of extensions. We conclude with a comprehensive bibliography of text indexing literature.

Subfields: Artificial Intelligence, Information Systems, Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Information Retrieval & Search

Citations in the corpus

Unbounded cache model for online language modeling with open vocabulary (2017, methodology): “Inverted file systems [56] are a core component of standard large-scale text retrieval systems, like search engines.”
Packing bag-of-features (2009, methodology): “Storing vectors with an inverted file [16] is a better strategy, as it allows the efficient computation of the distances between a given query vector and a set of sparse vectors representing the images in the dataset.”
Anytime Ranking for Impact-Ordered Indexes (2015, methodology): “Although Zobel and Moffat [22] allude in passing to an approach along the lines of what we propose, we are not aware of any work that has detailed a concrete implementation with appropriate performance evaluations.”
Incorporating Query Term Independence Assumption for Efficient Retrieval and Ranking using Deep Neural Networks (2019, methodology): “…a document collection, these term-document scores can be precomputed and combined with specialized IR data structures, such as inverted indexes [Zobel and Moffat, 2006], and clever organization strategies (e.g., impact-ordering [Anh et al., 2001]) to aggressively prune the set of documents…”
Assessing efficiency–effectiveness tradeoffs in multi-stage retrieval systems without using relevance judgments (2015, background): “We now group possible retrieval tasks into the three general phases; then describe each phase and the systems that result when they are composed in various ways; and finally in this section discuss ways in which system effectiveness can be evaluated.”
Book Reviews: Data-Intensive Text Processing with MapReduce by Jimmy Lin and Chris Dyer (2010, background): “Putting everything together, standard best practices for postings compression is to represent d-gaps with Golomb codes and term frequencies with γ codes [109, 112].”
Bridging the Gap Between Indexing and Retrieval for Differentiable Search Index with Query Generation (2022, methodology): “Most modern information retrieval systems are based on the index-then-retrieve pipeline where documents are first encoded and stored in an inverted index [10, 13, 15, 26, 34, 55, 58] or a nearest neighbor search index [7, 14, 20, 21, 25, 29, 49, 51] and search results are then constructed based on a”
RDF-3X: a RISC-style engine for RDF (2008, methodology): “This compression scheme is inspired by methods for inverted lists in text retrieval systems [50], but we generalize it to id triples rather than simple ids.”
iBAT: detecting anomalous taxi trajectories from GPS traces (2011, methodology): “To achieve this, we employ the inverted index mechanism [31], which is popularly used in information retrieval, to index all the taxi trajectories, As an analogy, the taxi trajectory and cell correspond to the document and word [31], respectively.”
Mining Query Logs: Turning Search Usage Data into Knowledge (2010, methodology): “First, an inverted file index allows the efficient resolution of queries on huge collections of web data [246].”
Collective spatial keyword querying (2011, methodology): “The IR-tree [8] is essentially an R-tree [12] extended with inverted files [16].”
The RDF-3X engine for scalable management of RDF data (2010, methodology): “This compression scheme is inspired by methods for inverted lists in text retrieval systems [68], but we generalize it to id triples rather than simple ids.”
A review on automatic image annotation techniques (2012, result): “in the same way as text documents [17–40,115,116].”
Old dogs are great at new tricks: column stores for ir prototyping (2014, background): “Information retrieval researchers and practitioners have long implemented specialized, custom-built data structures and query evaluation algorithms for document ranking [15].”