The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
Efficient similarity search and classification via rank aggregation
Abstract
We propose a novel approach to performing efficient similarity search and classification in high dimensional data. In this framework, the database elements are vectors in a Euclidean space. Given a query vector in the same space, the goal is to find elements of the database that are similar to the query. In our approach, a small number of independent "voters" rank the database elements based on similarity to the query. These rankings are then combined by a highly efficient aggregation algorithm. Our methodology leads both to techniques for computing approximate nearest neighbors and to a conceptually rich alternative to nearest neighbors.
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
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
(1999) · Cited by 3,186
When Is ''Nearest Neighbor'' Meaningful?
Beyer, K., Goldstein, J., Ramakrishnan, R., & Shaft, U. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-49257-7_15 · Cited by 2,403 · cited 4×
“For some recent theoretical work, see [18, 16, 19]; for recent theoretical/applied work, see [13, 1 , 12, 5, 4, 20].”
BackgroundMethodInfluentialSimilarity estimation techniques from rounding algorithms
Charikar, M. S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509965 · Cited by 2,220
Rank aggregation methods for the Web
Dwork, C., Kumar, R., Naor, M., & Sivakumar, D. (2001) · Proceedings of the 10th international conference on World Wide Web · doi:10.1145/371920.372165 · Cited by 1,793
Self-citationMathematics without Numbers: Towards a Modal-Structural Interpretation
Hellman, G. (1993) · doi:10.1093/0198240341.001.0001 · Cited by 1,158
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
Optimal aggregation algorithms for middleware
Fagin, R., Lotem, A., & Naor, M. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375567 · Cited by 1,086
Self-citationOptimal aggregation algorithms for middleware
Fagin, R., Lotem, A., & Naor, M. (2003) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(03)00026-6 · Cited by 942
Self-citationProceedings of the 27th International Conference on Very Large Data Bases
Apers, P. M. G., Atzeni, P., Ceri, S., Paraboschi, S., Ramamohanarao, K., & Snodgrass, R. T. (2001) · Cited by 845
Young, H. P. (1988) · American Political Science Review · doi:10.2307/1961757 · Cited by 746
Spearman's Footrule as a Measure of Disarray
Diaconis, P., & Graham, R. L. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01624.x · Cited by 640
Similarity indexing with the SS-tree
White, D. A., & Jain, R. (2002) · Proceedings of the Twelfth International Conference on Data Engineering · doi:10.1109/icde.1996.492202 · Cited by 635
The computational difficulty of manipulating an election
Bartholdi, J. J., Tovey, C. A., & Trick, M. A. (1989) · Social Choice and Welfare · doi:10.1007/bf00295861 · Cited by 529
Proceedings of the 32nd international conference on Very large data bases
Dayal, U., Whang, K.-Y., Lomet, D., Alonso, G., Lohman, G. M., Kersten, M. L., Sang, K., & Kim, Y. (2006) · Medical Entomology and Zoology · Cited by 479
A Consistent Extension of Condorcet’s Election Principle
Young, H. P., & Levenglick, A. (1978) · SIAM Journal on Applied Mathematics · doi:10.1137/0135023 · Cited by 455
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
Two algorithms for nearest-neighbor search in high dimensions
Kleinberg, J. M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258653 · Cited by 348
Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
Kushilevitz, E., Ostrovsky, R., & Rabani, Y. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798347177 · Cited by 245
Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches
Goldstein, J., & Ramakrishnan, R. (2000) · Very Large Data Bases · Cited by 47
Cited by
Scaling up all pairs similarity search
Bayardo, R. J., Ma, Y., & Srikant, R. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242591 · Cited by 673
Efficient similarity joins for near duplicate detection
Xiao, C., Wang, W., Lin, X., & Yu, J. X. (2008) · Proceedings of the 17th international conference on World Wide Web · doi:10.1145/1367497.1367516 · Cited by 455
Efficient similarity joins for near-duplicate detection
Xiao, C., Wang, W., Lin, X., Yu, J. X., & Wang, G. (2011) · ACM Transactions on Database Systems · doi:10.1145/2000824.2000825 · Cited by 331
Generalized distances between rankings
Kumar, R., & Vassilvitskii, S. (2010) · Proceedings of the 19th international conference on World wide web · doi:10.1145/1772690.1772749 · Cited by 273
Self-citation
Metadata
- Authors
- Fagin, R., Kumar, R., & Sivakumar, D.
- Venue
- Proceedings of the 2003 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2003-06-09
- Pages
- 301-312
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2142385580
- Cited by
- 362
- References
- 20
- FWCI
- 12.09
- 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.