基于本地化差分隐私的空间数据近似k-近邻查询

针对现有本地编码机制与本地扰动机制在收集空间数据时不具有保距性的问题,提出了基于局部敏感Hash结构(locality-sensitive hashing, LSH)的近似k-近邻(k nearest neighbor,kNN)查询算法PELSH与PULSH.这2种算法利用具有多Hash函数的多Hash表对所有用户位置数据进行索引,结合多Hash表结构响应近似kNN查询.每个用户结合收集者所共享的多Hash表副本,将自身位置数据以汉明空间嵌入方式编码成0/1串.借助LSH结构对0/1串进行Hash压缩,并利用GRR机制与按位扰动机制对压缩后的0/1串进行本地处理.收集者利用每个用户的报告值重构多Hash表索引结构,遍历多Hash表响应空间近似kNN查询.为了有效地利用LSH索引结构的特点,PELSH和PULSH算法结合隐私预算分割与用户分组策略来重构多Hash表结构,基于这2种策略设计了4种本地扰动算法PELSHB,PELSHG,PULSHB和PULSHG.PELSH和PULSH算法与现有的近似kNN查询算法在真实的大规模空间数据集上的实验结果表明,所设计的近似空间kNN查询效果优于同...     

基于分布式范围树的结构化P2P多维范围查询

基于分布式哈希表（DHT）的结构化P2P网络具有扩展性好、健壮和自组织等优点,但只支持精确匹配的查询.本文提出一种基于分布式范围树的结构化P2P范围查询方法（DRT-RQ）,该方法将多维索引的分布式范围树分发到已有的结构化DHT覆盖网络中,利用DHT系统提供的数据查找接口,有效实现数据对象的范围查询.实验结果表明,基于分布式范围树的范围查询（DRT-RQ）比基于前缀哈希树的范围查询（PHT-RQ）需要更短的查询延时.     

RB树:一种支持空间近似关键字查询的外存索引

空间近似关键字查询包含一个空间条件和一组关键字相似性条件,这种查询在空间数据库中返回同时满足以下条件的对象:1)对象的位置信息满足查询中的空间条件;2)对于查询中的任何一个关键字,对象中至少包含一个关键字与其相似度大于给定阈值.随着当前数据的爆炸性增长,空间数据库无法完整地存放在内存中,因此空间数据库需要支持空间近似关键字查询的外存索引.目前,还没有在外存中支持精确的空间近似关键字查询的索引结构.设计了一种新型的外存索引RB树,在外存中支持精确的空间近似关键字查询.RB树支持的空间近似关键字查询包括多种空间条件,如范围查询、NN查询,同时支持多种关键字相似性度量,包括编辑距离、规范化编辑距离等.通过真实数据中的性能测试验证了RB树的效率.     

基于DPR树的分布式并行空间索引机制的研究

针对分布式并行环境下海量空间数据管理与并行化处理的效率问题,以提高分布式并行空间数据的查询效率为目的,根据现有的空间索引结构与并行化技术,提出一种新的分布式并行空间索引结构--DPR树.DPR树是空间索引技术与并行化技术优化结合的成果.DPR树在数据的总体划分与部分查询中所采用的均是基于高效处理技术.它在原有的并行Master-client R树的基础上进行改进,采用了HCSDP数据划分技术,并将其应用到分布式环境下,且每个节点机中各子树采用了改进的R树--R*Q树.通过性能分析表明,该索引结构具有高效的查询性能.     

面向移动对象的高效预测范围聚集查询方法

预测范围聚集查询是移动对象数据库中重要的查询类型之一.提出了一种PRA树高效预测范围聚集查询索引,对速度域进行规则划分,根据速度矢量大小将移动对象映射到不同的速度桶中,针对每个速度桶,提出了一种聚集TPR树索引,通过在TPR树中间节点中加入聚集信息以减少预测范围聚集查询所需要的节点访问代价.PRA树索引增加了一个建于叶节点之上的Hash辅助索引结构,并采用自底向上的删除搜索算法,具有很好的动态性能和并发性.提出了一种增强预测范围聚集查询EPRA算法,采用更精确的剪枝搜索准则,减少了查询所需要访问的节点代价.实验结果与分析表明,基于PRA树索引的EPRA查询算法具有良好的查询性能,优于通用的TPR*树索引.     

支持预测查询和部分历史查询的移动对象索引方法

针对TPR*-tree隐含移动对象部分最近历史信息但不能提供历史信息查询的问题,将移动对象创建或更新时间引入到索引树中,提出一种既支持预测查询又支持部分历史信息查询的索引树Basic HTPR*-tree,为全时态查询奠定了坚实的基础.同时,为了支持移动对象的频繁更新,在Basic HTPR*-tree索引树基础上引入内存概要结构和Hash辅助索引结构,提出支持自底向上更新策略的HTPR*-tree索引结构.实验结果表明,HTPR*-tree更新性能优于TPR*-tree和Basic HTPR*-tree(TD_HTPR*-tree),预测查询性能仅仅稍逊于TPR*-tree.     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

