计算机科学 ›› 2013, Vol. 40 ›› Issue (7): 201-205.
姚华传,王丽珍,陈红梅,胡新
YAO Hua-chuan,WANG Li-zhen,CHEN Hong-mei and HU Xin
摘要: 求解最近点对问题在诸如地理信息查询、空间数据库等领域应用广泛。但到目前为止,还没有一种高效的求解算法,如传统求解最近对的分治算法存在比较次数较多、阈值收敛速度慢、计算距离次数较多的缺点。基于网格技术的求解最近邻方法存在网格的大小难以确定和算法效率低的问题。据此,首先提出基于单向检测的最近对求解算法(CP_SDD),然后提出按行划分的排序算法(RDS),最后得到基于分行排序单向检测的最近对求解算法(CP_SDD+RDS)。该算法不仅克服了分治法存在的缺点,而且子算法(RDS)的分行思想还克服了划分网格过程中存在的弊端。大量实验表明,CP_SDD+RDS算法是高效和可行的。
[1] Shamos M I,Hoey D.Closest-point problems[C]∥ Proc.16th IEEE Annu.Symp.Found.Comput.Sci.Berkeley,US,1975:151-162 [2] Zhou Yu-lin,Xiong Peng-rong,Zhu Hong.An improved algo-rithm about the closest pair of points on plane set[J].Computer Reachearch and Development,1998,35(10):957-960 [3] Ge Qi,Wang Hai-tao,Zhu Hong.An Improved Algorithm for Finding the Closest Pair of Points[J].J.Comput.Sci.& Tech-nol.,2006,21(1):27-31 [4] Xiong X P,Mohamed F,et al.SEA-CNN:Scalable processing of continuous K-nearest neighbor queries in spatio-temporal databases[C]∥Proc of ICDE2005.Piscataway,NJ:IEEE,2005:643-654 [5] Yu X H,Pu K Q,et al.Monitoring K-nearest neighbor queries over moving objects[C]∥Proc of Data Engineering (ICDE2005).Piscataway,NJ:IEEE,2005:631-642 [6] Mouratidis K,Hadjieleftheriou M.Conceptual partitioning:Anefficient method for continuous nearest neighbor monitoring[C]∥Proc of ACM SIGMOD2005.New York:ACM,2005:634-645 [7] Zhang Xiao-feng,Wang Li-zhen,Xiao Qing,et al.ContinuousNearest Neighbor Query Based on Conceptual Partitioning[J].Journal of Computer Research and Development,2010,47(Suppl.):154-160 [8] Xu Hong-bo,Hao Zhong-xiao.Nearest-neighbor Query Algo-rithm Based on Grid Partition of Space-filling Curve[J].Computer Science,2010,37(1) [9] 张丽平,李松.数据集中强邻近对的查询方法[J].计算机工程与设计,2008,9(16):4353-4355 [10] 张奋,潘梅生,邹北骥.基于SR-树的空间对象最近邻查询[J].计算机工程与应用,2007,3(4):173-175 [11] 李松,郝忠孝.移动对象的动态反向最近邻查询技术[J].计算机工程,2008,34(10):40-42 [12] Sack J R,Urrutia J.Closest-point problems in computational geometry[M].Handbook on Computational Geometry.Ottawa:Elesvier Science,2000:877-935 [13] Corral A,Manolopoulos Y,Theodoridis Y,et al.Algorithms for processing k-closest-pair queries in spatial databases[J].Data and Knowledge Engineering,2004,49(1):67-104 [14] Fabrizio A,Clara P.Approximate k-closest-pairs in large high dimensional data sets[J].Journal of Mathematical Modeling and Algorithms Springer Netherlands,2005,4(2):149-179 |
No related articles found! |
|