摘要
本文研究的重点是以万维网地理信息系统(Web Geographical Information System,WEBGIS)中的服务质量(Quality of Service,QoS)问题为出发点,通过对GIS 服务质量因素、缓存和空间索引结构等问题的研究,为进一步系统地研究WEBGIS 中的QoS 问题做铺垫。
万维网地理信息系统是当今GIS 的发展方向,即利用Internet 在Web 上为用户提供空间数据服务。提供服务的目的是满足用户的需求,而服务的QoS 是要针对用户的特点提供满意的服务。对QoS 问题的研究包括建立QoS 的评价体系、用于支持QoS 的技术和建立QoS的技术支持体系等。
本文认为, 万维网地理信息系统将以数据服务中心和专业服务中心为基础为用户提供空间数据服务。从用户的角度,GIS 服务可分为地理空间信息的管理服务、数据服务、处理服务、搜索与导航服务和其它增值服务等。本文探讨了各种万维网地理信息系统服务中的QoS 因素,同时本文探讨了两种保证QoS 的关键技术-空间索引和缓存技术问题。
空间索引技术是本文研究重点,主要研究了R*树、PK 树和Hilbert R 树等有代表性且效率较高的索引结构。总结出从查询效率上来看,PK 树效率最高,Hilbert R 树次之,R*树最差,而PK 树的存储效率不如Hilbert R 树和R*树高。
本文同时研究了在Hilbert R树和PK树基础上建立的平衡PK树索引结构、启发式Hilbert R 树算法、以及探讨利用Voronoi 图的空间概念进一步改进平衡PK 树、启发式Hilbert R 树等比较有创造性的方法。
缓存技术是提高系统性能保证QoS 的另一个重要手段。本文提出了基于缓存技术的数据代理服务器概念,用于在网络环境中提供高性能的区域数据服务,大大增强了GIS 服务器的伸缩性和系统综合性能,可以大大缩小网络负载,缓解网络带宽瓶颈。
最后,本文简要介绍了我们实现的中国地质图书馆网上地图发布平台的体系结构和设计思想,以及Web 应用的问题,然后分析了该地图发布平台的地图显示问题,并总结归纳了WEBGIS 系统在建设过程中的十五个关键因素。
This paper is focusing on QoS for WebGIS. Some important QoS factors in GIS services, such as spatial index structures and cache for improving spatial database in query are analyzed for the sake of QoS in WebGIS.
WebGIS is an important research area, and the idea of “Software as Service”will take an influence on it. The goal of service is to satisfy the needs of users. The QoS issues include establishing a QoS evaluation system, technologies of supporting QoS, establishing a supporting system of QoS technologies etc.
Data Providing Center, Domain Service Center, and User are three key roles in WebGIS. From the viewpoint of users, GIS services are classified into Data Management Service, Data Providing Service, Data Processing Service, Information Searching and Navigating Service, and some other Value-Added Service. The QoS factors of those services are also discussed in the paper.
Spatial index is a key issue in massive geo-data processing. In this paper, R* tree, PK tree and Hilbert R tree are analyzed in detail, and the analysis reveals that for the performance of query, PK tree is the best, Hilbert R tree is the second, and R* tree is the last among the three (PK tree has the worst storage performance).
Balance PK tree and Heuristic Hilbert R tree are analyzed based on the searches of PK tree and Hilbert R tree aiming to improve the performance of query. And with the concepts of Voronoi Map, the paper presents an outstanding method on the spatial index and its related algorithm to re-improve the performance of query.
Cache is another key issue in performance improvement. As the result of the cache theory, this paper issues the concepts of cache-based data proxy. It is used to provide high performance area data service, enhance the flexibility of GIS server and integrated system performance greatly, reduce network load and relieve bottle-neck problem of network bandwidth.
Finally, the architecture and design goals of the mapping distribution system of China Geological Library, which is a WebGIS platform developed by our research group, are presented. Many issues concerning of applying in WedGIS application, including fifteen key technical issues in developing GIS are briefly discussed.
引文
[1] Abel D.J. & Mark D.M. A comparative analysis of some two-dimensional orderings. International Journal of Geographical Information Systems, 1990, 4(1):21-31
[2] Andrew S. Tanenbaum. 分布式操作系统. 清华大学出版社. 1996.
[3] Andrew S. Tanenbaum. 计算机网络. 清华大学出版社. 1996.
[4] Anon et. al. A Measure of Transaction Processing Power, Tandem Technical Report 85.1, Tandem Computers, Cupertino, Ca., August 1985
[5] Antonin Guttman. R-trees: a dynamic index structure for spatial searching. Proc. ACM SIGMOD Conf. on Management of Data, 47-57, 1984.
[6] Arthur R. Butz. Convergence with Hilbert’s space filling curve. Journal of Computer and System Sciences, 3:128–146, 1969.
[7] B. Moon. H.V. Jagadish. C. Faloutsos. J.H. Saltz. Analysis of the Clustering Properties of Hilbert Space-filling Curve. http://www.cs.umd. edu /TR /UMCP-CSD :CS-TR-3611
[8] Ben Teitelbaum , Ted Hanss. QoS Requirements for Internet2 (draft). http ://www.internet2.edu\qos\may98Workshop\html\requirements.html
[9] Bernstain P.A., Hadzilacos V., Goodman N.. Concurrency Control and Recovery in Database System. Addison Wesley. 1987.
[10] Bongki Moon, H.V.Jagadish, Christos Faloutsos, and Joel H.Saltz, Analysis of the Clustering Properties of Hilbert Space-filling Curve, Submitted to IEEE Transactions on Knowledge and Data Engineering, March 1996
[11] BSP Tree Frequently Asked Questions (FAQ). file://www.qualia.com/ pub /bspfaq /bspfaq.txt
[12] C. Faloutsos, K.-I. Lin, Fastmap: a fast algorithms for indexing data-mining and visualization of traditional and multimedia datasets, Proceedings of the ACM SIGMOD International Conference on Management of Data, May 1995, pp. 163-174
[13] Chao-Ju Hou, Ching-Chih Han, Yao-Min Chen. Communication Middleware and Software for QoS Control in Distributed Real-Time Environments. Proceedings of the COMPSAC '97 -21st International Computer Software and Applications Conference. 1997.
[14] Cheng Hian Goh, Agnes Lim, Beng Chin Ooi, Kian-Lee Tan. Efficient indexing of high-dimensional data through dimensional reduction, Data & Knowledge Engineering 32(2000) 115-130
[15] D. A. White and R. Jain, Similarity Indexing with the SS-tree, Proc. of the 12th Int. Conf. on Data Engineering, New Orleans, USA, pp.516-523, Feb. 1996.
[16] D. Hilbert. Uber die stetige Abbildung einer Linie auf Flachenst uck. Math. Annln., 38:459–460, 1891.
[17] E. Bertino et al. Indexing Techniques for Advanced Database Systems. Kluwer Academic Press. Dordrecht. 1997.
[18] Eswaran K., Gray J., Lorie R., Traiger L.. The Notion of Consistency and Predicate Locks in a Database System. ACM, 1976, 19(11):624-632
[19] Faloutsos C. & Roseman S. Fractals for secondary key retrieval. Proceeding of the 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principle of Database Systems. New York: ACM Press, 1989, 247-252
[20] G. Peano. Sur une courbe qui remplit toute une aire plaine. Math. Ann., 36, 1890.
[21] GoAhead. Service Availability: A Customer-Centric Approach to Availability. http://www.goahead.com/sr/pn.wp.219.3 10.00.pdf
[22] Goh CH. Lim A. Ooi BC. Tan KL. Efficient indexing of high-dimensional data through dimensionality reduction. DATA & KNOWLEDGE ENGINEERING 32: (2) 115-130. FEB 2000.
[23] Grag Barish, Katla Obraczka. World Wide Web Caching: Trends and Techniques. IEEE Communications Magazine. 178-185. May 2000.
[24] H.V. Jagadish. Linear clustering of objects with multiple attributes. ACM SIGMOD Conf., pages 332–342, May 1990.
[25] Hans Sagan. A three-dimensional Hilbert-Curve. Inter. J. Math. Ed. Sc. Tech., 24:541–545, 1993.
[26] http://www-4.ibm.com/software/webservers/edgeserver/index.html
[27] Ibrahim Kamel and Christos Faloutsos. Hilbert R-tree: an improved R-tree using fractals. Proc. 20th Intl. Conf. on Very Large Data Bases (VLDB), 500-509, 1994.
[28] IMB Technical Report. Relational Database Technology for enterprise GIS Solutions. http://giswww.pok.ibm.com/gishome.html
[29] J.T.Robinson. The K-D-B tree: a search structure for large multidimensional dynamic indexes. Proc. ACM SIGMOD, pages 10-18, 1981.
[30] Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352. 1990.
[31] Jiong Yang, Wei Wang, and Richard Muntz. Yet another spatial index structure. Submitted to 17th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), 1998. http://dml.cs.cla.edu/eiwang/paper/TR-97040.ps
[32] King-Ip Lin, H.V.Jagadish, and Christos Faloutsos. The TV-tree: an indexing structure for high-dimensional data. VLDB Journal, 3(4):517-542, 1994
[33] M.Abrash .BSP trees. Dr. Dobbs sourcebook, 20(14), 49-53, May/June 1995
[34] M.Stonebraker, J.Frew, K.Gardels, and J.Meredith. The SEQUOIA 2000 storage benchmark, Proc.1994 ACM SIGMOD Int. Conf. Management of Data,pp. 2-11, 1993
[35] Managing Application Services: A Progressive Approach -Manage the Service, Not the Server. http://www.sun.com /software /cluster /wp-sericemgmt /service mgmt -wp.pdf; $sessionid $V5Y2RPYAAB13BAMTA1FU4GQ
[36] Mark E. Easterfield, Richard G. Newell, David G. Theriault. Smallworld GIS: Version Management in GIS –Applications and Techniques. http : //www.swldy.com /english /products/whitepapers/
[37] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. The R*-tree: an efficient and robust access method for points and rectangles. Proc. ACM SIGMOD Conf.
on Management of Data, 322-331, 1990.
[38] Norio Katayama and Shin'ichi Satoh. The SR-tree: an index structure for high-dimensional nearest neighbor queries. Proc. ACM SIGMOD Conf. on Management of Data, 369-380, 1997.
[39] Open GIS Consortium. The OpenGISTM Abstract Specification Topic 12: OpenGISTM Service Architecture. http://www.opengis.org
[40] ORACLE 8i Spatial User’s Guide and Reference. http://www.oracle.com/
[41] Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: an efficient access method for similarity search in metric spaces. Proc. 23rd Intl. Conf. on Very Large Data Bases (VLDB), 426-435, 1997.
[42] Richard G. Newell. Smallworld GIS: The Why and the How of the Long Transaction. http://www.swldy.com/english/products/whitepapers/
[43] Stefan Berchtold, Daniel A. Keim, and Hans-Peter Kriegel. The X-tree : an index structure for high-dimensional data. Proc. 22nd Intl. Conf. on Very Large Data Bases (VLDB), 28-39, 1996.
[44] Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. The R+-tree: a dynamic index for multi-dimensional objects. Proc. 13th Intl. Conf. on Very Large Data Bases (VLDB), 507-518, 1987.
[45] Wei Wang, Jiong Yang, and Richard Muntz. PK-tree: a dynamic spatial index struc-ture for large data sets. UCLA Computer Science Department Technical Report #970039, 1997. http://dml.cs.ucla.edu/ weiwang/paper/TR-97039.ps
[46] 凌小宁. Software as Service. 2001.
[47] 徐冠华, 孙枢. 迎接“数字地球”的挑战. 遥感学报. 1999 年,第3 卷,第2 期
[48] 施伯乐,楼荣生,崔靖,蒋家福. 数据库理论及新理论. 高等教育出版社. 1990.
[49] 陆锋,周成虎. 一种基于Hilbert 排列码的GIS 空间索引方法. 北京. 2000.
[50] 崔伟宏.区域可持续发展决策支持系统研究.北京:宇航出版社,1995
[51] 李伟生,胡启平.大型DIS 的地理数据模型.中国地理信息系统协会首届年会论文集.1995
[52] 龚健雅.GIS 软件的发展趋势与我们的对策.中国地理信息系统协会首届年会论文集.1995
[53] 程承旗,邬伦.发展我国GIS 软件产业的基本思路.中国地理信息系统协会首届年会论文集.1995
[54] 马劲松,黄杏元.微机局域网络上的GIS 客户/服务器模式.中国地理信息系统协会首届年会论文集.1995
[55] 王光启.基于客户/服务器方式的地理信息系统及其实现.中国地理信息系统协会首届年会论文集.1995
[56] 易文根.空间数据库的数据存取:[硕士学位论文].武汉:武汉大学计算机科学与技术学院,1996.5.
[57] 谈国新.一体化空间数据结构及其索引机制研究.测绘学报,1998,27(4):293-299.
[58] 龚健雅.整体SIS的数据组织与处理方法[M].武汉:武汉测绘科技大学出版社,1993.[3]
[59] 崔伟宏.空间数据结构研究[M].北京:中国科学技术出版社,1995.[2]
[60] 郭达志,盛业华,余兆平,等.地理信息系统基础与应用[M].北京:煤炭工业出版社,1997.[4].