Name: PWL#11 Ideal Hash Trees
Start: 2015-09-10T19:00:00-07:00
End: 2015-09-10T22:00:00-07:00
Location: Whitepages

David Murray will present Ideal Hash Trees (http://lampwww.epfl.ch/papers/idealhashtrees.pdf):

"Hash Trees with nearly ideal characteristics are described. These Hash Trees require no initial root hash table yet are faster and use significantly less space than chained or double hash trees. Insert, search and delete times are small and constant, independent of key set size, operations are O(1). Small worst-case times for insert, search and removal operations can be guaranteed and misses cost less than successful searches. Array Mapped Tries(AMT), first described in Fast and Space Efficient Trie Searches, Bagwell [2000], form the underlying data structure. The concept is then applied to external disk or distributed storage to obtain an algorithm that achieves single access searches, close to single access inserts and greater than 80 percent disk block load factors. Comparisons are made with Linear Hashing, Litwin, Neimat, and Schneider [1993] and B-Trees, R.Bayer and E.M.McCreight [1972]. In addition two further applications of AMTs are briefly described, namely, Class/Selector dispatch tables and IP Routing tables. Each of the algorithms has a performance and space usage that is comparable to contemporary implementations but simpler. "

Ankur Chauhan

David Murray

Papers We Love @ Seattle

Technology

Open Source

Intellectual Discussions

Learning

Engineering

Computer Science

Intellectual Curiosity

Education & Technology

New Technology

Research & Development Engineer

Computer Programming

Technology Professionals

Researchers

PWL#11 Ideal Hash Trees

Whitepages

Share

Papers We Love @ Seattle

PWL#11 Ideal Hash Trees

Papers We Love @ Seattle

Details

Members are also interested in