BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Cisłak Aleksander (Technical University of Munich, Germany), Grabowski Szymon (Lodz University of Technology, Poland)
Experimental evaluation of selected tree structures for exact and approximate k-nearest neighbor classification
Annals of Computer Science and Information Systems, 2014, vol. 2, s. 93-100, rys., bibliogr. 13 poz.
Słowa kluczowe
Struktury danych, Algorytmy, Metody klasyfikacyjne
Data structures, Algorithms, Classification methods
Spatial data structures, for vector or metric spaces, are a well-known means to speed-up proximity queries. One of the common uses of the found neighbors of the query object is in classification methods, e.g, the famous emph{k}-nearest neighbor algorithm. Still, most experimental works focus on providing attractive tradeoffs between neighbor search times and the neighborhood quality, but they ignore the impact of such tradeoffs on the classification accuracy.(original abstract)
Pełny tekst
  1. Arya S., Mount D. M., and Narayan O., "Accounting for boundary effects in nearest-neighbor searching," Discrete & Computational Geometry, vol. 16, no. 2, pp. 155-176, 1996. doi: 10.1007/BF02716805
  2. Arya S., Mount D. M., Netanyahu N. S., Silverman R., and Wu A. Y., "An optimal algorithm for approximate nearest neighbor searching fixed dimensions," Journal of the ACM (JACM), vol. 45, no. 6, pp. 891-923, 1998. doi: 10.1145/293347.293348
  3. Beis J. S. and Lowe D. G., "Shape indexing using approximate nearestneighbour search in high-dimensional spaces," in CVPR, 1997. doi: 10.1109/CVPR.1997.609451 pp. 1000-1006.
  4. Bentley J. L., "Multidimensional binary search trees used for associative searching," Commun. ACM, vol. 18, no. 9, pp. 509-517, 1975. doi: 10.1145/361002.361007
  5. Cisłak A., "Approximate and probabilistic variants of the k-nearest neighbor classification rule," Bachelor's Thesis, Lodz University of Technology, 2014.
  6. Cormen T. H. , Leiserson C. E., Rivest R. L., and Stein C., Introduction to Algorithms (3. ed.). MIT Press, 2009. ISBN 9780262033848
  7. Fredman M. L. and Tarjan R. E., "Fibonacci heaps and their uses in improved network optimization algorithms," J. ACM, vol. 34, no. 3, pp. 596-615, 1987. doi: 10.1145/28869.28874
  8. Indyk P. and Motwani R., "Approximate nearest neighbors: towards removing the curse of dimensionality," in Proceedings of the thirtieth annual ACM symposium on Theory of computing. ACM, 1998. doi: 10.1145/276698.276876 pp. 604-613.
  9. Jones P. W., Osipov A., and Rokhlin V., "Randomized approximate nearest neighbors algorithm," Proceedings of the National Academy of Sciences, vol. 108, no. 38, pp. 15 679-15 686, 2011. doi: 10.1073/pnas.1107769108
  10. Kibriya A. M. and Frank E., "An empirical comparison of exact nearest neighbour algorithms," pp. 140-151, 2007. doi: 10.1007/978-3-540-74976-9_16
  11. Lowe D. G., "Object recognition from local scale-invariant features," in ICCV, 1999. doi: 10.1109/ICCV.1999.790410 pp. 1150-1157.
  12. Munaga H. and Jarugumalli V., "Performance evaluation: Ball-tree and kd-tree in the context of mst," CoRR, vol. abs/1210.6122, 2012. doi: 10.1007/978-3-642-32573-1_38
  13. Omohundro S. M., Five balltree construction algorithms. International Computer Science Institute Berkeley, 1989.
Cytowane przez
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu