外包空间数据库中反向k近邻查询验证

在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(ReversekNearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.     

空间数据库中的线段k近邻查询研究

K近邻查询是空间数据库中的重要查询之一,k近邻查询在内容的相似性检索、模式识别、地理信息系统中有重要应用。针对现有k近邻查询都是基于点查询的情况,提出基于平面线段的k近邻查询,查找线段集中给定查询点的k个最近线段。给出基于Voronoi图的线段k近邻查询算法及给出相关定理和证明。该算法通过线段Voronoi图的邻接特性找到一个候选集,然后从中找到最终结果。通过随机数据的实验证明,所提算法明显优于线性扫描算法和基于R树的k近邻查询算法。     

基于Geohash编码的位置隐私保护算法

针对基于位置服务中用户位置信息易泄露用户个人隐私的问题，利用Geohash编码优化网格化Casper模型，提出了基于Geohash的位置隐私保护算法G-Casper。该算法采用自底向上的机制，对目标位置的Geohash编码进行字符串模糊查询来确定组成匿名区域的[k-1]个近邻，在扩大扫描区域时，对请求用户所在网格以及周边网格跨域扫描，然后再进行层级的递归，同时使用[Lmax]和[Lmin]两个参数来控制匿名区域范围，最终通过剪枝算法删除冗余网格并随机发送一个候选网格区域代替用户原本位置，达到[k]-匿名的效果。实验结果表明，该算法能够更好地提高位置服务的质量和匿名区域的成功率，并且减少了查询时间和所需储存空间。     

路网中移动对象快照K近邻查询处理

扩展了一种支持路网中移动对象的位置相关查询框架的功能,利用存在磁盘上的R树来存储网络连通性和一种基于内存的网格结构来维持移动对象的位置更新,提出了基于范围查询(MNDR)的快照K近邻查询算法(SKNN),对空间中的任意一条边,分析可能受影响的最大数量和最小数量的网格单元格,说明用于快照范围查询处理的搜索空间的最大范围,预估包含查询结果的子空间,使用这个子空间作为范围调用MNDR来有效地计算路网中查询点的KNN POI,降低I/O成本,缩短查询时间。通过实验对比,当规模扩展到数十万的移动对象时,SKNN比种有效查询处理空间网络数据的预计算方法S-GRID有更好大的系统吞吐量。     

基于最小k 近邻错分率编码确定方法及其在多类分类中的应用

构造输出编码矩阵是将多类分类问题分解为多个两类分类问题的有效方法之一,如何判断一个编码阵的好坏是此类问题的关键．提出以最小庇近邻错分率作为评价标准,把构造问题简化为一个搜索问题．在M类的所有二类划分空间中,通过行交换规则和有限启发式搜索策略搜索出南近邻错分率最小的l个二类划分,并依据编码规则得到最终输出编码矩阵．实验中用人工数据集和UCI数据集分别测试,通过与几种经典的编码方法比较,结果表明该编码方法能在编码长度较小情况下得到更好的分类效果．     

约束的组近邻查询算法

传统的组近邻算法不能很好解决约束区域中的查询问题。因为一旦约束区域改变,算法需要重新建立索引。另外,如果查询集合发生变化,算法需要重新从磁盘装入节点,从而带来了冗余的I／O成本。为此,提出了一种新的算法,即约束的组近邻查询算法。主要思想包括在遍历过程中应用约束条件并利用信息重用方法。集中的实验结果表明提出的算法是有效而高效的。     

可伸缩的道路网络多连续k近邻查询处理

针对基于道路网络的多用户连续k近邻查询处理,提出了一种可伸缩的多用户连续查询处理(scalable processing of multiple continuous queries,SPMCQ)框架.SPMCQ框架采用流水线处理策略,将连续k近邻查询执行分解为可同时作业的预处理、查询执行和结果分发3个阶段,利用多线程技术提高查询处理的并行性.基于SPMCO框架,分别利用基于内存的哈希表和线性链表结构对移动对象位置和道路网络有向图模型进行存储和管理,提出了多连续k近邻查询处理SCkNN算法.实验结果表明,在处理多用户连续k近邻查询时,该算法性能优于目前的道路网络连续k近邻查询处理算法.     

基于NNlists的路网k路径近邻查询

为满足k路径近邻查询的实时性要求,运用预计算思想提出了基于NNlists的BNNL算法,通过在用户当前位置和目的地结点进行双向Dijkstra扩展得到两点间的最短路径,再通过对最短路径上的路网结点预计算的m近邻进行优化处理,最终得到正确的k路径近邻。该方法提高了k路径近邻查询的查询速度,尤其适用于兴趣点密度较大、k值较大的情况。     

基于Geohash的人工影响天气气象预警系统设计

通过对GDAL、Sharp Map、Net Topology Suite等开源GIS类库以及Geohash算法理论的研究,针对Geohash算法无法实现空间区域精确查询的问题,提出一种提高Geohash算法区域检索精度的解决方案,并据此实现人工影响天气气象预警系统。系统采用Geohash算法进行区域检索,结合以上开源类库对Geohash编码进行精确的地理距离计算及对查询区域最小外包矩形的划分等方法,有效地提高该算法的检索精度。通过实验对比,在空间数据越大,查询区域越小的情况下,相对于经纬度查询,越能体现基于Geohash编码的空间区域精确查询效率高的优势。该方案有效地提升了气象预警中区域栅格数据的检索分析效率,为海量气象资料的处理提供了一定的应用参考价值。     

基于空间网络数据库的组最近邻居查询

组最近邻居查询是空间数据库在最近邻居查询上的新问题.目前,对组最近邻居查询的研究局限于欧氏空间,考察的只是对象间的相对位置关系,无法处理现实生活中对象间的连通性问题.鉴于此,本文基于空间网络数据库提出以网络距离为度量标准的组最近邻居查询概念,进而提出作为其算法基础的增量最近邻居查询算法INNN,最后构造出算法NMQM.
实验证明,NMQM是一种有效的组最近邻居查询算法.     

基于自适应空间球的k最近邻域快速搜索算法

利用空间球搜索大规模点云数据k邻域存在速率慢和稳定性差的问题,为此,提出一种新的k邻域快速搜索算法。利用与k无关的分块策略对点云进行分块,使用候选点所在子块内采样点的近似密度自适应确定候选点的初始动态球半径,应用动态球的外切立方体搜索k邻域候选点。当候选点数目不满足要求或搜索不成功时,采用候选点动态球外切立方体的外接球扩大搜索范围。实验结果表明,与已有算法相比,该算法的k邻域搜索效率明显提高,而且当子块内预设点数变化、采样密度提高时具有较强稳定性,自动化程度较高。     

空间数据库平面线段近邻查询问题研究

空间数据库的近邻查询近几年受到人们越来越多的关注.近邻查询根据程度不同可分为点与点的近邻查询、点与线段、线段与线段的近邻查询.目前,前两者研究的较多,后者没有查到相关文献.提出平面线段与线段的近邻查询问题.有针对性地解决一些空间物体无法抽象为点的情况.平面线段的近邻查询在现实中有着广泛的应用价值.根据平面线段与线段是否相交分为两类;不相交的平面线段再根据位置关系分成9种情况.分别对上述各种情况进行讨论研究.给出了线段近邻查询的筛选规则、定理和查询算法,进行了实验分析和比较,新方法实现了平面线段与线段的近邻查询,具有较高的查询效率.     

一种可抵抗关键词猜测攻击的动态非对称可搜索加密方案

密文搜索可以用于保护用户存储在云端的文件,防止隐私的泄露,允许用户在不泄露明文信息的情况下进行搜索,根据使用密钥体制的不同,可分为对称可搜索加密和非对称可搜索加密.但是现有大多数的PEKS方案的索引构造都是基于文件-关键词对,每次搜索都需要遍历所有文件,这会使方案的搜索效率较为低下,并且现有的PEKS方案大都只支持静态...     

基于Voronoi图的连续反向最近邻查询

为解决动态环境中移动点的连续反向最近邻查询问题,将连续反向最近邻查询分为单色和双色2种情况进行研究。利用移动点Voronoi图,分别给出单色连续反向最近邻查询算法、双色连续反向最近邻查询算法以及相关定理,对算法正确性和可终止性进行证明,分析算法时间复杂性。按照移动点Voronoi图的拓扑结构是否改变分为2种情况,分析每种情况下候选所在区域的变化,在变化区域内进行Voronoi图的重构,得到对应的解决方法。在多数情况下,该算法只需生成局部移动点的Voronoi图即可找到结果,减小了连续反向最近邻查询的代价。     

基于新型索引结构的反最近邻查询

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义,提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree),该索引结构运用了R-树中分割空间数据的思想,将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance),利用多种序关系对原始点集进行划分,从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析,给出了MBDNN-树的性质.在此基础上,给出了MBDNN-树进行反最近邻查询的剪枝规则,进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性,有效地减少了结点的访问数量,从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明：基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.     

