Efficient Searching Technique for Nearest Neighbor Object in High-Dimensional Data


The KIPS Transactions:PartD, Vol. 11, No. 2, pp. 269-280, Apr. 2004
10.3745/KIPSTD.2004.11.2.269,   PDF Download:

Abstract

The Pyramid-Technique is based on mapping n-dimensional space data into one-dimensional data and expresses it as a B -tree. By solving the problem of search time complexity the pyramid technique also prevents the effect of ´phenomenon of dimensional curse´ which is caused by treatment of hypercube range query in n-dimensional data space. The SPY-TEC applies the space division strategy in pyramid method and uses spherical range query suitable for similarity search so that improves the search performance. However, nearest neighbor query is more efficient than range query because it is difficult to specify range in similarity search. Previously proposed index methods perform well only in the specific distribution of data. In this paper, we propose an efficient searching technique for nearest neighbor object usingPdR-Tree suggested to improve the search performance for high dimensional data such as multimedia data. Test results, which uses simulation data with various distribution as well as real data, demonstrate that PdR-Tree surpasses both the Pyramid-Technique and SPY-TEC in views of search performance.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. J. Ho and P. Y. Bae, "Efficient Searching Technique for Nearest Neighbor Object in High-Dimensional Data," The KIPS Transactions:PartD, vol. 11, no. 2, pp. 269-280, 2004. DOI: 10.3745/KIPSTD.2004.11.2.269.

[ACM Style]
Kim Jin Ho and Park Yeong Bae. 2004. Efficient Searching Technique for Nearest Neighbor Object in High-Dimensional Data. The KIPS Transactions:PartD, 11, 2, (2004), 269-280. DOI: 10.3745/KIPSTD.2004.11.2.269.