-
Don Syme, Kenji Takeda, and Keith Battocchi (Microsoft Research)
We live in an information society. Programming languages are not designed for this. As we move into a world of “Devices + Services”, it is vital that developers can productively integrate information at internet-scale into their everyday programming environment. Effectively exploring, navigating, understanding, analysing and presenting data – both big and broad – is a key to success for developers. Current experiences for this are cumbersome & labour-intensive. In this new demo we explain the latest research behind F# Type Providers and show how they can bring Internet-Scale Metadata to the fingers of developers. IntelliSense for Internet-Scale Metadata creates a completely new way of rapidly developing applications on Azure, when using Hadoop, and when programming against the web. We explain how this can transform F# into a uniquely powerful and developer-friendly Data Science scripting language for Azure.
-
Frank McSherry, Derek Murray, Rebecca Isaacs, and Michael Isard (Microsoft Research)
We are developing a system for scalable data analysis designed to support iterative queries over continuously changing inputs at interactive timescales. The system is based on a new computational framework, differential dataflow, that generalizes standard incremental dataflow for far greater reuse of previous results when collections change. Differential dataflow distinguishes between the multiple reasons a collection might change, including both loop feedback and new input data, allowing a system to re-use the most appropriate results from previously performed work when an incremental update arrives.
Our prototype system, Naiad, demonstrates the practical application of differential dataflow. Like many systems, Naiad supports high-level declarative queries, data-parallel execution, and transparent distribution. Unlike other systems, Naiad efficiently executes queries with multiple (possibly nested) loops, while simultaneously responding with low latency to incremental changes to the inputs. We show how differential dataflow enables orders of magnitude speedups for a variety of complex workloads on real streaming data.
-
Dan Alistarh (MIT), James Aspnes (Yale University), Michael A. Bender (Stony Brook University), Rati Gelashvili (MIT), and Seth Gilbert (NUS)
Task allocation is a classic distributed problem in which a set of p potentially faulty processes must perform a set of m tasks. The problem is all the more challenging when there is heterogeneity, either on the workers’ side, since individual agents may have varying speed and robustness, or because of uneven workloads. In large-scale systems, heterogeneity is the norm. Our work considers the dynamic version of task allocation, in which tasks are injected adversarially during an asynchronous execution. Intuitively, a major challenge in this setting is the fact that, at the same time, the adversary controls scheduling, process crashes, and the input.
We give a new shared-memory algorithm for dynamic task allocation which is within logarithmic factors of optimal. The main algorithmic idea is a randomized data structure called a dynamic to-do tree, which allows processes to pick new tasks to perform uniformly at random from the set of available tasks, and to insert tasks at uniform random locations in the data structure. We show that these properties avoid duplicating work unnecessarily in well-behaved executions, and that work duplication is inherent under certain input-schedule combinations. This is the first algorithm to allow efficient work sharing in this challenging setting, and the result has applications to other problems, such as producer-consumer buffers, and distributed renaming.
-
Eiko Yoneki (University of Cambridge), Karthik Nilakant (University of Cambridge), Valentin Dalibard (University of Cambridge), and Amitabha Roy (EPFL)
Mining large graphs has now become an important aspect of multiple diverse applications and a number of computer systems have been proposed to efficiently execute graph algorithms. Recent interest in this area has led to the construction of single machine graph computation systems that use solid state drives (SSDs) to store the graph. This approach reduces the cost and simplifies the implementation of graph algorithms, making computations on large graphs available to the average user. However, SSDs are slower than main memory, and making full use of their bandwidth is crucial for executing graph algorithms in a reasonable amount of time. We present RASP (the (R)un(A)head (S)SD(P)refetcher) for graph algorithms that parallelises requests to derive maximum throughput from SSDs. RASP combines a judicious distribution of graph state between main memory and SSDs with an innovative run-ahead algorithm to prefetch needed data in parallel. This is in contrast to existing approaches that depend on multi-threading the graph algorithms to saturate available bandwidth. Our experiments on graph algorithms using random access
show that RASP not only is capable of maximising the throughput from SSDs but is also able to almost hide the effect of I/O latency. The improvements in runtime for graph algorithms is up to 14 X when compared to a single threaded baseline. When compared to sophisticated multi-threaded implementations, RASP performs up to 80% faster without the program complexity and the programmer effort needed for multithreaded graph algorithms.
-
Karthik Nilakant (University of Cambridge) and Eiko Yoneki (University of Cambridge)
Graph processing systems are subject to two conflicting concerns: firstly, a large number of algorithms for processing graphs exist, most of which exhibit poor locality of accesses. Secondly, the increasing scale of data has resulted in a need to distribute the data across multiple machines, further affecting locality. Most existing systems tend to consider these factors separately. We propose schemes for pro-active or reactive active graph management. Pro-actively, one could instrument algorithmic code fragments to allow the processing engine to predict future behaviour of the graph algorithm. Producing “balanced cuts” on a graph is computationally expensive, and infeasible for large datasets. Instead, lightweight graph analytics could be deployed to re-arrange the graph into less tightly coupled clusters. We propose a framework for considering these factors in unison. Ultimately, the choice of method to use in a given scenario will depend on the structure of the dataset and the processing algorithm. Our focus will be on identifying the minimum characteristics that must be gleaned from the code or data to be processed (or alternatively provided by the user), in order to boost the performance of such a system.
-
Aleksandar Dragojevic, Dushyanth Narayanan, Orion Hodson, Miguel Castro (Microsoft Research)
Two hardware trends present a great opportunity for building efficient infrastructure for real-time analytics: (1) servers today have tens to hundreds of gigabytes of RAM making it possible to keep large data sets in RAM of a moderately-sized cluster of servers and (2) modern cluster networks, such as InfiniBand and RoCE, support access to memory of remote servers with just a few micro-seconds of latency. By keeping the whole data set in main memory of a cluster and using direct remote memory access (RDMA) primitives of the network it is possible to support tens to hundreds of millions of point lookups in a terabyte-scale key-value store on a cluster of just several tens of servers.
We present Farm, a platform for building infrastructure for supporting in-memory applications that efficiently use modern cluster networks. Farm exposes the memory of all servers in a cluster as a single, fault-tolerant shared memory; it supports atomic reads and writes of small user-defined objects, efficient short transactions for easier synchronization, and exposes the location of objects to support locality-aware optimizations. We describe how to use Farm to build efficient and scalable B-trees and hashtables, which can be used as key-value stores or building blocks for more complex systems.
-
Florian Bourse (Ecole Normale Supérieure, Paris), Marc Lelarge (INRIA- Ecole Normale Supérieure, Paris), and Milan Vojnovic (Microsoft Research)
Many computation tasks are performed on large scale graph data which may amount to as many as billions or even trillions of vertices or edges (e.g. online social network graphs, knowledge graphs, and web graphs). A standard way to scale up such computations is to partition an input graph into clusters of balanced sizes and small cut costs. Graph partitioning is of interest for a wide range of systems including iterative computation platforms, distributed graph databases, and stream processing platforms. Besides its practical importance, graph partitioning is one of the most fundamental and challenging theoretical computer science problems.
In our work we consider novel graph partitioning problems that arise under some computation models of interest — which specify how the size of a cluster and the cost of a cut are defined. We devote special focus to online assignment algorithms that require a single pass through vertices or edges. Our preliminary performance evaluation results demonstrate significant benefits of using graph partitioning algorithms that are specifically tailored for given computation model.
This is a collaboration project with MSR-INRIA joint research centre.
-
Eirini Spyropoulou (University of Bristol) and Tijl De Bie (University of Bristol)
Research on local pattern mining algorithms has focused for years on mining one table of transactions and items (market basket data). However, a large amount of real-world datasets are multi-relational, i.e., they contain more than two entities and more than one relationships. There is therefore increasing interest in developing techniques for mining such complex types of data. Defining a multi-relational pattern syntax that is suitably expressive and finding an efficient mining algorithm, is a challenging problem. Furthermore, since local pattern mining methods usually suffer from the combinatorial explosion of patterns in the output, assessing the quality of patterns is also very important in order to make them useful to the end user.
In this work we introduce a novel approach for mining patterns in multi-relational data. We propose the pattern syntax of Complete Connected Subsets, a new syntax for multi-relational patterns. While this pattern syntax is generally applicable to multi-relational data it reduces to well known itemsets when the data is a simple transaction table. We also introduce RMiner, a simple yet practically efficient algorithm to mine such patterns. We show how the interestingness of patterns of the proposed syntax can be conveniently quantified using a framework for quantifying the subjective interestingness of patterns according to the user’s prior knowledge. Finally, we present results on real world data sets.