1st ACM workshop on hot topics in software upgrades (HotSWUp 2008) - Tudor Dumitras; Dig, Danny; Neamtiu, Iulian (OOPSLA Companion'08 Companion to the 23rd ACM SIGPLAN Conference on Object-Oriented Programming Systems Languages and Applications, 2008)
The goal of HotSWUp is to identify cutting-edge research ideas for implementing software upgrades. Actively-used software is upgraded regularly to incorporate bug fixes and security patches or to keep up with the evolving requirements. Whether upgrades are applied offline or online, they significantly impact the software's performance and reliability. Recently-introduced commercial products aim to address various aspects of this problem, e.g., programing language/framework/middleware support for online upgrade, large-scale dissemination of fine-grained updates, live data migration in storage-area networks. However, recent studies and a large body of anecdotal evidence suggest that, in practice, upgrades are failure-prone, tedious, and expensive.
Keywords: software; upgrades

ACamera Phone Based Currency Reader for the Visually Impaired - Liu,Xu; David Doermann (The Tenth International ACMSIG ACCESS Conference on Computers and Accessibility, 2008)
In this paper we present a camera phone-based currency reader for the visually impaired to denominate face values of the U.S. paper dollars. Currently, they can only be identified visually and this situation will continue in foreseeable future. Our solution harvests the imaging and computational power on camera phones to read bills. Considering it is impractical for the visually impaired to capture high quality image, our currency reader performs real time processing for each captured frame as the camera approaches the bill. We develop efficient background subtraction and perspective correction algorithms and train our currency reader using the Ada-boost framework, which is efficient. Our currency reader processes 10 frames/second and achieves a false positive rate of 10^-4. Major smart phone platforms, including Symbian and Windows Mobile, are supported.

ACamera-based Mobile Data Channel: Capacity and Analysis - Liu,Xu; David Doermann; Li,H. (ACM International Conference on Multimedia, 2008)
In this paper we propose a novel application, color Video Code (V-Code) and analyze its data transmission capacity through camera-based mobile data channels. Users can use the camera on a mobile device (PDA or camera phone) as a passive and pervasive data channel to download data encoded as a sequence of color visual patterns. The color V-Code is animated on a display, acquired by the camera and decoded by the pre-embedded software in the mobile device. One interesting question is what is the data transmission capacity it can achieve, theoretically and practically. To answer this question we build a camera channel model to measure color degradation using information theory and show that the capacity of the camera channel can be improved with the optimized color selection through color calibration. After initialization color models are learned automatically as downloading proceeds. We address the problem of precise registration, and implemented a fast perspective correction method to accelerate the decoder in real-time on a resource constrained device. With the optimized color set and efficient implementation we achieve a transmission bit rate of 15.4kbps on a common iMate Jamin phone (200MHz CPU). This speed is faster than the average GPRS bit rate (12kbps).

The acl anthology reference corpus: A reference dataset for bibliographic research in computational linguistics - Bird,S.; Dale,R.; Dorr, Bonnie J; Gibson,B.; Joseph,M.T.; Kan,M.Y.; Lee,D.; Powley,B.; Radev,D.R.; Tan,Y.F. (Proc. of the 6th International Conference on Language Resources and Evaluation Conference (LREC’08), 2008)
The ACL Anthology is a digital archive of conference and journal papers in natural language processing and computational linguistics.Its primary purpose is to serve as a reference repository of research results, but we believe that it can also be an object of study and a platform for research in its own right. We describe an enriched and standardized reference corpus derived from the ACL Anthology that can be used for research in scholarly document processing. This corpus, which we call the ACL Anthology Reference Corpus (ACL ARC), brings together the recent activities of a number of research groups around the world. Our goal is to make the corpus widely available, and to encourage other researchers to use it as a standard testbed for experiments in both bibliographic and bibliometric research.

Action recognition using ballistic dynamics - Vitaladevuni,S.N.; Kellokumpu,V.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
We present a Bayesian framework for action recognition through ballistic dynamics. Psycho-kinesiological studies indicate that ballistic movements form the natural units for human movement planning. The framework leads to an efficient and robust algorithm for temporally segmenting videos into atomic movements. Individual movements are annotated with person-centric morphological labels called ballistic verbs. This is tested on a dataset of interactive movements, achieving high recognition rates. The approach is also applied on a gesture recognition task, improving a previously reported recognition rate from 84% to 92%. Consideration of ballistic dynamics enhances the performance of the popular Motion History Image feature. We also illustrate the approachpsilas general utility on real-world videos. Experiments indicate that the method is robust to view, style and appearance variations.
Keywords: analysis; image; Bayesian; dynamics; gesture; feature; person-centric; framework; action; History; image; labels; psycho-kinesiological; morphological; MOTION; Movement; movements; motion; planning; interactive; processing; recognition; recognition; ballistic; recognition; image; segmentation; video; signal; studies; image; task; human

Applying automatically generated semantic knowledge: A case study in machine translation - Madnani,N.; Resnik, Philip; Dorr, Bonnie J; Schwartz,R. (NSF Symposium on Semantic Knowledge Discovery, Organization and Use, 2008)
In this paper, we discuss how we apply automatically generated semantic knowledge to benefit statisticalmachine translation (SMT). Currently, almost all statistical machine translation systems rely heavily on memorizing translations of phrases. Some systems attempt to go further and generalize these learned phrase translations into templates using empirically derived information about word alignments and a small amount of syntactic information, if at all. There are several issues in a SMT pipeline that could be addressed by the application of semantic knowledge, if such knowledge were easily available. One such issue, an important one, is that of reference sparsity. The fundamental problem that translation systems have to face is that there is no such thing as the correct translation for any sentence. In fact, any given source sentence can often be translated into the target language in many valid ways. Since there can be many “correct answers,” almost all models employed by SMT systems require, in addition to a large bitext, a held-out development set comprised of multiple high-quality, human-authored reference translations in the target language in order to tune their parameters relative to a translation quality metric.1 There are several reasons that this requirement is not an easy one to satisfy. First, with a few exceptions—notably NIST’s annual MT evaluations—most new MT research data sets are provided with only a single reference translation. Second, obtaining multiple reference translations in rapid development, low-density source language scenarios (e.g. (Oard, 2003)) is likely to be severely limited (or made entirely impractical) by limitations of time, cost, and ready availability of qualified translators.

Are multiple reference translations necessary? investigating the value of paraphrased reference translations in parameter optimization - Madnani,N.; Resnik, Philip; Dorr, Bonnie J; Schwartz,R. (Proceedings of the Eighth Conference of the Association for Machine Translation in the Americas, October, 2008)
Most state-of-the-art statistical machine trans-lation systems use log-linear models, which are defined in terms of hypothesis features and weights for those features. It is standard to tune the feature weights in order to maxi- mize a translation quality metric, using held- out test sentences and their corresponding ref- erence translations. However, obtaining refer- ence translations is expensive. In our earlier work (Madnani et al., 2007), we introduced a new full-sentence paraphrase technique, based on English-to-English decoding with an MT system, and demonstrated that the resulting paraphrases can be used to cut the number of human reference translations needed in half. In this paper, we take the idea a step further, asking how far it is possible to get with just a single good reference translation for each item in the development set. Our analysis suggests that it is necessary to invest in four or more hu- man translations in order to significantly im- prove on a single translation augmented by monolingual paraphrases.

Audio Camera Using Microphone Arrays for Real Time Capture of Audio Images ... - Duraiswami, Ramani; O'donovan,Adam; Neumann, Jan; Gumerov, Nail A. (2008)
Spherical microphone arrays provide an ability to compute the acoustical intensity corresponding to different spatial directions in a given frame of audio data. These intensities may be exhibited as an image and these images are generated at a high frame rate to achieve a video image if the data capture and intensity computations can be performed sufficiently quickly, thereby creating a frame-rate audio camera. A description is provided herein regarding how such a camera is built and the processing done sufficiently quickly using graphics processors. The joint processing of and captured frame-rate audio and video images enables applications such as visual identification of noise sources, beamforming and noise-suppression in video conferenceing and others, by accounting for the spatial differences in the location of the audio and the video cameras. Based on the recognition that the spherical array can be viewed as a central projection camera, such joint analysis can be performed.

Automatic online tuning for fast Gaussian summation - Morariu,V.; Srinivasan,B.V.; Raykar,V.C.; Duraiswami, Ramani; Davis, Larry S. (Advances in Neural Information Processing Systems, 2008)
Many machine learning algorithms require the summation of Gaussian kernelfunctions, an expensive operation if implemented straightforwardly. Several meth- ods have been proposed to reduce the computational complexity of evaluating such sums, including tree and analysis based methods. These achieve varying speedups depending on the bandwidth, dimension, and prescribed error, making the choice between methods difficult for machine learning tasks. We provide an algorithm that combines tree methods with the Improved Fast Gauss Transform (IFGT). As originally proposed the IFGT suffers from two problems: (1) the Taylor series expansion does not perform well for very low bandwidths, and (2) parameter se- lection is not trivial and can drastically affect performance and ease of use. We address the first problem by employing a tree data structure, resulting in four eval- uation methods whose performance varies based on the distribution of sources and targets and input parameters such as desired accuracy and bandwidth. To solve the second problem, we present an online tuning approach that results in a black box method that automatically chooses the evaluation method and its parameters to yield the best performance for the input data, desired accuracy, and bandwidth. In addition, the new IFGT parameter selection approach allows for tighter error bounds. Our approach chooses the fastest method at negligible additional cost, and has superior performance in comparisons with previous approaches.

Bandwidth-constrained queries in sensor networks - Deligiannakis,A.; Kotidis,Y.; Roussopoulos, Nick (The VLDB Journal, 2008)

A Bayesian statistics approach to multiscale coarse graining - Liu,P.; Shi,Q.; Daumé, Hal; Voth,G. A (The Journal of chemical physics, 2008)

Beyond nouns: Exploiting prepositions and comparative adjectives for learning visual classifiers - Gupta,A.; Davis, Larry S. (Computer Vision–ECCV 2008, 2008)
Learning visual classifiers for object recognition from weakly labeled data requires determining correspondence between image regions and semantic object classes. Most approaches use co-occurrence of “nouns” and image features over large datasets to determine the correspondence, but many correspondence ambiguities remain. We further constrain the correspondence problem by exploiting additional language constructs to improve the learning process from weakly labeled data. We consider both “prepositions” and “comparative adjectives” which are used to express relationships between objects. If the models of such relationships can be determined, they help resolve correspondence ambiguities. However, learning models of these relationships requires solving the correspondence problem. We simultaneously learn the visual features defining “nouns” and the differential visual features defining such “binary-relationships” using an EM-based approach.

Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One - Choi, Seung Geol; Dana Dachman-Soled; Malkin, Tal; Wee, Hoeteck (Theory of Cryptography, 2008)
We show how to transform any semantically secure encryption scheme into a non-malleable one, with a black-box construction that achieves a quasi-linear blow-up in the size of the ciphertext. This improves upon the previous non-black-box construction of Pass, Shelat and Vaikuntanathan (Crypto ’06). Our construction also extends readily to guarantee non-malleability under a bounded-CCA2 attack, thereby simultaneously improving on both results in the work of Cramer et al. (Asiacrypt ’07). Our construction departs from the oft-used paradigm of re-encrypting the same message with different keys and then proving consistency of encryptions; instead, we encrypt an encoding of the message with certain locally testable and self-correcting properties. We exploit the fact that low-degree polynomials are simultaneously good error-correcting codes and a secret-sharing scheme.
Keywords: Algorithm Analysis and Problem Complexity; black-box constructions; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; non-malleability; public-key encryption; semantic security; Systems and Data Security

Camera Phone Based Tools for People with Visual Impairments - Liu,Xu; David Doermann; Li,H. (The First International Workshop on Mobile Multimedia Processing, 2008)
In this paper we describe a set of applications that utilize a camera phone to help the visually impaired with daily tasks. Our “MobileEye” software suite turns a camera enabled mobile device into a multi-purpose vision tool that helps individuals with visual disabilities. MobileEye consists of four subsystems for different types of visual disabilities. A color channel mapper helps distinguish colors, a software magnifier helps low vision individuals see detail, a pattern recognizer helps the severely impaired recognize objects and a document retriever provides access to printed materials. We apply cutting edge computer vision and image processing technologies on the mobile devices and tackle the challenges of limited computational resources and low image quality. We also consider the usability for the visually impaired so our system requires minimum keyboard operation. We provide a full software solution which runs on Symbian and Windows Mobile handsets. This paper provides a high level overview of the system.

Cancellation of critical points in 2D and 3D Morse and Morse-Smale complexes - Čomić,L.; De Floriani, Leila (Discrete Geometry for Computer Imagery, 2008)
Morse theory studies the relationship between the topology of a manifold M and the critical points of a scalar function f defined on M. The Morse-Smale complex associated with f induces a subdivision of M into regions of uniform gradient flow, and represents the topology of M in a compact way. Function f can be simplified by cancelling its critical points in pairs, thus simplifying the topological representation of M, provided by the Morse-Smale complex. Here, we investigate the effect of the cancellation of critical points of f in Morse-Smale complexes in two and three dimensions by showing how the change of connectivity of a Morse-Smale complex induced by a cancellation can be interpreted and understood in a more intuitive and straightforward way as a change of connectivity in the corresponding ascending and descending Morse complexes. We consider a discrete counterpart of the Morse-Smale complex, called a quasi-Morse complex, and we present a compact graph-based representation of such complex and of its associated discrete Morse complexes, showing also how such representation is affected by a cancellation.

Canny edge detection on NVIDIA CUDA - Luo,Yuancheng; Duraiswami, Ramani (Computer Vision and Pattern Recognition Workshops, 2008. CVPRW '08. IEEE Computer Society Conference on, 2008)
The Canny edge detector is a very popular and effective edge feature detector that is used as a pre-processing step in many computer vision algorithms. It is a multi-step detector which performs smoothing and filtering, non-maxima suppression, followed by a connected-component analysis stage to detect ldquotruerdquo edges, while suppressing ldquofalserdquo non edge filter responses. While there have been previous (partial) implementations of the Canny and other edge detectors on GPUs, they have been focussed on the old style GPGPU computing with programming using graphical application layers. Using the more programmer friendly CUDA framework, we are able to implement the entire Canny algorithm. Details are presented along with a comparison with CPU implementations. We also integrate our detector in to MATLAB, a popular interactive simulation package often used by researchers. The source code will be made available as open source.
Keywords: algorithms; connected-component; analysis; application; Canny; CUDA; computer; detection; feature; detection; NVIDIA; detector; filtering; graphical; detector; non; edge; extraction; smoothing; feature; filter; layers; multistep; methods; responses; nonmaxima; stage; edge; suppression; smoothing; computer; VISION; vision; edge

On classification, ranking, and probability estimation - Flach,P.; Matsubara,E.T.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Internationales Begegnungs- und Forschungszentrum fur Informatik (IBFI), Schloss Dagstuhl, Germany, 2008)
Given a binary classification task, a ranker is an algorithm that can sort a set of instances from highest to lowest expectation that the instance is positive. In contrast to a classifier, a ranker does not output class predictions – although it can be turned into a classifier with help of an additional procedure to split the ranked list into two. A straightforward way to compute rankings is to train a scoring classifier to assign numerical scores to instances, for example the predicted odds that an instance is positive. However, rankings can be computed without scores, as we demonstrate in this paper. We propose a lexicographic ranker, LexRank , whose rankings are derived not from scores, but from a simple ranking of attribute values obtained from the training data. Although various metrics can be used, we show that by using the odds ratio to rank the attribute values we obtain a ranker that is conceptually close to the naive Bayes classifier, in the sense that for every instance of LexRank there exists an instance of naive Bayes that achieves the same ranking. However, the reverse is not true, which means that LexRank is more biased than naive Bayes. We systematically develop the relationships and differences between classification, ranking, and probability estimation, which leads to a novel connection between the Brier score and ROC curves. Combining LexRank with isotonic regression, which derives probability estimates from the ROC convex hull, results in the lexicographic probability estimator LexProb.

Combining Classifiers with Informational Confidence - Jaeger,Stefan; Ma,Huanfeng; David Doermann (Studies in Computational Intelligence: Machine Learning in Document Analysis and RecognitionStudies in Computational Intelligence: Machine Learning in Document Analysis and Recognition, 2008)
We propose a new statistical method for learning normalized confidence values in multiple classifier systems. Our main idea is to adjust confidence values so that their nominal values equal the information actually conveyed. In order to do so, we assume that information depends on the actual performance of each confidence value on an evaluation set. As information measure, we use Shannon's well-known logarithmic notion of information. With the confidence values matching their informational content, the classifier combination scheme reduces to the simple sum-rule, theoretically justifying this elementary combination scheme. In experimental evaluations for script identification, and both handwritten and printed character recognition, we achieve a consistent improvement on the best single recognition rate. We cherish the hope that our information-theoretical framework helps fill the theoretical gap we still experience in classifier combination, and puts the excellent practical performance of multiple classifier systems on a more solid basis.

Combining open-source with research to re-engineer a hands-on introductory NLP course - Madnani,Nitin; Dorr, Bonnie J (Proceedings of the Third Workshop on Issues in Teaching Computational Linguistics, 2008)
We describe our first attempts to re-engineer the curriculum of our introductory NLP course by using two important building blocks: (1) Access to an easy-to-learn programming language and framework to build hands-on programming assignments with real-world data and corpora and, (2) Incorporation of interesting ideas from recent NLP research publications into assignment and examination problems. We believe that these are extremely important components of a curriculum aimed at a diverse audience consisting primarily of first-year graduate students from both linguistics and computer science. Based on overwhelmingly positive student feedback, we find that our attempts were hugely successful.

Compressive sensing for background subtraction - Cevher, V.; Sankaranarayanan, A.; Duarte, M.; Reddy, D.; Baraniuk, R.; Chellapa, Rama (Computer Vision–ECCV 2008, 2008)
Compressive sensing (CS) is an emerging field that provides a framework for image recovery using sub-Nyquist sampling rates. The CS theory shows that a signal can be reconstructed from a small set of random projections, provided that the signal is sparse in some basis, e.g., wavelets. In this paper, we describe a method to directly recover background subtracted images using CS and discuss its applications in some communication constrained multi-camera computer vision problems. We show how to apply the CS theory to recover object silhouettes (binary background subtracted images) when the objects of interest occupy a small portion of the camera view, i.e., when they are sparse in the spatial domain. We cast the background subtraction as a sparse approximation problem and provide different solutions based on convex optimization and total variation. In our method, as opposed to learning the background, we learn and adapt a low dimensional compressed representation of it, which is sufficient to determine spatial innovations; object silhouettes are then estimated directly using the compressive samples without any auxiliary image reconstruction. We also discuss simultaneous appearance recovery of the objects using compressive measurements. In this case, we show that it may be necessary to reconstruct one auxiliary image. To demonstrate the performance of the proposed algorithm, we provide results on data captured using a compressive single-pixel camera. We also illustrate that our approach is suitable for image coding in communication constrained problems by using data captured by multiple conventional cameras to provide 2D tracking and 3D shape reconstruction results with compressive measurements.

Computer Vision and Image Processing Techniques for Mobile Application - Liu,Xu; David Doermann (Center for Automation Research, University of Maryland, 2008)
Camera phones have penetrated every corner of society and have become a focal point for communications. In our research we extend the traditional use of such devices to help bridge the gap between physical and digital worlds. Their combined image acquisition, processing, storage, and communication capabilities in a compact, portable device make them an ideal platform for embedding computer vision and image processing capabilities in the pursuit of new mobile applications. This technical report is presented as a series of computer vision and image processing techniques together with their applications on the mobile device. We have developed a set of techniques for ego-motion estimation, enhancement, feature extraction, perspective correction, object detection, and document retrieval that serve as a basis for such applications. Our applications include a dynamic video barcode that can transfer significant amounts of information visually, a document retrieval system that can retrieve documents from low resolution snapshots, and a series of applications for the users with visual disabilities such as a currency reader. Solutions for mobile devices require a fundamentally different approach than traditional vision techniques that run on traditional computers, so we consider user-device interaction and the fact that these algorithms must execute in a resource constrained environment. For each problem we perform both theoretical and empirical analysis in an attempt to optimize performance and usability. The thesis makes contributions related to efficient implementation of image processing and computer vision techniques, analysis of information theory, feature extraction and analysis of low quality images, and device usability.

Computing word-pair antonymy - Mohammad,Saif; Dorr, Bonnie J; Hirst,Graeme (Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008)
Knowing the degree of antonymy between words has widespread applications in natural language processing. Manually-created lexicons have limited coverage and do not include most semantically contrasting word pairs. We present a new automatic and empirical measure of antonymy that combines corpus statistics with the structure of a published thesaurus. The approach is evaluated on a set of closest-opposite questions, obtaining a precision of over 80%. Along the way, we discuss what humans consider antonymous and how antonymy manifests itself in utterances.

Confluent Volumetric Visualization of Gyrokinetic Turbulence - Stantchev,G.; Juba,D.; Dorland,W.; Varshney, Amitabh (Plasma Science, IEEE Transactions on, 2008)
Data from gyrokinetic turbulence codes are often difficult to visualize due their high dimensionality, the nontrivial geometry of the underlying grids, and the vast range of spatial scales. We present an interactive visualization framework that attempts to address these issues. Images from a nonlinear gyrokinetic simulation are presented.
Keywords: flow; plasma; geometry; plasma; gyrokinetic; simulation; nontrivial; simulation; plasma; turbulence; turbulence; nonlinear; turbulence; volumetric; visualisation; plasma; visualization; flow

Constraint Integration for Efficient Multiview Pose Estimation with Self-Occlusions - Gupta,A.; Mittal,A.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2008)
Automatic initialization and tracking of human pose is an important task in visual surveillance. We present a part-based approach that incorporates a variety of constraints in a unified framework. These constraints include the kinematic constraints between parts that are physically connected to each other, the occlusion of one part by another, and the high correlation between the appearance of certain parts, such as the arms. The location probability distribution of each part is determined by evaluating appropriate likelihood measures. The graphical (nontree) structure representing the interdependencies between parts is utilized to "connect" such part distributions via nonparametric belief propagation. Methods are also developed to perform this optimization efficiently in the large space of pose configurations.
Keywords: Automated; Posture; Reproducibility of Results; Sensitivity and Specificity; Video Recording; Whole Body Imaging; automatic initialization; constraint integration; graphical structure; human pose tracking; kinematic constraint; likelihood measure; location probability distribution; multiview pose estimation; nonparametric belief propagation; optimization; pose configuration; se; Computer-Assisted; Imaging; Three-Dimensional; Pattern Recognition

