最近邻查询

摘要： 针对用户移动后解析服务节点切换问题,文中提出一种基于Geohash网格编码的节点地理邻居生成方法,用于新服务节点的快速发现。该方法通过把节点的地理位置转换为Geohash网格编码,借助编码规律提高近邻查询效率。实验结果表明,与kNN查询中最精确的穷举法对比,在保证地理邻居节点查全率的情况下,节点数量级为104时,算法平均耗时下降60%,且随着节点数量的不断上升,算法耗时下降比例会继续增加。在节点数量较大时,所提方法可以大量节省计算资源。

摘要： 针对路网数据存储数据量较大、常规查询算法效率较低的问题,将存储技术与查询算法相结合,提出利用4-叉树结构对路网数据进行均匀划分的最近邻查询算法.首先根据兴趣点使用Voronoi图将空间划分为多个相邻空间单元,利用空间均分法对整个空间区域分区,使每个分区包含若干个空间单元;再使用4-叉树结构创建内存索引数据,降低最近邻查询的数据范围;最后采用OSM(open street map)官网的路网数据进行分区查询实验验证.结果 表明,与传统迭代切分法和折半分割法相比,建立在结构化分区上的最近邻查询算法可大大提高路网数据的查询效率.

摘要： 隐私问题受到越来越多的关注,基于计算的私有信息检索(CPIR)的隐私保护技术允许用户从服务提供商检索数据并且不会泄露查询信息.但是,对于大规模应用,隐私保护技术与可用性之间存在较大差距.针对CPIR算法计算量大、计算时间长而不适合应用于大规模数据隐私保护的问题,提出了基于Spark和Huff man编码的CPIR最近邻查询隐私保护算法(H-PCPIR-V).H-PCPIR-V算法主要是在数据预处理阶段将最近邻矩阵使用Huff man编码进行压缩减少计算位数,然后通过压缩后矩阵中元素的最大位数对其他元素进行补位,在服务端使用Spark并行框架对查询网格进行并行计算.通过对比实验及实验结果分析发现,相比PCPIR-V算法,H-PCPIR-V算法在服务端的计算代价下降30％左右,客户端的计算代价下降10％左右,通信代价下降40％左右.%With the privacy issues drawing more and more concerns,privacy protection techniques based on Computational Private Information Retrieval (CPIR) allow a user to retrieve data from a service provider without revealing the users query information.For large-scale applications,there exists a gap between privacy protection techniques and its feasibility.For the problem that the CPIR algorithm needs long computing time so as not to be suitable for large-scale data privacy protection,this paper proposes a CPIR nearest neighbor privacy protection algorithm (H-PCPIR-V) based on Spark and Huffman code.The H-PCPIR-V algorithm partitions the spatial data into Voronoi diagrams according to the points of interest in the data preprocessing stage,and then utilizes the Huffman code to compress the candidate data in order to reduce bit computation operation.Spark parallel framework is used for query grid parallel computing in the server side.The experimental results show that the computational cost of HPCPIR-V algorithm is about 30 ％ lower than that of PCPIR-V algorithm on the server side,the computational cost of client is about 10％ lower,and the communication cost is about 40％ lower.

摘要： Nearest neighbor query,as one of the building blocks of location-based service,has become a hot research topic in recent years.Compared with Euclidean space,road network is a more practical model in real applications;hence,nearest neighbor query in road network has received broader research efforts.In road network,tremendous data are generated along with sophisticated data structure,making nearest neighbor query computationally expensive.This poses a major challenge to spatial database community on its effort to effectively improve the query processing efficiency for nearest neighbor query.This work summarizes existing nearest neighbor query techniques in road network,and conducts analysis and comparison among them,from various perspectives including indexing structure and algorithm implementation.Additionally,several variants of nearest neighbor query are also summarized in this work.Finally,future research focus and trend for nearest neighbor query in road network are discussed.%最近邻查询作为基于位置服务的重要支持性技术之一,引起了众多学者的广泛关注和深入研究.相对于欧式空间而言,路网环境下的最近邻查询更贴近人们的生活,有着更重要的研究意义.路网环境下庞大的数据量和复杂的数据结构,使得最近邻查询的操作代价变得非常昂贵,如何有效地提高查询效率,是研究者面临的主要挑战.对路网环境下的最近邻查询技术进行综述,分别从最近邻查询采用的索引结构和查询处理过程对现有路网环境下的最近邻查询方法进行了分析和比较,也介绍了路网环境下最近邻的变体查询技术的研究情况,最后探讨路网上最近邻查询技术未来的研究重点.

