Game-tree search with combinatorially large belief states - Parker,A.; Nau, Dana S.; V.S. Subrahmanian (2005)
In games such as kriegspiel chess (a chess variantwhere players have no direct knowledge of the op- ponent’s pieces’ locations) the belief state’s sizes dwarf those of other partial information games like bridge, scrabble, and poker–and there is no easy way to generate states satisfying the given observa- tions. We show that statistical sampling approaches can be developed to do well in such games. We show that it is not necessary for the random sample to consist only of game boards that satisfy each and every one of a player’s observations. In fact, we win 24% more often by beginning with such completely consistent boards and gradually switching (as the game progressed) to boards that are merely consistent with the latest observation. This surprising result is explained by noting that as the game progresses, a board that is consistent with the last move becomes more and more likely to be consistent with the entire set of observations, even if we have no idea what sequence of moves might have actually generated this board.

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, 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 half-edge tree: a compact data structure for level-of-detail tetrahedral meshes - Danovaro,E.; De Floriani, Leila; Magillo,P.; Puppo,E.; Sobrero,D.; Sokolovsky,N. (Shape Modeling and Applications, 2005 International Conference, 2005)
We propose a new data structure for the compact encoding of a level-of detail (LOD) model of a three-dimensional scalar field based on unstructured tetrahedral meshes. Such data structure, called a half-edge tree (HET), is built through the iterative application of a half-edge collapse, i.e. by contracting an edge to one of its endpoints. We also show that selective refined meshes extracted from an HET contain on average about 34% and up to 75% less tetrahedra than those extracted from an LOD model built through a general edge collapse.
Keywords: application; compact; computational; data; detection; edge; encoding; generation; geometry; half-edge; iterative; level-of-detail; mesh; meshes; methods; model; structure; structures; tetrahedral; tree; tree

A hierarchical task-network planner based on symbolic model checking - Kuter,U.; Nau, Dana S.; Pistore,M.; Traverso,P. (2005)
Although several approaches have been developed for planning in nondeterministic domains, solving large planning problems is still quite difficult. In this work, we present a novel algorithm, called YoYo, for planning in nondeterministic domains under the assumption of full observability. This algorithm enables us to combine the power of search-control strategies as in Planning with Hierarchical Task Networks (HTNs) with tech- niques from the Planning via Symbolic Model-Checking (SMC). Our experimental evaluation confirms the po- tentialities of our approach, demonstrating that it com- bines the advantages of these paradigms.

Human action-recognition using mutual invariants - Parameswaran,Vasu; Chellapa, Rama (Computer Vision and Image Understanding, 2005)
Static and temporally varying 3D invariants are proposed for capturing the spatio-temporal dynamics of a general human action to enable its representation in a compact, view-invariant manner. Two variants of the representation are presented and studied: (1) a restricted-3D version, whose theory and implementation are simple and efficient but which can be applied only to a restricted class of human action, and (2) a full-3D version, whose theory and implementation are more complex but which can be applied to any general human action. A detailed analysis of the two representations is presented. We show why a straightforward implementation of the key ideas does not work well in the general case, and present strategies designed to overcome inherent weaknesses in the approach. What results is an approach for human action modeling and recognition that is not only invariant to viewpoint, but is also robust enough to handle different people, different speeds of action (and hence, frame rate) and minor variabilities in a given action, while encoding sufficient distinction among actions. Results on 2D projections of human motion capture and on manually segmented real image sequences demonstrate the effectiveness of the approach.
Keywords: Human action-recognition; Model based invariants; Mutual invariants; View invariance

"I hear the pattern": interactive sonification of geographical data patterns - Zhao,Haixia; Plaisant, Catherine; Shneiderman, Ben (CHI '05 extended abstracts on Human factors in computing systems, 2005)
Interactive sonification (non-speech sound) is a novel strategy to present the geographical distribution patterns of statistical data to vision impaired users. We discuss the design space with dimensions of interaction actions, data representation forms, input devices, navigation structures, and sound feedback encoding. Two interfaces were designed, one using a keyboard and another using a smooth surface touch tablet. A study with three blind users shows that they are able to perceive patterns of 5-category values on both familiar and unknown maps, and learn new map geography, in both interfaces.
Keywords: auditory user interfaces; information seeking; sonification; universal usability; vision impairment

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

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

Improving Accessibility and Usability of Geo-referenced Statistical Data (2003) - Zhao,Haixia; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Several technology breakthroughs are needed to achieve the goals of universal accessibility and usability. These goals are especially challenging in the case of geo-referenced statistical data that many U.S. government agencies supply. We present technical and user-interface design challenges in accommodating users with low-end technology (slow network connection and low-end machine) and users who are blind or vision-impaired. Our solutions are presented and future work is discussed.
Keywords: Technical Report

Information gathering during planning for Web Service composition - Kuter,Ugur; Sirin,Evren; Parsia,Bijan; Nau, Dana S.; Hendler,James (Web Semantics: Science, Services and Agents on the World Wide Web, 2005)
Hierarchical task network (HTN) based planning techniques have been applied to the problem of composing Web Services, especially when described using the OWL-S service ontologies. Many of the existing Web Services are either exclusively information providing or crucially depend on information-providing services. Thus, many interesting service compositions involve collecting information either during execution or during the composition process itself. In this paper, we focus on the latter issue. In particular, we present ENQUIRER , an HTN-planning algorithm designed for planning domains in which the information about the initial state of the world may not be complete, but it is discoverable through plan-time information-gathering queries. We have shown that ENQUIRER is sound and complete, and derived several mathematical relationships among the amount of available information, the likelihood of the planner finding a plan, and the quality of the plan found. We have performed experimental tests that confirmed our theoretical results and that demonstrated how ENQUIRER can be used for Web Service composition.
Keywords: HTN planning; Information gathering; Web Service composition

Information Visualization and the Challenge of Universal Usability - Plaisant, Catherine (Exploring GeovisualizationExploring Geovisualization, 2005)
Information Visualization aims to provide compact graphical presentations and user interfaces for interactively manipulating large numbers of items. We present a simple “data by tasks taxonomy” then discuss the challenges of providing universal usability, with example applications using geo-referenced data. Information Visualization has been shown to be a powerful visual thinking or decision tool but it is becoming important for services to reach and empower every citizen. Technological advances are needed to deal with user diversity (age, language, disabilities, etc.) but also with the variety of technology used (screen size, network speed, etc.) and the gaps in user's knowledge (general knowledge, knowledge of the application domain, of the interface syntax or semantic). We present examples that illustrate how those challenges can be addressed.

Interactive pattern search in time series - Buono,Paolo; Aris,Aleks; Plaisant, Catherine; Khella,Amir; Shneiderman, Ben (Proceedings of SPIE, 2005)
The need for pattern discovery in long time series data led researchers to develop algorithms for similarity search. Most of the literature about time series focuses on algorithms that index time series and bring the data into the main storage, thus providing fast information retrieval on large time series. This paper reviews the state of the art in visualizing time series, and focuses on techniques that enable users to visually and interactively query time series. Then, it presents TimeSearcher 2, a tool that enables users to explore multidimensional data using synchronized tables and graphs with overview+detail, filter the time series data to reduce the scope of the search, select an existing pattern to find similar occurrences, and interactively adjust similarity parameters to narrow the result set. This tool is an extension of previous work, TimeSearcher 1, which uses graphical timeboxes to interactively query time series data.

Interactive Pattern Search in Time Series (2004) - Buono,Paolo; Aris,Aleks; Plaisant, Catherine; Khella,Amir; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
The need for pattern discovery in long time series data led researchers to develop algorithms for similarity search. Most of the literature about time series focuses on algorithms that index time series and bring the data into the main storage, thus providing fast information retrieval on large time series. This paper reviews the state of the art in visualizing time series, and focuses on techniques that enable users to interactively query time series. Then it presents TimeSearcher 2, a tool that enables users to explore multidimensional data using coordinated tables and graphs with overview+detail, filter the time series data to reduce the scope of the search, select an existing pattern to find similar occurrences, and interactively adjust similarity parameters to narrow the result set. This tool is an extension of previous work, TimeSearcher 1, which uses graphical timeboxes to interactively query time series data.
Keywords: Technical Report

Interactive sonification of choropleth maps - Zhao,Haixia; Smith,B. K; Norman,K.; Plaisant, Catherine; Shneiderman, Ben (IEEE Multimedia, 2005)
Auditory information is an important channel for the visually impaired. Effective sonification (the use of non-speech audio to convey information) promotes equal working opportunities for people with vision impairments by helping them explore data collections for problem solving and decision making. Interactive sonification systems can make georeferenced data accessible to people with vision impairments. The authors compare methods for using sound to encode georeferenced data patterns and for navigating maps.
Keywords: audio signal processing; audio user interfaces; Auditory (non-speech) feedback; auditory information; cartography; choropleth maps; data collections; decision making; Evaluation; Feedback; georeferenced data; Guidelines; handicapped aids; Hardware; HUMANS; information resources; interaction style; Interactive sonification; interactive systems; Navigation; nonspeech audio; problem solving; Problem-solving; sound; universal usability; US Government; User interfaces; vision impairments; World Wide Web

InterSon: Interactive Sonification for Geo-referenced Data Exploration for the Vision Impaired - Zhao,H.; Plaisant, Catherine (Tech Report HCIL-2005-13, 2005)
InterSon is an interactive sonification tool that allows vision im-paired users to explore complex geo-referenced statistical data for fact finding, problem solving and decision making. Examples include maps of population density, crime rates or housing prices. The integrated use of sounds and speech allows users to hear the overall distribution of values on maps and to explore the map to get more details. Users can use the standard computer keyboard, or take advantage of special devices such as a touchpad when they are available. Synchronized auditory and visual displays allow the use of residual vision and facilitate collaboration with sighted colleagues.

Introduction to the special review issue - Perlis, Don; Norvig,P. (Artificial Intelligence, 2005)

iSonic: interactive sonification for non-visual data exploration - Zhao,Haixia; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 7th international ACM SIGACCESS conference on Computers and accessibility, 2005)
iSonic is an interactive sonification tool for vision impaired users to explore geo-referenced statistical data, such as population or crime rates by geographical regions. Users use a keyboard or a smooth surface touchpad to interact with coordinated map and table views of the data. The integrated use of musical sounds and speech allows users to grasp the overall data trends and to explore the data to get more details. Scenarios of use are described.
Keywords: auditory user interfaces; information seeking; sonification; universal usability; vision impairment

The Java memory model - Manson,Jeremy; Pugh, William; Adve,Sarita V. (Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2005)
This paper describes the new Java memory model, which has been revised as part of Java 5.0. The model specifies the legal behaviors for a multithreaded program; it defines the semantics of multithreaded Java programs and partially determines legal implementations of Java virtual machines and compilers.The new Java model provides a simple interface for correctly synchronized programs -- it guarantees sequential consistency to data-race-free programs. Its novel contribution is requiring that the behavior of incorrectly synchronized programs be bounded by a well defined notion of causality. The causality requirement is strong enough to respect the safety and security properties of Java and weak enough to allow standard compiler and hardware optimizations. To our knowledge, other models are either too weak because they do not provide for sufficient safety/security, or are too strong because they rely on a strong notion of data and control dependences that precludes some standard compiler transformations.Although the majority of what is currently done in compilers is legal, the new model introduces significant differences, and clearly defines the boundaries of legal transformations. For example, the commonly accepted definition for control dependence is incorrect for Java, and transformations based on it may be invalid.In addition to providing the official memory model for Java, we believe the model described here could prove to be a useful basis for other programming languages that currently lack well-defined models, such as C++ and C#.
Keywords: concurrency; java; memory model; Multithreading

Listening to Maps: User Evaluation of Interactive Sonifications of Geo-Referenced Data - Zhao,Haixia; Smith,Benjamin K; Norman,Kent L; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
In this paper, we summarize the Auditory Information Seeking Principle (AISP) (gist, navigate, filter, and details-ondemand). To improve blind access to geo-referenced statistical data, we developed several interactive sonifications, adhering to the above AISP. Two user studies are presented. In the first user study with nine sighted subjects, a preliminary map design is compared with an enhanced table design. The study shows subjects can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The map-based design was strongly preferred. The study also shows evidence that AISP conforms to people information seeking strategies. Based on the observations from the first user study, a second user study was conducted with forty-eight sighted subjects comparing four map designs. The effects of using sound to encode vertical geographic positions and two map navigation methods were compared. The result is presented and future work is discussed.
Keywords: Technical Report

Listening to Maps: User Evaluation of Interactive Sonifications of Geo-Referenced Data (2004) - Zhao,Haixia; Smith,Benjamin K; Norman,Kent L; Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
In this paper, we summarize the Auditory Information Seeking Principle (AISP) (gist, navigate, filter, and details-ondemand). To improve blind access to geo-referenced statistical data, we developed several interactive sonifications, adhering to the above AISP. Two user studies are presented. In the first user study with nine sighted subjects, a preliminary map design is compared with an enhanced table design. The study shows subjects can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The map-based design was strongly preferred. The study also shows evidence that AISP conforms to people information seeking strategies. Based on the observations from the first user study, a second user study was conducted with forty-eight sighted subjects comparing four map designs. The effects of using sound to encode vertical geographic positions and two map navigation methods were compared. The result is presented and future work is discussed.
Keywords: Technical Report

Logic, self-awareness and self-improvement: The metacognitive loop and the problem of brittleness - Anderson,M. L; Perlis, Don (Journal of Logic and Computation, 2005)

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

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

Merging Network Measurement with Data Transport - Papageorgiou,Pavlos; Hicks, Michael W. (Passive and Active Network MeasurementPassive and Active Network Measurement, 2005)
The tasks of measurement and data transport are often treated independently, but we believe there are benefits to bringing them together. This paper proposes the simple idea of a transport agent to encapsulate useful data within probe packets in place of useless padding.

Metacognition for dropping and reconsidering intentions - Josyula,D. P; Anderson,M. L; Perlis, Don (AAAI Spring Symposium on Metacognition in Computation, 2005)

A methodology for extrinsic evaluation of text summarization: Does ROUGE correlate - Dorr, Bonnie J; Monz,C.; President,S.; Schwartz,R.; Zajic, David (Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, 2005)
This paper demonstrates the usefulness of sum-maries in an extrinsic task of relevance judgment based on a new method for measuring agree- ment, Relevance-Prediction, which compares sub- jects’ judgments on summaries with their own judg- ments on full text documents. We demonstrate that, because this measure is more reliable than previ- ous gold-standard measures, we are able to make stronger statistical statements about the benefits of summarization. We found positive correlations be- tween ROUGE scores and two different summary types, where only weak or negative correlations were found using other agreement measures. How- ever, we show that ROUGE may be sensitive to the choice of summarization style. We discuss the im- portance of these results and the implications for fu- ture summarization evaluations.

