CN116303434A - Grid R-tree Hybrid Index Construction Method, Retrieval Method and Device - Google Patents

Abstract

The invention discloses a grid R tree-based hybrid index construction method, which comprises the following steps: s1: initializing a grid mixed index data structure by using grid initialization parameters; s2: generating a global grid index partition mapping file, and storing and recording a feature element sequence number and a feature element unique number of each feature element in the global grid index partition mapping file; s3: generating a feature element storage file, and storing and recording feature element information of each feature element in the feature element storage file; s4: judging whether the ground object element is a complex geometric object or not, and splitting the complex geometric object of the ground object element into a plurality of ground object element splitting triangles by adopting a triangulation algorithm; s5: combining the ground feature elements and/or the minimum external rectangle of the ground feature element subdivision triangle and grid initialization parameters to calculate and obtain a grid partition set of the ground feature elements; s6: traversing the grid partition set of the ground object element, and correspondingly establishing an R tree index for each grid partition.

Description

Grid R-tree Hybrid Index Construction Method, Retrieval Method and Device

technical field

The invention relates to the field of information technology, in particular to a method for constructing a hybrid index based on a grid R tree, a retrieval method and a device.

Background technique

In recent years, as geographic information systems have been widely used in the power industry, transportation, meteorological early warning, hydrological monitoring, vehicle logistics, disaster prevention and reduction, agriculture, forestry and fishery, public safety and other fields, the value of spatial data information is particularly reflected in all walks of life. Obviously, the unified storage, centralized management, and efficient access to the accumulated spatial big data have become the key processing technologies for the study of geographic information systems.

At present, due to the large scale of spatial data information, and the diversity and complexity of these spatial data information, the query performance of spatial data is extremely high in the actual application process, and the spatial query performance is used as a measure of spatial data operations. important indicators.

It should be pointed out that the spatial data query technology is mainly to build various spatial indexes to realize the spatial data query operation, so as to meet the high-performance access requirements of spatial data. Among them, the spatial index mainly includes: grid index, KD tree index, quadtree index, R tree index and other types.

However, the inventor found that the traditional spatial index mainly uses a single memory index structure for spatial data management, which can only meet the spatial data access with a small data volume, and the spatial index data structure is fully loaded into the memory. The memory overhead of the method is large, the index building speed is slow, the query efficiency is low, and the actual application effect is not good.

Therefore, the current traditional spatial indexing methods have the following disadvantages:

(1) The traditional single-memory spatial index only supports spatial data with a small data size.

(2) The query efficiency of the traditional single memory space index is low. Spatial data retrieval efficiency is an important indicator of spatial indexing. Due to large-scale and diverse irregular spatial vector data, the spatial distribution is irregular. Using a single two-dimensional tree index structure will lead to a higher index tree height and higher spatial data retrieval costs. Larger, the query will be slower.

(3) The traditional single-memory spatial index loads all the space vector data into the memory, which has a large memory overhead.

(4) The sequential construction speed of the traditional single memory space index is slow. It uses two-dimensional tree index structures such as R tree, quad tree, and KD tree index. The speed of building large-scale spatial data is slow, and it is difficult to carry out parallel construction.

(5) The total number of point sets composed of complex geometric objects is relatively large, generally reaching tens of thousands of points or even more. Using a traditional single memory space index to judge the precise spatial geometric relationship of complex geometric objects requires a lot of CPU computing time.

Contents of the invention

In order to overcome the above-mentioned defects in the prior art, the technical problem to be solved by the present invention is to provide a method for building a hybrid index based on a grid R tree, a retrieval method and a device. It supports the construction of ultra-large-scale spatial vector data indexes, and optimizes the construction process of complex geometric objects by triangulation to reduce memory usage overhead while improving data retrieval performance and enabling efficient spatial data retrieval based on the retrieval range.

In order to solve the above-mentioned technical problems, the first technical solution adopted by the present invention is: a method for constructing a hybrid index based on a grid R tree, which includes the steps of:

S1: Initialize the grid hybrid index data structure by using grid initialization parameters;

S2: Generate a global grid index partition mapping file, and store and record the sequential number of the feature element and the unique number of the feature element in the global grid index partition mapping file;

S3: Generate a feature element storage file, and store and record feature element information of each feature element in the feature element storage file;

S4: Analyze and judge the geometric range parameters, the number of constituent points, and the number of multifaceted holes in the feature element information of each feature element, if the geometric range parameters, constituent points, and the number of multifaceted holes exceed the set If the threshold is fixed, then it is judged that the feature element is a complex geometric object, and the complex geometric object of the feature element is split into several triangles of the feature element by using a triangulation algorithm;

S5: Combining the ground feature elements and/or the minimum circumscribed rectangle of the triangular subdivision of the ground feature elements and the grid initialization parameters to calculate and obtain the grid partition set of the ground feature elements;

