Show simple item record

dc.contributor.authorBoehm, Matthias
dc.contributor.authorSchlegel, Benjamin
dc.contributor.authorVolk, Peter Benjamin
dc.contributor.authorFischer, Ulrike
dc.contributor.authorHabich, Dirk
dc.contributor.authorLehner, Wolfgang
dc.contributor.editorHärder, Theo
dc.contributor.editorLehner, Wolfgang
dc.contributor.editorMitschang, Bernhard
dc.contributor.editorSchöning, Harald
dc.contributor.editorSchwarz, Holger
dc.date.accessioned2019-01-17T10:36:44Z
dc.date.available2019-01-17T10:36:44Z
dc.date.issued2011
dc.identifier.isbn978-3-88579-274-1
dc.identifier.issn1617-5468
dc.identifier.urihttp://dl.gi.de/handle/20.500.12116/19581
dc.description.abstractEfficient data structures for in-memory indexing gain in importance due to (1) the exponentially increasing amount of data, (2) the growing main-memory capacity, and (3) the gap between main-memory and CPU speed. In consequence, there are high performance demands for in-memory data structures. Such index structures are used-with minor changes-as primary or secondary indices in almost every DBMS. Typically, tree-based or hash-based structures are used, while structures based on prefix-trees (tries) are neglected in this context. For tree-based and hash-based structures, the major disadvantages are inherently caused by the need for reorganization and key comparisons. In contrast, the major disadvantage of trie-based structures in terms of high memory consumption (created and accessed nodes) could be improved. In this paper, we argue for reconsidering prefix trees as in-memory index structures and we present the generalized trie, which is a prefix tree with variable prefix length for indexing arbitrary data types of fixed or variable length. The variable prefix length enables the adjustment of the trie height and its memory consumption. Further, we introduce concepts for reducing the number of created and accessed trie levels. This trie is order-preserving and has deterministic trie paths for keys, and hence, it does not require any dynamic reorganization or key comparisons. Finally, the generalized trie yields improvements compared to existing in-memory index structures, especially for skewed data. In conclusion, the generalized trie is applicable as general-purpose in-memory index structure in many different OLTP or hybrid (OLTP and OLAP) data management systems that require balanced read/write performance.en
dc.language.isoen
dc.publisherGesellschaft für Informatik e.V.
dc.relation.ispartofDatenbanksysteme für Business, Technologie und Web (BTW)
dc.relation.ispartofseriesLecture Notes in Informatics (LNI) - Proceedings, Volume P-180
dc.titleEfficient in-memory indexing with generalized prefix treesen
dc.typeText/Conference Paper
dc.pubPlaceBonn
mci.reference.pages227-246
mci.conference.sessiontitleRegular Research Papers
mci.conference.locationKaiserslautern
mci.conference.date02.-04.03.2011


Files in this item

Thumbnail

Show simple item record