Dynamic External Hashing: The Limit of Buffering

Details Dynamic External Hashing: The Limit of Buffering Dynamic External Hashing: The Limit of Buffering

2008-11-19

arxiv.org/abs/0811.3062v1

Computer Science

Data Structures and Algorithms

10 pages, 1 figure

Scientific paper

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 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^{\Omega(b)}$, where each I/O can read a disk block containing $b$ items. Inserting a new item into the hash table also costs $1+1/2^{\Omega(b)}$ I/Os, which is again almost the best one can do if the hash table is entirely stored on disk. However, this assumption is unrealistic since any algorithm operating on an external hash table must have some internal memory (at least $\Omega(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 query cost is targeted at $1+O(1/b^{c})$ I/Os, then it is not possible to support insertions in less than $1-O(1/b^{\frac{c-1}{4}})$ I/Os amortized, which means that the memory buffer is essentially useless. While if the query cost is relaxed to $1+O(1/b^{c})$ I/Os for any constant $c<1$, there is a simple dynamic hash table with $o(1)$ insertion cost. These results also answer the open question recently posed by Jensen and Pagh.

Affiliated with

Also associated with

No associations

Rating

Dynamic External Hashing: The Limit of Buffering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Dynamic External Hashing: The Limit of Buffering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic External Hashing: The Limit of Buffering will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-429017