Adaptive cardinal number tree dynamic indexing method based on GPU parallelism

Abstract

The invention provides an adaptive cardinal number tree dynamic indexing method based on GPU parallelism. Firstly, an adaptive cardinal number tree data structure is constructed; the first two layerscreate tree nodes of the Node256 type; a cardinal number sequencing method based on high-order priority is created for the third layer and the fourth layer; tree nodes capable of accommodating corresponding sizes are created according to the number of the branches; the creation of a dynamic data structure is realized; it can be ensured that the latest update in the original batch of data is stillbehind the old update after sorting; and de-duplication is performed, redundant old updates are removed, latest updates are reserved, each section of sequence without duplicate data is inserted into anode corresponding to the section after duplicate removal to finish the establishment of the whole self-adaptive cardinal number tree, and secondly, data insertion, query and deletion operations canbe performed in parallel based on GPU parallel computing capability.

Description

technical field [0001] The invention relates to the technical field of parallel indexing in the direction of computer databases, in particular to a GPU parallel adaptive radix tree dynamic indexing method. Background technique [0002] Indexing technology is one of the key technologies in modern information retrieval, search applications, and data mining. In order to accurately locate data in a large amount of data, various types of data indexes have been proposed for different types of data and different query requirements. In recent years, the explosive growth of data scale has further expanded the field of research to large-scale, high-dimensional, and sparse data sets. Efficient index construction and data query for such data sets have become the main research direction at this stage. . In addition, with the expansion of the data scale, the requirements for the processor are getting higher and higher. The parallel capability of the graphics processing unit (GPU) provide...

AI Technical Summary

Problems solved by technology

The search, insertion and deletion operations on the four types of nodes of the adaptive radix tree index are all single-threaded serial designs, which cannot be operated in parallel, and the existing GPU method is a serial tree structure, which cannot dynamically update nodes. The type changes, and the warp and cache cannot be fully utilized when querying, and the performance is poor

Images