S6: Traverse the set of grid partitions of the feature elements, and establish an R-tree index corresponding to each grid partition.

In the grid-based R-tree hybrid index construction method designed by the present invention, the idea of divide and conquer is adopted for storage optimization, and the ultra-large-scale space vector data is partitioned according to the grid first-level index, and each partition corresponds to a storage file , so that each partition file corresponds to an R-tree index. The invention creatively combines the grid index and the R-tree index, effectively exerts the advantages of the two indexes, and the advantages of the mixed index are complementary. Among them, the R-tree index after partition reduces the tree height of only the unique R-tree, reduces the geometric intersection judgment between the query rectangle range and the node rectangle range of more levels, thereby improving the query efficiency.

In addition, in the present invention, by triangulating the complex geometric object, the complex geometric object can be decomposed into a number of simplified triangulations of ground feature elements, so as to improve the precision geometric operation efficiency of the complex object, improve the query efficiency, and reduce the cpu Resource usage.

Comparing the technical solution designed by the present invention with the technical solution in which the traditional spatial index uses a single memory index structure for spatial data management, it is not difficult to see that:

(1) The traditional single-memory spatial index only supports spatial data with a small data size. The grid-based R-tree hybrid index scheme proposed by the present invention can partition massive data through grids, and then independently construct an R-tree index on each partition, so as to meet the requirements of massive space vector data. storage organization management.

(2) The query efficiency of the traditional single memory space index is low. However, this grid-based R-tree hybrid index scheme proposed by the present invention divides multiple R-tree indexes through grids, so that the index rectangle range of each R-tree is controlled within a certain range, reducing the cost of a single tree. The amount of geometric object data reduces the height of the tree, and its tree path is small during the retrieval query, which can quickly obtain the query result set, thereby improving the efficiency of the retrieval query.

(3) The traditional single-memory spatial index loads all the space vector data into the memory, which has a large memory overhead. However, the grid-based R-tree hybrid indexing scheme proposed by the present invention first partitions massive space vector data to reduce the amount of spatial data in each partition, and at the same time builds a disk-based R-tree index to support Relevant spatial data needs to be accessed from disk.

(4) The sequential construction speed of the traditional single memory space index is slow. However, the grid R-tree-based hybrid index scheme proposed by the present invention adopts the first-level grid index for partitioning, and the data size is reduced, and each grid second-level index is independent of each other, and independent index construction can be carried out. It is easy to implement parallel construction of multiple tree index structures at the same time, which can effectively shorten the overall spatial index construction time.

(5) Traditional in-memory spatial indexes are time-consuming for querying complex geometric objects to refine geometric relations. However, the grid R-tree-based hybrid indexing scheme proposed by the present invention specifically performs index construction processing for complex geometric objects, which performs triangulation processing on complex objects, and then constructs indexes. When matching accurately, since complex objects are composed of several simple subdivision triangles of ground features, in most cases the query range only needs to be finely matched with subdivision geometric objects, which can effectively improve query efficiency and reduce cpu computing consumption.

Further, in the grid R-tree-based hybrid index construction method of the present invention, in step S6, an R-tree index is correspondingly established for each grid partition, specifically including the following steps:

S61: Initialize the R-tree index, create an R-tree index file, and set the maximum node number N of R-tree nodes;

S62: When inserting the R-tree index file, firstly select the appropriate path for inserting the feature element index item starting from the root node, perform geometric relationship calculation on the minimum circumscribing rectangle of the feature element and the rectangular range of each node, and find a path from The insertion path from the root node to the leaf node;

S63: Insert the feature element index item into the leaf node of the insertion path in an additional manner;

S64: If the number of nodes of the leaf node is full, that is, exceeds the maximum number of nodes N of the R tree node, the leaf node will be split into two nodes, and the whole process is followed by the leaf node along the insertion path from bottom to top Propagate to the root node; if the root node splits, the entire R-tree index will increase by one layer.

Further, in the grid R tree-based hybrid index construction method according to the present invention, in step S1, according to grid minimum longitude grid_minx, grid minimum latitude grid_miny, grid maximum longitude grid_maxx, grid maximum latitude grid_maxy, The grid size grid_cellsize, the number of grid rows grid_rows, and the number of grid columns grid_columns initialize the grid hybrid index data structure.

Further, in the method for constructing a hybrid index based on a grid R-tree according to the present invention, in step S2, the sequence numbers of the feature elements are incrementally generated according to the integer sequence numbers starting from 1 when the feature element index is constructed, The unique number of the feature element is a character string uniquely identifying the feature element.

Further, in the method for constructing a hybrid index based on a grid R tree according to the present invention, in step S3, the feature element information includes feature element spatial attribute information and feature element entity attribute information, and the feature element The spatial attribute information of the feature includes the shape of the geometric object of the feature element, and the entity attribute information of the feature element includes the unique number identification of the feature element and the name of the feature element.

