一種基於ab直方圖的空間查詢選擇率估計方法

2023-06-13 19:30:06 2

專利名稱：一種基於ab直方圖的空間查詢選擇率估計方法
技術領域：
本發明涉及一種基於AB直方圖的空間查詢選擇率估計方法，屬於空間數據查詢 與處理技術領域。
背景技術：
近年來，空間資料庫在許多應用中變得越來越重要，如地理信息系統(GIS)、計算 機輔助設計(CAD)、圖像處理、多媒體系統等。由於空間查詢能夠處理空間資料庫中的多維 數據和滿足廣泛的應用類型，因此對空間查詢的研究近年來頗受關注，這是因為空間數據 量龐大，數據結構複雜，操作代價昂貴，關係資料庫中的查詢優化代價模型並不能完全適用 於空間數據，所以空間查詢的優化勢必成為空間應用的難點和突破點。空間選擇和空間連接是空間查詢中最重要，也是代價(I/O和CPU代價)比較昂貴 的兩種操作，有關他們的查詢優化引起了廣泛關注。目前，基於查詢代價估算的代價模型是 最常用的一種查詢優化方法。估算代價的主要問題是估算查詢結果(選擇率)的大小。在資料庫系統中，對於給定的查詢，查詢優化器比較各種不同執行方案的代價，從 中選出代價最小者執行。選擇率估算準確與否直接影響到相應方案代價估算的準確性，從 而對查詢優化器的質量有實質性的影響。因此，空間查詢的選擇率估計在尋找最有效的執 行計劃時是很重要的。用於估算選擇率的算法主要有以下三種採樣法、參數法和直方圖。在眾多方法 中，基於直方圖的空間查詢選擇率估計是最常用的一種方法。其基本思想採用某種策略將 數據空間劃分為數個子空間，一個記錄單元對應一個子空間；在記錄單元中統計落在其對 應子空間內的對象數目；用某種方法對這些統計值進行估計，得到查詢結果集大小的估算 值，由此估算查詢代價。這些記錄單元稱為桶，桶的集合稱為直方圖。用這種方法建立的空 間直方圖存在一個嚴重的缺陷重複計數問題。國內外學者先後提出了 MinSkew、SQ、CD、Euler、MP、GH等直方圖。其中，MinSkew 和SQ直方圖是通過有效的劃分數據空間來適應任意查詢窗口，但它們在為線和多邊形數 據的應用中存在重複計數問題，故其選擇率估算的誤差較大。CD直方圖將數據空間劃分為 大小相等的格網單元，用四個子直方圖分別與數據對象MBR的四個角點對應，子直方圖中 的一個桶存儲落入該桶中對應角點的數目，它能精確的返回與查詢窗口相交的地理幾何要 素數目；Euler直方圖是利用Euler原理構建的直方圖，它在拓撲關係選擇率估計方面有 所特長，但是由於存在「邊界問題」，無法準確估計查詢區域與直方圖格網線不重合時的選 擇率；雖然CD和Euler直方圖能解決重複計數問題，但是它們不能區分更為精細空間關係 (如cotains，overlap等)，在圖2中有兩種不同的情況，⑶和Euler直方圖卻分別存儲了 相同的信息(見附圖2)。Sim等人在Euelr直方圖的基礎上，研究了更為精細的4種拓撲 關係(disjoint，cotains, within, overlap)的選擇率估計，提出了 3種近似的算法，但在 計算Me時存在較大的誤差，使其選擇率估計誤差較大。後來，Iiu等人提出了一種精確的 多尺度模式來解決上述4種關係的選擇率估計算法。MinSkew、SQ、CD、Euler、以及Euler直方圖的改進算法均是為空間選擇操作提出的，尚且不能運用到空間連接操作中。有關空間連接的直方圖研究較少。目前主要有MP算法和GH直方圖。MP算法的 基本假設是與格網單元相交的數據對象不僅是均勻分布的，而且要有相似的寬度和高度。 因此，在精細格網粒度下，估計效果非常差。一般只有數據對象的大小與查詢窗口的大小相 當這種極端情況下，MP算法的誤差才比較小。GH直方圖是基於對兩個相交的矩形總會產生 四個相交的點的觀察，空間連接的選擇率能通過首先估計兩個數據集間相交點的數目，然 後除以4得到。GH直方圖的精確度依賴於數據對象的高和寬比查詢窗口的高和寬相對要小 的假設，即如果數據集中是一些較小的數據對象，GH估算精度較高，反之，數據集中以較大 對象為主，GH估算精度較低。MP算法和GH直方圖只能用於空間連接操作，不能用於空間選 擇的選擇率估計。上述已有的各種直方圖，除了不能同時支持空間選擇和空間連接操作的選擇率估 計外，也沒有指出從已有的直方圖生成查詢結果數據直方圖的方法，即它們只對原始數據 預先建立直方圖。而一個查詢操作是按照查詢計劃樹分步執行的，查詢樹中每個節點的選 擇率對於代價模型中的參數都是很重要的。但是目前並沒有估計後續節點選擇率的直方圖 算法，不能很好的滿足空間查詢優化的要求。

