Technical Reports

The ICICS/CS Reading Room

2011 UBC CS Technical Report Abstracts

TR-2011-01 Hydra-MIP: Automated Algorithm Configuration and Selection for Mixed Integer Programming, April 04, 2011 Lin Xu, Frank Hutter, Holger Hoos and Kevin Leyton-Brown, 15 pages

State-of-the-art mixed integer programming (MIP) solvers are highly parameterized. For heterogeneous and a priori unknown instance distributions, no single parameter configuration generally achieves consistently strong performance, and hence it is useful to select from a portfolio of different solvers. HYDRA is a recent method for using automated algorithm configuration to derive multiple configurations of a single parameterized algorithm for use with portfolio-based selection. This paper shows that, leveraging two key innovations, HYDRA can achieve strong performance for MIP. First, we describe a new algorithm selection approach based on classification with a non-uniform loss function, which significantly improves the performance of algorithm selection for MIP (and SAT). Second, by modifying HYDRA’s method for selecting candidate configurations, we obtain better performance as a function of training time.

TR-2011-02 Displacement Interpolation Using Lagrangian Mass Transport, April 08, 2011 Nicolas Bonneel, Michiel van de Panne, Sylvain Paris and Wolfgang Heidrich, 10 pages

Interpolation between pairs of values, typically vectors, is a fundamental operation in many computer graphics applications. In some cases simple linear interpolation yields meaningful results without requiring domain knowledge. However, interpolation between pairs of distributions or pairs of functions often demands more care because features may exhibit translational motion between exemplars. This property is not captured by linear interpolation. This paper develops the use of displacement interpolation for this class of problem, which provides a generic method for interpolating between distributions or functions based on advection instead of blending. The functions can be non-uniformly sampled, high-dimensional, and defined on non-Euclidean manifolds, e.g., spheres and tori. Our method decomposes distributions or functions into sums of radial basis functions (RBFs). We solve a mass transport problem to pair the RBFs and apply partial transport to obtain the interpolated function. We describe practical methods for computing the RBF decomposition and solving the transport problem. We demonstrate the interpolation approach on synthetic examples, BRDFs, color distributions, environment maps, stipple patterns, and value functions.

TR-2011-03 SinfoniaEx : Fault-Tolerant Distributed Transactional Memory, April 10, 2011 Mahdi Tayarani Najaran and Charles Krasic, 4 pages

We present SinfoniaEx, a powerful paradigm for designing distributed applications. SinfoniaEx is an extension to Sinfonia, a service that provides fault-tolerant atomic access to distributed memory, and is suitable for cloud environments. SinfoniaEx is built over the same design principles of Sinfonia, while extending the interface to allow applications to share system resources, i.e. memory nodes.

TR-2011-04 Applying Interruption Techniques from the HCI Literature to Portable Music, April 21, 2011 Amirhossein Mehrabian and Joanna McGrenere, 40 pages


TR-2011-05 Closed-Form Multigrid Smoothing Factors for Lexicographic Gauss-Seidel, May 3, 2011 L. Robert Hocking and Chen Greif, 15 pages

Abstract: This paper aims to present a unified framework for deriving analytical formulas for smoothing factors in arbitrary dimensions, under certain simplifying assumptions. To derive these expressions we rely on complex analysis and geometric considerations, using the maximum modulus principle and m\"obius transformations. We restrict our attention to pointwise and block lexicographic Gauss-Seidel smoothers on a $d$-dimensional uniform mesh, where the computational molecule of the associated discrete operator forms a $2d+1$ point star. Our results apply to any number of spatial dimensions, and are applicable to high-dimensional versions of a few common model problems with constant coefficients, including the Poisson and anisotropic diffusion equations and a special case of the convection-diffusion equation. We show that our formulas, exact under the simplifying assumptions of Local Fourier Analysis, form tight upper bounds for the asymptotic convergence of geometric multigrid in practice. We also show that there are asymmetric cases where lexicographic Gauss-Seidel smoothing outperforms red-black Gauss-Seidel smoothing; this occurs in particular for certain model convection-diffusion equations with high mesh Reynolds numbers.

TR-2011-06 Audio Stream Bookmarking with a Wristband Controller: Exploring the Role of Explicit Commands in an Implicit Control Loop, May 13, 2011 Jih-Shiang Chang, Joanna McGrenere and Karon E. MacLean, 14 pages

