Efficient Distributed Algorithms for the K-Nearest Neighbors Problem
Efficient Distributed Algorithms for the K-Nearest Neighbors Problem
复制标题
K近邻问题的高效分布式算法
DOI：
10.1145/3350755.3400268
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Pandurangan, Gopal
中科院分区：
文献类型：
--
作者：
Fathi, Reza;Molla, Anisur Rahaman;Pandurangan, Gopal
K近邻问题是机器学习中的一个基本问题，有着广泛的应用。在这个问题中，给定一组(训练)n个带标签的数据点和一个查询点Q，我们想要根据查询的K个最近点的标签为Q分配一个标签。我们在k-Machine模型中研究了这个问题，k-Machine模型是一个分布式大规模数据模型。在该模型中，我们假设n个点(以均衡的方式)分布在k台机器上，目标是使用少量的通信轮次来计算给定机器查询点的答案。我们的主要结果是在k机模型中的随机化算法，其运行在O(LogK)次通信轮次中具有很高的成功概率(无论机器数k和点数n)。该算法的消息复杂度较小，仅需O(KlogK)条消息。对于基于比较的算法，我们的界限基本上是最好的。我们还实现了我们的算法，并在实践中证明了它的良好性能。
The K-nearest neighbors is a basic problem in machine learning with numerous applications. In this problem, given a (training) set of n data points with labels and a query point q, we want to assign a label to q based on the labels of the K-nearest points to the query. We study this problem in the k-machine model, a model for distributed large-scale data. In this model, we assume that the n points are distributed (in a balanced fashion) among the k machines and the goal is to compute an answer given a query point to a machine using a small number of communication rounds.Our main result is a randomized algorithm in the k-machine model that runs in O(log K) communication rounds with high success probability (regardless of the number of machines k and the number of points n). The message complexity of the algorithm is small taking only O(k log K) messages. Our bounds are essentially the best possible for comparison-based algorithms. We also implemented our algorithm and show that it performs well in practice.
登录
查看更多内容
DOI：
10.1145/3210377.3210409
发表时间：
2016-02
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
DOI：
--
发表时间：
1982
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
M. Rodeh
通讯作者：
M. Rodeh
影响因子：
4.1
作者：
Yang, Min;Ma, Kun;Yu, Xiaohui
通讯作者：
Yu, Xiaohui
k 机模型中的近最优聚类
DOI：
--
发表时间：
2017
期刊：
International Conference of Distributed Computing and Networking
影响因子：
--
作者：
Sayan Bandyapadhyay;Tanmay Inamdar;Shreyas Pai;Sriram V. Pemmaraju
通讯作者：
Sriram V. Pemmaraju
随机领导者选举的次线性边界
影响因子：
1.1
作者：
S. Kutten;Gopal Pandurangan;D. Peleg;Peter Robinson;Amitabh Trehan
通讯作者：
Amitabh Trehan