一种障碍空间数据库中的连续反k近邻查询方法

随着智能移动设备和无线定位技术的飞速发展,使用基于位置服务应用的用户越来越多.特别地,不同于传统的针对固定位置的快照查询,移动的用户往往基于移动轨迹发出连续的查询.在真实和虚拟的空间环境中,障碍物的影响都是广泛存在的,障碍空间内的查询处理技术得到了越来越多的关注,其中,障碍空间内的连续反k近邻查询处理有着重要的应用.对障碍空间中的连续反k近邻查询问题进行了定义和系统的研究,通过定义控制点和分割点,提出了针对该问题的处理框架.进一步地,提出了一系列的过滤和求精算法,包括剪枝数据集、获取障碍物、剪枝和计算控制点和更新结果集等处理策略.基于多种数据集对所提出的算法进行了实验评估.与针对每个数据点进行k 近邻计算的基本方法相比,这些方法可以大幅度提高查询处理的CPU 和I/O 效率.     

面向多核多线程的移动对象连续K近邻查询

针对移动对象的多用户连续K近邻查询处理问题,结合多核多线程技术的发展,提出了一种基于多线程的两阶段多用户连续K近邻查询处理框架.将查询处理分为查询预处理阶段和查询执行阶段,分别执行数据更新任务和查询处理任务,每个阶段都设计了优化cache访问命中率,并利用多线程技术提高多用户连续查询处理并行性的方法及数据结构.提出了一...     

面向复杂时间序列的k近邻分类器

基于时序对齐的k近邻分类器是时间序列分类的基准算法.在实际应用中,同类复杂时间序列经常展现出不同的全局特性.由于传统时序对齐方法平等对待实例特征并忽略其局部辨别特性,因此难以准确、高效地处理此类具有挑战性的时间序列.为了有效对齐并分类复杂时间序列,提出了一种具有辨别性的局部加权动态时间扭曲方法,用于发现同类复杂时间序列的共同点以及异类序列间的不同点.同时,通过迭代学习时间序列对齐点的正例集与负例集,获取每条复杂时间序列中每个特征的辨别性权重.在多个人工和真实数据集上的实验结果表明了基于局部加权对齐策略的k近邻分类器所具有的可解释性与有效性,并将所提出方法扩展至多变量时间序列分类问题中.     

基于Voronoi-R*的隐私保护路网k近邻查询方法

针对已有的保护位置隐私路网k近邻查询依赖可信匿名服务器造成的安全隐患,以及服务器端全局路网索引利用效率低的缺陷,提出基于路网局部索引机制的保护位置隐私路网近邻查询方法.查询客户端通过与LBS服务器的一轮通信获取局部路网信息,生成查询位置所在路段满足l-路段多样性的匿名查询序列,并将匿名查询序列提交LBS服务器,从而避免保护位置隐私查询对可信第三方服务器的依赖.在LBS服务器端,提出基于路网基本单元划分的分段式近邻查询处理策略,对频繁查询请求路网基本单元,构建基于路网泰森多边形和R^*树的局部Vor-R^*索引结构,实现基于索引的快速查找.对非频繁请求路网基本单元,采用常规路网扩张查询处理.有效降低索引存储规模和基于全局索引进行无差异近邻查询的访问代价,在保证查询结果正确的同时,提高了LBS服务器端k近邻查询处理效率.理论分析和实验结果表明,所提方法在兼顾查询准确性的同时,有效地提高了查询处理效率.     

道路网中的移动对象连续K近邻查询

已有道路网中的连续k近邻查询处理算法采用增量式的查询处理机制,当数据频繁更新时性能急剧下降.结合多核多线程技术,提出了一种基于多线程的连续查询处理框架.该框架周期性重计算所有查询结果,将查询处理分为顺序执行的数据更新阶段和查询执行阶段,分别使用任务并行和数据并行的方法执行各阶段的操作.设计了数据更新阶段使用的数据结构,提出了查询处理阶段的k近邻查询处理策略,包含离线预计算和在线k近邻查询处理算法两个部分.对k近邻算法复杂性及多线程处理框架的加速比进行了理论分析.实验结果表明,提出的算法在数据频繁更新下,串行执行时性能优于已有算法,而基于多线程处理框架的并行执行在任何参数配置下性能均优于已有算法;且基于多线程处理框架的并行执行具有较好的性能扩展性,加速比可以达到1.51～1.7.     

基于k近邻隔离森林的异常检测

异常检测是机器学习与数据挖掘的热点研究领域之一, 主要应用于故障诊断、入侵检测、欺诈检测等领域. 当前已有很多有效的相关研究工作, 特别是基于隔离森林的异常检测方法, 但在处理高维数据时仍然存在许多困难. 提出了一种新的k近邻隔离森林的异常检算法: k-nearest neighbor based isolation forest (KNIF). 该方法采用超球体作为隔离工具, 利用第k近邻的方法来构建隔离森林, 并构建基于距离的异常值计算方法. 通过充分实验表明KNIF方法能有效地进行复杂分布环境下的异常检测, 并能适应不同分布形式的应用场景.     

面向不确定移动对象的连续K近邻查询算法*

近年来,位置服务等领域急需解决的一个难点问题是不确定移动对象连续K近邻查询.基于此情况,文中提出高效的面向不确定移动对象的连续K近邻查询算法.首先提出2种预测移动对象可能区域算法MaxMin与Rate,利用最近一段时间窗口内的位置采样、速度和方向预测移动对象在查询时刻到未来I区间可能的位置区域.同时使用最小距离与最大距离区间描述移动对象到查询对象的距离.然后采用优化的基于模糊可能度判定的排序方法查找查询对象的K近邻.最后在真实和合成的大规模移动对象数据集上验证文中方法的有效性.     

