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

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-07-01 发布日期:2014-08-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-07-01 Published:2014-08-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]. 计算机应用, 0, (): 0-0.
[4]	王周恺, 张炯, 马维纲, 王怀军. 面向高速列车监测数据的并行解压缩算法[J]. 计算机应用, 2021, 41(9): 2586-2593.
[5]	李卓, 宋子晖, 沈鑫, 陈昕. 边缘计算支持下的移动群智感知本地差分隐私保护机制[J]. 计算机应用, 2021, 41(9): 2678-2686.
[6]	赵津宋文爱邰隽杨吉江王青李晓丹雷毅邱悦. 儿童阻塞性睡眠呼吸暂停计算机人脸辅助诊断综述[J]. 计算机应用, 0, (): 0-0.
[7]	张妮韩萌王乐李小娟程浩东. 基于正负效用划分的高效用模式挖掘方法综述[J]. 计算机应用, 0, (): 0-0.
[8]	武鹏, 吴尽昭. 基于线性误差断言的推理方法[J]. 计算机应用, 2021, 41(8): 2199-2204.
[9]	王梓森, 梁英, 刘政君, 谢小杰, 张伟, 史红周. 科研项目同行评议专家学术专长匹配方法[J]. 计算机应用, 2021, 41(8): 2418-2426.
[10]	赵全, 汤小春, 朱紫钰, 毛安琪, 李战怀. 大规模短时间任务的低延迟集群调度框架[J]. 计算机应用, 2021, 41(8): 2396-2405.
[11]	康军, 黄山, 段宗涛, 李宜修. 时空轨迹序列模式挖掘方法综述[J]. 计算机应用, 2021, 41(8): 2379-2385.
[12]	陈静, 毛莺池, 陈豪, 王龙宝, 王子成. 基于改进单点多盒检测器的大坝缺陷目标检测方法[J]. 计算机应用, 2021, 41(8): 2366-2372.
[13]	马华, 陈跃鹏, 唐文胜, 娄小平, 黄卓轩. 面向工作者能力评估的众包任务分配方法的研究进展综述[J]. 计算机应用, 2021, 41(8): 2232-2241.
[14]	孙蕊, 韩萌, 张春砚, 申明尧, 杜诗语. 含负项top-k高效用项集挖掘算法[J]. 计算机应用, 2021, 41(8): 2386-2395.
[15]	李莉吴怡杨祉坤陈云鹏. 基于分区型区块链医疗电子病历共享方案[J]. , 0, (): 0-0.

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

Spatial keyword query based on collective object

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics