Index Structures for Supporting Block Edit Distance

In approximate string matching, the traditional edit distance cannot evaluate the similarity between strings very well, especially for the name, address datasets, etc. The block edit distance, however, can do the job easily. It is important to efficiently support block edit distance for approximate string query processing. Since computing the block edit distance between two strings is an NP-Complete problem, it is desired to provide solutions to increase filterability and decrease false positives. In this paper, a novel index structure, called SHV-Trie, is proposed. A lower bound of the block edit distances is presented according to the features of the block edit distance with move operations, i.e. the frequencies of each character in a string. A corresponding query filter approach is proposed based on the lower bound on character frequencies. Meanwhile, considering the large space cost problem, an optimized ordered character index structure and a compressed index structure are proposed. The corresponding query filtering approaches are further given based on the optimized and compressed index structures. The experimental results and analysis on real data sets show that the proposed index structures can provide good filtering ability and high query performance by decreasing false positives.