14.2.9.1 Fast Nearest Neighbor Techniques

Kim, B.S., and Park, S.B.,
A Fast K Nearest Neighbor Finding Algorithm Based on the Ordered Partition,
PAMI(8), No. 6, November 1986, pp. 761-766. BibRef 8611

Broder, A.J.[Alan J.],
Strategies for efficient incremental nearest neighbor search,
PR(23), No. 1-2, 1990, pp. 171-178.
WWW Version. 0401
BibRef

Belkasim, S.O., Shridhar, M., Ahmadi, M.,
Pattern classification using an efficient KNNR,
PR(25), No. 10, October 1992, pp. 1269-1274.
WWW Version. 0401
BibRef

Farago, A., Linder, T., Lugosi, G.,
Fast nearest-neighbor search in dissimilarity spaces,
PAMI(15), No. 9, September 1993, pp. 957-962.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0401
BibRef

Kao, T.W.[Tzong-Wann], Horng, S.J.[Shi-Jinn],
Efficient algorithms for computing two nearest-neighbor problems on a rap,
PR(27), No. 12, December 1994, pp. 1707-1716.
WWW Version. 0401
BibRef

Mico, L., Oncina, J., Carrasco, R.C.,
A Fast Branch-and-Bound Nearest-Neighbor Classifier in Metric-Spaces,
PRL(17), No. 7, June 10 1996, pp. 731-739. 9607
BibRef

Mico, L., Oncina, J., Vidal, E.,
An algorithm for finding nearest neighbours in constant average time with a linear space complexity,
ICPR92(II:557-560).
IEEE DOI Link 9208
BibRef

Gómez Ballester, E.[Eva], Micó, L.[Luisa], Oncina, J.[Jose],
Some approaches to improve tree-based nearest neighbour search algorithms,
PR(39), No. 2, February 2006, pp. 171-179.
WWW Version. 0512
BibRef
Earlier:
Testing Some Improvements of the Fukunaga and Narendra's Fast Nearest Neighbour Search Algorithm in a Spelling Task,
IbPRIA05(II:3).
Springer DOI Link 0509
BibRef

Warfield, S.,
Fast K-NN Classification for Multichannel Image Data,
PRL(17), No. 7, June 10 1996, pp. 713-721. 9607
BibRef

Djouadi, A., Bouktache, E.,
A Fast Algorithm for the Nearest-Neighbor Classifier,
PAMI(19), No. 3, March 1997, pp. 277-282.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9704
BibRef

Djouadi, A.,
On the Reduction of the Nearest Neighbor Variation for More Accurate Classification and Error Estimates,
PAMI(20), No. 5, May 1998, pp. 567-571.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9806
BibRef

Grother, P.J., Candela, G.T., Blue, J.L.,
Fast Implementations of Nearest-Neighbor Classifiers,
PR(30), No. 3, March 1997, pp. 459-465.
WWW Version. 9705
BibRef

Lee, E.W., Chae, S.I.,
Fast Design of Reduced Complexity Nearest Neighbor Classifiers Using Triangular Inequality,
PAMI(20), No. 5, May 1998, pp. 562-566.
IEEE Abstract. IEEE Top Reference.
WWW Version. 9806
BibRef

Ramasubramanian, V., Paliwal, K.K.[Kuldip K.],
Fast nearest-neighbor search algorithms based on approximation-elimination search,
PR(33), No. 9, September 2000, pp. 1497-1510.
WWW Version. 0005
BibRef

Fränti, P., Kaukoranta, T., Shen, D.F., Chang, K.S.,
Fast and Memory Efficient Implementation of the Exact PNN,
IP(9), No. 5, May 2000, pp. 773-777.
IEEE DOI Link 0005
BibRef

Virmajoki, O.[Olli], Fränti, P.[Pasi], Kaukoranta, T.[Timo],
Fast PNN Using Partial Distortion Search,
CAIP01(77 ff.).
HTML Version. 0210
BibRef

Franti, P., Kaukoranta, T.,
Fast implementation of the optimal PNN method,
ICIP98(III: 104-108).
IEEE DOI Link 9810
BibRef

McNames, J.[James],
A Fast Nearest-Neighbor Algorithm Based on a Principal Axis Search Tree,
PAMI(23), No. 9, September 2001, pp. 964-976.
IEEE Abstract. IEEE Top Reference.
WWW Version. 0110
At each node partition the data along the maximum variance (from PCA). BibRef