Content-based assembly search: A step towards assembly reuse - Deshmukh,Abhijit S.; Banerjee,Ashis Gopal; Gupta, Satyandra K.; Sriram,Ram D. (Computer-Aided Design, 2008)
The increased use of CAD systems by product development organizations has resulted in the creation of large databases of assemblies. This explosion of assembly data is likely to continue in the future. In many situations, a text-based search alone may not be sufficient to search for assemblies and it may be desirable to search for assemblies based on the content of the assembly models. The ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate the reuse of existing assembly designs, thereby reducing the design time. Second, a lot of useful designs for manufacturing, and assembly knowledge are implicitly embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by designers to learn from the existing assembly designs. This paper describes a system for performing content-based searches on assembly databases. We identify templates for comprehensive search definitions and describe algorithms to perform content-based searches for mechanical assemblies. We also illustrate the capabilities of our system through several examples.
Keywords: Assembly characteristics; Assembly mating conditions; Content-based assembly search; Graph compatibility

Context and observation driven latent variable model for human pose estimation - Gupta,A.; Chen,T.; Chen,F.; Kimber,D.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Current approaches to pose estimation and tracking can be classified into two categories: generative and discriminative. While generative approaches can accurately determine human pose from image observations, they are computationally expensive due to search in the high dimensional human pose space. On the other hand, discriminative approaches do not generalize well, but are computationally efficient. We present a hybrid model that combines the strengths of the two in an integrated learning and inference framework. We extend the Gaussian process latent variable model (GPLVM) to include an embedding from observation space (the space of image features) to the latent space. GPLVM is a generative model, but the inclusion of this mapping provides a discriminative component, making the model observation driven. Observation Driven GPLVM (OD-GPLVM) not only provides a faster inference approach, but also more accurate estimates (compared to GPLVM) in cases where dynamics are not sufficient for the initialization of search in the latent space. We also extend OD-GPLVM to learn and estimate poses from parameterized actions/gestures. Parameterized gestures are actions which exhibit large systematic variation in joint angle space for different instances due to difference in contextual variables. For example, the joint angles in a forehand tennis shot are function of the height of the ball (Figure 2). We learn these systematic variations as a function of the contextual variables. We then present an approach to use information from scene/objects to provide context for human pose estimation for such parameterized actions.
Keywords: estimation; estimation; image; Gaussian; gestures; pose; latent; learning; parameterized; model; human; observations; integrated; pose; process; processes; gesture; processing; pose; recognition; image; tracking; Gaussian; variable

Contribution to a Taxonomy of Non-Manifold Models Based on Topological Properties - Leon,Jean-Claude; De Floriani, Leila (ASME Conference Proceedings, 2008)
Non-manifold models have classically been used in Finite Element (FE) simulations to describe the shape of a mechanical part. Sketching the shape of an object is also important in a design stage, where non-manifold models could be of help for the designer. The purpose of the taxonomy proposed here is to be able either to accept or reject them based on the design context and on the type of product. This will contribute to model non-manifold objects and to their binary classification. The proposed taxonomy is also based on the topological properties of non-manifold objects, and especially on topological invariants. We will classify several topological properties as local or global ones, and we will illustrate how such properties can help either modelling these objects or searching for them in industrial data bases when large numbers of FE models have been stored.

CrossTalk: The Journal of Defense Software Engineering. Volume 21, Number 10, October 2008 - Basili, Victor R.; Dangle,K.; Esker,L.; Marotta,F.; Rus,I.; Brosgol,B. M; Jamin,S.; Arthur,J. D; Ravichandar,R.; Wisnosky,D. E (DTIC Document, 2008)

Cross-task knowledge-constrained self training - Daumé, Hal (Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008)

Decentralized discovery of camera network topology - Farrell,R.; Davis, Larry S. (Distributed Smart Cameras, 2008. ICDSC 2008. Second ACM/IEEE International Conference on, 2008)
One of the primary uses of camera networks is the observation and tracking of objects within some domain. Substantial research has gone into tracking objects within single and multiple views. However, few such approaches scale to large numbers of sensors, and those that do require an understanding of the network topology. Camera network topology models camera adjacency in the context of tracking: when an object/entity leaves one camera, which cameras could it appear at next? This paper presents a decentralized approach for estimating a camera networkpsilas topology based on sequential Bayesian estimation using a modified multinomial distribution. Central to this method is an information-theoretic appearance model for observation weighting. The distributed nature of the approach utilizes all of the sensors as processing agents in collectively recovering the network topology. Experimental results are presented using camera networks varying in size from 10-100 nodes.
Keywords: adjacency; camera; Bayesian; camera; discovery; modified; distribution; sequential; estimation; Bayes; methods; distributed; multinomial; network; sensors; sensors; image; topology; decentralized

Delegating Capabilities in Predicate Encryption Systems - Elaine Shi; Waters,Brent (Automata, Languages and Programming, 2008)
In predicate encryption systems, given a capability, one can evaluate one or more predicates on the plaintext encrypted, while all other information about the plaintext remains hidden. We consider the role of delegation in such predicate encryption systems. Suppose Alice has a capability, and she wishes to delegate to Bob a more restrictive capability allowing the decryption of a subset of the information Alice can learn about the plaintext encrypted. We formally define delegation in predicate encryption systems, propose a new security definition for delegation, and give an efficient construction supporting conjunctive queries. The security of our construction can be reduced to the general 3-party Bilinear Diffie-Hellman assumption, and the Bilinear Decisional Diffie-Hellman assumption in composite order bilinear groups.
Keywords: Computer science

Detecting botnet membership with dnsbl counterintelligence - Ramachandran,A.; Feamster, Nick; Dagon,D. (Botnet Detection, 2008)

Discrete Distortion in Triangulated 3‐Manifolds - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Port,Umberto (Computer Graphics Forum, 2008)
We introduce a novel notion, that we call discrete distortion, for a triangulated 3-manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3-manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3-manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R4 defined by a scalar field on a 3D mesh. distance fields.
Keywords: I.3.3 [Computer Graphics]; I.3.5 [Computational Geometry and Object Modeling]

Distinguishing persistent failures from transient losses - Cunha,Ítalo; Teixeira,Renata; Feamster, Nick; Diot,Christophe (Proceedings of the 2008 ACM CoNEXT Conference, 2008)
Network tomography is a promising technique to identify the location of of IP faults. The goal of tomography is to infer the status of network internal characteristics based on end-to-end observations. In particular, binary tomography identifies the set of failed links from end-to-end path meausrments. Upon detecting the failure of one or more of the monitored paths, a monitor sends its measurements to a central coordinator. The coordinator then runs the binary tomography algorithm, which takes as input the topology of the network and the status (i.e., up or down) of all monitored paths and finds the minimum set of links that explain the observations.

Document Zone Classification Using Partial Least Squares and Hybrid Classifiers - Abd-Almageed, Wael; Agrawal,Mudit; Seo,W.; David Doermann (ICPR 2008. 19th International Conference on Pattern Recognition, 2008., 2008)
This paper introduces a novel document-zone classification algorithm. Low level image features are first extracted from document zones and partial least squares is used on pairs of classes to compute discriminating pairwise features. Rather than using the popular one-against-all and one-against-one voting schemes, we introduce a novel hybrid method which combines the benefits of the two schemes. The algorithm is applied on the University of Washington dataset and 97.3% classification accuracy is obtained.

The draft genome of the transgenic tropical fruit tree papaya (Carica papaya Linnaeus) - Ming,R.; Hou,S.; Feng,Y.; Yu,Q.; Dionne-Laporte,A.; Saw,J.H.; Senin,P.; Wang,W.; Ly,B.V.; Lewis,K.L.T.; others (Nature, 2008)
Papaya, a fruit crop cultivated in tropical and subtropical regions, is known for its nutritional benefits and medicinal applications. Here we report a 3 draft genome sequence of 'SunUp' papaya, the first commercial virus-resistant transgenic fruit tree to be sequenced. The papaya genome is three times the size of the Arabidopsis genome, but contains fewer genes, including significantly fewer disease-resistance gene analogues. Comparison of the five sequenced genomes suggests a minimal angiosperm gene set of 13,311. A lack of recent genome duplication, atypical of other angiosperm genomes sequenced so far, may account for the smaller papaya gene number in most functional groups. Nonetheless, striking amplifications in gene number within particular functional groups suggest roles in the evolution of tree-like habit, deposition and remobilization of starch reserves, attraction of seed dispersal agents, and adaptation to tropical daylengths. Transgenesis at three locations is closely associated with chloroplast insertions into the nuclear genome, and with topoisomerase I recognition sites. Papaya offers numerous advantages as a system for fruit-tree functional genomics, and this draft genome sequence provides the foundation for revealing the basis of Carica's distinguishing morpho-physiological, medicinal and nutritional properties.

Dynamic visual category learning - Tom Yeh; Darrell,Trevor (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Dynamic visual category learning calls for efficient adaptation as new training images become available or new categories are defined, existing training images or categories become modified or obsolete, or when categories are divided into subcategories or merged together. We develop novel methods for efficient incremental learning of SVM-based visual category classifiers to handle such dynamic tasks. Our method exploits previous classifier estimates to more efficiently learn the optimal parameters for the current set of training images and categories. We show empirically that for dynamic visual category tasks, our incremental learning methods are significantly faster than batch retraining.

THE EFFECT OF NETWORK STRUCTURE ON DYNAMIC TEAM FORMATION IN MULTI‐AGENT SYSTEMS - Gaston,Matthew E.; desJardins, Marie (Computational Intelligence, 2008)
Previous studies of team formation in multi-agent systems have typically assumed that the agent social network underlying the agent organization is either not explicitly described or the social network is assumed to take on some regular structure such as a fully connected network or a hierarchy. However, recent studies have shown that real-world networks have a rich and purposeful structure, with common properties being observed in many different types of networks. As multi-agent systems continue to grow in size and complexity, the network structure of such systems will become increasing important for designing efficient, effective agent communities.We present a simple agent-based computational model of team formation, and analyze the theoretical performance of team formation in two simple classes of networks (ring and star topologies). We then give empirical results for team formation in more complex networks under a variety of conditions. From these experiments, we conclude that a key factor in effective team formation is the underlying agent interaction topology that determines the direct interconnections among agents. Specifically, we identify the property of diversity support as a key factor in the effectiveness of network structures for team formation. Scale-free networks, which were developed as a way to model real-world networks, exhibit short average path lengths and hub-like structures. We show that these properties, in turn, result in higher diversity support; as a result, scale-free networks yield higher organizational efficiency than the other classes of networks we have studied.
Keywords: dynamics of networked systems; multi‐agent systems; network structure; team formation

Efficient Kriging via Fast Matrix-Vector Products - Memarsadeghi,N.; Raykar,V.C.; Duraiswami, Ramani; Mount, Dave (Aerospace Conference, 2008 IEEE, 2008)
Interpolating scattered data points is a problem of wide ranging interest. Ordinary kriging is an optimal scattered data estimator, widely used in geosciences and remote sensing. A generalized version of this technique, called cokriging, can be used for image fusion of remotely sensed data. However, it is computationally very expensive for large data sets. We demonstrate the time efficiency and accuracy of approximating ordinary kriging through the use of fast matrix-vector products combined with iterative methods. We used methods based on the fast Multipole methods and nearest neighbor searching techniques for implementations of the fast matrix-vector products.
Keywords: cokriging technique; fast matrix-vector products; fast multipole methods; geophysical techniques; image fusion; Interpolation; iterative methods; nearest neighbor searching; optimal scattered data estimator; Remote sensing; remotely sensed data; scattered data points; sensor fusion; time efficiency

Efficient Kriging via Fast Matrix-Vector Products - Memarsadeghi,N.; Raykar,V.C.; Duraiswami, Ramani; Mount, Dave (Aerospace Conference, 2008 IEEE, 2008)
Interpolating scattered data points is a problem of wide ranging interest. Ordinary kriging is an optimal scattered data estimator, widely used in geosciences and remote sensing. A generalized version of this technique, called cokriging, can be used for image fusion of remotely sensed data. However, it is computationally very expensive for large data sets. We demonstrate the time efficiency and accuracy of approximating ordinary kriging through the use of fast matrix-vector products combined with iterative methods. We used methods based on the fast Multipole methods and nearest neighbor searching techniques for implementations of the fast matrix-vector products.
Keywords: cokriging; data; data; scattered; efficiency; geophysical; estimator; remotely; fusion; fusion; interpolation; iterative; matrix-vector; methods; image; methods; nearest; methods; remote; multipole; neighbor; points; time; products; fast; scattered; searching; optimal; sensed; sensing; sensor; technique; fast; techniques; iterative

Energy Efficient Monitoring in Sensor Networks - Deshpande, Amol; Khuller, Samir; Malekian,Azarakhsh; Toossi,Mohammed (LATIN 2008: Theoretical InformaticsLATIN 2008: Theoretical Informatics, 2008)
In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k -Cover, which can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots) and activate each partition in a different time-slot. The goal is to find the partitioning that maximizes the coverage of the regions. This problem is known to be NP -hard. We first develop improved approximation algorithms for this problem based on its similarities to the max k -cut problem. We then consider a variation, called Set ( k , α )-cover, where each sensor is allowed to be active in α different time-slots. We develop a randomized routing algorithm for this problem. We then consider extensions where each sensor can monitor only a bounded number of regions in any time-slot. We develop the first approximation algorithms for this problem. An experimental evaluation of the algorithms we propose can be found in the full version of the paper.

Event modeling and recognition using markov logic networks - Tran,S.; Davis, Larry S. (Computer Vision–ECCV 2008, 2008)
We address the problem of visual event recognition in surveillance where noise and missing observations are serious problems. Common sense domain knowledge is exploited to overcome them. The knowledge is represented as first-order logic production rules with associated weights to indicate their confidence. These rules are used in combination with a relaxed deduction algorithm to construct a network of grounded atoms, the Markov Logic Network. The network is used to perform probabilistic inference for input queries about events of interest. The system’s performance is demonstrated on a number of videos from a parking lot domain that contains complex interactions of people and vehicles.

Exploiting Prior Knowledge in Intelligent Assistants: Combining Relational Models with Hierarchies - Natarajan,S.; Tadepalli,P.; Fern,A.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning - A Further Synthesis, 2008)
Statitsical relational models have been successfully used to model static probabilistic relationships between the entities of the domain. In this talk, we illustrate their use in a dynamic decison-theoretic setting where the task is to assist a user by inferring his intentional structure and taking appropriate assistive actions. We show that the statistical relational models can be used to succintly express the system's prior knowledge about the user's goal-subgoal structure and tune it with experience. As the system is better able to predict the user's goals, it improves the effectiveness of its assistance. We show through experiments that both the hierarchical structure of the goals and the parameter sharing facilitated by relational models significantly improve the learning speed.

Exploiting shared correlations in probabilistic databases - Sen,Prithviraj; Deshpande, Amol; Getoor, Lise (Proceedings of the VLDB Endowment, 2008)
There has been a recent surge in work in probabilistic databases, propelled in large part by the huge increase in noisy data sources --- from sensor data, experimental data, data from uncurated sources, and many others. There is a growing need for database management systems that can efficiently represent and query such data. In this work, we show how data characteristics can be leveraged to make the query evaluation process more efficient. In particular, we exploit what we refer to as shared correlations where the same uncertainties and correlations occur repeatedly in the data. Shared correlations occur mainly due to two reasons: (1) Uncertainty and correlations usually come from general statistics and rarely vary on a tuple-to-tuple basis; (2) The query evaluation procedure itself tends to re-introduce the same correlations. Prior work has shown that the query evaluation problem on probabilistic databases is equivalent to a probabilistic inference problem on an appropriately constructed probabilistic graphical model (PGM). We leverage this by introducing a new data structure, called the random variable elimination graph (rv-elim graph) that can be built from the PGM obtained from query evaluation. We develop techniques based on bisimulation that can be used to compress the rv-elim graph exploiting the presence of shared correlations in the PGM, the compressed rv-elim graph can then be used to run inference. We validate our methods by evaluating them empirically and show that even with a few shared correlations significant speed-ups are possible.

A Fast Algorithm for Learning a Ranking Function from Large-Scale Data Sets - Raykar,V.C.; Duraiswami, Ramani; Krishnapuram,B. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2008)
We consider the problem of learning a ranking function that maximizes a generalization of the Wilcoxon-Mann-Whitney statistic on the training data. Relying on an e-accurate approximation for the error function, we reduce the computational complexity of each iteration of a conjugate gradient algorithm for learning ranking functions from O(m2) to O(m), where m is the number of training samples. Experiments on public benchmarks for ordinal regression and collaborative filtering indicate that the proposed algorithm is as accurate as the best available methods in terms of ranking accuracy, when the algorithms are trained on the same data. However, since it is several orders of magnitude faster than the current state-of-the-art approaches, it is able to leverage much larger training data sets.
Keywords: Automated; Factual; Information Storage and Retrieval; Likelihood Functions; Models; Statistical; Pattern Recognition; Wilcoxon-Mann-Whitney statistics; collaborative filtering; error function; gradient algorithm; large-scale data sets; learning ranking functions; ranking function; training data; computational complexity; error analysis; learning (artificial intelligence); regressio

Fast concurrent object classification and localization - Tom Yeh; Lee,John J; Darrell,Trevor (CSAIL Technical Reports (July 1, 2003 - present), 2008)
Object localization and classification are important problems incomputer vision. However, in many applications, exhaustive searchover all class labels and image locations is computationallyprohibitive. While several methods have been proposed to makeeither classification or localization more efficient, few havedealt with both tasks simultaneously. This paper proposes anefficient method for concurrent object localization andclassification based on a data-dependent multi-classbranch-and-bound formalism. Existing bag-of-featuresclassification schemes, which can be expressed as weightedcombinations of feature counts can be readily adapted to ourmethod. We present experimental results that demonstrate the meritof our algorithm in terms of classification accuracy, localizationaccuracy, and speed, compared to baseline approaches includingexhaustive search, the ISM method, and single-class branch andbound.

Fast, easy, and cheap: Construction of statistical machine translation models with MapReduce - Dyer,C.; Cordova,A.; Mont,A.; Jimmy Lin (Proceedings of the Third Workshop on Statistical Machine Translation, 2008)
In recent years, the quantity of parallel train-ing data available for statistical machine trans- lation has increased far more rapidly than the performance of individual computers, re- sulting in a potentially serious impediment to progress. Parallelization of the model- building algorithms that process this data on computer clusters is fraught with challenges such as synchronization, data exchange, and fault tolerance. However, the MapReduce programming paradigm has recently emerged as one solution to these issues: a powerful functional abstraction hides system-level de- tails from the researcher, allowing programs to be transparently distributed across potentially very large clusters of commodity hardware. We describe MapReduce implementations of two algorithms used to estimate the parame- ters for two word alignment models and one phrase-based translation model, all of which rely on maximum likelihood probability esti- mates. On a 20-machine cluster, experimental results show that our solutions exhibit good scaling characteristics compared to a hypo- thetical, optimally-parallelized version of cur- rent state-of-the-art single-core tools.

Fast multipole accelerated boundary element method (FMBEM) for solution of 3D scattering problems - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2008)
Wideband FMBEM codes are challenging to implement since there are problems at both very low and high frequencies. Substantially different schemes for function representation and translation are efficient for low and high frequency ranges. We present a method which is suitable for solution both high and low frequency problems since it implements a switch between different representations and uses fast translation methods appropriate to each representation. For a high frequency problem the switch between representations may occur at some intermediate levels of hierarchical space subdivision of the FMM. We also present an FMM‐based preconditioner used in the flexible GMRES iterative solver for scattering problems and discuss example problems computed in range 0.001<kD<200, where k is the wave number and D is the size of the computational domain. The theoretical and experimental computational complexity of our algorithm is approximately O((kD)3) at large kD with relatively small asymptotic constant and the algorithm allows to solve problems with up to million nodes used for surface discretization in the range tested on a conventional personal computer.

Fast Multipole Accelerated Boundary Element Methods for the 3D Helmholtz Equation - Gumerov, Nail A.; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR-2008-03, 2008)
The development of a fast multipole method accelerated iterativesolution of the boundary element equations for large problems involving hundreds of thousands elements for the Helmholtz equations in 3D is described. The BEM requires several approximate computations (numerical quadrature, approximations of the boundary shapes using elements) and the convergence criterion for iterative computation. When accelerated using the FMM, 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 used, choices of representations, and boundary element integration consistent with these approximations are described. A novel preconditioner for accelerating convergence, using a low accuracy FMM accelerated solver as a right preconditioner is also described. Results of the developed and tested solvers for boundary value problems for the Helmholtz equations using the solver are presented for the number of unknowns N <= 106 and product of wavenumber k times domain size D, kD <= 200 and show good performance close to theoretical expectations.
Keywords: Technical Report

Fast multipole methods on graphics processors - Gumerov, Nail A.; Duraiswami, Ramani (Journal of Computational Physics, 2008)
The fast multipole method allows the rapid approximate evaluation of sums of radial basis functions. For a specified accuracy, ϵ , the method scales as O ( N ) in both time and memory compared to the direct method with complexity O ( N 2 ) , which allows the solution of larger problems with given resources. Graphical processing units (GPU) are now increasingly viewed as data parallel compute coprocessors that can provide significant computational performance at low price. We describe acceleration of the FMM using the data parallel GPU architecture.The FMM has a complex hierarchical (adaptive) structure, which is not easily implemented on data-parallel processors. We described strategies for parallelization of all components of the FMM, develop a model to explain the performance of the algorithm on the GPU architecture; and determined optimal settings for the FMM on the GPU. These optimal settings are different from those on usual CPUs. Some innovations in the FMM algorithm, including the use of modified stencils, real polynomial basis functions for the Laplace kernel, and decompositions of the translation operators, are also described. We obtained accelerations of the Laplace kernel FMM on a single NVIDIA GeForce 8800 GTX GPU in the range of 30–60 compared to a serial CPU FMM implementation. For a problem with a million sources, the summations involved are performed in approximately one second. This performance is equivalent to solving of the same problem at a 43 Teraflop rate if we use straightforward summation.

