P2P網(wǎng)絡(luò)中的Anytime查詢處理.pdf

1、P2P網(wǎng)絡(luò)具有高可擴(kuò)展性、健壯性、自主性等優(yōu)點(diǎn)，被廣泛應(yīng)用。結(jié)構(gòu)化的P2P數(shù)據(jù)管理系統(tǒng)具有結(jié)構(gòu)化P2P網(wǎng)絡(luò)的優(yōu)點(diǎn)，可以為數(shù)據(jù)管理用戶應(yīng)用提供具有以上優(yōu)點(diǎn)的服務(wù)?，F(xiàn)有的結(jié)構(gòu)化P2P數(shù)據(jù)管理查詢技術(shù)可以良好的解決基于關(guān)鍵字的等值查詢和范圍查詢，然而一些更為復(fù)雜的查詢，如多維范圍查詢、top-k查詢、KNN查詢、join查詢、skyline查詢等，還沒有得到很好的解決方法。
　　在P2P網(wǎng)絡(luò)中，如果一個復(fù)雜查詢涉及的節(jié)點(diǎn)數(shù)量眾多，該查詢

2、的代價將十分巨大而且無法避免。本文設(shè)計了結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的anytime查詢處理算法，在增量形式地返回查詢結(jié)果的同時，實(shí)時計算當(dāng)前結(jié)果的質(zhì)量。如果用戶對當(dāng)前結(jié)果滿意，用戶可以隨時中止查詢處理，減少用戶需求之外的查詢處理代價。
　　為了實(shí)時計算查詢處理結(jié)果質(zhì)量，本文設(shè)計了HA2-d樹存儲結(jié)構(gòu)，以及HA2-d樹在P2P網(wǎng)絡(luò)中的動態(tài)維護(hù)方法，并在HA2-d樹中索引多維數(shù)據(jù)和多維直方圖。HA2-d樹是一棵平衡二叉樹，其中每個節(jié)點(diǎn)維護(hù)一個

3、多維區(qū)域內(nèi)數(shù)據(jù)的直方圖。由于精確的直方圖獲取代價太大，本文使用近似聚集的方法，使得HA2-d樹所維護(hù)的直方圖具有較小的誤差界限(如5％)。
　　本文設(shè)計了多維范圍查詢、top-k查詢和KNN查詢處理算法，這些查詢處理算法基于HA2-d樹存儲結(jié)構(gòu)。我們定義了HA2-d樹中，兩個節(jié)點(diǎn)的最高分離樹概念，將其用于查詢路由決策。本文設(shè)計的查詢處理算法消息代價為O(MlogN)，其中M是含有查詢結(jié)果的節(jié)點(diǎn)數(shù)量，N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量。由查詢消息代