Efficient Merging and Filtering Algorithms for Approximate String Searches

By Jiaheng Lu, Yiming Lu. IEEE International Conference on Data Engineering, 2008

314 citations recorded by the source corpus.

We study the following problem: how to efficiently find in a collection of strings those similar to a given query string? Various similarity functions can be used, such as edit distance, Jaccard similarity, and cosine similarity. This problem is of great interests to a variety of applications that need a high real-time performance, such as data cleaning, query relaxation, and spellchecking. Several algorithms have been proposed based on the idea of merging inverted lists of grams generated from the strings. In this paper we make two contributions. First, we develop several algorithms that can greatly improve the performance of existing algorithms. Second, we study how to integrate existing filtering techniques with these algorithms, and show that they should be used together judiciously, since the way to do the integration can greatly affect the performance. We have conducted experiments on several real data sets to evaluate the proposed techniques.

Subfields: Information Systems, Management Science and Operations Research, Signal Processing

View Paper: https://www.semanticscholar.org/paper/3b2616ec17a71453c11f06e1cc38f9034d23c74f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

In Management Science and Operations Research

In Signal Processing

Citations in the corpus

Permutation Search Methods are Efficient, Yet Faster Search is Possible (2015, methodology): “Our implementation is diﬀerent from the proposition of Ch´avez et al. [25] and Tellez et al. [41] in at least two ways: (1) we do not compress the index and (2) we use a simpler algorithm, namely, the ScanCount, to merge posting lists [29].”
Efficient verifiable fuzzy keyword search over encrypted data in cloud computing (2013, background): “Recently, plaintext fuzzy keyword search solutions have been proposed [4], [14], [13].”
Fuzzy Keyword Search over Encrypted Data in Cloud Computing (2010, background): “Recently, the importance of fuzzy search has received attention in the context of plaint ext searching in information retrieval community [11]–[13].”