Reflecting on Health: A System for Students to Monitor Diet and Exercise - Brown, Brandon; Marshini Chetty; Grimes, Andrea; Harmon, Ellie (SIGCHI EA '06, 2006)
Using an iterative design process, we designed and evaluated a system for college students to encourage the development and maintenance of healthy diet and exercise habits. The system has three components: a camera phone application to support photographic diet and exercise journaling, an automatic workout tracking application for exercise machines in the gym, and a visualization application to support users as they reflect on their diet and exercise activities.
Keywords: diet; exercise; journaling; mobile phone; Visualization

Relational clustering for entity resolution queries - Bhattacharya,I.; Licamele,L.; Getoor, Lise (ICML 2006 Workshop on Statistical Relational Learning (SRL), 2006)
The goal of entity resolution is to recon-cile database references corresponding to the same real-world entities. Given the abun- dance of publicly available databases where entities are not resolved, we motivate the problem of quickly processing queries that require resolved entities from such ‘unclean’ databases. We first propose a cut-based rela- tional clustering formulation for collective en- tity resolution. We then show how it can be performed on-the-fly by adaptively extract- ing and resolving those database references that are the most helpful for resolving the query. We validate our approach on two large real-world publication databases, where we show the usefulness of collective resolution and at the same time demonstrate the need for adaptive strategies for query processing. We then show how the same queries can be answered in real time using our adaptive ap- proach while preserving the gains of collective resolution.

Safe manual memory management in Cyclone - Swamy,Nikhil; Hicks, Michael W.; Morrisett,Greg; Grossman,Dan; Jim,Trevor (Science of Computer Programming, 2006)
The goal of the Cyclone project is to investigate how to make a low-level C-like language safe. Our most difficult challenge has been providing programmers with control over memory management while retaining safety. This paper describes our experience trying to integrate and use effectively two previously-proposed, safe memory-management mechanisms: statically-scoped regions and tracked pointers. We found that these typing mechanisms can be combined to build alternative memory-management abstractions, such as reference counted objects and arenas with dynamic lifetimes, and thus provide a flexible basis. Our experience — porting C programs and device drivers, and building new applications for resource-constrained systems — confirms that experts can use these features to improve memory footprint and sometimes to improve throughput when used instead of, or in combination with, conservative garbage collection.
Keywords: cyclone; Memory management; memory safety; Reaps; Reference counting; regions; unique pointers

Scalable data collection and retrieval infrastructure for digital government applications - Samet, Hanan; Golubchik,Leana (Proceedings of the 2006 international conference on Digital government research, 2006)
In this paper we describe highlights of the project titled "Scalable data collection infrastructure for digital government applications" under the auspices of the Digital Government Research Program of the National Science Foundation. Our research is focused on taking advantage of the distributed nature of data and the interaction with it. Our efforts have been directed at both the systems/theoretical and applications levels. On the systems and theoretical levels, we have continued our development of the BISTRO system (Section 2). On the applications level, work has commenced on the development of a mechanism for spatially tagging text documents for retrieval by search engines based on both content and spatial proximity (Section 3).

A Sensory-Motor Language for Human Activity Understanding - Guerra-Filho,G.; Aloimonos, J. (2006 6th IEEE-RAS International Conference on Humanoid Robots, 2006)
We have empirically discovered that the space of human actions has a linguistic framework. This is a sensory-motor space consisting of the evolution of the joint angles of the human body in movement. The space of human activity has its own phonemes, morphemes, and sentences. We present a human activity language (HAL) for symbolic non-arbitrary representation of visual and motor information. In phonology, we define atomic segments (kinetemes) that are used to compose human activity. We introduce the concept of a kinetological system and propose five basic properties for such a system: compactness, view-invariance, reproducibility, selectivity, and reconstructivity. In morphology, we extend sequential language learning to incorporate associative learning with our parallel learning approach. Parallel learning is effective in identifying the kinetemes and active joints in a particular action. In syntax, we suggest four lexical categories for our human activity language (noun, verb, adjective, and adverb). These categories are combined into sentences through syntax for human movement
Keywords: Actuators; associative learning; atomic segments; computational linguistics; Computer science; Computer vision; Educational institutions; grammars; human activity language; human activity understanding; human movement syntax; Humanoid robots; HUMANS; joint angles; kinetemes; kinetological system; Laboratories; learning (artificial intelligence); List key index terms here; Morphology; motor information; No mare than 5; parallel learning; Reproducibility of results; Robot kinematics; Robot programming; robot vision; sensory-motor language; sequential language learning; symbolic nonarbitrary representation; visual information

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

Session 8A-Combinatorial Optimization and Quantum Computing-Lower Bounds on the Deterministic and Quantum Communication Complexities of Hamming-Distance Problems - Ambainis,A.; Gasarch,W.; Srinivasan, Aravind; Utis,A. (Lecture Notes in Computer Science, 2006)

Shape Similarity Assessment Based On Face Alignment Using Attributed Applied Vectors. - Cardone, Antonio; Gupta, Satyandra K. (CAD Conference, 2006)

Social Capital in Friendship-Event Networks - Licamele,L.; Getoor, Lise (Data Mining, 2006. ICDM '06. Sixth International Conference on, 2006)
In this paper, we examine a particular form of social network which we call a friendship-event network. A friendship-event network captures both the friendship relationship among a set of actors, and also the organizer and participation relationships of actors in a series of events. Within these networks, we formulate the notion of social capital based on the actor-organizer friendship relationship and the notion of benefit, based on event participation. We investigate appropriate definitions for the social capital of both a single actor and a collection of actors. 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 show that our definitions of capital and benefit capture interesting qualitative properties of event series. In addition, we show that social capital is a better publication predictor than publication history.
Keywords: academic; based; capital; Internet; groupware; knowledge; Collaboration; friendship; friendship-event; network; actor-organizer; network; social; systems

Spherical and hemispherical microphone arrays for capture and analysis of sound fields - Duraiswami, Ramani; Zhiyun Li; Zotkin,Dmitry N; Grassi,Elena (The Journal of the Acoustical Society of America, 2006)
The capture of the spatial structure of a sound field and analysis is important in many fields including creating virtual environments, source localization and detection, noise suppression, and beamforming. Spherical microphone arrays are a promising development to help achieve such capture and analysis, and have been studied by several groups. We develop a practical spherical microphone array and demonstrate its utility in applications for sound capture, room measurement and for beamforming and tracking. To accommodate equipment failure and manufacturing imprecision we extend their theory to handle arbitrary microphone placement. To handle speech capture and surveillance we describe the development of a new sensor, the hemispherical microphone array. For each array the practical performance follows that predicted by theory. Future applications and improvements are also discussed. [Work supported by NSF.]

A Step Towards Automated Design of Side Actions in Injection Molding of Complex Parts - Banerjee,Ashis; Gupta, Satyandra K. (Geometric Modeling and Processing - GMP 2006, 2006)
Side actions contribute to mold cost by resulting in an additional manufacturing and assembly cost as well as by increasing the molding cycle time. Therefore, generating shapes of side actions requires solving a complex geometric optimization problem. Different objective functions may be needed depending upon different molding scenarios (e.g., prototyping versus large production runs). Manually designing side actions is a challenging task and requires considerable expertise. Automated design of side actions will significantly reduce mold design lead times. This paper describes algorithms for generating shapes of side actions to minimize a customizable molding cost function.
Keywords: Computer science

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

Summarization-Inspired Temporal-Relation Extraction: Tense-Pair Templates and Treebank-3 Analysis - Dorr, Bonnie J; Gaasterland,Terry (Department of Computer Science, University of Maryland, College Park, 2006)
This document describes the information used for summarization-inspired temporal-relation extraction [Dorr and Gaasterland, 2007]. We present a set of tense/aspect extraction templates that are applied to a Penn Treebank-style analysis of the input sentence. We also present an analysis of tense-pair combinations for different temporal connectives based on a corpus analysis of complex tense structures in Treebank-3. Finally, we include analysis charts and temporal relation tables for all combinations of intervals/points for each legal BTS combinations.
Keywords: *COMPUTATIONAL LINGUISTICS; CYBERNETICS; linguistics; operations research; TEMPORALRELATION EXTRACTION; TENSE-PAIR COMBINATIONS; TEXT PROCESSING

Techniques and processes for improving the quality and performance of open-source software - Porter, Adam; Yilmaz,Cemal; Memon, Atif M.; Krishna,Arvind S.; Schmidt,Douglas C.; Gokhale,Aniruddha (Software Process: Improvement and Practice, 2006)
Open-source development processes have emerged as an effective approach to reduce cycle-time and decrease design, implementation, and quality assurance (QA) costs for certain types of software, particularly systems infrastructure software, such as operating systems (OS), compilers and language processing tools, text and drawing editors, and middleware. This article presents two contributions to the study of open-source software processes. First, we describe key challenges of open-source software and illustrate how QA processes—specifically those tailored to open-source development—help mitigate these challenges better than traditional closed-source processes do. Second, we summarize results of empirical studies that evaluate how our Skoll distributed continuous quality assurance (DCQA) techniques and processes help to resolve key challenges in developing and validating open-source software. Our results show that: (a) using models to configure and guide the DCQA process improves developer understanding of open-source software, (b) improving the diversity of platform configurations helps QA engineers find defects missed during conventional testing, and (c) centralizing control of QA activities helps to eliminate redundant work. Copyright © 2006 John Wiley & Sons, Ltd.
Keywords: distributed continuous quality assurance; open-source software development and testing

Is there a grand challenge or X-prize for data mining? - Piatetsky-Shapiro,Gregory; Grossman,Robert; Djeraba,Chabane; Feldman,Ronen; Getoor, Lise; Zaki,Mohammed (Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, 2006)
This panel will discuss possible exciting and motivating Grand Challenge problems for Data Mining, focusing on bioinformatics, multimedia mining, link mining, text mining, and web mining.
Keywords: Bioinformatics; data mining; grand challenge; image mining; link mining; multimedia mining; text mining; video mining; web mining; X-prize

A Time Saving Method for Human Detection in Wide Angle Camera Images - Zhuolin Jiang; Li,Shao-Fa; Gao,Dong-Fa (Machine Learning and Cybernetics, 2006 International Conference on, 2006)
A time-saving method for human detection in an indoor environment in wide angle camera images is presented in this paper, without using time-consuming template operations such as edge detection and morphological operations. It excludes other objects in motion to detect humans including cases of the partial occlusion of humans, rotation of the head and variation of skin colors. This algorithm is applicable where the memory space is limited and the time requirements are strict, such as in an embedded system. The experimental results show that it took about 0.35 seconds to process the algorithm after the scene study time
Keywords: CAMERAS; Embedded system; human detection; image recognition; Image segmentation; indoor environment; Motion estimation; time-saving method; wide angle camera images

Towards a sensorimotor WordNet SM: Closing the semantic gap - Guerra-Filho,G.; Aloimonos, J. (Proc. of the International WordNet Conference (GWC), 2006)

Towards Dependability in Everyday Software Using Software Telemetry - Gross,Kenny C.; Urmanov,Aleksey; Votta,Lawrence G.; McMaster,Scott; Porter, Adam (Engineering of Autonomic and Autonomous Systems, IEEE International Workshop on, 2006)
Application-level software dependability is difficult to ensure. Thus it?s typically used only in custom systems and is achieved using one-of-a-kind, handcrafted solutions. We are interested in understanding whether and how these techniques can be applied to more common, lower-end systems. To this end, we have adapted a condition-based maintenance (CBM) approach called the Multivariate State Estimation Technique (MSET). This approach automatically creates sophisticated statistical models that predict system failure well before failures occur, leading to simpler and more successful recoveries. We have packaged this approach in the Software Dependability Framework (SDF). The SDF consists of instrumentation and data management libraries, a CBM module, performance visualization tools, and a software architecture that supports system designers. Finally, we evaluated our framework on a simple video game application. Our results suggest that we can cheaply and reliably predict impending runtime failures and respond to them in time to improve the system?s dependability.

Transcriptional Genomics Associates FOX Transcription Factors With Human Heart Failure - Hannenhalli, Sridhar; Putt,Mary E.; Gilmore,Joan M.; Wang,Junwen; Parmacek,Michael S.; Epstein,Jonathan A.; Morrisey,Edward E.; Margulies,Kenneth B.; Cappola,Thomas P. (Circulation, 2006)
Background— Specific transcription factors (TFs) modulate cardiac gene expression in murine models of heart failure, but their relevance in human subjects remains untested. We developed and applied a computational approach called transcriptional genomics to test the hypothesis that a discrete set of cardiac TFs is associated with human heart failure.Methods and Results— RNA isolates from failing (n=196) and nonfailing (n=16) human hearts were hybridized with Affymetrix HU133A arrays, and differentially expressed heart failure genes were determined. TF binding sites overrepresented in the −5-kb promoter sequences of these heart failure genes were then determined with the use of public genome sequence databases. Binding sites for TFs identified in murine heart failure models (MEF2, NKX, NF-AT, and GATA) were significantly overrepresented in promoters of human heart failure genes (P<0.002; false discovery rate 2% to 4%). In addition, binding sites for FOX TFs showed substantial overrepresentation in both advanced human and early murine heart failure (P<0.002 and false discovery rate <4% for each). A role for FOX TFs was supported further by expression of FOXC1, C2, P1, P4, and O1A in failing human cardiac myocytes at levels similar to established hypertrophic TFs and by abundant FOXP1 protein in failing human cardiac myocyte nuclei.Conclusions— Our results provide the first evidence that specific TFs identified in murine models (MEF2, NKX, NFAT, and GATA) are associated with human heart failure. Moreover, these data implicate specific members of the FOX family of TFs (FOXC1, C2, P1, P4, and O1A) not previously suggested in heart failure pathogenesis. These findings provide a crucial link between animal models and human disease and suggest a specific role for FOX signaling in modulating the hypertrophic response of the heart to stress in humans.

TreePlus: Interactive Exploration of Networks with Enhanced Tree Layouts - Lee,B.; Parr,C.S.; Plaisant, Catherine; Bederson, Benjamin B.; Veksler,V.D.; Gray,W.D.; Kotfila,C. (Visualization and Computer Graphics, IEEE Transactions on, 2006)
Despite extensive research, it is still difficult to produce effective interactive layouts for large graphs. Dense layout and occlusion make food Webs, ontologies and social networks difficult to understand and interact with. We propose a new interactive visual analytics component called TreePlus that is based on a tree-style layout. TreePlus reveals the missing graph structure with visualization and interaction while maintaining good readability. To support exploration of the local structure of the graph and gathering of information from the extensive reading of labels, we use a guiding metaphor of "plant a seed and watch it grow." It allows users to start with a node and expand the graph as needed, which complements the classic overview techniques that can be effective at (but often limited to) revealing clusters. We describe our design goals, describe the interface and report on a controlled user study with 28 participants comparing TreePlus with a traditional graph interface for six tasks. In general, the advantage of TreePlus over the traditional interface increased as the density of the displayed data increased. Participants also reported higher levels of confidence in their answers with TreePlus and most of them preferred TreePlus
Keywords: Automated; Software; User-Computer Interface; Biological; Pattern Recognition; data visualization; graph structure; graphical user interface; interactive visual analytics; occlusion; tree-style layout; data visualisation; graphical user interfaces; hidden feature removal; interactive systems; trees (mathematics); Algorithms; Computer Graphics; C

The Trypanosoma cruzi L1Tc and NARTc non-LTR retrotransposons show relative site specificity for insertion - Bringaud,F.; Bartholomeu,D. C; Blandin,G.; Delcher,A.; Baltz,T.; El‐Sayed, Najib M.; Ghedin,E. (Molecular biology and evolution, 2006)

Understanding visuo‐motor primitives for motion synthesis and analysis - Guerra‐Filho,Gutemberg; Aloimonos, J. (Computer Animation and Virtual Worlds, 2006)
The problem addressed in this paper concerns the representation of human movement in terms of atomic visuo-motor primitives considering both generation and perception of movement. We introduce the concept of kinetology, the phonology of human movement, and five principles on which such a system should be based: compactness, view-invariance, reproducibility, selectivity, and reconstructivity. We propose visuo-motor primitives and demonstrate their kinetological properties. Further evaluation is accomplished with experiments on compression and decompression. Our long-term goal is to demonstrate that action has a space characterized by a visuo-motor language. Copyright © 2006 John Wiley & Sons, Ltd.
Keywords: compression; motion synthesis; visuo‐motor primitives

VAST 2006 Contest - A Tale of Alderwood - Grinstein,G.; O'Connell,T.; Laskowski,S.; Plaisant, Catherine; Scholtz,J.; Whiting,M. (Visual Analytics Science And Technology, 2006 IEEE Symposium On, 2006)
Visual analytics experts realize that one effective way to push the field forward and to develop metrics for measuring the performance of various visual analytics components is to hold an annual competition. The first visual analytics science and technology (VAST) contest was held in conjunction with the 2006 IEEE VAST Symposium. The competition entailed the identification of possible political shenanigans in the fictitious town of Alderwood. A synthetic data set was made available as well as tasks. We summarize how we prepared and advertised the contest, developed some initial metrics for evaluation, and selected the winners. The winners were invited to participate at an additional live competition at the symposium to provide them with feedback from senior analysts
Keywords: Alderwood; human; analysis; data; analytics; and; contest; data; information; interaction; sense; making; visual; Science; technology; visualisation

Vehicle Fingerprinting Using Drive-By Sounds - Cevher, V.; Chellapa, Rama; Gurbuz, A.C.; Shah, F.; McClellan, J.H. (CENTER FOR AUTOMATION RESEARCH, UNIVERSITY OF MARYLAND COLLEGE PARK, 2006)
We estimate a vehicle's speed, width, and length by jointly estimating its acoustic wave-pattern using a single passive acoustic sensor that records the vehicle's drive-by noise. The acoustic wave-pattern is estimated using three envelope shape (ES) components, which approximate the shape of the received signal's power envelope. We incorporate the parameters of the ES components along with estimates of the vehicle engine RPM and number of cylinders to form a vehicle profile vector. This vector provides a compressed statistics that can be used for vehicle identification and classification. Vehicle speed estimation and classification results are provided using field data.
Keywords: *ACOUSTIC DETECTORS; *GROUND VEHICLES; *SIGNAL PROCESSING; ACOUSTIC DETECTION AND DETECTORS; AMPLITUDE; Interference; PASSIVE SYSTEMS; spatial distribution; STATISTICAL PROCESSES; SURFACE TRANSPORTATION AND EQUIPMENT; SYMPOSIA; WAVE PROPAGATION

Video Mensuration Using a Stationary Camera - Guo,Feng; Chellapa, Rama (Computer Vision – ECCV 2006Computer Vision – ECCV 2006, 2006)
This paper presents a method for video mensuration using a single stationary camera. The problem we address is simple, i.e., the mensuration of any arbitrary line segment on the reference plane using multiple frames with minimal calibration. Unlike previous solutions that are based on planar rectification, our approach is based on fitting the image of multiple concentric circles on the plane. Further, the proposed method aims to minimize the error in mensuration. Hence we can calculate the mensuration of the line segments not lying on the reference plane. Using an algorithm for detecting and tracking wheels of an automobile, we have implemented a fully automatic system for wheel base mensuration. The mensuration results are accurate enough that they can be used to determine the vehicle classes. Furthermore, we measure the line segment between any two points on the vehicle and plot them in top and side views.

What are the grand challenges for data mining? - KDD-2006 panel report - Piatetsky-Shapiro,G.; Djeraba,C.; Getoor, Lise; Grossman,R.; Feldman,R.; Zaki,M. (ACM SIGKDD Explorations Newsletter, 2006)
We discuss what makes exciting and motivating Grand Challenge problems for Data Mining, and propose criteria for a good Grand Challenge. We then consider possible GC problems from multimedia mining, link mining, large- scale modeling, text mining, and proteomics. This report is the result of a panel held at KDD-2006 conference.

What do high-level memory models mean for transactions? - Grossman,Dan; Manson,Jeremy; Pugh, William (Proceedings of the 2006 workshop on Memory system performance and correctness - MSPC '06, 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.

Agent-organized networks for dynamic team formation - Gaston,Matthew E.; desJardins, Marie (Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, 2005)
Many multi-agent systems consist of a complex network of autonomous yet interdependent agents. Examples of such networked multi-agent systems include supply chains and sensor networks. In these systems, agents have a select set of other agents with whom they interact based on environmental knowledge, cognitive capabilities, resource limitations, and communications constraints. Previous findings have demonstrated that the structure of the artificial social network governing the agent interactions is strongly correlated with organizational performance. As multi-agent systems are typically embedded in dynamic environments, we wish to develop distributed, on-line network adaptation mechanisms for discovering effective network structures. Therefore, within the context of dynamic team formation, we propose several strategies for agent-organized networks (AONs) and evaluate their effectiveness for increasing organizational performance.
Keywords: multi-agent systems; organizational learning; team formation

Agent-organized networks for multi-agent production and exchange - Gaston,Matthew E.; desJardins, Marie (Proceedings of the 20th national conference on Artificial intelligence - Volume 1, 2005)
As multi-agent systems grow in size and complexity, social networks that govern the interactions among the agents will directly impact system behavior at the individual and collective levels. Examples of such large-scale, networked multi-agent systems include peer-to-peer networks, distributed information retrieval, and agent-based supply chains. One way of dealing with the uncertain and dynamic nature of such environments is to endow agents with the ability to modify the agent social network by autonomously adapting their local connectivity structure. In this paper, we present a framework for agent-organized networks (AONs) in the context of multi-agent production and exchange, and experimentally evaluate the feasibility and efficiency of specific AON strategies. We find that decentralized network adaptation can significantly improve organizational performance. Additionally, we analyze several properties of the resulting network structures and consider their relationship to the observed increase in organizational performance.

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

Algorithms for constructing 3-D point clouds using multiple digital fringe projection patterns - Peng,T.; Gupta,S.K.; Lau,K. (Computer-Aided Design and Applications, 2005)
This paper describes algorithms for generating 3-D point clouds from a set of digital imagesobtained from projecting phase-shifted sinusoidal fringe patterns onto object. In this paper, a mathematical model is introduced for describing the geometric relationship between the fringe patterns being projected, the image captured and the shape of the object being measured. This model allows considerable flexibility in the spatial configuration of shape measurement system. The algorithms for point cloud construction described in this paper present an improvement over the existing algorithms in terms of accuracy, ease of system calibration, and sensitivity to parameter errors. These algorithms have been incorporated in a shape measurement system and shown to have a very good performance.

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

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.

Bounds on the efficiency of generic cryptographic constructions - Gennaro,R.; Gertner,Y.; Katz, Jonathan; Trevisan,L. (SIAM Journal on Computing, 2005)
A central focus of modern cryptography is the construction of efficient, “high-level”cryptographic tools (e.g., encryption schemes) from weaker, “low-level” cryptographic primitives (e.g., one-way functions). Of interest are both the existence of such construc- tions, and their efficiency. Here, we show essentially-tight lower bounds on the best possible efficiency of any black-box construction of some fundamental cryptographic tools from the most basic and widely-used cryptographic primitives. Our results hold in an extension of the model introduced by Impagliazzo and Rudich, and improve and extend earlier results of Kim, Simon, and Tetali. We focus on constructions of pseudorandom generators, universal one-way hash functions, and digital signatures based on one-way permutations, as well as constructions of public- and private-key encryption schemes based on trapdoor permutations. In each case, we show that any black-box construction beating our efficiency bound would yield the unconditional existence of a one-way function and thus, in particular, prove P \= NP

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.

Child's play: a comparison of desktop and physical interactive environments - Fails,J. A; Druin, Allison; Guha,M.L.; Chipman,G.; Simms,S.; Churaman,W. (Proceedings of the 2005 conference on Interaction design and children, 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.

Comparison of the Efficiency of Translation Operators Used in the Fast Multipole Method for the 3D Laplace Equation - Gumerov, Nail A.; Duraiswami, Ramani (Technical Reports from UMIACS UMIACS-TR–2005-09, 2005)
We examine the practical implementation of a fast multipole method algorithm for the rapid summation of Laplace multipoles. Several translation operators with different asymptotic computational and memory complexities have been proposed for this problem. These algorithms include: Method 0 — the originally proposed matrix based translations due to Greengard andRokhlin (1987), Method 1 — the rotation, axial translation and rotation algorithm due to White and Martin Head-Gordon (1993), and Method 3 — the plane-wave version of the multipole-to local translation operator due to Greengard and Rokhlin (1997). We compare the algorithms on data sets of varying size and with varying imposed accuracy requirements. While from the literature it would have been expected that method 2 would always be the method of choice, at least as far as computational speed is concerned, we find that this is not always the case. We find that as far as speed is concerned the choice between methods 1 and 2 depends on problem size and error requirements. Method 2 is the algorithm of choice for large problems where high accuracy is required, though the advantage is not clear cut, especially if memory requirements are an issue. If memory is an issue, Method 1 is the method of choice for most problems. A new analysis of the computational complexities of the algorithms is provided, which explains the observed results. We provide guidelines for choosing parameters for FMM algorithms.
Keywords: Fast Algorithms; Fast Multipole Method; Harmonic analysis; Laplace Equation in 3D; Translation operators

Computation of scattering from clusters of spheres using the fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2005)

Computation of scattering from clusters of spheres using the fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2005)
A T-matrix based method of solution of the multiple scattering problem was presented by the authors [J. Acoust Soc. Am. 112, 2688–2701 (2002)]. This method can be applied to the computation of relatively small problems, since the number of operations required grows with the number of spheres N as O(N3), and with the sixth power of the wave number. The use of iterative techniques accelerated using the fast multipole method (FMM) can accelerate this solution, as presented by Koc and Chew [J. Acoust. Soc. Am. 103, 721–734 (1998)] originally. In this study we present a method that combines preconditioned Krylov subspace iterative techniques, FMM accelerated matrix vector products, a novel FMM-based preconditioner, and fast translation techniques that enable us to achieve an overall algorithm in which the cost of the matrix-vector multiplication grows with N as O(N log N) and with the third power of the wave number. We discuss the convergence of the iterative techniques, selection of the truncation number, errors in the solution, and other issues. The results of the solution of test problems obtained with the method for N ∼ 102–104 for different wave numbers are presented. © 2005 Acoustical Society of America.
Keywords: acoustic wave scattering; convergence of numerical methods; iterative methods; matrix multiplication

Cyclone: A type-safe dialect of C - Grossman,D.; Hicks, Michael W.; Jim,T.; Morrisett,G. (C/C++ Users Journal, 2005)
If any bug has achieved celebrity status, it is thebuffer overflow. It made front-page news as early as 1987, as the enabler of the Morris worm, the first worm to spread through the Internet. In recent years, attacks exploiting buffer overflows have become more frequent, and more virulent. This year, for exam- ple, the Witty worm was released to the wild less than 48 hours after a buffer overflow vulnerability was publicly announced; in 45 minutes, it infected the entire world-wide population of 12,000 machines running the vulnerable programs. Notably, buffer overflows are a problem only for the C and C++ languages—Java and other “safe” lan- guages have built-in protection against them. More- over, buffer overflows appear in C programs written by expert programmers who are security concious— programs such as OpenSSH, Kerberos, and the com- mercial intrusion detection programs that were the target of Witty. This is bad news for C. If security experts have trouble producing overflow-free C programs, then there is not much hope for ordinary C program- mers. On the other hand, programming in Java is no panacea; for certain applications, C has no com- petition. From a programmer’s point of view, all the safe languages are about the same, while C is a very different beast.

Data hiding in curves with application to fingerprinting maps - Gou,Hongmei; M. Wu (Signal Processing, IEEE Transactions on, 2005)
This paper presents a new data hiding method for curves. The proposed algorithm parameterizes a curve using the B-spline model and adds a spread spectrum sequence to the coordinates of the B-spline control points. In order to achieve robust fingerprint detection, an iterative alignment-minimization algorithm is proposed to perform curve registration and to deal with the nonuniqueness of B-spline control points. Through experiments, we demonstrate the robustness of the proposed data-hiding algorithm against various attacks, such as collusion, cropping, geometric transformations, vector/raster-raster/vector conversions, printing-and-scanning, and some of their combinations. We also show the feasibility of our method for fingerprinting topographic maps as well as writings and drawings.
Keywords: (mathematics); algorithm; alignment-minimization; B-spline; CONTROL; curve; data; detection; edge; embedding; encapsulation; fingerprint; geospatial; hiding; identification; image; iterative; method; methods; minimisation; point; protection; registration; sequence; spectrum; splines; spread; watermarking

Discovering a language for human activity - Guerra-Filho,G.; Fermüller, Cornelia; Aloimonos, J. (Proceedings of the AAAI 2005 Fall Symposium on Anticipatory Cognitive Embodied Systems, Washington, DC, 2005)

Document Ranking by Layout Relevance - Huang,Mei; DeMenthon,Daniel; David Doermann; Golebiowski,Lynn (ICDAR, 2005)
This paper describes the development of a new document ranking system based on layout similarity. The user has a need represented by a set of ”wanted” documents, and the system ranks documents in the collection according to this need. Rather than performing complete document analysis, the system extracts text lines, and models layouts as relationships between pairs of these lines. This paper explores three novel feature sets to support scoring in large document collections. First, pairs of lines are used to form quadrilaterals, which are represented by their turning functions. A non- Euclidean distance is used to measure similarity. Second, the quadrilaterals are represented by 5DEuclidean vectors, and third, each line is represented by a 5DEuclidean vector. We compare the classification performance and computation speed of these three feature sets using a large database of diverse documents including forms, academic papers and handwritten pages in English and Arabic. The approach using quadrilaterals and turning functions produces slightly better results, but the approach using vectors to represent text lines is much faster for large document databases.

Dynamic network resource allocation using multimedia content features and ... - M. Wu; Joyce,Robert A.; Vetro,Anthony; Wong,Hau-San; Guan,Ling; Kung,Sun-Yuan (2005)
A method for dynamically allocating network resources while transferring multimedia at variable bit-rates in a network extracts first content features from the multimedia to determine renegotiation points and observation periods. Second content features and traffic features are extracted from the multimedia bit stream during the observation periods. The second content features and the traffic features are combined in a neural network to predict the network resources to be allocated at the renegotiation points.

Dynamic Query Chloropleth Maps for Information Seeking and Decision Making (2003) - Norman,Kent L; Zhao,Haixia; Shneiderman, Ben; Golub,Evan (Institute for Systems Research Technical Reports, 2005)
Information retrieval and visualization can be combined in dynamic query systems that allow users unparalleled access to information for decision making. In this paper, we report on the development and evaluation of a dynamic query system (YMap) that displays information on a chloropleth map using double thumb sliders to select ranges of query variables. The YMap prototype is a Java-Applet that supports panning and zooming. Several usability studies were conducted on early prototypes that resulted in the current version. Applications of YMap for decision making tasks are discussed.
Keywords: Technical Report

Dynamic Query Visualizations on World Wide Web Clients: A DHTML Solution for Maps and Scattergrams (2002) - Golub,Evan; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Dynamic queries are gaining popularity as a method for interactive information visualization. Many implementations have been made on personal computers, and there is increasing interest in web-based designs. While Java and Flash strategies have been developed, we believe that a Dynamic HTML implementation could help promote more widespread use. We implemented double-box range sliders with choropleth maps and scattergrams, which are two popular visualizations, using HTML layers and tables. This paper describes our methods for slider control, visual presentation, and displaying/updating results for these visualizations. Visual design issues innovations and performance enhancements were necessary to create viable designs.
Keywords: Technical Report

Entity resolution in graph data - Bhattacharya,I.; Getoor, Lise (Technical report, University of Maryland, College Park, 2005)
The goal of entity resolution is to reconcile data references corresponding to the same realworld entity. Here we introduce the problem of entity resolution in graphs, where the nodes are the references in the data and the hyper-edges represent the relations that are observed to hold between the references. The goal then is to reconstruct a 'cleaned' entity graph that captures the relations among the true underlying entities from the reference graph. This is an important first step in any graph mining process; mining an unresolved graph will be inefficient and result in inaccurate conclusions. We also motivate collective entity resolution in graphs where references sharing hyper-edges are resolved jointly, as opposed to independent pair-wise resolution of the references. We illustrate the problem of graph-based entity resolution in bibliographic datasets. We discuss several interesting issues such as mul- tiple entity types, local and global resolution and different kinds of graph-based evidence. We formulate the graph-based entity resolution problem as an unsupervised clustering task, where each cluster represents references that map to the same entity, and the similarity measure between two clusters incorporates the similarity of the references attributes and, more interestingly, the similarity between their relations. We explore two different measures of relational similarity. One approach, which we call 'edge detail similarity', explicitly com- pares the individual edges that each cluster participates in, but is expensive to compute. A less computationally intensive alternative is measuring 'neighborhood similarity', which only compares the multi-set of neighboring clusters for each cluster. We perform an extensive empirical evaluation of the two relational similarity measures for author resolution using co- author relations in two real bibliographic datasets. We show that both similarity measures improve performance over unsupervised algorithms that consider only reference attributes. We also describe an efficient implementation and show that these algorithms scale gracefully with increasing size of the data.

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

Exploiting Correlated Attributes in Acquisitional Query Processing - Deshpande, Amol; Guestrin,C.; Wei Hong; Madden,S. (21st International Conference on Data Engineering, 2005. ICDE 2005. Proceedings, 2005)
Sensor networks and other distributed information systems (such as the Web) must frequently access data that has a high per-attribute acquisition cost, in terms of energy, latency, or computational resources. When executing queries that contain several predicates over such expensive attributes, we observe that it can be beneficial to use correlations to automatically introduce low-cost attributes whose observation will allow the query processor to better estimate the selectivity of these expensive predicates. In particular, we show how to build conditional plans that branch into one or more sub-plans, each with a different ordering for the expensive query predicates, based on the runtime observation of low-cost attributes. We frame the problem of constructing the optimal conditional plan for a given user query and set of candidate low-cost attributes as an optimization problem. We describe an exponential time algorithm for finding such optimal plans, and describe a polynomial-time heuristic for identifying conditional plans that perform well in practice. We also show how to compactly model conditional probability distributions needed to identify correlations and build these plans. We evaluate our algorithms against several real-world sensor-network data sets, showing several-times performance increases for a variety of queries versus traditional optimization techniques.
Keywords: acquisitional query processing; Computer networks; Costs; data acquisition; Delay; Distributed computing; distributed information system; Distributed information systems; distributed processing; exponential time algorithm; optimization techniques; polynomial-time heuristic; Polynomials; probability; Query processing; real-time systems; real-world sensor-network; Runtime; Sensor phenomena and characterization; Sensor systems

Extracting regions of symmetry - Gupta,A.; Prasad,V. S.N; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
This paper presents an approach for extending the normalized-cut (n-cut) segmentation algorithm to find symmetric regions present in natural images. We use an existing algorithm to quickly detect possible symmetries present in an image. The detected symmetries are then individually verified using the modified n-cut algorithm to eliminate spurious detections. The weights of the n-cut algorithm are modified so as to include both symmetric and spatial affinities. A global parameter is defined to model the tradeoff between spatial coherence and symmetry. Experimental results indicate that symmetric quality measure for a region segmented by our algorithm is a good indicator for the significance of the principal axis of symmetry.
Keywords: algorithm; coherence; DETECTION; detection; elimination; extraction; feature; image; images; natural; normalized-cut; object; region; segmentation; segmentation; spatial; spurious; symmetry

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

Fast Multipole Method for the Biharmonic Equation - Gumerov, Nail A.; Duraiswami, Ramani (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2005)
The evaluation of sums (matrix-vector products) of the solutions ofthe three-dimensional biharmonic equation can be accelerated using the fast multipole method, while memory requirements can also be significantly reduced. We develop a complete translation theory for these equations. It is shown that translations of elementary solutions of the biharmonic equation can be achieved by considering the translation of a pair of elementary solutions of the Laplace equations. Compared to previous methods that required the translation of five Laplace elementary solutions for the biharmonic Green's function, and much larger numbers for higher order multipoles, our method is significantly more efficient. The theory is implemented and numerical tests presented that demonstrate the performance of the method for varying problem sizes and accuracy requirements. In our implementation the FMM\ is faster than direct solution for a matrix size of $550$ for an accuracy of $10^{-3},$ 950 for an accuracy of $10^{-6} and $N=3550$ for an accuracy of $10^{-9}$.
Keywords: Technical Report

Fingerprinting curves - Gou,H.; Wu,M. (Digital Watermarking, 2005)
This paper presents a new method for robust data hiding in curves and highlights potential applications including digital fingerprinting of map document for trace and track purposes. We parameterize a curve using the B-spline model and add a spread spectrum sequence to the coordinates of the B-spline control points. In order to achieve robust fingerprint detection, we propose an iterative alignment-minimization algorithm to perform curve registration and deal with the non-uniqueness of B-spline control points. We show through experiments the robustness of our method against various attacks such as collusion, geometric transformations and perturbation, printing-and-scanning, and some of their combinations. We demonstrate the feasibility of our method for fingerprinting topographic maps as well as writings and drawings. The extension from hiding data in 2D topographic maps to 3D elevation data sets is also discussed.

Formal approaches to teamwork - Grant,J.; Kraus,S.; Perlis, Don (We Will Show Them: Essays in Honour of Dov Gabbay, 2005)

Frame semantic enhancement of lexical-semantic resources - Green,Rebecca; Dorr, Bonnie J (Proceedings of the ACL-SIGLEX Workshop on Deep Lexical Acquisition, 2005)
SemFrame generates FrameNet-like frames, complete with semantic roles and evoking lexical units. This output can enhance FrameNet by suggesting new frames, as well as additional lexical units that evoke existing frames. SemFrame output can also support the addition of frame semantic relationships to WordNet.

Generating and Querying Semantic Web Environments for Photo Libraries (2005) - Axelrod,Adam; Golbeck,Jennifer; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Online photo libraries require a method to efficiently search a collection of photographs, and retrieve photos with similar attributes. Our motivation was to incorporate an existing collection of over 250 photographs of over 200 faculty members and events spanning 7 decades into a library called CS PhotoHistory that is available in hypertext and on the Semantic Web. In this paper, we identify challenges related to making this repository available on the Semantic Web, including issues of automation, modeling, and expressivity. Using CS PhotoHistory as a case study, we describe the process of creating an ontology and a querying interface for interacting with a digital photo library on the Semantic Web.
Keywords: Technical Report

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 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.

The genome sequence of Trypanosoma cruzi, etiologic agent of Chagas disease - El-Sayed, N.M.; Myler,P. J; Bartholomeu,D. C; Nilsson,D.; Aggarwal,G.; Tran,A. N; Ghedin,E.; Worthey,E. A; Delcher,A. L; Blandin,G.; others (Science, 2005)

Geometric algorithms for computing cutter engagement functions in 2.5D milling operations - Gupta, Satyandra K.; Saini,Sunil K.; Spranklin,Brent W.; Yao,Zhiyang (Computer-Aided Design, 2005)
Cutter engagement is a measure that describes what portion of the cutter is involved in machining at a given instant of time. During profile milling of complex geometries, cutter engagement varies significantly along the cutter path. Cutter engagement information helps in determining the efficiency of the cutter path and also helps in improving it by adjusting the feed rate. This paper describes geometric algorithms for computing piece-wise continuous closed-form cutter engagement functions for 2.5D milling operations. The results produced by our algorithm are compared with the results obtained by discrete simulations of the cutting process and appear to match very well.
Keywords: Cutter engagement; Cutter path planning; Feed rate adjustments

Geometric algorithms for containment analysis of rotational parts - Karnik,Mukul; Gupta, Satyandra K.; Magrab,Edward B. (Computer-Aided Design, 2005)
This paper describes a system and underlying algorithms to perform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank-orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used by designers and process planners to find an existing part that can be used as a stock to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products.
Keywords: COMPUTER AIDED DESIGN; geometric reasoning; Part containment; Shape signatures; Shape similarity

Handling uneven embedding capacity in binary images: a revisit - M. Wu; Fridrich,Jessica; Goljan,Miroslav; Gou,Hongmei (Proceedings of SPIE, 2005)
Hiding data in binary images can facilitate the authentication and annotation of important document images in digital domain. A representative approach is to first identify pixels whose binary color can be flipped without introducing noticeable artifacts, and then embed one bit in each non-overlapping block by adjusting the flippable pixel values to obtain the desired block parity. The distribution of these flippable pixels is highly uneven across the image, which is handled by random shuffling in the literature. In this paper, we revisit the problem of data embedding for binary images and investigate the incorporation of a most recent steganography framework known as the wet paper coding to improve the embedding capacity. The wet paper codes naturally handle the uneven embedding capacity through randomized projections. In contrast to the previous approach, where only a small portion of the flippable pixels are actually utilized in the embedding, the wet paper codes allow for a high utilization of pixels that have high flippability score for embedding, thus giving a significantly improved embedding capacity than the previous approach. The performance of the proposed technique is demonstrated on several representative images. We also analyze the perceptual impact and capacity-robustness relation of the new approach.

High Order Spatial Audio Capture and Binaural Head-Tracked Playback over Headphones with HRTF Cues - Duraiswami, Ramani; Zotkin,Dmitry N; Li,Z.; Grassi,E.; Gumerov, Nail A.; Davis, Larry S. (Proceedings 119th convention of AES, 2005)
A theory and a system for capturing an audio scene and then rendering it remotely are developed andpresented. The sound capture is performed with a spherical microphone array. The sound field at the location of the array is deduced from the captured sound and is represented using either spherical wave-functions or plane-wave expansions. The sound field representation is then transmitted to a remote location for immediate rendering or stored for later use. The sound renderer, coupled with the head tracker, reconstructs the acoustic field using individualized head-related transfer functions to preserve the perceptual spatial structure of the audio scene. Rigorous error bounds and Nyquist-like sampling criterion for the representation of the sound field are presented and verified.

High Order Spatial Audio Capture and Its Binaural Head-Tracked Playback Over Headphones with HRTF Cues - Davis, Larry S.; Duraiswami, Ramani; Grassi,E.; Gumerov, Nail A.; Li,Z.; Zotkin,Dmitry N (Audio Engineering Society Convention 119, 2005)
A theory and a system for capturing an audio scene and then rendering it remotely are developed and presented. The sound capture is performed with a spherical microphone array. The sound field at the location, and in a region of space in the neighborhood, of the array is deduced from the captured sound and represented using either spherical wave-functions or plane-wave expansions. The representation is then transmitted to a remote location for immediate rendering or stored for later reproduction. The sound renderer, coupled with the head tracker, reconstructs the acoustic field using individualized head-related transfer functions to preserve the perceptual spatial structure of the audio scene. Rigorous error bounds and a Nyquist-like sampling criterion for the representation of the sound field are presented and verified.

High Order Spatial Audio Capture and Its Binaural Head-Tracked Playback Over Headphones with HRTF Cues - Zotkin,Dmitry N; Davis, Larry S.; Duraiswami, Ramani; Grassi,Elena; Gumerov, Nail A.; Zhiyun,Li (Audio Engineering Society Convention 119, 2005)

Information and Knowledge Modeling for Computer Supported Micro Electro-Mechanical Systems Design and Development - Zha,X. F.; Sriram,R.D.; Gupta,S.K. (2005)
In this paper, we present a preliminary research effort towardsan effective computer support environment for the design and development of micro-electro-mechanical systems (MEMS). We first identify the characteristics of MEMS product design and development processes and examine the state-of-the-art of MEMS Computer-aided Design (CAD) and simulation systems. We then propose a function-(environment-effect)-behavior- (principle-state)-form (FEEBPSF) framework based on the NIST core product model and its extensions for modeling MEMS products, and apply the OESM (open embedded system model) developed to model information and knowledge for embedded MEMS design and development. Moreover, in order to tackle the knowledge-intensive tasks of design and development for MEMS products, we develop a general and flexible knowledge repository, called KR-MEMS, based on the FEEBPSF framework and the Unified Modeling Language (UML)/ Extensible Markup Language (XML) model, and integrate KR-MEMS into a web-based MEMS design support system. Throughout the paper, a micro fluidic dispensing device (a biomedical device for drug-delivery) is used as an example to illustrate the concepts, models, and knowledge bases necessary to support the MEMS product design and development.

Introduction to the special issue on link mining - Getoor, Lise; Diehl,Christopher P. (ACM SIGKDD Explorations Newsletter, 2005)
An emerging challenge for data mining is the problem of mining richly structured datasets, where the objects are linked in some way. Many real-world datasets describe a variety of entity types linked via multiple types of relations. These links provide additional context that can be helpful for many data mining tasks. Yet multi-relational data violates the traditional assumption of independent, identically distributed data instances that provides the basis for many statistical machine learning algorithms. Therefore, new approaches are needed that can exploit the dependencies across the attribute and link structure.

Link mining: a survey - Getoor, Lise; Diehl,Christopher P. (ACM SIGKDD Explorations Newsletter, 2005)
Many datasets of interest today are best described as a linked collection of interrelated objects. These may represent homogeneous networks, in which there is a single-object type and link type, or richer, heterogeneous networks, in which there may be multiple object and link types (and possibly other semantic information). Examples of homogeneous networks include single mode social networks, such as people connected by friendship links, or the WWW, a collection of linked web pages. Examples of heterogeneous networks include those in medical domains describing patients, diseases, treatments and contacts, or in bibliographic domains describing publications, authors, and venues. Link mining refers to data mining techniques that explicitly consider these links when building predictive or descriptive models of the linked data. Commonly addressed link mining tasks include object ranking, group detection, collective classification, link prediction and subgraph discovery. While network analysis has been studied in depth in particular areas such as social network analysis, hypertext mining, and web analysis, only recently has there been a cross-fertilization of ideas among these different communities. This is an exciting, rapidly expanding area. In this article, we review some of the common emerging themes.

Link Mining for the Semantic Web, Position Statement - Getoor, Lise; Licamele,L. (Proceedings of the Dagstuhl Seminar in Machine Learning for the Semantic Web, 2005)
A key challenge for data mining is tackling the problem of mining richly structured datasets, where the objectsare linked in some way and we have some ontological information describing the domain. Links among the objects demonstrate certain patterns, which can be helpful for many data mining tasks and are usually hard to capture with traditional statistical models. Our goals are to develop machine learning algorithms which can a) make use of the ontological theory during learning b) learn how to refine, or update the ontological theory, based on learned model and c) do a mix of both.

