String join using precedence count matrix
Xia Cao, Andrew Tung, Beng Chin Ooi, Kian‐Lee Tan, Shuai Cheng Li · Statistical and Scientific Database Management · 2004
In this paper; we propose a filter-and-refine string join algorithm. While the filtering phase can rapidly prune away strings that are not joinable, the refinement phase employs a comprehensive algorithm to remove the remaining false alarms. The efficiency of the proposed scheme lies in the use of the precedence count matrix (PCM) for computing the edit distance between two sequences. With PCM, the complexity of sequence comparison is a constant time. We also evaluated the proposed sequence join algorithm, and our study shows that it outperforms the known techniques.