Nothing Special   »   [go: up one dir, main page]

skip to main content
10.5555/338219.338582acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article
Free access

Dimensionality reduction techniques for proximity problems

Published: 01 February 2000 Publication History
First page of PDF

References

[1]
S. Arya, D.M. Mount, N.S. Netanyahu, R. Silverman, and A. Wu, "An optimal algorithm for approximate nearest neighbor searching", SODA'94, pp. 573-582.
[2]
A. Borodin, P~. Ostrovsky and Y. Rabani "Subquadratic Approximation Algorithms For clustering Problems in High Dimensional Spaces", STOC'99, to appear.
[3]
K. Clarkson. "A randomized algorithm for closestpoint queries", SIAM Journal on Computing, 17(1988), pp. 830-847.
[4]
E. Cohen, D. Lewis, "Approximating matrix multiplication for pattern recognition tasks", SODA'97, pp. 682-691.
[5]
A. Gionis, P. Indyk and R. Motwani, "Approximate similarity search in high dimensions via hashing", VLDB'99, to appear.
[6]
P. Indyk, "On Approximate Nearest Neighbors in Non- Euclidean Spaces", FOCS'98, pp. 148-155.
[7]
P. Indyk, R. Motwani, "Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality", STOC'98, pp. 604-613.
[8]
P. Indyk, R. Motwani, P. Raghavan, S. Vempala, "Locality-preserving hashing in multidimensional spaces", STOC'97, pp. 618-625.
[9]
W.B. Johnson and J. Lindenstrauss, "Extensions of Lipshitz mapping into Hilbert space", Contemporary Mathematics, 26(1984), pp. 189-206.
[10]
J. Kleinberg, "Two Algorithms for Nearest Neighbor Search in High Dimensions", STOC'97, pp. 599-608.
[11]
E. Kushilevitz, R. Ostrovsky, and Y. Rabani, " Efficient search for approximate nearest neighbor in high dimensional spaces", STOC'98, pp. 614-623.
[12]
S. Meiser. "Point location in arrangements of hyperplanes", Information and Computation, 106(1993):286-30s.
[13]
K. Mulmuley, "Computational geometry", Prentice Hall, 1993.
[14]
3. Naor and M. Naor, "Small-bias probability spaces: efficient constructions and applications", SIAM Journal on Computing, vol.22, no.4, pp. 838-856.
[15]
Rina Panigrahy, personal communication. See also S. Vishwanathan, SODA'96.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SODA '00: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms
February 2000
965 pages
ISBN:0898714532

Sponsors

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 2000

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)46
  • Downloads (Last 6 weeks)4
Reflects downloads up to 12 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2019)Optimal las vegas approximate near neighbors in lProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310543(1794-1813)Online publication date: 6-Jan-2019
  • (2018)Hardness of approximate nearest neighbor searchProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188916(1260-1268)Online publication date: 20-Jun-2018
  • (2018)CoveringLSHACM Transactions on Algorithms10.1145/315530014:3(1-17)Online publication date: 16-Jun-2018
  • (2017)Optimal hashing-based time-space trade-offs for approximate near neighborsProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039690(47-66)Online publication date: 16-Jan-2017
  • (2010)Almost-Euclidean subspaces of l1Nvia tensor productsProceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques10.5555/1886521.1886570(632-641)Online publication date: 1-Sep-2010
  • (2010)Faster dimension reductionCommunications of the ACM10.1145/1646353.164637953:2(97-104)Online publication date: 1-Feb-2010
  • (2008)Tighter bounds for random projections of manifoldsProceedings of the twenty-fourth annual symposium on Computational geometry10.1145/1377676.1377685(39-48)Online publication date: 9-Jun-2008
  • (2007)Uncertainty principles, extractors, and explicit embeddings of l2 into l1Proceedings of the thirty-ninth annual ACM symposium on Theory of computing10.1145/1250790.1250881(615-620)Online publication date: 11-Jun-2007
  • (2006)Stable distributions, pseudorandom generators, embeddings, and data stream computationJournal of the ACM10.1145/1147954.114795553:3(307-323)Online publication date: 1-May-2006
  • (2006)Approximate nearest neighbors and the fast Johnson-Lindenstrauss transformProceedings of the thirty-eighth annual ACM symposium on Theory of Computing10.1145/1132516.1132597(557-563)Online publication date: 21-May-2006
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media