Efficient query autocompletion with edit distance-based error tolerance
Efficient query autocompletion with edit distance-based error tolerance
复制标题
具有基于编辑距离的容错能力的高效查询自动完成
DOI：
10.1007/s00778-019-00595-4
复制
发表时间：
2019-12
期刊：
影响因子：
--
通讯作者：
Kunihiko Sadakane
中科院分区：
文献类型：
--
作者：
Jianbin Qin;Chuan Xiao;Sheng Hu;Jie Zhang;Wei Wang;Yoshiharu Ishikawa;Koji Tsuda;Kunihiko Sadakane
查询自动完成是一个重要的功能，节省了用户输入整个查询的许多时间。在本文中，我们研究了问题的查询自动完成，容忍错误的用户输入使用编辑距离约束。以往的方法都是在trie树中索引数据串，并不断维护与查询串的编辑距离在给定阈值内的所有数据串的前缀。这些方法的主要固有缺点是，对于查询字符串的前几个字符来说，这样的前缀的数量是巨大的，并且在字母表大小上是指数级的。这会导致查询响应缓慢，即使整个查询仅大致匹配几个前缀。提出了一种基于邻域生成的容错查询自动补全方法。我们所提出的方法只维护一小部分活动节点，从而节省了空间和时间来处理查询。我们还研究了高效的重复删除，一个核心的problem.in获取查询答案，并扩展我们的方法来支持top-k查询。提出了优化技术来减少索引的大小。通过在真实的数据集上的大量实验，证明了该方法的有效性。
Query autocompletion is an important feature saving users many keystrokes from typing the entire query. In this paper, we study the problem of query autocompletion that tolerates errors in users’ input using edit distance constraints. Previous approaches index data strings in a trie, and continuously maintain all the prefixes of data strings whose edit distances from.the query string are within the given threshold. The major inherent drawback of these approaches is that the number of such prefixes is huge for the first few characters of the query string and is exponential in the alphabet size. This results in slow query response even if the entire query approximately matches only few prefixes. We propose a novel neighborhood generation-based method to process error-tolerant query autocompletion. Our proposed method only maintains a small set of active nodes, thus saving both space and time to process the query. We also study efficient duplicate removal, a core problem.in fetching query answers, and extend our method to support top-k queries. Optimization techniques are proposed to reduce the index size. The efficiency of our method is demonstrated through extensive experiments on real datasets.
登录
查看更多内容
DOI：
10.1145/2396761.2396812
发表时间：
2012-10
期刊：
Proceedings of the 21st ACM international conference on Information and knowledge management
影响因子：
--
作者：
R. Zhong;Ju Fan;Guoliang Li;K. Tan;Lizhu Zhou
通讯作者：
R. Zhong;Ju Fan;Guoliang Li;K. Tan;Lizhu Zhou
影响因子：
5.3
作者：
通讯作者：
--
DOI：
10.1145/2508020.2508023
发表时间：
2013-08
期刊：
ACM Trans. Database Syst.
影响因子：
--
作者：
Jianbin Qin;Wei Wang-;Chuan Xiao;Yifei Lu;Xuemin Lin;Haixun Wang
通讯作者：
Jianbin Qin;Wei Wang-;Chuan Xiao;Yifei Lu;Xuemin Lin;Haixun Wang
DOI：
10.1145/2588555.2593675
发表时间：
2014-06
期刊：
Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
影响因子：
--
作者：
Dong Deng;Guoliang Li;Jianhua Feng
通讯作者：
Dong Deng;Guoliang Li;Jianhua Feng
DOI：
10.1145/1526709.1526736
发表时间：
2009-04
期刊：
IEEE Trans. Signal Process.
影响因子：
--
作者：
Huanhuan Cao;Daxin Jiang;Jian Pei;Enhong Chen;Hang Li
通讯作者：
Huanhuan Cao;Daxin Jiang;Jian Pei;Enhong Chen;Hang Li