Andrew Chi-Chih Yao
- 1 AHO, A V., HOPCROFT, J.E, AND ULLMAN, J D The Design and Analysls of Computer Algorithms Addison-Wesley, Reading, Mass., 1974 Google Scholar
- 2 BENTLEY, J, DETIG, D, GUmAS, L,, AND SAXE, J. An optimal data structure for mmmaal-storage dynamic member searching Unpubhshed manuscript.Google Scholar
- 3 BERGE, C Graphs and Hypergraphs North-Holland, Amsterdam, 1973 Google Scholar
- 4 DOBKIN, D., AND LIPTON, R J Multidimensional search problems SIAM J Comput 5 (1976), 181- 186Google Scholar
- 5 ELIAS, P Efficmnt storage and remeval by content and address of stauc files J. ACM 21, 2 (April 1974), 246-260 Google Scholar
- 6 ELIAS, P., AND FLOWER, R A The complexity of some simple retrieval problems J A CM 22, 3 (July 1975), 367-379 Google Scholar
- 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.Google Scholar
- 8 KNUTH, D E The Art of Computer Programming, 11ol 1. Fundamental Algomhms Addlslon-Wesley, Reading, Mass, 1968 Google Scholar
- 9 KNUTH, D E The Art of Computer Programming, Vol 3 Sorting and Searching. Addlslon-Wesley, Reading, Mass, 1973 Google Scholar
- 10 MINSKY, M., AND PAPERT, S Perceptrons. MIT Press, Cambridge, Mass, 1969Google Scholar
- 11 MULLER, D E, AND PREPARATA, F P Bounds to complexities of networks for sorting and for switching J ACM 22, 2 (April 1975), 195-201 Google Scholar
- 12 MUNRO, J I, AND SUWANDA, H Implicit data structures Proc 1 lth Ann. ACM Symp on Theory of Computing, Atlanta, Georgia, 1979, pp 108-117. Google Scholar
- 13 RIVEST, R.L Optimal arrangement of keys in a hash table J. ACM 25, 2 (April 1978), 200-209. Google Scholar
- 14 SHAMOS, M I. Geometric complexity Proc 7th Ann ACM Syrup. on Theory of Computing, Albuquerque, N M, 1975, pp 224-233 Google Scholar
- 15 SNYDER, L On uniquely representable data structures Proc 18th Ann IEEE Symp on Foundations of Computer Science, Providence, R I, 1977, pp 142-146Google Scholar
- 16 SPRUGNOLI, R Perfect hashing functions A single probe retrieving method for static sets Commun ACM 20, 11 (Nov 1977), 841-850 Google Scholar
- 17 TARJAN, R E Storing a sparse table Stanford Computer Science Dep Rep STAN-CS-78-683, December 1978 (this is a preliminary version of {19}) Google Scholar
- 18 TARjAN, R.E A class of algorithms which require nonlinear time to maintain disjoint sets J Comput Syst Sct. 18 (1979), 110-127Google Scholar
- 19 TARJAN, R E, AND YAO, A C Storing a sparse table Commun ACM 22, 11 (Nov 1979), 606-611 Google Scholar
- 20 VAt~ EMDE BOAS, P, KAAS, R, AND ZIJLSTRA, E Design and implementation of an efficient priority queue Math Syst Theory 10(1977), 99-127Google Scholar
- 21 VILFAN, B Lower bounds for the size of expressions for certain functions in d-ary logic Theor Comput Scl 2 (1976), 249-269.Google Scholar
Index Terms
- Should Tables Be Sorted?
Recommendations
Scalable blind search and broadcasting over Distributed Hash Tables
Typical blind search algorithms in P2P networks generate a significant amount of duplicate query messages in order to increase the success rate. We present a novel framework, named Recursive Partitioning Search (RPS), for blind search over structured ...
Enabling Dynamic Querying over Distributed Hash Tables
Dynamic querying (DQ) is a search technique used in unstructured peer-to-peer (P2P) networks to minimize the number of nodes that is necessary to visit to reach the desired number of results. In this paper, we introduce the use of the DQ technique in ...
Stable High-Capacity One-Hop Distributed Hash Tables
ISCC '06: Proceedings of the 11th IEEE Symposium on Computers and CommunicationsMost research on Distributed Hash Tables (DHTs) assumes ephemeral, lightly loaded deployments. Each node has a lifetime of a few hours and initiates a lookup once every few seconds or minutes. However, in giant internet data centers, each node has a ...
Comments