Spatial keyword query based on collective object

doi:10.11772/j.issn.1001-9081.2014.07.1992

Journal of Computer Applications ›› 2014, Vol. 34 ›› Issue (7): 1992-1996.DOI: 10.11772/j.issn.1001-9081.2014.07.1992

Previous Articles Next Articles

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

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

梁银,董永权

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

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

Abstract

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.

摘要：

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

CLC Number:

TP311

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

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

References

［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]	. Research advances in blockchain consensus mechanisms and improvement algorithms [J]. Journal of Computer Applications, 0, (): 0-0.
[2]	. Blockchain-based identity management system for internet of things [J]. Journal of Computer Applications, 0, (): 0-0.
[3]	Jinhui CAI, Zhongxu YIN, Guoxiao ZONG, Junru LI. Integrated method of inference and taint analysis for nested branch breakthrough [J]. Journal of Computer Applications, 2024, 44(12): 3823-3830.
[4]	Bo LI, Jianqiang HUANG, Dongqiang HUANG, Xiaoying WANG. Adaptive computing optimization of sparse matrix-vector multiplication based on heterogeneous platforms [J]. Journal of Computer Applications, 2024, 44(12): 3867-3875.
[5]	Ziqian CHEN, Kedi NIU, Zhongyuan YAO, Xueming SI. Review of blockchain lightweight technology applied to internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3688-3698.
[6]	Tingting GAO, Zhongyuan YAO, Miao JIA, Xueming SI. Overview of on-chain and off-chain consistency protection technologies [J]. Journal of Computer Applications, 2024, 44(12): 3658-3668.
[7]	Miao JIA, Zhongyuan YAO, Weihua ZHU, Tingting GAO, Xueming SI, Xiang DENG. Progress and prospect of zero-knowledge proof enabling blockchain [J]. Journal of Computer Applications, 2024, 44(12): 3669-3677.
[8]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[9]	. Heterogeneous Environment Aware Streaming Graph Partitioning for Power-Law Graphs [J]. Journal of Computer Applications, 0, (): 0-0.
[10]	. Source code vulnerability detection method based on Transformer-GCN [J]. Journal of Computer Applications, 0, (): 0-0.
[11]	. Partial label regression algorithm integrating feature attention and residual connection [J]. Journal of Computer Applications, 0, (): 0-0.
[12]	. Cloud-edge collaborative data storage and retrieval architecture for industrial scenarios [J]. Journal of Computer Applications, 0, (): 0-0.
[13]	Jinxing TU, Zhixiong LI, Jianqiang HUANG. Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU [J]. Journal of Computer Applications, 2024, 44(11): 3521-3529.
[14]	Li ZENG, Jingru YANG, Gang HUANG, Xiang JING, Chaoran LUO. Survey on hypergraph application methods： issues， advances， and challenges [J]. Journal of Computer Applications, 2024, 44(11): 3315-3326.
[15]	. Two-stage data selection method for classifier with high performance and low energy consumption [J]. Journal of Computer Applications, 0, (): 0-0.

Spatial keyword query based on collective object

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics