Deploying sensor networks with guaranteed fault tolerance - Bredin,J. L; Demaine,E. D; Hajiaghayi, Mohammad T.; Rus,D. (IEEE/ACM Transactions on Networking (TON), 2010)

Design, Analysis and Comparison of Spatial Indexes for Tetrahedral Meshes - De Floriani, Leila; Fellegara,R.; Magillo,P. (Department of Computer Science and Information Science, University of Genoa, 2010)
We address the problem of performing spatial queries on tetrahedral meshes. These latterarise in several application domains including 3D GIS, scientific visualization, finite element analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral trees. Tetrahedral trees are based on a subdivision of a cubic domain containing the mesh defined either by an octree or a 3D kd-tree. For each of them, we have four variants of the spatial index, depending on four different subdivision criteria. Here, we present such indexes, we discuss how to construct them and perform classical spatial queries such as point location and window queries. We compare the various tetrahedral trees based in memory usage, performances in spatial queries and computation times for constructing them.

Dynamic and Multidimensional Dataflow Graphs - Bhattacharyya, Shuvra S.; Deprettere, Ed F.; Keinert, Joachim (Handbook of Signal Processing Systems, 2010)
Much of the work to date on dataflow models for signal processing system design has focused decidable dataflow models that are best suited for onedimensional signal processing. In this chapter, we review more general dataflow modeling techniques that are targeted to applications that include multidimensional signal processing and dynamic dataflow behavior. As dataflow techniques are applied to signal processing systems that are more complex, and demand increasing degrees of agility and flexibility, these classes of more general dataflow models are of correspondingly increasing interest. We begin with a discussion of two dataflow modeling techniques - multi-dimensional synchronous dataflow and windowed dataflow - that are targeted towards multidimensional signal processing applications. We then provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. Our coverage of dynamic dataflowmodels in this chapter includes Boolean dataflow, the stream-based function model, CAL, parameterized dataflow, and enable-invoke dataflow.
Keywords: Communications Engineering, Networks; Computer Systems Organization and Communication Networks; Processor Architectures; Signal, Image and Speech Processing

Efficient kriging for real-time spatio-temporal interpolation - Srinivasan,B.V.; Duraiswami, Ramani; Murtugudde,R. (Proceedings of the 20 th Conference on Probability and Statistics in the Atmospheric Sciences, 2010)
Atmospheric data is often recorded at scattered stationlocations. While the data is generally available over a long period of time it cannot be used directly for extract- ing coherent patterns and mechanistic correlations. The only recourse is to spatially and temporally interpolate the data both to organize the station recording to a reg- ular grid and to query the data for predictions at a par- ticular location or time of interest. Spatio-temporal in- terpolation approaches require the evaluation of weights at each point of interest. A widely used interpolation ap- proach is kriging. However, kriging has a computational cost that scales as the cube of the number of data points N, resulting in cubic time complexity for each point of interest, which leads to a time complexity of O(N4) for interpolation at O(N) points. In this work, we formulate the kriging problem, to first reduce the computational cost to O(N3). We use an iterative solver (Saad, 2003), and further accelerate the solver using fast summation algo- rithms like GPUML (Srinivasan and Duraiswami, 2009) or FIGTREE (Morariu et al., 2008). We illustrate the speedup on synthetic data and compare the performance with other standard kriging approaches to demonstrate substantial improvement in the performance of our ap- proach. We then apply the developed approach on ocean color data from the Chesapeake Bay and present some quantitative analysis of the kriged results.

Evolutionary framework for Lepidoptera model systems - Roe,A.; Weller,S.; Baixeras,J.; Brown,J. W; Cummings, Michael P.; Davis,DR; Horak,M; Kawahara,A. Y; Mitter,C; Parr,C.S.; Regier,J. C; Rubinoff,D; et al. (Genetics and Molecular Biology of LepidopteraGenetics and Molecular Biology of Lepidoptera, 2010)
“Model systems” are specific organisms upon which detailed studies have been conducted examining a fundamental biological question. If the studies are robust, their results can be extrapolated among an array of organisms that possess features in common with the subject organism. The true power of model systems lies in the ability to extrapolate these details across larger groups of organisms. In order to generalize these results, comparative studies are essential and require that model systems be placed into their evolutionary or phylogenetic context. This chapter examines model systems in the insect order Lepidoptera from the perspective of several different superfamilies. Historically, many species of Lepidoptera have been essential in the development of invaluable model systems in the fields of development biology, genetics, molecular biology, physiology, co-evolution, population dynamics, and ecology.

An Experimental Study of Color-Based Segmentation Algorithms Based on the Mean-Shift Concept - Bitsakos,K.; Fermüller, Cornelia; Aloimonos, J. (Computer Vision – ECCV 2010Computer Vision – ECCV 2010, 2010)
We point out a difference between the original mean-shift formulation of Fukunaga and Hostetler and the common variant in the computer vision community, namely whether the pairwise comparison is performed with the original or with the filtered image of the previous iteration. This leads to a new hybrid algorithm, called Color Mean Shift, that roughly speaking, treats color as Fukunaga’s algorithm and spatial coordinates as Comaniciu’s algorithm. We perform experiments to evaluate how different kernel functions and color spaces affect the final filtering and segmentation results, and the computational speed, using the Berkeley and Weizmann segmentation databases. We conclude that the new method gives better results than existing mean shift ones on four standard comparison measures ( improvement on RAND and BDE measures respectively for color images), with slightly higher running times ( ). Overall, the new method produces segmentations comparable in quality to the ones obtained with current state of the art segmentation algorithms.

Fast Computation of Kernel Estimators - Raykar,Vikas C.; Duraiswami, Ramani; Zhao,Linda H. (Journal of Computational and Graphical Statistics, 2010)
The computational complexity of evaluating the kernel density estimate (or its derivatives) at m evaluation points given n sample points scales quadratically as O(nm)?making it prohibitively expensive for large datasets. While approximate methods like binning could speed up the computation, they lack a precise control over the accuracy of the approximation. There is no straightforward way of choosing the binning parameters a priori in order to achieve a desired approximation error. We propose a novel computationally efficient ε-exact approximation algorithm for the univariate Gaussian kernel-based density derivative estimation that reduces the computational complexity from O(nm) to linear O(n+m). The user can specify a desired accuracy ε. The algorithm guarantees that the actual error between the approximation and the original kernel estimate will always be less than ε. We also apply our proposed fast algorithm to speed up automatic bandwidth selection procedures. We compare our method to the best available binning methods in terms of the speed and the accuracy. Our experimental results show that the proposed method is almost twice as fast as the best binning methods and is around five orders of magnitude more accurate. The software for the proposed method is available online.

Fast matrix-vector product based fgmres for kernel machines - Srinivasan,B.V.; Duraiswami, Ramani; Gumerov, Nail A. (Copper Mountain Conference on Iterative Methods, 2010)
Kernel based approaches for machine learning have gained huge interest in the past decades because of their robustness. In somealgorithms, the primary problem is the solution of a linear system involving the kernel matrix. Iterative Krylov approaches are often used to solve these efficiently [2, 3]. Fast matrix-vector products can be used to accelerate each Krylov iteration to further optimize the performance. In order to reduce the number of iterations of the Krylov approach, a preconditioner becomes necessary in many cases. Several researchers have proposed flexible preconditioning methods where the preconditioner changes with each iteration, and this class of preconditioners are shown to have good performance [6, 12]. In this paper, we use a Tikhonov regularized kernel matrix as a preconditioner for flexible GMRES [12] to solve kernel matrix based systems of equations. We use a truncated conjugate gradient (CG) method to solve the preconditioner system and further accelerate each CG iteration using fast matrix-vector products. The convergence of the proposed preconditioned GMRES is shown on synthetic data. The performance is further validated on problems in Gaussian process regression and radial basis function interpolation. Improvements are seen in each case.

Fast radial basis function interpolation via preconditioned Krylov iteration - Gumerov, Nail A.; Duraiswami, Ramani (SIAM Journal on Scientific Computing, 2010)
We consider a preconditioned Krylov subspace iterative algorithm presented by Faul,Goodsell, and Powell (IMA J. Numer. Anal. 25 (2005), pp. 1–24) for computing the coefficients of a radial basis function interpolant over N data points. This preconditioned Krylov iteration has been demonstrated to be extremely robust to the distribution of the points and the iteration rapidly convergent. However, the iterative method has several steps whose computational and memory costs scale as O(N2), both in preliminary computations that compute the preconditioner and in the matrix-vector product involved in each step of the iteration. We effectively accelerate the iterative method to achieve an overall cost of O(N log N). The matrix vector product is accelerated via the use of the fast multipole method. The preconditioner requires the computation of a set of closest points to each point. We develop an O(N log N) algorithm for this step as well. Results are presented for multiquadric interpolation in R2 and biharmonic interpolation in R3. A novel FMM algorithm for the evaluation of sums involving multiquadric functions in R2 is presented as well.

Finishing genomes with limited resources: lessons from an ensemble of microbial genomes - Nagarajan,Niranjan; Cook,Christopher; Di Bonaventura,Maria Pia; Ge,Hong; Richards,Allen; Bishop-Lilly,Kimberly A; DeSalle,Robert; Read,Timothy D.; Pop, Mihai (BMC Genomics, 2010)
While new sequencing technologies have ushered in an era where microbial genomes can be easily sequenced, the goal of routinely producing high-quality draft and finished genomes in a cost-effective fashion has still remained elusive. Due to shorter read lengths and limitations in library construction protocols, shotgun sequencing and assembly based on these technologies often results in fragmented assemblies. Correspondingly, while draft assemblies can be obtained in days, finishing can take many months and hence the time and effort can only be justified for high-priority genomes and in large sequencing centers. In this work, we revisit this issue in light of our own experience in producing finished and nearly-finished genomes for a range of microbial species in a small-lab setting. These genomes were finished with surprisingly little investments in terms of time, computational effort and lab work, suggesting that the increased access to sequencing might also eventually lead to a greater proportion of finished genomes from small labs and genomics cores.

GEDI - AGroundtruthing Environment for Document Images - David Doermann; Zotkina,Elena; Huiping Li (Ninth IAPRInternational Workshop on Document Analysis Systems (DAS 2010), 2010)
In this paper, we describe a freely available highly configurable document image annotation tool called GEDI – Groundtruthing Environment for Document Images. Its basic structure involves two types of files, an Image file, and a corresponding .xml file in GEDI format. When users begin ground truthing an image, they can configure the interface to allow the creation of different types of zones, each of which may have a custom set of “attributes”. The output is compatible with the UMDDocLib architecture [2] and has been used in numerous funded and unfunded programs to create datasets in multiple languages. GEDI has been developed and released to the community as a comprehensive tool that we hope will ease the burden of document annotation and encourage additional sharing of data.

Generating Phrasal and Sentential Paraphrases: A Survey of Data-Driven Methods - Madnani,Nitin; Dorr, Bonnie J (Computational Linguistics, 2010)
The task of paraphrasing is inherently familiar to speakers of all languages. Moreover, the task of automatically generating or extracting semantic equivalences for the various units of language—words, phrases, and sentences—is an important part of natural language processing (NLP) and is being increasingly employed to improve the performance of several NLP applications. In this article, we attempt to conduct a comprehensive and application-independent survey of data-driven phrasal and sentential paraphrase generation methods, while also conveying an appreciation for the importance and potential use of paraphrases in the field of NLP research. Recent work done in manual and automatic construction of paraphrase corpora is also examined. We also discuss the strategies used for evaluating paraphrase generation techniques and briefly explore some future trends in paraphrase generation.

Genome Sequence of Hybrid Vibrio Cholerae O1 MJ-1236, B-33, and CIRS101 and Comparative Genomics with V. Cholerae - Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Haley,Bradd; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Detter,J. Chris; Han,Cliff S.; Chertkov,Olga; Challacombe,Jean; Huq,Anwar; et al. (Journal of BacteriologyJ. Bacteriol., 2010)
The genomes of Vibrio cholerae O1 Matlab variant MJ-1236, Mozambique O1 El Tor variant B33, and altered O1 El Tor CIRS101 were sequenced. All three strains were found to belong to the phylocore group 1 clade of V. cholerae, which includes the 7th-pandemic O1 El Tor and serogroup O139 isolates, despite displaying certain characteristics of the classical biotype. All three strains were found to harbor a hybrid variant of CTXΦ and an integrative conjugative element (ICE), leading to their establishment as successful clinical clones and the displacement of prototypical O1 El Tor. The absence of strain- and group-specific genomic islands, some of which appear to be prophages and phage-like elements, seems to be the most likely factor in the recent establishment of dominance of V. cholerae CIRS101 over the other two hybrid strains.

A geometric approach to curvature estimation on triangulated 3D shapes - Mesmoudi,M. M.; De Floriani, Leila; Magillo,P. (Int. Conf. on Computer Graphics Theory and Applications (GRAPP), 2010)
We present a geometric approach to define discrete normal, principal, Gaussian and mean curvatures, thatwe call Ccurvature. Our approach is based on the notion of concentrated curvature of a polygonal line and a simulation of rotation of the normal plane of the surface at a point. The advantages of our approach is its simplicity and its natural meaning. A comparison with widely-used discrete methods is presented.

GPUML: Graphical processors for speeding up kernel machines - Srinivasan,B.V.; Hu,Q.; Duraiswami, Ramani (Workshop on High Performance Analytics-Algorithms, Implementations, and Applications, 2010)
Algorithms based on kernel methods play a central rolein statistical machine learning. At their core are a num- ber of linear algebra operations on matrices of kernel functions which take as arguments the training and test- ing data. These range from the simple matrix-vector product, to more complex matrix decompositions, and iterative formulations of these. Often the algorithms scale quadratically or cubically, both in memory and op- erational complexity, and as data sizes increase, kernel methods scale poorly. We use parallelized approaches on a multi-core graphical processor (GPU) to partially address this lack of scalability. GPUs are used to scale three different classes of problems, a simple kernel- matrix-vector product, iterative solution of linear sys- tems of kernel function and QR and Cholesky decom- position of kernel matrices. Application of these accel- erated approaches in scaling several kernel based learn- ing approaches are shown, and in each case substantial speedups are obtained. The core software is released as an open source package, GPUML.

A graph-theoretic approach to protect static and moving targets from adversaries - Dickerson,J. P.; Simari,G. I; V.S. Subrahmanian; Kraus,Sarit (Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1, 2010)
The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.
Keywords: adversarial reasoning; agent systems; game theory

Handbook of Signal Processing Systems - Bhattacharyya, Shuvra S.; Deprettere, Ed F. (Springer, 2010)
The Handbook is organized in four parts. The first part motivates representative applications that drive and apply state-of-the art methods for design and implementation of signal processing systems; the second part discusses architectures for implementing these applications; the third part focuses on compilers and simulation tools; and the fourth part describes models of computation and their associated design tools and methodologies.
Keywords: Computers / Information Theory; Technology & Engineering / Electrical; Technology & Engineering / Signals & Signal Processing

Handwritten Arabic text line segmentation using affinity propagation - Kumar,Jayant; Abd-Almageed, Wael; Kang,Le; David Doermann (Proceedings of the 9th IAPR International Workshop on Document Analysis Systems, 2010)
In this paper, we present a novel graph-based method for extracting handwritten text lines in monochromatic Arabic document images. Our approach consists of two steps - Coarse text line estimation using primary components which define the line and assignment of diacritic components which are more difficult to associate with a given line. We first estimate local orientation at each primary component to build a sparse similarity graph. We then, use a shortest path algorithm to compute similarities between non-neighboring components. From this graph, we obtain coarse text lines using two estimates obtained from Affinity propagation and Breadth-first search. In the second step, we assign secondary components to each text line. The proposed method is very fast and robust to non-uniform skew and character size variations, normally present in handwritten text lines. We evaluate our method using a pixel-matching criteria, and report 96% accuracy on a dataset of 125 Arabic document images. We also present a proximity analysis on datasets generated by artificially decreasing the spacings between text lines to demonstrate the robustness of our approach.
Keywords: affinity propagation; arabic; arabic documents; breadth-first search; clustering; dijkstra's shortest path algorithm; handwritten documents; line detection; text line segmentation

Image classification of vascular smooth muscle cells - Grasso,Michael A.; Mokashi,Ronil; Dalvi,Darshana; Cardone, Antonio; Dima,Alden A.; Bhadriraju,Kiran; Plant,Anne L.; Brady,Mary; Yesha,Yaacov; Yesha,Yelena (Proceedings of the 1st ACM International Health Informatics Symposium, 2010)
Keywords: cell biology; digital image processing; machine learning

On the importance of sharing negative results - Giraud-Carrier,C.; Dunham,M.H.; Atreya,A.; Elkan,C.; Perlich,C.; Swirszcz,G.; Shi,X.; Philip,S.Y.; Fürnkranz,J.; Sima,J.F. (SIGKDD explorations, 2010)

Improving the Dependability of Distributed Systems Through Air Software Upgrades - Tudor Dumitras (Carnegie Mellon University, 2010)
Traditional fault-tolerance mechanisms concentrate almost entirely on responding to, avoiding, or tolerating unexpected faults or security violations. However, scheduled events, such as software upgrades, account for most of the system unavailability and often introduce data corruption or latent errors. Through two empirical studies, this dissertation identifies the leading causes of upgrade failure—breaking hidden dependencies—and of planned downtime—complex data conversions—in distributed enterprise systems. These findings represent the foundation of a new benchmark for software-upgrade dependability. This dissertation further introduces the AIR properties—A TOMICITY, ISOLATION and RUNTIME-TESTING—required for improving the dependability of distributed systems that undergo major software upgrades. The AIR properties are realized in Imago, a system designed to reduce both planned and unplanned downtime by upgrading distributed systems end-to-end. Imago builds upon the idea of isolating the production system from the upgrade operations, in order to avoid breaking hidden dependencies and to decouple the data conversions from the normal system operation. Imago includes novel mechanisms, such as providing a parallel universe for the new version, performing data conversions opportunistically, intercepting the live workload at the ingress and egress points or executing an atomic switchover to the new version, which allow it to deliver the AIR properties. Imago harnesses opportunities provided by the emerging cloud-computing technologies, by trading resource overhead (needed by the parallel universe) for an improved dependability of the software upgrades. This approach separates the functional aspects of the upgrade from the mechanisms for online upgrade, enabling an upgrade-as-a-service model. This dissertation also describes techniques for assessing the impact of software upgrades, in order to reason about the implications of relaxing the AIR guarantees .

Increasing representational power and scaling reasoning in probabilistic databases - Deshpande, Amol (Proceedings of the 13th International Conference on Database Theory, 2010)
Increasing numbers of real-world application domains are generating data that is inherently noisy, incomplete, and probabilistic in nature. Statistical analysis and probabilistic inference, widely used in those domains, often introduce additional layers of uncertainty. Examples include sensor data analysis, data integration and information extraction on the Web, social network analysis, and scientific and biomedical data management. Managing and querying such data requires us to combine the tools and the techniques from a variety of disciplines including databases, first-order logic, and probabilistic reasoning. There has been much work at the intersection of these research areas in recent years. The work on probabilistic databases has made great advances in efficiently executing SQL and inference queries over large-scale uncertain datasets [2, 1]. The research in first-order probabilistic models like probabilistic relational models [5], Markov logic networks [10] etc. (see Getoor and Taskar [6] for a comprehensive overview), and the work on lifted inference [9, 3, 8, 11] has resulted in several techniques for efficiently integrating first-order logic and probabilistic reasoning. In this talk, I will present some of the foundations of large-scale probabilistic data management, and the challenges in scaling the representational power and the reasoning capabilities of probabilistic databases. I will use the PrDB probabilistic data management system being developed at the University of Maryland as a case study for this purpose [4, 7, 12]. Unlike the other recent work on probabilistic databases, PrDB is designed to represent uncertain data with rich correlation structures, and it uses probabilistic graphical models as the basic representation model. I will discuss how PrDB supports compact specification of uncertainties at different abstraction levels, from "schema-level" uncertainties that apply to entire relations to "tuple-specific" uncertainties that apply to a specific tuple or a specific set of tuples; I will also discuss how this relates to the work on first-order probabilistic models. Query evaluation in PrDB can be formulated as inference in appropriately constructed graphical models, and I will briefly present some of the key novel techniques that we have developed for efficient query evaluation, and their relationship to recent work on efficient lifted inference. I will conclude with a discussion of some of the open research challenges moving forward.

