基于Top-k查詢算法改進的儲存與NSDL調度算法研究

陳欽榮，劉順來（.汕頭職業技術學院，汕頭5504；.廣州航海學院，廣州50000）

基于Top-k查詢算法改進的儲存與NSDL調度算法研究

陳欽榮1，劉順來2
（1.汕頭職業技術學院，汕頭515041；2.廣州航海學院，廣州510000）

針對Top-k查詢算法的缺陷，提出一種基于磁盤存儲的NSDL調度算法，并將NSDL算法擴展為近似的Top-k查詢算法——ANSDL。對NSDL算法和傳統DG算法進行I/O開銷比較實驗，從實驗結果來看，NSDL算法具有更高的查詢效率和查詢精度，而ANSDL算法則在一定的條件下進一步提高NSDL算法的查詢效率。

Top-k算法；調度策略；查詢優化

1　Top-k查詢算法

利用Top-k查詢算法對數據集合中的記錄進行檢索時，不需要查詢所有記錄，即可獲取檢索結果，檢索效率較高。Top-k查詢算法根據返回結果的精度可以分為精確和近似Tok-k查詢算法兩類[1]。而根據存儲結構的差異進行分類，可以將Top-k查詢算法分為四類，分別為基于排序列表的Top-k算法、基于分層的Topk查詢算法、基于視圖的Top-k查詢算法以及基于之配圖的Top-k查詢算法。當數據集的記錄維數較高時，常用的Top-k算法的局限性會表現得十分明顯，查詢效率大幅度降低。以Onion為例[2]，其時間復雜度為O（Nd/2），其中記錄的個數為N，維數為d。可以看出，當其維數增加時，時間復雜度成指數增長狀態。NRA算法的執行分為增長和收縮兩個階段，如果記錄維數較高，則NRA增長階段需要對更多的候選元組進行維護，直接影響Top-k算法的查詢效率。通過對TA算法進行分析，發現TA算法在執行過程中，每對一條記錄進行訪問時，都需要更新門限值τ，頻繁的門限值更新會浪費大量的性能。從相關的研究數據來看，TA查詢算法在執行的過程中，通常已經獲取到多個記錄，但是由于τ的下降速度較慢，導致算法不能及時退出，仍然會繼續循環搜索，浪費大量資源。在維數越高時，循環次數越多，所浪費的資源也更多，同時，多余的循環搜索還會對Top-k算法的響應時間產生較大的影響。

2　NSDL算法

基于支配圖的Top-k算法提出了基于磁盤的存儲和調度算法，但是該算法在很多情況下所劃分的層過多，而每層中的記錄較少，嚴重浪費內存空間的利用效率，進一步影響算法的效率[3]。針對該缺陷，本文提出了一種非嚴格支配的Top-k查詢算法——NSDL。

2　.1NSDL算法層的定義

在NSDL算法中，以DG算法的層為基礎，重新對DG算法各層之間的間距進行組織和記錄。

定義記錄層間距：如果DG算法中第i層用Li的形式進行表示，第j（j＞1）層的記錄用r進行表示。則可以利用Li以及Li與Lj層之間的層中支配記錄數量來表示r與Li之間的距離。

似最大層定義：在多維空間結構中，對于一個給定的記錄集合R，其生成的支配圖為D。其第一個似最大層為D中第一個最大層以及與該最大層間距較小的多個記錄的集合。第i個似最大層則是記錄集合R-UJ=1…i-1Lj（i＞1）所生成的支配圖中第一個最大層以及與該最大層間距較小的多個記錄的集合。

2.2存儲結構設計

在NSDL算法中，利用記錄的相似性特點可以增加每一層總的記錄數量，但是這可能導致每一層中的記錄數量過多而影響算法效率。對此，通常需要對每一層的記錄數量設置一個閾值，在對記錄進行分層操作的過程中，如果單層的記錄數量超過所設置的閾值，則需要對該層進行分頁操作，而不會對該層的空間進行擴展。這樣就可以在單層記錄數量過大的情況下以頁為單位將單層的所有記錄一次性加載到內存中。為了保證對第一層記錄檢索的有效性，采用排序列表的形式對第一層記錄進行排序。首先給定一個查詢表T，其中有N個記錄，每個記錄具有m個屬性，這些屬性分別用A1，A2，…，Am進行表示。每個列存儲一個列文件Ci（ID，Ai，Li），其中的ID為記錄標識號，Ai用于表示記錄的第i個屬性，Li則用于表示記錄的i+1個屬性的出現位置。當屬性Ai的位置為記錄的最后位置時，則Li的位置為記錄第一個屬性的位置。

