Extending autocompletion to tolerate errors

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.

REFERENCES

• 1: Arvind Arasu , Venkatesh Ganti , Raghav Kaushik, Efficient exact set-similarity joins, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 2: Holger Bast , Ingmar Weber, Type less, find more: fast autocompletion search with a succinct index, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148234]
• 3: Surajit Chaudhuri , Venkatesh Ganti , Raghav Kaushik, A Primitive Operator for Similarity Joins in Data Cleaning, Proceedings of the 22nd International Conference on Data Engineering, p.5, April 03-07, 2006 [doi>10.1109/ICDE.2006.9]
• 4: John J. Darragh , Ian H. Witten , Mark L. James, The Reactive Keyboard: A Predictive Typing Aid, Computer, v.23 n.11, p.41-49, November 1990 [doi>10.1109/2.60879]
• 5: Dblp. http://dblp.uni-trier.de/.
• 6: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 7: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 8: Korinna Grabski , Tobias Scheffer, Sentence completion, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009066]
• 9: Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
• 10: Trinh N. D. Huynh , Wing-Kai Hon , Tak-Wah Lam , Wing-Kin Sung, Approximate string matching using compressed suffix arrays, Theoretical Computer Science, v.352 n.1, p.240-249, 7 March 2006 [doi>10.1016/j.tcs.2005.11.022]
• 11: H. V. Jagadish , Adriane Chapman , Aaron Elkiss , Magesh Jayapandian , Yunyao Li , Arnab Nandi , Cong Yu, Making database systems usable, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247483]
• 12: Nick Koudas , Sunita Sarawagi , Divesh Srivastava, Record linkage: similarity measures and algorithms, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142599]
• 13: Moritz G. Maaí , Johannes Nowak, Text indexing with errors, Journal of Discrete Algorithms, v.5 n.4, p.662-681, December, 2007 [doi>10.1016/j.jda.2006.11.001]
• 14: Robert B. Miller, Response time in man-computer conversational transactions, Proceedings of the December 9-11, 1968, fall joint computer conference, part I, December 09-11, 1968, San Francisco, California [doi>10.1145/1476589.1476628]
• 15: Arnab Nandi , H. V. Jagadish, Assisted querying using instant-response interfaces, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247640]
• 16: Arnab Nandi , H. V. Jagadish, Effective phrase prediction, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 17: Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001 [doi>10.1145/375360.375365]
• 18: G. Navarro, R. A. Baeza-Yates, E. Sutinen, and J. Tarhio. Indexing methods for approximate string matching. IEEE Data Eng. Bull., 24(4):19--27, 2001.
• 19: Gonzalo Navarro , Takuya Kida , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, Faster Approximate String Matching over Compressed Text, Proceedings of the Data Compression Conference, p.459, March 27-29, 2001
• 20: Esko Ukkonen, Approximate String-Matching over Suffix Trees, Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, p.228-242, June 02-04, 1993
• 21: Chuan Xiao , Wei Wang , Xuemin Lin, Ed-Join: an efficient algorithm for similarity joins with edit distance constraints, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453957]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Design, Experimentation

Keywords:
autocompletion, edit distance