- 學位論文
研究在不確定資料上找尋反轉最近鄰居的方法
A Study for RNN Query Process on Multi-dimensional Uncertain Data
摘要
反轉最近鄰居查詢(RNNQ)為最近鄰居查詢方法的一種新的變化，並且可使用於相當多領域之中，例如: 決策支援(Decision Support)、資源分配(Resource Allo-cation)或市場調查(Profile-base Market)等…，尤其常用於資料庫之中，然而資料庫中的資料有時因設備因素、環境雜訊、型態不同而影響資料成為了由許多實例所組成的不確定資料。我們論文中首先會說明反轉最近鄰居查詢方法在不確定資料中會遇到的問題，並介紹現有可應用的方法(雙曲線演算法)，由於雙曲線演算法不夠直覺與快速，所以分別此篇論文中的提出了可應用於二維之中更有效率的EDS演算法以及可應用於高維度之中的UDP演算法，此兩種方法都是以相同理念出發並且UDP演算法是為了補足EDS演算法無法使用於高維度之中的缺點而提出，最後在實驗中分別用多種人造資料與真實資料來進行各種角度結果的觀察、分析與驗證EDS演算法與UDP演算法的效能及正確性。
並列摘要
Reverse nearest neighbor (RNN) search is a new type of nearest neighbor, RNN search is very crucial in many real applications, such as decision support, resource alloca-tion, profile-base market, and mix reality games. RNN Query is often use in the data-base, but limitation of measurement device, environmental disturbance, or characteristics of application, data obtained from sources are uncertain. In this paper we will talk about RNN search in the uncertain database encounter problem, and mention existing solution (hyperbola algorithm); since hyperbola algorithm is not intuitive and fast, so we propose two more efficient algorithm. First one is EDS algorithm which only can work on two-dimensional, but EDS algorithm is more faster than others. Second one is UDP al-gorithm which is proposed for makeup EDS algorithm defect though both algorithm is coming from same concept. The experiment use synthetic data and real data to evaluate the efficiency and effectiveness of our proposed EDS algorithm and UDP algorithm.