Research On The Representation And Management Of Geospatial Data From Volunteered Geographic Information

Online editing and real-time retrieval of vector data are needed by applications of Volunteered Geographic Information (VGI). The performance of existing data management systems in handling these tasks is inferior. Research of novel vector data management technologies is valuable in practice. This dissertation focuses on the multi-scale representation of 2d vector data. Several data structures and algorithms, which support building, querying and updating of multi-scale representation of large scale vector data, are presented.Dividing geospatial data into regions, scales and themes is common in data storage, but is not suitable for VGI applications because of:1. The number of scales is limited. Data from different scales cannot be easily merged.2. Geographic objects are divided into many parts; it is not convenient for applications.3. Map generalizations are performed by human. Data revisions are difficult to propagate to smaller scales.Using relational database to store geographic objects is good because of the gains of ACID features, but has following weakness:1. Reading and writing large geospatial object is slow.2. Relational database hasn't dynamic multi-representation of geospatial objects.3. The updating of an object is as a whole. No incremental updates of objects are supported.4. The performance of spatial queries with large results is poor.Based on the above analysis, data management solutions supporting dynamic multi-scale representation of vector data are presented in this dissertation. Dynamic multi-scale representation of geospatial objects eases the processing of visualizing queries, which include windowing and sampling on the data set. Visualizing query is a special case of 1D or 2D range top k query. Cartesian tree, DBLG-tree(Dynamic Binary Line Generalization tree), CDBLG-tree(Combined Dynamic Binary Line Generalization tree), Zoom quad-tree are used to process the 1D or 2D range top k queries with multiple orders.The main contributions of this dissertation are the sampling queries and visualizing queries, DBLG-tree, CDBLG-tree, Zoom quad-tree and related algorithms. Details are as follows:1) We propose the sampling query and visualizing query, which are two new spatial query types. They are abstraction of geospatial data simplification and windowing, aim to speed up the transmission, visualizing and analysis of geospatial data by limiting the result size of queries. We relate the classic range top k queries (RTKQ) to visualizing queries to locate the essential problem.2) We propose the DBLG-tree on the basis of BLG-tree as a multi-scale representation for geometric object. The visualizing query, which is essentially windowing and simplifying, of the object can be quickly processed in DBLG-tree. The performance of the updating of the DBLG-tree is adjustable. The result of visualizing query is also a binary tree which makes the distributed updating and multi-way merging possible. DBLG-tree solves the 1D range top k queries.3) Instead of representing the networks in nodes and edges, we represent the network in intersecting paths. CDBLG-tree, which is combination of Cartesian tree and DBLG-tree, is proposed to represent a path. we classify the vertices of geospatial objects into two type, topologically significant vertices and geometric vertices. The former are managed by Cartesian trees and the latter by DBLG-tree. CDBLG-tree is efficient in processing visualizing queries with two tolerance value. It solves a special case of 1D range top k queries with two orders.4) We present the Zoom quad-tree, which is an extension of MX-CIF quad-tree. Zoom quad-tree is efficient in processing visualizing queries of geographic features. Vector data pyramid can be built based on CDBLG-tree and Zoom quad-tree.5) We implement a prototype system of VGI application based on the technologies mentioned above. The Global self-consistent, Hierarchical, High-resolution Shoreline Database (GSHHS) are used for test. The prototype allows the real-time data visualization and editing in a web browser. The innovations of this dissertation are listed below:1) We define the operation of sampling a dataset and the parameters which limits the size of results and the error of the results. Visualizing query includes sampling and windowing of dataset, so the building of multi-scale representation of VGI data is converted to the efficient processing of visualizing queries.2) DBLG-tree and related algorithms such as windowing query, sampling query, visualizing query, subtree merging and incremental updating are presented. DBLG-tree is efficient in processing visualizing query of geometric object, hence efficiently solves the 1D range top k query.3) CDBLG-tree and related algorithms such as construction, query processing and updating are presented. It is used to represent the network comprised of many linear geometric objects. topology preserving simplification and updating of the network is achieved using CDBLG-tree.4) Zoom quad-tree is presented to solve the specific 2D range top k queries. The technologies of Building vector data pyramid using zoom quad-tree and CDBLG-tree is also presented.