Fast k-NN classification rule using metric on space-filling curves

Author

Skubalska-Rafajlowicz, Ewa ; Krzyzak, Adam

Author_Institution

Inst. of Eng. Cybern., Tech. Univ. Wroclaw, Poland

Volume

2

fYear

1996

fDate

25-29 Aug 1996

Firstpage

121

Abstract

A fast nearest neighbor algorithm for pattern classification is proposed and tested on real data. The patterns (points in d-dimensional Euclidean space) are sorted along a space-filling curve. This way the multi-dimensional problem is compressed to the simplest case of the nearest neighbor search in one dimension. Instead of Euclidean distance a metric on space-filling curve is used. The method may be inferior or superior to the k-NN rule in multidimensional Euclidean space

Keywords

computational complexity; curve fitting; data compression; decision theory; pattern classification; search problems; compressed classification; computational complexity; decision theory; fast k-NN classification rule; multidimensional Euclidean space; nearest neighbor search algorithm; pattern classification; space-filling curve; space-filling curves; Computer science; Cybernetics; Data engineering; Euclidean distance; Extraterrestrial measurements; Image coding; Multidimensional systems; Nearest neighbor searches; Pattern recognition; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Pattern Recognition, 1996., Proceedings of the 13th International Conference on

Conference_Location

Vienna

ISSN

1051-4651

Print_ISBN

0-8186-7282-X

Type

conf

DOI

10.1109/ICPR.1996.546736

Filename

546736