Link-based classification - Getoor, Lise (Advanced methods for knowledge discovery from complex data, 2005)
A key challenge for machine learning is the problem of mining richly structured data sets, where the objects are linked in some way due to either an explicit or implicit relationship that exists between the objects. Links among the objects demonstrate certain patterns, which can be helpful for many machine learning tasks and are usually hard to capture with traditional statistical models. Recently there has been a surge of interest in this area, fuelled largely by interest in web and hypertext mining, but also by interest in mining social networks, bibliographic citation data, epidemiological data and other domains best described using a linked or graph structure. In this chapter we propose a framework for modeling link distributions, a link-based model that supports discriminative models describing both the link distributions and the attributes of linked objects. We use a structured logistic regression model, capturing both content and links. We systematically evaluate several variants of our link-based model on a range of data sets including both web and citation collections. In all cases, the use of the link distribution improves classification performance.

A logic-based model of intention formation and action for multi-agent subcontracting - Grant,John; Kraus,Sarit; Perlis, Don (Artificial Intelligence, 2005)
We present a formalism for representing the formation of intentions by agents engaged in cooperative activity. We use a syntactic approach presenting a formal logical calculus that can be regarded as a meta-logic that describes the reasoning and activities of the agents. Our central focus is on the evolving intentions of agents over time, and the conditions under which an agent can adopt and maintain an intention. In particular, the reasoning time and the time taken to subcontract are modeled explicitly in the logic. We axiomatize the concept of agent interactions in the meta-language, show that the meta-theory is consistent and describe the unique intended model of the meta-theory. In this context we deal both with subcontracting between agents and the presence of multiple recipes, that is, multiple ways of accomplishing tasks. We show that under various initial conditions and known facts about agent beliefs and abilities, the meta-theory representation yields good results.
Keywords: Cooperative agents; intentions; Minimal model semantics; Subcontracting; Syntactic logic