Morse-Smale decompositions for modeling terrain knowledge - Čomić,L.; De Floriani, Leila; Papaleo,L. (Spatial Information Theory, 2005)
In this paper, we describe, analyze and compare techniques for extracting spatial knowledge from a terrain model. Specifically, we investigate techniques for extracting a morphological representation from a terrain model based on an approximation of a Morse-Smale complex. A Morse-Smale complex defines a decomposition of a topographic surface into regions with vertices at the critical points and bounded by integral lines which connect passes to pits and peaks. This provides a terrain representation which encompasses the knowledge on the salient characteristics of the terrain. We classify the various techniques for computing a Morse-Smale complexe based on the underlying terrain model, a Regular Square Grid (RSG) or a Triangulated Irregular Network (TIN), and based on the algorithmic approach they apply. Finally, we discuss hierarchical terrain representations based on a Morse-Smale decomposition.

Moving Object Detection and Compression in IR Sequences - Vaswani,Namrata; Agrawal,Amit; Qinfen Zheng; Chellapa, Rama (Computer Vision Beyond the Visible SpectrumComputer Vision Beyond the Visible Spectrum, 2005)
We consider the problem of remote surveillance using infrared (IR) sensors. The aim is to use IR image sequences to detect moving objects (humans or vehicles), and to transmit a few “best-view images” of every new object that is detected. Since the available bandwidth is usually low, if the object chip is big, it needs to be compressed before being transmitted. Due to low computational power of computing devices attached to the sensor, the algorithms should be computationally simple. We present two approaches for object detection — one which specifically solves the more difficult long-range object detection problem, and the other for objects at short range. For objects at short range, we also present techniques for selecting a single best-view object chip and computationally simple techniques for compressing it to very low bit rates due to the channel bandwidth constraint. A fast image chip compression scheme implemented in the wavelet domain by combining a non-iterative zerotree coding method with 2D-DPCM for both low-and high-frequency subbands is presented. Comparisons with some existing schemes are also included. The object detection and compression algorithms have been implemented in C/C++ and their performance has been evaluated using the Hitachi’s SH4 platform with software simulation.

Multi-resolution out-of-core modeling of terrain and geological data - Danovaro,Emanuele; De Floriani, Leila; Puppo,Enrico; Samet, Hanan (Proceedings of the 13th annual ACM international workshop on Geographic information systems, 2005)
Multi-resolution is a useful tool for managing the complexity of huge terrain and geological data sets. Since encoding large data sets may easily exceed main memory capabilities, data structures and algorithms capable of efficiently working in external memory are needed. In our work, we aim at developing an out-of-core multi-resolution model dimension-independent, that can be used for both terrains, represented by Triangulated Irregular Networks(TINs), and 3D data, such as geological data, represented by tetrahedral meshes. We have based our approach on a general multi-resolution model, that we have proposed in our previous work, which supports the extraction of variable-resolution representations. As first step, we have developed, in a prototype simulation system, a large number of clustering techniques for the modifications in a multi-resolution model. Here, we describe such techniques, and analyze and evaluate them experimentally. The result of this investigation has led us to select a specific clustering approach as the basis for an efficient out-of-core data structure.
Keywords: Multi-resolution; out-of-core; terrain models

A parametric visualization software for the assignment problem - Charalampos Papamanthou; Paparrizos, Konstantinos; Samaras, Nikolaos (Yugoslav Journal of Operations Research, 2005)

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

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

Pathogenic Vibrio species in the marine and estuarine environment - Pruzzo,C.; Huq,A.; Rita R Colwell; Donelli,G. (Oceans and health: pathogens in the marine environment, 2005)
The genus Vibrio includes more than 30 species, at least 12 of which are pathogenic to humans and/or have been associated with foodborne diseases (Chakraborty et al., 1997). Among these species, Vibrio cholerae, serogroups O1 and O139, are the most important, since they are associated with epidemic and pandemic diarrhea outbreaks in many parts of the world (Centers for Disease Control and Prevention, 1995; Kaper et al., 1995). However, other species of vibrios capable of causing diarrheal disease in humans have received greater attention in the last decade. These include Vibrio parahaemolyticus, a leading cause of foodborne disease outbreaks in Japan and Korea (Lee et al., 2001), Vibrio vulnificus, Vibrio alginolyticus, Vibrio damsela, Vibrio fluvialis, Vibrio furnissii, Vibrio hollisae, Vibrio metschnikovii, and Vibrio mimicus (Altekruse et al., 2000; Høi et al., 1997). In the USA, Vibrio species have been estimated to be the cause of about 8000 illnesses annually (Mead et al., 1999).

Pattern Recognition in Video - Chellapa, Rama; Veeraraghavan,Ashok; Aggarwal,Gaurav (Pattern Recognition and Machine IntelligencePattern Recognition and Machine Intelligence, 2005)
Images constitute data that live in a very high dimensional space, typically of the order of hundred thousand dimensions. Drawing inferences from correlated data of such high dimensions often becomes intractable. Therefore traditionally several of these problems like face recognition, object recognition, scene understanding etc. have been approached using techniques in pattern recognition. Such methods in conjunction with methods for dimensionality reduction have been highly popular and successful in tackling several image processing tasks. Of late, the advent of cheap, high quality video cameras has generated new interests in extending still image-based recognition methodologies to video sequences. The added temporal dimension in these videos makes problems like face and gait-based human recognition, event detection, activity recognition addressable. Our research has focussed on solving several of these problems through a pattern recognition approach. Of course, in video streams patterns refer to both patterns in the spatial structure of image intensities around interest points and temporal patterns that arise either due to camera motion or object motion. In this paper, we discuss the applications of pattern recognition in video to problems like face and gait-based human recognition, behavior classification, activity recognition and activity based person identification.

Pioneer: verifying code integrity and enforcing untampered code execution on legacy systems - Seshadri, Arvind; Luk, Mark; Elaine Shi; Perrig, Adrian; van Doorn, Leendert; Khosla, Pradeep (ACM SIGOPS Operating Systems Review, 2005)
We propose a primitive, called Pioneer, as a first step towards verifiable code execution on untrusted legacy hosts. Pioneer does not require any hardware support such as secure co-processors or CPU-architecture extensions. We implement Pioneer on an Intel Pentium IV Xeon processor. Pioneer can be used as a basic building block to build security systems. We demonstrate this by building a kernel rootkit detector.
Keywords: dynamic root of trust; rootkit detection; self-check-summing code; software-based code attestation; verifiable code execution

Processing of reverberant speech for time-delay estimation - Yegnanarayana,B.; Prasanna,S. R.M; Duraiswami, Ramani; Zotkin,Dmitry N (IEEE Transactions on Speech and Audio Processing, 2005)
In this paper, we present a method of extracting the time-delay between speech signals collected at two microphone locations. Time-delay estimation from microphone outputs is the first step for many sound localization algorithms, and also for enhancement of speech. For time-delay estimation, speech signals are normally processed using short-time spectral information (either magnitude or phase or both). The spectral features are affected by degradations in speech caused by noise and reverberation. Features corresponding to the excitation source of the speech production mechanism are robust to such degradations. We show that these source features can be extracted reliably from the speech signal. The time-delay estimate can be obtained using the features extracted even from short segments (50-100 ms) of speech from a pair of microphones. The proposed method for time-delay estimation is found to perform better than the generalized cross-correlation (GCC) approach. A method for enhancement of speech is also proposed using the knowledge of the time-delay and the information of the excitation source.
Keywords: Acoustic noise; acoustic signal processing; array signal processing; data mining; Degradation; delay estimation; Feature extraction; Hilbert envelope; localization algorithm; microphone arrays; microphone location; Microphones; Phase estimation; reverberation; short-time spectral information; Signal processing; source features; source information excitation; speech enhancement; Speech processing; speech production mechanism; speech signal; time-delay; time-delay estimation

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)

Representing Unevenly-Spaced Time Series Data for Visualization and Interactive Exploration - Aris,Aleks; Shneiderman, Ben; Plaisant, Catherine; Shmueli,Galit; Jank,Wolfgang (Human-Computer Interaction - INTERACT 2005Human-Computer Interaction - INTERACT 2005, 2005)
Visualizing time series is useful to support discovery of relations and patterns in financial, genomic, medical and other applications. Often, measurements are equally spaced over time. We discuss the challenges of unevenly-spaced time series and present fourrepresentationmethods: sampled events, aggregated sampled events, event index and interleaved event index. We developed these methods while studying eBay auction data with TimeSearcher. We describe the advantages, disadvantages, choices for algorithms and parameters, and compare the different methods for different tasks. Interaction issues such as screen resolution, response time for dynamic queries, and learnability are governed by these decisions.

Representing Unevenly-Spaced Time Series Data for Visualization and Interactive Exploration (2005) - Aris,Aleks; Shneiderman, Ben; Plaisant, Catherine; Shmueli,Galit; Jank,Wolfgang (Institute for Systems Research Technical Reports, 2005)
Visualizing time series data is useful to support discovery of relations and patterns in financial, genomic, medical and other applications. In most time series, measurements are equally spaced over time. This paper discusses the challenges for unevenly-spaced time series data and presents four methods to represent them: sampled events, aggregated sampled events, event index and interleaved event index. We developed these methods while studying eBay auction data with TimeSearcher. We describe the advantages, disadvantages, choices for algorithms and parameters, and compare the different methods. Since each method has its advantages, this paper provides guidance for choosing the right combination of methods, algorithms, and parameters to solve a given problem for unevenly-spaced time series. Interaction issues such as screen resolution, response time for dynamic queries, and meaning of the visual display are governed by these decisions.
Keywords: Technical Report

Robotic apparatus and wireless communication system - Lathan,Corinna E.; Tracey,Michael R.; Vice,Jack M.; Druin, Allison; Plaisant, Catherine (2005)
A robotic apparatus and system adapted to communicate with a wireless sensor. The apparatus may be either physical or virtual in nature and is adapted to communicate physical movements with a wireless sensor. Data received from the sensor and/or robotic apparatus may be reviewed in a real-time mode, or may be saved for review at a later time. In addition, the apparatus may be controlled through an operator that is in local or remote communication with the apparatus. The robotic system may include pre-programmed interactive platforms for enabling communication between a user and the apparatus in a dynamic mode. In addition, the system may allow an operator to program a game/story for use as an interactive platform. Accordingly, the apparatus and system provides a platform for rehabilitative exercise of a patient as well as an entertainment device.

The roots of self-awareness - Anderson,M. L; Perlis, Don (Phenomenology and the Cognitive Sciences, 2005)

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

Serendipitous discovery of Wolbachia genomes in multiple Drosophila species - Salzberg,Steven L.; Hotopp,Julie CD; Delcher,Arthur L.; Pop, Mihai; Smith,Douglas R.; Eisen,Michael B.; Nelson,William C. (Genome Biology, 2005)
The Trace Archive is a repository for the raw, unanalyzed data generated by large-scale genome sequencing projects. The existence of this data offers scientists the possibility of discovering additional genomic sequences beyond those originally sequenced. In particular, if the source DNA for a sequencing project came from a species that was colonized by another organism, then the project may yield substantial amounts of genomic DNA, including near-complete genomes, from the symbiotic or parasitic organism.

Show Me! Guidelines for producing recorded demonstrations - Plaisant, Catherine; Shneiderman, Ben (2005 IEEE Symposium on Visual Languages and Human-Centric Computing, 2005)
Although recorded demonstrations (screen capture animations with narration) have become a popular form of instruction for user interfaces, little work has been done to describe guidelines for their design. Based on our experience in several projects, we offer a starting set of guidelines for the design of visually appealing and cognitively effective recorded demonstrations. Technical guidelines encourage users to keep file sizes small, strive for universal usability, and ensure user control etc. and provide tips to achieve those goals. Content guidelines include: create short demonstrations that focus on tasks, highlight each step with auditory and visual cues, synchronize narration and animation carefully, and create demonstrations with a clear beginning, middle, and end.
Keywords: animation; auditory cues; Computer aided instruction; Computer animation; Computer Graphics; Computer interfaces; computer literacy; content guidelines; documentation; Government; Graphical user interfaces; Guidelines; Laboratories; narration; recorded demonstrations; screen capture animation; technical guidelines; usability; User interfaces; visual appeal; visual cues

Show Me! Guidelines for Producing Recorded Demonstrations (2005) - Plaisant, Catherine; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Although recorded demonstrations (screen capture animations with narration) have become a popular form of instruction for user interfaces, little work has been done to describe guidelines for their design. Based on our experience in several projects, we offer a starting set of guidelines for the design of recorded demonstrations. Technical guidelines encourage users to keep file sizes small, strive for universal usability, and ensure user control etc. and provide tips to achieve those goals. Content guidelines include: create short demonstrations that focus on tasks, highlight each step with auditory and visual cues, synchronize narration and animation carefully, and create demonstrations with a clear beginning, middle, and end.
Keywords: Technical Report

A simulation and data analysis system for large-scale, data-driven oil reservoir simulation studies - Kurc, T.; Catalyurek,U.; Zhang,X.; Saltz, J.; Martino,R.; Wheeler,M.; Peszyńska,M.; Sussman, Alan; Hansen,C.; Sen,M.; others (Concurrency and Computation: Practice and Experience, 2005)

Software repository mining with Marmoset: an automated programming project snapshot and testing system - Spacco,J.; Strecker,J.; Hovemeyer,D.; Pugh, William (ACM SIGSOFT Software Engineering Notes, 2005)

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

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

Tagged Sets: A Secure and Transparent Coordination Medium - Oriol,Manuel; Hicks, Michael W. (Coordination Models and LanguagesCoordination Models and Languages, 2005)
A simple and effective way of coordinating distributed, mobile, and parallel applications is to use a virtual shared memory (VSM), such as a Linda tuple-space. In this paper, we propose a new kind of VSM, called a tagged set . Each element in the VSM is a value with an associated tag, and values are read or removed from the VSM by matching the tag. Tagged sets exhibit three properties useful for VSMs: 1 Ease of use . A tagged value naturally corresponds to the notion that data has certain attributes, expressed by the tag, which can be used for later retrieval. 2 Flexibility . Tags are implemented as propositional logic formulae, and selection as logical implication, so the resulting system is quite powerful. Tagged sets naturally support a variety of applications, such as shared data repositories (e.g., for media or e-mail), message passing, and publish/subscribe algorithms; they are powerful enough to encode existing VSMs, such as Linda spaces. 3 Security . Our notion of tags naturally corresponds to keys, or capabilities: a user may not select data in the set unless she presents a legal key or keys. Normal tags correspond to symmetric keys, and we introduce asymmetric tags that correspond to public and private key pairs. Treating tags as keys permits users to easily specify protection criteria for data at a fine granularity. This paper motivates our approach, sketches its basic theory, and places it in the context of other data management strategies.

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.

