This work is funded by Project (No. 61272046) supported by the National Natural Science Foundation of China; Project supported by the Natural Science Foundation of Heilongjiang Province,China(Grant No. F201317); The Fundamental Research Funds for the Central University (Grant No. HIT.NSRIF.2015065); China Postdoctoral Science Foundation Funded Project(Grant No. 2013T60372, 2014M561351).
String similarity search is a basic operation for various applications,such as data cleaning, spell checking, bioinformatics and information integration. Memory based q-gram inverted indexes fail to support string sim...