检索结果-内蒙古大学图书馆

IEEE International Conference on Acoustics, Speech and Signal Processing

作者： Qilian Yu Hang Li Yun Liao Shuguang Cui Dept. of ECE University of California Davis CA 95616 USA Dept. of ECE University of California San Diego CA 92093 USA

ISBN: (纸本)9781538646595

In a social network, influence maximization is the problem of identifying a set of users that own the maximum influence ability across the network. In this paper, a novel credit distribution (CD) based model, termed as the multi-action CD (mCD) model, is introduced to quantify the influence ability of each user. Compared to existing models, the new model can work with practical datasets where one type of action is recorded for multiple times. Based on this model, influence maximization is formulated as a submodular maximization problem under a knapsack constraint, which is NP-hard. An efficient streaming algorithm is developed to achieve ([1/3]-ε) approximation of the optimality. Experiments conducted on real Twitter dataset demonstrate that the mCD model enjoys high accuracy compared to the conventional CD model in estimating the total number of people who get influenced in a social network. Furthermore, compared to the greedy algorithm, the proposed single-pass streaming algorithm achieves similar performance in terms of influence maximization, while running several orders of magnitude faster.

关键词： Social Networks Influence Maximization Credit Distribution Submodularity streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Submodular maximization over data streams with differential privacy noise

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期944卷

作者： Guo, Longkun Liao, Kewen Xiao, Di Yao, Pei Qilu Univ Technol Sch Comp Sci & Technol Jinan 250300 Peoples R China Fuzhou Univ Coll Math & Stat Fuzhou 350116 Peoples R China Australian Catholic Univ Peter Faber Business Sch HilstLab Sydney Australia

In the big data era, data often comes in the form of streams and fast data stream analysis has recently attracted intensive research interest. Submodular optimization naturally appears in many streaming data applications such as social network influence maximization with the property of diminishing returns. However, in a practical setting, streaming data frequently comes with noises that are small but significant enough to impact the optimality of submodular optimization solutions. Following the framework of differential privacy (DP), this paper considers a streaming model with DP noise that is small by construction. Within this noisy streaming model, the paper strives to address the general problem of submodular maximization with a cardinality constraint. The main theoretical result we obtained is a streaming algorithm that is one-pass and has an approximation guarantee of 1/(2+ (1 + 1/k)(2))(1 + 1/k) - delta for any delta > 0. Finally, we implement the algorithm and evaluate it against several baseline methods. Numerical results support the practical performance of our algorithm across several real datasets. (c) 2022 Published by Elsevier B.V.

关键词： Submodular maximization streaming algorithm Differential privacy noise

来源：评论

学校读者我要写书评

暂无评论

Bloom Filters in Adversarial Environments

引用

ACM TRANSACTIONS ON algorithmS 2019年第3期15卷 35-35页

作者： Naor, Moni Eylon, Yogev Wiczmann Inst Sci Dept Comp Sci & Appl Math IL-76100 Rehovot Israel

Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the adversarial model. Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, we consider a data structure known as a "Bloom filter" and prove a tight connection between Bloom filters in this model and cryptography. A Bloom filter represents a set S of elements approximately by using fewer bits than a precise representation. The price for succinctness is allowing for some errors: For any x is an element of S, it should always answer Yes, and for any x is not an element of S it should answer Yes only with small probability. In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the number of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries, we show that there exists a Bloom filter for sets of size n and error e that is secure against t queries and uses only O(n log 1/ epsilon+ t) bits of memory. In comparison, n log 1/epsilon is the best possible under a non-adaptive adversary.

关键词： Bloom filter adaptive inputs streaming algorithm pseudorandom functions

来源：评论

学校读者我要写书评

暂无评论

Address Block Counting Using Two-Tier Cardinality Estimation

引用

IEEE ACCESS 2019年 7卷 125754-125761页

作者： Yoon, Myungkeun Kim, Young Jae Kookmin Univ Dept Comp Engn Seoul 02707 South Korea

An address block is defined as a set of continuous addresses between two points in an address space. Counting the number of distinct address blocks that have been accessed during a measurement period can provide useful information for cyber security, computer networks, and storage systems. However, this counting problem becomes challenging when addresses are accessed randomly since adjacent addresses must be carefully identified and merged into one block. This study presents a new algorithm that can accurately estimate the number of distinct address blocks where each address access is monitored only once. This new algorithm requires only three counters to keep the numbers of distinct addresses and one-bit truncated addresses, respectively, in two-tier counting architecture. Both time and space complexities are significantly improved because only three counters are required for cardinality estimation instead of traditional hash table or tree data structures. Experimental results show that the new scheme saves more than 50% memory space and runs two times faster than a tree-based existing algorithm;the relative error of estimation is less than 10%.

关键词： Cardinality estimation streaming algorithm data analysis counting ransomware

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Non-Submodular Optimization Over Sliding Windows

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2022年第5期39卷 2150038-2150038页

作者： Luo, Yunxin Wu, Chenchen Xu, Chunming Tianjin Univ Technol Coll Sci Inst Operat Res & Syst Engn Tianjin 300384 Peoples R China

