CN104063406B - SVG form GIS data rapid comparison methods based on tense - Google Patents

Abstract

The present invention relates to a kind of time-based SVG format GIS data rapid comparison method, comprising the following steps: defining as a node set element; The labeling rule generates a corresponding flip-chip parsing structure tree, and converts it into two comparison arrays with the node set element as a unit to generate a matching node set element set; based on the matching node set element set, sequentially Traverse the flip-chip parsing structure trees of the two timestamps, add a delete operation or an insert operation to the difference script file of the comparison result, save the final obtained difference script file, and complete the comparison. Compared with the prior art, the present invention has the advantages of short matching process, low time complexity and high efficiency.

Description

Temporal-based quick comparison method for GIS data in SVG format

technical field

The present invention is the intersection of computer technology field and geographic information technology field, especially relates to a kind of time-based SVG format GIS data quick comparison method, solves the large-scale (more than 5M) of different time stamps through computer and its algorithm technology research ) Rapid comparison of temporal GIS data in SVG format.

Background technique

The GIS composed of spatial data and attribute data is called static GIS (Static GIS), which is a "snapshot" of the real world, and the research on the changing process and laws of the real world requires GIS to have time characteristics, such as environmental monitoring, The research on GIS that changes with time in the fields of weather forecast, traffic management, surveying and mapping, land survey, etc. is called temporal GIS (temporal GIS). Temporal GIS not only has time characteristics, but also has the characteristics of large amount of data, namely Data is massive. At present, the usual practice of temporal GIS data management is to expand the relational spatio-temporal database, take time as a general attribute, and organize the spatio-temporal database according to the time series, but there are bottlenecks and deficiencies, for example, it is not suitable for the management of massive data and requires engine support and Affect system performance and so on. The object-oriented data model solves some shortcomings of the temporal GIS data model to a certain extent, but OODB (object-oriented database) is still not widely accepted in the market and key application areas, because OODB as a DBMS (database management system) It is also immature, for example, it lacks a completely non-procedural query language, view, authorization, dynamic mode update and parameterized performance coordination, etc., and lacks due compatibility between OODB and RDB (relational database), which makes A large number of established RDB customers dare not choose OODB easily.

Therefore, it is necessary to study the access management of temporal GIS data from other aspects. The introduction of SVG (Scalable Vector Graphics, scalable two-dimensional vector graphics) format has brought infinite vitality to the development of GIS. SVG is a two-dimensional vector graphics format developed by W3C (World Wide Web Consortium, an international Internet standards organization), an open and universal standard. It has the following characteristics:

1) SVG is a fully vector format. SVG supports all operations of vector graphics.

2) SVG is an application standard of XML. Describe geographic information content in text format, easy to edit, and easy to implement a very efficient graphic search engine.

3) It has better compatibility. SVG is easy to integrate in Web pages, and the map in SVG format can be displayed conveniently through the browser.

4) Provide interactive graphics function. Scripts can be used to control the interaction between users and graphics, and script programming can be used to adjust the display parameters of graphics and change the appearance of graphics.

5) SVG supports GZIP compression. The compressed SVGZ can be reduced by 75% to 80%, thereby reducing the network transmission load and speeding up the display speed of the map.

At present, the research and application based on SVG format have been very extensive, but they are mainly concentrated on the presentation layer and the middle layer, and little is involved in the temporal database of temporal GIS. In the prior art, some researchers have mentioned the concept of temporal GIS data management with version increments, the extraction of SVG format data, and the comparison between different SVG format data, laying the foundation for the use of SVG to access temporal GIS data. base. It is a new way to study the incremental access of large-scale temporal GIS data in SVG format, which breaks through the traditional database access management method, but one of the difficulties is to solve the problem of fast access to large-scale GIS data in SVG format with different timestamps. The comparison problem, whether it can be solved reasonably and effectively is the key to the study of temporal GIS data incremental access in SVG format.

The related technologies involved in the rapid comparison of large-scale SVG format GIS data with different time stamps and the problems to be solved include:

1) Understanding of SVG format syntax and expansion of definitions, such as definitions of various geographical elements, nested relationships, etc.

2) Generation and optimization of the inverted structure tree corresponding to large-scale (over 5M) GIS data in SVG format.

3) The generation rules and function definitions of the difference script files that record the comparison results of GIS data in SVG format with different time stamps.

4) Realization of efficient comparison algorithm.

Contents of the invention

The purpose of the present invention is to provide a temporal-based quick comparison method for GIS data in SVG format in order to overcome the above-mentioned defects in the prior art.

The purpose of the present invention can be achieved through the following technical solutions:

A method for quickly comparing GIS data in SVG format based on temporal, comprising the following steps:

1) Consider the element nodes, attribute nodes and text nodes in a certain branch starting from the root node as a whole, and define them as node set elements;

2) Define the labeling rules of the flip-chip parsing structure tree, specifically: capital letters A to Z correspond to the main basic elements of the GIS data in the SVG format;

3) Generate corresponding flip-chip parsing structure trees from the SVG format GIS data of two different timestamps according to the labeling rules, and convert it into two comparison arrays with the node set element as the unit, and one of them The array is sorted, and by traversing the elements in another array, the sorted array is searched in half to generate a set of matching node set elements;

4) Based on the matching node set element set, first traverse the inverted parsing structure tree of the first timestamp, if there is a node that does not belong to the matching node set element set, add a delete operation in the difference script file of the comparison result , and then traverse the inverted parsing structure tree of the second timestamp, if there is a node that does not belong to the matching node set element set, add an insert operation to the difference script file of the comparison result, save the final obtained difference script file, and complete Comparison.

The difference script file is combined with the GIS data in SVG format of the first time stamp to obtain the GIS data in SVG format of the second time stamp

