Fast Algorithms for Computing Jaro Similarity

Area of Science:

• Computer Science
• Data Science
• Computational Linguistics

Background:

• Jaro and Jaro-Winkler similarity are key for character-based string comparison.
• Traditional methods have high computational costs, limiting large-scale applications.
• Previous work introduced a linear-time Jaro similarity algorithm for long strings.

Purpose of the Study:

• To introduce enhanced algorithms for Jaro and Jaro-Winkler similarity.
• To improve runtime efficiency for both short and long strings.
• To reduce computation time for large-scale, repeated string comparisons.

Main Methods:

• Development of optimized algorithms for Jaro and Jaro-Winkler similarity.
• Implementation of techniques for efficient handling of shorter strings.
• Introduction of methods for drastically reducing computation in self-comparison scenarios.

Main Results:

• Enhanced algorithms show improved runtime performance compared to traditional methods.
• The new algorithms are effective for both short and long strings.
• Significant speedups achieved for large datasets and repeated string comparisons.

Conclusions:

• The enhanced Jaro and Jaro-Winkler algorithms offer substantial computational improvements.
• These advancements make the algorithms more suitable for large-scale record linkage and entity resolution.
• The optimized methods address the limitations of traditional string comparison techniques.