In this paper, the problem we study is how to maximize a monotone non-submodular function with cardinality constraint. Different from the previous streaming algorithms, this paper mainly considers the sliding window model. Based on the concept of diminishing-return ratio gamma, we propose a (1/3-gamma(2) - epsilon)-approximation algorithm with the memory O(k log(2)(k Phi 1/gamma/epsilon(2)), where Phi is the ratio between maximum and minimum values of any singleton element of function f. Then, we improve the approximation ratio to (1/2 gamma - epsilon) through the sub-windows at the expense of losing some memory. Our results 2 generalize the corresponding results for the submodular case.

关键词： streaming algorithm non-submodular maximization cardinality constraint set function sliding window

来源：评论

学校读者我要写书评

暂无评论

Complete Subhedge Projection for Stepwise Hedge Automata

引用

algorithmS 2024年第8期17卷 339页

作者： Al Serhali, Antonio Niehren, Joachim Univ Lille Inria Ctr Lille France

We demonstrate how to evaluate stepwise hedge automata (Shas) with subhedge projection while completely projecting irrelevant subhedges. Since this requires passing finite state information top-down, we introduce the notion of downward stepwise hedge automata. We use them to define in-memory and streaming evaluators with complete subhedge projection for Shas. We then tune the evaluators so that they can decide on membership at the earliest time point. We apply our algorithms to the problem of answering regular XPath queries on Xml streams. Our experiments show that complete subhedge projection of Shas can indeed speed up earliest query answering on Xml streams so that it becomes competitive with the best existing streaming tools for XPath queries.

关键词： automata projection algorithm streaming algorithm Xml

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Applications of Uniform Sampling: Densest Subgraph and Beyond 16

Brief Announcement: Applications of Uniform Sampling: Denses...

引用

Proceedings of the 28th ACM Symposium on Parallelism in algorithms and Architectures

作者： Hossein Esfandiari MohammadTaghi Hajiaghayi David P. Woodruff University of Maryland College Park MD USA IBM Almaden CA USA

ISBN: (纸本)9781450342100

In this paper we provide a framework to analyze the effect of uniform sampling on graph optimization problems. Interestingly, we apply this framework to a general class of graph optimization problems that we call heavy subgraph problems, and show that uniform sampling preserves a 1-ε approximate solution to these problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, d-max cut, and d-sum-max clustering. As an immediate impact of this result, one can use uniform sampling to solve these problems in streaming, turnstile or Map-Reduce settings. Indeed, our results by characterizing heavy subgraph problems address Open Problem 13 at the IITK Workshop on algorithms for Data Streams in 2006 regarding the effects of subsampling, in the context of graph *** Bhattacharya et al. in STOC 2015 provide the first one pass algorithm for the densest subgraph problem in the streaming model with additions and deletions to its edges, i.e., for dynamic graph streams. They present a (0.5-ε)-approximation algorithm using ~O(n) space, where factors of ε and log(n) are suppressed in the ~O notation. In this paper we improve the (0.5-ε)-approximation algorithm of Bhattacharya et al. by providing a (1-ε)-approximation algorithm using ~O(n) space.

关键词： uniform sampling streaming algorithm densest subgraph

来源：评论

学校读者我要写书评

暂无评论

Optimality of linear sketching under modular updates 19

Optimality of linear sketching under modular updates

引用

Proceedings of the 34th Computational Complexity Conference

作者： Kaave Hosseini Shachar Lovett Grigory Yaroslavtsev University of California Indiana University

ISBN: (纸本)9783959771160

We study the relation between streaming algorithms and linear sketching algorithms, in the context of binary updates. We show that for inputs in n dimensions, the existence of efficient streaming algorithms which can process Ω(n2) updates implies efficient linear sketching algorithms with comparable cost. This improves upon the previous work of Li, Nguyen and Woodruff [23] and Ai, Hu, Li and Woodruff [3] which required a triple-exponential number of updates to achieve a similar result for updates over integers. We extend our results to updates modulo p for integers p ≥ 2, and to approximation instead of exact computation.

关键词： communication complexity linear sketching streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

Estimating cardinality distributions in network traffic: extended abstract 08

Estimating cardinality distributions in network traffic: ext...

引用

Proceedings of the 2008 ACM SIGMETRICS international conference on Measurement and modeling of computer systems

作者： Aiyou Chen Li Li Jin Cao Bell Labs Alcatel-Lucent Technologies Murray Hill NJ USA

ISBN: (纸本)9781605580050

Information on network host connectivity patterns are important for network monitoring and traffic engineering. In this paper, an efficient streaming algorithm is proposed to estimate cardinality distributions including connectivity distributions, e.g. percent of hosts with any given number of distinct communicating peers or flows.

关键词： streaming algorithm cardinality distribution

来源：评论

学校读者我要写书评

暂无评论

Private and Continual Release of Statistics

引用

ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY 2011年第3期14卷 26-26页

作者： Chan, T. -H. Hubert Shi, Elaine Song, Dawn Univ Hong Kong Hong Kong Hong Kong Peoples R China Palo Alto Res Ctr Palo Alto CA USA Univ Calif Berkeley Berkeley CA 94720 USA

We ask the question: how can Web sites and data aggregators continually release updated statistics, and meanwhile preserve each individual user's privacy? Suppose we are given a stream of 0's and 1's. We propose a differentially private continual counter that outputs at every time step the approximate number of 1's seen thus far. Our counter construction has error that is only poly-log in the number of time steps. We can extend the basic counter construction to allow Web sites to continually give top-k and hot items suggestions while preserving users' privacy.

关键词： algorithms Differential privacy continual mechanism streaming algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：