Advanced Methods for Large and Long String/Set Similarity Searches

String/Set Similarity Search (SSS) is a core function for database tasks like data cleaning and near-duplicate detection, which aims to find data objects meeting query criteria via similarity functions. Extensively studied for decades, SSS faces new challenges (low efficiency, high space consumption of traditional methods) and opportunities (emerging technologies like machine learning) due to the explosive growth of large-scale datasets. Thus, designing efficient SSS algorithms and integrating new technologies to optimize SSS have become key research issues. This study explores SSS techniques, focusing on string/set similarity query and join algorithms under various similarity functions, as well as learned index and representation learning-based SSS algorithms, with three key research contents: Top-k overlap string similarity join: A step size-based algorithm is proposed to optimize traditional methods. Theoretical analysis verifies the positive effect of step size and identifies the optimal fixed step size, on the basis of which a fixed step size algorithm is designed. For practical applicability, an adaptive step size algorithm is further proposed to avoid manual setting and fully exploit the advantages of large step sizes, with extensions to Jaccard and Cosine similarity functions. Experiments on large-scale real datasets show the proposed algorithms outperform SOTA methods, with query speed 4–14 times faster. Threshold-based string similarity search under edit distance: A sketching-based indexing algorithm integrated with ML-based learned index technology is proposed. Sketching captures pivot characters to construct concise string sketches with high candidate accuracy, and corresponding compact index structures are designed to reduce space consumption; learned index replaces length filtering structures to accelerate index search. Real-world dataset experiments show the algorithm reduces space consumption by up to 75% and speeds up search by up to 60 times compared with SOTA methods. Box embeddings-based representation learning for set similarity search: The MTB multi-task learning method is proposed, which adopts a concise model and balanced loss design to improve learning efficiency and accuracy. The universal USearch algorithm is also designed to address various set similarity problems, leveraging set representation and GPU parallel execution to boost efficiency. Experiments demonstrate superior performance: MTB improves learning accuracy by 1.15–8.6 times and reduces training time by 30%–70% vs. competitors; the GPU-based US-G is over 50% faster than the CPU-based US-C and far more efficient than other competing methods.

Author dc:creator

• Yang, Zhong

Statement dc:rights

• info:eu-repo/semantics/openAccess
• The author owns the copyright in this thesis including all reproduction and reuse rights for the work. The work may not be altered without the permission of the copyright owner. Attribution is essential when quoting or paraphrasing from this thesis.
• © 2025 YANG Zhong
• au.edu.uts.lib/cph

Language dc:language.iso

en_US

Handle dc:identifier.uri

http://hdl.handle.net/10453/195391

OAI identifier oai:identifier

oai:opus.lib.uts.edu.au:10453/195391