Papers.

Managing data transfers in computer clusters with orchestra

Cluster computing applications like MapReduce and Dryad transfer massive amounts of data between their computation stages. These transfers can have a significant impact on job performance, accounting for more than 50% of job completion times. Despite this impact, there has been relatively little work on optimizing the performance of these data transfers, with networking researchers traditionally focusing on per-flow traffic management. We address this limitation by proposing a global management architecture and a set of algorithms that (1) improve the transfer times of common communication patterns, such as broadcast and shuffle, and (2) allow scheduling policies at the transfer level, such as prioritizing a transfer over other transfers. Using a prototype implementation, we show that our solution improves broadcast completion times by up to 4.5X compared to the status quo in Hadoop. We also show that transfer-level scheduling can reduce the completion time of high-priority transfers by 1.7X.

Building a highly consumable semantic model for smarter cities

Web retrieval

Crowdsourcing for information retrieval: principles, methods, and applications

Scalable multi-dimensional user intent identification using tree structured distributions

The world according to LINQ

Big data is about more than size, and LINQ is more than up to the task.

Interpreting Relational Databases in the RDF Domain

VMFlock: Virtual Machine Co-Migration for the Cloud

Personalisation in the wild: providing personalisation across semantic, social and open-web resources

Record and Transplay: Partial Checkpointing for Replay Debugging Across Heterogeneous Systems

The SystemT IDE: an integrated development environment for information extraction rules

Information Extraction (IE)-the problem of extracting structured information from unstructured text - has become the key enabler for many enterprise applications such as semantic search, business analytics and regulatory compliance. While rule-based IE systems are widely used in practice due to their well-known "explainability," developing high-quality information extraction rules is known to be a labor-intensive and time-consuming iterative process. Our demonstration showcases SystemT IDE, the integrated development environment for SystemT, a state-of-the-art rule-based IE system from IBMResearch that has been successfully embedded in multiple IBM enterprise products. SystemT IDE facilitates the development, test and analysis of high-quality IE rules by means of sophisticated techniques, ranging from data management to machine learning. We show how to build high-quality IE annotators using a suite of tools provided by SystemT IDE, including computing data provenance, learning basic features such as regular expressions and dictionaries, and automatically refining rules based on labeled examples.

CrowdDB: answering queries with crowdsourcing

Some queries cannot be answered by machines only. Processing such queries requires human input for providing information that is missing from the database, for performing computationally difficult functions, and for matching, ranking, or aggregating results based on fuzzy criteria. CrowdDB uses human input via crowdsourcing to process queries that neither database systems nor search engines can adequately answer. It uses SQL both as a language for posing complex queries and as a way to model data. While CrowdDB leverages many aspects of traditional database systems, there are also important differences. Conceptually, a major change is that the traditional closed-world assumption for query processing does not hold for human input. From an implementation perspective, human-oriented query operators are needed to solicit, integrate and cleanse crowdsourced data. Furthermore, performance and cost depend on a number of new factors including worker affinity, training, fatigue, motivation and location. We describe the design of CrowdDB, report on an initial set of experiments using Amazon Mechanical Turk, and outline important avenues for future work in the development of crowdsourced query processing systems.

Estimating dyslexia in the web

Parallel symbolic execution for automated real-world software testing

The 1st temporal web analytics workshop (TWAW)

Distributed web retrieval

If You Have Too Much Data, then 'Good Enough' Is Good Enough

Argues that at very large scale, classic single-truth relational semantics give way to approximate, loosely-coupled and eventually-consistent answers - and that this is usually acceptable.

Finding social roles in Wikipedia

Efficient online ad serving in a display advertising exchange

Batch query processing for web search engines

Web retrieval

Crowdsourcing 101: putting the WSDM of crowds to work for you

Crowdsourcing has emerged in recent years as an exciting new avenue for leveraging the tremendous potential and resources of today's digitally-connected, diverse, distributed workforce. Generally speaking, crowdsourcing describes outsourcing of tasks to a large group of people instead of assigning such tasks to an in-house employee or contractor. Crowdsourcing platforms such as Amazon Mechanical Turk and CrowdFlower have gained particular attention as active online market places for reaching and tapping into this glut of a still largely under-utilized workforce. Crowdsourcing offers intriguing new opportunities for accomplishing different kinds of tasks or achieving broader participation than previously possible, as well as completing standard tasks more accurately in less time and at lower cost. Unlocking the potential of crowdsourcing in practice, however, requires a tri-partite understanding of principles, platforms, and best practices. This tutorial will introduce the opportunities and challenges of crowdsourcing while discussing the three issues above. This will provide attendees with a basic foundation to begin applying crowdsourcing in the context of their own particular tasks.

A co-relational model of data for large shared data banks

Contrary to popular belief, SQL and noSQL are really just two sides of the same coin.

