Set-valued attributes are convenient to model complex objects
occurring in the real world. Currently available database systems
support the storage of set-valued attributes in relational tables but contain
no primitives to query them e.ciently. Queries involving set-valued
attributes either perform full scans of the source data or make multiple
passes over single-value indexes to reduce the number of retrieved tuples.
Existing techniques for indexing set-valued attributes (e.g., inverted .les,
signature indexes or RD-trees) are not e.cient enough to support fast
access of set-valued data in very large databases.
In this paper we present the hierarchical bitmap index—a novel technique
for indexing set-valued attributes. Our index permits to index sets
of arbitrary length and its performance is not a.ected by the size of the
indexed domain. The hierarchical bitmap index e.ciently supports different
classes of queries, including subset, superset and similarity queries.
Our experiments show that the hierarchical bitmap index outperforms
other set indexing techniques signi.cantly.