Using Hashing to Solve the Dictionary Problem (In External Memory)

Details Using Hashing to Solve the Dictionary Problem (In External Memory) Using Hashing to Solve the Dictionary Problem (In External Memory)

2011-04-14

arxiv.org/abs/1104.2799v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any \lambda >= max {lg lg n, log_{M/B} (n/B)}, we can support updates in time O(\lambda / B) and queries in sublogarithmic time, O(log_\lambda n). We also present a lower bound in the cell-probe model showing that our data structure is optimal. In the RAM, hash tables have been used to solve the dictionary problem faster than binary search for more than half a century. By contrast, our data structure is the first to beat the comparison barrier in external memory. Ours is also the first data structure to depart convincingly from the indivisibility paradigm.

Affiliated with

Also associated with

No associations

Rating

Using Hashing to Solve the Dictionary Problem (In External Memory) 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 Using Hashing to Solve the Dictionary Problem (In External Memory), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using Hashing to Solve the Dictionary Problem (In External Memory) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-166929