In mining sensitive databases, access to sensitive class attributes of individual records is often prohibited by enforcing field-level security, while only aggregate class-specific statistics are allowed to be released. We consider a common privacy-preserving data analytics scenario where only a noisy sample mean of the class of interest can be queried. Such practice is widely found in medical research and business analytics settings. This paper studies the hazard of re-identification of entire class caused by revealing a noisy sample mean of the class. With a novel formulation of the re-identification attack as a generalized positive-unlabeled learning problem, we prove that the risk function of the re-identification problem is closely related to that of learning with complete data. We demonstrate that with a one-sided noisy sample mean, an effective re-identification attack can be devised with existing PU learning algorithms. We then propose a novel algorithm, growPU, that exploits the unique property of sample mean and consistently outperforms existing PU learning algorithms on the re-identification task. GrowPU achieves re-identification accuracy of 93.6% on the MNIST dataset and 88.1% on an online behavioral dataset with noiseless sample mean. With noise that guarantees 0.01-differential privacy, growPU achieves 91.9% on the MNIST dataset and 84.6% on the online behavioral dataset.

Data locality is a fundamental problem to data-parallel applications where data-processing tasks consume different amounts of time and resources at different locations. The problem is especially prominent under stressed conditions such as hot spots. While replication based on data popularity relieves hot spots due to contention for a single file, hot spots caused by skewed node popularity, due to contention for files co-located with each other, are more complex, unpredictable, hence more difficult to deal with. We propose Pandas, a light-weight acceleration engine for data-processing tasks that is robust to changes in load and skewness in node popularity. Pandas is a stochastic delay-optimal algorithm. Trace-driven experiments on Hadoop show that Pandas accelerates the data-processing phase of jobs by 11 times with hot spots and 2.4 times without hot spots over existing schedulers. When the difference in processing times due to location is large, such as applicable to the case of memory-locality, the acceleration by Pandas is 22 times.

A fundamental problem to all data-parallel applications is data locality. An example is map task scheduling in the MapReduce framework. Existing theoretical work analyzes systems with only two levels of locality, despite the existence of multiple locality levels within and across data centers. We found that going from two to three levels of locality changes the problem drastically, as a tradeoff between performance and throughput emerges. The recently proposed priority algorithm, which is throughput and heavy-traffic optimal for two locality levels, is not even throughput-optimal with three locality levels. The JSQ-MaxWeight algorithm proposed by Wang et al. is heavy-traffic optimal only for a special traffic scenario with two locality levels. We show that an extension of the JSQ-MaxWeight algorithm to three locality levels preserves its throughput-optimality, but suffers from the same lack of heavy-traffic optimality for most traffic scenarios. We propose a novel algorithm that uses Weighted-Workload (WW) routing and priority service. We establish its throughput and heavy-traffic optimality for all traffic scenarios. The main challenge is the construction of an appropriate ideal load decomposition that allows the separate treatment of different subsystems.

The prevalence of data-parallel applications has made near-data scheduling an important problem. An example is the map task scheduling in the map-reduce framework. Wang et. al. [13] was the first to identify its capacity region and proposed a throughput-optimal algorithm based on MaxWeight. However, the study of the algorithm's delay performance revealed that it is only heavy-traffic optimal for a very special traffic scenario, where all traffic concentrates on a subset of servers. We propose a simple “local-tasks first” priority algorithm and show that it is throughput-optimal and heavy-traffic optimal for all traffic scenarios, i.e., it asymptotically minimizes the average delay as the arrival rate vector approaches the boundary of the capacity region. So far, it is the only known heavy-traffic optimal algorithm for this setting. As the algorithm is based on pre-determined priority, a direct application of the Lyapunov drift technique does not work. The main proof ideas are the construction of an ideal load decomposition and the separate treatment of two subsystems based on their ideal load. To the best of our knowledge, this is the only setup of affinity scheduling where a simple priority algorithm is shown to be heavy-traffic optimal. Simulation shows that our algorithm also significantly outperforms existing algorithms at loads away from the boundary of the capacity region.

