Portal de Periódicos da CAPES

New Algorithms for δγ-Order Preserving Matching

2018; Sergio A. Rojas; Volume: 23; Issue: 2 Linguagem: Inglês

10.14483/23448393.13248

2344-8393

Juan Mendivelso, Rafael Niquefa, Yoan J. Pinzón, Germán Hernández,

Natural Language Processing Techniques

Context: Order-preserving matching regards the relative order of strings. However, its application areas require more flexibility in the matching paradigm. We advance in this direction in this paper that extends our previous work [27].Method: We define γ -order preserving matching as an approximate variant of order-preserving matching. We devise two solutions for it based on segment and Fenwick trees: segtreeBA and bitBA.Results: We experimentally show the efficiency of our algorithms compared to the ones presented in [26] (naiveA and updateBA). Also, we present applications of our approach in music retrieval and stock market analysis.Conclusions: Even though the worst-case time complexity of the proposed algorithms (namely, O(nm log m)) is higher than the Ѳ(nm)-time complexity of updateBA, their Ω (n log n) lower bound makes them more efficient in practice. On the other hand, we show that our approach is useful to identify similarity in music melodies and stock price trends through real application examples.