@inproceedings{ding2011fast,
author = {Ding, Bolin and König, Arnd Christian},
title = {Fast Set Intersection in Memory},
booktitle = {37th International Conference on Very Large Databases (VLDB)},
year = {2011},
month = {January},
abstract = {Set intersection is a fundamental operation in information retrieval and database systems. This paper introduces linear space data structures to represent sets such that their intersection can be computed in a worst-case efficient way. In general, given k (preprocessed) sets, with totally n elements, we will show how to compute their intersection in expected time O(n / sqrt(w) + kr), where r is the intersection size and w is the number of bits in a machine-word. In addition,we introduce a very simple version of this algorithm that has weaker asymptotic guarantees but performs even better in practice; both algorithms outperform the state of the art techniques for both synthetic and real data sets and workloads.},
publisher = {Very Large Data Bases Endowment Inc.},
url = {http://approjects.co.za/?big=en-us/research/publication/fast-set-intersection-in-memory/},
edition = {37th International Conference on Very Large Databases (VLDB)},
}