Approximate range searching in higher dimension. (English) Zbl 1124.65018
Summary: Applying standard dimensionality reduction techniques, we show how to perform approximate range searching in higher dimension while avoiding the curse of dimensionality. Given \(n\) points in a unit ball in \(\mathbb R^n\), an approximate halfspace range query counts (or reports) the points in a query halfspace; the qualifier “approximate” indicates that points within distance \(\varepsilon \) of the boundary of the halfspace might be misclassified. Allowing errors near the boundary has a dramatic effect on the complexity of the problem. We give a solution with \(\tilde O(d/\varepsilon^2)\) query time and \(dn^{O(\varepsilon ^{ - 2})}\) storage. For an exact solution with comparable query time, one needs roughly \(\Omega (n^{d})\) storage. In other words, an approximate answer to a range query lowers the storage requirement from exponential to polynomial. We generalize our solution to polytope/ball range searching.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
References:
| [1] | Agarwal, P. K.; Erickson, J., Geometric range searching and its relatives, (Chazelle, B.; Goodman, J. E.; Pollack, R., Advances in Discrete and Computational Geometry (1999), AMS Press), 1-56 · Zbl 0916.68031 |
| [2] | Agarwal, P. K., Range searching, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), Chapman and Hall: Chapman and Hall CRC) · Zbl 0806.68106 |
| [3] | Arya, S.; Mount, D. M., Approximate range searching, Comput. Geom. Theory Appl., 17, 135-163 (2000) · Zbl 0968.68167 |
| [4] | Brönnimann, H.; Chazelle, B.; Pach, J., How hard is halfspace range searching, Discrete Comput. Geom., 10, 143-155 (1993) · Zbl 0778.68087 |
| [5] | Chazelle, B., The Discrepancy Method: Randomness and Complexity (2000), Cambridge University Press, Chapter 6, paperback version 2001 · Zbl 0960.65149 |
| [6] | P. Indyk, High-dimensional computational geometry, PhD Thesis, Stanford University, 2000, http://theory.lcs.mit.edu/ indyk/thesis.ps; P. Indyk, High-dimensional computational geometry, PhD Thesis, Stanford University, 2000, http://theory.lcs.mit.edu/ indyk/thesis.ps |
| [7] | Indyk, P.; Matousek, J., Low-distortion embeddings of finite metric spaces, (Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (2004), Chapman and Hall: Chapman and Hall CRC) |
| [8] | P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. ACM STOC, 1998, pp. 604-613; P. Indyk, R. Motwani, Approximate nearest neighbors: Towards removing the curse of dimensionality, in: Proc. ACM STOC, 1998, pp. 604-613 · Zbl 1029.68541 |
| [9] | J.M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, in: Proc. ACM STOC, 1997, pp. 599-608; J.M. Kleinberg, Two algorithms for nearest-neighbor search in high dimensions, in: Proc. ACM STOC, 1997, pp. 599-608 · Zbl 0963.68049 |
| [10] | Kushilevitz, E.; Ostrovsky, R.; Rabani, Y., Efficient search for approximate nearest neighbor in high dimensional spaces, SIAM J. Comput., 30, 457-474 (2000) · Zbl 0963.68078 |
| [11] | Vapnik, V. N.; Chervonenkis, A. Y., On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 16, 264-280 (1971) · Zbl 0247.60005 |
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.
