基于不确定数据的top-k概率相互最近邻查询*

不确定数据上的概率相互最近邻查询具有重要的实际应用,针对目前关于这方面的研究尚少,提出了不确定数据上的概率相互最近邻的top-k查询算法。首先对问题进行描述与定义,其次总结可行的裁剪规则,从而裁剪查询对象中未计算的实例点。通过实验表明,该算法能有效地降低最近邻查询中的I/O开销,提高查询的响应速度。     

移动对象反向最近邻查询处理技术研究进展

随着移动通信技术的快速发展和个人移动通信终端功能的不断完善,移动计算技术有了更加广阔的应用背景,尤其是移动对象的反向最近邻查询处理技术得到了研究人员的广泛关注。对近几年提出的移动对象反向最近邻查询方法进行了研究,根据其查询处理过程,将反向最近邻查询方法分为基于预处理的方法和基于空间修剪的方法;总结了近年来提出的有效解决方法和研究进展,最后介绍了移动对象反向最近邻查询处理技术的最新发展趋势。     

基于Voronoi图及其对偶图的反最近邻查询

最近邻查询是地理信息系统领域经常遇到的问题,而反最近邻查询是在最近邻查询的基础上提出的一种新的查询类型。在分析利用Voronoi图进行最近邻查询的基础上,提出了基于Voronoi图及其对偶图Delaunay图的反最近邻查询,大大缩小了在海量空间数据库中进行反最近邻查询的查询范围。     

基于道路网的连续k近邻查询算法

针对增量式监测算法(IMA)的冗余搜索问题,提出一种基于IMA改进的移动对象连续k近邻(Continuous k Nearest Neighbor, CkNN)查询处理新算法。采用增量式查询处理机制;利用距离相近的查询其查询结果大部分相同这一特性,在以查询点为中心进行网络扩展之前,首先执行一个预处理过程,分析相近的其他查询的扩展树,并重用其中的有效部分,从而避免了对道路网的盲目扩展;且在节点的网络扩展中,通过应用具有相同扩展方向的其他查询的扩展结果,不仅减少了对道路网的重复扩展,还节省了计算代价。实验结果表明,所提算法同传统算法相比较, 缩短了查询响应时间,提高了运行效率,并且适用于不同类型的k近邻查询。     

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

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

Self-monitoring query execution for adaptive query processing

Adaptive query processing generally involves a feedback loop comprising monitoring, assessment and response. So far, individual proposals have tended to group together an approach to monitoring, a means of assessment, and a form of response. However, there are many benefits in decoupling these three phases, and in constructing generic frameworks for each of them. To this end, this paper discusses monitoring of query plan execution as a topic in its own right, and advocates an approach based on self-monitoring algebraic operators. This approach is shown to be generic and independent of any specific adaptation mechanism, easily implementable and portable, sufficiently comprehensive, appropriate for heterogeneous distributed environments, and more importantly, capable of driving on-the-fly adaptations of query plan execution. An experimental evaluation of the overheads and of the quality of the results obtained by monitoring is also presented.     

Locally nearest neighbor classifiers for pattern classification

In this paper, two novel classifiers based on locally nearest neighborhood rule, called nearest neighbor line and nearest neighbor plane, are presented for pattern classification. Comparison to nearest feature line and nearest feature plane, the proposed methods take much lower computation cost and achieve competitive performance.     

Round-Eye: A system for tracking nearest surrounders in moving object environments

This paper presents “Round-Eye”, a system for tracking nearest surrounding objects (or nearest surrounders) in moving object environments. This system provides a platform for surveillance applications. The core part of this system is continuous nearest surrounder (NS) query that maintains views of the nearest objects at distinct angles from query points. This query differs from conventional spatial queries such as range queries and nearest neighbor queries as NS query considers both distance and angular aspects of objects with respect to a query point at the same time. In our system framework, a centralized server is dedicated (1) to collect location updates of both objects and queries, (2) to determine which NS queries are invalidated in presence of object/query location changes and corresponding result changes if any, and (3) to refresh the affected query answers. To enhance the system performance in terms of processing time and network bandwidth consumption, we propose various techniques, namely, safe region, partial query reevaluation, and incremental query result update. Through simulations, we evaluate our system with the proposed techniques over a wide range of settings.     

Efficient skyline query processing in wireless sensor networks

How to process a skyline query efficiently has received considerable attention in recent years. A skyline query identifies a set of non-dominated data records in a multidimensional dataset. Whereas most previous studies have resolved this problem in a centralized environment, this work considers it in a distributed sensor network environment. An algorithm, known as Skyline Sensor Algorithm (SkySensor), is presented to efficiently retrieve skyline results from a sensor network. A cluster-based architecture is designed in SkySensor to collect all sensor readings. A pruning method is then proposed to progressively sift out the skyline results from the sensor network. SkySensor avoids the need of collecting data from all sensors in the network, which is an extremely expensive action, when searching for the skyline results. The performance study indicates that SkySensor is highly efficient, and significantly outperforms previous methods in processing skyline queries.     

空间对象的反最近邻查询处理技术研究

