Efficient Set Intersection for Inverted Indexing
J. Shane Culpepper
School of Computer Science and Information Technology,
Victoria 3001, Australia.
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
ACM Trans. Information Systems, 29(1):1.1-1.25, December
Conjunctive Boolean queries are a key component of modern information
retrieval systems, especially when web-scale repositories are being
A conjunctive query q is equivalent to a |q|-way intersection
over ordered sets of integers, where each set represents the
documents containing one of the terms, and each integer in each set
is an ordinal document identifier.
As is the case with many computing applications, there is tension
between the way in which the data is represented, and the ways in
which it is to be manipulated.
In particular, the sets representing index data for typical document
collections are highly compressible, but are processed using random
access techniques, meaning that methods for carrying out set
intersections must be alert to issues to do with access patterns and
Our purpose in this paper is to explore these tradeoffs, by
investigating intersection techniques that make use of both
uncompressed "integer" representations, as well as compressed
We also propose a simple hybrid method that provides both compact
storage, and also faster intersection computations for conjunctive
querying than is possible even with uncompressed representations.