基于Voronoi图的反向最近邻查询方法研究

为了解决数据集中数据点的反向最近邻问题,利用Voronoi图及空间分割区域的性质计算查询点的反向最近邻,通过Voronoi图的特性可免去每次都计算数据集中给定查询点的最近邻的步骤,每次查询可过滤出少数的几个数据点并对其进行反向最近邻的判断.给出了在数据点被加入或删除时,对查询点的反向最近邻变化情况的判断方法与算法.为了便于数据库查询,设计了相应的空间存储数据结构.比较分析表明,该方法较适用于平面及复杂曲面上的数据点的反向最近邻的查询.     

不确定对象的反向最近邻查询研究

确定对象在空间数据库研究中受到人们的重视,不确定对象的反向最近邻研究成为研究热点。文中给出不确定对象反向最近邻查询的形式化表示,将其称为可能反向最近邻查询,即为检索所有可能成为给定不确定对象的反向最近邻的可能性大于给定阈值的不确定性对象。提出基于各种剪枝规则的算法,解决多维不确定对象的可能反向最近邻查询问题。     

一种障碍空间中移动对象的连续k最近邻查询方法

针对时空数据库中的连续移动对象的最近邻查询问题,提出COp KNN(continuous obstructed possible k-nearest neighbor)查询:在二维空间中,给定一个移动查询点q、一组移动查询对象集合P和一组多边形障碍物集合O,根据障碍距离的概念,查询q所有可能的k最近邻集合。由于移动对象本身的不确定性以及现实生活中障碍物的存在,已有的查询方式不再适用COp KNN查询。COp KNN查询包括三个子过程:根据可视图、R树和堆排序的概念,给出计算两点之间障碍距离(大于等于欧几里得距离)的方法;基于R树的查询方式查找在用户给定时间段内q所有可能的k最近邻结果集(初步结果,也叫候选集);采用Mindist(E,q)和候选集更新算法Updata C(pn)对k最近邻结果集进行剪枝,得到较为精确的k最近邻结果集。实验数据集和障碍物集均采用真实的数据集,理论研究和实验结果表明,该方法具有良好的效率。     

位置隐私保护下的连续最近邻查询

已有的位置隐私保护下的连续最近邻查询往往采用snapshot方式进行,导致较高的中央处理器开销.为此,研究了基于位置隐私的连续最近邻查询,提出了基于重用技术的位置隐私保护的连续最近邻查询算法.该算法利用相邻时刻查询结果集的相似性来减少计算成本,从而实现答案集的快速更新,可大大加快系统响应时间.实验结果表明了该算法的有效性.     

改进的概率数据流上Skyline查询算法

SOPDS是一种概率数据流上的skyline查询算法,它主要采用网格索引结构,使用概率定界、逐步求精、提前淘汰和选择补偿等启发式规则从时间和空间两个方面进行系统的优化。通过对对象间支配关系的进一步分析,在SOPDS算法的基础上,增加有效的过滤策略和对象身份判定规则,实现了改进的算法(ISOPDS)。实验表明,ISOPDS算法能有效地减少查询响应时间。     

一种连续最近邻查询的优化方法

连续最近邻查询是空间数据库中最重要的查询之一,在地理信息系统和位置定位服务等领域有重要应用.给定一个空间数据集P和查询线段q,连续最近邻查询返回结果＜R,T＞,其中T是一个间隔,R是这个间隔中所有点的最近邻.已有的连续最近邻查询算法无法实现I/O的优化,为此,提出一种优化的连续最近邻查询方法,该方法具有较高的I/O效率,不仅在减少磁盘访问数量方面进行优化,同时也提高CPU的性能.     

一种面向不确定图的 SimRank 算法

针对以往的搜索引擎日志分析都主要集中在用户行为分析、查询推荐及搜索引擎评价等方面,采用社会网络分析法对搜索引擎进行日志分析。以不确定图的方式逻辑表示搜索引擎的日志中查询词和网页的链接关系,通过基于不确定图的SimRank算法,计算查询词与网页的相似度,最终以相似度和查询词的加权方式建立网页描述库。针对概率抽样的3点基本要求,提出一种渐进式的抽样策略,从而保证采用抽样技术对于不确定图中SimRank值计算的准确性。实验表明该算法具有较好的准确率和可行性。     

