[發明專利]度量空間中逐個支撐點數據劃分方法

在審

• 申請號: 201410472953.8
• 申請日: 2014-09-16
• 公開（公告）號: CN104281652A
• 公開（公告）日: 2015-01-14
• 發明（設計）人: 毛睿;陸敏華;蔡曄;劉剛;李榮華;王毅;羅秋明
• 申請（專利權）人: 深圳大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 深圳市興科達知識產權代理有限公司 44260
• 代理人: 王翀

技術領域

本發明屬于計算機軟件領域，涉及度量空間，相似性搜索和數據挖掘，尤其涉及一種度量空間中逐個支撐點數據劃分方法。

背景技術

基于內容的相似性搜索是一種重要的信息檢索類型，廣泛存在于數據庫和數據挖掘應用中。隨著多媒體技術的發展和推廣普及，基于復雜數據對象(空間數據、文本、圖像、音頻、視頻、時空序列等)的海量數據庫不斷涌現，相似性搜索已經成為多媒體信息系統基于內容搜索的基本需求，其性能已經成為衡量多媒體系統查詢功能的重要指標。同時，近年來生物信息學的蓬勃發展也產生了龐大的復雜生物數據(基因序列、蛋白質譜等)，對這些數據的高效搜索已經成為一個迫切需要解決的問題。據統計，相似性搜索在整個計算生物學研究任務中所占比例高達35％。

度量空間索引是一種適用性非常廣的解決相似性搜索的方法。它把復雜的數據對象抽象成度量空間中的點，利用用戶定義距離函數的三角不等性來去除無關數據并減少直接距離計算的次數，以實現高速搜索。度量空間索引只要求用戶提供滿足度量空間性質的距離函數，而距離函數的具體實現和數據的表達都是透明的，同樣的算法可以應用于不同的數據，因而具備了更廣泛的適用范圍。近年來，多媒體技術的推廣應用和生物學研究的蓬勃發展產生了大量新型的多媒體和生物數據，度量空間索引技術也因為其不斷體現出的普遍適應性成為一個國內外較為熱門的研究領域。

度量空間索引也被稱為基于距離的索引，主要用于相似性搜索。距離函數是它唯一需要的相似性定義。樹結構是最流行的度量空間索引結構的一種，在建樹過程中包括了選取支撐點和逐個支撐點數據劃分兩個步驟。

目前，應用與度量空間的樹結構包括BKT(Burkhard-Keller?Tree)，FQT(Fixed?Queries?Tree)，VPT(Vantage?Point?Tree)和MVPT(Multi-Vantage?Point?Tree)等等，在度量空間建樹的過程中，需要遞歸的根據數據點到給定支撐點的距離進行數據劃分。其中，支撐點的選擇和數據劃分方法，直接影響了索引的建立，從而影響到相似性搜索的效率。

度量空間中支撐點如何選取及數據如何逐個支撐點進行劃分對建立索引具有極其重要的作用。

通過FFT或者Incremental等方法選取的支撐點集合，在逐個支撐點進行數據劃分時，支撐點使用的順序對相似性搜索的效率具有一定的影響，但是，目前并沒有方法針對這個問題，提出解決方案；與此同時，數據劃分方法的選擇，也并沒有參考數據集到支撐點的距離分布情況，而這使得現有的數據劃分方法并不一定能夠提高相似性搜索的效率。

發明內容

為解決現有技術中存在的問題，本發明提供一種在數據量較大且數據類型較多的情況下，在度量空間中逐個支撐點進行數據劃分方法。

本發明通過以下技術手段實現：

為了解決度量空間中相似性搜索的效率問題，本發明采用的技術方案是，一種度量空間中逐個支撐點數據劃分方法，在建立索引時，包括以下步驟：

101)從數據集內根據起始和終止位置截取需要處理的數據；

102)選擇一種支撐點優化方法，確定支撐點使用次序；

103)選擇一種數據劃分方法，逐個支撐點進行數據劃分；

104)確定每個劃分的上界與下界；

105)確定每個劃分到每個支撐點的距離值的上界與下界；

106)返回劃分結果。

以上所述的度量空間中逐個支撐點數據劃分方法，

在步驟102中，采用了Variance方法，即遍歷每一個支撐點并根據該支撐點進行數據劃分，計算每個劃分中的數據點大小，然后計算每個支撐點對數據劃分大小的方差，對支撐點按照方差從小到大進行排序。

在步驟103中，確定本次劃分要使用的支撐點，然后進行數據劃分，最后對已劃分部分進行相應的處理。

在步驟104與105之間，找到每個任務列表中的子節點及全部的直系父節點并存儲。

以上所述的度量空間中逐個支撐點數據劃分方法，需要從main函數接收四個參數，分別是dpm(data?partition?method)，sop(select?optimal?pivot)，pbop(partition?by?one?pivot)和tR(trisection?Radius)。當tR參數用于逐個支撐點數據劃分方法中的Trisection方法，其他方法并不使用。