Approximate \(k\)-flat nearest neighbor search. (English) Zbl 1321.68416
Proceedings of the 47th annual ACM symposium on theory of computing, STOC ’15, Portland, OR, USA, June 14–17, 2015. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-3536-2). 783-792 (2015).
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68P05 | Data structures |
| 68W25 | Approximation algorithms |
Software:
GraphsReferences:
| [1] | A. Andoni. Nearest Neighbor Search: the Old, the New, and the Impossible. PhD thesis, MIT, 2009. |
| [2] | A. Andoni, P. Indyk, R. Krauthgamer, and H. L. Nguyen. Approximate line nearest neighbor in high dimensions. In Proc. 20th SODA, pages 293-301, 2009. · Zbl 1422.68282 |
| [3] | A. Andoni, P. Indyk, H. L. Nguyen, and I. Razenshteyn. Beyond locality-sensitive hashing. In Proc. 24th SODA, pages 1018-1028, 2014. · Zbl 1422.68042 |
| [4] | R. Basri, T. Hassner, and L. Zelnik-Manor. Approximate nearest subspace search with applications to pattern recognition. In Proc. CVPR, pages 1-8, 2007. |
| [5] | T. M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661-690, 2012. 10.1007/s00454-012-9410-z · Zbl 1242.68353 |
| [6] | B. Chazelle. The discrepancy method. Randomness and complexity. Cambridge University Press, 2000. · Zbl 0960.65149 |
| [7] | K. L. Clarkson. A randomized algorithm for closest-point queries. SICOMP, 17(4):830-847, 1988. 10.1137/0217052 · Zbl 0651.68062 |
| [8] | S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures Algorithms, 22(1):60-65, 2003. 10.1002/rsa.10073 · Zbl 1018.51010 |
| [9] | R. A. Horn and C. R. Johnson. Matrix analysis. Cambridge University Press, second edition, 2013. · Zbl 1267.15001 |
| [10] | P. Indyk. Nearest neighbors in high-dimensional spaces. In J. E. Goodman and J. O’Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 39. CRC Press, 2nd edition, 2004. |
| [11] | P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proc. 30th STOC, pages 604-613, 1998. 10.1145/276698.276876 · Zbl 1029.68541 |
| [12] | E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. In Proc. 30th STOC, pages 614-623, 1998. 10.1145/276698.276877 · Zbl 1029.68542 |
| [13] | Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe LSH: Efficient indexing for high-dimensional similarity search. In Proc. 33rd VLDB, pages 950-961, 2007. |
| [14] | A. Magen. Dimensionality reductions in l_2 that preserve volumes and distance to affine spaces. Discrete Comput. Geom., 38(1):139-153, 2007. 10.1007/s00454-007-1329-4 · Zbl 1130.46004 |
| [15] | S. Mahabadi. Approximate nearest line search in high dimensions. In Proc. 26th SODA, pages 337-354, 2015. · Zbl 1371.68295 |
| [16] | J. Matousek. Efficient partition trees. Discrete Comput. Geom., 8(3):315-334, 1992. · Zbl 0752.68088 |
| [17] | S. Meiser. Point location in arrangements of hyperplanes. Inform. and Comput., 106(2):286-303, 1993. 10.1006/inco.1993.1057 · Zbl 0781.68121 |
| [18] | R. Panigrahy. Entropy based nearest neighbor search in high dimensions. In Proc. 17th SODA, pages 1186-1195, 2006. · Zbl 1192.68217 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
