In this work, we study the notion of representation obliviousness in the context of pseudodeterministic streaming algorithms. A (randomized) streaming algorithm A is pseudodeterministic, if for every stream D, there is a ''canonical value'' g(D) so that with probability at least 2/3, A on input stream D outputs g(D). Intuitively, a randomized algorithm is representation oblivious if the output distribution of the algorithm does not depend on the representation of the input. We investigate this notion in the context of streaming algorithms, more specifically, distinct elements estimation (F 0 estimation) in data streams. In this context, representation obliviousness captures the idea that the output distribution of an algorithm for estimating F 0 should only depend on the set of distinct elements of the stream. This is a natural notion, as we note that standard streaming algorithms are representation-oblivious in this sense. We prove that any representation oblivious pseudodeterministic streaming algorithm for estimating F 0 must use Ω(n) space, where [n] is the universe. More generally, we prove that any representation oblivious pseudodeterministic t(n)-pass streaming algorithm requires Ω(n/t(n)) space. This lower bound matches the space requirement of the straightforward multi-pass deterministic algorithm that exactly computes F 0 .

Submodular optimization has become increasingly prominent in machine learning, and fairness has drawn much attention. In this paper, we propose to study the fair k-submodular maximization problem and develop a 1/3-approximation greedy algorithm with a running time of O(knB). Our theoretical guarantee matches the best-known k-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a (1/3 ϵ) approximation with ${\mathcal{O}}\left({\frac{{kn}}{\varepsilon }\log \frac{B}{\varepsilon }}\right)$ evaluations of the function−f. Furthermore, for both algorithms, we provide approximation guarantees when the k-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical study and examined the practical implications of fairness. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.

Submodular optimization finds applications in machine learning and data mining. In this paper, we study the problem of maximizing functions of the form h = f-c, where f is a monotone, non-negative, weakly submodular set function and c is a modular function. We design a deterministic approximation algorithm that runs with O(n/ε log n/(γ ε) ) oracle calls to function h, and outputs a set S such that h(S) ≥ γ(1-ε)f(OPT)-c(OPT)-c(OPT)/γ(1-ε) log f(OPT)/c(OPT), where γ is the submodularity ratio of f. Existing algorithms for this problem either admit a worse approximation ratio or have quadratic runtime. We also present an approximation ratio of our algorithm for this problem with an approximate oracle of f. We validate our theoretical results through extensive empirical evaluations on real-world applications, including vertex cover and influence diffusion problems for submodular utility function f, and Bayesian A-Optimal design for weakly submodular f. Our experimental results demonstrate that our algorithms efficiently achieve high-quality solutions.

In today's digital age, it is becoming increasingly prevalent to retain digital footprints in the cloud indefinitely. Nonetheless, there is a valid argument that entities should have the authority to decide whether their personal data remains within a specific database or is expunged. Indeed, nations across the globe are increasingly enacting legislation to uphold the "Right To Be Forgotten" for individuals. Investigating computational challenges, including the formalization and implementation of this notion, is crucial due to its relevance in the domains of data privacy and management. This work introduces a new streaming model: the 'Right to be Forgotten Data Streaming Model' (RFDS model). The main feature of this model is that any element in the stream has the right to have its history removed from the stream. Formally, the input is a stream of updates of the form (a, Δ) where Δ ∈ {+, ⊥} and a is an element from a universe U. When the update Δ=+ occurs, the frequency of a, denoted as f a , is incremented to f a +1. When the update Δ=⊥, occurs, f a is set to 0. This feature, which represents the forget request, distinguishes the present model from existing data streaming models. This work systematically investigates computational challenges that arise while incorporating the notion of the right to be forgotten. Our initial considerations reveal that even estimating F 1 (sum of the frequencies of elements) of the stream is a non-trivial problem in this model. Based on the initial investigations, we focus on a modified model which we call α-RFDS where we limit the number of forget operations to be at most α fraction. In this modified model, we focus on estimating F 0 (number of distinct elements) and F 1 . We present algorithms and establish almost-matching lower bounds on the space complexity for these computational tasks.

Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP’s and computation of zeroth frequency moments ( F 0 ) for data streams. Our investigations lead us to observe a striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and F 0 computation. We design a recipe for translating algorithms developed for F 0 estimation to model counting, resulting in new algorithms for model counting. We also provide a recipe for transforming sampling algorithm over streams to constraint sampling algorithms. We then observe that algorithms in the context of distributed streaming can be transformed into distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing F 0 estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields an algorithm for multidimensional range efficient F 0 estimation with a simpler analysis.

We investigate the problem of multi-objective submodular optimization with cardinality constraint in the context of δ-approximate oracle and show that it is possible to ensure (1 − 1/e)2− 3δ-approximate guarantee for the multi-objective submodular optimization problem. We show that group influence maximization in online social networks is an instance of this optimization problem with cardinality constraint and δ-oracle. We develop a prototype implementation of our solution strategy for group influence maximization problem for networks of different sizes and experimentally justify the effectiveness and scalability of our strategy.

Constraint satisfaction problems (CSP's) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments F0 for data streams.

Influence diffusion has been central to the study of the propagation of information in social networks, where influence is typically modeled as a binary property of entities: influenced or not influenced. We introduce the notion of attitude, which, as described in social psychology, is the degree by which an entity is influenced by the information. We present an information diffusion model that quantifies the degree of influence, i.e., attitude of individuals, in a social network. With this model, we formulate and study the attitude maximization problem. We prove that the function for computing attitude is monotonic and sub-modular, and the attitude maximization problem is NP-Hard. We present a greedy algorithm for maximization with an approximation guarantee of (1 - 1/e). Using the same model, we also introduce the notion of “actionable” attitude with the aim to study the scenarios where attaining individuals with high attitude is objectively more important than maximizing the attitude of the entire network. We show that the function for computing actionable attitude, unlike that for computing attitude, is non-submodular but is approximately submodular. We present an approximation algorithm for maximizing actionable attitude in a network. We experimentally evaluated our algorithms and studied empirical properties of the attitude of nodes in the network such as spatial and value distribution of high attitude nodes.

Some of the well known streaming algorithms to estimate number of triangles in a graph stream work as follows: Sample a single triangle with high enough probability and repeat this basic step to obtain a global triangle count. For example, the algorithm due to Buriol et al. (PODS 2006) uniformly at random picks a single vertex v and a single edge e and checks whether the two cross edges that connect$v$to$e$appear in the stream. Similarly, the neighborhood sampling algorithm (PVLDB 2013) attempts to sample a triangle by randomly choosing a single vertex v, a single neighbor$u$of$v$and waits for a third edge that completes the triangle. In both the algorithms, the basic sampling step is repeated multiple times to obtain an estimate for the global triangle count in the input graph stream. In this work, we propose a multi-sampling variant of these algorithms: In case of Buriol et al's algorithm, instead of randomly choosing a single vertex and edge, randomly sample multiple vertices and multiple edges and collect cross edges that connect sampled vertices to the sampled edges. In case of neighborhood sampling algorithm, randomly pick multiple edges and pick multiple neighbors of them. We provide a theoretical analysis of these algorithms and prove that these new algorithms improve upon the known space and accuracy bounds. We experimentally show that these algorithms outperform well known triangle counting streaming algorithms.

We formulate and study Constrained Influence Maximization problem where a network has two types of nodes-targets and non-targets. Given k and θ, the objective is to find a k-size seed set which maximizes the influence spread among the target nodes and keeps the number of non-targets influenced below the threshold θ. The problem, in general, is NP-hard. We also prove that obtaining a constant factor approximation algorithm for this problem is quasi-NP hard. Nevertheless, we are able to present a greedy algorithm and prove that it has certain approximation guarantees with a multiplicative factor of (1 - 1/e) and an additive error, where the latter is dependent on the underlying network structure. We evaluate the extent of the additive error on several representative social networks of varying sizes, and show that in most scenarios, the greedy algorithm indeed provides a high quality solution efficiently. We also develop a multi-greedy algorithm that attempts to keep multiple seed sets and improves upon the greedy algorithm. However, naive implementations of this algorithm is not practically viable due to prohibitively high time overhead. To address this issue, we develop a two-phase heuristic framework to improve the run times. We have conducted extensive empirical evaluation, which not only validates our algorithms, evaluates their effectiveness and efficiency, but also provides important insights on the interplay between the seed-set size, number of non-targets, the threshold, and the additive approximation error on influence-spread.

We formalize notions of triangle and open-wedge heavy-hitters in large networks. Intuitively, a node of a network G is a triangle heavy-hitter if it participates in relatively many triangles of G (analogously for open wedges). These notions have applications in social network analysis. We consider the triangle and open-wedge heavy-hitter problems: the computational problems of maintaining a set of nodes of a network that participate in many triangles and open wedges. We give sampling-based algorithms for these problems when the input network G comes as an edge stream. We prove theoretical guarantees on the quality of solutions, time and space complexity of these algorithms. This is the first work that studies the triangle and open-wedge heavy hitters problem on massive streaming networks. We evaluate the performance of our proposed algorithms by running on several real-world data sets. These experiments indicate that our algorithms efficiently detect heavy hitters while keeping both the false-positive and the false-negative errors very low.

The number of triangles in a graph is a fundamental metric widely used in social network analysis, link classification and recommendation, and more. In these applications, modern graphs of interest tend to both large and dynamic. This paper presents the design and implementation of a fast parallel algorithm for estimating the number of triangles in a massive undirected graph whose edges arrive as a stream. Our algorithm is designed for shared-memory multicore machines and can make efficient use of parallelism and the memory hierarchy. We provide theoretical guarantees on performance and accuracy, and our experiments on real-world datasets show accurate results and substantial speedups compared to an optimized sequential implementation.

This paper presents a new space-efficient algorithm for counting and sampling triangles--and more generally, constant-sized cliques--in a massive graph whose edges arrive as a stream. Compared to prior work, our algorithm yields significant improvements in the space and time complexity for these fundamental problems. Our algorithm is simple to implement and has very good practical performance on large graphs.

In many stream monitoring situations, the data arrival rate is so high that it is not even possible to observe each element of the stream. The most common solution is to sample a small fraction of the data stream and use the sample to infer properties and estimate aggregates of the original stream. However, the quantities that need to be computed on the sampled stream are often different from the original quantities of interest and their estimation requires new algorithms. We present upper and lower bounds (often matching) for estimating frequency moments, support size, entropy, and heavy hitters of the original stream from the data observed in the sampled stream.

Efficient one-pass computation of F/sub 0/, the number of distinct elements in a data stream, is a fundamental problem arising in various contexts in databases and networking. We consider the problem of efficiently estimating F/sub 0/ of a data stream where each element of the stream is an interval of integers. We present a randomized algorithm which gives an (/spl epsiv/, /spl delta/) approximation of F/sub 0/, with the following time complexity (n is the size of the universe of the items): (1) the amortized processing time per interval is O(log1//spl delta/ log n//spl epsiv/). (2) The time to answer a query for F/sub 0/ is O(log1//spl delta/). The workspace used is O(1//spl epsiv//sup 2/log1//spl delta/logn) bits. Our algorithm improves upon a previous algorithm by Bar-Yossef Kumar and Sivakumar (2002), which requires O(1//spl epsiv//sup 5/log1//spl delta/log/sup 5/n) processing time per item. Our algorithm can be used to compute the max-dominance norm of a stream of multiple signals, and significantly improves upon the current best bounds due to Cormode and Muthukrishnan (2003). This also provides efficient and novel solutions for data aggregation problems in sensor networks studied by Nath and Gibbons (2004) and Considine et. al. (2004).