空间数据库中混合数据组最近邻查询

doi:10.3778/j.issn.1673-9418.2009032

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (2): 348-358.DOI: 10.3778/j.issn.1673-9418.2009032

空间数据库中混合数据组最近邻查询

蒋祎莹, 张丽平, 金飞虎⁺(), 郝晓红

哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080

收稿日期:2020-09-14 修回日期:2020-11-27 出版日期:2022-02-01 发布日期:2021-01-12
通讯作者: + E-mail: a1889657@163.com
作者简介:蒋祎莹（1995—）,女,黑龙江齐齐哈尔人,博士研究生,CCF学生会员,主要研究方向为空间数据库、大数据。
张丽平（1976—）,女,辽宁调兵山人,博士,副教授,主要研究方向为时空数据库、信息数据安全。
金飞虎（1973—）,男,黑龙江哈尔滨人,博士,副教授,主要研究方向为时空数据库、大数据、人工智能。
郝晓红（1969—）,女,黑龙江哈尔滨人,硕士,高级实验师,主要研究方向为数据库理论及应用、空间推理、空间关系、数据挖掘。
基金资助:
国家自然科学基金(61872105);黑龙江省科学基金(LH2020F047);黑龙江省教育厅科学技术研究项目(12531z004)

Groups Nearest Neighbor Query of Mixed Data in Spatial Database

JIANG Yiying, ZHANG Liping, JIN Feihu⁺(), HAO Xiaohong

College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China

Received:2020-09-14 Revised:2020-11-27 Online:2022-02-01 Published:2021-01-12
About author:JIANG Yiying, born in 1995, Ph.D. candidate, student member of CCF. Her research interests include spatial database and big data.
ZHANG Liping, born in 1976, Ph.D., associate professor. Her research interests include spatio-temporal database and information data security.
JIN Feihu, born in 1973, Ph.D., associate professor. His research interests include spatio-temporal database, big data and artificial intelligence.
HAO Xiaohong, born in 1969, M.S., expert experimenter. Her research interests include data-base theory and application, spatial reasoning, spatial relations and data mining.
Supported by:
National Natural Science Foundation of China(61872105);Science Foundation of Heilongjiang Province(LH2020F047);Science and Technology Research Project of Heilongjiang Provincial Department of Education(12531z004)

摘要/Abstract

摘要：

现有的组最近邻查询方法主要将空间中数据对象抽象为点或线段进行处理。但在现实应用中,仅仅将空间对象抽象为点或者线段,往往会影响查询的精度及效率。针对现有的组最近邻查询方法无法直接有效地处理混合数据组最近邻查询的不足,提出空间数据库中混合数据组最近邻查询方法。首先提出了混合数据Voronoi图的概念和性质。接着基于混合数据Voronoi图对混合数据集进行剪枝,针对查询对象数量为1和查询对象数量大于1的情况分别给出了相应的剪枝算法。利用所提的剪枝算法能有效去除不可能成为结果的数据对象,得到候选集合。在精炼过程中根据各个数据对象之间的位置关系给出相应的距离计算方法,通过比较候选集中数据对象到各个查询对象的距离之和,最终得到正确的查询结果。理论研究和实验表明,所提算法能够准确、有效地处理混合数据组最近邻查询问题。

关键词: 地理信息系统, 空间数据库, 组最近邻, 混合数据, 混合数据Voronoi图

Abstract:

The existing group nearest neighbor query methods mainly abstract data objects in space as points or line segments for processing. However, in real applications, simply abstracting spatial objects into points or line segments often affects the accuracy and efficiency of the query. In view of the shortcomings that the existing group nearest neighbor query method cannot directly and effectively deal with the group nearest neighbor query of the mixed data, the group nearest neighbor query method of the mixed data in the spatial database is proposed in this paper. Firstly, the concept and properties of the mixed data Voronoi diagram are proposed. Then the mixed data set is pruned based on the mixed data Voronoi diagram. The corresponding pruning algorithm is given for the case that the number of query objects is 1 and the number of query objects is greater than 1. The proposed pruning algorithm can effectively remove the impossible resultant data objects and get the candidate set. In the refining process, a corresponding distance calculation method is given according to the position relationship between data objects, and the correct query result is finally obtained by comparing the sum of the distance between the data object in the candidate set and each query object. Theoretical research and experiments show that the proposed algorithm in this paper can accurately and effectively deal with the group nearest neighbor query problem of mixed data.

Key words: geographic information system, spatial database, group nearest neighbor, mixed data, mixed data Voronoi diagram

中图分类号:

TP311.13

蒋祎莹, 张丽平, 金飞虎, 郝晓红. 空间数据库中混合数据组最近邻查询[J]. 计算机科学与探索, 2022, 16(2): 348-358.

