Publications
Detailed Information
Fast Approximate Algorithms for k-NN Search and k-NN Graph Construction : k-NN 검색 및 k-NN 그래프 생성을 위한 고속 근사 알고리즘
Cited 0 time in
Web of Science
Cited 0 time in Scopus
- Authors
- Advisor
- 이상구
- Major
- 공과대학 전기·컴퓨터공학부
- Issue Date
- 2015-02
- Publisher
- 서울대학교 대학원
- Keywords
- k-nearest neighbor search ; k-nearest neighbor graph construction ; collaborative filtering ; locality-sensitive hashing
- Description
- 학위논문 (박사)-- 서울대학교 대학원 : 전기·컴퓨터공학부, 2015. 2. 이상구.
- Abstract
- Finding k-nearest neighbors (k-NN) is an essential part of recommeder systems, information retrieval, and many data mining and machine learning algorithms. However, there are two main problems in finding k-nearest neighbors: 1) Existing approaches require a huge amount of time when the number of objects or dimensions is scale up. 2) The k-NN computation methods do not show the consistent performance over different search tasks and types of data. In this dissertation, we present fast and versatile algorithms for finding k-nearest neighbors in order to cope with these problems. The main contributions are summarized as follows: first, we present an efficient and scalable algorithm for finding an approximate k-NN graph by filtering node pairs whose large value dimensions do not match at all. Second, a fast collaborative filtering algorithm that utilizes k-NN graph is presented. The main idea of this approach is to reverse the process of finding k-nearest neighbors in item-based collaborative filtering. Last, we propose a fast approximate algorithm for k-NN search by selecting query-specific signatures from a signature pool to pick high-quality k-NN candidates.The experimental results show that the proposed algorithms guarantee a high level of accuracy while also being much faster than the other algorithms over different types of search tasks and datasets.
- Language
- English
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.