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.
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.[Luisa], Oncina, J.[Jose], 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.[Luisa], Oncina, J.[Jose], 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

Moreno-Seco, F.[Francisco], Micó, L.[Luisa], Oncina, J.[Jose],
A modification of the LAESA algorithm for approximated k-NN classification,
PRL(24), No. 1-3, January 2003, pp. 47-53.
Elsevier DOI Link 0211
BibRef
Earlier:
A new classification rule based on nearest neighbour search,
ICPR04(IV: 408-411).
IEEE DOI Link 0409
BibRef

Socorro, R.[Raisa], Mico, L.[Luisa], Oncina, J.[Jose],
A fast pivot-based indexing algorithm for metric spaces,
PRL(32), No. 11, 1 August 2011, pp. 1511-1516.
Elsevier DOI Link
WWW Version. 1108
Fast nearest neighbor; Similarity search; Metric space See also approximate median search algorithm in non-metric spaces, An. BibRef

Mico, L.[Luisa], Oncina, J.[Jose],
A Constant Average Time Algorithm to Allow Insertions in the LAESA Fast Nearest Neighbour Search Index,
ICPR10(3911-3914).
IEEE DOI Link 1008
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.
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.
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.
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.
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.
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. 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 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
Earlier:
Winner-update Algorithm for Nearest Neighbor Search,
ICPR00(Vol II: 704-707).
IEEE DOI Link 0009
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

Hernández-Rodríguez, S.[Selene], Martínez-Trinidad, J.F.[J. Francisco], Carrasco-Ochoa, J.A.[J. Ariel],
Fast k most similar neighbor classifier for mixed data (tree k-MSN),
PR(43), No. 3, March 2010, pp. 873-886.
Elsevier DOI Link
WWW Version. 1001
BibRef
Earlier: A1, A3, A2:
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, A2, A3:
Fast k Most Similar Neighbor Classifier for Mixed Data Based on a Tree Structure,
CIARP07(407-416).
Springer DOI Link 0711
Nearest neighbor rule; Fast k nearest neighbor search; Mixed data; Non-metric comparison functions BibRef

Chang, C.T.[Chih-Tang], Lai, J.Z.C.[Jim Z.C.], Jeng, M.D.,
Fast agglomerative clustering using information of k-nearest neighbors,
PR(43), No. 12, December 2010, pp. 3958-3968.
Elsevier DOI Link
WWW Version. 1003
Nearest neighbor; Agglomerative clustering; Vector quantization BibRef

Fernandez-Navarro, F.[Francisco], Hervas-Martinez, C.[Cesar], Gutierrez, P.A.[Pedro Antonio],
A dynamic over-sampling procedure based on sensitivity for multi-class problems,
PR(44), No. 8, August 2011, pp. 1821-1833.
Elsevier DOI Link
WWW Version. 1104
Classification; Multi-class; Sensitivity; Accuracy; Memetic algorithm; Imbalanced datasets; Over-sampling method; SMOTE BibRef

Raniszewski, M.[Marcin],
Sequential Reduction Algorithm for Nearest Neighbor Rule,
ICCVG10(II: 219-226).
Springer DOI Link 1009
Training set size reduction. BibRef

Brandt, J.[Jonathan],
Transform coding for fast approximate nearest neighbor search in high dimensions,
CVPR10(1815-1822).
IEEE DOI Link 1006
BibRef

Min, K.[Kerui], Yang, L.J.[Lin-Jun], Wright, J.[John], Wu, L.[Lei], Hua, X.S.[Xian-Sheng], Ma, Y.[Yi],
Compact projection: Simple and efficient near neighbor search with practical memory requirements,
CVPR10(3477-3484).
IEEE DOI Link 1006
BibRef

Himei, N.[Noritaka], Wada, T.[Toshikazu],
Approximate nearest neighbor search on HDD,
Emergent09(2101-2108).
IEEE DOI Link 0910
BibRef

Matsushita, Y.[Yusuke], Wada, T.[Toshikazu],
Principal Component Hashing: An Accelerated Approximate Nearest Neighbor Search,
PSIVT09(374-385).
Springer DOI Link 0901
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

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 .