徐紅波，胡 文，潘海為，高 祥，劉潤(rùn)濤

(1.哈爾濱商業(yè)大學(xué)計(jì)算機(jī)與信息工程學(xué)院，哈爾濱150028;2.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱150001;3.哈爾濱理工大學(xué)應(yīng)用科學(xué)學(xué)院，哈爾濱150080)

空間數(shù)據(jù)庫(kù)被廣泛地應(yīng)用到多個(gè)領(lǐng)域中.如今對(duì)海量復(fù)雜空間信息進(jìn)行查詢?cè)絹?lái)越需要空間數(shù)據(jù)庫(kù)的支持.空間范圍查詢查找點(diǎn)集中位于查詢區(qū)域中的點(diǎn)[1].

線性掃描范圍查詢算法BFRQ依次掃描點(diǎn)集中每個(gè)點(diǎn)，計(jì)算該點(diǎn)是否位于查詢區(qū)域中，如果位于該查詢區(qū)域中，那么當(dāng)前點(diǎn)在結(jié)果集中，否則繼續(xù)掃描下一個(gè)點(diǎn)[2].

基于R樹空間范圍查詢算法RRQ從根結(jié)點(diǎn)開始深度優(yōu)先遍歷R樹.若訪問(wèn)的結(jié)點(diǎn)是索引結(jié)點(diǎn)，則依次判斷該結(jié)點(diǎn)的分支對(duì)應(yīng)的最小外包矩形是否與查詢區(qū)域相交，若是，遞歸遍歷該分支對(duì)應(yīng)的子樹，否則，繼續(xù)判斷下個(gè)分支;若訪問(wèn)的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，則依次判斷該結(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)點(diǎn)是否落在查詢區(qū)域中，若是，則該點(diǎn)在結(jié)果集中，否則，繼續(xù)判斷下個(gè)點(diǎn).R樹中存在最小外包矩形之間交疊問(wèn)題.基于R樹空間范圍查詢算法的執(zhí)行時(shí)間指數(shù)依賴于空間維度.該現(xiàn)象被稱為“維度災(zāi)難”[3].

基于VA文件空間范圍查詢算法VARQ順序掃描文件中每個(gè)位串，若查詢區(qū)域包含位串所在網(wǎng)格，則位串對(duì)應(yīng)點(diǎn)在結(jié)果集中，否則，判斷查詢區(qū)域與位串對(duì)應(yīng)的網(wǎng)格是否相交，若相交，則訪問(wèn)數(shù)據(jù)文件對(duì)應(yīng)點(diǎn)的坐標(biāo)，判斷該點(diǎn)是否落在查詢區(qū)域中，若是，則該點(diǎn)在結(jié)果集中[4].

基于NB樹空間范圍查詢算法NBRQ在樹中定位查詢點(diǎn)q，然后向前和向后分別掃描前驅(qū)點(diǎn)Pp和后繼點(diǎn)Ps.當(dāng) Pp滿足 Norm(Pp)＜Norm(q)－DIAMETER時(shí)，退出向前遍歷，否則，判斷Pp與q之間的距離是否小于查詢半徑DIAMETER，若小于，則Pp在結(jié)果集中，否則，繼續(xù)判斷Pp的前驅(qū)點(diǎn)，直到雙向鏈表的表頭為止;當(dāng)ps滿足Norm(ps)＞Norm(q)+DIAMETER時(shí)，退出向后遍歷操作，否則，判斷ps與q之間的距離是否小于DIAMETER，若小于，ps在結(jié)果集中，否則，繼續(xù)訪問(wèn)ps的后繼點(diǎn)，直到雙向鏈表的表尾為止[5].

本文采用并行技術(shù)[6]解決高維空間范圍查詢問(wèn)題，將d維范圍查詢操作轉(zhuǎn)換到d個(gè)從處理機(jī)上的一維范圍查詢操作.從處理并行執(zhí)行范圍查詢操作，大大減少了算法的查詢時(shí)間.

1 基本概念

二維空間查詢區(qū)域?qū)?yīng)矩形.三維空間查詢區(qū)域?qū)?yīng)長(zhǎng)方體.以此類推，d維空間查詢區(qū)域?qū)?yīng)超矩形.超矩形的形狀可以由主對(duì)角線上的兩個(gè)頂點(diǎn)確定，但是本文將超矩形投影到每一維上，用投影線段表示超矩形.

例如，在圖1中矩形可以由x軸上的線段[27，56]和y軸上的線段[28，68]表示.d維空間查詢區(qū)域在每一維上的投影之后將得到d條線段用來(lái)表示超矩形.

圖1 二維空間查詢區(qū)域

定義1 d維空間查詢區(qū)域定義為Rd=((l1，u1)，(l2，u2)，...，(ld，ud))，其中 li≤ui(i=1，...，d).

定義2 給定點(diǎn)集P={p1，p2，…，pn}，點(diǎn)集P 中每個(gè)點(diǎn) pi=(pi1，pi2，...，pid)，點(diǎn)集 P 在第 i維上的投影Pi定義為由點(diǎn)集P中每個(gè)點(diǎn)的第i維坐標(biāo)組成的集合，記作Pi={p1i，p2i，…，pni}.

