|
| | | |
PartSS: An Efficient Partition-based Filtering for Edit Distance Constraints
Li, Z., Sitbon, L. and Zhou, X.
This paper introduces PartSS, a new partition-based fil- tering for tasks performing string comparisons under edit distance constraints. PartSS offers improvements over the state-of-the-art method NGPP with the implementation of a new partitioning scheme and also improves filtering abilities by exploiting theoretical results on shifting and scaling ranges, thus accelerating the rate of calculating edit distance between strings. PartSS filtering has been implemented within two major tasks of data integration: similarity join and approximate membership extraction under edit distance constraints. The evaluation on an extensive range of real-world datasets demonstrates major gain in efficiency over NGPP and QGrams approaches. |
Cite as: Li, Z., Sitbon, L. and Zhou, X. (2011). PartSS: An Efficient Partition-based Filtering for Edit Distance Constraints. In Proc. Australasian Database Conference (ADC 2011) Perth, Australia. CRPIT, 115. Heng Tao Shen and Yanchun Zhang Eds., ACS. 103-112 |
(from crpit.com)
(local if available)
|
|