A Prefix-Filter based Method for Spatio-Textual Similarity Join
A Prefix-Filter based Method for Spatio-Textual Similarity Join
复制标题
基于前缀过滤的空间文本相似度连接方法
DOI：
10.1109/tkde.2013.83
复制
发表时间：
2014-10
期刊：
影响因子：
--
通讯作者：
Jianhua Feng
中科院分区：
文献类型：
--
作者：
Sitong Liu;Guoliang Li;Jianhua Feng
由于现代手机配备了GPS设备，基于位置的服务备受关注。这些服务生成大量的空间文本数据，其中包含空间位置和文本描述。由于GPS的偏差或用户描述的不同，空间文本对象可能具有不同的表示，因此需要有效的方法来整合来自不同来源的空间文本数据。本文研究了一个新的研究问题——空间-文本相似连接：给定两组空间-文本对象，找出相似的对象对。我们做出了以下贡献：(1)我们开发了一个过滤和细化框架，并设计了几个有效的算法。我们扩展前缀过滤技术，为对象生成空间和文本签名，并在这些签名之上构建倒排索引。然后，我们使用签名的倒列表生成候选对。最后对候选项进行细化，生成最终结果。(2)研究如何生成高质量的空间信息签名。我们开发了一种基于mbr前缀的签名来修剪大量不相似的对象对。(3)提出了一种同时支持文本修剪和空间修剪的混合签名方案。(4)在真实和合成数据集上的实验结果表明，我们的算法具有良好的性能和可扩展性。
Location-based services have attracted significant attention due to modern mobile phones equipped with GPS devices. These services generate large amounts of spatio-textual data which contain both spatial location and textual descriptions. Since a spatio-textual object may have different representations, possibly because of deviations of GPS or different user descriptions, it calls for efficient methods to integrate spatio-textual data from different sources. In this paper we study a new research problem called spatio-textual similarity join: given two sets of spatio-textual objects, find the similar object pairs. We make the following contributions: (1) We develop a filter-and-refine framework and devise several efficient algorithms. We extend the prefix filter technique to generate spatial and textual signatures for the objects and build inverted index on top of these signatures. Then we generate candidate pairs using the inverted lists of signatures. Finally we refine the candidates and generate the final result. (2) We study how to generate high-quality signatures for spatial information. We develop an MBR-prefix based signature to prune large numbers of dissimilar object pairs. (3) We propose a hybrid signature scheme to support both textual pruning and spatial pruning simultaneously. (4) Experimental results on real and synthetic datasets show that our algorithms achieve high performance and scale well.
登录
查看更多内容
影响因子：
2.5
作者：
Wang, Jiannan;Feng, Jianhua;Li, Guoliang
通讯作者：
Li, Guoliang
DOI：
10.1145/191839.191881
发表时间：
1994-05
期刊：
--
影响因子：
--
作者：
Ming-Ling Lo;C. Ravishankar
通讯作者：
Ming-Ling Lo;C. Ravishankar
DOI：
--
发表时间：
1997-08
期刊：
--
影响因子：
--
作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
通讯作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
DOI：
10.1145/1367497.1367516
发表时间：
2008-04
期刊：
--
影响因子：
--
作者：
Chuan Xiao;Wei Wang;Xuemin Lin;J. Yu;Guoren Wang
通讯作者：
Chuan Xiao;Wei Wang;Xuemin Lin;J. Yu;Guoren Wang
影响因子：
2.5
作者：
Xiao, Chuan;Wang, Wei;Lin, Xuemin
通讯作者：
Lin, Xuemin