Dynamic interpolation search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Dynamic interpolation search

Full text

Pdf (768 KB)

Source

Journal of the ACM (JACM) archive
Volume 40 , Issue 3 (July 1993) table of contents

Pages: 621 - 634

Year of Publication: 1993

ISSN:0004-5411

Authors

Kurt Mehlhorn	Max-Planck-Institut für Informatik and Universität des Saarlandes, Saarlandes, Germany
Athanasios Tsakalidis	Computer Technology Institute, Patras, Greece

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 70, Citation Count: 4

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/174130.174139 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	~FRANKLIN, W. R. Padded lists' Set operations in expected O(loglog N) time. b~fi Proc. ~Letters 9 (1979), 161-166.
	2	Greg N. Frederickson, Implicit Data Structures for the Dictionary Problem, Journal of the ACM (JACM), v.30 n.1, p.80-94, Jan. 1983 [doi>10.1145/322358.322364]
	3	~GONNET, G., ROGERS, L., AND GEORGE, J. An algorithmic and complexity analys~s of ~interpolation search," Acta Inf. 13, 1 (1980), 39-52.
	4	Micha Hofri , Alan G. Konheim, Padded lists revisited, SIAM Journal on Computing, v.16 n.6, p.1073-1114, December 1, 1987 [doi>10.1137/0216069]
	5	Alon Itai , Alan G. Konheim , Michael Rodeh, A Sparse Table Implementation of Priority Queues, Proceedings of the 8th Colloquium on Automata, Languages and Programming, p.417-431, July 13-17, 1981
	6	~KNUTH, D.E. Deletions that preserve randomness. IEEE Trans. Sofm,. Eng. SE 3 (1977), ~351-359.
	7	~MEHLHORN, K. Data Structures and Algorithms. Vol. 1; Sortzng and Searching. EATCS ~Monographs in Theoretical Computer Science. Springer-Verlag, New York, 1984.
	8	~MELVILI,E, R., AND GRIES, D. Controlled density sorting, htf Proc. Lett. 10 (1980), 169-172.
	9	Yehoshua Perl , Alon Itai , Haim Avni, Interpolation search—a log logN search, Communications of the ACM, v.21 n.7, p.550-553, July 1978 [doi>10.1145/359545.359557]
	10	~PEARL, Y., AND REINGOLD, E.M. Understanding the complexity of interpolation search, bzJ. ~Proc. Lett. 6, 6 (1977), 219 222.
	11	~PETERSON, W.W. Addressing for random storage. IBM./ Res. DeL'elop. 1 (1957), 131 132.
	12	Dan E. Willard, Maintaining dense sequential files in a dynamic environment (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.114-121, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802183]
	13	~WILLARD, D.E. Searching unindexed and nonuniformly generated files in loglog N time. ~S1AM J. Comput. 14 (1985), 1013-1029.
	14	~YAO, A. C., AND YAO, F. F. The complexity of searching an ordered random table. In ~Proceedings of the 17th Anmtal Sympo~izim on the Foundatlons of Computer Science. 1EEE, New ~York, 1976, pp. 173-175.

CITED BY 4

	Alan Siegel, Median bounds and their application, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.776-785, January 17-19, 1999, Baltimore, Maryland, United States
	Erik D. Demaine , Thouis Jones , Mihai Pătraşcu, Interpolation search for non-independent data, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Spyros A. Sioutas, NBDT: an efficient P2P indexing scheme for web service discovery, International Journal of Web Engineering and Technology, v.4 n.1, p.95-113, December 2008
	S. Sioutas , E. Sakkopoulos , Ch. Makris , B. Vassiliadis , A. Tsakalidis , P. Triantafillou, Dynamic Web Service discovery architecture based on a novel peer based overlay network, Journal of Systems and Software, v.82 n.5, p.809-824, May, 2009

INDEX TERMS

Primary Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Trees

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms

Keywords:
dynamization, search tree

REVIEW

"Jerzy W. Jaromczyk : Reviewer"

Interpolation search is an elementary searching technique for sorted sequences stored in arrays (or in random access contiguous storage) that provides a fast expected time if the data have a uniform distribution. The main contribut more...

Collaborative Colleagues:

Kurt Mehlhorn: colleagues

Athanasios Tsakalidis: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player