JIANG Yiying, ZHANG Liping, JIN Feihu, HAO Xiaohong. Groups Nearest Neighbor Query of Mixed Data in Spatial Database[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(2): 348-358.

图/表 11

图1 混合数据组最近邻

Fig.1 Group nearest neighbor for mixed data

图2 点与线段距离平分线的构建

Fig.2 Construction of bisector of distance between point and line segment

图3 线段与线段距离平分线的构建

Fig.3 Construction of bisector of distance between line segments

图4 查询对象的剪枝

Fig.4 Pruning of query objects

图5 线段与线段位置关系

Fig.5 Position relationship between line segments

图6 数据对象的数量变化对运行时间的影响

Fig.6 Impact of changes in the number of data objects on running time

图7 数据对象的数量变化对I/O代价的影响

Fig.7 Impact of changes in the number of data objects on I/O cost

图8 数据对象的密度对候选对象数量的影响

Fig.8 Impact of density of data objects on the number of candidate objects

图9 查询对象的数量变化对运行时间的影响

Fig.9 Impact of the number of query objects on running time

图10 查询对象的数量变化对I/O代价的影响

Fig.10 Impact of the number of query objects on I/O cost

图11 查询次数对算法准确率的影响

Fig.11 Impact of the number of query objects on accuracy of algorithm

参考文献 18

[1]	ROUSSOPOULOS N, KELLEY S, VINCENT F. Nearest neighbor queries[J]. ACM Sigmod Record, 1995, 24(2):71-79.
[2]	刘润涛, 郝忠孝. 空间数据库平面线段快速最近邻查询算法[J]. 计算机研究与发展, 2011, 48(12):2379-2384.
	LIU R T, HAO Z X. Fast algorithm of nearest neignbor for line segments of spatial database[J]. Journal of Computer Research and Development, 2011, 48(12):2379-2384.
[3]	YI X, PAULET R, BERTINO E, et al. Practical approximate k nearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(6):1546-1559. DOI URL
[4]	章登义, 李想. 一种基于密度网格索引的k-最近邻查询算法[J]. 电子学报, 2017, 45(2):376-383.
	ZHANG D Y, LI X. A k-nearest neighbor query algorithm for density grid-based index[J]. Acta Electronica Sinica, 2017, 45(2):376-383.
[5]	YU Z Q, LIU Y, YU X H, et al. Scalable distributed proces-sing of k nearest neighbor queries over moving objects[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(5):1383-1396. DOI URL
[6]	LEE M J, CHOI D W, KIM S Y, et al. The direction- constrained k nearest neighbor query[J]. GeoInformatica, 2016, 20(3):471-502. DOI URL
[7]	GUO X, YANG X C. Direction-aware nearest neighbor query[J]. IEEE Access, 2019, 7:30285-30301. DOI URL
[8]	ELMONGUI H G, MOKBEL M F, AREF W G. Continuous aggregate nearest neighbor queries[J]. GeoInformatica, 2013, 17(1):63-95. DOI URL
[9]	SUN W W, CHEN C N, ZHU L, et al. On efficient aggregate nearest neighbor query processing in road networks[J]. Journal of Computer Science and Technology, 2015, 30(4):781-798. DOI URL
[10]	于嘉希, 李松, 张丽平, 等. 面向不确定数据的概率障碍k聚集最近邻查询[J]. 计算机科学与探索, 2018, 12(2):231-240.
	YU J X, LI S, ZHANG L P, et al. Probabilistic obstacle k aggregate nearest neighbor query on uncertain data[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(2):231-240.
[11]	PAPADIAS D, SHEN Q M, TAO Y F, et al. Group nearest neighbor queries[C]//Proceedings of the 20th International Conference on Data Engineering, Boston, Mar 30-Apr 2, 2004. Washington: IEEE Computer Society, 2004: 301-312.
[12]	郭莹莹, 张丽平, 李松. 空间数据库中基于Voronoi图的线段组最近邻查询[J]. 小型微型计算机系统, 2017, 38(10):2341-2345.
	GUO Y Y, ZHANG L P, LI S. Voronoi-based line segment group nearest neighbor query in spatial database[J]. Journal of Chinese Computer Systems, 2017, 38(10):2341-2345.
[13]	孙冬璞, 郝忠孝. 基于Voronoi图的组最近邻查询[J]. 计算机研究与发展, 2010, 47(7):1244-1251.
	SUN D P, HAO Z X. Group nearest neighbor queries based on Voronoi diagrams[J]. Journal of Computer Research and Development, 2010, 47(7):1244-1251.
[14]	NURAIN N, ALI M E, HASHEM T, et al. Group nearest neighbor queries for fuzzy geospatial objects[C]//Proceedings of the 2nd International ACM Workshop on Managing and Mining Enriched GeoSpatial Data, Melbourne, May 31-Jun 4, 2015. New York: ACM, 2015: 25-30.
[15]	SON W, BAE S W, AHN H K. Group nearest neighbor queries in the L1 plane[J]. Theoretical Computer Science, 2015, 592(C):39-48. DOI URL
[16]	GAO Y J, ZHENG B H, CHEN G C, et al. Algorithms for constrained k-nearest neighbor queries over moving object trajectories[J]. Geoinformatica, 2010, 14(2):241-276. DOI URL
[17]	周长利, 陈永红, 田晖, 等. 保护位置隐私和查询内容隐私的路网K近邻查询方法[J]. 软件学报, 2020, 31(2):471-492.
	ZHOU C L, CHEN Y H, TIAN H, et al. Location privacy and query privacy preserving method for K-nearest neighbor query in road networks[J]. Journal of Software, 2020, 31(2):471-492.
[18]	郭莹莹, 张丽平, 李松. 障碍环境中线段组最近邻查询方法研究[J]. 计算机科学, 2018, 45(6):172-175.
	GUO Y Y, ZHANG L P, LI S. Group nearest neighbor query method of line segment in obstacle space[J]. Computer Science, 2018, 45(6):172-175.

空间数据库中混合数据组最近邻查询

Groups Nearest Neighbor Query of Mixed Data in Spatial Database

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 18

相关文章 3

编辑推荐

Metrics

[1]	屈晶晶, 蔡英, 范艳芳, 夏红科. 基于k-prototype聚类的差分隐私混合数据发布算法[J]. 计算机科学与探索, 2021, 15(1): 109-118.
[2]	郝晓红，李松，郝忠孝. 复杂3D空间中的3DR46模型的表示与推理[J]. 计算机科学与探索, 2020, 14(12): 2004-2013.
[3]	车庆首，李传文，张轶，邓庆绪. GAPI：GPU加速的移动对象并行索引方法[J]. 计算机科学与探索, 2017, 11(11): 1713-1722.