Efficient interactive fuzzy keyword search

ABSTRACT

Traditional information systems return answers after a user submits a complete query. Users often feel "left in the dark" when they have limited knowledge about the underlying data, and have to use a try-and-see approach for finding information. A recent trend of supporting autocomplete in these systems is a first step towards solving this problem. In this paper, we study a new information-access paradigm, called "interactive, fuzzy search," in which the system searches the underlying data "on the fly" as the user types in query keywords. It extends autocomplete interfaces by (1) allowing keywords to appear in multiple attributes (in an arbitrary order) of the underlying data; and (2) finding relevant records that have keywords matching query keywords approximately. This framework allows users to explore data as they type, even in the presence of minor errors. We study research challenges in this framework for large amounts of data. Since each keystroke of the user could invoke a query on the backend, we need efficient algorithms to process each query within milliseconds. We develop various incremental-search algorithms using previously computed and cached results in order to achieve an interactive speed. We have deployed several real prototypes using these techniques. One of them has been deployed to support interactive search on the UC Irvine people directory, which has been used regularly and well received by users due to its friendly interface and high efficiency.

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 , Alexandru Chitea , Fabian Suchanek , Ingmar Weber, ESTER: efficient search on text, entities, and relations, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277856]
• 3: H. Bast, C. W. Mortensen, and I. Weber. Output-sensitive autocompletion search. In SPIRE, pages 150--162, 2006.
• 4: 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]
• 5: H. Bast and I. Weber. The completesearch engine: Interactive, efficient, and towards ir&db integration. In CIDR, pages 88--95, 2007.
• 6: A. Behm, S. Ji, C. Li, and J. Lu. Space-constrained gram--based indexing for efficient approximate string search. In ICDE, 2009.
• 7: Kaushik Chakrabarti , Surajit Chaudhuri , Venkatesh Ganti , Dong Xin, An efficient filter for approximate membership checking, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376697]
• 8: Surajit Chaudhuri , Venkatesh Ganti , Rajeev Motwani, Robust Identification of Fuzzy Duplicates, Proceedings of the 21st International Conference on Data Engineering, p.865-876, April 05-08, 2005 [doi>10.1109/ICDE.2005.125]
• 9: 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]
• 10: M. Hadjieleftheriou, A. Chandel, N. Koudas, and D. Srivastava. Fast indexes and algorithms for set similarity selection queries. In ICDE, pages 267--276, 2008.
• 11: Liang Jin , Chen Li , Nick Koudas , Anthony K. H. Tung, Indexing mixed types for approximate retrieval, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Liang Jin , Chen Li, Selectivity estimation for fuzzy string predicates in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 13: Nick Koudas , Chen Li , Anthony K. H. Tung , Rares Vernica, Relaxing join and selection queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 14: Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
• 15: C. Li, J. Lu, and Y. Lu. Efficient merging and filtering algorithms for approximate string searches. In ICDE, pages 257--266, 2008.
• 16: Chen Li , Bin Wang , Xiaochun Yang, VGRAM: improving performance of approximate queries on string collections using variable-length grams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 17: Hiroshi Motoda , Kenichi Yoshida, Machine learning techniques to make computers easier to use, Artificial Intelligence, v.103 n.1-2, p.295-321, Aug. 1998 [doi>10.1016/S0004-3702(98)00062-9]
• 18: 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
• 19: Hugh E. Williams , Justin Zobel , Dirk Bahle, Fast phrase querying with combined indexes, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.573-594, October 2004 [doi>10.1145/1028099.1028102]
• 20: Chuan Xiao , Wei Wang , Xuemin Lin , Jeffrey Xu Yu, Efficient similarity joins for near duplicate detection, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367516]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Algorithms, Experimentation, Performance

Keywords:
autocomplete, fuzzy search, interactive search