A Fault Model for Upgrades in Distributed Systems (CMU-PDL-08-115) - Tudor Dumitras; Kavulya, Soila; Narasimhan, Priya (Parallel Data Laboratory, 2008)

A Feature Generation Algorithm with Applications to Biological Sequence Classification - Dogan,R. I; Getoor, Lise; Wilbur,W. J (Computational Methods, 2008)

Flow Algorithms for Parallel Query Optimization - Deshpande, Amol; Hellerstein,L. (IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, 2008)
We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of ";interleaving"; plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a ";flow maximization problem";, and present polynomial-time algorithms that (statically) find the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.
Keywords: Casting; computational complexity; Cost function; Databases; Delay; distributed environment; Educational institutions; flow maximization algorithm; Interleaved codes; interoperator parallelism; minimisation; multiway join query response time minimization problem; parallel database; Parallel databases; parallel query optimization; Partitioning algorithms; pipeline processing; pipelined parallelism; polynomial-time algorithm; query planning problem; Query processing; Web service; Web services

A general method for sensor planning in multi-sensor systems: Extension to random occlusion - Mittal,A.; Davis, Larry S. (International Journal of Computer Vision, 2008)
ystems utilizing multiple sensors are required in many domains. In this paper, we specifically concern ourselves with applications where dynamic objects appear randomly and the system is employed to obtain some user-specified characteristics of such objects. For such systems, we deal with the tasks of determining measures for evaluating their performance and of determining good sensor configurations that would maximize such measures for better system performance.We introduce a constraint in sensor planning that has not been addressed earlier: visibility in the presence of random occluding objects. occlusion causes random loss of object capture from certain necessitates the use of other sensors that have visibility of this object. Two techniques are developed to analyze such visibility constraints: a probabilistic approach to determine “average” visibility rates and a deterministic approach to address worst-case scenarios. Apart from this constraint, other important constraints to be considered include image resolution, field of view, capture orientation, and algorithmic constraints such as stereo matching and background appearance. Integration of such constraints is performed via the development of a probabilistic framework that allows one to reason about different occlusion events and integrates different multi-view capture and visibility constraints in a natural way. Integration of the thus obtained capture quality measure across the region of interest yields a measure for the effectiveness of a sensor configuration and maximization of such measure yields sensor configurations that are best suited for a given scenario. The approach can be customized for use in many multi-sensor applications and our contribution is especially significant for those that involve randomly occurring objects capable of occluding each other. These include security systems for surveillance in public places, industrial automation and traffic monitoring. Several examples illustrate such versatility by application of our approach to a diverse set of different and sometimes multiple system objectives.

Generalizing Word Lattice Translation - Dyer,Christopher; Muresan,Smaranda; Resnik, Philip (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2008)
Word lattice decoding has proven useful in spoken language translation; we argue that it provides a compelling model for translation of text genres, as well. We extend lattice decoding to hierarchical phrase-based models, providing a unified treatment with phrase-based decoding by treating lattices as a case of weighted finite-state automata. In the process, we resolve a significant complication that lattice representations introduce in reordering models. Our experiments evaluating the approach demonstrate substantial gains for Chinese-English and Arabic-English translation.
Keywords: *MACHINE TRANSLATION; *STATISTICAL MACHINE TRANSLATION; *WORD LATTICE TRANSLATION; grammars; HIERARCHICAL PHRASE-BASED MODELS; linguistics; MODELS; STATISTICAL PROCESSES

Growth of the flickr social network - Mislove,Alan; Koppula,Hema Swetha; Gummadi,Krishna P.; Druschel,Peter; Bhattacharjee, Bobby (Proceedings of the first workshop on Online social networks, 2008)
Online social networking sites like MySpace, Orkut, and Flickr are among the most popular sites on the Web and continue to experience dramatic growth in their user population. The popularity of these sites offers a unique opportunity to study the dynamics of social networks at scale. Having a proper understanding of how online social networks grow can provide insights into the network structure, allow predictions of future growth, and enable simulation of systems on networks of arbitrary size. However, to date, most empirical studies have focused on static network snapshots rather than growth dynamics. In this paper, we collect and examine detailed growth data from the Flickr online social network, focusing on the ways in which new links are formed. Our study makes two contributions. First, we collect detailed data covering three months of growth, encompassing 950,143 new users and over 9.7 million new links, and we make this data available to the research community. Second, we use a first-principles approach to investigate the link formation process. In short, we find that links tend to be created by users who already have many links, that users tend to respond to incoming links by creating links back to the source, and that users link to other users who are already close in the network.
Keywords: growth; measurement; social networks

Handwritten Document Image Processing - Yefeng Zheng; David Doermann; Huiping Li (VDMVerlang Dr. Muller, 2008)

Hci for community and international development - Thomas, John; Dearden, Andy; Dray, Susan; Light, Ann; Best, Michael; Arkin, Nuray; Maunder, Andrew; Kam, Mathew; Marshini Chetty; Sambasivan, Nithya; Buckhalter, Celeste; Krishnan, Gaurishankar (SIGCHI EA '08, 2008)
This workshop explores the challenges in applying, extending and inventing appropriate methods and contributions of Human Computer Interaction (HCI) to International economic and community Development. We address interaction design for parts of the world that are often marginalized by the Global North as well as people in the Global North who are themselves similarly marginalized by poverty or other barriers. We hope to extend the boundaries of the field of Human Computer Interaction by spurring a discussion on how existing methods and practices can be adapted and modified, and how new practices can be developed, to deal with the unique challenges posed by these contexts.
Keywords: community design; ict4d; information and communication technology; international development; participatory design; ucd4id; User centered design

A hierarchical spatial index for triangulated surfaces - De Floriani, Leila; Facinoli,M.; Magillo,P.; Dimitri,D. (Int. Conf. on Computer Graphics Theory and Applications (GRAPP), 2008)
We present the PM2-Triangle quadtree (PM2T-quadtree), a new hierarchical spatial index for triangle mesheswhich has been designed for performing spatial queries on triangle-based terrain models. The PM2T-quadtree is based on a recursive space decomposition into square blocks. Here, we propose a highly compact data structure encoding a PM2T-quadtree, which decouples the spatial indexing structure from the combinatorial description of the mesh. We compare the PM2T-quadtree against other spatial indexes by considering the structure of the underlying domain subdivision, the storage costs of their data structures and the performance in geometric queries.

How to succeed in graduate school: a guide for students and advisors - desJardins, Marie (Crossroads, 2008)

Human detection using iterative feature selection and logistic principal component analysis - Abd-Almageed, Wael; Davis, Larry S. (Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on, 2008)
We present a fast feature selection algorithm suitable for object detection applications where the image being tested must be scanned repeatedly to detected the object of interest at different locations and scales. The algorithm iteratively estimates the belongness probability of image pixels to foreground of the image. To prove the validity of the algorithm, we apply it to a human detection problem. The edge map is filtered using a feature selection algorithm. The filtered edge map is then projected onto an eigen space of human shapes to determine if the image contains a human. Since the edge maps are binary in nature, Logistic Principal Component Analysis is used to obtain the eigen human shape space. Experimental results illustrate the accuracy of the human detector.
Keywords: algorithm; logistic; analysis; edge; analysis; probability; applications; principal; belongness; component; DETECTION; detection; feature; detection; iterative; detection; principal; extraction; filtering; feature; filtering; human; MAP; methods; object; PCA; object; probability; edge; selection; theory; iterative

Identification of Form Features in Non-Manifold Shapes Through a Decomposition Approach - De Floriani, Leila; Hui,Annie; Giannini,Franca (ASME Conference Proceedings, 2008)
In Computer-Aided Design (CAD), the idealization process reduces the complexity of the model of a solid object, thus resulting in a simplified representation which captures only the essential elements of its shape. Form features extraction is a relevant issue in order to recover semantic information from an idealized object model, since such information is typically lost during the idealization process. An idealized model is usually composed of non-manifold parts, whose topology carries significant structural information about the object shape. To this aim, we define form features for non-manifold object by extending the taxonomy of form features provided by STEP [19]. We describe an approach for the identification of features, which interact with non-manifold singularities in the object, based on a decomposition of a non-manifold object into nearly manifold components and on the properties of the graph representing such decomposition.

Imaging concert hall acoustics using visual and audio cameras - O'Donovan,A.; Duraiswami, Ramani; Zotkin,Dmitry N (IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, 2008)
Using a developed real time audio camera, that uses the output of a spherical microphone array beamformer steered in all directions to create central projection to create acoustic intensity images, we present a technique to measure the acoustics of rooms and halls. A panoramic mosaiced visual image of the space is also create. Since both the visual and the audio camera images are central projection, registration of the acquired audio and video images can be performed using standard computer vision techniques. We describe the technique, and apply it to the examine the relation between acoustical features and architectural details of the Dekelbaum concert hall at the Clarice Smith Performing Arts Center in College Park, MD.
Keywords: Acoustic imaging; acoustic intensity images; acoustic measurement; Acoustic measurements; Acoustic scattering; acoustic signal processing; acoustical camera; acoustical scene analysis; acquired audio registration; audio cameras; audio signal processing; CAMERAS; central projection; Computer vision; Educational institutions; HUMANS; image registration; Image segmentation; imaging concert hall acoustics; Layout; microphone arrays; panoramic mosaiced visual image; Raman scattering; reverberation; room acoustics; spherical microphone array beamformer; spherical microphone arrays; video image registration; visual cameras

A Java3D framework for inspecting and segmenting 3D models - De Floriani, Leila; Papaleo,Laura; Carissimi,Nicoló (Proceedings of the 13th international symposium on 3D web technology, 2008)
Models of 3D objects have become widely accessible in several disciplines within academia and industry, spanning from scientific visualization to entertainment. In the last few years, 3D models are often organized into digital libraries accessible over the network, and thus semantic annotation of such models becomes an important issue. A fundamental step in annotating a 3D model is to segment it into meaningful parts. In this work, we present a Java3D framework for inspecting and segmenting 3D objects represented in X3D format. In particular, we present a combination of segmentation and merging techniques for producing a feasible decomposition of the boundary of a 3D object. We represent such decomposition as a graph, that we call the segmentation graph which is the basis for semantic annotation. We describe also the interface we have developed to allow visualization and browsing of both the decomposition and the segmentation graph in order to understand the topological structure of the resulting decomposition.
Keywords: Java3D; object manipulation; Object segmentation; shape semantics; X3D

Kernel integral images: A framework for fast non-uniform filtering - Hussein,M.; Porikli, F.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Integral images are commonly used in computer vision and computer graphics applications. Evaluation of box filters via integral images can be performed in constant time, regardless of the filter size. Although Heckbert (1986) extended the integral image approach for more complex filters, its usage has been very limited, in practice. In this paper, we present an extension to integral images that allows for application of a wide class of non-uniform filters. Our approach is superior to Heckbertpsilas in terms of precision requirements and suitability for parallelization. We explain the theoretical basis of the approach and instantiate two concrete examples: filtering with bilinear interpolation, and filtering with approximated Gaussian weighting. Our experiments show the significant speedups we achieve, and the higher accuracy of our approach compared to Heckbertpsilas.
Keywords: approximated; equations; interpolation; filtering; bilinear; filtering; kernel; Gaussian; graphics; computer; images; approximation; integral; interpolation; computer; nonuniform; processing; integral; theory; filtering; theory; image; vision; fast; weighting

Language and translation model adaptation using comparable corpora - Snover,Matthew; Dorr, Bonnie J; Schwartz,Richard (Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008)
Traditionally, statistical machine translation systems have relied on parallel bi-lingual data to train a translation model. While bi-lingual parallel data are expensive to generate, monolingual data are relatively common. Yet monolingual data have been under-utilized, having been used primarily for training a language model in the target language. This paper describes a novel method for utilizing monolingual target data to improve the performance of a statistical machine translation system on news stories. The method exploits the existence of comparable text---multiple texts in the target language that discuss the same or similar stories as found in the source language document. For every source document that is to be translated, a large monolingual data set in the target language is searched for documents that might be comparable to the source documents. These documents are then used to adapt the MT system to increase the probability of generating texts that resemble the comparable document. Experimental results obtained by adapting both the language and translation models show substantial gains over the baseline system.

Learning Abstract Properties of Swarm Systems - Miner,D.; desJardins, Marie (Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, 2008)

Learning pairwise dissimilarity profiles for appearance recognition in visual surveillance - Lin,Z.; Davis, Larry S. (Advances in Visual Computing, 2008)
Training discriminative classifiers for a large number of classes is a challenging problem due to increased ambiguities between classes. In order to better handle the ambiguities and to improve the scalability of classifiers to larger number of categories, we learn pairwise dissimilarity profiles (functions of spatial location) between categories and adapt them into nearest neighbor classification. We introduce a dissimilarity distance measure and linearly or nonlinearly combine it with direct distances. We illustrate and demonstrate the approach mainly in the context of appearance-based person recognition.

LEARNING STRUCTURED BAYESIAN NETWORKS: COMBINING ABSTRACTION HIERARCHIES AND TREE‐STRUCTURED CONDITIONAL PROBABILITY TABLES - desJardins, Marie; Rathod,Priyang; Getoor, Lise (Computational Intelligence, 2008)
Context-specific independence representations, such as tree-structured conditional probability distributions, capture local independence relationships among the random variables in a Bayesian network (BN). Local independence relationships among the random variables can also be captured by using attribute-value hierarchies to find an appropriate abstraction level for the values used to describe the conditional probability distributions. Capturing this local structure is important because it reduces the number of parameters required to represent the distribution. This can lead to more robust parameter estimation and structure selection, more efficient inference algorithms, and more interpretable models. In this paper, we introduce Tree-Abstraction-Based Search (TABS), an approach for learning a data distribution by inducing the graph structure and parameters of a BN from training data. TABS combines tree structure and attribute-value hierarchies to compactly represent conditional probability tables. To construct the attribute-value hierarchies, we investigate two data-driven techniques: a global clustering method, which uses all of the training data to build the attribute-value hierarchies, and can be performed as a preprocessing step; and a local clustering method, which uses only the local network structure to learn attribute-value hierarchies. We present empirical results for three real-world domains, finding that (1) combining tree structure and attribute-value hierarchies improves the accuracy of generalization, while providing a significant reduction in the number of parameters in the learned networks, and (2) data-derived hierarchies perform as well or better than expert-provided hierarchies.
Keywords: abstraction hierarchies; background knowledge; Bayesian networks; clustering; machine learning; MDL

Learning Visual Shape Lexicon for Document Image Content Recognition - Zhu,Guangyu; Yu,Xiaodong; Li,Yi; David Doermann (The 10th European Conference on Computer Vision (ECCV 2008), 2008)
Developing effective content recognition methods for diverse imagery continues to challenge computer vision researchers. We present a new approach for document image content categorization using a lexicon of shape features. Each lexical word corresponds to a scale and rotation invariant shape feature that is generic enough to be detected repeatably and segmentation free. We learn a concise, structurally indexed shape lexicon from training by clustering and partitioning feature types through graph cuts. We demonstrate our approach on two challenging document image content recognition problems: 1) The classification of 4,500 Web images crawled from Google Image Search into three content categories — pure image, image with text, and document image, and 2) Language identification of 8 languages (Arabic, Chinese, English, Hindi, Japanese, Korean, Russian, and Thai) on a 1,512 complex document image database composed of mixed machine printed text and handwriting. Our approach is capable to handle high intra-class variability and shows results that exceed other state-of-the-art approaches, allowing it to be used as a content recognizer in image indexing and retrieval systems.

