Bounded Occurrence Edit Distance: A New Metric for String Similarity Joins with Edit Distance Constraints
The 40th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM2014),
Lecture Notes in Computer Science Vol.8324, pp.363-374
(2014), [peer-reviewed]
Event Date:
January 26-29, 2014
Abstract / 概要
Given two sets of strings and a similarity function on strings, similarity joins attempt to find all similar pairs of strings from each respective set. In this paper, we focus on similarity joins with respect to the edit distance, and propose a new metric called the bounded occurrence edit distance and a filter based on the metric. Using the filter, we can reduce the total time required to solve similarity joins because the metric can be computed faster than the edit distance by bitwise operations. We demonstrate the effectiveness of the filter through experiments.