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 -