Massive multiplayer human computation for fun, money, and survival

Discovery and Preclinical Validation of Drug Indications Using Compendia of Public Gene Expression Data

Unequal channel error protection of multiple description codes for wireless media streaming

The Hybrid Reciprocal Velocity Obstacle

We present the hybrid reciprocal velocity obstacle for collision-free and oscillation-free navigation of multiple mobile robots or virtual agents. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to compute their future trajectories in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots sense their surroundings as well and change their trajectories accordingly. We apply hybrid reciprocal velocity obstacles to iRobot Create mobile robots and demonstrate direct, collision-free, and oscillation-free navigation.

Modeling Unconnectable Peers in Private BitTorrent Communities

Using Social Sensing to Understand the Links between Sleep, Mood, and Sociability

Litter: A Lightweight Peer-to-Peer Microblogging Service

Group-in-a-Box Layout for Multi-faceted Analysis of Communities

Regulating Locality vs. Parallelism Tradeoffs in Multiple Memory Controller Environments

The presence of multiple MCs and their integration into the on-chip network fabric creates a highly concurrent system that can support significant levels of memory level parallelism (MLP) across cores. This work exposes the trade-off between DRAM parameters, bank level parallelism (BLP), and row buffer hit rate that exposes the amount of effective BLP that is necessary to approximate a 100% hit rate. We further study how this trade-off can be controlled and propose a class of global (system) and local (within an MC) address mappings that can be tuned to optimize the performance across a set of multiprogrammed benchmarks.

Inter-swarm resource allocation in BitTorrent communities

Fast download but eternal seeding: The reward and punishment of Sharing Ratio Enforcement

Identifying, analyzing, and modeling flashcrowds in BitTorrent

Tribler: Search and stream

Temporal classification of events in cricket videos

Implementing Domain-Specific Languages for Heterogeneous Parallel Computing

Domain-specific languages offer a solution to the performance and the productivity issues in heterogeneous computing systems. The Delite compiler framework simplifies the process of building embedded parallel DSLs. DSL developers can implement domain-specific operations by extending the DSL framework, which provides static optimizations and code generation for heterogeneous hardware. The Delite runtime automatically schedules and executes DSL operations on heterogeneous hardware.

Scala Web Frameworks: Looking Beyond Lift

GLive: The Gradient Overlay as a Market Maker for Mesh-Based P2P Live Streaming

Deftpack: A Robust Piece-Picking Algorithm for Scalable Video Coding in P2P Systems

Enhanced Visual Scene Understanding through Human-Robot Dialog

Betweenness Centrality Approximations for an Internet Deployed P2P Reputation System

Parallel Processing Framework on a P2P System Using Map and Reduce Primitives

Network warehouses: Efficient information distribution to mobile users

We consider the problem of distributing time-sensitive information from a collection of sources to mobile users traversing a wireless mesh network. Our strategy is to distributively select a set of well-placed nodes (warehouses) to act as intermediaries between the information sources and clusters of users. Warehouses are selected via the distributed construction of Hierarchical Well-Separated Trees (HSTs), which are sparse structures that induce a natural spatial clustering of the network. Unlike many traditional multicast protocols, our approach is not data driven. Rather, it is agnostic to the number and position of sources as well as to the mobility patterns of users. Whereas source-rooted tree multicast algorithms construct a separate routing infrastructure to support each source, our sparse and flexible infrastructure is precomputed and efficiently reused by sources and users, its cost amortized over time. Moreover, the route acquisition delay inherent in on-demand wireless ad hoc network protocols is avoided by exploiting the HST addressing scheme. Our algorithm ensures with high probability a guaranteed stretch bound for the information delivery path, and is robust to lossy links and node failure by providing alternative HST-induced routes. Nearby users are clustered and their requests aggregated, further reducing communication overhead.

Sleep, mood and sociability in a healthy population

Racetrack memory cell array with integrated magnetic tunnel junction readout

Reciprocal collision avoidance with acceleration-velocity obstacles

We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles [3], we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles.

COMET: A Recipe for Learning and Using Large Ensembles on Massive Data

COMET is a single-pass MapReduce algorithm for learning on large-scale data. It builds multiple random forest ensembles on distributed blocks of data and merges them into a mega-ensemble. This approach is appropriate when learning from massive-scale data that is too large to fit on a single machine. To get the best accuracy, IVoting should be used instead of bagging to generate the training subset for each decision tree in the random forest. Experiments with two large datasets (5GB and 50GB compressed) show that COMET compares favorably (in both accuracy and training time) to learning on a sub sample of data using a serial algorithm. Finally, we propose a new Gaussian approach for lazy ensemble evaluation which dynamically decides how many ensemble members to evaluate per data point, this can reduce evaluation cost by 100X or more.

Selectivity estimation for extraction operators over text data