TY - GEN

T1 - Using hashing to solve the dictionary problem (In external memory)

AU - Iacono, John

AU - Pǎtraşcu, Mihai

PY - 2012

Y1 - 2012

N2 - 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 λ ≥ max{lg lg n, logM/B(n/B)}, we can support updates in time O(λ/B) and queries in sublogarithmic time, O(log λ 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 use 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.

AB - 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 λ ≥ max{lg lg n, logM/B(n/B)}, we can support updates in time O(λ/B) and queries in sublogarithmic time, O(log λ 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 use 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.

UR - http://www.scopus.com/inward/record.url?scp=84860126891&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860126891&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.48

DO - 10.1137/1.9781611973099.48

M3 - Conference contribution

AN - SCOPUS:84860126891

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 570

EP - 582

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -