外存儲算法中兩個數據結構的設計研究.pdf

1、近年來,隨著信息科技的日益發(fā)展,人們已經淹沒在數據的海洋里,各種各樣的數據充斥著人們的生活。其中一部分數據由于其數據量比較龐大,需要海量的存儲空間,而目前的計算機內存空間不足以滿足這種需求,只能將其存儲在外存儲器中。因此處于內外存之間傳輸數據的I/O通道就成為了制約算法運行效率的主要瓶頸。這種現象在如下幾個方面表現的尤為明顯,比如:空間數據庫中的海量幾何數據、數據庫、統計學、地理信息系統(GIS)、約束邏輯規(guī)劃、計算機圖形學、虛擬現實系

2、統等。由此產生了外存儲算法與數據結構的設計和分析領域,其主要目標就是研究算法的有效性,以盡量減小程序運行過程中的輸入/輸出代價。
　　 本文首先研究了已有的適用于外存儲算法的數據結構?；贔ibonacci堆在內存儲算法中的特點,進一步改進得出了一種新的適合外存儲算法的數據結構,并分析了該數據結構中各種操作的時間復雜度。并以這種數據結構在Dijkstra算法中的應用為實例證明了該數據結構的可行性和有效性。
　　 其次,雙

3、端優(yōu)先級隊列是一種可同時支持針對最大、最小數據進行插入,刪除操作的數據結構,本文利用外存儲算法中對堆的研究,設計了一種新的適合外存儲算法的雙端優(yōu)先級隊列。并分析它的操作復雜度,其中除查找操作具有單位時間的頁面置換次數以外,其他操作都具有對數時間的頁面置換次數。最后借助網絡傳輸中的包緩存實現了該數據結構在外存中的應用。
　　 本文的創(chuàng)新點主要包括以下兩個方面:
　　 (1)針對外存儲算法中的數據結構問題,目前還沒有支持單位

4、時間操作復雜度的外存儲算法。本文根據Fibonacci堆在內存儲算法中的特點,設計出了一種針對海量數據支持單位時間操作復雜度的外存儲算法。并通過實例證明了算法的可行性和有效性。
　　 (2)基于外存儲算法中對堆的研究,經過一些改進得到了一種新的適應于外存儲算法的雙端優(yōu)先級隊列。該數據結構可以同時支持針對最大、最小數據的查找,刪除操作。并且其查找操作的頁面置換次數為O(1),其他操作的頁面置換次數為O(logN)。通過這種數據結構