预定数据链规模的单纯型连续近邻链查询

研究预定数据链规模的单纯型连续近邻链(SCNNC)查询问题,基于Hilbert曲线,提出SCNNC_H_SS算法,将已处理过的数据点从数据集中进行剔除,可减少大量冗余计算。为对SCNNC进行动态维护和更新,提出SCNNC_H_CS算法。理论分析和实验结果表明,在数据集和待查近邻链的规模较大时,相比基于传统树索引结构的方法,该算法具有更高的查询效率。     

空间数据库中的组障碍最近邻查询研究

已有的关于组最近邻查询的研究都是基于欧氏距离的,无法解决存在障碍情况下基于障碍距离的组最近邻查询问题.为此,提出障碍物环境中组最近邻查询的一种新的变体,即组障碍最近邻(group obstacle nearest neighbor, GONN)查询.GONN返回数据集中与查询点集中所有点的障碍距离之和最小的点.根据数据集中的点与查询点集的最小外包距离(minimum bounding rectangle, MBR)之间的不同位置关系,构造各种情况下查询点集的MBR相对于数据集中点的剪枝区域.利用剪枝区域剪去障碍集中对障碍距离计算无影响的障碍,给出数据集中点与查询点集之间障碍距离的计算算法.定义组障碍最近邻查询的剪枝规则,根据障碍距离计算给出组障碍最近邻查询的算法.并给出相关定理和证明.实验结果证明算法具有较高效率.     

