空间索引技术及其应用研究
|
摘要
空间索引技术在计算机辅助设计与制造（CAD/CAM）、地理信息系统（GIS）、图像处理（image processing ）、虚拟现实语言设计（VRML）、数字地球（digital earth）等诸多领域均具有十分重要的研究意义，它能为GIS中图形图像的存取处理提供技术支持，为空间关系的分析处理提供理论依据，同时为空间数据库的设计者在采用的数据结构方面提供有益的参考。
本论文首先对空间数据库的索引进行探讨，并给出了空间索引结构的发展演化图，然后介绍了目前国内外GIS的空间连接过程中的主流索引结构，最后引入了字符来表达空间对象。在大比例尺空间及日常生活中,人们普遍使用定性描述理解、分析和对空间环境下结论。定性描述可以处理非精确数据，简化描述和推理过程。当前地理信息系统空间关系描述模型和表示大多是定性的，而自然语言描述中往往采用定性的方法，空间信息的定量处理方式明显与人们对空间关系下结论的方式不同，不符合人们的空间认知结构。本文主要介绍了利用字符对二维空间的空间对象进行定性空间分析。
本文着重讨论了GIS中二维简单空间区域对象的空间关系， GIS空间数据索引方式，以及空间数据索引的应用。本文介绍了一种基于字符的空间对象索引方式及其在表达空间对象的空间关系分析上的应用。在空间连接处理的算法上采用了经典的R树作为索引，采用批生成算法生成R树。为改善生成效率，对空间对象的MBR按矩形中心点进行Hilbert排列码排序。实践证明，这种方式取得了最好的查询性能。在求精时，摒弃了传统的复杂的几何计算，本文提出了一种基于字符的查找模式，将二维的空间对象转化为一维字符串进行处理，并利用启发式搜索算法将二维空间上的无序查找转化为有序查找，从而利用折半查找法，大大提高了查询效率。实践证明，字符串在表达空间对象的方向关系上较为有效。本文基于对空间对象的投影，生成两个一维方向上的字符串，然后通过分析字符串，利用空间方向关系矩阵来进一步确定方向关系，进而得出空间对象的相对方向关系。
The Spatial Data Index Technology is of significance in researching into CAD/CAM, GIS, Image process, VRML, digital earth and many other fields. It can provide technological support for accessing images in GIS, offer theoretical basis for analyzing and managing space relation, and give spatial database designers helpful references for adopting data structure.
This thesis discusses spatial data index first, shows the history of spatial index structure, introduces the current domestic and foreign main index structure in GIS's spatial joining, and then makes use of character to express spatial object. Qualitative description is often used to understand, analyze and conclude about spatial environment in large scale space and everyday life. Qualitative description can deal with unaccurate data and simplify the description and reasoning process. The representation model of spatial relation and its expression are mostly qualitative in the current GIS, and natural language description often adopts the qualitative method. The quantitative method of spatial data is apparently different from the method of people's concluding about spatial relation and not in accordance with spatial cognition. This thesis is intended for the introduction to the qualitative spatial analysis of spatial object in two-dimensional space by using character.
This thesis mainly discusses spatial relation of simple area object in two-dimensional space, the methods of spatial data index in GIS and the application of spatial data index. This thesis introduces a method of spatial data index based on character and its application to spatial relation analysis of spatial object. The classical R-tree as index is adopted in spatial joining. R-tree is performed by bulk loading. In order to perfect performance efficiency, the MBR of spatial object is ordered by the Hilbert ordering code of the center of spatial object's MBR. Practice shows that this method gets best query performance. When refining the candidates, the author gets rid of traditional complicated geometric calculating. This thesis sets forward a new query model based on character. This model changes two-dimensional spatial object into one-dimensional string to process, and therefore turns two-dimensional disorder query into order query by using heuristic querying algorithm so that bisearch is used to improve query efficiency greatly. It is proved that string is relatively effective on expressing direction relations of spatial object. Based on the projection of spatial object,
two one-dimensional strings are produced. Analyzing these strings and using spatial direction relation matrices, we could further revise the direction relation. As a result the relative direction relation of spatial object is obtained.
本论文首先对空间数据库的索引进行探讨，并给出了空间索引结构的发展演化图，然后介绍了目前国内外GIS的空间连接过程中的主流索引结构，最后引入了字符来表达空间对象。在大比例尺空间及日常生活中,人们普遍使用定性描述理解、分析和对空间环境下结论。定性描述可以处理非精确数据，简化描述和推理过程。当前地理信息系统空间关系描述模型和表示大多是定性的，而自然语言描述中往往采用定性的方法，空间信息的定量处理方式明显与人们对空间关系下结论的方式不同，不符合人们的空间认知结构。本文主要介绍了利用字符对二维空间的空间对象进行定性空间分析。
本文着重讨论了GIS中二维简单空间区域对象的空间关系， GIS空间数据索引方式，以及空间数据索引的应用。本文介绍了一种基于字符的空间对象索引方式及其在表达空间对象的空间关系分析上的应用。在空间连接处理的算法上采用了经典的R树作为索引，采用批生成算法生成R树。为改善生成效率，对空间对象的MBR按矩形中心点进行Hilbert排列码排序。实践证明，这种方式取得了最好的查询性能。在求精时，摒弃了传统的复杂的几何计算，本文提出了一种基于字符的查找模式，将二维的空间对象转化为一维字符串进行处理，并利用启发式搜索算法将二维空间上的无序查找转化为有序查找，从而利用折半查找法，大大提高了查询效率。实践证明，字符串在表达空间对象的方向关系上较为有效。本文基于对空间对象的投影，生成两个一维方向上的字符串，然后通过分析字符串，利用空间方向关系矩阵来进一步确定方向关系，进而得出空间对象的相对方向关系。
The Spatial Data Index Technology is of significance in researching into CAD/CAM, GIS, Image process, VRML, digital earth and many other fields. It can provide technological support for accessing images in GIS, offer theoretical basis for analyzing and managing space relation, and give spatial database designers helpful references for adopting data structure.
This thesis discusses spatial data index first, shows the history of spatial index structure, introduces the current domestic and foreign main index structure in GIS's spatial joining, and then makes use of character to express spatial object. Qualitative description is often used to understand, analyze and conclude about spatial environment in large scale space and everyday life. Qualitative description can deal with unaccurate data and simplify the description and reasoning process. The representation model of spatial relation and its expression are mostly qualitative in the current GIS, and natural language description often adopts the qualitative method. The quantitative method of spatial data is apparently different from the method of people's concluding about spatial relation and not in accordance with spatial cognition. This thesis is intended for the introduction to the qualitative spatial analysis of spatial object in two-dimensional space by using character.
This thesis mainly discusses spatial relation of simple area object in two-dimensional space, the methods of spatial data index in GIS and the application of spatial data index. This thesis introduces a method of spatial data index based on character and its application to spatial relation analysis of spatial object. The classical R-tree as index is adopted in spatial joining. R-tree is performed by bulk loading. In order to perfect performance efficiency, the MBR of spatial object is ordered by the Hilbert ordering code of the center of spatial object's MBR. Practice shows that this method gets best query performance. When refining the candidates, the author gets rid of traditional complicated geometric calculating. This thesis sets forward a new query model based on character. This model changes two-dimensional spatial object into one-dimensional string to process, and therefore turns two-dimensional disorder query into order query by using heuristic querying algorithm so that bisearch is used to improve query efficiency greatly. It is proved that string is relatively effective on expressing direction relations of spatial object. Based on the projection of spatial object,
two one-dimensional strings are produced. Analyzing these strings and using spatial direction relation matrices, we could further revise the direction relation. As a result the relative direction relation of spatial object is obtained.
引文
[1] V.Gaede and O.Gunther，multidimentional access methods ，Computing Surveys 1998，30:2，pp.170～231.
[2] 朱欣娟，石美红，薛惠锋，彭文祥，基于GIS的空间分析及其发展研究，计算机工程与应用，2002.18，pp:62～63，105
[3] 陈菲，秦小麟，空间索引的研究，计算机科学，2001.28:12，pp：59～62
[4] J. P. Peloux, G. Reynal de St Michel, Michel Scholl ，Evaluation of spatial indices implemented with the DBMS O2 ，Gemo Report number 69，Ingenierie des Systemes d'Information，1995，http://osage.inria.fr/verso/Gemo/PUBLI/all-byyear.php ，2001.6
[5] Guttman, A., R-trees: A Dynamic Index Structure for Spatial Searching， In Proc. ACM SIGMOD International Conference on Management of Data, 1984, pp. 47～57
[6] Beckman，N，H．-P．Krigel，R．Schneid-er，B．Seeger，The R*-tree：An Efficient and Robust Access Method for Points and Rectangles，In Proc. ACM SIGMOD International Conference on Management of Data, 1990, pp. 322～331
[7] Smith, T.R., and P. Gao，Experimental performance evaluations on spatial access methods，In Proc. 4 th Int. Symp. on Spatial Data Handling, Zurich, 1990, pp.991～1002
[8] Hutflesz, A., H.W. Six, and P. Widmayer ，Globally order preserving multidimensional linear hashing， In Proc. 4 th IEEE Int. Conf. on Data Eng. ,1988, pp.572～579.
[9] B?hm and Hans-Peter Kriegel，Dynamically Optimizing High-Dimensional Index Structures， Advances in Database Technology - EDBT 2000, 7th International Conference on Extending Database Technology, Konstanz, Germany, March 27～31, Proceedings，2000，pp.36～50
[10] Stefan Berchtold1, Christian B?hm1,2, H. V. Jagadish3, Hans-Peter Kriegel2, J?rg Sander2 Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces，16th International Conference on Data Engineering (ICDE)，San Diego，CA ，2000 .
[11] C. A. Lang and A. K. Singh. Performance prediction of high-dimensional index structures using sampling，Technical Report TRCS00-16, Univ. of California at Santa Barbara，2000，http://www.cs.ucsb.edu/research/trcs/abstracts/2000-16.shtml ，2001.6
[12]Sakurai Y,et.al.The A-tree ：An index structure for high-demensions spaces using relative approximation，In：Proc．of the 26th VLDB Conf．Cairo，Egypt，2000
[13] 曹加恒，张剑，谭辉，赵莉，空间索引的新机制－G树，武汉大学学报（自然科学版），1998，44（1）：49～52
[14] 郭薇，陈军，基于点集拓扑学的三维拓扑空间空间关系形式化描述，测绘学报，1997，
26（2）：122～127
[15] 冯玉才，陈琳，曹忠升，空间数据库的方向关系模型，计算机工程与应用，2001.20：115～117
[16] Hoel, E.G. and H. Samet ．A qualitative comparison study of data structures for large segment databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data．1992，pp. 205-214.
[17]曹菡，师军，李生刚，陈军，点集拓扑理论在拓扑关系描述中的应用，工程数学学报，2001，18（4）：76～82
[18]阎浩文，郭仁忠，空间方向关系基础性问题研究，测绘学报，2002，31（4）：357～360
[19]曹菡，陈军，杜道生，空间目标方向关系的定性扩展描述，测绘学报，2001，30（２）：162～167
[20]曹加恒，赵莉，舒风笛，谭辉，对象管理的空间连接策略与算法，武汉大学学报（自然科学版），1998，44（5）：585～588
[21]顾军，吴长彬，常用空间索引技术的分析，微型电脑应用，2001，17（12）：40～42
[22]Dimitris Papadias and Timos Sellis，“Qualitative Representation of Spatial Knowledge in Two-Dimensional Space”，VLDB Journal,3, 479～516 ，May 1994
[23]Frank Andrew U. Qualitative Spatial Reasoning:Cardinal Directions as An Example[J].INT J Geographical Information Systems,1996,10(3):269～290.
[24]Hoel, E.G. and H. Samet ，A qualitative comparison study of data structures for large segment databases， In Proc. ACM SIGMOD Int. Conf. on Management of Data,,1992，pp. 205～214
[25]Kamel, I. and C. Faloustsos .Hilbert R-tree: An improved R-tree using fractals. In Proc. 20 th Int. Conf. On Very Large Data Bases, 1994 ，pp. 500～509.
[26]陈军，赵仁亮，GIS空间关系的基本问题与研究进展，测绘学报，1999，28（2）：95～103
[27]陈琳，杜友福，王元珍，MBR：基于MBR的空间关系模型，计算机工程与应用，2002，5：76～78
[28]史与正，蒋卫国，曾风山，在GIS软件中的拓扑关系及判定法则，湖南地质，2001.12，20（4）：309～315
[29]李成名，朱英浩，陈军，利用Voronoi图形式化描述和判断GIS中的方向关系，1998，15（2）：117～120
[30]Roussopoulos N ，Leifker，D.Drect Spatial Search on Pictorial Database Using Packed R－trees.ACM SIGMOD Int.Conf.on Management of Data .Austin,Texas,1985．pp:17~31
[31]Egenhofer M．Pre-processing Queries with Spatial Constraints．PE&RS，1994，60（6）：783～970
[32]Florence Ⅲ，John and Egenhofer，Max J．Distribution of Topological Relations in Geographic Datasets．In：ASPRS/ACSM．Annual Convention and Exposition Technical Papers．1996，
315～325
[33]Gold Christopher M．The Meaning of "Neighbor" Lecture Notes in Computer Science 639．Pisa：Springer-Verlag，1992,220～235
[34]胡勇，陈军，基于Voronoi图的空间邻近关系表达和查询操作，中国GIS协会第二届年会论文集，1997，346～356
[35]Zhao Renliang，Chen Jun and Li Zhilin，Voronoi-based Generalized Spatial Adjacency．In：Li Deren，et al．，ed．The processing of RS，GPS，GIS，Their integration and applications．Wuhan Technical University of Surveying and Mapping Press．1998，605～612
[36]Orenstein J A．Spatial query processing in an object-oriented database system[Ａ]．Proc ACM SIGMOD Int Conf on Management of Data[Ｃ]．Washington DC，1986，181～190
[37]Brinkhoff Ｔ，Kriegel H．P，Seeger B．Efficient processing of spatiall joins using R-trees[Ａ]．ACM SIGMOD Int Conf on Management of Data[Ｃ]．1993．237～246
[38]Lo M L，Ravishankar C V．Spatial hash joins[A]ACM SIGMOD Int Conf on Management of Data[Ｃ]．Washington DC，1996，247～258
[39]Lo M L，Ravishankar C V．The design and implementation of seeds trees：an efficient for Spatial joins[J]．IEEE Trans on Knowledge and Data Engineering，1998，10（１），136～152
[40]Peuquet，D．Ci－Xiang，Z．An Algorithm to Determine the Directional Realtionship between Arbitrarily－Shaped Polygons in the Plane．Pattern Recognition，1987，20（1）：65～74
[41]Goyal R．K．Similarity Assessment for Cardinal directions Between Extened Spatial Objects [D]．PHD Thesis，The University of Maine，2000
[42]LiChengming，Voronoi Principles and methods for spatial relation description [M]，Xi' an Map Press，2000
[43]Papadias D，Theodoridis Y．and Sellis T．The Retrieval of Direction Relations using R-trees，Database and Expert Systems Applications [C]．5th International Conference，DEXA'94，Athens，Greece，D．Karagiannis，Ed．Lecture Notes in Computer Science，Springer-Verlag，New York，1994，173～182
[44]史杏荣，孙贞寿，基于固定网格划分和面向类对象的四分树空间索引机制，小型微型计算机系统，1998，19（10）：24～31
[45]J．Patel and D．J．DeWitt．Partition Based Spatial-Merge join．In Proc．ACM SIGMOD Symp．Conf．on Management of Data，1996： 259～270
[46]N．Mamoulis and D．Papadias．Integration of spatiall join algorithms for joining multiple inputs．In Proc．ACM SIGMOD Symp．Conf．on Management of Data，1999
[47]A．Papadopoulos，P．Rigaux，and M．Scholl．A Performance Evaluation of Spatial join
Processing Strategies．In Proc．Intl．Conf．on Large Spatial Databases(SSD)，1999
[48]T．Brinkhoff，H．Kriegel，R．Schneider，and B．Seeger．Multi-step Processing of Spatial join．In Proc．ACM SIGMOD Symp．Conf．on the Management of Data，1994： 197～208
[49]Alexandre A．B．Lima，Cláudio Esperanca，Marta Mattoso．A Parallel Spatial Join Framework Using PMR-Quadtrees．11th International Workshop on Database and Expert Systems Applications (DEXA'00) ， 2000 ：889～893
[50]谈晓军，涂建光，一种自适应的两阶段R树批生成算法，武汉大学学报（信息科学版），2003，28（１）：31～38
[51]Hector Garcia-Molina，Jeffrey D．Ullman，Jennifer Widom 著，《数据库系统实现》（英文版），机械工业出版社，2002.1
[52] Greene, D. An implementation and performance analysis of spatial data access methods. In Proc. 5th IEEE Int. Conf. on Data Eng．1989， pp. 606～615.
[53] Brinkhoff Ｔ，Kriegel H．P，Schncider R．Comparision of Approsimations of Complex Objects Used for Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database system．In Proc．of 9th Int'l conf．Ｏn Data E ngineering,1993
[54] Kamel, I. and C. Faloustsos .On Packing R-tree . In Proc. 2nd Int. Conf. On Information and Management（CIKM）, 1993 ，pp. 490～499.
[55]Leutenegger S T，Edgiyton J M，Lopez M A．STR：A Simple and Efficeent Algorithim for R-tree Packing．In Proc. of the IEEE Int'l Conf. on Data Engineering．1997
[56]Berchtold S B?hm C，Kriegel H P．Improving the Query Performance of High Dimensional Index Structures by Bulk Load Operations．Proc．of the Int．Conf．on Extending Database Technology，Volume 1377 of Lecture Notes in Computer Science．Berlin：Sphinger-Verlag，1998
[57]Dewitt D J，Kabra N，Luo J，et al．Client-server Paradise，The 20th VLDB Conference，Santigo，1994
[58]刘宇，朱仲英，施颂椒，基于直角多边形近似的空间连接查询，上海交通大学学报，2001，35（2）：279～302
[59]Garcia Y J，López M A，Leutenegger S T．A Greedy Algorithm for Bulk Loading R-trees．The 6th ACM International Workshop on Advances in Geographic Information Systems．Washington，1998
[60] Paul Kimmel 著，郭旭、周建明 译，Delphi 6.0 应用开发指南，清华大学出版社，2002.1
[2] 朱欣娟，石美红，薛惠锋，彭文祥，基于GIS的空间分析及其发展研究，计算机工程与应用，2002.18，pp:62～63，105
[3] 陈菲，秦小麟，空间索引的研究，计算机科学，2001.28:12，pp：59～62
[4] J. P. Peloux, G. Reynal de St Michel, Michel Scholl ，Evaluation of spatial indices implemented with the DBMS O2 ，Gemo Report number 69，Ingenierie des Systemes d'Information，1995，http://osage.inria.fr/verso/Gemo/PUBLI/all-byyear.php ，2001.6
[5] Guttman, A., R-trees: A Dynamic Index Structure for Spatial Searching， In Proc. ACM SIGMOD International Conference on Management of Data, 1984, pp. 47～57
[6] Beckman，N，H．-P．Krigel，R．Schneid-er，B．Seeger，The R*-tree：An Efficient and Robust Access Method for Points and Rectangles，In Proc. ACM SIGMOD International Conference on Management of Data, 1990, pp. 322～331
[7] Smith, T.R., and P. Gao，Experimental performance evaluations on spatial access methods，In Proc. 4 th Int. Symp. on Spatial Data Handling, Zurich, 1990, pp.991～1002
[8] Hutflesz, A., H.W. Six, and P. Widmayer ，Globally order preserving multidimensional linear hashing， In Proc. 4 th IEEE Int. Conf. on Data Eng. ,1988, pp.572～579.
[9] B?hm and Hans-Peter Kriegel，Dynamically Optimizing High-Dimensional Index Structures， Advances in Database Technology - EDBT 2000, 7th International Conference on Extending Database Technology, Konstanz, Germany, March 27～31, Proceedings，2000，pp.36～50
[10] Stefan Berchtold1, Christian B?hm1,2, H. V. Jagadish3, Hans-Peter Kriegel2, J?rg Sander2 Independent Quantization: An Index Compression Technique for High-Dimensional Data Spaces，16th International Conference on Data Engineering (ICDE)，San Diego，CA ，2000 .
[11] C. A. Lang and A. K. Singh. Performance prediction of high-dimensional index structures using sampling，Technical Report TRCS00-16, Univ. of California at Santa Barbara，2000，http://www.cs.ucsb.edu/research/trcs/abstracts/2000-16.shtml ，2001.6
[12]Sakurai Y,et.al.The A-tree ：An index structure for high-demensions spaces using relative approximation，In：Proc．of the 26th VLDB Conf．Cairo，Egypt，2000
[13] 曹加恒，张剑，谭辉，赵莉，空间索引的新机制－G树，武汉大学学报（自然科学版），1998，44（1）：49～52
[14] 郭薇，陈军，基于点集拓扑学的三维拓扑空间空间关系形式化描述，测绘学报，1997，
26（2）：122～127
[15] 冯玉才，陈琳，曹忠升，空间数据库的方向关系模型，计算机工程与应用，2001.20：115～117
[16] Hoel, E.G. and H. Samet ．A qualitative comparison study of data structures for large segment databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data．1992，pp. 205-214.
[17]曹菡，师军，李生刚，陈军，点集拓扑理论在拓扑关系描述中的应用，工程数学学报，2001，18（4）：76～82
[18]阎浩文，郭仁忠，空间方向关系基础性问题研究，测绘学报，2002，31（4）：357～360
[19]曹菡，陈军，杜道生，空间目标方向关系的定性扩展描述，测绘学报，2001，30（２）：162～167
[20]曹加恒，赵莉，舒风笛，谭辉，对象管理的空间连接策略与算法，武汉大学学报（自然科学版），1998，44（5）：585～588
[21]顾军，吴长彬，常用空间索引技术的分析，微型电脑应用，2001，17（12）：40～42
[22]Dimitris Papadias and Timos Sellis，“Qualitative Representation of Spatial Knowledge in Two-Dimensional Space”，VLDB Journal,3, 479～516 ，May 1994
[23]Frank Andrew U. Qualitative Spatial Reasoning:Cardinal Directions as An Example[J].INT J Geographical Information Systems,1996,10(3):269～290.
[24]Hoel, E.G. and H. Samet ，A qualitative comparison study of data structures for large segment databases， In Proc. ACM SIGMOD Int. Conf. on Management of Data,,1992，pp. 205～214
[25]Kamel, I. and C. Faloustsos .Hilbert R-tree: An improved R-tree using fractals. In Proc. 20 th Int. Conf. On Very Large Data Bases, 1994 ，pp. 500～509.
[26]陈军，赵仁亮，GIS空间关系的基本问题与研究进展，测绘学报，1999，28（2）：95～103
[27]陈琳，杜友福，王元珍，MBR：基于MBR的空间关系模型，计算机工程与应用，2002，5：76～78
[28]史与正，蒋卫国，曾风山，在GIS软件中的拓扑关系及判定法则，湖南地质，2001.12，20（4）：309～315
[29]李成名，朱英浩，陈军，利用Voronoi图形式化描述和判断GIS中的方向关系，1998，15（2）：117～120
[30]Roussopoulos N ，Leifker，D.Drect Spatial Search on Pictorial Database Using Packed R－trees.ACM SIGMOD Int.Conf.on Management of Data .Austin,Texas,1985．pp:17~31
[31]Egenhofer M．Pre-processing Queries with Spatial Constraints．PE&RS，1994，60（6）：783～970
[32]Florence Ⅲ，John and Egenhofer，Max J．Distribution of Topological Relations in Geographic Datasets．In：ASPRS/ACSM．Annual Convention and Exposition Technical Papers．1996，
315～325
[33]Gold Christopher M．The Meaning of "Neighbor" Lecture Notes in Computer Science 639．Pisa：Springer-Verlag，1992,220～235
[34]胡勇，陈军，基于Voronoi图的空间邻近关系表达和查询操作，中国GIS协会第二届年会论文集，1997，346～356
[35]Zhao Renliang，Chen Jun and Li Zhilin，Voronoi-based Generalized Spatial Adjacency．In：Li Deren，et al．，ed．The processing of RS，GPS，GIS，Their integration and applications．Wuhan Technical University of Surveying and Mapping Press．1998，605～612
[36]Orenstein J A．Spatial query processing in an object-oriented database system[Ａ]．Proc ACM SIGMOD Int Conf on Management of Data[Ｃ]．Washington DC，1986，181～190
[37]Brinkhoff Ｔ，Kriegel H．P，Seeger B．Efficient processing of spatiall joins using R-trees[Ａ]．ACM SIGMOD Int Conf on Management of Data[Ｃ]．1993．237～246
[38]Lo M L，Ravishankar C V．Spatial hash joins[A]ACM SIGMOD Int Conf on Management of Data[Ｃ]．Washington DC，1996，247～258
[39]Lo M L，Ravishankar C V．The design and implementation of seeds trees：an efficient for Spatial joins[J]．IEEE Trans on Knowledge and Data Engineering，1998，10（１），136～152
[40]Peuquet，D．Ci－Xiang，Z．An Algorithm to Determine the Directional Realtionship between Arbitrarily－Shaped Polygons in the Plane．Pattern Recognition，1987，20（1）：65～74
[41]Goyal R．K．Similarity Assessment for Cardinal directions Between Extened Spatial Objects [D]．PHD Thesis，The University of Maine，2000
[42]LiChengming，Voronoi Principles and methods for spatial relation description [M]，Xi' an Map Press，2000
[43]Papadias D，Theodoridis Y．and Sellis T．The Retrieval of Direction Relations using R-trees，Database and Expert Systems Applications [C]．5th International Conference，DEXA'94，Athens，Greece，D．Karagiannis，Ed．Lecture Notes in Computer Science，Springer-Verlag，New York，1994，173～182
[44]史杏荣，孙贞寿，基于固定网格划分和面向类对象的四分树空间索引机制，小型微型计算机系统，1998，19（10）：24～31
[45]J．Patel and D．J．DeWitt．Partition Based Spatial-Merge join．In Proc．ACM SIGMOD Symp．Conf．on Management of Data，1996： 259～270
[46]N．Mamoulis and D．Papadias．Integration of spatiall join algorithms for joining multiple inputs．In Proc．ACM SIGMOD Symp．Conf．on Management of Data，1999
[47]A．Papadopoulos，P．Rigaux，and M．Scholl．A Performance Evaluation of Spatial join
Processing Strategies．In Proc．Intl．Conf．on Large Spatial Databases(SSD)，1999
[48]T．Brinkhoff，H．Kriegel，R．Schneider，and B．Seeger．Multi-step Processing of Spatial join．In Proc．ACM SIGMOD Symp．Conf．on the Management of Data，1994： 197～208
[49]Alexandre A．B．Lima，Cláudio Esperanca，Marta Mattoso．A Parallel Spatial Join Framework Using PMR-Quadtrees．11th International Workshop on Database and Expert Systems Applications (DEXA'00) ， 2000 ：889～893
[50]谈晓军，涂建光，一种自适应的两阶段R树批生成算法，武汉大学学报（信息科学版），2003，28（１）：31～38
[51]Hector Garcia-Molina，Jeffrey D．Ullman，Jennifer Widom 著，《数据库系统实现》（英文版），机械工业出版社，2002.1
[52] Greene, D. An implementation and performance analysis of spatial data access methods. In Proc. 5th IEEE Int. Conf. on Data Eng．1989， pp. 606～615.
[53] Brinkhoff Ｔ，Kriegel H．P，Schncider R．Comparision of Approsimations of Complex Objects Used for Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database system．In Proc．of 9th Int'l conf．Ｏn Data E ngineering,1993
[54] Kamel, I. and C. Faloustsos .On Packing R-tree . In Proc. 2nd Int. Conf. On Information and Management（CIKM）, 1993 ，pp. 490～499.
[55]Leutenegger S T，Edgiyton J M，Lopez M A．STR：A Simple and Efficeent Algorithim for R-tree Packing．In Proc. of the IEEE Int'l Conf. on Data Engineering．1997
[56]Berchtold S B?hm C，Kriegel H P．Improving the Query Performance of High Dimensional Index Structures by Bulk Load Operations．Proc．of the Int．Conf．on Extending Database Technology，Volume 1377 of Lecture Notes in Computer Science．Berlin：Sphinger-Verlag，1998
[57]Dewitt D J，Kabra N，Luo J，et al．Client-server Paradise，The 20th VLDB Conference，Santigo，1994
[58]刘宇，朱仲英，施颂椒，基于直角多边形近似的空间连接查询，上海交通大学学报，2001，35（2）：279～302
[59]Garcia Y J，López M A，Leutenegger S T．A Greedy Algorithm for Bulk Loading R-trees．The 6th ACM International Workshop on Advances in Geographic Information Systems．Washington，1998
[60] Paul Kimmel 著，郭旭、周建明 译，Delphi 6.0 应用开发指南，清华大学出版社，2002.1