基于Top-k查詢算法改進(jìn)的儲(chǔ)存與NSDL調(diào)度算法研究

陳欽榮，劉順來（.汕頭職業(yè)技術(shù)學(xué)院，汕頭5504；.廣州航海學(xué)院，廣州50000）

基于Top-k查詢算法改進(jìn)的儲(chǔ)存與NSDL調(diào)度算法研究

陳欽榮1，劉順來2
（1.汕頭職業(yè)技術(shù)學(xué)院，汕頭515041；2.廣州航海學(xué)院，廣州510000）

針對(duì)Top-k查詢算法的缺陷，提出一種基于磁盤存儲(chǔ)的NSDL調(diào)度算法，并將NSDL算法擴(kuò)展為近似的Top-k查詢算法——ANSDL。對(duì)NSDL算法和傳統(tǒng)DG算法進(jìn)行I/O開銷比較實(shí)驗(yàn)，從實(shí)驗(yàn)結(jié)果來看，NSDL算法具有更高的查詢效率和查詢精度，而ANSDL算法則在一定的條件下進(jìn)一步提高NSDL算法的查詢效率。

Top-k算法；調(diào)度策略；查詢優(yōu)化

1　Top-k查詢算法

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

2　NSDL算法

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

2　.1NSDL算法層的定義

在NSDL算法中，以DG算法的層為基礎(chǔ)，重新對(duì)DG算法各層之間的間距進(jìn)行組織和記錄。

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

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

2.2存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)

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

給定一個(gè)記錄集S，當(dāng)該記錄集中的屬性數(shù)量為m時(shí)，則列文件的數(shù)量也為m，以降序方式對(duì)列文件中的數(shù)據(jù)進(jìn)行排列，為了更加詳細(xì)的了解記錄中第一層的存儲(chǔ)結(jié)果，下面以表3種的記錄存儲(chǔ)結(jié)果進(jìn)行分析。

表1　 NSDL第一層記錄存儲(chǔ)結(jié)果

通過記錄增加下一個(gè)屬性的位置，可以快速查詢到第一層中的記錄，通過實(shí)驗(yàn)來看，該存儲(chǔ)結(jié)構(gòu)大大提高了對(duì)第一層記錄進(jìn)行檢索的效率。

2.3NSDL算法流程描述

NSDL算法以分層結(jié)構(gòu)為基礎(chǔ)，通過“似最大層”[4]的概念對(duì)每層中的記錄進(jìn)行分配，從而有效控制每層中記錄的數(shù)量，避免傳統(tǒng)DG算法單層記錄數(shù)過大而影響算法效率的問題。NSDL算法的具體流程如下：

在算法中，以數(shù)據(jù)集的輔助表（輔助表結(jié)構(gòu)如圖1所示）和Top-k算法的查詢數(shù)作為輸入數(shù)據(jù)；以查詢的結(jié)果作為輸出數(shù)據(jù)。

圖1　 AT輔助表

（1）將第一層記錄加載到內(nèi)存中。

（2）采用FTDT算法第一層記錄進(jìn)行查詢，找出k個(gè)查詢結(jié)果，并將所有結(jié)果按照記錄分?jǐn)?shù)非增長排序的方式存入到結(jié)果集RS中，同時(shí)假設(shè)RS中的最小分?jǐn)?shù)為min，記錄為r。

（3）設(shè)定一個(gè)標(biāo)志字段flag，并對(duì)flag賦值，使得flag=true。

N=1

While flag

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

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

While number

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

退出循環(huán)

將第N層第L頁中的所有記錄加載到內(nèi)存中，并對(duì)所有記錄進(jìn)行查詢，記錄為c

計(jì)算c的分?jǐn)?shù)f（c），if f（c）＞min，則flag= true，并從RS中移除記錄r，同時(shí)將記錄c存入RS中，并更新min

返回RS

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

2.4NSDL執(zhí)行效率分析

在NSDL算法中，CPU時(shí)間和I/O調(diào)用時(shí)間同時(shí)構(gòu)成了響應(yīng)Top-k查詢的時(shí)間[5]。

CPU時(shí)間定義：利用NSDL查詢出Top-k結(jié)果集需要處理的記錄條數(shù)計(jì)算CPU時(shí)間。

I/O時(shí)間定義：利用NSDL查詢出Top-k結(jié)果集的I/O調(diào)用次數(shù)計(jì)算I/O時(shí)間。

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

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

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

2.5近似NSDL算法----ANSDL

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

通過前文的分析發(fā)現(xiàn)，當(dāng)k值較小時(shí)，NSDL算法只需要對(duì)第一層進(jìn)行遍歷即可得到查詢結(jié)果。因此，提出了一種近似的Top-k查詢算法——ANSDL算法，該算法主要是通過NSDL算法存儲(chǔ)結(jié)構(gòu)第一層的記錄集響應(yīng)Top-k查詢，可以將其查詢結(jié)果近似作為對(duì)整個(gè)記錄集的Top-k查詢結(jié)果。

