ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Should Tables Be Sorted?
Full text PdfPdf (800 KB)
Source Journal of the ACM (JACM) archive
Volume 28 ,  Issue 3  (July 1981) table of contents
Pages: 615 - 628  
Year of Publication: 1981
ISSN:0004-5411
Author
Andrew Chi-Chih Yao  Department of Computer Science, Stanford University, Stanford, California
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 8,   Downloads (12 Months): 74,   Citation Count: 55
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/322261.322274
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
Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
 
2
BENTLEY, J, DETIG, D, GUmAS, L,, AND SAXE, J. An optimal data structure for mmmaal-storage dynamic member searching Unpubhshed manuscript.
 
3
C. Berge, Graphs and Hypergraphs, Elsevier Science Ltd, 1985
 
4
DOBKIN, D., AND LIPTON, R J Multidimensional search problems SIAM J Comput 5 (1976), 181- 186
5
Peter Elias, Efficient Storage and Retrieval by Content and Address of Static Files, Journal of the ACM (JACM), v.21 n.2, p.246-260, April 1974  [doi>10.1145/321812.321820]
6
Peter Elias , Richard A. Flower, The Complexity of Some Simple Retrieval Problems, Journal of the ACM (JACM), v.22 n.3, p.367-379, July 1975  [doi>10.1145/321892.321899]
 
7
GONNET, G H Average lower bounds for open-addressing hash coding. Proc Conf on Theoretical Computer Science, Waterloo, Ontario, Canada, August 1977, pp 159-162.
 
8
Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
 
9
Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
 
10
MINSKY, M., AND PAPERT, S Perceptrons. MIT Press, Cambridge, Mass, 1969
11
David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975  [doi>10.1145/321879.321882]
12
J. Ian Munro , Hendra Suwanda, Implicit data structures (Preliminary Draft), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.108-117, April 30-May 02, 1979, Atlanta, Georgia, United States  [doi>10.1145/800135.804404]
13
Ronald L. Rivest, Optimal Arrangement of Keys in a Hash Table, Journal of the ACM (JACM), v.25 n.2, p.200-209, April 1978  [doi>10.1145/322063.322065]
14
Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States  [doi>10.1145/800116.803772]
 
15
SNYDER, L On uniquely representable data structures Proc 18th Ann IEEE Symp on Foundations of Computer Science, Providence, R I, 1977, pp 142-146
16
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]
 
17
Robert E Tarjan, Storing a sparse table, Stanford University, Stanford, CA, 1978
 
18
TARjAN, R.E A class of algorithms which require nonlinear time to maintain disjoint sets J Comput Syst Sct. 18 (1979), 110-127
19
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]
 
20
VAt~ EMDE BOAS, P, KAAS, R, AND ZIJLSTRA, E Design and implementation of an efficient priority queue Math Syst Theory 10(1977), 99-127
 
21
VILFAN, B Lower bounds for the size of expressions for certain functions in d-ary logic Theor Comput Scl 2 (1976), 249-269.

CITED BY  55
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
Greg N. Frederickson , Nancy A. Lynch, The impact of synchronous communication on the problem of electing a leader in a ring, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.493-503, December 1984
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
C. Slot , P. van Emde Boas, On tape versus core an application of space efficient perfect hash functions to the invariance of space, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.391-400, December 1984
Moni Naor , Larry Stockmeyer, What can be computed locally?, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.184-193, May 16-18, 1993, San Diego, California, 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
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
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
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
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
Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, 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
Shlomo Moran , Marc Snir , Udi Manber, Applications of Ramsey's theorem to decision tree complexity, Journal of the ACM (JACM), v.32 n.4, p.938-949, Oct. 1985
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
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
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
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
Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987
Micah Adler, Asynchronous shared memory search structures, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.42-51, June 24-26, 1996, Padua, Italy
Monika Rauch, Improved data structures for fully dynamic biconnectivity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.686-695, May 23-25, 1994, Montreal, Quebec, Canada
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
Omer Barkol , Yuval Rabani, Tighter lower bounds for nearest neighbor search and related problems in the cell probe model, Journal of Computer and System Sciences, v.64 n.4, p.873-896, June 2002
Thore Husfeldt , Theis Rauhe , Søren Skyum, Lower bounds for dynamic transitive closure, planar point location, and parantheses matching, Nordic Journal of Computing, v.3 n.4, p.323-336, Winter 1996
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
T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Stephen Alstrup , Amir M. Ben-Amram , Theis Rauhe, Worst-case and amortised optimality in union-find (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.499-506, May 01-04, 1999, Atlanta, Georgia, United States
Rasmus Pagh, A trade-off for worst-case efficient dictionaries, Nordic Journal of Computing, v.7 n.3, p.151-163, Fall 2000
Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Joseph M. Hellerstein , Elias Koutsoupias , Daniel P. Miranker , Christos H. Papadimitriou , Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002
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
Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991
Erik D. Demaine , Alejandro López-Ortiz, A linear lower bound on index size for text retrieval, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.289-294, January 07-09, 2001, Washington, D.C., 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
Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Mihai Pǎtraşcu , Erik D. Demaine, Lower bounds for dynamic connectivity, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
Ding Liu, A strong lower bound for approximate nearest neighbor searching, Information Processing Letters, v.92 n.1, p.23-29, 16 October 2004
Amnon Ta-Shma, Storing information with extractors, Information Processing Letters, v.83 n.5, p.267-274, 15 September 2002
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
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
Loukas Georgiadis , Robert E. Tarjan , Renato F. Werneck, Design of data structures for mergeable trees, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.394-403, January 22-26, 2006, Miami, Florida
T. S. Jayram , Subhash Khot , Ravi Kumar , Yuval Rabani, Cell-probe lower bounds for the partial match problem, Journal of Computer and System Sciences, v.69 n.3, p.435-447, November 2004
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
Allan Borodin , Rafail Ostrovsky , Yuval Rabani, Lower bounds for high dimensional nearest neighbor search and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.312-321, May 01-04, 1999, Atlanta, Georgia, United States
Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States
Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Ho-Leung Chan , Wing-Kai Hon , Tak-Wah Lam , Kunihiko Sadakane, Compressed indexes for dynamic text collections, ACM Transactions on Algorithms (TALG), v.3 n.2, p.21-es, May 2007
Erik D. Demaine , Mihai Patrascu, Tight bounds for dynamic convex hull queries (again), Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, ACM Transactions on Algorithms (TALG), v.3 n.2, p.13-es, May 2007
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
Yakov Nekrich, Orthogonal range searching in linear and almost-linear space, Computational Geometry: Theory and Applications, v.42 n.4, p.342-351, May, 2009
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
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
Alexander Golynski, Cell probe lower bounds for succinct data structures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.625-634, January 04-06, 2009, New York, New York
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
Ke Yi, Dynamic indexability and lower bounds for dynamic one-dimensional range query indexes, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  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:
Management, Measurement, Performance, Theory, Verification

Collaborative Colleagues:
Andrew Chi-Chih Yao: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player