Cited By
View all- Navarro GRojas-Ledesma J(2020)Predecessor SearchACM Computing Surveys10.1145/340937153:5(1-35)Online publication date: 28-Sep-2020
Predecessor queries in constant time?
Pages 238 - 248
Abstract
In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports $O(\sqrt{{\rm log}n})$ queries in O(1) time per query and requires $O(n^{\epsilon\sqrt{{\rm log}n}})$ space for any ε > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary $N = \Omega(n^{\epsilon\sqrt{{\rm log}n}})$ where N is the size of the universe. We also present a data structure that answers O(log log N) predecessor queries in O(1) time per query and requires $O(n^{\epsilon{\rm log log} {\it N}})$ space for any ε > 0. The method of solution relies on a certain way of searching for predecessors of all elements of the query in parallel.
In a general case, our approach leads to a data structure that supports p(n) queries in $O(\sqrt{{\rm log} n}/p(n))$ time per query and requires O(n$^{p({\it n})}$) space for any $p(n) =O(\sqrt{{\rm log}n})$, and a data structure that supports p(N) queries in O(log log N/p(N)) time per query and requires O(n$^{p({\it N})}$) space for any p(N)=O(log log N).
References
[1]
G. M. Adelson-Velskii, E.M. Landis, An algorithm for the organization of information, Dokladi Akademii Nauk SSSR, 146(2):1259-1262, 1962.
[2]
M. Ajtai, M. L. Fredman, J. Komlòs, Hash Functions for Priority Queues, Information and Control 63(3): 217-225 (1984).
[3]
S. Alstrup, G. S. Brodal, T. Rauhe, Optimal static range reporting in one dimension, STOC 2001, pp. 476-482.
[4]
A. Andersson, Sublogarithmic Searching without Multiplications, FOCS 1995, pp. 655-663.
[5]
A. Andersson, Faster Deterministic Sorting and Searching in Linear Space, FOCS 1996, pp. 135-141.
[6]
A. Andersson, T. Hagerup, S. Nilsson, R. Raman, Sorting in linear time? STOC 1995, pp. 427-436.
[7]
A. Andersson, M. Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, STOC 2000, pp. 335-342.
[8]
A. Andersson, M. Thorup, Dynamic Ordered Sets with Exponential Search Trees, The Computing Research Repository (CoRR), cs.DS/0210006: (2002). Available at http://arxiv.org/abs/cs.DS/0210006.
[9]
P. Beame, F. E. Fich, Optimal Bounds for the Predecessor Problem and Related Problems, J. Comput. Syst. Sci. 65(1): 38-72 (2002).
[10]
A. Brodnik, S. Carlsson, J. Karlsson, J. I. Munro, Worst case constant time priority queue, SODA 2001, pp. 523-528.
[11]
L. Carter, M. N. Wegman, Universal Classes of Hash Functions. J. Comput. Syst. Sci. 18(2): 143-154 (1979).
[12]
P. van Emde Boas, Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space, Inf. Process. Lett. 6(3): 80-82 (1977).
[13]
P. van Emde Boas, R. Kaas, E. Zijlstra, Design and Implementation of an Efficient Priority Queue, Mathematical Systems Theory 10: 99-127 (1977).
[14]
M. L. Fredman, D. E. Willard, Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths, J. Comput. Syst. Sci. 48(3): 533-551 (1994).
[15]
T. Hagerup, Sorting and Searching on the Word RAM, STACS 1998, pp. 366-398.
[16]
Y. Han, Deterministic sorting in O(n log log n) time and linear space, STOC 2002, pp. 602-608.
[17]
B. Gum, R. Lipton, Cheaper by the Dozen: Batched Algorithms. 1st SIAM International Conference on Data Mining, 2001. Available at http://www.math.grin.edu/gum/papers/batched/
[18]
K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Springer 1984.
[19]
W. J. Paul, S. Simon, Decision Trees and Random Access Machines, International Symposium on Logik and Algorithmic, Zürich, pp 331-340, 1980.
[20]
D. E. Willard, Log-Logarithmic Worst-Case Range Queries are Possible in Space Theta(N), Inf. Process. Lett. 17(2): 81-84 (1983).
[21]
D. E. Willard, New Trie Data Structures Which Support Very Fast Search Operations, J. Comput. Syst. Sci. 28(3): 379-394 (1984).
[22]
A. C.-C. Yao Should Tables Be Sorted?, J. ACM 28(3): 615-628 (1981).
- Predecessor queries in constant time?
Recommendations
Time-space trade-offs for predecessor search
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingWe develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an ...
Constant-Time Randomized Parallel String Matching
Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern ...
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search
FOCS '14: Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer ScienceWe present a data structure representing a dynamic set S of w-bit integers on a w-bit word RAM. With |S| = n and w ≥ log n and space O(n), we support the following standard operations in O(log n/log w) time: insert(x) sets S = S + {x}. delete(x) sets S =...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- Ministerio de Educación y Ciencia: Ministerio de Educación y Ciencia
- Universitat de les Illes Balears: Universitat de les Illes Balears
- EATCS: European Association for Theoretical Computer Science
- Universitat Politècnica de Catalunya: Universitat Politècnica de Catalunya
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 03 October 2005
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Feb 2025
Other Metrics
Citations
Cited By
View all- Navarro GRojas-Ledesma J(2020)Predecessor SearchACM Computing Surveys10.1145/340937153:5(1-35)Online publication date: 28-Sep-2020