A Logic Framework for Sports Video Summarization Using Text-Based Semantic Annotation - Refaey,M.A.; Abd-Almageed, Wael; Davis, Larry S. (Semantic Media Adaptation and Personalization, 2008. SMAP '08. Third International Workshop on, 2008)
Detection of semantic events in sports videos is an essential step towards video summarization. A large volume of research has been conducted for automatic semantic event detection and summarization of sports videos. In this paper we present a novel sports video summarization framework using a combination of text, video and logic analysis. Parse trees are used to analyze structured and free-style text webcasting of sports games and extract the game¿s semantic events, such as goals and penalties in soccer games. Semantic events are then hierarchically arranged before being passed to a logic processing engine. The logic engine receives the summary preferences from the user and subsequently parses the event hierarchy to generate the game¿s summary according to the user¿s preferences. The proposed framework was applied to both soccer and basketball videos. We achieved an average accuracy of 98.6% and 100% on soccer and basketball videos, respectively.
Keywords: (mathematics); video; analysis; trees; annotation; Internet; broadcasting; sport; text; AUTOMATIC; detection; logic; engine; parse; event; PROCESSING; processing; semantic; signal; summarization; text; trees; sports; video; Webcasting; text-based

Measures and Risk Indicators for Early Insight into Software Safety. Development of Fault-Tolerant Systems - Basili, Victor R.; Marotta,Frank; Dangle,Kathleen; Esker,Linda; Rus,Ioana (ABERDEEN TEST CENTER MD, 2008)
Software contributes an ever-increasing level of functionality and control in today's systems. This increased use of software can dramatically increase the complexity and time needed to evaluate the safety of a system. Although the actual system safety cannot be verified during its development, measures can reveal early insights into potential safety problems and risks. An approach for developing early software safety measures is presented in this article. The approach and the example software measures presented are based on experience working with the safety engineering group on a large Department of Defense program.
Keywords: *SOFTWARE ENGINEERING; *SYSTEM SAFETY; COMPUTER PROGRAMMING AND SOFTWARE; fault tolerant computing; INDICATORS; measurement; REPRINTS; risk; SAFETY ENGINEERING

Measuring 1st order stretchwith a single filter - Bitsakos,K.; Domke, J.; Fermüller, Cornelia; Aloimonos, J. (IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, 2008)
We analytically develop a filter that is able to measure the 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.
Keywords: Cepstral analysis; Educational institutions; filter; filtering theory; Fourier transforms; Frequency domain analysis; Frequency estimation; Gabor filters; Image analysis; IMAGE PROCESSING; linear stretch measurement; local signal transformation measurement; Nonlinear filters; Phase estimation; Signal analysis; Speech processing

Method and System for Detecting and Responding to Attacking Networks - Dagon,David; Feamster, Nick; Lee,Weake; Edmonds,Robert; Lipton,Richard; Ramachandran,Anirudh (2008)
A system and method for detecting a first network of compromised computers in a second network of computers, comprising: collecting Domain Name System (DNS) data for the second network; examining the collected data relative to DNS data from known comprised and/or uncompromised computers in the second network; and determining the existence of the first network and/or the identity of compromised computers in the second network based on the examination.

Mobile Retriever: Access to Digital Documents from their Physical Source - Liu,Xu; David Doermann (International Journal on Document Analysis and Recognition, 2008)
In this paper, we describe an image based document retrieval system which runs on camera enabled mobile devices. “Mobile Retriever” aims to seamlessly link physical and digital documents by allowing users to snap a picture of the text of a document and retrieve its electronic version from a database. Experiments show that for a database of 100,093 pages, the correct document can be retrieved in less than 4 s at a success rate over 95%. Our system extracts token pairs from the text, to efficiently index and retrieve candidate pages using only a small portion of the image. We use token triplets that define the orientation of three corresponding tokens to effectively prune the false positives and identify the correct page to retrieve. We stress the importance of geometrical relationship between feature points and show its effectiveness in our camera based image retrieval system.

Modeling and visualization approaches for time-varying volumetric data - Weiss,K.; De Floriani, Leila (Advances in Visual Computing, 2008)
Time-varying volumetric data arise in a variety of application domains, and thus several techniques for dealing with such data have been proposed in the literature. A time-varying dataset is typically modeled either as a collection of discrete snapshots of volumetric data, or as a four-dimensional dataset. This choice influences the operations that can be efficiently performed on such data. Here, we classify the various approaches to modeling time-varying scalar fields, and briefly describe them. Since most models of time-varying data have been abstracted from well-known approaches to volumetric data, we review models of volumetric data as well as schemes to accelerate isosurface extraction and discuss how these approaches have been applied to time-varying datasets. Finally, we discuss multi-resolution approaches which allow interactive processing and visualization of large time varying datasets.

Modeling Transfer Relationships Between Learning Tasks for Improved Inductive Transfer - Eaton,Eric; desJardins, Marie; Lane,Terran (Machine Learning and Knowledge Discovery in DatabasesMachine Learning and Knowledge Discovery in Databases, 2008)
In this paper, we propose a novel graph-based method for knowledge transfer. We model the transfer relationships between source tasks by embedding the set of learned source models in a graph using transferability as the metric. Transfer to a new problem proceeds by mapping the problem into the graph, then learning a function on this graph that automatically determines the parameters to transfer to the new learning task. This method is analogous to inductive transfer along a manifold that captures the transfer relationships between the tasks. We demonstrate improved transfer performance using this method against existing approaches in several real-world domains.

Morphological analysis of terrains based on discrete curvature and distortion - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Magillo,Paola (Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008)
In order to characterize the morphology of a triangulated terrain, we define several discrete estimators that mimic mean and Gaussian curvatures in the discrete case. We start from concentrated curvature, a discrete notion of Gaussian curvature for polyhedral surfaces, defined by Troyanov [7]. Since concentrated curvature does not depend on the local geometric shape of the terrain, we introduce Ccurvature that allows us to obtain discrete counterparts of both Gaussian and mean curvature. Finally, we define distortion, which behaves as an approximation of mean curvature. We apply all such measures to the analysis of the morphology of triangulated terrains.
Keywords: curvature; Morphology; terrain modeling

Multimodal question answering for mobile devices - Tom Yeh; Darrell,Trevor (Proceedings of the 13th international conference on Intelligent user interfaces, 2008)
This paper introduces multimodal question answering, a new interface for community-based question answering services. By offering users an extra modality---photos---in addition to the text modality to formulate queries, multimodal question answering overcomes the limitations of text-only input methods when the users ask questions regarding visually distinctive objects. Such interface is especially useful when users become curious about an interesting object in the environment and want to know about it---simply by taking a photo and asking a question in a situated (from a mobile device) and intuitive (without describing the object in words) manner. We propose a system architecture for multimodal question answering, describe an algorithm for searching the database, and report on the findings of two prototype studies.
Keywords: Information retrieval; mobile application; pattern matching; Question answering

Multiple alternative sentence compressions and word-pair antonymy for automatic text summarization and recognizing textual entailment - Mohammad,S.; Dorr, Bonnie J; Egan,M.; Jimmy Lin; Zajic, David (Proceedings of the Text Analysis Conference (TAC-2008), Gaithersburg, MD, 2008)
The University of Maryland participatedin three tasks organized by the Text Anal- ysis Conference 2008 (TAC 2008): (1) the update task of text summarization; (2) the opinion task of text summariza- tion; and (3) recognizing textual entail- ment (RTE). At the heart of our summa- rization system is Trimmer, which gener- ates multiple alternative compressed ver- sions of the source sentences that act as candidate sentences for inclusion in the summary. For the first time, we investi- gated the use of automatically generated antonym pairs for both text summariza- tion and recognizing textual entailment. We used an antonymy feature in both the opinion summarization task and for rec- ognizing textual entailment. More coher- ent summaries resulted when using the antonymy feature as compared to when not using it. However, performance on ROUGE dropped. The RTE system per- formed almost equally well when using antonyms from WordNet and when using automatically generated antonyms.

Multi-resolution Tracking in Space and Time - Roy,S.D.; Tran,S.D.; Davis, Larry S.; Vikram,B.S. (Computer Vision, Graphics Image Processing, 2008. ICVGIP '08. Sixth Indian Conference on, 2008)
This paper proposes efficient and robust methods for tracking a moving object at multiple spatial and temporal resolution levels. The efficiency comes from optimising the amounts of spatial and temporal data processed. The robustness results from multi-level coarse-to-fine state-space searching. Tracking across resolution levels incurs an accuracy-versus-speed trade-off. For example, tracking at higher resolutions incurs greater processing cost, while maintaining higher accuracy in estimating the position of the moving object. We propose a novel spatial multi-scale tracker that tracks at the optimal accuracy-versus-speed operating point. Next, we relax this requirement to propose a multi-resolution tracker that operates at a minimum acceptable performance level. Finally, we extend these ideas to a multi-resolution spatio-temporal tracker. We show results of extensive experimentation in support of the proposed approaches.
Keywords: analysis; image; coarse-to-fine; detection; estimation; spatial; MOTION; moving; multiscale; object; resolution; object; searching; multiresolution; state-space; tracker; image; tracker; spatio-temporal; tracking; multilevel; tracking; position

Multi-Scale 3D Morse Complexes - Comic,L.; De Floriani, Leila (Computational Sciences and Its Applications, 2008. ICCSA '08. International Conference on, 2008)
Morse theory studies the relationship between the topology of a manifold M and the critical points of a scalar function f defined over M. Morse and Morse-Smale complexes, defined by critical points and integral lines of f, induce a subdivision of M into regions of uniform gradient flow, representing the morphology of M in a compact way. Function f can be simplified by canceling its critical points in pairs, thus simplifying the morphological representation of M, given by Morse and Morse-Smale complexes of f. Here, we propose a compact representation for the two Morse complexes in 3D, which is based on encoding the incidence relations of their cells, and on exploiting the duality among the complexes. We define cancellation operations, and their inverse expansion operations, on the Morse complexes and on their dual representation. We propose a multi-scale representation of the Morse complexes which provides a description of such complexes, and thus of the morphology of a 3D scalar field, at different levels of abstraction. This representation allows us also to perform selective refinement operations to extract description of the complexes which varies in different parts of the domain, thus improving efficiency on large data sets, and eliminating the noise in the data through topology simplification.
Keywords: (mathematics); inverse; 3D; analysis; duality; complexes; topology; data; computing; topology; critical; expansion; lines; inverse; morphology; mathematics; Morse; operations; morphology; multi-scale; points; duality; integral; problems; mathematical

Mutations in the Hydrophobic Core of Ubiquitin Differentially Affect Its Recognition by Receptor Proteins - Haririnia,Aydin; Verma,Rati; Purohit,Nisha; Twarog,Michael Z.; Deshaies,Raymond J.; Bolon,Dan; Fushman, David (Journal of Molecular Biology, 2008)
Ubiquitin (Ub) is one of the most highly conserved signaling proteins in eukaryotes. In carrying out its myriad functions, Ub conjugated to substrate proteins interacts with dozens of receptor proteins that link the Ub signal to various biological outcomes. Here we report mutations in conserved residues of Ub's hydrophobic core that have surprisingly potent and specific effects on molecular recognition. Mutant Ubs bind tightly to the Ub-associated domain of the receptor proteins Rad23 and hHR23A but fail to bind the Ub-interacting motif present in the receptors Rpn10 and S5a. Moreover, chains assembled on target substrates with mutant Ubs are unable to support substrate degradation by the proteasome in vitro or sustain viability of yeast cells. The mutations have relatively little effect on Ub's overall structure but reduce its rigidity and cause a slight displacement of the C-terminal β-sheet, thereby compromising association with Ub-interacting motif but not with Ub-associated domains. These studies emphasize an unexpected role for Ub's core in molecular recognition and suggest that the diversity of protein–protein interactions in which Ub engages placed enormous constraints on its evolvability.
Keywords: hydrophobic core mutation; molecular recognition; proteasomal degradation; ubiquitin; ubiquitin receptors

Name translation in statistical machine translation: Learning when to transliterate - Hermjakob,U.; Knight,K.; Daumé, Hal (Proceedings of ACL-08: HLT, 2008)

NASDAQ Velocity and Forces: An Interactive Visualization of Activity and Change - Dao,H.T.; Bazinet,A.; Berthier,R.; Shneiderman, Ben (Journal of Universal Computer Science, 2008)

Navigating information spaces: A case study of related article search in PubMed - Jimmy Lin; DiCuccio,Michael; Grigoryan,Vahan; Wilbur,W. John (Information Processing & Management, 2008)
The concept of an â€œinformation spaceâ€ provides a powerful metaphor for guiding the design of interactive retrieval systems. We present a case study of related article search, a browsing tool designed to help users navigate the information space defined by results of the PubMedÂ® search engine. This feature leverages content-similarity links that tie MEDLINEÂ® citations together in a vast document network. We examine the effectiveness of related article search from two perspectives: a topological analysis of networks generated from information needs represented in the TREC 2005 genomics track and a query log analysis of real PubMed users. Together, data suggest that related article search is a useful feature and that browsing related articles has become an integral part of how users interact with PubMed.
Keywords: Browsing; Interactive IR; MEDLINE; TREC genomics

Network-Aware Join Processing in Global-Scale Database Federations - Xiaodan Wang; Burns,R.; Terzis,A.; Deshpande, Amol (IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, 2008)
We introduce join scheduling algorithms that employ a balanced network utilization metric to optimize the use of all network paths in a global-scale database federation. This metric allows algorithms to exploit excess capacity in the network, while avoiding narrow, long-haul paths. We give a two- approximate, polynomial-time algorithm for serial (left-deep) join schedules. We also present extensions to this algorithm that explore parallel schedules, reduce resource usage, and define tradeoffs between computation and network utilization. We evaluate these techniques within the SkyQuery federation of Astronomy databases using spatial-join queries submitted by SkyQuery's users. Experiments show that our algorithms realize near-optimal network utilization with minor computational overhead.
Keywords: Astronomy; Computer networks; Concurrent computing; global-scale database federations; join scheduling algorithms; network utilization; network-aware join processing; parallel schedules; polynomial-time algorithm; Polynomials; Processor scheduling; Query processing; reduce resource usage; Scheduling algorithm; Spatial databases; spatial-join queries; Telecommunication traffic; Throughput

Nitric oxide production from surface recombination of oxygen and nitrogen atoms - Pejaković,D. A; Marschall,J.; Duan,L.; Martin, M.P (Journal of Thermophysics and Heat Transfer, 2008)

Online Filtering, Smoothing and Probabilistic Modeling of Streaming data - Kanagal,B.; Deshpande, Amol (IEEE 24th International Conference on Data Engineering, 2008. ICDE 2008, 2008)
In this paper, we address the problem of extending a relational database system to facilitate efficient real-time application of dynamic probabilistic models to streaming data. We use the recently proposed abstraction of model-based views for this purpose, by allowing users to declaratively specify the model to be applied, and by presenting the output of the models to the user as a probabilistic database view. We support declarative querying over such views using an extended version of SQL that allows for querying probabilistic data. Underneath we use particle filters, a class of sequential Monte Carlo algorithms, to represent the present and historical states of the model as sets of weighted samples (particles) that are kept up-to-date as new data arrives. We develop novel techniques to convert the queries on the model-based view directly into queries over particle tables, enabling highly efficient query processing. Finally, we present experimental evaluation of our prototype implementation over several synthetic and real datasets, that demonstrates the feasibility of online modeling of streaming data using our system and establishes the advantages of tight integration between dynamic probabilistic models and databases.
Keywords: Data analysis; data streaming; declarative query; dynamic probabilistic model; Filtering; Global Positioning System; hidden Markov models; Monitoring; Monte Carlo methods; Noise generators; Noise measurement; online filtering; particle filter; particle filtering (numerical methods); probabilistic database view; probability; Real time systems; real-time application; relational database system; Relational databases; sequential Monte Carlo algorithm; Smoothing methods; SQL

Optimal Cryptographic Hardness of Learning Monotone Functions - Dana Dachman-Soled; Lee, Homin K.; Malkin, Tal; Servedio, Rocco A.; Wan, Andrew; Wee, Hoeteck (Automata, Languages and Programming, 2008)
A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n‾‾√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS ’98). Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn; this result is close to optimal in terms of the circuit size parameter by known positive results as well (Servedio, Information and Computation ’04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS ’04).
Keywords: Data structures; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; Numeric Computing; Software Engineering/Programming and Operating Systems; Theory of computation

Photo-based question answering - Tom Yeh; Lee,John J; Darrell,Trevor (Proceedings of the 16th ACM international conference on Multimedia, 2008)
Photo-based question answering is a useful way of finding information about physical objects. Current question answering (QA) systems are text-based and can be difficult to use when a question involves an object with distinct visual features. A photo-based QA system allows direct use of a photo to refer to the object. We develop a three-layer system architecture for photo-based QA that brings together recent technical achievements in question answering and image matching. The first, template-based QA layer matches a query photo to online images and extracts structured data from multimedia databases to answer questions about the photo. To simplify image matching, it exploits the question text to filter images based on categories and keywords. The second, information retrieval QA layer searches an internal repository of resolved photo-based questions to retrieve relevant answers. The third, human-computation QA layer leverages community experts to handle the most difficult cases. A series of experiments performed on a pilot dataset of 30,000 images of books, movie DVD covers, grocery items, and landmarks demonstrate the technical feasibility of this architecture. We present three prototypes to show how photo-based QA can be built into an online album, a text-based QA, and a mobile application.
Keywords: Computer vision; Information retrieval; Question answering

A pose-invariant descriptor for human detection and segmentation - Lin,Z.; Davis, Larry S. (Computer Vision–ECCV 2008, 2008)
We present a learning-based, sliding window-style approach for the problem of detecting humans in still images. Instead of traditional concatenation-style image location-based feature encoding, a global descriptor more invariant to pose variation is introduced. Specifically, we propose a principled approach to learning and classifying human/non-human image patterns by simultaneously segmenting human shapes and poses, and extracting articulation-insensitive features. The shapes and poses are segmented by an efficient, probabilistic hierarchical part-template matching algorithm, and the features are collected in the context of poses by tracing around the estimated shape boundaries. Histograms of oriented gradients are used as a source of low-level features from which our pose-invariant descriptors are computed, and kernel SVMs are adopted as the test classifiers. We evaluate our detection and segmentation approach on two public pedestrian datasets.

Predictive Modeling-Based Data Collection in Wireless Sensor Networks - Wang,Lidan; Deshpande, Amol (Wireless Sensor NetworksWireless Sensor Networks, 2008)
We address the problem of designing practical, energy-efficient protocols for data collection in wireless sensor networks using predictive modeling. Prior work has suggested several approaches to capture and exploit the rich spatio-temporal correlations prevalent in WSNs during data collection. Although shown to be effective in reducing the data collection cost, those approaches use simplistic corelation models and further, ignore many idiosyncrasies of WSNs, in particular the broadcast nature of communication. Our proposed approach is based on approximating the joint probability distribution over the sensors using undirected graphical models , ideally suited to exploit both the spatial correlations and the broadcast nature of communication. We present algorithms for optimally using such a model for data collection under different communication models, and for identifying an appropriate model to use for a given sensor network. Experiments over synthetic and real-world datasets show that our approach significantly reduces the data collection cost.

The Randomized Coloring Procedure with Symmetry-Breaking - Pemmaraju,Sriram; Srinivasan, Aravind (Automata, Languages and ProgrammingAutomata, Languages and Programming, 2008)
A basic randomized coloring procedure has been used in probabilistic proofs to obtain remarkably strong results on graph coloring. These results include the asymptotic version of the List Coloring Conjecture due to Kahn, the extensions of Brooks’ Theorem to sparse graphs due to Kim and Johansson, and Luby’s fast parallel and distributed algorithms for graph coloring. The most challenging aspect of a typical probabilistic proof is showing adequate concentration bounds for key random variables. In this paper, we present a simple symmetry-breaking augmentation to the randomized coloring procedure that works well in conjunction with Azuma’s Martingale Inequality to easily yield the requisite concentration bounds. We use this approach to obtain a number of results in two areas: frugal coloring and weighted equitable coloring . A β-frugal coloring of a graph G is a proper vertex-coloring of G in which no color appears more than β times in any neighborhood. Let G = ( V , E ) be a vertex-weighted graph with weight function w : V →[0, 1] and let W = ∑ v ∈ V w ( v ). A weighted equitable coloring of G is a proper k -coloring such that the total weight of every color class is “large”, i.e., “not much smaller” than W / k ; this notion is useful in obtaining tail bounds for sums of dependent random variables.

Reciprocity between the cerebellum and the cerebral cortex: Nonlinear dynamics in microscopic modules for generating voluntary motor commands - Wang,Jun; Dam,Gregory; Yildirim,Sule; Rand, William; Wilensky,Uri; Houk,James C. (Complexity, 2008)
The cerebellum and basal ganglia are reciprocally connected with the cerebral cortex, forming many loops that function as distributed processing modules. Here we present a detailed model of one microscopic loop between the motor cortex and the cerebellum, and we show how small arrays of these microscopic loops (CB modules) can be used to generate biologically plausible motor commands for controlling movement. A fundamental feature of CB modules is the presence of positive feedback loops between the cerebellar nucleus and the motor cortex. We use nonlinear dynamics to model one microscopic loop and to investigate its bistable properties. Simulations demonstrate an ability to program a motor command well in advance of command generation and an ability to vary command duration. However, control of command intensity is minimal, which could interfere with the control of movement velocity. To assess these hypotheses, we use a minimal nonlinear model of the neuromuscular (NM) system that translates motor commands into actual movements. Simulations of the combined CB-NM modular model indicate that movement duration is readily controlled, whereas velocity is poorly controlled. We then explore how an array of eight CB-NM modules can be used to control the direction and endpoint of a planar movement. In actuality, thousands of such microscopic loops function together as an array of adjustable pattern generators for programming and regulating the composite motor commands that control limb movements. We discuss the biological plausibility and limitations of the model. We also discuss ways in which an agent-based representation can take advantage of the modularity in order to model this complex system. © 2008 Wiley Periodicals, Inc. Complexity, 2008
Keywords: agent‐based modeling; cerebellum; equilibrium point control; motor command; motor cortex; Movement; neural network; nonlinear dynamics

Resource allocation for tracking multiple targets using particle filters - Kembhavi,A.; Schwartz, W.R.; Davis, Larry S.; others (The Eighth International Workshop on Visual Surveillance, 2008)
Particle filters have been very widely used to track targets in video sequences. However, they suffer from an exponential rise in the number of particles needed to jointly track multiple targets. On the other hand, using multiple independent filters to track in crowded scenes often leads to erroneous results. We present a new particle filtering framework which uses an intelligent resource allocation scheme allowing us to track a large number of targets using a small set of particles. First, targets with overlapping posterior distributions and similar appearance models are clustered into interaction groups and tracked jointly, but independent of other targets in the scene. Second, different number of particles are allocated to different groups based on the following observations. Groups with higher associations (quantifying spatial proximity and pairwise appearance similarity) are given more particles. Groups with larger number of targets are given a larger number of particles. Finally, groups with ineffective proposal distributions are assigned more particles. Our experiments demonstrate the effectiveness of this framework over the commonly used joint particle filter with Markov Chain Monte Carlo (MCMC) sampling.

Re-Targetable OCR with Intelligent Character Segmentation - Agrawal,Mudit; David Doermann (DAS '08: Proceedings of the 2008 The Eighth IAPRInternational Workshop on Document Analysis Systems, 2008)
We have developed a font-model based intelligent character segmentation and recognition system. Using characteristics of structurally similar TrueType fonts, our system automatically builds a model to be used for the segmentation and recognition of the new script, independent of glyph composition. The key is a reliance on known font attributes. In our system three feature extraction methods are used to demonstrate the importance of appropriate features for classification. The methods are tested on both Latin (English) and non-Latin (Khmer) scripts. Results show that the character-level recognition accuracy exceeds 92% for Khmer and 96% for English on degraded documents. This work is a step toward the recognition of scripts of low-density languages which typically do not warrant the development of commercial OCR, yet often have complete TrueType font descriptions.

Review of Classifier Combination Methods - Tulyakov,Sergey; Jaeger,Stefan; Govindaraju,Venu; David Doermann (Studies in Computational Intelligence: Machine Learning in Document Analysis and RecognitionStudies in Computational Intelligence: Machine Learning in Document Analysis and Recognition, 2008)
Classifier combination methods have proved to be an effective tool to increase the performance of pattern recognition applications. In this chapter we review and categorize major advancements in this field. Despite a significant number of publications describing successful classifier combination implementations, the theoretical basis is still missing and achieved improvements are inconsistent. By introducing different categories of classifier combinations in this review we attempt to put forward more specific directions for future theoretical research.We also introduce a retraining effect and effects of locality based training as important properties of classifier combinations. Such effects have significant influence on the performance of combinations, and their study is necessary for complete theoretical understanding of combination algorithms.

Scalable classifiers for Internet vision tasks - Tom Yeh; Lee,John J; Darrell,Trevor (Computer Vision and Pattern Recognition Workshops, 2008. CVPRW'08. IEEE Computer Society Conference on, 2008)
Object recognition systems designed for Internet applications typically need to adapt to userspsila needs in a flexible fashion and scale up to very large data sets. In this paper, we analyze the complexity of several multiclass SVM-based algorithms and highlight the computational bottleneck they suffer at test time: comparing the input image to every training image. We propose an algorithm that overcomes this bottleneck; it offers not only the efficiency of a simple nearest-neighbor classifier, by voting on class labels based on the k nearest neighbors quickly determined by a vocabulary tree, but also the recognition accuracy comparable to that of a complex SVM classifier, by incorporating SVM parameters into the voting scores incrementally accumulated from individual image features. Empirical results demonstrate that adjusting votes by relevant support vector weights can improve the recognition accuracy of a nearest-neighbor classifier without sacrificing speed. Compared to existing methods, our algorithm achieves a ten-fold speed increase while incurring an acceptable accuracy loss that can be easily offset by showing about two more labels in the result. The speed, scalability, and adaptability of our algorithm makes it suitable for Internet vision applications.

Script-Independent Text Line Segmentation in Freestyle Handwritten Documents - Yi,L.; Zheng,Y.; David Doermann; Jaeger,S. (IEEETransactions on Pattern Analysis and Machine Intelligence, 2008)
Text line segmentation in freestyle handwritten documents remains an open document analysis problem. Curvilinear text lines and small gaps between neighboring text lines present a challenge to algorithms developed for machine printed or hand-printed documents. In this paper, we propose a novel approach based on density estimation and a state-of-the-art image segmentation technique, the level set method. From an input document image, we estimate a probability map, where each element represents the probability of the underlying pixel belonging to a text line. The level set method is then exploited to determine the boundary of neighboring text lines by evolving an initial estimate. Unlike connected component based methods ( [1] and [2] for example), the proposed algorithm does not use any script-specific knowledge. Extensive quantitative experiments on freestyle handwritten documents with diverse scripts, such as Arabic, Chinese, Korean, and Hindi in the University of Maryland Multilingual database, demonstrate that our algorithm consistently outperforms previous methods [1]–[3]. Further experiments show the proposed algorithm is robust to scale change, rotation, and noise.

Sequence diversity and evolution of multigene families in Trypanosoma cruzi - Cerqueira,Gustavo C.; Bartholomeu,Daniella C.; DaRocha,Wanderson D.; Hou,Lihua; Freitas-Silva,Danielle M.; Machado,Carlos Renato; El‐Sayed, Najib M.; Teixeira,Santuza M.R. (Molecular and Biochemical Parasitology, 2008)
Several copies of genes belonging to three multigene families present in the genome of Trypanosoma cruzi were sequenced and comparatively analyzed across six different strains of the parasite belonging to the T. cruzi I lineage (Colombiana, Silvio X10 and Dm28c), the T. cruzi II lineage (Esmeraldo and JG) and a hybrid strain (CL Brener). For all three gene families analyzed, our results support the division in T. cruzi I and II lineages. Furthermore, in agreement with its hybrid nature, sequences derived from the CL Brener clone clustered together with T. cruzi II sequences as well as with a third group of sequences. Paralogous sequences encoding Amastin, an amastigote surface glycoprotein and TcAG48, an antigenic RNA binding protein, which are clustered in the parasite genome, present higher intragenomic variability in T. cruzi II and CL Brener strains, when compared to T. cruzi I strains. Paralogous sequences derived from the TcADC gene family, which encode various isoforms of adenylyl cyclases and are dispersed throughout the T. cruzi genome, exhibit similar degree of variability in all strains, except in the CL Brener strain, in which the sequences were more divergent. Several factors including mutation rates and gene conversion mechanisms, acting differently within the T. cruzi population, may contribute to create such distinct levels of sequence diversity in multigene families that are clustered in the T. cruzi genome.
Keywords: Amastin; Gene conversion; Genetic diversity; Multigene families; Trypanosoma cruzi

Sequential Kernel Density Approximation and Its Application to Real-Time Visual Tracking - Han,Bohyung; Comaniciu, D.; Zhu,Ying; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2008)
Visual features are commonly modeled with probability density functions in computer vision problems, but current methods such as a mixture of Gaussians and kernel density estimation suffer from either the lack of flexibility by fixing or limiting the number of Gaussian components in the mixture or large memory requirement by maintaining a nonparametric representation of the density. These problems are aggravated in real-time computer vision applications since density functions are required to be updated as new data becomes available. We present a novel kernel density approximation technique based on the mean-shift mode finding algorithm and describe an efficient method to sequentially propagate the density modes over time. Although the proposed density representation is memory efficient, which is typical for mixture densities, it inherits the flexibility of nonparametric methods by allowing the number of components to be variable. The accuracy and compactness of the sequential kernel density approximation technique is illustrated by both simulations and experiments. Sequential kernel density approximation is applied to online target appearance modeling for visual tracking, and its performance is demonstrated on a variety of videos.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Statistical Distributions; Subtraction Technique; Computer-Assisted; Models; Gaussian estimation; kernel density estimation; mean-shift mode finding algorithm; online target appearance modeling; probability density function; real-time computer vision application; real-time visual tracking; sequential kernel density approximation; visual f; Statistical; Motion; Pattern Recognition

Sex and Age Dimorphism of Myocardial Gene Expression in Nonischemic Human Heart Failure - Fermin,David R.; Barac,Ana; Lee,Sangjin; Polster,Sean P.; Hannenhalli, Sridhar; Bergemann,Tracy L.; Grindle,Suzanne; Dyke,David B.; Pagani,Francis; Miller,Leslie W.; Tan,Sarah; dos Remedios,Cris; et al. (Circulation: Cardiovascular Genetics, 2008)
Background— We report the first comprehensive analysis of gene expression differences by sex and age in left ventricular samples from 102 patients with dilated cardiomyopathy.Methods and Results— Gene expression data (HG-U133A gene chip, Affymetrix) were analyzed from 30 females and 72 males from 3 separate centers. More than 1800 genes displayed sexual dimorphism in the heart (adjusted P value <0.05). A significant number of these genes were highly represented in gene ontology pathways involved in ion transport and G-protein-coupled receptor signaling. Localization of these genes revealed enrichment on both the sex chromosomes as well as chromosomes 3, 4, and 14. The second goal of this study was to determine the effect of age on gene expression. Within the female cohort, >140 genes were differentially expressed in the <55 years age group compared with the >55 years age group. These genes were highly represented in gene ontology pathways involved in DNA damage. In contrast, zero genes in the male cohort <55 years met statistical significance when compared with the >55 years age group.Conclusions— Gene expression in dilated cardiomyopathy displayed evidence of sexual dimorphism similar to other somatic tissues and age dimorphism within the female cohort.

Shape Analysis and Structuring - De Floriani, Leila; Spagnuolo,Michela (Springer, 2008)
With a lot of recent developments in the field, this much-needed book has come at just the right time. It covers a variety of topics related to preserving and enhancing shape information at a geometric level. The contributors also cover subjects that are relevant to effectively capturing the structure of a shape by identifying relevant shape components and their mutual relationships.
Keywords: Computer Graphics; Computer vision; Computers / Computer Graphics; Computers / Image Processing; Geometrical models; Geometry; Geometry, Analytic; Image analysis; IMAGE PROCESSING; Mathematics / Functional Analysis; Mathematics / Geometry / General; Mathematics / Graphic Methods; Mathematics / Mathematical Analysis; shapes; Technology & Engineering / Engineering (General); Visualization

A “Shape Aware” Model for semi-supervised Learning of Objects and its Context - Gupta,A.; Shi,J.; Davis, Larry S. (Proc. of NIPS, 2008)
We present an approach that combines bag-of-words and spatial models to performsemantic and syntactic analysis for recognition of an object based on its internal appearance and its context. We argue that while object recognition requires mod- eling relative spatial locations of image features within the object, a bag-of-word is sufficient for representing context. Learning such a model from weakly labeled data involves labeling of features into two classes: foreground(object) or “infor- mative” background(context). We present a “shape-aware” model which utilizes contour information for efficient and accurate labeling of features in the image. Our approach iterates between an MCMC-based labeling and contour based la- beling of features to integrate co-occurrence of features and shape similarity.

Signature-based Document Image Retrieval - Zhu,Guangyu; Yefeng Zheng; David Doermann (The 10th European Conference on Computer Vision (ECCV 2008), 2008)
As the most pervasive method 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. In this work, we developed a fully automatic signature-based document image retrieval system that handles: 1) Automatic detection and segmentation of signatures from document images and 2) Translation, scale, and rotation invariant signature matching for document image retrieval. We treat signature retrieval in the unconstrained setting of non-rigid shape matching and retrieval, and quantitatively study shape representations, shape matching algorithms, measures of dissimilarity, and the use of multiple query instances in document image retrieval. Extensive experiments using large real world collections of English and Arabic machine printed and handwritten documents demonstrate the excellent performance of our system. To the best of our knowledge, this is the first automatic retrieval system for general document images by using signatures as queries, without manual annotation of the image collection.

Single-document and multi-document summarization techniques for email threads using sentence compression - Zajic, David; Dorr, Bonnie J; Jimmy Lin (Information Processing & Management, 2008)
We present two approaches to email thread summarization: collective message summarization (CMS) applies a multi-document summarization approach, while individual message summarization (IMS) treats the problem as a sequence of single-document summarization tasks. Both approaches are implemented in our general framework driven by sentence compression. Instead of a purely extractive approach, we employ linguistic and statistical methods to generate multiple compressions, and then select from those candidates to produce a final summary. We demonstrate these ideas on the Enron email collection – a very challenging corpus because of the highly technical language. Experimental results point to two findings: that CMS represents a better approach to email thread summarization, and that current sentence compression techniques do not improve summarization performance in this genre.
Keywords: Email summarization; Enron; Informal media; Sentence compression; Trimming

Sound field decomposition using spherical microphone arrays - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE International Conference on Acoustics, Speech and Signal Processing, 2008. ICASSP 2008, 2008)
Spherical 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. Such ability is necessary in applications such as ambisonics and recreating auditory environment over headphones. We compare the performance of two scene reconstruction algorithms - one based on least-squares fitting the observed potentials and another based on computing the far-field signature function directly from the microphone measurements. 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.
Keywords: Acoustic applications; Acoustic arrays; Acoustic fields; acoustic position measurement; Acoustic propagation; acoustic signal processing; acoustic waves; array signal processing; Equations; far-field signature function; Layout; least-squares fitting; microphone arrays; scene reconstruction algorithms; Signal processing algorithms; sound field decomposition; spherical microphone arrays; Surface acoustic waves

