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ò)中，如果一個(gè)復(fù)雜查詢涉及的節(jié)點(diǎn)數(shù)量眾多，該查詢

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

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