Optimal bounds for the predecessor problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal bounds for the predecessor problem

Full text

Pdf (924 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 295 - 304

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Paul Beame	Computer Science and Engineering, University of Washington, Seattle, WA
Faith E. Fich	Department of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 1A4

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 52, Citation Count: 17

Additional Information:

references cited by index terms 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/301250.301323 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	M Ajtai , M Fredman , J Komlós, Hash functions for priority queues, Information and Control, v.63 n.3, p.217-225, Dec. 1986 [doi>10.1016/S0019-9958(84)80015-7]
	2	Mikl6s Ajtai. A lower bound for finding predecessors in Yao's cell probe model. Combinatorica, 8:235-247, 1988.
	3	A. Andersson, Sublogarithmic searching without multiplications, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.655, October 23-25, 1995
	4	A. Andersson, Faster deterministic sorting and searching in linear space, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.135, October 14-16, 1996
	5	A. Andersson, Static Dictionaries on RAMs: Query Time is Necessary and Sufficient, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.441, October 14-16, 1996
	6	A. Andersson and M. Thorup. Exponential search trees for faster deterministic searching, sorting and priority queues in linear space. Manuscript.
	7	Andrej Brodnik , Peter Bro Miltersen , J. Ian Munro, Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.426-439, August 06-08, 1997
	8	J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143- 154, 1979.
	9	Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301325]
	10	V. Chvfitat. Probabilistic methods in graph theory. Annals of Operations Research, 1:171-182, 1984.
	11	Martin Dietzfelbinger, Universal Hashing and k-Wise Independent Random Variables via Integer Arithmetic without Primes, Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, p.569-580, February 22-24, 1996
	12	Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
	13	Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
	14	M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
	15	Faith E. Fich , Peter Bro Miltersen, Tables Should Be Sorted (On Random Access Machines), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.482-493, August 16-18, 1995
	16	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	17	M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
	18	Michael L. Fredman , Dan E. Willard, Surpassing the information theoretic bound with fusion trees, Journal of Computer and System Sciences, v.47 n.3, p.424-436, Dec. 1993 [doi>10.1016/0022-0000(93)90040-4]
	19	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
	20	Peter Bro Miltersen, The Bit Probe Complexity Measure Revisited, Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, p.662-671, February 25-27, 1993
	21	Peter Bro Miltersen, Lower bounds for union-split-find related problems on random access machines, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.625-634, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195415]
	22	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
	23	Rajeev Raman, Priority Queues: Small, Monotone and Trans-dichotomous, Proceedings of the Fourth Annual European Symposium on Algorithms, p.121-137, September 25-27, 1996
	24	P. Van Erode Boas. Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters, 6:80-82, 1977.
	25	E Van Erode Boas, R Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, i977.
	26	D. E. Willard. Log-logarithmic worst case range queries are possible in space O(n). Information Processing Letters, 17:81-84, 1983.
	27	Bing Xiao, New bounds in cell probe model, University of California at San Diego, La Jolla, CA, 1992
	28	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	29	Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]

CITED BY 17

	David Eppstein , S. Muthukrishnan, Internet packet filter management and rectangle geometry, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.827-835, January 07-09, 2001, Washington, D.C., United States
	Ahto Buldas , Peeter Laud , Helger Lipmaa, Eliminating counterevidence with applications to accountable certificate management, Journal of Computer Security, v.10 n.3, p.273-296, 2002
	Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Succinct indexable dictionaries with applications to encoding k-ary trees and multisets, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.233-242, January 06-08, 2002, San Francisco, California
	Rasmus Pagh, Faster deterministic dictionaries, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.487-493, January 09-11, 2000, San Francisco, California, United States
	Arne Andersson , Mikkel Thorup, Dynamic string searching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.307-308, January 07-09, 2001, Washington, D.C., United States
	Stephen Alstrup , Thore Husfeldt , Theis Rauhe, A cell probe lower bound for dynamic nearest-neighbor searching, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.779-780, January 07-09, 2001, Washington, D.C., United States
	Andrej Brodnik , Svante Carlsson , Johan Karlsson , J. Ian Munro, Worst case constant time priority queue, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.523-528, January 07-09, 2001, Washington, D.C., United States
	Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece
	Stephen Alstrup , Gerth Brodal , Theis Rauhe, Optimal static range reporting in one dimension, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.476-482, July 2001, Hersonissos, Greece
	Ahto Buldas , Peeter Laud , Helger Lipmaa, Accountable certificate management using undeniable attestations, Proceedings of the 7th ACM conference on Computer and communications security, p.9-17, November 01-04, 2000, Athens, Greece
	Arne A. Andersson , Mikkel Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.335-342, May 21-23, 2000, Portland, Oregon, United States
	Mikkel Thorup, On AC⁰ implementations of fusion trees and atomic heaps, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Rasmus Pagh, A trade-off for worst-case efficient dictionaries, Nordic Journal of Computing, v.7 n.3, p.151-163, Fall 2000
	Baruch Awerbuch , Christian Scheideler, The hyperring: a low-congestion deterministic data structure for distributed environments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Kunihiko Sadakane , Roberto Grossi, Squeezing succinct data structures into entropy bounds, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1230-1239, January 22-26, 2006, Miami, Florida
	Paolo Ferragina , Igor Nitto , Rossano Venturini, On the bit-complexity of Lempel-Ziv compression, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.768-777, January 04-06, 2009, New York, New York
	Ankur Gupta , Wing-Kai Hon , Rahul Shah , Jeffrey Scott Vitter, Compressed data structures: Dictionaries and data-aware measures, Theoretical Computer Science, v.387 n.3, p.313-331, November, 2007