Efficient exact edit similarity query processing with the asymmetric signature scheme

Jianbin Qin, Wei Wang, Yifei Lu, Chuan Xiao, Xuemin Lin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a query string Q, an edit similarity search finds all strings in a database whose edit distance with Q is no more than a given threshold τ . Most existing method answering edit similarity queries rely on a signature scheme to generate candidates given the query string. We observe that the number of signatures generated by existing methods is far greater than the lower bound, and this results in high query time and index space complexities.
In this paper, we show that the minimum signature size lower bound is τ +1. We then propose asymmetric signature schemes that achieve this lower bound. We develop efficient query processing algorithms based on the new scheme. Several dynamic programming-based candidate pruning methods are also developed to further speed up the performance. We have conducted a comprehensive experimental study involving nine state-of-the-art algorithms. The experiment results clearly demonstrate the efficiency of our methods.
Original languageEnglish
Title of host publicationProceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011
Place of PublicationAthens, Greece
PublisherACM
Pages1033-1044
Number of pages12
ISBN (Print)978-1-4503-0661-4
DOIs
Publication statusPublished - 12 Jun 2011
Event2011 ACM SIGMOD International Conference on Management of data - Athens, Greece
Duration: 12 Jun 201116 Jun 2011
http://www.sigmod2011.org/index.shtml

Conference

Conference2011 ACM SIGMOD International Conference on Management of data
Country/TerritoryGreece
CityAthens
Period12/06/1116/06/11
Internet address

Fingerprint

Dive into the research topics of 'Efficient exact edit similarity query processing with the asymmetric signature scheme'. Together they form a unique fingerprint.

Cite this