摘要： 局部敏感哈希方法(LSH)已经被广泛用于高维数据和大规模数据集的最近邻查询,然而现有方法大多将LSH方法用于单一类型的数据,文中尝试将LSH方法用于二元混合类型数据,如图像-文本数据,空间-文本数据等.文中提出了一种基于LSH混合索引结构的相似性查询方法,该方法可有效地管理含两种数据类型的数据,并且融合两种数据类型的相似性进行最近邻查询.文中提出的查询方法主要有三个特点:首先,结合LSH方法为混合数据构建混合哈希值,该混合哈希值保留有数据对象之间内容相似性的信息,基于混合哈希值构建哈希索引,进行快速准确的最近邻查询;其次,该方法解决传统LSH方法固定敏感半径的问题,可以有效地处理可变查询范围的相似性查询;最后,该方法在分布式环境中不需要全局索引信息,保证分布式查询的伸缩性.文中通过理论分析证明了查询方法和查询算法的准确性和有效性,进一步通过分布式系统优化及基于真实数据和合成数据的大量实验验证了方法的伸缩性和高效性.

摘要： 对学习型哈希算法用于最近邻查询,出现二进制编码的海明距离小导致重排序的问题进行研究,提出一种基于加权自学习框架的哈希方法.给定一个查询对象,通过自学习哈希方法返回满足特定海明距离的候选对象,根据所得候选集求得二进制编码各位的权重,计算查询对象与候选集中各个数据对象的加权海明距离,得到在更细粒度上排序的候选集.实验结果表明,我们的方法能够高效的对具有相同海明距离的不同海明编码进行重排序.

摘要： 随着移动互联网的快速发展和智能移动设备的广泛普及,空间文本对象的数量在不断增大,随之而来的是开展空间关键词查询技术的研究.Top-k空间关键词搜索是从空间数据库中探索有用信息的重要途径.近年来已经提出了各种各样的混合索引技术,主要是将R树和倒排表结合起来,从而同时执行空间修剪和文本修剪.然而,随着数据量的快速增长,在索引维护成本和查询处理时间两个方面对现有的方法提出了很大的挑战.针对这一问题,在改进的线性四分树的基础上,提出一种基于自适应虚拟四分树的空间关键词最近邻查询算法Avqt.在真实数据上进行实验验证,结果表明该算法的有效性.

摘要： 因为查询和存储具有高效性,学习型散列逐渐被应用于解决最近邻查询问题.学习型散列将高维数据转化成二进制编码,并使得原始高维空间中越相似的数据对应二进制编码的汉明距离越小.在实际应用中,每次查询都会返回许多与查询点汉明距离相同而编码互不相同的数据.如何对这些数据进行排序是一个难题.提出了一种基于加权自学习散列的近邻查找算法.实验结果表明,算法能够高效地对具有相同汉明距离的不同编码进行重排序,加权排序后查询的F1值约是原来的2倍并优于同系算法,时间开销可比直接计算原始距离进行排序降低一个数量级.%Because of efficiency in query and storage,learning hash is applied in solving the nearest neighbor search problem.The learning hash usually converts high-dimensional data into binary codes.In this way,the similarities between binary codes from two objects are conserved as they were in the original high-dimensional space.In practical applications,a lot of data which have the same distance from the query point but with different code will be returned.How to reorder these candidates is a problem.An algorithm named weighted self-taught hashing was proposed.Experimental results show that the proposed algorithm can reorder the different binary codes with the same Hamming distances efficiently.Compared to the naive algorithm,the F1-score of the proposed algorithm is improved by about 2 times and it is better than the homologous algorithms,furthermore,the time cost is reduced by an order of magnitude.

摘要： 由于多索引哈希基于数据集中的二进制码呈均匀分布这一假设，不能有效地处理非均匀分布的数据集，故针对这一问题提出数据依赖的多索引哈希算法．首先把二进制码划分为多个连续不重合的子串，并通过计算二进制码每位之间的相关性为每一个子串学习得到自适应投影向量；在为每个子串建立哈希表时，使用投影向量对子串进行投影，从而得到哈希表中的下标；采用自适应投影的方法可以使得哈希表中的元素接近于均匀分布，进而提升了查询速度．此外，提出一个基于熵的分布度量方法，以评价哈希表中数据元素的分布情况．在大规模数据集上的实验表明，与多索引哈希算法相比，数据依赖的多索引哈希算法可以使查询速度提升36.9％～87.4％．%The multi‐index hashing ( MIH ) is the state‐of‐the‐art method for indexing binary codes . However , it is based on the dataset codes uniform distribution assumption , and will lower efficiency in dealing with non‐uniformly distributed codes . In this paper , we propose a data‐oriented multi‐index hashing method . We first compute the correlations between bits and learn adaptive projection vector for each binary substring . Then , instead of using substrings as direct indices into hash tables , we project them with corresponding projection vectors to generate new indices . With adaptive projection , the indices in each hash table are nearly uniformly distributed . Besides , we put forward an entropy based measurement to evaluate the distribution of data items in each hash table . Experiments conducted on reference large scale datasets show that compared to the MIH the time performance of our method can be 36.9% ~ 87.4% better .

