Search

CN-121979961-A - Space range query method based on Z-order curve maximum block segmentation and application thereof

CN121979961ACN 121979961 ACN121979961 ACN 121979961ACN-121979961-A

Abstract

The application relates to the technical field of spatial database indexing, in particular to a spatial range query method based on maximum block segmentation of a Z-order curve and application thereof. The method comprises the steps of mapping a two-dimensional space object into a one-dimensional Z value through bit interleaving, constructing a B+ tree based on the mapped Z value, decomposing a query area into a plurality of blocks by adopting a maximum block segmentation strategy for a given query area R in a space segmentation stage, calculating to obtain a Z value segment corresponding to each block in a space range query stage, and inputting each Z value segment into the B+ tree to carry out range retrieval to obtain a final result, so that invalid point access caused by jumping of a Z-order curve is reduced. The method aims at solving the problem of how to avoid accessing the position points outside the query frame when the space range is queried.

Inventors

  • JIA LIANYIN
  • WANG RONGJIN
  • LI MENGJUAN
  • DING JIAMAN
  • ZHOU HAIHE
  • ZENG RUI
  • LI XIAOWU

Assignees

  • 昆明理工大学

Dates

Publication Date
20260505
Application Date
20260120

Claims (8)

  1. 1. The space range query method based on the maximum block segmentation of the Z-order curve is characterized by comprising the following steps: s10, mapping two-dimensional coordinates of data points in a spatial data set into Z values through a Z-order curve, and constructing a B+ tree index based on the Z values; s20, determining a corner point from the upper left And lower right corner point Determined query region Computing a region containing a query Is the minimum Z-order block of (2) Based on minimum Z-stage block For query regions Dividing by using a maximum block dividing strategy to obtain a maximum block list ; S30, calculating each maximum block in the maximum block list L Corresponding Z values, and merging Z values of adjacent maximum blocks to obtain a Z value segment list List Z-value segments in the B+ tree index Performing range search to obtain a query result set 。
  2. 2. The spatial range query method based on Z-order curve maximum block segmentation according to claim 1, wherein S10 comprises: S11, determining two-dimensional coordinates (P.X, P.Y) of the data point P: ; Wherein m is the order of a Z-order curve; s12, alternately splicing And The binary bits of (a) yield a Z value P.Z: ; S13, at each point in the spatial data set After mapping to Z values, indexing the Z values based on a B+ tree, storing the Z values in leaf nodes of the B+ tree, and sequentially connecting the leaf nodes through pointers to obtain the B+ tree index.
  3. 3. The method for querying a spatial range based on maximum block segmentation of a Z-order curve according to claim 1, wherein in S20, a query region is calculated Is the minimum Z-order block of (2) The method comprises the following steps: S21, calculating k value: ; In the formula, The function is used to detect the first 1 number from left to right, where a represents a bitwise OR operation and max represents a calculated maximum; s22, making: , ; Obtaining the composition comprising Is the minimum Z-order block of (2) ; In the formula, Representation of Is used to determine the first k binary bits of (c), And Respectively represent continuity 0 And And 1, the number I represents splicing, and m is the order of the Z-order curve.
  4. 4. The method for spatial range query based on Z-order curve maximum block segmentation as set forth in claim 3, wherein in S20, minimum Z-order block is based For query regions Dividing by using a maximum block dividing strategy to obtain a maximum block list The method comprises the following steps: s23, calculating the minimum Z-order block Is defined by the center point C: ; In the formula, Represents consecutive m-k-1 0 s; S24, using horizontal line and vertical line passing through center point C to minimum Z-stage block Performing four-fork recursive segmentation to obtain four Sub-blocks of the order ; S25, completely including in the query area The target sub-block in (a) is determined as the maximum block and added to the maximum block list Is not fully contained in the query region And skipping or continuing four-way division until the maximum block division of all the query regions R is completed.
  5. 5. The Z-order curve maximum block segmentation-based spatial range query method as set forth in claim 4, wherein the S25 comprises: s251, selecting the segmented sub-blocks according to the sequence of upper left, upper right, lower left and lower right Determining sub-blocks With query area The intersection relationship between them; S252, if sub-block And query area If not, skipping the sub-block; S253, if subblock Is entirely contained in In (C), then Stopping for the maximum block Continue to split and add it to In (a) and (b); s254, if sub-block And (3) with Part of the intersection, return to step S23 to calculate Center point C of (2) The four-way splitting is continued.
  6. 6. The spatial range query method based on Z-order curve maximum block segmentation according to claim 1, wherein the S30 comprises: S31, selecting a maximum block list The first largest block in (a) Calculation of Z value of the upper left corner coordinate of (C) And Z value of lower right corner coordinates Obtaining segments ; S32, to Each segment thereafter If (if) Will then Corresponding segment merging into Is of the segment of (a) If not, then Adding into Z value segment list S, and placing Circularly executing the step to obtain a Z value segment list ; S33, for Z value segment list Each segment of (a) Retrieving in the B+ tree index All Z values within the range ; S34, performing inverse operation on all Z values to obtain: ; ; S35, adding the data point P with the abscissa being P.X and the ordinate being P.Y into a query result set as a query result In the process, a query result set is obtained 。
  7. 7. A Z-order curve maximum block segmentation-based spatial range query method according to any of claims 1 to 6, for use in spatial range queries.
  8. 8. A computer-readable storage medium, characterized in that it comprises a memory, a processor and a computer program stored on the memory and executable on the processor, which computer program, when being executed by the processor, implements the steps of the spatial range query method according to any one of claims 1 to 6.

