An optimal algorithm for approximate nearest neighbor searching fixed dimensions

Journal of the ACM - Tập 45 Số 6 - Trang 891-923 - 1998
Sunil Arya1, David M. Mount2, Nathan S. Netanyahu3,4, Ruth Silverman2,5, Angela Y. Wu6
1Hong Kong Univ. of Science of Technology, Kowloon, Hong Kong
2Univ. of Maryland, College Park
3NASA, Greenbelt, MD
4Univ. of Maryland, College Park; and NASA, Greenbelt, MD
5Univ. of the District of Columbia, Washington, D.C.; and Univ. of Maryland, College Park
6American Univ., Washington, D.C.

Tóm tắt

Consider a set of S of n data points in real d -dimensional space, R d , where distances are measured using any Minkowski metric. In nearest neighbor searching, we preprocess S into a data structure, so that given any query point q ∈ R d , is the closest point of S to q can be reported quickly. Given any positive real ϵ, data point p is a (1 +ϵ)- approximate nearest neighbor of q if its distance from q is within a factor of (1 + ϵ) of the distance to the true nearest neighbor. We show that it is possible to preprocess a set of n points in R d in O(dn log n ) time and O(dn) space, so that given a query point q ∈ R d , and ϵ > 0, a (1 + ϵ)-approximate nearest neighbor of q can be computed in O ( c d , ϵ log n ) time, where c d,ϵ ≤ d ⌈1 + 6d/ϵ⌉ d is a factor depending only on dimension and ϵ. In general, we show that given an integer k ≥ 1, (1 + ϵ)-approximations to the k nearest neighbors of q can be computed in additional O(kd log n ) time.

Từ khóa


Tài liệu tham khảo

10.1137/0222051

10.1109/DCC.1993.253111

ARYA , S. , AND MOUNT , D.M. 1993 b. Approximate nearest neighbor queries in fixed dimensions . In Proceedings of the 4th A CM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 271 - 280 . ARYA, S., AND MOUNT, D.M. 1993b. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th A CM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 271-280.

10.1145/220279.220298

10.1145/220279.220315

ARYA , S. , MOUNT , D. M. , NETANYAHU , N. , SILVERMAN , R. , AND WU , A. Y. 1994 . An optimal algorithm for approximate nearest neighbor searching in fixed dimensions . In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 573 - 582 . ARYA, S., MOUNT, D. M., NETANYAHU, N., SILVERMAN, R., AND WU, A. Y. 1994. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. In Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 573-582.

10.1109/TCOM.1985.1096214

10.1145/355921.355927

10.1145/263661.263671

BERCHTOLD , S. , KEIM , D. A. , AND KRIEGEL , H.-P. 1996 . The X-tree: An index structure for high dimensional data . In Proceedings of the 22nd VLDB Conference. pp. 28 - 39 . BERCHTOLD, S., KEIM, D. A., AND KRIEGEL, H.-P. 1996. The X-tree: An index structure for high dimensional data. In Proceedings of the 22nd VLDB Conference. pp. 28-39.

10.1016/0020-0190(93)90222-U

BERN , M. , EPPSTEIN , D. , AND TENS , S.-H. 1993. Parallel construction of quadtrees and quality triangulations . In Proceedings of the 3rd Workshop Algorithms Data Structures . Lecture Notes in Computer Science , vol. 709 . Springer-Verlag , New York , pp. 188 - 199 . BERN, M., EPPSTEIN, D., AND TENS, S.-H. 1993. Parallel construction of quadtrees and quality triangulations. In Proceedings of the 3rd Workshop Algorithms Data Structures. Lecture Notes in Computer Science, vol. 709. Springer-Verlag, New York, pp. 188-199.

10.1145/220279.220296

10.1145/129712.129766

CALLAHAN , P. B. , AND KOSARAJU , S.U. 1995 . Algorithms for dynamic closest pair and n-body potential fields . In Proceedings of the 6th Annual A CM-SIAM Symposium on Discrete Algorithms ( San Francisco, Calif., Jan. 22-24). ACM, New York , pp. 263 - 272 . CALLAHAN, P. B., AND KOSARAJU, S.U. 1995. Algorithms for dynamic closest pair and n-body potential fields. In Proceedings of the 6th Annual A CM-SIAM Symposium on Discrete Algorithms (San Francisco, Calif., Jan. 22-24). ACM, New York, pp. 263-272.

10.1145/262839.263001

10.1109/SFCS.1982.58

10.1109/SFCS.1983.16

10.1137/0217052

10.1145/177424.177609

10.1145/355826.355832

CORMEN , T. H. , LEISERSON , C. E. , AND RIVEST , R.L. 1990. Introduction to Algorithms . MIT Press , Cambridge, Mass . CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R.L. 1990. Introduction to Algorithms. MIT Press, Cambridge, Mass.