基于V~＋图的移动K近邻查询研究

移动K近邻查询（MkNN）找到一个移动查询点的K个连续最近邻。目前解决此类查询的方法有两种：利用采样的方法和基于安全区域的方法。在传统的安全区域方法基础上提出一种基于安全区域的技术来计算MkNN,称为V＋图。此方法除了数据对象外还利用查询点和查询空间的信息,给出基于V＋图的MkNN查询算法和相应定理及其证明。     

时空数据库中基于TPR-树的反向最近邻查询

为研究动态环境下解决反向最近邻查询的算法,采用TPR-树索引结构给出了解决动态环境下的最近邻查询算法,并提出反向最近邻查询算法.该算法可有效解决平面上连续移动点的反向最近邻查询.     

移动点的反向最近邻查询

反向最近邻（RNN）查询是空间数据库查询的一个重要的问题。随着无线通讯的发展,时空数据库中反向最近邻查询问题越来越受到关注。本文基于Voronoi图的定义和性质,采用一种不同于Delaunay三角剖分的另外一种三角剖分进行研究,其优势在于对于某个特定点,包含它的三角形的数量较少,查询效率较高。     

道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。     

一种基于概率模型的运动趋势查询处理

运动趋势的准确预测是实现移动对象数据库中各种预测性时空查询处理的基础.提出了一种基于概率模型的运动趋势查询及处理方法.该方法将移动对象未来可能出现的位置定义为一种随机变量.运动趋势查询的处理就是检索随机变量的概率密度函数集合并进行概率计算的过程.为了获得较为准确的概率密度函数集合,提出一种通过对大量历史轨迹随机抽样来估计概率密度函数的方法.还设计了一种能够有效存储概率密度函数和提高运动趋势查询处理效率的索引结构.实验结果表明,提出的方法能够有效支持运动趋势查询的处理并提高对移动对象运动趋势预测的准确性.     

移动点对象轨迹上k-最近邻查询

移动点对象轨迹上k-最近邻查询是时空数据库中重要的查询之一.在时间-距离空间基础上,提出监测第k个最近邻的方法,采取了速度更新预测策略及更新预留内存的自底向上更新的R-树索引结构.当移动对象的速度或路径发生改变时,把即将更新的位置信息先存储在内存更新列表中,后更新列表已达最大预设值时才去更新R-树索引结构.此方法有效减少了磁盘的访问次数,提高了查询的效率.     

ISNN:一种基于密度的高效增量聚类算法

目的提高算法效率，减少磁盘访问次数，提出一种基于密度的高效增量聚类算法ISNN．方法将更新对象的空间进行划分，定义了基于该划分的最近邻居概念，在此基础上应用一种剪枝策略来确定受影响对象的集合，数据更新时，只需要对受影响对象集合进行处理．结果受影响对象集合远小于原数据集合，显著地提高了算法效率．结论实验表明。ISNN在效率和磁盘访问次数上都显著优于SNN算法．     

基于SR-树的空间对象反最近邻查询技术研究

反最近邻查询是空间数据库的重要应用之一,是在最近邻查询基础上提出的一种新的查询类型,以往基于范围查询或最近邻查询的方法搜索影响集效率不高,本文在分析RNN查询的基本概念和存储区域的基础上,区别于R＊-树,提出了基于SR-树的RNN查询方法,优化了空间对象的反最近查询性能,在高维空间查询上具有明显优势。     

基于Vague集的不确定方向查询

针对方向关系界定的不确定性,提出基于Vague集的不确定区域方向关系模型,并利用Vague集方向关系矩阵分析不确定空间对象的方向关系隶属程度.讨论了空间对象与其MBR间的方向谓词映射关系,给出了边界不确定对象之间的方向查询实例及算法.结果表明,用Vague集来表示不确定性区域能够体现出空间对象与方向片相交的最大(最小)程度,比用模糊集更确切,不确定查询更符合人类思维的心理特征.