In order to solve the above technical problems, the second technical solution adopted by the present invention is: a retrieval method based on a grid R tree hybrid index, the grid R tree hybrid index is based on the grid R tree described in any one of the above The tree hybrid index construction method is constructed, and the grid R tree hybrid index retrieval method based on the present invention specifically includes steps:

100: According to the shape of the input geometric object, calculate the smallest circumscribed rectangle of the geometric object as the query rectangular range of the spatial data;

200: Combining with the grid initialization parameters, calculate the grid partition set where the query rectangle range is located;

300: Traverse the set of grid partitions, load the R-tree index corresponding to the grid partition, and perform a spatial search operation on the R-tree index corresponding to the grid partition in parallel according to the scope of the query rectangle, so as to collect each R-tree The result set of the index, and remove the sequence numbers of the repeated feature elements in the result set, and merge them into a result set of candidate feature element numbers;

400: Traversing the result set of candidate feature element numbers, obtaining the unique number of each feature element from the relationship of the global grid index partition mapping file, and then obtaining the corresponding feature element number from the feature element storage file Feature information to form a complete result set of candidate feature features;

500: Traverse the result set of candidate feature elements, obtain the candidate feature elements screened out by triangulation of the feature elements, and perform precise geometric intersection judgments on the geometric object shapes of other feature elements and the shape of the input geometric object to filter out the intersection The result set of feature elements, the candidate feature elements screened out by the triangulation of the feature elements are directly added to the result set of intersecting feature elements, so as to generate the final result set of feature elements.

Further, in the grid R tree-based hybrid index retrieval method of the present invention, in the above step 100, the minimum circumscribed rectangle of the geometric object is composed of the lower left corner point and the upper right corner point information, which includes the minimum longitude query_minX , minimum latitude query_minY, maximum longitude query_maxX and maximum latitude query_maxY.

Further, in the grid R tree-based hybrid index retrieval method of the present invention, in the above step 200, the calculated minimum grid X-direction number cell_minx, The minimum grid number cell_miny in the Y direction, the maximum grid number cell_maxx in the X direction, and the maximum grid number cell_maxy in the Y direction obtain the grid partition set of the grid area.

Further, in the grid R-tree-based hybrid index retrieval method of the present invention, in the above step 300, the spatial retrieval operation is performed on the R-tree index corresponding to the grid partition in parallel according to the scope of the query rectangle, so as to Collecting the result set of each R-tree index specifically includes the following steps 301-302:

301: Start to query and match from the root node of the R-tree index, and determine the geometric intersection between the query rectangle range and the root node. All child nodes perform geometric intersection judgment;

302: Traverse the R-tree index according to the depth-first algorithm, iteratively traverse each branch of the R-tree index until the leaf nodes, and collect the leaf node result sets with intersections;

303: After removing duplications from all the result sets acquired by the retrieval, merge them into a result set corresponding to the R tree.

In order to solve the above-mentioned technical problems, the third technical solution adopted by the present invention is: a retrieval device based on grid R-tree hybrid index construction, which includes:

An index metadata module, the index metadata module is used to record the basic data information of the grid R-tree hybrid index, and the basic data information includes grid initialization parameter information and R-tree parameter information;

A triangulation module, the triangulation module is used to judge whether the feature element is a complex geometric object, and perform triangulation on the complex geometric object, so as to divide the complex geometric object of the feature element into several feature elements Divide the triangle;

A grid index module, the grid index module is used to calculate the grid index of feature elements, and generate a grid index structure according to the index metadata information;

R tree index module, the R tree index module is used to realize the generation and loading of R tree index files, and provide the data node insertion algorithm and R tree space query algorithm of R tree index;

A global grid index partition module, the global grid index partition module is used to realize the generation and loading of the global grid index partition mapping file, and provide the function of establishing the mapping relationship between the sequence number of the feature element and the unique number of the feature element;

The feature element storage module, the feature element storage module is used to realize the generation and loading of the feature element storage file, provide the basic attribute information storage of the feature element, the serialization of the spatial geometric object of the feature element and the feature element Serialized storage function of related attribute information;

Query data preprocessing module, the query data preprocessing module is used to realize the data preprocessing of the input geometric object, generate the corresponding minimum circumscribed rectangle according to the element type of the geometric object, and call the grid index module and the R tree index module to realize the spatial retrieval ;

A query result set generation module, the query result set generation module is capable of merging query candidate feature element result sets, and performing precise geometric matching on query input geometric objects and candidate result sets to generate a final feature element result set.

The beneficial effects of the present invention are: the scheme design of the grid R-tree-based hybrid index construction method, retrieval method and device designed by the present invention is simple, and it constructs a first-level grid index partition for large-scale space vector data, and then Construct a disk-based secondary R-tree index for each grid index partition to achieve index storage of massive spatial vector data, and provide an efficient hybrid index spatial query method, which can meet the high-performance spatial vector data access requirements.

