An effective candidate generation method for improving performance of edit similarity query processing

作者：

Highlights：

• We develop an intersection based candidate generation scheme.

• We prove that candidates can be generated using a DNF of inverted lists.

• We propose a dynamic programming algorithm to select an optimal generation plan.

• We experimentally show that the proposed technique outperforms existing techniques.

摘要

Highlights•We develop an intersection based candidate generation scheme.•We prove that candidates can be generated using a DNF of inverted lists.•We propose a dynamic programming algorithm to select an optimal generation plan.•We experimentally show that the proposed technique outperforms existing techniques.

论文关键词：Similarity query processing,Similarity search,Edit distance,Candidate generation

论文评审过程：Received 3 July 2014, Revised 20 July 2014, Accepted 22 July 2014, Available online 1 August 2014.

论文官网地址：https://doi.org/10.1016/j.is.2014.07.005