COCA Filters: Co-Occurrence Aware Bloom Filters
[.pdf]
Abstract
We propose an indexing data structure based on a novel variation of Bloom filters. Signature files have been proposed in the past as
a method to index large text databases though they sur from a high
false positive error problem. In this paper we introduce COCA Filters,
a new type of Bloom filters which exploits the co-occurrence probability
of words in documents to reduce the false positive error. We show experimentally that by using this technique we can reduce the false positive
error by up to 21 times for the same index size. Furthermore Bloom filters can be replaced by COCA filters wherever the co-occurrence of any
two members of the universe is identifiable.
Bibtex Entry
