The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Similarity estimation techniques from rounding algorithms
Abstract
A locality sensitive hashing scheme is a distribution on a family F of hash functions operating on a collection of objects, such that for two objects x, y, Prh∈F[h(x) = h(y)] = sim(x,y), where sim(x,y) ∈ [0, 1] is some similarity function defined on the collection of objects. Such a scheme leads to a compact representation of objects so that similarity of objects can be estimated from their compact sketches, and also leads to efficient algorithms for approximate nearest neighbor search and clustering. Min-wise independent permutations provide an elegant construction of such a locality sensitive hashing scheme for a collection of subsets with the set similarity measure sim(A, B) = |A∩B| |A∪B |. We show that rounding algorithms for LPs and SDPs used in the context of approximation algorithms can be viewed as locality sensitive hashing schemes for several interesting collections of objects. Based on this insight, we construct new locality sensitive hashing schemes for: 1. A collection of vectors with the distance between ⃗u and ⃗v measured by θ(⃗u,⃗v)/π, where θ(⃗u,⃗v) is the angle between ⃗u and ⃗v. This yields a sketching scheme for estimating the cosine similarity measure between two vectors, as well as a simple alternative to minwise independent permutations for estimating set similarity. 2. A collection of distributions on n points in a metric space, with distance between distributions measured by the Earth Mover Distance (EMD), (a popular distance measure in graphics and vision). Our hash functions map distributions to points in the metric space such that, for distributions P and Q,
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Earth Mover's Distance as a Metric for Image Retrieval
Rubner, Y., Tomasi, C., & Guibas, L. J. (2000) · International Journal of Computer Vision · doi:10.1023/a:1026543900054 · Cited by 4,568
Approximate nearest neighbors: towards removing the curse of dimensionality
Indyk, P., & Motwani, R. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276876 · Cited by 4,188
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587
(1999) · Cited by 3,186
A metric for distributions with applications to image databases
Rubner, Y., Tomasi, C., & Guibas, L. J. (2002) · Sixth International Conference on Computer Vision (IEEE Cat. No.98CH36271) · doi:10.1109/iccv.1998.710701 · Cited by 1,726
On the resemblance and containment of documents
Broder, A. Z. (2002) · Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) · doi:10.1109/sequen.1997.666900 · Cited by 1,698
Syntactic clustering of the Web
Broder, A. Z., 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,343
The Space Complexity of Approximating the Frequency Moments
Alon, N., Matias, Y., & Szegedy, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1545 · Cited by 1,140
Min-Wise Independent Permutations
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1690 · Cited by 802
Self-citationProbabilistic approximation of metric spaces and its algorithmic applications
Bartal, Y. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548477 · Cited by 635
Guha, S., Mishra, N., Motwani, R., & O'Callaghan, L. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892124 · Cited by 623
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Indyk, P. (2006) · Journal of the ACM · doi:10.1145/1147954.1147955 · Cited by 402
Kleinberg, J., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/585265.585268 · Cited by 400
Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries
Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2001) · Cited by 376
Min-wise independent permutations (extended abstract)
Broder, A. Z., Charikar, M., Frieze, A. M., & Mitzenmacher, M. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276781 · Cited by 364
Self-citationPerceptual Metrics for Image Database Navigation
Rubner, Y., & Tomasi, C. (2001) · Springer eBooks · doi:10.1007/978-1-4757-3343-3 · Cited by 296
Fast, small-space algorithms for approximate histogram maintenance
Gilbert, A. C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., & Strauss, M. J. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509966 · Cited by 242
Stable distributions, pseudorandom generators, embeddings and data stream computation
Indyk, P. (2002) · Proceedings 41st Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2000.892082 · Cited by 238
Tracking join and self-join sizes in limited storage
Alon, N., Gibbons, P. B., Matias, Y., & Szegedy, M. (1999) · doi:10.1145/303976.303978 · Cited by 211
Synopsis data structures for massive data sets
Gibbons, P. B., & Matias, Y. (1999) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/050/02 · Cited by 189
Locality-preserving hashing in multidimensional spaces
Indyk, P., Motwani, R., Raghavan, P., & Vempala, S. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258656 · Cited by 167
Scalable Techniques for Clustering the Web.
Haveliwala, T. H., Gionis, A., & Indyk, P. (2000) · Cited by 148
Color edge detection with the compass operator
Ruzon, M. A., & Tomasi, C. (2003) · 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.1999.784624 · Cited by 148
Finding interesting associations without support pruning
Cohen, E., Datar, M., Fujiwara, S., Gionis, A., Indyk, P., Motwani, R., Ullman, J. D., & Yang, C. (2002) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2000.839448 · Cited by 118
Selectively estimation for Boolean queries
Chen, Z., Koudas, N., Korn, F. R., & Muthukrishnan, S. (2000) · doi:10.1145/335168.335225 · Cited by 59
Derandomized Dimensionality Reduction with Applications
Engebretsen, L., Indyk, P., & O’Donnell, R. (2001) · Cited by 53
The Earth Mover's Distance: Lower Bounds and Invariance Under Translation
Cohen, S. D., & Guibas, L. (1997) · doi:10.21236/ada358270 · Cited by 39
Efficient and tumble similar set retrieval
Gionis, A., Gunopulos, D., & Koudas, N. (2001) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/375663.375689 · Cited by 37
Cited by
From Frequency to Meaning: Vector Space Models of Semantics
Turney, P. D., & Pantel, P. (2010) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2934 · Cited by 2,866
Rajaraman, A., & Ullman, J. D. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9781139058452 · Cited by 2,262
Google news personalization: scalable online collaborative filtering
Das, A. S., Datar, M., Garg, A., & Rajaram, S. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242610 · Cited by 1,511
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
Efficient integration of heterogeneous single-cell transcriptomes using Scanorama
Hie, B., Bryson, B., & Berger, B. (2019) · Nature Biotechnology · doi:10.1038/s41587-019-0113-3 · Cited by 974
Metadata
- Authors
- Charikar, M. S.
- Venue
- Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
- Publisher
- ACM
- Published
- 2002-05-19
- Pages
- 380-388
- OpenAlex
- W2012833704
- Cited by
- 2,220
- References
- 28
- FWCI
- 3.82
- Type
- conference paper
- Language
- en
- Open access
- closed
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
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.