Harvard Computer Science Technical Reports for 2009

TR-01-09 [tr-01-09.pdf (543 K)]
Lei Zhang , Ligang Liu, Craig Gotsman, and Steven J. Gortler. 2009. ``An As-Rigid-As-Possible Approach to Sensor Network Localization.''
We present a novel approach to localization of sensors in a network given a subset of noisy inter-sensor distances. The algorithm is based on "stitching" together local structures by solving an optimization problem requiring the structures to fit together in an "As-Rigid-As-Possible" manner, hence the name ARAP. The local structures consist of reference "patches" and reference triangles, both obtained from inter-sensor distances. We elaborate on the relationship between the ARAP algorithm and other state-of-the-art algorithms, and provide experimental results demonstrating that ARAP is significantly less sensitive to sparse connectivity and measurement noise. We also show how ARAP may be distributed.
TR-02-09 [tr-02-09.pdf (610 K)]
Rohan Murty, Jitendra Padhye, Alec Wolman, and Matt Welsh . 2009. ``Dyson: An Architecture for Extensible Wireless LANs.''
As wireless local area networks (WLANs) continue to evolve. the fundamental division of responsibility between the access point (AP) and the client has remained unchanged. In most cases, clients make independent decisions about associations and packet transmissions, using only locally available information Furthermore, the IEEE 802.11 standard defines a very limited interface for transferring information between the APs and the clients. These factors impede customization of WLANs to meet site-specific challenges, and in a more general sense, impede rapid innovation to face challenges posed by new applications such as VoIP.

This paper describes Dyson, an extensible architecture for WLANs, targeted primarily at enterprise scenarios. Our architecture is based on centralized, global management of channel resources. To provide extensibility, the interface between the infrastructure and clients is simple and relatively low-level, and can be controlled through a programmatic interface. Clients provide primitives that allow the central controller to control many aspects of client behavior. The controller can also instruct clients to gather and report information about channel conditions. We show thatusing these simple primitives, and by leveraging historical information, the network designer can easily customize many aspects of the WLAN behavior.

We have built a prototype implementation of Dyson, which currently runs on a 23-node testbed distributed across one floor of a typical academic building. Using this testbed, we examine various aspects of the architecture in detail, including a range of policies for improving client-AP associations, providing user-specific airtime reservations, mitigating the effects of interference, and improving mobile handoffs. We show that Dyson is effective at providing greater efficiency while opening up the network to site-specific customizations.

TR-03-09 [tr-03-09.pdf (617 K)]
H.T. Kung, Chit-Kwan Lin, Tsung-Han Lin, and Dario Vlah. 2009. ``Localization with Snap-Inducing Shaped Residuals (SISR) - Coping with Errors in Measurement.''
We consider the problem of localizing wireless nodes in an outdoor, open-space environment, using ad-hoc radio ranging measurements, e.g., 802.11. As in other range-based methods, we cast ranging measurements as a set of distance constraints, thus forming an over-determined system of equations suitable for non-linear least squares optimization. However, ranging measurements are often subject to errors, induced by multipath signals and variations in path loss, or even faulty hardware or antenna connectors. Including such potentially large and non-Gaussian errors in the measurement data ultimately produces inaccurate localization solutions. We propose a new method, called snap-inducing shaped residuals (SISR), to automatically identify "bad nodes" and "bad links" arising from these errors, so that they receive less weight in the localization process. In particular, SISR snaps "good nodes" to their accurate locations and gives less emphasis to other nodes. While the mathematical techniques used by SISR are similar to those in robust statistics, SISR's exploitation of the snap-in effect in localization appears to be novel. We provide analysis on the principle of SISR, and demonstrate a working SISR implementation in field experiments on a testbed of 20 wireless nodes, as well as the superior performance of SISR in simulation with a larger number of nodes.
TR-04-09 [tr-04-09.pdf (336 K)]
Hilary Finucane and Michael Mitzenmacher. 2009. ``Worst-Case and Average-Case Floating Codes for Flash Memory.''
Flash memory is used in portable electronic devices like cell phones, mp3 players, digital cameras, and PDA’s. The question of how to code information in flash memory is a difficult one whose answer can have effects on the speed and lifespan of a chip of flash memory. The main factor to be taken into account when designing codes for flash memory is the difference in cost between decreasing and increasing the state of a cell; decreasing the state of a cell requires first the resetting of an entire section of cells. Codes that focus on maximizing the number of updates between these reset operations are called floating codes. Worst-case floating codes focus on maximizing the lower bound on the number of updates between resets, and average-case floating codes focus on maximizing the average number of updates between resets. In this thesis, we review the work done on both worst-case and average-case floating codes. We also introduce a new code which performs as well as the previous best worst-case floating code but is significantly simpler, and a second code which performs asymptotically better.
TR-05-09 [tr-05-09.pdf (235 K)]
Swapna Reddy, Ya'akov Gal, and Stuart Shieber. 2009. ``Recognition of Users' Activities using Constraint Satisfaction.''
Ideally designed software allow users to explore and experiment during their interaction, and to pursue multiple, interleaving plans. This makes it challenging to automatically recognize users' interactions with such software. This paper shows that this recognition problem can be formalized and solved using constraint satisfaction techniques. It constructs algorithms that use these techniques to recognize users' activities by comparing their interaction histories with a set of ideal solutions. These plan-recognition algorithms are complete, in the sense that they are guaranteed to recognize users' plans if they exist. We evaluate these algorithms empirically on data obtained from different people solving mathematical problems using commercially available pedagogical software. In all cases, these algorithms were able to identify users' activities with the software and distinguish between those actions that played a salient part in the solution and redundant, exploratory actions.
Sven Seuken, , and . 2009. ``.''