Insights into head-related transfer function: Spatial dimensionality and continuous representation - Zhang,Wen; Abhayapala,Thushara D.; Kennedy,Rodney A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2010)
This paper studies head-related transfer function (HRTF) sampling and synthesis in a three-dimensional auditory scene based on a general modal decomposition of the HRTF in all frequency-range-angle domains. The main finding is that the HRTF decomposition with the derived spatial basis function modes can be well approximated by a finite number, which is defined as the spatial dimensionality of the HRTF. The dimensionality determines the minimum number of parameters to represent the HRTF corresponding to all directions and also the required spatial resolution in HRTF measurement. The general model is further developed to a continuous HRTF representation, in which the normalized spatial modes can achieve HRTF near-field and far-field representations in one formulation. The remaining HRTF spectral components are compactly represented using a Fourier spherical Bessel series, where the aim is to generate the HRTF with much higher spectral resolution in fewer parameters from typical measurements, which usually have limited spectral resolution constrained by sampling conditions. A low-computation algorithm is developed to obtain the model coefficients from the existing measurements. The HRTF synthesis using the proposed model is validated by three sets of data: (i) synthetic HRTFs from the spherical head model, (ii) the MIT KEMAR (Knowles Electronics Mannequin for Acoustics Research) data, and (iii) 45-subject CIPIC HRTF measurements.
Keywords: acoustic signal processing; Bessel functions; Fourier series; hearing; Transfer functions

Interlingual Annotation of Parallel Text Corpora: A New Framework for Annotation and Evaluation - Dorr, Bonnie J; Passonneau,Rebecca J.; Farwell,David; Green,Rebecca; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Miller,Keith J.; Mitamura,Teruko; Rambow,Owen; Siddharthan,Advaith (Natural Language Engineering, 2010)
This paper focuses on an important step in the creation of a system of meaning representation and the development of semantically annotated parallel corpora, for use in applications such as machine translation, question answering, text summarization, and information retrieval. The work described below constitutes the first effort of any kind to annotate multiple translations of foreign-language texts with interlingual content. Three levels of representation are introduced: deep syntactic dependencies (IL0), intermediate semantic representations (IL1), and a normalized representation that unifies conversives, nonliteral language, and paraphrase (IL2). The resulting annotated, multilingually induced, parallel corpora will be useful as an empirical basis for a wide range of research, including the development and evaluation of interlingual NLP systems and paraphrase-extraction systems as well as a host of other research and development efforts in theoretical and applied linguistics, foreign language pedagogy, translation studies, and other related disciplines.

Investigating the impact of design processes on children - Guha,M.L.; Druin, Allison; Fails,J. A (Proceedings of the 9th International Conference on Interaction Design and Children, 2010)

iOpener Workbench: Tools for rapid understanding of scientific literature - Dunne,C.; Shneiderman, Ben; Dorr, Bonnie J; Klavans,J. (Human-Computer Interaction Lab 27th Annual Symposium, University of Maryland, College Park, MD, 2010)

Isodiamond Hierarchies: An Efficient Multiresolution Representation for Isosurfaces and Interval Volumes - Weiss,K.; De Floriani, Leila (Visualization and Computer Graphics, IEEE Transactions on, 2010)
Efficient multiresolution representations for isosurfaces and interval volumes are becoming increasingly important as the gap between volume data sizes and processing speed continues to widen. Our multiresolution scalar field model is a hierarchy of tetrahedral clusters generated by longest edge bisection that we call a hierarchy of diamonds. We propose two multiresolution models for representing isosurfaces, or interval volumes, extracted from a hierarchy of diamonds which exploit its regular structure. These models are defined by subsets of diamonds in the hierarchy that we call isodiamonds, which are enhanced with geometric and topological information for encoding the relation between the isosurface, or interval volume, and the diamond itself. The first multiresolution model, called a relevant isodiamond hierarchy, encodes the isodiamonds intersected by the isosurface, or interval volume, as well as their nonintersected ancestors, while the second model, called a minimal isodiamond hierarchy, encodes only the intersected isodiamonds. Since both models operate directly on the extracted isosurface or interval volume, they require significantly less memory and support faster selective refinement queries than the original multiresolution scalar field, but do not support dynamic isovalue modifications. Moreover, since a minimal isodiamond hierarchy only encodes intersected isodiamonds, its extracted meshes require significantly less memory than those extracted from a relevant isodiamond hierarchy. We demonstrate the compactness of isodiamond hierarchies by comparing them to an indexed representation of the mesh at full resolution.
Keywords: Computer-Assisted; Imaging; data processing speed; edge bisection; encoding; interval volumes; isodiamond hierarchies; isosurfaces; mesh representation; minimal isodiamond hierarchy; multiresolution representation; multiresolution scalar field model; relevant isodiamond hierarchy; volume data; Theoretical; User-Computer Interface; Three-Dimensional; Models

Kernelized Rényi distance for speaker recognition - Vasan Srinivasan,B.; Duraiswami, Ramani; Zotkin,Dmitry N (Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, 2010)
Speaker recognition systems classify a test signal as a speaker or an imposter by evaluating a matching score between input and reference signals. We propose a new information theoretic approach for computation of the matching score using the Re #x0301;nyi entropy. The proposed entropic distance, the Kernelized Re #x0301;nyi distance (KRD), is formulated in a non-parametric way and the resulting measure is efficiently evaluated in a parallelized fashion on a graphical processor. The distance is then adapted as a scoring function and its performance compared with other popular scoring approaches in a speaker identification and speaker verification framework.
Keywords: #x0301; nyi; approach; input; distance; reference; entropy; graphical; equipment; entropy; speaker; graphic; identification; speaker; processor; information; Re; recognition; recognition; speaker; signals; kernelized; signals; speaker; theoretic; verification; computer

Learning algorithms for link prediction based on chance constraints - Doppa,J.; Yu,J.; Tadepalli,P.; Getoor, Lise (Machine Learning and Knowledge Discovery in Databases, 2010)
In this paper, we consider the link prediction problem, where we are given a partial snapshot of a network at some time and the goal is to predict the additional links formed at a later time. The accuracy of current prediction methods is quite low due to the extreme class skew and the large number of potential links. Here, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, they allow preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world domains—co-authorship networks, biological networks and citation networks—show significant performance improvement over baseline algorithms. We conclude by briefly describing some promising future directions based on this work.

Learning what and how of contextual models for scene labeling - Jain, A.; Gupta,A.; Davis, Larry S. (Computer Vision–ECCV 2010, 2010)
We present a data-driven approach to predict the importance of edges and construct a Markov network for image analysis based on statistical models of global and local image features. We also address the coupled problem of predicting the feature weights associated with each edge of a Markov network for evaluation of context. Experimental results indicate that this scene dependent structure construction model eliminates spurious edges and improves performance over fully-connected and neighborhood connected Markov network.

Lineage processing over correlated probabilistic databases - Kanagal,Bhargav; Deshpande, Amol (Proceedings of the 2010 international conference on Management of data, 2010)
In this paper, we address the problem of scalably evaluating conjunctive queries over correlated probabilistic databases containing tuple or attribute uncertainties. Like previous work, we adopt a two-phase approach where we first compute lineages of the output tuples, and then compute the probabilities of the lineage formulas. However unlike previous work, we allow for arbitrary and complex correlations to be present in the data, captured via a forest of junction trees. We observe that evaluating even read-once (tree structured) lineages (e.g., those generated by hierarchical conjunctive queries), polynomially computable over tuple independent probabilistic databases, is #P-complete for lightly correlated probabilistic databases like Markov sequences. We characterize the complexity of exact computation of the probability of the lineage formula on a correlated database using a parameter called lwidth (analogous to the notion of treewidth). For lineages that result in low lwidth, we compute exact probabilities using a novel message passing algorithm, and for lineages that induce large lwidths, we develop approximate Monte Carlo algorithms to estimate the result probabilities. We scale our algorithms to very large correlated probabilistic databases using the previously proposed INDSEP data structure. To mitigate the complexity of lineage evaluation, we develop optimization techniques to process a batch of lineages by sharing computation across formulas, and to exploit any independence relationships that may exist in the data. Our experimental study illustrates the benefits of using our algorithms for processing lineage formulas over correlated probabilistic databases.
Keywords: conjunctive queries; Indexing; junction trees; lineage; Probabilistic databases

Loudspeaker and Microphone Array Signal Processing-Plane-Wave Decomposition of Acoustical Scenes Via Spherical and Cylindrical Microphone Arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE transactions on audio, speech, and language processing, 2010)

The Metacognitive Loop: An Architecture for Building Robust Intelligent Systems - Shahri,Hamid Haidarian; Dinalankara,Wikum; Fults,Scott; Wilson,Shomir; Perlis, Don; Schmill,Matt; Oates,Tim; Josyula,Darsana; Anderson,Michael (2010 AAAI Fall Symposium Series, 2010)
The Metacognitive Loop: An Architecture for Building Robust Intelligent Systems
Keywords: commonsense; ontologies; robust intelligent systems

Method for measurement of head related transfer functions - Duraiswami, Ramani; Gumerov, Nail A. (2010)
Head Related Transfer Functions (HRTFs) of an individual are measured in rapid fashion in an arrangement where a sound source is positioned in the individual's ear channel, while microphones are arranged in the microphone array enveloping the individual's head. The pressure waves generated by the sounds emanating from the sound source reach the microphones and are converted into corresponding electrical signals which are further processed in a processing system to extract HRTFs, which may then be used to synthesize a spatial audio scene. The acoustic field generated by the sounds from the sound source can be evaluated at any desired point inside or outside the microphone array.

Mobile collaboration: collaboratively reading and creating children's stories on mobile devices - Fails,J. A; Druin, Allison; Guha,M.L. (Proceedings of the 9th International Conference on Interaction Design and Children, 2010)

Mobile Visual Aid Tools for Users with Visual Impairments - Liu,Xu; David Doermann; Huiping Li (Mobile Multimedia ProcessingMobile Multimedia Processing, 2010)
In this chapter we describe “MobileEye”, a software suite which converts a camera enabled mobile device into a multi-function vision tool that can assist the visually impaired in their daily activities. MobileEye consists of four subsystems, each customized for a specific type of visual disabilities: A color channel mapper which can tell the visually impaired different colors; a software based magnifier which provides image magnification as well as enhancement; a pattern recognizer which can read currencies; and a document retriever which allows access to printed materials. We developed cutting edge computer vision and image processing technologies, and tackled the challenges of implementing them on mobile devices with limited computational resources and low image quality. The system minimizes keyboard operation for the usability of users with visual impairments. Currently the software suite runs on Symbian and Windows Mobile handsets. In this chapter we provides a high level overview of the system, and then discuss the pattern recognizer in detail. The challenge is how to build a real-time recognition system on mobile devices and we present our detailed solutions.

A modality lexicon and its use in automatic tagging - Baker,K.; Bloodgood,M.; Dorr, Bonnie J; Filardo,N.W.; Levin,L.; Piatko,C. (Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10), 2010)
This paper describes our resource-building results for an eight-week JHU Human Language Technology Center of Excellence SummerCamp for Applied Language Exploration (SCALE-2009) on Semantically-Informed Machine Translation. Specifically, we describe the construction of a modality annotation scheme, a modality lexicon, and two automated modality taggers that were built using the lexicon and annotation scheme. Our annotation scheme is based on identifying three components of modality: a trigger, a target and a holder. We describe how our modality lexicon was produced semi-automatically, expanding from an initial hand-selected list of modality trigger words and phrases. The resulting expanded modality lexicon is being made publicly available. We demonstrate that one tagger—a structure-based tagger—results in precision around 86% (depending on genre) for tagging of a standard LDC data set. In a machine translation application, using the structure-based tagger to annotate English modalities on an English-Urdu training corpus improved the translation quality score for Urdu by 0.3 Bleu points in the face of sparse training data.

Modeling and generalization of discrete Morse terrain decompositions - De Floriani, Leila; Magillo,P.; Vitali,M. (Proc. 20th Int. Conf. on Pattern Recognition, ICPR, 2010)
We address the problem of morphological analysis ofreal terrains. We describe a morphological model for a terrain by considering extensions of Morse theory to the discrete case. We propose a two-level model of the morphology of a terrain based on a graph joining the critical points of the terrain through integral lines. We present a new set of generalization operators specific for discrete piece-wise linear terrain models, which are used to reduce noise and the size of the morphological representation. We show results of our approach on real terrains.

Multi-Camera Tracking with Adaptive Resource Allocation - Han,B.; Joo, S.W.; Davis, Larry S. (International Journal of Computer Vision, 2010)

Multiresolution analysis of 3D images based on discrete distortion - Weiss,K.; De Floriani, Leila; Mesmoudi,M. M. (International Conference on Pattern Recognition (ICPR), 2010)
We consider a model of a 3D image obtained bydiscretizing it into a multiresolution tetrahedral mesh known as a hierarchy of diamonds. This model enables us to extract crack-free approximations of the 3D image at any uniform or variable resolution, thus reducing the size of the data set without reducing the accuracy. A 3D intensity image is a scalar field (the intensity field) defined at the vertices of a 3D regular grid and thus the graph of the image is a hypersurface in R4. We measure the discrete distortion, a generalization of the notion of curvature, of the transformation which maps the tetrahedralized 3D grid onto its graph in R4. We evaluate the use of a hierarchy of diamonds to analyze properties of a 3D image, such as its discrete distortion, directly on lower resolution approximations. Our results indicate that distortion-guided extractions focus the resolution of approximated images on the salient features of the intensity image.

Multiresolution morse triangulations - Danovaro,Emanuele; De Floriani, Leila; Magillo,Paola; Vitali,Maria (Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, 2010)
We address the problem of representing the geometry and the morphology of a triangulated surface endowed with a scalar field in a combined geometric and topological multiresolution model. The model, called a Multiresolution Morse Triangulation (MMT), is composed of a multiresolution triangle mesh, and of a multiresolution Morse complex describing the morphology of the field. The MMT is built through a combined morphological and geometrical generalization, and supports queries to extract consistent geometrical and morphological representations of the field at both uniform and variable resolutions.

Multi-view clustering with constraint propagation for learning with an incomplete mapping between views - Eaton,Eric; desJardins, Marie; Jacob,Sara (Proceedings of the 19th ACM international conference on Information and knowledge management, 2010)
Multi-view learning algorithms typically assume a complete bipartite mapping between the different views in order to exchange information during the learning process. However, many applications provide only a partial mapping between the views, creating a challenge for current methods. To address this problem, we propose a multi-view algorithm based on constrained clustering that can operate with an incomplete mapping. Given a set of pairwise constraints in each view, our approach propagates these constraints using a local similarity measure to those instances that can be mapped to the other views, allowing the propagated constraints to be transferred across views via the partial mapping. It uses co-EM to iteratively estimate the propagation within each view based on the current clustering model, transfer the constraints across views, and update the clustering model, thereby learning a unified model for all views. We show that this approach significantly improves clustering performance over several other methods for transferring constraints and allows multi-view clustering to be reliably applied when given a limited mapping between the views.
Keywords: constrained clustering; multi-view learning; semi-supervised learning

Nested refinement domains for tetrahedral and diamond hierarchies - Weiss,K.; De Floriani, Leila (IEEE Visualization, 2010)
Three nested refinement domains for hierarchies of tetrahedra and diamonds. The descendant domain (left) is the limit shape of thedomain covered by all descendants of a given diamond (colored). Due to the fractal nature of these shapes, we introduce the more conservative convex descendant domain (middle) and bounding box descendant domain (right) to simplify the computation while still tightly covering the descendant domain. In each case, the refinement domain of one of the diamond’s parents, grandparents and great-grandparents is shown.

Non-visual exploration of geographic maps: Does sonification help? - Delogu,Franco; Palmiero,Massimiliano; Federici,Stefano; Plaisant, Catherine; Zhao,Haixia; Belardinelli,Olivetti (Disability & Rehabilitation: Assistive Technology, 2010)
Purpose. This study aims at evaluating the effectiveness of sonification as a mean to provide access to geo-referenced information to users with visual impairments.Method. Thiry-five participants (10 congenitally blind, 10 with acquired blindness and 15 blindfolded sighted) completed four tasks of progressive difficulty. During each task, participants first explored a sonified map by using either a tablet or a keyboard to move across regions and listened to sounds giving information about the current location. Then the participants were asked to identify, among four tactile maps, the one that crossmodally corresponds to the sonifed map they just explored. Finally, participants answered a self-report questionnaire of understanding and satisfaction. Results. Participants achieved high accuracy in all of the four tactile map discrimination tasks. No significant performance difference was found neither between subjects that used keyboard or tablet, nor between the three groups of blind and sighted participants. Differences between groups and interfaces were found in the usage strategies. High levels of satisfaction and understanding of the tools and tasks emerged from users' reports.

Obtaining valid safety data for software safety measurement and process improvement - Basili, Victor R.; Zelkowitz, Marvin V; Layman,Lucas; Dangle,Kathleen; Diep,Madeline (Proceedings of the 2010 ACM-IEEE International Symposium on Empirical Software Engineering and Measurement, 2010)
We report on a preliminary case study to examine software safety risk in the early design phase of the NASA Constellation spaceflight program. Our goal is to provide NASA quality assurance managers with information regarding the ongoing state of software safety across the program. We examined 154 hazard reports created during the preliminary design phase of three major flight hardware systems within the Constellation program. Our purpose was two-fold: 1) to quantify the relative importance of software with respect to system safety; and 2) to identify potential risks due to incorrect application of the safety process, deficiencies in the safety process, or the lack of a defined process. One early outcome of this work was to show that there are structural deficiencies in collecting valid safety data that make software safety different from hardware safety. In our conclusions we present some of these deficiencies.
Keywords: case study; NASA; risk analysis; safety metrics

Overlap-based cell tracker - Chalfoun, J; Cardone, Antonio; Dima, A.A.; Allen, D.P.; Halter, M.W. (The Journal of Research of the National Institute of Standards and Technology, 2010)
order to facilitate the extraction of quantitative data from live cell image sets, automated image analysis methods are needed. This paper presents an introduction to the general principle of an overlap cell tracking software developed by the National Institute of Standards and Technology (NIST). This cell tracker has the ability to track cells across a set of time lapse images acquired at high rates based on the amount of overlap between cellular regions in consecutive frames. It is designed to be highly flexible, requires little user parameterization, and has a fast execution time.

Partial least squares on graphical processor for efficient pattern recognition - Srinivasan,Balaji Vasan; Schwartz,William Robson; Duraiswami, Ramani; Davis, Larry S. (Technical Reports of the Computer Science Department, 2010)
Partial least squares (PLS) methods have recently been used for many patternrecognition problems in computer vision. Here, PLS is primarily used as a supervised dimensionality reduction tool to obtain effective feature combinations for better learning. However, application of PLS to large datasets is hindered by its higher computational cost. We propose an approach to accelerate the classical PLS algorithm on graphical processors to obtain the same performance at a reduced cost. Although, PLS modeling is practically an offline training process, accelerating it helps large scale modeling. The proposed acceleration is shown to perform well and it yields upto ~30X speedup, It is applied on standard datasets in human detection and face recognition.
Keywords: Technical Report

Performance Evaluation Tools for Zone Segmentation and Classification (PETS) - Seo,W.; Agrawal,Mudit; David Doermann (International Conference on Pattern Recognition, 2010)
This paper overviews a set of Performance Evaluation ToolS (PETS) for zone segmentation and classification. The tools allow researchers and developers to evaluate, optimize and compare their algorithms by providing a variety of quantitative performance metrics. The evaluation of segmentation quality is based on the pixel-based overlaps between two sets of regions proposed by Randriamasy and Vincent. PETS extends the approach by providing a set of metrics for overlap analysis, RLE and polygonal representation of regions and introduces type-matching to evaluate zone classification. The software is available for research use.