Sparse terrain pyramids - Weiss,Kenneth; De Floriani, Leila (Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008)
Bintrees based on longest edge bisection and hierarchies of diamonds are popular multiresolution techniques on regularly sampled terrain datasets. In this work, we consider Sparse Terrain Pyramids as a compact multiresolution representation for terrain datasets whose samples are a subset of those lying on a regular grid. While previous diamond-based approaches can efficiently represent meshes built on a complete grid of resolution (2k +1)2, this is not suitable when the field values are uniform in large areas or simply non-existent. We explore properties of diamonds to simplify an encoding of the implicit dependency relationship between diamonds. Additionally, we introduce a diamond clustering technique to further reduce the geometric and topological overhead of such representations. We demonstrate the coherence of our clustering technique as well as the compactness of our representation.
Keywords: diamond hierarchies; longest edge bisection; multiresolution terrain models; nested triangle meshes

Spherical Arrays Near Boundaries - Duraiswami, Ramani; Gumerov, Nail A.; O'Donovan,A. (Hands-Free Speech Communication and Microphone Arrays, 2008. HSCMA 2008, 2008)
Summary form only given. Solid spherical microphone arrays are beginning to be used for purposes such as beamforming, sound field capture and as audio cameras. They rely on the scattering of sound off their surface to achieve their purpose. This behavior is significantly affected in the presence of boundaries (floors, walls, ceilings), and the edges and corners they form. Algorithms designed for array analysis in a free field will work erroneously in this situation. We describe adaptation of the spherical microphone analysis algorithms to constructively use the scattering off the boundaries to significantly improve array performance. We also assess the influence of walls on beamforming algorithms for regular spherical arrays. Both synthetic and experimental results are presented.
Keywords: analysis; audio; analysis; microphone; array; arrays; arrays; sound; arrays; spherical; cameras; beamforming; solid; capture; spherical; field; microphone; spherical

Spherical microphone array based immersive audio scene rendering - O’donovan,A.M.; Zotkin,Dmitry N; Duraiswami, Ramani (Proc. ICAD, 2008)
In many applications such as entertainment, education, mil-itary training, remote telepresence, surveillance, etc. it is necessary to capture an acoustic field and present it to listen- ers with a goal of creating the same acoustic perception for them as if they were actually present at the scene. Currently, there is much interest in the use of spherical microphone ar- rays for acoustic scene capture and reproduction. We de- scribe a 32-microphone spherical array based system im- plemented for spatial audio capture and reproduction. Our array embeds hardware that is traditionally external, such as preamplifiers, filters, digital-to-analog converters, and USB adaptor, resulting in a portable lightweight solution and re- quiring no hardware on the PC side whatsoever other than a high-speed USB port. We provide capability analysis of the array and describe software suite developed for the applica- tion.

A spherical microphone array based system for immersive audio scene rendering - O'donovan,Adam; Zotkin,Dmitry N; Duraiswami, Ramani (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2008)
For many applications it is necessary to capture an acoustic field and present it for human listeners, creating the same acoustic perception for them as if they were actually present in the scene. Possible applications of this technique include entertainment, education, military training, remote telepresence, surveillance, and others. Recently, there is much interest on the use of spherical microphone arrays in acoustic scene capture and reproduction application. We describe a 32-microphone spherical array based system implemented for spatial audio capture and reproduction. The array embeds hardware that is traditionally external, such as preamplifiers, filters, digital-to-analog converters, and USB interface adapter, resulting in a portable lightweight solution and requiring no hardware on PC side whatsoever other than a high-speed USB port. We provide capability analysis of the array and describe software suite developed for the application.
Keywords: Technical Report

Structural Sampling for Statistical Software Testing - Baskiotis,N.; Sebag,M.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)
Structural Statistical Software Testing exploits the control flow graph of the program being tested to construct test cases. While test cases can easily be extracted from {em feasible paths} in the control flow graph, that is, paths which are actually exerted for some values of the program input, the feasible path region is a tiny fraction of the graph paths (less than $10^{-5}]$ for medium size programs). The S4T algorithm presented in this paper aims to address this limitation; as an Active Relational Learning Algorithm, it uses the few feasible paths initially available to sample new feasible paths. The difficulty comes from the non-Markovian nature of the feasible path concept, due to the long-range dependencies between the nodes in the control flow graph. Experimental validation on real-world and artificial problems demonstrates significant improvements compared to the state of the art.

Structured machine learning: the next ten years - Dietterich,T. G; Domingos,P.; Getoor, Lise; Muggleton,S.; Tadepalli,P. (Machine Learning, 2008)
The field of inductive logic programming (ILP) has made steady progress, since the first ILP workshop in 1991, based on a balance of developments in theory, implementations and applications. More recently there has been an increased emphasis on Probabilistic ILP and the related fields of Statistical Relational Learning (SRL) and Structured Prediction. The goal of the current paper is to consider these emerging trends and chart out the strategic directions and open problems for the broader area of structured machine learning for the next 10 years.

The swarm application framework - Miner,D.; desJardins, Marie (In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (Student Abstract, 2008)
The Swarm Application Framework (SAF) is a tool that makes the development of swarm applications more intuitive. Traditionally, swarm applications are created by programming several low-level rules. This approach leads to several problems in designing and testing swarms, which serve as inspiration for the features of SAF. SAF encourages a new paradigm for designing swarm applications: engineers can interact with a swarm at the abstract (swarm) level instead of the individual (agent) level. In this paper, we discuss the design of the framework, how agents and rules in SAF operate, and a planned rule abstraction feature.

TERp system description - Snover,M.; Madnani,N.; Dorr, Bonnie J; Schwartz,R. (MetricsMATR workshop at AMTA, 2008)
This paper describes TER-Plus (TERp) the University of Maryland / BBN Technologies submission for the NIST Metric MATR 2008 workshop on automatic machine translation evaluation metrics. TERp is an extension of Translation Edit Rate (TER) that builds off of the success of TER as an evaluation metric and alignment tool while addressing several of its weaknesses through the use of paraphrases, morphological stemming, and synonyms, as well as edit costs that are optimized to correlate better with various types of human judgments.

Towards Design and Fabrication of a Miniature MRI-Compatible Robot for Applications in Neurosurgery - Pappafotis,Nicholas; Bejgerowski,Wojciech; Gullapalli,Rao; Simard,J. Marc; Gupta, Satyandra K.; Desai,Jaydev P. (ASME, 2008)
Brain tumors are among the most feared complications of cancer and they occur in 20–40% of adult cancer patients. Despite numerous advances in treatment, the prognosis for these patients is poor, with a median survival of 4–8 months. The primary reasons for poor survival rate are the lack of good continuous imaging modality for intraoperative intracranial procedures and the inability to remove the complete tumor tissue due to its placement in the brain and the corresponding space constraints to reach it. Intraoperative magnetic resonance imaging (MRI) supplements the surgeon's visual and tactile senses in a way that no other imaging device can achieve resulting in less trauma to surrounding healthy brain tissue during surgery. To minimize the trauma to surrounding healthy brain tissue, it would be beneficial to operate through a narrow surgical corridor dissected by the neurosurgeon. Facilitating tumor removal by accessing regions outside the direct “line-of-sight” of the neurosurgical corridor will require a highly dexterous, small cross section, and MRI-compatible robot. Developing such a robot is extremely challenging task. In this paper we report a preliminary design of 6-DOF robot for possible application in neurosurgery. The robot actuators and body parts are constructed from MRI compatible materials. The current prototype is 0.36” in diameter and weighs only 0.0289 N (2.95 grams). The device was actuated using Flexinol® which is a shape memory alloy manufactured by Dynalloy, Inc. The end-effector forces ranged from 12 mN to 50 mN depending on the robot configuration. The end-effector force to robot weight ratio varied from 0.41 to 1.73. During trials the robot motion was repeatable and the range of motion of the robot was about 90 degrees for the end-effector when one side shape memory alloy (SMA) channel was actuated. The actuation time from the start to finish was about 2.5 s.

Tracking Down Under: Following the Satin Bowerbird - Kembhavi,A.; Farrell,R.; Luo,Yuancheng; Jacobs, David W.; Duraiswami, Ramani; Davis, Larry S. (Applications of Computer Vision, 2008. WACV 2008. IEEE Workshop on, 2008)
Socio biologists collect huge volumes of video to study animal behavior (our collaborators work with 30,000 hours of video). The scale of these datasets demands the development of automated video analysis tools. Detecting and tracking animals is a critical first step in this process. However, off-the-shelf methods prove incapable of handling videos characterized by poor quality, drastic illumination changes, non-stationary scenery and foreground objects that become motionless for long stretches of time. We improve on existing approaches by taking advantage of specific aspects of this problem: by using information from the entire video we are able to find animals that become motionless for long intervals of time; we make robust decisions based on regional features; for different parts of the image, we tailor the selection of model features, choosing the features most helpful in differentiating the target animal from the background in that part of the image. We evaluate our method, achieving almost 83% tracking accuracy on a more than 200,000 frame dataset of Satin Bowerbird courtship videos.
Keywords: analysis; behavior; animal; Bowerbird; animal; computing; feature; detection; animal; extraction; tracking; video; processing; zoology; Satin; sciences; selection; behavioural; signal; tool; feature; tracking; automated; video

UMD_VDT, an Integration of Detection and Tracking Methods for Multiple Human Tracking - Tran,S.; Lin,Z.; Harwood,D.; Davis, Larry S. (Multimodal Technologies for Perception of Humans, 2008)
This paper presents a cooperative body part labeling and tracking algorithm for locating body parts in a videoimage sequence. The body part labeling procedure is used to initialize the tracking procedure and to prevent tracking from getting lost; and the tracking procedure is used to analyze frames that cannot be handled reliably by the labeling procedure. This results in an automatic and robust body part tracking system. Unlike previous work that always start tracking from the first frame which may be difficult to analyze, our tracking procedure starts with some key frames in which body parts can be located reliably. Key frames are selected based on a labeling confidence measure which evaluates the similarity between the human model and the image features. The labeled body parts are tracked in-between frames based on such cues as shape, color, and location interpolated between key frames iteratively. The proposed algorithm has been applied to analyze NASA videotapes in which crew members present challenging postures of bending, twisting, and rotating in a space station. The experimental results demonstrate the effectiveness of the proposed algorithm.

Unconstrained Language Identification Using AShape Codebook - Zhu,Guangyu; Yu,Xiaodong; Li,Yi; David Doermann (The 11th International Conference on Frontiers in Handwritting Recognition (ICFHR 2008), 2008)
We propose a novel approach to language identification in document images containing handwriting 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 characteristic shape feature that is generic enough to appear repeatably. We learn a concise, structurally indexed shape codebook from training data by clustering similar features and partitioning the feature space by graph cuts. Our approach is segmentation free and easily extensible. We quantitatively evaluate our approach using a large real-world document image collection, which consists of more than 1,500 documents in 8 languages (Arabic, Chinese, English, Hindi, Japanese, Korean, Russian, and Thai) and contains a complex mixture of handwritten and machine printed content. Experimental results demonstrate the robustness and flexibility of our approach, and show exceptional language identification performance that exceeds the state of art.

Validation of a DNS code for wall-bounded turbulence including finite-rate reactions and surface catalysis - Duan,L.; Martin, M.P (AIAA Paper 2008, 2008)
This paper discusses the constitutive relations, surface catalytic model,and numerical methods for direct numerical simulation (DNS) of wall- bounded turbulence including finite-rate chemistry and gas-surface in- teraction. The validation of the code is provided for the mean flow by comparison to similarity solutions and laminar hypersonic boundary layer solutions, for the surface catalysis by comparison to analytic solutions for the one-dimensional diffusion-reaction equation, and for turbulent bound- ary layers by comparison to empirical predictions.

Variational Bayes via Propositionalization - Sato,T.; Kameya,Y.; Kurihara,K.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)

VCode - Pervasive Data Transfer Using Video Barcode - Liu,Xu; David Doermann; Huiping Li (IEEETransactions on Multimedia, 2008)
In this paper we describe a novel data transfer scheme that uses the camera in a smart phone as an alternative data channel. The data is encoded as a sequence of 2D barcode images, displayed on a flat panel display, acquired by the camera, and decoded in real time by the software embedded in device. The decoded data is written to a file. Compared with existing data channels, such as CDMA/GPRS, cables, Bluetooth, and Infrared, our method relies on visual communication and does not require special hardware or data plans. Users only need to point the camera at a monitor displaying the VCode to download. Technical challenges to overcome include correction of perspective distortion, compensation for contrast variation, and efficient implementation of small footprint software into a mobile device. We address these challenges and present our solution in detail. We have implemented a prototype which allows users to download various types of files successfully, including pictures, ring tones and Java games onto camera phones running Symbian and Windows Mobile platforms. We discuss the limitations of our solution and outline future work to overcome these limitations.

Who killed the directed model? - Domke, Justin; Karapurkar, Alap; Aloimonos, J. (Computer Vision and Pattern Recognition, IEEE Computer Society Conference on, 2008)
Prior distributions are useful for robust low-level vision, and undirected models (e.g. Markov Random Fields) have become a central tool for this purpose. Though sometimes these priors can be specified by hand, this becomes difficult in large models, which has motivated learning these models from data. However, maximum likelihood learning of undirected models is extremely difficult- essentially all known methods require approximations and/or high computational cost. Conversely, directed models are essentially trivial to learn from data, but have not received much attention for low-level vision. We compare the two formalisms of directed and undirected models, and conclude that there is no a priori reason to believe one better represents low-level vision quantities. We formulate two simple directed priors, for natural images and stereo disparity, to empirically test if the undirected formalism is superior. We find in both cases that a simple directed model can achieve results similar to the best learnt undirected models with significant speedups in training time, suggesting that directed models are an attractive choice for tractable learning.

Adaptive query processing - Deshpande, Amol; Ives,Zachary; Vijayshankar Raman (Foundations and Trends in Databases, 2007)
As the data management field has diversified to consider settings in which queries are increasingly complex, statistics are less available, or data is stored remotely, there has been an acknowledgment that the traditional optimize-then-execute paradigm is insufficient. This has led to a plethora of new techniques, generally placed under the common banner of adaptive query processing, that focus on using runtime feed-back to modify query processing in a way that provides better response time or more efficient CPU utilization.In this survey paper, we identify many of the common issues, themes, and approaches that pervade this work, and the settings in which each piece of work is most appropriate. Our goal with this paper is to be a "value-add" over the existing papers on the material, providing not only a brief overview of each technique, but also a basic framework for understanding the field of adaptive query processing in general. We focus primarily on intra-query adaptivity of long-running, but not full-fledged streaming, queries. We conclude with a discussion of open research problems that are of high importance.

Adaptive query processing: why, how, when, what next? - Deshpande, Amol; Ives,Zachary; Vijayshankar Raman (Proceedings of the 33rd international conference on Very large data bases, 2007)
Adaptive query processing has been the subject of a great deal of recent work, particularly in emerging data management environments such as data integration and data streams. We provide an overview of the work in this area, identifying its common themes, laying out the space of query plans, and discussing open research problems. We discuss why adaptive query processing is needed, how it is being implemented, where it is most appropriately used, and finally, what next, i.e., open research problems.