可伸缩的增量连续k近邻查询处理

针对基于TPR树(time-parameterized R-tree)索引的大量并发CKNN(continuous k-nearest neighbor)查询处理,提出了一种可伸缩的增量连续k近邻查询处理(scalable processing of incremental continuous k-nearest neighbor queries,简称SI-CNN)框架,通过引入搜索区域进行预裁剪以减少查询更新所需要的TPR树节点访问代价,并引入了增量结果表以保存候选对象,批量地更新查询结果集,具有良好的可伸缩性.基于SI-CNN框架提出了一种增量更新的SI-CNN查询处理算法,能够基于上次查询结果增量的更新查询,支持查询集合中加入或删除查询和移动对象数据集的插入、删除等动态更新操作.实验结果与分析表明,基于SI-CNN框架的SI-CNN算法可以很好地支持大量并发的CKNN查询处理,具有良好的实用价值.     

An Enhanced Technique for k-Nearest Neighbor Queries with Non-Spatial Selection Predicates

In multimedia databases, k-nearest neighbor queries are popular and frequently contain non-spatial predicates. Among the available techniques for such queries, the incremental nearest neighbor algorithm proposed by Hjaltason and Samet is known as the most useful algorithm [16]. The reason is that if k > k neighbors are needed, it can provide the next neighbor for the upper operator without restarting the query from scratch. However, the R-tree in their algorithm has no facility capable of partially pruning tuple candidates that will turn out not to satisfy the remaining predicates, leading their algorithm to inefficiency. In this paper, we propose an RS-tree-based incremental nearest neighbor algorithm complementary to their algorithm. The RS-tree used in our algorithm is a hybrid of the R-tree and the S-tree, as its buddy tree, based on the hierarchical signature file. Experimental results show that our RS-tree enhances the performance of Hjaltason and Samet's algorithm.