一种基于密度网格索引的k-最近邻查询算法

发布时间：2018-07-31 19:55

【摘要】：基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的k-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在k-最近邻查询的查询效率上与ST~2B-tree不相上下,而查询的I/O代价与其他索引结构相比有明显的优势.
[Abstract]:The rapid development of location-based services requires higher efficiency and cost control of service response. In this paper, a new k-nearest neighbor query algorithm based on density grid index is proposed. Firstly, a series of candidate search radii are obtained by using the geometric characteristics of the rectangle, and then the appropriate candidate search radii are selected according to the density distribution of moving objects for distance filtering. Minimize unnecessary access to memory indexing cells and disk indexing cells. Experiments show that the density grid index implemented in this paper is comparable to that of ST~2B-tree in terms of query efficiency of k- nearest neighbor query, and the I / O cost of the query is obviously superior to that of other index structures.
【作者单位】： 武汉大学计算机学院;
【基金】：国家自然科学基金(No.60903035,No.41001296) 国家863高技术研究发展计划(No.2013AA12A301)
【分类号】：TP311.13

【相似文献】

相关期刊论文 前10条

1 张桂榕;;反向最近邻查询研究综述[J];电脑知识与技术;2011年28期

2 周屹;;不确定对象的反向最近邻查询研究[J];黑龙江工程学院学报(自然科学版);2012年04期

3 刘永山,薄树奎,张强,郝忠孝;多对象的最近邻查询[J];计算机工程;2004年11期

4 郝忠孝;刘永山;;空间对象的反最近邻查询[J];计算机科学;2005年11期

5 王淼;郝忠孝;;不确定性对象的反向最近邻查询[J];计算机工程;2010年10期

6 张旭;何向南;金澈清;周傲英;;面向不确定图的k最近邻查询[J];计算机研究与发展;2011年10期

7 杨泽雪;郝忠孝;;空间数据库中的障碍反向最近邻查询[J];计算机工程与应用;2011年34期

8 王丹丹;郝忠孝;;道路网络中的多类型K最近邻查询[J];计算机工程与应用;2012年03期

9 邓瑾;周梅;;基于R树及其变种的最近邻查询研究[J];现代计算机;2013年09期

10 朱婧;;平面中点对一般多边形的最近邻查询研究[J];科技通报;2014年01期

相关会议论文 前10条

1 张晓峰;王丽珍;肖清;赵丽红;;基于概念划分的连续最近邻查询研究[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

2 管猛;张剡;柏文阳;;基于地表的连续可见最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集(B辑)[C];2010年

3 陈璐;高云君;柳晴;陈刚;;受限相互最近邻查询处理[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

4 盛梅红;沙朝锋;宫学庆;嵇晓;周傲英;;道路网络环境中的多对象最近邻查询[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 刘月清;章勇;;一种改进的动态最近邻聚类算法[A];全国自动化新技术学术交流会会议论文集（一）[C];2005年

6 李传文;谷峪;李芳芳;于戈;;一种障碍空间中不确定对象的连续最近邻查询方法[A];NDBC2010第27届中国数据库学术会议论文集A辑一[C];2010年

7 刘星毅;;基于欧式距离的最近邻改进算法[A];广西计算机学会2010年学术年会论文集[C];2010年

8 刘先康;梁菁;任杰;蒋光庆;;修正最近邻模糊分类算法在舰船目标识别中的应用[A];全国第4届信号和智能信息处理与应用学术会议论文集[C];2010年

9 刘俊岭;孙焕良;;多维度量空间中发现相互kNN(英文)[A];NDBC2010第27届中国数据库学术会议论文集A辑二[C];2010年

10 余小高;;P2P环境中k最近邻搜索算法研究[A];2009年全国开放式分布与并行计算机学术会议论文集(下册)[C];2009年

相关博士学位论文 前8条

1 魏本昌;基于内容的大规模图像检索技术研究[D];华中科技大学;2015年

2 杨泽雪;空间连接及最近邻变体查询研究[D];哈尔滨理工大学;2014年

3 孙冬璞;时空数据库多类型最近邻查询的研究[D];哈尔滨理工大学;2010年

4 王建峰;基于哈希的最近邻查找[D];中国科学技术大学;2015年

5 张得天;时间依赖路网高效k最近邻查询混搭机制的研究[D];中国科学技术大学;2014年

6 杜钦生;高维空间的K最近邻查询及连接问题研究[D];吉林大学;2015年

7 张军旗;支持最近邻查找的高维空间索引[D];复旦大学;2007年

8 李艳红;路网中移动对象最近邻及反向最近邻查询处理研究[D];华中科技大学;2011年

相关硕士学位论文 前10条

1 杨根茂;基于哈希加速的近似最近邻检索算法研究[D];浙江大学;2015年

2 原s，

本文编号：2156666