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

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

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

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