基于序的空间数据索引及查询算法研究
|
摘要
计算机硬件技术的不断发展为海量数据的处理提供了良好的平台。近年来,空间数据库已成为计算机科学领域的研究热点。它在地理信息系统(GIS)、计算机辅助设计与制造(CAD/CAM)、数字化城市、定位服务等众多领域得到了广泛的应用。空间数据索引技术是空间数据库的核心,它的性能直接决定着整个空间数据管理系统的好坏。研究空间数据索引技术以寻求更好的空间数据索引机制,一直是空间数据库领域的研究热点。因此,对它的研究既具有重要的理论意义又具有广泛的应用价值。
本文采用空间目标的最小外包矩形(Minimum Bounding Rectangle)近似表示方法,以获得具有较高性能的空间数据索引结构为目标,通过定义空间目标间的序关系并利用这些序关系对数据空间的划分方法进行探讨。同时,利用定义的空间目标间的序关系研究了区域查询问题、最近邻查询问题、k最近邻查询问题,将其方法进行扩展研究了空间数据库平面线段的最近邻问题。取得了如下的研究结果:
对数据空间的二分划分方法进行了深入的研究。建立了划分的优化准则,利用这些准则,分别给出了极小化覆盖和极小化交叠的二分划分方法,并建立了对应划分下的空间索引结构,用实验证明了得到的方法的先进性。
对数据空间的四分划分方法进行了深入的研究。建立了划分的极小化交叠的准则,给出了极小化交叠的四分划分方法,并建立了对应划分下的基于四叉树和R-树的空间索引结构,用实验验证了新索引结构中各层上结点间的交叠明显减少。给出了具有相对位置关系的数据空间的四分划分方法。
对数据空间的M分划分方法进行了深入的研究。建立了划分规则,给出了对应的空间索引结构、该结构上的区域查询算法。实验证明:利用数据间的有序性在进行区域查询时可得到有效的数据过滤,查询效果得到了很大的提高。
以上述研究为基础,给出了一种基于序的空间数据索引结构-MOIS-树。在树中规定每个结点的孩子结点按照其几何位置满足序关系,使得在中间结点中进行查询时可以进行快速定位。给出了全新的区域查询算法。查询算法中,一方面利用结点的有序性建立了有效的两次剪枝规则,使得只需少量的判断运算就可以过滤掉大量的数据,从而提高了查询的效率;另一方面在查询算法中引入查询窗口包含中间结点MBR的检测,对于较大的查询窗口的查询,有效地减少了MOIS-树区域查询算法中大量无效的相交性判断,从另一方面加快了查询速度。建立了最近邻查询的剪枝规则,利用这些规则给出了最近邻查询算法,减少了结点访问的次数,加快了查询的速度。将最近邻查询进行扩展,给出了k最近邻查询的算法。实验表明:本文给出的区域查询算法、最近邻和k最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高。
对空间数据库平面线段数据的最近邻问题进行了深入的研究。线段数据用其MBR近似表示。利用定义的空间数据间的序关系,给出了平面线段数据的索引结构-SI-树的定义、SI-树的生成和结点插入算法。给出了最近邻查询的剪枝规则,建立了最近邻查询算法。实验表明:本文给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大幅度的提高。
The continuous development of computer hardware techniques provides a good platform for dealing with mass data of great amount. In recent years, spatial database has become a hot research topic in computer science field. It has found wide applications in many areas such as geographic information system(GIS), computer aided design and manufacture(CAD/CAM), digital city and positioning service. Spatial data index is the kernel of spatial databases. Its properties will have direct and decisive impact on the whole spatial data management systems. To make research on spatial data index to find better index methods has been a hot research topic in the area of spatial databases. Therefore, the research on spatial data indexes has not only important theoretical significance but also wide application values.
The approximate expression of minimum bounding rectangle (MBR) for spatial objects is adopted in this dissertation. At the aim of obtaining a spatial index structure with high performance, the partition methods of data spaces are investigated, by defining the order relations between spatial objects and using them. Meanwhile the problems of range query, nearest query and k nearest query are studied by the defined order relations between spatial objects. By generalizing the methods, the nearest neighbor of planar line segments of spatial database is researched. The following research results are achieved:
The deep research on binary partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. With them, the binary partition methods with minimized coverage and minimized overlap are given. And the spatial index structures corresponding to the partition methods are established. Moreover, the advances of new methods are proved experimentally.
The deep research on quarter partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. The quarter partition methods with minimized overlap are given. And the quadtree and R-tree based spatial index structures corresponding to the partition methods are established. It is experimentally proved that the overlap among the nodes on the same level of the new index structure is reduced evidently. The quarter partition methods of data spaces with relative position relations is presented.
The research is done on M-partition method of data spaces. The partition rule related to the orders is set up, with which the spatial index structure is created, and the range query algorithm is given. Experiments show that data can be filtered effectively when range query is executed by the orders between data, and the query efficiency is greatly improved.
Based on the above-mentioned researches, an order-based spatial index structure-MOIS-tree is proposed. In the tree, it is set that the children nodes of any middle node must be arranged according to their geometric positions to satisfy one of the order relations given above. To do so can make the positions determined quickly when a range query is processed in the middle nodes. The brand new range query algorithm is proposed. The query efficiency is greatly improved in the algorithm in two ways: one is that the effective pruning rule for pruning two times by use of the orders between data objects is established so that a great amount of data can be filtered off just to take a little amount of judgment operations; another is that the the test of query window’s containing the middle node’s MBR is introduced to reduce a great number of invalid intersection judgment(computations) in the range query algorithm of MOIS-tree to accelerate the query speed. The pruning rules for nearest neighbor query on MOIS-tree is set up, with which nearest query algorithm is given to reduce the number of accessed nodes to speed the query. The nearest query algorithm is generalized to obtain the k nearest neighbor query algorithm. Experiments show that the range query algorithm, the nearest query algorithm and the k nearest neighbor query algorithm have higher query efficiencies than the algorithms of the same types.
The deep research is made on the nearest neighbor query of spatial database planar line segments. MBR approximate expression for line segments is adopted here. By using the order relations defined in this dissertation, the definition of the index structure-SI-tree for planar line segments and algorithms of the creation and node insertion of the new index structure are given. The pruning rule for nearest neighbor query is set up, with which the nearest neighbor query algorithm is proposed. Experiment shows that the query efficiency is improved greater with the algorithm in this dissertation than the existing ones of the same types.
本文采用空间目标的最小外包矩形(Minimum Bounding Rectangle)近似表示方法,以获得具有较高性能的空间数据索引结构为目标,通过定义空间目标间的序关系并利用这些序关系对数据空间的划分方法进行探讨。同时,利用定义的空间目标间的序关系研究了区域查询问题、最近邻查询问题、k最近邻查询问题,将其方法进行扩展研究了空间数据库平面线段的最近邻问题。取得了如下的研究结果:
对数据空间的二分划分方法进行了深入的研究。建立了划分的优化准则,利用这些准则,分别给出了极小化覆盖和极小化交叠的二分划分方法,并建立了对应划分下的空间索引结构,用实验证明了得到的方法的先进性。
对数据空间的四分划分方法进行了深入的研究。建立了划分的极小化交叠的准则,给出了极小化交叠的四分划分方法,并建立了对应划分下的基于四叉树和R-树的空间索引结构,用实验验证了新索引结构中各层上结点间的交叠明显减少。给出了具有相对位置关系的数据空间的四分划分方法。
对数据空间的M分划分方法进行了深入的研究。建立了划分规则,给出了对应的空间索引结构、该结构上的区域查询算法。实验证明:利用数据间的有序性在进行区域查询时可得到有效的数据过滤,查询效果得到了很大的提高。
以上述研究为基础,给出了一种基于序的空间数据索引结构-MOIS-树。在树中规定每个结点的孩子结点按照其几何位置满足序关系,使得在中间结点中进行查询时可以进行快速定位。给出了全新的区域查询算法。查询算法中,一方面利用结点的有序性建立了有效的两次剪枝规则,使得只需少量的判断运算就可以过滤掉大量的数据,从而提高了查询的效率;另一方面在查询算法中引入查询窗口包含中间结点MBR的检测,对于较大的查询窗口的查询,有效地减少了MOIS-树区域查询算法中大量无效的相交性判断,从另一方面加快了查询速度。建立了最近邻查询的剪枝规则,利用这些规则给出了最近邻查询算法,减少了结点访问的次数,加快了查询的速度。将最近邻查询进行扩展,给出了k最近邻查询的算法。实验表明:本文给出的区域查询算法、最近邻和k最近邻查询算法与现有的同类查询算法相比查询效率有较大的提高。
对空间数据库平面线段数据的最近邻问题进行了深入的研究。线段数据用其MBR近似表示。利用定义的空间数据间的序关系,给出了平面线段数据的索引结构-SI-树的定义、SI-树的生成和结点插入算法。给出了最近邻查询的剪枝规则,建立了最近邻查询算法。实验表明:本文给出的最近邻查询算法与现有的同类查询算法相比查询效率有较大幅度的提高。
The continuous development of computer hardware techniques provides a good platform for dealing with mass data of great amount. In recent years, spatial database has become a hot research topic in computer science field. It has found wide applications in many areas such as geographic information system(GIS), computer aided design and manufacture(CAD/CAM), digital city and positioning service. Spatial data index is the kernel of spatial databases. Its properties will have direct and decisive impact on the whole spatial data management systems. To make research on spatial data index to find better index methods has been a hot research topic in the area of spatial databases. Therefore, the research on spatial data indexes has not only important theoretical significance but also wide application values.
The approximate expression of minimum bounding rectangle (MBR) for spatial objects is adopted in this dissertation. At the aim of obtaining a spatial index structure with high performance, the partition methods of data spaces are investigated, by defining the order relations between spatial objects and using them. Meanwhile the problems of range query, nearest query and k nearest query are studied by the defined order relations between spatial objects. By generalizing the methods, the nearest neighbor of planar line segments of spatial database is researched. The following research results are achieved:
The deep research on binary partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. With them, the binary partition methods with minimized coverage and minimized overlap are given. And the spatial index structures corresponding to the partition methods are established. Moreover, the advances of new methods are proved experimentally.
The deep research on quarter partition methods of data spaces is made. The optimization criterions of partitioning data spaces are established. The quarter partition methods with minimized overlap are given. And the quadtree and R-tree based spatial index structures corresponding to the partition methods are established. It is experimentally proved that the overlap among the nodes on the same level of the new index structure is reduced evidently. The quarter partition methods of data spaces with relative position relations is presented.
The research is done on M-partition method of data spaces. The partition rule related to the orders is set up, with which the spatial index structure is created, and the range query algorithm is given. Experiments show that data can be filtered effectively when range query is executed by the orders between data, and the query efficiency is greatly improved.
Based on the above-mentioned researches, an order-based spatial index structure-MOIS-tree is proposed. In the tree, it is set that the children nodes of any middle node must be arranged according to their geometric positions to satisfy one of the order relations given above. To do so can make the positions determined quickly when a range query is processed in the middle nodes. The brand new range query algorithm is proposed. The query efficiency is greatly improved in the algorithm in two ways: one is that the effective pruning rule for pruning two times by use of the orders between data objects is established so that a great amount of data can be filtered off just to take a little amount of judgment operations; another is that the the test of query window’s containing the middle node’s MBR is introduced to reduce a great number of invalid intersection judgment(computations) in the range query algorithm of MOIS-tree to accelerate the query speed. The pruning rules for nearest neighbor query on MOIS-tree is set up, with which nearest query algorithm is given to reduce the number of accessed nodes to speed the query. The nearest query algorithm is generalized to obtain the k nearest neighbor query algorithm. Experiments show that the range query algorithm, the nearest query algorithm and the k nearest neighbor query algorithm have higher query efficiencies than the algorithms of the same types.
The deep research is made on the nearest neighbor query of spatial database planar line segments. MBR approximate expression for line segments is adopted here. By using the order relations defined in this dissertation, the definition of the index structure-SI-tree for planar line segments and algorithms of the creation and node insertion of the new index structure are given. The pruning rule for nearest neighbor query is set up, with which the nearest neighbor query algorithm is proposed. Experiment shows that the query efficiency is improved greater with the algorithm in this dissertation than the existing ones of the same types.
引文
[1] SHASHI SHEKHAR, SANJAY CHAWLA等著.空间数据库[M].谢昆青,马修军,杨冬青等译.北京:机械工业出版社, 2004: 118-133.
[2] GUTTMAN. A R-trees: A Dynamic Index Structure for Spatial Searching[C]. In:Proceedings of ACM SIGMOD, Boston, MA, 1984: 47-57.
[3] FRIEDMAN J H, BENTLEY J L, FINKEL R A. An Algorithm for Finding the Best Matches in Logarithmic Expected Time[J]. CAN Trans. Math. Software, 1977, (3):209-226.
[4] KOM F, MUTHUKRISHNAN S. Influence Sets Based on Reverse Nearest Neighbor Queries[C]. In:Proceedings of the 2000 ACM SIGMOD, Dallas, Texas, USA,2000:201-212.
[5] TAO Y, PAPADIAS D, SHEN Q. Continuous Nearest Neighbor Search[C]. In: Proceedings of the 28th International Conference on Very Large Data Bases. San Fransisco, USA, 2002:334-345.
[6] NUTANONG S, TANIN E, ZHANG R. Visible Nearest Neighbor Quering[C]. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications. Berlin, Germany, 2007:876-883.
[7]刘永山,郝忠孝.基于MBR的主方向关系一致性检验[J].软件学报, 2006, 17(5): 976-982.
[8]肖予钦,张臣,景宁等.基于R树的方向关系查询处理[J].软件学报,2004,15(1):103-111.
[9]李博涵.空间数据索引的优化及代价分析[D].黑龙江省:哈尔滨理工大学(博士), 2009:69-82.
[10] OOSTEROM P, JOHANNES P, VAN M. Reactive Data Structures for Geographic Information Systems[M]. Oxford, New York: Oxford University Press, 1993.
[11]史文中,郭薇.一种面向地理信息系统的空间索引方法[J].测绘学报,2001, 30(2): 156-161.
[12] KATAYAMA N, SATOH S. The SR-tree: An Index Structure for High-dimensional Nearest Neighbor Queries[J]. Transactions of the Institute of Electronics Information and Communication Engineers,1997:703-717.
[13]吴信才.空间数据库.北京:科学出版社,2009:171-176.
[14] BENTLEY J L. Multidiemnsional Binary Search Trees in Database Applications[J]. Communications of the ACM, 1975, 18(9):509-517.
[15] BANERJEE J, KIM W. Supporting VLSI GEOMETRY Operations in A Database System[C]. IEEE Proceedings of Data Engineering Conference, Los Angegels, USA, 1986:409-415.
[16] MATSUYAMA T, HAO L V, NAGAO M. A File Organization for Geographic Information Systems Based on Spatial Proximity[J]. International Journal of Computer Vision, Graphics and Image Processing, 1984, 26(3):303-318.
[17] OOI B C, MCDONELL K J, SACKS-DAVIS R. Spatial kd-tree: An Indexing Mechsnism for Spatial Databases[C]. In: Proceedings of International Conference on Computer Software and Applications, Japan, 1987: 247:258.
[18] ROBINSON J T. The K-D-B-tree: An Search Structure for Large Multidimensinal Dynamic Indexes[C]. In: Proceedings of the International Conference on Management of Data, USA, 1981:10-18.
[19] LOMET D, SALZBERG B. The hB-tree: A Multiattribute Indexing Method with Good Guarenteed Performance[J]. ACM Transactions Dtabase Systems, 1990, 15(4):625-658.
[20]金树东,冯玉才,孙小薇.多维索引hB-树的改进方法-hB*-树[J].软件学报,1998, 9(3):206-212.
[21] ABRASH M. BSP Trees[J], Dr. Dobbs Sourcebook, 1995, 20(14):49-52.
[22]谈国新.一体化空间数据结构及其索引机制研究[J].测绘学报,1998, 27(4):293-299.
[23]史杏荣,孙贞寿,曹爱军.基于固定网格划分的面向类对象的四分树空间索引机制[J].小型微型计算机系统,1998, 19(10):24-31.
[24] FINKEL R A, BENTLEY J I. Quadtrees:A Data Structure for Retrieval on Compositive Keys[J]. Acta Informatic, 1974, 4:1-9.
[25] SAMET H. The Quadtree and Related Hierarchical Data Structures[J]. ACM COMP. Surveys, 1984, 16:187-260.
[26] ORENSTEIN J A, MERRETT T H. A Class of Data Structures for Associative Searching[C]. In: Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Waterloo, Ontario, Canada, 1984:181-190.
[27] SAMET H. The Quadtree and Related Hierarchical Data Structures[J].Computing Surveys, 1984, 16(2):178-260.
[28] SAMET H. The Design and Analysis of Spatial Data Structures[M]. Addison-Wesley, Reading, Mass, 1989.
[29]邱建华,唐学兵,黄华国.一种基于四叉树和R*-树的索引结构—QR*-树[J].计算机应用,2003,23(8):124-152.
[30] YUCHEN FU, ZHIYONG HU, WEI GUO. QR-tree:A Hybrid Spatial Index Structure[C]. In: Porceedings of the Second International Conference on Machine Learning and Cybernecics, Xian, 2003:459-463.
[31] RUI DING, XIAOFENG MENG. A Quadtree Based Dynamic Attribute Index Structure and Query Process[C]. Proceedings of the 2001 International Conference on Computer Networks and Mobile Computing (ICCNMC' 01), 2001:446-448.
[32]唐立文,廖学军,汪荣峰.基于四叉树的海量空间数据模型研究[J].装备指挥技术学院学报,2007, 18(2):70-74.
[33] VALID G A. Pineline Spatial Join Processing for Quadtree-based Indexes[C]. In: Proceedings of the 15th Inernational Symposium on Advances in Geographic Information Systems, 2007:1-4.
[34] NELSON R C, SAMET H. A Population Analysis for Hierarchical Dta Structures[C]. In:Proceedings of ACM SIGMOD Conference, 1987:270-277.
[35] LAGUNA P. Low-pass Differentiations for Biological Signals with Known Spectra:Application to ECG Signal Processing[J]. IEEE Trans. on BME, 1990,37(4):420-425.
[36]徐少平,王命延,王炜力.一种基于R-树和四叉树的移动对象空间数据库混合索引结构[J].计算机与数字工程,2006,34(3):54-57.
[37] KOTHURI R K V, RAVADA S, ABUGOV D. Quadtree and R-tree Indexes in Oracle SPatial: A Comparison Using GIS Data[C]. In: Proc. of the ACM SIGMOD International Conference on Management of Data, 2002: 546-557.
[38] BERCHTOLD S, B?HM C, KRIEGEL H P. The Pyramid-Technique: Towards Indexing beyond the Curse of Dimensionality[C]. In: Proc. of ACM SIGMOD Int. Conf: on Management of Data, Seattle, 1998: 142-153.
[39]张明波,陆锋,申排伟等. R树家族的演变和发展[J].计算机学报, 2005, 28(3):289-300.
[40] RAVI KANTH KOTHURI, SIVA RAVADA, DANNIEL ABUGOV.Quadtree and R-tree Indexes in Oracle Spatial: A Comparison Using GIS Data[C]. In ACM SIGMOD, 2002:546-557.
[41] SELLIS T K., ROUSSOPOULOS N, FALOUTSOS C. The R+-trees: A Dynamic Index for Multri-dimensional Objects[J]. In: Proceedings of the 13th VLDB, Brighton, England, 1987: 507-518.
[42] BECKMANN N, KRIEGEL H P, SCHNEIDER R. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[J]. In: Proceeding of ACM SIGMOD International Conference on Management of Data, 1990: 322-332.
[43] TIAN XIA, DONGHUI ZHANG . Improving the R*-tree with Outlier Handling Techniques[C]. In:Proceedings of GIS’05, Bremen, Germany, 2005:125-134.
[44] DONGHUI ZHANG, and T. Xia. A Novel Improvement to the R*-tree Spatial Index using Gain/Loss Metrics[J]. In ACM Int. Symposium on Advances in Geographic Information Systems (GIS), 2004:204-213.
[45] KAMEL I, FALOUTSOS C. Hilbert R-tree: An Improved R-tree Using Fractals[C]. In: Proceedings of the 20th VLDB, Santiago, Chile, 1994: 501-509.
[46]郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社,2006:76-77.
[47] BERCHTOLD S, KEIM D A, HANS-PETER KRIEGEI. The X-tree: An Index Structure for High-Dimensional Data[C]. Proceedings of the 22ndV LDB Conference, India, 1996:28-39.
[48] WHITE D A, JAIN R. Similarity Indexing with the SS-tree[C]. In Proceedings of the 12th International Conference on Data Engineering, San Diego,USA,1996:516-523
[49] KATAYAMA N, SATOH S. The SR-tree: An Index Structure for High-dimensional Nearest Neighbor Queries[J]. Transactions of the Institute of Electronics Information and Communication Engineers,1997:703-717.
[50] CHEN LI , CHOUBEY R, RUNDENSTEINER E A. Bulk-insertions into R-trees Using the Small-Tree-Large-Tree Approach[C]. In: Proceedings of ACM2GIS, Washington, DC, USA, 1998, 161-162.
[51] LI CHEN, RUPESH CHOUBEY, EIKE A R. Merging R-Trees: Efficient Strategies for Local Bulk Insertion[J]. Geoinformatica, 2002, 6(1):7-34.
[52] CHOUBEY R, CHEN LI, RUNDENSTEINER E A. GBI: A Generalized R-tree Bulk-insertion Strategy[C]. In: Proceedings of SSD,Hong Kong, China, 1999, 91-108.
[53] BERCHTOLD S, BOHM C, JAGADISH H V. Independent Quantization: An Index Compression Technique for High-dimensional Spaces[C]. In: Proceedings of the Intenational Conference on Data Engineering, San Diego, USA, 2000,577-588.
[54] HUNG P W, LIN H Y. Optimizing Storage Utilization in R-tree Dynamic Index Structure for Spatial Database[J]. Journal of Systems and Software, 2001,55(3):291-299.
[55] CIACCIAL P, PATELLAL M. Searching in Metric Spaces with User-defined and Approximate Distances[J]. ACM Trans on Database System, 2002, 27(4):398– 437.
[56] SANG-HYUK LIM , KYONG-I KU, KICHANG KIM. A Node Split Algorithm Reducing Overlaped Index Spaces in M-tree Index Scheme for Music Information Retrieval System[C]. In:Proceedings of the 22nd International Conference on Data Engineering Workshops, 2006:15-22.
[57] JAKUB LOKOE, TOMAS SKOPAL. On Reinsertion in M-tree[C]. In:Proceedings of First International Workshop on Similarity Search and Applications, 2008:121-128.
[58] CAETANO TRAINA J R, AGMA TRAINA and CHRISTSOS. Fast Indexing and Visualization of Metric Data Sets Using Slim-Trees[J]. IEEE Trandactions on Knoledge and Data Engineering, 2002, 14(2):244-260.
[59]周学海,李曦,徐海燕等.多维向量动态索引结构研究[J].软件学报,2002, 13(4):768-773.
[60] UHLMANN J K. Satisfying General Proximity/Similarity Quries with Metric Trees[J]. Information Processing Letters, 1991, 40(4):175-179.
[61] BOZKAYA T, OZSOYOYOGLU M. Indexing Large Metric Spaces for Similarity Search Queries[J]. ACM Transactions on Database Systems, 1999, 24(3):361-404.
[62] LEE T, SUKHO. OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree[J]. Advanced Information Systems Engineering, 2003, (7):69-72.
[63]董道国,梁刘红,薛向阳. VAR-Tree一种新的高维数据索引结构[J].计算机研究与发展, 2005, 42(1): 10-17.
[64]董道国,刘振中,薛向阳. VA-Trie:一种用于近似k近邻查询的高维索引结构[J].计算机研究与发展, 2005, 42(12): 2213-2218.
[65] KLAUS STEINBACH, JAMES KUFFNER, TAMIM ASFOUR et al. Efficient Collision and Self-Collision Detection for Humanoids Based on Sphere Trees Hierarchies[C]. In: Proceedings of the 6th IEEE-RAS International Conference on Humaoid Robosts, 2006:560-566.
[66] QIAN GANG, ZHU QIANG, XUE QIANG et al. Dynamic Indexing For Multidimensional Non-Ordered Discrete Data Spaces Using A Data Partitioning Approach[J]. Pramanik, Sakti. ACM Transactions on Database Systems, 2006, 31(2):439-484.
[67]王国仁,黄健美,王斌等.基于最大间隙空间映射的高维数据索引技术[J].软件学报,2007,18(6):1419-1428.
[68] AGGRAWAL R, GEHRKE J, GUNOPULOS D. Automatic Subspace Clustering of High Dimensional Data[C]. In: Proc. Data Mining and Knowledge Discovery, 2005: 5-33.
[69] DANTONG YU, AIDONG ZHANG. ClusterTree: Integration of Cluster Representation and Nearest-Neighbor Search for Large Data Sets with High Dimensions[J]. IEEE TKDE, September/October, 2003,15(5):1316-1337.
[70] BRAKATSOULAS S, PFOSER D. The Revisiting R-tree Construction Principles[C]. In: Proceedings of the 6th ADBIS, Bratislava, Slovakia, 2002: 149-162.
[71]周项敏,王国仁,常立等.批量构建M+-tree[J].小型微型计算机系统,2006, 27(2):295-299.
[72]黄继先,鲍光淑.基于混合聚类算法的动态R-树[J].中南大学学报, 2006, 37(2):366-370.
[73]王锡钢,任伟,李青元.基于K-mesns聚类距离准则的R树结点分配算法研究[J].测绘科学, 2006:31(5):115-118.
[74]刘兵,严和平,段江娇等.度量空间一种自底向上索引树构造算法[J].计算机研究与发展,2006,43(9):1651-1657.
[75]张军旗,周向东,王梅等.基于聚类分解的高维度量空间索引B+-tree[J].软件学报,2008,19(6):1401-1412.
[76] SCOTT K. A Parallel Algorithm for Matrix Multiplication of Compressed Z Order Data Structures[C]. In: Proceedings of the ISCA 20th International Conference Computers and their Applications, 2005: 453-458.
[77] PROSKUROWSKI A, RUSKY F. Binary Tree Gray Codes[J]. Jouranl of Algorithm, 1985, 16:225-238.
[78] LOSEE R M. A Gray Code Based Ordering for Docments on Shelves: Classification for Browsing and Retrieval[J]. Journal of the American Society for Information Science, 1992, 43(4):312-322.
[79] OOI B C, TAN K L, YU C et al. Indexing the Edge: A Simple and Yet Efficient Approach to High-dimensional Indexing[C]. In: Proceedings of the 19th ACM SIGACT SIGMOD- SIGART Symposium on Principles of Database Systems, 2000: 166-174.
[80] BERCHTOLD S, B?HM C, KRIEGEL H P. The Pyramid-Technique: Towards Indexing beyond the Curse of Dimensionality[C]. In: Proc. of ACM SIGMOD Int. Conf: on Management of Data, Seattle, 1998: 142-153.
[81] LI JIA, WANG CHENG. Indexing Method for Hyperspectral Data Fast by Pyramid Technique[C]. Pro. of the International Conference on Computer Science and Software Engineering, Wuhan, China,2008:519-523.
[82] SAGAN HANS. Space-Filling Curves[M]. USA:Springer-Verlag, 1994.
[83] CHENYANG LI, YUCAI FENG. Algorithm for Analyzing N-dimensional Hilbert Curve[C]. In: Proc. of the 6th International Conference, Advances in Web-Age Information Management. WAIM2005, 2005, 3739: 657-662.
[84]陆锋,周成虎.一种基于Hilbert排列码的GIS空间索引方法[J].计算机辅助设计与图形学学报, 2001, 13(5): 424-429.
[85] JAGADISH H V , OOI B C, TAN K L . iDistance: Adaptive B+-tree based Indexing Method for Nearest Neighbor Search[J]. ACM Trans. On Database Systems,2005, 30(2):364-397.
[86] BOZKAYA T, OZSOYOGLU M. Distance-based Index for High-dimensional Metric Spaces[C]. In: Proceedings of the ACM SIGMOD Conerence on Management of Data, Tucson, 1997:367-368.
[87]黄扬铭.数据结构[M].北京:科学出版社,2001,219-221.
[88] KNUTH D E. The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1973.
[89] STEFAN BERCHTOLD, BERNHARD E, DANIEL A. Fast Nearest Neighbor Search in High-dimensional Spaces[C]. ICDE, 1998: 209-218.
[90] HAKAN FERHATOSMANOGLU, ERTEM TUNCEL, DIVYAKANT AGRAWAL. High Dimensional Nearest Neighbor Searching[J]. Information Systems, 2006, 31(6):512-540.
[91] SUNIL A, DAVID M, NATHAN S. NETANYAHU. An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions[J]. Journal of the ACM, 1999, 45(6): 891-923.
[92]刘永山,薄树奎,张强,郝忠孝.多对象的最近邻查询.计算机工程, 2004, 30(11): 66-68.
[93] SONG Z, ROUSSOPOULOS N. K-Nearest Neighbor Search for Moving Query Point[C]. SSTD, Redondo Beach, CA, USA, 2001: 79-96.
[94] ROUSSOPOLOUS N, KELLY S. and VINCENT F. Nearest Neighbor Queries[C]. In:Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 1995:71-79.
[95] PAPADOUPOLOS A, MANOLOPOULOS Y. Performance of Nearest Neighbor Queries in R-trees[C]. The 6th International Conference on Database Theory, Delphi, Greece, 1997: 394-408.
[96] HJALTASON G, SAMET H. Incremental Distance Join Algorithms for Spatial Databases[C]. In Proceedings of the 1998th ACM SIGMOD International Conference on Management of Data, Seattle, Washington, 1998: 237-248.
[97] KING LUM CHEUNG, ADA WAI-CHEE FU. Enhanced Nearest Neighbor Search on the R-tree[C]. ACM SIGMOD Record, 1998, 27(3): 16-21
[98]刘宇,朱仲英,施颂椒.空间k近邻查询的新策略[J].上海交通大学学报,2001, 35(9):1298-1302.
[99] SEIDL T, KRIEGEL H P. Optimal Multi-step k-Nearest Neighbor Search[C]. SIGMOD, Seattle, WA, USA, 1998: 154-165.
[100]刘云生,刘小峰,肖迎元.空间数据库中最小距离聚集查询及其算法[J].计算机科学, 2005, 32(9): 108-110, 122.
[101] SANG-WOOK KIM, CHARU C, YU P S. Effective Nearest Neighbor Indexing with The Euclidean Metric[C]. Proceedings of the 10th International Conference on Information and Knowledge Management, Atlanta, Georgia, USA, 2001. New York, NY, USA, ACM Press, 2001: 9-16.
[102] TAO Y, PAPADIAS D, SHEN Q. Continuous Nearest Neighbor Search[C]. VLDB, Hong Kong, China, 2002: 287-298.
[103] P P YUAN, Y Q CHEN, H JIN. MSVM-kNN: Combining SVM and k-NN for Multi-Class Text Classification[C]. Pro. of IEEE International Workshop on Semantic Computing and Systems, Huangshan, China, 2008:133-140.
[104] JUNG-HO UM, NIHAD KARIM CHOWDHURY , JAE-CHANG.. New Range k-NN Query Processing Algorithms Using Materialiation Technique on Spatial Network[C]. Pro. of the 2007 International Symposium on Information Technology Convergence, Jeonju, Korea, 2007: 76-80.
[105] HAIBO HU, DIK LUN L. Range Nearest Neighbor Query[J]. IEEE Trans on Knowledge and Data Engineering, 2006, 18(1):78-91.
[106]徐红波,郝忠孝.一种基于Z曲线近似k-最近对查询算法[J].计算机研究与发展, 2008, 45(2):310-317.
[107]徐红波,郝忠孝.基于Hilbert曲线的近似k-最近邻查询算法[J].计算机工程,2008, 34(12):47-49.
[108]徐红波,郝忠孝.基于Hilbert曲线的高维k-最近对查询算法[J].计算机工程, 2008, 34(2):17-19.
[109]郭小发.空间对象的连续可视最近邻查询处理研究[D].浙江省:浙江大学(硕士) , 2008: 12-17.
[110]郝忠孝,王晓东,何云斌.空间数据库平面线段近邻查询问题研究[J].计算机研究与发展, 2008, 45(9):1539-1545.
[111]周培德.计算几何[M].北京:清华大学出版社, 2008.
[2] GUTTMAN. A R-trees: A Dynamic Index Structure for Spatial Searching[C]. In:Proceedings of ACM SIGMOD, Boston, MA, 1984: 47-57.
[3] FRIEDMAN J H, BENTLEY J L, FINKEL R A. An Algorithm for Finding the Best Matches in Logarithmic Expected Time[J]. CAN Trans. Math. Software, 1977, (3):209-226.
[4] KOM F, MUTHUKRISHNAN S. Influence Sets Based on Reverse Nearest Neighbor Queries[C]. In:Proceedings of the 2000 ACM SIGMOD, Dallas, Texas, USA,2000:201-212.
[5] TAO Y, PAPADIAS D, SHEN Q. Continuous Nearest Neighbor Search[C]. In: Proceedings of the 28th International Conference on Very Large Data Bases. San Fransisco, USA, 2002:334-345.
[6] NUTANONG S, TANIN E, ZHANG R. Visible Nearest Neighbor Quering[C]. In: Proceedings of the 12th International Conference on Database Systems for Advanced Applications. Berlin, Germany, 2007:876-883.
[7]刘永山,郝忠孝.基于MBR的主方向关系一致性检验[J].软件学报, 2006, 17(5): 976-982.
[8]肖予钦,张臣,景宁等.基于R树的方向关系查询处理[J].软件学报,2004,15(1):103-111.
[9]李博涵.空间数据索引的优化及代价分析[D].黑龙江省:哈尔滨理工大学(博士), 2009:69-82.
[10] OOSTEROM P, JOHANNES P, VAN M. Reactive Data Structures for Geographic Information Systems[M]. Oxford, New York: Oxford University Press, 1993.
[11]史文中,郭薇.一种面向地理信息系统的空间索引方法[J].测绘学报,2001, 30(2): 156-161.
[12] KATAYAMA N, SATOH S. The SR-tree: An Index Structure for High-dimensional Nearest Neighbor Queries[J]. Transactions of the Institute of Electronics Information and Communication Engineers,1997:703-717.
[13]吴信才.空间数据库.北京:科学出版社,2009:171-176.
[14] BENTLEY J L. Multidiemnsional Binary Search Trees in Database Applications[J]. Communications of the ACM, 1975, 18(9):509-517.
[15] BANERJEE J, KIM W. Supporting VLSI GEOMETRY Operations in A Database System[C]. IEEE Proceedings of Data Engineering Conference, Los Angegels, USA, 1986:409-415.
[16] MATSUYAMA T, HAO L V, NAGAO M. A File Organization for Geographic Information Systems Based on Spatial Proximity[J]. International Journal of Computer Vision, Graphics and Image Processing, 1984, 26(3):303-318.
[17] OOI B C, MCDONELL K J, SACKS-DAVIS R. Spatial kd-tree: An Indexing Mechsnism for Spatial Databases[C]. In: Proceedings of International Conference on Computer Software and Applications, Japan, 1987: 247:258.
[18] ROBINSON J T. The K-D-B-tree: An Search Structure for Large Multidimensinal Dynamic Indexes[C]. In: Proceedings of the International Conference on Management of Data, USA, 1981:10-18.
[19] LOMET D, SALZBERG B. The hB-tree: A Multiattribute Indexing Method with Good Guarenteed Performance[J]. ACM Transactions Dtabase Systems, 1990, 15(4):625-658.
[20]金树东,冯玉才,孙小薇.多维索引hB-树的改进方法-hB*-树[J].软件学报,1998, 9(3):206-212.
[21] ABRASH M. BSP Trees[J], Dr. Dobbs Sourcebook, 1995, 20(14):49-52.
[22]谈国新.一体化空间数据结构及其索引机制研究[J].测绘学报,1998, 27(4):293-299.
[23]史杏荣,孙贞寿,曹爱军.基于固定网格划分的面向类对象的四分树空间索引机制[J].小型微型计算机系统,1998, 19(10):24-31.
[24] FINKEL R A, BENTLEY J I. Quadtrees:A Data Structure for Retrieval on Compositive Keys[J]. Acta Informatic, 1974, 4:1-9.
[25] SAMET H. The Quadtree and Related Hierarchical Data Structures[J]. ACM COMP. Surveys, 1984, 16:187-260.
[26] ORENSTEIN J A, MERRETT T H. A Class of Data Structures for Associative Searching[C]. In: Proceedings of the 3rd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Waterloo, Ontario, Canada, 1984:181-190.
[27] SAMET H. The Quadtree and Related Hierarchical Data Structures[J].Computing Surveys, 1984, 16(2):178-260.
[28] SAMET H. The Design and Analysis of Spatial Data Structures[M]. Addison-Wesley, Reading, Mass, 1989.
[29]邱建华,唐学兵,黄华国.一种基于四叉树和R*-树的索引结构—QR*-树[J].计算机应用,2003,23(8):124-152.
[30] YUCHEN FU, ZHIYONG HU, WEI GUO. QR-tree:A Hybrid Spatial Index Structure[C]. In: Porceedings of the Second International Conference on Machine Learning and Cybernecics, Xian, 2003:459-463.
[31] RUI DING, XIAOFENG MENG. A Quadtree Based Dynamic Attribute Index Structure and Query Process[C]. Proceedings of the 2001 International Conference on Computer Networks and Mobile Computing (ICCNMC' 01), 2001:446-448.
[32]唐立文,廖学军,汪荣峰.基于四叉树的海量空间数据模型研究[J].装备指挥技术学院学报,2007, 18(2):70-74.
[33] VALID G A. Pineline Spatial Join Processing for Quadtree-based Indexes[C]. In: Proceedings of the 15th Inernational Symposium on Advances in Geographic Information Systems, 2007:1-4.
[34] NELSON R C, SAMET H. A Population Analysis for Hierarchical Dta Structures[C]. In:Proceedings of ACM SIGMOD Conference, 1987:270-277.
[35] LAGUNA P. Low-pass Differentiations for Biological Signals with Known Spectra:Application to ECG Signal Processing[J]. IEEE Trans. on BME, 1990,37(4):420-425.
[36]徐少平,王命延,王炜力.一种基于R-树和四叉树的移动对象空间数据库混合索引结构[J].计算机与数字工程,2006,34(3):54-57.
[37] KOTHURI R K V, RAVADA S, ABUGOV D. Quadtree and R-tree Indexes in Oracle SPatial: A Comparison Using GIS Data[C]. In: Proc. of the ACM SIGMOD International Conference on Management of Data, 2002: 546-557.
[38] BERCHTOLD S, B?HM C, KRIEGEL H P. The Pyramid-Technique: Towards Indexing beyond the Curse of Dimensionality[C]. In: Proc. of ACM SIGMOD Int. Conf: on Management of Data, Seattle, 1998: 142-153.
[39]张明波,陆锋,申排伟等. R树家族的演变和发展[J].计算机学报, 2005, 28(3):289-300.
[40] RAVI KANTH KOTHURI, SIVA RAVADA, DANNIEL ABUGOV.Quadtree and R-tree Indexes in Oracle Spatial: A Comparison Using GIS Data[C]. In ACM SIGMOD, 2002:546-557.
[41] SELLIS T K., ROUSSOPOULOS N, FALOUTSOS C. The R+-trees: A Dynamic Index for Multri-dimensional Objects[J]. In: Proceedings of the 13th VLDB, Brighton, England, 1987: 507-518.
[42] BECKMANN N, KRIEGEL H P, SCHNEIDER R. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[J]. In: Proceeding of ACM SIGMOD International Conference on Management of Data, 1990: 322-332.
[43] TIAN XIA, DONGHUI ZHANG . Improving the R*-tree with Outlier Handling Techniques[C]. In:Proceedings of GIS’05, Bremen, Germany, 2005:125-134.
[44] DONGHUI ZHANG, and T. Xia. A Novel Improvement to the R*-tree Spatial Index using Gain/Loss Metrics[J]. In ACM Int. Symposium on Advances in Geographic Information Systems (GIS), 2004:204-213.
[45] KAMEL I, FALOUTSOS C. Hilbert R-tree: An Improved R-tree Using Fractals[C]. In: Proceedings of the 20th VLDB, Santiago, Chile, 1994: 501-509.
[46]郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社,2006:76-77.
[47] BERCHTOLD S, KEIM D A, HANS-PETER KRIEGEI. The X-tree: An Index Structure for High-Dimensional Data[C]. Proceedings of the 22ndV LDB Conference, India, 1996:28-39.
[48] WHITE D A, JAIN R. Similarity Indexing with the SS-tree[C]. In Proceedings of the 12th International Conference on Data Engineering, San Diego,USA,1996:516-523
[49] KATAYAMA N, SATOH S. The SR-tree: An Index Structure for High-dimensional Nearest Neighbor Queries[J]. Transactions of the Institute of Electronics Information and Communication Engineers,1997:703-717.
[50] CHEN LI , CHOUBEY R, RUNDENSTEINER E A. Bulk-insertions into R-trees Using the Small-Tree-Large-Tree Approach[C]. In: Proceedings of ACM2GIS, Washington, DC, USA, 1998, 161-162.
[51] LI CHEN, RUPESH CHOUBEY, EIKE A R. Merging R-Trees: Efficient Strategies for Local Bulk Insertion[J]. Geoinformatica, 2002, 6(1):7-34.
[52] CHOUBEY R, CHEN LI, RUNDENSTEINER E A. GBI: A Generalized R-tree Bulk-insertion Strategy[C]. In: Proceedings of SSD,Hong Kong, China, 1999, 91-108.
[53] BERCHTOLD S, BOHM C, JAGADISH H V. Independent Quantization: An Index Compression Technique for High-dimensional Spaces[C]. In: Proceedings of the Intenational Conference on Data Engineering, San Diego, USA, 2000,577-588.
[54] HUNG P W, LIN H Y. Optimizing Storage Utilization in R-tree Dynamic Index Structure for Spatial Database[J]. Journal of Systems and Software, 2001,55(3):291-299.
[55] CIACCIAL P, PATELLAL M. Searching in Metric Spaces with User-defined and Approximate Distances[J]. ACM Trans on Database System, 2002, 27(4):398– 437.
[56] SANG-HYUK LIM , KYONG-I KU, KICHANG KIM. A Node Split Algorithm Reducing Overlaped Index Spaces in M-tree Index Scheme for Music Information Retrieval System[C]. In:Proceedings of the 22nd International Conference on Data Engineering Workshops, 2006:15-22.
[57] JAKUB LOKOE, TOMAS SKOPAL. On Reinsertion in M-tree[C]. In:Proceedings of First International Workshop on Similarity Search and Applications, 2008:121-128.
[58] CAETANO TRAINA J R, AGMA TRAINA and CHRISTSOS. Fast Indexing and Visualization of Metric Data Sets Using Slim-Trees[J]. IEEE Trandactions on Knoledge and Data Engineering, 2002, 14(2):244-260.
[59]周学海,李曦,徐海燕等.多维向量动态索引结构研究[J].软件学报,2002, 13(4):768-773.
[60] UHLMANN J K. Satisfying General Proximity/Similarity Quries with Metric Trees[J]. Information Processing Letters, 1991, 40(4):175-179.
[61] BOZKAYA T, OZSOYOYOGLU M. Indexing Large Metric Spaces for Similarity Search Queries[J]. ACM Transactions on Database Systems, 1999, 24(3):361-404.
[62] LEE T, SUKHO. OMT: Overlap Minimizing Top-down Bulk Loading Algorithm for R-tree[J]. Advanced Information Systems Engineering, 2003, (7):69-72.
[63]董道国,梁刘红,薛向阳. VAR-Tree一种新的高维数据索引结构[J].计算机研究与发展, 2005, 42(1): 10-17.
[64]董道国,刘振中,薛向阳. VA-Trie:一种用于近似k近邻查询的高维索引结构[J].计算机研究与发展, 2005, 42(12): 2213-2218.
[65] KLAUS STEINBACH, JAMES KUFFNER, TAMIM ASFOUR et al. Efficient Collision and Self-Collision Detection for Humanoids Based on Sphere Trees Hierarchies[C]. In: Proceedings of the 6th IEEE-RAS International Conference on Humaoid Robosts, 2006:560-566.
[66] QIAN GANG, ZHU QIANG, XUE QIANG et al. Dynamic Indexing For Multidimensional Non-Ordered Discrete Data Spaces Using A Data Partitioning Approach[J]. Pramanik, Sakti. ACM Transactions on Database Systems, 2006, 31(2):439-484.
[67]王国仁,黄健美,王斌等.基于最大间隙空间映射的高维数据索引技术[J].软件学报,2007,18(6):1419-1428.
[68] AGGRAWAL R, GEHRKE J, GUNOPULOS D. Automatic Subspace Clustering of High Dimensional Data[C]. In: Proc. Data Mining and Knowledge Discovery, 2005: 5-33.
[69] DANTONG YU, AIDONG ZHANG. ClusterTree: Integration of Cluster Representation and Nearest-Neighbor Search for Large Data Sets with High Dimensions[J]. IEEE TKDE, September/October, 2003,15(5):1316-1337.
[70] BRAKATSOULAS S, PFOSER D. The Revisiting R-tree Construction Principles[C]. In: Proceedings of the 6th ADBIS, Bratislava, Slovakia, 2002: 149-162.
[71]周项敏,王国仁,常立等.批量构建M+-tree[J].小型微型计算机系统,2006, 27(2):295-299.
[72]黄继先,鲍光淑.基于混合聚类算法的动态R-树[J].中南大学学报, 2006, 37(2):366-370.
[73]王锡钢,任伟,李青元.基于K-mesns聚类距离准则的R树结点分配算法研究[J].测绘科学, 2006:31(5):115-118.
[74]刘兵,严和平,段江娇等.度量空间一种自底向上索引树构造算法[J].计算机研究与发展,2006,43(9):1651-1657.
[75]张军旗,周向东,王梅等.基于聚类分解的高维度量空间索引B+-tree[J].软件学报,2008,19(6):1401-1412.
[76] SCOTT K. A Parallel Algorithm for Matrix Multiplication of Compressed Z Order Data Structures[C]. In: Proceedings of the ISCA 20th International Conference Computers and their Applications, 2005: 453-458.
[77] PROSKUROWSKI A, RUSKY F. Binary Tree Gray Codes[J]. Jouranl of Algorithm, 1985, 16:225-238.
[78] LOSEE R M. A Gray Code Based Ordering for Docments on Shelves: Classification for Browsing and Retrieval[J]. Journal of the American Society for Information Science, 1992, 43(4):312-322.
[79] OOI B C, TAN K L, YU C et al. Indexing the Edge: A Simple and Yet Efficient Approach to High-dimensional Indexing[C]. In: Proceedings of the 19th ACM SIGACT SIGMOD- SIGART Symposium on Principles of Database Systems, 2000: 166-174.
[80] BERCHTOLD S, B?HM C, KRIEGEL H P. The Pyramid-Technique: Towards Indexing beyond the Curse of Dimensionality[C]. In: Proc. of ACM SIGMOD Int. Conf: on Management of Data, Seattle, 1998: 142-153.
[81] LI JIA, WANG CHENG. Indexing Method for Hyperspectral Data Fast by Pyramid Technique[C]. Pro. of the International Conference on Computer Science and Software Engineering, Wuhan, China,2008:519-523.
[82] SAGAN HANS. Space-Filling Curves[M]. USA:Springer-Verlag, 1994.
[83] CHENYANG LI, YUCAI FENG. Algorithm for Analyzing N-dimensional Hilbert Curve[C]. In: Proc. of the 6th International Conference, Advances in Web-Age Information Management. WAIM2005, 2005, 3739: 657-662.
[84]陆锋,周成虎.一种基于Hilbert排列码的GIS空间索引方法[J].计算机辅助设计与图形学学报, 2001, 13(5): 424-429.
[85] JAGADISH H V , OOI B C, TAN K L . iDistance: Adaptive B+-tree based Indexing Method for Nearest Neighbor Search[J]. ACM Trans. On Database Systems,2005, 30(2):364-397.
[86] BOZKAYA T, OZSOYOGLU M. Distance-based Index for High-dimensional Metric Spaces[C]. In: Proceedings of the ACM SIGMOD Conerence on Management of Data, Tucson, 1997:367-368.
[87]黄扬铭.数据结构[M].北京:科学出版社,2001,219-221.
[88] KNUTH D E. The Art of Computer Programming, Volume 3: Sorting and Searching, Addison-Wesley, Reading, Massachusetts, 1973.
[89] STEFAN BERCHTOLD, BERNHARD E, DANIEL A. Fast Nearest Neighbor Search in High-dimensional Spaces[C]. ICDE, 1998: 209-218.
[90] HAKAN FERHATOSMANOGLU, ERTEM TUNCEL, DIVYAKANT AGRAWAL. High Dimensional Nearest Neighbor Searching[J]. Information Systems, 2006, 31(6):512-540.
[91] SUNIL A, DAVID M, NATHAN S. NETANYAHU. An Optimal Algorithm for Approximate Nearest Neighbor Searching Fixed Dimensions[J]. Journal of the ACM, 1999, 45(6): 891-923.
[92]刘永山,薄树奎,张强,郝忠孝.多对象的最近邻查询.计算机工程, 2004, 30(11): 66-68.
[93] SONG Z, ROUSSOPOULOS N. K-Nearest Neighbor Search for Moving Query Point[C]. SSTD, Redondo Beach, CA, USA, 2001: 79-96.
[94] ROUSSOPOLOUS N, KELLY S. and VINCENT F. Nearest Neighbor Queries[C]. In:Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data, 1995:71-79.
[95] PAPADOUPOLOS A, MANOLOPOULOS Y. Performance of Nearest Neighbor Queries in R-trees[C]. The 6th International Conference on Database Theory, Delphi, Greece, 1997: 394-408.
[96] HJALTASON G, SAMET H. Incremental Distance Join Algorithms for Spatial Databases[C]. In Proceedings of the 1998th ACM SIGMOD International Conference on Management of Data, Seattle, Washington, 1998: 237-248.
[97] KING LUM CHEUNG, ADA WAI-CHEE FU. Enhanced Nearest Neighbor Search on the R-tree[C]. ACM SIGMOD Record, 1998, 27(3): 16-21
[98]刘宇,朱仲英,施颂椒.空间k近邻查询的新策略[J].上海交通大学学报,2001, 35(9):1298-1302.
[99] SEIDL T, KRIEGEL H P. Optimal Multi-step k-Nearest Neighbor Search[C]. SIGMOD, Seattle, WA, USA, 1998: 154-165.
[100]刘云生,刘小峰,肖迎元.空间数据库中最小距离聚集查询及其算法[J].计算机科学, 2005, 32(9): 108-110, 122.
[101] SANG-WOOK KIM, CHARU C, YU P S. Effective Nearest Neighbor Indexing with The Euclidean Metric[C]. Proceedings of the 10th International Conference on Information and Knowledge Management, Atlanta, Georgia, USA, 2001. New York, NY, USA, ACM Press, 2001: 9-16.
[102] TAO Y, PAPADIAS D, SHEN Q. Continuous Nearest Neighbor Search[C]. VLDB, Hong Kong, China, 2002: 287-298.
[103] P P YUAN, Y Q CHEN, H JIN. MSVM-kNN: Combining SVM and k-NN for Multi-Class Text Classification[C]. Pro. of IEEE International Workshop on Semantic Computing and Systems, Huangshan, China, 2008:133-140.
[104] JUNG-HO UM, NIHAD KARIM CHOWDHURY , JAE-CHANG.. New Range k-NN Query Processing Algorithms Using Materialiation Technique on Spatial Network[C]. Pro. of the 2007 International Symposium on Information Technology Convergence, Jeonju, Korea, 2007: 76-80.
[105] HAIBO HU, DIK LUN L. Range Nearest Neighbor Query[J]. IEEE Trans on Knowledge and Data Engineering, 2006, 18(1):78-91.
[106]徐红波,郝忠孝.一种基于Z曲线近似k-最近对查询算法[J].计算机研究与发展, 2008, 45(2):310-317.
[107]徐红波,郝忠孝.基于Hilbert曲线的近似k-最近邻查询算法[J].计算机工程,2008, 34(12):47-49.
[108]徐红波,郝忠孝.基于Hilbert曲线的高维k-最近对查询算法[J].计算机工程, 2008, 34(2):17-19.
[109]郭小发.空间对象的连续可视最近邻查询处理研究[D].浙江省:浙江大学(硕士) , 2008: 12-17.
[110]郝忠孝,王晓东,何云斌.空间数据库平面线段近邻查询问题研究[J].计算机研究与发展, 2008, 45(9):1539-1545.
[111]周培德.计算几何[M].北京:清华大学出版社, 2008.