Cha, S.H.[Sung-Hyuk], Srihari, S.N.[Sargur N.],
A fast nearest neighbor search algorithm by filtration,
PR(35), No. 2, February 2002, pp. 515-525.
WWW Version. 0201
BibRef
Earlier:
Nearest Neighbor Search using Additive Binary Tree,
CVPR00(I: 782-787).
IEEE Abstract. IEEE Top Reference.
WWW Version. 0005
BibRef

Zhang, B.[Bin], Srihari, S.N.,
Fast K-Nearest Neighbor Classification Using Cluster-Based Trees,
PAMI(26), No. 4, April 2004, pp. 525-528.
IEEE Abstract. IEEE Top Reference. 0403
BibRef
Earlier:
A fast algorithm for finding k-nearest neighbors with non-metric dissimilarity,
FHR02(13-18).
IEEE Top Reference. 0209
Cluster based tree algorithm. Early decision making and minimal operations to reduce time. BibRef

Bandyopadhyay, S.[Sanghamitra], Maulik, U.[Ujjwal],
Efficient prototype reordering in nearest neighbor classification,
PR(35), No. 12, December 2002, pp. 2791-2799.
WWW Version. 0209
See also Fuzzy partitioning using a real-coded variable-length genetic algorithm for pixel classification. BibRef

Mollineda, R.A., Ferri, F.J., Vidal, E.,
An efficient prototype merging strategy for the condensed 1-NN rule through class-conditional hierarchical clustering,
PR(35), No. 12, December 2002, pp. 2771-2782.
WWW Version. 0209
BibRef
Earlier: A2, A1, A3:
An experimental comparison between consistency-based and adaptive prototype replacement schemes,
ICPR02(III: 41-44).
IEEE DOI Link 0211
BibRef
Earlier: A1, A2, A3:
A Cluster-based Merging Strategy for Nearest Prototype Classifiers,
ICPR00(Vol II: 755-758).
IEEE DOI Link
HTML Version. 0009
BibRef

Ferri, F.J.[Francesc J.], Salvador-Sánchez, J., Pla, F.[Filiberto],
Complexity reduction in efficient prototype-based classification,
PR(39), No. 2, February 2006, pp. 161-163.
WWW Version. 0512
BibRef

Micó, L.[Luisa], Moreno-Seco, F.[Francisco], Salvador Sánchez, J.[José], Martinez Sotoca, J.[José], Mollineda, R.A.[Ramón Alberto],
On the Use of Different Classification Rules in an Editing Task,
SSPR06(747-754).
Springer DOI Link 0608
BibRef

Rendón, E.[Erendira], Salvador Sánchez, J.[José],
Clustering Based on Compressed Data for Categorical and Mixed Attributes,
SSPR06(817-825).
Springer DOI Link 0608
BibRef

Mollineda, R.A.[Ramón A.], Salvador-Sánchez, J., Martínez Sotoca, J.[José],
Data Characterization for Effective Prototype Selection,
IbPRIA05(II:27).
Springer DOI Link 0509
BibRef

Zheng, W.M.[Wen-Ming], Zhao, L.[Li], Zou, C.R.[Cai-Rong],
Locally nearest neighbor classifiers for pattern classification,
PR(37), No. 6, June 2004, pp. 1307-1309.
WWW Version. 0405
BibRef

Viswanath, P., Murty, M.N.[M. Narasimha], Bhatnagar, S.[Shalabh],
Overlap pattern synthesis with an efficient nearest neighbor classifier,
PR(38), No. 8, August 2005, pp. 1187-1195.
WWW Version. 0505
BibRef
Earlier:
A pattern synthesis technique with an efficient nearest neighbor classifier for binary pattern recognition,
ICPR04(IV: 416-419).
IEEE DOI Link 0409
BibRef

Viswanath, P., Murty, M.N.[M. Narasimha], Bhatnagar, S.[Shalabh],
Partition based pattern synthesis technique with efficient algorithms for nearest neighbor classification,
PRL(27), No. 14, 15 October 2006, pp. 1714-1724.
WWW Version. 0609
Pattern synthesis; Artificial patterns; Curse of dimensionality BibRef

Agrawal, M.[Monu], Gupta, N.[Neha], Shreelekshmi, R., Murty, M.N.[M. Narasimha],
Efficient pattern synthesis for nearest neighbour classifier,
PR(38), No. 11, November 2005, pp. 2200-2203.
WWW Version. 0509
BibRef

Raicharoen, T.[Thanapant], Lursinsap, C.[Chidchanok],
A divide-and-conquer approach to the pairwise opposite class-nearest neighbor (POC-NN) algorithm,
PRL(26), No. 10, 15 July 2005, pp. 1554-1567.
WWW Version. 0506
BibRef

