The International Children's Digital Library - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

The International Children's Digital Library: Description and analysis of first use - Druin, Allison; Bederson, Benjamin B.; Weeks,A.; Farber,A.; Grosjean,J.; Guha,M.L.; Hourcade,J. P; Lee,J.; Liao,S.; Reuter,K.; others (First Monday, 2003)

The International Children's Digital Library: viewing digital books online - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison; Rose,A.; Farber,A.; Takayama,Y. (Interacting with Computers, 2003)

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)

Making miracles: Interactive translingual search for cebuano and hindi - He,D.; Oard, Douglas; Wang,J.; Luo,J.; Demner-Fushman,D.; Darwish,K.; Resnik, Philip; Khudanpur,S.; Nossal,M.; Subotin,M.; others (ACM Transactions on Asian Language Information Processing (TALIP), 2003)

Method of DNA extraction and application of multiplex polymerase chain reaction to detect toxigenic Vibrio cholerae O1 and O139 from aquatic ecosystems - Rivera,Irma N. G.; Lipp,Erin K.; Gil,Ana; Choopun,Nipa; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2003)
Vibrio cholerae is a free-living bacterium found in water and in association with plankton. V. cholerae non-O1/non-O139 strains are frequently isolated from aquatic ecosystems worldwide. Less frequently isolated are V. cholerae O1 and V. cholerae O139, the aetiological agents of cholera. These strains have two main virulence-associated factors, cholera toxin (CT) and toxin co-regulated pilus (TCP). By extracting total DNA from aquatic samples, the presence of pathogenic strains can be determined quickly and used to improve a microbiological risk assessment for cholera in coastal areas. Some methods suggested for DNA extraction from water samples are not applicable to all water types. We describe here a method for DNA extraction from coastal water and a multiplex polymerase chain reaction (PCR) for O1 and O139 serogroups. DNA extraction was successfully accomplished from 117 sea water samples collected from coastal areas of Perú, Brazil and the USA. DNA concentration in all samples varied from 20 ng to 480 µg µl−1. The sensitivity of the DNA extraction method was 100 V. cholerae cells in 250 ml of water. The specificity of multiplex O1/O139 PCR was investigated by analysing 120 strains of V. cholerae, Vibrio and other Bacteria species. All V. cholerae O1 and O139 tested were positive. For cholera surveillance of aquatic environments and ballast water, total DNA extraction, followed by V. cholerae PCR, and O1/O139 serogroup and tcpA/ctxA genes by multiplex PCR offers an efficient system, permitting risk analysis for cholera in coastal areas.

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/

Performance of a Three-Stage System for Multi-Document Summarization - Dunlavy,Daniel M.; Conroy,John M.; Schlesinger,Judith D.; Goodman,Sarah A.; Okurowski,Mary Ellen; O'Leary, Dianne P.; Halteren,Hans van (DUC 03 Conference ProceedingsDUC 03 Conference Proceedings, 2003)

A perturbation method for evaluating background subtraction algorithms - Chalidabhongse,T.H.; Kim,K.; Harwood,D.; Davis, Larry S. (Joint IEEE International Workshop on Visual Surveillance and Performance Evaluation of Tracking and Surveillance (VS-PETS), 2003)
We introduce a performance evaluation methodology calledPerturbation Detection Rate (PDR) analysis, for measuring performance of background subtraction (BGS) algorithms. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analysis. Specifically, it does not require foreground targets or knowledge of fore- ground distributions. It measures the sensitivity of a BGS algorithm in detecting low contrast targets against back- ground as a function of contrast, also depending on how well the model captures mixed (moving) background events. We compare four algorithms having similarities and differ- ences. Three are in [2, 3, 5] while the fourth is recently de- veloped, called Codebook BGS. The latter algorithm quan- tizes sample background values at each pixel into code- books which represent a compressed form of background model for a long image sequence.

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)

Properties of embedding methods for similarity searching in metric spaces - Hjaltason,G. R; Samet, Hanan (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2003)
Complex data types-such as images, documents, DNA sequences, etc.-are becoming increasingly important in modern database applications. A typical query in many of these applications seeks to find objects that are similar to some target object, where (dis)similarity is defined by some distance function. Often, the cost of evaluating the distance between two objects is very high. Thus, the number of distance evaluations should be kept at a minimum, while (ideally) maintaining the quality of the result. One way to approach this goal is to embed the data objects in a vector space so that the distances of the embedded objects approximates the actual distances. Thus, queries can be performed (for the most part) on the embedded objects. We are especially interested in examining the issue of whether or not the embedding methods will ensure that no relevant objects are left out. Particular attention is paid to the SparseMap, FastMap, and MetricMap embedding methods. SparseMap is a variant of Lipschitz embeddings, while FastMap and MetricMap are inspired by dimension reduction methods for Euclidean spaces. We show that, in general, none of these embedding methods guarantee that queries on the embedded objects have no false dismissals, while also demonstrating the limited cases in which the guarantee does hold. Moreover, we describe a variant of SparseMap that allows queries with no false dismissals. In addition, we show that with FastMap and MetricMap, the distances of the embedded objects can be much greater than the actual distances. This makes it impossible (or at least impractical) to modify FastMap and MetricMap to guarantee no false dismissals.
Keywords: complex; contractiveness; data; databases; decomposition; dimension; distance; distortion; DNA; documents; EMBEDDING; embeddings; Euclidean; evaluations; FastMap; images; Lipschitz; methods; metric; MetricMap; multimedia; processing; query; reduction; search; searching; sequences; similarity; singular; spaces; SparseMap; types; value

PXML: a probabilistic semistructured data model and algebra - Hung,E.; Getoor, Lise; V.S. Subrahmanian (Data Engineering, 2003. Proceedings. 19th International Conference on, 2003)
Despite the recent proliferation of work on semistructured data models, there has been little work to date on supporting uncertainty in these models. We propose a model for probabilistic semistructured data (PSD). The advantage of our approach is that it supports a flexible representation that allows the specification of a wide class of distributions over semistructured instances. We provide two semantics for the model and show that the semantics are probabilistically coherent. Next, we develop an extension of the relational algebra to handle probabilistic semistructured data and describe efficient algorithms for answering queries that use this algebra. Finally, we present experimental results showing the efficiency of our algorithms.
Keywords: algebra; data; databases; instances; model; models; probabilistic; processing; PXML; query; relational; semistructured; structures; tree; XML

Random MAX SAT, random MAX CUT, and their phase transitions - Coppersmith,D.; Gamarnik,D.; Hajiaghayi, Mohammad T.; Sorkin,G. B (Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003)

Rapid porting of DUSTer to Hindi - Dorr, Bonnie J; Ayan,Necip Fazil; Habash,Nizar; Madnani,Nitin; Hwa,Rebecca (ACM Transactions on Asian Language Information Processing (TALIP), 2003)
The frequent occurrence of divergences—structural differences between languages---presents a great challenge for statistical word-level alignment and machine translation. This paper describes the adaptation of DUSTer, a divergence unraveling package, to Hindi during the DARPA TIDES-2003 Surprise Language Exercise. We show that it is possible to port DUSTer to Hindi in under 3 days.
Keywords: Divergences; Machine translation

Reduction of Cholera in Bangladeshi Villages by Simple Filtration - Rita R Colwell; Huq,Anwar; M. Sirajul Islam; K. M. A. Aziz; Yunus,M.; N. Huda Khan; A. Mahmud; Sack,R. Bradley; Nair,G. B.; J. Chakraborty; Sack,David A.; E. Russek-Cohen (Proceedings of the National Academy of SciencesPNAS, 2003)
Based on results of ecological studies demonstrating that Vibrio cholerae, the etiological agent of epidemic cholera, is commensal to zooplankton, notably copepods, a simple filtration procedure was developed whereby zooplankton, most phytoplankton, and particulates >20 μm were removed from water before use. Effective deployment of this filtration procedure, from September 1999 through July 2002 in 65 villages of rural Bangladesh, of which the total population for the entire study comprised ≈133,000 individuals, yielded a 48% reduction in cholera (P < 0.005) compared with the control.

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

Safe and flexible memory management in Cyclone - Hicks, Michael W.; Morrisett,G.; Grossman,D.; Jim,T. (Technical Reports from UMIACS, 2003)
Cyclone is a type-safe programming language intended for applications requiring control over memory management. Our previous work on Cyclone included support for stack allocation, lexical region allocation, and a garbage-collected heap. We achieved safety (i.e., prevented dangling pointers) through a region-based type-and-effects system. This paper describes some new memory-management mechanisms that we have integrated into Cyclone: dynamic regions, unique pointers, and reference-counted objects. Our experience shows that these new mechanisms are well suited for the timely recovery of objects in situations where it is awkward to use lexical regions. Crucially, programmers can write reusable functions without unnecessarily restricting callers' choices among the variety of memory-management options. To achieve this goal, Cyclone employs a combination of polymorphism and scoped constructs that temporarily let us treat objects as if they were allocated in a lexical region.

A scalable data structure for three-dimensional non-manifold objects - De Floriani, Leila; Hui,Annie (Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, 2003)
In this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the design and the implementation of a new data structure, that we call the non-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.

A search engine for 3D models - Funkhouser,Thomas; Min,Patrick; Kazhdan,Michael; Chen,Joyce; Halderman,Alex; Dobkin,David; Jacobs, David W. (ACM Trans. Graph., 2003)
As the number of 3D models available on the Web grows, there is an increasing need for a search engine to help people find them. Unfortunately, traditional text-based search techniques are not always effective for 3D data. In this article, we investigate new shape-based search methods. The key challenges are to develop query methods simple enough for novice users and matching algorithms robust enough to work for arbitrary polygonal models. We present a Web-based search engine system that supports queries based on 3D sketches, 2D sketches, 3D models, and/or text keywords. For the shape-based queries, we have developed a new matching algorithm that uses spherical harmonics to compute discriminating similarity measures without requiring repair of model degeneracies or alignment of orientations. It provides 46 to 245% better performance than related shape-matching methods during precision--recall experiments, and it is fast enough to return query results from a repository of 20,000 models in under a second. The net result is a growing interactive index of 3D models available on the Web (i.e., a Google for 3D models).
Keywords: Search engine; shape matching; shape representation; shape retrieval

A secure PLAN - Hicks, Michael W.; Keromytis,A. D; Smith,J. M (IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2003)
Active networks, being programmable, promise greater flexibility than current networks. Programmability, however, may introduce safety and security risks. This correspondence describes the design and implementation of a security architecture for the active network PLANet. Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN, with an environment of general-purpose service routines governed by trust management. In particular, a technique is used which expands or contracts a packet's service environment based on its level of privilege, termed namespace-based security. The design and implementation of an active-network firewall and virtual private network is used as an application of the security architecture. Measurements of the system show that the addition of the firewall imposes an approximately 34% latency overhead and as little as a 6.7% space overhead to incoming packets.
Keywords: active networks; active-network firewall; Authentication; Authorization; Contracts; cryptography; Environmental management; Extraterrestrial measurements; functionally restricted packet language; general-purpose service routines; Internet; latency overhead; namespace-based security; packet switching; PLANet; Planets; privilege level; programmable networks; Safety; safety risks; secure PLAN; security of data; security risks; trust management; two-level architecture; virtual private network; Virtual private networks; Web and internet services

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)

Special Issue on Visual Analysis of Human Movement - Davis, Larry S.; Horaud,R. (The International Journal of Robotics Research, 2003)

Supporting statistical electronic table usage by citizens - Hert,Carol A.; Liddy,Elizabeth D.; Shneiderman, Ben; Marchionini,Gary (Commun. ACM, 2003)
Over 70 agencies at the federal level are charged with collecting data and producing and disseminating statistics. These statistics are used to inform government policy, shape health care initiatives, provide information on the state of the economy, and others. They also have significant impact on the lives of citizens who use the statistics, for example, to determine job opportunities, changes in social security benefits, and quality of life in particular areas. Our digital government project developed several specific technologies to support the location, manipulation, and understanding of a quintessential format for statistical information---the table.

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

TelegraphCQ: An architectural status report - Krishnamurthy, S.; Chandrasekaran,S.; Cooper,O.; Deshpande, Amol; Franklin,M.J.; Hellerstein,J. M; Hong,W.; Madden,S.; Reiss,F.; Shah,M. A (IEEE Data Engineering Bulletin, 2003)

TelegraphCQ: continuous dataflow processing - Chandrasekaran,Sirish; Cooper,Owen; Deshpande, Amol; Franklin,Michael J.; Hellerstein,Joseph M.; Wei Hong; Krishnamurthy,Sailesh; Madden,Samuel R.; Reiss,Fred; Shah,Mehul A. (Proceedings of the 2003 ACM SIGMOD international conference on Management of data, 2003)

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.

Transcriptional regulation of protein complexes and biological pathways - Hannenhalli, Sridhar; Levy,Samuel (Mammalian Genome, 2003)
The cis-element profile (or cis-profile) of a gene refers to the collection of transcription factor binding sites (TFBS) regulating the transcription of the gene. Underlying the various published studies that attempt to discover cis-elements in the vicinity of co-expressed genes via pattern detection algorithms, there is an implicit assumption that a correlation exists between co-expressed genes and their cis-profiles. In this study, we show that the cis-similarity, defined as the proportion of shared TFBS between two cis-element profiles, is higher for functionally linked interacting proteins as well as for members of a signal transduction pathway. A similar analysis of the enzymes catalyzing the conversion of adjacent substrates to products in a collection of metabolic pathways, did not reveal higher cis-similarity. The analysis is based on three distinct sources of publicly available data, namely, 1) the BIND database of interacting proteins, 2) known interactions in NMDAR protein complex, 3) the apoptosis pathway and nine pathways related to metabolism of cofactors and vitamins all from KEGG. Additionally, we analyze the cis-element profiles of all the genes in the glutamate receptor (GR) sub-complex of NMDAR complex to detect a set of cis-elements that occur adjacent to a majority of the genes. We show that most of the corresponding transcription factors are known to be involved in GR regulation by comparing our findings with the published biomedical literature. In addition, we were able to detect transcripts whose gene products associate with GR by searching for transcripts that share the same regulatory signals as those detected for GR. This suggests a novel computational methodology for constructing high-order gene regulatory models and detecting co-regulated gene products.

Use of the SAND spatial browser for digital government applications - Samet, Hanan; Alborzi,Houman; Brabec,František; Esperança,Claudio; Hjaltason,Gísli R.; Morgan,Frank; Tanin,Egemen (Commun. ACM, 2003)
Numerous federal agencies produce official statistics made accessible to ordinary citizens for searching and data retrieval. This is frequently done via the Internet through a Web browser interface. If this data is presented in textual format, it can often be searched and retrieved by such attributes as topic, responsible agency, keywords, or press release. However, if the data is of spatial nature, for example, in the form of a map, then using text-based queries is often too cumbersome for the intended audience. We describe the use of the SAND Spatial Browser to provide more power to users of these databases by enabling them to define and explore the specific spatial region of interest graphically. The SAND Spatial Browser allows users to form either purely spatial or mixed spatial/nonspatial queries intuitively, which can present information to users that might have been missed if only a textual interface was available.
Keywords: GIS

User-specified adaptive scheduling in a streaming media network - Hicks, Michael W.; Nagarajan,A.; van Renesse,R. (2003 IEEE Conference on Open Architectures and Network Programming, 2003)
In disaster and combat situations, mobile cameras and other sensors transmit real-time data, used by many operators or analysis tools. Unfortunately, in the face of limited, unreliable resources, and varying demands, not all users may be able to get the fidelity they require. This paper describes MediaNet, a distributed stream processing system designed with the above scenarios in mind. Unlike past approaches, MediaNet's users can intuitively specify how the system should adapt based on their individual needs. MediaNet uses both local and online global resource scheduling to improve user performance and network utilization, and adapts without requiring underlying support for resource reservations. Performance experiments show that our scheduling algorithm is reasonably fast, and that user performance and network utilization are both significantly improved.
Keywords: Adaptive scheduling; CAMERAS; Computer networks; Computer science; distributed stream processing system; Educational institutions; global resource scheduling; Intelligent networks; MediaNet; Mobile computing; network utilization; Process design; Processor scheduling; quality of service; Streaming media; streaming media network; user performance; user-specified adaptive scheduling

Using state modules for adaptive query processing - Vijayshankar Raman; Deshpande, Amol; Hellerstein,J. M (19th International Conference on Data Engineering, 2003. Proceedings, 2003)
We present a query architecture in which join operators are decomposed into their constituent data structures (State Modules, or SteMs), and dataflow among these SteMs is managed adaptively by an eddy routing operator [R. Avnur et al., (2000)]. Breaking the encapsulation of joins serves two purposes. First, it allows the eddy to observe multiple physical operations embedded in a join algorithm, allowing for better calibration and control of these operations. Second, the SteM on a relation serves as a shared materialization point, enabling multiple competing access methods to share results, which can be leveraged by multiple competing join algorithms. Our architecture extends prior work significantly, allowing continuously adaptive decisions for most major aspects of traditional query optimization: choice of access methods and join algorithms, ordering of operators, and choice of a query spanning tree. SteMs introduce significant routing flexibility to the eddy, enabling more opportunities for adaptation, but also introducing the possibility of incorrect query results. We present constraints on eddy routing through SteMs that ensure correctness while preserving a great deal of flexibility. We also demonstrate the benefits of our architecture via experiments in the Telegraph dataflow system. We show that even a simple routing policy allows significant flexibility in adaptation, including novel effects like automatic "hybridization " of multiple algorithms for a single join.
Keywords: adaptive query processing; Bandwidth; Calibration; data encapsulation; data structure; Data structures; Databases; Dictionaries; eddy routing; eddy routing operator; Encapsulation; join operator; multiple algorithm automatic hybridization; multiple competing join algorithm; query architecture; Query processing; query spanning tree; Routing; routing policy; Runtime; shared materialization point; State Module; SteMs; Telegraph dataflow system; Telegraphy; Tree data structures

What makes a good answer? The role of context in question answering - Jimmy Lin; Quan,D.; Sinha,V.; Bakshi,K.; Huynh,D.; Katz,B.; Karger,D. R (Human-Computer Interaction, Interact '03, 2003)

WLAN problems and solutions - Housley,R.; Arbaugh, William A. (Communications of the ACM, 2003)

1.375-Approximation Algorithm for Sorting by Reversals - Berman,Piotr; Hannenhalli, Sridhar; Karpinski,Marek (Algorithms — ESA 2002Algorithms — ESA 2002, 2002)
Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals , MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem.

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)

Active Harmony: Towards Automated Performance Tuning - Tapus, C.; I-Hsin Chung; Hollingsworth, Jeffrey K (Supercomputing, ACM/IEEE 2002 Conference, 2002)
In this paper, we present the Active Harmony automated runtime tuning system. We describe the interface used by programs to make applications tunable. We present the Library Specification Layer which helps program library developers expose multiple variations of the same API using different algorithms.The Library Specification Language helps to select the most appropriate program library to tune the overall performance. We also present the optimization algorithm used to adjust parameters in the application and the libraries. Finally, we present results that show how the system is able to tune several real applications. The automated tuning system is able to tune the application parameers to within a few percent of the best value after evaluating only 11 out of over 1,700 possible configurations.
Keywords: Application software; Automatic control; Computational modeling; Computer science; Computerized monitoring; Control systems; grid computing; Runtime library; software libraries; Specification languages

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

Analysis of stage-specific gene expression in the bloodstream and the procyclic form of Trypanosoma brucei using a genomic DNA-microarray - Diehl,Susanne; Diehl,Frank; El‐Sayed, Najib M.; Clayton,Christine; Hoheisel,Jörg D. (Molecular and Biochemical Parasitology, 2002)
A microarray comprising 21[punctuation space]024 different PCR products spotted on glass slides was constructed for gene expression studies on Trypanosoma brucei. The arrayed fragments were generated from a T. brucei shotgun clone library, which had been prepared from randomly sheared and size-fractionated genomic DNA. For the identification of stage-specific gene activity, total RNA from in vitro cultures of the human, long slender form and the insect, procyclic form of the parasite was labelled and hybridised to the microarray. Approximately 75% of the genomic fragments produced a signal and about 2% exhibited significant differences between the transcript levels in the bloodstream and procyclic forms. A few results were confirmed by Northern blot analysis or reverse-transcription and PCR. Three hundred differentially regulated clones have been selected for sequencing. So far, of 33 clones that showed about 2-fold or more over-expression in bloodstream forms, 15 contained sequences similar to those of VSG expression sites and at least six others appeared non-protein-coding. Of 29 procyclic-specific clones, at least eight appeared not to be protein-coding. A surprisingly large proportion of known regulated genes was already identified in this small sample, and some new ones were found, illustrating the utility of genomic arrays.
Keywords: Expression; Gene; Microarray; Regulation; Trypanosoma brucei

An Augmented Visual Query Mechanism for Finding Patterns in Time Series Data - Keogh,Eamonn; Hochheiser,Harry; Shneiderman, Ben (Flexible Query Answering SystemsFlexible Query Answering Systems, 2002)
Relatively few query tools exist for data exploration and pattern identification in time series data sets. In previous work we introduced Timeboxes . Timeboxes are rectangular, direct-manipulation queries for studying time-series datasets. We demonstrated how Timeboxes can be used to support interactive exploration via dynamic queries, along with overviews of query results and drag-and-drop support for query-by-example. In this paper, we extend our work by introducing Variable Time Timeboxes (VTT). VTTs are a natural generalization of Timeboxes, which permit the specification of queries that allow a degree of uncertainty in the time axis. We carefully motivate the need for these more expressive queries, and demonstrate the utility of our approach on several data sets.

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)

