請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56119
標題: | 在分散式環境下以正交轉換技術節省頻寬之最近鄰查詢演算法 Exact kNN-Search with Orthogonal Transformation in the Distributed Environment |
作者: | JUI-PIN WANG 王瑞斌 |
指導教授: | 林守德(Shou-De Lin) |
關鍵字: | 確切相似性搜索,剪枝,傳輸量節省,正交轉換,最優化問題, Exact Similarity Search,Pruning,Bandwidth-efficient,Orthogonal Transformation,Optimization, |
出版年 : | 2014 |
學位: | 碩士 |
摘要: | With the popularity of mobile devices and Internet of Things, similarity search such as image querying or query by humming among data distributed in different machines has become an increasingly important problem. Moreover, in a distributed environment, the transmission cost is usually much more crucial than the computation cost as generally it consumes more resource to in transmission. Thus, this thesis proposes a framework to conduct a bandwidth-efficient, exact k-nearest neighbor search amount a large number of distributed machines through exploiting the techniques of the orthogonal transformation. On the basis of our previous work, new bounds on the Euclidean distance have been derived to prune impossible instances in the early stages of searching using partial information of the query. Moreover, three additional enhancements are devised to further save the communication cost. The experiment results show that our method significantly outperforms other competitions in bandwidth consumption in large-scale experiments of millions of instances. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56119 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 2.9 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。