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

Range query filtering method for key value pair storage and key value pair storage system

A filtering method and storage system technology, which is applied in the field of key-value pair storage systems, can solve problems, such as serious range query performance, and achieve the effects of improving filtering capabilities, meeting space efficiency goals, and saving memory overhead

Active Publication Date: 2018-10-30
NANJING UNIV +2
View PDF3 Cites 4 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

And this makes the range query more expensive
Therefore, range query performance is a rather serious problem for key-value store systems

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
  • Range query filtering method for key value pair storage and key value pair storage system
  • Range query filtering method for key value pair storage and key value pair storage system
  • Range query filtering method for key value pair storage and key value pair storage system

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0030] The technical solution of the present invention will be further described below in conjunction with the accompanying drawings.

[0031] First, according to the key in the container in the key-value pair storage system, combined with the memory overhead, the range filter is constructed by using growth and shrinkage. figure 1 is a schematic diagram of a range filter according to an embodiment of the present invention. like figure 1As shown, the range filter is a binary tree, where the root node represents the range interval of the key in the entire container, which is [aa,iq) in the figure. Each non-root node has its corresponding key range interval, but this interval does not need to be stored in memory, but can be calculated according to the corresponding interval of the root node. The function of non-leaf nodes is that for each query, the corresponding leaf nodes can be found by relying on non-leaf nodes. Each non-leaf node must have two child nodes, and the corresp...

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 range query filtering method for key value pair storage and a key value pair storage system. According to the range query filtering method for key value pair storage, a growth and contraction method is used for index of key value pairs contained in each container in the key value pair storage system; and a range filter is generated according to a given space budget so asto filter the range query. The system workload is learned in the query process, and the range filter is adjusted. The false positive rate of the range filter can be effectively reduced through such dynamic adjustment; the filtering effect is improved; invalid disk IO of the key value pair storage system is greatly reduced; and the reading performance of the whole system is improved.

Description

technical field [0001] The invention belongs to the technical field of storage, and in particular relates to a range query filtering method for key-value pair storage, a range query method and a key-value pair storage system. Background technique [0002] With the advent of the mobile Internet era, digital devices have begun to penetrate into all aspects of human society, which has brought about a rapid increase in the amount of data. According to IDC's 2017 report, by 2025, the global data volume will expand to 163ZB, which is 10 times that of 2016. The report also pointed out that the real-time data of the Internet of Things will occupy a huge share. The data forms they generate will also be very diverse, and the data will also show unstructured characteristics, and this type of data is very suitable for storage with a key-value store (Key-Value Store) system. [0003] According to Baidu's observation, in the key-value pair storage system, the number of read operations i...

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
IPC IPC(8): G06F17/30
Inventor 王谐谦叶保留唐斌陆桑璐
Owner NANJING 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