本文選題：稀疏矩陣存儲 + UB樹　； 參考：《云南大學》2013年碩士論文

【摘要】：稀疏矩陣的應用領域廣泛,典型的如網(wǎng)絡分析、圖論、解微分方程、社會關系分析、線性規(guī)劃等領域。傳統(tǒng)用于存儲大型稀疏矩陣的通用存儲結構主要有兩種——行壓縮存儲格式CRS (Compressed Row Storage)和列壓縮存儲格式CCS (Compressed Column Storage)。CRS和CCS均有效實現(xiàn)了數(shù)據(jù)的壓縮存儲,其中行壓縮存儲是按整行來存儲非零元素,行壓縮存儲使用行索引來實現(xiàn)對行的查詢；列壓縮存儲是按整列來存儲非零元素,且列壓縮存儲使用列索引來對列的元素查詢。 本文從多維數(shù)據(jù)角度重新審視稀疏矩陣大數(shù)據(jù)存儲,提出了基于UB樹的稀疏矩陣存儲結構。本文主要工作點主要包括： ①稀疏矩陣的UB樹存儲機制研究,包括稀疏矩陣的Z-order降維,B+樹分裂與Z-region演化過程研究。 ②提出基于UB樹的稀疏矩陣的查詢算法與各類運算算法。查詢算法主要實現(xiàn)矩陣的非零元素查詢,矩陣運算算法本文只是做了簡單實現(xiàn),分別有矩陣加法運算、乘法運算、轉置運算。 ③對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

【共引文獻】

相關期刊論文 前10條

1 ;THREE DIMENSIONAL DATA STRUCTURE AND DATA MODEL[J];Geo-Spatial Information Science;2000年03期

2 周寧;丁琦;;開放實時數(shù)據(jù)庫及其在調度自動化系統(tǒng)中的應用[J];電網(wǎng)技術;2006年S2期

3 羅心,樂曉波;延緩B-樹生成過程中結點分裂的算法[J];湖南教育學院學報;2000年02期

4 張斐;;一種國外預測網(wǎng)絡社區(qū)發(fā)展趨勢的新方法[J];才智;2013年06期

5 江克勤;吳海峰;程玉勝;;《數(shù)據(jù)結構》中B-樹的刪除算法的實現(xiàn)[J];電腦知識與技術;2014年16期

6 陳德智;姜賀;張哲;潘瑞敏;;有限元法的一種數(shù)據(jù)結構[J];電工技術學報;2015年01期

7 徐國定;;查詢語句語義優(yōu)化的一個方法[J];華東師范大學學報(自然科學版);1987年02期

8 ;第四章 索引結構[J];計算機工程與應用;1981年Z2期

9 David B.Lomet;顧君忠;;數(shù)字B樹[J];計算機科學;1984年01期

10 周鵬;楊丹;魚詳訓;;帶快照的混合數(shù)據(jù)庫系統(tǒng)設計與應用[J];計算機科學;2008年04期

相關會議論文 前2條

1 周寧;丁琦;;開放實時數(shù)據(jù)庫及其在調度自動化系統(tǒng)中的應用[A];2006電力系統(tǒng)自動化學術交流研討大會論文集[C];2006年

2 馬文騫;王珊;;DBMS進程結構研究及多線索DBMS的設計與實現(xiàn)[A];第十一屆全國數(shù)據(jù)庫學術會議論文集[C];1993年

相關博士學位論文 前10條

1 許滸;時空數(shù)據(jù)庫聚集查詢算法研究[D];華中科技大學;2010年

2 徐紅波;基于空間填充曲線高維空間查詢算法研究[D];哈爾濱理工大學;2010年

3 羅德安;一種基于關系數(shù)據(jù)庫的空間數(shù)據(jù)模型及其特殊應用[D];西南交通大學;2001年

4 郭斯羽;動態(tài)數(shù)據(jù)中的數(shù)據(jù)挖掘研究[D];浙江大學;2002年

5 朱鐵穩(wěn);基于均勻空間離散域對象的空間數(shù)據(jù)庫關鍵技術研究[D];中國人民解放軍國防科學技術大學;2002年

6 楊峰;分布式并行索引研究[D];電子科技大學;2003年

7 董云衛(wèi);工作流管理系統(tǒng)的事務建模研究[D];西北大學;2004年

8 袁貞明;基于樣例的空間數(shù)據(jù)檢索技術研究[D];浙江大學;2005年

9 崔江濤;高維索引技術中向量近似方法研究[D];西安電子科技大學;2005年

10 劉小虎;安全組播中的組密鑰管理算法研究[D];中國科學技術大學;2006年

相關碩士學位論文 前10條

1 程曉;數(shù)據(jù)倉庫中基于位圖索引查詢優(yōu)化的研究[D];鄭州大學;2010年

2 路瑞強;基于均值和標準差的空間索引方法研究[D];哈爾濱工程大學;2010年

3 馬偉;基于FD-tree的閃存數(shù)據(jù)庫索引技術研究[D];浙江大學;2011年

4 楊玉軍;時態(tài)索引技術及算法的研究[D];中南林業(yè)科技大學;2007年

5 譚長德;南岳衡山景區(qū)網(wǎng)絡地理信息系統(tǒng)的研究與設計[D];電子科技大學;2010年

6 馮知一;基于數(shù)據(jù)倉庫的聯(lián)機分析處理系統(tǒng)關鍵技術研究與實現(xiàn)[D];西安電子科技大學;2009年

7 吳家盛;支持無線傳感器網(wǎng)絡的實時數(shù)據(jù)庫存儲管理[D];華中科技大學;2010年

8 程陽;關系數(shù)據(jù)庫管理系統(tǒng)的一種簡易的數(shù)據(jù)存儲與查詢模塊的設計與實現(xiàn)[D];華中科技大學;2010年

9 翟建東;閃存碎片影響分析與閃存數(shù)據(jù)庫索引技術研究[D];華中科技大學;2011年

10 楊藍麒;一種智能手機上基于位置的多媒體信息分享系統(tǒng)[D];上海交通大學;2012年

，

本文編號：1883384