Efficient fuzzy full-text type-ahead search
Efficient fuzzy full-text type-ahead search
复制标题
高效的模糊全文预输入搜索
DOI：
10.1007/s00778-011-0218-x
复制
发表时间：
2011-08-01
期刊：
影响因子：
4.2
通讯作者：
Feng, Jianhua
中科院分区：
文献类型：
--
作者：
Li, Guoliang;Ji, Shengyue;Feng, Jianhua
传统的信息系统在用户提交完整的查询后返回答案。当用户对底层数据的了解有限并且不得不使用尝试和查看的方法来查找信息时，他们通常会感到“被蒙在鼓里”。在这些系统中支持自动完成的最新趋势是解决这个问题的第一步。在本文中，我们研究了一种新的信息访问范式，称为“类型提前搜索”，其中系统搜索的基础数据“在飞”作为用户类型的查询关键字。它通过允许关键字出现在基础数据中的不同位置来扩展自动完成接口。这个框架允许用户在输入时浏览数据，即使存在微小的错误。我们在这个框架中研究大量数据的研究挑战。由于用户的每一个查询都可以在后端调用一个查询，我们需要高效的算法来在毫秒内处理每个查询。我们开发了各种增量搜索算法的单关键字查询和多关键字查询，使用以前计算和缓存的结果，以实现高的交互速度。我们开发了新的技术来支持模糊搜索，允许查询关键字和答案之间的不匹配。我们已经使用这些技术部署了几个真实的原型。其中一个已经部署用于支持UC Irvine people directory上的type-ahead搜索，由于其友好的界面和高效率，用户经常使用并深受用户欢迎。
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 toward solving this problem. In this paper, we study a new information-access paradigm, called "type-ahead search" in which the system searches the underlying data "on the fly" as the user types in query keywords. It extends autocomplete interfaces by allowing keywords to appear at different places in the underlying data. 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 for both single-keyword queries and multi-keyword queries, using previously computed and cached results in order to achieve a high interactive speed. We develop novel techniques to support fuzzy search by allowing mismatches between query keywords and answers. We have deployed several real prototypes using these techniques. One of them has been deployed to support type-ahead 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.