Toward a Statistical Knowledge Network (2004) - Marchionini,Gary; Haas,Stephanie; Plaisant, Catherine; Shneiderman, Ben; Hert,Carol (Institute for Systems Research Technical Reports, 2005)
Statistics support planning and decision making and enormous efforts are made to collect data and produce statistics at all levels of governance. An important principle of democratic societies is that government statistics should be accessible to the broadest possible constituencies to empower better plans and decisions in all aspects of life. Given the potential of near-ubiquitous Internet access in homes and workplaces and efforts by government agencies to mount websites, physical access to large volumes of government is close to a fait accompli. What remains a significant challenge is enabling access to the right statistical information at the right time and in the right form.
Keywords: Technical Report

Visualizing missing data: classification and empirical study - Eaton,C.; Plaisant, Catherine; Drizd,T. (Proceedings of INTERACT, 2005)
Most visualization tools fail to provide support for missing data. We identify sources of missing, and categorize data visualization techniques based on the impact missing data have on the display: region dependent, attribute dependent, and neighbor dependent. We then report on a user study with 30 participants that compared three design variants. A between-subject graph interpretation study provides strong evidence for the need of indicating the presence of missing information, and some direction for addressing the problem.

Visualizing Missing Data: Graph Interpretation User Study - Eaton,Cyntrica; Plaisant, Catherine; Drizd,Terence (Human-Computer Interaction - INTERACT 2005, 2005)
Most visualization tools fail to provide support for missing data. In this paper, we identify sources of missing data and describe three levels of impact missing data can have on the visualization: perceivable, invisible or propagating. We then report on a user study with 30 participants that compared three design variants. A between-subject graph interpretation study provides strong evidence for the need of indicating the presence of missing information, and some direction for addressing the problem.

Active logic for more effective human-computer interaction and other commonsense applications - Anderson,M. L; Josyula,D.; Perlis, Don; Purang,K. (Proceedings of the Workshop Empirically Successful First-Order Reasoning, International Joint Conference on Automated Reasoning, 2004)

Adaptive limited-supply online auctions - Hajiaghayi, Mohammad T.; Kleinberg,R.; Parkes,D. C (Proceedings of the 5th ACM Conference on Electronic Commerce, 2004)

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

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.

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.

Bias in Shape Estimation - Hui Ji; Fermüller, Cornelia (Computer Vision - ECCV 2004Computer Vision - ECCV 2004, 2004)
This paper analyses the uncertainty in the estimation of shape from motion and stereo. It is shown that there are computational limitations of a statistical nature that previously have not been recognized. Because there is noise in all the input parameters, we cannot avoid bias. The analysis rests on a new constraint which relates image lines and rotation to shape. Because the human visual system has to cope with bias as well, it makes errors. This explains the underestimation of slant found in computational and psychophysical experiments, and demonstrated here for an illusory display. We discuss properties of the best known estimators with regard to the problem, as well as possible avenues for visual systems to deal with the bias.

The challenge of information visualization evaluation - Plaisant, Catherine (Proceedings of the working conference on Advanced visual interfaces, 2004)
As the field of information visualization matures, the tools and ideas described in our research publications are reaching users. The reports of usability studies and controlled experiments are helpful to understand the potential and limitations of our tools, but we need to consider other evaluation approaches that take into account the long exploratory nature of users tasks, the value of potential discoveries or the benefits of overall awareness. We need better metrics and benchmark repositories to compare tools, and we should also seek reports of successful adoption and demonstrated utility.
Keywords: adoption; Evaluation; return on investment; technology transfer; usability; usefulness; User studies; Visualization

CHARACTERIZATION OF Ath17, A QUANTITATIVE TRAIT LOCUS FOR ATHEROSCLEROSIS SUSCEPTIBILITY BETWEEN C57BL/6J AND 129S1/SvImJ; SINGLE-NUCLEOTIDE POLYMORPHISMS HAVE IMPORTANT IMPLICATIONS ON IDENTIFYING ATHEROSCLEROSIS MODIFIER GENES - Ishimori,Naoki; Walsh,Kenneth; Zheng,Xiangqun; Lu,Fu; Hannenhalli, Sridhar; Nusskern,Deborah; Mural,Richard; Paigen,Beverly (Cardiovascular Pathology, 2004)
Although identifying quantitative trait loci (QTL) for atherosclerosis susceptibility in experimental murine models has helped us better understand the pathophysiology of atherosclerosis, identifying the genes underlying these QTL has been a slow and difficult process. We are currently in the process of identifying the gene that underlies Ath17, an atherosclerosis-susceptibility QTL we discovered in a (C57BL/6J×129S1/SvImJ)F2 intercross. Ath17 maps to a 6 cM interval region on chromosome 10 (D10Mit31, LOD score 6.6) and contains 46 annotated and 133 predicted genes. We searched the Celera Discovery System database for single nucleotide polymorphisms (SNPs) between C57BL/6J (B6) and 129S1/SvImJ in the Ath17 region and found defined blocks of high and low diversity and one polymorphic region of over 4 Mb surrounded by nonpolymorphic regions. Four of the genes, including the annotated Desrt, in the polymorphic region contained mis-sense mutations. The Desrt coding region contained four mis-sense mutations: B6 lysine to 129 glutamic acid at aa382, B6 asparagine to 129 serine at aa388, B6 threonine to 129 alanine at aa836, and B6 glycine to 129 serine at aa964. In addition, intron 5 of Desrt contained a SNP which co-localized with a putative transcription factor binding site. Desrt is a DNA binding protein, widely expressed in adult tissues, and likely plays a role in cell proliferation, differentiation, and development, making Dsert a strong candidate gene for Ath17. The murine SNP database dramatically reduced the percentage of the murine genome we had to search to find viable candidate genes for Ath17.

Comparative Genome Assembly - Pop, Mihai; Phillippy,Adam; Delcher,Arthur L.; Salzberg,Steven L. (Briefings in Bioinformatics, 2004)
One of the most complex and computationally intensive tasks of genome sequence analysis is genome assembly. Even today, few centres have the resources, in both software and hardware, to assemble a genome from the thousands or millions of individual sequences generated in a whole-genome shotgun sequencing project. With the rapid growth in the number of sequenced genomes has come an increase in the number of organisms for which two or more closely related species have been sequenced. This has created the possibility of building a comparative genome assembly algorithm, which can assemble a newly sequenced genome by mapping it onto a reference genome.We describe here a novel algorithm for comparative genome assembly that can accurately assemble a typical bacterial genome in less than four minutes on a standard desktop computer. The software is available as part of the open-source AMOS project.
Keywords: Assembly; comparative genomics; open source; shotgun sequencing

Computational experience with exterior point algorithms for the transportation problem - Charalampos Papamanthou; Paparrizos, Konstantinos; Samaras, Nikolaos (Applied Mathematics and Computation, 2004)
An experimental computational study to compare the classical primal simplex algorithm and the exterior point algorithms for the transportation problem (TP) is presented. Totally, four algorithms are compared on uniformly randomly generated test problems. The results are very encouraging for one of the competitive algorithms. In particular, a dual forest exterior point algorithm is on average up to 4.5 times faster than network simplex algorithm on TPs of size 300 × 300 and for all classes. This result leads into corresponding savings in computational time. From the computational performance we conclude that as the problem size increases, exterior point algorithm get relatively faster.
Keywords: Algorithm evaluation; Experimental computational study; Exterior point simplex algorithms; Network simplex algorithm; Transportation problem

A computational framework for incremental motion - Mount, Dave; Netanyahu,Nathan S.; Piatko,Christine D.; Silverman,Ruth; Wu,Angela Y. (Proceedings of the twentieth annual symposium on Computational geometry, 2004)
We propose a generic computational framework for maintaining a discrete geometric structure defined by a collection of static and mobile objects. We assume that the mobile objects move incrementally, that is, in discrete time steps. We assume that the structure to be maintained is a function of the current locations of the mobile and static objects (independent of their prior motion). Unlike other models for kinetic computation, we place no restrictions on the motion nor on its predictability.In order to handle unrestricted incremental motion, our framework is based on the coordination of two computational entities. The first is the incremental motion algorithm. It is responsible for maintaining the structure and a set of certificates, or conditions, that prove the structure's correctness. The other entity, called the motion processor, is responsible for handling all the low-level aspects of motion, including computing and/or tracking the motion of the mobile objects, answering queries about their current positions and velocities, and validating that the object motions satisfy simple motion estimates, which are generated by the incremental motion algorithm. Computational efficiency is measured in terms of the number of interactions between these two entities.
Keywords: competitive analysis; incremental motion; kinetic data structures

Copilot - a coprocessor-based kernel runtime integrity monitor - Petroni,Jr.; Fraser,Timothy; Molina,Jesus; Arbaugh, William A. (Proceedings of the 13th conference on USENIX Security Symposium - Volume 13, 2004)
Copilot is a coprocessor-based kernel integrity monitor for commodity systems. Copilot is designed to detect malicious modifications to a host's kernel and has correctly detected the presence of 12 real-world rootkits, each within 30 seconds of their installation with less than a 1% penalty to the host's performance. Copilot requires no modifications to the protected host's software and can be expected to operate correctly even when the host kernel is thoroughly compromised - an advantage over traditional monitors designed to run on the host itself.
Keywords: design; management; MONITORS; Security; security and protection

Covering arrays for efficient fault characterization in complex configuration spaces - Yilmaz,C.; Cohen,M. B; Porter, Adam (ACM SIGSOFT Software Engineering Notes, 2004)

Designing secure sensor networks - Elaine Shi; Perrig, A. (Wireless Communications, IEEE, 2004)
Sensor networks are expected to play an essential role in the upcoming age of pervasive computing. Due to their constraints in computation, memory, and power resources, their susceptibility to physical capture, and use of wireless communications, security is a challenge in these networks. The scale of deployments of wireless sensor networks require careful decisions and trade-offs among various security measures. The authors discuss these issues and consider mechanisms to achieve secure communication in these networks.
Keywords: Pervasive computing; secure sensor network design; telecommunication security; Ubiquitous Computing; wireless sensor network; Wireless sensor networks

Designing the user interface: Strategies for Effective Human-Computer Interaction - Plaisant, Catherine; Schneiderman,B. (Pearson Higher Education, 2004)

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)

Domain-independent reason-enhanced controller for task-oriented systems-DIRECTOR - Josyula,D. P; Anderson,M. L; Perlis, Don (PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL IN℡LIGENCE, 2004)

The Drosophila U1-70K Protein Is Required for Viability, but Its Arginine-Rich Domain Is Dispensable - Salz,Helen K.; Mancebo,Ricardo S. Y.; Nagengast,Alexis A.; Speck,Olga; Psotka,Mitchell; Mount, Stephen M. (GeneticsGenetics, 2004)
The conserved spliceosomal U1-70K protein is thought to play a key role in RNA splicing by linking the U1 snRNP particle to regulatory RNA-binding proteins. Although these protein interactions are mediated by repeating units rich in arginines and serines (RS domains) in vitro, tests of this domain's importance in intact multicellular organisms have not been carried out. Here we report a comprehensive genetic analysis of U1-70K function in Drosophila. Consistent with the idea that U1-70K is an essential splicing factor, we find that loss of U1-70K function results in lethality during embryogenesis. Surprisingly, and contrary to the current view of U1-70K function, animals carrying a mutant U1-70K protein lacking the arginine-rich domain, which includes two embedded sets of RS dipeptide repeats, have no discernible mutant phenotype. Through double-mutant studies, however, we show that the U1-70K RS domain deletion no longer supports viability when combined with a viable mutation in another U1 snRNP component. Together our studies demonstrate that while the protein interactions mediated by the U1-70K RS domain are not essential for viability, they nevertheless contribute to an essential U1 snRNP function.

End-to-end packet-scheduling in wireless ad-hoc networks - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, 2004)
Packet-scheduling is a particular challenge in wireless networks due to interference from nearby transmissions. A distance-2 interference model serves as a useful abstraction here, and we study packet routing and scheduling under this model. The main focus of our work is the development of fully-distributed (decentralized) protocols. We present polylogarithmic/constant factor approximation algorithms for various families of disk graphs (which capture the geometric nature of wireless-signal propagation), as well as near-optimal approximation algorithms for general graphs. The packet-scheduling work by L eighton, Maggs and Rao (Combinatorica, 1994) and a basic distributed coloring procedure, originally due to Luby (J. Computer and System Sciences, 1993), underlie many of our algorithms. Experimental work of Finocchi, Panconesi, and Silvestri (SODA 2002) showed that a natural modification of Luby's algorithm leads to improved performance, and a rigorous explanation of this was left as an open question; we prove that the modified algorithm is provably better in the worst-case. Finally, using simulations, we study the impact of the routing strategy and the choice of parameters on the performance of our distributed algorithm for unit disk graphs.

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

Extending the utility of treemaps with flexible hierarchy - Chintalapani,G.; Plaisant, Catherine; Shneiderman, Ben (Eighth International Conference on Information Visualisation, 2004. IV 2004. Proceedings, 2004)
Treemaps are a visualization technique for presenting hierarchical information on two-dimensional displays. Prior implementations limit the visualization to pre-defined static hierarchies. Flexible hierarchy, a new capability of Treemap 4.0, enables users to define various hierarchies through dynamically selecting a series of data attributes so that they can discover patterns, clusters and outliers. This work describes the design and implementation issues of flexible hierarchy. It then reports on a usability study, which led to enhancements to the interface.
Keywords: 2D displays; Computer displays; Computer science; data visualisation; Data visualization; Educational institutions; flexible hierarchy; graphical user interface; Graphical user interfaces; hierarchical information; Nominations and elections; Switches; Tree data structures; Tree graphs; Treemap 4.0; Two dimensional displays; usability; visualization technique

