基于R-Tree的空間連接代價(jià)模型的改進(jìn).pdf

1、空間連接查詢是空間數(shù)據(jù)庫系統(tǒng)中最頻繁的操作之一，而且由于空間數(shù)據(jù)庫中數(shù)據(jù)無序、數(shù)據(jù)量大等特點(diǎn)，使得其代價(jià)評估對于空間查詢優(yōu)化來說具有重要意義。 空間連接代價(jià)模型建立在窗口查詢理論的基礎(chǔ)上，文中所述的原始模型即是窗口查詢代價(jià)公式的擴(kuò)展。該模型考慮到了非定長緩沖區(qū)和所存儲(chǔ)數(shù)據(jù)的分布等情況對評估的影響程度。另外，該模型主要依靠大規(guī)模的計(jì)算，需要比較長的計(jì)算時(shí)間才能得到結(jié)果。 本文所提出的改進(jìn)模型主要采用的思想就是以空間換時(shí)間，

2、通過引入少量存儲(chǔ)空間來大大減少模型估計(jì)的時(shí)間復(fù)雜度。改進(jìn)模型所引入的輔助存儲(chǔ)包括：結(jié)點(diǎn)對記錄隊(duì)列和定長緩沖區(qū)。對于定長的緩沖區(qū)，對其所引起的缺頁中斷進(jìn)行概率建模，缺頁中斷的隨機(jī)變量服從指數(shù)分布。改進(jìn)模型的具體實(shí)現(xiàn)方法是選取出大部分相交概率比較大的結(jié)點(diǎn)對，用其平均代價(jià)來估算整體的連接代價(jià)。改進(jìn)模型可以應(yīng)用于均勻分布和非均勻分布數(shù)據(jù)集。對于非均勻分布，采用分區(qū)域抽樣的方法，即所有區(qū)域查詢代價(jià)的總和就是總體代價(jià)。 最后用實(shí)驗(yàn)仿真數(shù)據(jù)對