加密XML数据结构索引方案研究

充分利用XML数据库文档的树形结构特性,结合Dewey编码原理和B+树的索引特性,提出了一种基于B+树的加密XML结构索引和查询模型.在XML文档加密过程中,将XML加密数据与基于加密数据的B+树索引一起存储在服务器端,以便在服务器端完成对加密数据的结构索引.实验结果表明,此法提高了查询的效率,无需解密无关的加密数据,有效地实现了对加密XML数据的结构索引.     

道路网络环境下的近似反k最近邻查询算法

针对欧式空间中基于R树索引结构的反最近邻查询技术不适用于道路网环境,利用任意度量空间中的M树索引结构代替R树索引结构,进行道路网络中的反最近邻查询处理.然而,由于网络距离的计算代价高的问题,使得基于M树索引的反k最近邻查询效率很低.因此,采用道路网络嵌入技术,映射道路网络到高维向量空间,简单的L∞距离准确近似计算网络距离.在此基础上,提出道路网中近似反k最近邻查询的ARkNN算法,并对本文L∞距离近似网络距离的质量、k-中心聚类算法选取参考点的有效性和ARkNN算法的查询效率进行了实验验证.     

一种基于二层网格的移动对象B+树索引

在已有的基于空间分割的移动对象B+树索引基础上,提出一种分割空间的新方法,对空间进行二层网格分割,使空间分割很好地解决由移动对象在空间中分布不均造成的索引效率下降的问题。给出基于这种索引结构的Range查询和kNN查询算法。实验结果表明, 该索引结构的性能基本不受移动对象分布的影响。     

深度优先遍历Δ-tree的非递归KNN查询

kNN查询是高维数据库中最重要的操作之一,尽管它在数据库研究中得到了极大的关注,但很少有关于主存数据库kNN查询的工作。充分利用kNN查询自身的特点,基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search,该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索空间,从而提高kNN查询效率。通过实验对该算法进行了估价,结果证明该算法是有效的。     

Hierarchical Indexing Structure for Efficient Similarity Search in Video Retrieval