給定一個記錄集S，當該記錄集中的屬性數量為m時，則列文件的數量也為m，以降序方式對列文件中的數據進行排列，為了更加詳細的了解記錄中第一層的存儲結果，下面以表3種的記錄存儲結果進行分析。

表1　 NSDL第一層記錄存儲結果

通過記錄增加下一個屬性的位置，可以快速查詢到第一層中的記錄，通過實驗來看，該存儲結構大大提高了對第一層記錄進行檢索的效率。

2.3NSDL算法流程描述

NSDL算法以分層結構為基礎，通過“似最大層”[4]的概念對每層中的記錄進行分配，從而有效控制每層中記錄的數量，避免傳統DG算法單層記錄數過大而影響算法效率的問題。NSDL算法的具體流程如下：

在算法中，以數據集的輔助表（輔助表結構如圖1所示）和Top-k算法的查詢數作為輸入數據；以查詢的結果作為輸出數據。

圖1　 AT輔助表

（1）將第一層記錄加載到內存中。

（2）采用FTDT算法第一層記錄進行查詢，找出k個查詢結果，并將所有結果按照記錄分數非增長排序的方式存入到結果集RS中，同時假設RS中的最小分數為min，記錄為r。

（3）設定一個標志字段flag，并對flag賦值，使得flag=true。

N=1

While flag

N=N+1;L=1;flag=false

從輔助表中取出第N層頁數信息，并使number=第N層頁數

While number

定義Pu為第N層第L頁記錄數量的上限

退出循環

將第N層第L頁中的所有記錄加載到內存中，并對所有記錄進行查詢，記錄為c

計算c的分數f（c），if f（c）＞min，則flag= true，并從RS中移除記錄r，同時將記錄c存入RS中，并更新min

返回RS

首先，將第一層中的所有記錄加載進內存，使用DG算法對內存中所加載的記錄進行查詢，同時找出滿足設計條件的k個記錄，按照非增長排序的方式將查詢結果的記錄分數進行排序并存入RS中。假設RS中的最小分數為min，記錄為r。然后從輔助表的第N層中獲取該層分頁的數量number。將該層第一頁的記錄上限分數Pu與min進行大小比較，如果Pu＜min，則說明該層中的記錄都不能存入RS中，并終止算法，返回RS。如果Pu＞min，則將該層第一頁中所包含的記錄加到到內存，對該頁的所有記錄c進行遍歷，并計算其分數F（c），然后將F（c）與min進行大小比較，如果F（c）＞min，則將記錄r從RS中移除，并將c插入到RS中，更新min，同時也說明算法需要對N+1層進行查詢。如果該頁中的每條記錄c，都滿足F（c）≤min，則說明該頁中的記錄都無法放入RS中，繼續對下一頁的記錄進行比較分析。如果第N層，每頁中都不存在能夠插入RS中的記錄，則終止查詢算法，并返回RS。如果第N層中有記錄插入RS中，則繼續對第N+1層進行訪問。

2.4NSDL執行效率分析

在NSDL算法中，CPU時間和I/O調用時間同時構成了響應Top-k查詢的時間[5]。

CPU時間定義：利用NSDL查詢出Top-k結果集需要處理的記錄條數計算CPU時間。

I/O時間定義：利用NSDL查詢出Top-k結果集的I/O調用次數計算I/O時間。

如果利用NSDL_TotalCost（k）來表示NSDL算法查詢出最終k個記錄所花費的時間，則NSDL_TotalCost（k）=CPU_Cost*Tcpu+IO_Cost*Ti。

其中，Tcpu用于表示平均處理每條記錄所占用的CPU時間，Tio表示每次調用I/O所消耗的平均時間，CPU_Cost和IO_Cost則分別用于表示處理記錄的數量以及I/O調用的次數。

在NSDL算法中，每層和每頁的記錄數是影響算法效率的最主要因素，這兩個因素會直接影響I/O調用的次數。因此，針對不同的實驗環境，需要對這兩個因素設置不同的值。NSDL算法中最好的情況是在第一層結構中直接檢索到結果，同時第二層第一頁的記錄分數上限小于min。此時，算法在執行的過程中，只需要調用第一層記錄，I/O調用次數最少；而當算法在訪問到第i層時，該層中某一頁或者某幾頁中存在記錄被插入到記錄集中，則需要對AT表進行查詢，如果第i+1層中仍然存在有效記錄，則需要繼續進行訪問，直到i+ 1層中的記錄均無法滿足條件，才能終止算法，這時I/O的調用次數達到最大，算法的效率也降到最低。

2.5近似NSDL算法----ANSDL

在大多數情況下，精確的Top-k檢索過程需要花費較長的時間，查詢的代價也很高，尤其是在高維海量數據的查詢中，這種時間花費會表現得更加明顯。另外，用戶所使用的聚合函數通常難以清楚地表達出具體的檢索要求，例如用戶在利用搜索引擎檢索網頁的過程中，有時所得到的結果并非用戶最滿意的網頁。而在部分情況下，用戶對檢索性能具有極高的要求，而對結果的精確性的要求則一般，因此，就產生了近似的Top-k檢索。

通過前文的分析發現，當k值較小時，NSDL算法只需要對第一層進行遍歷即可得到查詢結果。因此，提出了一種近似的Top-k查詢算法——ANSDL算法，該算法主要是通過NSDL算法存儲結構第一層的記錄集響應Top-k查詢，可以將其查詢結果近似作為對整個記錄集的Top-k查詢結果。

（1）ANSDL算法描述

ANSDL算法是在NSDL的基礎上進行擴展所實現的一種算法，因此與NSDL算法的分層結構相同。ANSDL算法中，將關于數據集上的輔助表以及Top-k的查詢數作為輸入數據，并輸出查詢結果。

NSDL算法對層進行劃分的思想是基于Skyline算法的，對于Top-k查詢，響應查詢結果的記錄必然在第一層中。利用記錄層間距擴展第一層的記錄，使記錄集一次性全部加載到內存中。ANSDL算法主要是對第一層的記錄進行Top-k查詢，并將查詢結果近似作為整體數據集的Top-k的查詢結果。通過分析發現，當k值越小時，算法的精度越高，其屬于基抽樣的近似Top-k查詢算法，算法的精度主要受到樣本容量以及k值的影響。

3　NSDL算法效率比較實驗

3.1實驗環境搭建

NSDL算法和DG算法均通過C#語言實現[6]，開發平臺為Microsoft Visual Studio 2012。運行主機配置：Intel 4核處理器，主頻2.5GHz，內存4GB，Windows 7 64位旗艦版操作系統。實驗從68維USCensus記錄集中取前5維不同的記錄組合成新的記錄集，然后從USCensus記錄集中取出不同的5維記錄插入到新記錄集，使新記錄集的記錄數量達到40萬條。

3.2NSDL算法與DG算法I/O調用次數比較分析

在采用DG算法進行查詢時，記錄共分為41層，在試驗過程中，NSDL算法每層記錄的上限控制在20000以下，因此共分為20層。圖2中給出了不同k值下，NSDL算法與DG算法的I/O調用次數情況，從圖中的結果來看，當檢索結果k的數量不斷增加時，采用NSDL算法所調用的I/O次數基本保持不變，而采用DG算法時，I/O調用次數不斷增加。

3.3NSDL算法與DG算法耗時比較分析

在實驗過程中，NSDL算法相對于DG算法每層中的記錄數量均更少，因此忽略了CPU獲取k值的時間，因此，只需要對I/O耗時進行計算。如圖3所示，圖中給出了不同k之下，NSDL算法與DG算法的耗時情況。從圖中的數據來看，當K值較小時，DG算法具有更高的查詢效率，這主要是由于NSDL算法需要消耗更長的I/O載入時間。而隨著k值的不斷增加，NSDL所消耗的I/O時間基本保持不變，而DG算法則需要不斷消耗CPU時間，因此，當k值超過一定范圍后，NSDL的查詢效率會隨著k值的增加不斷上升。

