Index Structures for Main Memory Database Systems

@article{10.1145/3506692,
author = {Binna, Robert and Zangerle, Eva and Pichl, Martin and Specht, G\"{u}nther and Leis, Viktor},
title = {Height Optimized Tries},
year = {2022},
issue_date = {March 2022},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
volume = {47},
number = {1},
issn = {0362-5915},
url = {https://doi.org/10.1145/3506692},
doi = {10.1145/3506692},
abstract = {We present the Height Optimized Trie (HOT), a fast and space-efficient in-memory index structure. The core algorithmic idea of HOT is to dynamically vary the number of bits considered at each node, which enables a consistently high fanout and thereby good cache efficiency. For a fixed maximum node fanout, the overall tree height is minimal and its structure is deterministically defined. Multiple carefully engineered node implementations using SIMD instructions or lightweight compression schemes provide compactness and fast search and optimize HOT structures for different usage scenarios. Our experiments, which use a wide variety of workloads and data sets, show that HOT outperforms other state-of-the-art index structures for string keys both in terms of search performance and memory footprint, while being competitive for integer keys.},
journal = {ACM Trans. Database Syst.},
month = {apr},
articleno = {3},
numpages = {46},
keywords = {main memory, SIMD, Height optimized trie, index structure}
}

@inproceedings{Binna:2018:HHO:3183713.3196896,
 author = {Binna, Robert and Zangerle, Eva and Pichl, Martin and Specht, G\"{u}nther and Leis, Viktor},
 title = {HOT: A Height Optimized Trie Index for Main-Memory Database Systems},
 booktitle = {Proceedings of the 2018 International Conference on Management of Data},
 series = {SIGMOD '18},
 year = {2018},
 isbn = {978-1-4503-4703-7},
 location = {Houston, TX, USA},
 pages = {521--534},
 numpages = {14},
 url = {http://doi.acm.org/10.1145/3183713.3196896},
 doi = {10.1145/3183713.3196896},
 acmid = {3196896},
 publisher = {ACM},
 address = {New York, NY, USA},
 keywords = {height optimized trie, index, main memory, simd},
} 

@inproceedings{gvdb11,
author = {Binna, Robert and Gassler, Wolfgang and Zangerle, Eva and Pacher, Dominic and Specht, G\"unther},
booktitle = {Proceedings of the 23nd Workshop Grundlagen von Datenbanken (GvDB 2011), Obergurgl, Austria},
publisher = {CEUR-WS.org, ISSN 1613-0073, Vol. 733},
title = {{SpiderStore: A Native Main Memory Approach for Graph Storage}},
year = {2011},
howpublished = {online}
}

@inproceedings{vldb10,
title={{SpiderStore: Exploiting Main Memory for Efficient RDF Graph Representation and Fast Querying}},
booktitle = {Proceedings of the 1st International Workshop on Semantic Data Management (SemData) at the 36th International Conference on Very Large Data Bases (VLDB 2010), Singapore},
author={Binna, Robert and Gassler, Wolfgang and Zangerle, Eva and Pacher, Dominic and Günther Specht},
year={2010},
publisher = {CEUR-WS.org},
howpublished = {online}
}