Lower bounds for high dimensional nearest neighbor search and related problems. (English) Zbl 1346.68077
Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 312-321 (1999).
MSC:
| 68P10 | Searching and sorting |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | P.K. Agarwal and J. Matou ek. Ray shooting and parametric search. In Proc. of 2 lh STOC, pp. 517-526, I992. 10.1145/129712.129763 |
| [2] | M. Ajtai. A lower bound for finding predecessors in Yao’s cell probe model. Combinatorica, 8:235- 47, 1988. · Zbl 0659.68030 |
| [3] | S. Arya and D. Mount. Approximate nearest neighbor searching. In Proc. of gih SODA, pp. 271-280, 1993. · Zbl 0801.68161 |
| [4] | S. Arya, D. Mount, N. N etanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In Proc. of 5 h SODA, pp. 573-582, 1994. · Zbl 0871.68068 |
| [5] | P. Beame, M. Saks, and J.S. Thathachar. Timespace tradeoffs for branching programs. In Proc. of 39th FOCS, pp. 254-263, 1998. |
| [6] | J.S. Beis and D.G. Lowe. Shape indexing using approximate nearest-neighbor search in highdimensional spaces. In Proc. IEEE Conj. Comp. Vision Part. Recog., pages 1000-1006, 1997. |
| [7] | J.L. Bentley and R. Sedgewick. Fast algorithms for sorting and search strings. In Proc. of 8th SODA, pp. 360-369, 1997. · Zbl 1321.68549 |
| [8] | M. Ben-Or. Lower bounds for algebraic computation trees. In Prvc. of 15th STOC, pp. 80-86, 1983. 10.1145/800061.808735 |
| [9] | M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry, Algorithms and Applications. Springer, 1997. · Zbl 0939.68134 |
| [10] | M. Bern. Approximate closest-point queries in high dimensions. Information Processing Lett., 45:95-99, 1993. 10.1016/0020-0190(93)90222-U · Zbl 0795.68187 |
| [11] | A. Chakrabaxti, B. Chazelle, B. Gum, A. Lvov. A good neighbor is hard to find. These Proceedings. |
| [12] | T.M. Chan. Approximate nearest neighbor queries revisited. In Proc. of 13lh \(CG, pp. 352- 358, 1997. 10.1145/262839.26300\) |
| [13] | B. Chazelle. Private communication. |
| [14] | K. Claxkson. A randomized algorithm for closestpoint queries. SIAM J. Comput., 17:830-847, 1988. 10.1137/0217052 · Zbl 0651.68062 |
| [15] | K. Clarkson. An algorithm for approximate closest-point queries. In Proc. of l Oth SCG, pp. 160-164, 1994. 10.1145/177424.177609 |
| [16] | S. Deerwester, S.T. Dumais, G.W. Furnas, T.K. Landauer, and R. tIarshman. Indexing by latent semantic analysis. J. Amer. Soc. lnfo. \(ci., 41(6):391-407, 1990\) |
| [17] | D. Dobkin and R. Lipton. Multidimensional search problems. SIAM J. Comput., 5:181-186, 1976. · Zbl 0333.68031 |
| [18] | D. Dolev, Y. Harari, and M. Pumas. Finding’the neighborhood of a query in a dictionary. In Proc. of nd ISTC\(, 1993\) |
| [19] | D. Dolev, Y. Harari, N. Linial, N. Nisan, and M. Pumas. Neighborhood preserving hashing and approximate queries. In Proc. of 5th SODA, pp. 251-259, 1994. · Zbl 0873.68034 |
| [20] | J. Erickson. New lower bounds for Hopcroft’s problem. Discrete Comput. eom., 16:389-418, 1996. · Zbl 0857.68061 |
| [21] | P . Fagin. Fuzzy queries in multimedia database systems. In Proc. of PODS, 1998. 10.1145/275487.275488 |
| [22] | M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: the QBIC system. IEEE Computer, 28:23-32, 1995. 10.1109/2.410146 |
| [23] | M.L. Fredman. A lower bound on the complexity of orthogonal range queries. Journal of the A CM, 28:696-705, 1981 10.1145/322276.322281 · Zbl 0468.68049 |
| [24] | M.L. Fredman. Lower bounds on the complexity of some optimal data structures. SIAM J. Computing, I0:1-10, 198i · Zbl 0454.68006 |
| [25] | M.L. Fredman and D.J. Volper. The complexity of partial match retrieval in a dynamic setting. Journal of Algorithms, 3:68-78, 1982. · Zbl 0477.68112 |
| [26] | D. Grigoriev. Randomized complexity lower bounds. Proc. of 30th \(TOC, pp. 219-223, 1998. 10.1145/276698.27674\) · Zbl 1027.68608 |
| [27] | T. H astie and R. Tibshirani. Discriminant adaptive nearest neighbor classification. In Is! International Conf. on Knowledge Discovery and Data Mining, 1995. |
| [28] | J. Hellerstein, E. Koutsoupias, and C.H. Papadimitriou. On the analysis of indexing schemes. in Proc. of PODS, 1997. 10.1145/263661.263688 |
| [29] | P. Indyk. On approximate nearest neighbors in non-Euclidean spaces. In Proc. of 39th FOU\(, 1998. \) |
| [30] | P. Indyk and R. Motwani. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. of 30th \(TOC, 1998. 10.1145/276698.27687\) · Zbl 1029.68541 |
| [31] | J. Kleinberg. Two algorithms for nearestneighbor search in high dimensions. In Proc. of 29th \(TOC, pp. 599-608, 1997. 10.1145/258533.25865\) · Zbl 0963.68049 |
| [32] | E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. · Zbl 0869.68048 |
| [33] | E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate neares neighbor in high dimensional spaces. In Proc. of 30th \(TOC, 1998. 10.1145/276698.27687\) · Zbl 1029.68542 |
| [34] | J. Matou ek. Reporting points in halfspaces. In Proc. of 32nd FOCS, 1991. 10.1109/SFCS.1991.185370 |
| [35] | S. Meiser. Point location in arrangements of hyperplanes. Information and Computation, 106(2):286-303, 1993. 10.1006/inco.1993.1057 · Zbl 0781.68121 |
| [36] | P.B. Miltersen. The bit probe complexity measure revisited. In Pvoc. of l Oth STA C\(, pp. 662- 671, 1993\) · Zbl 0799.68048 |
| [37] | P.B. Miltersen. Lower bounds for union-split-find related problems on random access machines. In Proc. of of 6th \(TO~, pp. 625-634, 1994. 10.1145/195058.19541\) · Zbl 1345.68118 |
| [38] | P.B. Miltersen. On the cell probe complexity of polynomial evaluation. Theoretical Computer Science, 143:167-174, 1995. · Zbl 0873.68093 |
| [39] | P.B. Miltersen, N. Nisan, S. Safra, and A. Widgerson. On data structures and asymmetric communication complexity. In Prvc. of 7ih STOC, pp. 103-111, 1995. 10.1145/225058.225093 · Zbl 0968.68507 |
| [40] | A. Pentland, R.W. Picard, and S. Sclaroff. Photobook: tools for content-based manipulation of image databases. In Proc. \(PIE Conf. on Storage and Retrieval of Image and Video Databases lI, 1994\) |
| [41] | R. Rivest. Partial-match retrieval algorithms. SIAM J. Comput., 5:19-50, 1976. · Zbl 0331.68064 |
| [42] | G. Salton. Automatic Text Processing. Addison- Wesley, 1989. |
| [43] | A.W.M. Smeulders and R. Jain (eds). Proc. 1st Workshop on Image Databases and Multi-Media Search, 1996. |
| [44] | B. Xiao. New Bounds in Cell Probe Model. Ph.D. thesis, UC San Diego, 1992. |
| [45] | A.C. Yao. Should tables be sorted? J. Assoc. Comput. Much., 28:615-628, 1981. 10.1145/322261.322274 · Zbl 0462.68079 |
| [46] | A.C. Yao and F.F. Yao. A general approach to d-dimension geometric queries. In Proc. of 17th \(TOC, pp. 163-168, 1985. 10.1145/22145.2216\) |
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.