3.4ANSDL算法的精度實驗

在實驗過程中，通過選擇三種不同的第一層記錄數量進行實驗，分別將第一層的記錄控制為5000條、10000條和20000條。實驗結果如圖4所示。

3.5NSDL算法與ANSDL算法耗時對比

NSDL算法中每次記錄控制為20000條，ANSDL算法中第一層的記錄控制為20000條。如圖5所示，給出了兩種算法的I/O調用時間。從圖中的結果來看，ANSDL算法效率為NSDL算法查詢效率的1倍左右。通過對圖4和圖5進行綜合分析可以發現，在k值保持不變的情況下，ANSDL算法具有更高的查詢效率，同時還保證了較高的查詢精度。

圖2　不同k值下NSDL算法與DG算法I/O調用次數對比

圖3　不同k值條件下NSDL算法與DG算法I/O調用時間對比

圖4　ANSDL算法不同記錄條數下精度隨k值的變化情況

圖5　NSDL算法與ANSDL算法耗時對比

4　結語

目前，常用的數據庫查詢優化策略和技術種類較多，Top-k算法因為其特點而被廣泛應用，但是在應用過程中，存在一定的局限性。對此，本文提出了一種基于磁盤存儲的調度算法NSDL，通過實驗分析，NSDL因為可以忽略CPU耗時，因此，在應用過程中，具有更高的查詢效率。另外在NSDL提出了近似Top-k查詢算法ANSDL算法，該算法可以在一定的條件下進一步提高NSDL算法的查詢效率。本文所提出的算法利用“似最大層”的概念對數據集進行分層，對每層記錄進行有效的組織，并通過“輔助表”優化I/O調度，從而控制I/O調度次數，大大提高數據庫的查詢效率，這對相關研究工作的開展具有重要意義。

[1]李文鳳，彭智勇，李德毅.不確定性Top-K查詢處理[J].軟件學報，2012（06）：1542～1560

[2]慈祥，馬友忠，孟小峰.一種云環境下的大數據Top-K查詢方法[J].軟件學報，2014（04）：813～825

[3]韓希先，楊東華，李建中.TKEP：海量數據上一種有效的Top-K查詢處理算法[J].計算機學報，2010（08）：1405～1417

[4]周帆，李樹全，肖春靜，吳躍.不確定數據庫中概率Top-k和排序查詢算法[J].計算機應用，2010（10）：2605～2609

[5]孫永佼，袁野，王國仁.P2P環境下面向不確定數據的Top-k查詢[J].計算機學報，2011（11）：2155～2164

[6]盧鑫，陳華輝，董一鴻，錢江波.MapReduce框架下的不確定數據Top-k查詢計算[J].模式識別與人工智能，2013（07）：695～704

Top-k Algorithm;Scheduling Policy;Query Optimization

Research on the Improved Storage and NSDL Scheduling Algorithm Based on Top-k Query Algorithms

CHEN Qin-rong1,LIU Shun-lai2
（1.Shantou Polytechnic,Shantou 515041；2.Guangzhou Maritime Institute，Guangzhou 510000）

Top-k query algorithms for its high efficiency has been widely applied,but its efficiency with the increase in size of data,shows a larger decline.Aiming at the Top-k query algorithms defects,puts a NSDL scheduling algorithm based on disk storage,and the NSDL algorithms for Top-k query algorithms that approximate,ANSDL.Compares NSDL and traditional I/O overhead DG algorithm,judges from the results,NSDL algorithms with higher efficiency and precision,and ANSDL algorithms under certain conditions to further improve the NSDL query efficiency.

1007-1423（2015）14-0028-05

10.3969/j.issn.1007-1423.2015.14.007

陳欽榮（1970-），男，廣東饒平人，本科，計算機實驗師，研究方向為計算機及應用技術

劉順來（1971-），男，廣東饒平人，碩士，副教授，研究方向為計算機及應用技術

2015-04-16

2015-05-10