The present invention creatively combines the grid index and the R-tree index to effectively utilize the advantages of the two indexes, and the advantages of the hybrid index are complementary, so as to use the hybrid index construction method to support the construction of a super-large-scale space vector data index; in addition, the present invention also aims at Complex geometric objects are triangulated to optimize the construction process. Based on the combination of internal and external memory, it can perform efficient spatial data retrieval according to the retrieval range, so as to reduce memory usage overhead and improve data retrieval performance.

Description of drawings

Fig. 1 is a flow chart of steps in an embodiment of a method for constructing a hybrid index based on a grid R tree according to the present invention;

FIG. 2 is a schematic structural diagram of a grid R-tree hybrid index data structure according to the present invention.

Fig. 3 is a flow chart of steps in an embodiment of a grid-based R-tree hybrid index retrieval method according to the present invention;

Fig. 4 is a schematic diagram of the functional modules of the retrieval device based on the grid R-tree hybrid index construction in an implementation manner according to the present invention.

Detailed ways

In order to describe the technical content, achieved goals and effects of the present invention in detail, the following descriptions will be made in conjunction with the embodiments and accompanying drawings.

Please refer to Fig. 1 and Fig. 2, in this embodiment, the present invention designs a method for constructing a hybrid index based on a grid R tree, which includes steps:

S1: Initialize the grid hybrid index data structure by using grid initialization parameters;

S2: Generate a global grid index partition mapping file, and store and record the sequential number of the feature element and the unique number of the feature element in the global grid index partition mapping file;

S3: Generate a feature element storage file, and store and record feature element information of each feature element in the feature element storage file;

S4: Analyze and judge the geometric range parameters, the number of constituent points, and the number of multifaceted holes in the feature element information of each feature element, if the geometric range parameters, constituent points, and the number of multifaceted holes exceed the set If the threshold is fixed, then it is judged that the feature element is a complex geometric object, and the complex geometric object of the feature element is split into several triangles of the feature element by using a triangulation algorithm;

S5: Combining the ground feature elements and/or the minimum circumscribed rectangle of the triangular subdivision of the ground feature elements and the grid initialization parameters to calculate and obtain the grid partition set of the ground feature elements;

S6: Traverse the set of grid partitions of the feature elements, and establish an R-tree index corresponding to each grid partition.

Referring to Fig. 1, combined with the grid R-tree hybrid index data structure shown in Fig. 2, it is not difficult to see that the most critical idea of the present invention is: by constructing a first-level grid index partition for large-scale space vector data, and then Each grid index partition builds a disk-based secondary R-tree index to realize the index storage of massive spatial vector data, so as to provide an efficient hybrid index spatial query method and meet the high-performance spatial vector data access requirements.

As shown in Figure 1, the inventor creates a first-level grid index partition for the feature elements and/or the triangulation of the feature elements, and writes the feature elements and/or the triangulation triangles of the feature elements into the relevant associated grid index file , so that each partition corresponds to a storage file, so that each partition storage file corresponds to an R-tree index, and then write the feature element index items into the secondary R-tree index file to construct each grid index partition Disk-based secondary R-tree index.

In addition, in the present invention, by triangulating the complex geometric object, the complex geometric object can be decomposed into a number of simplified triangulations of ground feature elements, so as to improve the precision geometric operation efficiency of the complex object, improve the query efficiency, and reduce the cpu Resource usage. Wherein, in step S4, the several subdivided triangles of feature elements based on the complex geometric object of feature elements can be used for subsequent query operation optimization, and all the subdivided triangles of feature elements can become index objects, and can be combined with Associated with original features.

In addition, it should also be noted that the grid R-tree-based hybrid index construction method designed by the present invention may also include step S7: After writing the feature element information of all feature elements into the R-tree index file, refresh and save file, and write it persistently to the local disk.

When implementing the application, each R-tree index file can be named after the X-direction and Y-direction grid numbers, and the file saved in the above step S7 can be specifically named as R{cell_row}_{cell_column}.idx; wherein, cell_row is the grid number The row number in the Y direction of the grid, and cell_column is the column number in the X direction of the grid.

Further, in step S6, an R-tree index is correspondingly established for each grid partition, specifically including the following steps:

S61: Initialize the R-tree index, create an R-tree index file, and set the maximum node number N of R-tree nodes;

S62: When inserting the R-tree index file, firstly select the appropriate path for inserting the feature element index item starting from the root node, perform geometric relationship calculation on the minimum circumscribing rectangle of the feature element and the rectangular range of each node, and find a path from The insertion path from the root node to the leaf node;

S63: Insert the feature element index item into the leaf node of the insertion path in an additional manner;

S64: If the number of nodes of the leaf node is full, that is, exceeds the maximum number of nodes N of the R tree node, the leaf node will be split into two nodes, and the whole process is followed by the leaf node along the insertion path from bottom to top Propagate to the root node; if the root node splits, the entire R-tree index will increase by one layer.