摘要： 近年来,基于位置的服务获得了越来越广泛的关注,其中最近邻查询是最常用的一种查询方式。测量手段的不准确性以及数据本身的性质导致不确定性在位置数据中普遍存在,这种不确定性会对最近邻查询结果产生影响。空间中障碍物的存在也给空间数据查询带来了挑战。文中研究存在障碍物的空间中不确定对象连续最近邻查询的处理方法,设计了一种剪枝策略大幅降低需要计算的不确定对象数目,并进一步提出了障碍空间中不确定对象最近邻查询安全区域的概念及安全区域生成算法。设计了安全区域的索引存储方法。实验结果表明,文章所提出的方法具有良好的效率和可扩展性。

摘要： 本文阐述高维空间中的最近邻(Nearest Neighbor,NN)查询是多媒体数据库领域中的一个基本问题.局部敏感哈希(Locality-Sensitive Hashing,LSH)索引结构能有效克服“维数灾难”现象,是解决c-近似最近邻(c-ANN)问题的一种有效手段.为进一步降低I/O开销,SK-LSH方法为复合哈希键值建立线序,通过优化候选点在磁盘上分布的局部聚敛性,能有效兼顾最近邻查询精度和磁盘访问效率.本文通过分析空间线序机理对最近邻候选点分布局部聚敛性的影响,指出SK-LSH中键值线序的不足,提出一种基于线序优化的LSH外存索引技术,O2LSH(Optimized Order LSH).使用曲线性能更加优秀的z-order代替SK-LSH中的row-wise曲线指导键值排序,借助z-order更好的局部空间优先遍历的性质更快地召回最近邻,从而在保证查询精度的前提下,进一步提升磁盘访问效率、节省多索引哈希表的构建开销.在实际的多媒体数据集上进行的对比实验表明:优化了键值线序后,O2LSH在最近邻查询精度和效率上相对于SK-LSH有较大地提升.

摘要： 曲面感知的最近邻查询问题是空问感知数据受限查询的扩展。为了高效的处理曲面上数据集中给定点的最近邻，根据曲面的特征利用数学工具对其进行优化处理，将曲面上的最近邻问题转化为求解有界平面内点集的最近邻问题。根据不同的查询要求，利用球面Voronoi图可以查询球面上给定点的静态最近邻，运用欧式空间内空间数据索引结构的剪枝策略实现查询优化：给出基于Delaunay图的处理球面上数据点的反向最近邻查询的方法。利用降维方法对球面上数据集的最近邻问题进行优化处理：利用曲面投影于平面的思想可以简化查询，解决球面上定向受限最近邻问题。

摘要： 多媒体检索领域中处理特征向量的空间索引需要能够按照特征本身的相似程度建立索引结构,以实现快速的最近邻查询。目前主流的高维索引结构都无法满足多媒体信息检索的这种特殊需要。本文在R树的基本索引结构基础上,改进了插入算法,节点分裂算法,使索引树建立起来以后更加适合多媒体检索的需要,并通过对查询算法的改进实现了高效的最近邻查询。

摘要： 局部相关空间不确定数据越来越受到许多实际应用的关注。提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象。应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销。为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法。给出了分别作用于两个阶段的两个过滤方法。在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标。还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件。最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础。

摘要： 局部相关空间不确定数据越来越受到许多实际应用的关注。提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象。应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销。为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法。给出了分别作用于两个阶段的两个过滤方法。在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标。还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件。最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础。

摘要： 局部相关空间不确定数据越来越受到许多实际应用的关注。提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象。应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销。为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法。给出了分别作用于两个阶段的两个过滤方法。在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标。还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件。最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础。

摘要： 局部相关空间不确定数据越来越受到许多实际应用的关注。提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象。应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销。为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法。给出了分别作用于两个阶段的两个过滤方法。在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标。还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件。最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础。