Sookhanaphibarn, K., Raicharoen, T.[Thanapant], Lursinsap, C.[Chidchanok],
A supervised neural network approach to invariant image recognition,
ICARCV04(III: 1820-1825).
IEEE DOI Link 0412
BibRef

Cano, J.R.[José Ramón], Herrera, F.[Francisco], Lozano, M.[Manuel],
Stratification for scaling up evolutionary prototype selection,
PRL(26), No. 7, 15 May 2005, pp. 953-963.
WWW Version. 0506
Evolutionary Prototype Selection with large datasets. BibRef

Garcia, S.[Salvador], Cano, J.R.[Jose Ramon], Herrera, F.[Francisco],
A memetic algorithm for evolutionary prototype selection: A scaling up approach,
PR(41), No. 8, August 2008, pp. 2693-2709.
WWW Version. 0805
Data reduction; Evolutionary algorithms; Memetic algorithms; Prototype selection; Scaling up; Nearest neighbour rule; Data mining BibRef

Cano, J.R.[Jose-Ramon], Garcia, S.[Salvador], Herrera, F.[Francisco],
Subgroup discover in large size data sets preprocessed using stratified instance selection for increasing the presence of minority classes,
PRL(29), No. 16, 1 December 2008, pp. 2156-2164.
WWW Version. 0811
Large size data sets; Scaling up; Subgroup discovery; Instance selection; Stratification; Minority classes BibRef

Amores, J.[Jaume], Sebe, N.[Nicu], Radeva, P.I.[Petia I.],
Boosting the distance estimation: Application to the K-Nearest Neighbor Classifier,
PRL(27), No. 3, February 2006, pp. 201-209.
WWW Version. 0512
BibRef
Earlier:
Efficient Object-Class Recognition by Boosting Contextual Information,
IbPRIA05(I:28).
Springer DOI Link 0509
BibRef
And:
Fast Spatial Pattern Discovery Integrating Boosting with Constellations of Contextual Descriptors,
CVPR05(II: 769-774).
IEEE DOI Link 0507
Apply to retrieval. See also Context-Based Object-Class Recognition and Retrieval by Generalized Correlograms. BibRef

Chen, Y.S.[Yong-Sheng], Hung, Y.P.[Yi-Ping], Yen, T.F.[Ting-Fang], Fuh, C.S.[Chiou-Shann],
Fast and versatile algorithm for nearest neighbor search based on a lower bound tree,
PR(40), No. 2, February 2007, pp. 360-375.
WWW Version. 0611
Nearest neighbor search; Lower bound tree BibRef

Chen, Y.S.[Yong-Sheng], Hung, Y.P.[Yi-Ping], Fuh, C.S.[Chiou-Shann],
Fast Algorithm for Nearest Neighbor Search Based on a Lower Bound Tree,
ICCV01(I: 446-453).
IEEE DOI Link 0106
BibRef

Lai, J.Z.C.[Jim Z.C.], Liaw, Y.C.[Yi-Ching], Liu, J.[Julie],
Fast k-nearest-neighbor search based on projection and triangular inequality,
PR(40), No. 2, February 2007, pp. 351-359.
WWW Version. 0611
Fast search algorithm; Projection value; Intrinsic dimension BibRef

Li, B.Y.[Bo Yu], Chen, Y.W.[Yun Wen],
The Nearest Neighbor Algorithm of Local Probability Centers,
SMC-B(38), No. 1, February 2007, pp. 141-154.
IEEE DOI Link 0801
BibRef
Earlier:
Classification Using the Local Probabilistic Centers of k-Nearest Neighbors,
ICPR06(III: 1220-1223).
WWW Version. 0609
BibRef
And: ICPR06(IV: 954).
WWW Version. 0609
BibRef

Battiato, S., di Blasi, G., Reforgiato, D.,
Advanced indexing schema for imaging applications: three case studies,
IET-IPR(1), No. 3, September 2007, pp. 249-268.
WWW Version. 0905
Finding k-nearest neighbor. BibRef

Atiya, A.F.[Amir F.], Al-Ani, A.[Ahmed],
A penalized likelihood based pattern classification algorithm,
PR(42), No. 11, November 2009, pp. 2684-2694.
Elsevier DOI Link
WWW Version. 0907
K-nearest neighbor; Penalized likelihood; Pattern classification; Posterior probability; Class balancing; Weighted KNN BibRef

