Asymmetric signature schemes for efficient exact edit similarity query processing

DOI10.1145/2508020.2508023zbMATH Open1321.68256OpenAlexW2044312046MaRDI QIDQ2943545FDOQ2943545

Authors: Jianbin Qin, Wei Wang, Chuan Xiao, Xuemin Lin, Haixun Wang, Yi-Fei Lu 

Publication date: 3 September 2015

Published in: ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2508020.2508023

Recommendations

• Polylogarithmic approximation for edit distance and the asymmetric query complexity
• Index structures for fast similarity search for symbol strings
• Automata, Languages and Programming
• Bounded occurrence edit distance: a new metric for string similarity joins with edit distance constraints
• Approximate nearest neighbor under edit distance via product metrics

zbMATH Keywords

lower boundedit distancesignaturequery processingquery optimizationasymmetric schemenear-duplicate detection

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Database theory (68P15)

Cited In (1)

• Extending string similarity join to tolerant fuzzy token matching

This page was built for publication: Asymmetric signature schemes for efficient exact edit similarity query processing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2943545)