發明內容
本發明的目的是提出一種基於AB直方圖的空間查詢選擇率估計方法。該方法能 較精確地估計disjoint，intersect, within, contains和overlap等5種空間關係的空間 選擇和空間連接的選擇率，而且能從原始數據的直方圖生成查詢結果數據的直方圖，滿足 查詢樹中後續節點選擇率估計的需求。本發明提出的一種基於AB直方圖的空間查詢選擇率估計方法，包括以下步驟第一步，按AB直方圖的建立方法，為需要進行選擇率估計的矢量數據建立直方 圖；第二步，用戶給定查詢操作條件；第三步，如果所述查詢操作條件中只涉及一個矢量數據集合，那麼該操作為空間 選擇操作，則先估算直方圖各桶滿足給定空間選擇條件的概率，再估計該空間選擇操作的 選擇率；第四步，如果所述查詢操作條件中涉及兩個以上矢量數據集合，那麼該操作為空 間連接操作，則先估算直方圖各桶滿足給定空間連接條件的概率，再估計兩個數據集合空 間連接操作的選擇率；
第五步，利用原有的AB直方圖生成查詢結果數據的AB直方圖，估算查詢樹中後續 節點的選擇率。上述第三步中提到的估算直方圖各桶滿足給定空間選擇條件的概率，此處給定的 空間選擇條件是指disjoint， intersect, within, contains, overlap關係中的一種或多 種。其中，對估算disjoint和overlap的概率方法加以說明。根據Max J. Egenhofer 等人提出的 9-1 模型(9-intersection model)可知，兩個 空間對象P、Q間的空間關係可用以下3X3矩陣來表示
formula see original document page 7
其中，P. i，Q. i，P. e，Q. e，P. b，Q. b分別表示兩個對象的內部、外部和邊界。如果 僅比較兩個空間對象的內部是否相交，可以將空間關係區分為disjoint和intersect兩種 互補情形；如果通過比較兩個空間對象的內部與外部的相交情況，則可以得到disjoint， overlap, contains, within禾口 equal五種互不相容'清形，艮intersect關係可以進一步分 角軍為overlap, contains, within禾口 equal這四禾中關係。在進行概率估算時，一般假設存在equal關係的概率為0。因為在實際應用中，查 詢窗口與空間對象的MBR構成equal關係的數目最多為1 (正常情況下為0)，相對於整個 數據集合中很多空間對象而言，equal關係的概率近似為0，故該假設是合理的。由於相離 disjoint和相交intersect是互不相容的兩種情況、且構成互補關係，依據概率的基本性 質，某桶滿足disjoint的概率等於1減去該桶滿足intersect的概率。由於intersect關 系可以分解為overlap，contains, within和equal互不相容的四種情形，且equal的概率 為0，依據概率的加法公式，某桶滿足overlap概率等於該桶滿足intersect的概率分別減 去該桶滿足within、contains的概率。上述估算概率方法同樣適用於第四步中估算直方圖各桶滿足給定空間連接條件 的概率。本發明提出的一種基於AB直方圖的空間查詢選擇率估計方法，其優點如下(I)AB直方圖是一種更為概括、實用的空間直方圖。它不僅能支持空間選擇的選擇 率估計，而且能支持空間連接的選擇率估計。(2)AB 直方圖對 disjoint, intersect, within, contains 禾口 overlap 五種空間關 系的選擇率估計具有較高的精度。此外，利用空間關係之間相互轉換的規則，AB直方圖能 解決更多更精細空間關係的選擇率估計問題。(3) AB直方圖能從原始數據的直方圖生成查詢結果數據的直方圖，滿足查詢樹中 後續節點選擇率估計的需求。直方圖轉換法使得估計查詢樹中後續節點以及整個查詢樹的 選擇率成為可能。這些節點的選擇率在空間查詢的優化與執行中是一個重要參數。(4)在空間資料庫中，AB直方圖易於與傳統的屬性直方圖集成。因為除了計算不 同空間關係概率的邏輯方法屬於AB直方圖特有外，AB直方圖的大多數概念(例如用圖形 化的方法來表示各種空間關係的概率等)都與傳統的屬性直方圖相同。這樣，在空間查詢 優化過程中能充分借鑑傳統屬性直方圖已有的良好性質。


圖1為本發明實現流程圖；圖2a和圖2b、圖2c為⑶和Euler直方圖在處理精細空間關係時的缺陷；圖3a和圖3b為矢量數據、環形桶以及AB直方圖示意圖；圖4a、圖4b、圖4c、圖4d為圖3所示矢量數據與查詢窗口空間關係的概率直方圖；圖5a為另外一個矢量數據集、圖5b為其對應的AB直方圖；圖6a為intersect空間選擇查詢結果AB直方圖、圖6b為intersect空間連接查詢結果AB直方圖；圖7a為對比實驗中用到的中國某個城市的土地利用矢量數據、圖7b為查詢窗口 數據；圖8為5種空間關係的空間選擇的選擇率實驗結果；圖9為5種空間關係的空間連接的選擇率實驗結果，Dl表示圖7(a)中的 土地利 用數據；D2表示圖7(b)中的查詢窗口數據。
具體實施例方式1、以圖3所示的矢量數據為例，說明本發明中空間選擇查詢選擇率估計的具體實 施步驟(1. 1)為圖3所示的矢量數據生成AB直方圖；用每個數據對象的MBR代替相應的數據對象，對整個數據空間劃分12行X 12列 格網單元，根據每個對象MBR所在位置判斷它所屬的環形桶，如果沒有環形桶包含該對象， 則向AB直方圖中增加一個環形桶，記錄下環形桶的範圍，並將桶內數值置為1 ；如果有相 應的環形桶包含該對象，則將桶內數值增加1。重複這一過程，直到所有的數據對象都分配 到了相應的環形桶內。數據對象的MBR，以及環形桶如圖3 (a)所示；建立的AB直方圖如圖 3(b)所示。該直方圖中共有A、B、C、D四個環形桶，範圍分別為(2，2;5，5)、(6，2;10，5)、 (2,6 ；7，10)、(0,0 ；12，12)，每個環形桶內分別有2、3、1、2個數據對象。(1. 2)用戶給定空間查詢操作條件，此處為空間選擇操作；(i)用戶需要指定一個查詢窗口，此處的查詢窗口如圖3(a)左下角所示。(ii)估計每個環形桶滿足intersect關係的概率，如圖4(a)所示；估計後A、B、C、D四個環形桶與查詢窗口滿足intersect關係的概率分別為1. 0、 0. 3、0· 0、1. O0(iii)估計每個環形桶滿足within關係的概率，如圖4(b)所示；估計後A、B、C、D四個環形桶與查詢窗口滿足within關係的概率分別為0. 5,0. 0、 0. 0、0. O0(iv)估計每個環形桶滿足contains關係的概率，如圖4(c)所示；估計後A、B、C、D四個環形桶與查詢窗口滿足contains關係的概率分別為0. 0、 0. 0、0· 0、0· 5。(ν)根據某桶滿足overlap概率等於該桶滿足intersect的概率分別減去該桶滿 足within、contains的概率來計算每個環形桶滿足overlap關係的概率，如圖4(d)所示；經計算，A、B、C、D四個環形桶與查詢窗口滿足overlap關係的概率分別為0. 5、 0. 3、0· 0、0· 5。(1. 3)根據空間選擇的選擇率等於每個環形桶內對象數目與該桶滿足給定選擇條 件的概率乘積的總和，計算用戶給定查詢窗口內滿足給定空間條件的空間對象選擇率。圖3(a)中，查詢窗口與空間對象構成intersect關係的估計值為 2X1. 0+3X0. 3+1X0. 0+2X1 = 4. 9 ；查詢窗口與空間對象構成overlap關係的估計值為 2X0. 5+3X0. 3+1X0. 0+2X0.5 = 2.9。同理可得其他空間關係的估計值。2、以圖3和圖5所示的矢量數據為例，說明本發明中intersect空間連接查詢選擇率估計的具體實施步驟(2. 1)為圖3和圖5所示的矢量數據生成AB直方圖；對兩個矢量數據的數據空間均劃分為12行X 12列格網單元，分別建立AB直方 圖，步驟如具體實施步驟1. 1所述。由于格網單元未變，故圖3中矢量數據生成的AB直方圖 也不變。圖5中矢量數據生成的直方圖共有A』、B』兩個環形桶，範圍分別為(5，7;9，10)、 (1，1 ;6，3)，每個環形桶內分別有1、1個數據對象。(2. 2)用戶給定空間查詢操作條件，此處為intersect空間連接操作；(i)分別獲取數據對象的MBR分布圖；將圖3數據集的MBR當作基本數據集合，圖5數據集的MBR作為查詢窗口集合。為下面敘述方便起見，將圖5中環形桶A』的數據對象MBR記為I，環形桶B』中的 數據對象記為II，即圖5中總共有2個查詢窗口。(ii)估計圖3中每個環形桶內intersect空間關係的概率。如果bucket [i]的外環與查詢窗口矩形相離，則P (i) = 0.0 ；如果bucket [i]的 外環與查詢窗口矩形相交、且內環與查詢窗口矩形相離，此時，需要計算bucket [i]與查詢 窗口矩形重疊部分的長度length和寬度wide，則P (i) =min (length, wide)+外環與內 環間的距離；否則，P(i) = 1。計算結果如下①估計後圖3中A、B、C、D四個環形桶內數據對象與圖5中查詢窗口 I滿足 intersect 關係的概率分別為 0. 0,0. 0,1. 0,1. 0 ；②估計後圖3中A、B、C、D四個環形桶內數據對象與圖5中查詢窗口 II滿足 intersect 關係的概率分別為 0. 8,0. 0,0. 0,1. 0 ；(2. 3)根據基本數據集合空間連接的選擇率是通過計算該數據集合中每個環形桶 內對象的數目乘以該桶滿足給定空間連接條件的概率之和，則基本數據集合(圖3)相對於 查詢窗口數據集合(圖5)的intersect空間連接選擇率為
I^1CC(I) χ max (P(U), P(i 2), "」P(U)」,」 P(U))) =2 χ max (ο. ο, ο. 8)+3 χ
max(0. O, 0. 0)+1 X max (1. 0』 0. 0)+2 X max (1.0，1.0) -2 X 0.8+3 X 0.0+1 X 1.0+2 X1.0=4.6。同理，可以將圖3數據集的MBR當作查詢窗口集合，圖5數據集的MBR作為基本數 據集合，計算圖5數據集相對於圖3數據集的intersect空間連接選擇率。與具體實施方式
2相似，可估計within、contains和overlap等空間連接查詢的選擇率。3、以intersect為例，說明本發明中查詢結果的AB直方圖生成方法。(3. 1) intersect空間選擇操作的查詢結果AB直方圖。以圖3中intersect空間選擇操作為例。由空間選擇查詢結果AB直方圖的桶內 數值是由原始數據的AB直方圖中各個環形桶內數值與該桶滿足給定空間選擇條件的概率 之積得到可知，intersect空間選擇查詢結果的AB直方圖的環形桶內數值是由原始數據的 AB直方圖中各個環形桶內數值與該桶滿足intersect空間選擇條件的概率之積得到。則 查詢結果AB直方圖中A、B、C、D四個環形桶內數值分別是2X1.0 = 2.0 ;3X0. 3 = 0. 9 ；1X0.0 = 0.0 ;2X1.0 = 2.0。生成結果的AB直方圖如圖6 (a)所示。(3. 2) intersect空間連接操作的查詢結果AB直方圖。以圖3和圖5中intersect空間連接操作為例。由新生成的AB直方圖桶內數值是由原環形桶內數值乘以該桶與查詢窗口數據集合中多個對象之間滿足給定空間連接條 件的所有概率之均值可知，圖3中的矢量數據進行intersect空間連接操作後，新生成的 AB直方圖環形桶內數值是由原環形桶內數值乘以該桶與查詢窗口數據集合中多個對象之 間滿足intersect空間連接條件的概率均值得到。按照= Ce(0 X I1 Pft 0/s，則圖
3中數據新生成的AB直方圖中A、B、C、D四個環形桶內數值分別是:2X (0. 0+0. 8)/(1+1) =0. 8 ；3X (0. 0+0. 0)/(1+1) = 0. 0 ;1X (1. 0+0. 0)/(1+1) = 0. 5 ；2X (1. 0+1. 0)/(1+1)= 2.0。生成結果的AB直方圖如圖6(b)所示。同理可得圖5中數據intersect空間連接操 作後的查詢結果AB直方圖，此處從略。與具體實施方式
3相似，同理可以得到disjoint，within，contains和overlap等 空間選擇和空間連接查詢結果的AB直方圖。對比分析實驗我們以中國某個城市的1 10，000 土地利用數據為實驗數據，它包含17207個 多邊形，其MBR分布如圖7 (a)所示，另外我們定義9個矩形作為查詢窗口數據，如圖7 (b) 所示。在空間選擇測試中，我們將9個矩形分別作為不同的查詢窗口，來估計滿足特定空 間關係的土地利用數據的數目。在空間連接測試中，9個矩形被看成是另一個數據集，當作 查詢窗口的集合。用本發明方法，我們分別對disjoint、intersect、within、contains和 overlap等關係的空間選擇和空間連接操作的選擇率估計進行了實驗，並計算了選擇率估 計值與真值之間的相對誤差。空間選擇與空間連接的實驗數據統計結果分別見圖8和圖9。可見，AB 直方圖能用於估計 disjoint, intersect, within, contains 禾口 overlap 關係的空間選擇和空間連接的選擇率。本發明的方法的誤差較小，具有較高的準確率。本發明說明書中未作詳細描述的內容屬於本領域專業技術人員公知的現有技術。以上所述僅是本發明的優選實施方式，應當指出，對於本技術領域的普通技術人 員來說，在不脫離本發明原理的前提下，還可以做出若干改進和潤飾，這些改進和潤飾也應 視為本發明的保護範圍。
權利要求
一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在於該方法包括如下步驟第一步，按AB直方圖的建立方法，為需要進行選擇率估計的矢量數據建立直方圖；第二步，用戶給定查詢操作條件；第三步，如果所述查詢操作條件中只涉及一個矢量數據集合，那麼該操作為空間選擇操作，則先估算直方圖各桶滿足給定空間選擇條件的概率，再估計該空間選擇操作的選擇率；第四步，如果所述查詢操作條件中涉及兩個以上矢量數據集合，那麼該操作為空間連接操作，則先估算直方圖各桶滿足給定空間連接條件的概率，再估計兩個數據集合空間連接操作的選擇率；第五步，利用原有的AB直方圖生成查詢結果數據的AB直方圖，估算查詢樹中後續節點的選擇率。
2.根據權利要求1所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在 於，所述AB直方圖建立方法包括如下步驟(2. 1)將需要進行選擇率估計的矢量數據的整個空間範圍劃分為大小相等的格網單元；(2. 2)最初AB直方圖中沒有任何環形桶；(2. 3)對於每個對象，如果它的最小外包矩形MBR不在任意一個環形桶的內外矩形之 間，則向AB直方圖中增加一個環形桶，並將環形桶內的數值賦為1 ；否則，將對象MBR所在 的環形桶內數值增加1 ；(2. 4)AB直方圖中每個環形桶需要記錄兩類信息環形桶的範圍，以及落入該桶內數 據對象MBR的個數，記為{(R(i)，C(i))}，其中1彡i彡N，N是直方圖中環形桶的數目。
3.根據權利要求1所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在 於，所述給定空間選擇和空間連接條件均是指disjoint，intersect, within, contains, overlap關係中的一種或多種。
4.根據權利要求1所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在 於，先估算直方圖各桶滿足給定空間選擇條件的概率，再估計該空間選擇操作的選擇率方 法，包括如下步驟(4. 1)估算直方圖各桶f薛足 disjoint, intersect, within, contains, overlap 中單個 空間選擇條件的概率；(4. 2)估算直方圖各桶f薛足 disjoint, intersect, within, contains, overlap 中複合 空間選擇條件的概率；對於涉及複合空間選擇條件的查詢都可以轉換為由or或and連接的單個空間選擇 條件查詢的組合，對於其中的單個空間選擇條件按(4. 1)步計算其滿足單個空間條件的概 率，對於由or或and連接的複合空間選擇條件，則按下列公式1和公式2來計算該複合條 件的概率formula see original document page 2(4. 3)基於(4. 1) (4. 2)步得出各個桶滿足給定空間選擇條件的概率，則該空間選擇的 選擇率等於每個環形桶內對象數目與該桶滿足給定選擇條件的概率乘積的總和，即空間選擇的選擇率為Σ ^1N(CG)XP(D),其中，1彡i彡N，N是直方圖中環形桶的數目，P⑴是 桶i滿足給定空間條件的概率，C(i)是落入該桶內數據對象MBR的個數。
5.根據權利要求1所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在 於，先估算直方圖各桶滿足給定空間連接條件的概率，再估計兩個數據集合空間連接操作 的選擇率方法，包括如下步驟(5. 1)對已經建立好AB直方圖的兩個矢量數據集合，分別獲取數據對象的MBR分布圖；(5. 2)在估計兩個數據集合空間連接的選擇率時，將一個數據集的MBR當作基本數據 集合，另一個數據集的MBR作為查詢窗口數據集合；(5. 3)基本數據集合直方圖的每個桶滿足給定空間連接條件的概率是該桶與查詢窗口 數據集合中多個對象之間滿足給定連接條件的概率最大值，即max(P(i，l)，P(i，2)，…， P(i，l)，…，P(i，s))，其中，P(i，l)是基本數據集合與查詢窗口數據集合中空間對象1間 滿足給定空間連接條件的概率，s為查詢窗口數據集合中空間對象的數目；(5. 4)基本數據集合空間連接的選擇率是通過計算該數據集合中每個環形桶內對象 的數目乘以該桶滿足給定空間連接條件的概率之和，即Σ i = T(C⑴Xmax(P(i，l)，P(i， 2)，...，P(i，l)，...，P(i，s)))，其中，m為直方圖中環形桶的數目；(5. 5)反之，將基本數據集合作為查詢窗口數據集合，將查詢窗口數據集合作為基本數 據集合，通過(5. 3)-(5. 4)步可以估算出原查詢窗口數據集合滿足給定空間連接條件的選 擇率。
6.根據權利要求1所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在 於，所述利用原有的AB直方圖生成查詢結果數據的AB直方圖，包括如下步驟(6. 1)空間選擇查詢結果AB直方圖的桶內數值是由原始數據的AB直方圖中各個環形 桶內數值與該桶滿足給定空間選擇條件的概率之積得到；(6.2)由於空間連接查詢的結果是由兩個空間列組成的數據對g，g』，在滿足連接條件 數據集合中，g，g』的AB直方圖中的每個環形桶內數值可分別按公式3和公式4計算，即新 生成的AB直方圖桶內數值是由原環形桶內數值乘以該桶與查詢窗口數據集合中多個對象 之間滿足給定空間連接條件的所有概率之均值Ci(I) = CeCOx IU P(t i)/s 公式 3 K(I) = CKOxSkPi(U)Zi^SA其中，Ctl(i)，C'0(i)分別是兩個數據集合對應的AB直方圖中第i個環形桶內數據對象 MBR的數目A⑴，C，「i)分別是新生成的AB直方圖環形桶內數據對象MBR的數目；P(i, 1)是基本數據集合第i個環形桶與查詢窗口數據中第1個對象滿足給定空間連接條件的概 率，P』(i，1)是查詢窗口數據集合第i個環形桶與基本數據集合中第1個對象滿足給定空 間連接條件的概率；t、s分別為兩個數據集合中空間對象的數目。
7.根據權利要求2所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵 在於，所述環形桶是由數據對象的MBR所在的格網單元形成的環形區域，環形桶的範圍用 (xa, ya ；xb, yb)表示，其中，(xa, ya)，(xb, yb)分別表示環形桶外環的左下角坐標，右上角 坐標。
8.根據權利要求4所述的一種基於AB直方圖的空間查詢選擇率估計方法，其特徵在於，所述 disjoint, intersect, within, contains, overlap空間關係中給定空間條件的概率估計法，包括如下步驟(8. 1)估計i桶bucket [i]滿足intersection概率方法如下A.若bucket[i]的外環與查詢窗口矩形相離，則P (i) = 0.0 ；B.若bucket[i]的外環與查詢窗口矩形相交、且內環與查詢窗口矩形相離，此時， 需要計算bucket [i]與查詢窗口矩形重疊部分的長度length和寬度wide，則P (i)= min (length, wide) +外環與內環間的距離；C.其他情況，P⑴=1；(8. 2)估計i桶滿足within概率方法如下A.若bucket[i]的外環與查詢窗口矩形不構成within關係，且內環與查詢窗口也不構 成 within 關係，則 P (i) = 0.0 ；B.若bucket[i]的外環與查詢窗口矩形不構成within關係、且內環與查詢窗口構成 within關係，則P(i) = bucket[i]的內環的四條邊與相應的查詢窗口矩形四條邊的最小距 離+外環與內環間的距離；C.其他情況，P⑴=1；(8. 3)估計i桶滿足contains概率方法如下A.若bucket[i]的外環與查詢窗口矩形不構成contains關係，且內環與查詢窗口也不 構成 contains 關係，則 P(i) =0.0；B.若bucket[i]的外環與查詢窗口矩形不構成contains關係、且內環與查詢窗口構 成contains關係，則P(i) = bucket[i]的外環的四條邊與相應的查詢窗口矩形四條邊的 最小距離+外環與內環間的距離；C.其他情況，P⑴=1；(8. 4) i桶滿足disjoint概率是1減去該桶滿足intersect的概率；(8. 5) i桶滿足overlap概率是該桶滿足intersect的概率分別減去該桶滿足within、 contains的才既率。
全文摘要
一種基於AB直方圖的空間查詢選擇率估計方法，屬於空間數據查詢與處理技術領域。本發明首先對需要查詢的矢量數據建立AB直方圖，用戶給定查詢操作條件，空間選擇操作的選擇率是每個環形桶內對象數目與該桶滿足給定選擇條件的概率乘積的總和；而空間連接操作的選擇率則是通過計算一個數據集中每個環形桶內對象的數目乘以該桶與另一個數據集中多個對象之間滿足給定連接條件的概率最大值的總和。根據原始AB直方圖以及相應空間關係的概率值，生成查詢結果數據的AB直方圖。本發明能較精確地估計含有disjoint，intersect，within，contains和overlap等空間關係的查詢選擇率，且能從原數據直方圖生成查詢結果數據的直方圖，滿足查詢樹中後續節點選擇率估計的需求。
文檔編號G06F17/30GK101826098SQ20101010526
公開日2010年9月8日 申請日期2010年2月3日 優先權日2010年2月3日
發明者周成虎, 張明波, 朱焰爐, 程昌秀, 謝炯, 陳榮國 申請人:中國科學院地理科學與資源研究所