Dynamic external hashing: the limit of buffering

ABSTRACT

Hash tables are one of the most fundamental data structures in computer science, in both theory and practice. They are especially useful in external memory, where their query performance approaches the ideal cost of just one disk access. Knuth [16] gave an elegant analysis showing that with some simple collision resolution strategies such as linear probing or chaining, the expected average number of disk I/Os of a lookup is merely 1+1/2^Ω(b), where each I/O can read and/or write a disk block containing b items. Inserting a new item into the hash table also costs 1+1/2^Ω(b) I/Os, which is again almost the best one can do if the hash table is entirely stored on disk. However, this requirement is unrealistic since any algorithm operating on an external hash table must have some internal memory (at least Ω(1) blocks) to work with. The availability of a small internal memory buffer can dramatically reduce the amortized insertion cost to o(1) I/Os for many external memory data structures. In this paper we study the inherent query-insertion tradeoff of external hash tables in the presence of a memory buffer. In particular, we show that for any constant c>1, if the expected average successful query cost is targeted at 1+O(1/bc) I/Os, then it is not possible to support insertions in less than 1-O(1/bc-1/6) I/Os amortized, which means that the memory buffer is essentially useless. While if the query cost is relaxed to 1+O(1/bc) I/Os for any constant c<1, there is a simple dynamic hash table with o(1) insertion cost.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.
• 3: Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509950]
• 4: Lars Arge , Vasilis Samoladas , Ke Yi, Optimal External Memory Planar Point Enclosure, Algorithmica, v.54 n.3, p.337-352, May 2009 [doi>10.1007/s00453-007-9126-2]
• 5: J. L. Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244--251, 1979.
• 6: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 7: Gerth Stolting Brodal , Rolf Fagerberg, Lower bounds for external memory dictionaries, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 8: J. Carter and M. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143--154, 1979.
• 9: Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm Meyer auf der Heide , Hans Rohnert , Robert E. Tarjan, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
• 10: R. Fadel , K. V. Jakobsen , J. Katajainen , J. Teuhola, Heaps and heapsort on secondary storage, Theoretical Computer Science, v.220 n.2, p.345-362, June 17, 1999 [doi>10.1016/S0304-3975(99)00006-7]
• 11: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• 12: 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]
• 13: Hector Garcia-Molina , Jeffrey D. Ullman , Jennifer Widom, Database Systems: The Complete Book, Prentice Hall Press, Upper Saddle River, NJ, 2008
• 14: 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 [doi>10.1145/505241.505244]
• 15: Morten Skaarup Jensen , Rasmus Pagh, Optimality in External Memory Hashing, Algorithmica, v.52 n.3, p.403-411, October 2008 [doi>10.1007/s00453-007-9155-x]
• 16: D. E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, Reading, MA, 1973.
• 17: Witold Litwin, Linear hashing: a new tool for file and table addressing, Proceedings of the sixth international conference on Very Large Data Bases, p.212-223, October 01-03, 1980, Montreal, Quebec, Canada
• 18: Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004 [doi>10.1016/j.jalgor.2003.12.002]
• 19: Jeffrey Scott Vitter, Algorithms and Data Structures for External Memory, Now Publishers Inc., Hanover, MA, 2008
• 20: Andrew Chi-Chin Yao, Probabilistic computations: Toward a unified measure of complexity, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, p.222-227, September 30-October 31, 1977
• 21: 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 [doi>10.1145/1559795.1559825]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

General Terms:
Theory

Keywords:
dynamic hash table, lower bound, successful query