[發(fā)明專利]基于最大間隙空間映射的高維數據索引方法

無效

• 申請?zhí)枺?/td>: 200810011323.5
• 申請日: 2008-05-09
• 公開（公告）號: CN101266607A
• 公開（公告）日: 2008-09-17
• 發(fā)明（設計）人: 王國仁;王波濤;王斌;趙相國;喬百友;韓東紅;于亞新;趙宇海;信俊昌;張恩德
• 申請（專利權）人: 東北大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 沈陽東大專利代理有限公司
• 代理人: 朱光林

技術領域

本發(fā)明屬于數據庫領域，特別涉及一種數據索引方法，具體涉及一種基于最大間隙空間映射的高維數據索引方法。

背景技術

隨著在各應用領域中多媒體數據源的不斷增長，在大型數據庫中快速處理基于內容的相似性查找變得越來越重要。為了加速高維空間中相似性查找，常用的方法是設計一個高維索引來支持這種類型的查詢。高維索引方法可以分為兩大類：基于向量空間的索引結構和基于度量空間的索引結構。R-tree及其變種是前者的代表，它們是基于向量空間中的相對位置來管理數據。其它類型的索引結構，包括VP-tree，MVP-tree，M-tree，MB⁺-tree，Slim-tree，M+-tree，是基于度量空間的索引技術，它們是基于數據對象間的相對距離來管理數據。

VP-tree是第一種支持相似性查詢的層次索引結構，它使用數據對象到代表點之間的相對距離和三角不等式來進行數據空間的過濾。因為VP-tree索引結構較小的扇出(因而索引的高度很高)而引起了大量的距離計算，從而大大影響了它的查詢性能。應該指出的是，在度量空間中距離計算是非常復雜且非常耗時的。為了克服上述問題，MVP-tree索引結構使用多個代表點，從而大大增加了索引的扇出，降低了索引的高度。VP-tree和MVP-tree都是靜態(tài)的基于度量空間的索引結構，它們采用一個自上而下的方法來構建。這就意味著這些索引無法支持數據的更新和刪除。

M-tree是基于度量空間的動態(tài)索引結構的代表，它是一種頁面結構的平衡樹，采用自下而上的索引構造方法，具有節(jié)點提升和分裂機制。因此，它適合作為一種磁盤索引結構，并能處理數據的更新而無需重構整個索引。M-tree是第一個認識到了距離計算的高代價，因此它將大多數距離已經預計算好并存儲在索引當中。這樣，就可以避免很多距離的動態(tài)計算。但是，M-tree的兄弟節(jié)點索引空間的重疊是一個非常值得注意的問題，因為它對查詢處理的性能有著非常大的影響。為此，基于M-tree索引結構的基本思想，幾種改進的索引技術被提出，例如MB⁺-tree，Slim-tree，M⁺-tree。

Slim-tree通過一個后處理過程來減少子空間的交疊和索引節(jié)點的數目。MB⁺-tree采用一個不同的方法，即采用B⁺-tree作為一個輔助索引結構。盡管MB⁺-tree的空間劃分是不相交的，但由于MB⁺-tree不是采用一個單一的多維索引來處理高維空間中的查詢問題，這樣查詢處理的效率將非常低下。

發(fā)明內容

為了解決現(xiàn)有技術的不足之處，本發(fā)明提供一種基于最大間隙空間映射的高維數據索引方法，改進了高維索引的性能，在查詢處理的過程中如何盡量減少對假活動子空間的訪問。

本發(fā)明采用的技術方案是：設計并實現(xiàn)了一種新的索引結構MS-tree。在MS-tree索引結構中有兩種類型的節(jié)點對象：路由對象(routing?objects)和葉子對象(leaf?objects)。每一個葉子節(jié)點入口項包含三部分：數據對象Oj的特征值，對象標識符oid(O_j)，以及對象O_j到它的父親P(O_j)的距離d(O_j，P(O_j))。中間節(jié)點的入口項信息包含兩部分：對象在原始空間的信息和該對象在投影空間的信息，其中前者包括下面幾部分：中間節(jié)點對象的特征值及其覆蓋半徑、距離其父節(jié)點的距離，指向孩子節(jié)點的指針。而后者則包含一個代表投影空間的隊列、投影空間的覆蓋半徑以及該對象在投影空間中距離其父節(jié)點對象的投影距離。

首先定義假活動子空間，在基于高維索引的相似性查詢處理過程中，如果一個子空間可能包含查詢結果時(即該子空間與查詢空間相交)，則該子空間被稱為一個活動子空間。反之，如果一個子空間不可能包含查詢結果時(即該子空間與查詢空間不相交)，則該子空間被稱為一個非活動子空間。

在相似性查詢處理過程中，如果一個子空間S可能包含查詢結果，但該子空間的所有孩子空間并不包含任何查詢結果，則稱該子空間S為假活動子空間。

本發(fā)明的步驟如下：

步驟1進行最大間隙空間映射