Theory Lunch ------------ TIME:: Wednesday, Oct. 31, noon till 1pm PLACE:: 7220 Wean Hall TITLE:: Efficient Finger Search Using Eager Walk SPEAKER:: Maverick Woo ABSTRACT:: 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.