In step S6 designed by the present invention, it is necessary to traverse the grid partition set of feature elements, and establish an R-tree index for each grid partition. Among them, the R-tree index can be constructed in parallel according to the grid partition specifically for the surface feature element and/or the triangular data of the surface feature element, so as to first prepare the data structure initialization for the uninitialized grid partition R-tree index, and then according to the R The tree insertion algorithm inserts feature features into disk-based R-tree index files.

Further, in step S1, according to grid minimum longitude grid_minx, grid minimum latitude grid_miny, grid maximum longitude grid_maxx, grid maximum latitude grid_maxy, grid size grid_cellsize, grid row number grid_rows, grid column number grid_columns initialization Grid hybrid index data structure.

It should be noted that, in this embodiment, in the above-mentioned step S1 of the present invention, the grid minimum longitude grid_minx, the grid minimum latitude grid_miny, the grid maximum longitude grid_maxx, the grid maximum latitude grid_maxy, and the grid size can be specified. grid_cellsize, the number of grid rows grid_rows, and the number of grid columns grid_columns initialize the grid index structure to divide the given geographic space into grids of the same size; each grid data structure can specifically include : R-tree data structure of enclosing rectangle, X-direction grid number, Y-direction grid number, and grid-associated secondary index.

Further, in step S2, the sequence number of the feature element is generated incrementally according to the integer serial number starting from 1 when the feature element index is constructed, and the unique number of the feature element is a character string uniquely identified by the feature element.

In the step S2 of the present invention, the sequential numbering of the feature elements and the unique numbering of the feature elements can be written into the global grid index partition mapping file through the LSM algorithm. The sequence number of the object element is the key value, and the unique number information of the object element is the storage content.

Further, in step S3, the feature element information includes the feature element spatial attribute information and the feature element entity attribute information, the feature element spatial attribute information includes the feature element geometric object shape, and the feature element Entity attribute information includes the unique number identification of feature elements and the name of feature elements.

In the grid R-tree-based hybrid index construction method designed by the present invention, the geometric object shape of feature elements included in the spatial attribute information, the geometric object shape of feature elements can specifically include: point shape, line shape, surface Three types of shapes. In the present invention, the minimum circumscribed rectangle of the corresponding feature element can be further calculated based on the shape of the geometric object of the feature element.

It should be noted that, in this embodiment, in step S3 of the present invention, the feature element information can be specifically written into the feature element storage file through the LSM algorithm, and in the feature element storage file, the feature element information can be The unique number of the feature is the key value, and the storage content of the feature feature storage file can specifically include: the unique number of the feature feature, the name of the feature feature, the shape of the geometric object of the feature feature, and the minimum circumscribed rectangle of the feature feature.

In addition, it should be noted that in this embodiment, in the above step S5, the minimum circumscribing rectangle of the feature element or the subdivided triangle is composed of the lower left corner point and the upper right corner point information, which may specifically include the minimum longitude minX , minimum latitude minY, maximum longitude maxX and maximum latitude maxY. The minimum grid X-direction number cell_minx, the minimum grid Y-direction number cell_miny, the maximum grid X-direction number cell_maxx, and the maximum grid Y-direction number cell_maxy can be calculated based on the above information.

In the specific calculation process, the mathematical function math.Ceil needs to be used in the calculation formula. The calculation formula of each data is as follows:

cell_minx=math.Ceil(minX-grid_minx)/grid_cellsize-1

Calculate the minimum grid Y direction number formula:

cell_miny=math.Ceil(minY-grid_miny)/grid_cellsize-1

The formula for calculating the maximum grid number in the X direction:

cell_maxx=math.Ceil(maxX-grid_maxx)/grid_cellsize-1

The formula for calculating the maximum grid number in the Y direction:

cell_maxy=math.Ceil(maxY-grid_maxy)/grid_cellsize-1

The minimum grid X-direction number cell_minx, the minimum grid Y-direction number cell_miny, the maximum grid X-direction number cell_maxx, and the maximum grid Y-direction number cell_maxy of the grid area spanned by the calculated ground object elements or subdivision triangles, The corresponding grid partition set can be obtained.

Correspondingly, referring to Fig. 3, the present invention designs a retrieval method based on grid R tree hybrid index, the grid R tree hybrid index used in the grid R tree hybrid index retrieval method is according to the present invention The above-mentioned grid R-tree-based hybrid index construction method is constructed.

In the present invention, the hybrid index retrieval method based on the grid R tree described in the present invention specifically includes steps:

100: According to the shape of the input geometric object, calculate the smallest circumscribed rectangle of the geometric object as the query rectangular range of the spatial data;

200: Combining with the grid initialization parameters, calculate the grid partition set where the query rectangle range is located;

