基于UB树的大型稀疏矩阵存储研究

发布时间：2018-05-13 13:45

本文选题：稀疏矩阵存储 + UB树　；参考：《云南大学》2013年硕士论文

【摘要】：稀疏矩阵的应用领域广泛,典型的如网络分析、图论、解微分方程、社会关系分析、线性规划等领域。传统用于存储大型稀疏矩阵的通用存储结构主要有两种——行压缩存储格式CRS (Compressed Row Storage)和列压缩存储格式CCS (Compressed Column Storage)。CRS和CCS均有效实现了数据的压缩存储,其中行压缩存储是按整行来存储非零元素,行压缩存储使用行索引来实现对行的查询；列压缩存储是按整列来存储非零元素,且列压缩存储使用列索引来对列的元素查询。本文从多维数据角度重新审视稀疏矩阵大数据存储,提出了基于UB树的稀疏矩阵存储结构。本文主要工作点主要包括： ①稀疏矩阵的UB树存储机制研究,包括稀疏矩阵的Z-order降维,B+树分裂与Z-region演化过程研究。 ②提出基于UB树的稀疏矩阵的查询算法与各类运算算法。查询算法主要实现矩阵的非零元素查询,矩阵运算算法本文只是做了简单实现,分别有矩阵加法运算、乘法运算、转置运算。 ③对UB树范围查询算法进行了改进。本文在研究范围查询算法时针对UB树范围查询算法的某处的性能瓶颈,提出了一种新的范围查询算法。 ④最后与行压缩存储进行了比较测试,测试内容有存储性能、元素查询性能、子矩阵查询性能以及改进后的范围查询算法与原算法的性能比较。
[Abstract]:The sparse matrix has wide application fields , such as network analysis , graph theory , differential equation , social relation analysis , linear programming and so on . The conventional general storage structure used to store large sparse matrix mainly includes two _ row compressed storage format CRS ( Compressed Row Storage ) and column compressed storage format CCS ( Compressed Column Storage ) . CRS and CCS effectively implement the compressed storage of the data , wherein the row compression storage is to store non - zero elements according to the whole row , and the row compression storage uses the row index to realize the query of the row ;
Column compression stores are columns that store non - zero elements , and column compression stores column indexes to query columns of elements .

In this paper , a sparse matrix storage structure based on UB tree is proposed from the viewpoint of multi - dimensional data . The main work points of this paper are as follows :

( 1 ) The research on UB tree storage mechanism of sparse matrix , including Z - order dimension reduction , B + tree splitting and Z - region evolution of sparse matrix .

In this paper , a query algorithm of sparse matrix based on UB tree and various algorithms are proposed . The query algorithm mainly implements non - zero element query of matrix , and the matrix operation algorithm is simply implemented .

In this paper , a new range query algorithm is proposed for the performance bottleneck of UB tree range query algorithm .

( 4 ) Finally , the comparison test is carried out with the line compression storage , and the test content has storage performance , element query performance , sub - matrix query performance and improved range query algorithm compared with the performance of the original algorithm .

【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP333

【共引文献】