Papers.

Implementing Higher-Kinded Types in Dotty

Proceedings of the 2016 7th ACM SIGPLAN Symposium on Scala

Snap, Eat, RepEat: A Food Recognition Engine for Dietary Logging

Function Passing: A Model for Typed, Distributed Functional Programming

The Power of Babble: Just Enough Consistency

Gentrification Gone too Far? Affordable 2nd-Class Values for Fun and (Co-)Effect

First-class functions dramatically increase expressiveness, at the expense of static guarantees. In ALGOL or PASCAL, functions could be passed as arguments but never escape their defining scope. Therefore, function arguments could serve as temporary access tokens or capabilities, enabling callees to perform some action, but only for the duration of the call. In modern languages, such programming patterns are no longer available. The central thrust of this paper is to re-introduce second-class functions and other values alongside first-class entities in modern languages. We formalize second-class values with stack-bounded lifetimes as an extension to simply-typed lambda calculus, and for richer type systems such as F<: and systems with path-dependent types. We generalize the binary first- vs second-class distinction to arbitrary privilege lattices, with the underlying type lattice as a special case. In this setting, abstract types naturally enable privilege parametricity. We prove type soundness and lifetime properties in Coq. We implement our system as an extension of Scala, and present several case studies.

Call graphs for languages with parametric polymorphism

The Truth, The Whole Truth, and Nothing But the Truth

The Role of Relevance in Sponsored Search

Off the Beaten Path: Let's Replace Term-Based Retrieval with k-NN Search

Retrieval pipelines commonly rely on a term-based search to obtain candidate records, which are subsequently re-ranked. Some candidates are missed by this approach, e.g., due to a vocabulary mismatch. We address this issue by replacing the term-based search with a generic k-NN retrieval algorithm, where a similarity function can take into account subtle term associations. While an exact brute-force k-NN search using this similarity function is slow, we demonstrate that an approximate algorithm can be nearly two orders of magnitude faster at the expense of only a small loss in accuracy. A retrieval pipeline using an approximate k-NN search can be more effective and efficient than the term-based pipeline. This opens up new possibilities for designing effective retrieval pipelines. Our software (including data-generating code) and derivative data based on the Stack Overflow collection is available online.

Research for practice

Functional at scale

Learning to Make Better Mistakes: Semantics-aware Visual Food Recognition

GraphFrames: an integrated API for mixing graph and relational queries

Graph data is prevalent in many domains, but it has usually required specialized engines to analyze. This design is onerous for users and precludes optimization across complete workflows. We present GraphFrames, an integrated system that lets users combine graph algorithms, pattern matching and relational queries, and optimizes work across them. GraphFrames generalize the ideas in previous graph-on-RDBMS systems, such as GraphX and Vertexica, by letting the system materialize multiple views of the graph (not just the specific triplet views in these systems) and executing both iterative algorithms and pattern matching using joins. To make applications easy to write, GraphFrames provide a concise, declarative API based on the "data frame" concept in R that can be used for both interactive queries and standalone programs. Under this API, GraphFrames use a graph-aware join optimization algorithm across the whole computation that can select from the available views. We implement GraphFrames over Spark SQL, enabling parallel execution on Spark and integration with custom code. We find that GraphFrames make it easy to express end-to-end workflows and match or exceed the performance of standalone tools, while enabling optimizations across workflow steps that cannot occur in current systems. In addition, we show that GraphFrames' view abstraction makes it easy to further speed up interactive queries by registering the appropriate view, and that the combination of graph and relational data allows for other optimizations, such as attribute-aware partitioning.

Using Navigation to Improve Recommendations in Real-Time

Implicit feedback is a key source of information for many recommendation and personalization approaches. However, using it typically requires multiple episodes of interaction and roundtrips to a recommendation engine. This adds latency and neglects the opportunity of immediate personalization for a user while the user is navigating recommendations. We propose a novel strategy to address the above problem in a principled manner. The key insight is that as we observe a user's interactions, it reveals much more information about her desires. We exploit this by inferring the within-session user intent on-the-fly based on navigation interactions, since they offer valuable clues into a user's current state of mind. Using navigation patterns and adapting recommendations in real-time creates an opportunity to provide more accurate recommendations. By prefetching a larger amount of content, this can be carried out entirely in the client (such as a browser) without added latency. We define a new Bayesian model with an efficient inference algorithm. We demonstrate significant improvements with this novel approach on a real-world, large-scale dataset from Netflix on the problem of adapting the recommendations on a user's homepage.

