受限空間連接查詢及代價(jià)分析

楊澤雪，郝忠孝

（1.哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150080 哈爾濱;2.黑龍江工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，150050 哈爾濱;3.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001 哈爾濱）

受限空間連接查詢及代價(jià)分析

楊澤雪1，2，郝忠孝1，3

（1.哈爾濱理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150080 哈爾濱;2.黑龍江工程學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，150050 哈爾濱;3.哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，150001 哈爾濱）

針對(duì)已有的空間連接查詢算法無法解決限定范圍內(nèi)的空間連接查詢問題，提出了受限的空間連接查詢，在給定查詢范圍內(nèi)找到滿足某種空間謂詞的空間對(duì)象，給出直接解決方法和基于R－樹的受限空間連接查詢算法.基于QR樹的優(yōu)良特性，提出一種基于QR樹的受限空間連接查詢算法，該算法既避免了四叉樹的較大存儲(chǔ)代價(jià)，又克服了R樹的節(jié)點(diǎn)重復(fù)的弊端，使得受限空間連接查詢可以在多棵較小的R樹上進(jìn)行，較好地解決了空間連接查詢開銷較大的問題.對(duì)所提出的算法進(jìn)行代價(jià)分析，實(shí)驗(yàn)證明算法具有較高效率.

空間連接查詢;QR樹;空間數(shù)據(jù)庫(kù);R樹;受限空間連接查詢

近年來空間連接查詢成為空間數(shù)據(jù)庫(kù)中的熱點(diǎn)問題.給定兩個(gè)空間數(shù)據(jù)集，空間連接查詢找到兩個(gè)數(shù)據(jù)集中所有滿足某個(gè)空間謂詞的對(duì)象.空間謂詞包括交疊、相交、方向和距離等，本文主要研究相交的情況.例如:找到與某條河流相交的所有城市.按照兩個(gè)空間數(shù)據(jù)集是否有索引，可以將空間連接查詢分為3種情況:兩個(gè)數(shù)據(jù)集都有索引［1－7］;一個(gè)數(shù)據(jù)集有索引［8－9］;兩個(gè)數(shù)據(jù)集都沒有索引.

對(duì)于受限的空間連接查詢，沒有找到文獻(xiàn).考慮到若對(duì)于兩個(gè)數(shù)據(jù)集的空間連接只考慮某個(gè)限定的空間而不是整個(gè)空間，提出了受限的空間連接查詢.例如:找到某個(gè)國(guó)家與河流相交的城市.而已有的算法都不能直接用于某個(gè)限定的空間，根據(jù)已有的空間連接方法和范圍查詢方法，給出受限空間連接的直接解決方法，并給出基于R－樹的受限空間連接算法.針對(duì)基于R－樹的空間連接方法和四叉樹的空間連接方法的局限性，提出了基于QR樹的受限空間連接方法.

1 QR 樹［10］

圖1是二維空間QR樹的一個(gè)例子.在該例中，QR樹由一棵深度為2的四叉樹和5棵R樹組成.整個(gè)空間被劃分為2級(jí)共5個(gè)子空間:S0，S1，S2，S3，S4(S0=S1∪ S2∪ S3∪ S4)，Rt0，Rt1，Rt2，Rt3，Rt4這5棵R樹分別與之相關(guān)聯(lián).

圖1 二維空間QR－樹

2 基于R－樹的受限空間連接查詢

2.1 受限空間連接查詢的直接解決方法

給定兩個(gè)數(shù)據(jù)集和一個(gè)查詢范圍，受限的空間連接(CSJ)查詢是指找到與給定查詢范圍相交的且滿足某空間謂詞的數(shù)據(jù)對(duì)象的集合.

受限的空間連接查詢是空間連接查詢和空間范圍查詢的結(jié)合.雖然已有很多方法解決了空間連接查詢和范圍查詢，但已有的方法并不能直接實(shí)現(xiàn)受限的空間連接查詢.對(duì)于受限的空間連接查詢，直接的解決方法就是順序執(zhí)行兩個(gè)算法，按照兩個(gè)算法的執(zhí)行順序分為兩種方法，一種是先進(jìn)行范圍查詢，然后再進(jìn)行連接查詢，此方法表示為FRLJ.另一種方法是先進(jìn)行連接查詢，然后在進(jìn)行范圍查詢，此方法表示為FJLR.

