OpenMP Implementation of Parallel Longest Common Subsequence Algorithm for Mathematical Expression Retrieval

Given a mathematical expression in LaTeX or MathML format, retrieval algorithm extracts similar expressions from a database. In our previous work, we have used Longest Common Subsequence (LCS) algorithm to match two expressions of lengths, m and n, which takes O(mn) time complexity. If there are T database expressions, total complexity is O(Tmn), and an increase in T also increases this complexity. In the present work, we propose to use parallel LCS algorithm in our retrieval process. Parallel LCS has O(max(m,n)) time complexity with max(m,n) processors and total complexity can be reduced to O(Tmax(m,n)). For our experimentation, OpenMP based implementation has been used on Intel i3 processor with 4 cores. However, for smaller expressions, parallel version takes more time as the implementation overhead dominates the algorithmic improvement. As such, we have proposed to use parallel version, selectively, only on larger expressions, in our retrieval algorithm to achieve better performance. We have compared the sequential and parallel versions of our ME retrieval algorithm, and the performance results have been reported on a database of 829 mathematical expressions.