Moving Objects Snapshot KNN Query Algorithm   Based on Range Query

doi:10.3969/j.issn.1000-3428.2012.07.017

Computer Engineering ›› 2012, Vol. 38 ›› Issue (7): 49-52,56. doi: 10.3969/j.issn.1000-3428.2012.07.017

• Networks and Communications • Previous Articles Next Articles

Moving Objects Snapshot KNN Query Algorithm Based on Range Query

LU Bing-liang, LIU Na, ZHANG Da-wei

(School of Computer, Shenyang Aerospace University, Shenyang 110136, China)

Received:2011-05-04 Online:2012-04-05 Published:2012-04-05

基于范围查询的移动对象快照KNN查询算法

卢秉亮，刘娜，张大伟

(沈阳航空航天大学计算机学院，沈阳 110136)

作者简介:卢秉亮(1953－)，男，副教授、硕士，主研方向：数据库技术；刘娜，硕士研究生；张大伟，讲师、硕士研究生

Abstract

Abstract: This paper presents a moving objects snapshot K Nearest Neighbor(KNN) query algorithm based on range query, named SKNN. It estimates the subspace containing the result set and uses the subspace as range to efficiently compute the KNN Points of Interest(POIs) from the query points to reduce I/O cost. It introduces cache to shorten the average response time of query. Experimental results show that after introducing cache, SKNN has better performance while scaling to a very large number of moving objects.

Key words: mobile database, range query, location-dependent, K Nearest Neighbor(KNN), dual index, cache

摘要： 提出一种基于范围查询的移动对象快照K最近邻(KNN)查询算法——SKNN。预估包含结果集的子空间，使用该子空间作为范围，计算查询点的KNN兴趣点，以降低I/O成本。引入移动数据库中的缓存技术，缩短查询的平均响应时间。实验结果表明，当移动对象的规模较大时，SKNN算法的性能较优。

关键词: 移动数据库, 范围查询, 位置相关, K最近邻, 双索引, 缓存

CLC Number:

TP311

LEI Bing-Liang, LIU Na, ZHANG Da-Wei. Moving Objects Snapshot KNN Query Algorithm Based on Range Query[J]. Computer Engineering, 2012, 38(7): 49-52,56.

卢秉亮, 刘娜, 张大伟. 基于范围查询的移动对象快照KNN查询算法[J]. 计算机工程, 2012, 38(7): 49-52,56.

/ / Recommend / Download Citations

URL: http://www.ecice06.com/EN/10.3969/j.issn.1000-3428.2012.07.017

http://www.ecice06.com/EN/Y2012/V38/I7/49

References

[1] Wang Haojun, Zimmermann R. Snapshot Location-based Query Processing on Moving Objects in Road Networks[C]//Proc. of the 16th ACM Int’l Conf. on Advances in Geographic Information Systems. [S. l.]: ACM Press, 2008.
[2] Papadias D, Zhang Jun, Mamoulis N, et al. Query Processing in Spatial Network Databases[C]//Proc. of VLDB’03. Berlin, Germany: ACM Press, 2003.
[3] Kolahdouzan M R, Shahabi C. Voronoi-based K Nearest Neighbor Search for Spatial Network Databases[C]//Proc. of VLDB’04. Toronto, Ontario, Canada: ACM Press, 2004.
[4] Huang Xuegang, Jensen C S, Saltenis S. The Islands Approach to Nearest Neighbor Querying in Spatial Networks[C]//Proc. of SSTD’05. [S. l.]: ACM Press, 2005.
[5] Kolahdouzan M R, Shahabi C. Continuous K Nearest Neighbor Queries in Spatial Network Databases[C]//Proc. of STDBM’04. Toronto, Canada: ACM Press, 2004.
[6] Cho H J, Chung C W. An Efficient and Scalable Approach to CNN Queries in a Road Network[C]//Proc. of VLDB’05. Trondheim, Norway: ACM Press, 2005.
[7] 王晓辉, 曹泽文, 谭川豫. 移动对象反向最近邻查询技术研究[J]. 计算机工程, 2010, 36(20): 66-67.
[8] 郭景峰, 刘汉峰, 马倩. 基于路网的移动对象K近邻查询方法[J]. 计算机工程, 2008, 34(3): 100-101.
[9] Jensen C S, Kola J, Pedersen T B, et al. Nearest Neighbor Queries in Road Networks[C]//Proc. of the 11th ACM Int’l Symp. on Advances in Geographic Information Systems. New Orleans, Louisiana, USA: ACM Press, 2003.
[10] Huang Xuegang, Jensen C S, Lu H, et al. S-GRID: A Versatile Approach to Efficient Query Processing in Spatial Net- works[C]//Proc. of SSTD’07. Boston, USA: ACM Press, 2007.
[11] Mouratidis K, Yiu M L, Papadias D, et al. Continuous Nearest Neighbor Monitoring in Road Networks[C]//Proc. of VLDB’06. Seoul, Korea: ACM Press, 2006.

