一种障碍空间中移动对象的连续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最近邻结果集。实验数据集和障碍物集均采用真实的数据集,理论研究和实验结果表明,该方法具有良好的效率。     

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

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

反向最远设施查询及其代价模型的研究

针对现有反向最近邻查询不能有效支持满足弱影响集的设施查询这一类问题,利用离散边界点及邻域区等概念和相关定理实现对反向最远邻的判定.在此基础上提出反向最远设施查询,并给出其选择查询算法及索引结构.该算法可以准确地得到反向最远设施查询的结果,其动态更新算法可实现对查询点的反向最远设施查询结果的更新.在R~*-树的基础上构建RFF-树,并给出其选择查询算法的代价模型.实验结果表明,在3种不同数据分布空间中,采用基于RFF-树的反向最远设施选择查询的实际页面访问次数与代价分析预测的结果相近,代价模型的平均误差率约为12%.     

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

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

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

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

移动云计算环境下的双色反近邻查询算法

研究在移动云计算环境下的最大双色反最近邻查询优化问题,设计新的高效的双色反最近邻查询算法——SILM算法.SILM算法是基于MapReduce框架下的倒排网格索引结构,在Map函数中对分片数据区域使用PCT轮圈算法.对包含在圆区域内或与圆相交的网格的权值记为1,在Reduce函数中使用网格处理算法对分片数据区域进行扫描及合并,对重叠的网格的权值进行累加,输出网格空间中权值最大的网格区域.SILM算法可以在多计算节点上进行分布式计算,更适合于在移动云计算环境下处理大规模并行查询请求.通过实验对SILM算法的效率进行验证.实验结果表明,当数据量较大(数据点个数大于2.0×10~6)时,SILM算法的查询效率是目前解决最优选址问题最佳算法的2倍.     

基于维诺图的位置隐私最近邻查询方法

针对K-匿名、空间匿名、位置模糊等隐私保护方法易受推理攻击及连续多查询攻击的不足,提出了一种抗连续多查询攻击的基于维诺图的位置隐私最近邻查询算法.该算法基于K-匿名思想以及维诺图算法,在可信第三方生成K-匿名集,用基于位置的服务(location based service,LBS)运营方服务器上存储的兴趣点(point of interest,POI)划分维诺图,基于用户与POI之间的邻近关系生成关系矩阵;用K-匿名集生成的离散维诺图构成匿名空间,以抵抗多查询攻击,保护用户位置隐私安全;用私有信息检索(privacy information retrieval,PIR)技术保护用户兴趣点查询隐私的安全.在保证关系矩阵匿名度的同时,也确保了K-匿名集的用户查询位置语义的单一性,以不同的维诺图划分集合,确保了l-多样性.     

概率可视最近邻查询算法

针对不确定对象的可视最近邻查询问题,对不确定Voronoi图的性质进行分析,提出多层邻接生成点和多层不确定Voronoi区域等概念,给出判断概率可视最近邻的理论方法,并提出基于不确定Voronoi图的概率可视最近邻查询算法,该算法通过直接确定参与查询的概率可视最近邻的范围以及参与可视性判断的障碍集的范围,避免了索引遍历时大量的比较计算和剪枝操作,采用真实数据集和模拟数据集对提出的算法进行了性能分析,实验结果表明,提出的算法能够有效地处理不确定对象的可视最近邻查询．     

移动对象的动态反向最近邻算法

针对现有的算法,很多观点都是基于静态对象的,提出以TPR-tree为索引结构,用现有的半平面修剪策略进行改进的,利用剩余MBR的对角线判断是否保留MBR的方法,使原修剪策略性能优化,并采用过滤提纯的方法来获取移动查询点的反向最近邻,实现了移动对象的动态反向最近邻查询.     

一种快速的反向k近邻查找算法及其改进

提出一种快速的反向k近邻查找算法,该方法利用现代计算机具有外存便宜、运行速度快的特点,预先计算数据之间的距离,并组织为数据索引块存储于外存,由计算机在空闲时自动进行维护.在进行反向最近邻查询时,只需读入相应的索引块,就可进行直接查询,其时间复杂度为O(N),而且不受k的影响.为减少索引块的读取时间,提出一种改进方法来有效地压缩索引块,仅用必要的二进制位来存储对象之间的距离,并将冗余减少到最低水平,提高了算法的效率.最后通过实验分析评估算法的有效性和效率.     

一般空间对象的空间数据类型

空间数据类型的定义一直是空间数据库和GIS等领域的研究热点.针对一般空间对象的空间数据类型定义问题,依据点集和拓扑理论,采用函数方法,研究了一般空间对象的特点,并给出了一组有效时间内的一般空间对象的带时间维的空间数据类型定义,包括一般点,一般线,一般区域.一般空间对象的空间数据类型定义将一般点定义为多个单点的并集;一般线定义为多个连续函数的并集;一般区域定义为多个面的并集.在一般空间对象的空间数据类型基础上,可建立一般空间对象的数据模型,一般空间对象的空间关系,从而在空间查询中,能处理针对一般空间对象的空间查询.     

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

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

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

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

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

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

基于Google地图的KML空间数据查询

给出KML空间数据查询的解决方案,并在基于Google地图建立的Web地理信息系统中予以实现.该方案采用Linq to XML方法实现KML属性查询,采用Net Topology Suite计算空间对象之间的拓扑关系,综合应用此两种技术解决KML空间查询.基于此方案,在VS2010中开发出一套交互式KML空间查询工具,包括点选、连选、区域选择、依属性选择、去选等.     

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

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

基于改进Kd-Tree构建算法的k近邻查询

k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率。但是,传统的Kd-Tree构建有两个缺点：使用测试数据点进行k近邻查询每次都需要回溯到根节点,影响了查询的效率;Kd-Tree使用split域对空间进行层次划分,空间划分为立方体（二维数据表现为矩形）,多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间,这样会影响查询的效率。针对这两个缺点,本文提出了相应的改进算法---RB算法。实验结果证明,该算法比传统的KD算法拥有更高的查询效率。本文的主要贡献有两点：（1）构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作。（2）改进传统的Kd-Tree索引构建方法,提出新的改进算法RB算法,提高KNN算法查询的效率。     

交通网络中移动对象定点CRNN查询算法

目的在交通网络中实现移动对象的定点CRNN查询监控,确定受到定点影响的移动对象集合.方法根据交通网络的特征,定义网络中RNN的概念,采用PMR四叉树来索引交通网络结构,利用监控树来简化对网络上移动对象的计算判断和监控.结果测试显示该算法能够针对现实交通网络,实现定点CRNN的查询监控.结论实验表明,在移动对象和查询数量增大时,该算法显示出较好的伸缩性.