Extrinsic Evaluation of Automatic Metrics for Summarization - Dorr, Bonnie J; Monz,Christof; Oard, Douglas; President,Stacy; Zajic, David; Schwartz,Richard (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This paper describes extrinsic-task evaluation of summarization. We show that it is possible to save time using summaries for relevance assessment without adversely impacting the degree of accuracy that would be possible with full documents. In addition, we demonstrate that the extrinsic task we have selected exhibits a high degree of interannotator agreement, i.e., consistent relevance decisions across subjects. We also conducted a composite experiment that better reflects the actual document selection process and found that using a surrogate improves the processing speed over reading the entire document. Finally, we have found a small yet statistically significant correlation between some of the intrinsic measures and a user's performance in an extrinsic task. The overall conclusion we can draw at this point is that ROUGE-1 does correlate with precision and to a somewhat lesser degree with accuracy, but that it remains to be investigated how stable these correlations are and how differences in ROUGE-1 translate into significant differences in human performance in an extrinsic task.
Keywords: *ABSTRACTS; *ACCURACY; *DATA SUMMARIZATION; *DOCUMENT SUMMARIES; *DOCUMENTS; *READING MACHINES; *SOFTWARE METRICS; *STATISTICAL ANALYSIS; ABSTRACT SELECTION; ANNOTATIONS; Automation; COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER SYSTEMS; CORRELATION TECHNIQUES; DATA PROCESSING; DOCUMENT SUMMARIES; EXTRINSIC TASKS; Information retrieval; INFORMATION SCIENCE; PERFORMANCE(HUMAN); PRECISION; RELEVANCY; ROUGE-1 COMPUTER PROGRAM; STATISTICS AND PROBABILITY; TEST AND EVALUATION

Finding bugs is easy - Hovemeyer, David; Pugh, William (ACM SIGPLAN NoticesSIGPLAN Not., 2004)

Finding concurrency bugs in java - Hovemeyer,D.; Pugh, William (Proceedings of the PODC Workshop on Concurrency and Synchronization in Java Programs, St. John's, Newfoundland, Canada, 2004)

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

Headline evaluation experiment results - Zajic, David; Dorr, Bonnie J; Schwartz,R.; President,S. (University of Maryland, College Park, MD. UMIACS-TR-2004-18, 2004)
This technical report describes an experiment intending to show that different summarizationtechniques have an effect on human performance of an extrinsic task. The task is document selection in the context of information retrieval. We conclude that the task was too difficult and ambiguous for subjects to perform at the level required in order to make statistically significant claims about the relationship between summarization techniques and human performance. An alternate interpretation of the experimental results is described and plans for future experiments are discussed.

Hierarchical Scaffolding With Bambus - Pop, Mihai; Kosack,Daniel S.; Salzberg,Steven L. (Genome Research, 2004)
The output of a genome assembler generally comprises a collection of contiguous DNA sequences (contigs) whose relative placement along the genome is not defined. A procedure called scaffolding is commonly used to order and orient these contigs using paired read information. This ordering of contigs is an essential step when finishing and analyzing the data from a whole-genome shotgun project. Most recent assemblers include a scaffolding module; however, users have little control over the scaffolding algorithm or the information produced. We thus developed a general-purpose scaffolder, called Bambus, which affords users significant flexibility in controlling the scaffolding parameters. Bambus was used recently to scaffold the low-coverage draft dog genome data. Most significantly, Bambus enables the use of linking data other than that inferred from mate-pair information. For example, the sequence of a completed genome can be used to guide the scaffolding of a related organism. We present several applications of Bambus: support for finishing, comparative genomics, analysis of the haplotype structure of genomes, and scaffolding of a mammalian genome at low coverage. Bambus is available as an open-source package from our Web site.

HTN planning for Web Service composition using SHOP2 - Sirin,Evren; Parsia,Bijan; Wu,Dan; Hendler,James; Nau, Dana S. (Web Semantics: Science, Services and Agents on the World Wide Web, 2004)
Automated composition of Web Services can be achieved by using AI planning techniques. Hierarchical Task Network (HTN) planning is especially well-suited for this task. In this paper, we describe how HTN planning system SHOP2 can be used with OWL-S Web Service descriptions. We provide a sound and complete algorithm to translate OWL-S service descriptions to a SHOP2 domain. We prove the correctness of the algorithm by showing the correspondence to the situation calculus semantics of OWL-S. We implemented a system that plans over sets of OWL-S descriptions using SHOP2 and then executes the resulting plans over the Web. The system is also capable of executing information-providing Web Services during the planning process. We discuss the challenges and difficulties of using planning in the information-rich and human-oriented context of Web Services.
Keywords: HTN planning; OWL-S; SHOP2; Web Service composition; Web services

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.

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

Improving the Quality of Performance-intensive Software via Model-integrated Distributed Continuous Quality Assurance - Krishna,A. S; Schmidt,D. C; Porter, Adam; Memon, Atif M.; Sevilla-Ruiz,D. (Proceedings of the 8th International Conference on Software Reuse, 2004)

Information Gathering During Planning for Web Service Composition - Kuter,Ugur; Sirin,Evren; Nau, Dana S.; Parsia,Bijan; Hendler,James (The Semantic Web – ISWC 2004, 2004)
Hierarchical Task-Network (HTN) based planning techniques have been applied to the problem of composing Web Services, especially when described using the OWL − S service ontologies. Many of the existing Web Services are either exclusively information providing or crucially depend on information-providing services. Thus, many interesting service compositions involve collecting information either during execution or during the composition process itself. In this paper, we focus on the latter issue. In particular, we present ENQUIRER , an HTN-planning algorithm designed for planning domains in which the information about the initial state of the world may not be complete, but it is discoverable through plan-time information-gathering queries. We have shown that ENQUIRER is sound and complete, and derived several mathematical relationships among the amount of available information, the likelihood of the planner finding a plan, and the quality of the plan found. We have performed experimental tests that confirmed our theoretical results and that demonstrated how ENQUIRER can be used in Web Service composition.
Keywords: Computer science

Les leçons tirées des deux compétitions de visualisation d'information - Fekete,Jean-Daniel; Plaisant, Catherine (Proceedings of the 16th conference on Association Francophone d'Interaction Homme-Machine, 2004)
Information visualization needs benchmarks to carry on. A benchmark is aimed at comparing information visualization techniques or systems. A benchmark is made of a dataset, a list of tasks mostly based on finding facts about the dataset, and a list of interesting or important findings about the datasets (the nuggets to find). For the second year, we are organizing the InfoVis Contest aimed at collecting results for benchmarks. We describe here the main lessons we learned.
Keywords: benchmark; contest; Evaluation; Information Visualization

An MCMC-Based Particle Filter for Tracking Multiple Interacting Targets - Zia Khan; Balch, Tucker; Dellaert, Frank (Computer Vision - ECCV 2004, 2004)
We describe a Markov chain Monte Carlo based particle filter that effectively deals with interacting targets, i.e., targets that are influenced by the proximity and/or behavior of other targets. Such interactions cause problems for traditional approaches to the data association problem. In response, we developed a joint tracker that includes a more sophisticated motion model to maintain the identity of targets throughout an interaction, drastically reducing tracker failures. The paper presents two main contributions: (1) we show how a Markov random field (MRF) motion prior, built on the fly at each time step, can substantially improve tracking when targets interact, and (2) we show how this can be done efficiently using Markov chain Monte Carlo (MCMC) sampling. We prove that incorporating an MRF to model interactions is equivalent to adding an additional interaction factor to the importance weights in a joint particle filter. Since a joint particle filter suffers from exponential complexity in the number of tracked targets, we replace the traditional importance sampling step in the particle filter with an MCMC sampling step. The resulting filter deals efficiently and effectively with complicated interactions when targets approach each other. We present both qualitative and quantitative results to substantiate the claims made in the paper, including a large scale experiment on a video-sequence of over 10,000 frames in length.
Keywords: Artificial Intelligence (incl. Robotics); Computer Graphics; Image Processing and Computer Vision; pattern recognition

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

Model-Based Approaches-Validating Quality of Service for Reusable Software Via Model-Integrated Distributed Continuous Quality Assurance - Krishna,A. S; Schmidt,D. C; Memon, Atif M.; Porter, Adam; Sevilla,D. (Lecture Notes in Computer Science, 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.

Mpjava: High-performance message passing in java using java. nio - Pugh, William; Spacco,J. (Languages and Compilers for Parallel Computing, 2004)

Multi-cue exemplar-based nonparametric model for gesture recognition - Shet,V. D; Prasad,V. S.N; Elgammal,A.; Yacoob,Yaser; Davis, Larry S. (Indian Conference on Computer Vision, Graphics and Image Processing, 2004)
This paper presents an approach for a multi-cue, view-based recognition of gestures. We describe an exemplar- based technique that combines two different forms of exem- plars - shape exemplars and motion exemplars - in a uni- fied probabilistic framework. Each gesture is represented as a sequence of learned body poses as well as a sequence of learned motion parameters. The shape exemplars are comprised of pose contours, and the motion exemplars are represented as affine motion parameters extracted using a robust estimation approach. The probabilistic framework learns by employing a nonparametric estimation technique to model the exemplar distributions. It imposes temporal constraints between different exemplars through a learned Hidden Markov Model (HMM) for each gesture. We use the proposed multi-cue approach to recognize a set of four- teen gestures and contrast it against a shape only, single- cue based system.

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

A multi-resolution topological representation for non-manifold meshes - De Floriani, Leila; Magillo,Paola; Puppo,Enrico; Sobrero,Davide (Computer-Aided Design, 2004)
We address the problem of representing and processing 3D objects, described through simplicial meshes, which consist of parts of mixed dimensions, and with a non-manifold topology, at different levels of detail. First, we describe a multi-resolution model, that we call a non-manifold multi-tessellation (NMT), and we consider the selective refinement query, which is at the heart of several analysis operations on multi-resolution meshes. Next, we focus on a specific instance of a NMT, generated by simplifying simplicial meshes based on vertex-pair contraction, and we describe a compact data structure for encoding such a model. We also propose a new data structure for two-dimensional simplicial meshes, capable of representing both connectivity and adjacency information with a small memory overhead, which is used to describe the mesh extracted from an NMT through selective refinement. Finally, we present algorithms to efficiently perform updates on such a data structure.
Keywords: Data structures; Multi-resolution; Non-manifold modeling

Multiscale advanced raster map analysis system: definition, design and development - Patil,G. P.; Balbus,J.; Biging,G.; JaJa, Joseph F.; Myers,W. L.; Taillie,C. (Environmental and Ecological Statistics, 2004)
This paper brings together a multidisciplinary initiative to develop advanced statistical and computational techniques for analyzing, assessing, and extracting information from raster maps. This information will provide a rigorous foundation to address a wide range of applications including disease mapping, emerging infectious diseases, landscape ecological assessment, land cover trends and change detection, watershed assessment, and map accuracy assessment. It will develop an advanced map analysis system that integrates these techniques with an advanced visualization toolbox, and use the system to conduct large case studies using rich sets of raster data, primarily from remotely sensed imagery. As a result, it will be possible to study and evaluate raster maps of societal, ecological, and environmental variables to facilitate quantitative characterization and comparative analysis of geospatial trends, patterns, and phenomena. In addition to environmental and ecological studies, these techniques and tools can be used for policy decisions at national, state, and local levels, crisis management, and protection of infrastructure. Geospatial data form the foundation of an information-based society. Remote sensing has been a vastly under-utilized resource involving a multi-million dollar investment at the national levels. Even when utilized, the credibility has been at stake, largely because of lack of tools that can assess, visualize, and communicate accuracy and reliability in timely manner and at desired confidence levels. Consider an imminent 21st century scenario: What message does a multi-categorical map have about the large landscape it represents? And at what scale, and at what level of detail? Does the spatial pattern of the map reveal any societal, ecological, environmental condition of the landscape? And therefore can it be an indicator of change? How do you automate the assessment of the spatial structure and behavior of change to discover critical areas, hot spots, and their corridors? Is the map accurate? How accurate is it? How do you assess the accuracy of the map? How do we evaluate a temporal change map for change detection? What are the implications of the kind and amount of change and accuracy on what matters, whether climate change, carbon emission, water resources, urban sprawl, biodiversity, indicator species, human health, or early warning? And with what confidence? The proposed research initiative is expected to find answers to these questions and a few more that involve multi-categorical raster maps based on remote sensing and other geospatial data. It includes the development of techniques for map modeling and analysis using Markov Random Fields, geospatial statistics, accuracy assessment and change detection, upper echelons of surfaces, advanced computational techniques for geospatial data mining, and advanced visualization techniques.

New year’s resolutions for software quality - Basili, Victor R.; Boehm,B.; Davis,A.; Humphrey,W. S; Leveson,N.; Mead,N. R; Musa,J. D; Parnas,D. L; Pfleeger,S. L; Weyuker,E. (IEEE Software, 2004)
In the spirit of making resolutions for betterment in the New Year, ten distinguished individuals in the software quality field offer their recommendations on how organizations can improve software quality In the spirit of making resolutions for betterment in the New Year, ten distinguished individuals in the software quality field offer their recommendations on how organizations can improve software quality.

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

Polyubiquitin chains: polymeric protein signals - Pickart,Cecile M.; Fushman, David (Current Opinion in Chemical Biology, 2004)
The 76-residue protein ubiquitin exists within eukaryotic cells both as a monomer and in the form of isopeptide-linked polymers called polyubiquitin chains. In two well-described cases, structurally distinct polyubiquitin chains represent functionally distinct intracellular signals. Recently, additional polymeric structures have been detected in vivo and in vitro, and several large families of proteins with polyubiquitin chain-binding activity have been discovered. Although the molecular mechanisms governing specificity in chain synthesis and recognition are still incompletely understood, the scope of signaling by polyubiquitin chains is likely to be broader than originally envisioned.

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

The priority curve algorithm for video summarization - Fayzullin,M.; V.S. Subrahmanian; Albanese, M.; Picariello, A. (Proceedings of the 2nd ACM international workshop on Multimedia databases, 2004)
In this paper, we introduce the concept of a priority curve associated with a video. We then provide an algorithm that can use the priority curve to create a summary (of a desired length) of any video. The summary thus created exhibits nice continuity properties and also avoids repetition. We have implemented the priority curve algorithm (PCA) and compared it with other summarization algorithms in the literature. We show that PCA is faster than existing algorithms and also produces better quality summaries. The quality of summaries was evaluated by a group of 200 students in Naples, Italy, who watched soccer videos. We also briefly describe a soccer video summarization system we have built on using the PCA architecture and various (classical) image processing algorithms.
Keywords: probabilistic; Summarization; system; video

Proactive key distribution using neighbor graphs - Mishra,A.; Min Ho Shin; Petroni,N. L.; Clancy,T. C; Arbaugh, William A. (IEEE Wireless Communications, 2004)
User mobility in wireless data networks is increasing because of technological advances, and the desire for voice and multimedia applications. These applications, however, require that handoffs between base stations (or access points) be fast to maintain the quality of the connections. In this article we introduce a novel data structure, the neighbor graph, that dynamically captures the mobility topology of a wireless network. We show how neighbor graphs can be utilized to obtain a 99 percent reduction in the authentication time of an IEEE 802.11 handoff (full EAP-TLS) by proactively distributing necessary key material one hop ahead of the mobile user. We also present a reactive method for fast authentication that requires only firmware changes to access points and hence can easily be deployed on existing wireless networks.
Keywords: access points; Authentication; authentication time; Base stations; Communication system security; Delay; graph theory; GSM; IEEE 802.11 handoff; Land mobile radio cellular systems; Message authentication; mobile radio; Multiaccess communication; neighbor graph; Network topology; Roaming; telecommunication security; Telephone sets; user mobility; Wi-Fi networks; wireless data networks; Wireless LAN; Wireless networks

Project highlight: toward the statistical knowledge network - Marchionini,Gary; Haas,Stephanie; Shneiderman, Ben; Plaisant, Catherine; Hert,Carol A. (Proceedings of the 2004 annual national conference on Digital government research, 2004)
This project aims to help people find and understand government statistical information. To achieve this goal, we envision a statistical knowledge network that brings stakeholders from government at all levels together with citizens who provide or seek statistical information. The linchpin of this network is a series of human-computer interfaces that facilitate information seeking, understanding, and use. In turn, these interfaces depend on high-quality metadata and intra-agency cooperation. In this briefing, we summarize our accomplishments in the second year of the project.

Project portfolio earned value management using treemaps - Cable,J. H; Ordonez,J. F; Chintalapani,G.; Plaisant, Catherine (Proceedings of the Project Management Institute Research Conference, 2004)
Project portfolio management deals with organizing and managing a set of projects in anorganization. Each organization has its own way of managing the portfolio that meets its business goals. One of the main challenges is to track project performance across the entire portfolio in a timely and effective manner. It allows managers to diagnose performance trends and identify projects in need of attention, giving them the opportunity to take management action in a timely fashion. In this paper, we investigate the use of Earned Value Management (EVM) for tracking project performance across the portfolio, and explore the benefits of an interactive visualization technique called Treemaps to display project performance metrics for the entire portfolio on a single screen.

Security issues in IEEE 802.11 wireless local area networks: a survey - Mishra,A.; Petroni Jr,N. L; Arbaugh, William A.; Fraser,T. (Wireless Communications and Mobile Computing, 2004)

Selective refinement queries for volume visualization of unstructured tetrahedral meshes - Cignoni,P.; De Floriani, Leila; Magillo,P.; Puppo,E.; Scopigno,R. (Visualization and Computer Graphics, IEEE Transactions on, 2004)
We address the problem of the efficient visualization of large irregular volume data sets by exploiting a multiresolution model based on tetrahedral meshes. Multiresolution models, also called Level-Of-Detail (LOD) models, allow encoding the whole data set at a virtually continuous range of different resolutions. We have identified a set of queries for extracting meshes at variable resolution from a multiresolution model, based on field values, domain location, or opacity of the transfer function. Such queries allow trading off between resolution and speed in visualization. We define a new compact data structure for encoding a multiresolution tetrahedral mesh built through edge collapses to support selective refinement efficiently and show that such a structure has a storage cost from 3 to 5.5 times lower than standard data structures used for tetrahedral meshes. The data structures and variable resolution queries have been implemented together with state-of-the art visualization techniques in a system for the interactive visualization of three-dimensional scalar fields defined on tetrahedral meshes. Experimental results show that selective refinement queries can support interactive visualization of large data sets.
Keywords: Automated; Signal Processing; Computer-Assisted; Imaging; Computer-Assisted; User-Computer Interface; data structure; geometric modeling; interactive visualization; large data sets; multiresolution model; selective refinement queries; unstructured tetrahedral meshes; variable resolution queries; volume data visualization; data visualisation; mesh generation; query p; Three-Dimensional; Online Systems; Pattern Recognition

SESSION 2: STREAMING - Banerjee,S.; Lee,S.; Braud,R.; Bhattacharjee, Bobby; Srinivasan, Aravind; Chu,Y.; Zhang,H.; Sinha,R.; Papadopoulos,C.; Boustead,P.; others (Proceedings of the 14th International Workshop on Network and Operating Systems Support for Digital Audio and Video: NOSSDAV 2003: June 16-18, 2004, Cork, Ireland, 2004)

Shotgun Sequence Assembly - Pop, Mihai (Advances in ComputersAdvances in Computers, 2004)
Shotgun sequencing is the most widely used technique for determining the DNA sequence of organisms. It involves breaking up the DNA into many small pieces that can be read by automated sequencing machines, then piecing together the original genome using specialized software programs called assemblers. Due to the large amounts of data being generated and to the complex structure of most organisms' genomes, successful assembly programs rely on sophisticated algorithms based on knowledge from such diverse fields as statistics, graph theory, computer science, and computer engineering. Throughout this chapter we will describe the main computational challenges imposed by the shotgun sequencing method, and survey the most widely used assembly algorithms.

Skoll: distributed continuous quality assurance - Memon, Atif M.; Porter, Adam; Yilmaz,C.; Nagarajan,A.; Schmidt,D.; Natarajan,B. (Software Engineering, 2004. ICSE 2004. Proceedings. 26th International Conference on, 2004)
Quality assurance (QA) tasks, such as testing, profiling, and performance evaluation, have historically been done in-house on developer-generated workloads and regression suites. Since this approach is inadequate for many systems, tools and processes are being developed to improve software quality by increasing user participation in the QA process. A limitation of these approaches is that they focus on isolated mechanisms, not on the coordination and control policies and tools needed to make the global QA process efficient, effective, and scalable. To address these issues, we have initiated the Skoll project, 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 manner to significantly and rapidly improve software quality. This paper provides several contributions to the study of distributed continuous QA. First, it illustrates the structure and functionality of a generic around-the-world, around-the-clock QA process and describes several sophisticated tools that support this process. Second, it describes several QA scenarios built using these tools and process. Finally, it presents a feasibility study applying these scenarios to a 1MLOC+ software package called ACE+TAO. While much work remains to be done, the study suggests that the Skoll process and tools effectively manage and control distributed, continuous QA processes. Using Skoll we rapidly identified problems that had taken the ACE+TAO developers substantially longer to find and several of which had previously not been found. Moreover, automatic analysis of QA task results often provided developers information that quickly led them to the root cause of the problems.
Keywords: 1MLOC+ software package; ACE+TAO; around-the-clock QA process; around-the-world QA process; distributed continuous QA; distributed continuous quality assurance; distributed programming; program verification; Quality assurance; Skoll; software performance evaluation; software profiling; Software quality; Software testing

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

Sonification of geo-referenced data for auditory information seeking: Design principle and pilot study - Zhao,H.; Plaisant, Catherine; Shneiderman, Ben; Duraiswami, Ramani (Proceedings of ICAD, 2004)
We present an Auditory Information Seeking Principle (AISP)(gist, navigate, filter, and details-on-demand) modeled after the visual information seeking mantra [1]. We propose that data sonification designs should conform to this principle. We also present some design challenges imposed by human auditory perception characteristics. To improve blind access to geo- referenced statistical data, we developed two preliminary sonifications adhering to the above AISP, an enhanced table and a spatial choropleth map. Our pilot study shows people can recognize geographic data distribution patterns on a real map with 51 geographic regions, in both designs. The study also shows evidence that AISP conforms to people’s information seeking strategies. Future work is discussed, including the improvement of the choropleth map design.

The sybil attack in sensor networks: analysis & defenses - Newsome, James; Elaine Shi; Song, Dawn; Perrig, Adrian (ACM, 2004)
Security is important for many sensor network applications. A particularly harmful attack against sensor and ad hoc networks is known as the Sybil attack [6], where a node illegitimately claims multiple identities. This paper systematically analyzes the threat posed by the Sybil attack to wireless sensor networks. We demonstrate that the attack can be exceedingly detrimental to many important functions of the sensor network such as routing, resource allocation, misbehavior detection, etc. We establish a classification of different types of the Sybil attack, which enables us to better understand the threats posed by each type, and better design countermeasures against each type. We then propose several novel techniques to defend against the Sybil attack, and analyze their effectiveness quantitatively.
Keywords: Security; sensor networks; sybil attack

Transparent proxies for java futures - Pratikakis,Polyvios; Spacco,Jaime; Hicks, Michael W. (Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2004)
A proxy object is a surrogate or placeholder that controls access to another target object. Proxies can be used to support distributed programming, lazy or parallel evaluation, access control, and other simple forms of behavioral reflection. However, wrapper proxies (like futures or suspensions> for yet-to-be-computed results) can require significant code changes to be used in statically-typed languages, while proxies more generally can inadvertently violate assumptions of transparency, resulting in subtle bugs. To solve these problems, we have designed and implemented a simple framework for proxy programming that employs a static analysis based on qualifier inference, but with additional novelties. Code for using wrapper proxies is automatically introduced via a classfile-to-classfile transformation, and potential violations of transparency are signaled to the programmer. We have formalized our analysis and proven it sound. Our framework has a variety of applications, including support for asynchronous method calls returning futures. Experimental results demonstrate the benefits of our framework: programmers are relieved of managing and/or checking proxy usage, analysis times are reasonably fast, overheads introduced by added dynamic checks are negligible, and performance improvements can be significant. For example, changing two lines in a simple RMI-based peer-to-peer application and then using our framework resulted in a large performance gain.
Keywords: future; java; proxy; Type inference; type qualifier

Ubistatins Inhibit Proteasome-Dependent Degradation by Binding the Ubiquitin Chain - Verma,Rati; Peters,Noel R.; D'Onofrio,Mariapina; Tochtrop,Gregory P.; Sakamoto,Kathleen M.; Varadan,Ranjani; Zhang,Mingsheng; Coffino,Philip; Fushman, David; Deshaies,Raymond J.; King,Randall W. (Science, 2004)
To identify previously unknown small molecules that inhibit cell cycle machinery, we performed a chemical genetic screen in Xenopus extracts. One class of inhibitors, termed ubistatins, blocked cell cycle progression by inhibiting cyclin B proteolysis and inhibited degradation of ubiquitinated Sic1 by purified proteasomes. Ubistatins blocked the binding of ubiquitinated substrates to the proteasome by targeting the ubiquitin-ubiquitin interface of Lys48-linked chains. The same interface is recognized by ubiquitin-chain receptors of the proteasome, indicating that ubistatins act by disrupting a critical protein-protein interaction in the ubiquitin-proteasome system.

Uncalibrated stereo rectification for automatic 3D surveillance - Lim,S.-N.; Mittal,A.; Davis, Larry S.; Paragios,N. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We describe a stereo rectification method suitable for automatic 3D surveillance. We take advantage of the fact that in a typical urban scene, there is ordinarily a small number of dominant planes. Given two views of the scene, we align a dominant plane in one view with the other. Conjugate epipolar lines between the reference view and plane-aligned image become geometrically identical and can be added to the rectified image pair line by line. Selecting conjugate epipolar lines to cover the whole image is simplified since they are geometrically identical. In addition, the polarities of conjugate epipolar lines are automatically preserved by plane alignment, which simplifies stereo matching.
Keywords: 3D; AUTOMATIC; conjugate; epipolar; image; lines; matching; method; processing; rectification; scene; stereo; surveillance; uncalibrated; urban

Using the TIGR Assembler in Shotgun Sequencing Projects - Pop, Mihai; Kosack,Dan (Bacterial Artificial Chromosomes, 2004)
The TIGR Assembler (TA) ( 1 ) is the sequence assembly program used in sequencing projects at The Institute for Genomic Research (TIGR). Development of the TA was based on the experience obtained in more than 20 sequencing projects completed at TIGR ( see http://www.tigr.org ). This extensive experience led to a sequence assembler that produces few misassemblies ( 2 , 3 ) and has been used successfully in whole-genome shotgun sequencing of prokaryotic and eukaryotic organisms, bacterial artificial chromosome-based sequencing of eukaryotic organisms, and expressed sequence tag assembly.

Using Trust in Recommender Systems: An Experimental Analysis - Massa,Paolo; Bhattacharjee, Bobby (Trust ManagementTrust Management, 2004)
Recommender systems (RS) have been used for suggesting items (movies, books, songs, etc.) that users might like. RSs compute a user similarity between users and use it as a weight for the users’ ratings. However they have many weaknesses, such as sparseness, cold start and vulnerability to attacks. We assert that these weaknesses can be alleviated using a Trust-aware system that takes into account the “web of trust” provided by every user. Specifically, we analyze data from the popular Internet web site epinions.com . The dataset consists of 49290 users who expressed reviews (with rating) on items and explicitly specified their web of trust, i.e. users whose reviews they have consistently found to be valuable. We show that any two users have usually few items rated in common. For this reason, the classic RS technique is often ineffective and is not able to compute a user similarity weight for many of the users. Instead exploiting the webs of trust, it is possible to propagate trust and infer an additional weight for other users. We show how this quantity can be computed against a larger number of users.
Keywords: Computer; Science

Validating quality of service for reusable software via model-integrated distributed continuous quality assurance - Krishna,A.; Schmidt,D.; Memon, Atif M.; Porter, Adam; Sevilla,D. (Software Reuse: Methods, Techniques, and Tools, 2004)
Quality assurance (QA) tasks, such as testing, profiling, and performance evaluation, have historically been done in-house on developer-generated workloads and regression suites. Performance-intensive systems software, such as that found in the scientific computing grid and distributed real-time and embedded (DRE) domains, increasingly run on heterogeneous combinations of OS, compiler, and hardware platforms. Such software has stringent quality of service (QoS) requirements and often provides a variety of configuration options to optimize QoS. As a result, QA performed solely in-house is inadequate since it is hard to manage software variability, i.e., ensuring software quality on all supported target platforms across all desired configuration options. This paper describes how the Skoll project is addressing these issues by developing advanced QA processes and tools that leverage the extensive computing resources of user communities in a distributed, continuous manner to improve key software quality attributes.

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

View independent human body pose estimation from a single perspective image - Parameswaran, V.; Chellapa, Rama (Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on, 2004)
Recovering the 3D coordinates of various joints of the human body from an image is a critical first step for several model-based human tracking and optical motion capture systems. Unlike previous approaches that have used a restrictive camera model or assumed a calibrated camera, our work deals with the general case of a perspective uncalibrated camera and is thus well suited for archived video. The input to the system is an image of the human body and correspondences of several body landmarks, while the output is the set of 3D coordinates of the landmarks in a body-centric coordinate system. Using ideas from 3D model based invariants, we set up a polynomial system of equations in the unknown head pitch, yaw and roll angles. If we are able to make the often-valid assumption that the torso twist is small, there are finite numbers of solutions to the head-orientation that can be computed readily. Once the head orientation is computed, the epipolar geometry of the camera is recovered, leading to solutions to the 3D joint positions. Results are presented on synthetic and real images.
Keywords: 3D; analysis; biomechanics; body; body-centric; camera; capture; coordinate; coordinates; detection; epipolar; equation; estimation; geometry; human; image; image; images; model-based; models; MOTION; object; optical; perspective; physiological; polynomial; polynomials; pose; real; single; synthetic; system; systems; torso; tracking; twist; uncalibrated

Visualizations for taxonomic and phylogenetic trees - Parr,C.S.; Lee,B.; Campbell,D.; Bederson, Benjamin B. (Bioinformatics, 2004)

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

Automating DAML-S Web Services Composition Using SHOP2 - Wu,Dan; Parsia,Bijan; Sirin,Evren; Hendler,James; Nau, Dana S. (The Semantic Web - ISWC 2003, 2003)
The DAML-S Process Model is designed to support the application of AI planning techniques to the automated composition of Web services. SHOP2 is an Hierarchical Task Network (HTN) planner well-suited for working with the Process Model. We have proven the correspondence between the semantics of SHOP2 and the situation calculus semantics of the Process Model. We have also implemented a system which soundly and completely plans over sets of DAML-S descriptions using a SHOP2 planner, and then executes the resulting plans over the Web. We discuss the challenges and difficulties of using SHOP2 in the information-rich and human-oriented context of Web services.
Keywords: Computer science

Blind Deconvolution Using a Regularized Structured Total Least Norm Approach - Pruessner,Armin; O'Leary, Dianne P. (SIAM J. on Matrix Analysis and Applications, 2003)

Broadening Access to Large Online Databases by Generalizing Query Previews - Tanin,Egemen; Plaisant, Catherine; Shneiderman, Ben (The Craft of Information VisualizationThe Craft of Information Visualization, 2003)
Companies, government agencies, and other types of organizations are making their large databases available to the world over the Internet. Current database front-ends do not give users information about the distribution of data. This leads many users to waste time and network resources posing queries that have either zero-hit or mega-hit result sets. Query previews form a novel visual approach for browsing large databases. Query previews supply data distribution information about the database that is being searched and give continuous feedback about the size of the result set for the query as it is being formed. On the other hand, query previews use only a few pre-selected attributes of the database. The distribution information is displayed only on these attributes. Unfortunately, many databases are formed of numerous relations and attributes. This paper introduces a generalization of query previews. We allow users to browse all of the relations and attributes of a database using a hierarchical browser. Any of the attributes can be used to display the distribution information, making query previews applicable to many public online databases.

The Challenge of Missing and Uncertain Data - Eaton,Cyntrica; Plaisant, Catherine; Drizd,Terence (Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003)

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.

The CPR model for summarizing video - Fayzullin,M.; V.S. Subrahmanian; Picariello, A.; Sapino,M. L (Proceedings of the 1st ACM international workshop on Multimedia databases, 2003)
Most past work on video summarization has been based on selecting key frames from videos. We propose a model of video summarization based on three important parameters: Priority (of frames), Continuity (of the summary), and non-Repetition (of the summary). In short, a summary must include high priority frames, must be continuous and non-repetitive. An optimal summary is one that maximizes an objective function based on these three parameters. We develop formal definitions of all these concepts and provide algorithms to find optimal summaries. We briefly report on the performance of these algorithms.
Keywords: multimedia; Summarization; video

The dangers of mitigating security design flaws: a wireless case study - Petroni,N. L.; Arbaugh, William A. (IEEE Security & Privacy, 2003)
Mitigating design flaws often provides the only means to protect legacy equipment, particularly in wireless local area networks. A synchronous active attack against the wired equivalent privacy protocol demonstrates how mitigating one flaw or attack can facilitate another.
Keywords: Communication system security; computer security; cryptography; design flaw mitigation; Dictionaries; legacy equipment; privacy; Protection; Protocols; security design flaws; security of data; synchronous active attack; telecommunication security; Telecommunication traffic; wired equivalent privacy protocol; Wireless LAN; wireless local area networks; Wireless networks

Data exploration with paired hierarchical visualizations: initial designs of PairTrees - Kules,Bill; Shneiderman, Ben; Plaisant, Catherine (Proceedings of the 2003 annual national conference on Digital government research, 2003)
Paired hierarchical visualizations (PairTrees) integrate treemaps, node-link diagrams, choropleth maps and other information visualization techniques to support exploration of hierarchical data sets at multiple levels of abstraction. This paper describes several novel applications of PairTrees in the econometric and health statistics domains, as well as some challenges and trade-offs inherent in the technique.

Data structures for 3D Multi-Tessellations: an overview - Danovaro,E.; De Floriani, Leila; Magillo,P.; Puppo,E. (Data Visualization: The State of the ArtData Visualization: The State of the Art, 2003)

Database Discovery with Dynamic Queries - Fredrikson,A.; North,C.; Plaisant, Catherine; Shneiderman, Ben; Tanin,E.; Pkisant,C. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

Decomposing non-manifold objects in arbitrary dimensions - De Floriani, Leila; Mesmoudi,Mostefa M.; Morando,Franco; Puppo,Enrico (Graphical Models, 2003)
We address the problem of building valid representations of non-manifold d-dimensional objects through an approach based on decomposing a non-manifold d-dimensional object into an assembly of more regular components. We first define a standard decomposition of d-dimensional non-manifold objects described by abstract simplicial complexes. This decomposition splits a non-manifold object into components that belong to a well-understood class of objects, that we call initial quasi-manifold. Initial quasi-manifolds cannot be decomposed without cutting them along manifold faces. They form a decidable superset of d-manifolds for d⩾3, and coincide with manifolds for d⩽2. We then present an algorithm that computes the standard decomposition of a general non-manifold complex. This decomposition is unique, and removes all singularities which can be removed without cutting the complex along its manifold faces.

Designing a digital library for young children: An intergenerational partnership - Druin, Allison; Bederson, Benjamin B.; Hourcade,J. P; Sherman,L.; Revelle,G.; Platner,M.; Weng,S. (The craft of information visualization: readings and reflections, 2003)

Deterministic Resource Discovery in Distributed Networks - Kutten,Shay; Peleg,David; Vishkin, Uzi (Theory of Computing Systems, 2003)
The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| łog n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(łog^2n)$ to\pagebreak[4] $O(łog n )$, the message complexity from $O(n łog^2 n)$ to $O(n łog n )$, and the communication complexity from $O(n^2 łog^3 n)$ to $O(|E_0|łog ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.
Keywords: Computer; Science

Distributed continuous quality assurance: The Skoll project - Yilmaz,C.; Porter, Adam; Schmidt,D. C (Workshop on Remote Analysis and Measurement of Software Systems (RAMSS), 2003)

The dog genome: survey sequencing and comparative analysis - Kirkness,E. F; Bafna,V.; Halpern,A. L; Levy,S.; Remington,K.; Rusch,D. B; Delcher,A. L; Pop, Mihai; Wang,W.; Fraser,C. M; others (Science, 2003)

The Dog Genome: Survey Sequencing and Comparative Analysis - Kirkness,Ewen F.; Bafna,Vineet; Halpern,Aaron L.; Levy,Samuel; Remington,Karin; Rusch,Douglas B; Delcher,Arthur L.; Pop, Mihai; Wang,Wei; Fraser,Claire M.; Venter,J. Craig (ScienceScience, 2003)
A survey of the dog genome sequence (6.22 million sequence reads; 1.5× coverage) demonstrates the power of sample sequencing for comparative analysis of mammalian genomes and the generation of species-specific resources. More than 650 million base pairs (>25%) of dog sequence align uniquely to the human genome, including fragments of putative orthologs for 18,473 of 24,567 annotated human genes. Mutation rates, conserved synteny, repeat content, and phylogeny can be compared among human, mouse, and dog. A variety of polymorphic elements are identified that will be valuable for mapping the genetic basis of diseases and traits in the dog.

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)

Effect of treatment on the dynamics of circulating hypodermin C in cattle naturally infested with Hypoderma lineatum (Diptera: Oestridae) - Douglas D Colwell; Panadero-Fontan,Rosario; López-Sandez,Ceferino; Parra-Fernandez,Francisco; Paz-Silva,A; Sánchez-Andrade,Rita; Dı́ez-Baños,Pablo (Veterinary Parasitology, 2003)
An antigen capture ELISA, using a murine monoclonal antibody recognising recombinant hypodermin C (rHyC), was used to evaluate the influence of early treatment with eprinomectin (Eprinex®) or fenthion (Spotton®) on the kinetics of circulating hypodermin C in calves naturally infested with Hypoderma lineatum. No viable larvae were collected from treated animals, whereas a variable number of warbles were found in control animals. Treatment provoked a decrease in circulating HyC levels that was significant 9 days post-treatment (p.t.). Circulating antigen levels in the treated cattle remained detectable for approximately 99 days p.t. In contrast, control animals had no detectable antigen at 64 days p.t., 42 days earlier than in the treated animals. These results suggest that larvae were either gradually killed, resulting in slow release of antigen or they were encapsulated, leading to the slow liberation of antigen. Kinetics of circulating HyC did not differ among the two insecticide treatments. Antibodies persisted, in all groups, throughout the 120-day study. These results suggest that the antigen capture ELISA will be useful as a technique for detecting successful treatment of cattle grub infestations and for the detection of new infestations in previously infested cattle.
Keywords: Capture ELISA; Cattle-arthropoda; Control methods-arthropoda; Eprinomectin; Fenthion; Hypoderma spp.

Face recognition: A literature survey - Zhao, W.; Chellapa, Rama; Phillips,P.J.; Rosenfeld, A. (ACM Comput. Surv., 2003)
As one of the most successful applications of image analysis and understanding, face recognition has recently received significant attention, especially during the past several years. At least two reasons account for this trend: the first is the wide range of commercial and law enforcement applications, and the second is the availability of feasible technologies after 30 years of research. Even though current machine recognition systems have reached a certain level of maturity, their success is limited by the conditions imposed by many real applications. For example, recognition of face images acquired in an outdoor environment with changes in illumination and/or pose remains a largely unsolved problem. In other words, current systems are still far away from the capability of the human perception system.This paper provides an up-to-date critical survey of still- and video-based face recognition research. There are two underlying motivations for us to write this survey paper: the first is to provide an up-to-date review of the existing literature, and the second is to offer some insights into the studies of machine recognition of faces. To provide a comprehensive survey, we not only categorize existing recognition techniques but also present detailed descriptions of representative methods within each category. In addition, relevant topics such as psychophysical studies, system evaluation, and issues of illumination and pose variation are covered.
Keywords: face recognition; person identification

Family Calendar Survey - Hutchinson,Hilary; Bederson, Benjamin B.; Plaisant, Catherine; Druin, Allison (Technical Reports from UMIACS, 2003)
Beginning in late July 2002, we conducted a survey about people's personal andfamily calendaring habits. By the end of September, we had over 400 responses, which are summarized below. The survey was conducted to help inform our work in designing new technologies for families, motivated in part by our work on the interLiving project. InterLiving is a 3 year, European Union-funded project where we work with distributed, multi-generational families as design partners to create new technologies (see http://www.cs.umd.edu/hcil/interliving for details). The survey was administered from a web page (https://www.cs.umd.edu/users/hilary/survey/survey.htm), and participants were solicited via a "chain-mail" email approach. We began by sending a request to fill out a survey to our friends, families, and colleagues. We asked that they forward the request on to their friends, family and colleagues as well. While we realize that this was an imperfect approach, we believed that the respondents would be representative of the users we are initially targeting in our research on family calendaring and coordination - individuals who are already making relatively heavy use of computers at home and/or work. The results seem to validate this assumption. Many of our respondents likely come from the HCI community as the mailing went to our large lab mailing list. We may have some pollution in the data as a result of people in the same household (e.g. husband and wife) both filling out the survey. Despite these issues, the results we got were helpful in eliciting a number of important findings, namely that people rely on multiple calendars, many of which are still paper. (UMIACS-TR-2002-92) (HCIL-TR-2002-21)
Keywords: Technical Report

Footloose: a case for physical eventual consistency and selective conflict resolution - Paluska; Saff; Yeh; Chen (Mobile Computing Systems and Applications, 2003. Proceedings. Fifth IEEE Workshop on, 2003)
Users are increasingly inundated with small devices with communication and storage capabilities. Unfortunately, the user is still responsible for reconciling all of the devices whenever a change is made. We present Footloose, a user-centered data store that can share data and reconcile conflicts across diverse devices. Footloose is an optimistic system based on physical eventual consistency: consistency based on the movement of devices, and selective conflict resolution, which allows conflicts to flow through devices that cannot resolve the conflict to devices that can. Using these techniques, Footloose can present consistent views of data on the devices closest to the user without user interaction.

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.

Guest editors' Introduction to the special section on energy minimization methods in computer vision and pattern recognition - Figueiredo,M.A.T.; Hancock,E.R.; Pelillo,M.; Zerubia, J. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2003)

Helping users get started with visual interfaces: multi-layered interfaces, integrated initial guidance and video demonstrations - Kang,Hyunmo; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 2003 annual national conference on Digital government research, 2003)
We are investigating new ways to help users learn to use public access interactive tools, in particular for the visual exploration of government statistics. Our work led to a series of interfaces using multi-layered design, a new help method called Integrated Initial Guidance, and video demonstrations. Multi-layer designs structure an interface so that a simpler interface is available for users to get started and more complex features are accessed as users move through the more advanced layers. Integrated Initial Guidance provides help within the working interface, right at the start of the application. Using the metaphor of "sticky notes" overlaid on top of the functional interface locates the main widgets, demonstrates their manipulation, and explains the resulting actions using preset activations of the interface.

ICSE workshop on remote analysis and measurement of software systems (RAMSS) - Orso,Alessandro; Porter, Adam (ACM SIGSOFT Software Engineering NotesSIGSOFT Softw. Eng. Notes, 2003)

Immediate Usability: Kiosk design principles from the CHI 2001 Photo Library - Kules,Bill; Kang,Hyunmo; Plaisant, Catherine; Rose,Anne; Shneiderman, Ben (Technical Reports from UMIACS, 2003)
This paper describes a novel set of design principles and guidelines forensuring the immediate usability of public access systems. These principles and guidelines were formulated while developing PhotoFinder Kiosk, a community photo library. Attendees of CHI 2001 successfully used the tool to browse and annotate collections of photographs spanning 20 years of CHI and related conferences, producing a richly annotated photo history of the field of human-computer interaction. We used observations and log data to evaluate the tool and refine the guidelines. They provide specific guidance for practitioners, as well as a useful framework for additional research in public access interfaces. Keywords Photo collection, community photo library, group annotation, public access system, direct annotation, direct manipulation, drag-and-drop, immediate usability, zero-trial learning, walk-up-and-use, casual use. (UMIACS-TR-2001-71) (HCIL-TR-2001-23)
Keywords: Technical Report

Improving Accessibility and Usability of Geo-referenced Statistical Data - Zhao,Haixia; Plaisant, Catherine; Shneiderman, Ben (Technical Reports from UMIACS, 2003)
Several technology breakthroughs are needed to achieve the goals ofuniversal accessibility and usability. These goals are especially challenging in the case of geo-referenced statistical data that many U.S. government agencies supply. We present technical and user-interface design challenges in accommodating users with low-end technology (slow network connection and low-end machine) and users who are blind or vision-impaired. Our solutions are presented and future work is discussed. (UMIACS-TR-2003-37) (HCIL-2003-11)
Keywords: Technical Report

Innovating the Interaction - Bederson, Benjamin B.; Plaisant, Catherine; Mushlin,R.; Snyder,A.; Li,J.; Heller,D.; Shneiderman, Ben; Hochheiser,H.; Fekete,J. D; Czenvinski,M. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

The interaction between zoning regulations and residential preferences as a driver of urban form - Zellner,M.L.; Riolo,R; Rand, William; Page,S.E.; Brown,D.G.; Fernandez,L.E. (Proceedings of the 2003 UTEP Distinguished Faculty and Student Symposium, 2003)

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.

LifeLines: Using Visualization to Enhance Navigation and Analysis of Patient Records - Plaisant, Catherine; Mushlin,Richard; Snyder,Aaron; Li,Jia; Heller,Dan; Shneiderman, Ben (The Craft of Information VisualizationThe Craft of Information Visualization, 2003)

Morphology-driven simplification and multiresolution modeling of terrains - Danovaro,Emanuele; De Floriani, Leila; Magillo,Paola; Mesmoudi,Mohammed Mostefa; Puppo,Enrico (Proceedings of the 11th ACM international symposium on Advances in geographic information systems, 2003)
We propose a technique for simplification and multiresolution modeling of a terrain represented as a TIN. Our goal is to maintain the morphological structure of the terrain in the resulting multiresolution model. To this aim, we extend Morse theory, developed for continuous and differentiable functions, to the case of piecewise linear functions. We decompose a TIN into areas with uniform morphological properties (such as valleys, basins, etc.) separated by a network of critical lines and points. We describe an algorithm to compute the above decomposition and the critical net, and a TIN simplification algorithm that preserves them. On this basis, we build a multiresolution terrain model, which provides a representation of critical features at any level of detail.
Keywords: morphological structure; Multi-resolution; terrain models

Navigation Patterns and Usability of Zoomable User Interfaces With and Without an Overview - Bederson, Benjamin B.; Plaisant, Catherine (The craft of information visualization: readings and reflections, 2003)

Navigation patterns & usability of zoomable user interfaces: with and without an overview - Hornbaek,Kasper; Bederson, Benjamin B.; Plaisant, Catherine (interactions, 2003)
The following abstracts are from recent issues and the forthcoming issue of ACM's Transactions of Computer Human Interaction (ToCHI). They are included here to alert interactions' readers to what research is being done in the field of Computer Human Interaction. The complete papers, when published, can be found in ACM's Digital Library at www.acm.org/pubs/contents/journals/tochi/

New approaches to help users get started with visual interfaces: multi-layered interfaces and integrated initial guidance - Kang,Hyunmo; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 2003 annual national conference on Digital government research, 2003)
We are investigating new ways to help users learn to use public access interactive tools, in particular for the visual exploration of government statistics. Our work led to a series of interfaces using multi-layered design and a new help method called Integrated Initial Guidance. Multi-layer designs structure an interface so that a simpler interface is available for users to get started and more complex features are accessed as users move through the more advanced layers. Integrated Initial Guidance provides help within the working interface, right at the start of the application. Using the metaphor of "sticky notes" overlaid on top of the functional interface locates the main widgets, demonstrates their manipulation, and explains the resulting actions using preset animation of the interface. Usability testing with 12 participants led to refined designs and guidelines for the design of Integrated Initial Guidance interfaces.

On-line computation of two types of structural relations in Japanese - Aoshima,S.; Phillips,C.; Weinberg, Amy (2003)

Overlaying graph links on treemaps - Fekete,J. D; Wang,D.; Dang,N.; Aris,A.; Plaisant, Catherine (IEEE Symposium on Information Visualization Conference Compendium (demonstration), 2003)
Every graph can be decomposed into a tree structure plus a set ofremaining edges. We describe a visualization technique that displays the tree structure as a Treemap and the remaining edges as curved links overlaid on the Treemap. Link curves are designed to show where the link starts and where it ends without requiring an explicit arrow that would clutter the already dense visualization. This technique is effective for visualizing structures where the underlying tree has some meaning, such as Web sites or XML documents with cross-references. Graphic attributes of the links – such as color or thickness – can be used to represent attributes of the edges. Users can choose to see all links at once or only the links to and from the node or branch under the cursor.

The people in digital libraries: Multifaceted approaches to assessing needs and impact - Marchionini,G.; Plaisant, Catherine; Komlodi,A. (Digital library use: Social practice in design and evaluationDigital library use: Social practice in design and evaluation, 2003)

Persistence of adhesive properties in Vibrio cholerae after long‐term exposure to sea water - Pruzzo,Carla; Tarsi,Renato; Del Mar Lleò,Maria; Signoretto,Caterina; Zampini,Massimiliano; Pane,Luigi; Rita R Colwell; Canepari,Pietro (Environmental Microbiology, 2003)
The effect of exposure to artificial sea water (ASW) on the ability of classical Vibrio cholerae O1 cells to interact with chitin-containing substrates and human intestinal cells was studied. Incubation of vibrios in ASW at 5°C and 18°C resulted in two kinds of cell responses: the viable but non-culturable (VBNC) state (i.e. <0.1 colony forming unit ml−1) at 5°C, and starvation (i.e. maintenance of culturability of the population) at 18°C. The latter remained rod shaped and, after 40 days’ incubation, presented a 47–58% reduction in the number of cells attached to chitin, a 48–53% reduction in the number of bacteria adhering to copepods, and a 48–54% reduction in the number of bacteria adhering to human cultured intestinal cells, compared to control cells not suspended in ASW. Bacteria suspended in ASW at 5°C became coccoid and, after 40 days, showed 34–42% fewer cells attached to chitin, 52–55% fewer adhering to copep-ods, and 45–48% fewer cells adhering to intestinal cell monolayers, compared to controls. Sarkosyl-insoluble membrane proteins that bind chitin particles were isolated and analysed by SDS-PAGE. After 40 days incubation in ASW at both 5°C and 18°C vibrios expressed chitin-binding ligands similar to bacteria harvested in the stationary growth phase. It is concluded that as vibrios do not lose adhesive properties after long-term exposure to ASW, it is important to include methods for VBNC bacteria when testing environmental and clinical samples for purposes of public health safety.

Phylogenetic analysis reveals five independent transfers of the chloroplast gene ıt rbcL to the mitochondrial genome in angiosperms - Cummings, Michael P.; Nugent,J. M; Olmstead,R. G; Palmer,J. D (Curr Genet, 2003)
We used the chloroplast gene rbcL as a model to study the frequency and relative timing of transfer of chloroplast sequences to the mitochondrial genome. Southern blot survey of 20 mitochondrial DNAs confirmed three previously reported groups of plants containing rbcL in their mitochondrion, while PCR studies identified a new mitochondrial rbcL. Published and newly determined mitochondrial and chloroplast rbcL sequences were used to reconstruct rbcL phylogeny. The results imply five or six separate interorganellar transfers of rbcL among the angiosperms examined, and hundreds of successful transfers across all flowering plants. By taxonomic criteria, the crucifer transfer is the most ancient, two separate transfers within the grass family are of intermediate ancestry, and the morning-glory transfer is most recent. All five mitochondrial copies of rbcL examined exhibit insertion and/or deletion events that disrupt the reading frame (three are grossly truncated); and all are elevated in the proportion of nonsynonymous substitutions, providing clear evidence that these sequences are pseudogenes.

Predictability of Vibrio Cholerae in Chesapeake Bay - Louis,Valérie R.; Russek-Cohen,Estelle; Choopun,Nipa; Rivera,Irma N. G.; Gangle,Brian; Jiang,Sunny C.; Rubin,Andrea; Patz,Jonathan A.; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2003)
Vibrio cholerae is autochthonous to natural waters and can pose a health risk when it is consumed via untreated water or contaminated shellfish. The correlation between the occurrence of V. cholerae in Chesapeake Bay and environmental factors was investigated over a 3-year period. Water and plankton samples were collected monthly from five shore sampling sites in northern Chesapeake Bay (January 1998 to February 2000) and from research cruise stations on a north-south transect (summers of 1999 and 2000). Enrichment was used to detect culturable V. cholerae, and 21.1% (n = 427) of the samples were positive. As determined by serology tests, the isolates, did not belong to serogroup O1 or O139 associated with cholera epidemics. A direct fluorescent-antibody assay was used to detect V. cholerae O1, and 23.8% (n = 412) of the samples were positive. V. cholerae was more frequently detected during the warmer months and in northern Chesapeake Bay, where the salinity is lower. Statistical models successfully predicted the presence of V. cholerae as a function of water temperature and salinity. Temperatures above 19°C and salinities between 2 and 14 ppt yielded at least a fourfold increase in the number of detectable V. cholerae. The results suggest that salinity variation in Chesapeake Bay or other parameters associated with Susquehanna River inflow contribute to the variability in the occurrence of V. cholerae and that salinity is a useful indicator. Under scenarios of global climate change, increased climate variability, accompanied by higher stream flow rates and warmer temperatures, could favor conditions that increase the occurrence of V. cholerae in Chesapeake Bay.

