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

Preview

PDF
TR-99-002.pdf - Published
Download (287kB)

URL:	https://ub-madoc.bib.uni-mannheim.de/774
URN:	urn:nbn:de:bsz:180-madoc-7746
Document Type:	Working paper
Year of publication:	1999
The title of a journal, publication series:	Technical Reports
Volume:	99-002
Place of publication:	Mannheim
Publication language:	English
Institution:	School of Business Informatics and Mathematics > Sonstige - Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik
MADOC publication series:	Veröffentlichungen der Fakultät für Mathematik und Informatik > Institut für Informatik > Technical Reports
Subject:	004 Computer science, internet
Subject headings (SWD):	Indizierung <Informatik> , Mengenwertige Abbildung
Keywords (English):	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).
Additional information: