Home>Results

  • Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

[期刊论文]

Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee

Share
Edit Delete 报错

author:

Lin, Zeyu (Lin, Zeyu.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤) | Jia, Chaoqi (Jia, Chaoqi.) [3]

Indexed by:

CPCI-S EI Scopus

Abstract:

Emerging applications are imposing challenges for incorporating fairness constraints into k-center clustering in the streaming setting. Different from the traditional k-center problem, the fairness constraints require that the input points be divided into disjoint groups and the number of centers from each group is constrained by a given upper bound. Moreover, observing the applications of fair k-center inmassive datasets, we consider the problem in the streaming setting, where the data points arrive in a streaming manner that each point can be processed at its arrival. As themain contributions, we propose a two-pass streaming algorithm for the fair k-center problem with two groups, achieving an approximation ratio of 3 + epsilon and consuming only O(k log n) memory and O(k) update time, matching the state-of-art ratio for the offline setting. Then, we show that the algorithm can be easily improved to a one-pass streaming algorithm with an approximation ratio of 7+ epsilon and the same memory complexity and update time. Moreover, we show that our algorithm can be simply tuned to solve the case with an arbitrary number of groups while achieving the same ratio and space complexity. Lastly, we carried out extensive experiments to evaluate the practical performance of our algorithm compared with the state-of-the-art algorithms.

Keyword:

Approximation algorithm Fair k-center clustering Streaming algorithm

Community:

  • [ 1 ] [Lin, Zeyu]Fuzhou Univ, Sch Math & Stat, Fuzhou 350116, Peoples R China
  • [ 2 ] [Guo, Longkun]Fuzhou Univ, Sch Math & Stat, Fuzhou 350116, Peoples R China
  • [ 3 ] [Jia, Chaoqi]RMIT Univ, Sch Accounting Informat Syst & Supply Chain, Melbourne, Vic 3000, Australia
  • [ 4 ] [Guo, Longkun]Qilu Univ Technol, Sch Comp Sci, Shandong Acad Sci, Jinan 250316, Peoples R China
  • [ 5 ] [Jia, Chaoqi]Qilu Univ Technol, Sch Comp Sci, Shandong Acad Sci, Jinan 250316, Peoples R China

Reprint 's Address:

  • [Guo, Longkun]Fuzhou Univ, Sch Math & Stat, Fuzhou 350116, Peoples R China;;[Guo, Longkun]Qilu Univ Technol, Sch Comp Sci, Shandong Acad Sci, Jinan 250316, Peoples R China;;

Show more details

Version:

Related Article:

Source :

ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT III, PAKDD 2024

ISSN: 2945-9133

Year: 2024

Volume: 14647

Page: 105-117

Cited Count:

WoS CC Cited Count:

30 Days PV: 1

Online/Total:85/10272447
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1