Vision and Around

Dedicated to my research and life

Subspace Search

Efficient query of high-dimensional structures with points/high-dimensional structures. (Update: Nov 30 2015)


#. [Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search](
  1. Optimal Data-Dependent Hashing for Approximate Near Neighbors


  1. Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS)
  2. Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)
  3. Approximate k-flat Nearest Neighbor Search
  4. Approximate Nearest Line Search in High Dimensions


  1. Beyond Locality-Sensitive Hashing
  2. Fast Subspace Search via Grassmannian Based Hashing


  1. Near-optimal hashing algorithms for approximate nearest neighbor in high dimension (Simplified Journal Version in 2012)
  2. Efficient point-to-subspace query in \(\ell^1\) with applications to robust face recognition (ECCV)

Before 2012

  1. Dimensionality reductions in \(\ell^2\) that preserve volumes and distance to affine spaces (DCG 2007)
  2. Approximate nearest subspace search (PAMI 2011)
  3. Hashing hyperplane queries to near points with applications to large-scale active learning (NIPS 2011)
  4. Subspace embeddings for the \(\ell^1\)-norm with applications (STOC 2011)
  5. Dimension reduction in \(\ell^1\) (from TCS math - a wordpress blog by Prof. James R. Lee)
  6. Approximate line nearest neighbor in high dimensions
  7. List of open problems on embeddings of finite metric spaces (by Prof. Jiri Matousek)
  8. Lecture notes on metric embedding (by Prof. Jiri Matousek)

Disclaimer - This page is meant to serve a hub for references on this problem, and does not represent in any way personal endorsement of papers listed here. So I do not hold any responsibility for quality and technical correctness of each paper listed here. The reader is advised to use this resource with discretion.

If you’d like your paper to be listed here - Just drop me a few lines via email (which can be found on “Welcome” page). If you don’t bother to spend a word, just deposit your paper on arXiv. I get email alert about new animals there every morning,  and will be happy to hunt one for this zoo if it seems fit.