第二十卷 第三期 - 2011年十月二十一日 PDF
Counter
路網中移動查詢點反向最近鄰連續監控
Li Guohui1, Li Yanhong1, Li Jianjun1, 徐立群2*, Yang Fumin1
1School of Computer Science & Technology, Huazhong University of Science & Technology, PRChina
2國立成功大學管理學院會計學系
 
字體放大
研究探討路網中連續反向k個最近鄰查詢之處理。每個反向k個最近鄰(RkNN)查詢物件皆會回傳一個或多個資料物件,這些物件的k個最近鄰集合中必須包含該查詢物件。雖然現有一些在歐式空間中找尋RkNN的演算法,它們並不適用在真實路網上之查詢。我們因此提出在路網中允許查詢與資料物件皆能任意移動之高效率查詢處理演算法。

我們的方法包含兩個階段──初始結果產生階段與漸進維護階段。在初始階段,我們首先計算RkNN初始結果集合,同時也算出相對於查詢的監視區域。我們使用一創新的資料結構─DLM樹去呈現查詢之監視區域。DLM樹是一雙層多路樹,它的上層用來儲存所有RkNN候選物件的監視區域稱為verifying樹。藉由DLM樹,我們將「處理CRkNN查詢問題」轉變為「監視DLM樹問題」。我們的方法採漸進式的修正CRkNN結果,因此無需在每次位置更新時就重新計算結果。我們證明數項重要定理,讓我們藉以降低樹的尺度與減少候選物件的數目。

經由模擬實驗,我們評估所提出的演算法之效能。我們與另一計算初始CRkNN方法(稱作NAV)做比較,大致上我們的方法較NAV快上1.9倍,同時在以下各方面皆展現其強健性:k值、查詢數、物件數、查詢行動性、物件行動性、查詢速度與網路尺度。一言以蔽之,我們的方法既有效率又具擴充性。
< 上一篇
下一篇 >
Copyright National Cheng Kung University