Perturbing the Ubiquitin Pathway Reveals How Mitosis Is Hijacked to Denucleate and Regulate Cell Proliferation and Differentiation In Vivo - Caceres,Andrea; Shang,Fu; Wawrousek,Eric; Liu,Qing; Avidan,Orna; Cvekl,Ales; Yang,Ying; Haririnia,Aydin; Storaska,Andrew; Fushman, David; Kuszak,Jer; Dudek,Edward; et al. (PLoS ONEPLoS ONE, 2010)
BackgroundThe eye lens presents a unique opportunity to explore roles for specific molecules in cell proliferation, differentiation and development because cells remain in place throughout life and, like red blood cells and keratinocytes, they go through the most extreme differentiation, including removal of nuclei and cessation of protein synthesis. Ubiquitination controls many critical cellular processes, most of which require specific lysines on ubiquitin (Ub). Of the 7 lysines (K) least is known about effects of modification of K6. Methodology and Principal Findings We replaced K6 with tryptophan (W) because K6 is the most readily modified K and W is the most structurally similar residue to biotin. The backbone of K6W-Ub is indistinguishable from that of Wt-Ub. K6W-Ub is effectively conjugated and deconjugated but the conjugates are not degraded via the ubiquitin proteasome pathways (UPP). Expression of K6W-ubiquitin in the lens and lens cells results in accumulation of intracellular aggregates and also slows cell proliferation and the differentiation program, including expression of lens specific proteins, differentiation of epithelial cells into fibers, achieving proper fiber cell morphology, and removal of nuclei. The latter is critical for transparency, but the mechanism by which cell nuclei are removed has remained an age old enigma. This was also solved by expressing K6W-Ub. p27kip, a UPP substrate accumulates in lenses which express K6W-Ub. This precludes phosphorylation of nuclear lamin by the mitotic kinase, a prerequisite for disassembly of the nuclear membrane. Thus the nucleus remains intact and DNAseIIβ neither gains entry to the nucleus nor degrades the DNA. These results could not be obtained using chemical proteasome inhibitors that cannot be directed to specific tissues. Conclusions and Significance K6W-Ub provides a novel, genetic means to study functions of the UPP because it can be targeted to specific cells and tissues. A fully functional UPP is required to execute most stages of lens differentiation, specifically removal of cell nuclei. In the absence of a functional UPP, small aggregate prone, cataractous lenses are formed.

Plane-Wave Decomposition of Acoustical Scenes Via Spherical and Cylindrical Microphone Arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE Transactions on Audio, Speech, and Language Processing, 2010)
Spherical and cylindrical microphone arrays offer a number of attractive properties such as direction-independent acoustic behavior and ability to reconstruct the sound field in the vicinity of the array. Beamforming and scene analysis for such arrays is typically done using sound field representation in terms of orthogonal basis functions (spherical/cylindrical harmonics). In this paper, an alternative sound field representation in terms of plane waves is described, and a method for estimating it directly from measurements at microphones is proposed. It is shown that representing a field as a collection of plane waves arriving from various directions simplifies source localization, beamforming, and spatial audio playback. A comparison of the new method with the well-known spherical harmonics based beamforming algorithm is done, and it is shown that both algorithms can be expressed in the same framework but with weights computed differently. It is also shown that the proposed method can be extended to cylindrical arrays. A number of features important for the design and operation of spherical microphone arrays in real applications are revealed. Results indicate that it is possible to reconstruct the sound scene up to order p with p2 microphones spherical array.
Keywords: Acoustic fields; acoustic position measurement; acoustic signal processing; acoustic waves; acoustical scene analysis; array signal processing; circular arrays; cylindrical microphone arrays; direction-independent acoustic behavior; microphone arrays; orthogonal basis functions; plane-wave decomposition; Position measurement; signal reconstruction; sound field reconstruction; sound field representation; source localization; spatial audio playback; spherical harmonics based beamforming algorithm; spherical microphone arrays

Plasmonic Systems and Devices Utilizing Surface Plasmon Polariton - Smolyaninov,Igor I.; Vishkin, Uzi; Davis,Christopher C. (2010)
Plasmonic systems and devices that utilize surface plasmon polaritons (or “plasmons”) for inter-chip and/or intra-chip communications are provided. A plasmonic system includes a microchip that has an integrated circuit module and a plasmonic device configured to interface with the integrated circuit module. The plasmonic device includes a first electrode, a second electrode positioned at a non-contact distance from the first electrode, and a tunneling-junction configured to create a plasmon when a potential difference is created between the first electrode and the second electrode.

The pre‐seventh pandemic Vibrio cholerae BX 330286 El Tor genome: evidence for the environment as a genome reservoir - Haley,Bradd J.; Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Challacombe,Jean F.; Detter,J. Chris; Han,Cliff S.; Huq,Anwar; Nair,G. Balakrish; et al. (Environmental Microbiology Reports, 2010)
Vibrio cholerae O1 El Tor BX 330286 was isolated from a water sample in Australia in 1986, 9 years after an indigenous outbreak of cholera occurred in that region. This environmental strain encodes virulence factors highly similar to those of clinical strains, suggesting an ability to cause disease in humans. We demonstrate its high similarity in gene content and genome-wide nucleotide sequence to clinical V. cholerae strains, notably to pre-seventh pandemic O1 El Tor strains isolated in 1910 (V. cholerae NCTC 8457) and 1937 (V. cholerae MAK 757), as well as seventh pandemic strains isolated after 1960 globally. Here we demonstrate that this strain represents a transitory clone with shared characteristics between pre-seventh and seventh pandemic strains of V. cholerae. Interestingly, this strain was isolated 25 years after the beginning of the seventh pandemic, suggesting the environment as a genome reservoir in areas where cholera does not occur in sporadic, endemic or epidemic form.

Putting the user in the loop: interactive Maximal Marginal Relevance for query-focused summarization - Jimmy Lin; Madnani,Nitin; Dorr, Bonnie J (Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2010)
This work represents an initial attempt to move beyond "single-shot" summarization to interactive summarization. We present an extension to the classic Maximal Marginal Relevance (MMR) algorithm that places a user "in the loop" to assist in candidate selection. Experiments in the complex interactive Question Answering (ciQA) task at TREC 2007 show that interactively-constructed responses are significantly higher in quality than automatically-generated ones. This novel algorithm provides a starting point for future work on interactive summarization.

Random sampling for estimating the performance of fast summations - Srinivasan,Balaji Vasan; Duraiswami, Ramani (Technical Reports of the Computer Science Department, 2010)
Summation of functions of N source points evaluated at M target pointsoccurs commonly in many applications. To scale these approaches for large datasets, many fast algorithms have been proposed. In this technical report, we propose a Chernoff bound based efficient approach to test the performance of a fast summation algorithms providing a probabilistic accuracy. We further validate and use our approach in separate comparisons.
Keywords: Technical Report

Ranking continuous probabilistic datasets - Li,Jian; Deshpande, Amol (Proc. VLDB Endow., 2010)
Ranking is a fundamental operation in data analysis and decision support, and plays an even more crucial role if the dataset being explored exhibits uncertainty. This has led to much work in understanding how to rank uncertain datasets in recent years. In this paper, we address the problem of ranking when the tuple scores are uncertain, and the uncertainty is captured using continuous probability distributions (e.g. Gaussian distributions). We present a comprehensive solution to compute the values of a parameterized ranking function (PRF) [18] for arbitrary continuous probability distributions (and thus rank the uncertain dataset); PRF can be used to simulate or approximate many other ranking functions proposed in prior work. We develop exact polynomial time algorithms for some continuous probability distribution classes, and efficient approximation schemes with provable guarantees for arbitrary probability distributions. Our algorithms can also be used for exact or approximate evaluation of k-nearest neighbor queries over uncertain objects, whose positions are modeled using continuous probability distributions. Our experimental evaluation over several datasets illustrates the effectiveness of our approach at efficiently ranking uncertain datasets with continuous attribute uncertainty.

Read-once functions and query evaluation in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proc. VLDB Endow., 2010)
Probabilistic databases hold promise of being a viable means for large-scale uncertainty management, increasingly needed in a number of real world applications domains. However, query evaluation in probabilistic databases remains a computational challenge. Prior work on efficient exact query evaluation in probabilistic databases has largely concentrated on query-centric formulations (e.g., safe plans, hierarchical queries), in that, they only consider characteristics of the query and not the data in the database. It is easy to construct examples where a supposedly hard query run on an appropriate database gives rise to a tractable query evaluation problem. In this paper, we develop efficient query evaluation techniques that leverage characteristics of both the query and the data in the database. We focus on tuple-independent databases where the query evaluation problem is equivalent to computing marginal probabilities of Boolean formulas associated with the result tuples. This latter task is easy if the Boolean formulas can be factorized into a form that has every variable appearing at most once (called read-once). However, a naive approach that directly uses previously developed Boolean formula factorization algorithms is inefficient, because those algorithms require the input formulas to be in the disjunctive normal form (DNF). We instead develop novel, more efficient factorization algorithms that directly construct the read-once expression for a result tuple Boolean formula (if one exists), for a large subclass of queries (specifically, conjunctive queries without self-joins). We empirically demonstrate that (1) our proposed techniques are orders of magnitude faster than generic inference algorithms for queries where the result Boolean formulas can be factorized into read-once expressions, and (2) for the special case of hierarchical queries, they rival the efficiency of prior techniques specifically designed to handle such queries.

A robust and scalable approach to face identification - Schwartz,W.; Guo,H.; Davis, Larry S. (Computer Vision–ECCV 2010, 2010)
The problem of face identification has received significant attention over the years. For a given probe face, the goal of face identification is to match this unknown face against a gallery of known people. Due to the availability of large amounts of data acquired in a variety of conditions, techniques that are both robust to uncontrolled acquisition conditions and scalable to large gallery sizes, which may need to be incrementally built, are challenges. In this work we tackle both problems. Initially, we propose a novel approach to robust face identification based on Partial Least Squares (PLS) to perform multi-channel feature weighting. Then, we extend the method to a tree-based discriminative structure aiming at reducing the time required to evaluate novel probe samples. The method is evaluated through experiments on FERET and FRGC datasets. In most of the comparisons our method outperforms state-of-art face identification techniques. Furthermore, our method presents scalability to large datasets.

Shape analysis and its applications in image understanding - Zhe Lin; Davis, Larry S. (IEEE transactions on pattern analysis and machine intelligence, 2010)
We propose a shape-based, hierarchical part-template matching approach to simultaneous human detection and segmentation combining local part-based and global shape-template-based schemes. The approach relies on the key idea of matching a part-template tree to images hierarchically to detect humans and estimate their poses. For learning a generic human detector, a pose-adaptive feature computation scheme is developed based on a tree matching approach. Instead of traditional concatenation-style image location-based feature encoding, we extract features adaptively in the context of human poses and train a kernel-SVM classifier to separate human/nonhuman patterns. Specifically, the features are collected in the local context of poses by tracing around the estimated shape boundaries. We also introduce an approach to multiple occluded human detection and segmentation based on an iterative occlusion compensation scheme. The output of our learned generic human detector can be used as an initial set of human hypotheses for the iterative optimization. We evaluate our approaches on three public pedestrian data sets (INRIA, MIT-CBCL, and USC-B) and two crowded sequences from Caviar Benchmark and Munich Airport data sets.

Shape-based human detection and segmentation via hierarchical part-template matching - Lin,Z.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010)
We propose a shape-based, hierarchical part-template matching approach to simultaneous human detection and segmentation combining local part-based and global shape-template-based schemes. The approach relies on the key idea of matching a part-template tree to images hierarchically to detect humans and estimate their poses. For learning a generic human detector, a pose-adaptive feature computation scheme is developed based on a tree matching approach. Instead of traditional concatenation-style image location-based feature encoding, we extract features adaptively in the context of human poses and train a kernel-SVM classifier to separate human/nonhuman patterns. Specifically, the features are collected in the local context of poses by tracing around the estimated shape boundaries. We also introduce an approach to multiple occluded human detection and segmentation based on an iterative occlusion compensation scheme. The output of our learned generic human detector can be used as an initial set of human hypotheses for the iterative optimization. We evaluate our approaches on three public pedestrian data sets (INRIA, MIT-CBCL, and USC-B) and two crowded sequences from Caviar Benchmark and Munich Airport data sets.

Sharing-aware horizontal partitioning for exploiting correlations during query processing - Tzoumas,Kostas; Deshpande, Amol; Jensen,Christian S. (Proc. VLDB Endow., 2010)
Optimization of join queries based on average selectivities is suboptimal in highly correlated databases. In such databases, relations are naturally divided into partitions, each partition having substantially different statistical characteristics. It is very compelling to discover such data partitions during query optimization and create multiple plans for a given query, one plan being optimal for a particular combination of data partitions. This scenario calls for the sharing of state among plans, so that common intermediate results are not recomputed. We study this problem in a setting with a routing-based query execution engine based on eddies [1]. Eddies naturally encapsulate horizontal partitioning and maximal state sharing across multiple plans. We define the notion of a conditional join plan, a novel representation of the search space that enables us to address the problem in a principled way. We present a low-overhead greedy algorithm that uses statistical summaries based on graphical models. Experimental results suggest an order of magnitude faster execution time over traditional optimization for high correlations, while maintaining the same performance for low correlations.

Signal Processing for Audio HCI - Zotkin,Dmitry N; Duraiswami, Ramani (Handbook of Signal Processing Systems, 2010)
This chapter reviews recent advances in computer audio processing from the viewpoint of improving the human-computer interface. Microphone arrays are described as basic tools for untethered audio acquisition, and principles for the synthesis of realistic virtual audio are outlined. The influence of room acoustics on audio acquisition and production is also considered. The chapter finishes with a review of several relevant signal processing systems, including a fast head-related transfer function (HRTF) measurement system and a complete system for capture, visualization, and reproduction of auditory scenes.

Spatial indexing on tetrahedral meshes - De Floriani, Leila; Fellegara,Riccardo; Magillo,Paola (Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2010)
We address the problem of performing spatial queries on tetrahedral meshes. These latter arise in several application domains including 3D GIS, scientific visualization, finite element analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral trees. Tetrahedral trees subdivide a cubic domain containing the mesh in an octree or 3D kd-tree fashion, with three different subdivision criteria. Here, we present and compare such indexes, their memory usage, and spatial queries on them.
Keywords: kd-trees; octrees; spatial indexes; tetrahedral meshes

SPECIAL SECTION ON SHAPE ANALYSIS AND ITS APPLICATIONS IN IMAGE UNDERSTANDING - Srivastava, A.; Damon,J.N.; Dryden,I.L.; Jermyn,I.H.; Das,S.; Vaswani, N.; Huckemann,S.; Hotz,T.; Munk,A.; Lin,Z.; others (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010)

System and method for analysis of an opinion expressed in documents with regard to a particular topic - V.S. Subrahmanian; Picariello,Antonio; Dorr, Bonnie J; Reforgiato,Diego Recupero; Cesarano,Carmine; Sagoff,Amelia (2010)
System and method for analysis of an opinion expressed in documents on a particular topic computes opinion strength on a continuous numeric scale, or qualitatively. A variety of opinion scoring techniques are plugged in to score opinion expressing words and sentences in documents. These scores are aggregated to measure the opinion intensity of documents. Multilingual opinion analysis is supported by capability to concurrently identify and visualize the opinion intensity expressed in documents in multiple languages. A multi-dimensional representation of the measured opinion intensity is generated which is agreeable with multi-lingual domain.

