### Abstract

We introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. Formally, given a dictionary of n strings S1, . . ., Sn, we aim at supporting a search sequence for m not necessarily distinct strings T1, T2, . . ., Tm, as well as inserting and deleting individual strings. The dictionary is stored on disk, where each access to a disk page fetches B items, the cost of an operation is the number of pages accessed (I/Os), and efficiency must be attained on entire sequences of string operations rather than on individual ones. Our approach relies on a novel and conceptually simple self-adjusting data structure (SASL) based on skip lists, that is also interesting per se. The search for the whole sequence T1, T2, . . ., Tm can be done in an expected number of I/Os: O (∑ ^{m} _{j=1} |T_{j}|/B + ∑^{n}_{i=1} (ni log _{B} m/ni)), where each Tj may or may not be present in the dictionary, and ni is the number of times Si is queried (i.e., the number of Tj s equal to Si ). Moreover, inserting or deleting a string Si takes an expected amortized number O( |Si |/ B + log_{B} n) of I/Os. The term ∑^{m} _{j =1} |Tj |/ B in the search formula is a lower bound for reading the input, and the term ∑^{n}_{i=1} ni log_{B} m/ni (entropy of the query sequence) is a standard information-theoretic lower bound.We regard this result as the static optimality theorem for external-memory string access, as compared to Sleator and Tarjan's classical theorem for numerical dictionaries [Sleator and Tarjan 1985]. Finally,we reformulate the search bound if a cache is available, taking advantage of common prefixes among the strings examined in the search.

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

Article number | 1219952 |

Journal | ACM Transactions on Algorithms |

Volume | 3 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1 2007 |

### Keywords

- Caching
- External-memory data structure
- Sequence of string searches and updates
- Skip list

### ASJC Scopus subject areas

- Mathematics (miscellaneous)

## Fingerprint Dive into the research topics of 'A data structure for a sequence of string accesses in external memory'. Together they form a unique fingerprint.

## Cite this

*ACM Transactions on Algorithms*,

*3*(1), [1219952]. https://doi.org/10.1145/1186810.1186816