Breaking the resource bottleneck for multilingual applications - Hwa,R.; Resnik, Philip; Weinberg, Amy (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.

Characterization of Pseudoalteromonas citrea and P. nigrifaciens Isolated from Different Ecological Habitats Based on REP-PCR Genomic Fingerprints - Ivanova,Elena P.; Matte,Glavur R.; Matte,Maria H.; Coenye,Tom; Huq,Anwarul; Rita R Colwell (Systematic and Applied Microbiology, 2002)
SummaryDNA primers corresponding to conserved repetitive interspersed genomic motifs and PCR were used to show that REP, ERIC and BOX-like DNA sequences are present in marine, oxidative, Gram-negative Pseudoalteromonas strains. REP, ERIC and BOX-PCR were used for rapid molecular characterization of both the type species of the genus and environmental strains isolated from samples collected in different geographical areas. PCR-generated genomic fingerprint patterns were found to be both complex and strain specific. Analysis of the genotypic structure of phenotypically diverse P. citrea revealed a geographic clustering of Far Eastern brown-pigmented, agar-digesting strains of this species. Marine isolates of P. nigrifaciens with 67–70% DNA relatedness generated genomic patterns different from those of the type strain and formed a separate cluster. It is concluded that REP, ERIC and BOX-PCR are effective in generating strain specific patterns that can be used to elucidate geographic distribution, with these genomic patterns providing a valuable biogeographic criterion.
Keywords: biogeography; BOX-PCR; ERIC; Pseudoalteromonas; REP

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.

Cyclone: A safe dialect of C - Jim,T.; Morrisett,G.; Grossman,D.; Hicks, Michael W.; Cheney,J.; Wang, Y. (USENIX Annual Technical Conference, 2002)
Cyclone is a safe dialect of C. It has been designed from the ground up to prevent the buffer overflows, format string attacks, and memory management errors that are common in C programs, while retaining C's syntax and semantics. This paper examines safety violations enabled by C's design, and shows how Cyclone avoids them, without giving up C's hallmark control over low-level details such as data representation and memory management.

Decoupled query optimization for federated database systems - Deshpande, Amol; Hellerstein,J. M (18th International Conference on Data Engineering, 2002. Proceedings, 2002)
We study the problem of query optimization in federated relational database systems. The nature of federated databases explicitly decouples many aspects of the optimization process, often making it imperative for the optimizer to consult underlying data sources while doing cost-based optimization. This not only increases the cost of optimization, but also changes the trade-offs involved in the optimization process significantly. The dominant cost in the decoupled optimization process is the "cost of costing" that traditionally has been considered insignificant. The optimizer can only afford a few rounds of messages to the underlying data sources and hence the optimization techniques in this environment must be geared toward gathering all the required cost information with minimal communication. In this paper, we explore the design space for a query optimizer in this environment and demonstrate the need for decoupling various aspects of the optimization process. We present minimum-communication decoupled variants of various query optimization techniques, and discuss tradeoffs in their performance in this scenario. We have implemented these techniques in the Cohera federated database system and our experimental results, somewhat surprisingly, indicate that a simple two-phase optimization scheme performs fairly well as long as the physical database design is known to the optimizer, though more aggressive algorithms are required otherwise
Keywords: Algorithm design and analysis; Cohera federated database; Computer science; Corporate acquisitions; Cost function; Database systems; decoupled optimization; Design optimization; distributed databases; federated databases; federated relational database systems; Internet; Query optimization; query optimizer; Query processing; Relational databases; Space exploration

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.

A dynamic query interface for finding patterns in time series data - Hochheiser,Harry; Shneiderman, Ben (CHI '02 extended abstracts on Human factors in computing systems, 2002)
Identification of patterns in time series data sets is a task that arises in a wide variety of application domains. This demonstration presents the timebox model of rectangular regions that specify constraints for dynamic queries over time series data sets, and the TimeSearcher application, which uses timeboxes as the basis of an interactive query tool.
Keywords: dynamic queries; Information Visualization; time series

Effects of Global Climate on Infectious Disease: The Cholera Model - Lipp,Erin K.; Huq,Anwar; Rita R Colwell (Clinical Microbiology ReviewsClin. Microbiol. Rev., 2002)
Recently, the role of the environment and climate in disease dynamics has become a subject of increasing interest to microbiologists, clinicians, epidemiologists, and ecologists. Much of the interest has been stimulated by the growing problems of antibiotic resistance among pathogens, emergence and/or reemergence of infectious diseases worldwide, the potential of bioterrorism, and the debate concerning climate change. Cholera, caused by Vibrio cholerae, lends itself to analyses of the role of climate in infectious disease, coupled to population dynamics of pathogenic microorganisms, for several reasons. First, the disease has a historical context linking it to specific seasons and biogeographical zones. In addition, the population dynamics of V. cholerae in the environment are strongly controlled by environmental factors, such as water temperature, salinity, and the presence of copepods, which are, in turn, controlled by larger-scale climate variability. In this review, the association between plankton and V. cholerae that has been documented over the last 20 years is discussed in support of the hypothesis that cholera shares properties of a vector-borne disease. In addition, a model for environmental transmission of cholera to humans in the context of climate variability is presented. The cholera model provides a template for future research on climate-sensitive diseases, allowing definition of critical parameters and offering a means of developing more sophisticated methods for prediction of disease outbreaks.

Efficient instrumentation for code coverage testing - Tikir, M. M; Hollingsworth, Jeffrey K (ACM SIGSOFT Software Engineering Notes, 2002)

Evaluating translational correspondence using annotation projection - Hwa,R.; Resnik, Philip; Weinberg, Amy; Kolak,O. (Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, 2002)

Evaluating translational correspondence using annotation projection - Hwa,Rebecca; Resnik, Philip; Weinberg, Amy; Kolak,Okan (Association for Computational Linguistics, 2002)
Recently, statistical machine translation models have begun to take advantage of higher level linguistic structures such as syntactic dependencies. Underlying these models is an assumption about the directness of translational correspondence between sentences in the two languages; however, the extent to which this assumption is valid and useful is not well understood. In this paper, we present an empirical study that quantifies the degree to which syntactic dependencies are preserved when parses are projected directly from English to Chinese. Our results show that although the direct correspondence assumption is often too restrictive, a small set of principled, elementary linguistic transformations can boost the quality of the projected Chinese parses by 76% relative to the unimproved baseline.

Evolution in Action: Using Active Networking to Evolve Network Support for Mobility - Seong-Kyu,Song; Shannon,Stephen; Hicks, Michael W.; Nettles,Scott (Active NetworksActive Networks, 2002)
A key early objective of Active Networking (AN) was to support on-the-fly network evolution. Although AN has been used relatively extensively to build application-customized protocols and even whole networking systems, demonstrations of evolution have been limited. This paper examines three AN mechanisms and how they enable evolution: active packets and plug-in extensions, well-known to the AN community, and update extensions, which are novel to AN. We devote our presentation to a series of demonstrations of how each type of evolution can be applied to the problem of adding support for mobility to a network. This represents the most large-scale demonstration of AN evolution to date. These demonstrations show what previous AN research has not: that AN technology can, in fact, support very significant changes to the network, even while the network is operational.

Experience in implementing a learning software organization - Schneider,K.; von Hunnius,J.-P.; Basili, Victor R. (Software, IEEE, 2002)
In an effort to improve software development and acquisition processes and explicitly reuse knowledge from previous software projects, DaimlerChrysler created a software experience center (SEC). The authors report on challenges the company faced in creating the SEC
Keywords: ACQUISITION; center; software; centres; project; DaimlerChrysler; explicit; development; experience; improvement; improvement; automobile; industry; computer; knowledge; management; software; organization; previous; process; processes; software; projects; software; reuse; learning; software

Experiences with capsule-based active networking - Hicks, Michael W.; Moore,J. T; Wetherall,D.; Nettles,S. (DARPA Active NEtworks Conference and Exposition, 2002. Proceedings, 2002)
Active networking adds programmability to the elements of the network, most aggressively by using programmable packets, or capsules. ANTS [22, 21] and PLANet [10, 8] are the most mature examples of capsule-based systems, both having been publicly available for several years. This paper presents our experience with these systems and the lessons they hold for the future of capsule-based active networking. The paper focuses on four key issues: flexibility, performance, security, and usability. We consider how ANTS and PLANet address these issues, noting that despite substantial surface differences, both systems identify similar key problems and use closely related solutions. Based on our experience with these systems we conclude that capsule-based systems can achieve useful levels of flexibility, performance, and usability. Many aspects of security can also be adequately addressed, but some important problems related to denial of service remain as open problems
Keywords: active networking; ANTS; application-specific routing; capsule architecture; capsule-based systems; computer crime; Computer network management; Computer networks; Computer science; Contracts; Electronic switching systems; INFORMATION SCIENCE; Internet; internetworking; network management; PLANet; Planets; programmability; programmable packets; Programming; Security; Standards development; telecommunication network routing; usability

Exponential speedup of fixed-parameter algorithms on K 3, 3-minor-free or K 5-minor-free graphs - Demaine,E.; Hajiaghayi, Mohammad T.; Thilikos,D. (Algorithms and Computation, 2002)

Genome sequence and comparative analysis of the model rodent malaria parasite Plasmodium yoelii yoelii - Carlton,Jane M.; Angiuoli,Samuel V; Suh,Bernard B.; Kooij,Taco W.; Pertea,Mihaela; Silva,Joana C.; Ermolaeva,Maria D.; Allen,Jonathan E; Jeremy D Selengut; Koo,Hean L.; Peterson,Jeremy D.; Pop, Mihai; et al. (Nature, 2002)
Species of malaria parasite that infect rodents have long been used as models for malaria disease research. Here we report the whole-genome shotgun sequence of one species, Plasmodium yoelii yoelii, and comparative studies with the genome of the human malaria parasite Plasmodium falciparum clone 3D7. A synteny map of 2,212 P. y. yoelii contiguous DNA sequences (contigs) aligned to 14 P. falciparum chromosomes reveals marked conservation of gene synteny within the body of each chromosome. Of about 5,300 P. falciparum genes, more than 3,300 P. y. yoelii orthologues of predominantly metabolic function were identified. Over 800 copies of a variant antigen gene located in subtelomeric regions were found. This is the first genome sequence of a model eukaryotic parasite, and it provides insight into the use of such systems in the modelling of Plasmodium biology and disease.

Genomic profiles of clinical and environmental isolates of Vibrio cholerae O1 in cholera-endemic areas of Bangladesh - Zo,Y. G.; Rivera,I. N. G.; E. Russek-Cohen; Islam,M. S.; Siddique,A. K.; Yunus,M.; Sack,R. B.; Huq,A.; Rita R Colwell (Proceedings of the National Academy of Sciences, 2002)
Diversity, relatedness, and ecological interactions of toxigenic Vibrio cholerae O1 populations in two distinctive habitats, the human intestine and the aquatic environment, were analyzed. Twenty environmental isolates and 42 clinical isolates were selected for study by matching serotype, geographic location of isolation in Bangladesh, and season of isolation. Genetic profiling was done by enterobacterial repetitive intergenic consensus sequence–PCR, optimized for profiling by using the fully sequenced V. cholerae El Tor N16961 genome. Five significant clonal clusters of haplotypes were found from 57 electrophoretic types. Isolates from different areas or habitats intermingled in two of the five significant clusters. Frequencies of haplotypes differed significantly only between the environmental populations (exact test; P < 0.05). Analysis of molecular variance yielded a population genetic structure reflecting the differentiating effects of geographic area, habitat, and sampling time. Although a parameter confounding the latter differences explained 9% of the total molecular variance in the entire population (P < 0.01), the net effect of habitat and time could not be separated because of the small number of environmental isolates included in the study. Five subpopulations from a single area were determined, and from these we were able to estimate a relative differentiating effect of habitat, which was small compared with the effect of temporal change. In conclusion, the resulting population structure supports the hypothesis that spatial and temporal fluctuations in the composition of toxigenic V. cholerae populations in the aquatic environment can cause shifts in the dynamics of the disease.

Handling Translation Divergences: Combining Statistical and Symbolic Techniques in Generation-Heavy Machine Translation - Habash,Nizar; Dorr, Bonnie J (Machine Translation: From Research to Real UsersMachine Translation: From Research to Real Users, 2002)
This paper describes a novel approach to handling translation divergences in a Generation-Heavy Hybrid Machine Translation (GHMT) system. The translation divergence problem is usually reserved for Transfer and Interlingual MT because it requires a large combination of complex lexical and structural mappings. A major requirement of these approaches is the accessibility of large amounts of explicit symmetric knowledge for both source and target languages. This limitation renders Transfer and Interlingual approaches ineffective in the face of structurally-divergent language pairs with asymmetric resources. GHMT addresses the more common form of this problem, source-poor/targetrich, by fully exploiting symbolic and statistical target-language resources. This non-interlingual non-transfer approach is accomplished by using target-language lexical semantics, categorial variations and subcategorization frames to overgenerate multiple lexico-structural variations from a target-glossed syntactic dependency of the source-language sentence. The symbolic overgeneration, which accounts for different possible translation divergences, is constrained by a statistical target-language model.

Identification of non-autonomous non-LTR retrotransposons in the genome of Trypanosoma cruzi - Bringaud,Frédéric; García-Pérez,José Luis; Heras,Sara R.; Ghedin,Elodie; El‐Sayed, Najib M.; Andersson,Björn; Baltz,Théo; Lopez,Manuel C. (Molecular and Biochemical Parasitology, 2002)
As observed for most eukaryotic cells, trypanosomatids contains non-LTR retrotransposons randomly inserted in the nuclear genome. Autonomous retroelements which, code for their own transposition, have been characterized in Trypanosoma brucei (ingi) and Trypanosoma cruzi (L1Tc), whereas non-autonomous retroelements have only been characterized in T. brucei (RIME). Here, we have characterized in the genome of Trypanosoma cruzi four complete copies of a non-autonomous non-LTR retrotransposon, called NARTc. This 0.26 kb NARTc element has the characteristics of non-LTR retrotransposons: the presence a poly(dA) tail and of a short flanking duplicated motif. Analysis of the Genome Survey Sequence databases indicated that the Trypanosoma cruzi haploid genome contains about 140 NARTc copies and about twice as many L1Tc copies. Interestingly, the NARTc and L1Tc retroelements share, with the Trypanosoma brucei ingi and RIME retrotransposons, a common sequence (the first 45 bp with 91% identity), whereas the remaining sequences are very divergent. This suggests that these four trypanosome non-LTR retrotransposons were derived from the same common ancester and the sequence of their 5'-extremity may have a functional role. In addition, the genome of Leishmania major contains the same conserved motif present in the trypanosome retroelements, whicle no transposable elements have been detected so far in Leishmania sp.
Keywords: Ingi; L1Tc; Non-LTR retrotransposon; RIME; Trypanosoma brucei; Trypanosoma cruzi

Identification of transcription factor binding sites in the human genome sequence - Levy,Samuel; Hannenhalli, Sridhar (Mammalian Genome, 2002)
The identification of transcription factor binding sites (TFBS) is an important initial step in determining the DNA signals that regulate transcription of the genome. We tested the performance of three distinct computational methods for the identification of TFBS applied to the human genome sequence, as judged by their ability to recover the location of experimentally determined, and uniquely mapped, TFBS taken from the TRANSFAC database. These identification methods all attempt to filter the quantity of TFBS identified by aligning positional weight matrices that describe the binding site and employ either (i) a P-value threshold for accepting a site, (ii) an over-representation measure of neighboring sites, or (iii) conservation with the mouse genome and application of P-value thresholds. The results show that the best recognition of TFBS is achieved by combining the identification of TFBS in regions of human–mouse conservation and also by applying a high stringency P-value to the TFBS identified in non-coding regions that are not conserved. Additionally, we find that only half of the 481 experimentally mapped sites can be found in sequence regions conserved with mouse, but the predictive power of the binding site identification method is up to threefold higher in the conserved regions.

Improved Approximation Algorithms for the Partial Vertex Cover Problem - Halperin,Eran; Srinivasan, Aravind (Approximation Algorithms for Combinatorial OptimizationApproximation Algorithms for Combinatorial Optimization, 2002)
The partial vertex cover problem is a generalization of the vertex cover problem:given an undirected graph G = ( V,E ) and an integer k , we wish to choose a minimum number of vertices such that at least k edges are covered. Just as for vertex cover, 2-approximation algorithms are known for this problem, and it is of interest to see if we can do better than this.The current-best approximation ratio for partial vertex cover, when parameterized by the maximum degree d of G , is (2 − Θ (1/ d )).We improve on this by presenting a $$ łeft( 2 - Θ łeft( \tfracłn łn d łn d \right) \right) $$ -approximation algorithm for partial vertex cover using semidefinite programming, matching the current-best bound for vertex cover. Our algorithmuses a new rounding technique, which involves a delicate probabilistic analysis.

Improved Word-Level Alignment: Injecting Knowledge about MT Divergences - Dorr, Bonnie J; Pearl,Lisa; Hwa,Rebecca; Habash,Nizar (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
Word-level alignments of bilingual text (bitexts) are not an integral part of statistical machine translation models, but also useful for lexical acquisition, treebank construction. and part-of-speech tagging. The frequent occurrence of divergences, structural differences between languages, presents a great challenge to the alignment task. We resolve some of the most prevalent divergence cases by using syntactic parse information to transform the sentence structure of one language to bear a closer resemblance to that of the other language. In this paper, we show that common divergence types can be found in multiple language pairs (in particular, we focus on English-Spanish and English-Arabic) and systematically identified. We describe our techniques for modifying English parse trees to form resulting sentences that share more similarity with the sentences in the other languages; finally, we present an empirical analysis comparing the complexities of performing word-level alignments with an without divergence handling. Our results suggest that divergence-handling can improve word-level alignment.
Keywords: *LEXICOGRAPHY; *MACHINE TRANSLATION; *STATISTICAL ANALYSIS; *WORDS(LANGUAGE); ACQUISITION; ALIGNMENT; EXPERIMENTAL DATA; LANGUAGE; linguistics; MATHEMATICAL MODELS; STATISTICS AND PROBABILITY; TREES

In Web we trust: establishing strategic trust among online customers - Ceaparu,I.; Demner,D.; Hung,E.; Zhao,H.; Shneiderman, Ben (E-Service: new directions in theory and practice, 2002)
Electronic commerce (e-commerce) provides an important chance for established large companies to gain more customers as well as for new small companies to have a good start and rapid growth. However, establishing trust between customers and companies through web interface, a key component of successful e-service, is not as easy as through human-buyer-human-seller interaction. In the past few years, a number of experiments have been conducted in order to determine the factors that influence customers' trust in online businesses. The goal of our experiment was to establish which features that appear on commercial websites are trust-inducing. Our study focused on three independent variables: customer service (limited and extensive), testimonial (self and external) and security features representation (graphics and text). We designed the homepages of eight web sites with all combinations of treatments of the three independent variables. Each of the 52 subjects reviewed all the eight homepages and gave them a relative rank of trustworthiness. After the experiment subjects answered additional e-trust related questions. The experiment results and the survey support the belief that specific customer service commitments, third party testimonials and graphic security representations are important in establishing strategic trust among on-line customers.

Infranet: Circumventing web censorship and surveillance - Feamster, Nick; Balazinska,M.; Harfst,G.; Balakrishnan,H.; Karger,D. (Proceedings of the 11th USENIX Security Symposium, 2002)
An increasing number of countries and companies routinely block or monitor access to parts of the Internet. To counteract these measures, we propose Infranet, a system that enables clients to surreptitiously retrieve sensitive content via cooperating Web servers distributed across the global Internet. These Infranet servers provide clients access to censored sites while continuing to host normal uncensored content. Infranet uses a tunnel protocol that provides a covert communication channel between its clients and servers, modulated over standard HTTP transactions that resemble innocuous Web browsing. In the upstream direction, Infranet clients send covert messages to Infranet servers by associating meaning to the sequence of HTTP requests being made. In the downstream direction, Infranet servers return content by hiding censored data in uncensored images using steganographic techniques. We describe the design, a prototype implementation, security properties, and performance of Infranet. Our security analysis shows that Infranet can successfully circumvent several sophisticated censoring techniques.

Interacting with identification technology: can it make us more secure? - Scholtz,Jean; Johnson,Jeff; Shneiderman, Ben; Hope-Tindall,Peter; Gosling,Marcus; Phillips,Jonathon; Wexelblat,Alan (CHI '02 extended abstracts on Human factors in computing systems, 2002)
Keywords: Biometrics; civil liberties; face recognition; national id card; privacy; Security

Interlingua approximation: A generation-heavy approach - Dorr, Bonnie J; Habash,N. (Proceedings of AMTA-2002, 2002)

Navigation patterns and usability of zoomable user interfaces with and without an overview - Hornbaek,K.; Bederson, Benjamin B.; Plaisant, Catherine (ACM Transactions on Computer-Human Interaction (TOCHI), 2002)

A new, expressed multigene family containing a hot spot for insertion of retroelements is associated with polymorphic subtelomeric regions of Trypanosoma brucei - Bringaud,F.; Biteau,N.; Melville,S. E.; Hez,S.; El‐Sayed, Najib M.; Leech,V.; Berriman,M.; Hall,N.; Donelson,J. E; Baltz,T. (Eukaryotic cell, 2002)

A Parallel Block Multi-level Preconditioner for the 3D Incompressible Navier--Stokes Equations - Elman, Howard; Howle, V. E; Shadid,John; Tuminaro,Ray (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
The development of robust and efficient algorithms for both steady-statesimulations and fully-implicit time integration of the Navier--Stokes equations is an active research topic. To be effective, the linear subproblems generated by these methods require solution techniques that exhibit robust and rapid convergence. In particular, they should be insensitive to parameters in the problem such as mesh size, time step, and Reynolds number. In this context, we explore a parallel preconditioner based on a block factorization of the coefficient matrix generated in an Oseen nonlinear iteration for the primitive variable formulation of the system. The key to this preconditioner is the approximation of a certain Schur complement operator by a technique first proposed by Kay, Loghin, and Wathen [25] and Silvester, Elman, Kay, and Wathen [45]. The resulting operator entails subsidiary computations (solutions of pressure Poisson and convection--diffusion subproblems) that are similar to those required for decoupled solution methods; however, in this case these solutions are applied as preconditioners to the coupled Oseen system. One important aspect of this approach is that the convection--diffusion and Poisson subproblems are significantly easier to solve than the entire coupled system, and a solver can be built using tools developed for the subproblems. In this paper, we apply smoothed aggregation algebraic multigrid to both subproblems. Previous work has focused on demonstrating the optimality of these preconditioners with respect to mesh size on serial, two-dimensional, steady-state computations employing geometric multi-grid methods; we focus on extending these methods to large-scale, parallel, three-dimensional, transient and steady-state simulations employing algebraic multigrid (AMG) methods. Our results display nearly optimal convergence rates for steady-state solutions as well as for transient solutions over a wide range of CFL numbers on the two-dimensional and three-dimensional lid-driven cavity problem. Also UMIACS-TR-2002-95
Keywords: Technical Report

Predicting Transcription Factor Synergism - Hannenhalli, Sridhar; Levy,Samuel (Nucleic Acids ResearchNucl. Acids Res., 2002)
Transcriptional regulation is mediated by a battery of transcription factor (TF) proteins, that form complexes involving protein–protein and protein–DNA interactions. Individual TFs bind to their cognate cis‐elements or transcription factor‐binding sites (TFBS). TFBS are organized on the DNA proximal to the gene in groups confined to a few hundred base pair regions. These groups are referred to as modules. Various modules work together to provide the combinatorial regulation of gene transcription in response to various developmental and environmental conditions. The sets of modules constitute a promoter model. Determining the TFs that preferentially work in concert as part of a module is an essential component of understanding transcriptional regulation. The TFs that act synergistically in such a fashion are likely to have their cis‐elements co‐localized on the genome at specific distances apart. We exploit this notion to predict TF pairs that are likely to be part of a transcriptional module on the human genome sequence. The computational method is validated statistically, using known interacting pairs extracted from the literature. There are 251 TFBS pairs up to 50 bp apart and 70 TFBS pairs up to 200 bp apart that score higher than any of the known synergistic pairs. Further investigation of 50 pairs randomly selected from each of these two sets using PubMed queries provided additional supporting evidence from the existing biological literature suggesting TF synergism for these novel pairs.

Presentation planning for distributed VoD systems - Hwang,Eenjun; Prabhakaran,B.; V.S. Subrahmanian (Knowledge and Data Engineering, IEEE Transactions on, 2002)
A distributed video-on-demand (VoD) system is one where a collection of video data is located at dispersed sites across a computer network. In a single site environment, a local video server retrieves video data from its local storage device. However, in distributed VoD systems, when a customer requests a movie from the local server, the server may need to interact with other servers located across the network. In this paper, we present different types of presentation plans that a local server can construct in order to satisfy a customer request. Informally speaking, a presentation plan is a temporally synchronized sequence of steps that the local server must perform in order to present the requested movie to the customer. This involves obtaining commitments from other video servers, obtaining commitments from the network service provider, as well as making commitments of local resources, while keeping within the limitations of available bandwidth, available buffer, and customer data consumption rates. Furthermore, in order to evaluate the quality of a presentation plan, we introduce two measures of optimality for presentation plans: minimizing wait time for a customer and minimizing access bandwidth which, informally speaking, specifies how much network/disk bandwidth is used. We develop algorithms to compute three different optimal presentation plans that work at a block level, or at a segment level, or with a hybrid mix of the two, and compare their performance through simulation experiments. We have also mathematically proven effects of increased buffer or bandwidth and data replications for presentation plans which had previously been verified experimentally in the literature.
Keywords: Computer; computing; databases; demand; distributed; local; multimedia; network; on; optimal; plan; plans; presentation; presentation; server; servers; video; video-on-demand; VoD

Probabilistic Human Recognition from Video - Zhou,Shaohua; Chellapa, Rama (Computer Vision — ECCV 2002Computer Vision — ECCV 2002, 2002)
This paper presents a method for incorporating temporal information in a video sequence for the task of human recognition. A time series state space model, parameterized by a tracking state vector and a recognizing identity variable , is proposed to simultaneously characterize the kinematics and identity. Two sequential importance sampling (SIS) methods, a brute-force version and an efficient version, are developed to provide numerical solutions to the model. The joint distribution of both state vector and identity variable is estimated at each time instant and then propagated to the next time instant. Marginalization over the state vector yields a robust estimate of the posterior distribution of the identity variable. Due to the propagation of identity and kinematics, a degeneracy in posterior probability of the identity variable is achieved to give improved recognition. This evolving behavior is characterized using changes in entropy . The effectiveness of this approach is illustrated using experimental results on low resolution face data and upper body data.

RECOMB '02: Proceedings of the sixth annual international conference on Computational biology (ACM, 2002)
The papers in this volume were presented at the Sixth Annual International Conference on Computational Biology RECOMB 2002, held in Washington, D.C. on April 18-21, 2002. The RECOMB series was started in 1997 by Sorin Istrail, Pavel Pevzner and Michael Waterman. RECOMB '99 took place in Lyon, France, RECOMB 2000 was held in Tokyo, Japan, and RECOMB 2001 was held in Montreal, Quebec, Canada.This year's call for papers gave rise to 118 submissions, out of which the program committee selected 35 papers to be presented at the conference and included in the proceedings. Each submission was refereed by at least three members of the program committee. After the completion of the referees' reports, an extensive web-based discussion took place.RECOMB 2002 had 8 invited speakers: Ruben Abagyan (The Scripps Research Institute), Ali H. Brivanlou (Rockefeller University), Evan Eichler (Case Western Reserve University), Harold "Skip" Garner (University of Texas Southwestern Medical Center at Dallas), David Ho (Rockefeller University), Gerry Rubin (Howard Hughes Medical Institute), J. Craig Venter (Celera) and Marc Vidal (Dana-Farber Cancer Institute). The Stanislaw Ulam Memorial Lecture was given by J. Craig Venter. The Distinguished Biology Lecture was given by David Ho. The Distinguished New Technologies Lecture was given by Harold Garner.Complete final versions of many of the papers presented in the conference will appear in a special issue of the Journal of Computational Biology, which is closely affiliated with the conference.

Recompilation for debugging support in a JIT-compiler - Tikir, Mustafa M.; Hollingsworth, Jeffrey K; Lueh,Guei-Yuan (Proceedings of the 2002 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2002)
A static Java compiler converts Java source code into a verifiably secure and compact architecture-neutral intermediate format, called Java byte codes. The Java byte codes can be either interpreted by a Java Virtual Machine or translated into native code by Java Just-In-Time compilers. Static Java compilers embed debug information in the Java class files to be used by the source level debuggers. However, the debug information is generated for architecture independent byte codes and most of the debug information is valid only when the byte codes are interpreted. Translating byte codes into native instructions puts a limitation on the amount of usable debug information that can be used by source level debuggers. In this paper, we present a new technique to generate valid debug information when Just-In-Time compilers are used. Our approach is based on the dynamic recompilation of Java methods by a fast code generator and lazily generates debug information when it is required. We also present three implementations for field watch support in the Java Virtual Machine Debugger Interface to investigate the runtime overhead and code size growth by our approach.
Keywords: algorithms; debug information; debugging aids; dynamic recompilation; field access watch; java; java virtual machine debugger interface; just-in-time compilation; measurement; performance

Region-based memory management in cyclone - Grossman,Dan; Morrisett,Greg; Jim,Trevor; Hicks, Michael W.; Wang,Yanling; Cheney,James (SIGPLAN Not., 2002)
Cyclone is a type-safe programming language derived from C. The primary design goal of Cyclone is to let programmers control data representation and memory management without sacrificing type-safety. In this paper, we focus on the region-based memory management of Cyclone and its static typing discipline. The design incorporates several advancements, including support for region subtyping and a coherent integration with stack allocation and a garbage collector. To support separate compilation, Cyclone requires programmers to write some explicit region annotations, but a combination of default annotations, local type inference, and a novel treatment of region effects reduces this burden. As a result, we integrate C idioms in a region-based framework. In our experience, porting legacy C to Cyclone has required altering about 8% of the code; of the changes, only 6% (of the 8%) were region annotations.

A secure PLAN (extended version) - Hicks, Michael W.; Keromytis,A. D; Smith,J. M (DARPA Active NEtworks Conference and Exposition, 2002. Proceedings, 2002)
Active networks promise greater flexibility than current networks, but threaten safety and security by virtue of their programmability. We describe the design and implementation of a security architecture for the active network PLANet (Hicks et al., 1999). Security is obtained with a two-level architecture that combines a functionally restricted packet language, PLAN (Hicks et al., 1998), with an environment of general-purpose service routines governed by trust management (Blaze et al., 1996). In particular, we employ a technique which expands or contracts a packet's service environment based on its level of privilege, termed namespace-based security. As an application of our security architecture, we present the design and implementation of an active-network firewall. We find that the addition of the firewall imposes an approximately 34% latency overhead and as little as a 6.7% space overhead to incoming packets
Keywords: active internetwork; active networks; active-network firewall; Authentication; authorisation; Authorization; Cities and towns; Computer networks; Computer science; cryptography; functionally restricted packet language; general-purpose service routines; Information security; internetworking; IP networks; latency overhead; namespace-based security; PLAN; PLANet; Planets; programmability; Safety; security architecture; telecommunication security; trust management; two-level architecture; Web and internet services

SIGMA: A Simulator Infrastructure to Guide Memory Analysis - DeRose,Luiz; Ekanadham, K.; Hollingsworth, Jeffrey K; Sbaraglia, Simone (SC Conference, 2002)
In this paper we present SIGMA (Simulation Infrastructure to Guide Memory Analysis), a new data collection framework and family of cache analysis tools. The SIGMA environment provides detailed cache information by gathering memory reference data using software-based instrumentation. This infrastructure can facilitate quick probing into the factors that influence the performance of an application by highlighting bottleneck scenarios including: excessive cache/TLB misses and inefficient data layouts. The tool can also assist in perturbation analysis to determine performance variations caused by changes to architecture or program. Our validation tests using the SPEC Swim benchmark show that most of the performance metrics obtained with SIGMA are within 1% of the metrics obtained with hardware performance counters, with the advantage that SIGMA provides performance data on a data structure level, as specified by the programmer.

Simple Procedure for Rapid Identification of Vibrio Cholerae from the Aquatic Environment - Choopun,Nipa; Louis,Valérie; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2002)
Biochemical tests commonly used to screen for Vibrio cholerae in environmental samples were evaluated, and we found that a combination of alkaline peptone enrichment followed by streaking on thiosulfate citrate bile salts sucrose agar and testing for arginine dihydrolase activity and esculin hydrolysis was an effective rapid technique to screen for aquatic environmental V. cholerae. This technique provided 100% sensitivity and ≥70% specificity.

Speeding up construction of PMR quadtree-based spatial indexes - Hjaltason,Gisli R.; Samet, Hanan (The VLDB Journal, 2002)
Spatial indexes, such as those based on the quadtree, are important in spatial databases for efficient execution of queries involving spatial constraints, especially when the queries involve spatial joins. In this paper we present a number of techniques for speeding up the construction of quadtree-based spatial indexes, specifically the PMR quadtree, which can index arbitrary spatial data. We assume a quadtree implementation using the “linear quadtree”, a disk-resident representation that stores objects contained in the leaf nodes of the quadtree in a linear index (e.g., a B-tree) ordered based on a space-filling curve. We present two complementary techniques: an improved insertion algorithm and a bulk-loading method. The bulk-loading method can be extended to handle bulk-insertions into an existing PMR quadtree. We make some analytical observations about the I/O cost and CPU cost of our PMR quadtree bulk-loading algorithm, and conduct an extensive empirical study of the techniques presented in the paper. Our techniques are found to yield significant speedup compared to traditional quadtree building methods, even when the size of a main memory buffer is very small compared to the size of the resulting quadtrees.
Keywords: Bulk-loading; I/O; spatial indexing

A Step Towards Automated Design of Multi-Piece Sacrificial Molds - Dhaliwal,Savinder; Gupta, Satyandra K.; Huang,Jun; Kumar,Malay (ASME, 2002)
This paper describes a feature-based approach for design of multi-piece sacrificial molds. Our mold design algorithm consists of the following three steps. First, the desired gross mold shape is formed based on the feature-based description of the part geometry. Second, if the desired gross mold shape is not machinable as a single piece, the gross mold shape is decomposed into simpler geometric components to make sure that each component is manufacturable using 3-axis CNC machining. The decomposition is performed to ensure that each component is accessible to end-milling tools, and decomposed components can be assembled together to form the gross mold shape. Finally, assembly features are added to mold components to facilitate assembly of mold components and eliminate unnecessary degree of freedoms from the final mold assembly. We expect that our decomposition algorithm will provide a step towards the necessary foundations for automating the design of multi-piece mold and therefore will help in significantly reducing the mold design and manufacturing lead-time.

Technologies for families - Plaisant, Catherine; Druin, Allison; Hutchinson,Hilary (CHI '02 extended abstracts on Human factors in computing systems, 2002)
In this workshop, we propose to bring together researchers from industry and academia to discuss the design of new technologies for families. We will focus on both design techniques and the technologies themselves. Through discussions and brainstorming we hope to discover new ideas, which can be disseminated more broadly.
Keywords: cooperative design; disappearing computer; family; Home; participatory design; probe; user interface

Understanding Machine Performance in the Context of Human Performance for Multi-document Summarization - Schlesinger,J.D.; Okurowski,M. E.; Conroy,J.M.; O'Leary, Dianne P.; Taylor,A.; Hobbs,J.; Wilson,H. T. (DUC 02 Conference ProceedingsDUC 02 Conference Proceedings, 2002)
We present a discussion of our summarization algorithm -- both single and multi-document -- along with a discussion of the evaluation experiments we have undertaken, what we have learned from them, and how we intend to utilize this information.

On using correlation-based synopses during query optimization - Deshpande, Amol; Hellerstein,J. (Computer Science Division (EECS), University of California Berkeley, 2002)
In recent years, a variety of complex synopsis structures have been proposed to capturestatistical correlations present in database relations. The goal of that work has been to improve cardinality estimation during query optimization by improving statistics on base tables. In order to use the correlation information for multi-table estimations as well, synopses must also be constructed on intermediate result tables during query optimization. We address that problem here, and show how to efficiently integrate multi-dimensional histograms and other complex synopsis structures into the search algorithm of a traditional query optimizer such as that of System R. A main challenge in this work is minimizing the computational expense of dynamically computing synopses on intermediate tables during query optimization. We show that one only needs to construct a very small subset of all possible synopses to get the full estimation bene- fits of multi-dimensional modeling. We also show that choosing this subset unwisely can have unacceptable performance overheads. This leads to an “estimation planning” problem that has been ignored to date in literature: how to choose the most efficiently-computable collection of intermediate synopses to construct, so that all the required cardinality estimates can be com- puted as accurately as possible from the base-table synopses? In this paper, we identify and formalize the estimation planning problem in the context of a System R-style optimizer extended with complex synopsis techniques such as multi-dimensional histograms. We propose algorithms that find very good estimation plans efficiently, and discuss properties of synopsis structures that make them amenable to efficient use in an optimizer.

Virtual Telescopes in Education - Hoban,S.; desJardins, Marie; Farrell,N.; Rathod,P.; Sachs,J.; Sansare,S.; Yesha,Y.; Keating,J.; Busschots,B.; Means,J.; others (Journal of Digital Information, 2002)
Virtual Telescopes in Education is providing the services required to operate a virtual observatory comprising distributed telescopes, including an interactive, constraint-based scheduling service, data and resource archive, proposal preparation and review environment, and a VTIE Journal. A major goal of VTIE is to elicit from learners questions about the nature of celestial objects and the physical processes that give rise to the spectacular imagery that catches their imaginations. Generation of constrained science questions will assist learners in the science process. To achieve interoperability with other NSDL resources, our approach follows the Open Archives Initiative and the W3C Semantic Web activity.

Visual queries for finding patterns in time series data - Hochheiser,H.; Shneiderman, Ben (University of Maryland, Computer Science Dept. Tech Report, CS-TR-4365, 2002)
Few tools exist for data exploration and pattern iden-tification in time series data sets. Timeboxes are rectan- gular, direct-manipulation queries for studying time-series datasets. Timeboxes are the primary query tool in our Time- Searcher application, which supports interactive explo- ration via dynamic queries, along with overviews of query results and drag-and-drop support for query-by-example. This paper describes the TimeSearcher application and pos- sible extensions to the timebox query model, along with a discussion of the use of TimeSearcher for exploring a time series data set involving gene expression profiles.

A visual search tool for early elementary science students - Revelle,G.; Druin, Allison; Platner,M.; Bederson, Benjamin B.; Hourcade,J. P; Sherman,L. (Journal of Science Education and Technology, 2002)

Word-level Alignment for Multilingual Resource Acquisition - Lopez,Adam; Nossal,Michael; Hwa,Rebecca; Resnik, Philip (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2002)
We present a simple, one-pass word alignment algorithm for parallel text. Our algorithm utilizes synchronous parsing and takes advantage of existing syntactic annotations. In our experiments the performance of this model is comparable to more complicated iterative methods. We discuss the challenges and potential benefits of using the model to train syntactic parsers for new languages.
Keywords: *LEARNING MACHINES; *MULTILINGUAL RESOURCES; *WORDS(LANGUAGE); ACQUISITION; algorithms; ALIGNMENT; BENEFITS; ITERATIONS; LANGUAGE; linguistics

Achieving Efficiency and Accuracy in Simulation for I/O-Intensive Applications - Eom, Hyeonsang; Hollingsworth, Jeffrey K (Journal of Parallel and Distributed Computing, 2001)
This paper presents a family of simulators for data-intensive applications, and a methodology to select the most efficient simulator based on a user-supplied requirement for accuracy. The methodology consists of a series of tests that select an appropriate simulation based on the attributes of the application. In addition, each simulator provides two estimates of application execution time: one for the minimum expected time and the other for the maximum. We present the results of applying the strategy to existing applications and show that we can accurately simulate applications tens to hundreds of times faster than application execution time.
Keywords: simulation; I/O-intensive applications; parallel or distributed applications; performance prediction; discrete-event simulation

Analysis and prediction of protein functional sub-types from protein sequence alignments - Hannenhalli, Sridhar; Russell,Robert B. (2001)
Here we present a method for analysis and prediction of functional sub-types from multiple protein sequence alignments. Given an alignment and set of proteins grouped into sub-types according to some definition of function, such as enzymatic specificity, the method identifies positions that are indicative of functional differences by subtraction of sequence profiles, and analysis of positional entropy in the alignment.

Attentive toys - Haritaoglu,I.; Cozzi,A.; Koons,D.; Flickner,M.; Zotkin,Dmitry N; Yacoob,Yaser (International Conference on Multimedia and Expo, 2001)

A Calculus for Dynamic Loading - Hicks, Michael W.; Weirich,Stephanie (Technical Reports (CIS), 2001)
We present the load-calculus, used to model dynamic loading, and prove it sound. The calculus extends the polymorphic λ-calculus with a load primitive that dynamically loads terms that are closed, with respect to values. The calculus is meant to approximate the process of dynamic loading in TAL/Load [4], a version of Typed Assembly Language [7] extending with dynamic linking. To model the key aspects of TAL, the calculus contains references and facilities for named types. Loadable programs may refer to named types defined by the running program, and may export new types to code loaded later. Our approach follows the framework initially outlined by Glew et. al [3]. This calculus has been implemented in the TALx86 [6] version of Typed Assembly Language, and is used to implement a full-featured dynamic linking library, DLpop [4].

Compiling PLAN to SNAP - Hicks, Michael W.; Moore,Jonathan; Nettles,Scott (Active NetworksActive Networks, 2001)
PLAN (Packet Language for Active Networks) [ 3 ] is a highly flexible and usable active packet language, whereas SNAP (Safe and Nimble Active Packets) [ 12 ] offers significant resource usage safety and achieves much higher performance compared to PLAN, but at the cost of flexibility and usability. Ideally, we would like to combine the good properties of PLAN with those of SNAP. We have achieved this end by developing a compiler that translates PLANi nto SNAP. The compiler allows us to achieve the flexibility and usability of PLAN, but with the safety and efficiency of SNAP. In this paper, we describe both languages, highlighting the features that require special compilation techniques. We then present the details of our compiler and experimental results to evaluate our compiler with respect to code size.

Cyclone User's Manual, Version 0.1. 3 - Grossman,D.; Morrisett,G.; Jim,T.; Hicks, Michael W.; Wang, Y.; Cheney,J. (Computer Science Technical Reports, 2001)
The current version of this manual should be available at http://www.cs.cornell.edu/projects/cyclone/ and http://www.research.att.com/projects/cyclone/. The version here describes Cyclone Version 0.1.3, although minor changes may have occurred before the release.

Dynamic software updating - Hicks, Michael W.; Moore,Jonathan T.; Nettles,Scott (Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, 2001)
Many important applications must run continuously and without interruption, yet must be changed to fix bugs or upgrade functionality. No prior general-purpose methodology for dynamic updating achieves a practical balance between flexibility, robustness, low overhead, and ease of use.We present a new approach for C-like languages that provides type-safe dynamic updating of native code in an extremely flexible manner (code, data, and types may be updated, at programmer-determined times) and permits the use of automated tools to aid the programmer in the updating process. Our system is based on dynamic patches that both contain the updated code and the code needed to transition from the old version to the new. A novel aspect of our patches is that they consist of verifiable native code (e.g. Proof-Carrying Code [17] or Typed Assembly Language [16]), which is native code accompanied by annotations that allow on-line verification of the code's safety. We discuss how patches are generated mostly automatically, how they are applied using dynamic-linking technology, and how code is compiled to make it updateable. To concretely illustrate our system, we have implemented a dynamically-updateable web server, FlashEd. We discuss our experience building and maintaining FlashEd. Performance experiments show that for FlashEd, the overhead due to updating is typically less than 1%.

Efficient Language Independent Generation from Lexical Conceptual Structure - Habash,Nizar; Dorr, Bonnie J; Traum,David (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2001)
This paper describes a system for generating natural-language sentences from an interlingual representation, Lexical Conceptual Structure (LCS). The system has been developed as part of a Chinese-English Machine Translation system; however, it is designed to be used for many other MT language pairs and Natural Language applications. The contributions of this work include: (1) Development of a language-independent generation system that maximizes efficiency through the use of a hybrid rule-based/statistical module; (2) Enhancements to an interlingual representation and associated algorithms for interpretation of multiply ambiguous input sentences; (3) Development of an efficient reusable language-independent linearization module with a grammar description language that can be used with other systems; (4) Improvements to an earlier algorithm for hierarchically mapping thematic roles to surface positions; (5) Development of a diagnostic tool for lexicon coverage and correctness and use of the tool for verification of English, Spanish, and Chinese lexicons. An evaluation of translation quality shows comparable performance with commercial translation system. The generation system can also be straightforwardly extended to their languages and this is demonstrated and evaluated for Spanish.
Keywords: *LEXICAL CONCEPTUAL STRUCTURE; *LEXICOGRAPHY; *MACHINE TRANSLATION; *VOCABULARY; *WORDS(LANGUAGE); algorithms; CHINA; COMMERCE; DIAGNOSTIC EQUIPMENT; efficiency; English language; grammars; INPUT; INTERLINGUAL; LANGUAGE; LANGUAGE-INDEPENDENT NLP.; linguistics; MAPPING; natural language; QUALITY; SPANISH LANGUAGE; verification

Efficient network and I/O throttling for fine-grain cycle stealing - Ryu, Kyung D.; Hollingsworth, Jeffrey K; Keleher, Peter J. (Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM) - Supercomputing '01, 2001)

Efficient perspective-accurate silhouette computation and applications - Pop, Mihai; Duncan,Christian; Barequet,Gill; Goodrich,Michael; Huang,Wenjing; Kumar,Subodh (Proceedings of the seventeenth annual symposium on Computational geometry, 2001)
Silhouettes are perceptually and geometrically salient features of geo metric models. Hence a number of graphics and visualization applications need to find them to aid further processing. The efficient computation of silhouettes, especially in the context of perspective projection, is known to be difficult. This paper presents a novel efficient and practical algorithm to compute silhouettes from a sequence of viewpoints under perspective projection. Parallel projection is a special case of this algorithm. Our approach is based on a point-plane duality in three dimensions, which allows an efficient computation of the changes in the silhouette of a polygonal model between consecutive frames. In addition, we present several applications of our technique to problems from computer graphics and medical visualization. We also provide experimental data that show the efficiency of our approach. million vertices on an SGI Onyx workstation.
Keywords: rendering; silhouette; simplification

An empirical study of regression test selection techniques - Graves,Todd L.; Harrold,Mary Jean; Kim,Jung-Min; Porter, Adam; Rothermel,Gregg (ACM Transactions on Software Engineering and MethodologyACM Trans. Softw. Eng. Methodol., 2001)

Enrichment of Regulatory Signals in Conserved Non-Coding Genomic Sequence - Levy,Samuel; Hannenhalli, Sridhar; Workman,Christopher (BioinformaticsBioinformatics, 2001)
Motivation: Whole genome shotgun sequencing strategies generate sequence data prior to the application of assembly methodologies that result in contiguous sequence. Sequence reads can be employed to indicate regions of conservation between closely related species for which only one genome has been assembled. Consequently, by using pairwise sequence alignments methods it is possible to identify novel, non-repetitive, conserved segments in non-coding sequence that exist between the assembled human genome and mouse whole genome shotgun sequencing fragments. Conserved non-coding regions identify potentially functional DNA that could be involved in transcriptional regulation.Results: Local sequence alignment methods were applied employing mouse fragments and the assembled human genome. In addition, transcription factor binding sites were detected by aligning their corresponding positional weight matrices to the sequence regions. These methods were applied to a set of transcripts corresponding to 502 genes associated with a variety of different human diseases taken from the Online Mendelian Inheritance in Man database. Using statistical arguments we have shown that conserved non-coding segments contain an enrichment of transcription factor binding sites when compared to the sequence background in which the conserved segments are located. This enrichment of binding sites was not observed in coding sequence. Conserved non-coding segments are not extensively repeated in the genome and therefore their identification provides a rapid means of finding genes with related conserved regions, and consequently potentially related regulatory mechanism. Conserved segments in upstream regions are found to contain binding sites that are co-localized in a manner consistent with experimentally known transcription factor pairwise co-occurrences and afford the identification of novel co-occurring Transcription Factor (TF) pairs. This study provides a methodology and more evidence to suggest that conserved non-coding regions are biologically significant since they contain a statistical enrichment of regulatory signals and pairs of signals that enable the construction of regulatory models for human genes. Contact: samuel.levy@celera.com

E-tables: Non-specialist use and understanding of statistical data - Marchionini,G.; Hert,C.; Shneiderman, Ben; Liddy,L. (SURFACE, the Syracuse University Research Facility And Collaborative Environment, 2001)
This paper provides a progress report on a project that aims to understand how people think about and understand statistical data presented in tables. The focus is on people who are not statistical specialists. To this end, studies of various user populations were conducted, underlying data enrichment and explanation was investigated, and interactive user interface prototypes were developed and tested.

Experimental Analysis of Algorithms for Bilateral-Contract Clearing Mechanisms Arising in Deregulated Power Industry - Barrett,Chris; Cook,Doug; Hicks,Gregory; Faber,Vance; Marathe,Achla; Marathe,Madhav; Srinivasan, Aravind; Sussmann,Yoram; Thornquist,Heidi (Algorithm EngineeringAlgorithm Engineering, 2001)
We consider the bilateral contract satisfaction problem arising from electrical power networks due to the proposed deregulation of the electric utility industry in the USA. Given a network and a (multi)set of pairs of vertices (contracts) with associated demands, the goal is to find the maximum number of simultaneously satisfiable contracts. We study how four different algorithms perform in fairly realistic settings; we use an approximate electrical power network from Colorado. Our experiments show that three heuristics outperform a theoretically better algorithm. We also test the algorithms on four types of scenarios that are likely to occur in a deregulated marketplace. Our results show that the networks that are adequate in a regulated marketplace might be inadequate for satisfying all the bilateral contracts in a deregulated industry.

A feature-based approach to automated design of multi-piece sacrificial molds - Dhaliwal,S.; Gupta,S.K.; Huang,J.; Kumar,M. (Journal of Computing and Information Science in Engineering, 2001)

Geometry of Eye Design: Biology and Technology - Fermüller, Cornelia; Aloimonos, J. (Multi-Image Analysis, 2001)
Natural or artificial vision systems process the images that they collect with their eyes or cameras in order to derive information for performing tasks related to navigation and recognition. Since the way images are acquired determines how dificult it is to perform a visual task, and since systems have to cope with limited resources, the eyes used by a specific system should be designed to optimize subsequent image processing as it relates to particular tasks. Different ways of sampling light, i.e., different eyes, may be less or more powerful with respect to particular competences. This seems intuitively evident in view of the variety of eye designs in the biological world. It is shown here that a spherical eye (an eye or system of eyes providing panoramic vision) is superior to a camera-type eye (an eye with restricted field of view) as regards the competence of three-dimensional motion estimation. This result is derived from a statistical analysis of all the possible computational models that can be used for estimating 3D motion from an image sequence. The findings explain biological design in a mathematical manner, by showing that systems that fly and thus need good estimates of 3D motion gain advantages from panoramic vision. Also, insights obtained from this study point to new ways of constructing powerful imaging devices that suit particular tasks in robotics, visualization and virtual reality better than conventional cameras, thus leading to a new camera technology.

Interactive Exploration of Time Series Data - Hochheiser,Harry; Shneiderman, Ben (Discovery ScienceDiscovery Science, 2001)
Widespread interest in discovering features and trends in time- series has generated a need for tools that support interactive exploration.This paper introduces timeboxes: a powerful direct-manipulation metaphor for the specification of queries over time series datasets. Our TimeSearcher implementation of timeboxes supports interactive formulation and modification of queries, thus speeding the process of exploring time series data sets and guiding data mining.

More efficient network class loading through bundling - Hovemeyer,D.; Pugh, William (Proceedings of the 2001 Symposium on Java TM Virtual Machine Research and Technology Symposium-Volume 1, 2001)

Practical programmable packets - Moore,J. T; Hicks, Michael W.; Nettles,S. (IEEE INFOCOM 2001. Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 2001)
We present SNAP (safe and nimble active packets), a new scheme for programmable (or active) packets centered around a new low-level packet language. Unlike previous active packet approaches, SNAP is practical: namely, adding significant flexibility over IP without compromising safety and security or efficiency. In this paper we show how to compile from the well-known active picket language PLAN to SNAP, showing that SNAP retains PLAN's flexibility; give proof sketches of its novel approach to resource control; and present experimental data showing SNAP attains performance very close to that of a software IP router
Keywords: active picket language; Application software; complier; Contracts; Data security; efficiency; Explosives; INFORMATION SCIENCE; Internet; IP; IP networks; low-level packet language; packet switching; performance; PLAN; practical programmable packets; program compilers; Protection; resource control; Resource management; safe and nimble active packets; Safety; Security; SNAP; software IP router; Software performance; telecommunication security; Transport protocols

Promoter prediction in the human genome - Hannenhalli, Sridhar; Levy,S. (Bioinformatics, 2001)
Computational prediction of eukaryotic polII promoters has been one of the most elusive problems despite considerable effort devoted to the study. Researchers have looked for various types of signals around the transcriptional start site (TSS), viz. oligo-nucleotide statistics, potential binding sites for core factors, clusters of binding sites, proximity to CpG islands etc.. The proximity of CpG islands to gene starts is now a well established fact, although until recently, it was based on very little genomic data. In this work we explore the possibility of enhancing the promoter prediction accuracy by combining CpG island information with a few other, biologically motivated, seemingly independent signals, that cover most of the known knowledge. We benchmarked the method on a much larger genomic datasets compared to previous studies. We were able to improve slightly upon current prediction accuracy. Furthermore, we observe that CpG islands are the most dominant signals and the other signals do not improve the prediction. This suggests that the computational prediction of promoters for genes with no associated CpG-island (typically having tissue-specific expression) looking only at the immediate neighborhood of the TSS may not even be possible. We suggest some biological experiments and studies to better understand the biology of transcription.

Relating amino acid sequence to phenotype: analysis of peptide-binding data - Segal,M. R; Cummings, Michael P.; Hubbard,A. E (Biometrics, 2001)
We illustrate data analytic concerns that arise in the context of relating genotype, as represented by amino acid sequence, to phenotypes (outcomes). The present application examines whether peptides that bind to a particular major histocompatibility complex (MHC) class I molecule have characteristic amino acid sequences. However, the concerns identified and addressed are considerably more general. It is recognized that simple rules for predicting binding based solely on preferences for specific amino acids in certain (anchor) positions of the peptide's amino acid sequence are generally inadequate and that binding is potentially influenced by all sequence positions as well as between-position interactions. The desire to elucidate these more complex prediction rules has spawned various modeling attempts, the shortcomings of which provide motivation for the methods adopted here. Because of (i) this need to model between-position interactions, (ii) amino acids constituting a highly (20) multilevel unordered categorical covariate, and (iii) there frequently being numerous such covariates (i.e., positions) comprising the sequence, standard regression/classification techniques are problematic due to the proliferation of indicator variables required for encoding the sequence position covariates and attendant interactions. These difficulties have led to analyses based on (continuous) properties (e.g., molecular weights) of the amino acids. However, there is potential information loss in such an approach if the properties used are incomplete and/or do not capture the mechanism underlying association with the phenotype. Here we demonstrate that handling unordered categorical covariates with numerous levels and accompanying interactions can be done effectively using classification trees and recently devised bump-hunting methods. We further tackle the question of whether observed associations are attributable to amino acid properties as well as addressing the assessment and implications of between-position covariation.

The role of a natural language conversational interface in online sales: A case study - Chai,J.; Jimmy Lin; Zadrozny,W.; Ye,Y.; Stys-Budzikowska,M.; Horvath,V.; Kambhatla,N.; Wolf,C. (International Journal of Speech Technology, 2001)
This paper describes the evaluation of a natural language dialog-based navigation system (HappyAssistant) that helps users access e-commerce sites to find relevant information about products and services. The prototype system leverages technologies in natural language processing and human-computer interaction to create a faster and more intuitive way of interacting with websites, especially for less experienced users. The result of a comparative study shows that users prefer the natural language-enabled navigation two to one over the menu driven navigation. In addition, the study confirmed the efficiency of using natural language dialog in terms of the number of clicks and the amount of time required to obtain the relevant information. In the case study, as compared to the menu driven system, the average number of clicks used in the natural language system was reduced by 63.2% and the average time was reduced by 33.3%.

Safe and Flexible Dynamic Linking of Native Code - Hicks, Michael W.; Weirich,Stephanie; Crary,Karl (Types in Compilation, 2001)
We present the design and implementation of the first complete framework for flexible and safe dynamic linking of native code. Our approach extends Typed Assembly Language with a primitive for loading and typechecking code, which is flexible enough to support a variety of linking strategies, but simple enough that it does not significantly expand the trusted computing base. Using this primitive, along with the ability to compute with types, we show that we can program many existing dynamic linking approaches. As a concrete demonstration, we have used our framework to implement dynamic linking for a type-safe dialect of C, closely modeled after the standard linking facility for Unix C programs. Aside from the unavoidable cost of verification, our implementation performs comparably with the standard, untyped approach.

A tool to help tune where computation is performed - Eom, Hyeonsang; Hollingsworth, Jeffrey K (IEEE Transactions on Software Engineering, 2001)
We introduce a new performance metric, called load balancing factor (LBF), to assist programmers when evaluating different tuning alternatives. The LBF metric differs from traditional performance metrics since it is intended to measure the performance implications of a specific tuning alternative rather than quantifying where time is spent in the current version of the program. A second unique aspect of the metric is that it provides guidance about moving work within a distributed or parallel program rather than reducing it. A variation of the LBF metric can also be used to predict the performance impact of changing the underlying network. The LBF metric is computed incrementally and online during the execution of the program to be tuned. We also present a case study that shows that our metric can accurately predict the actual performance gains for a test suite of six programs
Keywords: Computational modeling; Current measurement; Distributed computing; distributed program; distributed programming; load balancing factor; Load management; parallel program; parallel programming; Performance analysis; performance evaluation; Performance gain; performance metric; Programming profession; software metrics; software performance evaluation; Testing; Time measurement; tuning

Understanding Manufacturing Systems with a Learning Historian for User-Directed Experimentation - Chipman,G.; Plaisant, Catherine; Gahagan,S.; Herrmann,J.W.; Hewitt,S.; Reaves,L. (Department of Computer Science, University of Maryland, College Park, 2001)
This paper describes a learning historian to improve user-directed experimentation withdiscrete event simulation models of manufacturing systems. In user-directed experimentation, an analyst conducts simulation runs to estimate system performance. Then the analyst modifies the simulation model to evaluate other possibilities. An important characteristic is the ad hoc nature of the experimentation, as the analyst forms and runs new trials based on the results from previous trials. Through user-directed experimentation designers compare alternatives and students learn the relationships between input parameters and performance measures. Recording and reviewing previous trials while using simulation models enhances their benefits, transforming trial-and-error into learning. The learning historian combines a graphical user interface, a discrete event simulation model, and dynamic data visualization. Usability studies indicate that the learning historian is a usable and useful tool because it allows users to concentrate more on understanding system behavior than on operating simulation software.

Universal usability as a stimulus to advanced interface design - Shneiderman, Ben; Hochheiser,Harry (Behaviour & Information Technology, 2001)
The desire to make computing available to broader populations has historically been a motivation for research and innovation that led to new breakthroughs in usability. Menus, graphical user interfaces and the World Wide Web are examples of innovative technological solutions that have arisen out of the challenge of bringing larger and more diverse groups of users into the world of computing. Universal usability is the latest such challenge: In order to build systems that are universally usable, designers must account for technology variety, user diversity and gaps in user knowledge. These issues are particularly challenging and important in the context of increasing the usability of the World Wide Web. To raise awareness, web designers are urged to provide universal usability statements that offer users information about the usability of their sites. These statements can inform users and thereby reduce frustration and confusion. Further steps toward universal usability might be achieved through research aimed at developing tools that would encourage or promote usability. The paper closes with five proposals for future research.The desire to make computing available to broader populations has historically been a motivation for research and innovation that led to new breakthroughs in usability. Menus, graphical user interfaces and the World Wide Web are examples of innovative technological solutions that have arisen out of the challenge of bringing larger and more diverse groups of users into the world of computing. Universal usability is the latest such challenge: In order to build systems that are universally usable, designers must account for technology variety, user diversity and gaps in user knowledge. These issues are particularly challenging and important in the context of increasing the usability of the World Wide Web. To raise awareness, web designers are urged to provide universal usability statements that offer users information about the usability of their sites. These statements can inform users and thereby reduce frustration and confusion. Further steps toward universal usability might be achieved through research aimed at developing tools that would encourage or promote usability. The paper closes with five proposals for future research.

Universal usability statements: Marking the trail for all users - Hochheiser,Harry; Shneiderman, Ben (interactions, 2001)

Using interactive visualizations of WWW log data to characterize access patterns and inform site design - Hochheiser,Harry; Shneiderman, Ben (Journal of the American Society for Information Science and Technology, 2001)
HTTP server log files provide Web site operators with substantial detail regarding the visitors to their sites. Interest in interpreting this data has spawned an active market for software packages that summarize and analyze this data, providing histograms, pie graphs, and other charts summarizing usage patterns. Although useful, these summaries obscure useful information and restrict users to passive interpretation of static displays. Interactive visualizations can be used to provide users with greater abilities to interpret and explore Web log data. By combining two-dimensional displays of thousands of individual access requests, color, and size coding for additional attributes, and facilities for zooming and filtering, these visualizations provide capabilities for examining data that exceed those of traditional Web log analysis tools. We introduce a series of interactive visualizations that can be used to explore server data across various dimensions. Possible uses of these visualizations are discussed, and difficulties of data collection, presentation, and interpretation are explored.

Variable-precision rendering - Hao,Xuejun; Varshney, Amitabh (Proceedings of the 2001 symposium on Interactive 3D graphics, 2001)
Keywords: hierarchical rendering; levels of detail; variable-precision rendering; view-dependent rendering

Visual specification of queries for finding patterns in time-series data - Hochheiser,H.; Shneiderman, Ben (Proceedings of discovery science, 2001)
Widespread interest in discovering features and trends in time- series has generated a need for tools that support interactive exploration.This paper introduces timeboxes: a powerful graphical, direct-manipulation metaphor for the specification of queries over time-series datasets. Our TimeFinder implementation of timeboxes supports interactive formulation and modification of queries, thus speeding the process of exploring time-series data sets and guiding data mining. TimeFinder includes windows for timebox queries, individual time-series, and details-on-demand. Other features include drag-and-drop support for query-by-example and graphical envelopes for displaying the extent of the entire data set and result set from a given query. Extensions involving increased expressive power and general temporal data sets are discussed.

z-Approximations - Hassin,Refael; Khuller, Samir (Journal of Algorithms, 2001)
Approximation algorithms for NP-hard optimization problems have been widely studied for over three decades. Most of these measure the quality of the solution produced by taking the ratio of the cost of the solution produced by the algorithm to the cost of an optimal solution. In certain cases, this ratio may not be very meaningful—for example, if the ratio of the worst solution to the best solution is at most some constant α, then an approximation algorithm with factor α may in fact yield the worst solution! To overcome this hurdle (among others), several authors have independently suggested the use of a different measure which we call z-approximation. An algorithm is an α z-approximation if it runs in polynomial time and produces a solution whose distance from the optimal one is at most α times the distance between the optimal solution and the worst possible solution. The results known so far about z-approximations are either of the inapproximability type or rather straightforward observations. We design polynomial time algorithms for several fundamental discrete optimization problems; in particular we obtain a z-approximation factor of 12 for the directed traveling salesman problem (TSP) (with no triangle inequality assumption). For the undirected TSP this improves to 13. We also show that if there is a polynomial time algorithm that for any fixed ϵ > 0 yields an ϵ z-approximation then P = NP. We also present z-approximations for severa1 other problems such as max cut, stacker crane, maximum acyclic subgraph, and minimum disjoint cycle cover.

Active Networking Means Evolution (or Enhanced Extensibility Required) - Hicks, Michael W.; Nettles,Scott (Active NetworksActive Networks, 2000)
A primary goal of active networking is to increase the pace of network evolution. Evolution is typically achieved via extensibility; that is, typical active network implementations provide an interface to extend network nodes withdyna mically loaded code. Most implementations employ plug-in extensibility , a technique for loading code characterized by a concrete, pre-defined abstraction of future change. While flexible and convenient, we argue that plug-in extensibility alone is not sufficient for true network evolution. Instead, we propose dynamic software updating , a technique that reduces the a priori assumptions of plug-in extensibility, improving flexibility and eliminating the need to pre-plan extensions. However, this additional flexibility creates issues involving validity and security. We discuss these issues, and describe the state-of-the-art in systems that support dynamic software updating, thus framing the problem for researchers developing next-generation active networks.

Adaptive query processing: Technology in evolution - Hellerstein,J. M; Franklin,M.J.; Chandrasekaran,S.; Deshpande, Amol; Hildrum,K.; Madden,S.; Raman,V.; Shah,M. A (IEEE Data Engineering Bulletin, 2000)
As query engines are scaled and federated, they must cope with highly unpredictable and changeableenvironments. In the Telegraph project, we are attempting to architect and implement a continuously adaptive query engine suitable for global-area systems, massive parallelism, and sensor networks. To set the stage for our research, we present a survey of prior work on adaptive query processing, focusing on three characterizations of adaptivity: the frequency of adaptivity, the effects of adaptivity, and the extent of adaptivity. Given this survey, we sketch directions for research in the Telegraph project.

The African trypanosome genome - El‐Sayed, Najib M.; Hegde,Priti; Quackenbush,John; Melville,Sara E.; Donelson,John E. (International Journal for Parasitology, 2000)
The haploid nuclear genome of the African trypanosome, Trypanosoma brucei, is about 35 Mb and varies in size among different trypanosome isolates by as much as 25%. The nuclear DNA of this diploid organism is distributed among three size classes of chromosomes: the megabase chromosomes of which there are at least 11 pairs ranging from 1 Mb to more than 6 Mb (numbered I-XI from smallest to largest); several intermediate chromosomes of 200-900 kb and uncertain ploidy; and about 100 linear minichromosomes of 50-150 kb. Size differences of as much as four-fold can occur, both between the two homologues of a megabase chromosome pair in a specific trypanosome isolate and among chromosome pairs in different isolates. The genomic DNA sequences determined to date indicated that about 50% of the genome is coding sequence. The chromosomal telomeres possess TTAGGG repeats and many, if not all, of the telomeres of the megabase and intermediate chromosomes are linked to expression sites for genes encoding variant surface glycoproteins (VSGs). The minichromosomes serve as repositories for VSG genes since some but not all of their telomeres are linked to unexpressed VSG genes. A gene discovery program, based on sequencing the ends of cloned genomic DNA fragments, has generated more than 20 Mb of discontinuous single-pass genomic sequence data during the past year, and the complete sequences of chromosomes I and II (about 1 Mb each) in T. brucei GUTat 10.1 are currently being determined. It is anticipated that the entire genomic sequence of this organism will be known in a few years. Analysis of a test microarray of 400 cDNAs and small random genomic DNA fragments probed with RNAs from two developmental stages of T. brucei demonstrates that the microarray technology can be used to identify batteries of genes differentially expressed during the various life cycle stages of this parasite.

Agents in Network Management - Ertugay,Osman; Hicks, Michael W.; Smith,Jonathan; Kornblum,Jessica (Technical Reports (CIS), 2000)
The ubiquity and complexity of modern networks require automated management and control. With increases in scale, automated solutions based on simple data access models such as SNMP will give way to more distributed and algorithmic techniques. This article outlines present and near-term solutions based on the ideas of active networks and mobile agents, which permit sophisticated programmable control and management of ultra large scale networks.

Analysis and prediction of functional sub-types from protein sequence alignments - Hannenhalli, Sridhar; Russell,Robert B. (Journal of Molecular Biology, 2000)
The increasing number and diversity of protein sequence families requires new methods to define and predict details regarding function. Here, we present a method for analysis and prediction of functional sub-types from multiple protein sequence alignments. Given an alignment and set of proteins grouped into sub-types according to some definition of function, such as enzymatic specificity, the method identifies positions that are indicative of functional differences by comparison of sub-type specific sequence profiles, and analysis of positional entropy in the alignment. Alignment positions with significantly high positional relative entropy correlate with those known to be involved in defining sub-types for nucleotidyl cyclases, protein kinases, lactate/malate dehydrogenases and trypsin-like serine proteases. We highlight new positions for these proteins that suggest additional experiments to elucidate the basis of specificity. The method is also able to predict sub-type for unclassified sequences. We assess several variations on a prediction method, and compare them to simple sequence comparisons. For assessment, we remove close homologues to the sequence for which a prediction is to be made (by a sequence identity above a threshold). This simulates situations where a protein is known to belong to a protein family, but is not a close relative of another protein of known sub-type. Considering the four families above, and a sequence identity threshold of 30 %, our best method gives an accuracy of 96 % compared to 80 % obtained for sequence similarity and 74 % for BLAST. We describe the derivation of a set of sub-type groupings derived from an automated parsing of alignments from PFAM and the SWISSPROT database, and use this to perform a large-scale assessment. The best method gives an average accuracy of 94 % compared to 68 % for sequence similarity and 79 % for BLAST. We discuss implications for experimental design, genome annotation and the prediction of protein function and protein intra-residue distances.
Keywords: prediction; protein function; protein structure; sequence alignment

An API for Runtime Code Patching - Buck, Bryan; Hollingsworth, Jeffrey K (International Journal of High Performance Computing Applications, 2000)
The authors present a postcompiler program manipulation tool called Dyninst, which provides a C++ class library for program instrumentation. Using this library, it is possible to instrument and modify application programs during execution. A unique feature of this library is that it permits machine-independent binary instrumentation programs to be written. The authors describe the interface that a tool sees when using this library. They also discuss three simple tools built using this interface: a utility to count the number of times a function is called, a program to capture the output of an already running program to a file, and an implementation of conditional breakpoints. For the conditional breakpoint example, the authors show that by using their interface compared with gdb, they are able to execute a program with conditional breakpoints up to 900 times faster.

Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem - Guttmann-Beck,N.; Hassin,R.; Khuller, Samir; Raghavachari,B. (Algorithmica, 2000)
Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V 1 , . . ., V k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them.

An audio-video front-end for multimedia applications - Zotkin,Dmitry N; Duraiswami, Ramani; Davis, Larry S.; Haritaoglu,I. (2000 IEEE International Conference on Systems, Man, and Cybernetics, 2000)
Applications such as video gaming, virtual reality, multimodal user interfaces and videoconferencing, require systems that can locate and track persons in a room through a combination of visual and audio cues, enhance the sound that they produce, and perform identification. We describe the development of a particular multimodal sensor fusion system that is portable, runs in real time and achieves these objectives. The system employs novel algorithms for acoustical source location, video-based person tracking and overall system control, which are also described
Keywords: Acoustic noise; acoustical source location; Application software; audio cues; audio-video front-end; CAMERAS; Computer vision; Microphones; multimedia applications; multimedia systems; multimodal sensor fusion system; multimodal user interfaces; Position measurement; REAL TIME; Real time systems; real-time systems; sensor fusion; sound; Speech recognition; User interfaces; video cameras; video gaming; video-based person tracking; Videoconference; videoconferencing; Virtual reality; visual cues; Working environment noise

Combinatorial Problems Arising in Deregulated Electrical Power Industry: Survey and Future Directions - Cook,D.; Hicks,G.; Faber,V.; Marathe,M. V; Srinivasan, Aravind; Sussmann,Y. J; Thornquist,H. (NONCONVEX OPTIMIZATION AND ITS APPLICATIONS, 2000)

Comparative Evaluation of a Natural Language Dialog Based System and a Menu-Driven System for Information Access: A Case Study - Chai,J.; Jimmy Lin; Zadrozny,W.; Ye,Y.; Budzikowska,M.; Horvath,V.; Kambhatla,N.; Wolf,C. (In Proceedings of the International Conference on Multimedia Information Retrieval (RIAO 2000), 2000)
This paper describes the evaluation of a natural language dialog based navigation system (HappyAssistant) thathelps users access e-commerce sites to find relevant information about products and services. The prototype system leverages technologies in natural language processing and human computer interaction to create a faster and more intuitive way of interacting with websites, especially for the less experienced users. The result of a comparative study shows that users prefer the natural language enabled navigation two to one over the menu driven navigation. In addition, the study confirmed the efficiency of using natural language dialog in terms of the number of clicks and the amount of time required to obtain the relevant information. In the case study, comparing to the menu driven system, the average number of clicks used in the natural language system was reduced by 63.2% and the average time was reduced by 33.3%.

Coordinating overviews and detail views of WWW log data - Hochheiser,H.; Shneiderman, Ben (Workshop on New Paradigms in Information Visualization and Manipulation (NPIVM 2000), ACM Press, 2000)
Web server log analysis tools provide site operators with useful information regarding the visitors to their sites. Unfortunately, the utility of these tools is often limited by the use of aggregate summaries that hide the information associated with individual requests, and by the absence of contextual data that might help users interpret those summaries. Building upon earlier work in the use of starfield visualizations to display web site requests as individual data points [8], this paper describes the use of multiple-coordinated visualizations of web log data at varying granularities, and alongside additional related displays of appropriate contextual information.

Designing StoryRooms: interactive storytelling spaces for children - Alborzi,H.; Druin, Allison; Montemayor,J.; Platner,M.; Porteous,J.; Sherman,L.; Boltman,A.; Taxén,G.; Best,J.; Hammer,J.; others (Proceedings of the 3rd conference on Designing interactive systems: processes, practices, methods, and techniques, 2000)

Designing storytelling technologies to encouraging collaboration between young children - Benford,S.; Bederson, Benjamin B.; \AAkesson,K. P; Bayon,V.; Druin, Allison; Hansson,P.; Hourcade,J. P; Ingram,R.; Neale,H.; O'Malley,C.; others (Proceedings of the SIGCHI conference on Human factors in computing systems, 2000)

Efficient performance prediction for large-scale, data-intensive applications - Kurc, T.; Uysal, M.; Eom, H.; Hollingsworth, Jeffrey K; Saltz, J.; Sussman, Alan (International Journal of High Performance Computing Applications, 2000)

Exploiting fine-grained idle periods in networks of workstations - Kyung Dong Ryu; Hollingsworth, Jeffrey K (IEEE Transactions on Parallel and Distributed Systems, 2000)
Studies have shown that for a significant fraction of the time, workstations are idle. In this paper, we present a new scheduling policy called Linger-Longer that exploits the fine-grained availability of workstations to run sequential and parallel jobs. We present a two-level workload characterization study and use it to simulate a cluster of workstations running our new policy. We compare two variations of our policy to two previous policies: Immediate-Eviction and Pause-and-Migrate. Our study shows that the Linger-Longer policy can improve the throughput of foreign jobs on a cluster by 60 percent with only a 0.5 percent slowdown of local jobs. For parallel computing, we show that the Linger-Longer policy outperforms reconfiguration strategies when the processor utilization by the local process is 20 percent or less in both synthetic bulk synchronous and real data-parallel applications
Keywords: cluster of workstations; Computer networks; Concurrent computing; Contracts; Delay; fine-grained availability; Intelligent networks; Linger-Longer; networks of workstations; PARALLEL PROCESSING; Predictive models; Processor scheduling; Resumes; scheduling policy; Throughput; workload characterization; workstation clusters; Workstations

Extending understanding of federal statistics in tables - Marchionini,Gary; Hert,Carol; Liddy,Liz; Shneiderman, Ben (Proceedings of the 2000 annual national conference on Digital government research, 2000)
This paper describes progress toward improving user interfaces for US Federal government statistics that are presented in tables. Based on studies of user behaviors and needs related to statistical tables, we describe interfaces to assist diverse users with a range of statistical literacy to explore, find, understand, and use US Federal government statistics.
Keywords: data exploration; dynamic queries; Statistics; tablular data; User interfaces

Facilitating data exploration with query previews: A study of user performance and preference - Tanin,Egemen; Lotem,Amnon; Haddadin,Ihab; Shneiderman, Ben; Plaisant, Catherine; Slaughter,Laura (Behaviour & Information Technology, 2000)
Networked and local data exploration systems that use command languages, menus, or form fill-in interfaces rarely give users an indication of the distribution of data. This often leads users to waste time, posing queries that have zero-hit or mega-hit results. Query previews are a novel visual approach for browsing databases. Query previews supply users with data distribution information for selected attributes of the database, and give continuous feedback about the size of the result set as the query is being formed. Subsequent refinements might be necessary to narrow the search. As there is a risk that query previews are an additional step, leading to a more complex and slow search process, a within-subjects empirical study was ran with 12 subjects who used interfaces with and without query previews and with minimized network delays. Even with 12 subjects and minimized network delays statistically significant differences were found, showing that query previews could speed up performance 1.6 to 2.1 times and lead to higher user satisfaction.Networked and local data exploration systems that use command languages, menus, or form fill-in interfaces rarely give users an indication of the distribution of data. This often leads users to waste time, posing queries that have zero-hit or mega-hit results. Query previews are a novel visual approach for browsing databases. Query previews supply users with data distribution information for selected attributes of the database, and give continuous feedback about the size of the result set as the query is being formed. Subsequent refinements might be necessary to narrow the search. As there is a risk that query previews are an additional step, leading to a more complex and slow search process, a within-subjects empirical study was ran with 12 subjects who used interfaces with and without query previews and with minimized network delays. Even with 12 subjects and minimized network delays statistically significant differences were found, showing that query previews could speed up performance 1.6 to 2.1 times and lead to higher user satisfaction.

The genome sequence of Drosophila melanogaster - Adams,M.D.; Celniker,S.E.; Holt,R.A.; Evans,C.A.; Gocayne,J.D.; Amanatides,P.G.; Scherer,S.E.; Li,P.W.; Hoskins,R.A.; Galle,R.F.; others (Science, 2000)
The fly Drosophila melanogaster is one of the most intensively studied organisms in biology and serves as a model system for the investigation of many developmental and cellular processes common to higher eukaryotes, including humans. We have determined the nucleotide sequence of nearly all of the ∼120-megabase euchromatic portion of theDrosophila genome using a whole-genome shotgun sequencing strategy supported by extensive clone-based sequence and a high-quality bacterial artificial chromosome physical map. Efforts are under way to close the remaining gaps; however, the sequence is of sufficient accuracy and contiguity to be declared substantially complete and to support an initial analysis of genome structure and preliminary gene annotation and interpretation. The genome encodes ∼13,600 genes, somewhat fewer than the smaller Caenorhabditis elegansgenome, but with comparable functional diversity.

Geo-registration of Landsat data by robust matching of wavelet features - Le Moigne,J.; Netanyahu,N. S; Masek,J. G; Mount, Dave; Goward,S.; Honzak,M. (Geoscience and Remote Sensing Symposium, 2000. Proceedings. IGARSS 2000. IEEE 2000 International, 2000)
The goal of our project is to build an operational system, which will provide a sub-pixel accuracy registration of Landsat-5 and Landsat-7 data. Integrated within an automated mass processing/analysis system for Landsat data (REALM), the input to our registration method consists of scenes that have been geometrically and radiometrically corrected, as well as pre-processed for the detection of clouds and cloud shadows. Such pre-processed scenes are then geo-registered relative to a database of Landsat chips. This paper describes our registration process, including the use of a database of landmark chips, a feature extraction performed by an overcomplete wavelet representation, and feature matching using statistically robust techniques. Knowing the approximate longitudes and latitudes of the four corners of the scene, a subset of chips which represent landmarks included in the scene are extracted from the database. For each of these selected landmark chips, a corresponding window is extracted from the scene, and each chip-window pair is registered using our robust wavelet feature matching. First results and future directions are presented in the paper
Keywords: atmospheric techniques; automated mass processing/analysis system; chip-window pair; cloud shadows; Clouds; Feature extraction; feature matching; geo-registration; geometrically corrected scene; geophysical signal processing; Image matching; image registration; landmark chips; Landsat chips; Landsat data; Landsat-5 data; Landsat-7 data; overcomplete wavelet representation; pre-processed scenes; radiometrically corrected scene; REALM; Remote sensing; robust matching; robust wavelet feature matching; scenes; statistically robust techniques; sub-pixel accuracy registration; wavelet features; Wavelet transforms; window

Ligand-Receptor Pairing Via Tree Comparison - Bafna,Vineet; Hannenhalli, Sridhar; Rice,Ken; Vawter,Lisa (Journal of Computational Biology, 2000)
This paper introduces a novel class of tree comparison problems strongly motivated by an important and cost intensive step in drug discovery pipeline viz., mapping cell bound receptors to the ligands they bind to and vice versa. Tree comparison studies motivated by problems such as virus-host tree comparison, gene-species tree comparison and consensus tree problem have been reported. None of these studies are applicable in our context because in all these problems, there is a well-defined mapping of the nodes the trees are built on across the set of trees being compared. A new class of tree comparison problems arises in cases where finding the correspondence among the nodes of the trees being compared is itself the problem. The problem arises while trying to find the interclass correspondence between the members of a pair of coevolving classes, e.g., cell bound receptors and their ligands. Given the evolution of the two classes, the combinatorial problem is to find a mapping among the leaves of the two trees that optimizes a given cost function. In this work we formulate various combinatorial optimization problems motivated by the aforementioned biological problem for the first time. We present hardness results, give an efficient algorithm for a restriction of the problem and demonstrate its applicability.

Numerical simulation of small-signal microwave performance of 4H–SiC MESFET - Huang,Mingwei; Mayergoyz, Issak D; Goldsman,Neil (Solid-State Electronics, 2000)
Small-signal high frequency characteristics of 4H–SiC MESFET has been studied by using two-dimensional numerical drift-diffusion model in frequency domain. Non-ideal Schottky boundary conditions have been introduced that take into account a thin interfacial layer and interface energy states. It has been demonstrated that the 10 dB/dec small-signal current gain roll-off can be attributed to the existence of high density interface states at the metal–semiconductor interface. It has been found that as the gate length is reduced to 0.1 μm, fT and fmax may reach as high as 30 and 62 GHz, respectively.

Performance Benefits of Simultaneous Over Sequential Menus as Task Complexity Increases - Hochheiser,Harry; Shneiderman, Ben (International Journal of Human-Computer Interaction, 2000)
To date, experimental comparisons of menu layouts have concentrated on variants of hierarchical structures of sequentially presented menus. Simultaneous menus-layouts that present multiple active menus on a screen at the same time-are an alternative arrangement that may be useful in many Web design situations. This article describes an experiment involving a between-subject comparison of simultaneous menus and their traditional sequential counterparts. A total of 20 experienced Web users used either simultaneous or sequential menus in a standard Web browser to answer questions based on U.S. Census data. Our results suggest that appropriate use of simultaneous menus can lead to improved task performance speeds without harming subjective satisfaction measures. For novice users performing simple tasks, the simplicity of sequential menus appears to be helpful, but experienced users performing complex tasks may benefit from simultaneous menus. Design improvements can amplify the benefits of simultaneous menu layouts.To date, experimental comparisons of menu layouts have concentrated on variants of hierarchical structures of sequentially presented menus. Simultaneous menus-layouts that present multiple active menus on a screen at the same time-are an alternative arrangement that may be useful in many Web design situations. This article describes an experiment involving a between-subject comparison of simultaneous menus and their traditional sequential counterparts. A total of 20 experienced Web users used either simultaneous or sequential menus in a standard Web browser to answer questions based on U.S. Census data. Our results suggest that appropriate use of simultaneous menus can lead to improved task performance speeds without harming subjective satisfaction measures. For novice users performing simple tasks, the simplicity of sequential menus appears to be helpful, but experienced users performing complex tasks may benefit from simultaneous menus. Design improvements can amplify the benefits of simultaneous menu layouts.

Resource-aware meta-computing - Hollingsworth, Jeffrey K; Keleher, Peter J.; Ryu, Kyung D. (Emphasizing Distributed SystemsEmphasizing Distributed Systems, 2000)
Meta-computing, is an increasingly popular and useful method of obtaining resources to solve large computational problems. However, meta-computer environments pose a number of unique challenges, many of which have yet to be addressed effectively. Among these are dynamicism in both applications and environments, and heterogeneity at several different levels. This chapter discusses current approaches to these problems, and uses them in the Active Harmony system as a running example. Harmony supports an interface that allows applications to export tuning alternatives to the higher-level system. By exposing different parameters that can be changed at runtime, applications can be automatically adapted to changes in their execution environment caused by other programs, the addition or deletion of nodes, or changes in the availability of resources like communication links. Applications expose not only options, but also expected resource utilization with each option and the effect that the option will have on the application's performance. We discuss how this flexibility can be used to tune the overall performance of a collection of applications in a system.

A Review of Current Routing Protocols for Ad Hoc - Royer,E.M.; Toh,C.K.; Hicks, Michael W.; Kakkar,P.; Moore,J. T; Hicks, Michael W.; Moore,J. T; Alexander,D. S; Gunter,C. A; Nettles,S.; others (IEEE Personal Communications, 2000)

Safe and Flexible Dynamic Linking of Native Code - Crary,Karl; Hicks, Michael W.; Weirich,Stephanie (Technical Reports (CIS), 2000)
We present the design and implementation of a framework for flexible and safe dynamic linking of native code. Our approach extends Typed Assembly Language with a primitive for loading and typechecking code, which is flexible enough to support a variety of linking strategies, but simple enough that it does not significantly expand the trusted computing base. Using this primitive, along with the ability to compute with types, we show that we can program many existing dynamic linking approaches. As a concrete demonstration, we have used our framework to implement dynamic linking for a type-safe dialect of C, closely modeled after the standard linking facility for Unix C programs. Aside from the unavoidable cost of verification, our implementation performs comparably with the standard, untyped approach.

Scalable Resource Control in Active Networks - Anagnostakis,Kostas; Hicks, Michael W.; Ioannidis,Sotiris; Keromytis,Angelos; Smith,Jonathan (Active NetworksActive Networks, 2000)
The increased complexity of the service model relative to store-and-forward routers has made resource management one of the paramount concerns in active networking research and engineering. In this paper,we address two major challenges in scaling resource management-to-many-node active networks. The first is the use of market mechanisms and trading amongst nodes and programs with varying degrees of competition and cooperation to provide a scalable approach to managing active network resources. The second is the use of a trust-management architecture to ensure that the participants in the resource management marketplace have a policy-driven “rule of law” in which marketplace decisions can be made and relied upon. We have used lottery scheduling and the Keynote trust-management system for our implementation, for which we provide some initial performance indications.

Speed vs. Accuracy in Simulation for I/O-Intensive Applications - Eom, Hyeonsang; Hollingsworth, Jeffrey K (Parallel and Distributed Processing Symposium, International, 2000)
This paper presents a family of simulators that have been developed for data-intensive applications, and a methodology to select the most efficient one based on a user-supplied requirement for accuracy. The methodology consists of a series of tests that select an appropriate simulation based on the attributes of the application. In addition, each simulator provides two estimates of application execution time: one for the minimum expected time and the other for the maximum. We present the results of applying the strategy to existing applications and show that we can accurately simulate applications tens to hundreds of times faster than application execution time.
Keywords: discrete-event simulation; i/o-intensive applications; parallel or distributed applications; performance prediction; simulation

A Trip Report on Creativity and Cognition 1999: An Insider's Report on a Far Out Conference - Shneiderman, Ben; Hewett,T. (SIGCHI BULLETIN, 2000)

Using hardware performance monitors to isolate memory bottlenecks - Buck, B. R; Hollingsworth, Jeffrey K (Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), 2000)

Visualization 2000 - Ertl,T.; Hamann,B.; Varshney, Amitabh (IEEE Computer Society Press, 2000)

Bacterial Start Site Prediction - Hannenhalli, Sridhar; Hayes,William S; Hatzigeorgiou,Artemis G; Fickett,James W (Nucleic Acids ResearchNucl. Acids Res., 1999)
With the growing number of completely sequenced bacterial genes, accurate gene prediction in bacterial genomes remains an important problem. Although the existing tools predict genes in bacterial genomes with high overall accuracy, their ability to pinpoint the translation start site remains unsatisfactory. In this paper, we present a novel approach to bacterial start site prediction that takes into account multiple features of a potential start site, viz., ribosome binding site (RBS) binding energy, distance of the RBS from the start codon, distance from the beginning of the maximal ORF to the start codon, the start codon itself and the coding/non-coding potential around the start site. Mixed integer programing was used to optimize the discriminatory system. The accuracy of this approach is up to 90%, compared to 70%, using the most common tools in fully automated mode (that is, without expert human post-processing of results). The approach is evaluated using Bacillus subtilis, Escherichia coli and Pyrococcus furiosus. These three genomes cover a broad spectrum of bacterial genomes, since B.subtilis is a Gram-positive bacterium, E.coli is a Gram-negative bacterium and P.furiosus is an archaebacterium. A significant problem is generating a set of ‘true’ start sites for algorithm training, in the absence of experimental work. We found that sequence conservation between P.furiosus and the related Pyrococcus horikoshii clearly delimited the gene start in many cases, providing a sufficient training set.

Binary version management for computational grids - Hollingsworth, Jeffrey K; Miller, E. L; Akala, K. (Parallel processing letters, 1999)

Chunks in PLAN: Language support for programs as packets - Moore,J. T; Hicks, Michael W.; Nettles,S. (PROCEEDINGS OF THE ANNUAL ALLERTON CONFERENCE ON COMMUNICATION CONTROL AND COMPUTING, 1999)

A comparative study of the backbone dynamics of two closely related lipid binding proteins: Bovine heart fatty acid binding protein and porcine ileal lipid binding protein - Lücke,Christian; Fushman, David; Ludwig,Christian; Hamilton,James A.; Sacchettini,James C.; Rüterjans,Heinz (Molecular and Cellular Biochemistry, 1999)
The backbone dynamics of bovine heart fatty acid binding protein (H-FABP) and porcine ileal lipid binding protein (ILBP) were studied by 15N NMR relaxation (T1 and T2) and steady state heteronuclear 15N1H NOE measurements. The microdynamic parameters characterizing the backbone mobility were determined using the ‘model-free’ approach. For H-FABP, the non-terminal backbone amide groups display a rather compact protein structure of low flexibility. In contrast, for ILBP an increased number of backbone amide groups display unusually high internal mobility. Furthermore, the data indicate a higher degree of conformational exchange processes in the µsec-msec time range for ILBP compared to H-FABP. These results suggest significant differences in the conformational stability for these two structurally highly homologous members of the fatty acid binding protein family.
Keywords: Biomedical and Life Sciences

Designing PETS: a personal electronic teller of stories - Druin, Allison; Montemayor,Jamie; Hendler,Jim; McAlister,Britt; Boltman,Angela; Fiterman,Eric; Plaisant,Aurelie; Kruskal,Alex; Olsen,Hanne; Revett,Isabella; Schwenn,Thomas Plaisant; Sumida,Lauren; et al. (Proceedings of the SIGCHI conference on Human factors in computing systems: the CHI is the limit, 1999)
We have begun the development of a new robotic pet that cansupport children in the storytelling process. Children can build their own pet by snapping together the modular animal parts of the PETS robot. After their pet is built, children can tell stories using the My Pets software. These stories can then be acted out by their robotic pet. This video paper describes the motivation for this research and the design process of our intergenerational design team in building the first PETS prototypes. We will discuss our progress to date and our focus for the future.
Keywords: children; cooperative inquiry; design techniques; educational applications; intergenerational design team; PETS; ROBOTICS

Designing practical efficient algorithms for symmetric multiprocessors - Helman,D.; JaJa, Joseph F. (Algorithm Engineering and Experimentation, 1999)
Symmetric multiprocessors (SMPs) dominate the high-end server market and are currently the primary candidate for constructing large scale multiprocessor systems. Yet, the design of efficient parallel algorithms for this platform currently poses several challenges. In this paper, we present a computational model for designing efficient algorithms for symmetric multiprocessors. We then use this model to create efficient solutions to two widely different types of problems - linked list prefix computations and generalized sorting. Our novel algorithm for prefix computations builds upon the sparse ruling set approach of Reid-Miller and Blelloch. Besides being somewhat simpler and requiring nearly half the number of memory accesses, we can bound our complexity with high probability instead of merely on average. Our algorithm for generalized sorting is a modification of our algorithm for sorting by regular sampling on distributed memory architectures. The algorithm is a stable sort which appears to be asymptotically faster than any of the published algorithms for SMPs. Both of our algorithms were implemented in C using POSIX threads and run on four symmetric multiprocessors - the IBM SP-2 (High Node), the HP-Convex Exemplar (S-Class), the DEC AlphaServer, and the Silicon Graphics Power Challenge. We ran our code for each algorithm using a variety of benchmarks which we identified to examine the dependence of our algorithm on memory access patterns. In spite of the fact that the processors must compete for access to main memory, both algorithms still yielded scalable performance up to 16 processors, which was the largest platform available to us. For some problems, our prefix computation algorithm actually matched or exceeded the performance of the standard sequential solution using only a single thread. Similarly, our generalized sorting algorithm always beat the performance of sequential merge sort by at least an order of magnitude, even with a single thread.

Developing the next generation of Earth science data systems: the Global Land Cover Facility - Lindsay,F.E.; Townshend,J.R.G.; JaJa, Joseph F.; Humphries,J.; Plaisant, Catherine; Shneiderman, Ben (Geoscience and Remote Sensing Symposium, 1999. IGARSS '99 Proceedings. IEEE 1999 International, 1999)
A recent initiative by NASA has resulted in the formation of a federation of Earth science data partners. These Earth Science Information Partners (ESIPs) have been tasked with creating novel Earth science data products and services as well as distributing new and existing data sets to the Earth science community and the general public. The University of Maryland established its ESIP activities with the creation of the Global Land Cover Facility (GLCF). This joint effort of the Institute for Advanced Computer Studies (UMIACS) and the Department of Geography has developed an operational data archiving and distribution system aimed at advancing current land cover research efforts. The success of the GLCF is tied closely to assessing user needs as well. As the timely delivery of data products to the research community. This paper discusses the development and implementation of a web-based interface that allows users to query the authors' data holdings and perform user requested processing tasks on demand. The GLCF takes advantage of a scaleable, high performance computing architecture for the manipulation of very large remote sensing data sets and the rapid spatial indexing of multiple format data types. The user interface has been developed with the cooperation of the Human-Computer Interaction Laboratory (HCIL) and demonstrates advances in spatial and temporal querying tools as well as the ability to overlay multiple raster and vector data sets. Their work provides one perspective concerning how critical earth science data may be handled in the near future by a coalition of distributed data centers
Keywords: Computer architecture; data archiving; data distribution system; Data systems; Distributed computing; Earth science data products; Earth science data system; ESIP; geographic information system; geographic information systems; Geography; geophysical measurement technique; geophysical signal processing; geophysical techniques; Geoscience; GIS; GLCF; Global Land Cover Facility; High performance computing; Indexing; information service; Information services; Institute for Advanced Computer Studies; land cover; NASA; next generation; PACS; Remote sensing; terrain mapping; UMIACS; University of Maryland; User interfaces; web-based interface

Exposing Application Alternatives - Keleher, Peter J.; Hollingsworth, Jeffrey K; Perkovic, Dejan (Distributed Computing Systems, International Conference on, 1999)
We present the design of an interface to allow applications to export tuning alternatives to a higher-level system. By exposing different parameters that can be changed at runtime, applications can be made to adapt to changes in their execution environment due to other programs, or the addition or deletion of nodes, communication links etc. An integral part of this interface is that an application not only expose its options, but also the resource utilization of each option and the effect that the option will have on the application's performance. We discuss how these options can be evaluated to tune the overall performance of a collection of applications in the system. Finally, we show preliminary results from a database application that is automatically reconfigured by the system from query shipping to data shipping based on the number of active clients.
Keywords: computational grids; metacomputing; scheduling

Fault injection based on a partial view of the global state of a distributed system - Michel Cukier; Chandra,R.; Henke,D.; Pistole,J.; Sanders,W. H. (1999)
This paper describes the basis for and preliminary implementation of a new fault injector, called Loki, developed specifically for distributed systems. Loki addresses issues related to injecting correlated faults in distributed systems. In Loki, fault injection is performed based on a partial view of the global state of an application. In particular, facilities are provided to pass user-specified state information between nodes to provide a partial view of the global state in order to try to inject complex faults successfully. A post-runtime analysis, using an off-line clock synchronization and a bounding technique, is used to place events and injections on a single global time-line and determine whether the intended faults were properly injected. Finally, observations containing successful fault injections are used to estimate specified dependability measures. In addition to describing the details of our new approach, we present experimental results obtained from a preliminary implementation in order to illustrate Loki's ability to inject complex faults predictably
Keywords: bounding technique; clock synchronization; distributed programming; distributed software systems; fault injection; Loki; post-runtime analysis; program testing; program verification; software reliability; Synchronisation

Gate leakage current simulation by Boltzmann transport equation and its dependence on the gate oxide thickness - Han,Zhiyi; Lin,Chung-Kai; Goldsman,N.; Mayergoyz, Issak D; Yu,S.; Stettler,M. (Simulation of Semiconductor Processes and Devices, 1999. SISPAD '99. 1999 International Conference on, 1999)
As device dimensions shrink toward 0.1 mu;m, gate oxides are becoming so thin that MOSFET gate leakage current and oxide degradation are becoming limiting issues. We provide a more rigorous way to calculate gate leakage current. To achieve this we build upon the Spherical Harmonic Method of modeling, which deterministically solves the Boltzmann equation for an entire device. The method gives the distribution function and is 1000 times faster than MC. Once the distribution function is calculated, the tunneling probability is derived from the first principle WKB method. The barrier lowering effect is accounted for by the method of image charges. We calculate gate leakage current as a function of DC bias. The thermionic and tunneling components are compared at different DC bias points. The dependence of gate leakage current on gate oxide thickness is simulated
Keywords: 30; angstrom; 60; angstrom; Boltzmann; Bias; calculations; leakage; charges; spherical; component; tunneling; current; currents; semiconductor; dependence; method; dependence; MOSFET; barrier; device; effect; distribution; equation; DC; equation; MOSFET; WKB; function; first; harmonic; image; leakage; lowering; method; method; gate; model; thermionic; models; tunnelling; of; oxide; principle; probability; Boltzmann; simulation; gate; thickness; transport; WKB

Imprecise Calendars: an Approach to Scheduling Computational Grids - Hollingsworth, Jeffrey K; Maneewongvatana, Songrit (Distributed Computing Systems, International Conference on, 1999)
We describe imprecise calendars, a way to organize and schedule clusters of nodes in a computation grid. Imprecise calendars permit the easy and efficient sharing of resources between different clusters of computers that are part of a computational grid. In addition, they can be used to provide specific time reservations for applications. We describe the algorithms and policies for manipulation of imprecise calendars. We also include a series of simulation studies that compare our approach to previous batch scheduling systems for both a single cluster and collection of clusters up to over 3,000 nodes.
Keywords: parallel computing distributed scheduling computational grid batch scheduler meta computing

Machine Translation - Bel,N.; Dorr, Bonnie J; Hovy,E.; Knight,K.; Iida,H.; Boitet,C.; Maegaard,B.; Wilks,Y. (Multilingual Information Management: Current Levels and Future Abilities, 1999)

Network Programming Using PLAN - Hicks, Michael W.; Kakkar,Pankaj; Moore,Jonathan; Gunter,Carl; Nettles,Scott (Internet Programming LanguagesInternet Programming Languages, 1999)
We present here a methodology for programming active networks in the environment defined by our new language PLAN (Packet Language for Active Networks). This environment presumes a two-level architecture consisting of: 1. active packets carrying PLAN code; and 2. downloadable, node-resident services written in more general-purpose languages. We present several examples which illustrate how these two features can be combined to implement various network functions.

Perceptual Organization in Computer Vision - Boyer,K.L.; Sarkar,S.; Feldman,J.; Granlund,G.; Horaud,R.; Hutchinson,S.; Jacobs, David W.; Kak,A.; Lowe,D.; Malik,J. (Academic Press, 1999)

PLAN: A programming language for active networks - Hicks, Michael W.; Kakkar,P.; Moore,J. T; Gunter,C. A; Nettles,S. (ACM SIGPLAN NOTICES, 1999)
PLAN (Programming Language for Active Networks) is anew language for programs that are carried in the packets of a programmable network. PLAN programs replace the packet headers (which can be viewed as `dumb' programs) used in current networks. As a header replacement, PLAN programs must be lightweight and of limited functionality. These limitations are mitigated by allowing PLAN code to call service routines written in other, more powerful lan- guages. These service routines may also be loaded into the routers dynamically. This two-level architecture, in which PLAN serves as a scripting or `glue' language for more gen- eral services, is the primary contribution of the paper. PLAN is a strict functional language providing a limited set of primitives and datatypes. PLAN de nes primitives for remotely executing PLAN programs on other nodes, and these primitives are used to provide basic data transport in the network. Because remote execution makes debugging di cult, PLAN provides strong static guarantees to the pro- grammer, such as type safety. A more novel property aimed at protecting network availability is a guarantee that PLAN programs use a bounded amount of space and time on active routers and bandwidth in the network.

PLAN Service Programmer's Guide for PLAN version 3.2 - Hicks, Michael W. (University of Pennsylvania, 1999)

PLANet: an active internetwork - Hicks, Michael W.; Moore,J. T; Alexander,D. S; Gunter,C. A; Nettles,S. M (IEEE INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, 1999)
We present PLANet: an active network architecture and implementation. In addition to a standard suite of Internet-like services, PLANet has two key programmability features: (1) all packets contain programs; and (2) router functionality may be extended dynamically. Packet programs are written in our special purpose programming language PLAN, the Packet Language for Active Networks, while dynamic router extensions are written in OCaml, a dialect of ML. Currently, PLANet routers run as byte-code-interpreted Linux user-space applications, and support Ethernet and IP as link layers. PLANet achieves respectable performance on standard networking operations: on 300 MHz Pentium-II's attached to 100 Mbps Ethernet, PLANet can route 48 Mbps and switch over 5000 packets per second. We demonstrate the utility of PLANet's activeness by showing experimentally how it can nontrivially improve application and aggregate network performance in congested conditions
Keywords: 100 Mbit/s; 300 MHz; 48 Mbit/s; active internetwork; active network architecture; active network implementation; byte-code-interpreted applications; Computer architecture; Computer languages; Computer networks; congested conditions; dynamic programming; dynamic router extensions; Ethernet; Ethernet networks; INFORMATION SCIENCE; Internet; Internet-like services; internetworking; IP; IP networks; link layers; Linux user-space applications; Local area networks; ML dialect; Network performance; networking operations; OCaml; Packet Language for Active Networks; packet programs; packet switching; Pentium-II; performance; performance evaluation; PLAN; PLANet; Planets; programmability features; programming languages; router functionality; special purpose programming language; Switches; telecommunication network routing; Transport protocols; Web and internet services

Predicting the CPU availability of time-shared Unix systems on the computational grid - Wolski,R.; Spring, Neil; Hayes,J. (The Eighth International Symposium on High Performance Distributed Computing, 1999. Proceedings, 1999)
Focuses on the problem of making short- and medium-term forecasts of CPU availability on time-shared Unix systems. We evaluate the accuracy with which availability can be measured using the Unix load average, the Unix utility “vmstat” and the Network Weather Service (NWS) CPU sensor that uses both. We also examine the autocorrelation between successive CPU measurements to determine their degree of self-similarity. While our observations show a long-range autocorrelation dependence, we demonstrate how this dependence manifests itself in the short- and medium-term predictability of the CPU resources in our study
Keywords: accuracy; Application software; Autocorrelation; Availability; Central Processing Unit; computational grid; correlation methods; CPU availability prediction; CPU resources predictability; CPU sensor; Dynamic scheduling; grid computing; Load forecasting; long-range autocorrelation dependence; medium-term forecasts; network operating systems; Network Weather Service; NWS; performance evaluation; self-similarity degree; short-term forecasts; successive CPU measurements; Time measurement; Time sharing computer systems; time-shared Unix systems; time-sharing systems; Unix; Unix load average; vmstat utility; Weather forecasting

Prefix computations on symmetric multiprocessors - Helman,D.R.; JaJa, Joseph F. (Parallel and Distributed Processing, 1999. 13th International and 10th Symposium on Parallel and Distributed Processing, 1999. 1999 IPPS/SPDP. Proceedings, 1999)
We introduce a new optimal prefix computation algorithm on linked lists which builds upon the sparse ruling set approach of Reid-Miller and Blelloch. Besides being somewhat simpler and requiring nearly half the number of memory accesses, we can bound our complexity with high probability instead of merely on average. Moreover, whereas Reid-Miller and Blelloch (1996) targeted their algorithm for implementation on a vector multiprocessor architecture, we develop our algorithm for implementation on the symmetric multiprocessor architecture (SMP). These symmetric multiprocessors dominate the high-end server market and are currently the primary candidate for constructing large scale multiprocessor systems. Our prefix computation algorithm was implemented in C using POSIX threads and run on four symmetric multiprocessors-the IBM SP-2 (High Node), the HP-Convex Exemplar (S-Class), the DEC AlphaServer; and the Silicon Graphics Power Challenge. We ran our code using a variety of benchmarks which we identified to examine the dependence of our algorithm on memory access patterns. For some problems, our algorithm actually matched or exceeded the performance of the standard sequential solution using only a single thread. Moreover, in spite of the fact that the processors must compete for access to main memory, our algorithm still achieved scalable performance with up to 16 processors, which was the largest platform available to us
Keywords: access; algorithms; AlphaServer; HP-Convex; approach; symmetric; architecture; symmetric; Challenge; high-end; computations; scalable; DEC; Exemplar; IBM; Graphics; market; large; multiprocessor; multiprocessors; Unix; distributed; patterns; prefix; performance; sparse; power; ruling; scale; server; set; SP-2; POSIX; systems; memory; threads; Silicon

A real-time audio–video front-end for multimedia applications - Zotkin,Dmitry N; Duraiswami, Ramani; Hariatoglu,I.; Davis, Larry S.; Otsuka,T. (The Journal of the Acoustical Society of America, 1999)

Refining query previews techniques for data with multivalued attributes: the case of NASA EOSDIS - Plaisant, Catherine; Venkatraman,M.; Ngamkajorwiwat,K.; Barth,R.; Harberts,B.; Feng,Wenlan (Research and Technology Advances in Digital Libraries, 1999. ADL '99. Proceedings. IEEE Forum on, 1999)
Query Previews allow users to rapidly gain an understanding of the content and scope of a digital data collection. These previews present overviews of abstracted metadata, enabling users to rapidly and dynamically avoid undesired data. We present our recent work on developing query previews for a variety of NASA EOSDIS situations. We focus on approaches that successfully address the challenge of multi-valued attribute data. Memory requirements and processing time associated with running these new solutions remain independent of the number of records in the dataset. We describe two techniques and their respective prototypes used to preview NASA Earth science data
Keywords: attribute; attributes; processing; collection; memory; computing; meta; data; data; abstracted; data; digital; data; multivalued; data; query; Earth; EOSDIS; NASA; libraries; geophysics; metadata; dataset; digital; NASA; previews; processing; requirements; multi-valued; Science; techniques; undesired; time; query

Specifying the PLAN Network Programming Langauge - Kakkar,Pankaj; Hicks, Michael W.; Moore,Jon; Gunter,Carl A. (Electronic Notes in Theoretical Computer Science, 1999)
We discuss how the specification of the PLAN programming language supports the design objectives of the language. The specification aims to provide a mathematically precise operational semantics that can serve as a standard for implementing interpreters and portable programs. The semantics should also support proofs of key properties of PLAN that would hold of all conformant implementations. This paper discusses two such properties. (1) Type checking is required, but interpreters are given significant flexibility about when types are checked; the specification must support a clear description of the possible behaviors of a network of conformant implementations. (2) It is essential to have guarantees about how PLAN programs use global resources, but the specification must be flexible about extensions in the network service layer. We illustrate on of kind of issue that will arise in using to specification to prove properties of the network based on the choice of services.

A Study of the Structure of the Web - Deshpande, Amol; Huang,R.; Raman,V.; Riggs,T.; Song,D.; Subramanian,L. (University of California, Berkeley, 1999)
The World Wide Web is a huge, growing repository of information on a wide range of topics. It is alsobecoming important, commercially and sociologically, as a place of human interaction within different communities. In this paper we present an experimental study of the structure of the Web. We analyze link topologies of various communities, and patterns of mirroring of content, on 1997 and 1999 snapshots of the Web. Our results give insight into patterns of interaction within communities and how they evolve, as well as patterns of data replication. We also describe the techniques we have developed for performing complex processing on this large data set, and our experiences in doing so. We present new algorithms for finding partial and complete mirrors in URL hierarchies; these are also of independent interest for search and redirection. In order to study and visualize link topologies of different communities, we have developed techniques to compact these large link graphs without much information loss.

Temporal visualization for legal case histories - Harris,C.; Allen,R.B.; Plaisant, Catherine; Shneiderman, Ben (PROCEEDINGS OF THE ANNUAL MEETING-AMERICAN SOCIETY FOR INFORMATION SCIENCE, 1999)
This paper discusses visualization of legal information using a tool for temporal information called LifeLines. The direct and indirect histories of cases can become very complex. We explored ways that LifeLines could aid in viewing the links between the original case and the direct and indirect histories. The Apple Computer, Inc. v. Microsoft Corporation and Hewlett Packard Company case is used to illustrate the prototype. For example, if users want to find out how the rulings or statutes changed throughout this case, they could retrieve this information within a single display. Using the timeline, users could also choose at which point in time they would like to begin viewing the case. LifeLines support various views of a case's history. For instance, users can view the trial history of a case, the references involved in a case, and citations made to a case. The paper describes improvements to LifeLines that could help in providing a more useful visualization of case history.

Tikhonov Regularization and Total Least Squares - Golub, Gene H.; Hansen,Per Christian; O'Leary, Dianne P. (SIAM Journal on Matrix Analysis and Applications, 1999)
Discretizations of inverse problems lead to systems of linear equations with a highly ill-conditioned coefficient matrix, and in order to computestable solutions to these systems it is necessary to apply regularization methods. We show how Tikhonov's regularization method, which in its original formulation involves a least squares problem, can be recast in a total least squares formulation suited for problems in which both the coefficient matrix and the right-hand side are known only approximately. We analyze the regularizing properties of this method and demonstrate by a numerical example that, in certain cases with large perturbations, the new method is superior to standard regularization methods.
Keywords: bidiagonalization; discrete ill-posed problems; regularization; total least squares

Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals - Hannenhalli, Sridhar; Pevzner,Pavel A. (J. ACM, 1999)
Genomes frequently evolve by reversals &rgr;(i,j) that transform a gene order &pgr;1 … &pgr;i&pgr;i+1 … &pgr;j-1&pgr;j … &pgr;n into &pgr;1 … &pgr;i&pgr;j-1 … &pgr;i+1&pgr;j … &pgr;n. Reversal distance between permutations &pgr; and &sgr;is the minimum number of reversals to transform &pgr; into &Agr;. Analysis of genome rearrangements in molecular biology started in the late 1930's, when Dobzhansky and Sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of Drosophilia. Analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. We study sorting of signed permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial DNA. The previously suggested approximation algorithms for sorting signed permutations by reversals compute the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. We prove a duality theorem explaining this intriguing performance and show that there exists a “hidden” parameter that allows one to compute the reversal distance between signed permutations in polynomial time.
Keywords: Computational Biology; Genetics

Transparent communication for distributed objects in Java - Hicks, Michael W.; Jagannathan,Suresh; Kelsey,Richard; Moore,Jonathan T.; Ungureanu,Cristian (Proceedings of the ACM 1999 conference on Java Grande, 1999)

Understanding Patterns of User Visits to Web Sites: Interactive Starfield Visualization of WWW Log Data-Short Version - Hochheiser,H.; Shneiderman, Ben (Tech Report HCIL-99-06, 1999)
HTTP server log files provide Web site operators with substantial detail regarding the visitors to their sites. Interest in interpreting this data has spawned an active market for software packages that summarize and analyze this data, providing histograms, pie graphs, and other charts summarizing usage patterns. While useful, these summaries obscure useful information and restrict users to passive interpretation of static displays.Interactive starfield visualizations can be used to provide users with greater abilities to interpret and explore web log data. By combining two-dimensional displays of thousands of individual access requests, color and size coding for additional attributes, and facilities for zooming and filtering, these visualizations provide capabilities for examining data that exceed those of traditional web log analysis tools. We introduce a series of interactive starfield visualizations, which can be used to explore server data across various dimensions. Possible uses of these visualizations are discussed, and difficulties of data collection, presentation, and interpretation are explored.

Using Interactive Visualizations of WWW Log Data to Characterize Access Patterns and Inform Site Design - Hochheiser,Harry; Shneiderman, Ben (Institute for Systems Research Technical Reports, 1999)
HTTP server log files provide Web site operators with substantial detail regarding the visitors to their sites. Interest ininterpreting this data has spawned an active market for software packages that summarize and analyze this data, providing histograms, pie graphs, and other charts summarizing usage patterns. While useful, these summaries obscureuseful information and restrict users to passive interpretation of static displays. Interactive visualizations can be used to provide users with greater abilities to interpret and explore web log data. Bycombining two-dimensional displays of thousands of individual access requests, color and size coding for additional attributes, and facilities for zooming and filtering, these visualizations provide capabilities for examining data that exceed those of traditional web log analysis tools. We introduce a series of interactive visualizations that can be used to explore server data across various dimensions. Sample visualizations of server data from two web sites are presented. Coordinated, snap-together visualizations (STVs) of log data are introduced as a means of gaining additional expressive power. Possible uses of these visualizations are discussed, and difficulties of data collection, presentation, and interpretation are explored.
Keywords: Information Visualization; log file analysis; World Wide Web

AQuA: an adaptive architecture that provides dependable distributed objects - Cukier, Michel; Ren,J.; Sabnis,C.; Henke,D.; Pistole,J.; Sanders,W. H.; Bakken,D. E.; Berman,M.E.; Karr,D. A.; Schantz,R.E. (Seventeenth IEEE Symposium on Reliable Distributed Systems, 1998)
Dependable distributed systems are difficult to build. This is particularly true if they have dependability requirements that change during the execution of an application, and are built with commercial off-the-shelf hardware. In that case, fault tolerance must be achieved using middleware software, and mechanisms must be provided to communicate the dependability requirements of a distributed application to the system and to adapt the system's configuration to try to achieve the desired dependability. The AQuA architecture allows distributed applications to request a desired level of availability using the Quality Objects (QuO) framework and includes a dependability manager that attempts to meet requested availability levels by configuring the system in response to outside requests and changes in system resources due to faults. The AQuA architecture uses the QuO runtime to process and invoke availability requests, the Proteus dependability manager to configure the system in response to faults and availability requests, and the Ensemble protocol stack to provide group communication services. Furthermore, a CORBA interface is provided to application objects using the AQuA gateway. The gateway provides a mechanism to translate between process-level communication, as supported by Ensemble, and IIOP messages, understood by Object Request Brokers. Both active and passive replication are supported, and the replication type to use is chosen based on the performance and dependability requirements of particular distributed applications
Keywords: adaptive architecture; AQuA; availability requests; client-server systems; commercial off-the-shelf hardware; CORBA; dependability manager; dependability requirements; dependable distributed objects; distributed object management; Ensemble protocol stack; Fault tolerance; group communication services; middleware software; Object Request Brokers; process-level communication; proteus; Quality Objects; replication; software fault tolerance; Software quality

Benchmarking a network of PCs running parallel applications - Hollingsworth, Jeffrey K; Guven, E.; Akinlar, C. (Performance, Computing and Communications, 1998. IPCCC '98., IEEE International, 1998)
Presents a benchmarking study that compares the performance of a network of four PCs connected by a 100 Mbit/s fast Ethernet running three different system software configurations: TCP/IP on Windows NT, TCP/IP on Linux and a lightweight message-passing protocol (U-Net active messages) on Linux. For each configuration, we report results for communication micro-benchmarks and the NAS (Numerical Aerodynamics Simulation) parallel benchmarks. For the NAS benchmarks, the overall running time using Linux TCP/IP was 12-500% less than the Windows NT TCP/IP configuration. Likewise, the Linux U-Net based message-passing protocol outperformed the Linux TCP/IP version by 5-200%+. We also show that, by using Linux U-Net, we are able to achieve 125 μs latency between two processes using PVM. Finally, we report that the default mathematical libraries supplied with NT (for both gcc and Visual C++) are substantially slower than the one supplied with Linux
Keywords: 100 Mbit/s; 125 mus; Aerodynamics; Application software; communication micro-benchmarks; default mathematical libraries; Delay; Ethernet; Ethernet networks; gcc; latency; lightweight message-passing protocol; Linux; Local area networks; mathematics computing; Message passing; microcomputer applications; Microsoft Windows NT; NAS parallel benchmarks; network operating systems; Numerical simulation; parallel applications; PARALLEL PROCESSING; PC network benchmarking; performance comparison; performance evaluation; Personal communication networks; Protocols; PVM; running time; software libraries; System software; system software configurations; TCP/IP; TCPIP; Transport protocols; U-Net active messages; Visual C++

A Comparative Study of Knowledge-Based Approaches for Cross-Language - Oard, Douglas; Dorr, Bonnie J; Hackett,P.; Katsova,M. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 1998)
Cross-language retrieval systems seek to use queries in one natural language to guide theretrieval of documents that might be written in another. Acquisition and representation of translation knowledge plays a central role in this process. This paper explores the util- ity of two sources of manually encoded translation knowledge, bilingual dictionaries and translation lexicons, for cross-language retrieval. We have implemented six query trans- lation techniques that use bilingual dictionaries, one based on lexical-semantic analysis, and one based on direct use of the translation output from an existing machine transla- tion system; these are compared with a document translation technique that uses output from the same existing translation system. Average precision measures on portions of the TREC collection suggest that arbitrarily selecting a single translation from a bilingual dictionary is typically no less effective than using every translation in the dictionary, that query translation using an existing machine translation system can achieve some- what better effectiveness than simple dictionary-based techniques, and that performing document translation rather than query translation may result in further improvements in retrieval effectiveness under some conditions.

Critical path profiling of message passing and shared-memory programs - Hollingsworth, Jeffrey K (IEEE Transactions on Parallel and Distributed Systems, 1998)
We introduce a runtime, nontrace-based algorithm to compute the critical path profile of the execution of message passing and shared-memory parallel programs. Our algorithm permits starting or stopping the critical path computation during program execution and reporting intermediate values. We also present an online algorithm to compute a variant of critical path, called critical path zeroing, that measures the reduction in application execution time that improving a selected procedure will have. Finally, we present a brief case study to quantify the runtime overhead of our algorithm and to show that online critical path profiling can be used to find program bottlenecks
Keywords: Computer Society; Concurrent computing; critical path computation; critical path profile; critical path zeroing; distributed processing; distributed shared memory systems; Instruments; Message passing; Monitoring; online algorithm; online critical path profiling; Parallel algorithms; program bottlenecks; Runtime; runtime nontrace-based algorithm; runtime overhead; shared-memory programs; system monitoring; Time measurement; Yarn

De-amortization of Algorithms - Rao Kosaraju,S.; Pop, Mihai (Computing and CombinatoricsComputing and Combinatorics, 1998)
De-amortization aims to convert algorithms with excellent overall speed, f ( n ) for performing n operations, into algorithms that take no more than O ( f ( n )/ n ) steps for each operation. The paper reviews several existing techniques for de-amortization of algorithms.

The Design of a Telepathology Workstation: Exploring Remote Images - Carr,David; Plaisant, Catherine; Hasegawa,Hiroaki (Technical Reports of the Computer Science Department, 1998)
Dynamic telepathology uses a tele-operated microscope to allowpathologists to view samples at a remote location. However, time delays introduced by remote operation have made use of a commercial dynamic telepathology system difficult and frustrating. This paper describes experiments to evaluate and redesign the user interface. We also make recomendations for further automation to support the pathology process and increase the usefulness of the system. Copyright, 1994, by David Carr, Catherine Plaisant, and Hiroaki Hasegawa All rights reserved (Also cross-referenced as CAR-TR-708)
Keywords: Technical Report

Designing a real-time telepathology workstation to mitigate communication delays - Carr,David; Plaisant, Catherine; Hasegawa,Hiroaki (Interacting with Computers, 1998)
Dynamic telepathology uses a teleoperated microscope to allow pathologists to view samples at a remote location. However, time delays introduced by remote operation have made use of a commercial dynamic telepathology system difficult and frustrating. This paper describes the iterative redesign of the user interface. We redesigned the interface, conducted experiments to evaluate the improvements, and then redesigned the user interface based on the results.Our work shows that predictive displays and local maps improve user control of the microscope and increase user comfort with the system. It also indicates that some degree of automation is necessary to support the navigation process and increase the overall usefulness of the system. Therefore, we also make recommendations for further automation to support the telepathology process and increase the usefulness of the system. While performed on a specific device using a dedicated communications system, the same problems would be encountered in other environments. For example, Internet-based systems that enable remote control or require browsing of large images will need to compensate for time delays and can benefit from our experience with the telepathology application.
Keywords: Iterative design; Predictive displays; Remote control; Supervisory control; Telepathology; Time delays

Designing to facilitate browsing: A look back at the Hyperties workstation browser - Shneiderman, Ben; Plaisant, Catherine; Botafogo,Rodrigo; Hopkins,Don; Weiland,William (Technical Reports of the Computer Science Department, University of Maryland, 1998)
Since browsing hypertext can present a formidable cognitivechallenge, user interface design plays a major role in determining acceptability. In the Unix workstation version of Hyperties, a research-oriented prototype, we focussed on design features that facilitate browsing. We first give a general overview of Hyperties and its markup language. Customizable documents can be generated by the conditional text feature that enables dynamic and selective display of text and graphics. In addition we present: - an innovative solution to link identification: pop-out graphical buttons of arbitrary shape. - application of pie menus to permit low cognitive load actions that reduce the distraction of common actions, such as page turning or window selection. - multiple window selection strategies that reduce clutter and housekeeping effort. We preferred piles-of-tiles, in which standard-sized windows were arranged in a consistent pattern on the display and actions could be done rapidly, allowing users to concentrate on the contents. (Also cross-referenced as CAR-TR-494)
Keywords: Technical Report

Enhancing Automatic Acquisition of Thematic Structure in a Large-Scale Lexicon for Mandarin Chinese - Olsen,Mari; Dorr, Bonnie J; Thomas,Scott (Machine Translation and the Information SoupMachine Translation and the Information Soup, 1998)
This paper describes a refinement to our procedure for porting lexical conceptual structure (LCS) into new languages. Specifically we describe a two-step process for creating candidate thematic grids for Mandarin Chinese verbs, using the English verb heading the VP in the subde_nitions to separate senses, and roughly parsing the verb complement structure to match thematic structure templates. We accomplished a substantial reduction in manual effort, without substantive loss. The procedure is part of a larger process of creating a usable lexicon for interlingual machine translation from a large on-line resource with both too much and too little information.

Facilitating Network Data Exploration with Query Previews: A Study of User Performance and Preference - Tanin,Egemen; Lotem,Amnon; Haddadin,Ihab; Shneiderman, Ben; Plaisant, Catherine; Slaughter,Laura (Technical Reports of the Computer Science Department, 1998)
Current network data exploration systems which use command languages (e.g.SQL) or form fill-in interfaces fail to give users an indication of the distribution of data items. This leads many users to waste time posing queries which have zero-hit or mega-hit result sets. Query previewing is a novel visual approach for browsing huge networked information warehouses. 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. Our within-subjects empirical comparison studied 12 subjects using a form fill-in interface with and without query previews. We found statistically significant differences showing that query previews sped up performance 1.6 to 2.1 times and led to higher subjective satisfaction. (Also cross-referenced as UMIACS-98-14)
Keywords: Technical Report

Instrumentation and measurement - Hollingsworth, Jeffrey K; Miller, B. (The grid, 1998)

LBF: a performance metric for program reorganization - Eom, H.; Hollingsworth, Jeffrey K (18th International Conference on Distributed Computing Systems, 1998. Proceedings, 1998)
We introduce a new performance metric, called Load Balancing Factor (LBF), to assist programmers with evaluating different tuning alternatives. The LBF metric differs from traditional performance metrics since it is intended to measure the performance implications of a specific tuning alternative rather than quantifying where time is spent in the current version of the program. A second unique aspect of the metric is that it provides guidance about moving work within a distributed or parallel program rather than reducing it. A variation of the LBF metric can also be used to predict the performance impact of changing the underlying network. The LBF metric can be computed incrementally and online during the execution of the program to be tuned. We also present a case study that shows that our metric can predict the actual performance gains accurately for a test suite of six programs
Keywords: case study; Computational modeling; computer network; Computer science; Debugging; distributed processing; distributed program; Educational institutions; Integrated circuit testing; LBF metric; load balancing factor; Load management; measurement; NIST; parallel program; parallel programming; performance metric; program reorganization; program tuning; Programming profession; resource allocation; software metrics; software performance evaluation; US Department of Energy

Lexical Selection for Cross-Language Applications: Combining LCS with WordNet - Dorr, Bonnie J; Katsova,Maria (Machine Translation and the Information SoupMachine Translation and the Information Soup, 1998)
This paper describes experiments for testing the power of large-scale resources for lexical selection in machine translation (MT) and cross-language information retrieval (CLIR). We adopt the view that verbs with similar argument structure share certain meaning components, but that those meaning components are more relevant to argument realization than to idiosyncratic verb meaning. We verify this by demonstrating that verbs with similar argument structure as encoded in Lexical Conceptual Structure (LCS) are rarely synonymous in WordNet. We then use the results of this work to guide our implementation of an algorithm for cross-language selection of lexical items, exploiting the strengths of each resource: LCS for semantic structure and WordNet for semantic content. We use the Parka Knowledge-Based System to encode LCS representations and WordNet synonym sets and we implement our lexical-selection algorithm as Parka-based queries into a knowledge base containing both information types.

LifeLines: using visualization to enhance navigation and analysis of patient records - Plaisant, Catherine; Mushlin,R.; Snyder,A.; Li,J.; Heller,D.; Shneiderman, Ben (In Proceedings of the 1998 American Medical Informatic Association Annual Fall SymposiumProc AMIA Symp, 1998)
LifeLines provide a general visualization environment for personal histories. We explore its use for clinical patient records. A Java user interface is described, which presents a one-screen overview of a computerized patient record using timelines. Problems, diagnoses, test results or medications can be represented as dots or horizontal lines. Zooming provides more details; line color and thickness illustrate relationships or significance. The visual display acts as a giant menu, giving direct access to the data.

LifeLines: using visualization to enhance navigation and analysis of patient records. - Plaisant, Catherine; Mushlin,R.; Snyder,A.; Li,J.; Heller,D.; Shneiderman, Ben (Proceedings of the AMIA Symposium, 1998)
LifeLines provide a general visualization environment for personal histories. We explore its use for clinical patient records. A Java user interface is described, which presents a one-screen overview of a computerized patient record using timelines. Problems, diagnoses, test results or medications can be represented as dots or horizontal lines. Zooming provides more details; line color and thickness illustrate relationships or significance. The visual display acts as a giant menu, giving direct access to the data.

Linger longer: Fine-grain cycle stealing for networks of workstations - Ryu, K. D; Hollingsworth, Jeffrey K (Proceedings of the 1998 ACM/IEEE Conference on Supercomputing (CDROM), 1998)

Modeling and evaluating design alternatives for an on-line instrumentation system: a case study - Waheed, A.; Rover, D. T; Hollingsworth, Jeffrey K (IEEE Transactions on Software Engineering, 1998)
This paper demonstrates the use of a model-based evaluation approach for instrumentation systems (ISs). The overall objective of this study is to provide early feedback to tool developers regarding IS overhead and performance; such feedback helps developers make appropriate design decisions about alternative system configurations and task scheduling policies. We consider three types of system architectures: network of workstations (NOW), symmetric multiprocessors (SMP), and massively parallel processing (MPP) systems. We develop a Resource OCCupancy (ROCC) model for an on-line IS for an existing tool and parameterize it for an IBM SP-2 platform. This model is simulated to answer several “what if” questions regarding two policies to schedule instrumentation data forwarding: collect-and-forward (CF) and batch-and-forward (BF). In addition, this study investigates two alternatives for forwarding the instrumentation data: direct and binary tree forwarding for an MPP system. Simulation results indicate that the BF policy can significantly reduce the overhead and that the tree forwarding configuration exhibits desirable scalability characteristics for MPP systems. Initial measurement-based testing results indicate more than 60 percent reduction in the direct IS overhead when the BF policy was added to Paradyn parallel performance measurement tool
Keywords: alternative system configurations; Application software; batch-and-forward; collect-and-forward; Computer aided software engineering; design alternatives; design decisions; Feedback; IBM SP-2 platform; Instruments; massively parallel processing; model-based evaluation approach; Monitoring; multiprocessing programs; on-line instrumentation system; Paradyn parallel performance measurement tool; PARALLEL PROCESSING; Real time systems; scalability characteristics; software metrics; software tools; Space technology; symmetric multiprocessors; system architectures; system monitoring; System testing; task scheduling policies; tool developers; tree forwarding configuration; Workstations

Multiple mechanisms of immune evasion by African trypanosomes - Donelson,John E.; Hill,Kent L.; El‐Sayed, Najib M. (Molecular and Biochemical Parasitology, 1998)
During infection of a mammalian host, African trypanosomes are in constant contact with the host's immune system. These protozoan parasites are infamous for their ability to evade the immune responses by periodically switching their major variant surface glycoprotein (VSG), a phenomenon called antigenic variation. Antigenic variation, however, is likely to be only one of several mechanisms enabling these organisms to thrive in the face of the immune defenses. The ability to grow in high levels of interferon-gamma (IFN-[gamma]) and to avoid complement-mediated destruction may also facilitate the parasite's survival. In this review we summarize (i) the activation of trypanosome genes for three different VSGs during antigenic variation, (ii) the secretion of a trypanosome protein that induces host CD8+ T cells to produce IFN-[gamma], and (iii) the evidence for trypansome protein similar to a surface protease of Leishmania that plays a role in resistance to complement-mediated lysis.
Keywords: Leishmania; Recombinant cloning; T cell; Trypanosomes; VSG genes