DocumentCode
2500847
Title
Trie hashing analysis
Author
Régnier, Mireille
Author_Institution
INRIA, Le Chesnay, France
fYear
1988
fDate
1-5 Feb 1988
Firstpage
377
Lastpage
381
Abstract
The author presents an analysis of trie hashing for alphanumerical keys. He proposes a variant that uses a binary code and an asymptotic analysis of the size of the index. This provides, for biased distribution, a computable formula that predicts the size of the index as a function of the frequencies of the characters and the transition frequencies between these characters. These results are confirmed by a simulation. The author considers a Markovian probabilistic method and uses the Mellin transform
Keywords
Markov processes; file organisation; probability; Markovian probabilistic method; Mellin transform; alphanumerical keys; asymptotic analysis; biased distribution; binary code; characters frequencies; computable formula; index size; simulation; transition frequencies; trie hashing; variant; Ambient intelligence; Binary codes; Buildings; Computational modeling; Computer science; Data structures; Distributed computing; Frequency; Multidimensional systems;
fLanguage
English
Publisher
ieee
Conference_Titel
Data Engineering, 1988. Proceedings. Fourth International Conference on
Conference_Location
Los Angeles, CA
Print_ISBN
0-8186-0827-7
Type
conf
DOI
10.1109/ICDE.1988.105481
Filename
105481
Link To Document