TY - JOUR AU - Mendivelso, Juan AU - Niquefa, Rafael AU - Pinzón, Yoan AU - Hernández, Germán PY - 2018/05/31 Y2 - 2024/03/28 TI - New Algorithms for δγ-Order Preserving Matching JF - Ingeniería JA - Ing. VL - 23 IS - 2 SE - Computational Intelligence DO - 10.14483/23448393.13248 UR - https://revistas.udistrital.edu.co/index.php/reving/article/view/13248 SP - 190-202 AB - <p><strong>Context</strong>: 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].</p><p><strong>Method</strong>: 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: <em>segtreeBA</em> and<em> bitBA</em>.</p><p><strong>Results</strong>: We experimentally show the efficiency of our algorithms compared to the ones presented in [26] (<em>naiveA </em>and<em> updateBA</em>). Also, we present applications of our approach in music retrieval and stock market analysis.</p><p><strong>Conclusions</strong>: Even though the worst-case time complexity of the proposed algorithms (namely, O(<em>nm</em> log <em>m</em>)) is higher than the Ѳ(<em>nm</em>)-time complexity of <em>updateBA</em>, their Ω (<em>n</em> log <em>n</em>) 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.</p> ER -