Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Thouis Jones, and Mihai Pǎtraşcu, “Interpolation Search for Non-Independent Data”, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 522–523.

Abstract:

We define a deterministic metric of “well-behaved data” that enables searching along the lines of interpolation search. Specifically, define Delta to be the ratio of distances between the farthest and nearest pair of adjacent elements. We develop a data structure that stores a dynamic set of n integers subject to insertions, deletions, and predecessor/successor queries in O(lg Δ) time per operation. This result generalizes interpolation search and interpolation search trees smoothly to nonrandom (in particular, non-independent) input data. In this sense, we capture the amount of “pseudorandomness” required for effective interpolation search.

Length:

The paper is 2 pages.

Availability:

The paper is available in PostScript (95k), gzipped PostScript (40k), and PDF (145k).

See information on file formats.

[Google Scholar search]