This project places itself as a preliminary and informal evaluation to explicit commands and a proposed implicit control loop. It focuses on the design methods for explicit commands and the relationship between implicit and explicit control channels. Attentional bookmarking (interruption driven) for spoken audio streams (e.g., audio books, podcasts) are chosen as a sample use case. The full project is comprised of information gathering of the use case, brainstorming and designing a controller prototype, and a preliminary field evaluation of the controller. Several design implications for explicit commands and implicit control loops are suggested.

TR-2011-08 Semi-supervised Learning for Identifying Players from Broadcast Sport Videos with Play-by-Play Information, July 22, 2011 Wei-Lwun Lu, Jo-Anne Ting, James J. Little and Kevin P. Murphy, 8 pages

Tracking and identifying players in sports videos filmed with a single moving pan-tilt-zoom camera has many applications, but it is also a challenging problem due to fast camera motions, unpredictable player movements, and unreliable visual features. Recently, [26] introduced a system to tackle this problem based on conditional random fields. However, their system requires a large number of labeled images for training. In this paper, we take advantage of weakly labeled data in the form of publicly available play-by-play information. This, together with semi-supervised learning, allows us to train an identification system with very little supervision. Experiments show that by using only 1500 labels with the play-by-play information in a dataset of 75000 images, we can train a system that has a comparable accuracy as a fully supervised model trained by using 75000 labels.

TR-2011-09 SinExTree : Scalable Multi-Attribute Queries through Distributed Spatial Partitioning, July 22, 2011 Mahdi Tayarani Najaran, Charles Krasic and Norman C. Hutchinson, 7 pages

In this paper we present SinExTree, a spatial partitioning tree designed for scalable low-latency information stor- age and retrieval. SinExTree is built over a Sinfonia-like service that provides atomic access to distributed mem- ory suitable for a cloud environment. An n-dimension SinExTree provides key/value storage, where each key has n attributes, and supports general application-defined queries over multiple attributes.

TR-2011-10 Ephemeral Paths: Gradual Fade-In as a Visual Cue for Subgraph Highlighting, July 28, 2011 Jessica Dawson, Joanna McGrenere, Tamara Munzner, Karyn Moffatt Moffatt and Leah Findlater, 11 pages

Ephemeral highlighting uses the temporal dimension to draw the user's attention to specific interface elements through a combination of abrupt onset and gradual fade-in. This technique has shown promise in adaptive interfaces, but has not been tested as a dynamic visual encoding to support information visualization. We conducted a study with 32 participants using subgraph highlighting to support path tracing in node-link graphs, a task abstracting a large class of visual queries. The study compared multiple highlighting techniques, including traditional static highlighting (using color and size), ephemeral highlighting (where the subgraph is emphasized by appearing first, and the rest of the graph fades in gradually), and a combination of static and ephemeral. The combination was the most effective visual cue: it always performed at least as well or better than static highlighting. Ephemeral on its own was sometimes faster than the combined technique, but it was also more error prone. Self-reported workload and preference followed these performance results.

TR-2011-11 Local Naive Bayes Nearest Neighbor for Image Classification, November 30, 2011 Sancho McCann and David G. Lowe, 10 pages

We present Local Naive Bayes Nearest Neighbor, an improvement to the NBNN image classification algorithm that increases classification accuracy and improves its ability to scale to large numbers of object classes. The key observation is that only the classes represented in the local neighborhood of a descriptor contribute significantly and reliably to their posterior probability estimates. Instead of maintaining a separate search structure for each class, we merge all of the reference data together into one search structure, allowing quick identification of a descriptor's local neighborhood. We show an increase in classification accuracy when we ignore adjustments to the more distant classes and show that the run time grows with the log of the number of classes rather than linearly in the number of classes as did the original. This gives a 100 times speed-up over the original method on the Caltech 256 dataset. We also provide the first head-to-head comparison of NBNN against spatial pyramid methods using a common set of input features. We show that local NBNN outperforms all previous NBNN based methods and the original spatial pyramid model. However, we find that local NBNN, while competitive with, does not beat state-of-the-art spatial pyramid methods that use local soft assignment and max-pooling.

TR-2011-12 Multi-preconditioned GMRES, December 23, 2011 Chen Greif, Tyrone Rees and Daniel Szyld, 24 pages

Standard Krylov subspace methods only allow the user to choose a single preconditioner, although in many situations there may be a number of possibilities. Here we describe an extension of GMRES, multi-preconditioned GMRES, which allows the use of more than one preconditioner. We give some theoretical results, propose a practical algorithm, and present numerical results from problems in domain decomposition and PDE-constrained optimization. These numerical experiments illustrate the applicability and potential of the multi-preconditioned approach.

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