To Upgrade or Not to Upgrade: Impact of Online Upgrades Across Multiple Administrative Domains - Tudor Dumitras; Narasimhan, Priya; Tilevich, Eli (OOPSLA'10 Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, 2010)
Online software upgrades are often plagued by runtime behaviors that are poorly understood and difficult to ascertain. For example, the interactions among multiple versions of the software expose the system to race conditions that can introduce latent errors or data corruption. Moreover, industry trends suggest that online upgrades are currently needed in large-scale enterprise systems, which often span multiple administrative domains (e.g., Web 2.0 applications that rely on AJAX client-side code or systems that lease cloud-computing resources). In such systems, the enterprise does not control all the tiers of the system and cannot coordinate the upgrade process, making existing techniques inadequate to prevent mixed-version races. In this paper, we present an analytical framework for impact assessment, which allows system administrators to directly compare the risk of following an online-upgrade plan with the risk of delaying or canceling the upgrade. We also describe an executable model that implements our formal impact assessment and enables a systematic approach for deciding whether an online upgrade is appropriate. Our model provides a method of last resort for avoiding undesirable program behaviors, in situations where mixed-version races cannot be avoided through other technical means.
Keywords: mixed-version race; multiple administrative domains; online upgrade; risk assessment

Toque: designing a cooking-based programming language for and with children - Tarkan,S.; Sazawal,V.; Druin, Allison; Golub,E.; Bonsignore,E. M; Walsh,G.; Atrash,Z. (Proceedings of the 28th international conference on Human factors in computing systems, 2010)

A tree-based approach to integrated action localization, recognition and segmentation - Zhuolin Jiang; Lin,Z.; Davis, Larry S. (ECCV Workshops, 2010)
A tree-based approach to integrated action segmentation,localization and recognition is proposed. An action is represented as a sequence of joint hog-flow descriptors extracted independently from each frame. During training, a set of action prototypes is first learned based on a k-means clustering, and then a binary tree model is constructed from the set of action prototypes based on hierarchical k-means cluster- ing. Each tree node is characterized by a shape-motion descriptor and a rejection threshold, and an action segmentation mask is defined for leaf nodes (corresponding to a prototype). During testing, an action is local- ized by mapping each test frame to a nearest neighbor prototype using a fast matching method to search the learned tree, followed by global fil- tering refinement. An action is recognized by maximizing the sum of the joint probabilities of the action category and action prototype over test frames. Our approach does not explicitly rely on human tracking and background subtraction, and enables action localization and recognition in realistic and challenging conditions (such as crowded backgrounds). Experimental results show that our approach can achieve recognition rates of 100% on the CMU action dataset and 100% on the Weizmann dataset.

Using a Trust Model in Decision Making for Supply Chain Management - Haghpanah,Y.; desJardins, Marie; others (Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010)

Utilizing Hierarchical Multiprocessing for Medical Image Registration - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (IEEE Signal Processing Magazine, 2010)
This work discusses an approach to utilize hierarchical multiprocessing in the context of medical image registration. By first organizing application parallelism into a domain-specific taxonomy, an algorithm is structured to target a set of multicore platforms.The approach on a cluster of graphics processing units (GPUs) requiring the use of two parallel programming environments to achieve fast execution times is demonstrated.There is negligible loss in accuracy for rigid registration when employing GPU acceleration, but it does adversely effect our nonrigid registration implementation due to our usage of a gradient descent approach.
Keywords: Acceleration; application parallelism; Biomedical imaging; domain-specific taxonomy; GPU acceleration; gradient descent approach; Graphics processing unit; hierarchical multiprocessing; image registration; Magnetic resonance imaging; Medical diagnostic imaging; medical image processing; medical image registration; multicore platform set; Multicore processing; PARALLEL PROCESSING; parallel programming; Robustness; Signal processing algorithms; Ultrasonic imaging

Web-scale computer vision using MapReduce for multimedia data mining - White,Brandyn; Tom Yeh; Jimmy Lin; Davis, Larry S. (Proceedings of the Tenth International Workshop on Multimedia Data Mining, 2010)
This work explores computer vision applications of the MapReduce framework that are relevant to the data mining community. An overview of MapReduce and common design patterns are provided for those with limited MapReduce background. We discuss both the high level theory and the low level implementation for several computer vision algorithms: classifier training, sliding windows, clustering, bag-of-features, background subtraction, and image registration. Experimental results for the k-means clustering and single Gaussian background subtraction algorithms are performed on a 410 node Hadoop cluster.
Keywords: background subtraction; bag-of-features; Cloud computing; clustering; Computer vision; image registration; MapReduce

Which Factors Affect Access Network Performance? - Sundaresan,S.; Feamster, Nick; Dicioccio,L.; Teixeira,R. (Georgia Institute of Technology, 2010)
This paper presents an analysis of the performance of residential access networks using over four months of round-trip, download, and upload measurements from more than 7,000 users across four ADSL and cable providers in France. Previous studies have characterized residential access network performance, but this paper presents the first study of how access network performance relates to other factors, such as choice of access provider, service-level agreement, and geographic location. We first explore the extent to which user performance matches the capacity advertised by an access provider, and whether the ability to achieve this capacity depends on the user’s access network. We then analyze the extent to which various factors influence the performance that users experience. Finally, we explore how different groups of users experience simultaneous performance anomalies and analyze the common characteristics of users that share fate (e.g., whether users that experience simultaneous performance degradation share the same provider, city). Our analysis informs both users and designers of networked services who wish to improve the reliability and performance of access networks through multihoming and may also assist operators with troubleshooting network issues by narrowing down likely causes.

Why Did the Person Cross the Road (There)? Scene Understanding Using Probabilistic Logic Models and Common Sense Reasoning - Kembhavi,Aniruddha; Tom Yeh; Davis, Larry S. (Computer Vision – ECCV 2010, 2010)
We develop a video understanding system for scene elements, such as bus stops, crosswalks, and intersections, that are characterized more by qualitative activities and geometry than by intrinsic appearance. The domain models for scene elements are not learned from a corpus of video, but instead, naturally elicited by humans, and represented as probabilistic logic rules within a Markov Logic Network framework. Human elicited models, however, represent object interactions as they occur in the 3D world rather than describing their appearance projection in some specific 2D image plane. We bridge this gap by recovering qualitative scene geometry to analyze object interactions in the 3D world and then reasoning about scene geometry, occlusions and common sense domain knowledge using a set of meta-rules. The effectiveness of this approach is demonstrated on a set of videos of public spaces.

Workshop on experimental evaluation of software and systems in computer science (Evaluate 2010) - Blackburn,Steven M.; Diwan,Amer; Hauswirth,Matthias; Memon, Atif M.; Sweeney,Peter F. (Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, 2010)
We call ourselves 'computer scientists', but are we scientists? If we are scientists, then we must practice the scientific method. This includes a solid experimental evaluation. In our experience, our experimental methodology is ad hoc at best, and nonexistent at worst. This workshop brings together experts from different areas of computer science to discuss, explore, and attempt to identify the principles of sound experimental evaluation
Keywords: Evaluation; METHODOLOGY

Action recognition based on human movement characteristics - Dondera,R.; David Doermann; Davis, Larry S. (Motion and Video Computing, 2009. WMVC '09. Workshop on, 2009)
We present a motion descriptor for human action recognition where appearance and shape information are unreliable. Unlike other motion-based approaches, we leverage image characteristics specific to human movement to achieve better robustness and lower computational cost. Drawing on recent work on motion recognition with ballistic dynamics, an action is modeled as a series of short correlated linear movements and represented with a probability density function over motion vector data. We are targeting common human actions composed of ballistic movements, and our descriptor can handle both short actions (e.g. reaching with the hand) and long actions with events at relatively stable time offsets (e.g. walking). The proposed descriptor is used for both classification and detection of action instances, in a nearest-neighbor framework. We evaluate the descriptor on the KTH action database and obtain a recognition rate of 90% in a relevant test setting, comparable to the state-of-the-art approaches that use other cues in addition to motion. We also acquired a database of actions with slight occlusion and a human actor manipulating objects of various shapes and appearances. This database makes the use of appearance and shape information problematic, but we obtain a recognition rate of 95%. Our work demonstrates that human movement has distinctive patterns, and that these patterns can be used effectively for action recognition.
Keywords: action; ballistic; characteristics; motion; correlated; cost; human; data; probability; databases; density; descriptor; motion; dynamics; computational; function; robustness; shape; information; short; linear; Movement; movements; computer; recognition; human; recognition; stability; visual; vector; vision; pattern

Algorithms for distributional and adversarial pipelined filter ordering problems - Condon,Anne; Deshpande, Amol; Hellerstein,Lisa; Wu,Ning (ACM Trans. Algorithms, 2009)
Pipelined filter ordering is a central problem in database query optimization. The problem is to determine the optimal order in which to apply a given set of commutative filters (predicates) to a set of elements (the tuples of a relation), so as to find, as efficiently as possible, the tuples that satisfy all of the filters. Optimization of pipelined filter ordering has recently received renewed attention in the context of environments such as the Web, continuous high-speed data streams, and sensor networks. Pipelined filter ordering problems are also studied in areas such as fault detection and machine learning under names such as learning with attribute costs, minimum-sum set cover, and satisficing search. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional-type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial-type problem where the goal is to minimize the expected value of multiplicative regret. We present two related algorithms for solving (1), both running in time O(n2), which improve on the O(n3 log n) algorithm of Kodialam. We use techniques from our algorithms for (1) to obtain an algorithm for (2).
Keywords: flow algorithms; Pipelined filter ordering; Query optimization; selection ordering

Analyzing (social media) networks with NodeXL - Smith,Marc A.; Shneiderman, Ben; Milic-Frayling,Natasa; Mendes Rodrigues,Eduarda; Barash,Vladimir; Dunne,Cody; Capone,Tony; Perer,Adam; Gleave,Eric (Proceedings of the fourth international conference on Communities and technologies, 2009)
We present NodeXL, an extendible toolkit for network overview, discovery and exploration implemented as an add-in to the Microsoft Excel 2007 spreadsheet software. We demonstrate NodeXL data analysis and visualization features with a social media data sample drawn from an enterprise intranet social network. A sequence of NodeXL operations from data import to computation of network statistics and refinement of network visualization through sorting, filtering, and clustering functions is described. These operations reveal sociologically relevant differences in the patterns of interconnection among employee participants in the social media space. The tool and method can be broadly applied.
Keywords: excel; network analysis; social media; social network; spreadsheet; Visualization

Assigning cameras to subjects in video surveillance systems - El-Alfy,H.; Jacobs, David W.; Davis, Larry S. (Robotics and Automation, 2009. ICRA '09. IEEE International Conference on, 2009)
We consider the problem of tracking multiple agents moving amongst obstacles, using multiple cameras. Given an environment with obstacles, and many people moving through it, we construct a separate narrow field of view video for as many people as possible, by stitching together video segments from multiple cameras over time. We employ a novel approach to assign cameras to people as a function of time, with camera switches when needed. The problem is modeled as a bipartite graph and the solution corresponds to a maximum matching. As people move, the solution is efficiently updated by computing an augmenting path rather than by solving for a new matching. This reduces computation time by an order of magnitude. In addition, solving for the shortest augmenting path minimizes the number of camera switches at each update. When not all people can be covered by the available cameras, we cluster as many people as possible into small groups, then assign cameras to groups using a minimum cost matching algorithm. We test our method using numerous runs from different simulators.
Keywords: agent; algorithm; multiple; assignment; computation; augmenting; cameras; video; cost; detection; video; graph; camera; MATCHING; matching; minimum; matching; target; path; bipartite; reduction; maximum; segment; video; Surveillance; surveillance; system; graph; theory; image; TIME; tracking; obstacle; tracking; video; video

Avid interactions underlie the Lys63-linked polyubiquitin binding specificities observed for UBA domains - Sims,Joshua J.; Haririnia,Aydin; Dickinson,Bryan C.; Fushman, David; Cohen,Robert E. (Nature Structural & Molecular Biology, 2009)
Ubiquitin (denoted Ub) receptor proteins as a group must contain a diverse set of binding specificities to distinguish the many forms of polyubiquitin (polyUb) signals. Previous studies suggested that the large class of ubiquitin-associated (UBA) domains contains members with intrinsic specificity for Lys63-linked polyUb or Lys48-linked polyUb, thus explaining how UBA-containing proteins can mediate diverse signaling events. Here we show that previously observed Lys63-polyUb selectivity in UBA domains is the result of an artifact in which the dimeric fusion partner, glutathione S-transferase (GST), positions two UBAs for higher affinity, avid interactions with Lys63-polyUb, but not with Lys48-polyUb. Freed from GST, these UBAs are either nonselective or prefer Lys48-polyUb. Accordingly, NMR experiments reveal no Lys63-polyUb–specific binding epitopes for these UBAs. We reexamine previous conclusions based on GST-UBAs and present an alternative model for how UBAs achieve a diverse range of linkage specificities.
Keywords: apoptosis; basic cellular processes; Biochemistry; biophysics; cell biology; cell cycle; cell surface proteins; cell-cell interactions; checkpoints; chromatin; chromatin remodeling; chromatin structure; content; DNA recombination; DNA repair; DNA replication; Gene expression; Genetics; intracellular signaling; journal; macromolecules; mechanism; membrane processes; molecular; molecular basis of disease; molecular biology; molecular interactions; multi-component complexes; nature publishing group; nature structural molecular biology; nucleic acids; protein degradation; protein folding; protein processing; Proteins; regulation of transcription; regulation of translation; RNA; RNA processing; RNAi; signal transduction; single molecule studies; structure and function of proteins; transcription; translation

Bayesian multitask learning with latent hierarchies - Daumé, Hal (Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009)

Bisimulation-based approximate lifted inference - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009)
There has been a great deal of recent interest in methods for performing lifted inference; however, most of this work assumes that the first-order model is given as input to the system. Here, we describe lifted inference algorithms that determine symmetries and automatically lift the probabilistic model to speedup inference. In particular, we describe approximate lifted inference techniques that allow the user to trade off inference accuracy for computational efficiency by using a handful of tunable parameters, while keeping the error bounded. Our algorithms are closely related to the graph-theoretic concept of bisimulation. We report experiments on both synthetic and real data to show that in the presence of symmetries, run-times for inference can be improved significantly, with approximate lifted inference providing orders of magnitude speedup over ground inference.

A broadband fast multipole accelerated boundary element method for the three dimensional Helmholtz equation - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2009)
The development of a fast multipole method (FMM) accelerated iterative solution of the boundary element method (BEM) for the Helmholtz equations in three dimensions is described. The FMM for the Helmholtz equation is significantly different for problems with low and high kD (where k is the wavenumber and D the domain size), and for large problems the method must be switched between levels of the hierarchy. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements), and these errors must be balanced against approximations introduced by the FMM and the convergence criterion for iterative solution. These different errors must all be chosen in a way that, on the one hand, excess work is not done and, on the other, that the error achieved by the overall computation is acceptable. Details of translation operators for low and high kD, choice of representations, and BEM quadrature schemes, all consistent with these approximations, are described. A novel preconditioner using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed solvers for large boundary value problems with 0.0001≲kD≲500 are presented and shown to perform close to theoretical expectations.
Keywords: acoustic wave scattering; boundary-elements methods; boundary-value problems; Helmholtz equations; iterative methods

Call for Papers: Special Issue of the Journal of Parallel and Distributed Computing: Cloud Computing - Chockler,Gregory; Dekel,Eliezer; JaJa, Joseph F.; Jimmy Lin (J. Parallel Distrib. Comput., 2009)

Chance-constrained programs for link prediction - Doppa,J.R.; Yu,J.; Tadepalli,P.; Getoor, Lise (Proceedings of Workshop on Analyzing Networks and Learning with Graphs at NIPS Conference, 2009)
In this paper, we consider the link prediction problem, where we are given a par-tial snapshot of a network at some time and the goal is to predict additional links at a later time. The accuracy of the current prediction methods is quite low due to the extreme class skew and the large number of potential links. In this paper, we describe learning algorithms based on chance constrained programs and show that they exhibit all the properties needed for a good link predictor, namely, al- low preferential bias to positive or negative class; handle skewness in the data; and scale to large networks. Our experimental results on three real-world co- authorship networks show significant improvement in prediction accuracy over baseline algorithms.

Classification of non-manifold singularities from transformations of 2-manifolds - Leon,J.-C.; De Floriani, Leila; Hetroy,F. (Shape Modeling and Applications, 2009. SMI 2009. IEEE International Conference on, 2009)
Non-manifold models are frequently encountered in engineering simulations and design as well as in computer graphics. However, these models lack shape characterization for modelling and searching purposes. Topological properties act as a kernel for deriving key features of objects. Here we propose a classification for the non-manifold singularities of non-manifold objects through continuous shape transformations of 2-manifolds without boundary up to the creation of non-manifold singularities. As a result, the non-manifold objects thus created can be categorized and contribute to the definition of a general purpose taxonomy for non-manifold shapes.
Keywords: classification; search; Computer; graphic; continuous; graphics; pattern; model; nonmanifold; problems; topology; property; computer; SHAPE; singularity; topological; transformation; nonmanifold

