Abstract | ||
---|---|---|
Order-preserving pattern matching was first studied surprisingly recently buthas already attracted much attention. For this problem we propose aspace-efficient index that works well in practice despite its lack of goodworst-case time bounds. Our solution is based on the new approach ofdecomposing the indexed sequence into an em order component, containingordering information, and a δ component, containing informationon the absolute values. Experiments show that this approach is viable and itis the first one offering simultaneously small space usage and fast retrieval. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1109/DCC.2017.35 | 2017 Data Compression Conference (DCC) |
Keywords | Field | DocType |
order-preserving pattern matching,compact data structures,indexing | Algorithm design,Pattern recognition,Computer science,Absolute value,Theoretical computer science,Artificial intelligence,3-dimensional matching,Pattern matching | Conference |
Volume | Issue | ISSN |
49 | 6 | 1068-0314 |
ISBN | Citations | PageRank |
978-1-5090-6722-0 | 1 | 0.35 |
References | Authors | |
15 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gianni Decaroli | 1 | 1 | 0.69 |
Travis Gagie | 2 | 643 | 63.61 |
Giovanni Manzini | 3 | 1584 | 111.42 |