Modern approaches for multiparty secure collaboration must strike the right balance between rich analytics and requisite data privacy guarantees, especially in the face of new regulations.While cryptographic technologies such as fully homomorphic encryption (FHE) and secure multiparty computation (MPC) provide strong, provable security guarantees as standalone tools, deploying them in practice throws up a myriad of challenges, including usability constraints and lack of precise specification of privacy guarantees.In this work, we propose a novel framework for real-world deployment of cryptographic privacy preserving techniques that achieves the twin goals of practical usability in real-world setting and provable privacy guarantees from users' perspective.To this end, we formalize the notion of a secure computation platform (SCP) for privacy preserving data collaboration, and introduce a model for precise specification of privacy guarantees for multiparty workflows.We then describe abstractions of a set of cryptoprimitives, that are usable by non-experts in cryptography.We present two demo workflows that empirically validate our claims, and serve as potential building blocks for the development of squeaky-clean data rooms with practical performance and privacy guarantees.

To address the classical selectivity estimation problem for OLAP queries in relational databases, a radically different approach calledPlanBouquetwas recently proposed in[1], wherein the estimation process is completely abandoned and replaced with a calibrated discovery mechanism. The beneficial outcome of this new construction is that provable guarantees on worst-case performance, measured as Maximum Sub-Optimality (MSO), are obtained thereby facilitating robust query processing. ThePlanBouquetformulation suffers, however, from a systemic drawback—the MSO bound is a function of not only the query, but also the optimizer's behavioral profile over the underlying database platform. As a result, there are adverse consequences: (i) the bound value becomes highly variable, depending on the specifics of the current operating environment, and (ii) it becomes infeasible to compute the value without substantial investments in preprocessing overheads. In this paper, we first presentSpillBound, a new query processing algorithm that retains the core strength of thePlanBouquetdiscovery process, but reduces the bound dependency to only the query. It does so by incorporating plan termination and selectivity monitoring mechanisms in the database engine. Specifically,SpillBounddelivers a worst-case multiplicative bound, of$D^2+3D$, where$D$is simply the number of error-prone predicates in the user query. Consequently, the bound value becomes independent of the optimizer and the database platform, and the guarantee can be issued simply by query inspection. We go on to prove thatSpillBoundis within an$O(D)$factor of thebest possibledeterministic selectivity discovery algorithm in its class. We next devise techniques to bridge this quadratic-to-linear MSO gap by introducing the notion ofcontour alignment, a characterization of the nature of plan structures along theboundariesof the selectivity space. Specifically, we propose a variant ofSpillBound, calledAlignedBound, which exploits the alignment property and provides a guarantee in the range$\mathbf {[2D+2,D^2+3D]}$. Finally, a detailed empirical evaluation over the standard decision-support benchmarks indicates that: (i)SpillBoundprovides markedly superior performance w.r.t. MSO as compared toPlanBouquet, and (ii)AlignedBoundprovides additional benefits for query instances that are challenging forSpillBound, often coming close to the ideal of MSO linearity in$D$. From an absolute perspective,AlignedBoundevaluates virtually all the benchmark queries considered in our study with MSO of around10or lesser. Therefore, in an overall sense,SpillBoundandAlignedBoundoffer a substantive step forward in the long-standing quest for robust query processing.

To address the classical selectivity estimation problem in database systems, a radically different query processing technique called PlanBouquet was proposed in 2014. In this approach, the estimation process is completely abandoned and replaced with a calibrated selectivity discovery mechanism. The beneficial outcome is that provable guarantees are obtained on worst-case execution performance, thereby facilitating robust query processing. An improved version of PlanBouquet, called SpillBound (SB), which significantly accelerates the selectivity discovery process, and provides platform-independent performance guarantees, was presented two years ago.

To address the classical selectivity estimation problem in databases, a radically different approach called PlanBouquet was recently proposed in [3], wherein the estimation process is completely abandoned and replaced with a calibrated discovery mechanism. The beneficial outcome of this new construction is that, for the first time, provable guarantees are obtained on worst-case performance, thereby facilitating robust query processing.

