An Algorithm for Finding Best Matches in Logarithmic Expected Time

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An Algorithm for Finding Best Matches in Logarithmic Expected Time

Full text

Pdf (1.15 MB)

Source

ACM Transactions on Mathematical Software (TOMS) archive
Volume 3 , Issue 3 (September 1977) table of contents

Pages: 209 - 226

Year of Publication: 1977

ISSN:0098-3500

Authors

Jerome H. Friedman	Stanford Linear Accelerator Center, Stanford University, Stanford, CA
Jon Louis Bentley	Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC
Raphael Ari Finkel	Department of Computer Science, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 55, Downloads (12 Months): 565, Citation Count: 153

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/355744.355745 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	2	W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
	3	FINKEL, R.A., AND BENTLEY, J.L. Quad trees--a data structure for retrmval on composite keys. Acta Informatica 4, 1 (1974), 1-9.
	4	FRIEDMAN, J.H., BASKETT, F., AND SHUSTEK, L.J. An algorithm for finding nearest neighbors. IEEE Trans. Comptrs C-24 (1975), 1000-1006.
	5	FUKUNAGA, K., AND HOSTETLER, L.D Optimization of k-nearest neighbor density estimates. 1EEE Trans. Inform Theory IT-19 (1973), 320-326.
	6	FUKUNAGA, K., AND NARENDRA, P.M. A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. Comptrs. C-24 (1975), 750-753.
	7	HYAYIL, L., Am) RZVEST, R.L. Constructing optimal binary decision trees is NP-complete. Information Processing Letters 5, (May 1976), 15-17.
	8	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	9	PIZER, S.M. Numerical Computing and Mathematical Analysis, Science Research Associates, Chicago, Ill., 1975, p. 88, eq. 87.
	10	RIVEST, R. On the optimality of Elias' algorithm for performing best match searches. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 678-681.
	11	Michael Ian Shamos, Geometric complexity, Proceedings of seventh annual ACM symposium on Theory of computing, p.224-233, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803772]

