基于对象集合的空间关键词查询

doi:10.11772/j.issn.1001-9081.2014.07.1992

计算机应用 ›› 2014, Vol. 34 ›› Issue (7): 1992-1996.DOI: 10.11772/j.issn.1001-9081.2014.07.1992

基于对象集合的空间关键词查询

梁银,董永权

江苏师范大学计算机科学与技术学院，江苏徐州 221116

收稿日期:2014-01-06 修回日期:2014-02-20 发布日期:2014-08-01 出版日期:2014-07-01
通讯作者: 梁银
作者简介:梁银(1970-)，女，云南建水人，副教授，博士，主要研究方向：空间数据库、空间关键词查询；董永权(1979-)，男，江苏宿迁人，副教授，博士，主要研究方向：Web数据集成、关键词查询。
基金资助:
国家自然科学基金项目;江苏省自然科学基金项目

Spatial keyword query based on collective object

LIANG Yin,DONG Yongquan

School of Computer Science and Technology, Jiangsu Normal University, Xuzhou Jiangsu 221116, China

Received:2014-01-06 Revised:2014-02-20 Online:2014-08-01 Published:2014-07-01
Contact: LIANG Yin

摘要/Abstract

摘要：

在进行空间关键词查询时，有时需要查找一组既紧凑且离查询点最近、又覆盖查询关键词且对象个数很少的对象，而现有的查询方法通常只能返回包含所有查询关键词的单个空间对象。为此，提出了解决此类查询问题的近似查询算法和精确查询算法。首先给出了这类查询问题的形式化定义，以及描述对象集合质量的代价函数，并对代价函数进行了归一化处理；然后在近似查询算法中采用基于IR-tree的最佳优先搜索策略进行剪枝，有效缩减了查询候选空间；在精确查询算法中采用基于IR-tree的广度优先搜索策略查找包含查询关键词的对象，以达到降低查询处理代价的目的。实验结果表明，近似算法的查询效率明显优于精确算法，且能获得非常精确的查询结果。

Abstract:

In spatial keyword query, a group of objects involving minimum number that cover the query keywords and are compact and nearest to the query location will be queried, but generally, the current query method only can return the single spatial object containing all query keywords. To address this query, an approximate algorithm and an exact algorithm were introduced. The query problem was formally defined. A new cost function to describe the quality of the collective objects was defined and normalized. Then the approximate algorithm utilized a best-first search based on the IR-tree to prune the search space. The exact algorithm utilized a breadth-first search based on the IR-tree to retrieve the objects that contain some query keywords to reduce query processing cost. The experiments show that query efficiency of the approximate algorithm is much better than that of the exact algorithm, and approximate algorithm is capable of achieving very accurate results.

中图分类号:

TP311

梁银董永权. 基于对象集合的空间关键词查询[J]. 计算机应用, 2014, 34(7): 1992-1996.

LIANG Yin DONG Yongquan. Spatial keyword query based on collective object[J]. Journal of Computer Applications, 2014, 34(7): 1992-1996.

参考文献

［1］WU D M, YIU M L, CONG G, et al. Joint top-k spatial keyword query processing［J］. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(10): 1889-1903.
［2］ZHANG J Z, LIU D Q, MENG X F. Preference-based top-k spatial keyword queries［C］// Proceedings of the 1st International Workshop on Mobile Location-based Service. New York: ACM, 2011: 31-40.
［3］WU D M, YIU M L, JENSEN C S, et al. Efficient continuously moving top-k spatial keyword query processing［C］// Proceedings of the IEEE 27th International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2011: 541-552.
［4］HUANG W H, LI G L, TAN K L, et al. Efficient safe-region construction for moving top-k spatial keyword queries［C］// Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York: ACM, 2012: 932-941.
［5］ROCHA-JUNIOR J B, NRVG K. Top-k spatial keyword queries on road networks［C］// Proceedings of the 15th International Conference on Extending Database Technology. New York: ACM, 2012: 168-179.
［6］ZHANG J, KU W S, JIANG X F, et al. Evaluation of spatial keyword queries with partial result support on spatial networks［C］// Proceedings of the 14th IEEE International Conference on Mobile Data Management. Washington, DC: IEEE Computer Society, 2013: 279-282.
［7］LI F F, YAO B, TANG M W, et al. Spatial approximate string search［J］. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(6): 1394-1409.
［8］YAO B, TANG M W, LI F F. Multi-approximate-keyword routing in GIS data［C］// Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2011: 201-210.
［9］YAO B, LI F F, HADJIELEFTHERIOU M, et al. Approximate string search in spatial databases［C］// Proceedings of the 26th IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2010: 545-556.
［10］CAO X, CONG G, JENSEN C S, et al. Collective spatial keyword querying［C］// Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2011: 373-384.
［11］ZHANG D X, CHEE Y M, MONDAL A, et al. Keyword search in spatial databases: towards searching by document［C］// Proceedings of the 2009 IEEE International Conference on Data Engineering. Washington, DC: IEEE Computer Society, 2009: 688-699.
［12］LIU W, FU Y, CHEN Z. New collective query processing method based on spatial keyword［J］. Journal of Chinese Computer Systems, 2013, 34(8): 1831-1836. (刘文远, 付颜胜, 陈子军. 一种新的面向集合的空间关键字查询方法［J］. 小型微型计算机系统, 2013, 34(8): 1831-1836.)
［13］ZHANG L, SUN X P, ZHUGE H. Density based collective spatial keyword query［C］// Proceedings of the 8th International Conference on Semantics, Knowledge and Grids. Washington, DC: IEEE Computer Society, 2012: 213-216.
［14］LONG C, WONG R C W, WANG K, et al. Collective spatial keyword queries: a distance owner-driven approach［C］// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 689-700.
［15］CONG G, JENSEN C S, WU D M. Efficient retrieval of the top-k most relevant spatial Web objects［J］. Proceedings of the VLDB Endowment, 2009, 2(1): 337-348.

[1]	高威刘丽华和斌涛邓方安. 区块链共识机制与改进算法研究进展[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	翟社平朱鹏举杨锐刘佳一腾. 基于区块链的物联网身份管理系统[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[3]	蔡锦辉, 尹中旭, 宗国笑, 李俊儒. 面向嵌套分支突破的推断与污点分析融合的方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3823-3830.
[4]	李博, 黄建强, 黄东强, 王晓英. 基于异构平台的稀疏矩阵向量乘自适应计算优化[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3867-3875.
[5]	陈姿芊, 牛科迪, 姚中原, 斯雪明. 适用于物联网的区块链轻量化技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3688-3698.
[6]	高婷婷, 姚中原, 贾淼, 斯雪明. 链上链下一致性保护技术综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3658-3668.
[7]	贾淼, 姚中原, 祝卫华, 高婷婷, 斯雪明, 邓翔. 零知识证明赋能区块链的进展与展望[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3669-3677.
[8]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[9]	杨巍白璐宁俊义董建军单春海信俊昌. 异构环境感知的幂律图流划分方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	梁辰王奕森魏强杜江. 基于Transformer-GCN的源代码漏洞检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	吴海峰陶丽青程玉胜. 集成特征注意力和残差连接的偏标签回归算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	秦学程刘春颜李宝赵蕴龙. 面向工业场景的云边协同数据存储与检索架构[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[13]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[14]	曾蠡, 杨婧如, 黄罡, 景翔, 罗超然. 超图应用方法综述：问题、进展与挑战[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3315-3326.
[15]	崔双双王宏志朱加昊吴昊. 面向低能耗高性能的分类器两阶段数据选择方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

基于对象集合的空间关键词查询

Spatial keyword query based on collective object

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics