Efficient and effective KNN sequence search with approximate n-grams
Xiaoli Wang, Xiaofeng Ding, Anthony K. H. Tung, Zhenjie Zhang · Proceedings of the VLDB Endowment · 2013
In this paper, we address the problem of finding k -nearest neighbors (KNN) in sequence databases using the edit distance. Unlike most existing works using short and exact n -gram matchings together with a filter-and-refine framework for KNN sequence search, our new approach allows us to use longer but approximate n -gram matchings as a basis of KNN candidates pruning. Based on this new idea, we devise a pipeline framework over a two-level index for searching KNN in the sequence database. By coupling this framework together with several efficient filtering strategies, i.e. the frequency queue and the well-known Combined Algorithm (CA), our proposal brings various enticing advantages over existing works, including 1) huge reduction on false positive candidates to avoid large overheads on candidate verifications; 2) progressive result update and early termination; and 3) good extensibility to parallel computation. We conduct extensive experiments on three real datasets to verify the superiority of the proposed framework.