10.1023/A:1022664626993

10.1109/TIT.1967.1053964

10.1007/978-3-662-03427-9

10.1002/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9

DEV a OYE , L., AND WAGNE a, T. J. 1982 . Nearest neighbor methods in discrimination . In Handbook of Statistics , vol. 2 . P. R. Krishnaiah and L. N. Kanal, eds. North-Holland, Amsterdam, The Netherlands. DEVaOYE, L., AND WAGNEa, T.J. 1982. Nearest neighbor methods in discrimination. In Handbook of Statistics, vol. 2. P. R. Krishnaiah and L. N. Kanal, eds. North-Holland, Amsterdam, The Netherlands.

DUDA , R. O. , AND HAST , P.E. 1978. Pattern Classification and Scene Analysis . Wiley , New York . DUDA, R. O., AND HAST, P.E. 1978. Pattern Classification and Scene Analysis. Wiley, New York.

EDELSB aUNN Ea, H . 1987. Algorithms in Combinatorial Geometry , vol. 10 of EATCS Monographs on Theoretical Computer Science . Springer-Verlag , New York . EDELSBaUNNEa, H. 1987. Algorithms in Combinatorial Geometry, vol. 10 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, New York.

10.1109/TIT.1985.1057040

FAYYAD , U. M. , PIATETSKY-SHAPIRO , G. , SMYTH , P. , AND UTHURUSAMY , R. 1996. Advances in Knowledge Discovery and Data Mining . AAAI Press/MIT Press , Cambridge, Mass . FAYYAD, U. M., PIATETSKY-SHAPIRO, G., SMYTH, P., AND UTHURUSAMY, R. 1996. Advances in Knowledge Discovery and Data Mining. AAAI Press/MIT Press, Cambridge, Mass.

10.1145/62212.62255

10.1109/2.410146

10.1137/0214055

FREDERICKSON , G.N. 1993 . A data structure for dynamically maintaining rooted trees . In Proceedings of the 4th Annual A CM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 175 - 194 . FREDERICKSON, G.N. 1993. A data structure for dynamically maintaining rooted trees. In Proceedings of the 4th Annual A CM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 175-194.

10.1145/28869.28874

10.1145/355744.355745

10.1109/T-C.1975.224110

GALPERIN , I. , AND RIVEST , R. L. 1993 . Scapegoat trees . In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. ACM , New York , pp. 165 - 174 . GALPERIN, I., AND RIVEST, R. L. 1993. Scapegoat trees. In Proceedings of the 4th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, pp. 165-174.

GERSHO , A. , AND GRAY , R. M. 1991. Vector Quantization and Signal Compression . Kluwer Academic , Boston, Mass . GERSHO, A., AND GRAY, R. M. 1991. Vector Quantization and Signal Compression. Kluwer Academic, Boston, Mass.

10.1016/0167-8655(92)90098-K

10.1145/276698.276876

10.1145/258533.258653

10.1145/276698.276877

10.1049/ip-vis:19941140

10.5555/615204.615210

10.1006/inco.1993.1057

MOUNT , D. M. , NETANYAHU , N. , SILVERMAN , R. , AND WU , A. Y. 1995 . Chromatic nearest neighbor searching: A query sensitive approach . In Proceedings of the 7th Canadian Conference on Computer Geometry. (Quebec City, Que., Canada, Aug. 10-13) . pp. 261 - 266 . MOUNT, D. M., NETANYAHU, N., SILVERMAN, R., AND WU, A. Y. 1995. Chromatic nearest neighbor searching: A query sensitive approach. In Proceedings of the 7th Canadian Conference on Computer Geometry. (Quebec City, Que., Canada, Aug. 10-13). pp. 261-266.

10.1007/978-1-4612-1098-6

RIVEST , R.L. 1974. On the optimality of Elais's algorithm for performing best-match searches . In Information Processing . North-Holland Publishing Company , Amsterdam, The Netherlands, pp. 678 - 681 . RIVEST, R.L. 1974. On the optimality of Elais's algorithm for performing best-match searches. In Information Processing. North-Holland Publishing Company, Amsterdam, The Netherlands, pp. 678-681.

10.1145/223784.223794

SAMET , n . 1990 . The Design and Analysis of Spatial Data Structures. Addison-Wesley , Reading, Mass. SAMET, n. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley, Reading, Mass.

10.1007/BF01377181

10.1016/0022-0000(83)90006-5

10.1007/BF01759061

10.1007/BF02187718

10.5555/645481.655573

10.1145/22145.22163

Thông tin
Thông tin xuất bản

Journal of the ACM

Tập 45 Số 6

891-923

Thông tin tác giả