Motivated by scheduling scenarios in large shared computing systems, we study the problem of reusable resource scheduling. In this problem, there are many resources, each specified by a capacity, duration, per-use cost, and an availability window comprising of a release time and a deadline. A resources can be reused multiple times within its availability window with each use being limited by the duration associated with the resource and incurring cost equal to per-use cost. Different uses of a resource have to be non-overlapping. Given a demand profile, the goal is to cover it by scheduling the resources within their availability windows while minimizing their total cost. Reusable resource scheduling is a generalization of the well known interval covering problem. We present approximation algorithms and hardness results for the reusable resource scheduling problem. While the interval cover problem is NP-hard, it can be solved optimally for the special case where all the resources have unit capacities. In contrast, we show that the reusable resource scheduling is NP-hard and APX-hard, even for the case where the resources have unit capacities and unit costs. The approximation algorithms are derived by considering the notion of colored interval coloring, which could be of independent interest.

Various industries are turning to social media to identify key influencers on topics of interest. Following this trend, the All England Lawn Tennis and Croquet Club (AELTC) is keen to analyze the `social pulse' around the famous Wimbledon Championships. IBM developed and deployed social influence analysis capability for AELTC during the 2014 edition of the Championship. The design and implementation of influence analysis technology in the real world involves several challenges. In this paper, we define various functional and usability criteria that social influence scores should satisfy, and propose a multi-dimensional definition of influence that satisfies these criteria. We highlight the need to identify both all-time influencers and recent influencers, and track user influences over multiple time-scales for this purpose. We also stress the importance of aspect-specific influence analysis, and investigate an approach that uses an aspect hierarchy that annotates tweets with topics or aspects before analyzing them for influence. We also describe interesting insights discovered by our tool and the lessons that we learnt from this engagement.

There are many diverse domains like academic collaboration, service industry, and movies, where a group of agents are involved in a set of activities through interactions or collaborations to create value. The end result of the value creation process is two pronged: firstly, there is a cumulative value created due to the interactions and secondly, a network that captures the pattern of historical interactions between the agents. In this paper we summarize our efforts towards design and analysis of value creation networks: 1) network representation of interactions and value creations, 2) identify contribution of a node based on values created from various activities, and 3) ranking nodes based on structural properties of interactions and the resulting values. To highlight the efficacy of our proposed algorithms, we present results on IMDB and services industry data.

The problem of ordering a set of entities which contain inherent ties among them arises in many applications. Notion of “bucket order” has emerged as a popular mechanism of ranking in such settings. A bucket order is an ordered partition of the set of entities into “buckets”. There is a total order on the buckets, but the entities within a bucket are treated as tied. In this paper, we focus on discovering bucket order from data captured in the form of user preferences. We consider two settings: one in which the discrepancies in the input preferences are “local” (when collected from experts) and the other in which discrepancies could be arbitrary (when collected from a large population). We present a formal model to capture the setting of local discrepancies and consider the following question: “how many experts need to be queried to discover the underlying bucket order on n entities?”. We prove an upperbound of . In the case of arbitrary discrepancies, we model it as the bucket order problem of discovering a bucket order that best fits the data (captured as pairwise preference statistics). We present a new approach which exploits a connection between the discovery of buckets and the correlation clustering problem. We present empirical evaluation of our algorithms on real and artificially generated datasets.

We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O ( r K ⋅ log N ), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value r K is a suitably defined Ramsey number, which is at most log K . We show that it is NP-hard to approximate the problem within a factor of Ω(log N ), even for binary tables (i.e., K =2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r 2 =2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdös.

In this paper, we present a novel ranking technique that we developed in the context of an application that arose in a Service Delivery setting. We consider the problem of ranking agents of a service organization. The service agents typically need to interact with other service agents to accomplish the end goal of resolving customer requests. Their ranking needs to take into account two aspects: firstly, their importance in the network structure that arises as a result of their interactions, and secondly, the value generated by the interactions involving them. We highlight several other applications which have the common theme of ranking the participants of a value creation process based on the network structure of their interactions and the value generated by their interactions. We formally present the problem and describe the modeling technique which enables us to encode the value of interaction in the graph. Our ranking algorithm is based on extension of eigen value methods. We present experimental results on real-life, public domain datasets from the Internet Movie DataBase. This makes our experiments replicable and verifiable.

The maximum independent set problem (MaxIS) on general graphs is known to be NP-hard to approximate within a factor of $n^{1-epsilon}$, for any $epsilon > 0$. However, there are many ``easy" classes of graphs on which the problem can be solved in polynomial time. In this context, an interesting question is that of computing the maximum independent set in a graph that can be expressed as the union of a small number of graphs from an easy class. The MaxIS problem has been studied on unions of interval graphs and chordal graphs. We study the MaxIS problem on unions of perfect graphs (which generalize the above two classes). We present an $O(sqrt{n})$-approximation algorithm when the input graph is the union of two perfect graphs. We also show that the MaxIS problem on unions of two comparability graphs (a subclass of perfect graphs) cannot be approximated within any constant factor.

We consider the problem of scheduling jobs on a pool of machines. Each job requires multiple machines on which it executes in parallel. For each job, the input specifies release time, deadline, processing time, profit and the number of machines required. The total number of machines may be different at different points of time. A feasible solution is a subset of jobs and a schedule for them such that at any timeslot, the total number of machines required by the jobs active at the timeslot does not exceed the number of machines available at that timeslot. We present an O(log(Bmax/Bmin))-approximation algorithm, where Bmaxand Bminare the maximum and minimum available bandwidth (maximum and minimum number of machines available over all the timeslots). Our algorithm and the approximation ratio are applicable for more a general problem that we call the Varying bandwidth resource allocation problem with bag constraints (BAGVBRAP). The BAGVBRAP problem is a generalization of some previously studied scheduling and resource allocation problems.

In this paper, we present a comprehensive theoretical analysis of the sampling technique for the association rule mining problem. Most of the previous works have concentrated only on the empirical evaluation of the effectiveness of sampling for the step of finding frequent itemsets. To the best of our knowledge, a theoretical framework to analyze the quality of the solutions obtained by sampling has not been studied. Our contributions are two-fold. First, we present the notions of ε-close frequent itemset mining and ε-close association rule mining that help assess the quality of the solutions obtained by sampling. Secondly, we show that both the frequent items mining and association rule mining problems can be solved satisfactorily with a sample size that is independent of both the number of transactions size and the number of items. Let θ be the required support, ε the closeness parameter, and 1/h the desired bound on the probability of failure. We show that the sampling based analysis succeeds in solving both ε-close frequent itemset mining and ε-close association rule mining with a probability of at least (1 - 1/h) with a sample of size S = O(1/ε2θ [Δ + log h/(1 - ε)θ]), where Δ is the maximum number of items present in any transaction. Thus, we establish that it is possible to speed up the entire process of association rule mining for massive databases by working with a small sample while retaining any desired degree of accuracy. Our work gives a comprehensive explanation for the well known empirical successes of sampling for association rule mining.

One of the distinguishing features of the services industry is the high emphasis on people interacting with other people and serving customers rather than transforming physical goods like in the traditional manufacturing processes. It is evident that analysis of such interactions is an essential aspect of designing effective and efficient services delivery. In this work we focus on learning individual and team behavior of different people or agents of a service organization by studying the patterns and outcomes of historical interactions. For each past interaction, we assume that only the list of participants and an outcome indicating the overall effectiveness of the interaction are known. Note that this offers limited information on the mutual (pairwise) compatibility of different participants. We develop the notion of service interaction networks which is an abstraction of the historical data and allows one to cast practical problems in a formal setting. We identify the unique characteristics of analyzing service interaction networks when compared to traditional analyses considered in social network analysis and establish a need for new modeling and algorithmic techniques for such networks. On the algorithmic front, we develop new algorithms to infer attributes of agents individually and in team settings. Our first algorithm is based on a novel modification to the eigen-vector based centrality for ranking the agents and the second algorithm is an iterative update technique that can be applied for subsets of agents as well. One of the challenges of conducting research in this setting is the sensitive and proprietary nature of the data. Therefore, there is a need for a realistic simulator for studying service interaction networks. We present the initial version of our simulator that is geared to capture several characteristics of service interaction networks that arise in real-life.

We consider the problem of constructing decision trees for entity identification from a given relational table. The input is a table containing information about a set of entities over a fixed set of attributes and a probability distribution over the set of entities that specifies the likelihood of the occurrence of each entity. The goal is to construct a decision tree that identifies each entity unambiguously by testing the attribute values such that the average number of tests is minimized. This classical problem finds such diverse applications as efficient fault detection, species identification in biology, and efficient diagnosis in the field of medicine. Prior work mainly deals with the special case where the input table is binary and the probability distribution over the set of entities is uniform. We study the general problem involving arbitrary input tables and arbitrary probability distributions over the set of entities. We consider a natural greedy algorithm and prove an approximation guarantee of O(rK • log N), where N is the number of entities and K is the maximum number of distinct values of an attribute. The value rK is a suitably defined Ramsey number, which is at most log K. We show that it is NP-hard to approximate the problem within a factor of Ω(log N), even for binary tables (i.e. K=2). Thus, for the case of binary tables, our approximation algorithm is optimal up to constant factors (since r2=2). In addition, our analysis indicates a possible way of resolving a Ramsey-theoretic conjecture by Erdos.

We analyze local search heuristics for the metric k-median and facility location problems. We define the locality gap of a local search procedure for a minimization problem as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of 5. Furthermore, if we permit up to p facilities to be swapped simultaneously, then the locality gap is 3+2/p. This is the first analysis of a local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For uncapacitated facility location, we show that local search, which permits adding, dropping, and swapping a facility, has a locality gap of 3. This improves the bound of 5 given by M. Korupolu, C. Plaxton, and R. Rajaraman [Analysis of a Local Search Heuristic for Facility Location Problems, Technical Report 98-30, DIMACS, 1998]. We also consider a capacitated facility location problem where each facility has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new local search operation which opens one or more copies of a facility and drops zero or more facilities. We prove that this local search has a locality gap between 3 and 4.

This paper gives an overview of the BlueGene/L Supercomputer. This is a jointly funded research partnership between IBM and the Lawrence Livermore National Laboratory as part of the United States Department of Energy ASCI Advanced Architecture Research Program. Application performance and scaling studies have recently been initiated with partners at a number of academic and government institutions,including the San Diego Supercomputer Center and the California Institute of Technology. This massively parallel system of 65,536 nodes is based on a new architecture that exploits system-on-a-chip technology to deliver target peak processing power of 360 teraFLOPS (trillion floating-point operations per second). The machine is scheduled to be operational in the 2004-2005 time frame, at price/performance and power consumption/performance targets unobtainable with conventional architectures.

In this paper, we analyze local search heuristics for the k-median and facility location problems. We define the {\em locality gap\/} of a local search procedure as the maximum ratio of a locally optimum solution (obtained using this procedure) to the global optimum. For k-median, we show that local search with swaps has a locality gap of exactly 5. When we permit p facilities to be swapped simultaneously then the locality gap of the local search procedure is exactly 3+2/p. This is the first analysis of local search for k-median that provides a bounded performance guarantee with only k medians. This also improves the previous known 4 approximation for this problem. For Uncapacitated facility location, we show that local search, which permits adding, dropping and swapping a facility, has a locality gap of exactly 3. This improves the 5 bound of Korupolu et al. We also consider a capacitated facility location problem where each facilitym has a capacity and we are allowed to open multiple copies of a facility. For this problem we introduce a new operation which opens one or more copies of a facility and drops zero or more facilities. We prove that local search which permits this new operation has a locality gap between 3 and 4.