publication . Conference object . Preprint . 2014

Spectral Approaches to Nearest Neighbor Search

Abdullah, Amirali; Andoni, Alexandr; Kannan, Ravindran; Krauthgamer, Robert;
Open Access
  • Published: 04 Aug 2014
  • Publisher: IEEE
Comment: Accepted in the proceedings of FOCS 2014. 30 pages and 4 figures
free text keywords: Pattern recognition, Data structure, Gaussian noise, symbols.namesake, symbols, Subspace topology, Computer science, Computation, Best bin first, Algorithm design, Nearest neighbor search, Principal component analysis, Artificial intelligence, business.industry, business, Computer Science - Data Structures and Algorithms
Related Organizations
Funded by
NSF| CAREER: Geometric Algorithms For Data Analysis In Spaces Of Distributions
  • Funder: National Science Foundation (NSF)
  • Project Code: 0953066
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

M. Rudelson and R. Vershynin. Non-asymptotic theory of random matrices: extreme singular values. In Proceedings of the International Congress of Mathematicians. Volume III, pages 1576-1602, New Delhi, 2010. Hindustan Book Agency. arXiv:1003.2990. [OpenAIRE]

C. Silpa-Anan and R. Hartley. Optimised kd-trees for fast image descriptor matching. In Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, pages 1-8. IEEE, 2008.

R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 50(7):969-978, 2009.

R. Sproull. Refinements to nearest-neighbor searching in k-dimensional trees. Algorithmica, 6:579-589, 1991. doi:10.1007/BF01759061.

D. A. Spielman and S.-H. Teng. Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Commun. ACM, 52(10):76-84, October 2009. doi:10.1145/1562764.1562785.

G. W. Stewart. On the early history of the singular value decomposition. SIAM review, 35(4):551-566, 1993.

N. Verma, S. Kpotufe, and S. Dasgupta. Which spatial partition trees are adaptive to intrinsic dimension? In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 565-574.

AUAI Press, 2009.

K. R. Varadarajan, S. Venkatesh, and J. Zhang. On approximating the radii of point sets in high dimensions. In 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 561-569. IEEE, 2002. doi:10.1109/SFCS.2002.1181980.

S. Vempala and G. Wang. A spectral algorithm for learning mixture models. Journal of Computer and System Sciences, 68(4):841-860, 2004. Previously in FOCS'02.

P.- A˚. Wedin. Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics, 12(1):99-111, 1972. doi:10.1007/BF01932678.

Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In Advances in neural information processing systems, pages 1753-1760, 2008. Available from: nips21/NIPS2008_0806.pdf.

[YSRL11] J. Yagnik, D. Strelow, D. A. Ross, and R.-S. Lin. The power of comparative reasoning. In Computer Vision (ICCV), 2011 IEEE International Conference on, pages 2431-2438. IEEE, 2011.

We will later need the following basic facts (see, e.g., [Ste93]). We denote the singular values of a matrix X 2 Rn d by s1(X) s2(X) : : : sd(X).

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue