Fuzzy svm ensembles for relevance feedback in image retrieval - Rao,Y.; Mundur, Padma; Yesha,Y. (Image and Video Retrieval, 2006)

The Goal Question Metric Approach - Basili, Victor R.; Caldiera,G.; Rombach,H. D (5th ACM-IEEE International Symposium on Empirical Software Engineering (ISESE’06), 2006)

Heuristic search and information visualization methods for school redistricting - desJardins, Marie; Bulka,Blazej; Carr,Ryan; Hunt,Andrew; Rathod,Priyang; Rheingans,Penny (Proceedings of the 18th conference on Innovative applications of artificial intelligence - Volume 2, 2006)
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 must be considered, such as school capacity, busing costs, and socioeconomic distribution. 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 tradeoffs 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.

High-confidence medical device software and systems - Lee,I.; Pappas,G. J; Cleaveland, Rance; Hatcliff,J.; Krogh,B. H; Lee,P.; Rubin,H.; Sha,L. (Computer, 2006)
Given the shortage of caregivers and the increase in an aging US population, the future of US healthcare quality does not look promising and definitely is unlikely to be cheaper. Advances in health information systems and healthcare technology offer a tremendous opportunity for improving the quality of care while reducing costs. The development and production of medical device software and systems is a crucial issue, both for the US economy and for ensuring safe advances in healthcare delivery. As devices become increasingly smaller in physical terms but larger in software terms, the design, testing, and eventual Food and Drug Administration (FDA) device approval is becoming much more expensive for medical device manufacturers both in terms of time and cost. Furthermore, the number of devices that have recently been recalled due to software and hardware problems is increasing at an alarming rate. As medical devices are becoming increasingly networked, ensuring even the same level of health safety seems a challenge.
Keywords: Aging; biomedical equipment; Clinical software engineering; Costs; FDA device; Food and Drug Administration device; health and safety; health care; health information system; health safety; healthcare delivery; Healthcare technology; Information systems; medical computing; medical device manufacturing; medical device software development; medical device systems development; medical information systems; Medical services; Medical software; Medical tests; networked medical devices; Production systems; Software design; Software safety; Software systems; Software testing; US healthcare quality

Implementing a bioinformatics pipeline (bip) on a mediator platform: Comparing cost and quality of alternate choices - Eckman,B. A; Gaasterland,T.; Lacroix,Z.; Raschid, Louiqa; Snyder,B.; Vidal,M. E (Data Engineering Workshops, 2006. Proceedings. 22nd International Conference on, 2006)

In VINI veritas: realistic and controlled network experimentation - Bavier,Andy; Feamster, Nick; Huang,Mark; Peterson,Larry; Rexford,Jennifer (SIGCOMM Comput. Commun. Rev., 2006)
This paper describes VINI, a virtual network infrastructure that allows network researchers to evaluate their protocols and services in a realistic environment that also provides a high degree of control over network conditions. VINI allows researchers to deploy and evaluate their ideas with real routing software, traffic loads, and network events. To provide researchers flexibility in designing their experiments, VINI supports simultaneous experiments with arbitrary network topologies on a shared physical infrastructure. This paper tackles the following important design question: What set of concepts and techniques facilitate flexible, realistic, and controlled experimentation (e.g., multiple topologies and the ability to tweak routing algorithms) on a fixed physical infrastructure? We first present VINI's high-level design and the challenges of virtualizing a single network. We then present PL-VINI, an implementation of VINI on PlanetLab, running the "Internet In a Slice". Our evaluation of PL-VINI shows that it provides a realistic and controlled environment for evaluating new protocols and services.
Keywords: architecture; experimentation; Internet; Routing; virtualization

An Interaction-Dependent Model for Transcription Factor Binding - Wang,Li-San; Jensen,Shane; Hannenhalli, Sridhar (Systems Biology and Regulatory GenomicsSystems Biology and Regulatory Genomics, 2006)
Transcriptional regulation is accomplished by several transcription factor proteins that bind to specific DNA elements in the relative vicinity of the gene, and interact with each other and with Polymerase enzyme. Thus the determination of transcription factor-DNA binding is an important step toward understanding transcriptional regulation. An effective way to experimentally determine the genomic regions bound by a transcription factor is by a ChIP-on-chip assay. Then, given the putative genomic regions, computational motif finding algorithms are applied to estimate the DNA binding motif or positional weight matrix for the TF. The a priori expectation is that the presence or absence of the estimated motif in a promoter should be a good indicator of the binding of the TF to that promoter. This association between the presence of the transcription factor motif and its binding is however weak in a majority of cases where the whole genome ChIP experiments have been performed. One possible reason for this is that the DNA binding of a particular transcription factor depends not only on its own motif, but also on synergistic or antagonistic action of neighboring motifs for other transcription factors. We believe that modeling this interaction-dependent binding with linear regression can better explain the observed binding data. We assess this hypothesis based on the whole genome ChIP-on-chip data for Yeast. The derived interactions are largely consistent with previous results that combine ChIP-on-chip data with expression data. We additionally apply our method to determine interacting partners for CREB and validate our findings based on published experimental results.

Interdomain mobility in di-ubiquitin revealed by NMR - Ryabov,Yaroslav; Fushman, David (Proteins: Structure, Function, and Bioinformatics, 2006)
Domain orientation and dynamics can play an essential role in the function of multidomain proteins. Lys48-linked polyubiquitin chains, the principal signal for proteasomal protein degradation, adopt a closed conformation at physiological conditions, in which the functionally important residues Leu8, Ile44, and Val70 are sequestered at the interdomain interface. This interface must open in order for these groups to become available for interactions with various chain-recognition factors. Knowledge of the mechanism of domain motion leading to the opening of the interdomain interface in polyubiqutin is, therefore, essential for the understanding of the processes controlling molecular recognition events in polyubiquitin signaling. Here we use NMR to characterize the interdomain dynamics that open the interface in a di-ubiquitin chain. This process occurs via domain reorientations on a 10-ns time scale and with the amplitudes that are sufficient for making functionally important hydrophobic residues in polyubiquitin available for direct interactions with various ubiquitin-binding factors. The analysis revealed the structures of the interconverting conformational states of di-ubiquitin and the rates and amplitudes of this process at near-physiological and acidic pH. The proposed mechanism of domain reorientation is quite general and could serve as a paradigm of interdomain mobility in other multidomain systems. Proteins 2006. © 2006 Wiley-Liss, Inc.
Keywords: anisotropic diffusion; domain motion; interdomain orientation; polyubiquitin; spin relaxation

Machine Learning Meets Agent-Based Modeling: When not to go to A Bar - Rand, William (Proceedings of Agent Based Simulation, 2006)
One of the promises of ABM is the ability to have adaptive agents make decisions inchanging environments. Though great work has been done using adaptive agents in ABM, more research into the theoretical understanding of these systems would be useful. Adaptive agents have already been studied within machine learning (ML)—an area of artificial intelligence specifically concerned with adaptation and building internal models. The first part of this paper presents a framework for understanding ML as a component of ABM, and describes how different ML techniques can be incorporated into some ABMs. At the high level this framework consists of two cycles that involve evaluating input, making decisions and then generating output. Within this generalized framework, the ML algorithm is using the ABM as an environment and a reward generator, while the ABM is using the ML algorithm to refine the internal models of the agents. There are many details that must be answered before any ML technique can be incorporated into an ABM. In this paper I start to explore some guidelines for how to more closely integrate ABM and ML and will discuss complications that arise when combining ABM and ML techniques. To illustrate some of these issues, I will describe an integration of a ML technique within the El Farol Bar Problem. I will conclude with some discussion of this integration and a look toward future research.

Metagenomic Analysis of the Human Distal Gut Microbiome - Gill,Steven R.; Pop, Mihai; DeBoy,Robert T.; Eckburg,Paul B; Turnbaugh,Peter J; Samuel,Buck S; Gordon,Jeffrey I; Relman,David A; Fraser-Liggett,Claire M; Nelson,Karen E. (Science, 2006)
The human intestinal microbiota is composed of 1013 to 1014 microorganisms whose collective genome (“microbiome”) contains at least 100 times as many genes as our own genome. We analyzed ∼78 million base pairs of unique DNA sequence and 2062 polymerase chain reaction–amplified 16S ribosomal DNA sequences obtained from the fecal DNAs of two healthy adults. Using metabolic function analyses of identified genes, we compared our human genome with the average content of previously sequenced microbial genomes. Our microbiome has significantly enriched metabolism of glycans, amino acids, and xenobiotics; methanogenesis; and 2-methyl-d-erythritol 4-phosphate pathway–mediated biosynthesis of vitamins and isoprenoids. Thus, humans are superorganisms whose metabolism represents an amalgamation of microbial and human attributes.

Method and System for Object Surveillance and Real Time Activity Recognition - Yang Ran; Chellapa, Rama; Qinfen Zheng (2006)
Method and system for objects surveillance and real-time activity recognition is based on analysis of spatio-temporal images of individuals under surveillance where a spatio-temporal volume occupied by each individual is decomposed by crossing the same at specific heights to form 2-dimensional slices, each containing representation of trajectory of the motion of corresponding portions of the individual body. The symmetry of the trajectories (Gait DNA) is analyzed and classified to generate data indicative of a type of activity of the individual based on the symmetry or asymmetry of the Gait DNA in each 2-dimensional slice. An effective occlusion handling ability is implemented which permits to restore the occluded silhouette of an individual.

Model based verification and validation of distributed control architectures - Ray,A.; Cleaveland, Rance; Jiang,S.; Fuhrman,T. (Proceedings of Convergence Convergence International Congress and Exposition on Transportation Electronics, Detroit, USA, 2006)

A model for computer frustration: the role of instrumental and dispositional factors on incident, session, and post-session frustration and mood - Bessière,Katie; Newhagen,John E.; Robinson,John P.; Shneiderman, Ben (Computers in Human Behavior, 2006)
Frustration is almost universally accepted as the emotional outcome of a negative computing experience. Despite the wide use of the term, however, it has not been rigorously conceptualized as a factor in the study of the human–computer interface. This project sets out to explicate frustration as a pre-emotional state generated by the user’s appraisal of the interface as an impediment to goal attainment, and looks at how user characteristics, such as self-efficacy, relate to it. This project employed episode report methodology to capture data from 144 computer users’ reports of actual frustrating events as they took place. Diaries taken as users worked at their everyday tasks yield detailed data about the problems they encountered and included information about session length and an estimate of the time lost due to the experiences. Outcomes were measured as either situational or dispositional factors. Situational factors, having to do with specific events, predicted incident frustration. However, disposition variables, especially user self-efficacy, were much stronger, predicting incident and session frustration, and post-session mood. One surprising outcome was the failure of demographic variables as predictors of frustration.
Keywords: Efficacy; Emotion; Frustration; Mood; problem solving; usability

Modeling Age Progression in Young Faces - Ramanathan,N.; Chellapa, Rama (Computer Vision and Pattern Recognition, 2006 IEEE Computer Society Conference on, 2006)
We propose a craniofacial growth model that characterizes growth related shape variations observed in human faces during formative years. The model draws inspiration from the #145;revised #146; cardioidal strain transformation model proposed in psychophysical studies related to craniofacial growth. The model takes into account anthropometric evidences collected on facial growth and hence is in accordance with the observed growth patterns in human faces across years. We characterize facial growth by means of growth parameters defined over facial landmarks often used in anthropometric studies. We illustrate how the age-based anthropometric constraints on facial proportions translate into linear and non-linear constraints on facial growth parameters and propose methods to compute the optimal growth parameters. The proposed craniofacial growth model can be used to predict one #146;s appearance across years and to perform face recognition across age progression. This is demonstrated on a database of age separated face images of individuals under 18 years of age.

Modeling and Simulation of the Escalation Archetype in Computer Security - Rosenfeld,S. N.; Rus,I.; Michel Cukier (Symposium on Simulation Software Security (SSSS 06), 2006)
To support decision-making for mitigating computer security risks, we developed and used a system dynamics model of security aspects of an enterprise system. We describe the notion of archetypes in general and the escalation archetype specifically, showing how it can arise in computer security. We show the effects of this instance of escalation through simulation of our model, consider the effects of changes in the simulation, and discuss the prognoses drawn from the archetype literature and their applicability to security.

Modeling the Symptomatic Fixes Archetype in Enterprise Computer Security - Rosenfeld,S. N.; Rus,I.; Michel Cukier (2006)
To support decision-making for security-risk mitigation and the appropriate selection of security countermeasures, we propose a system dynamics model of the security aspects of an enterprise system. We developed such an executable model, incorporating the concept of archetypes. We present here one archetype for computer security, namely symptomatic fixes (or shifting the burden). Using simulation, we show one instance of how this archetype can be used for recognizing and diagnosing typical situations, as well as for fixing problems. The global effects of changes and behavioral trends are examined, and other instances of symptomatic fixes in security are described as well
Keywords: business data processing; decision making; decision-making; enterprise computer security; human factors; security of data; security-risk mitigation; symptomatic fixes archetype modeling; system dynamics model; system modeling

New lower bounds for oblivious routing in undirected graphs - Hajiaghayi, Mohammad T.; Kleinberg,R. D; Leighton,T.; R\äcke,H. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

Numerical computation of the Green?s function for two-dimensional finite-size photonic crystals of infinite length - Seydou,F.; Ramahi,Omar M.; Duraiswami, Ramani; Seppänen,T. (Optics ExpressOpt. Express, 2006)
We develop a numerical algorithm that computes the Green’s function of Maxwell equation for a 2D finite-size photonic crystal, composed of rods of arbitrary shape. The method is based on the boundary integral equation, and a Nyström discretization is used for the numerical solution. To provide an exact solution that validates our code we derive multipole expansions for circular cylinders using our integral equation approach. The numerical method performs very well on the test case. We then apply it to crystals of arbitrary shape and discuss the convergence.
Keywords: Diffraction and gratings; Multiple scattering

Oblivious network design - Gupta,A.; Hajiaghayi, Mohammad T.; R\äcke,H. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

Opinion Analysis in Document Databases - Cesarano,C.; Dorr, Bonnie J; Picariello, A.; Reforgiato,D.; Sagoff,A.; V.S. Subrahmanian (Proc. AAAI Spring Symposium on Computational Approaches to Analyzing Weblogs, Stanford, CA, 2006)
There are numerous applications in which we would like toassess what opinions are being expressed in text documents. Forr example, Martha Stewart’s company may have wished to assess the degree of harshness of news articles about her in the recent past. Likewise, a World Bank official may wish to as- sess the degree of criticism of a proposed dam in Bangladesh. The ability to gauge opinion on a given topic is therefore of critical interest. In this paper, we develop a suite of algo- rithms which take as input, a set D of documents as well as a topic t, and gauge the degree of opinion expressed about topic t in the set D of documents. Our algorithms can return both a number (larger the number, more positive the opinion) as well as a qualitative opinion (e.g. harsh, complimentary). We as- sess the accuracy of these algorithms via human experiments and show that the best of these algorithms can accurately re- flect human opinions. We have also conducted performance experiments showing that our algorithms are computationally fast.

Parallel syntactic annotation of multiple languages - Rambow,O.; Dorr, Bonnie J; Farwell,D.; Green,R.; Habash,N.; Helmreich,S.; Hovy,E.; Levin,L.; Miller,K.J.; Mitamura,T.; others (Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC2006). Genoa, Italy, 2006)
This paper describes an effort to investigate the incrementally deepening development of an interlingua notation, validated by humanannotation of texts in English plus six languages. We begin with deep syntactic annotation, and in this paper present a series of annotation manuals for six different languages at the deep-syntactic level of representation. Many syntactic differences between languages are removed in the proposed syntactic annotation, making them useful resources for multilingual NLP projects with semantic components.

Participatory, embodied, multi-agent simulation - Blikstein,Paulo; Rand, William; Wilensky,Uri (Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, 2006)
We will demonstrate the integration of a software-based multi-agent modeling platform with a participatory simulation environment and real-time control over a physical agent (robot). Both real and virtual participants will be able to act as agents in a simulation that will control a physical agent. The backbone of this demonstration is a widely used, freely available, mature modeling platform known as NetLogo.
Keywords: embedded agents; multi-agent simulation; participatory simulation; ROBOTICS; Sensors

PCFGs with syntactic and prosodic indicators of speech repairs - Hale,John; Shafran,Izhak; Yung,Lisa; Dorr, Bonnie J; Harper,Mary; Krasnyanskaya,Anna; Lease,Matthew; Liu,Yang; Roark,Brian; Snover,Matthew; Stewart,Robin (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
A grammatical method of combining two kinds of speech repair cues is presented. One cue, prosodic disjuncture, is detected by a decision tree-based ensemble classifier that uses acoustic cues to identify where normal prosody seems to be interrupted (Lickley, 1996). The other cue, syntactic parallelism, codifies the expectation that repairs continue a syntactic category that was left unfinished in the reparandum (Levelt, 1983). The two cues are combined in a Treebank PCFG whose states are split using a few simple tree transformations. Parsing performance on the Switchboard and Fisher corpora suggests that these two cues help to locate speech repairs in a synergistic way.

Probabilistic, Logical and Relational Learning-Towards a Synthesis - De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H; Lloyd,J. W; Sears,T. D; Milch,B.; Marthi,B.; Russell,S.; Sontag,D. (Dagstuhl Seminar Proceedings, 2006)

Processing approximate aggregate queries in wireless sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Information Systems, 2006)
In-network data aggregation has been recently proposed as an effective means to reduce the number of messages exchanged in wireless sensor networks. Nodes of the network form an aggregation tree, in which parent nodes aggregate the values received from their children and propagate the result to their own parents. However, this schema provides little flexibility for the end-user to control the operation of the nodes in a data sensitive manner. For large sensor networks with severe energy constraints, the reduction (in the number of messages exchanged) obtained through the aggregation tree might not be sufficient. In this paper, we present new algorithms for obtaining approximate aggregate statistics from large sensor networks. The user specifies the maximum error that he is willing to tolerate and, in turn, our algorithms program the nodes in a way that seeks to minimize the number of messages exchanged in the network, while always guaranteeing that the produced estimate lies within the specified error from the exact answer. A key ingredient to our framework is the notion of the residual mode of operation that is used to eliminate messages from sibling nodes when their cumulative change to the computed aggregate is small. We introduce two new algorithms, based on potential gains, which adaptively redistribute the error thresholds to those nodes that benefit the most and try to minimize the total number of transmitted messages in the network. Our techniques significantly reduce the number of messages, often by a factor of 10 for a modest 2% relative error bound, and consistently outperform previous techniques for computing approximate aggregates, which we have adapted for sensor networks.
Keywords: Aggregate queries; approximation; sensor networks

ProMo-A Scalable and Efficient Framework for Online Data Delivery - Roitman,H.; Gal,A.; Raschid, Louiqa (Lecture notes in computer science, 2006)

Query planning in the presence of overlapping sources - Bleiholder,J.; Khuller, Samir; Naumann,F.; Raschid, Louiqa; Wu,Y. (Advances in Database Technology-EDBT 2006, 2006)

