Sets and sequences are commonly used to model complex entities. Attributes 
containing sets or sequences of elements appear in various application domains, 
e.g., in telecommunication and retail databases, web server log tools, 
bioinformatics, etc. However, the support for such attributes is usually limited 
to definition and storage in relational tables. Contemporary database systems don't 
support either indexing or advanced querying of set or sequence attributes, such as 
executing set containment or set similarity queries. In this paper we focus on 
approximate queries on set and sequence attributes. We present the notion of an 
approximate query and we review similarity measures proposed so far for such attributes. 
We introduce a new similarity measure that can be successfully used with sequences. 
We present the hierarchical bitmap index - a novel and efficient indexing technique for 
sets and show how the hierarchical bitmap index framework can be extended to incorporate 
sequences as well. We conclude with algorithms for efficient approximate query processing 
using the hierarchical bitmap index.

Keywords: set and sequence valued attributes, set index, sequence index, 
approximate queries, similarity measures