ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

8 Apr 2005:
Skip Graphs and Family Trees: Two Ordered Dictionaries for Distributed Systems (Series Part 2)
Michael Nelson

Abstract: The talk will focus on two solutions to the problem of storing a dynamic ordered dictionary over a distributed set of machines. Both of these data structures can support efficient search operations as well as range queries. This second part of the talk focuses on family trees and 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