Break-out Topics and Talks

Link to

• Big Data Analytics as a Service (CSE 305)

• 11:15-11:20: Introduction and Overview, Dan Halperin
• 11:20-11:40: Communication Steps for Parallel Query Processing, Paris Koutris (PDF slides)
  

  We consider the problem of computing a relational query on a large database of size using a large number of servers. The computation is performed in rounds, and each server can receive only a limited amount of data that is controlled by a replication parameter. In this setting, we examine how many global communication steps are need to compute the query. For the case of one communication round, we establish lower bounds, and then present a 1-round algorithm that performs optimally according to our bound. For multiple rounds, we show a tradeoff between the number of rounds and the amount of replication needed. An important implication of our results is that transitive closure cannot be computed in a constant number of rounds.

• 11:40-12:00: Personalized Service Level Agreements in the Cloud, Jennifer Ortiz (PDF slides)
  

  Today's pricing models and SLAs in the Cloud are described at the level of compute resources (instance-hours or gigabytes processed) that may vary from one service to the next. Both conditions make it difficult for users to select a service, pick a configuration, and predict the actual analysis cost. To address this challenge, we propose a new abstraction, called a Personalized Service Level Agreement, where users are presented with what they can do with their data in terms of query capabilities, guaranteed query performance and fixed hourly prices.

• 12:00-12:20: MyriaX: the Myria backend execution engine, Shengliang Xu (PDF slides)
  

  MyriaX is the the Myria backend execution system built from scratch. It has a relational data model with Operators as basic processing units. It uses data streaming instead of blocking for high processing performance. Iterative data processing, which is known as one of the core requirements for scientific computing, is supported natively. The system is currently still in development. But extensive benchmarking and experimentation on MyriaX have proven that the system is highly efficient.

• Programming Languages & Software Engineering Session (CSE 403)

• 11:15-11:20: Introduction and Overview, Dan Grossman
• 11:20-11:40: Interactive Record/Replay for Debugging Web Applications, Brian Burg (PDF slides)
  

  During debugging, a developer must repeatedly and manually reproduce errant behavior in order to inspect different facets of the program’s execution. Existing behavior reproduction tools support replay via linear pause/play controls, but none is designed for interactive, random-access exploration during debugging tasks.

  We present Timelapse, a developer tool and record/replay infrastructure for disseminating and debugging behaviors in web applications. Timelapse is integrated with the browser and introduces negligible runtime overhead when capturing behaviors. Developers can use Timelapse’s user interface to interactively browse, visualize, and seek through recordings while simultaneously using familiar debugging tools such as breakpoints and logging. Testers and end-users can use it demonstrate failures in situ and share captured recordings with developers, improving bug report quality by obviating the need for detailed reproduction steps. Together, our tool and infrastructure support systematic bug reporting and debugging practices.

  Bio: Brian Burg is a Ph.D student in the Computer Science & Engineering Department at the University of Washington. He is advised by Michael Ernst and Andrew Ko. He is interested in tools, techniques and designs that help programmers understand and debug software more effectively.

• 11:40-12:00: Input-Covering Schedules for Multithreaded Programs, Tom Bergan
  

  We propose constraining multithreaded execution to small sets of input-covering schedules, which we define as follows: given a program P, we say that a set of schedules S covers all inputs of program P if, when given any input, P's execution can be constrained to some schedule in S and still produce a semantically valid result.

  Our approach is to first compute a small S for a given program P, using symbolic execution, and then, at runtime, constrain P's execution to always follow some schedule in S, and never deviate. Our approach has the following advantage: because all possible runtime schedules are known a priori, we can seek to validate the program by thoroughly verifying each schedule in S, in isolation, without needing to reason about the huge space of thread interleavings that arises due to conventional nondeterministic execution.

• 12:00-12:20: Securing Software via Design and Proof, Zach Tatlock
  

  Web browsers mediate access to valuable private data in domains ranging from health care to banking. Despite this critical role, attackers routinely exploit vulnerabilities in browser implementations to exfiltrate private data and take over the underlying system. I'll present QUARK, a browser whose kernel has been implemented and verified using Coq, a proof assistant that allows us to construct machine-checkable proofs. In particular, I'll discuss how we specify the correctness of the Quark kernel, prove that the implementation satisfies the specification, and finally show that the specification implies several security properties, including tab non-interference, cookie integrity and confidentiality, and address bar integrity.

• Reconstructing and Exploring the World, Inside and Out (CSE 691)