Past, Present, and Future of Recommender Systems: An Industry Perspective

When the Netflix Prize launched in 2006, it put a spotlight on the importance and use of recommender systems in real-world applications. The competition provided many lessons, and many more have been learned since the Grand Prize was awarded in 2009. The use of recommender systems in industry has continued to grow driven by the availability of many kinds of user data and the continued interest for the area within the research community. In this paper, we will describe what we see as the past, present, and future of recommender systems from an industry perspective.

The Exploit-Explore Dilemma in Music Recommendation

Recommending for the World

The Netflix experience is driven by a number of recommendation algorithms: personalized ranking, page generation, similarity, ratings, search, etc. On the January 6th, 2016 we simultaneously launched Netflix in 130 new countries around the world, which brought the total to over 190 countries. Preparing for such a rapid expansion while ensuring each algorithm was ready to work seamlessly created new challenges for our recommendation and search teams. In this talk, we will highlight the four most interesting challenges we encountered in making our algorithms operate globally and how this improved our ability to connect members worldwide with stories they'll love. In particular, we will dive into the problems of uneven availability across catalogs, balancing personal and cultural tastes, handling language, and tracking quality of recommendations. Uneven catalog availability is a challenge because many recommendation algorithms assume that people could interact with any item and then use the absence of interaction implicitly or explicitly as negative information in the model. However, this assumption does not hold globally and across time where item availability differs. Running algorithms globally means needing a notion of location so that we can handle local variations in taste while also providing a good basis for personalization. Language is another challenge in recommending video content because people can typically only enjoy content that has assets (audio, subtitles) in languages they understand. The preferences for how people enjoy such content also vary between people and depend on their familiarity with a language. Also, while would like our recommendations to work well for every one of our members, tracking quality becomes difficult because with so many members in so many countries speaking so many languages, it can be hard to determine when an algorithm or system is performing sub-optimally for some subset of them. Thus, to support this global launch, we exa

Static Type Checking for the Kompics Component Model: Kola - The Kompics Language

The Singular Success of SQL and Its Failure to Compete

Why SQL won inside the enterprise and yet keeps losing to purpose-built systems at the edges.

Research for Practice: Distributed Consensus and Implications of NVM on Database Management Systems

Research for practice

Social Question Answering

Community question answering (CQA) sites use a collaborative paradigm to satisfy complex information needs. Although the task of matching questions to their best answers has been tackled for more than a decade, the social question-answering practice is a complex process. The factors influencing the accuracy of question-answer matching are many and hard to disentangle. We approach the task from an application-oriented perspective, probing the space of several dimensions relevant to this problem: features, algorithms, and topics. We gather under a learning to rank framework the most extensive feature set used in literature to date, including 225 features from five different families. We test the power of such features in predicting the best answer to a question on the largest dataset from Yahoo Answers used for this task so far (40M answers) and provide a faceted analysis of the results along different topical areas and question types. We propose a novel family of distributional semantics measures that most of the time can seamlessly replace widely used linguistic similarity features, being more than one order of magnitude faster to compute and providing greater predictive power. The best feature set reaches an improvement between 11% and 26% in P@1 compared to recent well-established state-of-the-art methods.

Accelerating the Race to Autonomous Cars

XGBoost: A Scalable Tree Boosting System

Tree boosting is a highly effective and widely used machine learning method. In this paper, we describe a scalable end-to-end tree boosting system called XGBoost, which is used widely by data scientists to achieve state-of-the-art results on many machine learning challenges. We propose a novel sparsity-aware algorithm for sparse data and weighted quantile sketch for approximate tree learning. More importantly, we provide insights on cache access patterns, data compression and sharding to build a scalable tree boosting system. By combining these insights, XGBoost scales beyond billions of examples using far fewer resources than existing systems.

“Why Should I Trust You?”: Explaining the Predictions of Any Classifier

Despite widespread adoption, machine learning models remain mostly black boxes. Understanding the reasons behind predictions is, however, quite important in assessing trust, which is fundamental if one plans to take action based on a prediction, or when choosing whether to deploy a new model. Such understanding also provides insights into the model, which can be used to transform an untrustworthy model or prediction into a trustworthy one. In this work, we propose LIME, a novel explanation technique that explains the predictions of any classifier in an interpretable and faithful manner, by learning an interpretable model locally varound the prediction. We also propose a method to explain models by presenting representative individual predictions and their explanations in a non-redundant way, framing the task as a submodular optimization problem. We demonstrate the flexibility of these methods by explaining different models for text (e.g. random forests) and image classification (e.g. neural networks). We show the utility of explanations via novel experiments, both simulated and with human subjects, on various scenarios that require trust: deciding if one should trust a prediction, choosing between models, improving an untrustworthy classifier, and identifying why a classifier should not be trusted.

