A compact index for order-preserving pattern matching

Gianni Decaroli, Travis Gagie, Giovanni Manzini

Risultato della ricerca: Contributo su rivistaArticolo in rivistapeer review

Abstract

Order-preserving pattern matching has been introduced recently, but it has already attracted much attention. Given a reference sequence and a pattern, we want to locate all substrings of the reference sequence whose elements have the same relative order as the pattern elements. For this problem, we consider the offline version in which we build an index for the reference sequence so that subsequent searches can be completed very efficiently. We propose a space-efficient index that works well in practice despite its lack of good worst-case time bounds. Our solution is based on the new approach of decomposing the indexed sequence into an order component, containing ordering information, and a δ component, containing information on the absolute values. Experiments show that this approach is viable, is faster than the available alternatives, and is the first one offering simultaneously small space usage and fast retrieval.

Lingua originaleInglese
pagine (da-a)1041-1051
Numero di pagine11
RivistaSoftware - Practice and Experience
Volume49
Numero di pubblicazione6
DOI
Stato di pubblicazionePubblicato - giu 2019
Pubblicato esternamente

Fingerprint

Entra nei temi di ricerca di 'A compact index for order-preserving pattern matching'. Insieme formano una fingerprint unica.

Cita questo