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

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

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