摘要： 局部相关空间不确定数据越来越受到许多实际应用的关注。提出了一种新颖的定义在不确定数据库的多个快照上的概率频繁近邻查询,目的是在多个快照数据上找到以一定概率频繁成为查询点最近邻的那些对象。应用现有的基于传统数据和基于不确定数据上的近邻查询算法直接处理这种查询会产生昂贵的开销。为了很好地解决这一问题,提出了一般的处理框架,其中包括相应的基于切尔诺夫界的过滤方法,以及对于概率质量函数的动态规划算法。给出了分别作用于两个阶段的两个过滤方法。在第1阶段,利用切尔诺夫界的上界推广形式可以过滤大量的候选目标,之后在第2阶段,利用切尔诺夫界的标准形式来进一步过滤候选目标。还讨论了用于处理扩展查询的动态规划算法以及相应的过滤条件。最后,在人工的和真实的数据上都进行了充分的实验,并验证了给出算法的有效性,为进一步的研究工作奠定了基础。

摘要： 基于位置的服务、电子地图定位等这样的概念正在逐渐为广大用户所熟悉,越来越多的电子地图类产品正不断地改变着我们的生活.利用电子地图,可以方便地查找最近的加油站、餐厅等各种信息.将电子地图的功能加入到如PDA、车载电脑等便携式设备中,结合全球定位系统(GPS),更可以为用户提供基于用户当前位置的各种服务,如随时告知用户的位置并为用户进行旅行导航等.这样的服务现在大多是面向汽车用户,提供基于城市道路网络的定位和导航服务. 依据道路网的实际特点,通过对R-tree结构进行适当的扩展,本文设计并构建了RR-tree结构.经实验证明,RR-tree索引结构以路段作为索引的基本单元,在不丢失路网信息的前提之下,对城市路网进行建模索引,提高了检索效率。

摘要： 本发明公开了一种基于Spark与Huffman编码的CPIR‑V最近邻隐私保护查询方法，将最近邻矩阵的数据使用Huffman编码进行压缩减少每个网格中的数据Bit位数；然后将压缩的数据，字符的码长以及元素最大值存储到空数据库HBase中；接着服务器端读取读取HBase数据库中的数据并缓存到Spark并行框架的RDD中，并根据并行策略对RDD中的CPIR最近邻矩阵进行分组，分组后Spark服务端根据查询信息进行CPIR并行计算，将每个分组的计算结果聚合然后将查询结果和字符码长发送给客户端；客户端将查询结果解析获得查询位的值，将查询位的值解压，得到查询信息。本发明基于Spark并行化和Huffman编码的隐私保护查询算法，保证在大数据应用场景下，保护用户的查询隐私并在原有的查询效果下提高查询效率。

摘要： 本发明公开了一种基于数据块学习的在线哈希最近邻查询方法，特点是包括以下步骤，图像数据获取及预处理、定义处理数据的哈希模型、建立判断更新后的哈希向量是否合理的海明距离预测损失函数、获取目标函数、优化目标函数和在测试数据库对给定的待查询数据进行在线哈希最近邻查询；优点是主要基于数据块的思路，每次处理流式小数据块，并在较小的数据空间中设计优化算法，提高学习效率，在设计方法上保证了在数据块内部数据样本间的海明空间损失最小，同时还对总体在线学习的增量变化进行约束，对噪声数据进行了有效控制，大大提高对给定的待查询数据的查询效率，并且减小了整体存储空间。

摘要： 本发明公开了一种基于哈希学习的在线高维数据最近邻查询方法，首先设计了分别根据样本相似或不相似性的预测损失函数并且扩宽了损失函数的范围，进一步设置了相似或不相似范围，然后结合哈希模型需要保持历史信息同时需要当前数据对损失最小的原则，提出新的目标函数，通过对在线哈希算法的收敛性进行分析，找到目标函数最优值。在此基础上，对于待查询数据点，能够快速地查询到最接近的数据点，平均准确率结果稳定收敛，迭代学习过程中哈希函数的更新大大减少。

摘要： 本发明公开了一种可变长度哈希编码的高维数据最近邻查询方法，特点是首先获取原始高维数据集并给定查询点，生成随机傅里叶特征向量集，接着获取与每个原始高维数据对应的哈希码及每个哈希码的编码频率，将编码频率相同的哈希码作为一组子数据集并排序，对每组子数据集设置压缩比，根据压缩比对每组子数据集进行压缩和训练，获取与每组训练后的子数据集对应的哈希编码和原始编码，复制每组训练后的子数据集的哈希编码得到多个复本，再将原始编码与对应复本串联得到串联后的哈希编码并融合组成最终的最近邻查询表；最后获取查询点的查询编码，在最终的最近邻查询表中查找最近邻数据集完成查询；优点是查询效率和准确性大大提高。

