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.
|Titolo:||A data structure for a sequence of string accesses in external memory|
CIRIANI, VALENTINA (Primo)
|Parole Chiave:||Caching; External-memory data structure; Sequence of string searches and updates; Skip list|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||2007|
|Digital Object Identifier (DOI):||10.1145/1186810.1186816|
|Appare nelle tipologie:||01 - Articolo su periodico|