Preserving Context with Zoomable User Interfaces - Hombsek,K.; Bederson, Benjamin B.; Plaisant, Catherine (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

A representation for abstract simplicial complexes: an analysis and a comparison - De Floriani, Leila; Morando,F.; Puppo,E. (Discrete Geometry for Computer Imagery, 2003)
Abstract simplicial complexes are used in many application contexts to represent multi-dimensional, possibly non-manifold and non-uniformly dimensional, geometric objects. In this paper we introduce a new general yet compact data structure for representing simplicial complexes, which is based on a decomposition approach that we have presented in our previous work [3]. We compare our data structure with the existing ones and we discuss in which respect it performs better than others.

Representation of non-manifold objects - De Floriani, Leila; Morando,Franco; Puppo,Enrico (Proceedings of the eighth ACM symposium on Solid modeling and applications, 2003)
In our previous work [2], we have shown that a non-manifold, mixed-dimensional object described by simplicial complexes can be decomposed in a unique way into regular components, all belonging to a well-understood class. Based on such decomposition, we define here a two-level topological data structure for representing non-manifold objects in any dimension: the first level represents components; while the second level represents the connectivity relation among them. The resulting data structure is compact and scalable, allowing for the efficient treatment of singularities without burdening well-behaved parts of a complex with excessive space overheads.
Keywords: Data structures; Non-manifold modeling; simplicial complexes

RGL study in a hybrid real-time system - Hennacy,K.; Swamy,N.; Perlis, Don (Proceedings of the IASTED NCI, 2003)

Seeing the World Through Image Libraries - North,C.; Shneiderman, Ben; Plaisant, Catherine; Kang,H.; Bederson, Benjamin B. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

The sequence and analysis of Trypanosoma brucei chromosome II - El‐Sayed, Najib M.; Ghedin,E.; Song,J.; MacLeod,A.; Bringaud,F.; Larkin,C.; Wanless,D.; Peterson,J.; Hou,L.; Taylor,S.; others (Nucleic acids research, 2003)

Seven days in the life of a robotic agent - Chong,W.; O'Donovan-Anderson,M.; Okamoto,Y.; Perlis, Don (Innovative Concepts for Agent-Based Systems, 2003)

Statistical validation of spatial patterns in agent-based models - Rand, William; Brown,D.G.; Page,S.E.; Riolo,R; Fernandez,L.E.; Zellner,M (Proceedings of Agent Based Simulation, 2003)
We present and evaluate an agent-based model(ABM) of land use change at the rural-urban fringe. This paper is part of a project that links the ABM to surveys of residential preferences and historical patterns of development. Validation is an important issue for such models and we discuss the use of distributional phenomena as a method of validation. We then highlight the ability of our ABM to gen- erate two phenomena evident in empirical analysis of urban development patterns: a power law rela- tionship between frequency and cluster size and a negative exponential relationship between density and distance from city center. We discuss these results in the light of validation of ABMs.

Technology probes: inspiring design for and with families - Hutchinson,Hilary; Mackay,Wendy; Westerlund,Bo; Bederson, Benjamin B.; Druin, Allison; Plaisant, Catherine; Beaudouin-Lafon,Michel; Conversy,Stéphane; Evans,Helen; Hansen,Heiko; Roussel,Nicolas; Eiderbäck,Björn (Proceedings of the SIGCHI conference on Human factors in computing systems, 2003)
We describe a new method for use in the process of co-designing technologies with users called technology probes. Technology probes are simple, flexible, adaptable technologies with three interdisciplinary goals: the social science goal of understanding the needs and desires of users in a real-world setting, the engineering goal of field-testing the technology, and the design goal of inspiring users and researchers to think about new technologies. We present the results of designing and deploying two technology probes, the messageProbe and the videoProbe, with diverse families in France, Sweden, and the U.S. We conclude with our plans for creating new technologies for and with families based on our experiences.
Keywords: computer mediated communication; ethnography; Home; participatory design and cooperative design

Toward a statistical knowledge network - Marchionini,Gary; Haas,Stephanie; Plaisant, Catherine; Shneiderman, Ben; Hert,Carol (Proceedings of the 2003 annual national conference on Digital government research, 2003)
This paper describes an architecture for a statistical knowledge network that depends on user interfaces as the glue among the components. These interfaces aim to serve non-expert users with diverse needs and statistical and computing experiences. Such interfaces are crucially dependent on different indexing schemes and good metadata.

Towards domain-independent, task-oriented, conversational adequacy - Josyula,D. P; Anderson,M. L; Perlis, Don (INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL IN℡LIGENCE, 2003)

Tracking a moving speaker using excitation source information - Raykar,V.C.; Duraiswami, Ramani; Yegnanarayana,B.; Prasanna,S. R.M (Eighth European Conference on Speech Communication and Technology, 2003)
Microphone arrays are widely used to detect, locate, and track a stationary or moving speaker. The first step is to estimate the time delay, between the speech signals received by a pair of microphones. Conventional methods like generalized cross-correlation are based on the spectral content of the vocal tract system in the speech signal. The spectral content of the speech signal is affected due to degradations in the speech signal caused by noise and reverberation. However, features corresponding to the excitation source of speech are less affected by such degradations. This paper proposes a novel method to estimate the time delays using the excitation source information in speech. The estimated delays are used to get the position of the moving speaker. The proposed method is compared with the spectrum-based approach using real data from a microphone array setup.

On the use of flow migration for handling short-term overloads - Kuo,Kuo-Tung; Phuvoravan,S.; Bhattacharjee, Bobby; Jun La,R.; Shayman,M.; Chang,Hyeong Soo (Global Telecommunications Conference, 2003. GLOBECOM '03. IEEE, 2003)
In this work, we investigate flow migration as a mechanism to sustain QoS to network users during short-term overloads in the context of an MPLS IP network. We experiment with three different control techniques: static long-term optimal mapping of flows to LSPs; on-line locally optimal mapping of flows to LSPs at flow set-up time; and dynamic flow migration in response to transient congestion. These techniques are applicable over different timescales, have different run-time overheads, and require different levels of monitoring and control software inside the network. We present results both from detailed simulations and a complete implementation using software IP routers. We use voice-over-IP as our test application, and show that if end-to-end quality is to be maintained during short unpredictable bursts of high load, then a fast-timescale control such as migration is required.
Keywords: computing; CONGESTION; congestion; CONTROL; control; dynamic; end-to-end; engineering; fast-timescale; flow; Internet; IP; label; long-term; mapping; migration; MPLS; multiprotocol; network; network; networks; of; optimal; overloads; protocol; QoS; QUALITY; quality; routers; routing; service; set-up; short-term; software; software; static; switching; Telecommunication; telephony; time; transient; voice-over-IP

Using Visualization Tools to Gain Insight Into Your Data - Plaisant, Catherine; Chintalapani,G.; Lukehart,C.; Schiro,D.; Ryan,J. (SPE Annual Technical Conference and Exhibition, 2003)
When the term ‘visualization’ is used in the oil and gas industry, it is usually referring to the viewing of complex geologic structures in three-dimensional space. This paper illustrates insights gained by applying interactive visual environments to petroleum industry data that has traditionally been presented in spreadsheets, line graphs, and bar charts. Two information visualization tools, Treemap and SpaceTree, will be shown applied to a variety of oilfield related data.

Visual Information Management for Network Configuration - Kumar,Harsha; Plaisant, Catherine; Teittinen,Marko; Shneiderman, Ben (The Craft of Information VisualizationThe Craft of Information Visualization, 2003)
Current network management systems rely heavily on forms in their user interfaces. The interfaces reflect the intricacies of the network hardware components but provide little support for guiding users through tasks. There is a scarcity of useful graphical visualizations and decision-support tools.

A Visualization of the Primal Simplex Algorithm for the Assignment Problem - Charalampos Papamanthou; Paparrizos, Konstantinos (ITiCSE '03 Proceedings of the 8th Annual Conference on Innovation and Technology in Computer Science Education, 2003)
An educationally-oriented Visualization Software used to assist the teaching of the Primal Simplex Algorithm for the Assignment Problem is presented.
Keywords: Assignment problem; Visualization

Visualizing websites using a hierarchical table of contents browser: WebTOC - Plaisant, Catherine; Marchionini,G.; Komlodi,A. (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

Which comes first, usability or utility? - Grinstein,Georges; Kobsa,Alfred; Plaisant, Catherine; Shneiderman, Ben; Stasko,John T (Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003)

The World's Information in Digital Libraries - Plaisant, Catherine; Marchimini,G.; Bruns,T.; Komlodi,A.; Campbell,L.; Rose,A.; Ding,G.M.; Beale Jr,J.; Nolet,V.; Shneiderman, Ben; others (The craft of information visualization: readings and reflectionsThe craft of information visualization: readings and reflections, 2003)

AAAI 2002 Workshops - Blake,Brian; Haigh,Karen; Hexmoor,Henry; Falcone,Rino; Soh,Leen-Kiat; Baral,Chitta; McIlraith,Sheila; Gmytrasiewicz,Piotr; Parsons,Simon; Malaka,Rainer; Krueger,Antonio; Bouquet,Paolo; et al. (AI Magazine, 2002)

Algorithmic issues in modeling motion - Agarwal,Pankaj K.; Guibas,Leonidas J.; Edelsbrunner,Herbert; Erickson,Jeff; Isard,Michael; Har-Peled,Sariel; Hershberger,John; Jensen,Christian; Kavraki,Lydia; Koehl,Patrice; Lin,Ming; Manocha,Dinesh; et al. (ACM Comput. Surv., 2002)
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory of motion representation that would be useful across several disciplines.
Keywords: computational geometry; Computer vision; mobile networks; modeling; molecular biology; motion modeling; physical simulation; robotoics; spatio-temporal databases

ALLI: An Information Integration System Based on Active Logic Framework - Barfourosh,A. A.; Nezhad,H. R.M; Anderson,M.; Perlis, Don (Proceedings of the Third International Conference on Management Information Systems, Greece, 2002)

Automatic transcription of Czech language oral history in the MALACH project: resources and initial experiments - Oard, Douglas; Demner-Fushman,D.; Hajic,J.; Ramabhadran,B.; Gustman,S.; Byrne,WJ; Soergel,D.; Dorr, Bonnie J; Resnik, Philip; Picheny,M. (Proceedings of the The 5th International Conference on Text, Speech and Dialogue, 2002)

Case study: a message board as a technology probe for family communication and coordination - Hutchinson,H.; Plaisant, Catherine; Druin, Allison (Proceedings of the 2002 Conference on Human Factors in Computing Systems, 2002)
In this paper, we describe the design of an electronic family message board and the initial results of its deployment in three households. The message board was used as a “technology probe” to help understand the communication and coordination needs of a distributed, multigenerational family. Using this information, we are working with the family as design partners to design new technologies.

Combinatorial Algorithms for Design of DNA Arrays - Hannenhalli, Sridhar; Hubbell,Earl; Lipshutz,Robert; Pevzner,Pavel (Chip TechnologyChip Technology, 2002)
Optimal design of DNA arrays requires the development of algorithms with two-fold goals: reducing the effects caused by unintended illumination ( border length minimization problem ) and reducing the complexity of masks ( mask decomposition problem ). We describe algorithms that reduce the number of rectangles in mask decomposition by 20–30% as compared to a standard array design under the assumption that the arrangement of oligonucleotides on the array is fixed. This algorithm produces provably optimal solution for all studied real instances of array design. We also address the difficult problem of finding an arrangement which minimizes the border length and come up with a new idea of threading that significantly reduces the border length as compared to standard designs.

Comparative Genome Sequencing for Discovery of Novel Polymorphisms in Bacillus Anthracis - Read,Timothy D.; Salzberg,Steven L.; Pop, Mihai; Shumway,Martin; Umayam,Lowell; Jiang,Lingxia; Holtzapple,Erik; Busch,Joseph D; Smith,Kimothy L; Schupp,James M; Solomon,Daniel; Keim,Paul; et al. (Science, 2002)
Comparison of the whole-genome sequence ofBacillus anthracis isolated from a victim of a recent bioterrorist anthrax attack with a reference reveals 60 new markers that include single nucleotide polymorphisms (SNPs), inserted or deleted sequences, and tandem repeats. Genome comparison detected four high-quality SNPs between the two sequenced B. anthracischromosomes and seven differences among different preparations of the reference genome. These markers have been tested on a collection of anthrax isolates and were found to divide these samples into distinct families. These results demonstrate that genome-based analysis of microbial pathogens will provide a powerful new tool for investigation of infectious disease outbreaks.

Complete genome sequence and comparative analysis of the metabolically versatile Pseudomonas putida KT2440 - Nelson,K. E; Weinel,C.; Paulsen,IT; Dodson,RJ; Hilbert,H.; Martins dos Santos,VAP; Fouts,DE; Gill,S. R; Pop, Mihai; Holmes,M.; others (Environmental microbiology, 2002)
Pseudomonas putida is a metabolically versatile saprophytic soil bacterium that has been certified as a biosafety host for the cloning of foreign genes. The bacterium also has considerable potential for biotechnological applications. Sequence analysis of the 6.18 Mb genome of strain KT2440 reveals diverse transport and metabolic systems. Although there is a high level of genome conservation with the pathogenic Pseudomonad Pseudomonas aeruginosa (85% of the predicted coding regions are shared), key virulence factors including exotoxin A and type III secretion systems are absent. Analysis of the genome gives insight into the non-pathogenic nature of P. putida and points to potential new applications in agriculture, biocatalysis, bioremediation and bioplastic production.

The complex interaction of agents and environments: An example in urban sprawl - Rand, William; Zellner,M; Page,S.E.; Riolo,R; Brown,D.G.; Fernandez,L.E. (Proceedings of Agent Based Simulation, 2002)
We present and evaluate a foundational agent-based model of land use change at therural-urban fringe within the context of a larger project that will link to surveys of the environmental and community preferences of residents with historical data on patterns of development. In this paper, we focus on the dynamics arising from a model of residential location resulting from preferences for services, density, and aesthetics focusing on the relationship between micro level preferences and policy relevant macro phenomena such as scattered development, largest city size, and the number of residential clusters. We consider two representations of agents’ utility functions – one additively separable and one multiplicative – to see if functional form has any impact on the dynamics of the system, and find that they produce similar results. Our analysis includes both representative agent runs, in which all agents have identical preferences, as well as runs in which the agents have diverse preferences. We find that diversity can increase sprawl through feedbacks associated with the spatial locations of services and agents. In addition, we examine cases in which the agents’ location decisions affect the aesthetic quality of neighboring sites and find that these feedbacks further exacerbate the sprawl effect.

On the Complexity of Plan Adaptation by Derivational Analogy in a Universal Classical Planning Framework - Au,Tsz-Chiu; Muñoz-Avila,Héctor; Nau, Dana S. (Advances in Case-Based Reasoning, 2002)
In this paper we present an algorithm called DerUCP, which can be regarded as a general model for plan adaptation using Derivational Analogy. Using DerUCP, we show that previous results on the complexity of plan adaptation do not apply to Derivational Analogy. We also show that Derivational Analogy can potentially produce exponential reductions in the size of the search space generated by a planning system.
Keywords: Computer science

COTS-based software development: Processes and open issues - Morisio,M; Seaman,C.B; Basili, Victor R.; Parra,A.T; Kraft,S.E; Condon,S.E (Journal of Systems and Software, 2002)
The work described in this paper is an investigation of the COTS-based software development within a particular NASA environment, with an emphasis on the processes used. Fifteen projects using a COTS-based approach were studied and their actual process was documented. This process is evaluated to identify essential differences in comparison to traditional software development. The main differences, and the activities for which projects require more guidance, are requirements definition and COTS selection, high level design, integration and testing. Starting from these empirical observations, a new process and set of guidelines for COTS-based development are developed and briefly presented.
Keywords: Commercial off-the-shelf; Component-based; COTS; empirical study; Software development process

Dependent rounding in bipartite graphs - Gandhi,R.; Khuller, Samir; Parthasarathy,S.; Srinivasan, Aravind (The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings, 2002)
We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan (2001), to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to the following applications: richer random-graph models for graphs with a given degree-sequence; improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.
Keywords: Application software; Approximation algorithms; bipartite graph; bipartite graphs; broadcast channels; broadcast scheduling; Broadcasting; capacitated vertex cover; Character generation; computational complexity; Computer science; Delay; edge-sets; Educational institutions; fair scheduling; fractional vectors; graph theory; per-user fairness properties; pipage rounding technique; Processor scheduling; Random variables; random-graph models; randomized rounding approach; rounding method; scheduling; Scheduling algorithm; telecommunication computing; unrelated parallel machines

Detection of Cytotoxin-Hemolysin mRNA in Nonculturable Populations of Environmental and Clinical Vibrio Vulnificus Strains in Artificial Seawater - Fischer-Le Saux,Marion; Hervio-Heath,Dominique; Loaec,Solen; Rita R Colwell; Pommepuy,Monique (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2002)
The objective of this study was to develop a molecular detection method that better estimates the potential risk associated with the presence of Vibrio vulnificus. For that purpose, we applied seminested reverse transcription-PCR (RT-PCR) to viable but nonculturable (VBNC) populations of V. vulnificus and targeted the cytotoxin-hemolysin virulence gene vvhA. Three strains, two environmental, IF Vv10 and IF Vv18, and one clinical, C7184, were used in this study. Artificial seawater, inoculated with mid-log-phase cells, was maintained at 4°C. VBNC cells resulted after 3, 6, and 14 days for C7184, IF Vv18, and IF Vv10, respectively. Our data indicate that seminested RT-PCR is sensitive for the detection of vvhA mRNA in artificial seawater when exclusively nonculturable bacteria are present. This is the first report of the expression of a toxin gene in VBNC V. vulnificus. Moreover, vvhA transcripts were shown to persist in nonculturable populations over a 4.5-month period, with a progressive decline of the signal over time. This result indicates that special attention should be given to the presence of potentially pathogenic VBNC cells in environmental samples when assessing public health risk.

DUSTer: A Method for Unraveling Cross-Language Divergences for Statistical Word-Level Alignment - Dorr, Bonnie J; Pearl,Lisa; Hwa,Rebecca; Habash,Nizar (Machine Translation: From Research to Real UsersMachine Translation: From Research to Real Users, 2002)
The frequent occurrence of divergenceS —structural differences between languages—presents a great challenge for statistical word-level alignment. In this paper, we introduce DUSTer, a method for systematically identifying common divergence types and transforming an English sentence structure to bear a closer resemblance to that of another language. Our ultimate goal is to enable more accurate alignment and projection of dependency trees in another language without requiring any training on dependency-tree data in that language. We present an empirical analysis comparing the complexities of performing word-level alignments with and without divergence handling. Our results suggest that our approach facilitates word-level alignment, particularly for sentence pairs containing divergences.