Adaptive Vocabulary Forests br Dynamic Indexing and Category Learning - Tom Yeh; Lee,John; Darrell,Trevor (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Histogram pyramid representations computed from a vocabulary tree of visual words have proven valuable for a range of image indexing and recognition tasks; however, they have only used a single, fixed partition of feature space. We present a new efficient algorithm to incrementally compute set-of-trees (forest) vocabulary representations, and show that they improve recognition and indexing performance in methods which use histogram pyramids. Our algorithm incrementally adapts a vocabulary forest with an Inverted file system at the leaf nodes and automatically keeps existing histogram pyramid database entries up-to-date in a forward filesystem. It is possible not only to apply vocabulary tree indexing algorithms directly, but also to compute pyramid match kernel values efficiently. On dynamic recognition tasks where categories or objects under consideration may change over time, we show that adaptive vocabularies offer significant performance advantages in comparison to a single, fixed vocabulary.

Amino acid quantitative structure property relationship database: a web-based platform for quantitative investigations of amino acids - Lu,Yi; Bulka,Blazej; desJardins, Marie; Freeland,Stephen J (Protein Engineering Design and SelectionProtein Engineering, Design and Selection, 2007)
Here, we present the AA-QSPR Db (Amino Acid Quantitative Structure Property Relationship Database): a novel, freely available web-resource of data pertaining to amino acids, both engineered and naturally occurring. In addition to presenting fundamental molecular descriptors of size, charge and hydrophobicity, it also includes online visualization tools for users to perform instant, interactive analyses of amino acid sub-sets in which they are interested. The database has been designed with extensible markup language technology to provide a flexible structure, suitable for future development. In addition to providing easy access for queries by external computers, it also offers a user-friendly web-based interface that facilitates human interactions (submission, storage and retrieval of amino acid data) and an associated e-forum that encourages users to question and discuss current and future database contents.
Keywords: Amino acids; database; QSPR; XML

Answering Clinical Questions with Knowledge-Based and Statistical Techniques - Demner-Fushman,Dina; Jimmy Lin (Computational Linguistics, 2007)
The combination of recent developments in question-answering research and the availability of unparalleled resources developed specifically for automatic semantic processing of text in the medical domain provides a unique opportunity to explore complex question answering in the domain of clinical medicine. This article presents a system designed to satisfy the information needs of physicians practicing evidence-based medicine. We have developed a series of knowledge extractors, which employ a combination of knowledge-based and statistical techniques, for automatically identifying clinically relevant aspects of MEDLINE abstracts. These extracted elements serve as the input to an algorithm that scores the relevance of citations with respect to structured representations of information needs, in accordance with the principles of evidence-based medicine. Starting with an initial list of citations retrieved by PubMed, our system can bring relevant abstracts into higher ranking positions, and from these abstracts generate responses that directly answer physicians' questions. We describe three separate evaluations: one focused on the accuracy of the knowledge extractors, one conceptualized as a document reranking task, and finally, an evaluation of answers by two physicians. Experiments on a collection of real-world clinical questions show that our approach significantly outperforms the already competitive PubMed baseline.

Automatic Document Logo Detection - Zhu,Guangyu; David Doermann (The 9th International Conference on Document Analysis and Recognition (ICDAR 2007), 2007)
Automatic logo detection and recognition continues to be of great interest to the document retrieval community as it enables effective identification of the source of a document. In this paper, we propose a new approach to logo detection and extraction in document images that robustly classifiesand precisely localizes logos using a boosting strategy across multiple image scales. At a coarse scale, a trained Fisher classifier performs initial classification using features from document context and connected components. Each logo candidate region is further classified at successively finer scales by a cascade of simple classifiers, which allows false alarms to be discarded and the detected region to be refined. Our approach is segmentation free and layout independent. We define a meaningful evaluation metric to measure the quality of logo detection using labeled groundtruth. We demonstrate the effectiveness of our approach using a large collection of real-world documents.

A Bayesian model for discovering typological implications - Daumé, Hal; Campbell,L. (ANNUAL MEETING-ASSOCIATION FOR COMPUTATIONAL LINGUISTICS, 2007)

Bilattice-based Logical Reasoning for Human Detection - Shet,V. D; Neumann, J.; Ramesh,V.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
The capacity to robustly detect humans in video is a critical component of automated visual surveillance systems. This paper describes a bilattice based logical reasoning approach that exploits contextual information and knowledge about interactions between humans, and augments it with the output of different low level detectors for human detection. Detections from low level parts-based detectors are treated as logical facts and used to reason explicitly about the presence or absence of humans in the scene. Positive and negative information from different sources, as well as uncertainties from detections and logical rules, are integrated within the bilattice framework. This approach also generates proofs or justifications for each hypothesis it proposes. These justifications (or lack thereof) are further employed by the system to explain and validate, or reject potential hypotheses. This allows the system to explicitly reason about complex interactions between humans and handle occlusions. These proofs are also available to the end user as an explanation of why the system thinks a particular hypothesis is actually a human. We employ a boosted cascade of gradient histograms based detector to detect individual body parts. We have applied this framework to analyze the presence of humans in static images from different datasets.
Keywords: automated; detection; parts-based; detectors; static; histograms; human; images; formal; interactions; gradient; logic; image; logical; mechanisms; surveillance; video; processing; reasoning; complex; recognition; inference; signal; Surveillance; systems; bilattice-based; visual

Bridging art and science with creativity support tools - Shneiderman, Ben; Rita R Colwell; Diamond,Sara; Greenhalgh,Paul; Wulf,William (Proceedings of the 6th ACM SIGCHI conference on Creativity & cognition, 2007)

Characterizing RNA Secondary-Structure Features and Their Effects on Splice-Site Prediction - Dogan,R. I; Getoor, Lise; Wilbur,W. J (Data Mining Workshops, 2007. ICDM Workshops 2007. Seventh IEEE International Conference on, 2007)
RNA molecules are distinguished by their sequence composition and by their three-dimensional shape, called the secondary structure. The secondary structure of a pre-mRNA sequence may have a strong influence on gene splicing. In our previous work, we showed that a splice-site model employing sequence features built using our feature generation algorithm was very effective in predicting splice sites. The generated sequence features also contained biologically relevant features. In this paper, we extend the feature generation algorithm to construct secondary-structure features. These features capture the nucleotide pairing tendency in the splice-site neighborhood. We extend the splice-site model to include both pre-mRNA sequence and structure characteristics. The new model significantly outperforms the sequence-based features model. The identified secondary-structure features capture biologically relevant signals such as splicing silencers. We also found these signals to prefer specific regions around the splice-site neighborhood and we detail their preference.
Keywords: algorithm; gene; biophysics; molecular; composition; splice-site; compounds; sequences; computing; genetics; macromolecules; molecular; configurations; organic; features; feature; generation; model; splice-site; molecules; RNA; neighborhood; three-dimensional; pairing; RNA; secondary-structure; sequence; shape; biology; splicing; nucleotide; tendency; pre-mRNA

Children's interests and concerns when using the international children's digital library: a four-country case study - Druin, Allison; Weeks,A.; Massey,S.; Bederson, Benjamin B. (Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, 2007)

Classifying Computer Generated Charts - Prasad,V. S.N; Siddiquie,B.; Golbeck,J.; Davis, Larry S. (Content-Based Multimedia Indexing, 2007. CBMI '07. International Workshop on, 2007)
We present an approach for classifying images of charts based on the shape and spatial relationships of their primitives. Five categories are considered: bar-charts, curve-plots, pie-charts, scatter-plots and surface-plots. We introduce two novel features to represent the structural information based on (a) region segmentation and (b) curve saliency. The local shape is characterized using the Histograms of Oriented Gradients (HOG) and the Scale Invariant Feature Transform (SIFT) descriptors. Each image is represented by sets of feature vectors of each modality. The similarity between two images is measured by the overlap in the distribution of the features -measured using the Pyramid Match algorithm. A test image is classified based on its similarity with training images from the categories. The approach is tested with a database of images collected from the Internet.
Keywords: algorithm; scale; analysis; visual; classification; image; database; image; databases; feature; Internet; bar-chart; curve-plot; image; invariant; match; matching; image; relationship; surface-plot; Internet; image; representation; image; segmentation; pie-chart; pyramid; segmentation; statistical; transform; scatter-plot; spatial

Cofactor-independent phosphoglycerate mutase is an essential gene in procyclic form Trypanosoma brucei - Djikeng,A.; Raverdy,S.; Foster, Jeffrey S.; Bartholomeu,D.; Zhang,Y.; El‐Sayed, Najib M.; Carlow,C. (Parasitology research, 2007)

Combining outputs from multiple machine translation systems - Rosti,A.V.I.; Ayan,N.F.; Xiang,B.; Matsoukas,S.; Schwartz,R.; Dorr, Bonnie J (Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, 2007)
Currently there are several approaches tomachine translation (MT) based on differ- ent paradigms; e.g., phrasal, hierarchical and syntax-based. These three approaches yield similar translation accuracy despite using fairly different levels of linguistic knowledge. The availability of such a variety of systems has led to a growing interest toward finding better translations by combining outputs from multiple sys- tems. This paper describes three differ- ent approaches to MT system combina- tion. These combination methods oper- ate on sentence, phrase and word level exploiting information from N -best lists, system scores and target-to-source phrase alignments. The word-level combination provides the most robust gains but the best results on the development test sets (NIST MT05 and the newsgroup portion of GALE 2006 dry-run) were achieved by combining all three methods.

Configuration Reasoning and Ontology For Web - Dana Dachman-Soled; Sreedhar, V.C. (IEEE International Conference on Services Computing, 2007. SCC 2007, 2007)
Configuration plays a central role in the deployment and management of Web infrastructures and applications. A configuration often consists of assigning "values" to a pre-defined set of parameters defined in one or more files. Although the task of assigning values to (configuration) parameters looks simple, configuring infrastructures and applications is a very complex process. In this paper we present a framework for defining and analyzing configuration of an Apache server. We define the notion of "configuration space" of an Apache server as a set of possible values that can be assigned to configuration parameters. We then define the notion of an "obstacle" and "forbidden region" in the configuration space that should be avoided. We model configuration space using a logical framework based on OWL (Web ontology language). The obstacles and forbidden regions in the configuration space are modeled as constraints in the logical framework. These obstacles and forbidden regions are essentially "anti-patterns" that a typical installation should avoid. Given an instance of a configuration (that is, a "point" in the configuration space) we then check if the instance is "obstacle free" using logical reasoning.
Keywords: Apache server; Application software; configuration management; configuration reasoning; configuration space; File servers; Information security; Internet; knowledge representation languages; logical framework; logical reasoning; ontologies; ontologies (artificial intelligence); Orbital robotics; OWL; path planning; Robot kinematics; Runtime environment; Taxonomy; Web infrastructures management; Web ontology language; Web server

COST: An Approach for Camera Selection and Multi-Object Inference Ordering in Dynamic Scenes - Gupta,Abhinav; Mittal,Anurag; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Development of multiple camera based vision systems for analysis of dynamic objects such as humans is challenging due to occlusions and similarity in the appearance of a person with the background and other people- visual "confusion". Since occlusion and confusion depends on the presence of other people in the scene, it leads to a dependency structure where there are often loops in the resulting Bayesian network. While approaches such as loopy belief propagation can be used for inference, they are computationally expensive and convergence is not guaranteed in many situations. We present a unified approach, COST, that reasons about such dependencies and yields an order for the inference of each person in a group of people and a set of cameras to be used for inferences for a person. Using the probabilistic distribution of the positions and appearances of people, COST performs visibility and confusion analysis for each part of each person and computes the amount of information that can be computed with and without more accurate estimation of the positions of other people. We present an optimization problem to select set of cameras and inference dependencies for each person which attempts to minimize the computational cost under given performance constraints. Results show the efficiency of COST in improving the performance of such systems and reducing the computational resources required.

On the Cost of Persistence and Authentication in Skip Lists - Goodrich, Michael T.; Charalampos Papamanthou; Tamassia, Roberto (Experimental Algorithms, 2007)
We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging, as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them in various applications.
Keywords: Algorithm Analysis and Problem Complexity; algorithms; Computer Graphics; Data structures; Discrete Mathematics in Computer Science; Numeric Computing

Data Clustering with a Relational Push-Pull Model - Anthony,Adam; desJardins, Marie (Data Mining Workshops, 2007. ICDM Workshops 2007. Seventh IEEE International Conference on, 2007)
We present a new generative model for relational data in which relations between objects can have ei- ther a binding or a separating effect. For example, in a group of students separated into gender clusters, a "dating" relation would appear most frequently between the clusters, but a "roommate" relation would appear more often within clusters. In visualizing these rela- tions, one can imagine that the "dating" relation effec- tively pushes clusters apart, while the "roommate" re- lation pulls clusters into tighter formations. A unique aspect of the model is that an edge's existence is depen- dent on both the clusters to which the two connected objects belong and the features of the connected objects. We use simulated annealing to search for optimal val- ues of the unknown model parameters, where the ob- jective function is a Bayesian score derived from the generative model. Results describing the performance of the model are shown with artificial data as well as a subset of the Internet Movie Database. The results show that discovering a relation's tendency to either push or pull is critical to discovering a consistent clustering.

Data Management in the Worldwide Sensor Web - Balazinska,Magdalena; Deshpande, Amol; Franklin,Michael J.; Gibbons,Phillip B.; Gray,Jim; Hansen,Mark; Liebhold,Michael; Nath,Suman; Szalay,Alexander; Tao,Vincent (IEEE Pervasive Computing, 2007)
Advances in hardware and miniaturization technologies have led to a rapid increase in the number of large-scale sensor network deployments around the world, bringing us closer to the vision of a worldwide sensor web. Exploiting the sensor web to its full potential, however, raises several hard data management challenges. Addressing these challenges requires a concerted multidisciplinary effort encompassing many computer science fields. This article outlines some of the key data management challenges of a worldwide sensor web. It also presents recent advances in data management research that aim to address these challenges. Hopefully, the scientific, ubiquitous computing, and sensor network communities will adopt some of these solutions for managing their data. The article also attempts to bring many of the remaining open issues to the attention of the database community. This article is part of a special issue on Building a Sensor-Rich World.
Keywords: data modeling; data streams; data uncertainty; distributed systems; interoperability; sensor networks

Discovering interesting usage patterns in text collections: integrating text mining with visualization - Don,Anthony; Zheleva,Elena; Gregory,Machon; Tarkan,Sureyya; Auvil,Loretta; Clement,Tanya; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007)
This paper addresses the problem of making text mining results more comprehensible to humanities scholars, journalists, intelligence analysts, and other researchers, in order to support the analysis of text collections. Our system, FeatureLens1, visualizes a text collection at several levels of granularity and enables users to explore interesting text patterns. The current implementation focuses on frequent itemsets of n-grams, as they capture the repetition of exact or similar expressions in the collection. Users can find meaningful co-occurrences of text patterns by visualizing them within and across documents in the collection. This also permits users to identify the temporal evolution of usage such as increasing, decreasing or sudden appearance of text patterns. The interface could be used to explore other text features as well. Initial studies suggest that FeatureLens helped a literary scholar and 8 users generate new hypotheses and interesting insights using 2 text collections.
Keywords: digital humanities; frequent closed itemsets; n-grams; text mining; user interface

Distribution-Free Testing Lower Bounds for Basic Boolean Functions - Dana Dachman-Soled; Servedio, Rocco A. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2007)
In the distribution-free property testing model, the distance between functions is measured with respect to an arbitrary and unknown probability distribution \mathcal{D} over the input domain. We consider distribution-free testing of several basic Boolean function classes over {0,1} n , namely monotone conjunctions, general conjunctions, decision lists, and linear threshold functions. We prove that for each of these function classes, Ω((n/logn)1/5) oracle calls are required for any distribution-free testing algorithm. Since each of these function classes is known to be distribution-free properly learnable (and hence testable) using Θ(n) oracle calls, our lower bounds are within a polynomial factor of the best possible.
Keywords: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing

Document Image Mosaicing with Mobile Phones - Hannuksela,J.; Sangi,P.; Heikkila,J.; Liu,X.; David Doermann (International Conference on Image Analysis and Processing (ICIAP'07), 2007)
This paper presents a novel user interaction oncept for document image scanning with mobile phones. A high resolution mosaic image is constructed in two main stages. Firstly, online camera motion estimation is applied on the phone to assist the user to capture small image batches of the document page. Automatic image stitching process with a help of estimated device motion is carried out to reconstruct the full view of the document. Experiments on document images captured and processed with the mosaicing software clearly show the feasibility of the approach.

Draft Genome of the Filarial Nematode Parasite Brugia Malayi - Ghedin,Elodie; Wang,Shiliang; Spiro,David; Caler,Elisabet; Zhao,Qi; Crabtree,Jonathan; Allen,Jonathan E; Delcher,Arthur L.; Guiliano,David B; Miranda-Saavedra,Diego; Angiuoli,Samuel V; Creasy,Todd; et al. (Science, 2007)
Parasitic nematodes that cause elephantiasis and river blindness threaten hundreds of millions of people in the developing world. We have sequenced the ∼90 megabase (Mb) genome of the human filarial parasite Brugia malayi and predict ∼11,500 protein coding genes in 71 Mb of robustly assembled sequence. Comparative analysis with the free-living, model nematode Caenorhabditis elegans revealed that, despite these genes having maintained little conservation of local synteny during ∼350 million years of evolution, they largely remain in linkage on chromosomal units. More than 100 conserved operons were identified. Analysis of the predicted proteome provides evidence for adaptations of B. malayi to niches in its human and vector hosts and insights into the molecular basis of a mutualistic relationship with its Wolbachia endosymbiont. These findings offer a foundation for rational drug design.

An ease-of-use stereo-based particle filter for tracking under occlusion - Lim,S.N.; Davis, Larry S. (Human Motion–Understanding, Modeling, Capture and Animation, 2007)
We describe a tracker that handles occlusion by clustering foreground pixels based on their disparity values. Stereo-matched foreground pixels, mapped from multiple views to a reference view, allow the tracker to recover occluded foreground regions in the reference view. The stereo algorithm utilizes a common plan view into which foreground regions from multiple views are projected and intersected to construct polygons that contain the ground plane locations of objects, followed by constraining the epipolar search to only those pixels with ground plane locations lying within these polygons. Consequently, a stereo-matched foreground pixel is easily mapped between views by first mapping its ground plane location using pre-computed homography, followed by intersecting the vertical axis passing through the mapped location with the epipolar line. Finally, tracking in a reference view allows a particle filter to be “seamlessly” integrated, so that uncertainties can be effectively dealt with. Experimental results illustrate the effectiveness of our algorithm.

Ecotopia: An Ecological Framework for Change Management in Distributed Systems - Tudor Dumitras; Roşu, Daniela; Dan, Asit; Narasimhan, Priya (Architecting Dependable Systems IV, 2007)
Dynamic change management in an autonomic, service-oriented infrastructure is likely to disrupt the critical services delivered by the infrastructure. Furthermore, change management must accommodate complex real-world systems, where dependability and performance objectives are managed across multiple distributed service components and have specific criticality/value models. In this paper, we present Ecotopia, a framework for change management in complex service-oriented architectures (SOA) that is ecological in its intent: it schedules change operations with the goal of minimizing the service-delivery disruptions by accounting for their impact on the SOA environment. The change-planning functionality of Ecotopia is split between multiple objective-advisors and a system-level change-orchestrator component. The objective advisors assess the change-impact on service delivery by estimating the expected values of the Key Performance Indicators (KPIs), during and after change. The orchestrator uses the KPI estimations to assess the per-objective and overall business-value changes over a long time-horizon and to identify the scheduling plan that maximizes the overall business value. Ecotopia handles both external change requests, like software upgrades, and internal changes requests, like fault-recovery actions. We evaluate the Ecotopia framework using two realistic change-management scenarios in distributed enterprise systems.
Keywords: Autonomic Computing; Dynamic Change Management; Fault-Tolerant Architecture; Operating systems; Performability; Service Orchestration; software engineering

Effects of cyclization on conformational dynamics and binding properties of Lys48-linked di-ubiquitin - Dickinson,Bryan C.; Varadan,Ranjani; Fushman, David (Protein Science, 2007)
In solution, Lys48-linked di-ubiquitin exists in dynamic equilibrium between closed and open conformations. To understand the effect of interdomain motion in polyubiquitin chains on their ability to bind ligands, we cyclized di-ubiquitin by cross-linking the free C terminus of the proximal ubiquitin with the side chain of residue 48 in the distal ubiquitin, using a chemical cross-linker, 1,6-Hexane-bis-vinylsulfone. Our NMR studies confirm that the cyclization affects conformational dynamics in di-ubiquitin by restricting opening of the interface and shifting the conformational equilibrium toward closed conformations. The cyclization, however, did not rigidly lock di-ubiquitin in a single closed conformation: The chain undergoes slow exchange between at least two closed conformations, characterized by interdomain contacts involving the same hydrophobic patch residues (Leu8-Ile44-Val70) as in the uncyclized di-ubiquitin. Lowering the pH changes the relative populations of these conformations, but in contrast with the uncyclized di-ubiquitin, does not lead to opening of the interface. This restriction of domain motions inhibits direct access of protein molecules to the hydrophobic patch residues located at the very center of the interdomain interface in di-ubiquitin, although the residual motions are sufficient to allow access of small molecules to the interface. This renders di-ubiquitin unable to bind protein molecules (e.g., UBA2 domain) in the normal manner, and thus could interfere with Ub2 recognition by various downstream effectors. These results emphasize the importance of the opening/closing domain motions for the recognition and function of di-ubiquitin and possibly longer polyubiquitin chains.
Keywords: cyclization; di-ubiquitin; interdomain dynamics; Lys48-linked ubiquitin chain; UBA domain

Efficient Conversion of X.Y Surround Sound Content to Binaural Head-Tracked Form for HRTF-Enabled Playback - Zotkin,Dmitry N; Duraiswami, Ramani; Gumerov, Nail A. (IEEE International Conference on Acoustics, Speech and Signal Processing, 2007. ICASSP 2007, 2007)
Binaural presentation of X.Y sound is usually performed using virtual audio principles - that is, by attempting to virtually reproduce the setup of the X+Y loudspeakers in the reference room configuration. The computational cost of such playback is linear in the number of channels in the X.Y setup. We present a novel scheme that computes, offline, a spatio-temporal representation of the sound field in the listening area and store it as a multipole expansion. During head-tracked playback, the binaural signal is obtained by evaluating the multipole expansion at the ear position corresponding to the current user pose, resulting in a fixed playback cost. The representation is further extended to incorporate individualized HRTFs at no additional cost. Simulation results are presented.
Keywords: Acoustic fields; Acoustic scattering; acoustic signal processing; audio acoustics; Audio systems; binaural head-tracked; binaural presentation; Computational efficiency; Costs; Ear; head-related transfer function; Headphones; HRTF-enabled playback; Loudspeakers; Music; reverberation; sound field; spatio-temporal representation; surround sound; surround sound content; Transfer functions; virtual audio principles

Evaluating a cross-cultural children’s online book community: Lessons learned for sociability, usability, and cultural exchange - Komlodi,Anita; Hou,Weimin; Preece,Jenny; Druin, Allison; Golub,Evan; Alburo,Jade; Liao,Sabrina; Elkiss,Aaron; Resnik, Philip (Interacting with Computers, 2007)
The use of computers for human-to-human communication among adults has been studied for many years, but using computer technology to enable children from all over the world to talk to each other has rarely been discussed by researchers. The goal of our research is to fill this gap and explore the design and evaluation of children’s cross-language online communities via a case study of the International Children’s Digital Library Communities (ICDLCommunities). This project supports the development of communities for children (ages 7–11) that form around the International Digital Children’s Library (ICDL) book collection. In this community the children can learn about each others’ cultures and make friends even if they do not speak the same language. They can also read and create stories and ask and answer questions about these. From this evaluation study we learned that: (i) children are very interested in their counterparts in other countries and a remarkable amount of communication takes place even when they do not share a common language; (ii) representing their identity online in many different forms is particularly important to children when communicating in an online community; (iii) children enjoy drawing but representing stories in a sequence of diagrams is challenging and needs support; and (iv) asking and answering questions without language is possible using graphical templates. In this paper we present our findings and make recommendations for designing children’s cross-cultural online communities.
Keywords: children; Cross-cultural; Evaluation and design; International Children’s Digital Library; Online communities

Evolution of genes and genomes on the Drosophila phylogeny - Clark,Andrew G.; Eisen,Michael B.; Smith,Douglas R.; Bergman,Casey M.; Oliver,Brian; Markow,Therese A.; Kaufman,Thomas C.; Kellis,Manolis; Gelbart,William; Iyer,Venky N.; Pollard,Daniel A.; Sackton,Timothy B.; et al. (Nature, 2007)
Comparative analysis of multiple genomes in a phylogenetic framework dramatically improves the precision and sensitivity of evolutionary inference, producing more robust results than single-genome analyses can provide. The genomes of 12 Drosophila species, ten of which are presented here for the first time (sechellia, simulans, yakuba, erecta, ananassae, persimilis, willistoni, mojavensis, virilis and grimshawi), illustrate how rates and patterns of sequence divergence across taxa can illuminate evolutionary processes on a genomic scale. These genome sequences augment the formidable genetic tools that have made Drosophila melanogaster a pre-eminent model for animal genetics, and will further catalyse fundamental research on mechanisms of development, cell biology, genetics, disease, neurobiology, behaviour, physiology and evolution. Despite remarkable similarities among these Drosophila species, we identified many putatively non-neutral changes in protein-coding genes, non-coding RNA genes, and cis-regulatory regions. These may prove to underlie differences in the ecology and behaviour of these diverse species.

Experimenting with software testbeds for evaluating new technologies - Lindvall,M.; Rus,I.; Donzelli,P.; Memon, Atif M.; Zelkowitz, Marvin V; Betin-Can,A.; Bultan,T.; Ackermann,C.; Anders,B.; Asgari, S.; Basili, Victor R. (Empirical Software Engineering, 2007)
The evolution of a new technology depends upon a good theoretical basis for developing the technology, as well as upon its experimental validation. In order to provide for this experimentation, we have investigated the creation of a software testbed and the feasibility of using the same testbed for experimenting with a broad set of technologies. The testbed is a set of programs, data, and supporting documentation that allows researchers to test their new technology on a standard software platform. An important component of this testbed is the Unified Model of Dependability (UMD), which was used to elicit dependability requirements for the testbed software. With a collection of seeded faults and known issues of the target system, we are able to determine if a new technology is adept at uncovering defects or providing other aids proposed by its developers. In this paper, we present the Tactical Separation Assisted Flight Environment (TSAFE) testbed environment for which we modeled and evaluated dependability requirements and defined faults to be seeded for experimentation. We describe two completed experiments that we conducted on the testbed. The first experiment studies a technology that identifies architectural violations and evaluates its ability to detect the violations. The second experiment studies model checking as part of design for verification. We conclude by describing ongoing experimental work studying testing, using the same testbed. Our conclusion is that even though these three experiments are very different in terms of the studied technology, using and re-using the same testbed is beneficial and cost effective.

Exploiting aspectual features and connecting words for summarization-inspired temporal-relation extraction - Dorr, Bonnie J; Gaasterland,Terry (Information Processing & Management, 2007)
This paper presents a model that incorporates contemporary theories of tense and aspect and develops a new framework for extracting temporal relations between two sentence-internal events, given their tense, aspect, and a temporal connecting word relating the two events. A linguistic constraint on event combination has been implemented to detect incorrect parser analyses and potentially apply syntactic reanalysis or semantic reinterpretation—in preparation for subsequent processing for multi-document summarization. An important contribution of this work is the extension of two different existing theoretical frameworks—Hornstein’s 1990 theory of tense analysis and Allen’s 1984 theory on event ordering—and the combination of both into a unified system for representing and constraining combinations of different event types (points, closed intervals, and open-ended intervals). We show that our theoretical results have been verified in a large-scale corpus analysis. The framework is designed to inform a temporally motivated sentence-ordering module in an implemented multi-document summarization system.
Keywords: Parsing and corpus analysis; Summarization; temporal ordering; Temporal-relation extraction; Tense, aspect and connecting words

Extended wavelets for multiple measures - Deligiannakis,Antonios; Garofalakis,Minos; Roussopoulos, Nick (ACM Transactions on Database SystemsACM Trans. Database Syst., 2007)

A fast algorithm for learning large scale preference relations - Raykar,V.C.; Duraiswami, Ramani; Krishnapuram,B. (Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS 2007), 2007)
We consider the problem of learning the rank-ing function that maximizes a generalization of the Wilcoxon-Mann-Whitney statistic on training data. Relying on an ϵ-exact approx- imation for the error-function, we reduce the computational complexity of each iteration of a conjugate gradient algorithm for learn- ing ranking functions from O(m2), to O(m), where m is the size of the training data. Experiments on public benchmarks for ordi- nal regression and collaborative filtering show that the proposed algorithm is as accurate as the best available methods in terms of rank- ing accuracy, when trained on the same data, and is several orders of magnitude faster.

Fast computation of sums of Gaussians - Raykar,V.C.; Duraiswami, Ramani; Gumerov, Nail A. (Journal of Machine Learning Research (submitted), 2007)
Evaluating sums of multivariate Gaussian kernels is a key computational task in manyproblems in computational statistics and machine learning. The computational cost of the direct evaluation of such sums scales as the product of the number of kernel functions and the evaluation points. The fast Gauss transform proposed by Greengard and Strain (1991) is a ǫ-exact approximation algorithm that reduces the computational complexity of the evaluation of the sum of N Gaussians at M points in d dimensions from O(MN) to O(M + N). However, the constant factor in O(M + N) grows exponentially with increasing dimensionality d, which makes the algorithm impractical for dimensions greater than three. In this paper we present a new algorithm where the constant factor is reduced to asymptotically polynomial order. The reduction is based on a new multivariate Taylor’s series expansion (which can act both as a local as well as a far field expansion) scheme combined with the efficient space subdivision using the k-center algorithm. The proposed method differs from the original fast Gauss transform in terms of a different factorization, efficient space subdivision, and the use of different error bounds for each source point. Algorithm details, error bounds, a procedure to choose the parameters, and numerical experiments are presented. We also compare our algorithm with the dual-tree algorithm of Gray and Moore (2003). As an example we show how the proposed method can be used for very fast ǫ-exact multivariate kernel density estimation.

Fast Evaluation of the Room Transfer Function Using Multipole Expansion - Duraiswami, Ramani; Zotkin,Dmitry N; Gumerov, Nail A. (Audio, Speech, and Language Processing, IEEE Transactions on, 2007)
Reverberation in rooms is often simulated with the image method due to Allen and Berkley (1979). This method has an asymptotic complexity that is cubic in terms of the simulated reverberation length. When employed in the frequency domain, it is relatively computationally expensive if there are many receivers in the room or if the source or receiver positions are changing with time. The computational complexity of the image method is due to the repeated summation of the fields generated by a large number of image sources. In this paper, a fast method to perform such summations is presented. The method is based on multipole expansion of the monopole source potential. For offline computation of the room transfer function for N image sources and M receiver points, use of the Allen-Berkley algorithm requires O(NM) operations, whereas use of the proposed method requires only O(N+M) operations, resulting in significantly faster computation of reverberant sound fields. The proposed method also has a considerable speed advantage in situations where the room transfer function must be rapidly updated online in response to source/receiver location changes. Simulation results are presented, and algorithm accuracy, speed, and implementation details are discussed. For problems that require frequency-domain computations, the algorithm is found to generate sound fields identical to the ones obtained with the frequency-domain version of the Allen-Berkley algorithm at a fraction of computational cost
Keywords: acoustics; computational; algorithm; frequency-domain; Alien-Berkley; analysis; reverberation; complexity; frequency-domain; computations; image; expansion; receivers; reverberant; field; architectural; fields; reverberation; room; function; acoustic; method; image; potential; multipole; sound; source; sources; monopole; transfer

Fast large scale Gaussian process regression using approximate matrix-vector products - Raykar,V.C.; Duraiswami, Ramani (Learning workshop, 2007)

Fast Multipole Accelerated Boundary Elements for Numerical Computation of the Head Related Transfer Function - Gumerov, Nail A.; Duraiswami, Ramani; Zotkin,Dmitry N (IEEE International Conference on Acoustics, Speech and Signal Processing, 2007. ICASSP 2007, 2007)
The numerical computation of head related transfer functions has been attempted by a number of researchers. However, the cost of the computations has meant that usually only low frequencies can be computed and further the computations take inordinately long times. Because of this, comparisons of the computations with measurements are also difficult. We present a fast multipole based iterative preconditioned Krylov solution of a boundary element formulation of the problem and use a new formulation that enables the reciprocity technique to be accurately employed. This allows the calculation to proceed for higher frequencies and larger discretizations. Preliminary results of the computations and of comparisons with measured HRTFs are presented.
Keywords: Acceleration; Acoustic measurements; Acoustic scattering; audio signal processing; boundary element formulation; Boundary element method; Boundary element methods; boundary-elements methods; Costs; Ear; Fast Multipole Method; Frequency; Head related transfer function; HUMANS; Irrigation; iterative methods; multipole accelerated boundary elements; multipole based iterative preconditioned Krylov solution; numerical computation; Reciprocity; Transfer functions

Fast Time-Domain Spherical Microphone Array Beamforming - Zhiyun Li; Duraiswami, Ramani (Applications of Signal Processing to Audio and Acoustics, 2007 IEEE Workshop on, 2007)
Capturing and reproducing 3D audio has several applications. Spherical array based beamforming is an important technique in this field. However, such a beamformer is very expensive to implement, especially for interactive applications. In this paper, we propose a fast spherical beamforming algorithm in the time domain. It uses pre-computed data and can be steered to arbitrary 3D directions. It is ideal for interactive audio applications such as 3D games, etc. Simulation and experimental results are demonstrated to verify our algorithm.

Fast weighted summation of erfc functions - Raykar,Vikas C.; Duraiswami, Ramani; Krishnapuram,B. (Technical Reports from UMIACS UMIACS-TR-2007-03, 2007)
Abstract: Direct computation of the weighted sum of N complementaryerror functions at M points scales as O(MN). We present a O(M + N) $ε$-exact approximation algorithm to compute the same.
Keywords: Technical Report

Features generated for computational splice-site prediction correspond to functional elements - Dogan,Rezarta I.; Getoor,Lise; Wilbur,W. John; Mount, Stephen M. (BMC Bioinformatics, 2007)
Accurate selection of splice sites during the splicing of precursors to messenger RNA requires both relatively well-characterized signals at the splice sites and auxiliary signals in the adjacent exons and introns. We previously described a feature generation algorithm (FGA) that is capable of achieving high classification accuracy on human 3' splice sites. In this paper, we extend the splice-site prediction to 5' splice sites and explore the generated features for biologically meaningful splicing signals.

Flexible and Optimal Design of Spherical Microphone Arrays for Beamforming - Li,Z.; Duraiswami, Ramani (Audio, Speech, and Language Processing, IEEE Transactions on, 2007)
This paper describes a methodology for designing a flexible and optimal spherical microphone array for beamforming. Using the approach presented, a spherical microphone array can have very flexible layouts of microphones on the spherical surface, yet optimally approximate a desired beampattern of higher order within a specified robustness constraint. Depending on the specified beampattern order, our approach automatically achieves optimal performances in two cases: when the specified beampattern order is reachable within the robustness constraint we achieve a beamformer with optimal approximation of the desired beampattern; otherwise we achieve a beamformer with maximum directivity, both robustly. For efficient implementation, we also developed an adaptive algorithm for computing the beamformer weights. It converges to the optimal performance quickly while exactly satisfying the specified frequency response and robustness constraint in each step. One application of the method is to allow the building of a real-world system, where microphones may not be placeable on regions, such as near cable outlets and/or a mounting base, while having a minimal effect on the performance. Simulation results are presented
Keywords: adaptive; algorithm; beamforming; beampattern; frequency; arrays; arrays; acoustic; directivity; optimal; microphone; processing; array; processing; microphone; response; maximum; signal; spherical

Frustratingly easy domain adaptation - Daumé, Hal (Annual meeting-association for computational linguistics, 2007)

Genome Analysis Linking Recent European and African Influenza (H5N1) Viruses - Salzberg,Steven L.; Kingsford, Carl; Cattoli,Giovanni; Spiro,David J.; Janies,Daniel A.; Aly,Mona Mehrez; Brown,Ian H.; Couacy-Hymann,Emmanuel; De Mia,Gian Mario; Dung,Do Huu; Guercio,Annalisa; Joannis,Tony; et al. (Emerging Infectious DiseasesEmerg Infect Dis, 2007)
Although linked, these viruses are distinct from earlier outbreak strains., To better understand the ecology and epidemiology of the highly pathogenic avian influenza virus in its transcontinental spread, we sequenced and analyzed the complete genomes of 36 recent influenza A (H5N1) viruses collected from birds in Europe, northern Africa, and southeastern Asia. These sequences, among the first complete genomes of influenza (H5N1) viruses outside Asia, clearly depict the lineages now infecting wild and domestic birds in Europe and Africa and show the relationships among these isolates and other strains affecting both birds and humans. The isolates fall into 3 distinct lineages, 1 of which contains all known non-Asian isolates. This new Euro-African lineage, which was the cause of several recent (2006) fatal human infections in Egypt and Iraq, has been introduced at least 3 times into the European-African region and has split into 3 distinct, independently evolving sublineages. One isolate provides evidence that 2 of these sublineages have recently reassorted.

Geometrical Characteristics of Regular Polyhedra: Application to EXAFS Studies of Nanoclusters - Dana Dachman-Soled; Frenkel, Anatoly I. (X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference, 2007)
EXAFS data modeling of nanoparticles can be done at a very high level of detail if regular polyhedral geometries are considered as possible structural models. Such geometries can be characterized by unique sequence of indices (coordination numbers) of the first few coordination shells that serve as a signature of a shape, size, morphology and packing model of atoms in the cluster. We wrote a suite of programs for cluster geometry generation and its pair radial distribution function analysis. The programs generate x,y,z coordinates and calculate the coordination numbers of the corresponding clusters for any order of a large number of regular polyhedra. We present the results for the first few nearest neighboring shells in the icosahedral, cuboctahedral, hcp structures for the small, 10–1000 atom clusters.
Keywords: Atomic and molecular clusters; Cluster Analysis; Cluster geometric structure; Extended X-ray absorption fine structure spectroscopy; nanoparticles; Numerical modeling; Particle distribution functions; Polyhedra; Signal generators

Geometry and Charge State of Mixed‐Ligand Au13 Nanoclusters - Frenkel, A. I.; Menard, L. D.; Northrup, P.; Rodriguez, J. A.; Zypman, F.; Dana Dachman-Soled; Gao, S.-P.; Xu, H.; Yang, J. C.; Nuzzo, R. G. (X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference, 2007)
The integration of synthetic, experimental and theoretical tools into a self‐consistent data analysis methodology allowed us to develop unique new levels of detail in nanoparticle characterization. We describe our methods using an example of Au 13 monolayer‐protected clusters (MPCs), synthesized by ligand exchange methods. The combination of atom counting methods of scanning transmission electron microscopy and Au L3‐edge EXAFS allowed us to characterize these clusters as icosahedral, with surface strain reduced from 5% (as in ideal, regular icosahedra) to 3%, due to the interaction with ligands. Charge transfer from Au to the thiol and phosphine ligands was evidenced by S and P K‐edge XANES. A comparison of total energies of bare clusters of different geometries was performed by equivalent crystal theory calculations.
Keywords: Atom surface interactions; Charge transfer; Data analysis; Extended X-ray absorption fine structure spectroscopy; Gold; nanoparticles; Scanning transmission electron microscopy; Surface strains; Total energy calculations; X-ray absorption near edge structure

Got Predictability?: Experiences with Fault-tolerant Middleware - Tudor Dumitras; Narasimhan, Priya (MC'07 Proceedings of the 2007 ACM/IFIP/USENIX International Conference on Middleware Companion, 2007)
Unpredictability in COTS-based systems often manifests as occasional instances of uncontrollably-high response times. A particular category of COTS systems, fault-tolerant (FT) middleware, is used in critical enterprise and embedded applications where predictability is of paramount importance. Our prior empirical study, which used a client-server microbenchmark, suggested that hard bounds for the maximum latency are hard to establish a priori, but that the unpredictability may be confined to less than 1% of the requests. In this paper, we present empirical data, from 7 different three-tier, FT-middleware applications, that shows strong evidence supporting this "magical 1%" hypothesis. We conducted a controlled experiment with 7 teams of students from a graduate-level course at Carnegie Mellon University. Each team, starting from a common three-tier architecture, independently implemented and evaluated an original application using middleware (either CORBA or EJB) and a custom-implemented fault-tolerance mechanism (relying on either state-machine or primary-backup replication) for the middle-tier server. This experiment shows that unpredictability may not be avoidable, even in the absence of faults, and that, in some cases, the random latency outliers are larger than the time needed to recover from a fault. The data also reveals a statistically-significant result that, across all 7 applications, unpredictability is confined to the highest 1% of the recorded end-to-end latencies and is not correlated with the request rate, the size of messages exchanged or the number of clients. This suggests that strict predictability is hard to achieve in FT-middleware systems and that developers of critical FT applications should focus on guaranteeing bounds for statistical measures, such as the 99th percentile of the latency.

A graph-based approach to vehicle tracking in traffic camera video streams - Shahri,Hamid Haidarian; Namata,Galileo; Navlakha,Saket; Deshpande, Amol; Roussopoulos, Nick (Proceedings of the 4th workshop on Data management for sensor networks: in conjunction with 33rd International Conference on Very Large Data Bases, 2007)
Vehicle tracking has a wide variety of applications from law enforcement to traffic planning and public safety. However, the image resolution of the videos available from most traffic camera systems, make it difficult to track vehicles based on unique identifiers like license plates. In many cases, vehicles with similar attributes are indistinguishable from one another due to image quality issues. Often, network bandwidth and power constraints limit the frame rate, as well. In this paper, we discuss the challenges of performing vehicle tracking queries over video streams from ubiquitous traffic cameras. We identify the limitations of tracking vehicles individually in such conditions and provide a novel graph-based approach using the identity of neighboring vehicles to improve the performance. We evaluate our approach using streaming video feeds from live traffic cameras available on the Internet. The results show that vehicle tracking is feasible, even for low quality and low frame rate traffic cameras. Additionally, exploitation of the attributes of neighboring vehicles significantly improves the performance.

Heuristic Search and Information Visualization Methods for School Redistricting - desJardins, Marie; Bulka,Blazej; Carr,Ryan; Jordan,Eric; Rheingans,Penny (AI Magazine, 2007)
We describe an application of AI search and information visualization techniques to the problem of school redistricting, in which students are assigned to home schools within a county or school district. This is a multicriteria optimization problem in which competing objectives, such as school capacity, busing costs, and socioeconomic distribution, must be considered. Because of the complexity of the decision-making problem, tools are needed to help end users generate, evaluate, and compare alternative school assignment plans. A key goal of our research is to aid users in finding multiple qualitatively different redistricting plans that represent different trade-offs in the decision space. We present heuristic search methods that can be used to find a set of qualitatively different plans, and give empirical results of these search methods on population data from the school district of Howard County, Maryland. We show the resulting plans using novel visualization methods that we have developed for summarizing and comparing alternative plans.

Hierarchical Part-Template Matching for Human Detection and Segmentation - Zhe Lin; Davis, Larry S.; David Doermann; DeMenthon,D. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Local part-based human detectors are capable of handling partial occlusions efficiently and modeling shape articulations flexibly, while global shape template-based human detectors are capable of detecting and segmenting human shapes simultaneously. We describe a Bayesian approach to human detection and segmentation combining local part-based and global template-based schemes. The approach relies on the key ideas of matching a part-template tree to images hierarchically to generate a reliable set of detection hypotheses and optimizing it under a Bayesian MAP framework through global likelihood re-evaluation and fine occlusion analysis. In addition to detection, our approach is able to obtain human shapes and poses simultaneously. We applied the approach to human detection and segmentation in crowded scenes with and without background subtraction. Experimental results show that our approach achieves good performance on images and video sequences with severe occlusion.
Keywords: analysis; global; approach; background; articulations; video; Bayesian; detection; human; detectors; hierarchical; detectors; partial; framework; Bayesian; human; likelihood; MAP; matching; human; matching; image; methods; image; occlusion; occlusions; shape; part-based; part-template; re-evaluation; global; segmentation; image; segmentation; local; sequences; sequences; Bayes; SHAPE; subtraction; fine; template-based

High frequency acoustic simulations via FMM accelerated BEM - Gumerov, Nail A.; Duraiswami, Ramani (19th Internal congress on acoustics, 2007)
High frequency simulations of acoustics are among the most expensive problems to simulate. Inpractice 6 to 10 points per wavelength are required. Since the wavenumber k is inversely proportional to wavelength, if a numerical method is a surface based method (such as the BEM), then problem size scales as O(k2D2), where D is the size of the domain. Dense matrices appear and typical iter- ative solution can be achieved for O(k4D4) memory and O(k4D4) per iteration cost. We employ an algorithm based on the fast multipole method (FMM) using coaxial and diagonal translation operators based on the frequency of simulation to reduce the memory requirements and per iteration cost to O(k2D2 log kD) for larger kD (kD ~250). The number of iterations needed depend upon the condition of the matrix, and preconditioning chosen. Preconditioned Krylov methods such as the flexible gen- eralized minimum residual method (FGMRES), with preconditioning based upon a lower accuracy FMM, usually ensure a convergent iteration. Example calculations are presented.

High-throughput sequence alignment using Graphics Processing Units - Schatz,Michael C; Trapnell,Cole; Delcher,Arthur L.; Varshney, Amitabh (BMC Bioinformatics, 2007)

HIV risk behaviors among female IDUs in developing and transitional countries - Charles,C.; Des Jarlais Don,P. T; Gerry,S. (BMC Public Health, 2007)

Human activity understanding using visibility context - Morariu,V.I.; Prasad,V. S.N; Davis, Larry S. (IEEE/RSJ IROS Workshop: From sensors to human spatial concepts (FS2HSC), 2007)
Visibility in architectural layouts affects humannavigation, so a suitable representation of visibility context is useful in understanding human activity. Motivated by studies of spatial behavior, we use a set of features from visibility analysis to represent spatial context in the interpretation of human activity. An agent’s goal, belief about the world, trajectory and visible layout are considered to be random variables that evolve with time during the agent’s movement, and are modeled in a Bayesian framework. We design a search-based task in a sprite-world, and compare the results of our framework to those of human subject experiments. Our findings confirm that knowledge of spatial layout improves human interpretations of the trajectories (implying that visibility context is useful in this task). Since our framework demonstrates performance close to that of human subjects with knowledge of spatial layout, our findings confirm that our model makes adequate use of visibility context. In addition, the representation we use for visibility context allows our model to generalize well when presented with new scenes.

Human Appearance Change Detection - Ghanem,N.M.; Davis, Larry S. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
We present a machine learning approach to detect changes in human appearance between instances of the same person that may be taken with different cameras, but over short periods of time. For each video sequence of the person, we approximately align each frame in the sequence and then generate a set of features that captures the differences between the two sequences. The features are the occupancy difference map, the codeword frequency difference map (based on a vector quantization of the set of colors and frequencies) at each aligned pixel and the histogram intersection map. A boosting technique is then applied to learn the most discriminative set of features, and these features are then used to train a support vector machine classifier to recognize significant appearance changes. We apply our approach to the problem of left package detection. We train the classifiers on a laboratory database of videos in which people are seen with and without common articles that people carry - backpacks and suitcases. We test the approach on some real airport video sequences. Moving to the real world videos requires addressing additional problems, including the view selection problem and the frame selection problem.
Keywords: (artificial; appearance; approach; occupancy; change; changes; classification; support; classifier; vector; detection; image; detection; machine; difference; Frequency; intelligence); pattern; intersection; learning; machine; machines; vector; map; histogram; map; human; map; support; package; quantisation; video; quantization; video; recognition; boosting; recognition; image; sequence; left; sequences; image; sequences; learning; surveillance; technique; codeword; vector

Human appearance modeling for matching across video sequences - Yu,Y.; Harwood,D.; Yoon,K.; Davis, Larry S. (Machine Vision and Applications, 2007)
We present an appearance model for establishing correspondence between tracks of people which may be taken at different places, at different times or across different cameras. The appearance model is constructed by kernel density estimation. To incorporate structural information and to achieve invariance to motion and pose, besides color features, an additional feature of path-length is used. To achieve illumination invariance, two types of illumination insensitive color features are discussed: brightness color feature and RGB rank feature. The similarity between a test image and an appearance model is measured by the information gain or Kullback–Leibler distance. To thoroughly represent the information contained in a video sequence with as little data as possible, a key frame selection and matching scheme is proposed. Experimental results demonstrate the important role of the path-length feature in the appearance model and the effectiveness of the proposed appearance model and matching method.

On implementing graph cuts on cuda - Hussein,M.; Varshney, Amitabh; Davis, Larry S. (First Workshop on General Purpose Processing on Graphics Processing Units, 2007)
The Compute Unified Device Architecture (CUDA)has enabled graphics processors to be explicitly programmed as general-purpose shared-memory multi-core processors with a high level of parallelism. In this paper, we present our preliminary results of implementing the Graph Cuts algorithm on CUDA. Our primary focus is on implementing Graph Cuts on grid graphs, which are extensively used in imaging applications. We first explain our implementation of breadth first search (BFS) graph traversal on CUDA, which is extensively used in our Graph Cuts implementation. We then present a basic implementation of Graph Cuts that succeeds to achieve absolute and relative speedups when used for foreground-background segmentation on synthesized images. Finally, we introduce two optimizations that utilize the special structure of grid graphs. The first one is lockstep BFS, which is used to reduce the overhead of BFS traversals. The second is cache emulation, which is a general technique to regularize memory access patterns and hence enhance memory access throughput. We experimentally show how each of the two optimizations can enhance the performance of the basic implementation on the image segmentation application.

The improved fast Gauss transform with applications to machine learning - Raykar,V.C.; Duraiswami, Ramani (Large Scale Kernel Machines, 2007)

Inferring organizational titles in online communication - Namata,G.; Getoor, Lise; Diehl,C. (Statistical Network Analysis: Models, Issues, and New Directions, 2007)
There is increasing interest in the storage, retrieval, and analysis of email communications. One active area of research focuses on the inference of properties of the underlying social network giving rise to the email communications[1,2]. Email communication between individuals implies some type of relationship, whether it is formal, such as a manager-employee relationship, or informal, such as friendship relationships. Understanding the nature of these observed relationships can be problematic given there is a shared context among the individuals that isn’t necessarily communicated. This provides a challenge for analysts that wish to explore and understand email archives for legal or historical research.

An Interactive Approach to Pose-Assisted and Appearance-based Segmentation of Humans - Zhe Lin; Davis, Larry S.; David Doermann; DeMenthon,D. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
An interactive human segmentation approach is described. Given regions of interest provided by users, the approach iteratively estimates segmentation via a generalized EM algorithm. Specifically, it encodes both spatial and color information in a nonparametric kernel density estimator, and incorporates local MRF constraints and global pose inferences to propagate beliefs over image space iteratively to determine a coherent segmentation. This ensures the segmented humans resemble the shapes of human poses. Additionally, a layered occlusion model and a probabilistic occlusion reasoning method are proposed to handle segmentation of multiple humans in occlusion. The approach is tested on a wide variety of images containing single or multiple occluded humans, and the segmentation performance is evaluated quantitatively.
Keywords: algorithm; appearance-based; algorithm; hidden; approach; layered; density; EM; Estimation; estimation; estimator; pose-assisted; feature; human; Kernel; mechanisms; pose; method; expectation-maximisation; model; nonparametric; occlusion; reasoning; removal; image; segmentation; inference; segmentation; interactive; segmentation; probabilistic

Interactive visual clustering - desJardins, Marie; MacGlashan,James; Ferraioli,Julia (Proceedings of the 12th international conference on Intelligent user interfaces, 2007)
Interactive Visual Clustering (IVC) is a novel method that allows a user to explore relational data sets interactively, in order to produce a clustering that satisfies their objectives. IVC combines spring-embedded graph layout with user interaction and constrained clustering. Experimental results on several synthetic and real-world data sets show that IVC yields better clustering performance than alternative methods.
Keywords: clustering; constraints; interaction

Learning and visualizing user preferences over sets - Wagstaff,K.; desJardins, Marie; Eaton,E.; Montminy,J. (American Association for Artificial Intelligence (AAAI), 2007)
In previous work, we introduced a representation language,DD-PREF, that balances preferences for particular items with preferences about the properties of the set. Specifically, DD- PREF permits the expression of preferences for depth (i.e., preferences for specific attribute values over others) and di- versity of sets (i.e., preferences for broad vs. narrow distri- butions of attribute values). We have also shown how pref- erences represented in DD-PREF can be learned from training data. In this paper, we present a new experimental method- ology, and give results in a Mars rover image domain. We also provide new visualizations of the learned preferences in this domain. Finally, we describe a Chinese restaurant menu domain for which we are currently gathering user data.

Learning Higher-order Transition Models in Medium-scale Camera Networks - Farrell,R.; David Doermann; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
We present a Bayesian framework for learning higher- order transition models in video surveillance networks. Such higher-order models describe object movement between cameras in the network and have a greater predictive power for multi-camera tracking than camera adjacency alone. These models also provide inherent resilience to camera failure, filling in gaps left by single or even multiple non-adjacent camera failures. Our approach to estimating higher-order transition models relies on the accurate assignment of camera observations to the underlying trajectories of objects moving through the network. We addresses this data association problem by gathering the observations and evaluating alternative partitions of the observation set into individual object trajectories. Searching the complete partition space is intractable, so an incremental approach is taken, iteratively adding observations and pruning unlikely partitions. Partition likelihood is determined by the evaluation of a probabilistic graphical model. When the algorithm has considered all observations, the most likely (MAP) partition is taken as the true object trajectories. From these recovered trajectories, the higher-order statistics we seek can be derived and employed for tracking. The partitioning algorithm we present is parallel in nature and can be readily extended to distributed computation in medium-scale smart camera networks.
Keywords: (artificial; approach; medium-scale; association; Bayesian; camera; cameras; video; framework; data; fusion; iterative; graphical; intelligence); optical; learning; incremental; likelihood; multicamera; likely; methods; higher; methods; learning; model; model; video; movement; probabilistic; network; Bayes; network; most; order; partition; problem; higher-order; statistics; higher-order; statistics; image; Surveillance; surveillance; tracking; object; tracking; probability; video; transition

Local strategy learning in networked multi-agent team formation - Bulka,Blazej; Gaston,Matthew; desJardins, Marie (Autonomous Agents and Multi-Agent Systems, 2007)
Networked multi-agent systems are comprised of many autonomous yet interdependent agents situated in a virtual social network. Two examples of such systems are supply chain networks and sensor networks. A common challenge in many networked multi-agent systems is decentralized team formation among the spatially and logically extended agents. Even in cooperative multi-agent systems, efficient team formation is made difficult by the limited local information available to the individual agents. We present a model of distributed multi-agent team formation in networked multi-agent systems, describe a policy learning framework for joining teams based on local information, and give empirical results on improving team formation performance. In particular, we show that local policy learning from limited information leads to a significant increase in organizational team formation performance compared to a random policy.

Mapping the Interactions between Lys48 and Lys63-Linked Di-ubiquitins and a Ubiquitin-Interacting Motif of S5a - Haririnia,Aydin; D’Onofrio,Mariapina; Fushman, David (Journal of Molecular Biology, 2007)
Numerous cellular processes are regulated by (poly)ubiquitin-mediated signaling events, which involve a covalent modification of the substrate protein by a single ubiquitin or a chain of ubiquitin molecules linked via a specific lysine. Remarkably, the outcome of polyubiquitination is linkage-dependent. For example, Lys48-linked chains are the principal signal for proteasomal degradation, while Lys63-linked chains act as nonproteolytic signals. Despite significant progress in characterization of various cellular pathways involving ubiquitin, understanding of the structural details of polyubiquitin chain recognition by downstream cellular effectors is missing. Here we use NMR to study the interaction of a ubiquitin-interacting motif (UIM) of the proteasomal subunit S5a with di-ubiquitin, the simplest model for polyubiquitin chain, to gain insights into the mechanism of polyubiquitin recognition by the proteasome. We have mapped the binding interface and characterized the stoichiometry and the process of UIM binding to Lys48- and Lys63-linked di-ubiquitin chains. Our data provide the first direct evidence that UIM binding involves a conformational transition in Lys48-linked di-ubiquitin, which opens the hydrophobic interdomain interface. This allows UIM to enter the interface and bind directly to the same ubiquitin hydrophobic-patch surface as utilized in UIM:monoubiquitin complexes. The results indicate that up to two UIM molecules can bind di-ubiquitin, and the binding interface between UIM and ubiquitin units in di-ubiquitin is essentially the same for both Lys48- and Lys63-linked chains. Our data suggest possible structural models for the binding of UIM and of full-length S5a to di-ubiquitin.
Keywords: chemical shift perturbation mapping; polyubiquitin; S5a; ubiquitin; ubiquitin-interacting motif

Measurement and analysis of online social networks - Mislove,Alan; Marcon,Massimiliano; Gummadi,Krishna P.; Druschel,Peter; Bhattacharjee, Bobby (Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007)
Online social networking sites like Orkut, YouTube, and Flickr are among the most popular sites on the Internet. Users of these sites form a social network, which provides a powerful means of sharing, organizing, and finding content and contacts. The popularity of these sites provides an opportunity to study the characteristics of online social network graphs at large scale. Understanding these graphs is important, both to improve current systems and to design new applications of online social networks. This paper presents a large-scale measurement study and analysis of the structure of multiple online social networks. We examine data gathered from four popular online social networks: Flickr, YouTube, LiveJournal, and Orkut. We crawled the publicly accessible user links on each site, obtaining a large portion of each social network's graph. Our data set contains over 11.3 million users and 328 million links. We believe that this is the first study to examine multiple online social networks at scale. Our results confirm the power-law, small-world, and scale-free properties of online social networks. We observe that the indegree of user nodes tends to match the outdegree; that the networks contain a densely connected core of high-degree nodes; and that this core links small groups of strongly clustered, low-degree nodes at the fringes of the network. Finally, we discuss the implications of these structural properties for the design of social network based systems.
Keywords: analysis; measurement; social networks

Measuring variability in sentence ordering for news summarization - Madnani,Nitin; Passonneau,Rebecca; Ayan,Necip Fazil; Conroy,John M.; Dorr, Bonnie J; Klavans,Judith L.; O'Leary, Dianne P.; Schlesinger,Judith D. (Proceedings of the Eleventh European Workshop on Natural Language Generation, 2007)
The issue of sentence ordering is an important one for natural language tasks such as multi-document summarization, yet there has not been a quantitative exploration of the range of acceptable sentence orderings for short texts. We present results of a sentence reordering experiment with three experimental conditions. Our findings indicate a very high degree of variability in the orderings that the eighteen subjects produce. In addition, the variability of reorderings is significantly greater when the initial ordering seen by subjects is different from the original summary. We conclude that evaluation of sentence ordering should use multiple reference orderings. Our evaluation presents several metrics that might prove useful in assessing against multiple references. We conclude with a deeper set of questions: (a) what sorts of independent assessments of quality of the different reference orderings could be made and (b) whether a large enough test set would obviate the need for such independent means of quality assessment.

Microphone Arrays as Generalized Cameras for Integrated Audio Visual Processing - O'Donovan,A.; Duraiswami, Ramani; Neumann, J. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
Combinations of microphones and cameras allow the joint audio visual sensing of a scene. Such arrangements of sensors are common in biological organisms and in applications such as meeting recording and surveillance where both modalities are necessary to provide scene understanding. Microphone arrays provide geometrical information on the source location, and allow the sound sources in the scene to be separated and the noise suppressed, while cameras allow the scene geometry and the location and motion of people and other objects to be estimated. In most previous work the fusion of the audio-visual information occurs at a relatively late stage. In contrast, we take the viewpoint that both cameras and microphone arrays are geometry sensors, and treat the microphone arrays as generalized cameras. We employ computer-vision inspired algorithms to treat the combined system of arrays and cameras. In particular, we consider the geometry introduced by a general microphone array and spherical microphone arrays. The latter show a geometry that is very close to central projection cameras, and we show how standard vision based calibration algorithms can be profitably applied to them. Experiments are presented that demonstrate the usefulness of the considered approach.
Keywords: algorithms; generalized; arrays; scene; arrays; sensor; audio; audio-visual; cameras; geometrical; fusion; fusion; computer-vision; geometry; sound; information; information; geometry; inspired; location; acoustic; processing; array; processing; audio-visual; processing; microphone; sensors; integrated; signal; sources; source; systems; cameras; computer; vision; geometry; microphone; visual

Middleware for programming NVIDIA GPUs from Fortran 9x - Gumerov, Nail A.; Duraiswami, Ramani; Dorland,W. (Supercomputing, 2007)

Minimus: a fast, lightweight genome assembler - Sommer,Daniel D; Delcher,Arthur L.; Salzberg,Steven L.; Pop, Mihai (BMC Bioinformatics, 2007)
Genome assemblers have grown very large and complex in response to the need for algorithms to handle the challenges of large whole-genome sequencing projects. Many of the most common uses of assemblers, however, are best served by a simpler type of assembler that requires fewer software components, uses less memory, and is far easier to install and run.

Mobile Retriever - Finding Document with a Snapshot - Liu,Xu; David Doermann (CBDAR, 2007)
In this paper we describe a camera based document image retrieval system which is targeted toward camera phones. Our goal is to enable the device to identify which of a known set of documents it is “looking at”. This paper provides two key contributions 1) a local context descriptor that effectively rules out irrelevant documents using only a small patch of the document image and 2) a layout verification approach that boosts the accuracy of retrieval even under severe degradation such as warping or crinkling. We have implemented the mobile retriever client on an iMate Jamin camera phone and tested it with a document database of 12742 pages. Experiments show that our verification approach clearly separates successful retrievals from unsuccessful retrievals.

