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
Last updated June 16, 2019 by