2009 technical reports

Enterprises are increasingly deploying wireless local area connections (WLANs) to provide mobile access to users in corporate offices. However, existing enterprise WLANs are far from being truly mobile. In particular, they do not adequately support continuous mobility, where users access the network on-the-go. Furthermore, WLANs that do provide continuous mobility support require client modifications, making them hard to deploy in practice 20. In addition, with the growing interest in realtime applications such as voice and video, users are increasingly placing additional (QoS) demands on the network, which for inadequately designed WLANs, does not scale to large numbers of users 10. In this paper, we propose Overcast, a novel WLAN architecture that targets scenarios demanding continuous mobility and real-time support for 802.11 clients. Overcast does not require client modifications and supports all 802.11 standards. Though Overcast borrows some features from prior WLAN designs, it improves on them by incorporating a novel RF mapping framework (proposed in 3) for accurate online detection of RF interference. We describe the architecture of Overcast in detail and discuss our current efforts in realizing such a system on off-the-shelf commodity hardware. We also describe an example application of Overcast to highlight it’s usefulness in supporting realtime applications in continuously mobile user environments.

Valiant load balancing (VLB), also called two-stage load balancing, is gaining popularity as a routing scheme that can serve arbitrary traffic matrices. To date, VLB network design is well understood on a logical full-mesh topology, where VLB is optimal even when nodes or links can fail. In this paper, we address the design and capacity provisioning of arbitrary VLB network topologies. First, we introduce an algorithm to determine if VLB can serve all traffic matrices when a fixed number of arbitrary links fail, and we show how to find a mincost expansion of the network—via link upgrades or installs or both—so that it is resilient to these failures. Additionally, we propose a method to design a new VLB network under the fixed-charge network design cost model. Finally, we prove that VLB is no longer optimal on unrestricted topologies, and can require more capacity than shortest path routing to serve all traffic matrices on some topologies. These results rely on a novel theorem that characterizes the capacity VLB requires of links crossing each cut, i.e., a partition, of the network’s nodes.

The segment minimization problem consists of finding the smallest set of integer matrices that sum to a given intensity matrix, such that each summand has only one non-zero value, and the non-zeroes in each row are consecutive. This has direct applications in intensity-modulated radiation therapy, an effective form of cancer treatment.

We show here that for a single row, this problem is fixed-parameter tractable in the largest value of the intensity matrix. We use this to develop approximation algorithms for the full problem. One of these improves the approximation factor from the previous best of log 2 h + 1 to 3/2 · (log3 h + 1), where h is the largest entry in the intensity matrix; another improves the approximation factor from 2· (log D+1) to 24/13 · (log D+1), where D is the largest difference between consecutive elements of a row of the intensity matrix.

The configuration of network resources greatly impacts the communication overhead for data intensive tasks and constitutes a critical problem in the design and maintenance of networks. To address the issue of resource placement, we analyze and implement a heuristic for solving a known NP-complete graph optimization problem called MAXIMUM SIZE BOUNDED CAPACITY CUT. Experimental results for our heuristic demonstrate promising performance on both synthetic and real world data. Next our heuristic is used as a sub-routine to solve another known NP-complete problem called MIN-MAX MULTIWAY CUT whose traits we adapt to yield a resource placement scheme that exploits correlations between network resources. Our experimental results show that the resulting placement scheme achieves a significant savings in communication overhead.

With the popularity of model-driven methodologies, and the abundance of modelling languages, a major question for a requirements engineer is: which language is suitable for modelling a system under study? We address this question from a semantic point-of-view for big-step modelling languages (BSMLs). BSMLs are a popular class of behavioural modelling languages in which a model can respond to an environmental input by executing multiple, possibly concurrent, transitions. We deconstruct the semantics of a large class of BSMLs into high-level, orthogonal semantic aspects and discuss the relative advantages and disadvantages of the semantic options for each of these aspects to allow a requirements engineer to compare and choose the right BSML. We accompany our presentation with many modelling examples that illustrate the differences between a set of relevant semantic options.

The inherent inaccuracies in user modelling and the use of non-deterministic algorithms means that Preference Elicitation systems are often unsatisfactory for users. We address this issue using a technique called collaborative elicitation. Leveraging the fact that humans rarely have unique preferences, we minimize explicit elicitation from users while attempting to improve user satisfaction. We categorize users into groups using collaborative techniques based on Von Ahn's "Games with a purpose." We then allow groups of users to collectively select default preferences for their peers.

A call graph is a powerful tool for program analysis and can be used to: help plan testing strategies, reduce program size and help programmers understand and debug large programs. We can use either dynamic or static call graph generation techniques. Dynamic call graphs tend to underestimate the number of target methods for a call site where as static call graphs tend to overestimate this this number. A theoretically ideal call graph is the union of the dynamic call graphs over all possible executions of the program. Dynamic call graphs are not safe and generating static call graphs is computationally expensive. We propose an incremental call graph generation approach which will compute graphs for fragments of the program as they are being developed. It will then recursively combine fragments until a graph for the whole program is generated. The graph will be as precise as corresponding traditional algorithms and will present, upon completion, a safe call graph.