With the rapid increase in both centralized video archives and distributed WWW video resources, content-based video retrieval is gaining its importance. To support such applications efficiently, content-based video indexing must be addressed. Typically, each video is represented by a sequence of frames. Due to the high dimensionality of frame representation and the large number of frames, video indexing introduces an additional degree of complexity. In this paper, we address the problem of content-based video indexing and propose an efficient solution, called the ordered VA-file (OVA-file) based on the VA-file. OVA-file is a hierarchical structure and has two novel features: 1) partitioning the whole file into slices such that only a small number of slices are accessed and checked during k nearest neighbor (kNN) search and 2) efficient handling of insertions of new vectors into the OVA-file, such that the average distance between the new vectors and those approximations near that position is minimized. To facilitate a search, we present an efficient approximate kNN algorithm named ordered VA-LOW (OVA-LOW) based on the proposed OVA-file. OVA-LOW first chooses possible OVA-slices by ranking the distances between their corresponding centers and the query vector, and then visits all approximations in the selected OVA-slices to work out approximate kNN. The number of possible OVA-slices is controlled by a user-defined parameter delta. By adjusting delta, OVA-LOW provides a trade-off between the query cost and the result quality. Query by video clip consisting of multiple frames is also discussed. Extensive experimental studies using real video data sets were conducted and the results showed that our methods can yield a significant speed-up over an existing VA-file-based method and (distance with high query result quality. Furthermore, by incorporating temporal correlation of video content, our methods achieved much more efficient performance     

基于空间近邻查询的移动医疗呼叫算法

随着大数据时代的到来，传统的计算机因为单机资源有限、运行速度慢、分布式处理支持差，已满足不了现行的医疗体系中的大数据处理需求，基于时空数据的移动医疗呼叫系统方法可以很好地解决这些问题。在移动云计算环境下研究[k]最近邻查询算法是当前一个热点问题，支持可扩展和分布式的空间数据索引对于kNN查询的效率影响很大，目前已有的查询算法不适合并行化或者会导致内容冗余。将MapReduce分布式处理技术与空间kNN查询方法相结合，设计可以快速检索到满足用户查询需求的医生位置信息的移动医疗呼叫算法。提出并构建了一个新的分布式空间数据索引方法：倒排Voronoi图索引，它将倒排索引和Voronoi图索引进行结合；提出了一种基于MapReduce的利用Voronoi图来处理kNN查询的高效算法，其在分布式环境下可以有效提高查询效率；用真实的和仿真的数据集来进行大量实验评估，实验结果表明所提出的方法具有良好的高效性和可扩展性。     

一种基于图结构分解的图近似查询方法研究

图近似查询能够得到与查询图近似的结果集,相比较精确查询具有更广泛的应用范围。为提高近似查询的查准率和查全率,提出一种基于图结构分解的查询算法。该算法通过对查询图和目标图进行图结构分解,对其建立图分解索引,利用查询图的最小生成树集得到满足阈值的生成树集,通过图标准编码在索引中快速定位,查找出所有可能的近似结果。实验结果表明,该算法能有效得到近似结果,提高查询速度。     

基于Buddy*-Hash的移动对象时空查询方法

索引技术可以提高数据检索和查询效率,为了实现对时空数据库中移动对象的查询操作,需要引入时空索引技术。在传统Buddy-树的基础上提出Buddy*-Hash索引结构,根据扩展查询窗口策略给出范围查询算法。实验结果表明,基于BH索引结构的范围查询算法具有良好性能。     

路网中位置不确定的二元反kNN查询

针对路网限制和物体位置的不确定性,提出了路网中位置不确定的二元反kNN查询（PBRkNN）,旨在查找一组位置不确定的点,使得每个不确定点的kNN包含给定查询点的概率大于一个阈值。为了解决该问题,首先提出一种基于Dijkstra进行剪枝处理的基本算法,即PE算法;接着在PE算法的基础上通过预处理计算出每个点的kNN从而加快查询速度,即PPE算法;而为了进一步减小PPE算法中范围查询的开销,提出PPEE算法,利用网格索引来索引范围查询中要查询的不确定空间点,从而提升算法的效率。最后,在北京和加州路网数据集上进行了大量实验,结果表明通过一些预处理的策略确实可以有效地处理路网中位置不确定的二元反kNN查询。     

Density-based spatial keyword querying

With the rocket development of the Internet, WWW(World Wide Web), mobile computing and GPS (Global Positioning System) services, location-based services like Web GIS (Geographical Information System) portals are becoming more and more popular. Spatial keyword queries over GIS spatial data receive much more attention from both academic and industry communities than ever before. In general, a spatial keyword query containing spatial location information and keywords is to locate a set of spatial objects that satisfy the location condition and keyword query semantics. Researchers have proposed many solutions to various spatial keyword queries such as top-K keyword query, reversed kNN keyword query, moving object keyword query, collective keyword query, etc. In this paper, we propose a density-based spatial keyword query which is to locate a set of spatial objects that not only satisfies the query’s textual and distance condition, but also has a high density in their area. We use the collective keyword query semantics to find in a dense area, a group of spatial objects whose keywords collectively match the query keywords. To efficiently process the density based spatial keyword query, we use an IR-tree index as the base data structure to index spatial objects and their text contents and define a cost function over the IR-tree indexing nodes to approximately compute the density information of areas. We design a heuristic algorithm that can efficiently prune the region according to both the distance and region density in processing a query over the IR-tree index. Experimental results on datasets show that our method achieves desired results with high performance.     

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

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

面向不确定图的k最近邻查询

生物网络、社会网络、交际网络等复杂的网络被广泛的研究,由于数据抽出时引入的噪声和错误使这些数据具有不确定性,因此可以对这些应用使用不确定图模型建模,k最近邻查询问题是查询一个图上的距离某个特定点最近的k个邻居节点的问题,它是不确定图上的一个基础问题.设计了一个解决不确定图上最近邻问题的框架,首先定义了一种新颖的不确定图上的k最近邻查询,然后提出了针对该查询的一般处理算法,同时对该算法进行了优化,使算法效率得到极大提高.理论分析和实验结果表明提出的算法能够高效地处理不确定图上的k最近邻查询.     

基于对象数量的宽度加权聚类kNN算法

传统k最近邻算法（k-Nearest Neighbor,kNN）作为一种非参数化分类技术在数据分析中具有广泛的应用,但该算法具有较多的冗余计算,致使处理数据时需要花费较多的计算时间。目前大量的研究都集中在数据的预处理阶段,通过为数据建立模型降低kNN查询的计算量。提出一种基于对象数量的宽度加权聚类kNN算法（NOWCkNN）,该算法中数据集首先以全局宽度进行聚类,每个生成的子集群根据其对象数量递归计算其宽度的权值,然后算法根据其权值的大小和调和系数调节宽度值,最后生成不同宽度大小的集群用于kNN查询。这不仅减少了算法的聚类时间,还能平衡产生集群的大小,减少迭代次数,使三角不等式修剪率达到最大。实验结果表明,NOWCkNN算法与现有工作相比在各个维度的数据集中有较好的性能,尤其是在高维度、数据量较大的数据集中有更高的修剪效率。