Technical Reports

The ICICS/CS Reading Room

2007 UBC CS Technical Report Abstracts

TR-2007-02 Discussion of "The Dantzig Selector" by Candes and Tao, January 30, 2007 Michael P. Friedlander and Michael A. Saunders, 7 pages

(Abstract not available on-line)

TR-2007-03 Relationships Between Human and Automated System Identification of Physical Controls, March 01, 2007 Colin Swindells, Karon E. MacLean and Kellogg S. Booth, 20 pages

Active haptic renderings need not only mimic the physical characteristics of a mechanical control such as a knob or slider. They must also elicit a comparable subjective experience from a human who uses the physical control. We compare the results of automated and human captures of 4 salient static and dynamic physical parameters for 5 mechanical test knobs. The automated captures were accomplished using our custom rotary Haptic Camera tool. Human captures were accomplished through user studies in which users matched active haptic renderings to passive mechanical test knobs by adjusting the parameters of the model for the active knob. Both quantitative and qualitative results from the experiments support the hypothesis that the renderings evoke a subjective experience similar to the mechanical knob.

TR-2007-04 On Solving General State-Space Sequential Decision Problems using Inference Algorithms, March 08, 2007 M. Hoffman, A. Doucet, N. de Freitas and A. Jasra, 8 pages

A recently proposed formulation of the stochastic planning and control problem as one of parameter estimation for suitable artificial statistical models has led to the adoption of inference algorithms for this notoriously hard problem. At the algorithmic level, the focus has been on developing Expectation-Maximization (EM) algorithms. For example, Toussaint et al (2006) uses EM with optimal smoothing in the E step to solve finite state-space Markov Decision Processes. In this paper, we extend this EM approach in two directions. First, we derive a non-trivial EM algorithm for linear Gaussian models where the reward function is represented by a mixture of Gaussians, as opposed to the less flexible classical single quadratic function. Second, in order to treat arbitrary continuous state-space models, we present an EM algorithm with particle smoothing. However, by making the crucial observation that the stochastic control problem can be reinterpreted as one of trans-dimensional inference, we are able to propose a novel reversible jump Markov chain Monte Carlo (MCMC) algorithm that is more efficient than its smoothing counterparts. Moreover, this observation also enables us to design an alternative full Bayesian approach for policy search, which can be implemented using a single MCMC run.

TR-2007-06 Imaging and 3D Tomographic Reconstruction of Time-varying, Inhomogeneous Refractive Index Fields, April 03, 2007 B. Atcheson, I. Ihrke, D. Bradley, W. Heidrich, M. Magnor and HP. Seidel, 9 pages

We present a technique for 2D imaging and 3D tomographic reconstruction of time-varying, inhomogeneous refractive index fields. Our method can be used to perform three-dimensional reconstruction of phenomena such as gas plumes or liquid mixing. We can also use the 2D imaging results of such time-varying phenomena to render environment mattes and caustics. To achieve these results, we improve a recent fluid imaging technique called Background Oriented Schlieren imaging, and develop a novel theory for tomographic reconstructions from Schlieren images based on first principles of optics. We demonstrate our approach with two different measurement setups, and discuss example applications such as measuring the heat and density distribution in gas flows.

TR-2007-07 Interplay of Tactile and Visual Guidance Cues under Multimodal Workload, April 04, 2007 M. J. Enriquez, K. E. MacLean and H. Neilson, 19 pages

Modern user interfaces – computerized, complex and time-critical – increasingly support users who multi-task; yet to do this well, we need a better understanding of how computer-user communication degrades with demand on user attention, and the benefits and risks of introducing new display modalities into high-demand environments, Touch can be a natural and intuitive locus of information exchange and is an obvious candidate for offloading visual and/or auditory channels. In this study we compared salience-calibrated tactile, visual and multimodal navigation cues during a driving-like task, and examined the effectiveness and intrusiveness of the navigation signals while varying cognitive workload and masking of task cues. We found that participants continued to utilize haptic navigation signals under high workload, but their usage of visual and reinforced multimodal navigation cues degraded; further, the reinforced cues under high cognitive workload disrupted the visual primary task. While multimodal cue reinforcement is generally considered a positive interface design practice, these results demonstrate a different view: dual-modality cues can cross a distraction threshold in high-workload environments and lead to overall performance degradation. Conversely, our results indicate that tactile signals can be a robust, intuitive and non-intrusive way to communicate information to a user performing a visual primary task.

