Storing a Sparse Table with 0(1) Worst Case Access Time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Storing a Sparse Table with 0(1) Worst Case Access Time

Full text

Pdf (356 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 3 (July 1984) table of contents

Pages: 538 - 544

Year of Publication: 1984

ISSN:0004-5411

Authors

Michael L. Fredman	Univ. of California, San Diego, La Jolla
János Komlós
Endre Szemerédi

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 150, Citation Count: 121

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/828.1884 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	G. Jaeschke, Reciprocal hashing: a method for generating minimal perfect hashing functions, Communications of the ACM, v.24 n.12, p.829-833, Dec. 1981 [doi>10.1145/358800.358806]
	2	Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]
	3	Robert Endre Tarjan , Andrew Chi-Chih Yao, Storing a sparse table, Communications of the ACM, v.22 n.11, p.606-611, Nov. 1979 [doi>10.1145/359168.359175]
	4	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 121

	J. P. Schmidt , A. Siegel, On aspects of university and performance for closed hashing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.355-366, May 14-17, 1989, Seattle, Washington, United States
	Takao Miura , Wataru Matsumoto , Isamu Shioya , Yukio Wada, Extensible perfect hashing, Proceedings of the ninth international conference on Information and knowledge management, p.446-452, November 06-11, 2000, McLean, Virginia, United States
	A. Z. Broder , A. R. Karlin , P. Raghavan , E. Upfal, Trading space for time in undirected s-t connectivity, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.543-549, May 14-17, 1989, Seattle, Washington, United States
	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
	Edward A. Fox , Lenwood S. Heath , Qi Fan Chen , Amjad M. Daoud, Practical minimal perfect hash functions for large databases, Communications of the ACM, v.35 n.1, p.105-121, Jan. 1992
	Gudmund Skovbjerg Frandsen , Johan P. Hansen , Peter Bro Miltersen, Lower bounds for dynamic algebraic problems, Information and Computation, v.171 n.2, p.333-349, December 15, 2001
	Peter Bro Miltersen, Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.556-563, January 25-27, 1998, San Francisco, California, United States
	Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Randomized data structures for the dynamic closest-pair problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.301-310, January 25-27, 1993, Austin, Texas, United States
	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
	Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
	Andrei Z. Broder , Anna R. Karlin, Multilevel adaptive hashing, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.43-53, January 22-24, 1990, San Francisco, California, United States
	H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States
	Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Holger Bast , Torben Hagerup, Fast and reliable parallel hashing, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.50-61, July 21-24, 1991, Hilton Head, South Carolina, United States
	Richard Cole , Ramesh Hariharan, Faster suffix tree construction with missing suffix links, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.407-415, May 21-23, 2000, Portland, Oregon, United States
	Phillip B. Gibbons , Yossi Matias , Vijaya Ramachandran, Efficient low-contention parallel algorithms, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.236-247, June 27-29, 1994, Cape May, New Jersey, United States
	Ran Canetti , Rafail Ostrovsky, Secure computation with honest-looking parties (extended abstract): what if nobody is truly honest?, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.255-264, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Amos Fiat , Moni Naor , Jeanette P. Schmidt , Alan Siegel, Nonoblivious hashing, Journal of the ACM (JACM), v.39 n.4, p.764-782, Oct. 1992
	M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States
	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States
	Rasmus Pagh, On the cell probe complexity of membership and perfect hashing, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.425-432, July 2001, Hersonissos, Greece
	Torben Hagerup , Rajeev Raman, Fast deterministic approximate and exact parallel sorting, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.346-355, June 30-July 02, 1993, Velen, Germany
	Edward A. Fox , Qi Fan Chen , Lenwood S. Heath, A faster algorithm for constructing minimal perfect hash functions, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.266-273, June 21-24, 1992, Copenhagen, Denmark
	Amos Fiat , Moni Naor , Jeanette Schmidt , Alan Siegel, Non-oblivious hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.367-376, May 02-04, 1988, Chicago, Illinois, United States
	Moni Naor , Vanessa Teague, Anti-presistence: history independent data structures, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.492-501, July 2001, Hersonissos, Greece
	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
	Sergey Brin , Rajeev Motwani , Craig Silverstein, Beyond market baskets: generalizing association rules to correlations, ACM SIGMOD Record, v.26 n.2, p.265-276, June 1997
	Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995
	Roy Meshulam , Avi Wigderson, Expanders from symmetric codes, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Alan Siegel, On the statistical dependencies of coalesced hashing and their implications for both full and limited independence, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 22-24, 1995, San Francisco, California, United States
	Dan E. Willard, Quasilinear algorithms for processing relational calculus expressions (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.243-257, April 02-04, 1990, Nashville, Tennessee, United States
	Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States
	Marcel Waldvogel , George Varghese , Jon Turner , Bernhard Plattner, Scalable high-speed prefix matching, ACM Transactions on Computer Systems (TOCS), v.19 n.4, p.440-482, November 2001
	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
	Paolo Ferragina , Roberto Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM (JACM), v.46 n.2, p.236-280, March 1999
	Vladimír Glasnak, Sparse sets and collapse of complexity classes, Information and Computation, v.170 n.1, p.26-48, October 10, 2001
	Noga Alon , Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos, Is linear hashing good?, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.465-474, May 04-06, 1997, El Paso, Texas, United States
	Stephen Alstrup , Cyril Gavoille , Haim Kaplan , Theis Rauhe, Nearest common ancestors: a survey and a new distributed algorithm, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	M. V. Ramakrishna, Hashing practice: analysis of hashing and universal hashing, ACM SIGMOD Record, v.17 n.3, p.191-199, June 1988
	Noga Alon , Martin Dietzfelbinger , Peter Bro Miltersen , Erez Petrank , Gábor Tardos, Linear hash functions, Journal of the ACM (JACM), v.46 n.5, p.667-683, Sept. 1999
	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece
	Yossi Azar , Andrei Z. Broder , Anna R. Karlin , Eli Upfal, Balanced allocations (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.593-602, May 23-25, 1994, Montreal, Quebec, Canada
	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
	Shaibal Roy, Semantic complexity of classes of relational queries and query independent data partitioning, Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.259-267, May 29-31, 1991, Denver, Colorado, United States
	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem and related problems, Journal of Computer and System Sciences, v.65 n.1, p.38-72, August 2002
	Rasmus Pagh, A trade-off for worst-case efficient dictionaries, Nordic Journal of Computing, v.7 n.3, p.151-163, Fall 2000
	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
	Anna Ostlin , Rasmus Pagh, Uniform hashing in constant time and linear space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Wai Gen Yee , Shamkant B. Navathe, Efficient data access to multi-channel broadcast programs, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Xiaojie Gao , Kamal Jain , Leonard J. Schulman, Fair and efficient router congestion control, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	M. D. Brain , A. L. Tharp, Using Tries to Eliminate Pattern Collisions in Perfect Hashing, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.239-247, April 1994
	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States
	Piotr Indyk, Interpolation of symmetric functions and a new type of combinatorial design, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.736-740, May 01-04, 1999, Atlanta, Georgia, United States
	Torben Hagerup, Fast deterministic processor allocation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.1-10, January 25-27, 1993, Austin, Texas, United States
	Richard Cole , Ramesh Hariharan , Piotr Indyk, Tree pattern matching and subset matching in deterministic O(n log3 n)-time, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.245-254, January 17-19, 1999, Baltimore, Maryland, United States
	A. Fiat , M. Noar, Implicit O(1) probe search, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.336-344, May 14-17, 1989, Seattle, Washington, United States
	Noga Alon , Raphy Yuster , Uri Zwick, Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.326-335, May 23-25, 1994, Montreal, Quebec, Canada
	Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States
	Paul Beame , Faith E. Fich, Optimal bounds for the predecessor problem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.295-304, May 01-04, 1999, Atlanta, Georgia, United States
	Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Journal of Algorithms, v.48 n.1, p.2-15, August 2003
	Jun-ichi Aoe, An Efficient Digital Search Algorithm by Using a Double-Array Structure, IEEE Transactions on Software Engineering, v.15 n.9, p.1066-1077, September 1989
	Vassilis J. Tsotras , B. Gopinath , George W. Hart, Efficient Management of Time-Evolving Databases, IEEE Transactions on Knowledge and Data Engineering, v.7 n.4, p.591-608, August 1995
	Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004
	Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in Õ (n²) time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	C. Collberg , E. Carter , S. Debray , A. Huntwork , J. Kececioglu , C. Linn , M. Stepp, Dynamic path-based software watermarking, ACM SIGPLAN Notices, v.39 n.6, May 2004
	Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , Ayellet Tal, The Bloomier filter: an efficient data structure for static support lookup tables, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Gianni Franceschini , Roberto Grossi , J. Ian Munro , Linda Pagli, Implicit B-trees: a new data structure for the dictionary problem, Journal of Computer and System Sciences, v.68 n.4, p.788-807, June 2004
	Mikkel Thorup , Uri Zwick, Approximate distance oracles, Journal of the ACM (JACM), v.52 n.1, p.1-24, January 2005
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Cullen Linn , Saumya Debray, Obfuscation of executable code to improve resistance to static disassembly, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA
	Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
	Luc Devroye , Pat Morin, Cuckoo hashing: further analysis, Information Processing Letters, v.86 n.4, p.215-219, 31 May 2003
	Yoav Zibin , Joseph (Yossi) Gil, Incremental algorithms for dispatching in dynamically typed languages, ACM SIGPLAN Notices, v.38 n.1, p.126-138, January 2003
	Joseph (Yossi) Gil , Yoav Zibin, Efficient subtyping tests with PQ-encoding, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.819-856, September 2005
	Jun-ichi Aoe , Katsushi Morimoto , Masami Shishibori , Ki-Hong Park, A Trie Compaction Algorithm for a Large Set of Keys, IEEE Transactions on Knowledge and Data Engineering, v.8 n.3, p.476-491, June 1996
	Daniel K. Blandford , Guy E. Blelloch, Dictionaries using variable-length keys and data, with applications, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Sunil Arya , Theocharis Malamatos , David M. Mount, Space-time tradeoffs for approximate spherical range counting, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Rina Panigrahy, Efficient hashing with lookups in two memory accesses, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Y. Kadoya , M. Fuketa , El-Sayed Atlam , K. Morita , T. Sumitomo , J. Aoe, A compression algorithm using integrated record information for translation dictionaries, Information Sciences—Informatics and Computer Science: An International Journal, v.165 n.3-4, p.171-186, 19 October 2004
	Maulik A. Dave, Review of "Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenge by Michael H. Goldwasser, David S. Johnson, Catherine C. McGeoch", American Mathematical Society 2002, ACM SIGACT News, v.36 n.4, December 2005
	Sailesh Kumar , Patrick Crowley, Segmented hash: an efficient hash table implementation for high performance networking subsystems, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
	Krishnaram Kenthapadi , Rina Panigrahy, Balanced allocation on graphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.434-443, January 22-26, 2006, Miami, Florida
	Mikkel Thorup, Combinatorial power in multimedia processors, ACM SIGARCH Computer Architecture News, v.31 n.4, p.5-11, Sept 2003
	Andrej Brodnik , Svante Carlsson , Michael L. Fredman , Johan Karlsson , J. Ian Munro, Worst case constant time priority queue, Journal of Systems and Software, v.78 n.3, p.249-256, December 2005
	G. Myles , S. Nusser, Content protection for games, IBM Systems Journal, v.45 n.1, p.119-143, January 2006
	Chin-Chen Chang , Chih-Yang Lin , Henry Chou, Perfect hashing schemes for mining traversal patterns, Fundamenta Informaticae, v.70 n.3, p.185-202, April 2006
	Igor V. Popov , Saumya K. Debray , Gregory R. Andrews, Binary obfuscation using signals, Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, p.1-16, August 06-10, 2007, Boston, MA
	Fabiano C. Botelho , Nivio Ziviani, External perfect hashing for very large key sets, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Daniel K. Blandford , Guy E. Blelloch, Compact dictionaries for variable-length keys and data with applications, ACM Transactions on Algorithms (TALG), v.4 n.2, p.1-25, May 2008
	Sylvain Lefebvre , Hugues Hoppe, Perfect spatial hashing, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Nathan Linial , Ori Sasson, Non-expansive hashing, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.509-518, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Reza Curtmola , Juan Garay , Seny Kamara , Rafail Ostrovsky, Searchable symmetric encryption: improved definitions and efficient constructions, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA
	Philipp Woelfel, A construction method for optimally universal hash families and its consequences for the existence of RBIBDs, Theoretical Computer Science, v.363 n.1, p.76-84, 25 October 2006
	Michael Luby , Avi Wigderson, Pairwise independence and derandomization, Foundations and Trends® in Theoretical Computer Science, v.1 n.4, p.237-301, August 2006
	Richard F. Geary , Naila Rahman , Rajeev Raman , Venkatesh Raman, A simple optimal representation for balanced parentheses, Theoretical Computer Science, v.368 n.3, p.231-246, December, 2006
	Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in expected O(n²) time, ACM Transactions on Algorithms (TALG), v.2 n.4, p.557-577, October 2006
	Daniel Fernholz , Vijaya Ramachandran, The k-orientability thresholds for G_{n, p}, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.459-468, January 07-09, 2007, New Orleans, Louisiana
	Anna Gál , Peter Bro Miltersen, The cell probe complexity of succinct data structures, Theoretical Computer Science, v.379 n.3, p.405-417, June, 2007
	Arne Andersson , Mikkel Thorup, Dynamic ordered sets with exponential search trees, Journal of the ACM (JACM), v.54 n.3, p.13-es, June 2007
	Milan Ružić, Making deterministic signatures quickly, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.900-909, January 07-09, 2007, New Orleans, Louisiana
	Sébastien Baehni , João Barreto , Patrick Eugster , Rachid Guerraoui, Efficient distributed subtyping tests, Proceedings of the 2007 inaugural international conference on Distributed event-based systems, June 20-22, 2007, Toronto, Ontario, Canada
	Janne Nieminen , Pekka Kilpeläinen, Efficient implementation of Aho–Corasick pattern matching automata using Unicode, Software—Practice & Experience, v.37 n.6, p.669-690, May 2007
	Milan Ružić, Uniform deterministic dictionaries, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-23, March 2008
	Craig Silverstein , Sergey Brin , Rajeev Motwani, Beyond Market Baskets: Generalizing Association Rules to Dependence Rules, Data Mining and Knowledge Discovery, v.2 n.1, p.39-68, January 1998
	J. Gil , F. Meyer auf der Heide , A. Wigderson, Not all keys can be hashed in constant time, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.244-253, May 13-17, 1990, Baltimore, Maryland, United States
	M. Dietzfelbinger , F. Meyer auf der Heide, An optimal parallel dictionary, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.360-368, June 18-21, 1989, Santa Fe, New Mexico, United States
	Amjad M. Daoud, Perfect hash functions for large dictionaries, Proceedings of the ACM first workshop on CyberInfrastructure: information management in eScience, November 09-09, 2007, Lisbon, Portugal
	Iam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-17, June 2008
	Hamed Seiied Alavi , Seth Gilbert , Rachid Guerraoui, Extensible encoding of type hierarchies, ACM SIGPLAN Notices, v.43 n.1, January 2008
	Jianer Chen , Songjian Lu , Sing-Hoi Sze , Fenghui Zhang, Improved algorithms for path, matching, and packing problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.298-307, January 07-09, 2007, New Orleans, Louisiana
	Pranab Sen , S. Venkatesh, Lower bounds for predecessor searching in the cell probe model, Journal of Computer and System Sciences, v.74 n.3, p.364-385, May, 2008
	Timothy M. Chan , Eric Y. Chen, In-place 2-d nearest neighbor search, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.904-911, January 20-22, 2008, San Francisco, California
	Gianni Franceschini , Roberto Grossi, No sorting? better searching!, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-13, March 2008
	Rajeev Raman , Venkatesh Raman , Srinivasa Rao Satti, Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets, ACM Transactions on Algorithms (TALG), v.3 n.4, p.43-es, November 2007
	Martin Dietzfelbinger , Martin Hühne , Christoph Weidling, A dictionary implementation based on dynamic perfect hashing, Journal of Experimental Algorithmics (JEA), 12, June 2008
	Djamal Belazzougui , Paolo Boldi , Rasmus Pagh , Sebastiano Vigna, Monotone minimal perfect hashing: searching a sorted table with O(1) accesses, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.785-794, January 04-06, 2009, New York, New York
	Milan Ružić, Making deterministic signatures quickly, ACM Transactions on Algorithms (TALG), v.5 n.3, p.1-26, July 2009
	Rodrigo I. Silveira , Marc van Kreveld, Optimal higher order Delaunay triangulations of polygons, Computational Geometry: Theory and Applications, v.42 n.8, p.803-813, October, 2009
	Yuval Rabani , Amir Shpilka, Explicit construction of a small epsilon-net for linear threshold functions, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Zhewei Wei , Ke Yi , Qin Zhang, Dynamic external hashing: the limit of buffering, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada

INDEX TERMS

Classification:
E. Data
E.1 DATA STRUCTURES
Subjects: Tables**

F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

General Terms:
Algorithms, Measurement, Performance, Theory, Verification

REVIEW

"William Fennell Smyth : Reviewer"

This important little paper describes methods which almost achieve for searching n items what heapsort achieves for sorting: worst case execution time at the theoretical minimum order of magnitude using only n storage locat more...

Collaborative Colleagues:

Michael L. Fredman: colleagues

János Komlós: colleagues

Endre Szemerédi: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player