Clutter Noise Removal in Binary Document Images - Agrawal,Mudit; David Doermann (International Conference on Document Analysis and Recognition (ICDAR '09), 2009)
The paper presents a clutter detection and removal algorithm for complex document images. The distance transform based approach is independent of clutter's position, size, shape and connectivity with text. Features are based on a new technique called `nth erosion' and clutter elements are identified with an SVM classifier. Removal is restrictive, so text attached to the clutter is not deleted in the process. The method was tested on a mix of degraded and noisy, machine-printed and handwritten Arabic and English text documents. Results show pixel-level accuracies of 97.5% and 95% for clutter detection and removal respectively. This approach was also extended with a noise detection and removal model for documents having a mix of clutter and salt-n-pepper noise.

Combining multiple kernels for efficient image classification - Siddiquie,B.; Vitaladevuni,S.N.; Davis, Larry S. (Applications of Computer Vision (WACV), 2009 Workshop on, 2009)
We investigate the problem of combining multiple feature channels for the purpose of efficient image classification. Discriminative kernel based methods, such as SVMs, have been shown to be quite effective for image classification. To use these methods with several feature channels, one needs to combine base kernels computed from them. Multiple kernel learning is an effective method for combining the base kernels. However, the cost of computing the kernel similarities of a test image with each of the support vectors for all feature channels is extremely high. We propose an alternate method, where training data instances are selected, using AdaBoost, for each of the base kernels. A composite decision function, which can be evaluated by computing kernel similarities with respect to only these chosen instances, is learnt. This method significantly reduces the number of kernel computations required during testing. Experimental results on the benchmark UCI datasets, as well as on a challenging painting dataset, are included to demonstrate the effectiveness of our method.
Keywords: (artificial; AdaBoost; base; channels; multiple; classification; kernel; classification; learning; decision; feature; function; discriminative; intelligence); support; Kernel; kernel; image; kernels; composite; learning; support; machine; image; machines; similarity; multiple; vector

Complete Genome Sequence of Aggregatibacter (Haemophilus) Aphrophilus NJ8700 - Di Bonaventura,Maria Pia; DeSalle,Rob; Pop, Mihai; Nagarajan,Niranjan; Figurski,David H; Fine,Daniel H; Kaplan,Jeffrey B; Planet,Paul J (Journal of BacteriologyJ. Bacteriol., 2009)
We report the finished and annotated genome sequence of Aggregatibacter aphrophilus strain NJ8700, a strain isolated from the oral flora of a healthy individual, and discuss characteristics that may affect its dual roles in human health and disease. This strain has a rough appearance, and its genome contains genes encoding a type VI secretion system and several factors that may participate in host colonization.

Composability and on-line deniability of authentication - Dodis,Y.; Katz, Jonathan; Smith,A.; Walfish,S. (Theory of Cryptography, 2009)
Protocols for deniable authentication achieve seemingly paradoxical guarantees: upon completion of the protocol the receiver is convinced that the sender authenticated the message, but neither party can convince anyone else that the other party took part in the protocol. We introduce and study on-line deniability, where deniability should hold even when one of the parties colludes with a third party during execution of the protocol. This turns out to generalize several realistic scenarios that are outside the scope of previous models.We show that a protocol achieves our definition of on-line deniability if and only if it realizes the message authentication functionality in the generalized universal composability framework; any protocol satisfying our definition thus automatically inherits strong composability guarantees. Unfortunately, we show that our definition is impossible to realize in the PKI model if adaptive corruptions are allowed (even if secure erasure is assumed). On the other hand, we show feasibility with respect to static corruptions (giving the first separation in terms of feasibility between the static and adaptive setting), and show how to realize a relaxation termed deniability with incriminating abort under adaptive corruptions.

A Comprehensive Evaluation Framework and a Comparative Study for Human Detectors - Hussein,M.; Porikli, F.; Davis, Larry S. (Intelligent Transportation Systems, IEEE Transactions on, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.
Keywords: classification; infrared; classifier; comprehensive; curve; INRIA; dataset; average; DET; DETECTION; detection; detector; image; error; Evaluation; framework; cropped; image; image; imaging; object; log; miss; person; rate; cascade; rate; feature; rate; multisize; resize; human; resize; miss; scanning; near-infrared; sliding-window; tradeoff; false-alarm; window; detection

Computation of singular and hypersingular boundary integrals by Green identity and application to boundary value problems - Seydou,F.; Duraiswami, Ramani; Seppänen,T.; Gumerov, Nail A. (Engineering Analysis with Boundary Elements, 2009)
The problem of computing singular and hypersingular integrals involved in a large class of boundary value problems is considered. The method is based on Green's theorem for calculating the diagonal elements of the resulting discretized matrix using the Nyström discretization method. The method is successfully applied to classical boundary value problems. Convergence of the method is also discussed.
Keywords: Bounday integral method; Green identity; Hypersingular integrals; Nyström method; Singular integrals

Computation of the head-related transfer function via the boundary element method and representation via the spherical harmonic spectrum - Gumerov, Nail A.; O'donovan,Adam; Duraiswami, Ramani; Zotkin,Dmitry N (Technical Reports from UMIACS UMIACS-TR-2009-06, 2009)
The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle, by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs.HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models (for the “Fritz” and “Kemar”), and head and torso model (the Kemar manikin). Comparisons between the different cases and analysis of limiting cases is provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data is available. Our results show that, given a good mesh it is feasible to compute the HRTF over the full audible range on a regular personal computer.
Keywords: Technical Report

Computing and visualizing a graph-based decomposition for non-manifold shapes - De Floriani, Leila; Panozzo,D.; Hui,A. (Graph-Based Representations in Pattern Recognition, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an effective support to modeling, analyzing and understanding non-manifold shapes.

On Computing Compression Trees for Data Collection in Sensor Networks - Li,Jian; Deshpande, Amol; Khuller, Samir (arXiv:0907.5442, 2009)
We address the problem of efficiently gathering correlated data from a wired or a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal {\em compression tree} for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We consider this problem under different communication models, including the {\em broadcast communication} model that enables many new opportunities for energy-efficient data collection. We draw connections between the data collection problem and a previously studied graph concept, called {\em weakly connected dominating sets}, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
Keywords: Computer Science - Information Theory; Computer Science - Networking and Internet Architecture

Concurrent transition and shot detection in football videos using Fuzzy Logic - Refaey,M.A.; Elsayed,K.M.; Hanafy,S.M.; Davis, Larry S. (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
Shot detection is a fundamental step in video processing and analysis that should be achieved with high degree of accuracy. In this paper, we introduce a unified algorithm for shot detection in sports video using fuzzy logic as a powerful inference mechanism. Fuzzy logic overcomes the problems of hard cut thresholds and the need to large training data used in previous work. The proposed algorithm integrates many features like color histogram, edgeness, intensity variance, etc. Membership functions to represent different features and transitions between shots have been developed to detect different shot boundary and transition types. We address the detection of cut, fade, dissolve, and wipe shot transitions. The results show that our algorithm achieves high degree of accuracy.
Keywords: analysis; inference; boundary; shot; Color; colour; detection; sports; functions; shot; histogram; concurrent; logic; image; logic; inference; mechanism; intensity; mechanisms; sport; video; processing; processing; videonanalysis; fuzzy; signal; transition; edgeness; football; variance; membership; video; video; videos; fuzzy

Consensus answers for queries over probabilistic databases - Li,Jian; Deshpande, Amol (Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2009)
We address the problem of finding a "best" deterministic query answer to a query over a probabilistic database. For this purpose, we propose the notion of a consensus world (or a consensus answer) which is a deterministic world (answer) that minimizes the expected distance to the possible worlds (answers). This problem can be seen as a generalization of the well-studied inconsistent information aggregation problems (e.g. rank aggregation) to probabilistic databases. We consider this problem for various types of queries including SPJ queries, Top-k ranking queries, group-by aggregate queries, and clustering. For different distance metrics, we obtain polynomial time optimal or approximation algorithms for computing the consensus answers (or prove NP-hardness). Most of our results are for a general probabilistic database model, called and/xor tree model, which significantly generalizes previous probabilistic database models like x-tuples and block-independent disjoint models, and is of independent interest.
Keywords: consensus answers; probabilistic and/xor tree; Probabilistic databases; Query processing; rank aggregation

A cost-effective lexical acquisition process for large-scale thesaurus translation - Jimmy Lin; Murray,G. C; Dorr, Bonnie J; Hajič,J.; Pecina,P. (Language resources and evaluation, 2009)
Thesauri and controlled vocabularies facilitate access to digital collections by explicitly representing the underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most thesauri precludes fully-automatic translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations to construct domain-specific lexical resources. This process is illustrated on a thesaurus of 56,000 concepts used to catalog a large archive of oral histories. We elicited human translations on a small subset of concepts, induced a probabilistic phrase dictionary from these translations, and used the resulting resource to automatically translate the rest of the thesaurus. Two separate evaluations demonstrate the acceptability of the automatic translations and the cost-effectiveness of our approach.

Cross-document coreference resolution: A key technology for learning by reading - Mayfield,J.; Alexander,D.; Dorr, Bonnie J; Eisner,J.; Elsayed,T.; Finin,T.; Fink,C.; Freedman,M.; Garera,N.; McNamee,P.; others (AAAI Spring Symposium on Learning by Reading and Learning to Read, 2009)

Dependable, Online Upgrades in Enterprise Systems - Tudor Dumitras (OOPSLA'09 Proceedings of the 24th ACM SIGPLAN Conference Companion on Object Oriented Programming Systems Languages and Applications, 2009)
Software upgrades are unreliable, often causing downtime or data loss. I propose Imago, an approach for removing the leading causes of upgrade failures (broken dependencies) and of planned downtime (data migrations). While imposing a higher resource overhead than previous techniques, Imago is more dependable and easier to use correctly.
Keywords: data migration; Dependability; hidden dependencies; online upgrades; software upgrades

Designing the reading experience for scanned multi-lingual picture books on mobile phones - Bederson, Benjamin B.; Quinn,A.; Druin, Allison (Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries, 2009)

Diamond Hierarchies of Arbitrary Dimension - Weiss,Kenneth; De Floriani, Leila (Computer Graphics Forum, 2009)
Nested simplicial meshes generated by the simplicial bisection decomposition proposed by Maubach [Mau95] have been widely used in 2D and 3D as multi-resolution models of terrains and three-dimensional scalar fields, They are an alternative to octree representation since they allow generating crack-free representations of the underlying field. On the other hand, this method generates conforming meshes only when all simplices sharing the bisection edge are subdivided concurrently. Thus, efficient representations have been proposed in 2D and 3D based on a clustering of the simplices sharing a common longest edge in what is called a diamond. These representations exploit the regularity of the vertex distribution and the diamond structure to yield an implicit encoding of the hierarchical and geometric relationships among the triangles and tetrahedra, respectively. Here, we analyze properties of d-dimensional diamonds to better understand the hierarchical and geometric relationships among the simplices generated by Maubach's bisection scheme and derive closed-form equations for the number of vertices, simplices, parents and children of each type of diamond. We exploit these properties to yield an implicit pointerless representation for d-dimensional diamonds and reduce the number of required neighbor-finding accesses from O(d!) to O(d).
Keywords: I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling—Hierarchy and geometric transformations; I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures and data types

Digital forensics [From the Guest Editors] - Delp,E.; Memon, N.; Wu,M. (Signal Processing Magazine, IEEE, 2009)
This special issue provides a comprehensive overview of recent developments and open problems in digital forensics that are amenable to signal processing techniques.

A dimension-independent library for building and manipulating multiresolution triangulations - De Floriani, Leila; Magillo,P.; Puppo,E. (Department of Computer Science and Information Science, University of Genoa, 2009)
A Multi-Triangulation (MT) is a general multiresolution model for representing k-dimensional geometricobjects through simplicial complexes. An MT integrates several alternative representations of an object, and provides simple methods for handling representations at variable resolution efficiently , thus offering a basis for the development of applications that need to manage the level-of-detail of complex objects. In this paper, we present an object-oriented library that provides an open-ended tool for building and manipulating object representations based on the MT.

Discrete distortion for surface meshes - Mesmoudi,M.; De Floriani, Leila; Magillo,P. (Image Analysis and Processing–ICIAP 2009, 2009)
Discrete distortion for two- and three-dimensional combinatorial manifolds is a discrete alternative to Ricci curvature known for differentiable manifolds. Here, we show that distortion can be successfully used to estimate mean curvature at any point of a surface. We compare our approach with the continuous case and with a common discrete approximation of mean curvature, which depends on the area of the star of each vertex in the triangulated surface. This provides a new, area-independent, tool for curvature estimation and for morphological shape analysis. We illustrate our approach through experimental results showing the behavior of discrete distortion.

Ef?cient Query Evaluation over Temporally Correlated Probabilistic Streams - Kanagal,B.; Deshpande, Amol (IEEE 25th International Conference on Data Engineering, 2009. ICDE '09, 2009)
In this paper, we address the problem of efficient query evaluation over highly correlated probabilistic streams. We observe that although probabilistic streams tend to be strongly correlated in space and time, the correlations are usually quite structured (i.e., the same set of dependencies and independences repeat across time) and Markovian (i.e., the state at time "t+1" is independent of the states at previous times given the state at time "t"). We exploit this observation to compactly encode probabilistic streams by decoupling the correlation structure (the set of dependencies) from the actual probability values. We develop novel stream processing operators that can efficiently and incrementally process new data items; our operators are based on the previously proposed framework of viewing probabilistic query evaluation as inference over probabilistic graphical models (PGMs) [P. Sen and A. Deshpande, 2007]. We develop a query planning algorithm that constructs efficient query plans that are executable in polynomial-time whenever possible, and we characterize queries for which such plans are not possible. Finally we conduct an extensive experimental evaluation that illustrates the advantages of exploiting the structured nature of correlations in probabilistic streams.
Keywords: Birds; Computerized monitoring; correlated probabilistic streams; correlation structure; Data engineering; data mining; Databases; Event detection; Graphical models; inference mechanisms; Markov processes; polynomial time; probabilistic database; probabilistic graphical model; probabilistic query evaluation; query evaluation; query planning algorithm; query plans; Query processing; Random variables; stream processing operator; Streaming media

Efficient Robust Private Set Intersection - Dana Dachman-Soled; Malkin, Tal; Raykova, Mariana; Yung, Moti (Applied Cryptography and Network Security, 2009)
Computing Set Intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work the first solution to this problem is presented.
Keywords: Coding and Information Theory; Computer Communication Networks; Cryptographic protocols; Data Encryption; Data Structures, Cryptology and Information Theory; Information Systems Applications (incl.Internet); Privacy Preserving Data Mining; Secure Two-party Computation; Set Intersection; Systems and Data Security

Efficient subset selection via the kernelized Rényi distance - Srinivasan,B.V.; Duraiswami, Ramani (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
With improved sensors, the amount of data available in many vision problems has increased dramatically and allows the use of sophisticated learning algorithms to perform inference on the data. However, since these algorithms scale with data size, pruning the data is sometimes necessary. The pruning procedure must be statistically valid and a representative subset of the data must be selected without introducing selection bias. Information theoretic measures have been used for sampling the data, retaining its original information content. We propose an efficient Rényi entropy based subset selection algorithm. The algorithm is first validated and then applied to two sample applications where machine learning and data pruning are used. In the first application, Gaussian process regression is used to learn object pose. Here it is shown that the algorithm combined with the subset selection is significantly more efficient. In the second application, our subset selection approach is used to replace vector quantization in a standard object recognition algorithm, and improvements are shown.

Energy loss in MEMS resonators and the impact on inertial and RF devices - Weinberg,M.; Candler,R.; Chandorkar,S.; Varsanik,J.; Kenny,T.; Duwel,A. (2009)
In this paper, we review the current understanding of energy loss mechanisms in micromachined (MEMS and NEMS) devices. We describe the importance of high quality factor (Q) to the performance of MEMS gyros and MEMS resonators used in radio-frequency applications.
Keywords: energy loss; gyroscopes; inertial devices; MEMS gyros; MEMS resonators; micromachined devices; micromechanical resonators; NEMS devices; Q-factor; quality factor; radiofrequency applications; RF devices

Evidence for Bidentate Substrate Binding as the Basis for the K48 Linkage Specificity of Otubain 1 - Wang,Tao; Yin,Luming; Cooper,Eric M.; Lai,Ming-Yih; Dickey,Seth; Pickart,Cecile M.; Fushman, David; Wilkinson,Keith D.; Cohen,Robert E.; Wolberger,Cynthia (Journal of Molecular Biology, 2009)
Otubain 1 belongs to the ovarian tumor (OTU) domain class of cysteine protease deubiquitinating enzymes. We show here that human otubain 1 (hOtu1) is highly linkage-specific, cleaving Lys48 (K48)-linked polyubiquitin but not K63-, K29-, K6-, or K11-linked polyubiquitin, or linear α-linked polyubiquitin. Cleavage is not limited to either end of a polyubiquitin chain, and both free and substrate-linked polyubiquitin are disassembled. Intriguingly, cleavage of K48-diubiquitin by hOtu1 can be inhibited by diubiquitins of various linkage types, as well as by monoubiquitin. NMR studies and activity assays suggest that both the proximal and distal units of K48-diubiquitin bind to hOtu1. Reaction of Cys23 with ubiquitin-vinylsulfone identified a ubiquitin binding site that is distinct from the active site, which includes Cys91. Occupancy of the active site is needed to enable tight binding to the second site. We propose that distinct binding sites for the ubiquitins on either side of the scissile bond allow hOtu1 to discriminate among different isopeptide linkages in polyubiquitin substrates. Bidentate binding may be a general strategy used to achieve linkage-specific deubiquitination.
Keywords: deubiquitination; isopeptide; linkage specificity; otubain; polyubiquitin

Exponential family hybrid semi-supervised learning - Agarwal,A.; Daumé, Hal (Proceedings of the 21st International Joint Conference on Artifical Intelligence (IJCAI-09), 2009)

Extreme polymorphism in a vaccine antigen and risk of clinical malaria: implications for vaccine development - Takala,S. L; Coulibaly,D.; Thera,M. A; Batchelor,A. H; Cummings, Michael P.; Escalante,A. A; Ouattara,A.; Traoré,K.; Niangaly,A.; Djimdé,A. A; Doumbo,OK; Plowe,CV (Sci Transl Med, 2009)
Vaccines directed against the blood stages of Plasmodium falciparum malaria are intended to prevent the parasite from invading and replicating within host cells. No blood-stage malaria vaccine has shown clinical efficacy in humans. Most malaria vaccine antigens are parasite surface proteins that have evolved extensive genetic diversity, and this diversity could allow malaria parasites to escape vaccine-induced immunity. We examined the extent and within-host dynamics of genetic diversity in the blood-stage malaria vaccine antigen apical membrane antigen-1 in a longitudinal study in Mali. Two hundred and fourteen unique apical membrane antigen-1 haplotypes were identified among 506 human infections, and amino acid changes near a putative invasion machinery binding site were strongly associated with the development of clinical symptoms, suggesting that these residues may be important to consider in designing polyvalent apical membrane antigen-1 vaccines and in assessing vaccine efficacy in field trials. This extreme diversity may pose a serious obstacle to an effective polyvalent recombinant subunit apical membrane antigen-1 vaccine.

Fast concurrent object localization and recognition - Tom Yeh; Lee,J.J.; Darrell,T. (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)
Object localization and recognition are important problems in computer vision. However, in many applications, exhaustive search over all object models and image locations is computationally prohibitive. While several methods have been proposed to make either recognition or localization more efficient, few have dealt with both tasks simultaneously. This paper proposes an efficient method for concurrent object localization and recognition based on a data-dependent multi-class branch-and-bound formalism. Existing bag-of-features recognition techniques which can be expressed as weighted combinations of feature counts can be readily adapted to our method. We present experimental results that demonstrate the merit of our algorithm in terms of recognition accuracy, localization accuracy, and speed, compared to baseline approaches including exhaustive search, implicit-shape model (ISM), and efficient sub-window search (ESS). Moreover, we develop two extensions to consider non-rectangular bounding regions-composite boxes and polygons-and demonstrate their ability to achieve higher recognition scores compared to traditional rectangular bounding boxes.

Fast search for Dirichlet process mixture models - Daumé, Hal (Arxiv preprint arXiv:0907.1812, 2009)

First Steps to Netviz Nirvana: Evaluating Social Network Analysis with NodeXL - Bonsignore,E. M; Dunne,C.; Rotman,D.; Smith,M.; Capone,T.; Hansen,D. L; Shneiderman, Ben (International Conference on Computational Science and Engineering, 2009. CSE '09, 2009)
Social Network Analysis (SNA) has evolved as a popular, standard method for modeling meaningful, often hidden structural relationships in communities. Existing SNA tools often involve extensive pre-processing or intensive programming skills that can challenge practitioners and students alike. NodeXL, an open-source template for Microsoft Excel, integrates a library of common network metrics and graph layout algorithms within the familiar spreadsheet format, offering a potentially low-barrier-to-entry framework for teaching and learning SNA. We present the preliminary findings of 2 user studies of 21 graduate students who engaged in SNA using NodeXL. The majority of students, while information professionals, had little technical background or experience with SNA techniques. Six of the participants had more technical backgrounds and were chosen specifically for their experience with graph drawing and information visualization. Our primary objectives were (1) to evaluate NodeXL as an SNA tool for a broad base of users and (2) to explore methods for teaching SNA. Our complementary dual case-study format demonstrates the usability of NodeXL for a diverse set of users, and significantly, the power of a tightly integrated metrics/visualization tool to spark insight and facilitate sense-making for students of SNA.
Keywords: Computer science; computer science education; data visualisation; Data visualization; Educational institutions; graph drawing; graph layout algorithm; Information services; Information Visualization; Internet; Libraries; Microsoft Excel open-source template; MILC; multi-dimensional in-depth long-term case studies; Netviz Nirvana; NodeXL; Open source software; Programming profession; SNA; social network analysis; Social network services; social networking (online); spreadsheet programs; structural relationship; teaching; visual analytics; visualization tool; Web sites

Fluency, adequacy, or HTER?: exploring different human judgments with a tunable MT metric - Snover,Matthew; Madnani,Nitin; Dorr, Bonnie J; Schwartz,Richard (Proceedings of the Fourth Workshop on Statistical Machine Translation, 2009)
Automatic Machine Translation (MT) evaluation metrics have traditionally been evaluated by the correlation of the scores they assign to MT output with human judgments of translation performance. Different types of human judgments, such as Fluency, Adequacy, and HTER, measure varying aspects of MT performance that can be captured by automatic MT metrics. We explore these differences through the use of a new tunable MT metric: TER-Plus, which extends the Translation Edit Rate evaluation metric with tunable parameters and the incorporation of morphology, synonymy and paraphrases. TER-Plus was shown to be one of the top metrics in NIST's Metrics MATR 2008 Challenge, having the highest average rank in terms of Pearson and Spearman correlation. Optimizing TER-Plus to different types of human judgments yields significantly improved correlations and meaningful changes in the weight of different types of edits, demonstrating significant differences between the types of human judgments.

From New Zealand to Mongolia: Co-designing and deploying a digital library for the world's children - Druin, Allison; Bederson, Benjamin B.; Rose,A.; Weeks,A. (Special issue of Children, Youth and Environments: Children in Technological Environments: Interaction, Development, and Design, 2009)

Generating high-coverage semantic orientation lexicons from overtly marked words and a thesaurus - Mohammad,Saif; Dunne,Cody; Dorr, Bonnie J (Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2 - Volume 2, 2009)
Sentiment analysis often relies on a semantic orientation lexicon of positive and negative words. A number of approaches have been proposed for creating such lexicons, but they tend to be computationally expensive, and usually rely on significant manual annotation and large corpora. Most of these methods use WordNet. In contrast, we propose a simple approach to generate a high-coverage semantic orientation lexicon, which includes both individual words and multi-word expressions, using only a Roget-like thesaurus and a handful of affixes. Further, the lexicon has properties that support the Polyanna Hypothesis. Using the General Inquirer as gold standard, we show that our lexicon has 14 percentage points more correct entries than the leading WordNet-based high-coverage lexicon (SentiWordNet). In an extrinsic evaluation, we obtain significantly higher performance in determining phrase polarity using our thesaurus-based lexicon than with any other. Additionally, we explore the use of visualization techniques to gain insight into the our algorithm beyond the evaluations mentioned above.

Generating surveys of scientific paradigms - Mohammad,S.; Dorr, Bonnie J; Egan,M.; Hassan,A.; Muthukrishan,P.; Qazvinian,V.; Radev,D.; Zajic, David (Proceedings of HLT-NAACL, 2009)
The number of research publications in var-ious disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of tech- nical material. In this paper we present the first steps in producing an automatically gen- erated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization tech- niques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the frame- work of multi-document survey creation, cita- tion texts can play a crucial role.

Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains - Brettin,Thomas S[Los Alamos National Laboratory; Bruce,David C[Los Alamos National Laboratory; Challacombe,Jean F[Los Alamos National Laboratory; Detter,John C[Los Alamos National Laboratory; Han,Cliff S[Los Alamos National Laboratory; Munik,A. C[Los Alamos National Laboratory; Chertkov,Olga[Los Alamos National Laboratory; Meincke,Linda[Los Alamos National Laboratory; Saunders,Elizabeth[Los Alamos National Laboratory; Choi,Seon Y[SEOUL NATL UNIV; Haley,Bradd J[U MARYLAND; Taviani,Elisa[U MARYLAND; et al. (Nature, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a 'shift' between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a 'drift' between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.
Keywords: 59; CHOLERA; GENES; GENETICS; GENOTYPE; ISLANDS; ORIGIN; PHENOTYPE; PUBLIC HEALTH; RECOMBINATION; STRAINS; TOXINS

Graphical models for uncertain data - Deshpande, Amol; Getoor, Lise; Sen,P. (Managing and Mining Uncertain Data, 2009)

HEALTH AND WELLBEING - Gillam,M.; Feied,C.; MOODY,E.; Shneiderman, Ben; Smith,M.; DICKASON,J. (The fourth paradigm: data-intensive scientific discovery, 2009)

How children search the internet with keyword interfaces - Druin, Allison; Foss,E.; Hatley,L.; Golub,E.; Guha,M.L.; Fails,J.; Hutchinson,H. (Proceedings of the 8th International Conference on Interaction Design and Children, 2009)

Human detection using partial least squares analysis - Schwartz,William Robson; Kembhavi,Aniruddha; Harwood,David; Davis, Larry S. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
Significant research has been devoted to detecting people in images and videos. In this paper we describe a human detection method that augments widely used edge-based features with texture and color information, providing us with a much richer descriptor set. This augmentation results in an extremely high-dimensional feature space (more than 170,000 dimensions). In such high-dimensional spaces, classical machine learning algorithms such as SVMs are nearly intractable with respect to training. Furthermore, the number of training samples is much smaller than the dimensionality of the feature space, by at least an order of magnitude. Finally, the extraction of features from a densely sampled grid structure leads to a high degree of multicollinearity. To circumvent these data characteristics, we employ Partial Least Squares (PLS) analysis, an efficient dimensionality reduction technique, one which preserves significant discriminative information, to project the data onto a much lower dimensional subspace (20 dimensions, reduced from the original 170,000). Our human detection system, employing PLS analysis over the enriched descriptor set, is shown to outperform state-of-the-art techniques on three varied datasets including the popular INRIA pedestrian dataset, the low-resolution gray-scale DaimlerChrysler pedestrian dataset, and the ETHZ pedestrian dataset consisting of full-length videos of crowded scenes.

Image Transformations and Blurring - Domke, Justin; Aloimonos, J. (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009)
Since cameras blur the incoming light during measurement, different images of the same surface do not contain the same information about that surface. Thus, in general, corresponding points in multiple views of a scene have different image intensities. While multiple-view geometry constrains the locations of corresponding points, it does not give relationships between the signals at corresponding locations. This paper offers an elementary treatment of these relationships. We first develop the notion of "ideal” and "real” images, corresponding to, respectively, the raw incoming light and the measured signal. This framework separates the filtering and geometric aspects of imaging. We then consider how to synthesize one view of a surface from another; if the transformation between the two views is affine, it emerges that this is possible if and only if the singular values of the affine matrix are positive. Next, we consider how to combine the information in several views of a surface into a single output image. By developing a new tool called "frequency segmentation,” we show how this can be done despite not knowing the blurring kernel.
Keywords: reconstruction; restoration; sharpening and deblurring; smoothing.

Imaging room acoustics with the audio camera. - O'donovan,Adam; Duraiswami, Ramani; Gumerov, Nail A.; Zotkin,Dmitry N (The Journal of the Acoustical Society of America, 2009)
Using a spherical microphone array and real time signal processing using a graphical processing unit (GPU), an audio camera has been developed. This device provides images of the intensity of the sound field arriving at a point from a specified direction to the spherical array. Real‐time performance is achieved via use of GPUs. The intensity can be displayed integrated over the whole frequency band of the array, or in false color, with different frequency bands mapped to different color bands. The resulting audio camera may be combined with video cameras to achieve multimodal scene capture and analysis. A theory of registration of audio camera images with video camera images is developed, and joint analysis of audio and video images performed. An interesting application of the audio camera is the imaging of concert hall acoustics. The individual reflections that constitute the impulse response measured at a particular seat may be imaged, and their spatial origin determined. Other applications of the audio camera to people tracking, noise suppression, and camera pointing are also presented. [Work partially supported by NVIDIA and the VA.]

Improved Non-committing Encryption with Applications to Adaptively Secure Protocols - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Advances in Cryptology – ASIACRYPT 2009, 2009)
We present a new construction of non-committing encryption schemes. Unlike the previous constructions of Canetti et al. (STOC ’96) and of Damgård and Nielsen (Crypto ’00), our construction achieves all of the following properties: Optimal round complexity. Our encryption scheme is a 2-round protocol, matching the round complexity of Canetti et al. and improving upon that in Damgård and Nielsen. Weaker assumptions. Our construction is based on trapdoor simulatable cryptosystems, a new primitive that we introduce as a relaxation of those used in previous works. We also show how to realize this primitive based on hardness of factoring. Improved efficiency. The amortized complexity of encrypting a single bit is O(1) public key operations on a constant-sized plaintext in the underlying cryptosystem. As a result, we obtain the first non-committing public-key encryption schemes under hardness of factoring and worst-case lattice assumptions; previously, such schemes were only known under the CDH and RSA assumptions. Combined with existing work on secure multi-party computation, we obtain protocols for multi-party computation secure against a malicious adversary that may adaptively corrupt an arbitrary number of parties under weaker assumptions than were previously known. Specifically, we obtain the first adaptively secure multi-party protocols based on hardness of factoring in both the stand-alone setting and the UC setting with a common reference string.
Keywords: adaptive corruption; Algorithm Analysis and Problem Complexity; Applications of Mathematics; Data Encryption; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; non-committing encryption; public-key encryption; secure multi-party computation; Systems and Data Security

Improving graph drawing readability by incorporating readability metrics: A software tool for network analysts - Dunne,C.; Shneiderman, Ben (University of Maryland, HCIL Tech Report HCIL-2009-13, 2009)
Designing graph drawings that effectively communicate the under-lying network is challenging as for every network there are many potential unintelligible or even misleading drawings. Automated graph layout algorithms have helped, but frequently generate in- effective drawings. In order to build awareness of effective graph drawing strategies, we detail readability metrics on a [0,1] contin- uous scale for node occlusion, edge crossing, edge crossing angle, and edge tunneling and summarize many more. Additionally, we define new node & edge readability metrics to provide more lo- calized identification of where improvement is needed. These are implemented in SocialAction, a tool for social network analysis, in order to direct users towards poor areas of the drawing and provide real-time readability metric feedback as users manipulate it. These contributions are aimed at heightening the awareness of network analysts that the images they share or publish could be of higher quality, so that readers could extract relevant information.

Improving recommendation accuracy by clustering social networks with trust - DuBois,T.; Golbeck,J.; Kleint,J.; Srinivasan, Aravind (Recommender Systems & the Social Web, 2009)
Social trust relationships between users in social networksspeak to the similarity in opinions between the users, both in general and in important nuanced ways. They have been used in the past to make recommendations on the web. New trust metrics allow us to easily cluster users based on trust. In this paper, we investigate the use of trust clusters as a new way of improving recommendations. Previous work on the use of clusters has shown the technique to be relatively un- successful, but those clusters were based on similarity rather than trust. Our results show that when trust clusters are integrated into memory-based collaborative filtering algo- rithms, they lead to statistically significant improvements in accuracy. In this paper we discuss our methods, experi- ments, results, and potential future applications of the tech- nique.

Incremental Multiple Kernel Learning for object recognition - Kembhavi,Aniruddha; Siddiquie,Behjat; Miezianko,Roland; McCloskey,Scott; Davis, Larry S. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
A good training dataset, representative of the test images expected in a given application, is critical for ensuring good performance of a visual categorization system. Obtaining task specific datasets of visual categories is, however, far more tedious than obtaining a generic dataset of the same classes. We propose an Incremental Multiple Kernel Learning (IMKL) approach to object recognition that initializes on a generic training database and then tunes itself to the classification task at hand. Our system simultaneously updates the training dataset as well as the weights used to combine multiple information sources. We demonstrate our system on a vehicle classification problem in a video stream overlooking a traffic intersection. Our system updates itself with images of vehicles in poses more commonly observed in the scene, as well as with image patches of the background, leading to an increase in performance. A considerable change in the kernel combination weights is observed as the system gathers scene specific training data over time. The system is also seen to adapt itself to the illumination change in the scene as day transitions to night.

Indexing correlated probabilistic databases - Kanagal,Bhargav; Deshpande, Amol (Proceedings of the 35th SIGMOD international conference on Management of data, 2009)
With large amounts of correlated probabilistic data being generated in a wide range of application domains including sensor networks, information extraction, event detection etc., effectively managing and querying them has become an important research direction. While there is an exhaustive body of literature on querying independent probabilistic data, supporting efficient queries over large-scale, correlated databases remains a challenge. In this paper, we develop efficient data structures and indexes for supporting inference and decision support queries over such databases. Our proposed hierarchical data structure is suitable both for in-memory and disk-resident databases. We represent the correlations in the probabilistic database using a junction tree over the tuple-existence or attribute-value random variables, and use tree partitioning techniques to build an index structure over it. We show how to efficiently answer inference and aggregation queries using such an index, resulting in orders of magnitude performance benefits in most cases. In addition, we develop novel algorithms for efficiently keeping the index structure up-to-date as changes (inserts, updates) are made to the probabilistic database. We present a comprehensive experimental study illustrating the benefits of our approach to query processing in probabilistic databases.
Keywords: caching; Indexing; inference queries; junction trees; Probabilistic databases

The infinite hierarchical factor regression model - Rai,P.; Daumé, Hal (Arxiv preprint arXiv:0908.0570, 2009)

Interlingual annotation of multilingual text corpora and FrameNet - Farwell,David; Dorr, Bonnie J; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Green,Rebecca; Levin,Lori; Miller,Keith; Mitamura,Teruko; Rambow,Owen; Reeder,Flo; Siddharthan,Advaith (Multilingual FrameNets in Computational LexicographyMultilingual FrameNets in Computational Lexicography, 2009)

Language Identification for Handwritten Document Images Using AShape Codebook - Zhu,Guangyu; Yu,Xiaodong; Li,Yi; David Doermann (Pattern Recognition, 2009)
Language identification for handwritten document images is an open document analysis problem. In this paper, we propose a novel approach to language identification for documents containing mixture of handwritten and machine printed text using image descriptors constructed from a codebook of shape features. We encode local text structures using scale and rotation invariant codewords, each representing a segmentation-free shape feature that is generic enough to be detected repeatably. We learn a concise, structurally indexed shape codebook from training by clustering and partitioning similar feature types through graph cuts. Our approach is easily extensible and does not require skew correction, scale normalization, or segmentation. We quantitatively evaluate our approach using a large real-world document image collection, which is composed of 1,512 documents in eight languages (Arabic, Chinese, English, Hindi, Japanese, Korean, Russian, and Thai) and contains a complex mixture of handwritten and machine printed content. Experiments demonstrate the robustness and flexibility of our approach, and show exceptional language identification performance that exceeds the state of the art.

Learning Discriminative Appearance-Based Models Using Partial Least Squares - Schwartz, W.R.; Davis, Larry S. (Computer Graphics and Image Processing (SIBGRAPI), 2009 XXII Brazilian Symposium on, 2009)
Appearance information is essential for applications such as tracking and people recognition. One of the main problems of using appearance-based discriminative models is the ambiguities among classes when the number of persons being considered increases. To reduce the amount of ambiguity, we propose the use of a rich set of feature descriptors based on color, textures and edges. Another issue regarding appearance modeling is the limited number of training samples available for each appearance. The discriminative models are created using a powerful statistical tool called partial least squares (PLS), responsible for weighting the features according to their discriminative power for each different appearance. The experimental results, based on appearance-based person recognition, demonstrate that the use of an enriched feature set analyzed by PLS reduces the ambiguity among different appearances and provides higher recognition rates when compared to other machine learning techniques.
Keywords: (artificial; analysis; learning; appearance; approximations; object; based; colour; descriptors; learning; discriminative; intelligence); least; learning; least; models; machine; person; recognition; recognition; feature; squares; squares; image; techniques; partial

Learning to trust in the competence and commitment of agents - Smith,Michael; desJardins, Marie (Autonomous Agents and Multi-Agent Systems, 2009)
For agents to collaborate in open multi-agent systems, each agent must trust in the other agents’ ability to complete tasks and willingness to cooperate. Agents need to decide between cooperative and opportunistic behavior based on their assessment of another agents’ trustworthiness. In particular, an agent can have two beliefs about a potential partner that tend to indicate trustworthiness: that the partner is competent and that the partner expects to engage in future interactions . This paper explores an approach that models competence as an agent’s probability of successfully performing an action, and models belief in future interactions as a discount factor. We evaluate the underlying decision framework’s performance given accurate knowledge of the model’s parameters in an evolutionary game setting. We then introduce a game-theoretic framework in which an agent can learn a model of another agent online, using the Harsanyi transformation. The learning agents evaluate a set of competing hypotheses about another agent during the simulated play of an indefinitely repeated game. The Harsanyi strategy is shown to demonstrate robust and successful online play against a variety of static, classic, and learning strategies in a variable-payoff Iterated Prisoner’s Dilemma setting.

Logo Matching for Document Image Retrieval - Zhu,Guangyu; David Doermann (International Conference on Document Analysis and Recognition (ICDAR 2009), 2009)
Graphics detection and recognition are fundamental research problems in document image analysis and retrieval. As one of the most pervasive graphical elements in business and government documents, logos may enable immediate identification of organizational entities and serve extensively as a declaration of a document's source and ownership. In this work, we developed an automatic logo-based document image retrieval system that handles: 1) Logo detection and segmentation by boosting a cascade of classifiers across multiple image scales; and 2) Logo matching using translation, scale, and rotation invariant shape descriptors and matching algorithms. Our approach is segmentation free and layout independent and we address logo retrieval in an unconstrained setting of 2-D feature point matching. Finally, we quantitatively evaluate the effectiveness of our approach using large collections of real-world complex document images.

Markov random topic fields - Daumé, Hal (Proceedings of the ACL-IJCNLP 2009 Conference Short Papers, 2009)

The Maryland Modular Method: An Approach to Doctoral Education in Information Studies - Druin, Allison; Jaeger,P. T; Golbeck,J.; Fleischmann,K.R.; Jimmy Lin; Qu,Y.; Wang,P.; Xie,B. (Journal of education for library and information science, 2009)

Measurement methods for fast and accurate blackhole identification with binary tomography - Cunha,Ítalo; Teixeira,Renata; Feamster, Nick; Diot,Christophe (Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, 2009)
Binary tomography - the process of identifying faulty network links through coordinated end-to-end probes - is a promising method for detecting failures that the network does not automatically mask (e.g., network "blackholes"). Because tomography is sensitive to the quality of the input, however, naïve end-to-end measurements can introduce inaccuracies. This paper develops two methods for generating inputs to binary tomography algorithms that improve their inference speed and accuracy. Failure confirmation is a per-path probing technique to distinguish packet losses caused by congestion from persistent link or node failures. Aggregation strategies combine path measurements from unsynchronized monitors into a set of consistent observations. When used in conjunction with existing binary tomography algorithms, our methods identify all failures that are longer than two measurement cycles, while inducing relatively few false alarms. In two wide-area networks, our techniques decrease the number of alarms by as much as two orders of magnitude. Compared to the state of the art in binary tomography, our techniques increase the identification rate and avoid hundreds of false alarms.
Keywords: diagnosis; network tomography; troubleshooting

MEASURING 1ST ORDER STRETCH WITH A SINGLE FILTER - Bitsakos,K.; Domke, J.; Fermüller, Cornelia; Aloimonos, J. (Relation, 2009)
We analytically develop a filter that is able to measurethe linear stretch of the transformation around a point, and present results of applying it to real signals. We show that this method is a real-time alternative solution for measuring local signal transformations. Experimentally, this method can accurately measure stretch, however, it is sensitive to shift.

Measuring General Relational Structure Using the Block Modularity Clustering Objective - Anthony,Adam Paul; desJardins, Marie; Lombardi,Michael (Twenty-Second International FLAIRS Conference, 2009)
The performance of all relational learning techniques has an implicit dependence on the underlying connectivity structure of the relations that are used as input. In this paper, we show how clustering can be used to develop an efficient optimization strategy can be used to effectively measure the structure of a graph in the absence of labeled instances.

Minimizing Communication Cost in Distributed Multi-query Processing - Li,Jian; Deshpande, Amol; Khuller, Samir (IEEE 25th International Conference on Data Engineering, 2009. ICDE '09, 2009)
Increasing prevalence of large-scale distributed monitoring and computing environments such as sensor networks, scientific federations, Grids etc., has led to a renewed interest in the area of distributed query processing and optimization. In this paper we address a general, distributed multi-query processing problem motivated by the need to minimize the communication cost in these environments. Specifically we address the problem of optimally sharing data movement across the communication edges in a distributed communication network given a set of overlapping queries and query plans for them (specifying the operations to be executed). Most of the problem variations of our general problem can be shown to be NP-Hard by a reduction from the Steiner tree problem. However, we show that the problem can be solved optimally if the communication network is a tree, and present a novel algorithm for finding an optimal data movement plan. For general communication networks, we present efficient approximation algorithms for several variations of the problem. Finally, we present an experimental study over synthetic datasets showing both the need for exploiting the sharing of data movement and the effectiveness of our algorithms at finding such plans.
Keywords: Approximation algorithms; Communication networks; Computer science; Cost function; Data engineering; distributed communication network; distributed databases; distributed multi-query processing; grid computing; Large-scale systems; NP-hard; optimisation; Polynomials; Publish-subscribe; publish-subscribe systems; Query optimization; Query processing; sensor networks; Steiner tree problem; Tree graphs; trees (mathematics)

Modal expansion of HRTFs: Continuous representation in frequency-range-angle - Zhang,Wen; Abhayapala,T.D.; Kennedy,R.A.; Duraiswami, Ramani (Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on, 2009)
This paper proposes a continuous HRTF representation in both 3D spatial and frequency domains. The method is based on the acoustic reciprocity principle and a modal expansion of the wave equation solution to represent the HRTF variations with different variables in separate basis functions. The derived spatial basis modes can achieve HRTF near-field and far-field representation in one formulation. The HRTF frequency components are expanded using Fourier Spherical Bessel series for compact representation. The proposed model can be used to reconstruct HRTFs at any arbitrary position in space and at any frequency point from a finite number of measurements. Analytical simulated and measured HRTFs from a KEMAR are used to validate the model.
Keywords: analysis; signal; bessel; domains; frequency-range-angle; head; expansion; modal; Fourier; function; modal; functions; reconstruction; signal; related; representation; transfer; series; HRTF; frequency; spherical; transfer

Morphology analysis of 3D scalar fields based on morse theory and discrete distortion - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Magillo,Paola (Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2009)
We investigate a morphological approach to the analysis and understanding of 3D scalar fields defined by volume data sets. We consider a discrete model of the 3D field obtained by discretizing its domain into a tetrahedral mesh. We use Morse theory as the basic mathematical tool which provides a segmentation of the graph of the scalar field based on relevant morphological features (such as critical points). Since the graph of a discrete 3D field is a tetrahedral hypersurface in 4D space, we measure the distortion of the transformation which maps the tetrahedral decomposition of the domain of the scalar field into the tetrahedral mesh representing its graph in R4, and we call it discrete distortion. We develop a segmentation algorithm to produce a Morse decompositions associated with the scalar field and its discrete distortion. We use a merging procedure to control the number of 3D regions in the segmentation output. Experimental results show the validity of our approach.
Keywords: curvature; morphological analysis; Morse theory; segmentation

Multi-label prediction via sparse infinite CCA - Rai,P.; Daumé, Hal (Advances in Neural Information Processing Systems, 2009)

Multiple instance Feature for robust part-based object detection - Lin,Z.; Hua,G.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)

No Downtime for Data Conversions: Rethinking Hot Upgrades (CMU-PDL-09-106) - Tudor Dumitras; Narasimhan, Priya (Parallel Data Laboratory, 2009)

Non-parametric bayesian areal linguistics - Daumé, Hal (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)

Object detection via boosted deformable features - Hussein,M.; Porikli, F.; Davis, Larry S. (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
It is a common practice to model an object for detection tasks as a boosted ensemble of many models built on features of the object. In this context, features are defined as subregions with fixed relative locations and extents with respect to the object's image window. We introduce using deformable features with boosted ensembles. A deformable features adapts its location depending on the visual evidence in order to match the corresponding physical feature. Therefore, deformable features can better handle deformable objects. We empirically show that boosted ensembles of deformable features perform significantly better than boosted ensembles of fixed features for human detection.
Keywords: boosted; detection; object; detection; statistics; detection; visual; ensembles; deformable; evidence; feature; extraction; object; features; human

Observing Human-Object Interactions: Using Spatial and Functional Compatibility for Recognition - Gupta,A.; Kembhavi,A.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009)
Interpretation of images and videos containing humans interacting with different objects is a daunting task. It involves understanding scene or event, analyzing human movements, recognizing manipulable objects, and observing the effect of the human movement on those objects. While each of these perceptual tasks can be conducted independently, recognition rate improves when interactions between them are considered. Motivated by psychological studies of human perception, we present a Bayesian approach which integrates various perceptual tasks involved in understanding human-object interactions. Previous approaches to object and action recognition rely on static shape or appearance feature matching and motion analysis, respectively. Our approach goes beyond these traditional approaches and applies spatial and functional constraints on each of the perceptual elements for coherent semantic interpretation. Such constraints allow us to recognize objects and actions when the appearances are not discriminative enough. We also demonstrate the use of such constraints in recognition of actions from static images without using any motion information.
Keywords: Automated; Recognition (Psychology); Video Recording; Bayesian approach; functional compatibility; human perception; human-object interactions; objects recognition; psychological studies; spatial compatibility; Bayes methods; behavioural sciences; human factors; image recognition; motion estimation; object recognition; A; Biological; Movement; Pattern Recognition; Computer-Assisted; Models

Off-Line Loop Investigation for Handwriting Analysis - Steinherz,T.; David Doermann; Rivlin,E.; Intrator,N. (IEEETransactions on Pattern Analysis and Machine Intelligence, 2009)

P r DB: managing and exploiting rich correlations in probabilistic databases - Sen,P.; Deshpande, Amol; Getoor, Lise (The VLDB Journal, 2009)
Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, PrDB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in PrDB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.

Page Rule-Line Removal using Linear Subspaces in Monochromatic Handwritten Arabic Documents - Abd-Almageed, Wael; Kumar,Jayant; David Doermann (Intl. Conf. on Document Analysis and Recognition (ICDAR 09), 2009)
In this paper we present a novel method for removing page rule lines in monochromatic handwritten Arabic documents using subspace methods with minimal effect on the quality of the foreground text. We use moment and histogram properties to extract features that represent the characteristics of the underlying rule lines. A linear subspace is incrementally built to obtain a line model that can be used to identify rule line pixels. We also introduce a novel scheme for evaluating noise removal algorithms in general and we use it to assess the quality of our rule line removal algorithm. Experimental results presented on a data set of 50 Arabic documents, handwritten by different writers, demonstrate the effectiveness of the proposed method.

PERCEPTION AND NAVIGATION FOR AUTONOMOUS VEHICLES - Hussein,M.; Porikli, F.; Davis, Larry S. (IEEE Transactions on intelligent transportation systems, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA Person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.

Plane-wave decomposition of a sound scene using a cylindrical microphone array - Zotkin,Dmitry N; Duraiswami, Ramani (Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on, 2009)
The analysis for microphone arrays formed by mounting microphones on a sound-hard spherical or cylindrical baffle is typically performed using a decomposition of the sound field in terms of orthogonal basis functions. An alternative representation in terms of plane waves and a method for obtaining the coefficients of such a representation directly from measurements was proposed recently for the case of a spherical array. It was shown that representing the field as a collection of plane waves arriving from various directions simplifies both source localization and beamforming. In this paper, these results are extended to the case of the cylindrical array. Similarly to the spherical array case, localization and beamforming based on plane-wave decomposition perform as well as the traditional orthogonal function based methods while being numerically more stable. Both simulated and experimental results are presented.
Keywords: array; plane; arrays; baffle; cylindrical; beamforming; cylindrical; decomposition; sound-hard; localization; array; microphone; plane-wave; processing; microphone; scene; signal; spherical; source; waves; sound

PrDB: managing and exploiting rich correlations in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (The VLDB Journal, 2009)
Due to numerous applications producing noisy data, e.g., sensor data, experimental data, data from uncurated sources, information extraction, etc., there has been a surge of interest in the development of probabilistic databases. Most probabilistic database models proposed to date, however, fail to meet the challenges of real-world applications on two counts: (1) they often restrict the kinds of uncertainty that the user can represent; and (2) the query processing algorithms often cannot scale up to the needs of the application. In this work, we define a probabilistic database model, P r DB, that uses graphical models, a state-of-the-art probabilistic modeling technique developed within the statistics and machine learning community, to model uncertain data. We show how this results in a rich, complex yet compact probabilistic database model, which can capture the commonly occurring uncertainty models (tuple uncertainty, attribute uncertainty), more complex models (correlated tuples and attributes) and allows compact representation (shared and schema-level correlations). In addition, we show how query evaluation in P r DB translates into inference in an appropriately augmented graphical model. This allows us to easily use any of a myriad of exact and approximate inference algorithms developed within the graphical modeling community. While probabilistic inference provides a generic approach to solving queries, we show how the use of shared correlations, together with a novel inference algorithm that we developed based on bisimulation, can speed query processing significantly. We present a comprehensive experimental evaluation of the proposed techniques and show that even with a few shared correlations, significant speedups are possible.

PrDB: Managing Large-Scale Correlated Probabilistic Databases (Abstract) - Deshpande, Amol (Scalable Uncertainty ManagementScalable Uncertainty Management, 2009)
Increasing numbers of real-world application domains are generating data that is inherently noisy, incomplete, and probabilistic in nature. Statistical inference and probabilistic modeling often introduce another layer of uncertainty on top of that. Examples of such data include measurement data collected by sensor networks, observation data in the context of social networks, scientific and biomedical data, and data collected by various online cyber-sources. Over the last few years, numerous approaches have been proposed, and several systems built, to integrate uncertainty into databases. However, these approaches typically make simplistic and restrictive assumptions concerning the types of uncertainties that can be represented. Most importantly, they often make highly restrictive independence assumptions, and cannot easily model rich correlations among the tuples or attribute values. Furthermore, they typically lack support for specifying uncertainties at different levels of abstractions, needed to handle large-scale uncertain datasets.

Predicting and Controlling System-Level Parameters of Multi-Agent Systems - Miner,Don; desJardins, Marie (2009 AAAI Fall Symposium Series, 2009)
Boid flocking is a system in which several individual agents follow three simple rules to generate swarm-level flocking behavior. To control this system, the user must adjust the agent program parameters, which indirectly modifies the flocking behavior. This is unintuitive because the properties of the flocking behavior are non-explicit in the agent program. In this paper, we discuss a domain-independent approach for detecting and controlling two emergent properties of boids: density and a qualitative threshold effect of swarming vs. flocking. Also, we discuss the possibility of applying this approach to detecting and controlling traffic jams in traffic simulations.
Keywords: Complex Adaptive Systems; System-level behavior

Probabilistic fusion-based parameter estimation for visual tracking - Han,Bohyung; Davis, Larry S. (Computer Vision and Image Understanding, 2009)
In object tracking, visual features may not be discriminative enough to estimate high dimensional motion parameters accurately, and complex motion estimation is computationally expensive due to a large search space. To tackle these problems, a reasonable strategy is to track small components within the target independently in lower dimensional motion parameter spaces (e.g., translation only) and then estimate the overall high dimensional motion (e.g., translation, scale and rotation) by statistically integrating the individual tracking results. Although tracking each component in a lower dimensional space is more reliable and faster, it is not trivial to combine the local motion information and estimate global parameters in a robust way because the individual component motions are frequently inconsistent. We propose a robust fusion algorithm to estimate the complex motion parameters using variable-bandwidth mean-shift. By employing correlation-based uncertainty modeling and fusion of individual components, the motion parameter that is robust to outliers can be detected with variable-bandwidth density-based fusion (VBDF) algorithm. In addition, we describe a method to update target appearance model for each component adaptively based on the component motion consistency. We present various tracking results and compare the performance of our algorithm with others using real video sequences.
Keywords: Component-based tracking; Density-based fusion; Mean-shift; visual tracking

Probabilistic graphical models - Gupta,A.; Kembhavi,A.; Davis, Larry S. (IEEE transactions on pattern analysis and machine intelligence, 2009)

Recognizing actions by shape-motion prototype trees - Zhe Lin; Zhuolin Jiang; Davis, Larry S. (Computer Vision, 2009 IEEE 12th International Conference on, 2009)
A prototype-based approach is introduced for action recognition. The approach represents an action as a sequence of prototypes for efficient and flexible action matching in long video sequences. During training, first, an action prototype tree is learned in a joint shape and motion space via hierarchical k-means clustering; then a lookup table of prototype-to-prototype distances is generated. During testing, based on a joint likelihood model of the actor location and action prototype, the actor is tracked while a frame-to-prototype correspondence is established by maximizing the joint likelihood, which is efficiently performed by searching the learned prototype tree; then actions are recognized using dynamic prototype sequence matching. Distance matrices used for sequence matching are rapidly obtained by look-up table indexing, which is an order of magnitude faster than brute-force computation of frame-to-frame distances. Our approach enables robust action matching in very challenging situations (such as moving cameras, dynamic backgrounds) and allows automatic alignment of action sequences. Experimental results demonstrate that our approach achieves recognition rates of 91.07% on a large gesture dataset (with dynamic backgrounds), 100% on the Weizmann action dataset and 95.77% on the KTH action dataset.

Regularized HRTF fitting using spherical harmonics - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2009. WASPAA '09, 2009)
By the Helmholtz reciprocity principle, the head-related transfer function (HRTF) is equivalent to an acoustic field created by a transmitter placed at the ear location. Therefore, it can be represented as a spherical harmonics spectrum - a weighted sum of spherical harmonics. Such representations are useful in theoretical and computational analysis. Many different (often severely undersampled) grids are used for HRTF measurement, making the spectral reconstruction difficult. In this paper, two methods of obtaining the spectrum are presented and analyzed both on synthetic (ground-truth data available) and real HRTF measurements.
Keywords: Acoustic applications; acoustic field; Acoustic fields; acoustic intensity measurement; Acoustic measurements; acoustic signal processing; Acoustic testing; acoustic waves; array signal processing; audio acoustics; circular arrays; computational analysis; Ear; ear location; head-related transfer function; Helmholtz reciprocity principle; HRTF; HRTF fitting; Loudspeakers; Microphones; Position measurement; signal reconstruction; spatial audio; spectral reconstruction; spherical harmonics; Transfer functions

Rigorous Probabilistic Trust-Inference with Applications to Clustering - DuBois,Thomas; Golbeck,Jennifer; Srinivasan, Aravind (IEEE/WIC/ACM International Joint Conferences on Web Intelligence and Intelligent Agent Technologies, 2009. WI-IAT '09, 2009)
The World Wide Web has transformed into an environment where users both produce and consume information. In order to judge the validity of information, it is important to know how trustworthy its creator is. Since no individual can have direct knowledge of more than a small fraction of information authors, methods for inferring trust are needed. We propose a new trust inference scheme based on the idea that a trust network can be viewed as a random graph, and a chain of trust as a path in that graph. In addition to having an intuitive interpretation, our algorithm has several advantages, noteworthy among which is the creation of an inferred trust-metric space where the shorter the distance between two people, the higher their trust. Metric spaces have rigorous algorithms for clustering, visualization, and related problems, any of which is directly applicable to our results.
Keywords: Clustering algorithms; Conferences; Educational institutions; Extraterrestrial measurements; Inference algorithms; Intelligent agent; random graphs; Social network services; trust inferrence; Visualization; Voting; Web sites

Robust human detection under occlusion by integrating face and person detectors - Schwartz, W.R.; Gopalan,R.; Chellapa, Rama; Davis, Larry S. (Proceedings of the Third International Conference on Advances in Biometrics, 2009)
Human detection under occlusion is a challenging problemin computer vision. We address this problem through a framework which integrates face detection and person detection. We first investigate how the response of a face detector is correlated with the response of a person detector. From these observations, we formulate hypotheses that capture the intuitive feedback between the responses of face and person detectors and use it to verify if the individual detectors’ outputs are true or false. We illustrate the performance of our integration framework on challeng- ing images that have considerable amount of occlusion, and demonstrate its advantages over individual face and person detectors.

Scaling kernel machine learning algorithm via the use of GPUs - Srinivasan,B.V.; Duraiswami, Ramani (GPU Technology Conference, 2009)

Scene it or not? incremental multiple kernel learning for object detection - Kembhavi,A.; Siddiquie,B.; Miezianko,R.; McCloskey,S.; Davis, Larry S.; Schwartz, W.R.; Harwood,D.; Gupta,A.; Farrell,R.; Luo,Y.; others (Proceedings of the International Conference on Computer Vision, 2009)

Second ACM Workshop on Hot Topics in Software Upgrades (HotSWUp 2009) - Tudor Dumitras; Neamtiu, Iulian; Tilevich, Eli (ACM, 2009)
The goal of HotSWUp is to identify cutting-edge research ideas for implementing software upgrades. In the presence of modified user requirements, deployment environments, and bug fixes, actively-used software must be upgraded continuously to ensure its utility and safety. The upgrades incorporate changes to the structure, behavior, configuration, data, or topology of a computer system. Whether applied offline or directly to a live system, such upgrades may have a significant impact on the performance and reliability of the software. Indeed, recent studies and a large body of anecdotal evidence suggest that, in practice, upgrades are failure-prone and can lead to outages, data corruption or latent errors. These problems not only inconvenience end users - they create a significant burden for organizations due to the associated downtime and high administrative costs.
Keywords: software; upgrades

Segmentation using appearance of mesostructure roughness - Yacoob,Yaser; Davis, Larry S. (International journal of computer vision, 2009)
This paper introduces mesostructure roughness as an effective cue in image segmentation. Mesostructure roughness corresponds to small-scale bumps on the macrostructure (i.e., geometry) of objects. Specifically, the focus is on the texture that is created by the projection of the mesostructure roughness on the camera plane. Three intrinsic images are derived: reflectance, smooth-surface shading and mesostructure roughness shading (meta-texture images). A constructive approach is proposed for computing a meta-texture image by preserving, equalizing and enhancing the underlying surface-roughness across color, brightness and illumination variations. We evaluate the performance on sample images and illustrate quantitatively that different patches of the same material, in an image, are normalized in their statistics despite variations in color, brightness and illumination. We develop an algorithm for segmentation of an image into patches that share salient mesostructure roughness. Finally, segmentation by line-based boundary-detection is proposed and results are provided and compared to known algorithms.

Semantically informed machine translation (SIMT) - Baker,K.; Bethard,S.; Bloodgood,M.; Brown,R.; Callison-Burch,C.; Coppersmith,G.; Dorr, Bonnie J; Filardo,W.; Giles,K.; Irvine,A.; others (SCALE summer workshop final report, Human Language Technology Center Of Excellence, 2009)

Semantic-based segmentation and annotation of 3d models - Papaleo,L.; De Floriani, Leila (Image Analysis and Processing–ICIAP 2009, 2009)
3D objects have become widely available and used in different application domains. Thus, it is becoming fundamental to use, integrate and develop techniques for extracting and maintaining their embedded knowledge. These techniques should be encapsulated in portable and intelligent systems able to semantically annotate the 3D object models in order to improve their usability and indexing, especially in innovative web cooperative environments. Lately, we are moving in this direction, with the definition and development of data structures, methods and interfaces for structuring and semantically annotating 3D complex models (and scenes) - even changing in time - according to ontology-driven metadata and following ontology-driven processes. Here, we concentrate on the tools for segmenting manifold 3D models and on the underline structural representation that we build and manipulate. We also describe the first prototype of an annotation tool which allows a hierarchical semantic-driven tagging of the segmented model and provides an interface from which the user can inspect and browse the entire segmentation graph.

Semi-supervised or semi-unsupervised? - Daumé, Hal (Proceedings of the NAACL HLT Workshop on Semisupervised Learning for Natural Language Processing, 2009)

A set of tools for Representing, Decomposing and Visualizing non manifold Cellular Complexes - De Floriani, Leila; Panozzo,D.; Hui,A. (Department of Computer Science and Information Science, University of Genoa, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an eﬀective support to modeling, analyzing and understanding non-manifold shapes. We describe a new data structure for non-manifold simplicial complex that we used in our decomposition software and we provide a complete description of all functionalities of the library we developed.

Set-Based Boosting for Instance-Level Transfer - Eaton,Eric; desJardins, Marie (Data Mining Workshops, 2009. ICDMW '09. IEEE International Conference on, 2009)
The success of transfer to improve learning on a target task is highly dependent on the selected source data. Instance-based transfer methods reuse data from the source tasks to augment the training data for the target task. If poorly chosen, this source data may inhibit learning, resulting in negative transfer. The current best performing algorithm for instance-based transfer, TrAdaBoost, performs poorly when given irrelevant source data. We present a novel set-based boosting technique for instance-based transfer. The proposed algorithm, TransferBoost, boosts both individual instances and collective sets of instances from each source task. In effect, TransferBoost boosts each source task, assigning higher weight to those source tasks which show positive transferability to the target task, and then adjusts the weights of the instances within each source task via AdaBoost. The results demonstrate that TransferBoost significantly improves transfer performance over existing instance-based algorithms when given a mix of relevant and irrelevant source data.

Signature Detection and Matching for Document Image Retrieval - Zhu,Guangyu; Yefeng Zheng; David Doermann; Jaeger,Stefan (IEEETransactions on Pattern Analysis and Machine Intelligence, 2009)
As one of the most pervasive methods of individual identification and document authentication, signatures present convincing evidence and provide an important form of indexing for effective document image processing and retrieval in a broad range of applications. However, detection and segmentation of free-form objects such as signatures from clustered background is currently an open document analysis problem. In this paper, we focus on two fundamental problems in signature-based document image retrieval. First, we propose a novel multi-scale approach to jointly detecting and segmenting signatures from document images. Rather than focusing on local features that typically have large variations, our approach captures the structural saliency using a signature production model and computes the dynamic curvature of 2-D contour fragments over multiple scales. This detection framework is general and computationally tractable. Second, we treat the problem of signature retrieval in the unconstrained setting of translation, scale, and rotation invariant non-rigid shape matching. We propose two novel measures of shape dissimilarity based on anisotropic scaling and registration residual error, and present a supervised learning framework for combining complementary shape information from different dissimilarity metrics using LDA. We quantitatively study state-of-the-art shape representations, shape matching algorithms, measures of dissimilarity, and the use of multiple instances as query in document image retrieval. We further demonstrate our matching techniques in off-line signature verification. Extensive experiments using large real world collections of English and Arabic machine printed and handwritten documents demonstrate the excellent performance of our approaches.

Simple, Black-Box Constructions of Adaptively Secure Protocols - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Theory of Cryptography, 2009)
We present a compiler for transforming an oblivious transfer (OT) protocol secure against an adaptive semi-honest adversary into one that is secure against an adaptive malicious adversary. Our compiler achieves security in the universal composability framework, assuming access to an ideal commitment functionality, and improves over previous work achieving the same security guarantee in two ways: it uses black-box access to the underlying protocol and achieves a constant multiplicative overhead in the round complexity. As a corollary, we obtain the first constructions of adaptively secure protocols in the stand-alone model using black-box access to a low-level primitive.
Keywords: Algorithm Analysis and Problem Complexity; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; Systems and Data Security

Streamed learning: one-pass SVMs - Rai,P.; Daumé, Hal; Venkatasubramanian,S. (Proceedings of the 21st international jont conference on Artifical intelligence, 2009)

Streaming for large scale NLP: Language modeling - Goyal,A.; Daumé, Hal; Venkatasubramanian,S. (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)

Supercubes: A High-Level Primitive for Diamond Hierarchies - Weiss,K.; De Floriani, Leila (Visualization and Computer Graphics, IEEE Transactions on, 2009)
Volumetric datasets are often modeled using a multiresolution approach based on a nested decomposition of the domain into a polyhedral mesh. Nested tetrahedral meshes generated through the longest edge bisection rule are commonly used to decompose regular volumetric datasets since they produce highly adaptive crack-free representations. Efficient representations for such models have been achieved by clustering the set of tetrahedra sharing a common longest edge into a structure called a diamond. The alignment and orientation of the longest edge can be used to implicitly determine the geometry of a diamond and its relations to the other diamonds within the hierarchy. We introduce the supercube as a high-level primitive within such meshes that encompasses all unique types of diamonds. A supercube is a coherent set of edges corresponding to three consecutive levels of subdivision. Diamonds are uniquely characterized by the longest edge of the tetrahedra forming them and are clustered in supercubes through the association of the longest edge of a diamond with a unique edge in a supercube. Supercubes are thus a compact and highly efficient means of associating information with a subset of the vertices, edges and tetrahedra of the meshes generated through longest edge bisection. We demonstrate the effectiveness of the supercube representation when encoding multiresolution diamond hierarchies built on a subset of the points of a regular grid. We also show how supercubes can be used to efficiently extract meshes from diamond hierarchies and to reduce the storage requirements of such variable-resolution meshes.
Keywords: (computer; adaptive; approach; nested; bisection; crack-free; datasets; computational; decomposition; nested; diamond; generation; rendering; geometry; mesh; graphics); hierarchies; edge; mesh; supercubes; tetrahedra; meshes; polyhedral; representations; multiresolution; rule; highly; sharing; volumetric; tetrahedral

Symbolic-to-statistical hybridization: extending generation-heavy machine translation - Habash,Nizar; Dorr, Bonnie J; Monz,Christof (Machine Translation, 2009)
The last few years have witnessed an increasing interest in hybridizing surface-based statistical approaches and rule-based symbolic approaches to machine translation (MT). Much of that work is focused on extending statistical MT systems with symbolic knowledge and components. In the brand of hybridization discussed here, we go in the opposite direction: adding statistical bilingual components to a symbolic system. Our base system is Generation-heavy machine translation (GHMT), a primarily symbolic asymmetrical approach that addresses the issue of Interlingual MT resource poverty in source-poor/target-rich language pairs by exploiting symbolic and statistical target-language resources. GHMT’s statistical components are limited to target-language models, which arguably makes it a simple form of a hybrid system . We extend the hybrid nature of GHMT by adding statistical bilingual components. We also describe the details of retargeting it to Arabic–English MT. The morphological richness of Arabic brings several challenges to the hybridization task. We conduct an extensive evaluation of multiple system variants. Our evaluation shows that this new variant of GHMT—a primarily symbolic system extended with monolingual and bilingual statistical components—has a higher degree of grammaticality than a phrase-based statistical MT system, where grammaticality is measured in terms of correct verb-argument realization and long-distance dependency translation.

System and method for fast illumination-invariant background subtraction ... - Lim,Ser-Nam; Mittal,Anurag; Davis, Larry S. (2009)
A method for eliminating errors in foreground object detection in digitized images comprises providing a reference camera and a secondary camera, vertically aligning each said camera with a baseline that is approximately perpendicular to a ground plane, wherein said reference camera is placed lower than said secondary camera, selecting a foreground pixel in a reference view of a first point in a foreground object, finding a conjugate pixel of the foreground pixel in a secondary view, using the foreground and conjugate pixels to determine an image base pixel of a base point in the reference view, wherein said base point is a point on the ground plane below the first point, and using the foreground and image base pixels to find a location where the ground plane is first visible.

TER-Plus: paraphrase, semantic, and alignment enhancements to Translation Edit Rate - Snover,Matthew; Madnani,Nitin; Dorr, Bonnie J; Schwartz,Richard (Machine Translation, 2009)
This paper describes a new evaluation metric, TER-Plus (TERp) for automatic evaluation of machine translation (MT). TERp is an extension of Translation Edit Rate (TER). It builds on the success of TER as an evaluation metric and alignment tool and addresses several of its weaknesses through the use of paraphrases, stemming, synonyms, as well as edit costs that can be automatically optimized to correlate better with various types of human judgments. We present a correlation study comparing TERp to BLEU, METEOR and TER, and illustrate that TERp can better evaluate translation adequacy.

Three genomes from the phylum Acidobacteria provide insight into the lifestyles of these microorganisms in soils. - Ward, Naomi L; Challacombe, Jean F; Janssen, Peter H; Henrissat, Bernard; Coutinho, Pedro M; Wu, Martin; Xie, Gary; Haft, Daniel H; Sait, Michelle; Badger, Jonathan; Barabote, Ravi D; Bradley, Brent; et al. (Appl Environ Microbiol, 2009)
The complete genomes of three strains from the phylum Acidobacteria were compared. Phylogenetic analysis placed them as a unique phylum. They share genomic traits with members of the Proteobacteria, the Cyanobacteria, and the Fungi. The three strains appear to be versatile heterotrophs. Genomic and culture traits indicate the use of carbon sources that span simple sugars to more complex substrates such as hemicellulose, cellulose, and chitin. The genomes encode low-specificity major facilitator superfamily transporters and high-affinity ABC transporters for sugars, suggesting that they are best suited to low-nutrient conditions. They appear capable of nitrate and nitrite reduction but not N(2) fixation or denitrification. The genomes contained numerous genes that encode siderophore receptors, but no evidence of siderophore production was found, suggesting that they may obtain iron via interaction with other microorganisms. The presence of cellulose synthesis genes and a large class of novel high-molecular-weight excreted proteins suggests potential traits for desiccation resistance, biofilm formation, and/or contribution to soil structure. Polyketide synthase and macrolide glycosylation genes suggest the production of novel antimicrobial compounds. Genes that encode a variety of novel proteins were also identified. The abundance of acidobacteria in soils worldwide and the breadth of potential carbon use by the sequenced strains suggest significant and previously unrecognized contributions to the terrestrial carbon cycle. Combining our genomic evidence with available culture traits, we postulate that cells of these isolates are long-lived, divide slowly, exhibit slow metabolic rates under low-nutrient conditions, and are well equipped to tolerate fluctuations in soil hydration.
Keywords: Anti-Bacterial Agents; bacteria; Biological Transport; Carbohydrate Metabolism; Cyanobacteria; DNA, Bacterial; Fungi; Genome, Bacterial; Macrolides; Molecular Sequence Data; Nitrogen; Phylogeny; Proteobacteria; Sequence Analysis, DNA; sequence homology; Soil Microbiology

Toward reconstructing the evolution of advanced moths and butterflies (Lepidoptera: Ditrysia): an initial molecular study - Regier,J. C; Zwick,A.; Cummings, Michael P.; Kawahara,A. Y; Cho,S.; Weller,S.; Roe,A.; Baixeras,J.; Brown,J. W; Parr,C.; Davis,DR; Epstein,M; et al. (BMC Evol Biol, 2009)
BACKGROUND: In the mega-diverse insect order Lepidoptera (butterflies and moths; 165,000 described species), deeper relationships are little understood within the clade Ditrysia, to which 98% of the species belong. To begin addressing this problem, we tested the ability of five protein-coding nuclear genes (6.7 kb total), and character subsets therein, to resolve relationships among 123 species representing 27 (of 33) superfamilies and 55 (of 100) families of Ditrysia under maximum likelihood analysis. RESULTS: Our trees show broad concordance with previous morphological hypotheses of ditrysian phylogeny, although most relationships among superfamilies are weakly supported. There are also notable surprises, such as a consistently closer relationship of Pyraloidea than of butterflies to most Macrolepidoptera. Monophyly is significantly rejected by one or more character sets for the putative clades Macrolepidoptera as currently defined (P < 0.05) and Macrolepidoptera excluding Noctuoidea and Bombycoidea sensu lato (P < or = 0.005), and nearly so for the superfamily Drepanoidea as currently defined (P < 0.08). Superfamilies are typically recovered or nearly so, but usually without strong support. Relationships within superfamilies and families, however, are often robustly resolved. We provide some of the first strong molecular evidence on deeper splits within Pyraloidea, Tortricoidea, Geometroidea, Noctuoidea and others.Separate analyses of mostly synonymous versus non-synonymous character sets revealed notable differences (though not strong conflict), including a marked influence of compositional heterogeneity on apparent signal in the third codon position (nt3). As available model partitioning methods cannot correct for this variation, we assessed overall phylogeny resolution through separate examination of trees from each character set. Exploration of "tree space" with GARLI, using grid computing, showed that hundreds of searches are typically needed to find the best-feasible phylogeny estimate for these data. CONCLUSION: Our results (a) corroborate the broad outlines of the current working phylogenetic hypothesis for Ditrysia, (b) demonstrate that some prominent features of that hypothesis, including the position of the butterflies, need revision, and (c) resolve the majority of family and subfamily relationships within superfamilies as thus far sampled. Much further gene and taxon sampling will be needed, however, to strongly resolve individual deeper nodes.

Toward Upgrades-as-a-service in Distributed Systems - Tudor Dumitras; Narasimhan, Priya (Middleware'09 Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware, 2009)
Unavailability in distributed enterprise systems is usually the result of planned events, such as upgrades, rather than failures. Major system upgrades entail complex data conversions that are difficult to perform on the fly, in the face of live workloads. Minimizing the downtime imposed by such conversions is a time-intensive and error-prone manual process. We propose upgrades-as-a-service, a novel approach that can eliminate all the causes of planned downtime recorded during the upgrade history of one of the ten most popular websites. Building on the lessons learned from past research on live upgrades in middleware systems, upgrades-as-a-service trade off a need for additional hardware resources during the upgrade for the ability to perform end-to-end upgrades online, with minimal application-specific knowledge.

Tree-Based Encoding for Cancellations on Morse Complexes - Čomić,L.; De Floriani, Leila (Combinatorial Image Analysis, 2009)
A scalar function f, defined on a manifold M, can be simplified by applying a sequence of removal and contraction operators, which eliminate its critical points in pairs, and simplify the topological representation of M, provided by Morse complexes of f. The inverse refinement operators, together with a dependency relation between them, enable a construction of a multi-resolution representation of such complexes. Here, we encode a sequence of simplification operators in a data structure called an augmented cancellation forest, which will enable procedural encoding of the inverse refinement operators, and reduce the dependency relation between modifications of the Morse complexes. In this way, this representation will induce a high flexibility of the hierarchical representation of the Morse complexes, producing a large number of Morse complexes at different resolutions that can be obtained from the hierarchy.

UbiGreen: investigating a mobile tool for tracking and supporting green transportation habits - Jon Froehlich; Dillahunt,Tawanna; Klasnja,Predrag; Mankoff,Jennifer; Consolvo,Sunny; Harrison,Beverly; Landay,James A. (Proceedings of the 27th international conference on Human factors in computing systems, 2009)
Keywords: ambient displays; mobile phones; sensing; Sustainability; transportation; ubicomp

Understanding the design tradeoffs for cooperative streaming multicast - Nandi,A.; Bhattacharjee, Bobby; Druschel,P. (Technical report MPI-SWS-2009-002, Max Planck Institute for Software Systems, 2009)
Video streaming over the Internet is rapidly increasing in popular-ity, but the availability and quality of the content is limited by the high bandwidth cost for server-based solutions. Cooperative end- system multicast (CEM) has emerged as a promising paradigm for content distribution in the Internet, because the bandwidth over- head of disseminating content is shared among the participants of the CEM overlay network. Several CEM systems have been pro- posed and deployed, but the tradeoffs inherent in the different de- signs are not well understood. In this work, we provide a common framework in which different CEM design choices can be empirically and systematically evalu- ated. Our results show that all CEM protocols are inherently lim- ited in certain aspects of their performance. We distill our observa- tions into a novel model that explains the inherent tradeoffs of CEM design choices and provides bounds on the practical performance limits of any future CEM protocol. In particular, the model conjec- tures that no CEM design can simultaneously achieve all three of low overhead, low lag, and high streaming quality.

Understanding videos, constructing plots learning a visually grounded storyline model from annotated videos - Gupta,A.; Srinivasan,P.; Shi,Jianbo; Davis, Larry S. (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)
Analyzing videos of human activities involves not only recognizing actions (typically based on their appearances), but also determining the story/plot of the video. The storyline of a video describes causal relationships between actions. Beyond recognition of individual actions, discovering causal relationships helps to better understand the semantic meaning of the activities. We present an approach to learn a visually grounded storyline model of videos directly from weakly labeled data. The storyline model is represented as an AND-OR graph, a structure that can compactly encode storyline variation across videos. The edges in the AND-OR graph correspond to causal relationships which are represented in terms of spatio-temporal constraints. We formulate an Integer Programming framework for action recognition and storyline extraction using the storyline model and visual groundings learned from training data.
Keywords: (artificial; action; activity; analysis; integer; AND-OR; annotation; video; coding; constraint; video; construction; semantic; extraction; graph; framework; plots; graph; encoding; human; grounded; intelligence); spatiotemporal; learning; meaning; spatio-temporal; model; phenomena; video; Programming; programming; learning; recognition; human; representation; integer; storyline; theory; image; understanding; visually

A unified approach to ranking in probabilistic databases - Li,Jian; Saha,Barna; Deshpande, Amol (Proceedings of the VLDB Endowment, 2009)
The dramatic growth in the number of application domains that naturally generate probabilistic, uncertain data has resulted in a need for efficiently supporting complex querying and decision-making over such data. In this paper, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criteria optimization problem, and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRFω and PRFe, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRFe, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.

The University of Maryland statistical machine translation system for the Fourth Workshop on Machine Translation - Dyer,C.; Setiawan,H.; Marton,Y.; Resnik, Philip (Proceedings of the Fourth Workshop on Statistical Machine Translation, 2009)

Unsupervised search-based structured prediction - Daumé, Hal (Proceedings of the 26th Annual International Conference on Machine Learning, 2009)
We describe an adaptation and application of a search-based structured prediction algorithm "Searn" to unsupervised learning problems. We show that it is possible to reduce unsupervised learning to supervised learning and demonstrate a high-quality un-supervised shift-reduce parsing model. We additionally show a close connection between unsupervised Searn and expectation maximization. Finally, we demonstrate the efficacy of a semi-supervised extension. The key idea that enables this is an application of the predict-self idea for unsupervised learning.

Using citations to generate surveys of scientific paradigms - Mohammad,Saif; Dorr, Bonnie J; Egan,Melissa; Hassan,Ahmed; Muthukrishan,Pradeep; Qazvinian,Vahed; Radev,Dragomir; Zajic, David (Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, 2009)
The number of research publications in various disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of technical material. In this paper we present the first steps in producing an automatically generated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization techniques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the framework of multi-document survey creation, citation texts can play a crucial role.

Using formal specifications to support testing - Hierons,Robert M.; Krause,Paul; Lüttgen,Gerald; Simons,Anthony J. H.; Vilkomir,Sergiy; Woodward,Martin R.; Zedan,Hussein; Bogdanov,Kirill; Bowen,Jonathan P.; Cleaveland, Rance; Derrick,John; Dick,Jeremy; et al. (ACM Computing Surveys, 2009)

Using Graphics Processors for High-Performance Computation and Visualization of Plasma Turbulence - Stantchev,G.; Juba,D.; Dorland,W.; Varshney, Amitabh (Computing in Science Engineering, 2009)
Direct numerical simulation (DNS) of turbulence is computationally intensive and typically relies on some form of parallel processing. The authors present techniques to map DNS computations to modern graphics processing units (GPUs), which are characterized by very high memory bandwidth and hundreds of SPMD (single-program-multiple-data) processors.
Keywords: analysis; parallel; computation; parallel; computing; numerical; direct; engineering; numerical; PROCESSING; processing; plasma; processors; data; simulation; graphics; systems; nuclear; turbulence; turbulence; units; high-performance; visualisation; multiprocessing; visualization; single-program-multiple-data

Video Compression and Retrieval of Moving Object Location Applied to Surveillance - Schwartz,W.; Pedrini,H.; Davis, Larry S. (Image Analysis and Recognition, 2009)
A major problem in surveillance systems is the storage requirements for video archival; videos are recorded continuously for long periods of time, resulting in large amounts of data. Therefore, it is essential to apply efficient compression techniques. Additionally, it is useful to be able to index the archived videos based on events. In general, such events are defined by the interaction among moving objects in the scene. Consequently, besides data compression, efficient ways of storing moving objects should be considered. We present a method that exploits both temporal and spatial redundancy of videos captured from static cameras to perform compression and subsequently allows fast retrieval of moving object locations directly from the compressed data. Experimental results show that the approach achieves high compression ratios compared to other existing video compression techniques without significant quality degradation and is fast due to the simplicity of the operations required for compression and decompression.

Visual Tag - BRETEY,STEVE; Kuhnly,Keith; Davis, Larry S. (2009)
An improved animal tag for application to an animal's ear which comprises a male portion that includes a flat segment and a projection segment, a female portion that includes a generally square or generally oval shaped flat segment and a raised segment with an aperture; wherein the projection segment of the male portion is adapted to be inserted through the animal's ear and into the aperture when pressure is applied thereto.

Visual Tracking by Continuous Density Propagation in Sequential Bayesian Filtering Framework - Han,Bohyung; Zhu,Ying; Comaniciu, D.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009)
Particle filtering is frequently used for visual tracking problems since it provides a general framework for estimating and propagating probability density functions for nonlinear and non-Gaussian dynamic systems. However, this algorithm is based on a Monte Carlo approach and the cost of sampling and measurement is a problematic issue, especially for high-dimensional problems. We describe an alternative to the classical particle filter in which the underlying density function has an analytic representation for better approximation and effective propagation. The techniques of density interpolation and density approximation are introduced to represent the likelihood and the posterior densities with Gaussian mixtures, where all relevant parameters are automatically determined. The proposed analytic approach is shown to perform more efficiently in sampling in high-dimensional space. We apply the algorithm to real-time tracking problems and demonstrate its performance on real video sequences as well as synthetic examples.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Computer-Assisted; Pattern Recognition; Computer-Assisted; Subtraction Technique; Monte Carlo approach; continuous density propagation; density approximation; density interpolation; nonGaussian dynamic systems; nonlinear dynamic systems; particle filtering; probability density functions; sequential Bayesian filtering framework; video sequences

Voronoi++: ADynamic Page Segmentation approach based on Voronoi and Docstrum features - Agrawal,Mudit; David Doermann (International Conference on Document Analysis and Recognition (ICDAR '09), 2009)
This paper presents a dynamic approach to document page segmentation. Current page segmentation algorithms lack the ability to dynamically adapt local variations in the size, orientation and distance of components within a page. Our approach builds upon one of the best algorithms, Kise et. al. work based on Area Voronoi Diagrams, which adapts globally to page content to determine algorithm parameters. In our approach, local thresholds are determined dynamically based on parabolic relations between components, and Docstrum based angular and neighborhood features are integrated to improve accuracy. Zone-based evaluation was performed on four sets of printed and handwritten documents in English and Arabic scripts and an increase of 33% in accuracy is reported.

What a mesh: understanding the design tradeoffs for streaming multicast - Nandi,Animesh; Bhattacharjee, Bobby; Druschel,Peter (SIGMETRICS Perform. Eval. Rev., 2009)
Cooperative end-system multicast (CEM) is a promising paradigm for Internet video distribution. Several CEM systems have been proposed and deployed, but the tradeoffs inherent in the different designs are not well understood. In this work, we provide a common framework in which different CEM design choices can be empirically and systematically evaluated. Based on our results, we conjecture that all CEM systems must abide by a set of fundamental design constraints, which we express in a simple model. By necessity, existing system implementations couple the data- and control-planes and often use different transport protocols.

Why Do Upgrades Fail and What Can We Do About It?: Toward Dependable, Online Upgrades in Enterprise System - Tudor Dumitras; Narasimhan, Priya (Middleware'09 Proceedings of the 10th ACM/IFIP/USENIX International Conference on Middleware, 2009)
Enterprise-system upgrades are unreliable and often produce downtime or data-loss. Errors in the upgrade procedure, such as broken dependencies, constitute the leading cause of upgrade failures. We propose a novel upgrade-centric fault model, based on data from three independent sources, which focuses on the impact of procedural errors rather than software defects. We show that current approaches for upgrading enterprise systems, such as rolling upgrades, are vulnerable to these faults because the upgrade is not an atomic operation and it risks breaking hidden dependencies among the distributed system-components. We also present a mechanism for tolerating complex procedural errors during an upgrade. Our system, called Imago, improves availability in the fault-free case, by performing an online upgrade, and in the faulty case, by reducing the risk of failure due to breaking hidden dependencies. Imago performs an end-to-end upgrade atomically and dependably, by dedicating separate resources to the new version and by isolating the old version from the upgrade procedure. Through fault injection, we show that Imago is more reliable than online-upgrade approaches that rely on dependency-tracking and that create system states with mixed versions.

Wideband fast multipole accelerated boundary element methods for the three-dimensional Helmholtz equation. - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2009)
The development of a fast multipole method (FMM) accelerated iterative solution of the boundary element method (BEM) for the Helmholtz equations in three dimensions is described. The FMM for the Helmholtz equation is significantly different for problems with low and high kD, where k is the wave number and D the domain size, and for large problems, the method must be switched between levels of the hierarchy. The BEM requires several approximate computations: numerical quadrature and approximations of the boundary shapes using elements. These errors must be balanced against approximations introduced by the FMM and the convergence criterion for an iterative solution. These different errors must all be chosen in a way that, on the one hand, excess work is not done and, on the other, that the error achieved by the overall computation is acceptable. Details of translation operators for low and high kD choice of representations and BEM quadrature schemes, all consistent with these approximations, are described. A novel preconditioner using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed solvers for large boundary value problems with 0.0001⩽kD⩽500 are presented and shown to perform close to theoretical expectations.