300: Traverse the set of grid partitions, load the R-tree index corresponding to the grid partition, and perform a spatial search operation on the R-tree index corresponding to the grid partition in parallel according to the scope of the query rectangle, so as to collect each R-tree The result set of the index, and remove the sequence numbers of the repeated feature elements in the result set, and merge them into a result set of candidate feature element numbers;

400: Traverse the result set of candidate feature element numbers, obtain the unique number of each feature element from the relationship of the global grid index partition mapping file, and then obtain the corresponding feature element number from the feature element storage file Feature information to form a complete result set of candidate feature features;

500: Traverse the result set of candidate feature elements, obtain the candidate feature elements screened out by triangulation of the feature elements, and perform precise geometric intersection judgments on the geometric object shapes of other feature elements and the shape of the input geometric object to filter out the intersection The result set of feature elements, the candidate feature elements screened out by the triangulation of the feature elements are directly added to the result set of intersecting feature elements, so as to generate the final result set of feature elements.

It should be noted that, in this embodiment, in the above step 300, the grid partition set is traversed, and the R index tree corresponding to the grid partition can be loaded according to the index file name R{cell_row}_{cell_column}.idx rule. Among them, the spatial retrieval operation is performed on the grid partition R-tree index in parallel according to the input query rectangle range. In the process of R-tree indexing, the feature element (that is, it is judged that the feature element is not a complex geometric object) or the feature element is divided into triangles (that is, it is judged that the feature element is a complex geometric object, and the triangulation algorithm is used to divide the triangular element into a triangle). The complex geometric object of the ground feature element is split into several ground feature elements and divided into triangles) for retrieval, and the results obtained by dividing the triangle are identified. For the triangle divided by the same ground feature element, as long as there is a triangle and a query rectangle If there is a geometric intersection in the range, the corresponding feature elements will be added to the query result set and identified.

In the above-mentioned retrieval method based on grid R-tree hybrid index of the present invention, the feature element information mentioned in step 400 may specifically include feature element spatial attribute information and feature element entity attribute information.

Further, in the above step 100, the minimum circumscribed rectangle of the geometric object is composed of lower left corner point and upper right corner point information, which includes minimum longitude query_minX, minimum latitude query_minY, maximum longitude query_maxX and maximum latitude query_maxY.

Further, in the above step 200, the calculated minimum grid X-direction number cell_minx, minimum grid Y-direction number cell_miny, maximum grid X-direction number cell_maxx, maximum grid X-direction number cell_maxx, and maximum Cell_maxy is the cell_maxy number in the Y direction of the grid, and the grid partition set of the grid area is obtained.

It should be noted that, in the above step 200, the minimum grid X-direction number cell_minx, the minimum grid Y-direction number cell_miny, the maximum grid X-direction number cell_maxx, the maximum When cell_maxy is numbered in the Y direction of the grid, the math function math.Ceil needs to be used in the calculation formula. The calculation formula of each data is as follows:

Calculate the minimum grid X direction number formula:

cell_minx=math.Ceil(query_minX-grid_minx)/grid_cellsize-1

Calculate the minimum grid Y direction number formula:

cell_miny=math.Ceil(query_minY-grid_miny)/grid_cellsize-1

The formula for calculating the maximum grid number in the X direction:

cell_maxx=math.Ceil(query_maxX-grid_maxx)/grid_cellsize-1

The formula for calculating the maximum grid number in the Y direction:

cell_maxy=math.Ceil(query_maxY-grid_maxy)/grid_cellsize-1

Further, in the above step 300, according to the scope of the query rectangle, the spatial retrieval operation is carried out on the R-tree index of the corresponding grid partition in parallel to collect the result set of each R-tree index, specifically including the following steps 301-303 :

301: Start to query and match from the root node of the R-tree index, and determine the geometric intersection between the query rectangle range and the root node. All child nodes perform geometric intersection judgment;

302: Traverse the R-tree index according to the depth-first algorithm, iteratively traverse each branch of the R-tree index until the leaf nodes, and collect the leaf node result sets with intersections;

303: After removing duplications from all the result sets acquired by the retrieval, merge them into a result set corresponding to the R tree.

In addition, further referring to FIG. 4, it can be seen that the present invention also designs a retrieval device based on a grid R-tree hybrid index, which is used to implement the above retrieval method based on a grid R-tree hybrid index.

As shown in Figure 4, in this embodiment, the retrieval device based on the grid R-tree hybrid index designed by the present invention may specifically include:

An index metadata module, the index metadata module is used to record the basic data information of the grid R-tree hybrid index, the basic data information includes grid initialization parameter information and R-tree parameter information; wherein, the grid initialization parameter information can be Including grid minimum longitude grid_minx, grid minimum latitude grid_miny, grid maximum longitude grid_maxx, grid maximum latitude grid_maxy, grid size grid_cellsize, grid row number grid_rows, grid column number grid_columns; R tree parameter information can include R tree File name, the maximum number of nodes N of R tree nodes;

