META: An efficient matching-based method for error-tolerant autocompletion

Dong Deng, Guoliang Li, He Wen, H. V. Jagadish, Jianhua Feng

Research output: Contribution to journalConference articlepeer-review

14 Scopus citations


Autocompletion has been widely adopted in many computing systems because it can instantly provide users with results as users type in queries. Since the typing task is tedious and prone to error, especially on mobile devices, a recent trend is to tolerate errors in autocompletion. Existing error-tolerant autocompletion methods build a trie to index the data, utilize the trie index to compute the trie nodes that are similar to the query, called active nodes, and identify the leaf descendants of active nodes as the results. However these methods have two limitations. First, they involve many redundant computations to identify the active nodes. Second, they do not support top-k queries. To address these problems, we propose a matching-based framework, which computes the answers based on matching characters between queries and data. We design a compact tree index to maintain active nodes in order to avoid the redundant computations. We devise an incremental method to effciently answer top-k queries. Experimental results on real datasets show that our method outperforms state-of- the-art approaches by 1-2 orders of magnitude.

Original languageEnglish (US)
Pages (from-to)828-839
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number10
StatePublished - 2016
Externally publishedYes
Event42nd International Conference on Very Large Data Bases, VLDB 2016 - New Delhi, India
Duration: Sep 5 2016Sep 9 2016

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Computer Science(all)


Dive into the research topics of 'META: An efficient matching-based method for error-tolerant autocompletion'. Together they form a unique fingerprint.

Cite this