Extending Autocompletion to Tolerate Errors - Chaudhuri, Surajit; Kaushik, Raghav (ACM SIGMOD, 2009)
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 preﬁx 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 ﬁrst step towards addressing this problem. We capture input typing errors via edit distance. We show that a naive approach of invoking an oﬄine edit distance matching algorithm at each step performs poorly and present more eﬃcient algorithms. Our empirical evaluation demonstrates the eﬀectiveness of our algorithms.