A triangulation module, the triangulation module is used to judge whether the feature element is a complex geometric object, and perform triangulation on the complex geometric object, so as to divide the complex geometric object of the feature element into several feature elements Divide the triangle;

A grid index module, the grid index module is used to calculate the grid index of feature elements, and generate a grid index structure according to the index metadata information;

R tree index module, the R tree index module is used to realize the generation and loading of R tree index files, and provide the data node insertion algorithm and R tree space query algorithm of R tree index;

A global grid index partition module, the global grid index partition module is used to realize the generation and loading of the global grid index partition mapping file, and provide the function of establishing the mapping relationship between the sequence number of the feature element and the unique number of the feature element;

The feature element storage module, the feature element storage module is used to realize the generation and loading of the feature element storage file, provide the basic attribute information storage of the feature element, the serialization of the spatial geometric object of the feature element and the feature element Serialized storage function of related attribute information;

Query data preprocessing module, the query data preprocessing module is used to realize the data preprocessing of the input geometric object, generate the corresponding minimum circumscribed rectangle according to the element type of the geometric object, and call the grid index module and the R tree index module to realize the spatial retrieval ;

A query result set generation module, the query result set generation module is capable of merging query candidate feature element result sets, and performing precise geometric matching on query input geometric objects and candidate result sets to generate a final feature element result set.

To sum up, in the present invention, the inventor adopts the idea of divide and conquer for storage optimization. By partitioning the ultra-large-scale space vector data according to the first-level grid index, each partition corresponds to a storage file, so that each partition file Corresponds to an R-tree index. The inventor creatively combines the grid index and the R-tree index to effectively utilize the advantages of the two indexes, and the advantages of the hybrid index are complementary. Among them, the R-tree index after partition reduces the tree height of only the unique R-tree, reduces the geometric intersection judgment between the query rectangle range and the node rectangle range of more levels, thereby improving the query efficiency.

In addition, in the present invention, by triangulating the complex geometric object, the complex geometric object can be decomposed into a number of simplified triangulations of ground feature elements, so as to improve the precision geometric operation efficiency of the complex object, improve the query efficiency, and reduce the cpu Resource usage.

The above description is only an embodiment of the present invention, and does not limit the patent scope of the present invention. All equivalent transformations made by using the description of the present invention and the contents of the accompanying drawings, or directly or indirectly used in related technical fields, are all included in the same principle. Within the scope of patent protection of the present invention.

Claims (10)