TR-2007-08 Localized Broadcasting with Guaranteed Delivery and Bounded, April 04, 2007 Hosna Jabbari, Majid Khabbazian and Vijay K. Bhargava, 14 pages

The common belief is that localized broadcast algorithms are not able to guarantee both full delivery and a good bound on the number of transmissions. In this paper, we propose the first localized broadcast algorithm that guarantees full delivery and a constant approximation ratio to the minimum number of required transmissions in the worst case. The proposed broadcast algorithm is a self-pruning algorithm based on 1-hop neighbor information. Using the proposed algorithm, each node determines its status (forwarding/non-forwarding) in O(d log(d)), where d is the maximum node degree of the network. By extending the proposed algorithm, we show that localized broadcast algorithms can achieve both full delivery and a constant approximation ratio to the optimum solution with message complexity O(N), where N is the total number of nodes in the network and each message contains a constant number of bits. We also show how to save bandwidth by reducing the size of piggybacked information. Finally, we relax several system-model assumptions, or replace them with practical ones, in order to improve the practicality of the proposed broadcast algorithm.

TR-2007-09 Understanding Performance for Two 802.11b Competing Flows, April 07, 2007 Kan Cai, Michael J. Feeley and Sharath J. George, 8 pages

It is well known that 802.11 suffers from both inefficiency and unfairness in the face of competition and interference. This paper provides a detailed analysis of the impact of topology and traffic type on network performance when two flows compete with each other for airspace. We consider both TCP and UDP flows and a comprehensive set of node topologies. We vary these topologies to consider all combinations of the following four node-to-node interactions: (1) nodes unable to read or sense each other, (2) nodes able to sense each other but not able to read each other’s packets and nodes able to communicate with (3) weak and with (4) strong signal. We evaluate all possible cases through simulation and show that, for 802.11b competing flows, the cases can be reduced to 11 UDP and 10 TCP models with similar efficiency/fairness characteristics. We also validate our simulation results with extensive experiments conducted in a laboratory testbed.

TR-2007-10 BRDF Acquisition with Basis Illumination, April 16, 2007 Abhijeet Ghosh, Shruthi Achutha, Wolfgang Heidrich and Matthew O'Toole, 8 pages

Realistic descriptions of surface reflectance have long been a topic of interest in both computer vision and computer graphics research. In this paper, we describe a novel and fast approach for the acquisition of bidirectional reflectance distribution functions (BRDFs). We develop a novel theory for directly measuring BRDFs in a basis representation by projecting incident light as a sequence of basis functions from a spherical zone of directions. We derive an orthonormal basis over spherical zones that is ideally suited for this task. BRDF values outside the zonal directions are extrapolated by re-projecting the zonal measurements into a spherical harmonics basis, or by fitting analytical reflection models to the data. We verify this approach with a compact optical setup that requires no moving parts and only a small number of image measurements. Using this approach, a BRDF can be measured in just a few minutes.

TR-2007-11 A Toolbox of Level Set Methods (version 1.1), June 1, 2007 Ian M Mitchell, 94 pages

This document describes a toolbox of level set methods for solving time-dependent Hamilton-Jacobi partial differential equations (PDEs) in the \matlab\ programming environment. Level set methods are often used for simulation of dynamic implicit surfaces in graphics, fluid and combustion simulation, image processing, and computer vision. Hamilton-Jacobi and related PDEs arise in fields such as control, robotics, differential games, dynamic programming, mesh generation, stochastic differential equations, financial mathematics, and verification. The algorithms in the toolbox can be used in any number of dimensions, although computational cost and visualization difficulty make dimensions four and higher a challenge. All source code for the toolbox is provided as plain text in the \matlab\ m-file programming language. The toolbox is designed to allow quick and easy experimentation with level set methods, although it is not by itself a level set tutorial and so should be used in combination with the existing literature.

TR-2007-12 Information Mobility Between Virtual and Physical Domains, May 31, 2007 Garth Shoemaker, 11 pages

