Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- Peyman Afshani
- Michael A. Bender, State University New York, Stony Brook ,
- Martin Farach-Colton, Rutgers, the State University of New Jersey ,
- Jeremy T. Fineman, Georgetown University ,
- Mayank Goswami, City University of New York ,
- Meng Tsung Tsai, Rutgers, the State University of New Jersey

Dictionaries remain the most well studied class of data structures. A dictionary supports insertions, deletions, membership queries, and usually successor, predecessor, and extract-min. In a RAM, all such operations take O(logN) time on N elements. Dictionaries are often cross-referenced as follows. Con- sider a set of tuples fhai; bi; ci : : :ig. A database might in- clude more than one dictionary on such a set, for example, one indexed on the a's, another on the b's, and so on. Once again, in a RAM, inserting into a set of L cross-referenced dictionaries takes O(LlogN) time, as does deleting. The situation is more interesting in external memory. On a Disk Access Machine (DAM), B-trees achieve O(logB N) I/Os for insertions and deletions on a single dictionary and K-element range queries take optimal O(logB N + K=B) I/Os. These bounds are also achievable by a B-tree on cross-referenced dictionaries, with a slowdown of an L factor on insertion and deletions. In recent years, both the theory and practice of external- memory dictionaries has been revolutionized by write- optimization techniques. A dictionary is write optimized if it is close to a B-tree for query time while beating B- trees on insertions. The best (and optimal) dictionaries achieve a substantially improved insertion and deletion cost of, amortized I/Os on a single dictionary while maintaining optimal O(log1+B" N +K=B)- I/O range queries. Although write optimization still helps for insertions into cross-referenced dictionaries, its value for deletions would seem to be greatly reduced. A deletion into a cross- referenced dictionary only specifies a key a. It seems to be necessary to look up the associated values b; c : : : in order to delete them from the other dictionaries. This takes (logB N) I/Os, well above the per-dictionary write- optimization budget of O( So the total deletion cost is O(logB N + L In short, for deletions, write optimization offers an ad- vantage over B-trees in that L multiplies a lower order term, but when L = 2, write optimization seems to offer no asymp- totic advantage over B-trees. That is, no known query- optimal solution for pairs of cross-referenced dictionaries seem to beat B-trees for deletions. In this paper, we show a lower bound establishing that a pair of cross-referenced dictionaries that are optimal for range queries and that supports deletions cannot match the write optimization bound available to insert-only dictionar- ies. This result thus establishes a limit to the applicability of write-optimization techniques on which many new databases and file systems are based.

Original language | English |
---|---|

Title of host publication | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |

Editors | P.N. Klein |

Number of pages | 10 |

Publisher | Association for Computing Machinery |

Publication year | 16 Jan 2017 |

Pages | 1523-1532 |

ISBN (Electronic) | 9781611974782 |

Publication status | Published - 16 Jan 2017 |

Event | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain Duration: 16 Jan 2017 → 19 Jan 2017 |

Conference | 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 |
---|---|

Land | Spain |

By | Barcelona |

Periode | 16/01/2017 → 19/01/2017 |

Sponsor | Universitat Politècnica de Catalunya |

See relations at Aarhus University Citationformats

ID: 120308558