Donald Bren School of Information and Computer Sciences

A finger is a point in a file near which updates and searches can be conducted particularly efficiently. We present a data structure which supports insertions, deletions, searches, and approximate range queries. In each case both a finger f and a key k are specified as arguments to the appropriate algorithm. The total time bound for n updates (insertion or deletions) in an initiallly empty data structure is the sum over all updates of 0(log d+log*n), where d is the linear distance (i.e., the distance in the linear list being represented) from f to k. By an approximate range query, we mean a query of the form "How many keys lie between the finger f and the key k?", where a predetermined percentage of error is allowed in the number returned. The time for each individual search or range query is 0(log d).