Distributed Partial Clustering
Distributed Partial Clustering
复制标题
分布式部分集群
DOI：
10.1145/3322808
复制
发表时间：
2019
影响因子：
1.6
通讯作者：
Zhang, Qin
中科院分区：
文献类型：
--
作者：
Guha, Sudipto;Li, Yi;Zhang, Qin
近年来，分布式数据的算法设计越来越受欢迎，这主要是由于大量数据集通常被收集和存储在不同的位置。在分布式环境中，通信通常支配查询处理时间。因此，为分布式数据查询设计通信高效的算法变得至关重要。同时，人们已经广泛认识到，部分优化，即允许我们忽略一小部分数据，为我们提供了更好的解决方案。被忽视点的动机通常来自大数据场景中普遍存在的噪音和其他现象。在本文中，我们重点关注分布式模型中的部分聚类问题、k中心、k中位数和k均值目标，并提供具有通信的算法输入大小的次线性。因此，我们开发的第一个算法的partialk中位数和手段的目标，运行在次二次运行时间。我们还开始研究分布式算法聚类不确定的数据，其中每个数据点可能会落在多个位置在一定的概率分布。
Recent years have witnessed an increasing popularity of algorithm design for distributed data, largely due to the fact that massive datasets are often collected and stored in different locations. In the distributed setting, communication typically dominates the query processing time. Thus, it becomes crucial to design communication-efficient algorithms for queries on distributed data. Simultaneously, it has been widely recognized that partial optimizations, where we are allowed to disregard a small part of the data, provide us significantly better solutions. The motivation for disregarded points often arises from noise and other phenomena that are pervasive in large data scenarios.In this article, we focus on partial clustering problems,k-center,k-median, andk-means objectives in the distributed model, and provide algorithms with communication sublinear of the input size. As a consequence, we develop the first algorithms for the partialk-median and means objectives that run in subquadratic running time. We also initiate the study of distributed algorithms for clustering uncertain data, where each data point can possibly fall into multiple locations under certain probability distribution.
DOI：
10.1006/jcss.1997.1547
发表时间：
1998
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
P. Duris;J. Rolim
通讯作者：
J. Rolim
不确定数据上的一维 k 中心
DOI：
10.1016/j.tcs.2015.08.017
发表时间：
2014
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
Haitao Wang;Jingru Zhang
通讯作者：
Jingru Zhang
不确定数据聚类算法综述
DOI：
10.1201/9781315373515-18
发表时间：
2018
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
C. Aggarwal
通讯作者：
C. Aggarwal