Approximate nearest neighbors: towards removing the curse of dimensionality
Abstract
Article Free Access Share on Approximate nearest neighbors: towards removing the curse of dimensionality Authors: Piotr Indyk Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile , Rajeev Motwani Department of Computer Science, Stanford University, Stanford, CA Department of Computer Science, Stanford University, Stanford, CAView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 604–613https://doi.org/10.1145/276698.276876Online:23 May 1998Publication History 2,363citation11,545DownloadsMetricsTotal Citations2,363Total Downloads11,545Last 12 Months769Last 6 weeks97 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
SSTH suffers from a serious efficiency issue due to the involvement of de-binarization and de-LSTM.
“However, SSTH suffers from serious efficiency issue due to the involvement of de-binarization and de-LSTM.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
For six query videos of different topics, UDVH-TSN makes fewer mistakes in retrieving similar videos for each query compared with SSTH.
“Given six query videos of different topics, the proposed algorithm makes fewer mistakes in retrieving the similar videos for each query compared with SSTH.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
On FCVID, SSTH training time is 8.21h at 16 bits, 8.23h at 32 bits, 8.48h at 64 bits, and 8.55h at 128 bits.
“SSTH [29] / / 8.21h / / 8.23h / / 8.48h / / 8.55h”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
The precision@100 at 64 bits reaches 26.1% under the proposed framework, and the difference over SSTH (20.4%) is 5.7%.
“For example, the precision@100 at 64 bits reaches 26.1% under the proposed framework and the difference over SSTH (20.4%) is 5.7%.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
The mAP@5 values at the code length of 128 are 59.3% and 57.1% for UDVH-TSN and UDVH-LSTM on FCVID, which are at least 7% higher than that in SSTH (50.1%).
“For examples, the mAP@5 values at the code length of 128 are 59.3% and 57.1% for UDVH-TSN and UDVH-LSTM on FCVID, which are at least 7% higher than that in SSTH (50.1%).”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
UDVH-based methods substantially yield better retrieval performance over SSTH.
“Moreover, the UDVH-based methods substantially yield better retrieval performance over SSTH, which is consistent with the results reported in Fig. 5 and further demonstrates the superiority of our self-taught training strategy involving clustering and balanced rotation.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
The total training cost for UDVH-based methods is less than 4.5 hours, which is much shorter than training SSTH (over 8 hours).
“Considering the deep architectures usually converge within t = 5 loops for the UDVH-based methods, the total training cost is less than 4.5 hours, which is much shorter than training SSTH (over 8 hours), thus indicating the high efficiency of the proposed hashing framework.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
The most time-consuming parts of SSTH include the backpropagation of Binary LSTM units when updating their binary outputs and the complex network structures, which are not adopted in the proposed algorithm.
“The most time-consuming parts of SSTH include the backpropagation of Binary LSTM units when updating their binary outputs and the complex network structures [29], which are not adopted in our algorithm.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
The mAP@5 values at 128 bits on FCVID are 50.1% and 57.1% for SSTH and UDVH-LSTM, which are over 15% higher than the values achieved when using CNN features.
“Specifically, as shown in Fig. 9(a), the mAP@5 values at 128 bits on FCVID are 50.1% and 57.1% for SSTH and UDVH-LSTM, which are over 15% higher than the values achieved when using CNN features.”
From Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval (2019) · cites this paper as [29]
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,620 · see citing works
Rayward-Smith, V. J., Cormen, T. H., Leiserson, C. E., & Rivest, R. L. (1991) · Journal of the Operational Research Society · doi:10.2307/2583667 · Cited by 16,953 · see citing works
Nearest neighbor pattern classification
Cover, T., & Hart, P. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1053964 · Cited by 16,936 · see citing works
Pattern classification and scene analysis
Duda, R. O., & Hart, P. E. (1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895 · see citing works
Indexing by latent semantic analysis
Deerwester, S. C., Dumais, S., Furnas, G. W., Landauer, T. K., & Harshman, R. A. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6 · Cited by 12,758 · see citing works
Introduction to Modern Information Retrieval
Salton, G., & McGill, M. J. (1983) · Virtual Defense Library (Ministerio de Defensa) · Cited by 9,743 · see citing works
Analysis of a complex of statistical variables into principal components.
Hotelling, H. (1933) · Journal of Educational Psychology · doi:10.1037/h0071325 · Cited by 9,691 · see citing works
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,659 · see citing works
Vector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,055 · see citing works
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,098 · see citing works
Self-citationPattern classification and scene analysis
Chien, Y. P. (1974) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1974.1100577 · Cited by 3,413 · see citing works
(1999) · Cited by 3,186 · see citing works
Self-citationQuery by image and video content: the QBIC system
Flickner, M., Sawhney, H., Niblack, W., Ashley, J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petković, D., et al. (1995) · Computer · doi:10.1109/2.410146 · Cited by 3,097 · see citing works
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,802 · see citing works
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,423 · see citing works
The design and analysis of spatial data structures
Samet, H. (1989) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,373 · see citing works
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,290 · see citing works
Algorithms in Combinatorial Geometry.
Goodman, J. E., & Edelsbrunner, H. (1989) · American Mathematical Monthly · doi:10.2307/2325168 · Cited by 1,800 · see citing works
On the resemblance and containment of documents
Broder, A. (2002) · Compression and Complexity of Sequences (SEQUENCES) · doi:10.1109/sequen.1997.666900 · Cited by 1,734 · see citing works
Query by Image and Video Content: The QBIC System
Flickner, M., Sawhney, H., Niblack, W., Ashley, J. J., Huang, Q., Dom, B., Gorkani, M., Hafner, J., Lee, D., Petković, D., et al. (2002) · Elsevier eBooks · doi:10.1016/b978-155860651-7/50108-x · Cited by 1,559 · see citing works
Algorithms in Combinatorial Geometry
Edelsbrunner, H. (1987) · Springer eBooks · doi:10.1007/978-3-642-61568-9 · Cited by 1,536 · see citing works
Syntactic clustering of the Web
Broder, A., Glassman, S. C., Manasse, M. S., & Zweig, G. (1997) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(97)00031-7 · Cited by 1,348 · see citing works
Efficient and effective Querying by Image Content
Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petković, D., & Equitz, W. (1994) · Journal of Intelligent Information Systems · doi:10.1007/bf00962238 · Cited by 1,250 · see citing works
Shamos, M. I., & Hoey, D. (1975) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1975.8 · Cited by 1,070 · see citing works
Pattern Classification and Scene Analysis.
Grenander, U., Duda, R. O., & Hart, P. E. (1974) · Journal of the American Statistical Association · doi:10.2307/2286028 · Cited by 1,018 · see citing works
(1993) · doi:10.5555/313559.313789 · Cited by 998 · see citing works
The Volume of Convex Bodies and Banach Space Geometry
Pisier, G. (1989) · Cambridge University Press eBooks · doi:10.1017/cbo9780511662454 · Cited by 997 · see citing works
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. G. (1995) · COMBINATORICA · doi:10.1007/bf01200757 · Cited by 972 · see citing works
Photobook: tools for content-based manipulation of image databases
Pentland, A. P., Picard, R. W., & Scarloff, S. (1994) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.171786 · Cited by 882 · see citing works
Discriminant adaptive nearest neighbor classification
Hastie, T., & Tibshirani, R. J. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.506411 · Cited by 833 · see citing works
A Weighted Nearest Neighbor Algorithm for Learning with Symbolic Features
Cost, S., & Salzberg, S. L. (1993) · Machine Learning · doi:10.1023/a:1022664626993 · Cited by 764 · see citing works
Storing a Sparse Table with 0 (1) Worst Case Access Time
Fredman, M. L., Komlós, J., & Szemerédi, E. (1984) · Journal of the ACM · doi:10.1145/828.1884 · Cited by 759 · see citing works
Über lineare Methoden in der Wahrscheinlichkeitsrechnung
Karhunen, K. (1947) · Suomalainen Tiedeakatemia eBooks · Cited by 706 · see citing works
Applications of a Planar Separator Theorem
Lipton, R. J., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209046 · Cited by 645 · see citing works
Applying Parallel Computation Algorithms in the Design of Serial Algorithms
Megiddo, N. (1983) · Journal of the ACM · doi:10.1145/2157.322410 · Cited by 632 · see citing works
An optimal algorithm for approximate nearest neighbor searching
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1994) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · doi:10.5555/314464.314652 · Cited by 590 · see citing works
Callahan, P. B., & Kosaraju, S. R. (1995) · Journal of the ACM · doi:10.1145/200836.200853 · Cited by 550 · see citing works
Some approaches to best-match file searching
Burkhard, W. A., & Keller, R. (1973) · Communications of the ACM · doi:10.1145/362003.362025 · Cited by 415 · see citing works
The design and analysis of spatial data structures
Egenhofer, M. J. (1991) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/0924-2716(91)90007-i · Cited by 368 · see citing works
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258653 · Cited by 347 · see citing works
Distance-based indexing for high-dimensional metric spaces
Bozkaya, T., & Özsoyoğlu, M. (1997) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/253260.253345 · Cited by 334 · see citing works
New Retrieval Approaches Using SMART: TREC 4.
Buckley, C., Singhal, A., Mitra, M., & Salton, G. (1995) · Cited by 319 · see citing works
Approximate nearest neighbor queries in fixed dimensions
Arya, S., & Mount, D. M. (1993) · doi:10.5555/313559.313768 · Cited by 314 · see citing works
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Frankl, P., & Maehara, H. (1988) · Journal of Combinatorial Theory Series B · doi:10.1016/0095-8956(88)90043-3 · Cited by 310 · see citing works
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Z., Ostrovsky, R., & Rabani, Y. (1998) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/276698.276877 · Cited by 261 · see citing works
Multidimensional Searching Problems
Dobkin, D., & Lipton, R. J. (1976) · SIAM Journal on Computing · doi:10.1137/0205015 · Cited by 250 · see citing works
A Randomized Algorithm for Closest-Point Queries
Clarkson, K. L. (1988) · SIAM Journal on Computing · doi:10.1137/0217052 · Cited by 249 · see citing works
Reporting points in halfspaces
Matous̆ek, J. (1992) · Computational Geometry · doi:10.1016/0925-7721(92)90006-e · Cited by 236 · see citing works
Ray Shooting and Parametric Search
Agarwal, P. K., & Matoušek, J. (1993) · SIAM Journal on Computing · doi:10.1137/0222051 · Cited by 173 · see citing works
Nearest Neighbor Queries in Metric Spaces
Clarkson, K. L. (1999) · Discrete & Computational Geometry · doi:10.1007/pl00009449 · Cited by 169 · see citing works
Point Location in Arrangements of Hyperplanes
Meiser, S. (1993) · Information and Computation · doi:10.1006/inco.1993.1057 · Cited by 156 · see citing works
A general approach to d-dimensional geometric queries
Yao, A. C.-C., & Yao, F. F. (1985) · doi:10.1145/22145.22163 · Cited by 144 · see citing works
An algorithm for approximate closest-point queries
Clarkson, K. L. (1994) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/177424.177609 · Cited by 133 · see citing works
FLASH: a fast look-up algorithm for string homology.
Califano, A., & Rigoutsos, I. (1993) · PubMed · Cited by 106 · see citing works
Multi-index hashing for information retrieval
Greene, D., Parnas, M., & Yao, F. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365720 · Cited by 97 · see citing works
Approximate closest-point queries in high dimensions
Bern, M. W. (1993) · Information Processing Letters · doi:10.1016/0020-0190(93)90222-u · Cited by 83 · see citing works
8 Nearest neighbor methods in discrimination
Devroye, L., & Wagner, T. J. (1982) · Handbook of statistics · doi:10.1016/s0169-7161(82)02011-2 · Cited by 82 · see citing works
Approximate Nearest Neighbor Queries Revisited
Chan, T. M. (1998) · Discrete & Computational Geometry · doi:10.1007/pl00009390 · Cited by 80 · see citing works
Geometric matching under noise: combinatorial bounds and algorithms
Indyk, P., Motwani, R., & Venkatasubramanian, S. (1999) · Cited by 67 · see citing works
Self-citationNearest neighbor queries in metric spaces
Clarkson, K. L. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258655 · Cited by 59 · see citing works
Embedding l ${}_{p}^{m}$ into l ${}_{1}^{n}$
Johnson, W. B., & Schechtman, G. (1982) · Acta Mathematica · doi:10.1007/bf02392350 · Cited by 57 · see citing works
Accounting for boundary effects in nearest neighbor searching
Arya, S., Mount, D. M., & Narayan, O. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220315 · Cited by 43 · see citing works
Fast hierarchical clustering and other applications of dynamic closest pairsPreprint
Eppstein, D. (1998) · doi:10.5555/314613.315030 · Cited by 39 · see citing works
Subquadratic approximation algorithms for clustering problems in high dimensional spaces
Borodin, A., Ostrovsky, R., & Rabani, Y. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301367 · Cited by 38 · see citing works
Multidimensional Access Methods: Trees Have Grown Everywhere
Sellis, T., Roussopoulos, N., & Faloutsos, C. (1997) · Very Large Data Bases · Cited by 36 · see citing works
Approximate nearest neighbor queries revisited
Chan, T. M. (1997) · doi:10.1145/262839.263001 · Cited by 33 · see citing works
Finding the neighborhood of a query in a dictionary
Dolev, D., Harari, Y., & Parnas, M. (2002) · doi:10.1109/istcs.1993.253486 · Cited by 20 · see citing works
The bit vector intersection problem
Karp, R. M., Waarts, O., & Zweig, G. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492663 · Cited by 19 · see citing works
Neighborhood preserving hashing and approximate queries
Dolev, D., Harari, Y. N., Linial, N., Nisan, N., & Parnas, M. (1994) · Symposium on Discrete Algorithms · doi:10.5555/314464.314501 · Cited by 18 · see citing works
Paturi, R., Rajasekaran, S., & Reif, J. H. (1995) · Information and Computation · doi:10.1006/inco.1995.1038 · Cited by 17 · see citing works
Neighborhood Preserving Hashing and Approximate Queries
Dolev, D., Harari, Y., Linial, N., Nisan, N., & Parnas, M. (2001) · SIAM Journal on Discrete Mathematics · doi:10.1137/s089548019731809x · Cited by 13 · see citing works
Static Dictionaries on RAMs: Query Time is Necessary and Sufficient
Andersson, A. (1996) · Cited by 13 · see citing works
A Case Study of Latent Semantic Indexing
Berry, M. W., & Shippy, A. T. (1995) · Cited by 9 · see citing works
Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering
Cazals, F. (1998) · doi:10.1145/276884.276910 · Cited by 4 · see citing works
Flagged first, then by citations
2 of the 76 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., & Saul, L. K. (2009) · Journal of Machine Learning Research · doi:10.5555/1577069.1577078 · Cited by 4,651 · see citing works
Halko, N., Martinsson, P., & Tropp, J. A. (2011) · SIAM Review · doi:10.1137/090771806 · Cited by 4,038 · see citing works
Scalable Recognition with a Vocabulary Tree
Nistér, D., & Stewénius, H. (2006) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2006.264 · Cited by 3,599 · see citing works
RRT-connect: An efficient approach to single-query path planning
Kuffner, J. J., & LaValle, S. M. (2000) · Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065) · doi:10.1109/robot.2000.844730 · Cited by 3,555 · see citing works
Mash: fast genome and metagenome distance estimation using MinHash
(2016) · Genome biology · doi:10.1186/s13059-016-0997-x · Cited by 3,373 · see citing works
Randomized Kinodynamic Planning
LaValle, S. M., & Kuffner, J. J. (2001) · The International Journal of Robotics Research · doi:10.1177/02783640122067453 · Cited by 3,254 · see citing works
(1999) · Cited by 3,186 · see citing works
Self-citationLocality-sensitive hashing scheme based on p-stable distributions
Datar, M., Immorlica, N., Indyk, P., & Mirrokni, V. (2004) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/997817.997857 · Cited by 2,971 · see citing works
Self-citationSchubert, E., Sander, J., Ester, M., Kriegel, H., & Xu, X. (2017) · ACM Transactions on Database Systems · doi:10.1145/3068335 · Cited by 2,789 · see citing works
ProtTrans: Toward Understanding the Language of Life Through Self-Supervised Learning
Elnaggar, A., Heinzinger, M., Dallago, C., Rehawi, G., Wang, Y., Jones, L., Gibbs, T., Feher, T., Angerer, C., Steinegger, M., et al. (2022) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3095381 · Cited by 2,329 · see citing works
A Simple Proof of the Restricted Isometry Property for Random Matrices
Baraniuk, R. G., Davenport, M. A., DeVore, R., & Wakin, M. B. (2008) · Constructive Approximation · doi:10.1007/s00365-007-9003-x · Cited by 2,310 · see citing works
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,290 · see citing works
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,287 · see citing works
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509965 · Cited by 2,263 · see citing works
Accelerating t-SNE using tree-based algorithms
van der Maaten, L. (2014) · Journal of machine learning research · doi:10.5555/2627435.2697068 · Cited by 2,207 · see citing works
Malkov, Y. A., & Yashunin, D. A. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2018.2889473 · Cited by 1,904 · see citing works
Distance Metric Learning for Large Margin Nearest Neighbor Classification
Weinberger, K. Q., Blitzer, J. C., & Saul, L. K. (2005) · Cited by 1,693 · see citing works
Google news personalization: scalable online collaborative filtering
Das, A., Datar, M., Garg, A., & Rajaram, S. (2007) · The Web Conference · doi:10.1145/1242572.1242610 · Cited by 1,833 · see citing works
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
Andoni, A., & Indyk, P. (2008) · Communications of the ACM · doi:10.1145/1327452.1327494 · Cited by 1,437 · see citing works
Self-citationDatabase-friendly random projections: Johnson-Lindenstrauss with binary coins
Achlioptas, D. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00025-4 · Cited by 1,374 · see citing works
Random projection in dimensionality reduction
Bingham, E., & Mannila, H. (2001) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/502512.502546 · Cited by 1,273 · see citing works
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions
Andoni, A., & Indyk, P. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.49 · Cited by 1,067 · see citing works
Self-citationWang, J., Zhang, T., Song, J., Sebe, N., & Shen, H. T. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2699960 · Cited by 1,034 · see citing works
k-Nearest Neighbour Classifiers - A Tutorial
Cunningham, P., & Delany, S. J. (2021) · ACM Computing Surveys · doi:10.1145/3459665 · Cited by 1,033 · see citing works
Funkhouser, T. A., Min, P., Kazhdan, M. M., Chen, J., Halderman, A., Dobkin, D., & Jacobs, D. W. (2003) · ACM Transactions on Graphics · doi:10.1145/588272.588279 · Cited by 934 · see citing works
Assembling large genomes with single-molecule sequencing and locality-sensitive hashing
Berlin, K., Koren, S., Chin, C.-S., Drake, J. P., Landolin, J. M., & Phillippy, A. M. (2015) · Nature Biotechnology · doi:10.1038/nbt.3238 · Cited by 928 · see citing works
An elementary proof of a theorem of Johnson and Lindenstrauss
Dasgupta, S., & Gupta, A. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10073 · Cited by 927 · see citing works
Recognizing Objects in Range Data Using Regional Point Descriptors
Frome, A., Huber, D., Kolluri, R. K., Bülow, T., & Malik, J. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24672-5_18 · Cited by 907 · see citing works
Kernelized locality-sensitive hashing for scalable image search
Kulis, B., & Grauman, K. L. (2009) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2009.5459466 · Cited by 905 · see citing works
A survey of content based 3D shape retrieval methods
Tangelder, J. W. H., & Veltkamp, R. C. (2007) · Multimedia Tools and Applications · doi:10.1007/s11042-007-0181-0 · Cited by 902 · see citing works
Sketching as a Tool for Numerical Linear Algebra
Woodruff, D. P. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000060 · Cited by 894 · see citing works
A survey on unsupervised outlier detection in high‐dimensional numerical data
Zimek, A., Schubert, E., & Kriegel, H. (2012) · Statistical Analysis and Data Mining The ASA Data Science Journal · doi:10.1002/sam.11161 · Cited by 864 · see citing works
PatternHunter: faster and more sensitive homology search
Ma, B., Tromp, J., & Li, M. (2002) · Bioinformatics · doi:10.1093/bioinformatics/18.3.440 · Cited by 819 · see citing works
Learning to Hash with Binary Reconstructive Embeddings
Kulis, B., & Darrell, T. (2009) · Cited by 806 · see citing works
Semi-Supervised Hashing for Large-Scale Search
Wang, J., Kumar, S., & Chang, S. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.48 · Cited by 805 · see citing works
Deep neural network based malware detection using two dimensional binary program features
Saxe, J., & Berlin, K. (2015) · International Conference on Malicious and Unwanted Software · doi:10.1109/malware.2015.7413680 · Cited by 781 · see citing works
SIFT Meets CNN: A Decade Survey of Instance Retrieval
Zheng, L., Yang, Y., & Tian, Q. (2017) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2017.2709749 · Cited by 758 · see citing works
Database-friendly random projections
Achlioptas, D. (2001) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/375551.375608 · Cited by 712 · see citing works
A Multi-View Deep Learning Approach for Cross Domain User Modeling in Recommendation Systems
Elkahky, A. M., Song, Y., & He, X. (2015) · International World Wide Web Conference (WWW) · doi:10.1145/2736277.2741667 · Cited by 709 · see citing works
Using the triangle inequality to accelerate k-means
Elkan, C. (2003) · Cited by 705 · see citing works
Kulis, B. (2013) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000019 · Cited by 697 · see citing works
Minimal Loss Hashing for Compact Binary Codes
Norouzi, M., & Blei, D. M. (2011) · Cited by 695 · see citing works
Randomized kinodynamic planning
LaValle, S. M., & Kuffner, J. (2003) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1999.770022 · Cited by 677 · see citing works
Scaling up all pairs similarity search
Bayardo, R. J., Ma, Y., & Srikant, R. (2007) · International World Wide Web Conference (WWW) · doi:10.1145/1242572.1242591 · Cited by 672 · see citing works
Improved Approximation Algorithms for Large Matrices via Random Projections
Sarlós, T. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.37 · Cited by 670 · see citing works
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality
Har-Peled, S., Indyk, P., & Motwani, R. (2012) · Theory of Computing · doi:10.4086/toc.2012.v008a014 · Cited by 666 · see citing works
Self-citationRobust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors
Jacques, L., Laska, J. N., Boufounos, P. T., & Baraniuk, R. G. (2013) · IEEE Transactions on Information Theory · doi:10.1109/tit.2012.2234823 · Cited by 646 · see citing works
Gibert, D., Mateu, C., & Planes, J. (2020) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2019.102526 · Cited by 646 · see citing works
Feature Learning based Deep Supervised Hashing with Pairwise LabelsPreprint
Li, W.-J., Wang, S., & Kang, W.-C. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.03855 · Cited by 643 · see citing works
A Survey on Malware Detection Using Data Mining Techniques
Ye, Y., Li, T., Adjeroh, D., & Iyengar, S. S. (2017) · ACM Computing Surveys · doi:10.1145/3073559 · Cited by 638 · see citing works
Multi-probe LSH: efficient indexing for high-dimensional similarity search
Lv, Q., Josephson, W. K., Wang, Z., Charikar, M., & Li, K. (2007) · Very Large Data Bases · Cited by 634 · see citing works
Shape Completion Using 3D-Encoder-Predictor CNNs and Shape Synthesis
Dai, A., Qi, C. R., & NieBner, M. (2017) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2017.693 · Cited by 633 · see citing works
Very sparse random projections
Li, P., Hastie, T. J., & Church, K. (2006) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/1150402.1150436 · Cited by 632 · see citing works
GMS: Grid-Based Motion Statistics for Fast, Ultra-Robust Feature Correspondence
Bian, J.-W., Lin, W.-Y., Matsushita, Y., Yeung, S.-K., Nguyen, T.-D., & Cheng, M. (2017) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2017.302 · Cited by 621 · see citing works
Scalable, behavior-based malware clustering
Bayer, U. (2009) · Cited by 605 · see citing works
Streaming First Story Detection with application to Twitter
Petrović, S., Osborne, M., & Lavrenko, V. P. (2010) · Cited by 578 · see citing works
Hamming Distance Metric Learning
Norouzi, M., Fleet, D. J., & Salakhutdinov, R. (2012) · Cited by 562 · see citing works
Liu, K., Kargupta, H., & Ryan, J. (2006) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2006.14 · Cited by 555 · see citing works
Toward Efficient Multi-Keyword Fuzzy Search Over Encrypted Outsourced Data With Accuracy Improvement
Fu, Z.-J., Wu, X., Guan, C., Sun, X.-M., & Ren, K. (2016) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2016.2596138 · Cited by 542 · see citing works
Vempala, S. (2005) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/065 · Cited by 541 · see citing works
Billinghurst, M., Clark, A., & Lee, G. (2015) · now publishers, Inc. eBooks · doi:10.1561/9781601989215 · Cited by 536 · see citing works
Finding generalized projected clusters in high dimensional spaces
Aggarwal, C. C., & Yu, P. S. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335383 · Cited by 536 · see citing works
Randomized Algorithms for Matrices and Data
Mahoney, M. W. (2012) · Chapman & Hall/CRC data mining and knowledge discovery series · doi:10.1201/b11822-37 · Cited by 535 · see citing works
Learning to Hash for Indexing Big Data—A Survey
Wang, J., Liu, W., Kumar, S., & Chang, S. (2015) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2487976 · Cited by 524 · see citing works
A learning theory approach to non-interactive database privacy
Blum, A. L., Ligett, K., & Roth, A. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374464 · Cited by 514 · see citing works
Ciufo, S. A., Kannan, S., Sharma, S., Badretdin, A. J., Clark, K., Turner, S. D., Brover, S., Schoch, C. L., Kimchi, A., & DiCuccio, M. N. (2018) · INTERNATIONAL JOURNAL OF SYSTEMATIC AND EVOLUTIONARY MICROBIOLOGY · doi:10.1099/ijsem.0.002809 · Cited by 513 · see citing works
Kulis, B. (2013) · now publishers, Inc. eBooks · doi:10.1561/9781601986979 · Cited by 509 · see citing works
Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., & Lin, X. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2909204 · Cited by 501 · see citing works
Latent semantic sparse hashing for cross-modal similarity search
Zhou, J., Ding, G., & Guo, Y. (2014) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2600428.2609610 · Cited by 485 · see citing works
A category-free neural population supports evolving demands during decision-making
Raposo, D. C., Kaufman, M. T., & Churchland, A. K. (2014) · Nature Neuroscience · doi:10.1038/nn.3865 · Cited by 474 · see citing works
The Fast Johnson–Lindenstrauss Transform and Approximate Nearest Neighbors
Ailon, N., & Chazelle, B. (2009) · SIAM Journal on Computing · doi:10.1137/060673096 · Cited by 473 · see citing works
Robust and efficient fuzzy match for online data cleaning
Chaudhuri, S., Ganjam, K., Ganti, V., & Motwani, R. (2003) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/872757.872796 · Cited by 466 · see citing works
Self-citationData fusion through cross-modality metric learning using similarity-sensitive hashing
Bronstein, M. M., Bronstein, A. M., Michel, F., & Nikos Paragios, A. (2010) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2010.5539928 · Cited by 461 · see citing works
Efficient shape matching using shape contexts
Mori, G., Belongie, S., & Malik, J. (2005) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2005.220 · Cited by 460 · see citing works
Hashing for Similarity Search: A SurveyPreprint
Wang, J., Shen, H. T., Song, J., & Ji, J. (2014) · arXiv (Cornell University) · doi:10.4230/lipics.cpm.2023.20 · Cited by 458 · see citing works
Efficient similarity joins for near duplicate detection
Xiao, C., Wang, W., Lin, X., & Yu, J. X. (2008) · International World Wide Web Conference (WWW) · doi:10.1145/1367497.1367516 · Cited by 454 · see citing works
A deep Recurrent Neural Network based approach for Internet of Things malware threat hunting
HaddadPajouh, H., Dehghantanha, A., Khayami, R., & Choo, K. R. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2018.03.007 · Cited by 450 · see citing works
VisualRank: Applying PageRank to Large-Scale Image Search
Jing, Y., & Baluja, S. (2008) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.121 · Cited by 436 · see citing works
Malware Analysis and Classification: A Survey
Gandotra, E., Bansal, D., & Sofat, S. (2014) · Journal of Information Security · doi:10.4236/jis.2014.52006 · Cited by 424 · see citing works
Approximate nearest neighbor algorithm based on navigable small world graphs
Malkov, Y. A., Ponomarenko, A., Logvinov, A., & Krylov, V. (2013) · Information Systems · doi:10.1016/j.is.2013.10.006 · Cited by 418 · see citing works
A survey of content based 3D shape retrieval methods
Tangelder, J. W. H., & Veltkamp, R. C. (2004) · IEEE International Conference on Shape Modeling and Applications · doi:10.1109/smi.2004.1314502 · Cited by 414 · see citing works
Mean shift based clustering in high dimensions: a texture classification example
Georgescu, Shimshoni, I., & Meer (2003) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2003.1238382 · Cited by 413 · see citing works
ProtTrans: Towards Cracking the Language of Life’s Code Through Self-Supervised LearningPreprint
Elnaggar, A., Heinzinger, M., Dallago, C., Rehawi, G., Wang, Y., Jones, L., Gibbs, T., Feher, T., Angerer, C., Steinegger, M., et al. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.07.12.199554 · Cited by 409 · see citing works
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Indyk, P. (2006) · Journal of the ACM · doi:10.1145/1147954.1147955 · Cited by 405 · see citing works
Self-citationOptimized Product Quantization
Ge, T., He, K., Ke, Q., & Sun, J. Z. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.240 · Cited by 398 · see citing works
Privacy-preserving multi-keyword fuzzy search over encrypted data in the cloud
Wang, B., Yu, S., Lou, W., & Hou, Y. (2014) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2014.6848153 · Cited by 396 · see citing works
K-Means Hashing: An Affinity-Preserving Quantization Method for Learning Binary Compact Codes
He, K., Wen, F., & Sun, J. (2013) · 2013 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2013.378 · Cited by 395 · see citing works
Multi-dimensional range queries in sensor networks
Li, X., Kim, Y. J., Govindan, R., & Hong, W. (2003) · ACM Conference on Embedded Networked Sensor Systems (SenSys) · doi:10.1145/958491.958500 · Cited by 390 · see citing works
Ambient Sound Provides Supervision for Visual Learning
Owens, A., Wu, J., McDermott, J. H., Freeman, W. T., & Torralba, A. B. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-46448-0_48 · Cited by 385 · see citing works
An Investigation of Practical Approximate Nearest Neighbor Algorithms
Liu, T., Moore, A., Yang, K., & Gray, A. (2004) · Cited by 375 · see citing works
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Ailon, N., & Chazelle, B. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132597 · Cited by 373 · see citing works
Heo, J., Lee, Y., He, J., Chang, S., & Yoon, S. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248024 · Cited by 373 · see citing works
Utility-Privacy Tradeoffs in Databases: An Information-Theoretic Approach
Sankar, L., Rajagopalan, S. R., & Poor, H. V. (2013) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2013.2253320 · Cited by 371 · see citing works
Adversarial Examples Detection in Deep Networks with Convolutional Filter Statistics
Li, X., & Li, F. (2017) · IEEE/CVF International Conference on Computer Vision (ICCV) · doi:10.1109/iccv.2017.615 · Cited by 368 · see citing works
How much can behavioral targeting help online advertising?
Yan, J. H., Liu, N., Wang, G., Zhang, W., Jiang, Y., & Chen, Z. (2009) · International World Wide Web Conference (WWW) · doi:10.1145/1526709.1526745 · Cited by 367 · see citing works
Efficient similarity search and classification via rank aggregation
Fagin, R., Kumar, R., & Sivakumar, D. (2003) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/872757.872795 · Cited by 365 · see citing works
An efficient parts-based near-duplicate and sub-image retrieval system
Ke, Y., Sukthankar, R., & Huston, L. (2004) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/1027527.1027729 · Cited by 364 · see citing works
Sparse, Dense, and Attentional Representations for Text Retrieval
Luan, Y., Eisenstein, J., Toutanova, K., & Collins, M. (2021) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00369 · Cited by 363 · see citing works
Yu, W., Cheng, W. D., Aggarwal, C. C., Zhang, K., Chen, H., & Wang, W. W. (2018) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3219819.3220024 · Cited by 353 · see citing works
Bawa, M., Condie, T., & Ganesan, P. (2005) · International World Wide Web Conference (WWW) · doi:10.1145/1060745.1060840 · Cited by 353 · see citing works
- Authors
- Indyk, P., & Motwani, R.
- Affiliations
- Stanford University (US)
- ORCID
- Indyk, Piotr
- Venue
- Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98
- Publisher
- ACM Press
- Published
- 1998
- Pages
- 604-613
- OpenAlex
- W2147717514
- Cited by
- 4,188
- References
- 76
- Citations by year
- 2026: 152 · 2025: 162 · 2024: 164 · 2023: 133 · 2022: 160 · 2021: 223 · 2020: 245 · 2019: 250 · 2018: 249 · 2017: 251 · 2016: 277 · 2015: 280 · 2014: 260 · 2013: 224 · 2012: 208
- FWCI
- 23.46
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- ACM Symposium on Theory of Computing (STOC) (publishedVersion)
- Funders
- National Science Foundation
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Computer Graphics and Computer-Aided Design › Computational Geometry and Mesh Generation
- Physical Sciences › Computer Science › Signal Processing › Data Management and Algorithms
- Keywords
- approximate nearest neighbor search, curse of dimensionality, nearest neighbor search, metric spaces, metric embeddings, randomized algorithms
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
