Dynamic Interpolation Search revisited

A new dynamic Interpolation Search (IS) data structure is presented that achieves O ( log ⁡ log ⁡ n ) search time with high probability on unknown continuous or even discrete input distributions with measurable probability of element collisions, including power law and Binomial distributions. No such previous result holds for IS when the probability of element collisions is measurable. Moreover, our data structure exhibits O ( 1 ) search time with high probability (w. h. p.) for a wide class of input distributions that contains all those for which o ( log ⁡ log ⁡ n ) expected search time was previously known.

Authors

• Alexis Kaporis
• Christos Makris
• Spyros Sioutas
• Athanasios Tsakalidis
• Kostas Tsichlas
• Christos Zaroliagis

Keywords

• Interpolation Search
• Dynamic predecessor search
• Dynamic search data structure