• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Yang, Ruiqi (Yang, Ruiqi.) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川) | Cheng, Yukun (Cheng, Yukun.) | Gao, Chuangen (Gao, Chuangen.) | Du, Ding-Zhu (Du, Ding-Zhu.)

收录:

CPCI-S EI Scopus

摘要:

Motivated by the need for analyzing the rapidly producing data streams, such as images, videos, sensor data, etc, in a timely manner, the study on the streaming algorithms to extract representative information from massive data to maximize some objective function is therefore important and urgent. Most of previous works are assumed under a noise-free environment, while in many realistic applications obtaining the exact function value is hard or computing the function value may cost much, which brings the noisy version. Hence in this paper, we address a more general problem to select a subset of at most k elements from the stream to maximize a noisy set function (not necessarily submodular). To be specific, we cast our problem as the streaming submodular maximization problem under multiplicative and additive noise models. We develop an efficient thresholding streaming algorithm, which calls several copies of a subroutine in parallel. Therefore, this algorithm only requires two passes over data and has a memory independent of data size. For both of noisy models, its approximation guarantee approaches 2/k. In our numerical experiments, we extensively evaluate the effectiveness of our thresholding streaming algorithm on some applications in real data set.

关键词:

approximation algorithm noisy stream submodular maximization thresholding

作者机构:

  • [ 1 ] [Yang, Ruiqi]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing, Peoples R China
  • [ 3 ] [Cheng, Yukun]Suzhou Univ Sci & Technol, Sch Business, Suzhou Key Lab Big Data & Informat Serv, Suzhou, Peoples R China
  • [ 4 ] [Gao, Chuangen]Shandong Univ, Sch Comp Sci & Technol, Jinan, Peoples R China
  • [ 5 ] [Du, Ding-Zhu]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75083 USA

通讯作者信息:

  • [Yang, Ruiqi]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing, Peoples R China

查看成果更多字段

相关关键词:

相关文章:

来源 :

2019 39TH IEEE INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS (ICDCS 2019)

ISSN: 1063-6927

年份: 2019

页码: 348-357

语种: 英文

被引次数:

WoS核心集被引频次: 8

SCOPUS被引频次: 11

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 2

归属院系:

在线人数/总访问数:869/2992862
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司