TR-07-09 [tr-07-09.pdf (1592 K)]
Guillermo D. Canas, Yuriy Vasilyev , Yair Adato , Todd Zickler , Steven Gortler , and Ohad Ben-Shahar . 2009. ``Unique specular shape from two specular flows.''
When a curved mirror-like surface moves relative to its environment, it induces a motion field--or specular flow--on the image plane that observes it. This specular flow is related to the mirror's shape through a non-linear partial differential equation, and there is interest in understanding when and how this equation can be solved for surface shape. Existing analyses of this 'shape from specular flow equation' have focused on closed-form solutions, and while they have yielded insight, their critical reliance on externally-provided initial conditions and/or specific motions makes them difficult to apply in practice. This paper resolves these issues. We show that a suitable reparameterization leads to a linear formulation of the shape from specular flow equation. This formulation radically simplifies the reconstruction process and allows, for example, both motion and shape to be recovered from as few as two specular flows even when no externally-provided initial conditions are available. The result of our analysis is a practical method for recovering shape from specular flow that operates under arbitrary, unknown motions in unknown illumination environments and does not require additional shape information from other sources.
TR-08-09 [tr-08-09.pdf (1122 K)]
Thomas Bradford Milnes, Christopher Thorpe, and Avi Pfeffer. 2009. ``Genetic Algorithm Optimization of Dynamic Support Vector Regression.''
We show that genetic algorithms (GA) find optimized dynamic support vector machines (DSVMs) more efficiently than the grid search (GS) optimization approach. In addition, we show that GA-DSVMs find extremely low-error solutions for a number of oft-cited benchmarks. Unlike standard support vector machines, DSVMs account for the fact that data further back in a time series are generally less predictive than more-recent data. In order to tune the discounting factors, DSVMs require two new free parameters for a total of five. Because of the five free parameters, traditional GS optimization becomes intractable for even modest grid resolutions. GA optimization finds better results while using fewer computational resources.
TR-09-09 [tr-09-09.pdf (838 K)]
Ryan Wisnesky . 2009. ``Mapping Dependence .''
We describe DMSL, a domain specific language for defining schema mappings. Schema mappings are assertions in carefully crafted logics that express constraints between data represented in different formats, including XML and relational schema. DMSL is suitable for representing programs over mappings, which, for instance, occur in dataflow graphs of mappings. DMSL programs of mapping type are statically guaranteed by a qualified type system to denote satisfiable constraints; the principal polymorphic schemas of source and target solution data instances are automatically inferred. DMSL implements a variety of operations over mappings (e.g., composition) by interfacing with IBM's Clio Mapping Engine.
TR-10-09 [tr-10-09.pdf (208 K)]
Ryan Wisnesky , Mauricio A. Hernandez, and Lucian Popa. 2009. ``Mapping Polymorphism - Proofs.''
This technical report contains the proofs for the paper Mapping Polymorphism, by Ryan Wisnesky, Mauricio A. Hernandez, and Lucian Popa, which appears in the proceedings of the 13th International Conference on Database Theory, held March 22--25, 2010, in Lausanne, Switzerland (ICDT '10).