Order-preserving pattern matching was first studied surprisingly recently but has already attracted much attention. For this problem 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 em order component, containing ordering information, and a δ component, containing information on the absolute values. Experiments show that this approach is viable and it is the first one offering simultaneously small space usage and fast retrieval.
A Compact Index for Order-Preserving Pattern Matching
MANZINI, Giovanni
2017-01-01
Abstract
Order-preserving pattern matching was first studied surprisingly recently but has already attracted much attention. For this problem 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 em order component, containing ordering information, and a δ component, containing information on the absolute values. Experiments show that this approach is viable and it is the first one offering simultaneously small space usage and fast retrieval.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.