Index Structures for Databases Containing Data Items with Set-valued Attributes

We introduce two new hash-based index structures to index set-valued attributes. Both are able to support subset and superset queries. Analytical cost models for the new index structures as well as for the two existing index structures, sequential signature file and Russian Doll Tree, are presented and experimentally validated. Using the validated cost model, we express the performance of all four index structures in terms of the performance of the sequential signature file. This allows a direct analytical comparison of their performance. Last, we report on our benchmark results comparing the real performance of all four index structures. We especially investigate their performance for skewed data. 1 Introduction Since the invention of database management systems, tremendous effort has been undertaken in order to invent index structures. Historically this work was mostly carried out in the context of relational databases. The impressive results comprise very versatile index s..