• 11:15-11:20: Introduction and Overview, Brian Curless
• 11:20-11:40: Real-time 3D Dense Reconstruction with Commodity Hardware, Richard Newcombe
  

  We appear to be on the verge of a transformation in how we capture the world around us! Affordable and easy-to-use real-time 3D reconstruction in unstructured environments has the potential to give our smart phones, games consoles and future household robots a sense of their spatial environment and goes some way in bridging the gap between the physical and virtual worlds we live in.

  A core problem that must be solved to obtain such live 3D reconstructions is the real-time 'Simultaneous Localisation and Mapping' (SLAM) problem that defines the need to jointly estimate where the camera or cameras are in the environment together with the environments 3D shape.

  While a number of solutions to the SLAM problem have existed for decades, in recent years a rapid rise in commodity computing power together with the availability of cheap depth cameras has accelerated the potential for non experts to make use of the technology by enabling more robust SLAM algorithms that go beyond sparse point cloud representations of the world to build dense surface models of the environment in real-time.

  I will talk about how these key commodity hardware developments together with algorithmic advances in dense SLAM algorithms have given us the ability to build 3D models of the environment in real-time, enabling applications ranging from affordable 3D object capture in unstructured environments, augmented reality with rich interactions between the real and virtual worlds and improved robot navigation.

• 11:40-12:00: The Visual Turing Test for Scene Reconstruction, Qi Shan
  

  We present the first large scale system for capturing and rendering relightable scene reconstructions from massive unstructured photo collections taken under different illumination conditions and viewpoints. We combine photos taken from many sources, Flickr-based ground-level imagery, oblique aerial views, and streetview, to recover models that are significantly more complete and detailed than previously demonstrated. We demonstrate the ability to match both the viewpoint and illumination of arbitrary input photos, enabling a Visual Turing Test in which photo and rendering are viewed side-by-side and the observer has to guess which is which. While we cannot yet fool human perception, the gap is closing.

• 12:00-12:20: 3D Wikipedia: Using Online Text to Automatically Label and Navigate Reconstructed Geometry, Bryan Russell (PDF slides)
  

  We introduce an approach for analyzing Wikipedia and other text, together with online photos, to produce annotated 3D models of famous tourist sites. The approach is completely automated, and leverages online text and photo co-occurrences via Google Image Search. It enables a number of new interactions, which we demonstrate in a new 3D visualization tool. Text can be selected to move the camera to the corresponding objects, 3D bounding boxes provide anchors back to the text describing them, and the overall narrative of the text provides a temporal guide for automatically flying through the scene to visualize the world as you read about it. We show compelling results on several major tourist sites.

• Systems and Networking 1 (CSE 305)

• 1:30-1:35: Introduction and Overview, Arvind Krishnamurthy
• 1:35-1:55: Simplifying Mobile/Cloud Applications with Sapphire, Adriana Szekeres
  

  This paper describes the motivation, architecture, and experience with Sapphire, an extensible programming system for simplifying the creation of mobile/cloud applications. Sapphire provides an integrated, distributed programming environment that bridges mobile client devices and cloud servers. A key feature of Sapphire is its separation of application logic from distributed system management and deployment logic; the programmer focuses on application-specific tasks, while a middleware management layer provides flexible support for distribution-specific tasks such as replication, caching, and failure recovery. Developers can therefore change deployment decisions without changes to their application code. The paper presents our experience building Sapphire applications and evaluates the benefits of the Sapphire approach.

• 1:55-2:15: Improving Distributed Systems using Approximate Synchrony in Datacenter Networks, Dan Ports
  

  Distributed systems are traditionally designed independently from the underlying network, making worst-case assumptions about its behavior. Such an approach is well-suited for the Internet, where one cannot predict what paths messages might take or what might happen to them along the way. However, many distributed applications are today deployed in datacenters, where the network is more reliable, predictable, and extensible. We argue that in these environments, it is possible to co-design distributed systems with their network layer, and doing so can offer substantial benefits.

  I'll describe our recent work that uses this approach to improve state machine replication protocols, which are important both as the standard mechanism for ensuring availability of critical datacenter services and as the basis for distributed storage systems. Our approach is to use network-level techniques to provide a Mostly-Ordered Multicast primitive (MOM) with a best-effort ordering property for concurrent multicast operations. We use this primitive to build Speculative Paxos, a new replication protocol that relies on the network to order requests in the normal case, while still remaining correct if messages are delivered out of order. The results are effective: Speculative Paxos provides substantially higher throughput and lower latency than the standard Paxos protocol.

• 2:15-2:35: Improving Power Efficiency Using Sensor Hubs Without Re-Coding Mobile Apps, Haichen Shen (PDF slides)
  

  In this talk, I describe MobileHub, a system that shows how unmodified mobile applications can be translated to seamlessly use sensor hubs. Sensor hubs are low-power hardware that perform sensing tasks autonomously, letting the CPU stay idle for longer. However, it is difficult for third-party applications to use these sensor hubs for their applications. Instead, MobileHub, automatically translates applications to use the sensor hub, to significantly improve power consumption. The key to our approach is to use data and control information flow tracking to learn how applications use sensor data. Based on the sensor usage pattern, we rewrite the application binary to perform efficient sensor processing on the sensor hub. We built a prototype and experiment on three applications downloaded from the Android marketplace. The results showed that MobileHub achieves power gains of up to 80%.

• Wireless and Ubicomp Session #1 (CSE 403)

