research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleDynamic Interpolation Search Revisited.
Bibtex cite IDRACTI-RU1-2006-45
Booktitle 33rd International Colloquium for Automata, Languages and Programming
Series Lecture Notes in Computer Science
Year published 2006
Month July
Volume 4051
Pages 382-394
Publisher Springer
Organization ICALP 2006
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 mea- surable probability of key collisions, including power law and Binomial distributions. No such previous result holds for IS when the probabil- ity of key collisions is measurable. Moreover, our data structure exhibits O(1) expected search time with high probability for a wide class of in- put distributions that contains all those for which o(log log n) expected search time was previously known.
Kaporis, Alexis
Makris, Christos
Sioutas, Spyros
Tsakalidis, Athanasios
Tsichlas, Kostas
Zaroliagis, Christos
C45-icalp2006-dis-revisited.pdf (main file)
Publication ID118