Compared with the prior art, the I-DiffS of the present invention is based on a newly defined node set element and the labeling rule and optimization of the inverted parsing structure tree, by generating a sub-algorithm model I of a matching node set element set -SVG-Match and I-SVG-DiffScript, a sub-algorithm model for generating difference scripts, have the following advantages:

1. The node set elements are defined, which greatly reduces the number of elements corresponding to the inverted parsing structure tree and shortens the matching process.

2. Using the label definition rules based on the inverted parsing structure tree, the original structure tree has been further optimized and the sorting time has been reduced. Based on the definition of the rules of the present invention, the number of nodes of the structure tree after optimization has been reduced by 55% compared with the original inverted structure tree, and compared with the document "Al Ekram R, Adma A, Baysal O.DiffX:An Algorithm to DetectChanges in Multi Version XML Document .2005 Conference of the Center for Advanced Studies on Collaborative Research, Toronto, Canada, 2005" in the DiffX algorithm structure tree node number reduced by 34%, compared with the document "Du Qingfeng, Tang Xuebo. The Improvement of VTDDML Processing Model. IEEE International Conference On Computer Science and Service System, Nanjing, China, 2011", the number of nodes in the optimized structure tree of the DiffS algorithm is reduced by 23%, which solves the problem of too many nodes in the DiffX algorithm and the DiffS algorithm, and the attribute string of each element The sorting and searching time caused by too long is too long.

3. The time complexity is O(n), which is lower than the time complexity O(nlogn) of the existing optimal matching algorithm model DiffS, which is suitable for differential matching of large-scale SVG format GIS data (maps).

4. The difference operation recorded in the comparison script is changed from the original three operations of insert, move and delete to two operations of insert and delete, which greatly improves the efficiency.

Description of drawings

Figure 1 is a schematic diagram of the GIS architecture in SVG format.

detailed description

The present invention will be described in detail below in conjunction with the accompanying drawings and specific embodiments. This embodiment is carried out on the premise of the technical solution of the present invention, and detailed implementation and specific operation process are given, but the protection scope of the present invention is not limited to the following embodiments.

This embodiment provides a method for quickly comparing GIS data in SVG format based on temporal, because large-scale GIS data in SVG format with different timestamps is a complex nested structure, as shown in Figure 1, and in SVG The representation of various geographic elements is complex and diverse, and this method defines rules based on GIS data in SVG format. This method is named after I-DiffS and includes the following steps:

1) The element nodes, attribute nodes and text nodes in a certain branch starting from the root node are regarded as a whole, defined as node set elements, and the number of elements in the comparison array is reduced.

2) Define the labeling rules for the flip-chip parsing structure tree, specifically: the uppercase letters A to Z correspond to the main basic elements of the GIS data in SVG format, and the GIS data in SVG format mainly includes basic graphic element sets, common There are a total of 26 main basic elements in the frame element set and common attribute element set.

3) Generate corresponding flip-chip parsing structure trees from the SVG format GIS data of two different timestamps according to the labeling rules, and convert it into two comparison arrays with the node set element as the unit, and one of them The array is sorted, and by traversing the elements in another array, the sorted array is searched in half to generate a set of matching node set elements.

4) Based on the matching node set element set, first traverse the inverted parsing structure tree of the first timestamp, if there is a node that does not belong to the matching node set element set, add a delete operation in the difference script file of the comparison result , and then traverse the inverted parsing structure tree of the second timestamp, if there is a node that does not belong to the matching node set element set, add an insert operation to the difference script file of the comparison result, save the final obtained difference script file, and complete For comparison, the difference script file is combined with the GIS data in SVG format of the first time stamp to obtain the GIS data in SVG format of the second time stamp

The implementation process of the above method is mainly based on the algorithm model theory. The time complexity of the comparison files based on the above steps is O(n), which is lower than the time complexity O(nlogn) of the existing optimal matching algorithm DiffS, so It is suitable for differential matching of large-scale GIS data in SVG format.

The verification of the method of the present invention adopts an incremental mode strategy, and the data volume of the SVG format GIS data is also increased according to a certain order of magnitude while increasing. Table 1 shows the verification results of DIFFX, DIFFS and I-DIFFS of the present invention according to the order of 10M, 0.1G, 1G and 2G, and the results prove the high efficiency of the method of the present invention.

Table 1 Comparison time statistics of the three methods for different sizes of GIS data in SVG format (unit: second)

Claims (2)

1. A temporal-based SVG format GIS data quick comparison method, is characterized in that, comprises the following steps: 1) Consider the element nodes, attribute nodes and text nodes in a certain branch starting from the root node as a whole, and define them as node set elements; 2) Define the labeling rules for the flip-chip parsing structure tree, specifically: the uppercase letters A to Z correspond to the main basic elements of the GIS data in SVG format, and the GIS data in SVG format mainly includes basic graphic element sets, common There are a total of 26 main basic elements in the frame element set and common attribute element set; 3) Generate corresponding flip-chip parsing structure trees from the SVG format GIS data of two different timestamps according to the labeling rules, and convert it into two comparison arrays with the node set element as the unit, and one of them The array is sorted, and by traversing the elements in another array, the sorted array is searched in half to generate a set of matching node set elements; 4) Based on the matching node set element set, first traverse the inverted parsing structure tree of the first timestamp, if there is a node that does not belong to the matching node set element set, add a delete operation in the difference script file of the comparison result , and then traverse the inverted parsing structure tree of the second timestamp, if there is a node that does not belong to the matching node set element set, add an insert operation to the difference script file of the comparison result, save the final obtained difference script file, and complete Comparison. 2. the temporal-based SVG format GIS data comparison method according to claim 1 is characterized in that, the SVG format GIS data of described difference script file and the first timestamp are combined to obtain the second timestamp GIS data in SVG format.