定義3 給定點(diǎn)集P={p1，p2，…，pn}，點(diǎn)集P 中每個(gè)點(diǎn) pi=(pi1，pi2，...，pid)，查詢區(qū)域 Rd=((l1，u1)，(l2，u2)，...，(ld，ud))，d 維空間范圍查詢定義為RQ(P，Rd)={p(p1，p2，…，pn)|(p∈P)∧ (l1≤p1≤u1)∧ (l2≤p2≤u2)∧…∧ (ld≤pd≤ud)}.

空間范圍查詢并行算法在執(zhí)行之前需要建立索引結(jié)構(gòu).索引結(jié)構(gòu)采用B+樹.B+樹是一種平衡多路查找樹.算法首先計(jì)算點(diǎn)集P在每一維上的投影Pi，然后在投影Pi上建立B+樹，因此點(diǎn)集P經(jīng)過(guò)投影之后對(duì)應(yīng)d棵B+樹.具體操作過(guò)程如圖2所示.

圖2 索引結(jié)構(gòu)創(chuàng)建過(guò)程

2 并行算法

空間范圍查詢并行算法劃分為2個(gè)階段:索引創(chuàng)建階段和執(zhí)行查詢階段.索引創(chuàng)建階段:首先根據(jù)空間維度d，主節(jié)點(diǎn)機(jī)調(diào)用d個(gè)從節(jié)點(diǎn)機(jī)并行計(jì)算，將保存在主節(jié)點(diǎn)機(jī)中的點(diǎn)集P分別發(fā)送到d個(gè)從節(jié)點(diǎn)上，在第i個(gè)從節(jié)點(diǎn)機(jī)中計(jì)算點(diǎn)集P在第i維上的投影Pi，然后在投影Pi上建立 B+樹Bi.執(zhí)行查詢階段:給定查詢區(qū)域Rd，d個(gè)從節(jié)點(diǎn)機(jī)并行查詢?cè)贐+樹Bi中位于線段[li，ui]上的點(diǎn)集，然后每個(gè)從節(jié)點(diǎn)機(jī)將查詢結(jié)果發(fā)送給主節(jié)點(diǎn)機(jī)，主節(jié)點(diǎn)機(jī)只需計(jì)算這些點(diǎn)集的交集，即為范圍查詢的結(jié)果.

算法PRQ(P，Rd)

輸入:點(diǎn)集P，查詢區(qū)域Rd;

輸出:點(diǎn)集P落在查詢區(qū)域Rd中的點(diǎn)集r;

BEGIN

call d slave node processors;

send point set P to d slave node processors;

1:for the ith slave node processors do

Pi={p1i，p2i，…，pni};

BuildBTree(Pi);

2:for the ith slave node processors do

ri=Search([li，ui]，Bi);

send rito the master node processors;

r=φ;

3:for i=1 to d do

r=r∩ri;

return r;

END

函數(shù)BuildBTree(Pi)的功能是在投影Pi上構(gòu)建B+樹，將投影Pi中的每個(gè)點(diǎn)依次插入到B+樹中.若將插入操作作為單位操作，則函數(shù)BuildBTree的時(shí)間復(fù)雜度是O(n).

函數(shù) Search([li，ui]，Bi)的功能是在 B+樹Bi中查詢位于區(qū)間[li，ui]上的點(diǎn).函數(shù)Search首先根據(jù)關(guān)鍵字li在B+樹Bi的雙向鏈表中查找其所在的位置，然后順著鏈表結(jié)構(gòu)向右掃描，直到關(guān)鍵字大于Ui為止.圖3給出函數(shù)Search的執(zhí)行過(guò)程，給定區(qū)間[3，6]，首先根據(jù)關(guān)鍵字3在B+樹中向下進(jìn)行搜索，直到定位到雙向鏈表中第一個(gè)節(jié)點(diǎn)，第一個(gè)節(jié)點(diǎn)的第3個(gè)關(guān)鍵字正好等于3，然后沿著雙向鏈表向右掃描每個(gè)關(guān)鍵字，直到第三個(gè)葉子節(jié)點(diǎn)中的關(guān)鍵字7為止，返回關(guān)鍵字對(duì)應(yīng)的點(diǎn)集{p3，p4，p5，p6}.

圖3 函數(shù)Search的執(zhí)行過(guò)程

定理1 算法PRQ的空間復(fù)雜度為O(dn)，時(shí)間復(fù)雜度為O(h+n(ui－li)/(uimax－limin)+d).

證明:(空間復(fù)雜度)d個(gè)從節(jié)點(diǎn)機(jī)需要分別存儲(chǔ)包含n個(gè)點(diǎn)的點(diǎn)集P，故算法的空間復(fù)雜度為O(dn).(時(shí)間復(fù)雜度)索引創(chuàng)建階段需要計(jì)算點(diǎn)集的投影和B+樹，需要非常大的計(jì)算量，但是索引創(chuàng)建階段屬于算法的初始化階段，只需執(zhí)行1次，之后只對(duì)索引結(jié)構(gòu)B+樹進(jìn)行更新操作，因此算法PRQ的第1步操作與算法的時(shí)間復(fù)雜度無(wú)關(guān)，算法的時(shí)間復(fù)雜度與第2步和第3步操作相關(guān).假設(shè)點(diǎn)集P中的點(diǎn)是均勻分布的，函數(shù) Search([li，ui]，Bi)首先在B+樹Bi雙向鏈表中定位li的位置，需要跟索引節(jié)點(diǎn)中的關(guān)鍵字進(jìn)行比較，假設(shè)B+樹的高為h，需要同h個(gè)索引節(jié)點(diǎn)進(jìn)行關(guān)鍵字比較才能夠定位li的位置.之后，只需要沿著雙向鏈表向右依次掃描關(guān)鍵字是否小于ui，那么落在區(qū)間[li，ui]上關(guān)鍵字個(gè)數(shù)等于 n(ui－ li)/(uimaxlimax)，因此函數(shù)Search的時(shí)間復(fù)雜度為O(h+n(ui－li)/(uimax－ limin))，其中 uimax為投影 Pi的最大值，limin為投影Pi的最小值.第3步操作是求d個(gè)Ri的交集，其時(shí)間復(fù)雜度為d.故算法的時(shí)間復(fù)雜度是 O(h+n(ui－li)/(uimax－limin)+d)，證畢.

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證范圍查詢并行算法的效率，本文比較算法PRQ與算法BFRQ、VARQ、RRQ之間的查詢性能.編程環(huán)境:1.86GHz賽揚(yáng)處理器、1G內(nèi)存、120G硬盤、Windows XP操作系統(tǒng)、Visual C++.net 2005.測(cè)試數(shù)據(jù)為由隨機(jī)函數(shù)產(chǎn)生的滿足均與分布的數(shù)據(jù).

實(shí)驗(yàn)1考查數(shù)據(jù)量對(duì)查詢時(shí)間的影響，實(shí)驗(yàn)中使用的數(shù)據(jù)是2維向量，數(shù)據(jù)量從10萬(wàn)條到160萬(wàn)條，查詢區(qū)域面積是總面積的1%.從表1可知，算法PRQ的查詢時(shí)間小于算法RRQ.算法BFRQ和算法VARQ的查詢時(shí)間最多.

表1 數(shù)據(jù)量與執(zhí)行時(shí)間的關(guān)系

實(shí)驗(yàn)2驗(yàn)證當(dāng)空間維度變化時(shí)對(duì)查詢時(shí)間的影響.實(shí)驗(yàn)中隨機(jī)生成維度分別為32、64、128、256、512的點(diǎn)數(shù)據(jù)，查詢區(qū)域在每維上的區(qū)間長(zhǎng)度是該維長(zhǎng)度的1/10，數(shù)據(jù)量均為100萬(wàn).

表2 空間維度與執(zhí)行時(shí)間的關(guān)系

從表2的數(shù)據(jù)可知，隨著空間維度的增加，算法PRQ的性能依然高效，而其他算法的性能明顯惡化.在d=512時(shí)算法BFRQ的查詢時(shí)間小于算法RRQ.當(dāng)d≥128時(shí)算法VARQ的查詢時(shí)間小于算法BFRQ.

4 結(jié)語(yǔ)

現(xiàn)有空間范圍串行查詢算法應(yīng)用到高維數(shù)據(jù)空間時(shí)執(zhí)行效率較低.本文采用并行技術(shù)提出一種高維空間范圍查詢并行算法.實(shí)驗(yàn)結(jié)果表明在高維數(shù)據(jù)空間中算法的查詢效率優(yōu)于線性掃描算法、基于R樹、VA文件空間范圍查詢算法.算法可行且有效.

[1] 郝忠孝.時(shí)空數(shù)據(jù)庫(kù)查詢與推理[M].北京:科學(xué)出版社，2010.

[2] 徐紅波，郝忠孝.一種采用Z曲線高維空間范圍查詢算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30(10):1952－1955.

[3] BEYER K，GOLDSTEIN J，RAMAKRISHNAN R.When is“nearest neighbor”meaningful[C]//Proceedings of the 7th International Conference on Database Theory，[S.l.]:[s.n.]，1999，217－235.

[4] WEBER R，BLOTT S.An Approximation－based data structure for similarity search[R].ESPRIT Project HERMES，1997.

[5] MANUEL J F，JOAQUIM A J.Indexing high－dimensional data for content－ based retrieval in large databases[C]//Proceedings of the 8th International Conference on Database Systems for Advanced Applications，[S.l.]:[s.n.]，2003:267 －274.

[6] 陳國(guó)良，孫廣中，徐 云，等.并行算法研究方法學(xué)[J].計(jì)算機(jī)學(xué)報(bào)，2008，31(9):1493－1502.