Jiang, X.H.[Xian-Hua], Motai, Y.[Yuichi], Snapp, R.R.[Robert R.], Zhu, X.Q.[Xing-Quan],
Accelerated Kernel Feature Analysis,
CVPR06(I: 109-116).
IEEE DOI Link 0606
BibRef

Hernández-Rodríguez, S.[Selene], Carrasco-Ochoa, J.A.[J. Ariel], Martínez-Trinidad, J.F.[J. Francisco],
Fast k Most Similar Neighbor Classifier for Mixed Data Based on a Tree Structure and Approximating-Eliminating,
CIARP08(364-371).
Springer DOI Link 0809
BibRef
Earlier: A1, A3, A2:
Fast k Most Similar Neighbor Classifier for Mixed Data Based on a Tree Structure,
CIARP07(407-416).
Springer DOI Link 0711
BibRef

Gomez-Ballester, E.[Eva], Micó, L.[Luisa], Oncina, J.[Jose],
A Pruning Rule Based on a Distance Sparse Table for Hierarchical Similarity Search Algorithms,
SSPR08(926-936).
Springer DOI Link 0812
BibRef

Oncina, J.[Jose], Thollard, F.[Franck], Gómez-Ballester, E.[Eva], Micó, L.[Luisa], Moreno-Seco, F.[Francisco],
A Tabular Pruning Rule in Tree-Based Fast Nearest Neighbor Search Algorithms,
IbPRIA07(II: 306-313).
Springer DOI Link 0706
BibRef

Li, H.Y.[Hui-Ya], Yeh, Y.J.[Yao-Jung], Hwang, W.J.[Wen-Jyi],
Using Wavelet Transform and Partial Distance Search to Implement k NN Classifier on FPGA with Multiple Modules,
ICIAR07(1105-1116).
Springer DOI Link 0708
BibRef

Yeh, Y.J.[Yao-Jung], Li, H.Y.[Hui-Ya], Hwang, W.J.[Wen-Jyi], Fang, C.Y.[Chiung-Yao],
FPGA Implementation of k NN Classifier Based on Wavelet Transform and Partial Distance Search,
SCIA07(512-521).
Springer DOI Link 0706
BibRef

Lou, Z.[Zhen], Jin, Z.[Zhong],
Novel Adaptive Nearest Neighbor Classifiers Based On Hit-Distance,
ICPR06(III: 87-90).
WWW Version. 0609
BibRef

Yang, S.[Shu], Zhang, C.[Chao],
Regression Nearest Neighbor in Face Recognition,
ICPR06(III: 515-518).
WWW Version. 0609
BibRef

Chou, C.H.[Chien-Hsing], Kuo, B.H.[Bo-Han], Chang, F.[Fu],
The Generalized Condensed Nearest Neighbor Rule as A Data Reduction Method,
ICPR06(II: 556-559).
WWW Version. 0609
BibRef

Lu, Z.M.[Zhe-Ming], Burkhardt, H.[Hans],
Fast Image Retrieval Based on Equal-average Equal-variance K-Nearest Neighbour Search,
ICPR06(II: 853-).
WWW Version. 0609
BibRef

Mainar-Ruiz, G.[Gloria], Perez-Cortes, J.C.[Juan-Carlos],
Approximate Nearest Neighbor Search using a Single Space-filling Curve and Multiple Representations of the Data Points,
ICPR06(II: 502-505).
WWW Version. 0609
BibRef

Snapp, R.R.[Robert R.], Palau, A.M.[Alessandro M.],
The Labelled Cell Classifier: A Fast Approximation to k Nearest Neighbors,
ICPR98(Vol I: 823-827).
IEEE DOI Link 9808
BibRef

Juan, A.[Alfons], Aibar, P., Vidal, E.,
Fast k-Nearest-Neighbours Searching Through Extended Versions of the Approximating and Eliminating Search Algorithm (AESA),
ICPR98(Vol I: 828-830).
IEEE DOI Link 9808
BibRef

Hofman, I.[Irving], Jarvis, R.[Ray],
Robust and Efficient Cluster Analysis Using a Shared Near Neighbours Approach,
ICPR98(Vol I: 243-247).
IEEE DOI Link 9808
BibRef

Skubalska-Rafajlowicz, E., Krzyzak, A.,
Fast K-NN Classification Rule Using Metrics on Space-Filling Curves,
ICPR96(II: 121-125).
IEEE DOI Link 9608
(Technical Univ. of Wroclaw, PL) BibRef

Chapter on Pattern Recognition, Clustering, Statistics, Grammars, Learning, Neural Nets, Genetic Algorithms continues in
Linear Separable Classification .