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

Author:

Cui, M. (Cui, M..) | Du, D. (Du, D..) | Gai, L. (Gai, L..) | Yang, R. (Yang, R..)

Indexed by:

Scopus SCIE

Abstract:

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-Time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ4 a(1+γ+γ2+γ3)-] for any ≥ 0 with a query complexity of n/ + a and a memory complexity of O(aklog(k)log(1/)), where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-Than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1-e-γ-with linear query complexity. © 2023 World Scientific Publishing Company.

Keyword:

Cardinality-constrained linear-Time streaming

Author Community:

  • [ 1 ] [Cui M.]Beijing International Center for Mathematical Research, Peking University, Beijing, 100871, China
  • [ 2 ] [Cui M.]Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, China
  • [ 3 ] [Du D.]Faculty of Management, University of New Brunswick, Fredericton, NB, Canada
  • [ 4 ] [Gai L.]Business School, University of Shanghai for Science and Technology, Shanghai, 200093, China
  • [ 5 ] [Gai L.]School of Intelligent Emergency Management, University of Shanghai for Science and Technology, Shanghai, 200093, China
  • [ 6 ] [Yang R.]Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing, 100124, China

Reprint Author's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

International Journal of Foundations of Computer Science

ISSN: 0129-0541

Year: 2023

Issue: 6

Volume: 35

Page: 631-650

0 . 8 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:19

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 8

Affiliated Colleges:

Online/Total:482/10713233
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.