### Abstract

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, log_{M/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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |

Publisher | Association for Computing Machinery |

Pages | 570-582 |

Number of pages | 13 |

ISBN (Print) | 9781611972108 |

DOIs | |

State | Published - 2012 |

Event | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

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

Country | Japan |

City | Kyoto |

Period | 1/17/12 → 1/19/12 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Using hashing to solve the dictionary problem (In external memory)'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012*(pp. 570-582). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611973099.48