We consider a system of $N$ parallel servers, where each server consists of B units of a resource. Jobs arrive at this system according to a Poisson process, and each job stays in the system for an exponentially distributed amount of time. Each job may request different units of the resource from the system. The goal is to understand how to route arriving jobs to the servers to minimize the probability that an arriving job does not find the required amount of resource at the server, i.e., the goal is to minimize blocking probability. The motivation for this problem arises from the design of cloud computing systems in which the jobs are virtual machines (VMs) that request resources such as memory from a large pool of servers. In this paper, we consider power-of-d-choices routing, where a job is routed to the server with the largest amount of available resource among d ≥ 2 randomly chosen servers. We consider a fluid model that corresponds to the limit as N goes to infinity and provide an explicit upper bound for the equilibrium blocking probability. We show that the upper bound exhibits different behavior as B goes to infinity depending on the relationship between the total traffic intensity λ and B. In particular, if (B -- λ)/√λ → α, the upper bound is doubly exponential in √λ and if (B -- λ)/logd λ → β, β > 1, the upper bound is exponential in λ. Simulation results show that the blocking probability, even for small B, exhibits qualitatively different behavior in the two traffic regimes. This is in contrast with the result for random routing, where the blocking probability scales as O(1/√λ) even if (B -- λ)/√λ → α.

The clustering of vertices often evolves with time in a streaming graph, where graph update events are given as a stream of edge (vertex) insertions and deletions. Although a sliding window in stream processing naturally captures some cluster evolution, it alone may not be adequate, especially if the window size is large and the clustering within the windowed stream is unstable. Prior graph clustering approaches are mostly insensitive to clustering evolution. In this paper, we present an efficient approach to processing streaming graphs for evolution-aware clustering (EAC) of vertices. We incrementally manage individual connected components as clusters subject to a constraint on the maximal cluster size. For each cluster, we keep the relative recency of edges in a sorted order and favor more recent edges in clustering. We evaluate the effectiveness of EAC and compare it with a previous state-of-the-art evolution-insensitive clustering (EIC) approach. The results show that EAC is both effective and efficient in capturing evolution in a streaming graph. Moreover, we implement EAC as a streaming graph operator on IBM's InfoSphere Streams, a large-scale distributed middleware for stream processing, and show snapshots of the user cluster evolution in a streaming Twitter mention graph.

The map-reduce framework is used in many data-intensive parallel processing systems. Data locality is an important problem with map-reduce as tasks with local data complete faster than those with remote data. We propose a degree-guided task assignment algorithm, which uses very little extra information than the currently implemented Random Server algorithm. We analyze a simple version of the degree-guided algorithm, called Peeling algorithm, and the Random Server algorithm in a discrete-time model using evolution of random graphs. We characterize the thresholds below which no queueing takes place and compute the effective service rates for both algorithms. The degree-guided algorithm achieves the optimal performance in the region of practical interest and significantly outperforms the Random Server algorithm. The performance characteristics derived from discrete time model are confirmed with simulation in continuous time.

Multi-banked embedded DRAM (eDRAM) has become increasingly popular in high-performance systems. However, the data retention problem of eDRAM is exacerbated by the larger number of banks and the high-performance environment in which it is deployed: The data retention time of each memory cell decreases while the number of cells to be refreshed increases. For this, multi-bank designs offer a concurrent refresh mode, where idle banks can be refreshed concurrently during read and write operations. However, conventional techniques such as periodically scheduling refreshes---with priority given to refreshes in case of conflicts with reads or writes---have variable performance, increase read latency, and can perform poorly in worst case memory access patterns. We propose a novel refresh scheduling algorithm that is low-complexity, produces near-optimal throughput with universal guarantees, and is tolerant to bursty memory access patterns. The central idea is to decouple the scheduler into two simple-to-implement modules: one determines which cell to refresh next and the other determines when to force an idle cycle in all banks. We derive necessary and sufficient conditions to guarantee data integrity for all access patterns, with any given number of banks, rows per bank, read/write ports and data retention time. Our analysis shows that there is a tradeoff between refresh overhead and burst tolerance and characterizes this tradeoff precisely. The algorithm is shown to be near-optimal and achieves, for instance, 76.6% reduction in worst-case refresh overhead from the periodic refresh algorithm for a 250MHz eDRAM with 10us retention time and 16 banks each with 128 rows. Simulations with Apex-Map synthetic benchmarks and switch lookup table traffic show that VR can almost completely hide the refresh overhead for memory accesses with moderate-to-high multiplexing across memory banks.

Placing data as close as possible to computation is a common practice of data intensive systems, commonly referred to as the data locality problem. By analyzing existing production systems, we confirm the benefit of data locality and find that data have different popularity and varying correlation of accesses. We propose DARE, a distributed adaptive data replication algorithm that aids the scheduler to achieve better data locality. DARE solves two problems, how many replicas to allocate for each file and where to place them, using probabilistic sampling and a competitive aging algorithm independently at each node. It takes advantage of existing remote data accesses in the system and incurs no extra network usage. Using two mixed workload traces from Face book, we show that DARE improves data locality by more than 7 times with the FIFO scheduler in Hadoop and achieves more than 85% data locality for the FAIR scheduler with delay scheduling. Turnaround time and job slowdown are reduced by 19% and 25\%, respectively.

