Many complex real world objects can be easily modeled using
sets or sequences. Attributes containing sets or sequences of elements appear
in various application domains, e.g. in telecommunication and retail
databases, multimedia systems, web server logs, genetic and molecular
databases, etc. However, the support for such attributes is usually limited
to definition and storage in flat relational tables. Currently available
database systems support neither indexing nor advanced querying of attributes
containing sets or sequences. SQL language does not offer any
primitives to express set containment or set similarity queries.
In this paper we investigate similarity queries for set and sequence-valued
attributes. We present the notion of a similarity query and we review
similarity measures proposed so far for sets and sequences. We present
hierarchical bitmap index, an e±cient indexing technique for sets, and
we show how the hierarchical bitmap index framework can be extended
to incorporate sequences as well. We introduce a new similarity measure
that can be successfully used with sequences. We present algorithms for
efficient similarity query processing using hierarchical bitmap index and
its variants. Our paper concludes with the results of conducted experiments.