Dean's Fellows Lecture Series

The Dean's Fellows Lecture Series is a series of talks about research that has been done by people in our department. In conjunction with the CS department's coffee hour, the lectures will be given at the ISR seminar room (AVW 1146) next to the Grad Student Lounge from 3:30pm to 4pm on Wednesdays. (That is, talks will start halfway through the coffee hour.)

Past Talks

Abstracts

New, high-throughput sequencing technologies have made it feasible to cheaply generate vast amounts of sequence information from a genome of interest. The computational reconstruction of the complete sequence of a genome is complicated by specific features of these new sequencing technologies, such as the short length of the sequencing reads and absence of mate-pair information. Here we propose methods to overcome such limitations by incorporating information from optical restriction maps.

During my talk I will provide a brief overview of the biological relevance of this problem and an introduction to the relevant terms and outline our computational solution.

This work is joint with Niranjan Nagarajan (post-doctoral fellow in my lab) and Timothy Read (Naval Medical Research Center).

With the availability of affordable new desktop fabrication techniques such as 3D printing and laser cutting, physical models are used increasingly often during the architectural and industrial design cycle. Models can easily be annotated to capture comments, edits and other forms of feedback. Unfortunately, these annotations remain in the physical world and cannot be easily transferred back to the digital world. Here we present a simple solution to this problem based on a tracking pattern printed on the surface of each model. Our solution is inexpensive, requires no tracking infrastructure or per object calibration, and can be used in the field without a computer nearby. It lets users not only capture annotations, but also edit the model using a simple yet versatile command system. Once captured, annotations and edits are merged into the original CAD models. There they can be easily edited or further refined. We present the design of a SolidWorks plug-in implementing this concept, and report initial feedback from potential users using our prototype. We also present how this prototype could be extended seamlessly to a fully functional system using current 3D printing technology.

In this paper, we address the problem of extending a relational database system to facilitate efficient real-time application of dynamic probabilistic models to streaming data. We use the recently proposed abstraction of model-based views for this purpose, by allowing users to declaratively specify the model to be applied, and by presenting the output of the models to the user as a probabilistic database view. We support declarative querying over such views using an extended version of SQL that allows for querying probabilistic data. Underneath we use particle filters, a class of sequential Monte Carlo algorithms, commonly used to implement dynamic probabilistic models, to represent the present and historical states of the model as sets of weighted samples (particles) that are kept up-to-date as new data arrives. We develop novel techniques to convert the queries on the model-based view directly into queries over particle tables, enabling highly efficient query processing. Finally, we present experimental evaluation of our prototype implementation that demonstrates the feasibility of online modeling of streaming data using our system and establishes the advantages of tight integration between dynamic probabilistic models and databases.

A similarity join takes two sets of points A, B and returns pairs p ∈ A, q ∈ B where the distance D(p,q) ≤ ε. The similarity join is a common database operation with many applications. An algorithm named LSS is presented that executes on a graphics processing unit (GPU), taking advantage of the GPU's parallelism and large data throughput. To achieve peak efficiency, LSS relies only on simple primitive operations that execute quickly on the GPU, such as the sorting and searching of arrays. It recasts the similarity join as a sort-and-search problem by mapping its input datasets onto a set of space-filling curves, generated by a parallel sort routine on the GPU. It then searches small intervals of these curves that are guaranteed to contain all pairs of the correct result. LSS offers a balance between time and work efficiencies and is shown to perform well when compared against existing prominent high-dimensional similarity join methods.

Students and researchers who attended the CRA Academic Careers Workshop on Feb. 25-26, 2008 will distill 1.5 days of lectures into 30 minutes of highly concentrated advice on how to succeed in academia. The topics and speakers will be (not necessarily in this order):

• Career networking (Jaymie Strecker)
• Grant writing (Dov Gordon)
• Interacting with industry (Sarah Wayland)
• Interdisciplinary research (David Zajic)
• Mentoring and managing students (Aleks Aris)
• Time management and family life (Ryan Farrell)

Each 4-minute talk will cover the essentials of the topic and point to resources for further information, including the workshop presenters' slides at http://www.cra.org/Activities/workshops/academic.careers/2008/agenda.2008.html.

Most of today's software falls into the category of event driven software, which takes user and system-generated events (mouse-clicks, messages) as input, and responds to each event by changing its state, and/or outputting an event sequence. This talk presents a statistical model trained on sequences of events and used 1.) to generate a more efficient set of test cases, 2.) to enable fault detection using run-time state gathered during test case execution, and 3.) to support regression testing through reuse of existing test cases. By using the same model for each of these three applications, we demonstrate the flexibilty and usefulness of this model.

To create new and better agents in multi-agent environments, we may want to examine the strategies of several existing agents, in order to combine their best skills. One problem is that in general, we won't know what those strategies are; instead, we'll only have observations of the agents' interactions with other agents. In this talk, I describe how to take a set of interaction traces produced by different pairs of players in a two-player repeated game, and then find the best way to combine them into a composite strategy. I also describe how to incorporate the composite strategy into an existing agent, as an enhancement of the agent's original strategy. In cross-validated experiments involving 126 agents (most of which written by students as class projects) for the Iterated Prisoner's Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes, composite strategies produced from these agents were able to make improvement to the performance of nearly all of the agents.

Solid Modeling is a well-established field. The significance of the contributions of this field is visible in the availability of abundant commercial and free modeling tools for the applications of CAD, animation, visualization etc.

There are various approaches to modeling shapes. A common problem to all of them however, is the handling of non-manifold shapes. Manifold shapes are shapes with the property of topological ``smoothness'' at the local neighbourhood of every point. Objects that contain one or more points that lack this smoothness are all considered non-manifold. Non-manifold objects form a huge catagory of shapes. In the field of solid modeling, solutions typically limit the application domain to manifold shapes. Where the occurrence of non-manifold shapes is inevitable, they are often processed at a high cost. The lack of understanding on the nature of non-manifold shapes is the main cause of it. There is a tremendous gap between the well-established mathematical theories in topology and the materialization of such knowledge in the discrete combinatorial domain of computer science and engineering. The motivation of this research is to bridge this gap between the two.

For any issue with this page, please contact Tsz-Chiu Au at chiu (at) cs.umd.edu.