Theory Lunch

TIME:: Wednesday, Oct. 31, noon till 1pm

PLACE:: 7220 Wean Hall

TITLE::  Efficient Finger Search Using Eager Walk

SPEAKER::  Maverick Woo


Balanced search trees (BST) are commonly used to represent sorted lists that
allow efficient access to list elements. A BST supports finger search if it
takes O(log d) time to access an element y after accessing an element x,
where d is the distance between x and y in the sorted order.

In this talk, we will develop a data structure that provides support for
finger search on Red-Black trees. Our data structure is radically different
from the many data structure designed to support finger search since 1980's.
Instead of being a new BST by itself, our data structure actually operates
on Red-Black trees. Our design does not impose any space overhead on the
tree itself and this makes our data structure desirable in practice.

A nice consequence of this work is that we can do an in-order walk on
B-trees so that it takes worst case O(1) time to travel between consecutive
nodes in the sorted order, given O(log n) time for pre-processing. Our
algorithm is simple and brings up an interesting issue in database design.

This is joint work with Guy Blelloch.