• 1:30-1:35: Introduction and Overview, Shyamnath Gollakota
• 1:35-1:55: WiSee: Whole-Home Gesture Recognition Using Wireless Signals, Sidhant Gupta
  

  The last two decades has seen an exponential proliferation of Wi-Fi devices. Wi-Fi capability today is incorporated in a diverse set of devices such as smart phones, gaming consoles, and video players. In this talk, we will show how to leverage the ubiquity of Wi-Fi to enable rich sensing capabilities such as gesture recognition. Specifically, we will present WiSee, a novel gesture recognition system that leverages wireless signals to enable whole-home sensing and recognition of human gestures. Since wireless signals do not require line-of-sight and can traverse through walls, WiSee can enable whole-home gesture recognition using few wireless sources. Further, it achieves this goal without requiring instrumentation of the human body with sensing devices.

• 1:55-2:15: Ambient Backscatter: Battery-Free Communication, Aaron Parks (PDF slides)
  

  We will present the design of a communication system that enables two devices to communicate using ambient RF as the only source of power. Our approach leverages existing TV and cellular transmissions to eliminate the need for wires and batteries, thus enabling ubiquitous communication where devices can communicate among themselves at unprecedented scales and in locations that were previously inaccessible. To achieve this, we introduce ambient backscatter, a new communication primitive where devices communicate by backscattering ambient RF signals. Our design avoids the expensive process of generating radio waves; backscatter communication is orders of magnitude more power-efficient than traditional radio communication. Further, since it leverages the ambient RF signals that are already around us, it does not require a dedicated power infrastructure, as in traditional backscatter communication.

• 2:15-2:35: AllSee: Gesture Recognition For All Devices, Bryce Kellogg
  

  In this talk, we introduce AllSee, a novel gesture recognition system that consumes three to four orders of magnitude lower power than the state-of-the-art systems today. AllSee enables always-on gesture recognition on mobile devices such as smartphones and tablets. We build prototypes and demonstrate that our system can detect and classify a set of eight gestures with classification accuracies as high as 97%. We believe that these results take us closer to the vision of ubiquitous gesture interaction which can be used for computing devices, no matter how low-end and power-constrained they are.

• Center for Game Science Session (CSE 691)

• 1:30-1:43: Introduction and Overview, Zoran Popović
• 1:43-1:56: Brain Points: A Growth Mindset Incentive Structure for Educational Games, Eleanor O'Rourke (PDF slides)
  

  There is a growing interest in leveraging video games to inspire children to achieve educational goals. Games have many features that make them well-suited for learning: they can adapt to meet individual needs, provide continual feedback as students learn, and offer rich and engaging reward structures. However, educational games are not uniformly effective, and little is known about how in-game rewards affect children's ideas about intelligence and success. In this talk, we will show that the effectiveness of educational games can be increased by fundamentally changing their incentive structures to promote the growth mindset, or the belief that intelligence is malleable. We present "brain points," a system that directly rewards the growth mindset by incentivizing effort, use of strategy, and incremental progress. Through a study of 15,000 children, we show that children's motivation and persistence in the educational game Refraction is improved through the introduction of this unorthodox incentive structure. The effectiveness of this intervention stems from showing children how to practice and develop growth mindset behaviors such as effort and use of strategy through incentives.

• 1:56-2:09: A Framework for Automation of Game Progression Design, Erik Andersen
  

  Creating levels and level progressions for computer games is challenging and time-intensive, and we still lack end-to-end automation of the entire content design process. We take a step towards full automation with a general framework that can rapidly generate and classify large numbers of levels with a wide range of difficulty, systematically introduce new game mechanics as the player masters them, and decrease complexity as necessary in order to provide remediation. We present results from 2,377 Refraction players showing that our automatically assembled progression of automatically generated levels can engage players for as long as the original, expert-crafted progression. Our system provides a natural way to improve the game with data and adapt to each player.

• 2:09-2:23: Automatic Educational Experimentation with Games, Yun-En Liu (PDF slides)
  

  Running behavioral studies is often a slow and expensive process. This problem is especially acute in educational research, where finding willing participants is hard and clean experimental designs are difficult to achieve. Games and other online systems offer a new paradigm for educational research that can help alleviate these problems. By taking advantage of the much larger number of relatively inexpensive users, and the system's ability to randomize players into experimental categories, we can run complex, multi-level experiments automatically to determine the most effective educational interventions. I show how such a system, using data gathered from 45,000 players, is able to automatically experiment with different numberline representations. In the process, we discover an uncommon method of presenting numberlines that outperforms more traditional numberlines, showing the exploratory power of our automated method.

• 2:23-2:35: Data-driven Adaptivity for Educational Games, Travis Mandel (Slides)
  

  In educational video games it is often possible to provide a personalized experience for every player. This ability, if properly leveraged, could allow us to meet the needs of every student in a way that traditional education cannot. However, this adaptivity is traditionally designed by experts, and due to the extreme challenge of creating a good adaptive experience, may not be very effective. In this talk, I will discuss a data-driven machine learning approach which allows us to discover strong adaptive progressions instead of relying solely on human expertise. I will present results from a deployment of our adaptation strategies to 2,000 real students, showing how even in this challenging setting, we can use data to find an adaptive policy that outperforms expert and random baselines by over 30% on a metric of student achievement.