期刊文献+
共找到242篇文章
< 1 2 13 >
每页显示 20 50 100
Directional nearest neighbor query method for specified geographical direction space based on Voronoi diagram 被引量:3
1
作者 LI Song SONG Shuang +1 位作者 HAO Xiaohong ZHANG Liping 《High Technology Letters》 EI CAS 2022年第2期122-133,共12页
The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional ne... The existing nearest neighbor query methods cannot directly perform the nearest neighbor query of specified geographical direction space.In order to compensate the shortcomings of the existing methods,a directional nearest neighbor query method in specific direction space based on Voronoi diagram is put forward.This work studies two cases,i.e.the query point is static and the query point moves with a constant velocity.Under the static condition,the corresponding pruning method and the pruning algorithm of the specified direction nearest neighbor(pruning_SDNN algorithm)are proposed by combining the plane right-angle coordinate system with the north-west direction,and then according to the smallest external rectangle of Voronoi polygon,the specific query is made and the direction nearest neighbor query based on Voronoi rectangle(VR-DNN) algorithm is given.In the case of moving with a constant velocity,first of all,the combination of plane right angle coordinate system,geographical direction and circle are used,the query range is determined and pruning methods and the pruning algorithm of the direction nearest neighbor based on decision circle(pruning_DDNN algorithm) are put forward.Then,according to the different position of motion trajectory and Voronoi diagram,a specific query through the nature of Voronoi diagram is given.At last,the direction nearest neighbor query based on Voronoi diagram and motion trajectory(VM-DNN) algorithm is put forward.The theoretical research and experiments show that the proposed algorithm can effectively deal with the problem of the nearest neighbor query for a specified geographical direction space. 展开更多
关键词 nearest neighbor query direction Voronoi diagram rectangular plane coordinate system
下载PDF
基于不规则区域划分方法的k-Nearest Neighbor查询算法 被引量:1
2
作者 张清清 李长云 +3 位作者 李旭 周玲芳 胡淑新 邹豪杰 《计算机系统应用》 2015年第9期186-190,共5页
随着越来越多的数据累积,对数据处理能力和分析能力的要求也越来越高.传统k-Nearest Neighbor(k NN)查询算法由于其容易导致计算负载整体不均衡的规则区域划分方法及其单个进程或单台计算机运行环境的较低数据处理能力.本文提出并详细... 随着越来越多的数据累积,对数据处理能力和分析能力的要求也越来越高.传统k-Nearest Neighbor(k NN)查询算法由于其容易导致计算负载整体不均衡的规则区域划分方法及其单个进程或单台计算机运行环境的较低数据处理能力.本文提出并详细介绍了一种基于不规则区域划分方法的改进型k NN查询算法,并利用对大规模数据集进行分布式并行计算的模型Map Reduce对该算法加以实现.实验结果与分析表明,Map Reduce框架下基于不规则区域划分方法的k NN查询算法可以获得较高的数据处理效率,并可以较好的支持大数据环境下数据的高效查询. 展开更多
关键词 k-nearest neighbor(k NN)查询算法 不规则区域划分方法 MAP REDUCE 大数据
下载PDF
A nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix
3
作者 李文法 Wang Gongming +1 位作者 Ma Nan Liu Hongzhe 《High Technology Letters》 EI CAS 2016年第3期241-247,共7页
Problems existin similarity measurement and index tree construction which affect the performance of nearest neighbor search of high-dimensional data. The equidistance problem is solved using NPsim function to calculat... Problems existin similarity measurement and index tree construction which affect the performance of nearest neighbor search of high-dimensional data. The equidistance problem is solved using NPsim function to calculate similarity. And a sequential NPsim matrix is built to improve indexing performance. To sum up the above innovations,a nearest neighbor search algorithm of high-dimensional data based on sequential NPsim matrix is proposed in comparison with the nearest neighbor search algorithms based on KD-tree or SR-tree on Munsell spectral data set. Experimental results show that the proposed algorithm similarity is better than that of other algorithms and searching speed is more than thousands times of others. In addition,the slow construction speed of sequential NPsim matrix can be increased by using parallel computing. 展开更多
关键词 nearest neighbor search high-dimensional data SIMILARITY indexing tree NPsim kd-tree SR-tree Munsell
下载PDF
基于容忍因子的近似最近邻混合查询算法 被引量:1
4
作者 贺广福 薛源海 +3 位作者 陈翠婷 俞晓明 刘欣然 程学旗 《大数据》 2024年第1期17-34,共18页
近似最近邻搜索(ANNS)是计算机领域中一种重要的高效相似度搜索技术,可用于在大规模数据集中进行快速信息检索。随着人们对高精度信息检索的需求不断增长,同时使用结构化信息和非结构化信息进行混合查询的方式也得到了广泛应用。然而,... 近似最近邻搜索(ANNS)是计算机领域中一种重要的高效相似度搜索技术,可用于在大规模数据集中进行快速信息检索。随着人们对高精度信息检索的需求不断增长,同时使用结构化信息和非结构化信息进行混合查询的方式也得到了广泛应用。然而,基于近邻图的过滤贪心算法在混合查询时可能会因结构化约束条件的影响导致连通性降低,进而损害搜索精度。为此,提出了一种基于容忍因子的过滤贪心算法,通过容忍因子控制不满足结构化约束条件的顶点参与路由,在不改变索引结构的前提下维持原有近邻图的连通性,克服了结构化约束条件对检索精度的负面影响。实验结果证明,新算法可以在不同结构化约束强度下实现ANNS的高精度搜索,同时保持检索效率。该研究解决了基于近邻图的ANNS在混合查询场景中的问题,为大规模数据集的快速混合查询信息检索提供了一种有效的解决方案。 展开更多
关键词 混合查询 向量检索 最近邻搜索 过滤搜索
下载PDF
APPROXIMATE QUERY AND CALCULATION OF RNN_k BASED ON VORONOI CELL 被引量:1
5
作者 郝忠孝 李博涵 《Transactions of Nanjing University of Aeronautics and Astronautics》 EI 2009年第2期154-161,共8页
Reverse k nearest neighbor (RNNk) is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data po... Reverse k nearest neighbor (RNNk) is a generalization of the reverse nearest neighbor problem and receives increasing attention recently in the spatial data index and query. RNNk query is to retrieve all the data points which use a query point as one of their k nearest neighbors. To answer the RNNk of queries efficiently, the properties of the Voronoi cell and the space-dividing regions are applied. The RNNk of the given point can be found without computing its nearest neighbors every time by using the rank Voronoi cell. With the elementary RNNk query result, the candidate data points of reverse nearest neighbors can he further limited by the approximation with sweepline and the partial extension of query region Q. The approximate minimum average distance (AMAD) can be calculated by the approximate RNNk without the restriction of k. Experimental results indicate the efficiency and the effectiveness of the algorithm and the approximate method in three varied data distribution spaces. The approximate query and the calculation method with the high precision and the accurate recall are obtained by filtrating data and pruning the search space. 展开更多
关键词 computational geometry approximation query filtrating reverse k nearest neighbor (RNNk) Voronoi cell
下载PDF
支持均匀缩放的不等长时间子序列查询方法
6
作者 熊浩然 何震瀛 《计算机工程》 CSCD 北大核心 2024年第1期60-67,共8页
作为时序数据分析中的基础技术之一,时间序列的子序列查询旨在寻找与目标序列相似的子序列。现有的子序列查询方法大多仅支持查询与目标序列长度相同的子序列,因而均匀缩放技术常被用于解决子序列查询中的不等长问题。但现有支持均匀缩... 作为时序数据分析中的基础技术之一,时间序列的子序列查询旨在寻找与目标序列相似的子序列。现有的子序列查询方法大多仅支持查询与目标序列长度相同的子序列,因而均匀缩放技术常被用于解决子序列查询中的不等长问题。但现有支持均匀缩放的子序列查询技术大多未考虑子序列的Z-标准化,且对查询效率仍有改善的空间。针对该问题,提出一种基于索引技术且支持均匀缩放的子序列查询方法。结合现有索引方法 ULISSE提供的树状数据结构,设计可保证非漏报的下界距离,为索引结构的剪枝提供理论保证,并利用索引中存储的元数据,提出精确K-近邻查询算法。所提方法适用于非归一化和归一化两种场景。实验结果表明,较UCR-US和ULISSE基线方法,该基于索引的不等长子序列查询方法在CAP、GAP两个真实数据集以及随机游走人工合成数据集上均实现了查询效率的显著提升,针对在非归一化和归一化两种场景下的不等长子序列查询,该方法的平均效率提升分别为2.33和2.51倍。 展开更多
关键词 时间序列 子序列查询 均匀缩放 索引 下界距离 K-近邻
下载PDF
保护两方隐私的多类型的路网K近邻查询方案
7
作者 曾聪爱 刘亚丽 +2 位作者 陈书仪 朱秀萍 宁建廷 《计算机科学》 CSCD 北大核心 2024年第11期400-417,共18页
在车联网场景中,现有基于位置服务的隐私保护方案存在不支持多种类型K近邻兴趣点的并行查询、难以同时保护车辆用户和位置服务提供商(Location-Based Service Provider,LBSP)两方隐私、无法抵抗恶意攻击等问题。为了解决上述问题,提出... 在车联网场景中,现有基于位置服务的隐私保护方案存在不支持多种类型K近邻兴趣点的并行查询、难以同时保护车辆用户和位置服务提供商(Location-Based Service Provider,LBSP)两方隐私、无法抵抗恶意攻击等问题。为了解决上述问题,提出了一种保护两方隐私的多类型的路网K近邻查询方案MTKNN-MPP。将改进的k-out-of-n不经意传输协议应用于K近邻查询方案中,实现了在保护车辆用户的查询内容隐私和LBSP的兴趣点信息隐私的同时,一次查询多种类型K近邻兴趣点。通过增设车载单元缓存机制,降低了计算代价和通信开销。安全性分析表明,MTKNN-MPP方案能够有效地保护车辆用户的位置隐私、查询内容隐私以及LBSP的兴趣点信息隐私,可以保证车辆的匿名性,能够抵抗合谋攻击、重放攻击、推断攻击、中间人攻击等恶意攻击。性能评估表明,与现有典型的K近邻查询方案相比,MTKNN-MPP方案具有更高的安全性,且在单一类型K近邻查询和多种类型K近邻查询中,查询延迟分别降低了43.23%~93.70%,81.07%~93.93%。 展开更多
关键词 基于位置的服务 两方隐私保护 K近邻查询 不经意传输协议 车联网 多类型
下载PDF
一种基于数据空间自适应规则网格划分的Skd-tree最近邻算法 被引量:1
8
作者 王荣秀 王波 《重庆理工大学学报(自然科学)》 CAS 北大核心 2021年第6期147-155,共9页
针对现有kd-tree KNN算法的不足,提出了一种基于规则数据空间网格划分的Skdtree KNN算法。该树形结构把数据置于空间网格内部,能更好地利用数据的空间分布特性,可以在更小的范围内对被查询数据定位,有效避免对部分无关数据的计算或回溯... 针对现有kd-tree KNN算法的不足,提出了一种基于规则数据空间网格划分的Skdtree KNN算法。该树形结构把数据置于空间网格内部,能更好地利用数据的空间分布特性,可以在更小的范围内对被查询数据定位,有效避免对部分无关数据的计算或回溯;同时,为了适应网格空间的规则性,算法中采用了超方体而非超球体来查询局域空间中的最优结果,避免了空间异构带来的缺点。数字实验的结果证明:Skd-tree KNN比kd-tree KNN具备更好的索引定位精度、更少的无关数据回溯和计算、更短的查询时间,尤其适用于数据样本较大或高维度数据的最近邻查询。 展开更多
关键词 最近邻算法 数据索引 Skd-tree KNN 查询超体
下载PDF
面向动态路网的移动对象分布式k近邻查询算法
9
作者 陈国祥 于自强 赵浩宇 《计算机应用》 CSCD 北大核心 2024年第11期3403-3410,共8页
动态路网k近邻(kNN)查询是许多基于位置的服务(LBS)中的一个重要问题。针对该问题,提出一种面向动态路网的移动对象分布式kNN查询算法DkNN(Distributed kNN)。首先,将整个路网划分为部署于集群中不同节点中的多个子图;其次,通过并行地... 动态路网k近邻(kNN)查询是许多基于位置的服务(LBS)中的一个重要问题。针对该问题,提出一种面向动态路网的移动对象分布式kNN查询算法DkNN(Distributed kNN)。首先,将整个路网划分为部署于集群中不同节点中的多个子图;其次,通过并行地搜索查询范围所涉及的子图得到精确的kNN结果;最后,优化查询的搜索过程,引入查询范围剪枝策略和查询终止策略。在4个道路网络数据集上与3种基线算法进行了充分对比和验证。实验结果显示,与TEN~*-Index(Tree dEcomposition based kNN~*Index)算法相比,DkNN算法的查询时间减少了56.8%,路网更新时间降低了3个数量级。DkNN算法可以快速响应动态路网中的kNN查询请求,且在处理路网更新时具有较低的更新成本。 展开更多
关键词 动态道路网络 K近邻查询 分布式环境 基于位置的服务 时空数据处理
下载PDF
基于改进Kd-Tree构建算法的k近邻查询 被引量:8
10
作者 陈晓康 刘竹松 《广东工业大学学报》 CAS 2014年第3期119-123,共5页
k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率.但是,传统的Kd-Tree构建有两个缺点:使用测试数据点进行k近邻查询每次都需要... k近邻查询算法是查询大规模空间数据的常用算法之一,使用Kd-Tree先构建大规模空间数据的索引,然后对搜索空间进行层次划分,再进行k近邻查询,能保证搜索的效率.但是,传统的Kd-Tree构建有两个缺点:使用测试数据点进行k近邻查询每次都需要回溯到根节点,影响了查询的效率;Kd-Tree使用split域对空间进行层次划分,空间划分为立方体(二维数据表现为矩形),多边形空间在相交判断时会出现没必要进行数据距离比较的多余空间,这样会影响查询的效率.针对这两个缺点,本文提出了相应的改进算法——RB算法.实验结果证明,该算法比传统的KD算法拥有更高的查询效率.本文的主要贡献有两点:(1)构建一种快速创建Kd-Tree索引来支持KNN算法进行大规模数据的分类查询操作.(2)改进传统的Kd-Tree索引构建方法,提出新的改进算法RB算法,提高KNN算法查询的效率. 展开更多
关键词 K近邻查询 KD树 空间数据 多边形空间 层次划分
下载PDF
Monitoring Median Queries over Moving Objects
11
作者 许浒 卢炎生 李支成 《Journal of Southwest Jiaotong University(English Edition)》 2010年第4期326-332,共7页
The k-median problem has attracted a number of researchers. However,few of them have considered both the dynamic environment and the issue of accuracy. In this paper,a new type of query is studied,called continuous me... The k-median problem has attracted a number of researchers. However,few of them have considered both the dynamic environment and the issue of accuracy. In this paper,a new type of query is studied,called continuous median monitoring (CMM) query. It considers the k-median problem under dynamic environment with an accuracy guarantee. A continuous group nearest neighbor based (CGB) algorithm and an average distance medoid (ADM) algorithm are proposed to solve the CMM problem. ADM is a hill climbing schemed algorithm and achieves a rapid converging speed by checking only qualified candidates. Experiments show that ADM is more efficient than CGB and outperforms the classical PAM (partitioning around medoids) and CLARANS (clustering large applications based on randomized search) algorithms with various parameter settings. 展开更多
关键词 Spatial databases query processing nearest neighbor query k-Median problem
下载PDF
A Parallel Processing Method for Moving Top-K Spatial Keyword Query
12
作者 Kunlun Chen Yanru Liu Qingxu Deng 《Journal of Software Engineering and Applications》 2019年第4期72-84,共13页
We propose an influential set based moving k keyword query processing model, which avoids the shortcoming of safe region-based approaches that the update cost and update frequency cannot be optimized simultaneously. B... We propose an influential set based moving k keyword query processing model, which avoids the shortcoming of safe region-based approaches that the update cost and update frequency cannot be optimized simultaneously. Based on the model, we design a parallel query processing method and a parallel validation method for multicore processing platforms. The time complexity of the algorithms is O((log|D|+p.k)/p.k)?and O(log p.k), respectively, which are all O(1/k) times the time complexity of the state-of-the-art method. The experiment result confirms the superiority of our algorithms over the state-of-the-art method. 展开更多
关键词 SPATIAL KEYWORDS K nearest neighborS Influential Set SPATIAL MOVING query Safe Region
下载PDF
基于服务相似性的隐私保护k近邻查询方法 被引量:2
13
作者 张学军 李佳乐 +4 位作者 杨依行 黄海燕 许陈 李桢 杜晓刚 《兰州交通大学学报》 CAS 2023年第1期44-53,61,共11页
如何同时保护用户的位置和查询隐私而又不妨碍服务质量和增加系统处理开销是当前位置服务隐私保护系统面临的一个重要挑战.为了解决这一挑战,基于位置查询的服务相似特性和Paillier密码系统的同态特性,提出了一种能同时保护位置隐私和... 如何同时保护用户的位置和查询隐私而又不妨碍服务质量和增加系统处理开销是当前位置服务隐私保护系统面临的一个重要挑战.为了解决这一挑战,基于位置查询的服务相似特性和Paillier密码系统的同态特性,提出了一种能同时保护位置隐私和查询隐私的k近邻查询方法,实现不依赖可信第三方便可实现用户位置和查询内容的隐私保护以及兴趣点的精确查询;同时,通过构造服务相似地图生成扰动位置,解决已有方法查询处理开销大的问题,并保证查询结果的准确性.利用真实数据集从查询准确性和系统开销等方面对所提方法进行了实验验证.实验结果与安全性分析表明:和已有方法相比,所提出的方法在兼顾位置和查询隐私保护的同时,有效地保证了服务质量,降低了系统处理开销. 展开更多
关键词 服务相似性 位置隐私 查询隐私 同态加密 K近邻查询
下载PDF
面向移动对象连续k近邻查询的双层索引结构 被引量:1
14
作者 韩士元 何清 +2 位作者 于自强 童向荣 郑渤龙 《软件学报》 EI CSCD 北大核心 2023年第6期2789-2803,共15页
移动对象连续k近邻(CKNN)查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及... 移动对象连续k近邻(CKNN)查询是指给定一个连续移动的对象集合,对于任意一个k近邻查询q,实时计算查询q的k近邻并在查询有效时间内对查询结果进行实时更新.现实生活中,交通出行、社交网络、电子商务等领域许多基于位置的应用服务都涉及移动对象连续k近邻查询这一基础问题.已有研究工作解决连续k近邻查询问题时,大多需要通过多次迭代确定一个包含k近邻的查询范围,而每次迭代需要根据移动对象的位置计算当前查询范围内移动对象的数量,整个迭代过程的计算代价占查询代价的很大部分.为此,提出了一种基于网络索引和混合高斯函数移动对象分布密度的双重索引结构(grid GMM index,GGI),并设计了移动对象连续k近邻增量查询算法(incremental search for continuous k nearest neighbors,IS-CKNN).GGI索引结构的底层采用网格索引对海量移动对象进行维护,上层构建混合高斯模型模拟移动对象在二维空间中的分布.对于给定的k近邻查询q,IS-CKNN算法能够基于混合高斯模型直接确定一个包含q的k近邻的查询区域,减少了已有算法求解该区域的多次迭代过程;当移动对象和查询q位置发生变化时,进一步提出一种高效的增量查询策略,能够最大限度地利用已有查询结果减少当前查询的计算量.最后,在滴滴成都网约车数据集以及两个模拟数据集上进行大量实验,充分验证了算法的性能. 展开更多
关键词 移动对象 连续k近邻查询(CKNN) 增量查询算法
下载PDF
加权路网空间中动态聚集最近邻居查询算法
15
作者 陈方疏 张为 +3 位作者 胡小明 张宇飞 孟宪凯 石林祥 《计算机应用》 CSCD 北大核心 2023年第7期2026-2033,共8页
聚集最近邻居(ANN)查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足:缺少针对大规模动态路网数... 聚集最近邻居(ANN)查询作为空间数据库的经典问题在网络链路结构优化、物流集散点选址、共享汽车服务等方面有着重要的意义,能有效促进物流、移动互联网行业以及运筹学等领域的发展。现有的研究存在如下不足:缺少针对大规模动态路网数据的高效索引结构,在数据点位置实时移动以及路网权重动态更新的场景下算法的查询效率较低。针对上述不足,提出动态场景下的ANN查询算法。首先利用G-tree作为路网索引,提出将四叉树和k-d树等空间索引结构与增量欧氏空间限制(IER)算法结合起来的剪枝方法,以完成静态空间下的ANN查询;随后针对动态场景下数据点位置频繁更新的问题,加入时间窗口及安全区域更新策略,以减少算法的重复计算次数,实验结果表明效率能提高8%~85%;最后针对路网权重变化的ANN查询问题,提出两个基于校正的连续查询方法,在历史查询结果的基础上,根据权重变化的增量来得到当前的查询结果,在某些场景中能够有效降低50%左右的误差。理论研究和实验结果表明,所提算法能够高效并且较为准确地解决动态场景下的ANN查询问题。 展开更多
关键词 聚集最近邻居查询 路网 加权空间 动态查询 空间索引
下载PDF
k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks 被引量:7
16
作者 Hyeong-Il Kim Jae-Woo Chang 《Journal of Computer Science & Technology》 SCIE EI CSCD 2013年第4期585-596,共12页
Recent development of wireless communication technologies and the popularity of smart phones .are making location-based services (LBS) popular. However, requesting queries to LBS servers with users' exact locations... Recent development of wireless communication technologies and the popularity of smart phones .are making location-based services (LBS) popular. However, requesting queries to LBS servers with users' exact locations may threat the privacy of users. Therefore, there have been many researches on generating a cloaked query region for user privacy protection. Consequently, an efficient query processing algorithm for a query region is required. So, in this paper, we propose k-nearest neighbor query (k-NN) processing algorithms for a query region in road networks. To efficiently retrieve k-NN points of interest (POIs), we make use of the Island index. We also propose a method that generates an adaptive Island index to improve the query processing performance and storage usage. Finally, we show by our performance analysis that our k-NN query processing algorithms outperform the existing k-Range Nearest Neighbor (kRNN) algorithm in terms of network expansion cost and query processing time. 展开更多
关键词 island index k-nearest neighbor query processing scheme locatiombased service road network
原文传递
不确定数据查询处理 被引量:21
17
作者 蒋涛 高云君 +2 位作者 张彬 周傲英 乐光学 《电子学报》 EI CAS CSCD 北大核心 2013年第5期966-976,共11页
数据的不确定性在现实世界中的经济、军事、物流、金融、电信等领域普遍存在.不确定数据广泛应用于环境维护、市场分析、基于位置的服务LBS以及数量经济研究等应用.由于这些应用的重要性以及收集和累积的不确定数据数量的快速增长,查询... 数据的不确定性在现实世界中的经济、军事、物流、金融、电信等领域普遍存在.不确定数据广泛应用于环境维护、市场分析、基于位置的服务LBS以及数量经济研究等应用.由于这些应用的重要性以及收集和累积的不确定数据数量的快速增长,查询这些数据已经成为一个重要的任务,并日益受到广大数据库研究者的关注.本文介绍了不确定数据查询的基本原理,并对不确定数据的近邻查询、逆向近邻查询、排序查询、Top-k查询以及连接查询进行了详细的讨论.同时对这些技术的优缺点进行了分析、对比.最后给出了未来的研究方向. 展开更多
关键词 不确定数据 近邻 逆向近邻 连接 查询处理
下载PDF
MapReduce框架下基于R-树的k-近邻连接算法 被引量:60
18
作者 刘义 景宁 +1 位作者 陈荦 熊伟 《软件学报》 EI CSCD 北大核心 2013年第8期1836-1851,共16页
针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速... 针对大规模空间数据的高性能k-近邻连接查询处理,研究了MapReduce框架下基于R-树索引的k-近邻连接查询处理.首先利用无依赖并行和串行同步计算的形式化定义抽象了MapReduce并行编程模型,基于此并行计算模型抽象,分别提出了R-树索引快速构建算法和基于R-树的并行k-近邻连接算法.在索引构建过程中,提出一种采样算法以快速确立空间划分函数,使得索引构建符合无依赖并行和串行同步计算抽象,在MapReduce框架下非常容易进行表达.在k-近邻连接查询过程中,基于构建的分布式R-树索引,引入k-近邻扩展框限定查询范围并进行数据划分,然后利用R-树索引进行k-近邻连接查询,提高了查询效率.从理论上分析了所提出算法的通信和计算代价.实验与分析结果表明,该算法在真实数据集的查询上具有良好的效率和可扩展性能,可以很好地支持大规模空间数据的k-近邻连接查询处理,具有良好的实用价值. 展开更多
关键词 云计算 MAPREDUCE k-近邻连接 空间查询 R-树
下载PDF
空间k近邻查询的新策略 被引量:17
19
作者 刘宇 朱仲英 施颂椒 《上海交通大学学报》 EI CAS CSCD 北大核心 2001年第9期1298-1302,共5页
有效执行空间 k近邻查询是地理信息系统尤其关心的问题 .空间近邻查询是基于空间索引的树的遍历过程 ,若测量距离和剪枝策略选取适当 ,可以极大地减少搜索空间所需访问的节点数 .基于 Rousspoulos等提出的测量距离 ,提出 2个新的近邻搜... 有效执行空间 k近邻查询是地理信息系统尤其关心的问题 .空间近邻查询是基于空间索引的树的遍历过程 ,若测量距离和剪枝策略选取适当 ,可以极大地减少搜索空间所需访问的节点数 .基于 Rousspoulos等提出的测量距离 ,提出 2个新的近邻搜索剪枝策略 ,用于空间 k近邻查询 .给出了搜索算法 ,并用算例表明该策略具有更好的剪枝效果 ,提高了空间 展开更多
关键词 空间数据库 R树 空间k近邻查询 GIS 空间索引 近邻搜索剪技策略
下载PDF
一种对时空信息的kNN查询处理方法 被引量:11
20
作者 李晨 申德荣 +3 位作者 朱命冬 寇月 聂铁铮 于戈 《软件学报》 EI CSCD 北大核心 2016年第9期2278-2289,共12页
互联网上每天都会产生大量的带地理位置标签和时间标签的信息,比如微博、新闻、团购等等,如何在众多的信息中找到在时间和空间地理位置上都满足用户查询需求的信息十分重要.针对这一需求,提出了一种对地理位置和时间信息的k近邻查询(ST-... 互联网上每天都会产生大量的带地理位置标签和时间标签的信息,比如微博、新闻、团购等等,如何在众多的信息中找到在时间和空间地理位置上都满足用户查询需求的信息十分重要.针对这一需求,提出了一种对地理位置和时间信息的k近邻查询(ST-k NN查询)处理方法.首先,利用时空相似度对数据对象的地理位置变量和时间变量进行映射变换,将数据对象映射到新的三维空间中,用三维空间中两点之间的距离相似度来近似代替两个对象之间实际的时空相似度;然后,针对这个三维空间设计了一种ST-Rtree(spatial temporal rtree)索引,该索引综合了空间因素和时间因素,保证在查询时每个对象至多遍历1次;最后,在该索引的基础上提出了一种精确的k近邻查询算法,并通过一次计算确定查询结果范围,从而找到前k个结果,保证了查询的高效性.基于大量数据集的实验,证明了该查询处理方法的高效性. 展开更多
关键词 地理位置 时间 时空相似度 索引 K最近邻查询
下载PDF
上一页 1 2 13 下一页 到第
使用帮助 返回顶部