Ideal Hash Trees

Welcome to the DC/NoVA Papers We Love meetup!

Papers We Love is an international organization centered around the appreciation of computer science research papers. There's so much we can learn from the landmark research that shaped the field and the current studies that are shaping our future. Our goal is to create a community of tech professionals passionate about learning and sharing knowledge. Come join us!

New to research papers? Watch The Refreshingly Rewarding Realm of Research Papers (https://www.youtube.com/watch?v=8eRx5Wo3xYA) by Sean Cribbs.

Ideas and suggestions are welcome–fill our our interest survey here (https://docs.google.com/forms/d/e/1FAIpQLSeJwLQhnmzWcuyodPrSmqHgqrvNxRbnNSbiWAuwzHwshhy_Sg/viewform) and let us know what motivates you!

// Tentative Schedule

• 7:00-7:30–Informal paper discussion

• 7:30-7:35–Introduction and announcements

• 7:35-8:40–Ideal Hash Trees (http://lampwww.epfl.ch/papers/idealhashtrees.pdf), led by Hugo Estrada

• 8:40-9:00–Informal paper discussion

// Directions

CustomInk Cafe (3rd Floor)
Mosaic District, 2910 District Ave #300
Fairfax, VA 22031

When you get here you can come in via the patio. Don't be scared by the metal gate and sign. It's accessible via the outside stairs near True Food. There is a parking garage next door for those coming by vehicle. And, there is a walkway to the patio on the 3rd floor of the garage nearest moms organic market.

Metro: The Dunn Loring metro station is about 0.7 miles from our meetup location. It’s very walkable, but if you’d prefer a bus, the 402 Southbound and 1A/1B/1C Westbound leave from Dunn Loring Station about every 5-10 minutes (see a schedule for more detailed timetable).

If you're late, we totally understand–please still come! (via the patio is best) Just be sure to slip in quietly if a speaker is presenting.

// Papers

Ideal Hash Trees by Phil Bagwell

pdf (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.