Paper by Erik D. Demaine

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.

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.

The paper is 2 pages.

The paper is available in PostScript (95k), gzipped PostScript (40k), and PDF (145k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated September 3, 2017 by Erik Demaine.