Description

Space range query method based on Z-order curve maximum block segmentation and application thereof Technical Field The application relates to the technical field of spatial database indexing, in particular to a spatial range query method based on maximum block segmentation of a Z-order curve and application thereof. Background Spatial scope queries are fundamental operations in spatial databases and geographic information systems, whose main objective is to determine a spatial query box R, quickly retrieving a collection of spatial objects that fall within R. The traditional index structure such as R tree, quad tree and the like can realize range query, but the problems of complex structure, high maintenance cost, multiple retrospective accesses caused by node overlapping and the like exist in a large-scale data scene. In the related technical scheme, a Z-order curve is often adopted as an index curve for space range query. The Z-order curve is a typical space-filling curve, which can map multi-dimensional coordinates into one-dimensional sequences, so that the multi-dimensional coordinates are indexed by using mature one-dimensional index structures such as B-trees, b+ trees and the like, however, due to the jump property of the Z-order curve, the phenomenon that the objects covered by the Z-segment often contain a large number of objects outside the query frame during range query occurs, and thus ineffective access and query efficiency are reduced. In view of this, the application proposes a new space range query method based on Z-order curve, aiming at effectively improving the efficiency of space range query under the condition of avoiding accessing the position points outside the query frame. Disclosure of Invention The application mainly aims to provide a space range query method based on maximum block segmentation of a Z-order curve, which aims to solve the problem of how to avoid accessing a position point outside a query frame during space range query. In order to achieve the above object, the present application provides a spatial range query method based on maximum block segmentation of a Z-order curve, the method comprising: s10, mapping two-dimensional coordinates of data points in a spatial data set into Z values through a Z-order curve, and constructing a B+ tree index based on the Z values; s20, determining a corner point from the upper left And lower right corner pointDetermined query regionComputing a region containing a queryIs the minimum Z-order block of (2)Based on minimum Z-stage blockFor query regionsDividing by using a maximum block dividing strategy to obtain a maximum block list; S30, calculating each maximum block in the maximum block list LCorresponding Z values, and merging Z values of adjacent maximum blocks to obtain a Z value segment listList Z-value segments in the B+ tree indexPerforming range search to obtain a query result set。 Optionally, the S10 includes: S11, determining two-dimensional coordinates (P.X, P.Y) of the data point P: Wherein m is the order of a Z-order curve; s12, alternately splicing AndThe binary bits of (a) yield a Z value P.Z: S13, at each point in the spatial data set After mapping to Z values, indexing the Z values based on a B+ tree, storing the Z values in leaf nodes of the B+ tree, and sequentially connecting the leaf nodes through pointers to obtain the B+ tree index. Optionally, in S20, calculating a query region is includedIs the minimum Z-order block of (2)The method comprises the following steps: S21, calculating k value: In the formula, The function is used to detect the first 1 number from left to right, where a represents a bitwise OR operation and max represents a calculated maximum; s22, making: , Obtaining the composition comprising Is the minimum Z-order block of (2); In the formula,Representation ofIs used to determine the first k binary bits of (c),AndRespectively represent continuity0 AndAnd 1, the number I represents splicing, and m is the order of the Z-order curve. Optionally, in S20, the minimum Z-order block is based onFor query regionsDividing by using a maximum block dividing strategy to obtain a maximum block listThe method comprises the following steps: s23, calculating the minimum Z-order block Is defined by the center point C: In the formula, Represents consecutive m-k-1 0 s; S24, using horizontal line and vertical line passing through center point C to minimum Z-stage block Performing four-fork recursive segmentation to obtain fourSub-blocks of the order; S25, completely including in the query areaThe target sub-block in (a) is determined as the maximum block and added to the maximum block listIs not fully contained in the query regionAnd skipping or continuing four-way division until the maximum block division of all the query regions R is completed. Optionally, the S25 includes: s251, selecting the segmented sub-blocks according to the sequence of upper left, upper right, lower left and lower right Determining sub-blo