Main effects screening - Yilmaz,Cemal; Krishna,Arvind S.; Memon, Atif M.; Porter, Adam; Schmidt,Douglas C.; Gokhale,Aniruddha; Natarajan,Balachandran (Proceedings of the 27th international conference on Software engineering - ICSE '05, 2005)

Main effects screening: a distributed continuous quality assurance process for monitoring performance degradation in evolving software systems - Yilmaz,Cemal; Krishna,Arvind S.; Memon, Atif M.; Porter, Adam; Schmidt,Douglas C.; Gokhale,Aniruddha; Natarajan,Balachandran (Proceedings of the 27th international conference on Software engineering, 2005)
Developers of highly configurable performance-intensive software systems often use a type of in-house performance-oriented "regression testing" to ensure that their modifications have not adversely affected their software's performance across its large configuration space. Unfortunately, time and resource constraints often limit developers to in-house testing of a small number of configurations and unreliable extrapolation from these results to the entire configuration space, which allows many performance bottlenecks and sources of QoS degradation to escape detection until systems are fielded. To improve performance assessment of evolving systems across large configuration spaces, we have developed a distributed continuous quality assurance (DCQA) process called main effects screening that uses in-the-field resources to execute formally designed experiments to help reduce the configuration space, thereby allowing developers to perform more targeted in-house QA. We have evaluated this process via several feasibility studies on several large, widely-used performance-intensive software systems. Our results indicate that main effects screening can detect key sources of performance degradation in large-scale systems with significantly less effort than conventional techniques.
Keywords: design of experiment theory; distributed continuous quality assurance; performance-oriented regression testing

Measurement-based multipath multicast - Guven,T.; La,R.J.; Shayman,M.A.; Bhattacharjee, Bobby (INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, 2005)
We propose a measurement-based routing algorithm to load balance intradomain traffic along multiple paths for multiple multicast sources. Multiple paths are established using application-layer overlaying. The proposed algorithm is able to converge under different network models, where each model reflects a different set of assumptions about the multicasting capabilities of the network. The algorithm is derived from simultaneous perturbation stochastic approximation and relies only on noisy estimates from measurements. Simulation results are presented to demonstrate the additional benefits obtained by incrementally increasing the multicasting capabilities.
Keywords: algorithm; allocation; application-layer; approximation; approximation; balance; communication; Convergence; convergence; intradomain; load; measurement-based; methods; Multicast; multipath; network; numerical; of; overlaying; perturbation; processes; resource; Routing; routing; source; Stochastic; techniques; Telecommunication; theory; traffic

Model-based approximate querying in sensor networks - Deshpande, Amol; Guestrin,Carlos; Madden,Samuel; Hellerstein,Joseph; Wei Hong (The VLDB Journal, 2005)
Declarative queries are proving to be an attractive paradigm for interacting with networks of wireless sensors. The metaphor that “the sensornet is a database” is problematic, however, because sensors do not exhaustively represent the data in the real world. In order to map the raw sensor readings onto physical reality, a model of that reality is required to complement the readings. In this article, we enrich interactive sensor querying with statistical modeling techniques. We demonstrate that such models can help provide answers that are both more meaningful, and, by introducing approximations with probabilistic confidences, significantly more efficient to compute in both time and energy. Utilizing the combination of a model and live data acquisition raises the challenging optimization problem of selecting the best sensor readings to acquire, balancing the increase in the confidence of our answer against the communication and data acquisition costs in the network. We describe an exponential time algorithm for finding the optimal solution to this optimization problem, and a polynomial-time heuristic for identifying solutions that perform well in practice. We evaluate our approach on several real-world sensor-network datasets, taking into account the real measured data and communication quality, demonstrating that our model-based approach provides a high-fidelity representation of the real phenomena and leads to significant performance gains versus traditional data acquisition techniques.

A picture is worth a thousand keywords: image-based object search on a mobile platform - Tom Yeh; Grauman,Kristen; Tollmar,Konrad; Darrell,Trevor (CHI '05 extended abstracts on Human factors in computing systems, 2005)
Finding information based on an object's visual appearance is useful when specific keywords for the object are not known. We have developed a mobile image-based search system that takes images of objects as queries and finds relevant web pages by matching them to similar images on the web. Image-based search works well when matching full scenes, such as images of buildings or landmarks, and for matching objects when the boundary of the object in the image is available. We demonstrate the effectiveness of a simple interactive paradigm for obtaining a segmented object boundary, and show how a shape-based image matching algorithm can use the object outline to find similar images on the web.
Keywords: content-based image retrieval; interactive segmentation; mobile interface; Object recognition

Plane-wave decomposition analysis for spherical microphone arrays - Duraiswami, Ramani; Zhiyun Li; Zotkin,Dmitry N; Grassi,E.; Gumerov, Nail A. (IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, 2005, 2005)
Spherical microphone arrays have attracted attention for analyzing the sound field in a region and beamforming. The analysis of the recorded sound has been performed in terms of spherical wave-functions, and recently the use of plane-wave expansions has been suggested. We show that the plane-wave basis is intimately related to the spherical wave-functions. Reproduction in terms of both representations satisfies certain band-limit criteria. We provide an error bound that shows that to reproduce the spatial characteristics of a sound of a certain frequency we need to be able to accurately represent sounds of up to a particular order, which establishes a Nyquist-like criterion. The order of the sound field in turn is related to the number of microphones in the array necessary to achieve accurate quadrature on the sphere. These results are illustrated with simulations.
Keywords: Acoustic propagation; Acoustic scattering; acoustic signal processing; acoustic waves; array signal processing; band-limit criteria; beamforming; Educational institutions; Fourier transforms; Frequency; Laboratories; microphone arrays; Nails; Nyquist criterion; Nyquist-like criterion; Partial differential equations; plane-wave decomposition analysis; sound field analysis; spherical microphone arrays; spherical wave-functions

Pose-Encoded Spherical Harmonics for Robust Face Recognition Using a Single Image - Yue,Zhanfeng; Zhao,Wenyi; Chellapa, Rama (Analysis and Modelling of Faces and GesturesAnalysis and Modelling of Faces and Gestures, 2005)
Face recognition under varying pose is a challenging problem, especially when illumination variations are also present. Under Lambertian model, spherical harmonics representation has proved to be effective in modelling illumination variations for a given pose. In this paper, we extend the spherical harmonics representation to encode pose information. More specifically, we show that 2D harmonic basis images at different poses are related by close-form linear combinations. This enables an analytic method for generating new basis images at a different pose which are typically required to handle illumination variations at that particular pose. Furthermore, the orthonormality of the linear combinations is utilized to propose an efficient method for robust face recognition where only one set of front-view basis images per subject is stored. In the method, we directly project a rotated testing image onto the space of front-view basis images after establishing the image correspondence. Very good recognition results have been demonstrated using this method.

Promoter architecture and response to a positive regulator of archaeal transcription - Ouhammouch,Mohamed; Langham,Geoffrey E; Hausner,Winfried; Simpson,Anjana J.; El‐Sayed, Najib M.; Geiduschek,E. Peter (Molecular Microbiology, 2005)
The archaeal transcription apparatus is chimeric: its core components (RNA polymerase and basal factors) closely resemble those of eukaryotic RNA polymerase II, but the putative archaeal transcriptional regulators are overwhelmingly of bacterial type. Particular interest attaches to how these bacterial-type effectors, especially activators, regulate a eukaryote-like transcription system. The hyperthermophilic archaeon Methanocaldococcus jannaschii encodes a potent transcriptional activator, Ptr2, related to the Lrp/AsnC family of bacterial regulators. Ptr2 activates rubredoxin 2 (rb2) transcription through a bipartite upstream activating site (UAS), and conveys its stimulatory effects on its cognate transcription machinery through direct recruitment of the TATA binding protein (TBP). A functional dissection of the highly constrained architecture of the rb2 promoter shows that a ‘one-site’ minimal UAS suffices for activation by Ptr2, and specifies the required placement of this site. The presence of such a simplified UAS upstream of the natural rubrerythrin (rbr) promoter also suffices for positive regulation by Ptr2 in vitro, and TBP recruitment remains the primary means of transcriptional activation at this promoter.

PROTOTYPING THE SIMULATION OF A GATE LEVEL LOGIC APPLICATION PROGRAM INTERFACE (API) ON AN EXPLICIT-MULTI-THREADED (XMT) COMPUTER - Gu,Pei (2005)
Explicit-multi-threading (XMT) is a parallel programming approach for exploiting on-chip parallelism. Its fine-grained SPMD programming model is suitable for many computing intensive applications. In this paper, we present a parallel gate level logic simulation algorithm and study its implementation on an XMT processor. The test results show that hundreds-fold speedup can be achieved.
Keywords: Computer Science (0984)

On the reasoning of real-world agents: Toward a semantics for active logic - Anderson,M. L; Gomaa,W.; Grant,J.; Perlis, Don (7-th Annual Symposium on the Logical Formalization of Commonsense Reasoning, 2005)

Relational clustering for multi-type entity resolution - Bhattacharya,Indrajit; Getoor, Lise (Proceedings of the 4th international workshop on Multi-relational mining, 2005)
In many applications, there are a variety of ways of referring to the same underlying entity. Given a collection of references to entities, we would like to determine the set of true underlying entities and map the references to these entities. The references may be to entities of different types and more than one type of entity may need to be resolved at the same time. We propose similarity measures for clustering references taking into account the different relations that are observed among the typed references. We pose typed entity resolution in relational data as a clustering problem and present experimental results on real data showing improvements over attribute-based models when relations are leveraged.

Resource-aware wireless sensor-actuator networks - Deshpande, Amol; Guestrin,C.; Madden,S. R (Data Engineering, 2005)

Robust digital fingerprinting for curves - Gou,H.; Wu,M. (Proc. of IEEE Int. Conf. on Acoustics, Speech, and Signal Processing (ICASSP'05), 2005)
Hiding data in curves can be achieved by parameterizing acurve using the B-spline model and adding spread spectrum sequences in B-spline control points. In this paper, we pro- pose an iterative alignment-minimization algorithm to per- form curve registration and deal with the non-uniqueness of B-spline control points. We demonstrate through experi- ments the robustness of our method against various attacks such as collusion, geometric transformation, and printing- and-scanning. We also show the feasibility of our method for fingerprinting topographic maps and detecting finger- prints from printed copies.

Scalable data collection infrastructure for digital government applications - Samet, Hanan; Tanin,Egemen; Golubchik,Leana (Proceedings of the 2005 national conference on Digital government research, 2005)
Highlights are presented of a project on the development of a scalable data collection infrastructure of digital government applications. The approach takes advantage of both the distributed nature of the data and the distributed ways of interacting with it. The approach is three-parted having theoretical, systems, and application components. On the theoretical and systems levels, work has continued on the development of the BISTRO system. On the applications level, work has continued on the investigation of the use of peer-to-peer networks in a number of domains in which the proper handling of spatial data is important.

System for capturing of highorder spatial audio using spherical microphone array and binaural head-tracked playback over headphones with head related transfer function cues - Duraiswami, Ramani; Zotkin,Dmitry N; Li,Z.; Grassi,E.; Gumerov, Nail A.; Davis, Larry S. (Proc. 119th convention AES, 2005)

A system for performing content-based searches on a database of mechanical assemblies - Deshmukh,A. S.; Gupta,S.K.; Karnik,M. V.; Sriram,R.D. (2005)
The increased use of 3D CAD systems by productdevelopment organizations has resulted in large databases of assemblies; this explosion of assembly data will continue in the future. Currently, there are no effective content-based techniques to search these databases. Ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate reuse of existing assembly designs, and thereby reducing the design time. Second, a lot of useful Design for Manufacturing and Assembly (DFMA) knowledge is embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by the designers to learn from the existing assembly designs and hence transfer the best DFMA practices to new designers. This paper describes a system for performing content-based searches on assembly databases. We identify templates for comprehensive search definitions and describe algorithms to perform content-based searches for mechanical assemblies. We also illustrate capabilities of our system through several examples.

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.

Tutorial on statistical relational learning - Getoor, Lise (Inductive Logic Programming, 2005)
Statistical machine learning is in the midst of a “relational revolution”. After many decades of focusing on independent and identically-distributed (iid) examples, many researchers are now studying problems in which the examples are linked together into complex networks. These networks ca be a simple as sequences and 2-D meshes (such as those arising in part-of-speech tagging and remote sensing) or as complex as citation graphs, the world wide web, and relational data bases.Statistical relational learning raises many new challenges and opportunities. Because the statistical model depends on the domain’s relational structure, parameters in the model are often tied. This has advantages for making parameter estimation feasible, but complicates the model search. Because the “features” involve relationships among multiple objects, there is often a need to intelligently construct aggregates and other relational features. Problems that arise from linkage and autocorrelation among objects must be taken into account. Because instances are linked together, classification typically involves complex inference to arrive at “collective classification” in which the labels predicted for the test instances are determined jointly rather than individually. Unlike iid problems, where the result of learning is a single classifier, relational learning often involves instances that are heterogeneous, where the result of learning is a set of multiple components (classifiers, probability distributions, etc.) that predict labels of objects and logical relationships between objects.

Two-server password-only authenticated key exchange - Katz, Jonathan; MacKenzie,P.; Taban,G.; Gligor,V. (Applied Cryptography and Network Security, 2005)
Typical protocols for password-based authentication assume a single server which stores all the information (e.g.), the password necessary to authenticate a user. Unfortunately, an inherent limitation of this approach (assuming low-entropy passwords are used) is that the user’s password is exposed if this server is ever compromised. To address this issue, a number of schemes have been proposed in which a user’s password information is shared among multiple servers, and these servers cooperate in a threshold manner when the user wants to authenticate.We show here a two-server protocol for this task assuming public parameters available to everyone in the system (as well as the adversary). Ours is the first provably-secure two-server protocol for the important password-only setting (in which the user need remember only a password, and not the servers’ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model.

Using Iterative Strategies for Aligning Attributed Points in Space - Cardone, Antonio; Gupta, Satyandra K.; Mount, Dave (Institute for Systems Research, University of Maryland, College Park, 2005)
Signatures based on shape features are expected to be useful for several similarity assessment applications. Such signatures can extract the relevant shape information needed for similarity assessment and ignore the shape information not needed for a particular application. Since different feature-based models are created in different coordinate systems, in order to compute distance between two sets of features, one needs to include geometric transformations for aligning features. Optimal alignment is the alignment that results in the minimum distance between two sets of features. In general, features can be viewed as attributed points in space. Hence, we need to develop techniques for aligning attributed points in space. This report introduces iterative strategies for optimally aligning attributed points in space. Iterative strategies presented in this report involve successively applying algorithms that perform alignment under restricted rigid body transformations (e.g., rotations only or translations only) to solve point alignment problems that require higher dimension transformations (e.g., combinations rotations and translations). Our preliminary experimental results show that the idea of using of iterative strategies to solve higher dimension attributed point alignment problems is promising and can be used to perform feature-based shape similarity assessment.
Keywords: Technical Report

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.

Using probabilistic models for data management in acquisitional environments - Deshpande, Amol; Guestrin,C.; Madden,S. (Proc. CIDR, 2005)

Web Service Composition with Volatile Information - Au,Tsz-Chiu; Kuter,Ugur; Nau, Dana S. (The Semantic Web – ISWC 2005, 2005)
In many Web service composition problems, information may be needed from Web services during the composition process. Existing research on Web service composition (WSC) procedures has generally assumed that this information will not change. We describe two ways to take such WSC procedures and systematically modify them to deal with volatile information. The black-box approach requires no knowledge of the WSC procedure’s internals: it places a wrapper around the WSC procedure to deal with volatile information. The gray-box approach requires partial information of those internals, in order to insert coding to perform certain bookkeeping operations. We show theoretically that both approaches work correctly. We present experimental results showing that the WSC procedures produced by the gray-box approach can run much faster than the ones produced by the black-box approach.
Keywords: Computer science

Achieving packet-level quality of service through scheduling in multirate WLANs - Yuan Yuan; Daqing Gu; Arbaugh, William A.; Jinyun Zhang (Vehicular Technology Conference, 2004. VTC2004-Fall. 2004 IEEE 60th, 2004)
Wireless packet scheduling has been a popular paradigm to achieve packet-level QoS in terms of fairness and throughput in the presence of channel errors. However, the current design does not anticipate the multi-rate capability offered by the IEEE 802.11a/b/g physical layer, thus suffering significant performance degradation in 802.11 WLANs. In this paper, we propose multirate wireless fair scheduling (WMFS). In MWFS, each flow is granted a temporal fair share of the channel, in contrast to the throughput fair share adopted by existing algorithms. Therefore, each flow receives services in proportion to its perceived transmission rate, and high-rate flows are able to opportunistically exploit their good channel conditions and receive more services. MWFS also renovates the compensation model in order to allow for error-prone flows to catch up, thus ensuring fairness for all flows over error-prone channels. We demonstrate the effectiveness of MWFS through both simulations and analysis. Especially, WMFS achieves system throughput 159% of state-of-the-art scheduling algorithms in simulated scenarios.
Keywords: Analytical models; channel conditions; channel errors; channel temporal fair share; compensation; Computer science; Delay; error-prone flow compensation; IEEE 802.11a/b/g physical layer; multirate wireless fair scheduling; multirate WLAN; packet radio networks; packet-level quality of service; Physical layer; Processor scheduling; QoS; quality of service; radio access networks; Scheduling algorithm; Throughput; throughput fairness; USA Councils; Wireless LAN; wireless packet scheduling; WMFS

Adapting network structure for efficient team formation - Gaston,M.; Simmons,J.; desJardins, Marie (Proceedings of the AAAI 2004 Fall Symposium on Artificial Multi-agent Learning, 2004)

Adaptive replication in peer-to-peer systems - Gopalakrishnan,V.; Silaghi,B.; Bhattacharjee, Bobby; Keleher,P. (Distributed Computing Systems, 2004. Proceedings. 24th International Conference on, 2004)
Peer-to-peer systems can be used to form a low-latency decentralized data delivery system. Structured peer-to-peer systems provide both low latency and excellent load balance with uniform query and data distributions. Under the more common skewed access distributions, however, individual nodes are easily overloaded, resulting in poor global performance and lost messages. This paper describes a lightweight, adaptive, and system-neutral replication protocol, called LAR, that maintains low access latencies and good load balance even under highly skewed demand. We apply LAR to Chord and show that it has lower overhead and better performance than existing replication strategies.
Keywords: adaptive; allocation; data; databases; decentralized; delivery; distributed; LAR; low-latency; peer-to-peer; processing; protocol; replicated; replication; resource; strategies; structured; system-neutral; system; systems

Algorithmic Foundations for Consistency-Checking of Interaction-States of Mechatronic Systems - Xu,C.; Gupta,S.K. (2004)
In order to reduce product development time, we needsoftware tools that can perform automated validation of the proposed design concepts. These tools will ensure that only valid design concepts are transferred to the detailed design stage for further development. This paper provides a step towards the automated validation of proposed design concepts. We define the problem of consistency-checking of interaction- states as a key step in the design concept validation. We present a polynomial time algorithm for solving the interaction consistency-checking problem. We also present an algorithm for analyzing inconsistent interaction-states and identifying the inconsistent interactions. We believe that the framework described in this paper will provide the underlying foundations for constructing the next generation software tools for conceptual design of complex mechatronic systems.

Applying Model-based Distributed Continuous Quality Assurance Processes to Enhance Persistent Software Attributes - Krishna,A. S; Yilmaz,C.; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (IEEE Software, 2004)
Time and resource constraints often force developers of highlyconfigurable quality of service (QoS)-intensive software sys- tems to guarantee their system’s persistent software attributes (PSAs) (e.g., functional correctness, portability, efficiency, and QoS) on very few platform configurations and to extrapolate from these configurations to the entire configuration space, which allows many sources of degradation to escape detec- tion until systems are fielded. This article illustrates how distributed continuous quality assurance (DCQA) processes help improve the assessment of these PSAs across large QoS- intensive software system configuration spaces. We also il- lustrate how model-based DCQA processes enable developers to run formally-designed screening experiments that isolate the most significant configuration options, such as different workload parameters, operating system, compiler flags, fea- ture sets, and/or run-time optimization controls. Our empir- ical results show that DCQA processes can be used monitor, safeguard, and enforce PSAs at an acceptable level of cost and effort.

Approximation algorithms for partial covering problems - Gandhi,Rajiv; Khuller, Samir; Srinivasan, Aravind (Journal of Algorithms, 2004)
We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks.
Keywords: Approximation algorithms; Partial covering; Primal-dual methods; Randomized rounding; Set cover; Vertex cover

Automated Planning: Theory and Practice - Ghallab,Malik; Nau, Dana S.; Traverso,Paolo (Elsevier, 2004)
Automated planning technology now plays a significant role in a variety of demanding applications, ranging from controlling space vehicles and robots to playing the game of bridge. These real-world applications create new opportunities for synergy between theory and practice: observing what works well in practice leads to better theories of planning, and better theories lead to better performance of practical applications. Automated Planning mirrors this dialogue by offering a comprehensive, up-to-date resource on both the theory and practice of automated planning. The book goes well beyond classical planning, to include temporal planning, resource scheduling, planning under uncertainty, and modern techniques for plan generation, such as task decomposition, propositional satisfiability, constraint satisfaction, and model checking. The authors combine over 30 years experience in planning research and development to offer an invaluable text to researchers, professionals, and graduate students. *Comprehensively explains paradigms for automated planning. *Provides a thorough understanding of theory and planning practice, and how they relate to each other. *Presents case studies of applications in space, robotics, CAD/CAM, process control, emergency operations, and games.*Provides a thorough understanding of AI planning theory and practice, and how they relate to each other. *Covers all the contemporary topics of planning, as well as important practical applications of planning, such as model checking and game playing. *Presents case studies and applications in planning engineering, space, robotics, CAD/CAM, process control, emergency operations, and games.*Provides lecture notes, examples of programming assignments, pointers to downloadable planning systems and related information online.
Keywords: Business & Economics / Management; Computers / Intelligence (AI) & Semantics; Production planning; Production planning/ Data processing; Technology & Engineering / Robotics

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.

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

Capture and recreation of higher order 3d sound fields via reciprocity - Li,Z.; Duraiswami, Ramani; Gumerov, Nail A. (International Conference on Audio Display, 2004)
We propose a unified and simple approach for capturing andrecreating 3D sound fields by exploring the reciprocity prin- ciple that is satisfied between the two processes. Our ap- proach makes the system easy to build, and practical. Us- ing this approach, we can capture the 3D sound field by a spherical microphone array and recreate it using a spheri- cal loudspeaker array, and ensure that the recreated sound field matches the recorded field up to a high order of spheri- cal harmonics. A design example and simulation results are presented. For some regular or semi-regular microphone layouts, we design an efficient parallel implementation of the multi-directional spherical beamformer by using the ro- tational symmetries of the beampattern and of the spherical microphone array. This can be implemented in either soft- ware or hardware. A simple design example is presented to demonstrate the idea. It can be easily adapted for other regular or semi-regular layouts of microphones.

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.

Cutter path generation for 2.5D milling by combining multiple different cutter path patterns - Yao,Zhiyang; Gupta, Satyandra K. (International Journal of Production Research, 2004)
Different cutter path patterns have been shown to be efficient for different types of pocket geometries. However, for certain types of complex pockets, no single type of pattern produces efficient cutter paths throughout the pocket. In this paper, different cutter path patterns are systematically analysed, and several existing heuristics for selecting cutter path patterns are discussed. Based on observations, a new cutter path generation algorithm is described in this paper. This algorithm generates a cutter path by using different patterns in different regions of the geometry and seamlessly morphing them together. In case of complex pockets, it produces solutions superior to those generated by any single pattern.

Data hiding in curves for collusion-resistant digital fingerprinting - Gou,Hongmei; M. Wu (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
This paper presents a new data hiding method for curves. The proposed algorithm parameterizes a curve using the B-spline model and adds a spread spectrum sequence in the coordinates of the B-spline control points. We demonstrate through experiments the robustness of the proposed data hiding algorithm against printing-and-scanning and collusions, and show its feasibility for collusion-resistant fingerprinting of topographic maps as well as writings/drawings from pen-based input devices.
Keywords: (mathematics); B-spline; coding; collusion-resistant; CONTROL; data; devices; digital; document; encapsulation; extraction; feature; fingerprinting; hiding; image; INPUT; maps; model; pen-based; points; printing-and-scanning; processing; robustness; sequence; spectrum; splines; spread; topographic; watermarking

Data migration on parallel disks - Golubchik,L.; Khuller, Samir; Kim,Y. A; Shargorodskaya,S.; Wan,Y. C (Algorithms–ESA 2004, 2004)
Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout is computed. In this work we study the data migration problem, which arises when we need to quickly change one layout to another. This problem has been studied earlier when for each disk the new layout has been prescribed. However, to apply these algorithms effectively, we identify another problem that we refer to as the correspondence problem, whose solution has a significant impact on the solution for the data migration problem. We study algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst case behavior.

Data sciences technology for homeland security information management and knowledge discovery - Kolda,T.; Brown,D; Corones,J.; Critchlow,T.; Eliassi-Rad,T.; Getoor, Lise; Hendrickson,B.; Kumar, V.; Lambert,D.; Matarazzo,C. (Report of the DHS Workshop Data Sciences, Jointly Released by Sandia National Laboratories and Lawrence Livermore National Laboratory, Alexandria, Va, 2004)

A data structure for non-manifold simplicial d-complexes - De Floriani, Leila; Greenfieldboyce,David; Hui,Annie (Proceedings of the 2004 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2004)
We propose a data structure for d-dimensional simplicial complexes, that we call the Simplified Incidence Graph (SIG). The simplified incidence graph encodes all simplices of a simplicial complex together with a set of boundary and partial co-boundary topological relations. It is a dimension-independent data structure in the sense that it can represent objects of arbitrary dimensions. It scales well to the manifold case, i.e. it exhibits a small overhead when applied to simplicial complexes with a manifold domain, Here, we present efficient navigation algorithms for retrieving all topological relations from a SIG, and an algorithm for generating a SIG from a representation of the complex as an incidence graph. Finally, we compare the simplified incidence graph with the incidence graph, with a widely-used data structure for d-dimensional pseudo-manifold simplicial complexes, and with two data structures specific for two-and three-dimensional simplicial complexes.

Data Structures and Algorithms in C++ - Goodrich,M. T; Tamassia,R.; Mount, Dave (John Wiley & Sons Inc, 2004)

Deduplication and group detection using links - Bhattacharya,I.; Getoor, Lise (KDD workshop on link analysis and group detection, 2004)
Clustering is a fundamental problem in data mining. Tradi-tionally, clustering is done based on the similarity of the at- tribute values of the entities to be clustered. More recently, there has been greater interest in clustering relational and structured data. Often times this data is best described as a graph, in which there are both entities, described by a collec- tion of attributes, and links between entities, representing the relations between them. Clustering in these scenarios becomes more complex, as we should also take into account the similarity of the entity links when we are clustering. We propose novel distance measures for clustering linked data, and show how they can be used to solve two important data mining tasks, entity deduplication and group discovery.

Detecting and correcting a failure sequence in a computer system before a failure occurs - Gross,K. C; Votta,L. G.; Porter, Adam (Google Patents, 2004)

A distributed continuous quality assurance process to manage variability in performance-intensive software - Krishna,A.; Yilmaz,C.; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (19th ACM OOPSLA Workshop on Component and Middleware Performance, 2004)

Efficient computation of acoustical scattering from N spheres via the fast multipole method accelerated flexible generalized minimal residual method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2004)
Many problems require computation of acoustic fields in systems consisting of a large number of scatterers, which can be modeled as spheres (or enclosed by them). These spheres can have different sizes, can be arbitrarily distributed in three dimensional space, and can have different surface impedance. Solution of this problem via direct T‐matrix approach [Gumerov and Duraiswami, J. Acoust. Soc. Am., 112, 2688–2701 (2002)] is practical only for relatively low number of scatterers, N, since its computational complexity grows as O(N3). We developed and implemented an efficient computational technique, based on an iterative solver employing a flexible generalized minimal residual method with a right preconditioner. Matrix‐vector multiplications involving a large system matrix and the preconditioner are sped up with the aid of the multilevel fast multipole method. We tested the accuracy, convergence and complexity of the method on example problems with N∼104 (millions of unknowns). These tests showed that the method is accurate for a range of frequencies, and experimentally scales as O(N1.25). The method has substantial advantages in speed and convergence compared to the reflection method reported earlier [Gumerov and Duraiswami, J. Acoust. Soc. Am., 113, 2334 (2002)]. [Work supported NSF Awards 0086075 and 0219681, which are gratefully acknowledged.]

Efficient peer-to-peer namespace searches - Gopalakrishnan,V.; Bhattacharjee, Bobby; Chawathe,S.; Keleher,P. (University of Maryland, College Park, MD, Tech. Rep. CSTR-4568, 2004)
In this paper we describe new methods for efficient and exact search (keyword and full-text) in distributed namespaces. Our methods can be used in conjunction with existing distributed lookup schemes, such as Distributed Hash Tables, and distributed directories. We describe how indexes for implementing distributed searches can be efficiently created, located, and stored. We describe techniques for creating approximate indexes that can be used to bound the space requirement at individual hosts; such techniques are particularly useful for full-text searches that may require a very large number of individual indexes to be created and maintained. Our methods use a new distributed data structure called the view tree. View trees can be used to efficiently cache and locate results from prior queries. We describe how view trees are created, and maintained. We present experimental results, using large namespaces and realistic data, showing that the techniques introduced in this paper can reduce search overheads (both network and processing costs) by more than an order of magnitude.

Enhancement of mechanical engineering curriculum to introduce manufacturing techniques and principles for bio-inspired product development - Bruck,H. A.; Gershon,A. L.; Gupta,S.K. (2004)

Experience with safe manual memory-management in cyclone - Hicks, Michael W.; Morrisett,Greg; Grossman,Dan; Jim,Trevor (Proceedings of the 4th international symposium on Memory management, 2004)
The goal of the Cyclone project is to investigate type safety for low-level languages such as C. Our most difficult challenge has been providing programmers control over memory management while retaining type safety. This paper reports on our experience trying to integrate and effectively use two previously proposed, type-safe memory management mechanisms: statically-scoped regions and unique pointers. We found that these typing mechanisms can be combined to build alternative memory-management abstractions, such as reference counted objects and arenas with dynamic lifetimes, and thus provide a flexible basis. Our experience---porting C programs and building new applications for resource-constrained systems---confirms that experts can use these features to improve memory footprint and sometimes to improve throughput when used instead of, or in combination with, conservative garbage collection.
Keywords: cyclone; Memory management; memory safety; regions; unique pointers

FAST ALGORITHMS TO COMPUTE MATRIX-VECTOR PRODUCTS FOR PASCAL MATRICES - Tang,Zhihui; Duraiswami, Ramani; Gumerov, Nail A. (Technical Reports from UMIACS UMIACS-TR-2004-08, 2004)
The Pascal matrix arises in a number of applications. We present a few waysto decompose the Pascal matrices of size $n × n$ into products of matrices with structure. Based on these decompositions, we propose fast algorithms to compute the product of a Pascal matrix and a vector with omplexity $O(n\log n)$. We also present a strategy to stabilize the proposed algorithms. Finally, we also present some interesting properties of the Pascal matrices that help us to compute fast the product of the inverse of a Pascal matrix and a vector, and fast algorithms for generalized Pascal Matrices. UMIACS-TR-2004-08
Keywords: Technical Report

Fast Multipole Methods For The Helmholtz Equation In Three Dimensions - Gumerov, Nail A.; Duraiswami, Ramani (Elsevier, 2004)
This volume in the Elsevier Series in Electromagnetism presents a detailed, in-depth and self-contained treatment of the Fast Multipole Method and its applications to the solution of the Helmholtz equation in three dimensions. The Fast Multipole Method was pioneered by Rokhlin and Greengard in 1987 and has enjoyed a dramatic development and recognition during the past two decades. This method has been described as one of the best 10 algorithms of the 20th century. Thus, it is becoming increasingly important to give a detailed exposition of the Fast Multipole Method that will be accessible to a broad audience of researchers. This is exactly what the authors of this book have accomplished. For this reason, it will be a valuable reference for a broad audience of engineers, physicists and applied mathematicians.The Only book that provides comprehensive coverage of this topic in one location.Presents a review of the basic theory of expansions of the Helmholtz equation solutionsComprehensive description of both mathematical and practical aspects of the fast multipole method and it's applications to issues described by the Helmholtz equation
Keywords: Electronic books; Helmholtz equation; Mathematics / Mathematical Analysis; Science / Physics / Electromagnetism; Science / Physics / Magnetism; Technology & Engineering / Acoustics & Sound; Technology & Engineering / Electrical

Flexible layout and optimal cancellation of the orthonormality error for spherical microphone arrays - Zhiyun Li; Duraiswami, Ramani; Grassi,E.; Davis, Larry S. (Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on, 2004)
This paper describes an approach to achieving a flexible layout of microphones on the surface of a spherical microphone array for beamforming. Our approach achieves orthonormality of spherical harmonics to higher order for relatively distributed layouts. This gives great flexibility in microphone layout on the spherical surface. One direct advantage is that it makes it much easier to build a real world system, such as those with cable outlets and a mounting base, with minimal effects on the performance. Simulation results are presented.
Keywords: array; audio; base; beamforming; cable; cancellation; correction; error; flexible; harmonics; higher; layout; microphone; microphones; mounting; optimization; order; orthonormality; outlets; processing; signal; spherical; surface

A Framework for Conceptual Design of Multiple Interaction-State Mechatronic Systems - Gupta,S.K.; Xu,C.; Yao,Z. (2004)
Increasingly, complex mechatronic systems are beingdesigned to have higher levels of autonomy and intelligence. This requires them to operate in multiple interaction-states. To facilitate computer- aided conceptual design of complex mechatronic systems, this paper provides a framework for modeling design concepts behind mechatronic systems with multiple interaction-states. We introduce the primitives and operators used in the modeling framework, and illustrate the modeling process by an example.

Geometric algorithms for automated design of multi-piece permanent molds - Priyadarshi,Alok K.; Gupta, Satyandra K. (Computer-Aided Design, 2004)
Multi-piece molds, which consist of more than two mold pieces, are capable of producing very complex parts—parts that cannot be produced by the traditional molds. The tooling cost is also low for multi-piece molds, which makes it a candidate for pre-production prototyping and bridge tooling. However, designing multi-piece molds is a time-consuming task. This article describes geometric algorithms for automated design of multi-piece molds. A multi-piece mold design algorithm has been developed to automate several important mold-design steps: finding parting directions, locating parting lines, creating parting surfaces, and constructing mold pieces. This algorithm constructs mold pieces based on global accessibility analysis results of the part and therefore guarantees the disassembly of the mold pieces. A software system has been developed, which has been successfully tested on several complex industrial parts.
Keywords: mold design; Multi-piece molds; spatial partitioning

Geometric algorithms for automated design of rotary-platen multi-shot molds - Li,Xuejun; Gupta, Satyandra K. (Computer-Aided Design, 2004)
This paper describes algorithms for automated design of rotary-platen type of multi-shot molds for manufacturing multi-material objects. The approach behind our algorithms works in the following manner. First, we classify the given multi-material object into several basic types based on the relationships among different components in the object. For every basic type, we find a molding sequence based on the precedence constraints resulting due to accessibility and disassembly requirements. Then, starting from the last mold stage, we generate the mold pieces for every mold stage. We expect that algorithms described in this paper will provide the necessary foundations for automating the design of rotary-platen molds.
Keywords: geometric reasoning; mold design; Multi-shot molds

Geometric Containment Analysis for Rotational Parts - Karnik,M.; Gupta,S.K.; Magrab,E. B. (2004)
This paper describes a system and underlying algorithms toperform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank- orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used to find an existing part from which to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products.

Hierarchical routing with soft-state replicas in TerraDir - Silaghi,B.; Gopalakrishnan,Vijay; Bhattacharjee, Bobby; Kelcher,P. (Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International, 2004)
Summary form only given. Recent work on peer-to-peer systems has demonstrated the ability to deliver low latencies and good load balance when demand for data is relatively uniform. We describe an adaptive replication protocol that delivers low latencies, good load balance even when demand is heavily skewed. The protocol can withstand arbitrary and instantaneous changes in demand distribution. Our approach also addresses classical concerns related to topological constraints of asymmetrical namespaces, such as hierarchical bottlenecks in the context of hierarchical namespaces. The protocol replicates routing state in an ad-hoc manner based on profiled information, is lightweight, scalable, and requires no replica consistency guarantees.
Keywords: ad-hoc; adaptive; allocation; asymmetrical; balancing; bottlenecks; consistency; constraints; delivering; demand; distribution; guarantees; hierarchical; latency; load; low; namespaces; peer-to-peer; protocol; protocols; replica; replicas; replication; resource; routing; soft-state; systems; TerraDir; topological

High-performance MAC for high-capacity wireless LANs - Yuan Yuan; Daqing Gu; Arbaugh, William A.; Jinyun Zhang (13th International Conference on Computer Communications and Networks, 2004. ICCCN 2004. Proceedings, 2004)
The next-generation wireless technologies, e.g., 802.11n and 802.15.3a, offer a physical-layer speed at least an-order-of-magnitude higher than the current standards. However, direct application of current MACs leads to high protocol overhead and significant throughput degradation. In this paper, we propose ADCA, a high-performance MAC that works with high-capacity physical layer. ADCA exploits two ideas of adaptive batch transmission and opportunistic selection of high-rate hosts to simultaneously reduce the overhead and improve the aggregate throughput. It opportunistically favors high-rate hosts by providing higher access probability and more access time, while ensuring each low-rate host certain minimum amount of channel access time. Simulations show that the ADCA design increases the throughput by 112% and reduces the average delay by 55% compared with the legacy DCF. It delivers more than 100 Mbps MAC-layer throughput as compared with 35 Mbps offered by the legacy MAC
Keywords: 35 Mbit/s; access protocols; Aggregates; Bandwidth; batch transmission; Computer science; Educational institutions; high-capacity wireless LAN; high-performance MAC; Laboratories; Local area networks; Media Access Protocol; opportunistic selection; Physical layer; probability; Throughput; Wireless LAN

iCLEF 2003 at Maryland: Translation Selection and Document Selection - Dorr, Bonnie J; He,Daqing; Luo,Jun; Oard, Douglas; Schwartz,Richard; Wang,Jianqiang; Zajic, David (Comparative Evaluation of Multilingual Information Access SystemsComparative Evaluation of Multilingual Information Access Systems, 2004)
Maryland performed two sets of experiments for the 2003 Cross-Language Evaluation Forum’s interactive track, one focused on interactive selection of appropriate translations for query terms, the second focused on interactive selection of relevant documents. Translation selection was supported using possible synonyms discovered through back translation and two techniques for generating KeyWord In Context (KWIC) examples of usage. The results indicate that searchers typically achieved a similar search effectiveness using fewer query iterations when interactive translation selection was available. For document selection, a complete extract of the first 40 words of each news story was compared to a compressed extract generated using an automated parse-and-trim approach that approximates one way in which people can produce headlines. The results indicate that compressed “headlines” result in faster assessment, but with a 20% relative reduction in the F α = 0.8 search effectiveness measure.

Identifying similar parts for assisting cost estimation of prismatic machined parts - Cardone, Antonio; Gupta,S.K.; Karnik,M. (ASME Design for Manufacturing Conference, Salt Lake City, Utah, 2004)

Improved Multiuser Detectors Employing Genetic Algorithms in a Space-Time Block Coded System, Yinggang Du and Kam Tai Chan - Self-Similarity,G.R.U.I.; BenAbdelkader,C.; Cutler,R.G.; Davis, Larry S.; Local,F.R.U.; Global Features,J.H.; Yuen, P.C.; Lai,JH; Li,C. (Signal, 2004)

Inducing a semantic frame lexicon from WordNet data - Green,Rebecca; Dorr, Bonnie J (Proceedings of the 2nd Workshop on Text Meaning and Interpretation, 2004)
This paper presents SemFrame, a system that automatically induces the names and internal structures of semantic frames. After SemFrame identifies sets of frame-evoking verb synsets, the conceptual density of nodes in the WordNet network for corresponding nouns and noun synsets is computed and analyzed. Conceptually dense nodes are candidates for frame names and frame slots. Ca. 76% of the frame names and 87% of the frame slots generated by SemFrame are rated adequate by human judges.

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.

The ingi and RIME non-LTR retrotransposons are not randomly distributed in the genome of Trypanosoma brucei - Bringaud,F.; Biteau,N.; Zuiderwijk,E.; Berriman,M.; El‐Sayed, Najib M.; Ghedin,E.; Melville,S. E.; Hall,N.; Baltz,T. (Molecular biology and evolution, 2004)

Interactive cross-language document selection - Oard, Douglas; Gonzalo,J.; Sanderson,M.; López-Ostenero,F.; Wang,J. (information retrieval, 2004)

INTERPOLATION AND RANGE EXTRAPOLATION OF HEAD RELATED TRANSFER FUNCTIONS - Duraiswami, Ramani; Zotkin,Dmitry N; Gumerov, Nail A. (IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS SPEECH AND SIGNAL PROCESSING, 2004)

Iterative record linkage for cleaning and integration - Bhattacharya,Indrajit; Getoor, Lise (Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, 2004)
Record linkage, the problem of determining when two records refer to the same entity, has applications for both data cleaning (deduplication) and for integrating data from multiple sources. Traditional approaches use a similarity measure that compares tuples' attribute values; tuples with similarity scores above a certain threshold are declared to be matches. While this method can perform quite well in many domains, particularly domains where there is not a large amount of noise in the data, in some domains looking only at tuple values is not enough. By also examining the context of the tuple, i.e. the other tuples to which it is linked, we can come up with a more accurate linkage decision. But this additional accuracy comes at a price. In order to correctly find all duplicates, we may need to make multiple passes over the data; as linkages are discovered, they may in turn allow us to discover additional linkages. We present results that illustrate the power and feasibility of making use of join information when comparing records.
Keywords: clustering; deduplication; distance measure; record linkage

Left-Brain/Right-Brain Multi-Document Summarization - Conroy,John M.; Schlesinger,Judith D.; Goldstein,Jade; O'Leary, Dianne P. (DUC 04 Conference ProceedingsDUC 04 Conference Proceedings, 2004)

Measurement based optimal multi-path routing - Guven,T.; Kommareddy,C.; La,R.J.; Shayman,M.A.; Bhattacharjee, Bobby (INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004)
We propose a new architecture for efficient network monitoring and measurements in a traditional IP network. This new architecture enables establishment of multiple paths (tunnels) between source-destination pairs without having to modify the underlying routing protocol(s). Based on the proposed architecture we propose a measurement-based multipath routing algorithm derived from simultaneous perturbation stochastic approximation. The proposed algorithm does not assume that the gradient of analytical cost function is known to the algorithm, but rather relies on noisy estimates from measurements. Using the analytical model presented in the paper we prove the convergence of the algorithm to the optimal solution. Simulation results are presented to demonstrate the advantages of the proposed algorithm under a variety of network scenarios. A comparative study with an existing optimal routing algorithm, MATE, is also provided
Keywords: algorithm; network; approximation; routing; IP; measurement; network; monitoring; optimization; perturbation; multipath; network; measurement-based; networks; Internet; optimisation; routing; processes; protocol; IP; protocols; stochastic; Routing; Stochastic

Measuring HPC productivity - Faulk,S.; Gustafson,J.; Johnson,P.; Porter, Adam; Tichy,W.; Votta,L. (International Journal of High Performance Computing Applications, 2004)

Mining tool for surveillance video - Ghanem,N.M.; David Doermann; Davis, Larry S.; DeMenthon,D. (SPIE 16th International Symposium on Electronic Imaging, Storage and Retrieval Methods and Applications for Multimedia, 2004)
This paper describes a system for the mining of surveillance video. Our main contributions are: providing ahigh level query language for submitting queries about spatial and temporal relations of background regions and moving entities, and about human activities; providing a compiler to map high level queries into a set of novel Petri net filters that utilize computer vision algorithms to answer components of the queries; and providing a powerful graphical interface where users have the ability to formulate the query visually.

Mining Tools for Surveillance Video - Ghanem,N.; David Doermann; Davis, Larry S.; DeMenthon,D. (Proceedings in SPIE 16th International Symposium on Electronic Imaging, 2004)

Mixing ideas: a new technique for working with young children as design partners - Guha,M.L.; Druin, Allison; Chipman,G.; Fails,J. A; Simms,S.; Farber,A. (Proceedings of the 2004 conference on Interaction design and children: building a community, 2004)

A Model-based Distributed Continuous Quality Assurance Process to Enhance the Quality of Service of Evolving Performance-intensive Software Systems - Yilmaz,C.; Krishna,A. S; Memon, Atif M.; Porter, Adam; Schmidt,D. C; Gokhale,A.; Natarajan,B. (Proceedings of the 2nd ICSE Workshop on Remote Analysis and Measurement of Software Systems (RAMSS), Edinburgh, Scotland, UK, 2004)
Performance-intensive software, such as that found in high-perfo-rmance computing systems and distributed real-time and embedded systems, increasingly executes on a multitude of platforms and user contexts. To ensure that performance-intensive software meets its quality of service (QoS) requirements, it must often be fine-tuned to specific platforms/contexts by adjusting many (in some cases hun- dreds of) configuration options. Developers who write these types of systems must therefore try to ensure that their additions and mod- ifications work across this large configuration space. In practice, however, time and resource constraints often force developers to assess performance on very few configurations and to extrapolate from these to the entire configuration space, which allows many performance bottlenecks and sources of QoS degradation to escape detection until systems are fielded. To improve the assessment of performance across large config- uration spaces, we present a model-based approach to develop- ing and deploying a new distributed continuous quality assurance (DCQA) process. Our approach builds upon and extends the Skoll environment, which is developing and validating novel software QA processes and tools that leverage the extensive computing resources of worldwide user communities in a distributed, continuous man- ner to significantly and rapidly improve software quality. This pa- per describes how our new DCQA performance assessment process enables developers to run formally-designed screening experiments that isolate the most significant options. After that, exhaustive ex- periments (on the now much smaller configuration space) are con- ducted. We implemented this process using model-based software tools and executed it in the Skoll environment to demonstrate its ef- fectiveness via two experiments on widely used QoS-enabled mid- dleware. Our results show that model-based DCQA processes im- proves developer insight into the effect of system changes on per- formance at an acceptable cost.

Model-driven data acquisition in sensor networks - Deshpande, Amol; Guestrin,Carlos; Madden,Samuel R.; Hellerstein,Joseph M.; Wei Hong (Proceedings of the Thirtieth international conference on Very large data bases - Volume 30, 2004)
Declarative queries are proving to be an attractive paradigm for ineracting with networks of wireless sensors. The metaphor that "the sensornet is a database" is problematic, however, because sensors do not exhaustively represent the data in the real world. In order to map the raw sensor readings onto physical reality, a model of that reality is required to complement the readings. In this paper, we enrich interactive sensor querying with statistical modeling techniques. We demonstrate that such models can help provide answers that are both more meaningful, and, by introducing approximations with probabilistic confidences, significantly more efficient to compute in both time and energy. Utilizing the combination of a model and live data acquisition raises the challenging optimization problem of selecting the best sensor readings to acquire, balancing the increase in the confidence of our answer against the communication and data acquisition costs in the network. We describe an exponential time algorithm for finding the optimal solution to this optimization problem, and a polynomial-time heuristic for identifying solutions that perform well in practice. We evaluate our approach on several real-world sensor-network data sets, taking into account the real measured data and communication quality, demonstrating that our model-based approach provides a high-fidelity representation of the real phenomena and leads to significant performance gains versus traditional data acquisition techniques.

Modelling disease outbreaks in realistic urban social networks - Eubank,Stephen; Guclu,Hasan; Kumar,V. S. Anil; Marathe,Madhav V.; Srinivasan, Aravind; Toroczkai,Zolt|[aacute]|n; Wang,Nan (Nature, 2004)
Most mathematical models for the spread of disease use differential equations based on uniform mixing assumptions1 or ad hoc models for the contact process2, 3, 4. Here we explore the use of dynamic bipartite graphs to model the physical contact patterns that result from movements of individuals between specific locations. The graphs are generated by large-scale individual-based urban traffic simulations built on actual census, land-use and population-mobility data. We find that the contact network among people is a strongly connected small-world-like5 graph with a well-defined scale for the degree distribution. However, the locations graph is scale-free6, which allows highly efficient outbreak detection by placing sensors in the hubs of the locations network. Within this large-scale simulation framework, we then analyse the relative merits of several proposed mitigation strategies for smallpox spread. Our results suggest that outbreaks can be contained by a strategy of targeted vaccination combined with early detection without resorting to mass vaccination of a population.

Multi-level fast multipole method for thin plate spline evaluation - Zandifar,A.; Lim,S.; Duraiswami, Ramani; Gumerov, Nail A.; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
Image registration is an important problem in image processing and computer vision. Much recent work in image registration is on matching non-rigid deformations. Thin plate splines are an effective image registration method when the deformation between two images can be modeled as the bending of a thin metal plate on point constraints such that the topology is preserved (non-rigid deformation). However, because evaluating the computed TPS model at all the image pixels is computationally expensive, we need to speed it up. We introduce the use of multi-level fast muitipole method (MLFMM) for this purpose. Our contribution lies in the presentation of a clear and concise MLFMM framework for TPS, which will be useful for future application developments. The achieved speedup using MLFMM is an improvement from O(N2) to O(N log N). We show that the fast evaluation outperforms the brute force method while maintaining acceptable error bound.
Keywords: (mathematics); Computer; deformation; evaluation; fast; image; MATCHING; matching; metal; method; multilevel; multipole; nonrigid; pixel; plate; plate; processing; registration; resolution; spline; splines; thin; vision

New directions in design for manufacturing - Herrmann,J.W.; Cooper,J.; Gupta,S.K.; Hayes,C. C.; Ishii,K.; Kazmer,D.; Sandborn,P. A.; Wood,W. H. (2004)
This paper gives an overview of research that is expandingthe domain of design for manufacturing (DFM) into new and important areas. This paper covers DFM and concurrent engineering, DFM for conceptual design, DFM for embodiment design, DFM for detailed design, design for production, platform design for reducing time-to-market, design for system quality, design for life cycle costs, and design for environment. The paper concludes with some general guidelines that suggest how manufacturing firms can develop useful, effective DFM tools.

A Note on Efficient Computation of Haplotypes via Perfect Phylogeny - Bafna,Vineet; Gusfield,Dan; Hannenhalli, Sridhar; Yooseph,Shibu (Journal of Computational Biology, 2004)
The problem of inferring haplotype phase from a population of genotypes has received a lot of attention recently. This is partly due to the observation that there are many regions on human genomic DNA where genetic recombination is rare (Helmuth, 2001; Daly et al., 2001; Stephens et al., 2001; Friss et al., 2001). A Haplotype Map project has been announced by NIH to identify and characterize populations in terms of these haplotypes. Recently, Gusfield introduced the perfect phylogeny haplotyping problem, as an algorithmic implication of the no-recombination in long blocks observation, together with the standard population-genetic assumption of infinite sites. Gusfield's solution based on matroid theory was followed by direct θ(nm2 ) solutions that use simpler techniques (Bafna et al., 2003; Eskin et al., 2003), and also bound the number of solutions to the PPH problem. In this short note, we address two questions that were left open. First, can the algorithms of Bafna et al. (2003) and Eskin et al. (2003) be sped-up to O(nm + m2 ) time, which would imply an O(nm) time-bound for the PPH problem? Second, if there are multiple solutions, can we find one that is most parsimonious in terms of the number of distinct haplotypes.We give reductions that suggests that the answer to both questions is "no." For the first problem, we show that computing the output of the first step (in either method) is equivalent to Boolean matrix multiplication. Therefore, the best bound we can presently achieve is O(nmω–1), where ω ≤ 2.52 is the exponent of matrix multiplication. Thus, any linear time solution to the PPH problem likely requires a different approach. For the second problem of computing a PPH solution that minimizes the number of distinct haplotypes, we show that the problem is NP-hard using a reduction from Vertex Cover (Garey and Johnson, 1979).

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.

Preserving distributed systems critical properties: a model-driven approach - Yilmaz,C.; Memon, Atif M.; Porter, Adam; Krishna,A. S; Schmidt,D. C; Gokhale,A.; Natarajan,B. (Software, IEEE, 2004)
The need for creating predictability in distributed systems is most often specified in terms of quality-of-service (QoS) requirements, which help define the acceptable levels of dependability with which capabilities such as processing capacity, data throughput, or service availability reach users. For longer-term properties such as scalability, maintainability, adaptability, and system security, we can similarly use persistent software attributes (PSAs) to specify how and to what degree such properties must remain intact as a network expands and evolves over time. The Skoll distributed continuous software quality assurance process helps to identify viable system and software configurations for meeting stringent QOS and PSA requirements by coordinating the use of distributed computing resources. The authors tested their process using the large, rapidly evolving ACE+TAO middleware suite.
Keywords: configuration management; formal verification; Middleware; middleware suite; model-driven approach; persistent software attributes; QoS requirements; Quality assurance; quality of service; quality-of-service; Skoll distributed computing resources; software configuration; Software maintenance; Software quality; software quality assurance process; system dependability

Reconstructing Images of Bar Codes for Construction Site Object Recognition - Gilsinn,David E.; Cheok,Geraldine S.; O'Leary, Dianne P. (Automation in Construction (Elsevier), 2004)

Recursions for the computation of multipole translation and rotation coefficients for the 3-D Helmholtz equation - Gumerov, Nail A.; Duraiswami, Ramani (SIAM Journal on Scientific Computing, 2004)
We develop exact expressions for the coefficients of series representations of trans-lations and rotations of local and multipole fundamental solutions of the Helmholtz equation in spherical coordinates. These expressions are based on the derivation of recurrence relations, some of which, to our knowledge, are presented here for the first time. The symmetry and other properties of the coefficients are also examined and, based on these, efficient procedures for calculating them are presented. Our expressions are direct and do not use the Clebsch–Gordan coefficients or the Wigner 3-j symbols, although we compare our results with methods that use these to prove their accuracy. For evaluating an Nt term truncation of the translated series (involving O(N2t) multipoles), our expressions require O(N3t) evaluations, compared to previous exact expressions that require O(N5t) operations.

Representation and Recognition of Events in Surveillance Video Using Petri Nets - Ghanem,N.; DeMenthon,D.; David Doermann; Davis, Larry S. (Second IEEEWorkshop on Event Mining 2004, CVPR2004, 2004)
Detection of events is an essential task in surveillance applications. This task requires finding a general event representation method and developing efficient recognition algorithms dealing with this representation. In this paper, we describe an interactive system for querying surveillance video about events. The queries may not be known in advance and have to be composed from primitive events and previously defined queries. We propose using Petri nets as both representation and recognition methods. The Petri net representation for users' queries is derived automatically from simpler event nets. Recognition is then performed by tokens moving through the Petri nets.

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.

SlideBar: Analysis of a linear input device - Chipman,L.E.; Bederson, Benjamin B.; Golbeck,J. (Behaviour & Information Technology, 2004)

A spherical microphone array system for traffic scene analysis - Zhiyun Li; Duraiswami, Ramani; Grassi,E.; Davis, Larry S. (Intelligent Transportation Systems, 2004. Proceedings. The 7th International IEEE Conference on, 2004)
This paper describes a practical spherical microphone array system for traffic auditory scene capture and analysis. Our system uses 60 microphones positioned on the rigid surface of a sphere. We then propose an optimal design of a robust spherical beamformer with minimum white noise gain (WNG) of -6 dB. We test this system in a real-world traffic environment. Some preliminary simulation and experimental results are presented to demonstrate its performance. This system may also find applications in broader areas such as 3D audio, virtual environment, etc.
Keywords: -6; 3D; analysis; array; arrays; audio; auditory; beamformer; capture; dB; environment; gain; microphone; NOISE; noise; processing; real; robust; scene; signal; spherical; system; traffic; traffic; virtual; white; World

A STEP TOWARDS AUTOMATED DESIGN OF INDEX-PLATE MULTI-SHOT MOLDS - Li,X.; Gupta,S.K. (2004)
This paper describes an algorithm for automateddesign of index-plate type of multi-shot molds for manufacturing multi-material objects. This new algorithm is a significant improvement over previous mold design algorithms and it accounts for constraints associated with the index-plate molding process. Our algorithm works in the following manner. First, based on the index-plate process constraints, we determine whether the given multi-material object is moldable by index- plate process by analyzing the geometry of the object. If the object can be molded, then the molding sequence is determined. Finally, the mold pieces. We expect that the algorithm described in this paper will provide the necessary foundations for automating the design of index-plate molds and therefore will help in significantly reducing the mold manufacturing lead-time associated with this type of molds.

A STEP TOWARDS INTEGRATED PRODUCT/PROCESS DEVELOPMENT OF MOLDED MULTI-MATERIAL STRUCTURES - Gupta,S.K.; Fowler,G. (Tools And Methods Of Competitive Engineering, 2004)
Multi-material molding is emerging as a popularmethod for making multi-material structures. In multi-material molding processes, fabrication and assembly steps are performed concurrently inside the mold. Therefore using existing knowledge on how to design molded products often results in the selection of wrong design alternatives and correcting these mistakes unnecessarily delays the product development process. To overcome this difficulty we need to develop an integrated product/process development methodology for designing molded multi-material structures. This paper presents an overview of different multi-material molding technologies and the role of manufacturing considerations in shape synthesis of molded multi- material structures.

Structure of applicable surfaces from single views - Gumerov, Nail A.; Zandifar,A.; Duraiswami, Ramani; Davis, Larry S. (Computer Vision-ECCV 2004, 2004)
The deformation of applicable surfaces such as sheets of paper satisfies the differential geometric constraints of isometry (lengths and areas are conserved) and vanishing Gaussian curvature. We show that these constraints lead to a closed set of equations that allow recovery of the full geometric structure from a single image of the surface and knowledge of its undeformed shape. We show that these partial differential equations can be reduced to the Hopf equation that arises in non-linear wave propagation, and deformations of the paper can be interpreted in terms of the characteristics of this equation. A new exact integration of these equations is developed that relates the 3-D structure of the applicable surface to an image. The solution is tested by comparison with particular exact solutions. We present results for both the forward and the inverse 3D structure recovery problem.

TM Electromagnetic Scattering from 2D Multilayered Dielectric Bodies-Numerical Solution - Duraiswami, Ramani; Seydou,F.; Gumerov, Nail A. (Applied Computational Electromagnetics Society journal, 2004)
An integral equation approach is derived for an electromagnetic scattering from an M arbitrary multilayereddielectric domain. The integral equation is valid for the 2D and 3D Helmholtz equation. Here we show the numerical solution for the 2D case by using the Nyström method. For validating the method we develop a mode matching method for the case when the domains are multilayered circular cylinders and give numerical results for illustrating the algorithm.

Toolkit design for interactive structured graphics - Bederson, Benjamin B.; Grosjean,J.; Meyer,J. (Software Engineering, IEEE Transactions on, 2004)

Tools for children to create physical interactive storyrooms - Montemayor,J.; Druin, Allison; Chipman,G.; Farber,A.; Guha,M.L. (Computers in Entertainment (CIE), 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

Unsupervised sense disambiguation using bilingual probabilistic models - Bhattacharya,Indrajit; Getoor, Lise; Bengio,Yoshua (Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics, 2004)
We describe two probabilistic models for unsupervised word-sense disambiguation using parallel corpora. The first model, which we call the Sense model, builds on the work of Diab and Resnik (2002) that uses both parallel text and a sense inventory for the target language, and recasts their approach in a probabilistic framework. The second model, which we call the Concept model, is a hierarchical model that uses a concept latent variable to relate different language specific sense labels. We show that both models improve performance on the word sense disambiguation task over previous unsupervised approaches, with the Concept model showing the largest improvement. Furthermore, in learning the Concept model, as a by-product, we learn a sense inventory for the parallel language.

Using the structure of Web sites for automatic segmentation of tables - Lerman,Kristina; Getoor, Lise; Minton,Steven; Knoblock,Craig (Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004)
Many Web sites, especially those that dynamically generate HTML pages to display the results of a user's query, present information in the form of list or tables. Current tools that allow applications to programmatically extract this information rely heavily on user input, often in the form of labeled extracted records. The sheer size and rate of growth of the Web make any solution that relies primarily on user input is infeasible in the long term. Fortunately, many Web sites contain much explicit and implicit structure, both in layout and content, that we can exploit for the purpose of information extraction. This paper describes an approach to automatic extraction and segmentation of records from Web tables. Automatic methods do not require any user input, but rely solely on the layout and content of the Web source. Our approach relies on the common structure of many Web sites, which present information as a list or a table, with a link in each entry leading to a detail page containing additional information about that item. We describe two algorithms that use redundancies in the content of table and detail pages to aid in information extraction. The first algorithm encodes additional information provided by detail pages as constraints and finds the segmentation by solving a constraint satisfaction problem. The second algorithm uses probabilistic inference to find the record segmentation. We show how each approach can exploit the web site structure in a general, domain-independent manner, and we demonstrate the effectiveness of each algorithm on a set of twelve Web sites.

Visualizing type qualifier inference with Eclipse - Greenfieldboyce,D.; Foster, Jeffrey S. (Proceedings of the 2004 OOPSLA workshop on eclipse technology eXchange, 2004)

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

A workshop report: mining for and from the Semantic Web at KDD 2004 - Hotho,Andreas; Sure,York; Getoor, Lise (SIGKDD Explor. Newsl., 2004)
The international workshop on Mining for and from the Semantic Web (MSW) at the KDD 2004 successfully brought together people from the communities Semantic Web and Knowledge Discovery. The goal of the workshop was to strengthen the communication and interaction between these communities as there is currently an agreement that both can benefit largely from each other. Overall the contributions and discussions showed that today mining for the semantic web is the primarily targeted research area. However, with a growing amount of available semantic web data also mining from the semantic web will be more prominent.

19th Biennial Conference on Mechanical Vibration and Noise - Gupta,A. K.; Fadel,G. M.; Lewicki,D. G.; Shabana,A. A.; Royston,T. J.; Gupta,S.K.; Hayes,C.; Herrmann,J.W.; Dym,C. L.; Schmidt,L. C. (American Society of Mechanical Engineers, 2003)

Accuracy, Target Reentry and Fitts’ Law Performance of Preschool Children Using Mice - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison; Guimbretiere,F. (University of Maryland Technical Report, HCIL-2003, 2003)

Acoustical scattering from N spheres using a multilevel fast multipole method - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2003)
We develop an efficient computational method for wave scattering from a large number of spherical objects that are characterized by their radii, locations, and complex acoustical impedances of the surfaces. The direct T‐matrix method for solution of the problem that was developed and tested in [Gumerov and Duraiswami, J. Acoust. Soc. Am. 112, 2688–2701 (2002)] is inefficient for computations involving a large number of scatterers. Here, we implement and test a multilevel fast multipole method for speeding up the solution and achieving better memory complexity. The method is based on hierarchical space subdivision with oct‐trees using optimal space‐partitioning, on a theory for fast translation and re‐expansion of multipole solutions of the Helmholtz equation, and employs an iterative technique for the solution of large dense systems of linear equations with reflection‐based iterations. For N scatterers the method provides O(N log N) asymptotic complexity opposed to O(N3) complexity of the direct T‐matrix approach. The results of computations were tested against solutions obtained by other methods, such as the boundary element method and the direct T‐matrix method tested in our early study, and show the computational efficiency and accuracy of the solution technique. [Work supported by NSF Awards 0086075 and 0219681 is gratefully acknowledged.]

Algorithms for computing global accessibility cones - Dhaliwal,S.; Gupta,S.K.; Huang,J.; Priyadarshini,A. (Journal of Computing and Information Science in Engineering, 2003)

Algorithms for selecting cutters in multi-part milling problems - Yao,Zhiyang; Gupta, Satyandra K.; Nau, Dana S. (Computer-Aided Design, 2003)
This paper describes geometric algorithms for automatically selecting an optimal sequence of cutters for machining a set of 2.5-D parts. In milling operations, cutter size affects the machining time significantly. Meanwhile, if the batch size is small, it is also important to shorten the time spent on loading tools into the tool magazine and establishing z-length compensation values. Therefore, in small-batch manufacturing, if we can select a set of milling tools that will produce good machining time on more than one type of parts, then several unnecessary machine-tool reconfiguration operations can be eliminated. In selecting milling cutters we consider both the tool loading time and the machining time and generate solutions that allow us to minimize the total machining time. In this paper we first present algorithms for finding the area that can be cut by a given cutter. Then we describe a graph search formulation for the tool selection problem. Finally, the optimal sequence of cutters is selected by using Dijkstra's shortest path planning algorithm.
Keywords: 2.5-D Milling; cutter selection; Geometric Algorithms

Analysis of particular phononic structures using single integral equations - Seydou,Fadoulourahmane; Duraiswami, Ramani; Gumerov, Nail A. (The Journal of the Acoustical Society of America, 2003)
A fast method for determining phononic (and photonic) bandgaps in composite materials is developed. It is known that in the propagation of waves in a 3D medium containing N scatterers arranged periodically, there exist refractive indices for which such structures have bandgaps, i.e., frequencies for which no waves can propagate inside. Our task is to find the frequencies that generate these prohibited waves. This requires the solution of an eigenvalue problem for the Helmholtz operator. To solve this problem we choose an alternate route which uses boundary integral equations. We derive a single integral equation on each of the interfaces between the outer region and the scatterers, considering a general transmission boundary condition, by using a hybrid method using layer potentials and Green’s formula. This approach reduces the number of unknowns considerably in comparison to other methods, but requires the treatment of large dense matrices and many matrix vector multiplications. To remedy this, we use the Fast Multipole Method. For solving the eigenvalue problem we discuss two methods: the Newton method and a method based on the Cauchy formula. Details of the numerical implementation, and results will be presented for different cases: sound hard, sound soft, impedance and transmission boundary conditions. [Work partially supported by NSF Award 0219681 is gratefully acknowledged.]

Approximation Algorithms for Channel Allocation Problems in Broadcast Networks - Gandhi,Rajiv; Khuller, Samir; Srinivasan, Aravind; Wang,Nan (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques, 2003)
We study two packing problems that arise in the area of dissemination-based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem , there are users who request subsets of items. There are a fixed number of channels that can carry an arbitrary amount of information. Each user must get all of the requested items from one channel, i.e., all the data items of each request must be broadcast on some channel. The load on any channel is the number of items that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem and also show that the problem is MAX-SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick ( Networks, 41:13-23, 2003 ). Each channel here can deliver information to at most k users, and we aim to minimize the total load on all channels. We present an O ( n⅓ )–approximation algorithm and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize to the case of hypergraphs.

Augmented intelligibility in simultaneous multi-talker environments - Mesgarani,N.; Shamma,S.; Grant,K.W.; Duraiswami, Ramani (Proc. International Conference on Auditory Display (ICAD’03), 2003)
Speech intelligibility can be severely compromised inenvironments where there are several competing speakers. It may be possible, however, to improve speech intelligibility in such environments by manipulating certain acoustic parameters known to facilitate the segregation of competing signals. The first step in designing such a feature-rich audio display is to understand the significant elements of human auditory perception that affect information transmission capacity. We review a series of experiments to examine the impact of different audio-display design parameters on overall intelligibility of simultaneous speech messages and show how using these features may improve intelligibility.

Automatic classification of multi-word expressions in print dictionaries - Geyken,Alexander; Jordan Boyd-Graber (Lingvisticae Investigationes, 2003)
SummaryThis work demonstrates the assignment of multi-word expressions in print dictionaries to POS classes with minimal linguistic resources. In this application, 32,000 entries from the Wörterbuch der deutschen Idiomatik (H. Schemann 1993) were classified using an inductive description of POS sequences in conjunction with a Brill Tagger trained on manually tagged idiomatic entries. This process assigned categories to 86% of entries with 88% accuracy. This classification supplies a meaningful preprocessing step for further applications: the resulting POS-sequences for all idiomatic entries might be used for the automatic recognition of multi-word lexemes in unrestricted text.

Bistro: a scalable and secure data transfer service for digital government applications - Golubchik,Leana; Cheng,William C.; Chou,Cheng-Fu; Khuller, Samir; Samet, Hanan; Wan,C. Justin (Commun. ACM, 2003)
Government at all levels is a major collector and provider of data.Our project focuses on the collection of data over wide-area networks (WANs) and addresses the scalability issues that arise in the context of Internet-based massive data collection applications. Furthermore, security, due to the need for privacy and integrity of the data, is a central issue for data collection applications that use a public infrastructure such as the Internet. Numerous digital government applications require data collection over WANs [5].One compelling example of such an application is the Internal Revenue Service's electronic submission of income tax forms. Other digital government applications include collecting census data, federal statistics, and surveys; gathering and tallying of electronic votes; collecting crime data for the U.S. Justice department; collecting data from sensors for disaster response applications; collecting data from geological surveys; collecting electronic filings of patents, permits, and securities (for SEC) applications; grant proposals and contract bids submissions; and so on. All these applications have scalability and security needs in common.The poor performance that may be experienced by current digital government users, given the existing state of technology (as in Figure 1a), is largely due to how (independent) data transfers using TCP/IP work over the Internet. TCP/IP is good at equally sharing bandwidth between data streams, which in large-scale applications can lead to poor performance for individual clients (as they receive only a very small share of this bandwidth). Given that TCP/IP is here to stay for the foreseeable future, what is needed is a scalable yet cost- effective solution that can be easily deployed over the existing Internet technology.We are designing and developing a system called Bistro, which addresses the scalability needs of digital government data collection applications while allowing them to share the same infrastructure and resources efficiently, cost-effectively, and securely [1]. Bistro's basic approach is to introduce intermediate hosts---bistros---which allow replacement of a traditionally "synchronized client push" approach with a "nonsynchronized combination of client-push and server-pull" approach (as depicted in Figure 1b). This in turn allows spreading of the workload on the destination server and the network over time, with subsequent elimination of hot spots as well as significant improvements in performance for both clients and servers. Our ongoing research [2, 4] indicates that orders of magnitude of improvement can be achieved with the Bistro architecture and the corresponding data collection algorithms it affords.Bistro's design allows for a gradual deployment and experimentation over the Internet (by simply downloading Bistro server software and installing it on public servers). Bistro's security protocol and trust structure [3] are designed such that only encrypted data travels through (not necessarily trusted) bistros. This means a government agency does not need to trust bistros installed by other agencies or commercial institutions. At the same time, these (untrusted) bistros can significantly improve the agency's data collection performance. Each application (within each agency) can have its own scalability, security, fault tolerance, and other data collection needs, and these applications and agencies can still share available resources, if so desired, across all Bistro servers.We believe an appropriately designed single infrastructure such as Bistro can address all digital government wide-area data collection needs in a scalable, secure, and cost-effective manner. (For more information, see bourbon.usc.edu/iml/bistro/.

Bistro: a scalable and secure data transfer service for digital government applications - Golubchik,Leana; Cheng,William C.; Chou,Cheng-Fu; Khuller, Samir; Samet, Hanan; Wan,C. Justin (Communications of the ACM, 2003)
Government at all levels is a major collector and provider of data.Our project focuses on the collection of data over wide-area networks (WANs) and addresses the scalability issues that arise in the context of Internet-based massive data collection applications. Furthermore, security, due to the need for privacy and integrity of the data, is a central issue for data collection applications that use a public infrastructure such as the Internet. Numerous digital government applications require data collection over WANs [5].One compelling example of such an application is the Internal Revenue Service's electronic submission of income tax forms. Other digital government applications include collecting census data, federal statistics, and surveys; gathering and tallying of electronic votes; collecting crime data for the U.S. Justice department; collecting data from sensors for disaster response applications; collecting data from geological surveys; collecting electronic filings of patents, permits, and securities (for SEC) applications; grant proposals and contract bids submissions; and so on. All these applications have scalability and security needs in common.The poor performance that may be experienced by current digital government users, given the existing state of technology (as in Figure 1a), is largely due to how (independent) data transfers using TCP/IP work over the Internet. TCP/IP is good at equally sharing bandwidth between data streams, which in large-scale applications can lead to poor performance for individual clients (as they receive only a very small share of this bandwidth). Given that TCP/IP is here to stay for the foreseeable future, what is needed is a scalable yet cost- effective solution that can be easily deployed over the existing Internet technology.We are designing and developing a system called Bistro, which addresses the scalability needs of digital government data collection applications while allowing them to share the same infrastructure and resources efficiently, cost-effectively, and securely [1]. Bistro's basic approach is to introduce intermediate hosts---bistros---which allow replacement of a traditionally "synchronized client push" approach with a "nonsynchronized combination of client-push and server-pull" approach (as depicted in Figure 1b). This in turn allows spreading of the workload on the destination server and the network over time, with subsequent elimination of hot spots as well as significant improvements in performance for both clients and servers. Our ongoing research [2, 4] indicates that orders of magnitude of improvement can be achieved with the Bistro architecture and the corresponding data collection algorithms it affords.Bistro's design allows for a gradual deployment and experimentation over the Internet (by simply downloading Bistro server software and installing it on public servers). Bistro's security protocol and trust structure [3] are designed such that only encrypted data travels through (not necessarily trusted) bistros. This means a government agency does not need to trust bistros installed by other agencies or commercial institutions. At the same time, these (untrusted) bistros can significantly improve the agency's data collection performance. Each application (within each agency) can have its own scalability, security, fault tolerance, and other data collection needs, and these applications and agencies can still share available resources, if so desired, across all Bistro servers.We believe an appropriately designed single infrastructure such as Bistro can address all digital government wide-area data collection needs in a scalable, secure, and cost-effective manner. (For more information, see bourbon.usc.edu/iml/bistro/.

Bootstrapping security associations for routing in mobile ad-hoc networks - Bobba,R. B; Eschenauer,L.; Gligor,V.; Arbaugh, William A. (IEEE Global Telecommunications Conference, 2003. GLOBECOM '03, 2003)
To date, most solutions proposed for secure routing in mobile ad-hoc networks (MANETs), assume that secure associations between pairs of nodes can be established on-line; e.g., by a trusted third party, by distributed trust establishment. However, establishing such security associations, with or without trusted third parties, requires reliance on routing layer security. In this paper, we eliminate this apparent cyclic dependency between security services and secure routing in MANETs and show how to bootstrap security for the routing layer. We use the notion of statistically unique and cryptographically verifiable (SUCV) identifiers to implement a secure binding between IP addresses and keys that is independent of any trusted security service. We illustrate our solution with the dynamic source routing (DSR) protocol and compare it with other solutions for secure routing.
Keywords: ad hoc networks; bootstrapping security association; Cryptographic protocols; dynamic source routing protocol; Fabrics; Intelligent networks; IP address; IP key; IP networks; Message authentication; mobile ad-hoc network; mobile radio; Protection; Public key; public key cryptography; routing layer security reliability; routing protocols; secure routing; Security; security service; statistically unique cryptographically verification; telecommunication security

Cache-and-query for wide area sensor databases - Deshpande, Amol; Nath,Suman; Gibbons,Phillip B.; Seshan,Srinivasan (Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003)
Webcams, microphones, pressure gauges and other sensors provide exciting new opportunities for querying and monitoring the physical world. In this paper we focus on querying wide area sensor databases, containing (XML) data derived from sensors spread over tens to thousands of miles. We present the first scalable system for executing XPATH queries on such databases. The system maintains the logical view of the data as a single XML document, while physically the data is fragmented across any number of host nodes. For scalability, sensor data is stored close to the sensors, but can be cached elsewhere as dictated by the queries. Our design enables self starting distributed queries that jump directly to the lowest common ancestor of the query result, dramatically reducing query response times. We present a novel query-evaluate gather technique (using XSLT) for detecting (1) which data in a local database fragment is part of the query result, and (2) how to gather the missing parts. We define partitioning and cache invariants that ensure that even partial matches on cached data are exploited and that correct answers are returned, despite our dynamic query-driven caching. Experimental results demonstrate that our techniques dramatically increase query throughputs and decrease query response times in wide area sensor databases.

On the Covering Steiner Problem - Gupta,Anupam; Srinivasan, Aravind (FST TCS 2003: Foundations of Software Technology and Theoretical Computer ScienceFST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003)
The Covering Steiner problem is a common generalization of the k -MST and Group Steiner problems. An instance of the Covering Steiner problem consists of an undirected graph with edge-costs, and some subsets of vertices called groups , with each group being equipped with a non-negative integer value (called its requirement ); the problem is to find a minimum-cost tree which spans at least the required number of vertices from every group. When all requirements are equal to 1, this is the Group Steiner problem. While many covering problems (e.g., the covering integer programs such as set cover) become easier to approximate as the requirements increase, the Covering Steiner problem remains at least as hard to approximate as the Group Steiner problem; in fact, the best guarantees previously known for the Covering Steiner problem were worse than those for Group Steiner as the requirements became large. In this work, we present an improved approximation algorithm whose guarantee equals the best known guarantee for the Group Steiner problem.

Data Structures and Algorithms in C++ - Goodrich, Michael T.; Tamassia, Roberto; Mount, Dave (John Wiley & Sons, 2003)
* Provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation * Each data structure is presented using ADTs and their respective implementations * Helps provide an understanding of the wide spectrum of skills ranging from sound algorithm and data structure design to efficient implementation and coding of these designs in C++
Keywords: Computers / Databases / General; Computers / Programming / Algorithms; Computers / Programming / General; Computers / Programming Languages / C; Fiction / General

Data Structures, Optimal Choice of Parameters, and Complexity Results for Generalized Multilevel Fast Multipole Methods in $d$ Dimensions - Gumerov, Nail A.; Duraiswami, Ramani; Borovikov,Eugene A. (Technical Reports from UMIACS UMIACS-TR-2003-28, 2003)
We present an overview of the Fast Multipole Method, explain the use ofoptimal data structures and present complexity results for the algorithm. We explain how octree structures and bit interleaving can be simply used to create efficient versions of the multipole algorithm in $d$ dimensions. We then present simulations that demonstrate various aspects of the algorithm, including optimal selection of the clustering parameter, the influence of the error bound on the complexity, and others. The use of these optimal parameters results in a many-fold speed-up of the FMM, and prove very useful in practice. UMIACS-TR-2003-28
Keywords: Technical Report

Digital Government-Bistro: A Scalable and Secure Data Transfer Service for Digital Government Applications - Golubchik,L.; Cheng,W. C; Chou,C. F; Khuller, Samir; Samet, Hanan; Wan,Y. C.J (Communications of the ACM-Association for Computing Machinery-CACM, 2003)

Direct Detection of Vibrio Cholerae and ctxA in Peruvian Coastal Water and Plankton by PCR - Lipp,Erin K.; Rivera,Irma N. G.; Gil,Ana I.; Espeland,Eric M.; Choopun,Nipa; Louis,Valérie R.; Russek-Cohen,Estelle; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2003)
Seawater and plankton samples were collected over a period of 17 months from November 1998 to March 2000 along the coast of Peru. Total DNA was extracted from water and from plankton grouped by size into two fractions (64 μm to 202 μm and >202 μm). All samples were assayed for Vibrio cholerae, V. cholerae O1, V. cholerae O139, and ctxA by PCR. Of 50 samples collected and tested, 33 (66.0%) were positive for V. cholerae in at least one of the three fractions. Of these, 62.5% (n = 32) contained V. cholerae O1; ctxA was detected in 25% (n = 20) of the V. cholerae O1-positive samples. None were positive for V. cholerae O139. Thus, PCR was successfully employed in detecting toxigenic V. cholerae directly in seawater and plankton samples and provides evidence for an environmental reservoir for this pathogen in Peruvian coastal waters.

Driving scientific applications by data in distributed environments - Saltz, J.; Catalyurek,U.; Kurc, T.; Gray,M.; Hastings,S.; Langella,S.; Narayanan,S.; Martino,R.; Bryant,S.; Peszynska,M.; others (Computational Science—ICCS 2003, 2003)

Dynamic query choropleth maps for information seeking and decision making - Norman,K.; Zhao,H.; Shneiderman, Ben; Golub,E. (Proc. Human-Computer Interaction International, 2003)
Information retrieval and visualization can be combined in dynamic query systems that allow users unparalleled access to information for decision making. In this paper, we report on the development and evaluation of a dynamic query system (YMap) that displays information on a chloropleth map using double thumb sliders to select ranges of query variables. The YMap prototype is a Java-Applet that supports panning and zooming. Several usability studies were conducted on early prototypes that resulted in the current version. Applications of YMap for decision making tasks are discussed.

Dynamic query visualisations on world wide web clients: A DHTML solution for maps and scattergrams - Golub,E.; Shneiderman, Ben (International journal of Web engineering and technology, 2003)
Dynamic queries are gaining popularity as a method for interactive information visualisation. Many implementations have been made on personal computers, and there is increasing interest in Web-based designs. While Java and Flash strategies have been developed, we believe that a Dynamic HTML implementation could help promote more widespread use. We implemented double-box range sliders with choropleth maps and scattergrams, which are two popular visualisations, using HTML layers and tables. This paper describes our methods for slider control, visual presentation, and displaying/updating results for these visualisations. Visual design issues innovations and performance enhancements were necessary to create viable designs.

Efficient peer-to-peer searches using result-caching - Bhattacharjee, Bobby; Chawathe,S.; Gopalakrishnan,V.; Keleher,P.; Silaghi,B. (Peer-to-Peer Systems II, 2003)
Existing peer-to-peer systems implement a single function well: data lookup. There is now a wealth of research describing how to reliably disseminate, and to later retrieve, data in a scalable and load-balanced manner.

The genome sequence of Bacillus anthracis Ames and comparison to closely related bacteria - Read,Timothy D.; Peterson,Scott N.; Tourasse,Nicolas; Baillie,Les W.; Paulsen,Ian T.; Nelson,Karen E.; Tettelin,Herv|[eacute]|; Fouts,Derrick E.; Eisen,Jonathan A.; Gill,Steven R.; Holtzapple,Erik K.; |[Oslash]|kstad,Ole Andreas; et al. (Nature, 2003)
Bacillus anthracis is an endospore-forming bacterium that causes inhalational anthrax1. Key virulence genes are found on plasmids (extra-chromosomal, circular, double-stranded DNA molecules) pXO1 (ref. 2) and pXO2 (ref. 3). To identify additional genes that might contribute to virulence, we analysed the complete sequence of the chromosome of B. anthracis Ames (about 5.23 megabases). We found several chromosomally encoded proteins that may contribute to pathogenicity—including haemolysins, phospholipases and iron acquisition functions—and identified numerous surface proteins that might be important targets for vaccines and drugs. Almost all these putative chromosomal virulence and surface proteins have homologues in Bacillus cereus, highlighting the similarity of B. anthracis to near-neighbours that are not associated with anthrax4. By performing a comparative genome hybridization of 19 B. cereus and Bacillus thuringiensis strains against a B. anthracis DNA microarray, we confirmed the general similarity of chromosomal genes among this group of close relatives. However, we found that the gene sequences of pXO1 and pXO2 were more variable between strains, suggesting plasmid mobility in the group. The complete sequence of B. anthracis is a step towards a better understanding of anthrax pathogenesis.

HCIL Technical Report Listing (1993-2002) - Ceaparu,I.; Druin, Allison; Guimbretiere,F.; Manipulation,D.; Shneiderman, Ben; Westerlurid,B.; Keogh,E.; Hochheiser,H.; Shrieidemian,B.; Shneidemiari,B.; others (The craft of information visualization: readings and reflections, 2003)

Implementing On-line Software Upgrades in Java - Gebremichael,M.; Hicks, Michael W. (University of Maryland, College Park, 2003)
There are many systems that have to be available without interruption and so cannot bebrought down for modifications. Examples of such applications include financial transaction processors, telephone switches and air traffic control systems. On the other hand, hardly any software is deployed error-free or fully functional, thus requiring fixes and changes. Therefore, there is a need for runtime software upgrading capability for such systems. This paper discusses existing approaches of “hotswapping” – runtime updating of classes – for the Java language. The different implementations of hotswapping are compared with respect to functionality, efficiency, ease of use and limitations. In addition, an improvement for one hotswapping mechanism is suggested and implemented.

An Improved Approximation Ratio for the Covering Steiner Problem - Gupta,Anupam; Srinivasan, Aravind (Theory of Computing, 2003)
In the Covering Steiner problem, we are given an undirected graph with edge-costs, and some subsets of vertices called groups, with each group being equipped with a non-negative integer value (called its requirement); the problem is to find a minimum-cost tree which spans at least the required number of vertices from every group. The Covering Steiner problem is a common generalization of the k-MST and the Group Steiner problems; indeed, when all the vertices of the graph lie in one group with a requirement of k, we get the k-MST problem, and when there are multiple groups with unit requirements, we obtain the Group Steiner problem. While many covering problems (e.g., the covering integer programs such as set cover) become easier to approximate as the requirements increase, the Covering Steiner problem remains at least as hard to approximate as the Group Steiner problem; in fact, the best guarantees previously known for the Covering Steiner problem were worse than those for Group Steiner as the requirements became large. In this work, we present an improved approximation algorithm whose guarantee equals the best known guarantee for the Group Steiner problem.

Improved fast gauss transform and efficient kernel density estimation - Yang,C.; Duraiswami, Ramani; Gumerov, Nail A.; Davis, Larry S. (Computer Vision, 2003. Proceedings. Ninth IEEE International Conference on, 2003)
Evaluating sums of multivariate Gaussians is a common computational task in computer vision and pattern recognition, including in the general and powerful kernel density estimation technique. The quadratic computational complexity of the summation is a significant barrier to the scalability of this algorithm to practical applications. The fast Gauss transform (FGT) has successfully accelerated the kernel density estimation to linear running time for low-dimensional problems. Unfortunately, the cost of a direct extension of the FGT to higher-dimensional problems grows exponentially with dimension, making it impractical for dimensions above 3. We develop an improved fast Gauss transform to efficiently estimate sums of Gaussians in higher dimensions, where a new multivariate expansion scheme and an adaptive space subdivision technique dramatically improve the performance. The improved FGT has been applied to the mean shift algorithm achieving linear computational complexity. Experimental results demonstrate the efficiency and effectiveness of our algorithm.
Keywords: adaptive; algorithm; multivariate; complexity; computer; complexity; Gaussian; computational; density; estimation; mean; expansion; Gauss; processes; computational; recognition; quadratic; scheme; pattern; shift; space; subdivision; technique; computer; theory; transform; kernel; vision; estimation; vision; fast

Interactive Visualization of Large Tetrahedral Meshes through Selective Refinement - Cignoni,P.; De Floriani, Leila; Magillo,P.; Puppo,E.; Scopigno,R.; di Genova,U. (IEEE Transactions on Visualization and Computer Graphics, 2003)
In this paper, we address the problem of the efficient visualization of very largeirregular volume datasets. To this aim, we exploit a multiresolution representation based on a domain decomposition into tetrahedral cells. A new compact data struc- ture is described which encodes the whole dataset at a virtually continuous range of different resolutions, with a storage cost six times lower than a standard data struc- ture for tetrahedral meshes. Such structure supports on-line selective refinement to focus resolution on areas that the user considers more critical, based on either field values, or domain location, or opacity of the transfer function. Selective refinement is used to trade-off between resolution and speed in visualization, according to user needs and hardware constraints. These features have been implemented in a new system, called TAn2 (Tetrahedra Analyzer), for the interactive visualization of three- dimensional scalar fields defined on very large tetrahedral meshes. Multiresolution representation and selective refinement make the system fully scalable with respect to the size of the dataset and to hardware requirements.