基于格网划分的道路最近邻查询算法
闫红松
George Almpanidis
凡高娟
1.河南大学 计算机与信息工程学院,河南 开封,4750032.河南大学 计算机与信息工程学院,河南 开封,4750033.河南大学 计算机与信息工程学院,河南 开封,475003
摘要：针对现有道路最近邻查询算法均以数据点作为道路端点进行查询,并未考虑数据点在道路上的情况,使得在大数据量时查询效率不够理想的问题,利用格网划分算法进行解决.利用分治法的思想,将查询区域进行格网划分,缩小有效的查询区域,快速定位查询点所在道路,进而找到最近邻数据点.研究结果表明:当数据量足够大时,格网划分算法与增量网络扩张(INE)算法相比,查询时间明显降低,效率明显提升,格网划分查询的时间复杂度为O(1);当数据量较少时,格网划分算法与INE算法相比,查询时间减少并不明显,表明格网划分算法更适用于大数据量最近邻查询.
关键词：道路最近邻空间查询空间数据库格网划分
分类号：TP311.13(计算技术、计算机技术)
资助基金：国家自然科学基金(41401466)
论文发表日期：2020-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：6( 30-35 )