zbMATH — the first resource for mathematics

Log-logarithmic worst-case range queries are possible in space theta(N). (English) Zbl 0509.68106

68P20 Information storage and retrieval of data
68P05 Data structures
Full Text: DOI
[1] Fredman, M.L.; Komolós, J.; Szemerédi, E., Storing a space table with O(1) worst-case access times, Proc. 23rd IEEE symp. on foundations of computer science, 165-169, (1982)
[2] Gonnet, G.H.; Rogers, L.D.; George, J.A., An algorithmic and complexity analysis of interpolation search, Acta inform., 13, 39-52, (1980) · Zbl 0405.68057
[3] Johnson, D.B., A priority queue in which initialization and queue operations take O(log log D) time, () · Zbl 0522.68039
[4] Knuth, D.E., The art of computer programming, () · Zbl 0191.17903
[5] Knuth, D.E., Widely disseminated classroom notes on stratified trees, (1979)
[6] Pearl, Y.; Itai, A.; Avni, H., Interpolation search—alog log N search, Comm. ACM, 21, 550-554, (1978)
[7] Pearl, Y.; Reingold, E.M., Understanding the complexity of interpolation search, Inform. process. letters, 6, 6, 219-222, (1977) · Zbl 0376.68038
[8] Van Emde Boas, P., Preserving order in a forest in less than logarithmic time, Proc. 16th ann. symp. on the foundations of computer science, 75-84, (1975)
[9] Van Emde Boas, P., Preserving order in a forest in less than logarithmic time and linear space, Inform. process. lett., 6, 80-82, (1977) · Zbl 0364.68053
[10] Van Emde Boas, P.; Kaas, R.; Zijlstra, E., Design and implementation of an efficient priority queue, Math. systems theory, 10, 99-127, (1977) · Zbl 0363.60104
[11] Willard, D.E., Two very fast trie data structures, 19th ann. allerton conf. on communication, control and computing, 355-363, (1981)
[12] D.E. Willard, New trie data structures which support very fast search operations of order \(log M\), JCSS, to appear. · Zbl 0541.68037
[13] D.E. Willard, Searching nonuniformly generated files in log log N runtime, SIAM J. Comput., to appear. · Zbl 0575.68061
[14] Willard, D.E., A log log N search algorithm for nonuniform distribution, (), 3-14
[15] Willard, D.E., A new time complexity for orthogonal range queries, 20th allerton conf. on communications, control, and computing, 462-472, (1982)
[16] Yao, A.C.; Yao, F.F., The complexity of searching an ordered random table, Proc. 17th ann. symp. on the foundations of computer science, 173-177, (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.