Query planning in the presence of overlapping sources - Bleiholder,J.; Khuller, Samir; Naumann,F.; Raschid, Louiqa; Wu,Y. (Advances in Database Technology-EDBT 2006, 2006)
Navigational queries on Web-accessible life science sources pose unique query optimization challenges. The objects in these sources are interconnected to objects in other sources, forming a large and complex graph, and there is an overlap of objects in the sources. Answering a query requires the traversal of multiple alternate paths through these sources. Each path can be associated with the benefit or the cardinality of the target object set (TOS) of objects reached in the result. There is also an evaluation cost of reaching the TOS.We present dual problems in selecting the best set of paths. The first problem is to select a set of paths that satisfy a constraint on the evaluation cost while maximizing the benefit (number of distinct objects in the TOS). The dual problem is to select a set of paths that satisfies a threshold of the TOS benefit with minimal evaluation cost. The two problems can be mapped to the budgeted maximum coverage problem and the maximal set cover with a threshold. To solve these problems, we explore several solutions including greedy heuristics, a randomized search, and a traditional IP/LP formulation with bounds. We perform experiments on a real-world graph of life sciences objects from NCBI and report on the computational overhead of our solutions and their performance compared to the optimal solution.

Query Rewriting in the Semantic Web7 - Vidal,Maria Esther; Raschid, Louiqa; Marquez,Natalia; Cardenas,Marelis; Yao Wu (Data Engineering Workshops, 22nd International Conference on, 2006)
The widespread explosion of Web accessible resources has lead to a new challenge of locating all relevant resources and identifying the best ones to answer a query. This challenge has to address the difficult task of ranking the resources based on user needs, as well as the more expensive computational task of determining all the solutions to answer a query. In this paper, we define a Top K problem for query rewriting on the Semantic Web. We first introduce a three level data model composed of the ontology level, the physical level of the physical resources, and the data level composed of the entries in the different resources. We present a query language for Top K navigational queries over ontology concepts. We then sketch the outline of an efficient search algorithm to compute an approximation of the Top K rewriting options to produce source paths among the physical resources. We briefly discuss the results of an experimental study

Real-Time Distributed Algorithms for Visual and Battlefield Reasoning - Davis, Larry S.; Basili, Victor R.; V.S. Subrahmanian; Reggia, James A.; Aloimonos, J. (MARYLAND UNIV COLLEGE PARK OFFICE OF RESEARCH ADMINISTRATION AND ADVANCEMENT, 2006)
Information is key to the success of the next generation battlefield. There is a critical need to determine, in real-time, what the enemy is doing, and to interpret that information in the context of past related events. In this project we examined two aspects of this issue: development of a high-level task definition language for tasking a network of sensors to carry out given objectives, and interpreting recounted events so that past related scenarios could be automatically identified from a case database.

