On the correctness of a lock-free compression-based elastic mechanism for a hash trie design

• Tipo: Artigo em Revista Científica Internacional
• Data: 2022

Autores

Miguel Areias (Autor) FCUP; Ricardo Rocha (Autor) FCUP

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: COMPUTING

Vol. 104

Páginas: 2279-2305

ISSN: 0010-485X

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00W-KKN

DOI: 10.1007/s00607-022-01085-2

Abstract (EN): A key aspect of any hash map design is the problem of dynamically resizing it in order to deal with hash collisions. Compression in tree-based hash maps is the ability of reducing the depth of the internal hash levels that support the hash map. In this context, elasticity refers to the ability of automatically resizing the internal data structures that support the hash map operations in order to meet varying workloads, thus optimizing the overall memory consumption of the hash map. This work extends a previous lock-free hash trie map design to support elastic hashing, i.e., expand saturated hash levels and compress unused hash levels, such that, at each point in time, the number of levels in a path is adjusted, as closely as possible, to the set of keys that is stored in the data structure. To materialize our design, we introduce a new compress operation for hash levels, which requires redesigning the existing search, insert, remove and expand operations in order to maintain the lock-freedom property of the data structure. Experimental results show that elasticity effectively improves the search operation and, in doing so, our design becomes very competitive when compared to other state-of-the-art designs implemented in Java.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 27