（1）ANSDL算法描述

ANSDL算法是在NSDL的基礎(chǔ)上進(jìn)行擴(kuò)展所實(shí)現(xiàn)的一種算法，因此與NSDL算法的分層結(jié)構(gòu)相同。ANSDL算法中，將關(guān)于數(shù)據(jù)集上的輔助表以及Top-k的查詢數(shù)作為輸入數(shù)據(jù)，并輸出查詢結(jié)果。

NSDL算法對(duì)層進(jìn)行劃分的思想是基于Skyline算法的，對(duì)于Top-k查詢，響應(yīng)查詢結(jié)果的記錄必然在第一層中。利用記錄層間距擴(kuò)展第一層的記錄，使記錄集一次性全部加載到內(nèi)存中。ANSDL算法主要是對(duì)第一層的記錄進(jìn)行Top-k查詢，并將查詢結(jié)果近似作為整體數(shù)據(jù)集的Top-k的查詢結(jié)果。通過分析發(fā)現(xiàn)，當(dāng)k值越小時(shí)，算法的精度越高，其屬于基抽樣的近似Top-k查詢算法，算法的精度主要受到樣本容量以及k值的影響。

3　NSDL算法效率比較實(shí)驗(yàn)

3.1實(shí)驗(yàn)環(huán)境搭建

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

3.2NSDL算法與DG算法I/O調(diào)用次數(shù)比較分析

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

3.3NSDL算法與DG算法耗時(shí)比較分析

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

3.4ANSDL算法的精度實(shí)驗(yàn)

在實(shí)驗(yàn)過程中，通過選擇三種不同的第一層記錄數(shù)量進(jìn)行實(shí)驗(yàn)，分別將第一層的記錄控制為5000條、10000條和20000條。實(shí)驗(yàn)結(jié)果如圖4所示。

3.5NSDL算法與ANSDL算法耗時(shí)對(duì)比

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

圖2　不同k值下NSDL算法與DG算法I/O調(diào)用次數(shù)對(duì)比

圖3　不同k值條件下NSDL算法與DG算法I/O調(diào)用時(shí)間對(duì)比

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

圖5　NSDL算法與ANSDL算法耗時(shí)對(duì)比

4　結(jié)語

目前，常用的數(shù)據(jù)庫查詢優(yōu)化策略和技術(shù)種類較多，Top-k算法因?yàn)槠涮攸c(diǎn)而被廣泛應(yīng)用，但是在應(yīng)用過程中，存在一定的局限性。對(duì)此，本文提出了一種基于磁盤存儲(chǔ)的調(diào)度算法NSDL，通過實(shí)驗(yàn)分析，NSDL因?yàn)榭梢院雎訡PU耗時(shí)，因此，在應(yīng)用過程中，具有更高的查詢效率。另外在NSDL提出了近似Top-k查詢算法ANSDL算法，該算法可以在一定的條件下進(jìn)一步提高NSDL算法的查詢效率。本文所提出的算法利用“似最大層”的概念對(duì)數(shù)據(jù)集進(jìn)行分層，對(duì)每層記錄進(jìn)行有效的組織，并通過“輔助表”優(yōu)化I/O調(diào)度，從而控制I/O調(diào)度次數(shù)，大大提高數(shù)據(jù)庫的查詢效率，這對(duì)相關(guān)研究工作的開展具有重要意義。

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

[2]慈祥，馬友忠，孟小峰.一種云環(huán)境下的大數(shù)據(jù)Top-K查詢方法[J].軟件學(xué)報(bào)，2014（04）：813～825

[3]韓希先，楊東華，李建中.TKEP：海量數(shù)據(jù)上一種有效的Top-K查詢處理算法[J].計(jì)算機(jī)學(xué)報(bào)，2010（08）：1405～1417

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

[5]孫永佼，袁野，王國仁.P2P環(huán)境下面向不確定數(shù)據(jù)的Top-k查詢[J].計(jì)算機(jī)學(xué)報(bào)，2011（11）：2155～2164

[6]盧鑫，陳華輝，董一鴻，錢江波.MapReduce框架下的不確定數(shù)據(jù)Top-k查詢計(jì)算[J].模式識(shí)別與人工智能，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-），男，廣東饒平人，本科，計(jì)算機(jī)實(shí)驗(yàn)師，研究方向?yàn)橛?jì)算機(jī)及應(yīng)用技術(shù)

劉順來（1971-），男，廣東饒平人，碩士，副教授，研究方向?yàn)橛?jì)算機(jī)及應(yīng)用技術(shù)

2015-04-16

2015-05-10