Key-sequential access methods for very large files derived from linear hashing

Autor:	P.B. Berra, N.I. Hachem
Rok vydání:	2003
Předmět:	Theoretical computer science Range query (data structures) Computer science Dynamic perfect hashing Linear hashing 2-choice hashing File format Sequential access Hash table K-independent hashing Locality preserving hashing Trie Data_FILES Algorithm Extendible hashing
Zdroj:	ICDE
DOI:	10.1109/icde.1989.47230
Popis:	A novel class of order-preserving dynamic hashing structures is introduced and analyzed. The access method is referred to as dynamic random-sequential access method (DRSAM) and is derived from linear hashing. With respect to previous methods DRSAM presents the following characteristics: (1) the structure captures the hashed order in consecutive storage areas so that order-preserving schemes result in performance improvements for range queries and sequential processing; and (2) it adapts elastic buckets for the control of file growth. This approach outperforms the partial expansion method. The file structure is also extended with proper control mechanisms to cope with nonuniform distributions. The outcome is a multilevel trie stored as a two-level sequentially allocated file. >
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::da559077c1db88a4562b730668e4a2eb https://doi.org/10.1109/icde.1989.47230 Zobrazit plný text záznamu