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

Author:

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

Indexed by:

CPCI-S EI Scopus

Abstract:

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.

Keyword:

approximation algorithm noisy thresholding stream submodular maximization

Author Community:

  • [ 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

Reprint Author's Address:

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

Show more details

Related Keywords:

Related Article:

Source :

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

ISSN: 1063-6927

Year: 2019

Page: 348-357

Language: English

Cited Count:

WoS CC Cited Count: 10

SCOPUS Cited Count: 13

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 4

Affiliated Colleges:

Online/Total:617/10633711
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.