本文關(guān)鍵詞：度量空間索引支撐點(diǎn)選擇問題研究

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

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

【參考文獻(xiàn)】

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

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

，

本文編號：1305440