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.
Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SIGMOD'09, June 29-July 2, 2009, Providence, Rhode Island, USA.Copyright 2009 ACM 978-1-60558-551-2/09/06 ...$5.00.