2009 ExtendingAutocompletiontoTolera

• (Chaudhuri & Kaushik, 2009) ⇒ Surajit Chaudhuri, and Raghav Kaushik. (2009). “Extending Autocompletion to Tolerate Errors.” In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. ISBN:978-1-60558-551-2 doi:10.1145/1559845.1559919

Subject Headings: Auto-Completion Task; Q-Gram Based Autocompletion; Edit Distance Matching Algorithm.

Cited By

• Google Scholar: ~ 147 Citations (Retrieved: 2019-10-10).
• ACM DL: ~ 53 Citations (Retrieved: 2019-10-10).
• Semantic Scholar: ~ 117 Citations (Retrieved: 2019-10-10).

Quotes

Keywords

• Autocompletion, Edit Distance.

Abstract

Autocompletion is a useful feature when a user is doing a look up from a table of records. With every letter being typed, autocompletion displays strings that are present in the table containing as their prefix the search string typed so far. Just as there is a need for making the lookup operation tolerant to typing errors, we argue that autocompletion also needs to be error-tolerant. In this paper, we take a first step towards addressing this problem. We capture input typing errors via edit distance. We show that a naive approach of invoking an offline edit distance matching algorithm at each step performs poorly and present more efficient algorithms. Our empirical evaluation demonstrates the effectiveness of our algorithms.

1. Introduction

…

2. Autocompletion: State Of The Art

At its core, autocompletion is about suggesting valid completions of a partially entered lookup string with the intention of minimizing and guiding the users typing. The concept of autocompletion is not new. There are various approaches studied in prior work on autocompletion. There is a vast body of work on predictive autocompletion 4, 8, 16 where the idea is to use information retrieval techniques, language models and learning to suggest potential completions.

In contrast, our focus is on the scenario where there is a table T of strings being looked up and thus completions are suggested based on matches in T. This is the form of autocompletion supported by http://www.amazon.com and Yahoo Finance for instance. The most common form of such autocompletion is based on exact matching. In this section, we formalize some of the key concepts involved in exact autocompletion.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 ExtendingAutocompletiontoTolera	Surajit Chaudhuri Raghav Kaushik			Extending Autocompletion to Tolerate Errors				10.1145/1559845.1559919		2009