BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Cisłak Aleksander (Technical University of Munich, Germany), Grabowski Szymon (Lodz University of Technology, Poland)
Tytuł
Experimental evaluation of selected tree structures for exact and approximate k-nearest neighbor classification
Źródło
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
Uwagi
summ.
Abstrakt
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
Pokaż
Bibliografia
Pokaż
  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
Pokaż
ISSN
2300-5963
Język
eng
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu