Technical Reports

The ICICS/CS Reading Room

2010 UBC CS Technical Report Abstracts

TR-2010-01 Interpreter Implementation of Advice Weaving, January 22, 2010 Immad Naseer, Ryan M. Golbeck, Peter Selby and Gregor Kiczales, 12 pages

When late-binding of advice is used for incremental development or configuration, implementing advice weaving using code rewriting external to the VM can cause performance problems during application startup. We present an interpreter-based (non-rewriting) weaver that uses a simple table and cache structure for matching pointcuts against dynamic join points together with a simple mechanism for calling the matched advice. An implementation of our approach in the Jikes RVM shows its feasibility. Internal micro-benchmarks show dynamic join point execution overhead of approximately 28\% in the common case where no advice is applicable and that start-up performance is improved over VM-external weavers. The cache and table structures could be used during later (i.e. JIT time) per-method rewrite based weaving to reduce pointcut matching overhead. We conclude that it is worthwhile to develop and evaluate a complete in-VM hybrid implementation, comprising both non-rewriting and rewriting based advice weaving.

TR-2010-03 Evaluating Two Window Manipulation Techniques on a Large Screen Display, May 08, 2010 Russell Mackenzie, Kirstie Hawkey, Presley Perswain and Kellogg S. Booth, 9 pages

Large screen displays are a common feature of modern meeting rooms, conference halls, and classrooms. The large size and often high resolution of these displays make them inherently suitable for collaborative work, but these attributes cause traditional windowing systems to become difficult to use because the interaction handles become smaller in visual space and in motor space. This may be exacerbated when a user faces the additional cognitive load of active, real-time collaboration. We describe a new window manipulation technique for such a collaborative meeting environment. Its design was inspired by recent collaborative systems in which a user must explicitly take control of a window in order to interact with its contents; actions are otherwise interpreted as navigational. Our Large Screen Optimized (LSO) window manipulation technique utilizes the entire window for manipulations instead of only the title-bar and borders. In addition, LSO includes „snapping regions‟ that automatically move the cursor to the boundary of the window, allowing quick, accurate manipulations involving the edges and corners of the screen. We experimentally validated that our new technique allows users to move and resize windows more quickly than with a traditional window manipulation technique.

TR-2010-04 Sparsity priors and boosting for learning localized distributed feature representations, March 29, 2010 K. Swersky, B. Marlin, and N. de Freitas B. Chen, 18 pages

This technical report presents a study of methods for learning sparse codes and localized features from data. In the context of this study, we propose a new prior for generating sparse image codes with low-energy, localized features. The experiments show that with this prior, it is possible to encode the model with significantly fewer bits without affecting accuracy. The report also introduces a boosting method for learning the structure and parameters of sparse coding models. The new methods are compared to several existing sparse coding techniques on two tasks: reconstruction of natural image patches and self taught learning. The experiments examine the effect of structural choices, priors and dataset size on model size and performance. Interestingly, we discover that, for sparse coding, it is possible to obtain more compact models without incurring reconstruction errors by simply increasing the dataset size.

TR-2010-05 PReach: A Distributed Explicit State Model Checker, April 06, 2010 Flavio M. de Paula, Brad Bingham, Jesse Bingham, John Erickson, Mark Reitblatt and Gaurav Singh, 4 pages

We present PReach, a distributed explicit state model checker based on Murphi. PReach is implemented in the concurrent functional language Erlang. This allowed a clean and simple implementation, with the core algorithms under 1000 lines of code. Additionally, the PReach implementation is targeted to deal with very large models. PReach is able to check an industrial cache coherence protocol with approximately 30 billion states. To our knowledge, this is the largest number published to date for a distributed explicit state model checker.

TR-2010-06 Where do priors and causal models come from? An experimental design perspective, April 07, 2010 and N. de Freitas H. Kueck, 12 pages

(Abstract not available on-line)

TR-2010-07 A Mixed Finite Element Method with Exactly Divergence-free Velocities for Incompressible Magnetohydrodynamics, May 21, 2010 Chen Greif, Dan Li, Dominik Schoetzau and Xiaoxi Wei, 33 pages

We introduce and analyze a mixed finite element method for the numerical discretization of a stationary incompressible magnetohydrodynamics problem, in two and three dimensions. The velocity field is discretized using divergence-conforming Brezzi-Douglas-Marini (BDM) elements and the magnetic field is approximated by curl-conforming N\'{e}d\'{e}lec elements. The $H1$-continuity of the velocity field is enforced by a DG approach. A central feature of the method is that it produces exactly divergence-free velocity approximations, and captures the strongest magnetic singularities. We prove that the energy norm error is convergent in the mesh size in general Lipschitz polyhedra under minimal regularity assumptions, and derive nearly optimal a-priori error estimates for the two-dimensional case. We present a comprehensive set of numerical experiments, which indicate optimal convergence of the proposed method for two-dimensional as well as three-dimensional problems.

TR-2010-08 Preconditioning Iterative Methods for the Optimal Control of the Stokes Equations, June 22, 2010 Tyrone Rees and Andrew J. Wathen, 22 pages

Solving problems regarding the optimal control of partial differential equations (PDEs) -- also known as PDE-constrained optimization -- is a frontier area of numerical analysis. Of particular interest is the problem of flow control, where one would like to effect some desired flow by exerting, for example, an external force. The bottleneck in many current algorithms is the solution of the optimality system -- a system of equations in saddle point form that is usually very large and ill-conditioned. In this paper we describe two preconditioners -- a block-diagonal preconditioner for the minimal residual method and a block-lower triangular preconditioner for a non-standard conjugate gradient method -- which can be effective when applied to such problems where the PDEs are the Stokes equations. We consider only distributed control here, although other problems -- for example boundary control -- could be treated in the same way. We give numerical results, and compare these with those obtained by solving the equivalent forward problem using similar techniques.

TR-2010-10 Sequential Model-Based Optimization for General Algorithm Configuration (extended version), October 13, 2010 Frank Hutter, Holger H. Hoos and Kevin Leyton-Brown, 24 pages

State-of-the-art algorithms for hard computational problems often expose many parameters that can be modified to improve empirical performance. However, manually exploring the resulting combinatorial space of parameter settings is tedious and tends to lead to unsatisfactory outcomes. Recently, automated approaches for solving this algorithm configuration problem have led to substantial improvements in the state of the art for solving various problems. One promising approach constructs explicit regression models to describe the dependence of target algorithm performance on parameter settings; however, this approach has so far been limited to the optimization of few numerical algorithm parameters on single instances. In this paper, we extend this paradigm for the first time to general algorithm configuration problems, allowing many categorical parameters and optimization for sets of instances. We experimentally validate our new algorithm configuration procedure by optimizing a local search and a tree search solver for the propositional satisfiability problem (SAT), as well as the commercial mixed integer programming (MIP) solver CPLEX. In these experiments, our procedure yielded state-of-the-art performance, and in many cases outperformed the previous best configuration approach. # /ubc/cs/home/h/hutter/World/papers/10-TR-SMAC.pdf

TR-2010-11 A Guide to Visual Multi-Level Interface Design From Synthesis of Empirical Study Evidence, October 21, 2010 Heidi Lam and Tamara Munzner, 57 pages

Displaying multiple levels of data visually has been proposed to address the challenge of limited screen space. We review 22 existing multi-level interface studies and cast findings into a four-point decision tree: (1) When are multi-level displays useful? (2) What should the higher visual levels display? (3) Should the visual levels be displayed simultaneously? (4) Should the visual levels be embedded, or separated? Our analysis resulted in three design guidelines: (1) display and data levels should match; (2) high visual levels should only display task-relevant information; (3) simultaneous display, rather than temporal switching, is suitable for tasks with multi-level answers.

TR-2010-12 Determining Relevancy: How Software Developers Determine Relevant Information in Feeds, December 06, 2010 Thomas Fritz and Gail C. Murphy, 4 pages

Finding relevant information within the vast amount of information exchanged via streams, such as provided by Twitter or Facebook, is difficult. Previous research into this problem has largely focused on recommending relevant information based on topicality. By not considering individual and situational factors that can affect whether information is relevant, these approaches fall short. Through a formative, interview-based study, we explored how five software developers from a team determined relevancy of items in two kinds of project news feeds. We identified four factors that the developers used to help determine relevancy and found that placement of items in source code and team contexts can ease the determination of relevancy.

TR-2010-13 Exploring older adults' needs and preferences in learning to use mobile computer devices, December 21, 2010 Rock Leung, Joanna McGrenere, Peter Graf and Vilia Ingriany, 31 pages

Older adults have difficulty using and learning to use mobile phones, in part because the displays are too small for providing effective interactive help. We were interested in augmenting the small phone display with a larger display to support older adults’ learning process, but it was not clear how to apply existing guidelines to design such an augmented display system. In this technical report, we present a comprehensive survey study of 131 respondents we conducted to better understand the learning needs and preferences that are unique to older adults. The results showed, among other things, that when learning, older adults want to learn to perform task steps and prefer using manuals.

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