Humans are ideally suited to interaction with physical information artifacts. These capabilities should be supported by computing systems, and users should be able to move seamlessly between interacting with virtual artifacts and equivalent physical artifacts. Unfortunately, existing computing systems are centered almost solely around virtual information interaction, with interaction metaphors developed sepcifically for computing systems. It is important that future computing systems evolve to properly support data mobility between physical and virtual domains, and as a result, natural human interactions. We perform a survey of existing research relevant to data mobility, identify key problems which need addressing, and speculate on future research that may help alleviate the problems identified.

TR-2007-13 Contour-based Modeling Using Deformable 3D Templates, June 06, 2007 Vladislav Kraevoy, Alla Sheffer, Michiel van de Panne and , 9 pages

We present a new technique for image-based modeling using as input image contours and a deformable 3D template. The technique gradually deforms the template to fit the contours. At the heart of this process is the need to provide good correspondences between points on image contours and vertices on the model. We propose the use of a hidden Markov model for efficiently computing an optimal set of correspondences. An iterative match-and-deform process then progressively deforms the 3D template to match the image contours. The technique can successfully deform the template to match contours that represent significant changes in shape. The template models can be augmented to include properties such as bending stiffness and symmetry constraints. We demonstrate the results on a variety of objects.

TR-2007-14 Interfaces for Web Service Intermediaries, June 05, 2007 S. Forghanizadeh, I. Minevskiy and E. Wohlstadter, 10 pages

The use of XML as a format for message exchange makes Web services well suited for composition of heterogeneous components. However, since the schema of these messages must be understood by all cooperating services, interoperability is still a significant problem. There is often some level of semantic overlap between schemas even when there is no syntactic match. We are interested in supporting interoperability through the use of partial interface adaptation. Using Web services, it is becoming common for clients to share adaptations provided by a Web service intermediary. Given a Web service and an intermediary, we generate the interface that can be used by a client taking into account what can happen at the intermediary. We provide examples using publicly available service schemas and a performance evaluation for the purpose of validating the usefulness of our approach.

TR-2007-15 Glimmer: Multilevel MDS on the GPU, June 11, 2007 Stephen Ingram, Tamara Munzner and Marc Olano, 8 pages

We present Glimmer, a new multilevel algorithm for multidimensional scaling that accurately reflects the high-dimensional structure of the original data in the low-dimensional embedding, and converges well. It is designed to exploit modern graphics processing unit (GPU) hardware for a dramatic speedup compared to previous work. We also present GPU-SF, an efficient GPU version of a stochastic force algorithm that we use as a subsystem in Glimmer. We propose robust termination conditions for the iterative GPU-SF computation based the filtered sum of point velocities. Our algorithms can either compute high-dimensional Euclidean distance on the fly from a set of high-dimensional points as input, or handle precomputed distance matrices. The O(N2) size of these matrices would quickly overflow texture memory, so we propose distance paging and distance feeding to remove this scalability restriction. We demonstrate Glimmer’s benefits in terms of speed, convergence and correctness against several previous algorithms for a range of synthetic and real benchmark datasets.

TR-2007-16 Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs, June 12, 2007 Michael P. Friedlander and Sven Leyffer, 24 pages

We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search direction. A filter determines the required accuracy of the subproblem solutions and provides an acceptance criterion for the search directions. The resulting algorithm is globally and finitely convergent. The algorithm is suitable for large-scale problems with many degrees of freedom, and provides an alternative to interior-point methods when iterative methods must be used to solve the underlying linear systems. Numerical experiments on a subset of the CUTEr QP test problems demonstrate the effectiveness of the approach.

TR-2007-17 Efficient Optimal Multi-Location Robot Rendezvous, October 05, 2007 Ken Alton and Ian M. Mitchell, 21 pages

We present an efficient algorithm to solve the problem of optimal multi-location robot rendezvous. The rendezvous problem considered can be structured as a tree, with each node representing a meeting of robots, and the algorithm computes optimal meeting locations and connecting robot trajectories. The tree structure is exploited by using dynamic programming to compute solutions in two passes through the tree: an upwards pass computing the cost of all potential solutions, and a downwards pass computing optimal trajectories and meeting locations. The correctness and efficiency of the algorithm are analyzed theoretically, while a discrete robotic clinic problem and a continuous robot arm problem demonstrate the algorithm's practicality.

