ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Full text PdfPdf (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): 84,   Downloads (12 Months): 504,   Citation Count: 141
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
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  141
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
 
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
 
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
 
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
Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, ACM SIGMOD Record, v.24 n.2, p.71-79, May 1995
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
 
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
 
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
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
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
 
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
 
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
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
D. P. Anderson, Techniques for Reducing Pen Plotting Time, ACM Transactions on Graphics (TOG), v.2 n.3, p.197-212, July 1983
 
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
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
 
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
 
N. Kim , N. Kehtarnavaz, DWT-based scene-adaptive color quantization, Real-Time Imaging, v.11 n.5-6, p.443-453, October - December 2005
 
Yonghuai Liu, Constraints for closest point finding, Pattern Recognition Letters, v.29 n.7, p.841-851, May, 2008
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
 
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
Paul Heckbert, Color image quantization for frame buffer display, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.297-307, July 1982
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
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
 
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
 
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
Jean-Daniel Boissonnat, Geometric structures for three-dimensional shape representation, ACM Transactions on Graphics (TOG), v.3 n.4, p.266-286, Oct. 1984
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
 
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
 
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
 
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
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
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
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
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
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
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
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
 
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
 
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
 
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
 
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
 
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
 
Huanzhuo Ye , Hongxia Luo , Kezhen Song , Huali Xiang , Jing Chen, Indexing moving objects based on 2 n 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
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
 
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
 
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
 
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
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
 
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
 
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
 
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
 
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
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
 
Enno Littmann , Helge Ritter, Learning and generalization in cascade network architectures, Neural Computation, v.8 n.7, p.1521-1539, October 1, 1996
 
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
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
 
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
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
 
Matthew Easley , Elizabeth Bradley, Information granulation in automated modeling, Granular computing: an emerging paradigm, Physica-Verlag GmbH, Heidelberg, Germany, 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
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
 
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
Xiaolin Wu, Color quantization by dynamic programming and principal analysis, ACM Transactions on Graphics (TOG), v.11 n.4, p.348-372, Oct. 1992
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
 
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
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
 
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
 
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
 
Apostolos Papadopoulos , Yannis Manolopoulos, Nearest Neighbor Queries in Shared-Nothing Environments, Geoinformatica, v.1 n.4, p.369-392, December 1997
 
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
 
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
 
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
 
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
 
David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004
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
 
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
 
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
 
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
 
Apostolos N. Papadopoulos , Yannis Manolopoulos, Distributed Processing of Similarity Queries, Distributed and Parallel Databases, v.9 n.1, p.67-92, January 1, 2001
 
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
 
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
 
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
 
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
 
Sriparna Saha , Sanghamitra Bandyopadhyay, Some Symmetry Based Classifiers, Fundamenta Informaticae, v.90 n.1-2, p.107-123, February 2009
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
 
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
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
 
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
Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979
 
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
 
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
 
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
 
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
 
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
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
 
Rémi Munos , Andrew Moore, Variable Resolution Discretization in Optimal Control, Machine Learning, v.49 n.2-3, p.291-323, November-December 2002
 
Hyunjung Shin , Sungzoon Cho, Neighborhood Property--Based Pattern Selection for Support Vector Machines, Neural Computation, v.19 n.3, p.816-855, March 2007
 
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
 
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
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
 
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
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
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
 
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
 
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
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
 
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
 
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
 
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
 
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
 
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
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
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
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
 
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
 
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
 
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
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
 
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
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
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
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
 
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
 
Yonghuai Liu, A mean field annealing approach to accurate free form shape matching, Pattern Recognition, v.40 n.9, p.2418-2436, September, 2007
 
Fionn Murtagh, Clustering in massive data sets, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984
 
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
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
Hanan Samet, Object-based and image-based object representations, ACM Computing Surveys (CSUR), v.36 n.2, p.159-217, June 2004
 
Axel Pinz, Object categorization, Foundations and Trends® in Computer Graphics and Vision, v.1 n.4, p.255-353, December 2005
 
Christopher G. Atkeson , Andrew W. Moore , Stefan Schaal, Locally Weighted Learning, Artificial Intelligence Review, v.11 n.1-5, p.11-73, Feb. 1997
 
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
 
Michael Berthold , David J. Hand, References, Intelligent data analysis, Springer-Verlag New York, Inc., New York, NY, 2003
Jun-ichi Aoe, A compendium of key search references, ACM SIGIR Forum, v.24 n.3, p.26-42, Fall 1990

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  E. Data

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS


General Terms:
Algorithms, Design, Theory

Collaborative Colleagues:
Jerome H. Friedman: colleagues
Jon Louis Bentley: colleagues
Raphael Ari Finkel: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player