A Compact Index for Order-Preserving Pattern Matching

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.