Matrix Computations and Optimization in Apache Spark

ModelDB: a system for machine learning model management

A Relational Framework for Information Extraction

Apache Spark: A Unified Engine for Big Data Processing

This open source computing framework unifies streaming, batch, and interactive big data workloads to unlock new applications.

Standing on Distributed Shoulders of Giants

Draws the parallel between 1980s hardware caching/pipelining tricks and today's distributed-systems tricks.

Introducing Research for Practice

Scalability and Efficiency Challenges in Large-Scale Web Search Engines

How Many Workers to Ask?: Adaptive Exploration for Collecting High Quality Labels

Crowdsourcing has been part of the IR toolbox as a cheap and fast mechanism to obtain labels for system development and evaluation. Successful deployment of crowdsourcing at scale involves adjusting many variables, a very important one being the number of workers needed per human intelligence task (HIT). We consider the crowdsourcing task of learning the answer to simple multiple-choice HITs, which are representative of many relevance experiments. In order to provide statistically significant results, one often needs to ask multiple workers to answer the same HIT. A stopping rule is an algorithm that, given a HIT, decides for any given set of worker answers to stop and output an answer or iterate and ask one more worker. In contrast to other solutions that try to estimate worker performance and answer at the same time, our approach assumes the historical performance of a worker is known and tries to estimate the HIT difficulty and answer at the same time. The difficulty of the HIT decides how much weight to give to each worker's answer. In this paper we investigate how to devise better stopping rules given workers' performance quality scores. We suggest adaptive exploration as a promising approach for scalable and automatic creation of ground truth. We conduct a data analysis on an industrial crowdsourcing platform, and use the observations from this analysis to design new stopping rules that use the workers' quality scores in a non-trivial manner. We then perform a number of experiments using real-world datasets and simulated data, showing that our algorithm performs better than other approaches.

Scalable Atomic Visibility with RAMP Transactions

Introducing research for practice

Data and algorithmic bias in the web

The Effect of Font Type on Screen Readability by People with Dyslexia

Communication lower bounds for statistical estimation problems via a distributed data processing inequality.

Introduction to Spark 2.0 for Database Researchers

The Snowflake Elastic Data Warehouse

SparkR: Scaling R Programs with Spark

R is a popular statistical programming language with a number of extensions that support data processing and machine learning tasks. However, interactive data analysis in R is usually limited as the R runtime is single threaded and can only process data sets that fit in a single machine's memory. We present SparkR, an R package that provides a frontend to Apache Spark and uses Spark's distributed computation engine to enable large scale data analysis from the R shell. We describe the main design goals of SparkR, discuss how the high-level DataFrame API enables scalable computation and present some of the key details of our implementation.

Declarative Cleaning of Inconsistencies in Information Extraction

Towards Mobile Query Auto-Completion

The Semantic Web and the Semantics of the Web: Where Does Meaning Come From?

Privacy-Preserving Mining of Sequential Association Rules from Provenance Workflows

Provenance workflows capture movement and transformation of data in complex environments, such as document management in large organizations, content generation and sharing in in social media, scientific computations, etc. Sharing and processing of provenance workflows brings numerous benefits, e.g., improving productivity in an organization, understanding social media interaction patterns, etc. However, directly sharing provenance may also disclose sensitive information such as confidential business practices, or private details about participants in a social network. We propose an algorithm that privately extracts sequential association rules from provenance workflow datasets. Finding such rules has numerous practical applications, such as capacity planning or identifying hot-spots in provenance graphs. Our approach provides good accuracy and strong privacy, by leveraging on the exponential mechanism of differential privacy. We propose an heuristic that identifies promising candidate rules and makes judicious use of the privacy budget. Experimental results show that the our approach is fast and accurate, and clearly outperforms the state-of-the-art. We also identify influential factors in improving accuracy, which helps in choosing promising directions for future improvement.

Data Portraits and Intermediary Topics

Encouraging Diversity- and Representation-Awareness in Geographically Centralized Content

Improving SQL query performance on embedded devices using pre-compilation.

NATCloud: cloud-assisted NAT-traversal service