基于分層抽樣的在線聚集方法設(shè)計(jì)與實(shí)現(xiàn).pdf

1、面對(duì)日益增加的數(shù)據(jù)量，近似查詢通過處理盡可能少的數(shù)據(jù)來獲得盡可能準(zhǔn)確的結(jié)果，相對(duì)于精確查詢，提高了數(shù)據(jù)查詢的效率。在線聚集是近似查詢中一種應(yīng)用比較廣泛的方法，但其使用效果會(huì)受到數(shù)據(jù)分布的影響，對(duì)于非均勻分布數(shù)據(jù)，可能導(dǎo)致較大的誤差，從而需要處理全部或絕大部分?jǐn)?shù)據(jù)才能得到較為準(zhǔn)確的結(jié)果，尤其是當(dāng)數(shù)據(jù)量很大時(shí)，運(yùn)行時(shí)間無法保證有可靠的上界。而抽樣方法可以通過降低數(shù)據(jù)的規(guī)模，從而保證運(yùn)行時(shí)間在可接受范圍之內(nèi)。
　　提出了一種基于分層抽樣

2、實(shí)現(xiàn)在線聚集的OASS方法，首先基于不同的查詢列創(chuàng)建多個(gè)不同的分層抽樣樣本，滿足最高精度的查詢請(qǐng)求，并且降低了數(shù)據(jù)的規(guī)模，保證時(shí)間上界在可接受范圍之內(nèi)。對(duì)較低精度的查詢請(qǐng)求，通過在線聚集技術(shù)，結(jié)果的精度可以隨著等待時(shí)間的增加而提高，并且當(dāng)用戶滿意時(shí)可以終止查詢，另外通過指定持續(xù)查詢每次處理的數(shù)據(jù)從每個(gè)分層中分別取得，相對(duì)原始在線聚集的隨機(jī)抽樣得到的近似結(jié)果的精度更高，誤差更小，從而降低數(shù)據(jù)偏斜分布對(duì)近似結(jié)果的影響，減少了平均運(yùn)行時(shí)間。<