[1]	ZHANG Liqun, PAN Zulie, HUANG Hui, WANG Ruipeng, LI Yang. Research on Automatic Verification Method of Tcache Poisoning Heap Vulnerability Based on Symbolic Execution [J]. Computer Engineering, 2023, 49(6): 24-33.
[2]	YANG Zhoufan, HAN Lin, LI Bingyang, XIE Jingming, HAN Pu, LIU Yongjie. Large-Scale Pipeline Network Simulation Based on “Songshan” Supercomputer System [J]. Computer Engineering, 2022, 48(9): 155-161.
[3]	JIN Yuanyuan, NI Zhiwei, ZHU Xuhui, CHEN Hengheng, CHEN Qian. Spatial Data Adaptive Partition Algorithm Based on Local Differential Privacy [J]. Computer Engineering, 2022, 48(5): 136-144.
[4]	HE Xiaobin, GAO Jie, XIAO Wei, CHEN Qi, LIU Xin, CHEN Zuoning. Research on Application-Transparent Supercomputing Multi-tier Storage Acceleration Technology [J]. Computer Engineering, 2022, 48(12): 1-8.
[5]	YANG Tao, ZHENG Quan, XU Zhenghuan, SHI Qianbao, PENG Siwei. Research on Strong Cache Consistency Under Generic Cache Replacement Strategy [J]. Computer Engineering, 2022, 48(12): 180-188,195.
[6]	LU Yi, WANG Peng, WANG Wei. Time-Series Semantic Mining Algorithm Based on Sub-Series Similarity [J]. Computer Engineering, 2022, 48(10): 88-94.
[7]	CONG Mou, ZHANG Ping, WANG NING. Method of Timing Attack for Linux Against KASLR [J]. Computer Engineering, 2021, 47(8): 177-182.
[8]	GE Junwei, YANG Guangxin. Spectral Clustering Algorithm for Density Adaptive Neighborhood Based on Shared Nearest Neighbors [J]. Computer Engineering, 2021, 47(8): 116-123.
[9]	JIAO Tong, CHEN Lingling, AN Xin, LI Jianhua. Reuse Information-based Dynamic Bypass Policy for Non-Volatile Cache [J]. Computer Engineering, 2021, 47(4): 158-165.
[10]	HU Qiaomu, DENG Yun. Range Query Method Based on Compressed HMAC Algorithm for Sensor Networks [J]. Computer Engineering, 2021, 47(12): 200-208.
[11]	GUO Yuluo, BIAN Haodong, DONG Runting, TANG Jiahao, WANG Xiaoying, HUANG Jianqiang. Parallel Fourier Space Image Similarity Calculation Based on SIMD [J]. Computer Engineering, 2021, 47(11): 247-253.
[12]	XU Wenjuan, JIA Xiangdong, CHEN Yuwan. Content Delivery Method Combined with Cache and MIMO Backhaul [J]. Computer Engineering, 2020, 46(6): 164-171.
[13]	ZHOU Qijun, WANG Peng, WANG Wei. DSI:An Index for Time Series Query Based on Dynamic Segmentation [J]. Computer Engineering, 2020, 46(2): 88-95.
[14]	ZHAO Guofeng, LIN Huan, DUAN Jie, ZOU Yaqin, ZENG Shuai. ICN-IoT Caching Scheme for Data Freshness [J]. Computer Engineering, 2020, 46(11): 223-230.
[15]	CHENG Zhiwei, CHEN Caisen, ZHU Lianjun, MO Weifeng, WANG Huiyu. Cache Timing Template Attack Method Based on Pearson Correlation Coefficient [J]. Computer Engineering, 2019, 45(7): 159-163.

Please choose a citation manager

Content to export

Moving Objects Snapshot KNN Query Algorithm Based on Range Query

基于范围查询的移动对象快照KNN查询算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

Moving Objects Snapshot KNN Query Algorithm Based on Range Query

基于范围查询的移动对象快照KNN查询算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments