本文關鍵詞：度量空間索引支撐點選擇問題研究

  更多相關文章： 多樣性 度量空間 支撐點選擇 半徑敏感目標函數(shù) RFT算法 PSS算法 理論上限

【摘要】：大數(shù)據(jù)的幾個特性中,關于數(shù)據(jù)多樣性的研究較少。度量空間數(shù)據(jù)管理分析方法把數(shù)據(jù)抽象成度量空間中的點,具有高度的通用性,是應對大數(shù)據(jù)多樣性挑戰(zhàn)的有效手段之一。由于度量空間沒有坐標,一般以數(shù)據(jù)到參考點(也稱支撐點)的距離作為坐標,從度量空間中選擇一些支撐點,用它們來劃分數(shù)據(jù),遞歸地建立索引樹。支撐點的好壞對索引性能有著關鍵性的影響。支撐點的選擇,可以從目標函數(shù)和選擇算法兩個方面進行研究。目前,較為常用的目標函數(shù)為均值目標函數(shù),較為常用的支撐點選擇算法有Farthest First Traversal(FFT)和Incremental。均值目標函數(shù)籠統(tǒng)地將距離均值作為目標函數(shù),沒有考慮到查詢半徑對排除效果的影響。FFT算法很難選出最優(yōu)的支撐點,Incremental算法存在局部最優(yōu)的問題。本文的研究內容主要有以下三個方面:·針對均值目標函數(shù)的不足,提出了半徑敏感目標函數(shù)。半徑敏感目標函數(shù)以距離大于查詢半徑的數(shù)據(jù)對的個數(shù)作為函數(shù)值,充分考慮了查詢半徑對排除效果的影響。實驗證明,半徑敏感目標函數(shù)能夠選出更好的支撐點,與索引性能具有更強的一致性。·針對FFT算法的不足,提出了 Recent Farthest Traversal(RFT)算法。實驗證明,RFT在選點速度和選點命中率上均優(yōu)于FFT算法。同時,FFT具有按空間均勻抽樣的特性,更適合用于數(shù)據(jù)的抽樣。提出的PivotSetSelection(PSS)算法,有效避免了 Incremental的局部最優(yōu)問題。實驗顯示,以RFT選擇候選集,以FFT選擇評價集,PSS性能良好,索引構建代價大大降低。·探索支撐點對索引性能影響的理論上限。目前的支撐點選擇方法在索引性能方面的差別不是很大,用復雜的數(shù)學工具以很高的構建計算代價選擇的支撐點帶來的索引性能提升往往相對較少,整個領域的研究處于一個性能瓶頸中。本文探究了支撐點選擇性能的可提升空間,為后續(xù)的研究方向提供了參考。
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP311.13

【參考文獻】

中國期刊全文數(shù)據(jù)庫 前1條

1 王國仁;黃健美;王斌;韓東紅;喬百友;于戈;;基于最大間隙空間映射的高維數(shù)據(jù)索引技術[J];軟件學報;2007年06期

，

本文編號：1305440