Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Method, device and medium for merging and updating r-tree index based on Hilbert curve

An update method and tree index technology, applied in database index, database update, structured data retrieval and other directions, can solve the problem of occupying system memory computing resources, affecting index query, insertion, deletion efficiency, etc., to improve space utilization, The effect of improving query efficiency and reducing the number of reads and writes

Active Publication Date: 2022-07-12
ZHEJIANG UNIV
View PDF0 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the actual application of LSM R trees often involves the merging of a large number of R trees. During the merging process, the R trees will occupy a certain amount of memory and computing resources in the system, which will affect the query, insertion, and deletion of indexes during this period. Efficiency of other operations

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Method, device and medium for merging and updating r-tree index based on Hilbert curve
  • Method, device and medium for merging and updating r-tree index based on Hilbert curve
  • Method, device and medium for merging and updating r-tree index based on Hilbert curve

Examples

Experimental program
Comparison scheme
Effect test

Embodiment

[0057] The steps of this embodiment are the same as the steps of the specific implementation, namely steps S1 to S4, and the steps of S2 are implemented by S21 to S25, and the steps of S3 are implemented by S31 to S34, which will not be repeated here. Part of the implementation process and implementation results are shown below:

[0058] In this example, the area-shaped spatial data type is used as the research object, and the data adopts the data of all Chinese construction areas downloaded through OpenStreetMap, and the total number of elements is 1,000,192. like image 3 Spatial data for the study subjects are shown. It can be seen from the figure that the spatial data has different sizes and is not uniformly distributed, and the density of the data has a certain degree of randomness, which can be used as experimental samples.

[0059] A total of 50 sets of data from 1000 to 50,000 records are randomly selected, and the Hilbert curve-based improved R tree index, conventi...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses a Hilbert curve-based R-tree index merging and updating method, device and medium. The method steps include: S1: obtaining the first R-tree to be merged and the second R-tree to be inserted into the first R-tree, and storing the upper and lower limit ranges of the Hilbert values ​​of the contained objects in the non-leaf nodes of the R-tree; S2: The "top-to-bottom" hierarchical query algorithm is used to query the to-be-inserted nodes of each merged leaf node in the first R-tree child node layer in the second R-tree child node layer; S3: adjust the algorithm according to the "bottom-to-top" level , for each leaf node in the first R tree, insert the space object contained in it into the node to be inserted determined in S2 according to the order of the Hilbert value, and realize the merging of the two R trees; S4 is for the merged No. The binary R tree updates the storage information in each node layer by layer in the order from the leaf node to the root node. The invention has important practical application value in the field of high-performance storage of geographic spatiotemporal big data.

Description

technical field [0001] The present invention relates to the technical field of data retrieval and updating, in particular to a technology for merging and updating a Hilbert R-tree index. Background technique [0002] The update frequency of spatial data has gradually increased with the development of geographic information data collection equipment. The management of spatial data must not only meet the needs of efficient query, but also need to take into account the needs of rapid update. The spatial index combined with the LSM tree structure can effectively support the needs of frequent insertion and update of spatial data. Compared with the DBH tree, DHVB tree and SHB tree, the LSM R tree index has better universality and stability. However, the actual application of LSM R-trees often involves a large number of R-tree merging operations. During the merging process, R-trees will occupy a certain amount of memory and computing resources of the system, affecting the query, in...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F16/22G06F16/23G06F16/2453G06F16/2455
CPCG06F16/2246G06F16/23G06F16/2455G06F16/2453G06F16/9027G06F16/2272
Inventor 张丰钱伯至汪愿愿胡林舒
Owner ZHEJIANG UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com