Real-Time Human Detection, Tracking, and Verification in Uncontrolled Camera Motion Environments - Hussein,M.; Abd-Almageed, Wael; Yang Ran; Davis, Larry S. (Computer Vision Systems, 2006 ICVS '06. IEEE International Conference on, 2006)
In environments where a camera is installed on a freely moving platform, e.g. a vehicle or a robot, object detection and tracking becomes much more difficult. In this paper, we presents a real time system for human detection, tracking, and verification in such challenging environments. To deliver a robust performance, the system integrates several computer vision algorithms to perform its function: a human detection algorithm, an object tracking algorithm, and a motion analysis algorithm. To utilize the available computing resources to the maximum possible extent, each of the system components is designed to work in a separate thread that communicates with the other threads through shared data structures. The focus of this paper is more on the implementation issues than on the algorithmic issues of the system. Object oriented design was adopted to abstract algorithmic details away from the system structure.

Reranking for Sentence Boundary Detection in Conversational Speech - Roark,B.; Liu,Yang; Harper,M.; Stewart,R.; Lease,M.; Snover,M.; Shafran,I.; Dorr, Bonnie J; Hale,J.; Krasnyanskaya,A.; Yung,L. (2006 IEEE International Conference on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings, 2006)
We present a reranking approach to sentence-like unit (SU) boundary detection, one of the EARS metadata extraction tasks. Techniques for generating relatively small n-best lists with high oracle accuracy are presented. For each candidate, features are derived from a range of information sources, including the output of a number of parsers. Our approach yields significant improvements over the best performing system from the NIST RT-04F community evaluation
Keywords: Automatic speech recognition; conversational speech; data mining; Ear; EARS metadata extraction tasks; Feature extraction; hidden Markov models; meta data; Model driven engineering; NIST; NIST RT-04F community evaluation; oracle accuracy; performance evaluation; reranking; sentence-like unit boundary detection; Speech processing; Speech recognition; Telephony

Revealing botnet membership using DNSBL counter-intelligence - Ramachandran,A.; Feamster, Nick; Dagon,D. (Proc. 2nd USENIX Steps to Reducing Unwanted Traffic on the Internet, 2006)
Botnets—networks of (typically compromised) machines—are often used for nefarious activities (e.g., spam, click fraud, denial-of-service attacks, etc.). Identifying members of botnets could help stem these attacks, but passively detecting botnet membership (i.e., without disrupting the operation of the botnet) proves to be difficult. This paper studies the effectiveness of monitoring lookups to a DNS-based blackhole list (DNSBL) to expose botnet membership. We perform counter-intelligence based on the insight that botmasters themselves perform DNSBL lookups to determine whether their spamming bots are blacklisted. Using heuristics to identify which DNSBL lookups are perpetrated by a botmaster performing such reconnaissance, we are able to compile a list of likely bots. This paper studies the prevalence of DNSBL reconnaissance observed at a mirror of a well-known blacklist for a 45-day period, identifies the means by which botmasters are performing reconnaissance, and suggests the possibility of using counter-intelligence to discover likely bots. We find that bots are performing reconnaissance on behalf of other bots. Based on this finding, we suggest counter-intelligence techniques that may be useful for early bot detection.

Robust fuzzy extractors and authenticated key agreement from close secrets - Dodis,Y.; Katz, Jonathan; Reyzin,L.; Smith,A. (Advances in Cryptology-CRYPTO 2006, 2006)
Consider two parties holding correlated random variables W and W′, respectively, that are within distance t of each other in some metric space. These parties wish to agree on a uniformly distributed secret key R by sending a single message over an insecure channel controlled by an all-powerful adversary. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret SK that they can use to generate a sequence of session keys R j using multiple pairs {(W j , W′ j )}. The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded storage model with errors.Our results improve upon previous work in several respects: – The best previous solution for the keyless case with no errors (i.e., t=0) requires the min-entropy of W to exceed 2|W|/3. We show a solution when the min-entropy of W exceeds the minimal threshold |W|/2. – Previous solutions for the keyless case in the presence of errors (i.e., t>0) required random oracles. We give the first constructions (for certain metrics) in the standard model. – Previous solutions for the keyed case were stateful. We give the first stateless solution.

Septaplex PCR assay for rapid identification of Vibrio cholerae including detection of virulence and int SXT genes - Mantri,Chinmay K.; Mohapatra,Saswat S.; Ramamurthy,Thandavarayan; Ghosh,Raikamal; Rita R Colwell; Singh,Durg V. (FEMS Microbiology Letters, 2006)
In this study, we describe a septaplex PCR assay for rapid identification of Vibrio cholerae including detection of the virulence and intsxt genes. Conditions were optimized to amplify fragments of ISRrRNA (encoding for 16S–23S rRNA gene, Intergenic spacer regions), O1rfb (O1 serogroup specific rfb), O139rfb (O139 serogroup specific rfb), ctxA (cholera toxin subunit A), tcpA (toxin coregulated pilus), and intsxt (sxt integron) simultaneously in a single PCR. The septaplex PCR was evaluated using 211 strains of V. cholerae and six water samples for in situ testing. PCR results were correlated with genotype data obtained by individual PCR and slot-blot assays. The one-step PCR described here can be used to identify V. cholerae accurately and rapidly. Also, the virulence and intsxt genes can be simultaneously detected, providing a useful method for monitoring pathogenic, intsxt-positive and nonpathogenic, intsxt-negative V. cholerae serogroups both in the environment and clinical settings.
Keywords: DETECTION; intsxt; septaplex PCR; Vibrio cholerae; virulence

A Software Architectural Approach to Security by Design - Ray,A.; Cleaveland, Rance (Computer Software and Applications Conference, 2006. COMPSAC '06. 30th Annual International, 2006)
This paper shows how an architecture description notation that has support for timed events can be used to provide a meta-language for specifying exact communication semantics. The advantages of such an approach is that a designer is made fully aware of the ramifications of her design choices so that an attacker can no longer take advantage of hidden assumptions
Keywords: architecture description notation; Clocks; communication semantics; Computer architecture; computer crime; computer security; Connectors; Costs; Degradation; Delay; Educational institutions; security design; security of data; Software architecture; software engineering

SParseval: Evaluation metrics for parsing speech - Roark,B.; Harper,M.; Charniak,E.; Dorr, Bonnie J; Johnson,M.; Kahn,J.; Liu,Y.; Ostendorf,M.; Hale,J.; Krasnyanskaya,A.; others (Proc. LREC, 2006)
While both spoken and written language processing stand to benefit from parsing, the standard Parseval metrics (Black et al., 1991) andtheir canonical implementation (Sekine and Collins, 1997) are only useful for text. The Parseval metrics are undefined when the words input to the parser do not match the words in the gold standard parse tree exactly, and word errors are unavoidable with automatic speech recognition (ASR) systems. To fill this gap, we have developed a publicly available tool for scoring parses that implements a variety of metrics which can handle mismatches in words and segmentations, including: alignment-based bracket evaluation, alignment-based dependency evaluation, and a dependency evaluation that does not require alignment. We describe the different metrics, how to use the tool, and the outcome of an extensive set of experiments on the sensitivity of the metrics.

Special Issue on Biometrics: Algorithms and Applications - Chellapa, Rama; Phillips, J.; Reynolds, D. (Proceedings of the IEEE, 2006)

Stabilization and Mosaicing of Airborne Videos - Ramachandran, M.; Chellapa, Rama (Image Processing, 2006 IEEE International Conference on, 2006)
We present an algorithm for stabilizing low-quality and low-resolution video sequences obtained from UAVs and MAVs flying over a predominantly planar terrain. The problem is important for the processing of videos captured from airborne platforms where most of the image region gives little information about the image-motion. The algorithm consists of approximately aligning the images using phase correlation, then refining the transformation parameters using available optical flow measurements and finally performing a minimization of the image difference by carefully selecting the image regions to make the iterations converge. In the second part of the paper, we describe an algorithm for camera ego-motion estimation by incorporating available metadata along with the video sequence. The availability of metadata such as IMU measurements provides a good initial solution for the camera orientation and helps the iterations converge faster by reducing the search space
Keywords: airborne; analysis; image; cameras; convergence; low-resolution; ego-motion; estimation; iterations; flow; measurement; video; mosaicing; camera; MOTION; resolution; image; segmentation; image; sequence; optical; sequences; video; stabilization; image; video; Videos

Stigmergic self-assembly of prespecified artificial structures in a constrained and continuous environment - Grushin,A.; Reggia, James A. (Integrated Computer-Aided Engineering, 2006)

The turbulence structure of shockwave and boundary layer interaction in a compression corner - Martin, M.P; Smits,A.; Wu,M.; Ringuette,M. (44th AIAA Aerospace Meeting and Exhibit, 2006)
Shockwave and turbulent boundary layer interactions (STBLI) result in intense localizedheating rates and pressure loads, making them extremely important flow features that must be identified for engineering design. The absence of detailed and complete experimental and numerical data at the same flow and boundary conditions is one of the major stumbling blocks in the development of accurate turbulence models for the prediction of STBLI. We use a set of direct numerical simulation data (Wu & Martin, 2006) that has been validated against experiments (Bookey et al., 2005) at the same conditions to present detailed flow features of the STBLI over a compression corner at Mach 3 and low Reynolds number with Reθ=2100. Details regarding the evolution of the turbulence structure angle, characteristic streamwise length scales, and hairpin packets through the interaction are presented. The three-dimensionality of the turbulence field and main shock are illustrated and the strength of shocks and shocklets through the interaction are considered.

Understanding the network-level behavior of spammers - Ramachandran,Anirudh; Feamster, Nick (Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, 2006)
This paper studies the network-level behavior of spammers, including: IP address ranges that send the most spam, common spamming modes (e.g., BGP route hijacking, bots), how persistent across time each spamming host is, and characteristics of spamming botnets. We try to answer these questions by analyzing a 17-month trace of over 10 million spam messages collected at an Internet "spam sinkhole", and by correlating this data with the results of IP-based blacklist lookups, passive TCP fingerprinting information, routing information, and botnet "command and control" traces.We find that most spam is being sent from a few regions of IP address space, and that spammers appear to be using transient "bots" that send only a few pieces of email over very short periods of time. Finally, a small, yet non-negligible, amount of spam is received from IP addresses that correspond to short-lived BGP routes, typically for hijacked prefixes. These trends suggest that developing algorithms to identify botnet membership, filtering email messages based on network-level properties (which are less variable than email content), and improving the security of the Internet routing infrastructure, may prove to be extremely effective for combating spam.
Keywords: BGP; botnet; network management; Security; spam

Verification and Validation through Replication: A Case Study Using Axelrod and Hammond’s Ethnocentrism Model - Rand, William; Wilensky,U. (North American Association for Computational Social and Organization Sciences (NAACSOS), 2006)
Recent years have seen a proliferation of agent-based models (ABMs), but with the exceptionof a few "classic" models, most of these models have never been replicated. We argue that replication has even greater benefits when applied to computational models than when applied to physical experiments. Replication affects model verification, in that it aids in determining if the implemented model reflects the conceptual model. It affects model validation, since a replication of a conceptual model may change the output from an implemented model and thus alter the correspondence between the model and the real world. Replication also affects validation by forcing the model developer and replicator to re-examine assumptions made in the original model. In addition replication fosters shared understanding of the details of modeling decisions within the research community. To facilitate the practice of replication, we argue for the creation of standards for both how to replicate models and how to evaluate the replication. In this paper, we present a case study of our attempt to replicate an ABM developed by Axelrod and Hammond. We detail our effort to replicate that model and the challenges that arose in recreating the model and in determining if the replication was successful.

Very fast optimal bandwidth selection for univariate kernel density estimation - Raykar,Vikas Chandrakant; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR-2005-73, 2006)
Most automatic bandwidth selection procedures for kernel density estimates require estimation of quantities involvingthe density derivatives. Estimation of modes and inflexion points of densities also require derivative estimates. The computational complexity of evaluating the density derivative at M evaluation points given N sample points from the density is O(MN). In this paper we propose a computationally efficient $ε$-exact approximation algorithm for univariate, Gaussian kernel based, density derivative estimation that reduces the computational complexity from O(MN) to linear order (O(N+M)). The constant depends on the desired arbitrary accuracy, $ε$. We apply the density derivative evaluation procedure to estimate the optimal bandwidth for kernel density estimation, a process that is often intractable for large data sets. For example for N = M = 409,600 points while the direct evaluation of the density derivative takes around 12.76 hours the fast evaluation requires only 65 seconds with an error of around $10^{-12)$. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. We demonstrate the speedup achieved on the bandwidth selection using the ``solve-the-equation plug-in method'' [18]. We also demonstrate that the proposed procedure can be extremely useful for speeding up exploratory projection pursuit techniques.
Keywords: Approximation algorithms; computational statistics; fast gauss transform; kernel density estimation; projection pursuit

Visualization Support for Fusing Relational, Spatio-Temporal Data: Building Career Histories - Blythe,Jim; Patwardhan,Mithila; Oates,Tim; desJardins, Marie; Rheingans,Penny (Information Fusion, 2006 9th International Conference on, 2006)
Many real-world domains resist analysis because they are best characterized by a variety of data types, including relational, spatial, and temporal components. Examples of such domains include disease outbreaks, criminal networks, and the World-Wide Web. We present two types of visualizations based on physical metaphors that facilitate fusion, analysis, and deep understanding of relational, spatio-temporal data. The first visualization is based on the metaphor of fluid flow through elastic pipes, and the second on wave propagation. We discuss both types of visualizations in the context of fusing information about the activities of scientists over time with the goal of constructing career histories

What Is the Range of Surface Reconstructions from a Gradient Field? - Agrawal,Amit; Raskar,Ramesh; Chellapa, Rama (Computer Vision – ECCV 2006Computer Vision – ECCV 2006, 2006)
We propose a generalized equation to represent a continuum of surface reconstruction solutions of a given non-integrable gradient field. We show that common approaches such as Poisson solver and Frankot-Chellappa algorithm are special cases of this generalized equation. For a N × N pixel grid, the subspace of all integrable gradient fields is of dimension N 2 – 1. Our framework can be applied to derive a range of meaningful surface reconstructions from this high dimensional space. The key observation is that the range of solutions is related to the degree of anisotropy in applying weights to the gradients in the integration process. While common approaches use isotropic weights, we show that by using a progression of spatially varying anisotropic weights, we can achieve significant improvement in reconstructions. We propose (a) α-surfaces using binary weights, where the parameter α allows trade off between smoothness and robustness, (b) M-estimators and edge preserving regularization using continuous weights and (c) Diffusion using affine transformation of gradients. We provide results on photometric stereo, compare with previous approaches and show that anisotropic treatment discounts noise while recovering salient features in reconstructions.

Widgets, Planets, and Demons: the Case for the Integration of Human, Embedded, and Virtual Agents via Mediation - Rand, William; Blikstein,P.; Wilensky,U. (Proceedings of Swarmfest, 2006)

Word-based alignment, phrase-based translation: What’s the link - Lopez,A.; Resnik, Philip (Proc. of AMTA, 2006)

3D face modeling from monocular video sequences - Roy-Chowdhury, A.; Chellapa, Rama; Gupta, R. (Face Processing: Advanced Modeling and Methods, 2005)
In this chapter we present two algorithms for 3D face modeling from a monocular video sequence. The firstmethod is based on Structure from Motion (SfM), while the second one relies on contour adaptation over time. The SfM based method incorporates statistical measures of quality of the 3D estimate into the reconstruction algorithm. The initial multi-frame SfM estimate is smoothed using a generic face model in an energy function minimization framework. Such a strategy avoids excessively biasing the final 3D estimate towards the generic model. The second method relies on matching a generic 3D face model to the outer contours of a face in the input video sequence, and integrating this strategy over all the frames in the sequence. It consists of an edge-based head pose estimation step, followed by global and local deformations of the generic face model in order to adapt it to the actual 3D face. This contour adaptation approach is able to separate the geometric subtleties of the human head from the variations in shading and texture, and it does not rely on finding accurate point correspondences across frames. Detailed experimental evaluation of both the methods along with reconstructed 3D models is presented.

Aggregate operators in probabilistic databases - Ross,Robert; V.S. Subrahmanian; Grant,John (J. ACM, 2005)
Though extensions to the relational data model have been proposed in order to handle probabilistic information, there has been very little work to date on handling aggregate operators in such databases. In this article, we present a very general notion of an aggregate operator and show how classical aggregation operators (such as COUNT, SUM, etc.) as well as statistical operators (such as percentiles, variance, etc.) are special cases of this general definition. We devise a formal linear programming based semantics for computing aggregates over probabilistic DBMSs, develop algorithms that satisfy this semantics, analyze their complexity, and introduce several families of approximation algorithms that run in polynomial time. We implemented all of these algorithms and tested them on a large set of data to help determine when each one is preferable.
Keywords: Aggregates; probabilistic relational databases

An algebraic approach to surface reconstruction from gradient fields - Agrawal,A.; Chellapa, Rama; Raskar, R. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
Several important problems in computer vision such as shape from shading (SFS) and photometric stereo (PS) require reconstructing a surface from an estimated gradient field, which is usually non-integrable, i.e. have non-zero curl. We propose a purely algebraic approach to enforce integrability in discrete domain. We first show that enforcing integrability can be formulated as solving a single linear system Ax =b over the image. In general, this system is under-determined. We show conditions under which the system can be solved and a method to get to those conditions based on graph theory. The proposed approach is non-iterative, has the important property of local error confinement and can be applied to several problems. Results on SFS and PS demonstrate the applicability of our method.
Keywords: algebra; algebraic; approach; Computer; confinement; discrete; domain; error; field; from; gradient; graph; image; integrability; linear; local; methods; photometric; reconstruction; shading; SHAPE; stereo; surface; system; theory; vision

An Algebraic Theory Of Boundary Crossing Transitions - Ray,Arnab; Cleaveland, Rance; Skou,Arne (Electronic Notes in Theoretical Computer Science, 2005)
This paper gives a process-algebraic semantics for the hierarchical state machine (HSM) fragment of Statecharts, in which state transitions are permitted to cross state boundaries. Although frowned upon by researchers as promoting unstructured modeling, such transitions are used extensively in practice to model parameterized start states and conditional exit states. The purpose of this work is to develop a compositional semantics for HSMs that may be fit together with compositional semantic accounts for Statecharts without boundary-crossing transitions in order to arrive at a compositional theory for virtually the whole Statecharts language. Our technical development consists of a process algebra for HSMs that is equipped with an operational semantics, an argument that bisimulation is a congruence for the algebra, a syntax-directed translation procedure for HSMs into the process algebra, and an equational axiomatization of the algebra.
Keywords: Compositional Semantics; Formal Methods; Process algebra; Statecharts

Approximate expressions for the mean and the covariance of the maximum likelihood estimator for acoustic source localization - Raykar,V.C.; Duraiswami, Ramani (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
Acoustic source localization using multiple microphones can be formulated as a maximum likelihood estimation problem. The estimator is implicitly defined as the minimum of a certain objective function. As a result, we cannot get explicit expressions for the mean and the covariance of the estimator. We derive approximate expressions for the mean vector and covariance matrix of the estimator using Taylor's series expansion of the implicitly defined estimator. The validity of our expressions is verified by Monte-Carlo simulations. We also study the performance of the estimator for different microphone array configurations.
Keywords: (mathematics); acoustic; approximate; approximation; array; array; covariance; estimation; expansion; expressions; function; likelihood; localization; matrices; matrix; maximum; mean; microphone; objective; processing; series; signal; source; Taylor; theory; vector; vectors

Architecting and Implementing Versatile Dependability - Tudor Dumitras; Srivastava, Deepti; Narasimhan, Priya (Architecting Dependable Systems III, 2005)
Distributed applications must often consider and select the appropriate trade-offs among three important aspects – fault-tolerance, performance and resources. We introduce a novel concept, called versatile dependability, that provides a framework for analyzing and reasoning about these trade-offs in dependable software architectures. We present the architecture of a middleware framework that implements versatile dependability by providing the appropriate ”knobs” to tune and re-calibrate the trade-offs. Our framework can adjust the properties and the behavior of the system at development-time, at deployment-time, and throughout the application’s life-cycle. This renders the versatile dependability approach useful both to applications that require static fault-tolerance configurations supporting the loss/addition of resources and changing workloads, as well as to applications that evolve in terms of their dependability requirements. Through a couple of specific examples, one on adapting the replication style at runtime and the other on tuning the system scalability under given constraints, we demonstrate concretely how versatile dependability can provide an extended coverage of the design space of dependable distributed systems.
Keywords: Operating systems; software engineering

Background learning for robust face recognition with PCA in the presence of clutter - Rajagopalan, AN; Chellapa, Rama; Koterba, N.T. (Image Processing, IEEE Transactions on, 2005)
We propose a new method within the framework of principal component analysis (PCA) to robustly recognize faces in the presence of clutter. The traditional eigenface recognition (EFR) method, which is based on PCA, works quite well when the input test patterns are faces. However, when confronted with the more general task of recognizing faces appearing against a background, the performance of the EFR method can be quite poor. It may miss faces completely or may wrongly associate many of the background image patterns to faces in the training set. In order to improve performance in the presence of background, we argue in favor of learning the distribution of background patterns and show how this can be done for a given test image. An eigenbackground space is constructed corresponding to the given test image and this space in conjunction with the eigenface space is used to impart robustness. A suitable classifier is derived to distinguish nonface patterns from faces. When tested on images depicting face recognition in real situations against cluttered background, the performance of the proposed method is quite good with fewer false alarms.
Keywords: Automated; Principal Component Analysis; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Biological; Models; Computer-Assisted; Information Storage and Retrieval; Models; Computer-Assisted; Subtraction Technique; PCA; background learning; clutter; eigenface recognition method; face recognition; linear discriminant; principal component analysis; clutter; eigenvalues and eigenfunctions; face recognition; learning (artificial intelligence); principal component analysis; Algorith; Statistical; Pattern Recognition

Bayesian network learning with abstraction hierarchies and context-specific independence - desJardins, Marie; Rathod,P.; Getoor, Lise (Machine Learning: ECML 2005, 2005)
Context-specific independence representations, such as tree-structured conditional probability tables (TCPTs), reduce the number of parameters in Bayesian networks by capturing local independence relationships and improve the quality of learned Bayesian networks. We previously presented Abstraction-Based Search (ABS), a technique for using attribute value hierarchies during Bayesian network learning to remove unimportant distinctions within the CPTs. In this paper, we introduce TCPT ABS (TABS), which integrates ABS with TCPT learning. Since expert-provided hierarchies may not be available, we provide a clustering technique for deriving hierarchies from data. We present empirical results for three real-world domains, finding that (1) combining TCPTs and ABS provides a significant increase in the quality of learned Bayesian networks (2) combining TCPTs and ABS provides a dramatic reduction in the number of parameters in the learned networks, and (3) data-derived hierarchies perform as well or better than expert-provided hierarchies.

The Bible and multilingual optical character recognition - Kanungo,T.; Resnik, Philip; Mao,S.; Kim,D.W.; Zheng,Q. (Communications of the ACM, 2005)

Bootstrapping parsers via syntactic projection across parallel texts - Hwa,Rebecca; Resnik, Philip; Weinberg, Amy; Cabezas,Clara; Kolak,Okan (Nat. Lang. Eng., 2005)
Broad coverage, high quality parsers are available for only a handful of languages. A prerequisite for developing broad coverage parsers for more languages is the annotation of text with the desired linguistic representations (also known as “treebanking”). However, syntactic annotation is a labor intensive and time-consuming process, and it is difficult to find linguistically annotated text in sufficient quantities. In this article, we explore using parallel text to help solving the problem of creating syntactic annotation in more languages. The central idea is to annotate the English side of a parallel corpus, project the analysis to the second language, and then train a stochastic analyzer on the resulting noisy annotations. We discuss our background assumptions, describe an initial study on the “projectability” of syntactic relations, and then present two experiments in which stochastic parsers are developed with minimal human intervention via projection from English.

Breaking the resource bottleneck for multilingual parsing - Hwa,R.; Resnik, Philip; Weinberg, Amy (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2005)
We propose a framework that enables the acquisition of annotation-heavy resources such as syntacfic dependency tree corpora for low-resource languages by importing linguistic annotations from high-quality English resources. We present a large-scale experiment showing that Chinese dependency trees can be induced by using an English parser, a word alignment package, and a large corpus of sentence-aligned bilingual text. As a part of the experiment, we evaluate the quality of a Chinese parser trained on the induced dependency treebank. We find that a parser trained in this manner out-performs some simple baselines inspite of the noise in the induced treebank. The results suggest that projecting syntactic structures from English is a viable option for acquiring annotated syntactic structures quickly and cheaply. We expect the quality of the induced treebank to improve when more sophisticated filtering and error-correction techniques are applied.

Capital and benefit in social networks - Licamele,Louis; Bilgic,Mustafa; Getoor, Lise; Roussopoulos, Nick (Proceedings of the 3rd international workshop on Link discovery, 2005)
Recently there has been a surge of interest in social networks. Email traffic, disease transmission, and criminal activity can all be modeled as social networks. In this paper, we introduce a particular form of social network which we call a friendship-event network. A friendship-event network describes two inter-related networks. One is a friendship network among a set of actors. The other is an event network that describes events, event organizers and event participants. Within these types of networks, we formulate the notion of capital based on the actor-organizer friendship relationship and the notion of benefit, based on event participation. We ground these definitions in a real-world example of academic collaboration networks, where the actors are researchers, the friendships are collaborations, the events are conferences, the organizers are program committee members and the participants are conference authors. We incorporate a temporal component by considering the notion of an event series. We explore the use of these measures on a data set describing three computer science conferences over the past ten years.

Collective-movement teams for cooperative problem solving - Rodríguez,A.; Reggia, James A. (Integrated Computer-Aided Engineering, 2005)

Comparative Genomics of Trypanosomatid Parasitic Protozoa - El‐Sayed, Najib M.; Myler,Peter J.; Blandin,Gaëlle; Berriman,Matthew; Crabtree,Jonathan; Aggarwal,Gautam; Caler,Elisabet; Renauld,Hubert; Worthey,Elizabeth A.; Hertz-Fowler,Christiane; Ghedin,Elodie; Peacock,Christopher; et al. (Science, 2005)
A comparison of gene content and genome architecture of Trypanosoma brucei, Trypanosoma cruzi, and Leishmania major, three related pathogens with different life cycles and disease pathology, revealed a conserved core proteome of about 6200 genes in large syntenic polycistronic gene clusters. Many species-specific genes, especially large surface antigen families, occur at nonsyntenic chromosome-internal and subtelomeric regions. Retroelements, structural RNAs, and gene family expansion are often associated with syntenic discontinuities that—along with gene divergence, acquisition and loss, and rearrangement within the syntenic regions—have shaped the genomes of each parasite. Contrary to recent reports, our analyses reveal no evidence that these species are descended from an ancestor that contained a photosynthetic endosymbiont.

Content Index to Volume 18 - Kuniavsky,M.; Vaughan,M.; Bederson, Benjamin B.; Shneiderman, Ben; Rau,P.L.P.; from Menus,T.; Lane,D.M.; Napier,H.A.; Peres,S.C.; Sándor,A. (INTERNATIONAL JOURNAL OF HUMAN–COMPUTER INTERACTION, 2005)

Controlled observations of the genetic algorithm in a changing environment: case studies using the shaky ladder hyperplane-defined functions - Rand, William (The University of Michigan, 2005)

A data model and query language to explore enhanced links and paths in life science sources - Mihaila,G.; Naumann,F.; Raschid, Louiqa; Vidal,M. E (Proceedings of the ACM SIGMOD Workshop on The Web and Databases (WebDB), 2005)

Design and implementation of a routing control platform - Caesar,Matthew; Caldwell,Donald; Feamster, Nick; Rexford,Jennifer; Shaikh,Aman; van der Merwe,Jacobus (Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2, 2005)
The routers in an Autonomous System (AS) must distribute the information they learn about how to reach external destinations. Unfortunately, today's internal Border Gateway Protocol (iBGP) architectures have serious problems: a "full mesh" iBGP configuration does not scale to large networks and "route reflection" can introduce problems such as protocol oscillations and persistent loops. Instead, we argue that a Routing Control Platform (RCP) should collect information about external destinations and internal topology and select the BGP routes for each router in an AS. RCP is a logically-centralized platform, separate from the IP forwarding plane, that performs route selection on behalf of routers and communicates selected routes to the routers using the unmodified iBGP protocol. RCP provides scalability without sacrificing correctness. In this paper, we present the design and implementation of an RCP prototype on commodity hardware. Using traces of BGP and internal routing data from a Tier-1 backbone, we demonstrate that RCP is fast and reliable enough to drive the BGP routing decisions for a large network. We show that RCP assigns routes correctly, even when the functionality is replicated and distributed, and that networks using RCP can expect comparable convergence delays to those using today's iBGP architectures.

Detection of denial-of-message attacks on sensor network broadcasts - McCune, J.M.; Elaine Shi; Perrig, A.; Reiter, M.K. (2005)
So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities.
Keywords: authenticated acknowledgments; broadcast channels; broadcast protocols; broadcasting base station; countermeasures; denial-of-message attacks; DoM; game theory; game-theoretic approach; malicious sensor nodes; Mobile computing; optimal attacker; probabilistic detection; probability; Protocols; Sampling methods; secure implicit sampling; sensor network broadcasts; SIS; telecommunication security; Wireless sensor networks

Determining Causes and Severity of End-User Frustration (2002) - Ceaparu,Irina; Lazar,Jonathan; Bessiere,Katie; Robinson,John; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
While computers are beneficial to individuals and society, frequently, users encounter frustrating experiences when using computers. This study attempts to measure, through 111 participants, the frequency, cause, and the level of severity of frustrating experiences. The data showed that frustrating experiences happen on a frequent basis. The applications in which the frustrating experiences happened most frequently were web browsing, e-mail, and word processing. The most-cited causes of frustrating experiences were error messages, dropped network connections, long download times, and hard-to-find features. The time lost due to frustrating experiences ranged from 47-53% of time spent on a computer depending on the location and study method. After discarding extreme cases the time lost was still above 38%. These disturbing results should be a basis for future study.
Keywords: Technical Report

Diagnostic problem solving using swarm intelligence - Lapizco-Encinas,G. C; Reggia, James A. (Swarm Intelligence Symposium, 2005. SIS 2005. Proceedings 2005 IEEE, 2005)

Dictionary-based cross-language retrieval - Levow,G.A.; Oard, Douglas; Resnik, Philip (Information Processing and Management, 2005)

Dictionary-based techniques for cross-language information retrieval - Levow,Gina-Anne; Oard, Douglas; Resnik, Philip (Information Processing & Management, 2005)
Cross-language information retrieval (CLIR) systems allow users to find documents written in different languages from that of their query. Simple knowledge structures such as bilingual term lists have proven to be a remarkably useful basis for bridging that language gap. A broad array of dictionary-based techniques have demonstrated utility, but comparison across techniques has been difficult because evaluation results often span only a limited range of conditions. This article identifies the key issues in dictionary-based CLIR, develops unified frameworks for term selection and term translation that help to explain the relationships among existing techniques, and illustrates the effect of those techniques using four contrasting languages for systematic experiments with a uniform query translation architecture. Key results include identification of a previously unseen dependence of pre- and post-translation expansion on orthographic cognates and development of a query-specific measure for translation fanout that helps to explain the utility of structured query methods.
Keywords: Cross-language information retrieval; Dictionary-based translation; Ranked retrieval

Diverse polyubiquitin interaction properties of ubiquitin-associated domains - Raasi,Shahri; Varadan,Ranjani; Fushman, David; Pickart,Cecile M. (Nature Structural & Molecular Biology, 2005)
The ubiquitin-associated (UBA) domain occurs frequently in proteins involved in ubiquitin-dependent signaling pathways. Although polyubiquitin chain binding is considered to be a defining feature of the UBA domain family, the generality of this property has not been established. Here we have surveyed the polyubiquitin interaction properties of 30 UBA domains, including 16 of 17 occurrences in budding yeast. The UBA domains sort into four classes that include linkage-selective polyubiquitin binders and domains that bind different chains (and monoubiquitin) in a nondiscriminatory manner; one notable class (30%) did not bind any ubiquitin ligand surveyed. The properties of a given UBA domain are conserved from yeast to mammals. Their functional relevance is further suggested by the ability of an ectopic UBA domain to alter the specificity of a deubiquitylating enzyme in a predictable manner. Conversely, non-UBA sequences can modulate the interaction properties of a UBA domain.
Keywords: apoptosis; basic cellular processes; Biochemistry; biophysics; cell biology; cell cycle; cell surface proteins; cell-cell interactions; checkpoints; chromatin; chromatin remodeling; chromatin structure; content; DNA recombination; DNA repair; DNA replication; Gene expression; Genetics; intracellular signaling; journal; macromolecules; mechanism; membrane processes; molecular; molecular basis of disease; molecular biology; molecular interactions; multi-component complexes; nature publishing group; nature structural molecular biology; nucleic acids; protein degradation; protein folding; protein processing; Proteins; regulation of transcription; regulation of translation; RNA; RNA processing; RNAi; signal transduction; single molecule studies; structure and function of proteins; transcription; translation

Dynamic inference of polymorphic lock types - Rose,James; Swamy,Nikhil; Hicks, Michael W. (Science of Computer Programming, 2005)
We present FindLocks, an approach for automatically proving the absence of data races in multi-threaded Java programs, using a combination of dynamic and static analysis. The program in question is instrumented so that when executed it will gather information about locking relationships. This information is then used to automatically generate annotations needed to type check the program using the Race-Free Java type system. Programs that type check are sure to be free from races. We call this technique dynamic annotation inference. We describe the design and implementation of our approach, and our experience applying the tool to a variety of Java programs. We have found that when using a reasonably comprehensive test suite, which is easy for small programs but harder for larger ones, the approach generates useful annotations.
Keywords: Data races; Dynamic analysis; java; Multithreading; Type inference

An empirical study of regression test application frequency - Kim,J. M; Porter, Adam; Rothermel,G. (Software Testing, Verification and Reliability, 2005)

Evolutionary discovery of arbitrary self-replicating structures - PAN,Z.; Reggia, James A. (Computational Science–ICCS 2005, 2005)

An evolutionary testbed for software technology evaluation - Lindvall,M.; Rus,I.; Shull, F.; Zelkowitz, Marvin V; Donzelli,P.; Memon, Atif M.; Basili, Victor R.; Costa,P.; Tvedt,R.; Hochstein, L. (Innovations in Systems and Software Engineering, 2005)
Empirical evidence and technology evaluation are needed to close the gap between the state of the art and the state of the practice in software engineering. However, there are difficulties associated with evaluating technologies based on empirical evidence: insufficient specification of context variables, cost of experimentation, and risks associated with trying out new technologies. In this paper, we propose the idea of an evolutionary testbed for addressing these problems. We demonstrate the utility of the testbed in empirical studies involving two different research technologies applied to the testbed, as well as the results of these studies. The work is part of NASArsquos High Dependability Computing Project (HDCP), in which we are evaluating a wide range of new technologies for improving the dependability of NASA mission-critical systems.

Evolving processing speed asymmetries and hemispheric interactions in a neural network model - Grushin,A.; Reggia, James A. (Neurocomputing, 2005)

EvoSTOC Contributions - Merkle,D.; Middendorf,M.; Scheidler,A.; Avigad,G.; Moshaiov,A.; Brauner,N.; Parsopoulos,K.E.; Vrahatis,M.N.; Rand, William; Riolo,R (Applications of evolutionary computing: EvoWorkshops 2005, EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoMUSART, and EvoSTOC, 2005)

Exploiting partially overlapping channels in wireless networks: Turning a peril into an advantage - Mishra,A.; Rozner,E.; Banerjee,S.; Arbaugh, William A. (Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, 2005)

Extracting the frequencies of the pinna spectral notches in measured head related impulse responses - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2005)
The head related impulse response (HRIR) characterizes the auditory cues created by scattering of sound off a person’s anatomy. The experimentally measured HRIR depends on several factors such as reflections from body parts (torso, shoulder, and knees), head diffraction, and reflection/diffraction effects due to the pinna. Structural models (Algazi et al., 2002; Brown and Duda, 1998) seek to establish direct relationships between the features in the HRIR and the anatomy. While there is evidence that particular features in the HRIR can be explained by anthropometry, the creation of such models from experimental data is hampered by the fact that the extraction of the features in the HRIR is not automatic. One of the prominent features observed in the HRIR, and one that has been shown to be important for elevation perception, are the deep spectral notches attributed to the pinna. In this paper we propose a method to robustly extract the frequencies of the pinna spectral notches from the measured HRIR, distinguishing them from other confounding features. The method also extracts the resonances described by Shaw (1997). The techniques are applied to the publicly available CIPIC HRIR database (Algazi et al., 2001c). The extracted notch frequencies are related to the physical dimensions and shape of the pinna.
Keywords: acoustic wave reflection; acoustic wave scattering; anthropometry; Ear; hearing; physiological models

A fast approximation scheme for probabilistic wavelet synopses - Deligiannakis,A.; Garofalakis,M.; Roussopoulos, Nick (Proceedings of the 17th International Conference on Scientific and Statistical Database Management (SSDBM), 2005)

Fast Computation of Sums of Gaussians in High Dimensions - Raykar,Vikas Chandrakant; Yang,Changjaing; Duraiswami, Ramani; Gumerov, Nail A. (Technical Reports from UMIACS UMIACS-TR-2005-69, 2005)
Evaluating sums of multivariate Gaussian kernels is a key computational task in many problems in computational statistics andmachine 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 $\mathcal{O}(MN)$ to $\mathcal{O}(M+N)$. However, the constant factor in $\mathcal{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 point-wise error bounds. Algorithm details, error bounds, procedure to choose the parameters and numerical experiments are presented. As an example we shows how the proposed method can be used for very fast $ε$-exact multivariate kernel density estimation.
Keywords: Technical Report

A framework for set-oriented computation in inductive logic programming and its application in generalizing inverse entailment - Corrada Bravo, Hector; Page,D.; Ramakrishnan,R.; Shavlik,J.; Costa,V. S (Inductive Logic Programming, 2005)

Gait-based human identification using appearance matching - Kale, A.; Cuntoor, N.; Yegnanarayana,B.; Rajagopalan, A.; Chellapa, Rama (Optical and Digital Techniques for Information Security, 2005)
In this chapter, we present an appearance-based approach for recognizing human gait. Given the gait video of an individual, the images are binarized and the width of the outer contour of the silhouette of that individual is obtained for each image frame. Several gait features are derived from this basic width vector. Temporally ordered sequences of the feature vectors are then used to represent the gait of a person. While matching the feature templates for recognition, dynamic time-warping (DTW), which is a nonlinear time-normalization technique, is used to deal with naturally occurring changes in the walking speeds of individuals. The performance of the proposed method is tested on indoor as well as outdoor gait databases, and the efficacy of different gait features and their noise resilience is studied. The experiments also demonstrate the effect of change in the viewing angle and frame rate of data capture on the accuracy of gait recognition.

The genome of the African trypanosome Trypanosoma brucei - Berriman,M.; Ghedin,E.; Hertz-Fowler,C.; Blandin,G.; Renauld,H.; Bartholomeu,D. C; Lennard,N. J; Caler,E.; Hamlin,N. E; Haas,B.; others (Science, 2005)

The genome of the protist parasite Entamoeba histolytica - Loftus,B.; Anderson,I.; Davies,R.; Alsmark,U. C.M; Samuelson,J.; Amedeo,P.; Roncaglia,P.; Berriman,M.; Hirt,R. P; Mann,B. J; others (Nature, 2005)

The Genome Sequence of Trypanosoma Cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (ScienceScience, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

The Genome Sequence of Trypanosoma cruzi, Etiologic Agent of Chagas Disease - El‐Sayed, Najib M.; Myler,Peter J.; Bartholomeu,Daniella C.; Nilsson,Daniel; Aggarwal,Gautam; Tran,Anh-Nhi; Ghedin,Elodie; Worthey,Elizabeth A.; Delcher,Arthur L.; Blandin,Gaëlle; Westenberger,Scott J.; Caler,Elisabet; et al. (Science, 2005)
Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.

A graph theoretical foundation for integrating RDF ontologies - Udrea,O.; Deng,Y.; Ruckhaus,E.; V.S. Subrahmanian (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2005)
RDF ontologies are rapidly increasing in number. We studythe problem of integrating two RDF ontologies under a given set H of Horn clauses that specify semantic relationships be- tween terms in the ontology, as well as under a given set of negative constraints. We formally define the notion of a “wit- ness” to the integrability of two RDF ontologies under such constraints. A witness represents a way of integrating the ontologies together. We define a “minimal” witnesses and provide the polynomial CROW (Computing RDF Ontology Witness) algorithm to find a witness. We report on the per- formance of CROW both on DAML, SchemaWeb and Onto- Broker ontologies as well as on synthetically generated data. The experiments show that CROW works very well on real- life ontologies and scales to massive ontologies.

Help! I'm Lost: User Frustration in Web Navigation (2003) - Lazar,Jonathan; Bessiere,Katie; Ceaparu,Irina; Robinson,John; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Computers can be valuable tools, and networked resources via the Internet can be beneficial to many different populations and communities. Unfortunately, when people are unable to reach their task goals due to frustrating experiences, this can hinder the effectiveness of technology. This research summary provides information about the user frustration research that has been performed at the University of Maryland and Towson University. Causes of user frustration are discussed in this research summary, along with the surprising finding that nearly one-third to one-half of the time spent in front of the computer is wasted due to frustrating experiences. Furthermore, when interfaces are planned to be deceptive and confusing, this
Keywords: Technical Report

The Hiero machine translation system: Extensions, evaluation, and analysis - Chiang,D.; Lopez,A.; Madnani,N.; Monz,C.; Resnik, Philip; Subotin,M. (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

How do I find blue books about dogs? The errors and frustrations of young digital library users - Hutchinson,H.; Druin, Allison; Bederson, Benjamin B.; Reuter,K.; Rose,A.; Weeks,A. C (Proceedings of HCII 2005, 2005)

Identity-based zero-knowledge - Katz, Jonathan; Ostrovsky,R.; Rabin,M. (Security in Communication Networks, 2005)
We introduce and define the notion of identity-based zero-knowledge, concentrating on the non-interactive setting. In this setting, our notion allows any prover to widely disseminate a proof of a statement while protecting the prover from plagiarism in the following sense: although proofs are transferable (i.e., publicly verifiable), they are also bound to the identity of the prover in a way which is recognizable to any verifier. Furthermore, an adversary is unable to change this identity (i.e., to claim the proof as his own, or to otherwise change the authorship), unless he could have proved the statement on his own.While we view the primary contribution of this work as a formal definition of the above notion, we also explore the relation of this notion to that of non-malleable (non-interactive) zero-knowledge. On the one hand, we show that these two notions are incomparable: that is, there are proof systems which are non-malleable but not identity-based, and vice versa. On the other hand, we show that a proof system of either type essentially implies a proof system of the other type.

Immediate Usability: A Case Study of Public Access Design for a Community Photo Library (2003) - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
This paper describes a novel instantiation of a digital photo library in a public access system. It demonstrates how designers can utilize characteristics of a target user community (social constraints, trust, and a lack of anonymity) to provide capabilities that would be impractical in other types of public access systems. It also presents a compact set of design principles and guidelines for ensuring the immediate usability of public access information systems. These principles and guidelines were derived from our experience developing PhotoFinder Kiosk, a community photo library. Attendees of a major HCI conference (CHI 2001 Conference on Human Factors in Computing Systems) successfully used the tool to browse and annotate collections of photographs spanning 20 years of HCI-related conferences, producing a richly annotated photo history of the field of human-computer interaction. Observations and log data were used to evaluate the tool and develop the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Technical Report

Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library (2001) - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
This paper describes a novel set of design principles and guidelines for ensuring the immediate usability of public access systems. These principles and guidelines were formulated while developing PhotoFinder Kiosk, a community photo library. Attendees of CHI 2001 successfully used the tool to browse and annotate collections of photographs spanning 20 years of CHI and related conferences, producing a richly annotated photo history of the field of human-computer interaction. We used observations and log data to evaluate the tool and refine the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Technical Report

Improved HMM alignment models for languages with scarce resources - Lopez,A.; Resnik, Philip (Proceedings of the ACL Workshop on Building and Using Parallel Texts, 2005)

The International Children’s Digital Library: A Case Study in Designing for a MultiLingual - Hutchinson,H.B.; Rose,A.; Bederson, Benjamin B.; Weeks,A. C; Druin, Allison (Multi-Cultural, Multi-Generational Audience. Information Technology and Libraries, 2005)

Johns Hopkins summer workshop final report on parsing and spoken structural event detection - Harper,MP; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A. (Johns Hopkins University, Tech. Rep, 2005)
This report describes research conducted by the Parsing and Spoken Structural Event Detection(PaSSED) team as part of the 2005 Johns Hopkins Summer Workshop on Language Engineering. This project investigated the interaction between parsing and the detection of structural metadata in conversational speech, including sentence boundaries, edits (the reparandum portion of speech repairs), and fillers. In terms of parsing, we explored alternative methods of exploiting metadata information in parsing models and measured how varying accuracy in transcription and metadata information affects parsing accuracy. In the other direction, we similarly considered how syntactic and prosodic knowledge could be leveraged in metadata detection, measuring how this knowledge impacts metadata detection accuracy. As part of this work, we investigated metrics for evaluating parse accuracy in the presence of tran- scription and metadata detection errors, and we report on our experience using these metrics with several parsers and across varying experimental conditions. A range of methods for handling edits during pars- ing were evaluated in this research (excision, addition of markups to the input string, and grammar modification). We also developed a ToBI (a prosodic structure annotation scheme [SBP+92]) prosodic event classifier and describe its evaluation. Finally, we present methods for effective n-best sentence boundary candidate generation and reranking using syntactic, prosodic, and other features. These stud- ies are complemented by a second set of reranking investigations wherein we optimize sentence boundary detection explicitly to improve parse accuracy. The PaSSED project has: • investigated various techniques to enhance parsing of speech given metadata detection on conver- sational speech; • defined metrics for evaluating speech parsing accuracy, implemented them in the publically avail- able SParseval software package, and evaluated them under a wide variety of conditions; • recast SU detection as an n-best reranking problem with a relatively small n. Using this approach, we demonstrated significant improvements over a very strong baseline SU detection system. • reported on the interaction between parsing and metadata detection and their synergy; • fostered new collaborations and identified a number of interesting avenues for future work.

A Knowledge Integration Framework for Information Visualization - Seo,Jinwook; Shneiderman, Ben (From Integrated Publication and Information Systems to Information and Knowledge EnvironmentsFrom Integrated Publication and Information Systems to Information and Knowledge Environments, 2005)
Users can better understand complex data sets by combining insights from multiple coordinated visual displays that include relevant domain knowledge. When dealing with multidimensional data and clustering results, the most familiar displays and comprehensible are 1- and 2-dimensional projections (histograms, and scatterplots). Other easily understood displays of domain knowledge are tabular and hierarchical information for the same or related data sets. The novel parallel coordinates view [6] powered by a direct-manipulation search, offers strong advantages, but requires some training for most users. We provide a review of related work in the area of information visualization, and introduce new tools and interaction examples on how to incorporate users’ domain knowledge for understanding clustering results. Our examples present hierarchical clustering of gene expression data, coordinated with a parallel coordinates view and with the gene annotation and gene ontology.

The linguist's search engine: an overview - Resnik, Philip; Elkiss,A. (Proceedings of the ACL 2005 on Interactive poster and demonstration sessions, 2005)

Maintaining Implicated Statistics in Constrained Environments - Sismanis,Yannis; Roussopoulos, Nick (Data Engineering, International Conference on, 2005)
Aggregated information regarding implicated entities is critical for online applications like network management, traffic characterization or identifying patters of resource consumption. Recently there has been a flurry of research for online aggregation on streams (like quantiles, hot items, hierarchical heavy hitters) but surprizingly the problem of summarizing implicated information in stream data has received no attention. As an example, consider an IP-network and the implication source → destination. Flash crowds, — such as those that follow recent sport events (like the olympics) or seek information regarding catastrophic events — or denial of service attacks direct a large volume of traffic from a huge number of sources to a very small number of destinations. In this paper we present novel randomized algorithms for monitoring such implications with constraints in both memory and processing power for environments like network routers. Our experiments demonstrate several factors of improvements over straightforward approaches.

The manifolds of spatial hearing - Duraiswami, Ramani; Raykar,V.C. (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
We present exploratory studies on learning the non-linear manifold structure, in head related impulse responses (HRIRs). We use the recently popular locally linear embedding technique. The lower dimensional manifold encodes the perceptual information in the HRIRs, namely the direction of the sound source. Based on this, we propose a new method for HRIR interpolation. We also propose that the distance between two HRIRs of an individual be taken as the geodesic distance on the learned manifold.
Keywords: acoustics; dimensional; direction; distance; EMBEDDING; encoding; geodesic; Head; hearing; hearing; HRIR; impulse; information; interpolation; learned; linear; localization; locally; low; manifold; manifold; manifolds; nonlinear; perceptual; related; response; responses; sound; source; spatial; structure; technique; transient

Matching shape sequences in video with applications in human movement analysis - A,Veeraraghavan; Roy-Chowdhury, A.K.; Chellapa, Rama (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2005)
We present an approach for comparing two sequences of deforming shapes using both parametric models and nonparametric methods. In our approach, Kendall's definition of shape is used for feature extraction. Since the shape feature rests on a non-Euclidean manifold, we propose parametric models like the autoregressive model and autoregressive moving average model on the tangent space and demonstrate the ability of these models to capture the nature of shape deformations using experiments on gait-based human recognition. The nonparametric model is based on dynamic time-warping. We suggest a modification of the dynamic time-warping algorithm to include the nature of the non-Euclidean space in which the shape deformations take place. We also show the efficacy of this algorithm by its application to gait-based human recognition. We exploit the shape deformations of a person's silhouette as a discriminating feature and provide recognition results using the nonparametric model. Our analysis leads to some interesting observations on the role of shape and kinematics in automated gait-based person authentication.
Keywords: Automated; Photography; Reproducibility of Results; Sensitivity and Specificity; Subtraction Technique; Video Recording; autoregressive moving average model; deforming shapes; dynamic time-warping; feature extraction; gait-based human recognition; human movement analysis; matching shape sequences; video; autoregressive moving average processes; feature extraction; image matching; imag; Biological; Models; Computer-Assisted; Imaging; Statistical; Movement; Pattern Recognition; Three-Dimensional; Leg; Models

MEAD: support for Real-Time Fault-Tolerant CORBA - Narasimhan, P.; Tudor Dumitras; Paulos, A. M.; Pertet, S. M.; Reverte, C. F.; Slember, J. G.; Srivastava, D. (Concurrency and Computation: Practice and Experience, 2005)
The OMG's Real-Time CORBA (RT-CORBA) and Fault-Tolerant CORBA (FT-CORBA) specifications make it possible for today's CORBA implementations to exhibit either real-time or fault tolerance in isolation. While real-time requires a priori knowledge of the system's temporal operation, fault tolerance necessarily deals with faults that occur unexpectedly, and with possibly unpredictable fault recovery times. The MEAD (Middleware for Embedded Adaptive Dependability) system attempts to identify and to reconcile the conflicts between real-time and fault tolerance, in a resource-aware manner, for distributed CORBA applications. MEAD supports transparent yet tunable fault tolerance in real-time, proactive dependability, resource-aware system adaptation to crash, communication and timing faults with bounded fault detection and fault recovery. Copyright © 2005 John Wiley & Sons, Ltd.
Keywords: CORBA; Fault tolerance; non-determinism; predictability; real-time; recovery; trade-offs

Measurements for understanding the behavior of the genetic algorithm in dynamic environments: a case study using the Shaky Ladder Hyperplane-Defined Functions - Rand, William; Riolo,Rick (Proceedings of the 2005 workshops on Genetic and evolutionary computation, 2005)
We describe a set of measures to examine the behavior of the Genetic Algorithm (GA) in dynamic environments. We describe how to use both average and best measures to look at performance, satisficability, robustness, and diversity. We use these measures to examine GA behavior with a recently devised dynamic test suite, the Shaky Ladder Hyperplane-Defined Functions (sl-hdf's). This test suite can generate random problems with similar levels of difficulty and provides a platform allowing systematic controlled observations of the GA in dynamic environments. We examine the results of these measures in two different versions of the sl-hdf's, one static and one regularly-changing. We provide explanations for the observations in these two different environments, and give suggestions as to future work.
Keywords: dynamic environments; Genetic algorithms; hyperplane-defined functions; measurement

A method for converting a smiling face to a neutral face with applications to face recognition - Ramachandran, M.; Zhou,S. K; Jhalani, D.; Chellapa, Rama (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
The human face displays a variety of expressions, like smile, sorrow, surprise, etc. All these expressions constitute nonrigid motions of various features of the face. These expressions lead to a significant change in the appearance of a facial image which leads to a drop in the recognition accuracy of a face-recognition system trained with neutral faces. There are other factors like pose and illumination which also lead to performance drops. Researchers have proposed methods to tackle the effects of pose and illumination; however, there has been little work on how to tackle expressions. We attempt to address the issue of expression invariant face-recognition. We present preprocessing steps for converting a smiling face to a neutral face. We expect that this would in turn make the vector in the feature space to be closer to the correct vector in the gallery, in an appearance-based face recognition. This conjecture is supported by our recognition results which demonstrate that the accuracy goes up if we include the expression-normalization block.
Keywords: appearance-based; Expression; Face; face; feature; invariant; motion; neutral; nonrigid; normalization; recognition; smiling

Mirror symmetric topographic maps can arise from activity-dependent synaptic changes - Schulz,R.; Reggia, James A. (Neural computation, 2005)

OCR post-processing for low density languages - Kolak,O.; Resnik, Philip (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

Path dependence and the validation of agent-based spatial models of land use - Corresponding,D.G.B.; Page,S; Riolo,R; Zellner,M; Rand, William (International Journal of Geographical Information Science, 2005)

Path dependence and the validation of agent‐based spatial models of land use - Brown,Daniel G.; Page,Scott; Riolo,Rick; Zellner,Moira; Rand, William (International Journal of Geographical Information Science, 2005)
In this paper, we identify two distinct notions of accuracy of land?use models and highlight a tension between them. A model can have predictive accuracy: its predicted land?use pattern can be highly correlated with the actual land?use pattern. A model can also have process accuracy: the process by which locations or land?use patterns are determined can be consistent with real world processes. To balance these two potentially conflicting motivations, we introduce the concept of the invariant region, i.e., the area where land?use type is almost certain, and thus path independent; and the variant region, i.e., the area where land use depends on a particular series of events, and is thus path dependent. We demonstrate our methods using an agent?based land?use model and using multi?temporal land?use data collected for Washtenaw County, Michigan, USA. The results indicate that, using the methods we describe, researchers can improve their ability to communicate how well their model performs, the situations or instances in which it does not perform well, and the cases in which it is relatively unlikely to predict well because of either path dependence or stochastic uncertainty.

Pedestrian classification from moving platforms using cyclic motion pattern - Yang Ran; Qinfen Zheng; Weiss, I.; Davis, Larry S.; Abd-Almageed, Wael; Liang Zhao (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
This paper describes an efficient pedestrian detection system for videos acquired from moving platforms. Given a detected and tracked object as a sequence of images within a bounding box, we describe the periodic signature of its motion pattern using a twin-pendulum model. Then a principle gait angle is extracted in every frame providing gait phase information. By estimating the periodicity from the phase data using a digital phase locked loop (dPLL), we quantify the cyclic pattern of the object, which helps us to continuously classify it as a pedestrian. Past approaches have used shape detectors applied to a single image or classifiers based on human body pixel oscillations, but ours is the first to integrate a global cyclic motion model and periodicity analysis. Novel contributions of this paper include: i) development of a compact shape representation of cyclic motion as a signature for a pedestrian, ii) estimation of gait period via a feedback loop module, and iii) implementation of a fast online pedestrian classification system which operates on videos acquired from moving platforms.
Keywords: analysis; angle; body; classification; compact; cyclic; DETECTION; detection; digital; Feedback; Gait; human; image; information; locked; loop; loop; loops; module; MOTION; object; oscillations; pattern; pedestrian; phase; Pixel; principle; representation; sequence; sequences; SHAPE; system

Pedestrian classification from moving platforms using cyclic motion pattern - Yang Ran; Qinfen Zheng; Weiss, I.; Davis, Larry S.; Abd-Almageed, Wael; Liang Zhao (IEEE International Conference on Image Processing, 2005. ICIP 2005, 2005)
This paper describes an efficient pedestrian detection system for videos acquired from moving platforms. Given a detected and tracked object as a sequence of images within a bounding box, we describe the periodic signature of its motion pattern using a twin-pendulum model. Then a principle gait angle is extracted in every frame providing gait phase information. By estimating the periodicity from the phase data using a digital phase locked loop (dPLL), we quantify the cyclic pattern of the object, which helps us to continuously classify it as a pedestrian. Past approaches have used shape detectors applied to a single image or classifiers based on human body pixel oscillations, but ours is the first to integrate a global cyclic motion model and periodicity analysis. Novel contributions of this paper include: i) development of a compact shape representation of cyclic motion as a signature for a pedestrian, ii) estimation of gait period via a feedback loop module, and iii) implementation of a fast online pedestrian classification system which operates on videos acquired from moving platforms.
Keywords: compact shape representation; cyclic motion pattern; data mining; Detectors; digital phase locked loop; digital phase locked loops; feedback loop module; gait analysis; gait phase information; human body pixel oscillations; HUMANS; image classification; Image motion analysis; image representation; image sequence; Image sequences; Motion detection; Object detection; pedestrian classification; pedestrian detection system; Phase estimation; Phase locked loops; principle gait angle; SHAPE; tracking; Videos

The problem with a self-adaptative mutation rate in some environments: a case study using the shaky ladder hyperplane-defined functions - Rand, William; Riolo,Rick (Proceedings of the 2005 conference on Genetic and evolutionary computation, 2005)
Dynamic environments have periods of quiescence and periods of change. In periods of quiescence a Genetic Algorithm (GA) should (optimally) exploit good individuals while in periods of change the GA should (optimally) explore new solutions. Self-adaptation is a mechanism which allows individuals in the GA to choose their own mutation rate, and thus allows the GA to control when it explores new solutions or exploits old ones. We examine the use of this mechanism on a recently devised dynamic test suite, the Shaky Ladder Hyperplane-Defined Functions (sl-hdf's). This test suite can generate random problems with similar levels of difficulty and provides a platform allowing systematic controlled observations of the GA in dynamic environments. We show that in a variety of circumstances self-adaptation fails to allow the GA to perform better on this test suite than fixed mutation, even when the environment is static. We also show that mutation is beneficial throughout the run of a GA, and that seeding a population with known good genetic material is not always beneficial to the results. We provide explanations for these observations, with particular emphasis on comparing our results to other results [2] which have shown the GA to work in static environments. We conclude by giving suggestions as to how to change the simple GA to solve these problems.
Keywords: dynamic environments; Genetic algorithms; hyperplane-defined functions; self-adaptation

Query planning for the grid: adapting to dynamic resource availability - Zhang,K.; Andrade,H.; Raschid, Louiqa; Sussman, Alan (Cluster Computing and the Grid, IEEE International Symposium on, 2005)
The availability of massive datasets, comprising sensor measurements or the results of scientific simulations, has had a significant impact on the methodology of scientific reasoning. Scientists require storage, bandwidth and computational capacity to query and analyze these datasets, to understand physical phenomena or to test hypotheses. This paper addresses the challenge of identifying and selecting resources to develop an evaluation plan for large scale data analysis queries when data processing capabilities and datasets are dispersed across nodes in one or more computing and storage clusters. We show that generating an optimal plan is hard and we propose heuristic techniques to find a good choice of resources. We also consider heuristics to cope with dynamic resource availability; in this situation we have stale information about reusable cached results (datasets) and the load on various nodes.

Recognition of Humans and Their Activities Using Video - Chellapa, Rama; Roy-Chowdhury,Amit K.; Zhou,S. Kevin (Synthesis Lectures on Image, Video, and Multimedia Processing, 2005)
The recognition of humans and their activities from video sequences is currently a very active area of research because of its applications in video surveillance, design of realistic entertainment systems, multimedia communications, and medical diagnosis. In this lecture, we discuss the use of face and gait signatures for human identification and recognition of human activities from video sequences. We survey existing work and describe some of the more well-known methods in these areas. We also describe our own research and outline future possibilities.In the area of face recognition, we start with the traditional methods for image-based analysis and then describe some of the more recent developments related to the use of video sequences, 3D models, and techniques for representing variations of illumination. We note that the main challenge facing researchers in this area is the development of recognition strategies that are robust to changes due to pose, illumination, disguise, and aging. Gait recognition is a more recent area of research in video understanding, although it has been studied for a long time in psychophysics and kinesiology. The goal for video scientists working in this area is to automatically extract the parameters for representation of human gait. We describe some of the techniques that have been developed for this purpose, most of which are appearance based. We also highlight the challenges involved in dealing with changes in viewpoint and propose methods based on image synthesis, visual hull, and 3D models. In the domain of human activity recognition, we present an extensive survey of various methods that have been developed in different disciplines like artificial intelligence, image processing, pattern recognition, and computer vision. We then outline our method for modeling complex activities using 2D and 3D deformable shape theory. The wide application of automatic human identification and activity recognition methods will require the fusion of different modalities like face and gait, dealing with the problems of pose and illumination variations, and accurate computation of 3D models. The last chapter of this lecture deals with these areas of future research.

Recovering from Intrusions in the OSPF Data-plane - Elaine Shi; Lu, Yong; Reid, Matt (Selected Project Reports, Spring 2005 Advanced OS & Distributed Systems (15-712), 2005)
In this paper, we propose CONS-ROUTE, a data-plane intrusion recoverymechanism for securing the OSPF routing protocol. CONS-ROUTE allows routers to perform intrusion detection in a distributed manner. The intrusion detection outcome can be used globally to reevaluate routing decisions in a way that is resilient to the slandering attack, where a malicious router claims that a legitimate router is misbehaving. We evaluate CONS-ROUTE through simulation and compare it with several simple OSPF data plane resilience techniques.

Reliable Segmentation of Pedestrians in Moving Scenes - Ran, Y.; Zheng,Q.; Weiss, I.; Davis, Larry S. (The 2005 International Conference on Acoustics, Speech, and Signal Processing (ICASSP2005), 2005)
This paper describes a periodic motion based pedestriansegmentation algorithm for videos acquired from moving platforms. Given a sequence of bounding boxes containing the detected and tracked walking human, the goal is to analyze the low dimension structure by considering every object sample as a point in the high dimensional manifold space and use the learned structure for segmentation. In this work, unlike the traditional top- down dimension reduction (manifold learning) methods such as Isomap and locally linear embedding (LLE) [9], we introduce a novel bottom-up learning approach. We represent the human stride as a cascade of models with increasing parameter numbers. These parameters describe the dynamics of pedestrians from coarse to fine. By applying the learned manifold structure, we can predict the location of body parts, especially legs, with high accuracy at every frame. The segmentation in consecutive images is done by EM clustering. With the accuracy for prediction using twin-pendulum model, EM is more likely to converge to global maximums. Experimental results for real videos are presented. The algorithm has demonstrated a reliable performance for videos acquired from moving platforms.

Scheduling on Unrelated Machines Under Tree-Like Precedence Constraints - Kumar, V.; Marathe,Madhav; Parthasarathy,Srinivasan; Srinivasan, Aravind (Approximation, Randomization and Combinatorial Optimization. Algorithms and TechniquesApproximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 2005)
We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are “treelike” – i.e., when the undirected graph underlying the precedences is a forest. We also obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment – this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion+dilation”, as in other job shop scheduling approaches. The first step in our algorithm for the R | prec | C max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random delays technique of Leighton, Maggs and Rao to the case of trees. For the weighted completion time, we show a certain type of reduction to the makespan problem, which dovetails well with the lower bound we employ for the makespan problem. For the special case of chains, we show a dependent rounding technique which leads to improved bounds on the weighted completion time and new bicriteria bounds for the flow time.

Secure requirements elicitation through triggered message sequence charts - Ray,A.; Sengupta,B.; Cleaveland, Rance (Distributed Computing and Internet Technology, 2005)

Shaky ladders, hyperplane-defined functions and genetic algorithms: Systematic controlled observation in dynamic environments - Rand, William; Riolo,R (Applications of Evolutionary Computing, 2005)
Though recently there has been interest in examining genetic algorithms (GAs) in dynamic environments, work still needs to be done in investigating the fundamental behavior of these algorithms in changing environments. When researching the GA in static environments, it has been useful to use test suites of functions that are designed for the GA so that the performance can be observed under systematic controlled conditions. One example of these suites is the hyperplane-defined functions (hdfs) designed by Holland [1]. We have created an extension of these functions, specifically designed for dynamic environments, which we call the shaky ladder functions. In this paper, we examine the qualities of this suite that facilitate its use in examining the GA in dynamic environments, describe the construction of these functions and present some preliminary results of a GA operating on these functions.

"Shape Activity": a continuous-state HMM for moving/deforming shapes with application to abnormal activity detection - Vaswani, N.; Roy-Chowdhury, A.K.; Chellapa, Rama (Image Processing, IEEE Transactions on, 2005)
The aim is to model "activity" performed by a group of moving and interacting objects (which can be people, cars, or different rigid components of the human body) and use the models for abnormal activity detection. Previous approaches to modeling group activity include co-occurrence statistics (individual and joint histograms) and dynamic Bayesian networks, neither of which is applicable when the number of interacting objects is large. We treat the objects as point objects (referred to as "landmarks") and propose to model their changing configuration as a moving and deforming "shape" (using Kendall's shape theory for discrete landmarks). A continuous-state hidden Markov model is defined for landmark shape dynamics in an activity. The configuration of landmarks at a given time forms the observation vector, and the corresponding shape and the scaled Euclidean motion parameters form the hidden-state vector. An abnormal activity is then defined as a change in the shape activity model, which could be slow or drastic and whose parameters are unknown. Results are shown on a real abnormal activity-detection problem involving multiple moving objects.
Keywords: abnormal activity detection; activity recognition; co-occurrence statistics; continuous-state hidden Markov model; dynamic Bayesian networks; hidden-state vector; particle filtering; scaled Euclidean motion parameter; shape deforming; belief networks; filtering the; Automated; Subtraction Technique; Video Recording; Biological; Models; Computer-Assisted; Information Storage and Retrieval; Markov Chains; Models; Statistical; Movement; Pattern Recognition

Social and Psychological Influences on Computer User Frustration (Newhagen book chapter, 2002) - Bessiere,Katie; Ceaparu,Irina; Lazar,Jonathan; Robinson,John; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
As computer usage has proliferated, so has user frustration. Even devoted and knowledgeable users encounter annoying delays, incomprehensible messages, incompatible files, and indecipherable menus. The frustration generated by these problems can be personally disturbing and socially disruptive. Psychological and social perspectives on frustration may clarify the relationships among variables such as personality types, cultural factors, goal attainment, workplace anger, and computer anxiety. These perspectives may also help designers, managers, and users understand the range of responses to frustration, which could lead to effective interventions such as redesign of software, improved training, better online help, user discipline, and even resetting of national research priorities.
Keywords: Technical Report

Spatial process and data models: Toward integration of agent-based models and GIS - Brown,D.G.; Riolo,R; Robinson,D.T.; North,M.; Rand, William (Journal of Geographical Systems, 2005)
The use of object-orientation for both spatial data and spatial process models facilitates their integration, which can allow exploration and explanation of spatial-temporal phenomena. In order to better understand how tight coupling might proceed and to evaluate the possible functional and efficiency gains from such a tight coupling, we identify four key relationships affecting how geographic data (fields and objects) and agent-based process models can interact: identity, causal, temporal and topological. We discuss approaches to implementing tight integration, focusing on a middleware approach that links existing GIS and ABM development platforms, and illustrate the need and approaches with example agent-based models.

Speaker Localization Using Excitation Source Information in Speech - Raykar,V.C.; Yegnanarayana,B.; Prasanna,S. R.M; Duraiswami, Ramani (Speech and Audio Processing, IEEE Transactions on, 2005)
This paper presents the results of simulation and real room studies for localization of a moving speaker using information about the excitation source of speech production. The first step in localization is the estimation of time-delay from speech collected by a pair of microphones. Methods for time-delay estimation generally use spectral features that correspond mostly to the shape of vocal tract during speech production. Spectral features are affected by degradations due to noise and reverberation. This paper proposes a method for localizing a speaker using features that arise from the excitation source during speech production. Experiments were conducted by simulating different noise and reverberation conditions to compare the performance of the time-delay estimation and source localization using the proposed method with the results obtained using the spectrum-based generalized cross correlation (GCC) methods. The results show that the proposed method shows lower number of discrepancies in the estimated time-delays. The bias, variance and the root mean square error (RMSE) of the proposed method is consistently equal or less than the GCC methods. The location of a moving speaker estimated using the time-delays obtained by the proposed method are closer to the actual values, than those obtained by the GCC method.
Keywords: correlation; correlation; cross; Delay; error; error; estimation; excitation; generalized; information; localization; mean; methods; processing; production; root; source; speaker; speech; square; TIME

Statistical bias in 3-D reconstruction from a monocular video - Roy-Chowdhury, A.K.; Chellapa, Rama (Image Processing, IEEE Transactions on, 2005)
The present state-of-the-art in computing the error statistics in three-dimensional (3-D) reconstruction from video concentrates on estimating the error covariance. A different source of error which has not received much attention is the fact that the reconstruction estimates are often significantly statistically biased. In this paper, we derive a precise expression for the bias in the depth estimate, based on the continuous (differentiable) version of structure from motion (SfM). Many SfM algorithms, or certain portions of them, can be posed in a linear least-squares (LS) framework Ax=b. Examples include initialization procedures for bundle adjustment or algorithms that alternately estimate depth and camera motion. It is a well-known fact that the LS estimate is biased if the system matrix A is noisy. In SfM, the matrix A contains point correspondences, which are always difficult to obtain precisely; thus, it is expected that the structure and motion estimates in such a formulation of the problem would be biased. Existing results on the minimum achievable variance of the SfM estimator are extended by deriving a generalized Cramer-Rao lower bound. A detailed analysis of the effect of various camera motion parameters on the bias is presented. We conclude by presenting the effect of bias compensation on reconstructing 3-D face models from rendered images.
Keywords: 3D face models; 3D video reconstruction; algorithms; artifacts; Artificial intelligence; Automated; Signal Processing; bias compensation; bundle adjustment; camera motion estimation; Computer simulation; Computer-Assisted; Imaging; Computer-Assisted; Subtraction Technique; Video Recording; depth estimate; error covariance estimation; error statistics; generalized Cramer-Rao lower bound; Image Enhancement; Image Interpretation; Image reconstruction; initialization procedures; least squares approximations; linear least-squares framework; monocular video; motion compensation; Motion estimation; statistical bias; Statistical; Pattern Recognition; structure from motion algorithms; Three-Dimensional; Information Storage and Retrieval; Models; video signal processing

Structural Determinants for Selective Recognition of a Lys48-Linked Polyubiquitin Chain by a UBA Domain - Varadan,Ranjani; Assfalg,Michael; Raasi,Shahri; Pickart,Cecile; Fushman, David (Molecular Cell, 2005)
SummaryAlthough functional diversity in polyubiquitin chain signaling has been ascribed to the ability of differently linked chains to bind in a distinctive manner to effector proteins, structural models of such interactions have been lacking. Here, we use NMR to unveil the structural basis of selective recognition of Lys48-linked di- and tetraubiquitin chains by the UBA2 domain of hHR23A. Although the interaction of UBA2 with Lys48-linked diubiquitin involves the same hydrophobic surface on each ubiquitin unit as that utilized in monoubiquitin:UBA complexes, our results show how the “closed” conformation of Lys48-linked diubiquitin is crucial for high-affinity binding. Moreover, recognition of Lys48-linked diubiquitin involves a unique epitope on UBA, which allows the formation of a sandwich-like diubiqutin:UBA complex. Studies of the UBA-tetraubiquitin interaction suggest that this mode of UBA binding to diubiquitin is relevant for longer chains.

Structural metadata and parsing speech - Harper,M.; Dorr, Bonnie J; Hale,J.; Roark,B.; Shafran,I.; Lease,M.; Liu,Y.; Snover,M.; Yung,L.; Krasnyanskaya,A.; others (JHU Language Engineering Workshop, 2005)

Temperature-Driven Campylobacter Seasonality in England and Wales - Louis,Valérie R.; Gillespie,Iain A.; O'Brien,Sarah J.; Russek-Cohen,Estelle; Pearson,Andrew D.; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2005)
Campylobacter incidence in England and Wales between 1990 and 1999 was examined in conjunction with weather conditions. Over the 10-year interval, the average annual rate was determined to be 78.4 ± 15.0 cases per 100,000, with an upward trend. Rates were higher in males than in females, regardless of age, and highest in children less than 5 years old. Major regional differences were detected, with the highest rates in Wales and the southwest and the lowest in the southeast. The disease displayed a seasonal pattern, and increased campylobacter rates were found to be correlated with temperature. The most marked seasonal effect was observed for children under the age of 5. The seasonal pattern of campylobacter infections indicated a linkage with environmental factors rather than food sources. Therefore, public health interventions should not be restricted to food-borne approaches, and the epidemiology of the seasonal peak in human campylobacter infections may best be understood through studies in young children.

Temporal visualization of planning polygons for e~cient partitioning of geo-spatial data - Shanbhag,P.; Rheingans,P.; desJardins, Marie (Information Visualization, 2005. INFOVIS 2005. IEEE Symposium on, 2005)
Partitioning of geo-spatial data for efficient allocation of resources such as schools and emergency health care services is driven by a need to provide better and more effective services. Partitioning of spatial data is a complex process that depends on numerous factors such as population, costs incurred in deploying or utilizing resources and target capacity of a resource. Moreover, complex data such as population distributions are dynamic i.e. they may change over time. Simple animation may not effectively show temporal changes in spatial data. We propose the use of three temporal visualization techniques -wedges, rings and time slices - to display the nature of change in temporal data in a single view. Along with maximizing resource utilization and minimizing utilization costs, a partition should also ensure the long term effectiveness of the plan. We use multi-attribute visualization techniques to highlight the strengths and identify the weaknesses of a partition. Comparative visualization techniques allow multiple partitions to be viewed simultaneously. Users can make informed decisions about how to partition geo spatial data by using a combination of our techniques for multi-attribute visualization, temporal visualization and comparative visualization.

Toward a graphical ABM toolkit with GIS integration - Rand, William; Brown,D; Riolo,R; Robinson,D (Proceedings of Agent2005, 2005)
Agent-based modeling (ABM) has proved useful in a number of fields. Many of theearly successes of ABM were due to its ability to represent the processes of a phenomenon. However, less emphasis has been placed in ABM on developing its ability to replicate spatial patterns of phenomena. In order to do that, more powerful spatial modeling techniques, like those within geographical information systems (GIS), are necessary. The integration of these two tool sets into a cohesive package would allow for elegant modeling of both process and pattern. One problem with an integrated toolkit is that most GIS users are not programmers, but most GIS users are familiar with the use of detailed graphical user interfaces (GUIs) in order to create complex visualizations of data. Thus providing a detailed GUI to access an integrated ABM-GIS toolkit would vastly expand the number of users for such a toolkit. This paper is a first step toward that goal. We first outline several design principles for an ABM-GIS toolkit and then describe a survey of extant toolkits (RepastPy, NetLogo, and MobiDyc) that were selected based on the design principles. The toolkits were surveyed to see how well they fulfill some of the design principles. This survey is not meant to be a comparative review of these toolkits but rather it was conducted to determine what useful design principles can be gathered from them that might inform a new “ideal” ABM-GIS toolkit. Finally, the paper concludes with some design recommendations for such a toolkit.

Turning information visualization innovations into commercial products: lessons to guide the next success - Shneiderman, Ben; Rao,R.; Andrews,K.; Ahlberg,C.; Brodbeck,D.; Jewitt,T.; Mackinlay,J. (IEEE Symposium on Information Visualization, 2005. INFOVIS 2005, 2005)
As information visualization matures as an academic research field, commercial spinoffs are proliferating, but success stories are harder to find. This is the normal process of emergence for new technologies, but the panel organizers believe that there are certain strategies that facilitate success. To teach these lessons, we have invited several key figures who are seeking to commercialize information visualization tools. The panelists make short presentations, engage in a moderated discussion, and respond to audience questions.
Keywords: Books; commercial development; commercial product; Computer interfaces; Computer science; data visualisation; Data visualization; Educational institutions; exploratory data analysis; information visualization innovation; information visualization tool; innovation management; Laboratories; Management training; new technology emergence; Technological innovation; technology transfer; Turning; User interfaces

Using aggregate motion in multi-agent teams to solve search and transport problems - RodrIGuez,A.; Reggia, James A. (Swarm Intelligence Symposium, 2005. SIS 2005. Proceedings 2005 IEEE, 2005)

Using Non-random Associations for Predicting Latency in WANs - Raschid, Louiqa; Ye,Q.; Zadorozhny,V.; Gal,A.; Murthy,H. (Web Information Systems Engineering – WISE 2005, 2005)
In this paper, we propose a scalable performance management tool for Wide Area Applications. Our objective is to scalably identify non-random associations between pairs of individual Latency Profiles (iLPs) (i.e., latency distributions experienced by clients when connecting to a server) and exploit them in latency prediction. Our approach utilizes Relevance Networks (RNs) to manage tens of thousands of iLPs. Non-random associations between iLPs can be identified by topology-independent measures such as correlation and mutual information. We demonstrate that these non-random associations do indeed have a significant impact in improving the error of latency prediction.

The web in theoretical linguistics research: Two case studies using the Linguist’s Search Engine - Resnik, Philip; Elkiss,A.; Lau,E.; Taylor,H. (31st Meeting of the Berkeley Linguistics Society, 2005)

3d modelling of human motion using kinematic chains and multiple cameras for tracking - Sundaresan, A.; RoyChowdhury, A.; Chellapa, Rama (Proc. of Eighth International Symposium on the, 2004)

Agent-based and analytical modeling to evaluate the effectiveness of greenbelts - Brown,Daniel G.; Page,Scott E.; Riolo,Rick; Rand, William (Environmental Modelling & Software, 2004)
We present several models of residential development at the rural–urban fringe to evaluate the effectiveness of a greenbelt located beside a developed area, for delaying development outside the greenbelt. First, we develop a mathematical model, under two assumptions about the distributions of service centers, that represents the trade-off between greenbelt placement and width, their effects on the rate of development beyond the greenbelt, and how these interact with spatial patterns of aesthetic quality and the locations of services. Next, we present three agent-based models (ABMs) that include agents with the potential for heterogeneous preferences and a landscape with the potential for heterogeneous attributes. Results from experiments run with a one-dimensional ABM agree with the starkest of the results from the mathematical model, strengthening the support for both models. Further, we present two different two-dimensional ABMs and conduct a series of experiments to supplement our mathematical analysis. These include examining the effects of heterogeneous agent preferences, multiple landscape patterns, incomplete or imperfect information available to agents, and a positive aesthetic quality impact of the greenbelt on neighboring locations. These results suggest how width and location of the greenbelt could help determine the effectiveness of greenbelts for slowing sprawl, but that these relationships are sensitive to the patterns of landscape aesthetic quality and assumptions about service center locations.
Keywords: Agent-based modeling; Land-use change; Landscape ecology; Urban sprawl

Automatic position calibration of multiple microphones - Raykar,V.C.; Duraiswami, Ramani (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
We describe a method to determine automatically the relative three dimensional positions of multiple microphones using at least five loudspeakers in unknown positions. The only assumption we make is that there is a microphone which is very close to a loudspeaker. In our experimental setup, we attach one microphone to each loudspeaker. We derive the maximum likelihood estimator and the solution turns out to be a non-linear least squares problem. A closed form solution which can be used as the initial guess for the minimization routine is derived. We also derive an approximate expression for the covariance of the estimator using the implicit function theorem. Using this, we analyze the performance of the estimator with respect to the positions of the loudspeakers. The algorithm is validated using both Monte-Carlo simulations and a real-time experimental setup.
Keywords: approximations; array; audio; AUTOMATIC; calibration; closed; covariance; dimensional; estimation; form; function; implicit; least; likelihood; loudspeakers; maximum; microphone; microphones; minimisation; minimization; multiple; nonlinear; position; positions; problem; processing; signal; solution; squares; theorem; three

Automatic recognition of spontaneous speech for access to multilingual oral history archives - Byrne,W.; David Doermann; Franz,M.; Gustman,S.; Hajic,J.; Oard, Douglas; Picheny,M.; Psutka,J.; Ramabhadran,B. (IEEE Transactions on Speech and Audio Processing, Special Issue on Spontaneous Speech Processing, 2004)
The MALACH project has the goal of developing the technologies needed to facilitate access to large collections of spontaneous speech. Its aim is to dramatically improve the state of the art in key Automatic Speech Recognition (ASR), Natural Language Processing (NLP) technologies for use in large-scale retrieval systems. The project leverages a unique collection of oral history interviews with survivors of the Holocaust that has been assembled and extensively annotated by the Survivors of the Shoah Visual History Foundation. This paper describes the collection, 116,000 hours of interviews in 32 languages, and the way in which system requirements have been discerned through user studies. It discusses ASR methods for very difficult speech (heavily accented, emotional, and elderly spontaneous speech), including transcription to create training data and methods for language modeling and speaker adaptation. Results are presented for for English and Czech. NLP results are presented for named entity tagging, topic segmentation, and supervised topic classification, and the architecture of an integrated search system that uses these results is described.

Automatic video summarization for wireless and mobile environments - Yong Rao; Mundur, Padma; Yesha,Y. (2004 IEEE International Conference on Communications, 2004)
In this paper, we propose a novel video summarization technique using which we can automatically generate high quality video summaries suitable for wireless and mobile environments. The significant contribution of this paper lies in the proposed clustering scheme. We use Delaunay diagrams to cluster multidimensional point data corresponding to the frame contents of the video. In contrast to the existing clustering techniques used for summarization, our clustering algorithm is fully automatic and well suited for batch processing. We illustrate the quality of our clustering and summarization scheme in an experiment using several video clips.
Keywords: automatic video summarization; batch processing; batch processing (computers); Clustering algorithms; Clustering methods; clustering scheme; Computer science; Delaunay diagram; graph theory; Gunshot detection systems; Image sequences; mesh generation; Mobile computing; mobile radio; multidimensional point data cluster; Multidimensional systems; Multimedia communication; video clip; video frame content; Video sequences; video signal processing; wireless mobile environment

BorderGuard: detecting cold potatoes from peers - Feamster, Nick; Mao,Zhuoqing Morley; Rexford,Jennifer (Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, 2004)
Internet Service Providers often establish contractual "peering" agreements, where they agree to forward traffic to each other's customers at no cost. Consistent route advertisement at all peering points is a common provision in these agreements, because it gives an AS the flexibility to select egress points for the traffic (e.g., performing "hot potato" routing). Verifying "consistent export" is challenging because route advertisements are exchanged at multiple peering points and may be modified by routing policies. In this paper, we propose two algorithms to detect inconsistent routes using routing and configuration data from an AS's border routers. The first algorithm requires access to all eBGP routes advertised by a peer. Because this data is often unavailable, we propose another algorithm that detects inconsistencies using readily available data. We have applied our algorithms to the routes advertised by the peers of AT&T's commercial IP backbone. Although a peer may intentionally send inconsistent advertisements to prevent its neighbor from performing hot-potato routing, we also discuss several configuration scenarios where a peer may inadvertently advertise inconsistent routes, despite having consistent export policies. Finally, we explain how simple modifications to the routers could make detection of inconsistent advertisements much easier than it is today.
Keywords: anomalies; BGP; inconsistent advertisement; peering

Bringing together children and books: An initial descriptive study of children's book searching and selection behavior in a digital library - Reuter,K.; Druin, Allison (Proceedings of the American Society for Information science and Technology, 2004)

Building an information retrieval test collection for spontaneous conversational speech - Oard, Douglas; Soergel,Dagobert; David Doermann; Huang,Xiaoli; Murray,G. Craig; Wang,Jianqiang; Ramabhadran,Bhuvana; Franz,Martin; Gustman,Samuel; Mayfield,James; Kharevych,Liliya; Strassel,Stephanie (Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, 2004)
Test collections model use cases in ways that facilitate evaluation of information retrieval systems. This paper describes the use of search-guided relevance assessment to create a test collection for retrieval of spontaneous conversational speech. Approximately 10,000 thematically coherent segments were manually identified in 625 hours of oral history interviews with 246 individuals. Automatic speech recognition results, manually prepared summaries, controlled vocabulary indexing, and name authority control are available for every segment. Those features were leveraged by a team of four relevance assessors to identify topically relevant segments for 28 topics developed from actual user requests. Search-guided assessment yielded sufficient inter-annotator agreement to support formative evaluation during system development. Baseline results for ranked retrieval are presented to illustrate use of the collection.
Keywords: assessment; Automatic speech recognition; oral history; search-guided relevance

The case for separating routing from routers - Feamster, Nick; Balakrishnan,Hari; Rexford,Jennifer; Shaikh,Aman; van der Merwe,Jacobus (Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, 2004)
Over the past decade, the complexity of the Internet's routing infrastructure has increased dramatically. This complexity and the problems it causes stem not just from various new demands made of the routing infrastructure, but also from fundamental limitations in the ability of today's distributed infrastructure to scalably cope with new requirements.The limitations in today's routing system arise in large part from the fully distributed path-selection computation that the IP routers in an autonomous system (AS) must perform. To overcome this weakness, interdomain routing should be separated from today's IP routers, which should simply forward packets (for the most part). Instead, a separate Routing Control Platform (RCP) should select routes on behalf of the IP routers in each AS and exchange reachability information with other domains.Our position is that an approach like RCP is a good way of coping with complexity while being responsive to new demands and can lead to a routing system that is substantially easier to manage than today. We present a design overview of RCP based on three architectural principles path computation based on a consistent view of network state, controlled interactions between routing protocol layers, and expressive specification of routing policies and discuss the architectural strengths and weaknesses of our proposal.
Keywords: BGP; interdomain routing; routing architecture

Challenges in selecting paths for navigational queries: Trade-off of benefit of path versus cost of plan - Vidal,M. E; Raschid, Louiqa; Mestre,J. (Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, 2004)

A comparison of bug finding tools for Java - Rutar,N.; Almazan,C.B.; Foster, Jeffrey S. (Software Reliability Engineering, 2004. ISSRE 2004. 15th International Symposium on, 2004)

Compressing historical information in sensor networks - Deligiannakis,Antonios; Kotidis,Yannis; Roussopoulos, Nick (Proceedings of the 2004 ACM SIGMOD international conference on Management of data - SIGMOD '04, 2004)

Computation of Green's function for finite-size photonic crystals by boundary element method - Seydou,F.; Ramahi,O.; Duraiswami, Ramani; Seppdnen,T. (Antennas and Propagation Society International Symposium, 2004. IEEE, 2004)
We have derived a new integral equation method for computing the Green's function for 2D electromagnetic wave propagation in a finite size photonic crystal. The method is also used for deriving the multipole expansions for the case of circular cylinders. This derivation is different from the ones in the literature. Our numerical results show an excellent agreement of the two algorithms. In the future we would like to expand the method to the numerical solution of the three-dimensional electromagnetic problem.
Keywords: 2D; boundary; boundary-elements; circular; crystals; cylinders; electromagnetic; element; equation; equations; expansions; finite-size; function; function; Green; Green's; integral; method; methods; multipole; photonic; propagation; wave

Contour-based 3D Face Modeling from a Monocular Video - Gupta, H.; Roy Chowdhury, A.K.; Chellapa, Rama (Proceedings of the British Machine Vision Conference, 2004)
In this paper, we present a novel 3D face modeling approach from a monoc-ular video captured using a conventional camera. The proposed algorithm relies on matching a generic 3D face model to the outer contours of the face to be modeled and a few of its internal features. At the first stage of the method, we estimate the head pose by comparing the edges extracted from video frames, with the contours extracted from a generic face model. Next, the generic face model is adapted to the actual 3D face by global and local deformations. An affine model is used for global deformation. The 3D model is locally deformed by computing the optimal perturbations of a sparse set of control points using a stochastic search optimization method. The deforma- tions are integrated over a set of poses in the video sequence, leading to an accurate 3D model.

DateLens: A fisheye calendar interface for PDAs - Bederson, Benjamin B.; Clamage,A.; Czerwinski,M.P.; Robertson,G.G. (ACM Transactions on Computer-Human Interaction (TOCHI), 2004)

Defect evolution in a product line environment - Zelkowitz, Marvin V; Rus,Ioana (Journal of Systems and Software, 2004)
One mechanism used for monitoring the development of the Space Shuttle flight control software, in order to minimize any risks to the missions, is the independent verification and validation (IV&V) process. Using data provided by both the Shuttle software developer and the IV&V contractor, in this paper we describe the overall IV&V process as used on the Space Shuttle program and provide an analysis of the use of metrics to document and control this process over multiple releases of this software. Our findings reaffirm the value of IV&V, show the impact of IV&V on multiple releases of a large complex software system, and indicate that some of the traditional measures of defect detection and repair are not applicable in a multiple-release environment such as this one.
Keywords: Evolutionary software; Life and mission critical software; metrics; Process characterization; Product line development; Software independent verification and validation; Software safety and reliability; Space Shuttle program

A descriptive encoding language for evolving modular neural networks - Jung,J. Y; Reggia, James A. (Genetic and Evolutionary Computation–GECCO 2004, 2004)

Determining Causes and Severity of End-User Frustration - Ceaparu,Irina; Lazar,Jonathan; Bessiere,Katie; Robinson,John; Shneiderman, Ben (International Journal of Human-Computer Interaction, 2004)
Although computers are beneficial to individuals and society, frequently users encounter frustrating experiences when using computers. This study represents an attempt to measure, in 111 participants, the frequency, the cause, and the level of severity of frustrating experiences. The data show that frustrating experiences happen on a frequent basis. The applications in which the frustrating experiences happened most frequently were Web browsing, e-mail, and word processing. The most-cited causes of frustrating experiences were error messages, dropped network connections, long download times, and hard-to-find features. The time lost due to frustrating experiences ranged from 47% to 53% of time spent on a computer, depending on the location and study method. After extreme cases were discarded, the time lost was still above 38%. These disturbing results should be a basis for future study.Although computers are beneficial to individuals and society, frequently users encounter frustrating experiences when using computers. This study represents an attempt to measure, in 111 participants, the frequency, the cause, and the level of severity of frustrating experiences. The data show that frustrating experiences happen on a frequent basis. The applications in which the frustrating experiences happened most frequently were Web browsing, e-mail, and word processing. The most-cited causes of frustrating experiences were error messages, dropped network connections, long download times, and hard-to-find features. The time lost due to frustrating experiences ranged from 47% to 53% of time spent on a computer, depending on the location and study method. After extreme cases were discarded, the time lost was still above 38%. These disturbing results should be a basis for future study.

An Efficient and Robust Human Classification Algorithm using Finite Frequencies Probing - Yang Ran; Weiss, I.; Qinfen Zheng; Davis, Larry S. (Computer Vision and Pattern Recognition Workshop, 2004. CVPRW '04. Conference on, 2004)
This paper describes a periodicity motion detection based object classification algorithm for infrared videos. Given a detected and tracked object, the goal is to analyze the periodic signature of its motion pattern. We propose an efficient and robust solution, which is related to the frequency estimation in speech recognition. Periodic reference functions are correlated with the video signal. Experimental results for both infrared and visible videos acquired by ground-based as well as airborne moving sensors are presented.

Efficient techniques to explore and rank paths in life science data sources - Lacroix,Z.; Raschid, Louiqa; Vidal,M. E (Data Integration in the Life Sciences, 2004)

Empirical-based estimation of the effect on software dependability of a technique for architecture conformance verification - Asgari, S.; Basili, Victor R.; Costa,P.; Donzelli,P.; Hochstein, L.; Lindvall,M.; Rus,I.; Shull, F.; Tvedt,R.; Zelkowitz, Marvin V (Proceedings of the ICSE 2004 Workshop on Architecting Dependable Systems, Edinburgh, UK, 2004)
The High Dependability Computing Program (HDCP)project is a NASA initiative for increasing dependability of software-based systems. It researches achieving high dependability by introducing new technologies. We focus on the evaluation of the effectiveness of technologies with respect to dependability. We employ empirical evaluation methods along with evaluation testbeds. In this paper, our technology evaluation approach is described. A testbed representative of air traffic control applications is used. An experiment to evaluate a technology to for identification of architectural violations is presented.

Exploiting multiple paths to express scientific queries - Lacroix,Z.; Moths,T.; Parekh,K.; Raschid, Louiqa; Vidal,M. -E (16th International Conference on Scientific and Statistical Database Management, 2004. Proceedings, 2004)
The purpose of this demonstration is to present the main features of the BioNavigation system. Scientific data collection needed in various stages of scientific discovery is typically performed manually. For each scientific object of interest (e.g., a gene, a sequence), scientists query a succession of Web resources following links between retrieved entries. Each of the steps provides part of the intended characterization of the scientific object. This process is sometimes partially supported by hard-coded scripts or complex queries that will be evaluated by a mediation-based data integration system or against a data warehouse. These approaches fail in guiding the scientists during the collection process. In contrast, the BioNavigation approach presented in the paper provides the scientists with information on the available alternative resources, their provenance, and the costs of data collection. The BioNavigation system enhances a mediation-based integration system and provides scientists with support for the following: to ask queries at a high conceptual level; to visualize the multiple alternative resources that may be exploited to execute their data collection queries; to choose the final execution path to evaluate their queries.
Keywords: access protocols; biology computing; BioNavigation system; complex queries; Costs; Data analysis; data handling; Data visualization; data warehouse; Data warehouses; Databases; diseases; distributed databases; hard-coded scripts; information resources; Information retrieval; mediation-based data integration system; multiple paths; query evaluation; Query processing; scientific data collection; scientific discovery; scientific information; scientific information systems; scientific object of interest; scientific queries; sequences; Web resources

Exploring the tradeoff between performance and data freshness in database-driven web servers - Labrinidis,A.; Roussopoulos, Nick (The VLDB Journal, 2004)

Extending self-organizing particle systems to problem solving - Rodríguez,A.; Reggia, James A. (Artificial Life, 2004)

Extracting the frequencies of the pinna spectral notches from measured head-related impulse responses - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2004)
Experimental data are available for the Head‐related impulse response (HRIR) for several azimuth and elevation angles, and for several subjects. The measured HRIR depends on several factors such as reflections from body parts (torso, shoulder, and knees), head diffraction, and reflection/diffraction effects due to the external ear (pinna). Due to the combined influence of these factors on the HRIR, it is difficult to isolate features thought to be perceptually important (such as the frequencies of pinna spectral notches) using standard signal‐processing techniques. Signal‐processing methods to extract the frequencies of the pinna spectral notches from the HRIR are presented. The techniques are applied to extracting the frequencies of the pinna spectral notches from the publicly available HRIR databases. A brief discussion relating the notch frequencies to the physical dimensions and the shape of the pinna is given. [The support of NSF Award ITR‐0086075 is gratefully acknowledged.]

Facial similarity across age, disguise, illumination and pose - Ramanathan,N.; Chellapa, Rama; Roy Chowdhury, A.K. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
Illumination, pose variations, disguises, aging effects and expression variations are some of the key factors that affect the performance of face recognition systems. Face recognition systems have always been studied from a recognition perspective. Our emphasis is on deriving a measure of similarity between faces. The similarity measure provides insights into the role each of the above mentioned variations play in affecting the performance of face recognition systems. In the process of computing the similarity measure between faces, we suggest a framework to compensate for pose variations and introduce the notion of 'half-faces' to circumvent the problem of non-uniform illumination. We used the similarity measure to retrieve similar faces from a database containing multiple images of individuals. Moreover, we devised experiments to study the effect age plays in affecting facial similarity. In conclusion, the similarity measure helps in studying the significance facial features play in affecting the performance of face recognition systems.
Keywords: Aging; database; databases; disguise; effect; Expression; Face; half-face; illumination; image; lighting; pose; recognition; recognition; retrieval; system; variation; visual

Formal Modeling Of Middleware-based Distributed Systems - Ray,Arnab; Cleaveland, Rance (Electronic Notes in Theoretical Computer Science, 2004)
Effective design of middleware-based systems requires modeling notations that allow the use of process-interaction schemes provided by different middleware packages directly in designs. Traditional design notations typically only support a fixed class of interprocess interaction schemes, and designers wishing to use them for modeling middleware-based systems must devote significant effort to encoding the middleware primitives in the notation. In this paper, we demonstrate how a new graphical design notation, Architectural Interaction Diagrams (AIDs), which provides parameterized support for different interaction schemes, may be used to model a real-life middleware-based system like the Event Heap coordination infrastructure of the i-Room ubiquitous computing environment.
Keywords: distributed systems; Formal Methods; Middleware; Software architecture

A Framework for Sharing Voluminous Content in P2P Systems - Tsoumakos,D.; Roussopoulos, Nick (PDPTA, 2004)

Fusion of gait and face for human identification - Kale, A.; Roy Chowdhury, A.K.; Chellapa, Rama (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
Identification of humans from arbitrary view points is an important requirement for different tasks including perceptual interfaces for intelligent environments, covert security and access control etc. For optimal performance, the system must use as many cues as possible and combine them in meaningful ways. In this paper, we discuss fusion of face and gait cues for the single camera case. We present a view invariant gait recognition algorithm for gait recognition. We employ decision fusion to combine the results of our gait recognition algorithm and a face recognition algorithm based on sequential importance sampling. We consider two fusion scenarios: hierarchical and holistic. The first involves using the gait recognition algorithm as a filter to pass on a smaller set of candidates to the face recognition algorithm. The second involves combining the similarity scores obtained individually from the face and gait recognition algorithms. Simple rules like the SUM, MIN and PRODUCT are used for combining the scores. The results of fusion experiments are demonstrated on the NIST database which has outdoor gait and face data of 30 subjects.
Keywords: access; algorithm; analysis; combining; control; covert; cues; data; decision; Environment; Face; fusion; Gait; hierarchical; holistic; human; identification; importance; intelligent; interfaces; invariant; perceptual; recognition; recognition; rules; sampling; score; scores; security; sensor; sequential; similarity; view

Gait-based human identification from a monocular video sequence - Kale, A.; Sundaresan, A.; Roy Chowdhury, A.K.; Chellapa, Rama (Handbook on Pattern Recognition and Computer Vision, 2004)
Human gait is a spatio-temporal phenomenon that characterizes the motion char-acteristics of an individual. It is possible to detect and measure gait even in low- resolution video. In this chapter, we discuss algorithms for identifying people by their gait from a monocular video sequence. Human identification using gait, sim- ilar to text-based speaker identification, involves different individuals performing the same task and a template-matching approach is suitable for such problems. In situations where the amount of training data is limited, we demonstrate the utility of a simple width feature for gait recognition. By virtue of their determin- istic nature, template matching methods have limited noise resilience. In order to deal with noise we introduce a systematic approach to gait recognition by building representations for the structural and dynamic components of gait using exemplars and hidden Markov models (HMMs). The above methods assume that an exact side-view of the subject is available in the probe sequence. For the case when the person walks at an arbitrary angle far away from the camera we present a view invariant gait recognition algorithm which is based on synthesizing a side view of a person from an arbitrary monocular view.

Hierarchical in-network data aggregation with quality guarantees - Deligiannakis,A.; Kotidis,Y.; Roussopoulos, Nick (Advances in Database Technology-EDBT 2004, 2004)

Identification of humans using gait - Kale, A.; Sundaresan, A.; Rajagopalan, AN; Cuntoor, N.P.; Roy-Chowdhury, A.K.; Kruger, V.; Chellapa, Rama (Image Processing, IEEE Transactions on, 2004)
We propose a view-based approach to recognize humans from their gait. Two different image features have been considered: the width of the outer contour of the binarized silhouette of the walking person and the entire binary silhouette itself. To obtain the observation vector from the image features, we employ two different methods. In the first method, referred to as the indirect approach, the high-dimensional image feature is transformed to a lower dimensional space by generating what we call the frame to exemplar (FED) distance. The FED vector captures both structural and dynamic traits of each individual. For compact and effective gait representation and recognition, the gait information in the FED vector sequences is captured in a hidden Markov model (HMM). In the second method, referred to as the direct approach, we work with the feature vector directly (as opposed to computing the FED) and train an HMM. We estimate the HMM parameters (specifically the observation probability B) based on the distance between the exemplars and the image features. In this way, we avoid learning high-dimensional probability density functions. The statistical nature of the HMM lends overall robustness to representation and recognition. The performance of the methods is illustrated using several databases.
Keywords: Automated; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; binary silhouette; frame to exemplar distance; gait databases; gait recognition; hidden Markov model; human identification; image features; observation probability; observation vector; hidden Markov models; image recognition; image representation; image sequences; pro; Biological; Models; Computer-Assisted; Models; Computer-Assisted; Subtraction Technique; Task Performance and Analysis; Video Recording; Statistical; Pattern Recognition

Immediate usability: a case study of public access design for a community photo library - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Interacting with Computers, 2004)
This paper describes a novel instantiation of a digital photo library in a public access system. It demonstrates how designers can utilize characteristics of a target user community (social constraints, trust, and a lack of anonymity) to provide capabilities, such as unrestricted annotation and uploading of photos, which would be impractical in other types of public access systems. It also presents a compact set of design principles and guidelines for ensuring the immediate usability of public access information systems. These principles and guidelines were derived from our experience developing PhotoFinder Kiosk, a community photo library. Attendees of a major HCI conference (CHI 2001 Conference on Human Factors in Computing Systems) successfully used the tool to browse and annotate collections of photographs spanning 20 years of HCI-related conferences, producing a richly annotated photo history of the field of human–computer interaction. Observations and usage log data were used to evaluate the tool and develop the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces.
Keywords: Casual use; Community photo library; direct annotation; direct manipulation; Drag-and-drop; Group annotation; Immediate usability; Photo collection; Public access system; Walk-up-and-use; Zero-trial learning

Inducing frame semantic verb classes from WordNet and LDOCE - Green,R.; Dorr, Bonnie J; Resnik, Philip (Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, 2004)
This paper presents SemFrame, a systemthat induces frame semantic verb classes from WordNet and LDOCE. Semantic frames are thought to have significant potential in resolving the paraphrase problem challenging many language- based applications. When compared to the handcrafted FrameNet, SemFrame achieves its best recall-precision balance with 83.2% recall (based on SemFrame's coverage of FrameNet frames) and 73.8% precision (based on SemFrame verbs’ semantic relatedness to frame-evoking verbs). The next best performing semantic verb classes achieve 56.9% recall and 55.0% precision.

An information theoretic criterion for evaluating the quality of 3-D reconstructions from video - Roy-Chowdhury, A.K.; Chellapa, Rama (Image Processing, IEEE Transactions on, 2004)
Even though numerous algorithms exist for estimating the three-dimensional (3-D) structure of a scene from its video, the solutions obtained are often of unacceptable quality. To overcome some of the deficiencies, many application systems rely on processing more data than necessary, thus raising the question: how is the accuracy of the solution related to the amount of data processed by the algorithm? Can we automatically recognize situations where the quality of the data is so bad that even a large number of additional observations will not yield the desired solution? Previous efforts to answer this question have used statistical measures like second order moments. They are useful if the estimate of the structure is unbiased and the higher order statistical effects are negligible, which is often not the case. This paper introduces an alternative information-theoretic criterion for evaluating the quality of a 3-D reconstruction. The accuracy of the reconstruction is judged by considering the change in mutual information (MI) (termed as the incremental MI) between a scene and its reconstructions. An example of 3-D reconstruction from a video sequence using optical flow equations and known noise distribution is considered and it is shown how the MI can be computed from first principles. We present simulations on both synthetic and real data to demonstrate the effectiveness of the proposed criterion.
Keywords: 3D reconstruction; algorithms; Artificial intelligence; Automated; Reproducibility of Results; Sensitivity and Specificity; Signal Processing; Computer Graphics; Computer-Assisted; Imaging; Computer-Assisted; Software Validation; Subtraction Technique; Video Recording; Image Enhancement; Image Interpretation; Image reconstruction; Image sequences; information theoretic criterion; Mutual information; NOISE; noise distribution; optical flow equations; second order moments; statistical analysis; Three-Dimensional; Information Storage and Retrieval; Information Theory; Movement; Pattern Recognition; Video sequences; video signal processing

Interlingual Annotation for MT Development - Reeder,Florence; Dorr, Bonnie J; Farwell,David; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Mitamura,Teruko; Miller,Keith; Rambow,Owen; Siddharthan,Advaith (Machine Translation: From Real Users to ResearchMachine Translation: From Real Users to Research, 2004)
MT systems that use only superficial representations, including the current generation of statistical MT systems, have been successful and useful. However, they will experience a plateau in quality, much like other “silver bullet” approaches to MT. We pursue work on the development of interlingual representations for use in symbolic or hybrid MT systems. In this paper, we describe the creation of an interlingua and the development of a corpus of semantically annotated text, to be validated in six languages and evaluated in several ways. We have established a distributed, well-functioning research methodology, designed a preliminary interlingua notation, created annotation manuals and tools, developed a test collection in six languages with associated English translations, annotated some 150 translations, and designed and applied various annotation metrics. We describe the data sets being annotated and the interlingual (IL) representation language which uses two ontologies and a systematic theta-role list. We present the annotation tools built and outline the annotation process. Following this, we describe our evaluation methodology and conclude with a summary of issues that have arisen.

Interlingual annotation of multilingual text corpora - Farwell,D.; Helmreich,S.; Dorr, Bonnie J; Habash,N.; Reeder,F.; Miller,K.; Levin,L.; Mitamura,T.; Hovy,E.; Rambow,O.; others (Proceedings of the North American Chapter of the Association for Computational Linguistics Workshop on Frontiers in Corpus Annotation, 2004)
This paper describes a multi-site project toannotate six sizable bilingual parallel corpora for interlingual content. After presenting the background and objectives of the effort, we describe the data set that is being annotated, the interlingua representation language used, an interface environment that supports the an- notation task and the annotation process itself. We will then present a preliminary version of our evaluation methodology and conclude with a summary of the current status of the project along with a number of issues which have arisen.

Links and paths through life sciences data sources - Lacroix,Z.; Murthy,H.; Naumann,F.; Raschid, Louiqa (Data Integration in the Life Sciences, 2004)

Method of designing signaling networks for internet telephony - Aravamudan,Murali; Kumaran,Krishnan; Ramakrishnan,Kajamalai Gopalaswamy; Srinivasan, Aravind (2004)
A method is disclosed for designing a signaling network of call coordinators (CCs) for internet telephony. The new method can be used to design a CC network of arbitrary size that satisfies, with high probability, limitations on the maximum number of sockets per CC and on the maximum number of hops between an arbitrary pair of switches in the network. According to the disclosed method, the network of CCs is treated initially as a collection of isolated points, one point for each CC. Then, links are added between pairs of CCs, excluding pairs lying within the same switch. The links are added randomly, but with a particular probability p, which may be different for different pairs. Thus, whether a given link is added depends, in effect, upon the outcome of a loaded coin toss in which the probability of a positive outcome is p.

A model of BGP routing for network engineering - Feamster, Nick; Winick,Jared; Rexford,Jennifer (SIGMETRICS Perform. Eval. Rev., 2004)
The performance of IP networks depends on a wide variety of dynamic conditions. Traffic shifts, equipment failures, planned maintenance, and topology changes in other parts of the Internet can all degrade performance. To maintain good performance, network operators must continually reconfigure the routing protocols. Operators configure BGP to control how traffic flows to neighboring Autonomous Systems (ASes), as well as how traffic traverses their networks. However, because BGP route selection is distributed, indirectly controlled by configurable policies, and influenced by complex interactions with intradomain routing protocols, operators cannot predict how a particular BGP configuration would behave in practice. To avoid inadvertently degrading network performance, operators need to evaluate the effects of configuration changes before deploying them on a live network. We propose an algorithm that computes the outcome of the BGP route selection process for each router in a single AS, given only a static snapshot of the network state, without simulating the complex details of BGP message passing. We describe a BGP emulator based on this algorithm; the emulator exploits the unique characteristics of routing data to reduce computational overhead. Using data from a large ISP, we show that the emulator correctly computes BGP routing decisions and has a running time that is acceptable for many tasks, such as traffic engineering and capacity planning.
Keywords: BGP; modeling; Routing; traffic engineering

Modeling BGP route selection within an AS - Feamster, Nick; Rexford,J. (IEEE/ACM Transactions on Networking, 2004)
This paper presents a provably correct model that computes the out-come of the BGP decision process for each router in a single AS, without simulating the complex details of BGP message passing. The model requires only static inputs that can be easily obtained from the routers: the set of candidate routes to a destination (and the routers in the AS at which they were learned), import policies and other session-level parameters, and internal topology. We pro- pose algorithms for computing route selection under four different network configurations: with the MED attribute compared across all routes, and compared only across routes from the same neigh- boring AS; and with a “full mesh” internal BGP (iBGP) topology versus an iBGP topology that uses a scalability technique called “route reflection”. For each scenario, we derive general properties of the routes that routers ultimately select, present an efficient al- gorithm for computing the outcome of BGP route selection, and prove the algorithm’s correctness. Studying the general properties and computational overhead of modeling the route selection pro- cess in each of these cases provides insights into the unnecessary complexity introduced by the MED attribute and route reflection; we use these insights to propose improvements to BGP that achieve the same goals as MED and route reflection without introducing the negative side effects of these features. We have implemented some of the algorithms from this paper in a prototype and have shown them to be efficient and accurate enough for many traffic engineer- ing tasks.

Multiple view tracking of humans modelled by kinematic chains - Sundaresan, A.; Chellapa, Rama; RoyChowdhury, R. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We use a kinematic chain to model human body motion. We estimate the kinematic chain motion parameters using pixel displacements calculated from video sequences obtained from multiple calibrated cameras to perform tracking. We derive a linear relation between the 2D motion of pixels in terms of the 3D motion parameters of various body parts using a perspective projection model for the cameras, a rigid body motion model for the base body and the kinematic chain model for the body parts. An error analysis of the estimator is provided, leading to an iterative algorithm for calculating the motion parameters from the pixel displacements. We provide experimental results to demonstrate the accuracy of our formulation. We also compare our iterative algorithm to the noniterative algorithm and discuss its robustness in the presence of noise.
Keywords: 3D; algorithm; analysis; body; calibrated; cameras; chain; displacement; error; estimation; human; image; iterative; kinematic; kinematics; methods; model; MOTION; motion; multiple; parameters; perspective; Pixel; processing; projection; sequences; signal; tracking; video; view

Multi-resolution modeling, visualization and streaming of volume meshes - Cignoni,P.; De Floriani, Leila; Lindstrom,P.; Pascucci,V.; Rossignac,J.; Silva,C. (Eurographics 2004, Tutorials 2: Multi-resolution Modeling, Visualization and Streaming of Volume Meshes, 2004)

Oasys: An opinion analysis system - Cesarano,C.; Dorr, Bonnie J; Picariello, A.; Reforgiato,D.; Sagoff,A.; V.S. Subrahmanian (AAAI Spring symposium on Computational Approaches to Analyzing Weblogs, 2004)
There are numerous applications in which we would like toassess what opinions are being expressed in text documents. For example, Martha Stewart’s company may have wished to assess the degree of harshness of news articles about her in the recent past. Likewise, a World Bank official may wish to as- sess the degree of criticism of a proposed dam in Bangladesh. The ability to gauge opinion on a given topic is therefore of critical interest. In this paper, we develop a suite of algo- rithms which take as input, a set D of documents as well as a topic t, and gauge the degree of opinion expressed about topic t in the set D of documents. Our algorithms can return both a number (larger the number, more positive the opinion) as well as a qualitative opinion (e.g. harsh, complimentary). We as- sess the accuracy of these algorithms via human experiments and show that the best of these algorithms can accurately re- flect human opinions. We have also conducted performance experiments showing that our algorithms are computationally fast.

Occurrence and distribution of Vibrio cholerae in the coastal environment of Peru - Gil,Ana I.; Louis,Valérie R.; Rivera,Irma N. G.; Lipp,Erin; Huq,Anwar; Lanata,Claudio F.; Taylor,David N.; Russek‐Cohen,Estelle; Choopun,Nipa; Sack,R. Bradley; Rita R Colwell (Environmental Microbiology, 2004)
The occurrence and distribution of Vibrio cholerae in sea water and plankton along the coast of Peru were studied from October 1997 to June 2000, and included the 1997–98 El Niño event. Samples were collected at four sites in coastal waters off Peru at monthly intervals. Of 178 samples collected and tested, V. cholerae O1 was cultured from 10 (5.6%) samples, and V. cholerae O1 was detected by direct fluorescent antibody assay in 26 out of 159 samples tested (16.4%). Based on the number of cholera cases reported in Peru from 1997 to 2000, a significant correlation was observed between cholera incidence and elevated sea surface temperature (SST) along the coast of Peru (P < 0.001). From the results of this study, coastal sea water and zooplankton are concluded to be a reservoir for V. cholerae in Peru. The climate–cholera relationship observed for the 1997–98 El Niño year suggests that an early warning system for cholera risk can be established for Peru and neighbouring Latin American countries.

Pandemic strains of O3:K6 Vibrio parahaemolyticus in the aquatic environment of Bangladesh - Islam,M. S.; Tasmin,Rizwana; Khan,Sirajul I. s l a m; Bakht,Habibul B. M.; Mahmood,Zahid H. a y a t; Rahman,M. Z. i a u r; Bhuiyan,Nurul A. m i n; Nishibuchi,Mitsuaki; Nair,G. B. a l a k r i s h; Sack,R. B. r a d l e y; Huq,Anwar; Rita R Colwell; et al. (Canadian Journal of Microbiology, 2004)
A total of 1500 environmental strains of Vibrio parahaemolyticus, isolated from the aquatic environment of Bangladesh, were screened for the presence of a major V. parahaemolyticus virulence factor, the thermostable direct haemolysin (tdh) gene, by the colony blot hybridization method using a digoxigenin-labeled tdh gene probe. Of 1500 strains, 5 carried the tdh sequence, which was further confirmed by PCR using primers specific for the tdh gene. Examination by PCR confirmed that the 5 strains were V. parahamolyticus and lacked the thermostable direct haemolysin-related haemolysin (trh) gene, the alternative major virulence gene known to be absent in pandemic strains. All 5 strains gave positive Kanagawa phenomenon reaction with characteristic beta-haemolysis on Wagatsuma agar medium. Southern blot analysis of the HindIII-digested chromosomal DNA demonstrated, in all 5 strains, the presence of 2 tdh genes common to strains positive for Kanagawa phenomenon. However, the 5 strains were found to belong to 3 different serotypes (O3:K29, O4:K37, and O3:K6). The 2 with pandemic serotype O3:K6 gave positive results in group-specific PCR and ORF8 PCR assays, characteristics unique to the pandemic clone. Clonal variations among the 5 isolates were analyzed by comparing RAPD and ribotyping patterns. Results showed different patterns for the 3 serotypes, but the pattern was identical among the O3:K6 strains. This is the first report on the isolation of pandemic O3:K6 strains of V. parahaemolyticus from the aquatic environment of Bangladesh.

Querying structured data in an unstructured P2P system - Kantere,Verena; Tsoumakos,Dimitrios; Roussopoulos, Nick (Proceedings of the 6th annual ACM international workshop on Web information and data management - WIDM '04, 2004)

Querying Web-Accessible Life Science Sources: Which paths to choose? - Bleiholder,J.; Naumann,F.; Raschid, Louiqa; Vidal,M. E (Proceedings of VLDB Workshop on Information Integration on the Web (IIWeb-2004), 2004)

Reducing storage requirements for biological sequence comparison - Roberts,Michael; Hayes,Wayne; Hunt,Brian R.; Mount, Stephen M.; Yorke,James A. (BioinformaticsBioinformatics, 2004)
Motivation: Comparison of nucleic acid and protein sequences is a fundamental tool of modern bioinformatics. A dominant method of such string matching is the ‘seed-and-extend’ approach, in which occurrences of short subsequences called ‘seeds’ are used to search for potentially longer matches in a large database of sequences. Each such potential match is then checked to see if it extends beyond the seed. To be effective, the seed-and-extend approach needs to catalogue seeds from virtually every substring in the database of search strings. Projects such as mammalian genome assemblies and large-scale protein matching, however, have such large sequence databases that the resulting list of seeds cannot be stored in RAM on a single computer. This significantly slows the matching process.Results: We present a simple and elegant method in which only a small fraction of seeds, called ‘minimizers’, needs to be stored. Using minimizers can speed up string-matching computations by a large factor while missing only a small fraction of the matches found using all seeds.

Resource policing to support fine-grain cycle stealing in networks of workstations - Ryu, K. D; Hollingsworth, Jeffrey K (IEEE Transactions on Parallel and Distributed Systems, 2004)
We present the design, implementation, and performance evaluation of a suite of resource policing mechanisms that allow guest processes to efficiently and unobtrusively exploit otherwise idle workstation resources. Unlike traditional policies that harvest cycles only from unused machines, we employ fine-grained cycle stealing to exploit resources even from machines that have active users. We developed a suite of kernel extensions that enable these policies to operate without significantly impacting host processes: 1) a new starvation-level CPU priority for guest jobs, 2) a new page replacement policy that imposes hard bounds on physical memory usage by guest processes, and 3) a new I/O scheduling mechanism called rate windows that throttle guest processes' usage of I/O and network bandwidth. We evaluate both the individual impacts of each mechanism, and their utility for our fine-grain cycle stealing.
Keywords: 65; Application software; Bandwidth; cluster computing; Computer networks; Computer Society; Concurrent computing; cycle stealing; cycle stealing.; grid computing; I/O scheduling; Intelligent networks; Kernel; network bandwidth; networks of workstations; page replacement policy; parallel computing; performance evaluation; Processor scheduling; resource allocation; resource scheduling; starvation-level CPU priority; workstation clusters; workstation resources; Workstations

Semantic annotation and lexico-syntactic paraphrase - Dorr, Bonnie J; Green,R.; Levin,L.; Rambow,O.; Farwell,D.; Habash,N.; Helmreich,S.; Hovy,E.; Miller,K.J.; Mitamura,T.; others (Proceedings of the 4th International Conference on Language Resources and Evaluation (LREC) Workshop on Building Lexical Resources from Semantically Annotated Corpora, 2004)
The IAMTC project (Interlingual Annotation of Multilingual Translation Corpora) is developing an interlingual representation frameworkfor annotation of parallel corpora (English paired with Arabic, French, Hindi, Japanese, Korean, and Spanish) with deep-semantic representations. In particular, we are investigating meaning equivalent paraphrases involving conversives and non-literal language use, as well as extended paraphrases involving syntax, lexicon, and grammatical features. The interlingua representation has three levels of depth. Each level is characterized by the types of meaning equivalent paraphrases that receive identical representations at that level.

Semantic Annotation for Interlingual Representation of Multilingual Texts - Mitamura,T.; Miller,K.; Dorr, Bonnie J; Farwell,D.; Habash,N.; Helmreich,S.; Hovy,E.; Levin,L.; Rambow,O.; Reeder,F.; others (Workshop Programme, 2004)
This paper describes the annotation process being used in a multi-site project to create six sizable bilingual parallel corpora annotated with a consistent interlingua representation. After presenting the background and objectives of the effort, we describe the multilingual corpora and the three stages of interlingual representation being developed. We then focus on the annotation process itself, including an interface environment that supports the annotation task, and the methodology for evaluating the interlingua representation. Finally, we discuss some issues encountered during the annotation tasks. The resulting annotated multilingual corpora will be useful for a wide range of natural language processing research tasks, including machine translation, question answering, text summarization, and information extraction.

Social and psychological influences on computer user frustration - Bessiere,K.; Ceaparu,I.; Lazar,J.; Robinson,J.; Shneiderman, Ben (Media access: Social and psychological dimensions of new technology useMedia access: Social and psychological dimensions of new technology use, 2004)

Solution Conformation of Lys63-linked Di-ubiquitin Chain Provides Clues to Functional Diversity of Polyubiquitin Signaling - Varadan,Ranjani; Assfalg,Michael; Haririnia,Aydin; Raasi,Shahri; Pickart,Cecile; Fushman, David (Journal of Biological ChemistryJ. Biol. Chem., 2004)
Diverse cellular events are regulated by post-translational modification of substrate proteins via covalent attachment of one or a chain of ubiquitin molecules. The outcome of (poly)ubiquitination depends upon the specific lysine residues involved in the formation of polyubiquitin chains. Lys48-linked chains act as a universal signal for proteasomal degradation, whereas Lys63-linked chains act as a specific signal in several non-degradative processes. Although it has been anticipated that functional diversity between alternatively linked polyubiquitin chains relies on linkage-dependent differences in chain conformation/topology, direct structural evidence in support of this model has been lacking. Here we use NMR methods to determine the structure of a Lys63-linked di-ubiquitin chain. The structure is characterized by an extended conformation, with no direct contact between the hydrophobic residues Leu8, Ile44, and Val70 on the ubiquitin units. This structure contrasts with the closed conformation observed for Lys48-linked di-ubiquitin wherein these residues form the interdomain interface (Cook, W. J., Jeffrey, L. C., Carson, M., Zhijian, C., and Pickart, C. M. (1992) J. Biol. Chem. 267, 16467-16471; Varadan, R., Walker, O., Pickart, C., and Fushman, D. (2002) J. Mol. Biol. 324, 637-647). Consistent with the open conformation of the Lys63-linked di-ubiquitin, our binding studies show that both ubiquitin domains in this chain can bind a ubiquitin-associated domain from HHR23A independently and in a mode similar to that for mono-ubiquitin. In contrast, Lys48-linked di-ubiquitin binds in a different, higher affinity mode that has yet to be determined. This is the first experimental evidence that alternatively linked polyubiquitin chains adopt distinct conformations.

Some foundational problems in interdomain routing - Feamster, Nick; Balakrishnan,H.; Rexford,J. (Proceedings of Third Workshop on Hot Topics in Networks (HotNets-III), 2004)
The substantial complexity of interdomain routing in theInternet comes from the need to support flexible poli- cies while scaling to a large number of Autonomous Systems. Despite impressive progress in characterizing the various ills of the Border Gateway Protocol (BGP), many problems remain unsolved, and the behavior of the routing system is still poorly understood. This paper argues that we must understand interdomain routing in terms of: (1) intrinsic properties and design tradeoffs of policy-based routing, independent of the specific routing protocol and (2) properties that relate to artifacts in to- day’s protocol. We pose open questions for the research community that, if answered, should help us understand why BGP’s many problems are so difficult to fix. Un- derstanding the fundamental properties of interdomain routing will help us decide how to make progress, be it making backward-compatible modifications to BGP or designing a radically different protocol.

A study of the pinna anthropometry and the spectral notch frequencies - Raykar,Vikas C.; Duraiswami, Ramani; Yegnanarayana,B. (The Journal of the Acoustical Society of America, 2004)
The head‐related transfer function (HRTF) varies significantly between individuals due to the different sizes and shapes of different anatomical parts like the pinnae, head, and torso. Applications in the creation of virtual auditory displays require individual HRTFs for perceptual fidelity. A generic HRTF would not work satisfactorily, since it has been shown that nonindividual HRTFs result in poor elevation perception. While good geometrical models exist for the effects of head, torso, and shoulders, a simple model for the pinna that connects the anthropometry to the features in the HRTF does not exist. One of the prominent cues contributed by the pinna are the sharp spectral notches, which encode the elevation of the sound source. Recently, we proposed a method to extract the frequencies of the pinna spectral notches from the HRTF. In this paper we study the relationship between the extracted notch frequency and pinna anthropometry. Based on these observations new approaches for HRTF customization can be developed. [The support of NSF Award ITR‐0086075 is gratefully acknowledged.]

Techniques for optimization of queries on integrated biological resources - Lacroix,Z.; Raschid, Louiqa; Eckman,B. A (Journal of bioinformatics and computational biology, 2004)

Temporally asymmetric learning supports sequence processing in multi-winner self-organizing maps - Schulz,R.; Reggia, James A. (Neural Computation, 2004)

Understanding tuberculosis epidemiology using structured statistical models - Getoor, Lise; Rhee,Jeanne T; Koller,Daphne; Small,Peter (Artificial Intelligence in Medicine, 2004)
Molecular epidemiological studies can provide novel insights into the transmission of infectious diseases such as tuberculosis. Typically, risk factors for transmission are identified using traditional hypothesis-driven statistical methods such as logistic regression. However, limitations become apparent in these approaches as the scope of these studies expand to include additional epidemiological and bacterial genomic data. Here we examine the use of Bayesian models to analyze tuberculosis epidemiology. We begin by exploring the use of Bayesian networks (BNs) to identify the distribution of tuberculosis patient attributes (including demographic and clinical attributes). Using existing algorithms for constructing BNs from observational data, we learned a BN from data about tuberculosis patients collected in San Francisco from 1991 to 1999. We verified that the resulting probabilistic models did in fact capture known statistical relationships. Next, we examine the use of newly introduced methods for representing and automatically constructing probabilistic models in structured domains. We use statistical relational models (SRMs) to model distributions over relational domains. SRMs are ideally suited to richly structured epidemiological data. We use a data-driven method to construct a statistical relational model directly from data stored in a relational database. The resulting model reveals the relationships between variables in the data and describes their distribution. We applied this procedure to the data on tuberculosis patients in San Francisco from 1991 to 1999, their Mycobacterium tuberculosis strains, and data on contact investigations. The resulting statistical relational model corroborated previously reported findings and revealed several novel associations. These models illustrate the potential for this approach to reveal relationships within richly structured data that may not be apparent using conventional statistical approaches. We show that Bayesian methods, in particular statistical relational models, are an important tool for understanding infectious disease epidemiology.
Keywords: Bayesian networks; epidemiology; Probabilistic and statistical relational models; Tuberculosis

Unit verification: the CARA experience - Ray,A.; Cleaveland, Rance (International Journal on Software Tools for Technology Transfer (STTT), 2004)

Unobtrusiveness and efficiency in idle cycle stealing for PC grids - Ryu, K. D; Hollingsworth, Jeffrey K (Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, 2004)
Summary form only given. Studies have shown that for a significant fraction of the time desktop PCs and workstations are under-utilized. To exploit these idle resources, various desktop/workstation grid systems have been developed. The ultimate goal of such systems is to maximize efficiency of resource usage while maintaining low obtrusiveness to machine owners. To this end, we created a new fine-grain cycle stealing approach and conducted a performance comparison study against the traditional coarse-grain cycle stealing. We developed a prototype of fine-grain cycle stealing, the Linger-Longer system, on a Linux cluster. The experiments on a cluster of desktop Linux PCs with benchmark applications show that, overall, fine-grain cycle stealing can improve efficiency of idle cycle usage by increasing the guest job throughput by 50% to 70%, while limiting obtrusiveness with no more than 3% of host job slowdown.
Keywords: Biological system modeling; Computational modeling; Computer science; Computer simulation; Contracts; desktop grid system; fine-grain cycle stealing approach; grid computing; idle cycle stealing; Linger-Longer system; Linux; Linux cluster; microcomputers; PC grids; Personal communication networks; Prototypes; resource allocation; Throughput; workstation clusters; workstation grid systems; Workstations

Using distributed partial memories to improve self-organizing collective movements - Winder,R.; Reggia, James A. (Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 2004)

Variation of toxigenic Vibrio cholerae O1 in the aquatic environment of Bangladesh and its correlation with the clinical strains - Islam,M. S.; Talukder,K. A.; Khan,N. H.; Mahmud,Z. H.; Rahman,M. Z.; Nair,G. B.; Siddique,A. K. M.; Yunus,M.; Sack,D. A.; Sack,R. B.; Rita R Colwell (Microbiology and immunology, 2004)

Viable but Nonculturable Vibrio Cholerae O1 in the Aquatic Environment of Argentina - Binsztein,Norma; Costagliola,Marcela C.; Pichel,Mariana; Jurquiza,Verónica; Ramírez,Fernando C.; Akselman,Rut; Vacchino,Marta; Huq,Anwarul; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2004)
In Argentina, as in other countries of Latin America, cholera has occurred in an epidemic pattern. Vibrio cholerae O1 is native to the aquatic environment, and it occurs in both culturable and viable but nonculturable (VNC) forms, the latter during interepidemic periods. This is the first report of the presence of VNC V. cholerae O1 in the estuarine and marine waters of the Río de la Plata and the Argentine shelf of the Atlantic Ocean, respectively. Employing immunofluorescence and PCR methods, we were able to detect reservoirs of V. cholerae O1 carrying the virulence-associated genes ctxA and tcpA. The VNC forms of V. cholerae O1 were identified in samples of water, phytoplankton, and zooplankton; the latter organisms were mainly the copepods Acartia tonsa, Diaptomus sp., Paracalanus crassirostris, and Paracalanus parvus. We found that under favorable conditions, the VNC form of V. cholerae can revert to the pathogenic, transmissible state. We concluded that V. cholerae O1 is a resident of Argentinean waters, as has been shown to be the case in other geographic regions of the world.

Wide area performance monitoring using aggregate latency profiles - Zadorozhny,V.; Gal,A.; Raschid, Louiqa; Ye,Q. (Web Engineering, 2004)

Wide baseline image registration with application to 3-D face modeling - Roy-Chowdhury, A.K.; Chellapa, Rama; Keaton, T. (Multimedia, IEEE Transactions on, 2004)
Establishing correspondence between features in two images of the same scene taken from different viewing angles is a challenging problem in image processing and computer vision. However, its solution is an important step in many applications like wide baseline stereo, three-dimensional (3-D) model alignment, creation of panoramic views, etc. In this paper, we propose a technique for registration of two images of a face obtained from different viewing angles. We show that prior information about the general characteristics of a face obtained from video sequences of different faces can be used to design a robust correspondence algorithm. The method works by matching two-dimensional (2-D) shapes of the different features of the face (e.g., eyes, nose etc.). A doubly stochastic matrix, representing the probability of match between the features, is derived using the Sinkhorn normalization procedure. The final correspondence is obtained by minimizing the probability of error of a match between the entire constellation of features in the two sets, thus taking into account the global spatial configuration of the features. The method is applied for creating holistic 3-D models of a face from partial representations. Although this paper focuses primarily on faces, the algorithm can also be used for other objects with small modifications.
Keywords: 2D; 3D; algorithm; baseline; biometrics; Computer; configuration; correspondence; doubly; error; extraction; Face; feature; holistic; image; matching; matrix; minimization; modeling; models; normalization; probability; probability; procedure; processes; processing; recognition; registration; representation; sequences; shapes; Sinkhorn; spatial; statistics; Stochastic; video; vision; wide