摘要： 本发明公开了一种面向大规模数据的自适应最近邻查询方法，特点是首先获取包含多个原始大规模数据的数据集并给定查询点，通过包含k次AND操作和L次OR操作的局部敏感哈希方法将原始数据集构造成若干个子数据集，然后学习得到与每个子数据集对应的哈希编码，然后将所有哈希编码按序排列得到所有子数据集的编码索引，再获取查询点在每个子数据集下的查找表，接下来获取查询点在对应的子数据集下的候选集并融合，得到对给定的查询点的最近邻查询结果；这种子数据集的构造方式能更好地挖掘数据集分布的信息，最大限度地降低了编码的冗余，提升了对给定的查询点的最近邻查询过程的查询精度和查询效率。

摘要： 本发明适用于通信技术领域，提供了一种基于语义轨迹大数据的反向最近邻查询方法及装置，其中方法包括：根据轨迹数据集建立轨迹索引IMC树，其中，所述IMC树包括倒排列表与多个MC树，所述倒排列表用于存储关键字词汇表，所述MC树包括用于存储轨迹局部位置的轨迹摘要；根据查询数据集建立查询索引WIBR树；通过对IMC树与WIBR树进行交替访问，确定查询q的查询结果rnnk(q)，所述查询结果为所述IMC树中将查询q作为最近邻查询的最小相关子轨迹。本发明提供的一种基于语义轨迹大数据的反向最近邻查询方法及装置，能够实现语义轨迹上的反向最近邻查询并能够得到更加具体确切的查询结果。

摘要： 本发明提供一种隐私保护群组最近邻查询方法及装置，包括：将位置排列信息发送给第二终端；根据所述位置排列信息将第一终端的真实位置和与所述第一终端的真实位置关联的假位置组合成第一位置集合；根据所述位置排列信息生成加密指示信息；根据用户输入的指示信息生成兴趣点集合；向服务器发送所述第一位置集合、所述加密指示信息和所述兴趣点集合，以使所述服务器根据所述兴趣点集合、所述第一位置集合、所述加密指示信息和从所述第二终端接收到的所述第二位置集合，生成目标查询结果。本发明提供的隐私保护群组最近邻查询方法，提高了隐私保护能力。

摘要： 本发明公开了一种路网下地理社交关键字反最近邻查询处理方法，利用GIM树对空间路网，文本，社交数据进行存储，并利用分支界限方法遍历索引；在遍历索引时本发明首先计算索引节点的最小相似性计数表与最大相似性计数表，而后利用上述最小相似性计数表和最大相似性计数表进行剪枝，并利用过滤、精炼算法以加速查询执行。本发明结合了空间数据库的现有技术，降低了地理社交文本相似性计算次数，从而提高了查询性能。

摘要： 本发明公开了一种基于轨迹大数据最近邻查询的个性化推荐方法。本发明基于轨迹大数据最近邻查询，设计高效的存储和索引结构来处理轨迹大数据。本发明首先对轨迹大数据进行抽取、降噪、转换和存储处理，而后对被存储的轨迹数据建立全局的R树索引和局部的R树索引，并对每个分区建立基于轨迹编号集合的索引和基于轨迹数目的索引。在用户提交查询时，通过访问本发明的索引结构，进行基于轨迹大数据最近邻查询以提供个性化推荐服务。本发明很好地满足了大数据环境下轨迹最近邻查询的需求，极大地提高了轨迹大数据最近邻查询的处理效率，提供了最佳的性能。

摘要： 本发明涉及一种基于点云最近邻查询的无人机轨迹生成方法，适用于搭载直接或间接深度传感器的旋翼类无人机直接基于原始点云进行轨迹生成。与传统在线维护地图耗费大量计算资源的轨迹生成方法相比，本发明采用了一种无图规划器，可以直接对未融合的传感器数据进行抽象。同时为了维护原始的历史信息，采用具有可靠邻近查询算法的有限内存数据结构，又基于采样方案提取自由空间骨架，并在最终的飞行走廊内生成高质量的轨迹。本发明提出的规划器不同于其他无地图的规划器，可以有效地提取和利用环境信息，显著提高了在线重规划的一致性和成功率。