Aggregate nearest neighbor(ANN) search retrieves for two spatial datasets T and Q, segment(s) of one or more trajectories from the set T having minimum aggregate distance to points in Q. When interacting with large am...Aggregate nearest neighbor(ANN) search retrieves for two spatial datasets T and Q, segment(s) of one or more trajectories from the set T having minimum aggregate distance to points in Q. When interacting with large amounts of trajectories, this process would be very time-consuming due to consecutive page loads. An approximate method for finding segments with minimum aggregate distance is proposed which can improve the response time. In order to index large volumes of trajectories, scalable and efficient trajectory index(SETI) structure is used. But some refinements are provided to temporal index of SETI to improve the performance of proposed method. The experiments were performed with different number of query points and percentages of dataset. It is shown that proposed method besides having an acceptable precision, can reduce the computation time significantly. It is also shown that the main fraction of search time among load time, ANN and computing convex and centroid, is related to ANN.展开更多
In recent years, the nearest neighbor search （NNS） problem has been widely used in various interesting applications. Locality-sensitive hashing （LSH）, a popular algorithm for the approximate nearest neighbor probl...In recent years, the nearest neighbor search （NNS） problem has been widely used in various interesting applications. Locality-sensitive hashing （LSH）, a popular algorithm for the approximate nearest neighbor problem, is proved to be an efficient method to solve the NNS problem in the high-dimensional and large-scale databases. Based on the scheme of p-stable LSH, this paper introduces a novel improvement algorithm called randomness-based locality-sensitive hashing （RLSH） based on p-stable LSH. Our proposed algorithm modifies the query strategy that it randomly selects a certain hash table to project the query point instead of mapping the query point into all hash tables in the period of the nearest neighbor query and reconstructs the candidate points for finding the nearest neighbors. This improvement strategy ensures that RLSH spends less time searching for the nearest neighbors than the p-stable LSH algorithm to keep a high recall. Besides, this strategy is proved to promote the diversity of the candidate points even with fewer hash tables. Experiments are executed on the synthetic dataset and open dataset. The results show that our method can cost less time consumption and less space requirements than the p-stable LSH while balancing the same recall.展开更多
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.展开更多
针对基于稀疏不变性假设的单帧超分辨率(SR)算法的局限性,提出一种利用相似最近邻(ANN)统计预测模型的单帧SR算法。首先,利用相似最近邻思想,通过波尔茨曼机捕捉HR字典与LR字典对稀疏模式之间的依赖关系,建立统计预测模型;然后,根据LR块...针对基于稀疏不变性假设的单帧超分辨率(SR)算法的局限性,提出一种利用相似最近邻(ANN)统计预测模型的单帧SR算法。首先,利用相似最近邻思想,通过波尔茨曼机捕捉HR字典与LR字典对稀疏模式之间的依赖关系,建立统计预测模型;然后,根据LR块与HR块相关的最小均方误差(MMSE)计算网络参数,获得它们的依赖关系;最后,利用多层前向神经网络提取字典元素内积,通过计算重叠局部块预测值的均值来重建图像。利用峰值信噪比PSNR和结构相似性度量SSIM评估实验结果,实验结果表明,提出的算法在视觉效果和数值标准方面大多优于其他算法,在选择合适参数情况下,峰值信噪比至少提高0.2 d B。展开更多
针对核环境下自主式导航机器人对目标识别与跟踪过程中提高特征点匹配的准确率和稳定性问题,提出一种基于加速鲁棒特征(speed up robust features,SURF)算法进行特征提取和特征描述,利用快速最近邻逼近搜索函数库(fast library for appr...针对核环境下自主式导航机器人对目标识别与跟踪过程中提高特征点匹配的准确率和稳定性问题,提出一种基于加速鲁棒特征(speed up robust features,SURF)算法进行特征提取和特征描述,利用快速最近邻逼近搜索函数库(fast library for approximate nearest neighbors,FLANN)算法进行特征点预匹配,并使用随机采样一致性(random sample consensus,RANSAC)算法优化匹配结果,从而实现图像实时匹配与识别。实验结果表明,在不同实验条件下,包括角度变换、缩放变换、局部遮挡、局部光照等,本文算法均能匹配出目标区域内模板图像,具有较好的精确性和稳定性。展开更多
Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the ...Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the intrinsic high order structures of data,which usually contain helpful information for improving the computational precision.In this paper,aiming at the complex structure of high order data,we design an optimized technique,called optimized high order product quantization(O-HOPQ)for ANN search.In O-HOPQ,we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way.As a result,spatial adjacent elements in the high order data space are grouped into the same subspace.Then,O-HOPQ generates its spatial structured codebook,by optimizing the quantization distortion.Starting from the structured codebook,the global optimum quantizers can be obtained effectively and efficiently.Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers.Besides,the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.展开更多
文摘Aggregate nearest neighbor(ANN) search retrieves for two spatial datasets T and Q, segment(s) of one or more trajectories from the set T having minimum aggregate distance to points in Q. When interacting with large amounts of trajectories, this process would be very time-consuming due to consecutive page loads. An approximate method for finding segments with minimum aggregate distance is proposed which can improve the response time. In order to index large volumes of trajectories, scalable and efficient trajectory index(SETI) structure is used. But some refinements are provided to temporal index of SETI to improve the performance of proposed method. The experiments were performed with different number of query points and percentages of dataset. It is shown that proposed method besides having an acceptable precision, can reduce the computation time significantly. It is also shown that the main fraction of search time among load time, ANN and computing convex and centroid, is related to ANN.
基金Project supported by the National Natural Science Foundation of China(Grant No.61173143)the Special Public Sector Research Program of China(Grant No.GYHY201206030)the Deanship of Scientific Research at King Saud University for funding this work through research group No.RGP-VPP-264
文摘In recent years, the nearest neighbor search （NNS） problem has been widely used in various interesting applications. Locality-sensitive hashing （LSH）, a popular algorithm for the approximate nearest neighbor problem, is proved to be an efficient method to solve the NNS problem in the high-dimensional and large-scale databases. Based on the scheme of p-stable LSH, this paper introduces a novel improvement algorithm called randomness-based locality-sensitive hashing （RLSH） based on p-stable LSH. Our proposed algorithm modifies the query strategy that it randomly selects a certain hash table to project the query point instead of mapping the query point into all hash tables in the period of the nearest neighbor query and reconstructs the candidate points for finding the nearest neighbors. This improvement strategy ensures that RLSH spends less time searching for the nearest neighbors than the p-stable LSH algorithm to keep a high recall. Besides, this strategy is proved to promote the diversity of the candidate points even with fewer hash tables. Experiments are executed on the synthetic dataset and open dataset. The results show that our method can cost less time consumption and less space requirements than the p-stable LSH while balancing the same recall.
基金Supported by the National Natural Science Foundation of China (60673136)the Natural Science Foundation of Heilongjiang Province of China (F200601)~~
文摘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.
文摘针对基于稀疏不变性假设的单帧超分辨率(SR)算法的局限性,提出一种利用相似最近邻(ANN)统计预测模型的单帧SR算法。首先,利用相似最近邻思想,通过波尔茨曼机捕捉HR字典与LR字典对稀疏模式之间的依赖关系,建立统计预测模型;然后,根据LR块与HR块相关的最小均方误差(MMSE)计算网络参数,获得它们的依赖关系;最后,利用多层前向神经网络提取字典元素内积,通过计算重叠局部块预测值的均值来重建图像。利用峰值信噪比PSNR和结构相似性度量SSIM评估实验结果,实验结果表明,提出的算法在视觉效果和数值标准方面大多优于其他算法,在选择合适参数情况下,峰值信噪比至少提高0.2 d B。
基金the National Natural Science Foundation of China(Grant No.61732011)Applied Fundamental Research Program of Qinghai Province(2019-ZJ-7017).
文摘Product quantization is now considered as an effective approach to solve the approximate nearest neighbor(ANN)search.A collection of derivative algorithms have been developed.However,the current techniques ignore the intrinsic high order structures of data,which usually contain helpful information for improving the computational precision.In this paper,aiming at the complex structure of high order data,we design an optimized technique,called optimized high order product quantization(O-HOPQ)for ANN search.In O-HOPQ,we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way.As a result,spatial adjacent elements in the high order data space are grouped into the same subspace.Then,O-HOPQ generates its spatial structured codebook,by optimizing the quantization distortion.Starting from the structured codebook,the global optimum quantizers can be obtained effectively and efficiently.Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers.Besides,the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.
