Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/56119
Title: | 在分散式環境下以正交轉換技術節省頻寬之最近鄰查詢演算法 Exact kNN-Search with Orthogonal Transformation in the Distributed Environment |
Authors: | JUI-PIN WANG 王瑞斌 |
Advisor: | 林守德(Shou-De Lin) |
Keyword: | 確切相似性搜索,剪枝,傳輸量節省,正交轉換,最優化問題, Exact Similarity Search,Pruning,Bandwidth-efficient,Orthogonal Transformation,Optimization, |
Publication Year : | 2014 |
Degree: | 碩士 |
Abstract: | 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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-103-1.pdf Restricted Access | 2.9 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.