Randomized load balancing greatly improves the sharing of resources in a number of applications while being simple to implement. One model that has been extensively used to study randomized load balancing schemes is the supermarket model. In this model, jobs arrive according to a rate-nλ Poisson process at a bank of n rate-1 exponential server queues. A notable result, due to Vvedenskaya et.al. (1996), showed that when each arriving job is assigned to the shortest of d ≥ 2 randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as n to ∞. This is a substantial improvement over the case d=1, where queue sizes decay exponentially.

A novel counter architecture, called counter braids, has recently been proposed for accurate per-flow measurement on high-speed links. Inspired by sparse random graph codes, counter braids solves two central problems of per-flow measurement: one-to-one flow-to-counter association and large amount of unused counter space. It eliminates the one-to-one association by randomly hashing a flow label to multiple counters and minimizes counter space by incrementally compressing counts as they accumulate. The random hash values are reproduced offline from a list of flow labels, with which flow sizes are decoded using a fast message passing algorithm. The decoding of counter braids introduces the problem of collecting flow labels active in a measurement epoch. An exact solution to this problem is expensive. This paper complements the previous proposal with an approximate flow label collection scheme and a novel error-resilient decoder that decodes despite missing flow labels. The approximate flow label collection detects new flows with variable-length signature counting Bloom filters in SRAM, and stores flow labels in high-density DRAM. It provides a good trade-off between space and accuracy: more than 99 percent of the flows are captured with very little SRAM space. The decoding challenge posed by missing flow labels calls for a new algorithm as the original message passing decoder becomes error-prone. In terms of sparse random graph codes, the problem is equivalent to decoding with graph deficiency, a scenario beyond coding theory. The error-resilient decoder employs a new message passing algorithm that recovers most flow sizes exactly despite graph deficiency. Together, our solution achieves a 10-fold reduction in SRAM space compared to hash-table based implementations, as demonstrated with Internet trace evaluations.

In this extended abstract the authors summarize recent work they have done on the design of a novel counter architecture for estimating flow sizes in high-speed networks, the algorithms and the theory that goes along with it. This note will provide a description of the problem and our approach. It serves as a pointer to papers ([2] and [3]) which cover the design, the algorithms and the theory of Counter Braids in more detail.

Fine-grained network measurement requires routers and switches to update large arrays of counters at very high link speed (e.g. 40 Gbps). A naive algorithm needs an infeasible amount of SRAM to store both the counters and a flow-to-counter association rule, so that arriving packets can update corresponding counters at link speed. This has made accurate per-flow measurement complex and expensive, and motivated approximate methods that detect and measure only the large flows.This paper revisits the problem of accurate per-flow measurement. We present a counter architecture, called Counter Braids, inspired by sparse random graph codes. In a nutshell, Counter Braids compresses while counting. It solves the central problems (counter space and flow-to-counter association) of per-flow measurement by braiding a hierarchy of counters with random graphs. Braiding results in drastic space reduction by sharing counters among flows; and using random graphs generated on-the-fly with hash functions avoids the storage of flow-to-counter association.The Counter Braids architecture is optimal (albeit with a complex decoder) as it achieves the maximum compression rate asymptotically. For implementation, we present a low-complexity message passing decoding algorithm, which can recover flow sizes with essentially zero error. Evaluation on Internet traces demonstrates that almost all flow sizes are recovered exactly with only a few bits of counter space per flow.

Hash tables are a fundamental data structure in many network applications, including route lookups, packet classification and monitoring. Often a part of the data path, they need to operate at wire-speed. However, several associative memory accesses are needed to resolve collisions, making them slower than required. This motivates us to consider minimal perfect hashing schemes, which reduce the number of memory accesses to just 1 and are also space-efficient. Existing perfect hashing algorithms are not tailored for network applications because they take too long to construct and are hard to implement in hardware. This paper introduces a hardware-friendly scheme for minimal perfect hashing, with space requirement approaching 3.7 times the information theoretic lower bound. Our construction is several orders faster than existing perfect hashing schemes. Instead of using the traditional mapping-partitioning-searching methodology, our scheme employs a Bloom filter, which is known for its simplicity and speed. We extend our scheme to the dynamic setting, thus handling insertions and deletions