TR-2007-18 Optimizing Acquaintance Selection in a PDMS, September 28, 2007 Rachel Pottinger Jian Xu, 16 pages

In a Peer Data Management System (PDMS), autonomous peers share semantically rich data. For queries to be translated across peers, a peer must provide a mapping to other peers in the PDMS; peers connected by such mappings are called acquaintances. To maximize query answering ability, a peer needs to optimize its choice of acquaintances. This paper introduces a novel framework for performing acquaintance selection. Our framework includes two selection schemes that effectively and efficiently estimate mapping quality. The "one-shot" scheme clusters peers and estimates the improvement in query answering based on cluster properties. The "two-hop" scheme, estimates using locally available information at multiple rounds. Our empirical study shows that both schemes effectively help acquaintance selection and scale to PDMSs with large number of peers.

TR-2007-21 A Study-Based Guide to Multiple Visual Information Resolution Interface Designs, September 22, 2007 H. Lam and T Munzner, 28 pages

Displaying multiple visual information resolutions (VIRs) of data has been proposed for the challenge of limited screen space. We review 19 existing multiple-VIR interface studies and cast our findings into a four-point decision tree: (1) When is multiple VIR useful? (2) How to create the low-VIR display? (3) Should the VIRs be displayed simultaneously? (4) Should the VIRs be embedded, or separated? We recommend that VIR and data levels should match, and low VIRs should only display task-relevant information. Simultaneous display, rather than temporal switching, is suitable for tasks with multi-level answers.

TR-2007-22 MAGIC Broker: A Middleware Toolkit for Interactive Public Displays, October 02, 2007 Aiman Erbad, Michael Blackstock, Adrian Friday, Rodger Lea and Jalal Al-Muhtadi, 6 pages

Large screen displays are being increasingly deployed in public areas for advertising, entertainment, and information display. Recently we have witnessed increasing interest in supporting interaction with such displays using personal mobile devices. To enable the rapid development of public large screen interactive applications, we have designed and developed the MAGIC Broker. The MAGIC Broker provides a set of abstractions and a simple RESTful web services protocol to easily program interactive public large screen display applications with a focus on mobile device interactions. We have carried out a preliminary evaluation of the MAGIC Broker via the development of a number of prototypes and believe our toolkit is a valid first step in developing a generic support infrastructure to empower developers of interactive large screen display applications.

TR-2007-23 GLUG: GPU Layout of Undirected Graphs, October 15, 2007 Stephen Ingram, Tamara Munzner and Marc Olano, 13 pages

We present a fast parallel algorithm for layout of undirected graphs, using commodity graphics processing unit (GPU) hardware. The GLUG algorithm creates a force-based layout minimizing the Kamada Kawai energy of the graph embedding. Two parameters control the graph layout: the number of landmarks used in the force simulation determines the influence of the global structure, while the number of near neighbors affects local structure. We provide examples and guidelines for their use in controlling the visualization. Our layouts are of comparable or better quality to existing fast, large-graph algorithms. GLUG is an order of magnitude faster than the previous CPU-based FM3 algorithm. It is considerably faster than the only previous GPU-based approach to force-directed placement, a multi-stage algorithm that uses a mix of CPU partitioning and GPU force simulation at each step. While GLUG has a preprocessing stage that runs on the CPU, the core algorithm operates entirely on the GPU.

TR-2007-25 A Tutorial on the Proof of the Existence of Nash Equilibria, November 09, 2007 Albert Xin Jiang and Kevin Leyton-Brown, 10 pages

In this tutorial we detail a proof of Nash's famous theorem on the existence of Nash equilibria in finite games, first proving Sperner's lemma and Brouwer's fixed-point theorem.

TR-2007-27 An Inner/Outer Stationary Iteration for Computing PageRank, December 20, 2007 Andrew P. Gray, Chen Greif and Tracy Lau, 12 pages

We present a stationary iterative scheme for PageRank computation. The algorithm is based on a linear system formulation of the problem, uses inner/outer iterations, and amounts to a simple preconditioning technique. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not particularly sensitive to the choice of the parameters involved. Numerical examples featuring matrices of dimensions up to approximately $107$ confirm the analytical results and demonstrate the accelerated convergence of the algorithm compared to the power method.

If you have any questions or comments regarding this page please send mail to