Multi-candidate reduction: Sentence compression as a tool for document summarization tasks - Zajic, David; Dorr, Bonnie J; Jimmy Lin; Schwartz,Richard (Information Processing & Management, 2007)
This article examines the application of two single-document sentence compression techniques to the problem of multi-document summarization—a “parse-and-trim” approach and a statistical noisy-channel approach. We introduce the multi-candidate reduction (MCR) framework for multi-document summarization, in which many compressed candidates are generated for each source sentence. These candidates are then selected for inclusion in the final summary based on a combination of static and dynamic features. Evaluations demonstrate that sentence compression is a valuable component of a larger multi-document summarization framework.
Keywords: Headline generation; Hidden Markov model; Parse-and-trim; Summarization

Multimodal Tracking for Smart Videoconferencing and Video Surveillance - Zotkin,Dmitry N; Raykar,V.C.; Duraiswami, Ramani; Davis, Larry S. (Computer Vision and Pattern Recognition, 2007. CVPR '07. IEEE Conference on, 2007)
Many applications require the ability to track the 3-D motion of the subjects. We build a particle filter based framework for multimodal tracking using multiple cameras and multiple microphone arrays. In order to calibrate the resulting system, we propose a method to determine the locations of all microphones using at least five loudspeakers and under assumption that for each loudspeaker there exists a microphone very close to it. We derive the maximum likelihood (ML) estimator, which reduces to the solution of the non-linear least squares problem. We verify the correctness and robustness of the multimodal tracker and of the self-calibration algorithm both with Monte-Carlo simulations and on real data from three experimental setups.
Keywords: (numerical; 3D; algorithm; smart; analysis; least; approximations; particle; arrays; nonlinear; cameras; multiple; Carlo; estimator; multimodal; filter; self-calibration; Filtering; least; likelihood; methods); teleconferencing; video; methods; image; microphone; MOTION; motion; Monte-Carlo; problem; particle; processing; video; signal; simulations; maximum; squares; surveillance; surveillance; Monte; tracking; multiple; videoconferencing; video

Multiple alternative sentence compressions for automatic text summarization - Madnani,N.; Zajic, David; Dorr, Bonnie J; Ayan,N.F.; Jimmy Lin (Proceedings of DUC, 2007)
We perform multi-document summariza-tion by generating compressed versions of source sentences as summary candi- dates and using weighted features of these candidates to construct summaries. We combine a parse-and-trim approach with a novel technique for producing multiple alternative compressions for source sen- tences. In addition, we use a novel method for tuning the feature weights that maxi- mizes the change in the ROUGE-2 score (∆ROUGE) between the already existing summary state and the new state that re- sults from the addition of the candidate under consideration. We also describe ex- periments using a new paraphrase-based feature for redundancy checking. Finally, we present the results of our DUC2007 submissions and some ideas for future work.

Multiple View Image Reconstruction: A Harmonic Approach - Domke, J.; Aloimonos, J. (IEEE Conference on Computer Vision and Pattern Recognition, 2007. CVPR '07, 2007)
This paper presents a new constraint connecting the signals in multiple views of a surface. The constraint arises from a harmonic analysis of the geometry of the imaging process and it gives rise to a new technique for multiple view image reconstruction. Given several views of a surface from different positions, fundamentally different information is present in each image, owing to the fact that cameras measure the incoming light only after the application of a low-pass filter. Our analysis shows how the geometry of the imaging is connected to this filtering. This leads to a technique for constructing a single output image containing all the information present in the input images.
Keywords: CAMERAS; filtering theory; Geometry; Harmonic analysis; Image reconstruction; imaging process geometry; Information filtering; Joining processes; Low pass filters; low-pass filter; low-pass filters; multiple view image reconstruction; Position measurement; Power harmonic filters; surface reconstruction

Multi-resolution Morse-Smale Complexes for Terrain Modeling - Danovaro,E.; De Floriani, Leila; Vitali,M. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
We propose a hierarchical representation for the morphology of a terrain. The basis of our morphological model is a decomposition of the terrain model, composed of the stable and unstable manifolds defined by its critical points, called a Morse-Smale complex. We propose a compact dual representation of the Morse-Smale complex and we define new simplification operators of the terrain morphology, which act on such representation. Based on these operators, we define a hierarchical morphology-based representation for a terrain, that we call a Multi-resolution Morse-Smale Complex (MMSC). Results from our implementation of the MMSC are shown.
Keywords: complex; terrain; hierarchical; mapping; modeling; terrain; modelling; terrain; morphology-based; morphology; image; morphology; solid; Morse-Smale; representation; image; representation; multiresolution; resolution; mathematical

Multiresolution Terrain Processing and Visualization with VARIANT - De Floriani, Leila; Magillo,P. (Department of Computer and Information Sciences, University of Genova, Via Dodecaneso, 2007)
We present VARIANT (VAriable Resolution Interactive ANalysis of Terrain), a system forprocessing and visualizing terrains represented through Triangulated Irregular Networks (TINs) at multiple resolutions. Multiresolution refers to the possibility of dynamically varying the density of the TIN, and is used to enhance speed of computation while guaranteeing the accuracy needed by operations. VARIANT directly supports basic queries as well as some high-level operations, and it can be enriched with many other functionalities. It is built on the Multi- Triangulation (MT) Library, an extensible library for multiresolution geometric modeling.