ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

11 Mar 2005:
Skip Graphs and Family Trees: Two Ordered Dictionaries for Distributed Systems
Presented by Michael Nelson

Abstract: The talk will focus on two solutions to the problem of storing a dynamic ordered dictionary over a distributed set of nodes. Both of these data structures can support efficient search operations as well as range queries. The talk will include definitions of the two data structures, an outline of their fundamental routines, and a discussion of their theoretical performance.

The content of the talk is taken from the following two papers:
"Skip Graphs" by James Aspnes and Gauri Shah, appeared in SODA 2003
"Family Trees" by Kevin C. Zatloukal and Nicholas J. A. Harvey, appeared in SODA 2004