本文選題：稀疏矩陣存儲(chǔ) + UB樹(shù)　； 參考：《云南大學(xué)》2013年碩士論文

【摘要】：稀疏矩陣的應(yīng)用領(lǐng)域廣泛,典型的如網(wǎng)絡(luò)分析、圖論、解微分方程、社會(huì)關(guān)系分析、線性規(guī)劃等領(lǐng)域。傳統(tǒng)用于存儲(chǔ)大型稀疏矩陣的通用存儲(chǔ)結(jié)構(gòu)主要有兩種——行壓縮存儲(chǔ)格式CRS (Compressed Row Storage)和列壓縮存儲(chǔ)格式CCS (Compressed Column Storage)。CRS和CCS均有效實(shí)現(xiàn)了數(shù)據(jù)的壓縮存儲(chǔ),其中行壓縮存儲(chǔ)是按整行來(lái)存儲(chǔ)非零元素,行壓縮存儲(chǔ)使用行索引來(lái)實(shí)現(xiàn)對(duì)行的查詢；列壓縮存儲(chǔ)是按整列來(lái)存儲(chǔ)非零元素,且列壓縮存儲(chǔ)使用列索引來(lái)對(duì)列的元素查詢。 本文從多維數(shù)據(jù)角度重新審視稀疏矩陣大數(shù)據(jù)存儲(chǔ),提出了基于UB樹(shù)的稀疏矩陣存儲(chǔ)結(jié)構(gòu)。本文主要工作點(diǎn)主要包括： ①稀疏矩陣的UB樹(shù)存儲(chǔ)機(jī)制研究,包括稀疏矩陣的Z-order降維,B+樹(shù)分裂與Z-region演化過(guò)程研究。 ②提出基于UB樹(shù)的稀疏矩陣的查詢算法與各類運(yùn)算算法。查詢算法主要實(shí)現(xiàn)矩陣的非零元素查詢,矩陣運(yùn)算算法本文只是做了簡(jiǎn)單實(shí)現(xiàn),分別有矩陣加法運(yùn)算、乘法運(yùn)算、轉(zhuǎn)置運(yùn)算。 ③對(duì)UB樹(shù)范圍查詢算法進(jìn)行了改進(jìn)。本文在研究范圍查詢算法時(shí)針對(duì)UB樹(shù)范圍查詢算法的某處的性能瓶頸,提出了一種新的范圍查詢算法。 ④最后與行壓縮存儲(chǔ)進(jìn)行了比較測(cè)試,測(cè)試內(nèi)容有存儲(chǔ)性能、元素查詢性能、子矩陣查詢性能以及改進(jìn)后的范圍查詢算法與原算法的性能比較。
[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 .

【學(xué)位授予單位】：云南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP333

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

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

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

3 羅心,樂(lè)曉波;延緩B-樹(shù)生成過(guò)程中結(jié)點(diǎn)分裂的算法[J];湖南教育學(xué)院學(xué)報(bào);2000年02期

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

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

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

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

8 ;第四章 索引結(jié)構(gòu)[J];計(jì)算機(jī)工程與應(yīng)用;1981年Z2期

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

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

相關(guān)會(huì)議論文 前2條

1 周寧;丁琦;;開(kāi)放實(shí)時(shí)數(shù)據(jù)庫(kù)及其在調(diào)度自動(dòng)化系統(tǒng)中的應(yīng)用[A];2006電力系統(tǒng)自動(dòng)化學(xué)術(shù)交流研討大會(huì)論文集[C];2006年

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

相關(guān)博士學(xué)位論文 前10條

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

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

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

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

5 朱鐵穩(wěn);基于均勻空間離散域?qū)ο蟮目臻g數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)研究[D];中國(guó)人民解放軍國(guó)防科學(xué)技術(shù)大學(xué);2002年

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

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

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

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

10 劉小虎;安全組播中的組密鑰管理算法研究[D];中國(guó)科學(xué)技術(shù)大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

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

2 路瑞強(qiáng);基于均值和標(biāo)準(zhǔn)差的空間索引方法研究[D];哈爾濱工程大學(xué);2010年

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

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

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

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

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

8 程陽(yáng);關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)的一種簡(jiǎn)易的數(shù)據(jù)存儲(chǔ)與查詢模塊的設(shè)計(jì)與實(shí)現(xiàn)[D];華中科技大學(xué);2010年

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

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

，

本文編號(hào)：1883384