Revised Algorithm Based on Turing Reduction for Solving ε-NN in Possion Point Process
Author:
Affiliation:

Clc Number:

TP311

  • Article
  • | |
  • Metrics
  • |
  • Reference [29]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    In a published study, the problem of using Turing reduction to solve ε-NN is studied. In other words, given a query point q, a point set P, and an approximate factor ε, the purpose is to return the approximate nearest neighbor of q in P with an approximation ratio of not more than 1+ε. Moreover, a Turing reduction algorithm with O(logn) query time complexity is proposed, where the query time is the number of times that the oracle is invoked. The comparison indicates that the O(logn) query time is the lowest compared to that of all the existing algorithms. However, the disadvantage of the proposed algorithm is that there is a factor of O((d/ε)d) in the preprocessing time complexity and space complexity. When the number of dimensions d is high, or the approximation factor ε is small, the factor would become unacceptable. Therefore, this study revises the reduction algorithm and analyzes the expected time complexity and space complexity of the algorithm when the input point set follows the Poisson point process. As a result, the expected preprocessing time complexity is reduced to O(nlogn), and the expected space complexity is reduced to O(nlogn), while the expected query time complexity remains O(logn). In this sense, the future work raised in the published study is completed.

    Reference
    [1] Ma HZ, Li JZ. An algorithm for reducing approximate nearest neighbor to approximate near neighbor with O(logn) query time. In: Proc. of the 12th Int’l Conf. on Combinatorial Optimization and Applications. Atlanta: Springer, 2018. 465-479.
    [2] Har-Peled S. A replacement for voronoi diagrams of near linear size. In: Proc. of the 42nd IEEE Symp. on Foundations of Computer Science. Newport Beach: IEEE, 2001. 94-103.
    [3] Har-Peled S, Indyk P, Motwani R. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 2012, 8(1): 321-350. [doi: 10.4086/toc.2012.v008a014
    [4] Indyk P, Motwani R. Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proc. of the 30th Annual ACM Symp. on Theory of Computing. Dallas: ACM, 1998. 604-613.
    [5] Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM, 1998, 45(6): 891-923. [doi: 10.1145/293347.293348
    [6] Goel A, Indyk P, Varadarajan K. Reductions among high dimensional proximity problems. In: Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms. Washington: Society for Industrial and Applied Mathematics, 2001. 769-778.
    [7] Iscen A, Tolias G, Avrithis Y, Chum O. Mining on manifolds: Metric learning without labels. In: Proc. of the 2018 IEEE/CVF Conf. on Computer Vision and Pattern Recognition. Salt Lake City: IEEE, 2018. 7642-7651.
    [8] Lu XL. Improving search using proximity-based statistics. In: Proc. of the 38th Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval. Santiago: ACM, 2015. 1065.
    [9] Luo YC, Zhu J, Li MX, Ren Y, Zhang B. Smooth neighbors on teacher graphs for semi-supervised learning. In: Proc. of the 2018 IEEE/CVF Conf. on Computer Vision and Pattern Recognition. Salt Lake City: IEEE, 2018. 8896-8905.
    [10] Zheng YX, Guo Q, Tung AKH, Wu S. LazyLSH: Approximate nearest neighbor search for multiple distance functions with a single index. In: Proc. of the 2016 Int’l Conf. on Management of Data. San Francisco: ACM, 2016. 2023-2037.
    [11] Minsky M, Papert S. Perceptrons. Cambridge: MIT Press, 1969.
    [12] Clarkson KL. An algorithm for approximate closest-point queries. In: Proc. of the 10th Annual Symp. on Computational Geometry. Stony Brook: ACM, 1994. 160-164.
    [13] Weber R, Schek HJ, Blott S. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: Proc. of the 24th Int’l Conf. on Very Large Data Bases. New York City: Morgan Kaufmann Publishers Inc., 1998. 194-205.
    [14] Arya S, Mount DM. Approximate nearest neighbor queries in fixed dimensions. In: Proc. of the 4th Annual ACM-SIAM Symp. on Discrete Algorithms. Austin: Society for Industrial and Applied Mathematics, 1993. 271-280.
    [15] Kleinberg JM. Two algorithms for nearest-neighbor search in high dimensions. In: Proc. of the 29th Annual ACM Symp. on Theory of Computing. El Paso: ACM, 1997. 599-608.
    [16] Datar M, Immorlica N, Indyk P, Mirrokni VS. Locality-sensitive hashing scheme based on p-stable distributions. In: Proc. of the 20th Annual Symp. on Computational Geometry. Brooklyn: ACM, 2004. 253-262.
    [17] Charikar MS. Similarity estimation techniques from rounding algorithms. In: Proc. of the 34th Annual ACM Symp. on Theory of Computing. Montreal: ACM, 2002. 380-388.
    [18] Li P, Mitzenmacher M, Shrivastava A. Coding for random projections. In: Proc. of the 31th Int’l Conf. on Machine Learning. Beijing: JMLR.org, 2014. II-676-II-684.
    [19] Terasawa K, Tanaka Y. Spherical LSH for approximate nearest neighbor search on unit hypersphere. In: Proc. of the 10th Int’l Conf. on Algorithms and Data Structures. Halifax: Springer, 2007. 27-38.
    [20] Andoni A, Razenshteyn IP. Tight lower bounds for data-dependent locality-sensitive hashing. In: Proc. of the 32nd Int’l Symp. on Computational Geometry. Dagstuhl: Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, 2016. 1-11.
    [21] Motwani R, Naor A, Panigrahy R. Lower bounds on locality sensitive hashing. SIAM Journal on Discrete Mathematics, 2008, 21(4): 930-935. [doi: 10.1137/050646858
    [22] Tao YF, Yi K, Sheng C, Kalnis P. Efficient and accurate nearest neighbor and closest pair search in high-dimensional space. ACM Trans. on Database Systems, 2010, 35(3): 20. [doi: 10.1145/1806907.1806912
    [23] Andoni A. Nearest neighbor search: The old, the new, and the impossible [Ph.D. Thesis]. Cambridge: Massachusetts Institute of Technology, 2009.
    [24] Wang JD, Shen HT, Song JK, Ji JQ. Hashing for similarity search: A survey. arXiv:1408.2927, 2014.
    [25] Andoni A, Indyk P. Nearest neighbors in high-dimensional spaces. In: Goodman JE, O’Rourke J, Tóth CD, eds. Handbook of Discrete and Computational Geometry. 3rd ed., Boca Raton: Chapman and Hall/CRC, 2017. 1135-1155.
    [26] Bern M, Eppstein D, Yao F. The expected extremes in a Delaunay triangulation. Int’l Journal of Computational Geometry & Applications, 1991, 1(1): 79-91. [doi: 10.1142/S0218195991000074
    [27] Bordenave C. Navigation on a Poisson point process. The Annals of Applied Probability, 2008, 18(2): 708-746. [doi: 10.1214/07-AAP472
    [28] Ahsen M, Ali Hassan S. A Poisson point process model for coverage analysis of multi-hop cooperative networks. In: Proc. of the 2015 Int’l Wireless Communications and Mobile Computing Conf. (IWCMC). Dubrovnik: IEEE, 2015. 442-447.
    [29] Kingman JFC. Poisson Process. Oxford: Oxford University Press, 1993.
    Cited by
Get Citation

马恒钊,闫跃,李建中.近似最近邻归约问题在泊松点过程上的再研究.软件学报,2023,34(10):4821-4829

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 06,2020
  • Revised:October 30,2020
  • Online: January 18,2023
  • Published: October 06,2023
You are the first2032505Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063