基于路网分层的多级搜索算法的研究与实现
|
摘要
近年来,智能交通系统(ITS)、车载GPS定位系统、城市交通诱导系统等相关地理信息系统(GIS)技术的广泛应用对电子地图搜索服务提出了更高的要求。因此,对电子地图搜索及其相关领域的研究已变得炙手可热。
本文研究了电子地图搜索服务中的一个核心议题:最短路径问题求解。拥有海量数据是GIS系统的一个显著特点,合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化,或者是基于少量地图数据的寻径系统的实现;本文则侧重于海量数据下的寻径及其性能优化,提出基于路网分层的多级搜索算法,实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下:
1.提出基于路网分层的多级搜索算法,并比较几种传统寻径算法的优劣,选择了适合GIS中大数据量寻径的A~*算法作为其通用最短寻径算法;
2.将分层思想引入路网数据组织,从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件,并建立路网数据库;
3.通过实验得出了适用于全美寻径系统的A~*算法的估价函数的加权模型;以此为基础提出了基于海量数据下的各种寻径策略,并讨论其具体实现的细节问题;
4.讨论寻径中的必备工具——RTree模块,研究TIGER数据和Shape文件的组织格式;
5.基于前面的研究实现了一个实用高效的寻径系统。
全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法,并且初步实现了全美国的Door2Door寻径系统,证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱,实用性的资料较少,因此本文的研究有较大的理论意义,而且本文已经初步实现了一个寻径系统,因此有着更大的现实意义。
In recent years, the widespread application of the Intelligent Transportation system (ITS), automotive GPS positioning system, Urban Transport system and so on related geographic information system (GIS) technology has set a higher request to the electronic map search service. It is very important to give a research in the electronic map searching and other related fields.
Finding the shortest Path that is one of the key problems in this field has been reasearched in the thesis. Huge Data is a special character of GIS. Extracting, organizing, analyzing and processing the huge data in a good way are the key point of improving the efficiency. Most of the traditional researches focus on the improvement and optimization of routing algorithm, or developing a routing system based on less map data, while this thesis concentrates on another aspect: how to find shortest path on a huge map data, and optimize its performance. Multi-level search algorithm based on hierarchy of road network (MSA-HR) was proposesed. Moreover, a door2door routing system of US was developped as an example based on the algorithm. The thesis mainly does the following work:
1. Put forward MSA-HR, and choose the A~* algorithm available for routing among huge data in GIS by comparing with other traditional routing algorithm as the current algorithm to find shortest route.
2. According to the idea of hierarchy of road network, pick up required information from Map Data through subdivision, combination, simplification, etc. to organization specific road data document to establish a database of road.
3. Obtain weighted model of appraisal function of A~* algorithm available for US routing system through experiment; based on which we put forward various strategies for routing under huge data and discuss details to make it come true.
4. Discuss the RTree module, which is necessary in the routing system, and investigate about the organization manner of TIGER data and document configuration of Shape file.
5. Fulfill a practical and high-efficiency routing system.
The routing in huge data is the mainly sought in the thesis, and some relative algorithm has been proposed, and a US Door2Door routing system has been realized, which can convince the value and feasibility. Research over shortest route under huge data seldom introduced in China, so there is little useful information about routing in huge data. Therefore, this thesis has some theoretical meaning; a routing system has fulfilled, so the thesis has practical meaning also.
本文研究了电子地图搜索服务中的一个核心议题:最短路径问题求解。拥有海量数据是GIS系统的一个显著特点,合理地提取、组织、分析和处理电子地图数据是提高寻径效率的关键。传统最短路径问题的研究更多地注重算法的改进和优化,或者是基于少量地图数据的寻径系统的实现;本文则侧重于海量数据下的寻径及其性能优化,提出基于路网分层的多级搜索算法,实现了全美国的Door2Door(门牌号到门牌号)寻径系统。其主要研究工作如下:
1.提出基于路网分层的多级搜索算法,并比较几种传统寻径算法的优劣,选择了适合GIS中大数据量寻径的A~*算法作为其通用最短寻径算法;
2.将分层思想引入路网数据组织,从地图数据中提取出需要的数据通过分层、合并、简化等方式组织成特定的道路数据文件,并建立路网数据库;
3.通过实验得出了适用于全美寻径系统的A~*算法的估价函数的加权模型;以此为基础提出了基于海量数据下的各种寻径策略,并讨论其具体实现的细节问题;
4.讨论寻径中的必备工具——RTree模块,研究TIGER数据和Shape文件的组织格式;
5.基于前面的研究实现了一个实用高效的寻径系统。
全文主要对GIS寻径问题中海量数据的处理进行了较为深入的探索并提出相应的算法,并且初步实现了全美国的Door2Door寻径系统,证明了理论研究的价值和可行性。目前国内关于大数据量下的最短路径问题的研究还比较薄弱,实用性的资料较少,因此本文的研究有较大的理论意义,而且本文已经初步实现了一个寻径系统,因此有着更大的现实意义。
In recent years, the widespread application of the Intelligent Transportation system (ITS), automotive GPS positioning system, Urban Transport system and so on related geographic information system (GIS) technology has set a higher request to the electronic map search service. It is very important to give a research in the electronic map searching and other related fields.
Finding the shortest Path that is one of the key problems in this field has been reasearched in the thesis. Huge Data is a special character of GIS. Extracting, organizing, analyzing and processing the huge data in a good way are the key point of improving the efficiency. Most of the traditional researches focus on the improvement and optimization of routing algorithm, or developing a routing system based on less map data, while this thesis concentrates on another aspect: how to find shortest path on a huge map data, and optimize its performance. Multi-level search algorithm based on hierarchy of road network (MSA-HR) was proposesed. Moreover, a door2door routing system of US was developped as an example based on the algorithm. The thesis mainly does the following work:
1. Put forward MSA-HR, and choose the A~* algorithm available for routing among huge data in GIS by comparing with other traditional routing algorithm as the current algorithm to find shortest route.
2. According to the idea of hierarchy of road network, pick up required information from Map Data through subdivision, combination, simplification, etc. to organization specific road data document to establish a database of road.
3. Obtain weighted model of appraisal function of A~* algorithm available for US routing system through experiment; based on which we put forward various strategies for routing under huge data and discuss details to make it come true.
4. Discuss the RTree module, which is necessary in the routing system, and investigate about the organization manner of TIGER data and document configuration of Shape file.
5. Fulfill a practical and high-efficiency routing system.
The routing in huge data is the mainly sought in the thesis, and some relative algorithm has been proposed, and a US Door2Door routing system has been realized, which can convince the value and feasibility. Research over shortest route under huge data seldom introduced in China, so there is little useful information about routing in huge data. Therefore, this thesis has some theoretical meaning; a routing system has fulfilled, so the thesis has practical meaning also.
引文
[1]陈述彭,鲁学军,周成虎.地理信息系统导论[M].科学出版社.1999,5
[2]闵连权.地理信息系统的发展动态.地理学与国土研究.2002,18(3):19-23
[3]康志瑜,王明生.GIS发展现状及应用分析.石家庄铁道学院学报.2005,18(1):62-66
[4]Jing Yuan Zhang,Hao Shi.Geospatial Visualization using Google Maps.Second International Multisymposium on Computer and Computational Sciences.2007,9
[5]国家遥感中心.我国地理空间信息技术20年来发展与现状研究报告[R].2002
[6]国家遥感中心.我国地理空间信息技术的需求报告[R].2002
[7]国家遥感中心..面向21世纪空间信息技术的发展趋势以及我国空间信息技术发展对策[R].2002
[8]李春葆.GIS中最短路径搜索算法.计算机科学与工程.2002:70-71
[9]倪凯,叶雷等.基于数据库中间件与GIS实现的最短路径算法.计算机工程.2005,31(13):78-80
[10]宋巨川,李军,张文俊.地理信息系统中建立最短路径的算法[J].上海大学学报(自然科学版).1997,15,Vol3(1):61-63
[11]戴文舟.交通网络中最短路径算法的研究[D].重庆大学硕士毕业论文.2003,10
[12]BV Cherkassky,AV Goldberg,T Radzik.Shortest Paths Algorithms Theory and Experimental Evaluation[J].Technical Report p93-1380.Computer Science Department,Stanford University.1993
[13]FB Zhan.Three Fastest Shortest Path Algorithms on Real Road Networks:Data Structures and Procedures.Journal of Geographic Information and Decision Analysis.1995,1(1):69-82
[14]Fu L,Rilett LR,Expected Shortest Paths in Dynamic and Stochastic Traffic Networks[J].Transportation Research Part B,1998,Vol.32,No.7:399-516
[15]张燕.基于矢量夹角的最短路径分析[D].武汉大学硕士学位论文.2005,5
[16]张福浩,刘纪平,李青元.基于Dijkstra算法的一种最短路径优化算法[J].遥感信息.2004,2:38-41
[17]荣纬.基于道路网的最短路径算法的研究与实现[D].武汉理工大学硕士毕业论文.2005,7
[18]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.1999,3(3)
[19]张连蓬,刘国林,江涛,李云岭,季民.基于先验知识的GIS路径寻优算法.测绘科学[J].2003,9,28(3):27-30
[20]张连蓬,刘国林,江涛,李云岭,季民.GIS路径寻优的方向优先搜索法[J].测绘通报.2003,12:37-39
[21]赵建宏,杨建宇,雷维礼.一种新的最短路径算法[J].电子科技大学学报.2005,12,33(6):778-781
[22]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报.2002,2,23(2):210-215
[23]Soltani A R,Tawfik H,Goulermas J Y,et al.Path planning in construction sites:Performance evaluation of the Dijkstra,a~*,and GA search algorithms[J].Advanced Engineering Informatics.2002:291-303
[24]马道松.动态路径诱导系统中行车路线优化和实施技术研究:[硕士毕业论文].吉林大学,2002.3
[25]孙明雪,蚁群算法的改进及其在TSP问题中的应用[D].吉林大学硕士学位论文.2006,5
[26]陈波,杨阳,郑文军.一种基于道路网分层的最短路径算法.海洋测绘.2006,26(3):21-23
[27]Zhan F B,Noon C E.Shortest path algorithms:An evaluation using real road networks[J].Transportaion,1998,32(1):65-73
[28]陆锋,卢冬梅,崔伟宏.基于四叉堆优先级队列及逆邻接表的改进Dijkstra算法.中国图像图形学报,1994,4A(12):1044-1050
[29]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.1999,24(3):209-212
[30]王杰臣,毛海城,杨得志.图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用.测绘学报.2000,29(1):47-51
[31]Goldberg A V,Harrelson C.Computing the Shortest Path:A~* Search Meets Graph Theroy[R].MSR-TR-2004-24,Microsoft Research,Microsoft Corporation,Redmond,WA,USA,2003
[32]Kaindl H,Kainz G.Bidirectional heuristic search reconsidered[J].Journal of Artificial Intelligence Reasearch,1997,7:283-317
[33]郑年波,李清泉,徐静海等.基于转向限制和延误的双向启发式最短路径算法[J].武汉大学学报(信息科学版),2006,31(3):256-259
[34]陈则王,袁信.基于分层分解的一种实时车辆路径规划算法.南京航空航天大学学报,2003,35(2):193-197
[35]Jagadeesh G R,Srikanthan T.Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks.IEEE Transations Intelligent Transportation Systems,2002,3(3):301-309
[36]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法.北京航空航天大学学报.2002,28(1):70-73
[37]Shan Zhu,Garng M.Huang.A New parallel and Distributed Shortest Path Algorithm for Hierarchically Clustered Data Networks.IEEE Transaction on parallel and distruibuted systems,1998,9,9(9):831-855
[38]J.K.Antonio,G.M.Huang and W.K.Tsai."A Fast DistributedShortest Path Algorithm for a Class of Hierarchically ClusteredData Network".IEEE Trans.Computers.1992,6,41(6):710-723
[39]严蔚敏,吴伟民.数据结构[M].清华大学出版社.1997,3
[40]蔡自兴等.人工智能及其应用[M].清华大学出版社.1996,5
[41]许精明.状态空间的启发式搜索方法研究[J].微机发展.2002,3
[42]高庆吉,于咏生,胡丹丹.基于改进A~*算法的可行性路径搜索及优化[J].中国民航学院学报.2005,3
[43]张前哨.基于A~*算法的地图寻径的研究[D].武汉科技大学硕士毕业论文.2005,5
[44]Marco Pinter.Toward More Realistic Path Finding.Game Developer Magazine(April)[J].CMP Media LLC.2001:53-63
[45]Patrick Lester.A~* Path finding for Beginners.Available at < http://www.policyalmanac.org/games/aStarTutorial.htm>
[46]Game Resource.深入A~*算法[EB/OL].< http://www.gameres.com>.2005
[47]Robert Sedgewick.Algorithms In C++(Part 5):GraphAlgorithrns[M].Person Education,Inc.USA,2002
[48]DUAN Li-qiong,ZHU Jian-jun,WANG Qing-she,MALing.Fast Realization of the Improved A~* Algorithm for Shortest Route.HYDROGRAPHIC SURVEYING ANDCHARTING.2003,9,Vol.23,No.5:20-22
[49]陈玉敏,龚健雅,史文中.多级道路网的最优路径算法研究.武汉大学学报.2006,1,31(1):70-73
[50]Hao Yue,Chunfu Shao.Study on Distributed and Parallel Search Strategy of Shortest Path in Urban Road Network.Thrid International Conference on Natural Computation(ICNC 2007)
[51]LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng.An Optimal Path Algorithm Based onHierarchically Structured Topographical Network.Journalof Image and Graphics.2006,7,Vol.11,No.7:1003-1009
[52]万志杰,杨宇鸿.TIGER空间数据模型及空间数据标准问题探讨.测绘与空间地理信息. 2006,29(3):25-27
[53]白一鸣,李来财.TIGER中地理/人口数据的关联与组织[J].大众科技.2006.2
[54]Geographic Products Management Branch,USA.2003 First Edition TIGER/Line Files Technical Documentation[S].2003
[55]ESRI.ESRI Shapefile Technical Description[S].1998,7
[56]于彩霞,黄文骞,郭立新.Shape数据模型的研究与实践.测绘工程.2007,16(3):39-32
[57]段莉琼.基于城市交通网络的路径分析与应用[D].郑州:解放军信息工程大学,2003
[58]邹旭东,孙刚,王丰元,潘福全.基于数据库动态操作的路径搜寻算法设计与应用
[59]Norbert BeckMann,Hans-Peter Kriegel Ralf Schnerder and Bernhard Seeger.The R~*-Tree:An efficient and robust access method for point s and rectangles[M].Proceedings of ACM Sigmod international conference on Management of data,Atlantic City,New Jersey.1990:322-331
[60]Abraham Silberschatz,Henry Korth,Sudarshan.Database System Concepts Fourth Edition[M].机械工业出版社.2003,3
[61]胡茂胜,刘书良,左泽军.基于R树查询的性能优化[J].软件导刊.2005,22
[62]谢跟踪,苏江文.空间数据索引技术及其在GIS软件中的应用[J].海南师范学院学报(自然科学版).2005,118(3):372-376
[63]Antonin Guttman.R-Trees:A dynamic index structure for spatial searching.Readings in database systems[M].Morgan Kaufmann Publishers Inc.1988.599-609
[2]闵连权.地理信息系统的发展动态.地理学与国土研究.2002,18(3):19-23
[3]康志瑜,王明生.GIS发展现状及应用分析.石家庄铁道学院学报.2005,18(1):62-66
[4]Jing Yuan Zhang,Hao Shi.Geospatial Visualization using Google Maps.Second International Multisymposium on Computer and Computational Sciences.2007,9
[5]国家遥感中心.我国地理空间信息技术20年来发展与现状研究报告[R].2002
[6]国家遥感中心.我国地理空间信息技术的需求报告[R].2002
[7]国家遥感中心..面向21世纪空间信息技术的发展趋势以及我国空间信息技术发展对策[R].2002
[8]李春葆.GIS中最短路径搜索算法.计算机科学与工程.2002:70-71
[9]倪凯,叶雷等.基于数据库中间件与GIS实现的最短路径算法.计算机工程.2005,31(13):78-80
[10]宋巨川,李军,张文俊.地理信息系统中建立最短路径的算法[J].上海大学学报(自然科学版).1997,15,Vol3(1):61-63
[11]戴文舟.交通网络中最短路径算法的研究[D].重庆大学硕士毕业论文.2003,10
[12]BV Cherkassky,AV Goldberg,T Radzik.Shortest Paths Algorithms Theory and Experimental Evaluation[J].Technical Report p93-1380.Computer Science Department,Stanford University.1993
[13]FB Zhan.Three Fastest Shortest Path Algorithms on Real Road Networks:Data Structures and Procedures.Journal of Geographic Information and Decision Analysis.1995,1(1):69-82
[14]Fu L,Rilett LR,Expected Shortest Paths in Dynamic and Stochastic Traffic Networks[J].Transportation Research Part B,1998,Vol.32,No.7:399-516
[15]张燕.基于矢量夹角的最短路径分析[D].武汉大学硕士学位论文.2005,5
[16]张福浩,刘纪平,李青元.基于Dijkstra算法的一种最短路径优化算法[J].遥感信息.2004,2:38-41
[17]荣纬.基于道路网的最短路径算法的研究与实现[D].武汉理工大学硕士毕业论文.2005,7
[18]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.1999,3(3)
[19]张连蓬,刘国林,江涛,李云岭,季民.基于先验知识的GIS路径寻优算法.测绘科学[J].2003,9,28(3):27-30
[20]张连蓬,刘国林,江涛,李云岭,季民.GIS路径寻优的方向优先搜索法[J].测绘通报.2003,12:37-39
[21]赵建宏,杨建宇,雷维礼.一种新的最短路径算法[J].电子科技大学学报.2005,12,33(6):778-781
[22]严寒冰,刘迎春.基于GIS的城市道路网最短路径算法探讨[J].计算机学报.2002,2,23(2):210-215
[23]Soltani A R,Tawfik H,Goulermas J Y,et al.Path planning in construction sites:Performance evaluation of the Dijkstra,a~*,and GA search algorithms[J].Advanced Engineering Informatics.2002:291-303
[24]马道松.动态路径诱导系统中行车路线优化和实施技术研究:[硕士毕业论文].吉林大学,2002.3
[25]孙明雪,蚁群算法的改进及其在TSP问题中的应用[D].吉林大学硕士学位论文.2006,5
[26]陈波,杨阳,郑文军.一种基于道路网分层的最短路径算法.海洋测绘.2006,26(3):21-23
[27]Zhan F B,Noon C E.Shortest path algorithms:An evaluation using real road networks[J].Transportaion,1998,32(1):65-73
[28]陆锋,卢冬梅,崔伟宏.基于四叉堆优先级队列及逆邻接表的改进Dijkstra算法.中国图像图形学报,1994,4A(12):1044-1050
[29]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报.1999,24(3):209-212
[30]王杰臣,毛海城,杨得志.图的节点-弧段联合结构表示法及其在GIS最优路径选取中的应用.测绘学报.2000,29(1):47-51
[31]Goldberg A V,Harrelson C.Computing the Shortest Path:A~* Search Meets Graph Theroy[R].MSR-TR-2004-24,Microsoft Research,Microsoft Corporation,Redmond,WA,USA,2003
[32]Kaindl H,Kainz G.Bidirectional heuristic search reconsidered[J].Journal of Artificial Intelligence Reasearch,1997,7:283-317
[33]郑年波,李清泉,徐静海等.基于转向限制和延误的双向启发式最短路径算法[J].武汉大学学报(信息科学版),2006,31(3):256-259
[34]陈则王,袁信.基于分层分解的一种实时车辆路径规划算法.南京航空航天大学学报,2003,35(2):193-197
[35]Jagadeesh G R,Srikanthan T.Heuristic Techniques for Accelerating Hierarchical Routing on Road Networks.IEEE Transations Intelligent Transportation Systems,2002,3(3):301-309
[36]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法.北京航空航天大学学报.2002,28(1):70-73
[37]Shan Zhu,Garng M.Huang.A New parallel and Distributed Shortest Path Algorithm for Hierarchically Clustered Data Networks.IEEE Transaction on parallel and distruibuted systems,1998,9,9(9):831-855
[38]J.K.Antonio,G.M.Huang and W.K.Tsai."A Fast DistributedShortest Path Algorithm for a Class of Hierarchically ClusteredData Network".IEEE Trans.Computers.1992,6,41(6):710-723
[39]严蔚敏,吴伟民.数据结构[M].清华大学出版社.1997,3
[40]蔡自兴等.人工智能及其应用[M].清华大学出版社.1996,5
[41]许精明.状态空间的启发式搜索方法研究[J].微机发展.2002,3
[42]高庆吉,于咏生,胡丹丹.基于改进A~*算法的可行性路径搜索及优化[J].中国民航学院学报.2005,3
[43]张前哨.基于A~*算法的地图寻径的研究[D].武汉科技大学硕士毕业论文.2005,5
[44]Marco Pinter.Toward More Realistic Path Finding.Game Developer Magazine(April)[J].CMP Media LLC.2001:53-63
[45]Patrick Lester.A~* Path finding for Beginners.Available at < http://www.policyalmanac.org/games/aStarTutorial.htm>
[46]Game Resource.深入A~*算法[EB/OL].< http://www.gameres.com>.2005
[47]Robert Sedgewick.Algorithms In C++(Part 5):GraphAlgorithrns[M].Person Education,Inc.USA,2002
[48]DUAN Li-qiong,ZHU Jian-jun,WANG Qing-she,MALing.Fast Realization of the Improved A~* Algorithm for Shortest Route.HYDROGRAPHIC SURVEYING ANDCHARTING.2003,9,Vol.23,No.5:20-22
[49]陈玉敏,龚健雅,史文中.多级道路网的最优路径算法研究.武汉大学学报.2006,1,31(1):70-73
[50]Hao Yue,Chunfu Shao.Study on Distributed and Parallel Search Strategy of Shortest Path in Urban Road Network.Thrid International Conference on Natural Computation(ICNC 2007)
[51]LI Kai,ZHONG Er-shun,ZENG Zhi-ming and CAO Guo-feng.An Optimal Path Algorithm Based onHierarchically Structured Topographical Network.Journalof Image and Graphics.2006,7,Vol.11,No.7:1003-1009
[52]万志杰,杨宇鸿.TIGER空间数据模型及空间数据标准问题探讨.测绘与空间地理信息. 2006,29(3):25-27
[53]白一鸣,李来财.TIGER中地理/人口数据的关联与组织[J].大众科技.2006.2
[54]Geographic Products Management Branch,USA.2003 First Edition TIGER/Line Files Technical Documentation[S].2003
[55]ESRI.ESRI Shapefile Technical Description[S].1998,7
[56]于彩霞,黄文骞,郭立新.Shape数据模型的研究与实践.测绘工程.2007,16(3):39-32
[57]段莉琼.基于城市交通网络的路径分析与应用[D].郑州:解放军信息工程大学,2003
[58]邹旭东,孙刚,王丰元,潘福全.基于数据库动态操作的路径搜寻算法设计与应用
[59]Norbert BeckMann,Hans-Peter Kriegel Ralf Schnerder and Bernhard Seeger.The R~*-Tree:An efficient and robust access method for point s and rectangles[M].Proceedings of ACM Sigmod international conference on Management of data,Atlantic City,New Jersey.1990:322-331
[60]Abraham Silberschatz,Henry Korth,Sudarshan.Database System Concepts Fourth Edition[M].机械工业出版社.2003,3
[61]胡茂胜,刘书良,左泽军.基于R树查询的性能优化[J].软件导刊.2005,22
[62]谢跟踪,苏江文.空间数据索引技术及其在GIS软件中的应用[J].海南师范学院学报(自然科学版).2005,118(3):372-376
[63]Antonin Guttman.R-Trees:A dynamic index structure for spatial searching.Readings in database systems[M].Morgan Kaufmann Publishers Inc.1988.599-609