Title | ||
---|---|---|
Approximate k-Nearest Neighbor Search Based on the Earth Mover's Distance for Efficient Content-based Information Retrieval. |
Abstract | ||
---|---|---|
The Earth Moveru0027s Distance (EMD) is one of the most-widely used distance functions to measure the similarity between two multimedia objects. While providing good search results, the EMD is too much time-consuming to be used in large multimedia databases. To solve the problem, we propose an approximate k-nearest neighbor (k-NN) search method based on the EMD. First, the proposed method builds an index using the M-tree, a distance-based multi-dimensional index structure, to reduce the disk access overhead. When building the index, we reduce the number of features in the multimedia objects through dimensionality-reduction. When performing the k-NN search on the M-tree, we find a small set of candidates from the disk using the index and then perform the post-processing on them. Second, the proposed method uses the approximate EMD for index retrieval and post-processing to reduce the computational overhead of the EMD. To compensate the errors due to the approximation, the method provides a way of accuracy improvement of the approximate EMD. We performed extensive experiments to show the efficiency of the proposed method. |
Year | Venue | Field |
---|---|---|
2018 | WIMS | k-nearest neighbors algorithm,Data mining,Overhead (computing),Earth mover's distance,Computer science,Content based information retrieval,Small set |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
20 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Min-Hee Jang | 1 | 25 | 5.93 |
Sang-Wook Kim | 2 | 792 | 152.77 |
Woong-Kee Loh | 3 | 188 | 22.16 |
Jung-Im Won | 4 | 86 | 10.56 |