空间数据库中反最近邻查询的研究是空间查询的研究热点。在对现有的反最近邻查询技术进行分析比较的基础上,针对提高动态数据集的查询效率问题,给出了基于R树索引结构的反最近邻查询方案。通过实验结果的分析比较,可以看出该方案能够有效地解决动态数据集的查询问题。     

基于查询集空间分布的聚合最近邻查询算法

聚合最近邻查询涉及到多个查询对象,因此比传统最近邻查询更复杂,而且其查询集空间分布特征暗含了查询集聚合最近邻的区域分布信息。充分考虑查询集分布特征,给出了利用分布特征指导聚合最近邻搜索的方法,并以此提出了一种新的聚合最近邻查询算法——AM算法。AM算法能动态地捕捉并利用查询集空间分布特征,使得对数据点的搜索按正确的次序进行,避免对不必要数据点的搜索。最后通过实验验证了AM算法的高效性。     

基于差分隐私的社交网络位置近邻查询方法

针对社交网络中近邻位置查询时个人位置隐私泄漏的问题,采用地理不可区分性机制对位置数据添加随机噪声,提出了一种隐私预算分配方法。首先,对空间区域进行网格化分割,根据用户在不同区域的位置访问量来个性化分配隐私预算;然后,为了解决在扰动位置数据集中近邻查询命中率偏低的问题,提出了一种组合增量近邻查询（CINQ）算法,以扩大需求空间的检索范围,并利用组合查询过滤冗余数据。在仿真实验中,与SpaceTwist算法相比,CINQ算法的查询命中率提高了13.7个百分点。实验结果表明,CINQ算法有效解决了因为查询目标的位置扰动所带来的查询命中率偏低问题,适用于社交网络应用中扰动位置的近邻查询。     

距离-关键字相似度约束的双色反k近邻查询方法

针对空间关键字双色反k近邻查询返回结果质量较低的问题,提出了基于距离-关键字相似度约束的双色反k近邻查询方法.首先,通过设置一个阈值将查询结果中质量较低的用户给过滤掉,从而避免了查询结果中出现空间距离相对较远的用户,保证了查询结果质量;然后,为支持该查询,提出了一种关键字多分辨率网格矩形树(KMG-Tree)索引来管理...     

An adaptable distributed query processing architecture

Traditionally, distributed query optimization techniques generate static query plans at compile time. However, the optimality of these plans depends on many parameters (such as the selectivities of operations, the transmission speeds and workloads of servers) that are not only difficult to estimate but are also often unpredictable and fluctuant at runtime. As the query processor cannot dynamically adjust the plans at runtime, the system performance is often less than satisfactory. In this paper, we introduce a new highly adaptive distributed query processing architecture. Our architecture can quickly detect fluctuations in selectivities of operations, as well as transmission speeds and workloads of servers, and accordingly change the operation order of a distributed query plan during execution. We have implemented a prototype based on the Telegraph system [Telegragraph project. Available from >]. Our experimental study shows that our mechanism can adapt itself to the changes in the environment and hence approach to an optimal plan during execution.     

Decomposable algorithms for nearest neighbor computing

Privacy and security concerns can prevent sharing of data, derailing many data projects. Distributed knowledge computing, if done correctly, can alleviate this problem. The key is to obtain valid results, while providing guarantees on the (non)disclosure of data. In the present study, two novel algorithms have been developed to find the nearest neighbor from known points, and a pair of nearest neighbors in a given set data points in d$d$-dimensional space in distributed databases. These algorithms preserve the privacy and security of the data at individual sites by requiring transmission of only minimal information to other sites.     

基于概率的反向K最近邻高效查询算法研究

反向K最近邻查询需要确定以给定查询对象作为其k个最近邻之一的所有对象。然而由于大量应用需要处理未知数据,人们迫切需要能够处理未知对象的新算法。这里的主要问题是,一个对象属于RKNN结果集的事件不再是一个确定性事件,而是一个以一定概率成立的随机变量。对基于概率论的未知数据集反向K最近邻(PRKNN)搜索问题展开研究,以足够大的概率返回以查询对象为其最近邻的未知对象。基于一种新的考虑了距离相关性的修剪机制,提出一种PRNN高效查询算法。此外,还给出了如何将该算法扩展至PRKNN(其中k>1)查询处理。最后,将该算法与当前其他最新算法作比较,实验评估结果表明,该算法性能明显优于其他算法。     

基于位置语义的增量近邻隐私保护研究

针对LBS查询服务中构造的匿名区或选取的锚点仍位于敏感区域而导致的位置隐私泄露问题,提出一种基于位置语义的增量近邻隐私保护方法。该方法在客户端/服务器体系架构下,先根据用户的位置隐私需求计算语义安全匿名区,保护用户位置隐私;再筛选语义安全匿名区中道路交叉点作为语义安全锚点,保证了选取锚点是真实存在的,且其语义安全性达到最大;最终客户端以锚点位置请求服务并获取查询结果。实验结果表明,该方法能够较好地保护用户位置的隐私,且查询准确率较高约90%,查询时间较低约60 ms。