基于图压缩的k可达查询处理

研究了基于图压缩的k可达查询处理,提出了一种支持k可达查询的图压缩算法k-RPC及无需解压缩的查询处理算法,k-RPC算法在所有基于等价类的支持k-reach查询的图压缩算法中是最优的.由于k-RPC算法是基于严格的等价关系,因此进一步又提出了线性时间的近似图压缩算法k-GRPC.k-GRPC算法允许从原始图中删除部分边,然后使用k-RPC获得更好的压缩比.提出了线性时间的无需解压缩的查询处理算法.真实数据上的实验结果表明,对于稀疏的原始图,两种压缩算法的压缩比分别可以达到45%,对于稠密的原始图,两种压缩算法的压缩比分别可以达到75%和67%;与在原始图上直接进行查询处理相比,两种基于压缩图的查询处理算法效率更好,在稀疏图上的查询效率可以提高2.5倍.     

面向时间依赖路网的连续k近邻查询

连续k近邻查询(continuous k-nearest neighor,Ck NN)定义为查找指定路径上每个点的k个最小代价数据对象。目前关于Ck NN的研究都是在欧式空间与静态路网中实现的,这些算法不能直接应用到边权值变化的时间依赖路网中。定义并解决了时间依赖路网中的Ck NN问题,利用积分的性质以及通过对权值代价函数合并的方式提出了两阶段的基于分割点的Ck NN查询算法。过滤阶段提出了计算节点到达时间的方法,再利用到达时间查询出多个候选k近邻结果;求精阶段将查询点到候选结果的权值函数合并,通过计算函数交点得到分割点,进而为查询返回若干个分割点以及相应区间内的k近邻结果。实验结果表明,与进行多次快照k近邻查询相比,所提算法在响应时间上减少了近一个数量级。     

高度动态环境下移动对象连续K近邻查询算法

针对面向高度动态移动对象集的多用户连续K近部查询,提出了基于查询索引的多用户连续K近邻查询处理(Query Index based Multiple Continuous K-Nearest Neighbor Queries, QI-MCKNN)算法,阐述了查询索引的概念和构建方法,分析了格网大小对查询性能的影响,给出了相应的查询处理算法。实验表明,算法在面对高度动态的移动对象集时,查询处理性能优于基于移动对象格网索引的SEA-CNN算法。     

Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity

One of the most important queries in spatio-temporal databases that aim at managing moving objects efficiently is the continuous K-nearest neighbor (CKNN) query. A CKNN query is to retrieve the K-nearest neighbors (KNNs) of a moving user at each time instant within a user-given time interval [t _s , t _e ]. In this paper, we investigate how to process a CKNN query efficiently. Different from the previous related works, our work relieves the past assumption, that an object moves with a fixed velocity, by allowing that the velocity of the object can vary within a known range. Due to the introduction of this uncertainty on the velocity of each object, processing a CKNN query becomes much more complicated. We will discuss the complications incurred by this uncertainty and propose a cost-effective P² KNN algorithm to find the objects that could be the KNNs at each time instant within the given query time interval. Besides, a probability-based model is designed to quantify the possibility of each object being one of the KNNs. Comprehensive experiments demonstrate the efficiency and the effectiveness of the proposed approach.

移动对象的连续最近邻查询算法

介绍了一种索引结构———TPR树和静态环境中基本的最近邻查询算法,并提出了影响时间这一概念,将其运用到最近邻查询算法中,可以完成移动对象的连续最近邻查询。     

可伸缩的增量连续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查询处理,具有良好的实用价值.     

道路网中的移动对象连续范围查询

研究了采用网络距离的道路网上移动对象连续多范围查询处理技术。设计了道路网、移动对象和查询数据在内存中存储的数据模型。基于该数据模型提出了两种道路网上的移动对象连续多范围查询处理算法。其中,增量式范围查询算法(incremental range query algorithm,IRQA)通过使用扩张树和影响列表结构减少查询的重新计算;组范围查询算法(group range query algorithm,GRQA)利用同一路径上多查询的结果具有相关性这一特点减少查询的重新计算。实验结果表明GRQA算法在查询分布比较集中时性能较优,IRQA算法在查询均匀分布时性能较优,此外,两种算法均优于重新计算所有查询结果的原始算法。     

移动对象历史轨迹的连续最近邻查询算法

提出一种直接在原始时空坐标系下对一维移动对象的历史轨迹进行连续最近邻查询的算法,给出相关的定义与定理,通过分析轨迹之间的交点及轨迹线段单调性等特征,利用以前所求得的最近邻结果信息进行连续最近邻的查询判断。实验结果与分析表明,该算法具有较好的性能。     

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.     

Indexing Fast Moving Objects for kNN Queries Based on Nearest Landmarks

With the rapid advancements in positioning technologies such as the Global Positioning System (GPS) and wireless communications, the tracking of continuously moving objects has become more convenient. However, this development poses new challenges to database technology since maintaining up-to-date information regarding the location of moving objects incurs an enormous amount of updates. Existing indexes can no longer keep up with the high update rate while providing speedy retrieval at the same time. This study aims to improve k nearest neighbor (kNN) query performance while reducing update costs. Our approach is based on an important observation that queries usually occur around certain places or spatial landmarks of interest, called reference points. We propose the Reference-Point-based tree (RP-tree), which is a two-layer index structure that indexes moving objects according to reference points. Experimental results show that the RP-tree achieves significant improvement over the TPR-tree.