A distributed and interface-based publish/subscribe system is proposed in this report. Components in the proposed system react with each other via events only, and these reactions are described in the component interfaces using a variation of Harel statecharts. By encapsulating component behaviour within the interfaces, the goal of the system is to allow the study of modularization and composition mechanisms in distributed event based applications. The presentation of the proposed system is complemented by a metamodel that describes the structural, control, and runtime aspects of distributed event systems.

This report examines the price/performance benefit of using a large cluster of commodity machines rather than server level hardware for certain large scale software applications. A number of tools are presented which make it easier to produce software that runs across large clusters of commodity machines. These tools are the Chubby locking service, the Google file system, MapReduce and BigTable, all written by Google.

A method of simulating distributed search engines is presented. This method measures throughput (queries per second) and resource usage. Disk and network costs are modelled in a simple way, while CPU costs are ignored. Our simulation results show that term distribution can perform better than document distribution when using a small number of machines. This goes against the accepted view that document distribution is faster than term distribution. We introduced a hybrid distribution scheme that splits a set of machines and disks into groups and then performs term distribution within a group and document distribution between groups. Our simulation results show that this hybrid distribution scheme has higher throughput rates than document distribution, but can still scale to large numbers of machines. A special case of our hybrid distribution scheme groups together multiple disks on a machine to produce better throughput without increasing network traffic. Such a scheme could easily be deployed in a web search engine.

Kell-m is a new asynchronous, higher-order process calculus with localities, developed for modelling and verifying distributed event-based systems and applications. Although simple, due to the low level nature of kell-m, considerable effort is required when modelling complex systems. In this report we illustrate how common programming constructs such as variables, procedures, modules and lists can be represented using kellm. These constructs facilitate the modelling of systems and applications using kell-m.

We consider the problem of deciding query equivalence for a conjunctive language in which queries output complex objects composed from a mixture of nested, unordered collection types. Using an encoding of nested objects as flat relations, we translate the problem to deciding the equivalence between encodings output by relational conjunctive queries. This encoding equivalence cleanly unifies and generalizes previous results for deciding equivalence of conjunctive queries evaluated under various processing semantics. As part of our characterization of encoding equivalence, we define a normal form for encoding queries and contend that this normal form offers new insight into the fundamental principles governing the behaviour of nested aggregation.

Distributing data collections by fragmenting them is an effective way of improving the scalability of relational database systems. The unique characteristics of XML data present challenges that require different distribution techniques to achieve scalability. In this paper, we propose solutions to two of the problems encountered in distributed query processing and optimization on XML data, namely localization and pruning. Localization takes a fragmentation-unaware query plan and converts it to a distributed query plan that can be executed at the individual sites that hold XML data fragments in a distributed system. We then show how the resulting distributed query plan can be pruned so that only those sites are accessed that can contribute to the query result. We demonstrate that our techniques can be integrated into a real-life XML database system and that they significantly improve the performance of distributed query execution.

Past research suggests a number of benefits to using hand-based interaction when interacting with electronic presentations. This paper introduces Maestro, a computer-vision based presentation system that uses hand gestures to allow fine-grained interaction with the contents of a projected slideshow. Maestro employs a single web camera and no other physical mediators. The contributions of this paper lie in robustly solving the gesture segmentation problem inherent in using only computer vision as input, and in a set of feedback mechanisms designed to scaffold use of the recognition system without interfering with the visual presentation of content. Specifically, Maestro employs bimanual cues, spatial and contentbased context, hand roles, and, in some case, dwell time to segment gestures. These strong segmentation cues are robust with respect to false positives and allow the actual gestures themselves to more directly match the action to be performed. They also result in a direct manipulation-style interface built on gestures alone. To assist with use, Maestro introduces a feedback comet, an augmented cursor that provides mnemonics for gestures and feedback to help govern gesture speeds to those conducive to gesture recognition. We present the design of the system and lessons learned from user evaluations

One of the most prominent data quality problems is the existence of duplicate records. Current duplicate elimination procedures usually produce one clean instance (repair) of the input data, by carefully choosing the parameters of the duplicate detection algorithms. Finding the right parameter settings can be hard, and in many cases, perfect settings do not exist. Furthermore, replacing the input dirty data with one possible clean instance may result in unrecoverable errors, for example, identification and merging of possible duplicate records in health care systems.
In this paper, we treat duplicate detection procedures as data processing tasks with uncertain outcomes. We concentrate on a family of duplicate detection algorithms that are based on parameterized clustering. We propose a
novel uncertainty model that compactly encodes the space of possible repairs. We show how to efficiently support relational queries under our model, and allowing new types of queries on the set of possible repairs. We give an experimental study illustrating the scalability and the efficiency of our techniques in different configurations.