1. A method for constructing a hybrid index based on grid R tree, characterized in that, comprising steps: S1: Initialize the grid hybrid index data structure by using grid initialization parameters; S2: Generate a global grid index partition mapping file, and store and record the sequential number of the feature element and the unique number of the feature element in the global grid index partition mapping file; S3: Generate a feature element storage file, and store and record feature element information of each feature element in the feature element storage file; S4: Analyze and judge the geometric range parameters, the number of constituent points, and the number of multifaceted holes in the feature element information of each feature element, if the geometric range parameters, constituent points, and the number of multifaceted holes exceed the set If the threshold is fixed, then it is judged that the feature element is a complex geometric object, and the complex geometric object of the feature element is split into several triangles of the feature element by using a triangulation algorithm; S5: Combining the ground feature elements and/or the minimum circumscribed rectangle of the triangular subdivision of the ground feature elements and the grid initialization parameters to calculate and obtain the grid partition set of the ground feature elements; S6: Traverse the set of grid partitions of the feature elements, and establish an R-tree index corresponding to each grid partition. 2. The grid-based R-tree hybrid index construction method according to claim 1, wherein in step S6, an R-tree index is correspondingly established for each grid partition, specifically comprising the following steps: S61: Initialize the R-tree index, create an R-tree index file, and set the maximum node number N of R-tree nodes; S62: When inserting the R-tree index file, firstly select the appropriate path for inserting the feature element index item starting from the root node, perform geometric relationship calculation on the minimum circumscribing rectangle of the feature element and the rectangular range of each node, and find a path from The insertion path from the root node to the leaf node; S63: Insert the feature element index item into the leaf node of the insertion path in an additional manner; S64: If the number of nodes of the leaf node is full, that is, exceeds the maximum number of nodes N of the R tree node, the leaf node will be split into two nodes, and the whole process is followed by the leaf node along the insertion path from bottom to top Propagate to the root node; if the root node splits, the entire R-tree index will increase by one layer. 3. The method for constructing a hybrid index based on grid R-tree according to claim 1, characterized in that, in step S1, according to grid minimum longitude grid_minx, grid minimum latitude grid_miny, grid maximum longitude grid_maxx, grid maximum Latitude grid_maxy, grid size grid_cellsize, grid row number grid_rows, grid column number grid_columns initialize the grid hybrid index data structure. 4. The method for constructing a hybrid index based on grid R tree according to claim 1, characterized in that, in step S2, the sequential numbering of the feature elements starts from 1 according to the integer sequence number when the feature element index is constructed Incrementally generated, the unique number of the feature element is a character string uniquely identified by the feature element. 5. The hybrid index construction method based on grid R tree according to claim 1, wherein in step S3, the feature element information includes feature element spatial attribute information and feature element entity attribute information, so The spatial attribute information of the feature element includes the geometric object shape of the feature element, and the entity attribute information of the feature element includes the unique number identification of the feature element and the name of the feature element. 6. A retrieval method based on a grid R-tree hybrid index, the grid R-tree hybrid index is constructed according to any one of claims 1-5 based on a grid R-tree hybrid index construction method, characterized in that , including the steps: 100: According to the shape of the input geometric object, calculate the smallest circumscribed rectangle of the geometric object as the query rectangular range of the spatial data; 200: Combining with the grid initialization parameters, calculate the grid partition set where the query rectangle range is located; 300: Traverse the set of grid partitions, load the R-tree index corresponding to the grid partition, and perform a spatial search operation on the R-tree index corresponding to the grid partition in parallel according to the scope of the query rectangle, so as to collect each R-tree The result set of the index, and remove the sequence numbers of the repeated feature elements in the result set, and merge them into a result set of candidate feature element numbers; 400: Traversing the result set of candidate feature element numbers, obtaining the unique number of each feature element from the relationship of the global grid index partition mapping file, and then obtaining the corresponding feature element number from the feature element storage file Feature information to form a complete result set of candidate feature features; 500: Traverse the result set of candidate feature elements, obtain the candidate feature elements screened out by triangulation of the feature elements, and perform precise geometric intersection judgments on the geometric object shapes of other feature elements and the shape of the input geometric object to filter out the intersection The result set of feature elements, the candidate feature elements screened out by the triangulation of the feature elements are directly added to the result set of intersecting feature elements, so as to generate the final result set of feature elements. 7. The hybrid index retrieval method based on grid R tree according to claim 6, characterized in that, in the above step 100, the minimum circumscribed rectangle of the geometric object is composed of the lower left corner point and the upper right corner point information, which includes Minimum longitude query_minX, minimum latitude query_minY, maximum longitude query_maxX, and maximum latitude query_maxY. 8. The hybrid index retrieval method based on grid R tree according to claim 6, characterized in that, in the above step 200, the minimum grid X direction of the grid area spanned by the calculated query rectangle range Number cell_minx, minimum grid number cell_miny in the Y direction, maximum grid number cell_maxx in the X direction, and maximum grid number cell_maxy in the Y direction to obtain the grid partition set of the grid area. 9. The grid-based R-tree hybrid index retrieval method according to claim 6, characterized in that, in the above step 300, the spatial retrieval is performed on the R-tree index corresponding to the grid partition in parallel according to the scope of the query rectangle The operation is to collect the result set of each R-tree index, which specifically includes the following steps 301-302: 301: Start to query and match from the root node of the R-tree index, and determine the geometric intersection between the query rectangle range and the root node. All child nodes perform geometric intersection judgment; 302: Traverse the R-tree index according to the depth-first algorithm, iteratively traverse each branch of the R-tree index until the leaf nodes, and collect the leaf node result sets with intersections; 303: After removing duplications from all the result sets acquired by the retrieval, merge them into a result set corresponding to the R tree. 10. A retrieval device based on grid R-tree hybrid index construction, characterized in that it comprises: An index metadata module, the index metadata module is used to record the basic data information of the grid R-tree hybrid index, and the basic data information includes grid initialization parameter information and R-tree parameter information; A triangulation module, the triangulation module is used to judge whether the feature element is a complex geometric object, and perform triangulation on the complex geometric object, so as to divide the complex geometric object of the feature element into several feature elements Divide the triangle; A grid index module, the grid index module is used to calculate the grid index of feature elements, and generate a grid index structure according to the index metadata information; R tree index module, the R tree index module is used to realize the generation and loading of R tree index files, and provide the data node insertion algorithm and R tree space query algorithm of R tree index; A global grid index partition module, the global grid index partition module is used to realize the generation and loading of the global grid index partition mapping file, and provide the function of establishing the mapping relationship between the sequence number of the feature element and the unique number of the feature element; The feature element storage module, the feature element storage module is used to realize the generation and loading of the feature element storage file, provide the basic attribute information storage of the feature element, the serialization of the spatial geometric object of the feature element and the feature element Serialized storage function of related attribute information; Query data preprocessing module, the query data preprocessing module is used to realize the data preprocessing of the input geometric object, generate the corresponding minimum circumscribed rectangle according to the element type of the geometric object, and call the grid index module and the R tree index module to realize the spatial retrieval ; A query result set generation module, the query result set generation module is capable of merging query candidate feature element result sets, and performing precise geometric matching on query input geometric objects and candidate result sets to generate a final feature element result set.

Images