A Study of Four Index Structures for Set-Valued Attributes of Low Cardinality

Vorschau

PDF
TR-99-002.pdf - Veröffentlichte Version
Download (287kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/774
URN:	urn:nbn:de:bsz:180-madoc-7746
Dokumenttyp:	Arbeitspapier
Erscheinungsjahr:	1999
Titel einer Zeitschrift oder einer Reihe:	Technical Reports
Band/Volume:	99-002
Ort der Veröffentlichung:	Mannheim
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC-Schriftenreihe:	Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Fachgebiet:	004 Informatik
Normierte Schlagwörter (SWD):	Indizierung <Informatik> , Mengenwertige Abbildung
Freie Schlagwörter (Englisch):	index structures , set-valued attributes
Abstract:	We review and study the performance of four different index structures for indexing set-valued attributes designed to speed up set equality, subset and superset queries. All index structures are based on traditional techniques, namely signatures and inverted files. More specifically, we consider sequential signature files, signature trees, extendible signature hashing, and a B-tree based implementation of inverted lists. The latter is refined by a compression scheme in order to keep space requirements within acceptable bounds. The performance study is based on real implementations subjected to a benchmark accounting for different set sizes, domain sizes, and data distributions (uniform and skewed).
Zusätzliche Informationen: