计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2015年
18期
131-134
,共4页
线段%Voronoi图%k近邻查询%空间数据库
線段%Voronoi圖%k近鄰查詢%空間數據庫
선단%Voronoi도%k근린사순%공간수거고
line segment%Voronoi diagram%k nearest neighbor query%spatial database
K近邻查询是空间数据库中的重要查询之一，k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况，提出基于平面线段的k近邻查询，查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集，然后从中找到最终结果。通过随机数据的实验证明，所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。
K近鄰查詢是空間數據庫中的重要查詢之一，k近鄰查詢在內容的相似性檢索、模式識彆、地理信息繫統中有重要應用。針對現有k近鄰查詢都是基于點查詢的情況，提齣基于平麵線段的k近鄰查詢，查找線段集中給定查詢點的k箇最近線段。給齣基于Voronoi圖的線段k近鄰查詢算法及給齣相關定理和證明。該算法通過線段Voronoi圖的鄰接特性找到一箇候選集，然後從中找到最終結果。通過隨機數據的實驗證明，所提算法明顯優于線性掃描算法和基于R樹的k近鄰查詢算法。
K근린사순시공간수거고중적중요사순지일，k근린사순재내용적상사성검색、모식식별、지리신식계통중유중요응용。침대현유k근린사순도시기우점사순적정황，제출기우평면선단적k근린사순，사조선단집중급정사순점적k개최근선단。급출기우Voronoi도적선단k근린사순산법급급출상관정리화증명。해산법통과선단Voronoi도적린접특성조도일개후선집，연후종중조도최종결과。통과수궤수거적실험증명，소제산법명현우우선성소묘산법화기우R수적k근린사순산법。
K-nearest neighbor query is one of the most important queries in spatial database. K-nearest neighbor query has important applications in the content similarity search, pattern recognition and geographic information systems. Exist-ing k-nearest neighbor query is the query based on the point. The line segment k-nearest neighbor queries are put forward. That is finding k line segments whose distances to query point are the nearest. The algorithm of line segment kNN query based on Voronoi diagram is proposed and the relevant theorem and proof are given. The algorithm finds a candidate set with the adjacent properties of the segment Voronoi diagram, then finds the final results. Experiments on synthetic data sets show that the proposed algorithm outperforms brute-force method and the algorithm based on R-tree.