CITED BY 153

	Lin Liang , Ce Liu , Ying-Qing Xu , Baining Guo , Heung-Yeung Shum, Real-time texture synthesis by patch-based sampling, ACM Transactions on Graphics (TOG), v.20 n.3, p.127-150, July 2001
	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980
	F. Cazals, Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering, Proceedings of the fourteenth annual symposium on Computational geometry, p.222-230, June 07-10, 1998, Minneapolis, Minnesota, United States
	Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
	Richard Anderson , Brian Tjaden, The inverse nearest neighbor problem with astrophysical applications, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.767-768, January 07-09, 2001, Washington, D.C., United States
	Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, ACM SIGMOD Record, v.27 n.2, p.154-165, June 1998
	Dennis Shasha , Tsong-Li Wang, New techniques for best-match retrieval, ACM Transactions on Information Systems (TOIS), v.8 n.2, p.140-158, Apr. 1990
	Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States
	Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979
	Caroline M. Eastman , Stephen F. Weiss, A tree algorithm for nearest neighbor searching in document retrieval systems, ACM SIGIR Forum, v.13 n.1, p.131-149, May 1978
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Wu, An optimal algorithm for approximate nearest neighbor searching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.573-582, January 23-25, 1994, Arlington, Virginia, United States
	Christian Böhm, A cost model for query processing in high dimensional data spaces, ACM Transactions on Database Systems (TODS), v.25 n.2, p.129-178, June 2000
	Michael Murphy , Steven S. Skiena, Ranger: a tool for nearest neighbor search in high dimensions, Proceedings of the ninth annual symposium on Computational geometry, p.403-404, May 18-21, 1993, San Diego, California, United States
	Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984
	Mark K. Wheeler , Yoichi Sato , Katsushi Ikeuchi, Consensus surfaces for modeling 3D objects from multiple range images, Modelling from reality, Kluwer Academic Publishers, Norwell, MA, 2001
	Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999
	David P. Williamson , Michel X. Goemans, Computational experience with an approximation algorithm on large-scale Euclidean matching instances, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.355-364, January 23-25, 1994, Arlington, Virginia, United States
	A. El-Hamdouchi , P. Willett, Hierarchic document classification using Ward's clustering method, Proceedings of the 9th annual international ACM SIGIR conference on Research and development in information retrieval, p.149-156, September 1986, Palazzo dei Congressi, Pisa, Italy
	K. V. Ravi Kanth , Divyakant Agrawal , Ambuj Singh, Dimensionality reduction for similarity searching in dynamic databases, ACM SIGMOD Record, v.27 n.2, p.166-176, June 1998
	John Gerald Cleary, Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.183-192, June 1979
	Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States
	James McNames, A Fast Nearest-Neighbor Algorithm Based on a Principal Axis Search Tree, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.9, p.964-976, September 2001
	Tapas Kanungo , David M. Mount , Nathan S. Netanyahu , Christine Piatko , Ruth Silverman , Angela Y. Wu, The analysis of a simple k-means clustering algorithm, Proceedings of the sixteenth annual symposium on Computational geometry, p.100-109, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Douglas A. Talbert , Doug Fisher, An empirical analysis of techniques for constructing and searching k-dimensional trees, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.26-33, August 20-23, 2000, Boston, Massachusetts, United States
	Paul Heckbert, Color image quantization for frame buffer display, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.297-307, July 1982
	Raphael A. Finkel , Arkady Zaslavsky , Krisztián Monostori , Heinz Schmidt, Signature extraction for overlap detection in documents, Australian Computer Science Communications, v.24 n.1, p.59-64, January-February 2002
	Apostolos N. Papadopoulos , Yannis Manolopoulos, Similarity query processing using disk arrays, ACM SIGMOD Record, v.27 n.2, p.225-236, June 1998
	Raphael Finkel , Udi Manber, DIB—a distributed implementation of backtracking, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.235-256, April 1987
	Andrew McCallum , Kamal Nigam , Lyle H. Ungar, Efficient clustering of high-dimensional data sets with application to reference matching, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.169-178, August 20-23, 2000, Boston, Massachusetts, United States
	R. Kurniawati , J. S. Jin , J. A. Shepherd, An efficient nearest-neighbour search while varying Euclidean metrics, Proceedings of the sixth ACM international conference on Multimedia, p.411-418, September 13-16, 1998, Bristol, United Kingdom
	Won-Ki Jeong , Chang-Hun Kim, Direct reconstruction of a displaced subdivision surface from unorganized points, Graphical Models, v.64 n.2, p.78-93, March 2002
	A. Belussi , E. Bertino , B. Catania, Using spatial data access structures for filtering nearest neighbor queries, Data & Knowledge Engineering, v.40 n.1, p.1-31, January 2002
	Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001
	D. A. Beckley , M. W. Evens , V. K. Raman, Multikey retrieval from K-d trees and QUAD-trees, ACM SIGMOD Record, v.14 n.4, p.291-301, May 1985
	Weixiong Zhang , Randal W. Hill, Jr., A template-based and pattern-driven approach to situation awareness and assessment in virtual humans, Proceedings of the fourth international conference on Autonomous agents, p.116-123, June 03-07, 2000, Barcelona, Spain
	Sunil Arya , David M. Mount , Onuttom Narayan, Accounting for boundary effects in nearest neighbor searching, Proceedings of the eleventh annual symposium on Computational geometry, p.336-344, June 05-07, 1995, Vancouver, British Columbia, Canada
	Matthew Easley , Elizabeth Bradley, Information granulation in automated modeling, Granular computing: an emerging paradigm, Physica-Verlag GmbH, Heidelberg, Germany, 2001
	D. P. Anderson, Techniques for Reducing Pen Plotting Time, ACM Transactions on Graphics (TOG), v.2 n.3, p.197-212, July 1983
	Jon M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.599-608, May 04-06, 1997, El Paso, Texas, United States
	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, ACM SIGMOD Record, v.27 n.2, p.142-153, June 1998
	Jon Louis Bentley, K-d trees for semidynamic point sets, Proceedings of the sixth annual symposium on Computational geometry, p.187-197, June 07-09, 1990, Berkley, California, United States
	Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Marina L. Gavrilova, On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets, The Journal of Supercomputing, v.22 n.1, p.87-98, May 2002
	David M. Mount , Nathan S. Netanyahu , Jacqueline Le Moigne, Improved algorithms for robust point pattern matching and applications to image registration, Proceedings of the fourteenth annual symposium on Computational geometry, p.155-164, June 07-10, 1998, Minneapolis, Minnesota, United States
	Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, ACM SIGMOD Record, v.26 n.2, p.1-12, June 1997
	Tetsuro Ito , Makoto Kizawa, Hierarchical file organization and its application to similar-string matching, ACM Transactions on Database Systems (TODS), v.8 n.3, p.410-433, Sept. 1983
	Peter N. Yianilos, Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.361-370, January 09-11, 2000, San Francisco, California, United States
	Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
	Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984
	David Hull, Improving text retrieval for the routing problem using latent semantic indexing, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.282-291, July 03-06, 1994, Dublin, Ireland
	Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, ACM SIGMOD Record, v.24 n.2, p.71-79, May 1995
	Wayne O. Cochran , John C. Hart , Patrick J. Flynn, Fractal Volume Compression, IEEE Transactions on Visualization and Computer Graphics, v.2 n.4, p.313-322, December 1996
	Michael Berthold , David J. Hand, References, Intelligent data analysis, Springer-Verlag New York, Inc., New York, NY, 2003
	Daniel Sýkora , Jan Buriánek , Jiří Žára, Unsupervised colorization of black-and-white cartoons, Proceedings of the 3rd international symposium on Non-photorealistic animation and rendering, June 07-09, 2004, Annecy, France
	A. Faragó , T. Linder , G. Lugosi, Fast Nearest-Neighbor Search in Dissimilarity Spaces, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.9, p.957-962, September 1993
	Hanan Samet , Aya Soffer, MARCO: MAp Retrieval by COntent, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.783-798, August 1996
	Dragan Tubic , Patrick Hébert , Denis Laurendeau, A volumetric approach for interactive 3D modeling, Computer Vision and Image Understanding, v.92 n.1, p.56-77, October 2003
	Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
	David W. Jacobs , Daphna Weinshall , Yoram Gdalyahu, Classification with Nonmetric Distances: Image Retrieval and Class Representation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.6, p.583-600, June 2000
	Sunil Arya , Ho-Yam Addy Fu, Expected-case complexity of approximate nearest neighbor searching, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.379-388, January 09-11, 2000, San Francisco, California, United States
	Stephen F. Weiss, A probabilistic algorithm for nearest neighbour searching, Proceedings of the 3rd annual ACM conference on Research and development in information retrieval, p.325-333, June 23-27, 1980, Cambridge, England
	Xiaolin Wu, Color quantization by dynamic programming and principal analysis, ACM Transactions on Graphics (TOG), v.11 n.4, p.348-372, Oct. 1992
	S. J. Wan , S. K. M. Wong , P. Prusinkiewicz, An algorithm for multidimensional data clustering, ACM Transactions on Mathematical Software (TOMS), v.14 n.2, p.153-162, June 1988
	Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997
	Walter Daelemans , Antal Van Den Bosch , Ton Weijters, IGTree: Using Trees for Compression and Classification in Lazy LearningAlgorithms, Artificial Intelligence Review, v.11 n.1-5, p.407-423, Feb. 1997
	Pierre Zakarauskas , John M. Ozard, Complexity Analysis for Partitioning Nearest Neighbor Searching Algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.6, p.663-668, June 1996
	Lawrence K. Saul , Sam T. Roweis, Think globally, fit locally: unsupervised learning of low dimensional manifolds, The Journal of Machine Learning Research, 4, p.119-155, 12/1/2003
	Ting Liu , Ke Yang , Andrew W. Moore, The IOC algorithm: efficient many-class non-parametric classification for high-dimensional data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Huan Liu , Hiroshi Motoda , Lei Yu, A selective sampling approach to active feature selection, Artificial Intelligence, v.159 n.1-2, p.49-74, November 2004
	Y. Sirisathitkul , S. Auwatanamongkol , B. Uyyanonvara, Color image quantization using distances between adjacent colors along the color axis with highest color variance, Pattern Recognition Letters, v.25 n.9, p.1025-1043, 2 July 2004
	Hanan Samet, Object-based and image-based object representations, ACM Computing Surveys (CSUR), v.36 n.2, p.159-217, June 2004
	Zhigang Deng , Shri Narayanan , Carlos Busso , Ulrich Neumann, Audio-based head motion synthesis for Avatar-based telepresence systems, Proceedings of the 2004 ACM SIGMM workshop on Effective telepresence, October 15-15, 2004, New York, NY, USA
	Keke Chen , Ling Liu, ClusterMap: labeling clusters in large datasets via visualization, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	A. M. Roumani , D. B. Skillicorn, Mobile services discovery and selection in the publish/subscribe paradigm, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.163-173, October 04-07, 2004, Markham, Ontario, Canada
	David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004
	Mark D. Wheeler , Katsushi Ikeuchi, Sensor Modeling, Probabilistic Hypothesis Generation, and Robust Localization for Object Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.3, p.252-265, March 1995
	Yufei Tao , Jun Zhang , Dimitris Papadias , Nikos Mamoulis, An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1169-1184, October 2004
	Evgeny Roytman , Craig Gotsman, Dynamic Color Quantization of Video Sequences, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.274-286, September 1995
	Apostolos N. Papadopoulos , Yannis Manolopoulos, Distributed Processing of Similarity Queries, Distributed and Parallel Databases, v.9 n.1, p.67-92, January 1, 2001
	Gerald Dalley , Patrick Flynn, Pair-wise range image registration: a study in outlier classification, Computer Vision and Image Understanding, v.87 n.1-3, p.104-115, July 2002
	Aaron Hertzmann , Steven M. Seitz, Example-Based Photometric Stereo: Shape Reconstruction with General, Varying BRDFs, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.8, p.1254-1264, August 2005
	Saurabh K. Tiwary , Rob A. Rutenbar, Scalable trajectory methods for on-demand analog macromodel extraction, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Mineichi Kudo , Naoto Masuyama , Jun Toyama , Masaru Shimbo, Simple termination conditions for k-nearest neighbor method, Pattern Recognition Letters, v.24 n.9-10, p.1203-1213, 01 June 2003
	Zhengzhu Feng , Richard Dearden , Nicolas Meuleau , Richard Washington, Dynamic programming for structured continuous Markov decision problems, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.154-161, July 07-11, 2004, Banff, Canada
	Jeffrey S. Beis , David G. Lowe, Indexing without Invariants in 3D Object Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.10, p.1000-1015, October 1999
	Kurt Driessens , Sašo Džeroski, Combining model-based and instance-based learning for first order regression, Proceedings of the 22nd international conference on Machine learning, p.193-200, August 07-11, 2005, Bonn, Germany
	Ryusuke Sagawa , Ko Nishino , Katsushi Ikeuchi, Adaptively Merging Large-Scale Range Data with Reflectance Properties, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.3, p.392-405, March 2005
	Marcos Salganicoff, Tolerating Concept and Sampling Shift in Lazy Learning UsingPrediction Error Context Switching, Artificial Intelligence Review, v.11 n.1-5, p.133-155, Feb. 1997
	N. Kim , N. Kehtarnavaz, DWT-based scene-adaptive color quantization, Real-Time Imaging, v.11 n.5-6, p.443-453, October - December 2005
	Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990
	Md. Saiful Islam , Andrzej Sluzek , Lin Zhu, Detecting and matching interest points in relative scale, Machine Graphics & Vision International Journal, v.14 n.3, p.259-283, January 2005
	Vincent C. H. Ma , Michael D. McCool, Low latency photon mapping using block hashing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
	A. Corral , Y. Manolopoulos , Y. Theodoridis , M. Vassilakopoulos, Algorithms for processing K-closest-pair queries in spatial databases, Data & Knowledge Engineering, v.49 n.1, p.67-104, 1 April 2004
	Markku Tamminen , Reijo Sulonen, The excell method for efficient geometric access to data, Proceedings of the 19th conference on Design automation, p.345-351, January 1982
	Rémi Munos , Andrew Moore, Variable Resolution Discretization in Optimal Control, Machine Learning, v.49 n.2-3, p.291-323, November-December 2002
	Miroslav Kubat , Martin Cooperson, Jr., A reduction technique for nearest-neighbor classification: Small groups of examples, Intelligent Data Analysis, v.5 n.6, p.463-476, December 2001
	Ricardo Bezerra de Andrade e Silva , Teresa Bernarda Ludermir, Hybrid systems of local basis functions, Intelligent Data Analysis, v.5 n.3, p.227-244, August 2001
	Antonin Rozsypal , Miroslav Kubat, Selecting representative examples and attributes by a genetic algorithm, Intelligent Data Analysis, v.7 n.4, p.291-304, September 2003
	Apostolos Papadopoulos , Yannis Manolopoulos, Nearest Neighbor Queries in Shared-Nothing Environments, Geoinformatica, v.1 n.4, p.369-392, December 1997
	Gabriel Ghinita , Panagiotis Karras , Panos Kalnis , Nikos Mamoulis, Fast data anonymization with low information loss, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Keke Chen , Ling Liu, iVIBRATE: Interactive visualization-based framework for clustering large datasets, ACM Transactions on Information Systems (TOIS), v.24 n.2, p.245-294, April 2006
	Peter Klier , Richard J. Fateman, On finding the closest bitwise matches in a fixed set, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.88-97, March 1991
	Alina Beygelzimer , Sham Kakade , John Langford, Cover trees for nearest neighbor, Proceedings of the 23rd international conference on Machine learning, p.97-104, June 25-29, 2006, Pittsburgh, Pennsylvania
	Erion Plaku , Lydia E. Kavraki, Distributed computation of the knn graph for large high-dimensional point sets, Journal of Parallel and Distributed Computing, v.67 n.3, p.346-359, March, 2007
	Xiaobin Ma , Shashi Shekhar , Hui Xiong , Pusheng Zhang, Exploiting a page-level upper bound for multi-type nearest neighbor queries, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
	Yonghuai Liu, A mean field annealing approach to accurate free form shape matching, Pattern Recognition, v.40 n.9, p.2418-2436, September, 2007
	Hyunjung Shin , Sungzoon Cho, Neighborhood Property--Based Pattern Selection for Support Vector Machines, Neural Computation, v.19 n.3, p.816-855, March 2007
	Dmitry Datsenko , Michael Elad, Example-based single document image super-resolution: a global MAP approach with outlier rejection, Multidimensional Systems and Signal Processing, v.18 n.2-3, p.103-121, September 2007
	Axel Pinz, Object categorization, Foundations and Trends® in Computer Graphics and Vision, v.1 n.4, p.255-353, December 2005
	Zhaolin Cheng , Dhanya Devarajan , Richard J. Radke, Determining vision graphs for distributed camera networks using feature digests, EURASIP Journal on Applied Signal Processing, v.2007 n.1, p.220-220, 1 January 2007
	Stefan Harmeling , Guido Dornhege , David Tax , Frank Meinecke , Klaus-Robert Müller, From outliers to prototypes: Ordering data, Neurocomputing, v.69 n.13-15, p.1608-1618, August, 2006
	Ting Liu , Andrew W. Moore , Alexander Gray, New Algorithms for Efficient High-Dimensional Nonparametric Classification, The Journal of Machine Learning Research, 7, p.1135-1158, 12/1/2006
	Sanghamitra Bandyopadhyay , Sriparna Saha, GAPS: A clustering method using a new point symmetry-based distance measure, Pattern Recognition, v.40 n.12, p.3430-3451, December, 2007
	Aya Soffer , Hanan Samet, Integrating symbolic images into a multimedia database system using classification and abstraction approaches, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.4, p.253-274, December 1998
	Ada Wai-chee Fu , Polly Mei-shuen Chan , Yin-Ling Cheung , Yiu Sang Moon, Dynamic vp-tree indexing for n-nearest neighbor search given pair-wise distances, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.2, p.154-173, July 2000
	J. Galindo , P. Tamayo, Credit Risk Assessment Using Statistical and MachineLearning: Basic Methodology and Risk Modeling Applications, Computational Economics, v.15 n.1-2, p.107-143, April 2000
	B. Park , H. Kargupta , E. Johnson , E. Sanseverino , D. Hershberger , L. Silvestre, Distributed, Collaborative Data Analysis from Heterogeneous Sites Using a Scalable Evolutionary Technique, Applied Intelligence, v.16 n.1, p.19-42, January-February 2002
	Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
	Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
	Huanzhuo Ye , Hongxia Luo , Kezhen Song , Huali Xiang , Jing Chen, Indexing moving objects based on 2 ⁿ index tree, Proceedings of the 6th Conference on 6th WSEAS Int. Conf. on Artificial Intelligence, Knowledge Engineering and Data Bases, p.175-180, February 16-19, 2007, Corfu Island, Greece
	M. K. Hughey , M. W. Berry, Improved Query Matching Using kd-Trees: A Latent Semantic Indexing Enhancement, Information Retrieval, v.2 n.4, p.287-302, May 2000
	Yonghuai Liu, Constraints for closest point finding, Pattern Recognition Letters, v.29 n.7, p.841-851, May, 2008
	Xiao-Bai Li , Sumit Sarkar, A Tree-Based Data Perturbation Approach for Privacy-Preserving Data Mining, IEEE Transactions on Knowledge and Data Engineering, v.18 n.9, p.1278-1283, September 2006
	Arnon Amir , Michael Lindenbaum, A Generic Grouping Algorithm and Its Quantitative Analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.20 n.2, p.168-185, February 1998
	Sameer A. Nene , Shree K. Nayar, A Simple Algorithm for Nearest Neighbor Search in High Dimensions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.9, p.989-1003, September 1997
	Heng Yang , Qing Wang , Zhoucan He, Randomized sub-vectors hashing for high-dimensional image feature matching, Proceeding of the 16th ACM international conference on Multimedia, October 26-31, 2008, Vancouver, British Columbia, Canada
	Manish Sarkar, Fuzzy-rough nearest neighbor algorithms in classification, Fuzzy Sets and Systems, v.158 n.19, p.2134-2152, October, 2007
	Mirko Zadravec , Andrej Brodnik , Markus Mannila , Merja Wanne , Borut alik, A practical approach to the 2D incremental nearest-point problem suitable for different point distributions, Pattern Recognition, v.41 n.2, p.646-653, February, 2008
	Lawrence Cayton, Fast nearest neighbor retrieval for bregman divergences, Proceedings of the 25th international conference on Machine learning, p.112-119, July 05-09, 2008, Helsinki, Finland
	Enno Littmann , Helge Ritter, Learning and generalization in cascade network architectures, Neural Computation, v.8 n.7, p.1521-1539, October 1, 1996
	S. Garrido , L. Moreno , D. Blanco, Exploration of a cluttered environment using Voronoi Transform and Fast Marching, Robotics and Autonomous Systems, v.56 n.12, p.1069-1081, December, 2008
	Ahmed M. Khedr , Ahmed Salim, Decomposable algorithms for nearest neighbor computing, Journal of Parallel and Distributed Computing, v.68 n.7, p.902-912, July, 2008
	Leonidas Lymberopoulos , Symeon Papavassiliou , Vasilis Maglaris, A novel load balancing mechanism for P2P networking, Proceedings of the first international conference on Networks for grid applications, October 17-19, 2007, Lyon, France
	Grigorios Loukides , Jianhua Shao, Data utility and privacy protection trade-off in k-anonymisation, Proceedings of the 2008 international workshop on Privacy and anonymity in information society, March 29-29, 2008, Nantes, France
	Pasi Franti , Olli Virmajoki , Ville Hautamaki, Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.11, p.1875-1881, November 2006
	Simon Heinzle , Gaël Guennebaud , Mario Botsch , Markus Gross, A hardware processing unit for point sets, Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, June 20-21, 2008, Sarajevo, Bosnia and Herzegovina
	Lihong Li , Michael L. Littman, Lazy approximation for solving continuous finite-horizon MDPs, Proceedings of the 20th national conference on Artificial intelligence, p.1175-1180, July 09-13, 2005, Pittsburgh, Pennsylvania
	Ying Liu , Xin Chen , Chengcui Zhang , Alan Sprague, Semantic clustering for region-based image retrieval, Journal of Visual Communication and Image Representation, v.20 n.2, p.157-166, February, 2009
	Lihong Li , Michael L. Littman , Christopher R. Mansley, Online exploration in least-squares policy iteration, Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems, May 10-15, 2009, Budapest, Hungary
	Sriparna Saha , Sanghamitra Bandyopadhyay, Some Symmetry Based Classifiers, Fundamenta Informaticae, v.90 n.1-2, p.107-123, February 2009
	Yonghuai Liu, Replicator Dynamics in the Iterative Process for Accurate Range Image Matching, International Journal of Computer Vision, v.83 n.1, p.30-56, June 2009
	S. Garrido , L. Moreno , D. Blanco, Exploration of 2D and 3D Environments using Voronoi Transform and Fast Marching Method, Journal of Intelligent and Robotic Systems, v.55 n.1, p.55-80, June 2009
	Gerald Fritz , Christin Seifert , Lucas Paletta , Horst Bischof, Rapid object recognition from discriminative regions of interest, Proceedings of the 19th national conference on Artifical intelligence, p.444-449, July 25-29, 2004, San Jose, California
	Sriparna Saha , Sanghamitra Bandyopadhyay, A new point symmetry based fuzzy genetic clustering technique for automatic evolution of clusters, Information Sciences: an International Journal, v.179 n.19, p.3230-3246, September, 2009
	Emmanuel Benazera , Louise Travé-Massuyés, Generating Diagnoses from Conflict Sets with Continuous Attributes, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.179-183, June 27, 2008
	Shlomo Berkovsky , Tsvi Kuflik , Francesco Ricci, P2P case storage and retrieval with an unspecified ontology, Artificial Intelligence Review, v.28 n.3, p.227-255, October 2007
	Nicolas Meuleau , Emmanuel Benazera , Ronen I. Brafman , Eric A. Hansen , Mausam Mausam, A heuristic search approach to planning with continuous resources in stochastic domains, Journal of Artificial Intelligence Research, v.34 n.1, p.27-59, January 2009
	Joseph O'Rourke, Dynamically quantized spaces for focusing the Hough Transform, Proceedings of the 7th international joint conference on Artificial intelligence, p.737-739, August 24-28, 1981, Vancouver, BC, Canada
	Sosa-Herrera Antonio , Rodriguez-Romo Suemi, Distance search techniques in quadtrees and octrees for random particle cluster simulations, Proceedings of the 9th WSEAS International Conference on Systems Theory and Scientific Computation, p.81-86, August 20-22, 2009, Moscow, Russia
	Kilian Q. Weinberger , Lawrence K. Saul, Distance Metric Learning for Large Margin Nearest Neighbor Classification, The Journal of Machine Learning Research, 10, p.207-244, June 2009
	Sosa-Herrera Antonio , Rodriguez-Romo Suemi, Variable precision distance search for random fractal cluster simulations, WSEAS Transactions on Computers, v.8 n.8, p.1245-1255, August 2009
	Mausam Mausam , Emmanuel Benazera , Ronen Brafman , Nicolas Meuleau , Eric A. Hansen, Planning with continuous resources in stochastic domains, Proceedings of the 19th international joint conference on Artificial intelligence, p.1244-1251, July 30-August 05, 2005, Edinburgh, Scotland