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.
A data structure for a sequence of string accesses in external memory / V. Ciriani, P. Ferragina, F. Luccio, S. Muthukrishnan. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 3:1(2007), p. 1219952.Article 6. [10.1145/1186810.1186816]
A data structure for a sequence of string accesses in external memory
V. CirianiPrimo
;
2007
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.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.