BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion

Xiaoling Zhou, Jianbin Qin, Chuan Xiao, Wei Wang, Xuemin Lin, Yoshiharu Ishikawa

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

Query autocompletion has become a standard feature in many search applications, especially for search engines. A recent trend is to support the error-tolerant autocompletion, which increases the usability significantly by matching prefixes of database strings and allowing a small number of errors. In this article, we systematically study the query processing problem for error-tolerant autocompletion with a given edit distance threshold. We propose a general framework that encompasses existing methods and characterizes different classes of algorithms and the minimum amount of information they need to maintain under different constraints. We then propose a novel evaluation strategy that achieves the minimum active node size by eliminating ancestor-descendant relationships among active nodes entirely. In addition, we characterize the essence of edit distance computation by a novel data structure named edit vector automaton (EVA). It enables us to compute new active nodes and their associated states efficiently by table lookups. In order to support large distance thresholds, we devise a partitioning scheme to reduce the size and construction cost of the automaton, which results in the universal partitioned EVA (UPEVA) to handle arbitrarily large thresholds. Our extensive evaluation demonstrates that our proposed method outperforms existing approaches in both space and time efficiencies.
Original languageEnglish
Article number5
Pages (from-to)5:1-5:44
Number of pages44
JournalACM Transactions on Database Systems
Issue number1
Publication statusPublished - 7 Apr 2016


Dive into the research topics of 'BEVA: An Efficient Query Processing Algorithm for Error-Tolerant Autocompletion'. Together they form a unique fingerprint.

Cite this