Experimental evaluation of selected tree structures for exact and approximate k-nearest neighbor classification

• Autorzy: Aleksander Cisłak , Szymon Grabowski
• Języki publikacji: EN

Abstrakty

EN

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)

Słowa kluczowe

EN

Data structures; Algorithms; Classification methods

PL

Struktury danych; Algorytmy; Metody klasyfikacyjne

• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2014
• Tom: 2
• Strony: 93--100

Twórcy

autor

Aleksander Cisłak

• Technical University of Munich, Germany

autor

Szymon Grabowski

• Lodz University of Technology, Poland

Bibliografia

• 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
• 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
• 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.
• 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
• Cisłak A., "Approximate and probabilistic variants of the k-nearest neighbor classification rule," Bachelor's Thesis, Lodz University of Technology, 2014.
• Cormen T. H. , Leiserson C. E., Rivest R. L., and Stein C., Introduction to Algorithms (3. ed.). MIT Press, 2009. ISBN 9780262033848
• 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
• 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.
• 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
• 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
• Lowe D. G., "Object recognition from local scale-invariant features," in ICCV, 1999. doi: 10.1109/ICCV.1999.790410 pp. 1150-1157.
• 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
• Omohundro S. M., Five balltree construction algorithms. International Computer Science Institute Berkeley, 1989.