假設(shè)兩個(gè)數(shù)據(jù)集都由R－樹索引，對(duì)應(yīng)R－樹索引分別為A和B，給定受限空間為W.利用基于R－樹的空間連接算法和基于R－樹的空間范圍查詢算法［11］，實(shí)現(xiàn)FRLJ的過程如下:

1)對(duì)A、B在W上分別執(zhí)行范圍查詢算法，獲取A中與W相交的結(jié)果集R1和B中與W相交的結(jié)果集R2;

2)對(duì)R1和R2執(zhí)行基于R－樹的空間連接算法，得到最終結(jié)果.

實(shí)現(xiàn)FJLR的過程如下:

1)對(duì)A、B執(zhí)行基于R樹的空間連接算法，獲取兩個(gè)數(shù)據(jù)集中相交的對(duì)象對(duì)的集合R;

2)對(duì)R執(zhí)行范圍查詢算法，判斷R中每一對(duì)對(duì)象對(duì)應(yīng)MBR是否與W相交，若相交，輸出結(jié)果，否則繼續(xù)其他結(jié)果的判斷.

分析兩種方法發(fā)現(xiàn)，如果受限范圍較小，F(xiàn)RLJ的效果較好，因?yàn)閳?zhí)行范圍查詢可以剪掉許多不會(huì)成為結(jié)果的節(jié)點(diǎn)，但隨著受限范圍的增大，F(xiàn)RLJ的優(yōu)勢(shì)逐漸減小;而對(duì)于FJLR來說，首先執(zhí)行連接查詢，對(duì)于兩個(gè)數(shù)據(jù)集的數(shù)量都不是很大時(shí)，效果較好，但隨著數(shù)據(jù)量的增大，連接代價(jià)變得很昂貴，因此效率不高.

2.2 基于R樹的受限空間連接查詢算法

基于上述分析，將范圍查詢和空間連接查詢結(jié)合在一起，提出基于R－樹的受限空間連接算法RCSJ.該算法的基本思想是:對(duì)兩棵R樹進(jìn)行同步遍歷，在遍歷過程中，設(shè)定節(jié)點(diǎn)是否與限定范圍W相交作為條件，按照節(jié)點(diǎn)的類型可分為兩個(gè)節(jié)點(diǎn)都為葉節(jié)點(diǎn)、一個(gè)為葉節(jié)點(diǎn)另一個(gè)為中間節(jié)點(diǎn)和兩個(gè)都為中間節(jié)點(diǎn)3種情況分別進(jìn)行處理.

3 基于QR－樹的受限空間連接查詢

利用QR樹將四叉樹和R－樹相結(jié)合的良好特性，提出一種基于QR樹的受限空間連接算法，在連接查詢的過程中判斷節(jié)點(diǎn)是否與限定空間相交，通過一次的樹遍歷可得到查詢結(jié)果.算法的基本思想是:利用四叉樹將空間進(jìn)行劃分，然后在每個(gè)子空間按照數(shù)據(jù)進(jìn)行劃分構(gòu)成R－樹，利用R－樹實(shí)現(xiàn)受限空間連接.因此按照空間劃分和數(shù)據(jù)劃分兩個(gè)方面實(shí)現(xiàn)受限空間連接.給定兩個(gè)數(shù)據(jù)集和對(duì)應(yīng)的兩棵QR樹，首先將兩棵QR樹的四叉樹節(jié)點(diǎn)進(jìn)行匹配，然后將匹配的節(jié)點(diǎn)對(duì)所對(duì)應(yīng)的R－樹的MBR以及受限空間進(jìn)行相交判斷，如果相交，則調(diào)用對(duì)應(yīng)的R－樹進(jìn)行連接.

3.1 節(jié)點(diǎn)匹配算法

考慮到QR樹的構(gòu)成，將節(jié)點(diǎn)分配到包含該節(jié)點(diǎn)的子空間中的最小者，則上一層子空間節(jié)點(diǎn)可能與下一層子空間的節(jié)點(diǎn)相交.所以要進(jìn)行不同層空間的節(jié)點(diǎn)匹配.算法如下.

3.2 連接算法

算法思想如下.

1)從兩棵QR樹的根開始，對(duì)兩棵QR樹進(jìn)行同步遍歷.

2)對(duì)于每一對(duì)節(jié)點(diǎn)，對(duì)與節(jié)點(diǎn)相關(guān)聯(lián)的子空間和受限空間進(jìn)行相交判斷，如果相交，則調(diào)用相應(yīng)的R－樹進(jìn)行連接，否則對(duì)該節(jié)點(diǎn)及其子節(jié)點(diǎn)的判斷結(jié)束.

3)針對(duì)兩個(gè)節(jié)點(diǎn)的類型，分成3種情況，對(duì)每種情況分別進(jìn)行處理.

算法 2QRCSJ(NA，NB，W)

輸入:兩棵 QR 樹 A、B 的節(jié)點(diǎn) NA，NB，限定空間W;

輸出:相交的數(shù)據(jù)對(duì)組成的結(jié)果集CRL.

4 代價(jià)分析

4.1 基于R樹的受限空間連接查詢代價(jià)分析

因?yàn)檫M(jìn)行受限空間連接要計(jì)算每一層節(jié)點(diǎn)與W相交且彼此相交的數(shù)據(jù)個(gè)數(shù)，因此要計(jì)算每一層R－樹節(jié)點(diǎn)與W相交的概率，為此有

所以總的連接代價(jià)為

4.2 基于QR樹的受限空間連接查詢代價(jià)分析

設(shè)兩棵QR樹分別為 ＜A，RA＞＜B，RB＞，其對(duì)應(yīng)數(shù)據(jù)個(gè)數(shù)分別為MA，MB，樹的高度分別為hA，hB，設(shè)hA≤hB，兩棵QR樹劃分子空間的個(gè)數(shù)分別為nA，nB，則對(duì)應(yīng)R － 樹個(gè)數(shù)也為nA，nB，其中

假設(shè)數(shù)據(jù)均勻分布，每棵R－樹對(duì)應(yīng)的數(shù)據(jù)個(gè)數(shù)為MA/nA，MB/nB，設(shè)兩棵R － 樹RAu，RBv的高度分別為hRAu和hRBv，設(shè)hRAu≥hRBv，由上述分析可知，兩棵R－樹進(jìn)行空間連接代價(jià)為

式中:NRAu，j為 RAu 在第 j層的結(jié)點(diǎn)數(shù);sRAu，j，t為 RAu在第j層的結(jié)點(diǎn)的平均范圍.

對(duì)于QR－樹的受限空間連接代價(jià)，主要計(jì)算進(jìn)行R－樹連接的次數(shù)，按照兩個(gè)QR－樹節(jié)點(diǎn)是否同層，分別考慮:

綜合以上兩種情況，基于QR－樹的受限連接查詢總代價(jià)為

4.3 兩種查詢代價(jià)比較

要比較QRCSJ和RCSJ的查詢代價(jià)，通過計(jì)算比值ratio=CQR(A，B)/CR(A，B)的值來衡量，如果ratio＜1，說明QRCSJ要比RCSJ好.

因此CQR(A，B)明顯小于CR(A，B).

5 結(jié)果

實(shí)驗(yàn)是在 PentiumⅣ2.8 GHz CPU，1 GB內(nèi)存，Windows XP平臺(tái)上用Visual C++6.0實(shí)現(xiàn)的，磁盤頁(yè)大小為1 024 Bytes.測(cè)試數(shù)據(jù)是由Spa－tial Data Generator(http://www.rtreeportal.org)產(chǎn)生的標(biāo)準(zhǔn)分布的數(shù)據(jù)，數(shù)據(jù)尺寸為12、13 K.對(duì)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，圖2對(duì)受限范圍的大小對(duì)各個(gè)算法的影響進(jìn)行了實(shí)驗(yàn).圖2中，x坐標(biāo)軸表示受限范圍的占整個(gè)數(shù)據(jù)空間的百分比，F(xiàn)RLJ、FJLR、RCSJ和QRCSJ表示上述的4種受限空間連接算法，其中QR－樹的高度為3.由圖2可知，基于QR樹的受限空間連接查詢明顯優(yōu)于其他幾個(gè)算法.隨著查詢范圍的增大，F(xiàn)RLJ的查詢時(shí)間逐漸增加，這是因?yàn)殡S著查詢范圍的增大，先做范圍查詢的優(yōu)勢(shì)越來越小，當(dāng)查詢范圍變?yōu)檎麄€(gè)數(shù)據(jù)區(qū)域的時(shí)候，F(xiàn)RLJ的效率是很低的.FJLR的查詢時(shí)間逐漸變少，這是因?yàn)殡S著查詢范圍的增大，由連接查詢得到的中間結(jié)果可能成為最終結(jié)果的可能性逐漸增大.

圖2 算法執(zhí)行時(shí)間比較

6 結(jié)論

1)提出受限的空間連接查詢，給出直接的解決方法和基于R－樹的受限空間連接算法.基于QR樹的優(yōu)良特性，給出了基于QR樹的受限空間連接算法.

2)通過代價(jià)分析得到基于QR樹的受限空間連接算法與基于R樹的算法代價(jià)比值小于1，證明所提算法優(yōu)于其他的方法.

［1］BRINKHOFF T，KRIEGEL H P，SEEGER B.Efficient processing of spatial joins using R－trees［C］//Proceedings of the ACM SIGMOD International Conference on Management of Data.Washington，DC:ACM，1993:237－246.

［2］HUANG Yunwu，JING Ning，RUNDENSTEINER E A.Spatial joins using R－trees:breadth－first traversal with global optimizations［C］//Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco， CA:Morgan Kaufmann PublishersInc，1997:396－405.

［3］BRINKHOFF T，KRIEGEL H P，SEEGER B.Parallel processing of spatial joins using R－trees［C］//Proceedings of the 12th International Conference on Data Engineering.New Orleans:IEEE，1996:258－265.

［4］CHEN Hue－ling，CHANG Ye－in.Spatial joins based on NA－trees［J］.Journal Information Processing Letters，2009，109(13):713－718.

［5］HOEL E G，SAMET H.Benchmarking spatial join operations with spatial output［C］//Proceedings of the 21th International Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc，1995:606－618.

［6］LIMA A A B，ESPERANCA C，MATTOSO M.A parallel spatial join framework using PMR－quadtrees［C］//Proceedings of the 11th International Workshop on Database and Expert Systems Applications.Los Alamitos:IEEE，2000:889－893.

［7］郝忠孝.時(shí)空數(shù)據(jù)庫(kù)－查詢與推理［M］.北京:科學(xué)出版社，2010:220－230.

［8］GURRET C，RIGAUX P.The sort/sweep algorithm:a new method for R－tree based spatial joins［C］//Proceedings of the 12th International Conference on Statistical and Scientific Database Management.Washington，DC:IEEE Computer Society，2000:153－165.

［9］JACOX E H，SAMET H.Spatial join techniques［J］.ACM Transactions on Database Systems，2007，32(1):1－44.

［10］FU Yuchen，HU Zhiyong，WEI Guo，et al.QR－tree:a hybrid spatial index structure［C］//Proceedings of International Conference on Machine Learning and Cybernetics.Xi－an:Institute of Electrical and Electronics Engineers Inc，2003:459－463.

［11］GUTTMAN A.R－trees:a dynamic index structure for spatial searching［J］.ACM SIGMOD，1984，14(2):47－57.

［12］THEODORIDIS Y，STEFANAKIS E，SELLIS T.Efficient cost models for spatial queries using R－trees［J］.IEEE TKDE，2000，12(1):19－32.

Constrained spatial join queries and cost analysis

YANG Ze－xue1，2，HAO Zhong－xiao1，3

(1.College of Computer Science and Technology，Harbin University of Science and Technology，150080 Harbin，China;2.Dept.of Computer Science and Technology，Heilongjiang Institute of Technology，150050 Harbin，China;3.College of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China)

Aimed at the problem that the existed spatial join algorithms can not solve the spatial join query within the constrained range，the constrained spatial join query is proposed which finds all the pairs of objects satisfying some spatial predicate within the given range.The directed solving methods and algorithms based on R－tree are given.Based on good property of QR－tree，a constrained spatial join algorithm is proposed which avoids larger storage cost of quadtree and overcomes the drawbacks of R－tree node overlapping.Thus the algorithm implements the constrained spatial join query on many small R－tree and the problem of expensive spatial join overhead is solved.The cost analysis for the proposed algorithms is given.Experiments show the algorithm has high efficiency.

spatial join query;QR－tree;spatial database;R－tree;constrained spatial join query

TP311.13

A

0367－6234(2012)11－118－05

2011－08－22.

國(guó)家自然科學(xué)基金資助項(xiàng)目(60673136);黑龍江省自然科學(xué)基金資助項(xiàng)目(F201134).

楊澤雪(1978—)，女，博士，講師;

郝忠孝(1940—)，男，教授，博士生導(dǎo)師.

楊澤雪，yzx1978@126.com.

(編輯 張 紅)