Indexing Set-Valued Attributes with a Multi-Level Extendible Hashing Scheme

S. Helmer, Robin Aly, T. Neumann, G. Moerkotte

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

5 Citations (Scopus)

Abstract

We present an access method for set-valued attributes that is based on a multi-level extendible hashing scheme. This scheme avoids exponential directory growth for skewed data and thus generates a much smaller number of subqueries for query sets (up to now fast-growing directories have prohibited the use of hash-based index structures for set-valued retrieval). We demonstrate the advantages of our scheme over regular extendible hashing both analytically and experimentally. Additionally, we compare the performance of a prototype implementation with that of several other access methods; the results underline the benefits of our approach.
Original languageUndefined
Title of host publicationProceedings of the 18th International Conference of Database and Expert Systems Applications (DEXA 2007)
Place of PublicationBerlin
PublisherSpringer
Pages98-108
Number of pages10
ISBN (Print)978-3-540-74467-2
DOIs
Publication statusPublished - Sep 2007

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
NumberSINTEF A13
Volume4653

Keywords

  • Subset superseq queries hashing
  • METIS-241714
  • IR-61763
  • EWI-10328

Cite this

Helmer, S., Aly, R., Neumann, T., & Moerkotte, G. (2007). Indexing Set-Valued Attributes with a Multi-Level Extendible Hashing Scheme. In Proceedings of the 18th International Conference of Database and Expert Systems Applications (DEXA 2007) (pp. 98-108). [10.1007/978-3-540-74469-6_11] (Lecture Notes in Computer Science; Vol. 4653, No. SINTEF A13). Berlin: Springer. https://doi.org/10.1007/978-3-540-74469-6_11