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

Computer vision on FPGAs: Design methodology and its application to gesture recognition - Sen,M.; Corretjer,I.; Haim,F.; Saha,S.; Bhattacharyya, Shuvra S.; Schlessman,J.; Wolf,W. (Computer Vision and Pattern Recognition-Workshops, 2005. CVPR Workshops. IEEE Computer Society Conference on, 2005)

Coordinating Overviews and Detail Views of WWW Log Data (2000) - Hochheiser,Harry; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
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.
Keywords: Technical Report

Critical Factors Influencing the Occurrence of Vibrio Cholerae in the Environment of Bangladesh - Huq,Anwar; Sack,R. Bradley; Nizam,Azhar; Longini,Ira M.; Nair,G. Balakrish; Ali,Afsar; Morris,J. Glenn; Khan,M. N. Huda; Siddique,A. Kasem; Yunus,Mohammed; Albert,M. John; Sack,David A.; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2005)
The occurrence of outbreaks of cholera in Africa in 1970 and in Latin America in 1991, mainly in coastal communities, and the appearance of the new serotype Vibrio cholerae O139 in India and subsequently in Bangladesh have stimulated efforts to understand environmental factors influencing the growth and geographic distribution of epidemic Vibrio cholerae serotypes. Because of the severity of recent epidemics, cholera is now being considered by some infectious disease investigators as a “reemerging” disease, prompting new work on the ecology of vibrios. Epidemiological and ecological surveillance for cholera has been under way in four rural, geographically separated locations in Bangladesh for the past 4 years, during which both clinical and environmental samples were collected at biweekly intervals. The clinical epidemiology portion of the research has been published (Sack et al., J. Infect. Dis. 187:96-101, 2003). The results of environmental sampling and analysis of the environmental and clinical data have revealed significant correlations of water temperature, water depth, rainfall, conductivity, and copepod counts with the occurrence of cholera toxin-producing bacteria (presumably V. cholerae). The lag periods between increases or decreases in units of factors, such as temperature and salinity, and occurrence of cholera correlate with biological parameters, e.g., plankton population blooms. The new information on the ecology of V. cholerae is proving useful in developing environmental models for the prediction of cholera epidemics.

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

Data structures for simplicial complexes: an analysis and a comparison - De Floriani, Leila; Hui,Annie (Proceedings of the third Eurographics symposium on Geometry processing, 2005)
In this paper, we review, analyze and compare representations for simplicial complexes. We classify such representations, based on the dimension of the complexes they can encode, into dimension-independent structures, and data structures for three- and for two-dimensional simplicial complexes. We further classify the data structures in each group according to the basic kinds of the topological entities they represent. We present a description of each data structure in terms of the entities and topological relations encoded, and we evaluate it based on its expressive power, on its storage cost and on the efficiency in supporting navigation inside the complex, i.e., in retrieving topological relations not explicitly encoded. We compare the various data structures inside each category based on the above features.

A distributed quadtree index for peer-to-peer settings - Tanin,E.; Harwood,A.; Samet, Hanan (PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON DATA ENGINEERING, 2005)

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

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

Dynamic query tools for time series data sets: Timebox widgets for interactive exploration (2004) - Hochheiser,Harry; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Timeboxes are rectangular widgets that can be used in direct-manipulation graphical user interfaces (GUIs) to specify query constraints on time series data sets. Timeboxes are used to specify simultaneously two sets of constraints: given a set of N time series profiles, a timebox covering time periods x1...x2 (x1rx2) and values y1...y2 (y1ry2) will retrieve only those nAN that have values y1ryry2 during all times x1rxrx2. TimeSearcher is an information visualization tool that combines timebox queries with overview displays, query-byexample facilities, and support for queries over multiple time-varying attributes. Query manipulation tools including pattern inversion and eaders & laggards graphical bookmarks provide additional support for interactive exploration of data sets. Extensions to the basic timebox model that provide additional expressivity include variable time timeboxes, which can be used to express queries with variability in the time interval, and angular queries, which search for ranges of differentials, rather than absolute values. Analysis of the algorithmic requirements for providing dynamic query performance for timebox queries showed that a sequential search outperformed searches based on geometric indices. Design studies helped identify the strengths and weaknesses of the query tools. Extended case studies involving the analysis of two different types of data from molecular biology experiments provided valuable feedback and validated the utility of both the timebox model and the TimeSearcher tool. Timesearcher is available [url=http://www.cs.umd.edu/hcil/ timesearcher]online.[/url]
Keywords: Technical Report

Dynamic Querying for Pattern Identification in Microarray and Genomic Data (2003) - Hochheiser,Harry; Baehrecke,Eric H; Mount, Stephen M.; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
Data sets involving linear ordered sequences are a recurring theme in bioinformatics. Dynamic query tools that support exploration of these data sets can be useful for identifying patterns of interest. This paper describes the use of one such tool TimeSearcher - to interactively explore linear sequence data sets taken from two bioinformatics problems. Microarray time course data sets involve expression levels for large numbers of genes over multiple time points. TimeSearcher can be used to interactively search these data sets for genes with expression profiles of interest. The occurrence frequencies of short sequences of DNA in aligned exons can be used to identify sequences that play a role in the pre-mRNA splicing. TimeSearcher can be used to search these data sets for candidate splicing signals.
Keywords: Technical Report

Dynamic software updating - Hicks, Michael W.; Nettles,Scott (ACM Trans. Program. Lang. Syst., 2005)
Many important applications must run continuously and without interruption, and yet also 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, ease of use, and low cost.We present an 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 contain both 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 or Typed Assembly Language), which is native code accompanied by annotations that allow online 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, and generalize to present observations about updateable software development. Performance experiments show that for FlashEd, the overhead due to updating is low: typically less than 1 percent.
Keywords: dynamic software updating; typed assembly language

Dynamic updating of information-flow policies - Hicks, Michael W.; Tse,S.; Hicks,B.; Zdancewic,S. (Proceedings of the International Workshop on Foundations of Computer Security (FCS), 2005)

Efficient online computation of statement coverage - Tikir, Mustafa M.; Hollingsworth, Jeffrey K (Journal of Systems and Software, 2005)
Evaluation of statement coverage is the problem of identifying the statements of a program that execute in one or more runs of a program. The traditional approach for statement coverage tools is to use static code instrumentation. In this paper we present a new approach to dynamically insert and remove instrumentation code to reduce the runtime overhead of statement coverage measurement. We also explore the use of dominator tree information to reduce the number of instrumentation points needed. Our experiments show that our approach reduces runtime overhead by 38-90% compared with purecov, a commercial statement coverage tool. Our tool is fully automated and available for download from the Internet.

EMPS: an environment for memory performance studies - Hollingsworth, Jeffrey K; Snavely, A.; Sbaraglia, S.; Ekanadham, K. (Parallel and Distributed Processing Symposium, 2005. Proceedings. 19th IEEE International, 2005)
This paper describes an overview of environment for memory performance studies (EMPS). EMPS is a framework to allow different data gathering and simulation tools to be composed together to predict the performance of parallel programs on a variety of current and future high end computing (HEC) systems. The framework seeks to combine the automated nature of direct execution simulation with the predictive capabilities of performance modeling.
Keywords: Application software; cache storage; Computational modeling; Concurrent computing; data gathering; Delay; digital simulation; Economic forecasting; EMP radiation effects; high end computing system; High performance computing; memory architecture; memory performance; Moore's Law; PARALLEL PROCESSING; parallel program; Predictive models; simulation tool; Writing

Enhanced position weight matrices using mixture models - Hannenhalli, Sridhar; Wang,L.-S. (Bioinformatics, 2005)
Motivation: Positional weight matrix (PWM) is derived from a set of experimentally determined binding sites. Here we explore whether there exist subclasses of binding sites and if the mixture of these subclass-PWMs can improve the binding site prediction. Intuitively, the subclasses correspond to either distinct binding preference of the same transcription factor in different contexts or distinct subtypes of the transcription factor.Result: We report an Expectation Maximization algorithm adapting the mixture model of Baily and Elkan. We assessed the relative merit of using two subclass-PWMs. The resulting PWMs were evaluated with respect to preferred conservation (relative to mouse) of potential sites in human promoters and expression coherence of the potential target genes. Based on 64 JASPAR vertebrate PWMs, 61–81% of the cases resulted in a higher conservation using the mixture model. Also in 98% of the cases the expression coherence was higher for the target genes of one of the subclass-PWMs. Our analysis of Reb1 sites is consistent with previously discovered subtypes using independent methods. Additionally application of our method to mutated sites for transcription factor LEU3 reveals subclasses that segregate into strongly binding and weakly binding sites with P-value of 0.008. This is the first study which attempts to quantify the subtly different binding specificities of a transcription factor on a large scale and suggests the use of a mixture of PWMs, instead of the current practice of using a single PWM, for a transcription factor.

Envisioning help resources for the future information ecology: Toward an enriched sense of help - Haas,Stephanie W; Brown,Laurie; Denn,Sheila; Locke,David; Shneiderman, Ben (Proceedings of the American Society for Information Science and Technology, 2005)

Evaluating and tuning a static analysis to find null pointer bugs - Hovemeyer,D.; Spacco,J.; Pugh, William (Proceedings of the 6th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2005)

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

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

Extending User Understanding of Federal Statistics in Tables (2000) - Marchionini,Gary; Hert,Carol; Liddy,Liz; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
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: Technical Report

Finite-State Language resources and Language Processing - Hale,K.; Keyser,S.J.; Hutchins,W.J.; Habash,N.; Dorr, Bonnie J; Traum,D. (Machine Translation, 2005)

Generalizations of Markov model to characterize biological sequences - Wang,Junwen; Hannenhalli, Sridhar (BMC Bioinformatics, 2005)
BACKGROUND:The currently used kth order Markov models estimate the probability of generating a single nucleotide conditional upon the immediately preceding (gap = 0) k units. However, this neither takes into account the joint dependency of multiple neighboring nucleotides, nor does it consider the long range dependency with gap>0.RESULT:We describe a configurable tool to explore generalizations of the standard Markov model. We evaluated whether the sequence classification accuracy can be improved by using an alternative set of model parameters. The evaluation was done on four classes of biological sequences - CpG-poor promoters, all promoters, exons and nucleosome positioning sequences. Using di- and tri-nucleotide as the model unit significantly improved the sequence classification accuracy relative to the standard single nucleotide model. In the case of nucleosome positioning sequences, optimal accuracy was achieved at a gap length of 4. Furthermore in the plot of classification accuracy versus the gap, a periodicity of 10-11 bps was observed which might indicate structural preferences in the nucleosome positioning sequence. The tool is implemented in Java and is available for download at ftp://ftp.pcbi.upenn.edu/GMM/.CONCLUSION:Markov modeling is an important component of many sequence analysis tools. We have extended the standard Markov model to incorporate joint and long range dependencies between the sequence elements. The proposed generalizations of the Markov model are likely to improve the overall accuracy of sequence analysis tools.

Generating testable hypotheses from tacit knowledge for high productivity computing - Asgari, Sima; Hochstein, Lorin; Basili, Victor R.; Zelkowitz, Marvin V; Hollingsworth, Jeffrey K; Carver, Jeff; Shull, Forrest (Proceedings of the second international workshop on Software engineering for high performance computing system applications, 2005)
In this research, we are developing our understanding of how the high performance computing community develops effective parallel implementations of programs by collecting the folklore within the community. We use this folklore as the basis for a series of experiments, which we expect, will validate or negate these assumptions.
Keywords: folklore elicitation; high productivity development time experimental studies; hypothesis generation; tacit knowledge solicitation; testable hypotheses

The genetic map and comparative analysis with the physical map of Trypanosoma brucei - MacLeod,A.; Tweedie,A.; McLellan,S.; Taylor,S.; Hall,N.; Berriman,M.; El‐Sayed, Najib M.; Hope,M.; Turner,C. M.R; Tait,A. (Nucleic acids research, 2005)

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

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

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

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

Genome-Wide Analysis of Chromosomal Features Repressing Human Immunodeficiency Virus Transcription - Lewinski,M. K; Bisgrove,D.; Shinn,P.; Chen,H.; Hoffmann,C.; Hannenhalli, Sridhar; Verdin,E.; Berry,C. C; Ecker,J. R; Bushman,F. D (Journal of VirologyJ. Virol., 2005)
We have investigated regulatory sequences in noncoding human DNA that are associated with repression of an integrated human immunodeficiency virus type 1 (HIV-1) promoter. HIV-1 integration results in the formation of precise and homogeneous junctions between viral and host DNA, but integration takes place at many locations. Thus, the variation in HIV-1 gene expression at different integration sites reports the activity of regulatory sequences at nearby chromosomal positions. Negative regulation of HIV transcription is of particular interest because of its association with maintaining HIV in a latent state in cells from infected patients. To identify chromosomal regulators of HIV transcription, we infected Jurkat T cells with an HIV-based vector transducing green fluorescent protein (GFP) and separated cells into populations containing well-expressed (GFP-positive) or poorly expressed (GFP-negative) proviruses. We then determined the chromosomal locations of the two classes by sequencing 971 junctions between viral and cellular DNA. Possible effects of endogenous cellular transcription were characterized by transcriptional profiling. Low-level GFP expression correlated with integration in (i) gene deserts, (ii) centromeric heterochromatin, and (iii) very highly expressed cellular genes. These data provide a genome-wide picture of chromosomal features that repress transcription and suggest models for transcriptional latency in cells from HIV-infected patients.

Genome-wide analysis of retroviral DNA integration - Bushman,Frederic; Lewinski,Mary; Ciuffi,Angela; Barr,Stephen; Leipzig,Jeremy; Hannenhalli, Sridhar; Hoffmann,Christian (Nat Rev MicroNat Rev Micro, 2005)

Grid computing - Cummings, Michael P.; Huskamp,J. C (EDUCAUSE Review, 2005)

Group-based joint coding and embedding technique for multimedia fingerprinting - He,S.; Wu,M. (Proc. SPIE, 2005)
This paper proposes a group-based fingerprinting scheme employing a joint coding and embedding strategy totrace multimedia distribution and proactively prevent the leak of multimedia information. Taking advantage of the prior knowledge on the collusion pattern, we construct compact fingerprints that consist of user sub-codeword and group sub-codeword and are embedded in host signal via spread spectrum technique. The detection is done in two levels, which identifies guilty groups through correlation and then narrows down to specific colluders through minimum distance decoding. Experimental results show that the proposed method provides higher collusion resistance than the existing non-grouped fingerprint codes.

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

Improving collusion resistance of error correcting code based multimedia fingerprinting - He,Shan; M. Wu (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
Digital fingerprinting protects multimedia content from illegal redistribution by uniquely marking copies of the content distributed to each user. Collusion is a powerful attack whereby several differently fingerprinted copies of the same content are combined together to attenuate or remove the fingerprints. Focusing on the error correction code (ECC) based fingerprinting, we explore in this paper new avenues that can substantially improve its collusion resistance, and in the mean time retain its advantages in detection complexity and fast distribution. Our analysis suggests a great need of jointly considering the coding, embedding, and detection issues, and inspires the proposed technique of permuted subsegment embedding that is able to substantially improve the collusion resistance of ECC based fingerprinting.
Keywords: based; code; codes; coding; collusion; correcting; correction; data; detection; digital; ECC; embedding; error; fingerprint; fingerprinting; fingerprinting; multimedia; of; permuted; resistance; Security; signatures; subsegment; systems

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

Interactive Color Mosaic and Dendogram Displays for Signal/Noise Optimization in Microarray Data Analysis (2003) - Seo,Jinwook; Bakay,Marina; Zhao,Po; Chen,Yi-Wen; Clarkson,Priscilla; Shneiderman, Ben; Hoffman,Eric P (Institute for Systems Research Technical Reports, 2005)
Data analysis and visualization is strongly influenced by noise and noise filters. There are multiple sources of oisein microarray data analysis, but signal/noise ratios are rarely optimized, or even considered. Here, we report a noise analysis of a novel 13 million oligonucleotide dataset - 25 human U133A (~500,000 features) profiles of patient muscle biposies. We use our recently described interactive visualization tool, the Hierarchical Clustering Explorer (HCE) to systemically address the effect of different noise filters on resolution of arrays into orrectbiological groups (unsupervised clustering into three patient groups of known diagnosis). We varied probe set interpretation methods (MAS 5.0, RMA), resent callfilters, and clustering linkage methods, and investigated the results in HCE. HCE interactive features enabled us to quickly see the impact of these three variables. Dendrogram displays showed the clustering results systematically, and color mosaic displays provided a visual support for the results. We show that each of these three variables has a strong effect on unsupervised clustering. For this dataset, the strength of the biological variable was maximized, and noise minimized, using MAS 5.0, 10% present call filter, and Average Group Linkage. We propose a general method of using interactive tools to identify the optimal signal/noise balance or the optimal combination of these three variables to maximize the effect of the desired biological variable on data interpretation.
Keywords: Technical Report

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

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

Joint uplink and downlink optimization for video conferencing over wireless LAN - Su,Guan-Ming; Han,Zhu; M. Wu; Liu,K. J.R (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
A real-time video conferencing framework is proposed for multiple conferencing pairs by jointly considering the uplink and downlink conditions within IEEE 802.11 networks. We formulate this system so as to minimize the maximal end-to-end expected distortion received by all users by selecting the PHY modes and transmission time. Compared with the strategy of individually optimizing uplink and downlink, the proposed framework outperforms by 3.67-8.65 dB for the average received PSNR among all users.
Keywords: 802.11; conferencing; conferencing; distortion; end-to-end; expected; IEEE; joint; LAN; maximal; minimisation; modes; multiple; networks; optimization; pairs; PHY; PSNR; real-time; teleconferencing; time; transmission; uplink-downlink; video; wireless

Kernel-based Bayesian filtering for object tracking - Han,Bohyung; Zhu,Ying; Comaniciu, D.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Particle filtering provides a general framework for propagating probability density functions in nonlinear and non-Gaussian systems. However, the algorithm is based on a Monte Carlo approach and sampling is a problematic issue, especially for high dimensional problems. This paper presents a new kernel-based Bayesian filtering framework, which adopts an analytic approach to better approximate and propagate density functions. In this framework, the techniques of density interpolation and density approximation are introduced to represent the likelihood and the posterior densities by Gaussian mixtures, where all parameters such as the number of mixands, their weight, mean, and covariance are automatically determined. The proposed analytic approach is shown to perform sampling more efficiently in high dimensional space. We apply our algorithm to real-time tracking problems, and demonstrate its performance on real video sequences as well as synthetic examples.
Keywords: approach; approximation; Bayes; Bayesian; Carlo; density; detection; filtering; functions; Gaussian; interpolation; kernel-based; methods; mixtures; Monte; nonGaussian; nonlinear; object; particle; probability; probability; processes; recognition; sampling; sampling; sequences; system; tracking; video

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

Measuring productivity on high performance computers - Zelkowitz, Marvin V; Basili, Victor R.; Asgari, S.; Hochstein, L.; Hollingsworth, Jeffrey K; Nakamura, T. (11th IEEE International Symposium on Software Metric, 2005)
In the high performance computing domain, the speed ofexecution of a program has typically been the primary performance metric. But productivity is also of concern to high performance computing developers. In this paper we will discuss the problems of defining and measuring productivity for these machines and we develop a model of productivity that includes both a performance component and a component that measures the development time of the program. We ran several experiments using students in high performance courses at several universities, and we report on those results with respect to our model of productivity.

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

A metric space for productivity measurement in software development - Numrich,Robert W.; Hochstein, Lorin; Basili, Victor R. (Proceedings of the second international workshop on Software engineering for high performance computing system applications, 2005)
We define a metric space to measure the contributions of individual programmers to a software development project. It allows us to measure the distance between the contributions of two different programmers as well as the absolute contribution of each individual programmer. Our metric is based on an action function that provides a picture of how one programmer's approach differs from another at each instance of time during the project. We apply our metric to data we collected from students taking a course in parallel programming. We display the pictures for two students who showed approximately equal contributions but who followed very different paths through the course.

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

Mutatis mutandis: safe and predictable dynamic software updating - Stoyle,Gareth; Hicks, Michael W.; Bierman,Gavin; Sewell,Peter; Neamtiu,Iulian (Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2005)
Dynamic software updates can be used to fix bugs or add features to a running program without downtime. Essential for some applications and convenient for others, low-level dynamic updating has been used for many years. Perhaps surprisingly, there is little high-level understanding or language support to help programmers write dynamic updates effectively.To bridge this gap, we present Proteus, a core calculus for dynamic software updating in C-like languages that is flexible, safe, and predictable. Proteus supports dynamic updates to functions (even active ones), to named types and to data, allowing on-line evolution to match source-code evolution as we have observed it in practice. We ensure updates are type-safe by checking for a property we call "con-freeness" for updated types t at the point of update. This means that non-updated code will not use t concretely beyond that point (concrete usages are via explicit coercions) and thus t's representation can safely change. We show how con-freeness can be enforced dynamically for a particular program state. We additionally define a novel and efficient static updateability analysis to establish con-freeness statically, and can thus automatically infer program points at which all future (well-formed) updates will be type-safe. We have implemented our analysis for C and tested it on several well-known programs.
Keywords: capability; dynamic software updating; proteus; Type inference; updateability analysis

Online auctions with re-usable goods - Hajiaghayi, Mohammad T. (Proceedings of the 6th ACM conference on Electronic commerce, 2005)

On-line density-based appearance modeling for object tracking - Han,B.; Davis, Larry S. (Computer Vision, 2005. ICCV 2005. Tenth IEEE International Conference on, 2005)
Object tracking is a challenging problem in real-time computer vision due to variations of lighting condition, pose, scale, and view-point over time. However, it is exceptionally difficult to model appearance with respect to all of those variations in advance; instead, on-line update algorithms are employed to adapt to these changes. We present a new on-line appearance modeling technique which is based on sequential density approximation. This technique provides accurate and compact representations using Gaussian mixtures, in which the number of Gaussians is automatically determined. This procedure is performed in linear time at each time step, which we prove by amortized analysis. Features for each pixel and rectangular region are modeled together by the proposed sequential density approximation algorithm, and the target model is updated in scale robustly. We show the performance of our method by simulations and tracking in natural videos
Keywords: appearance; approximation; Gaussian; Computer; density; density-based; detection; target; Gaussian; mixtures; object; modeling; modeling; real-time; processes; computer; sequences; object; technique; online; tracking; tracking; online; vision; image; vision; sequential

An outdoor 3-D visual tracking system for the study of spatial navigation and memory in rhesus monkeys - Zia Khan; Herman, Rebecca A.; Wallen, Kim; Balch, Tucker (Behavior Research Methods, 2005)
Previous studies of the navigational abilities of nonhuman primates have largely been limited to what could be described by a human observer with a pen and paper. Consequently, we have developed a system that uses a pair of cameras to automatically obtain the three-dimensional trajectory of rhesus monkeys performing an outdoor spatial navigation and memory task. The system provides trajectories, path length, speed, and other variables that would be impossible for an unaided observer to note. From trajectory data, we computed and validated a path-length measurement. We use this measurement to compare the navigation abilities of several animals. In addition, we provide quantitative data on the accuracy of a method for automatic behavior detection. Currently, the system is being used to examine the sex differences in spatial navigation of rhesus monkeys. We expect that measures derived from the trajectory data will reveal strategies used by animals to solve spatial problems.
Keywords: cognitive psychology

A pairwise key predistribution scheme for wireless sensor networks - Du,Wenliang; Deng,Jing; Han,Yunghsiang S.; Varshney,Pramod K.; Katz, Jonathan; Khalili,Aram (ACM Trans. Inf. Syst. Secur., 2005)
To achieve security in wireless sensor networks, it is important to be able to encrypt and authenticate messages sent between sensor nodes. Before doing so, keys for performing encryption and authentication must be agreed upon by the communicating parties. Due to resource constraints, however, achieving key agreement in wireless sensor networks is nontrivial. Many key agreement schemes used in general networks, such as Diffie-Hellman and other public-key based schemes, are not suitable for wireless sensor networks due to the limited computational abilities of the sensor nodes. Predistribution of secret keys for all pairs of nodes is not viable due to the large amount of memory this requires when the network size is large.In this paper, we provide a framework in which to study the security of key predistribution schemes, propose a new key predistribution scheme which substantially improves the resilience of the network compared to previous schemes, and give an in-depth analysis of our scheme in terms of network resilience and associated overhead. Our scheme exhibits a nice threshold property: when the number of compromised nodes is less than the threshold, the probability that communications between any additional nodes are compromised is close to zero. This desirable property lowers the initial payoff of smaller-scale network breaches to an adversary, and makes it necessary for the adversary to attack a large fraction of the network before it can achieve any significant gain.
Keywords: key predistribution; Security; Wireless sensor networks

Parallel Parameter Tuning for Applications with Performance Variability - Tabatabaee, Vahid; Tiwari, Ananta; Hollingsworth, Jeffrey K (Proceedings of the 2005 ACM/IEEE conference on Supercomputing, 2005)
In this paper, we present parallel on-line optimization algorithms for parameter tuning of parallel programs. We employ direct search algorithms that update parameters based on real-time performance measurements. We discuss the impact of performance variability on the accuracy and efficiency of the optimization algorithms and proposed modified versions of the direct search algorithms to cope with it. The modified version uses multiple samples instead of single sample to estimate the performance more accurately.We present preliminary results that the performance variability of applications on clusters is heavy tailed. Finally, we studay and demonstrate the performance ofthe proposed algorithms for real scientific application.
Keywords: algorithms; compilers; design

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

Performance study on multimedia fingerprinting employing traceability codes - He,S.; Wu,M. (Digital Watermarking, 2005)
Digital fingerprinting is a tool to protect multimedia content from illegal redistribution by uniquely marking copies of the content distributed to each user. Collusion attack is a powerful attack whereby several differently-fingerprinted copies of the same content are combined together to attenuate or even remove the fingerprint. Coded fingerprinting is one major category of fingerprinting techniques against collusion. Many fingerprinting codes are proposed with tracing capability and collusion resistance, such as Traceability (TA) codes and Identifiable Parent Property (IPP) codes. Most of these works treat the important embedding issue in terms of a set of simplified and abstract assumptions, and they do not examine the end-to-end performance of the coded multimedia fingerprinting. In this paper we jointly consider the coding and embedding issues and examine the collusion resistance of coded fingerprinting systems with various code parameters. Our results show that TA codes generally offer better collusion resistance than IPP codes, and a TA code with a larger alphabet size and a longer code length is preferred.

Porting DSP applications across design tools using the dataflow interchange format - Hsu,C.-J.; Bhattacharyya, Shuvra S. (Rapid System Prototyping, 2005. (RSP 2005). The 16th IEEE International Workshop on, 2005)
Modeling DSP applications through coarse-grain dataflow graphs is popular in the DSP design community, and a growing set of rapid prototyping tools support such dataflow semantics. Since different tools may be suitable for different phases or generations of a design, it is often desirable to migrate a dataflow-based application model from one prototyping tool to another. Two critical problems in transferring dataflow-based designs across different prototyping tools are the lack of a vendor-independent language for DSP-oriented dataflow graphs, and the lack of an efficient porting methodology. In our previous work, the dataflow interchange format (DIF) (C. Hsu et al., 2004) has been developed as a standard language to specify mixed-grain dataflow models for DSP systems. This paper presents the augmentation of the DIF infrastructure with a systematic porting approach that integrates DIF tightly with the specific exporting and importing mechanisms that interface DIF to specific DSP design tools. In conjunction with this porting mechanism, this paper also introduces a novel language, called the actor interchange format (AIF), for transferring relevant information pertaining to DSP library components across different tools. Through a case study of a synthetic aperture radar application, we demonstrate the high degree of automation offered by our DIF-based porting approach.
Keywords: actor interchange format; coarse-grain dataflow graph; data flow analysis; data flow graphs; dataflow interchange format; dataflow model; dataflow semantic; DSP application; DSP design tool; DSP library component; electronic data interchange; formal specification; rapid prototyping tool; Signal processing; software prototyping; Specification languages; vendor-independent language

Probabilistic Ontologies and Relational Databases - Udrea,Octavian; Yu,Deng; Hung,Edward; Subrahmanian,V. (On the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASEOn the Move to Meaningful Internet Systems 2005: CoopIS, DOA, and ODBASE, 2005)
The relational algebra and calculus do not take the semantics of terms into account when answering queries. As a consequence, not all tuples that should be returned in response to a query are always returned, leading to low recall. In this paper, we propose the novel notion of a constrained probabilistic ontology (CPO). We developed the concept of a CPO-enhanced relation in which each attribute of a relation has an associated CPO. These CPOs describe relationships between terms occurring in the domain of that attribute. We show that the relational algebra can be extended to handle CPO-enhanced relations. This allows queries to yield sets of tuples, each of which has a probability of being correct.
Keywords: Computer; Science

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

RDF aggregate queries and views - Hung,E.; Deng,Yu; V.S. Subrahmanian (Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on, 2005)
Resource description framework (RDF) is a rapidly expanding Web standard. RDF databases attempt to track the massive amounts of Web data and services available. In this paper, we study the problem of aggregate queries. We develop an algorithm to compute answers to aggregate queries over RDF databases and algorithms to maintain views involving those aggregates. Though RDF data can be stored in a standard relational DBMS (and hence we can execute standard relational aggregate queries and view maintenance methods on them), we show experimentally that our algorithms that operate directly on the RDF representation exhibit significantly superior performance.
Keywords: aggregate; databases; DBMS; description; framework; languages; Maintenance; methods; processing; queries; query; RDF; relational; resource; standard; standards; view; Web

Real-time foreground-background segmentation using codebook model - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Real-time imaging, 2005)

Recovering system specific rules from software repositories - Williams, Chadd C; Hollingsworth, Jeffrey K (SIGSOFT Softw. Eng. Notes, 2005)
One of the most successful applications of static analysis based bug finding tools is to search the source code for violations of system-specific rules. These rules may describe how functions interact in the code, how data is to be validated or how an API is to be used. To apply these tools, the developer must encode a rule that must be followed in the source code. The difficulty is that many of these system-specific rules are undocumented and "grow" over time as the source code changes. Most research in this area relies on expert programmers to document these little-known rules. In this paper we discuss a method to automatically recover a subset of these rules, function usage patterns, by mining the software repository. We present a preliminary study that applies our work to a large open source software project.
Keywords: data warehouse and repository; debugging aids; design; experimentation; measurement; performance

Reducing complexity assumptions for statistically-hiding commitment - Haitner,I.; Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R.; Shaltiel,R. (Advances in Cryptology–EUROCRYPT 2005, 2005)
Determining the minimal assumptions needed to construct various cryptographic building blocks has been a focal point of research in theoretical cryptography. Here, we revisit the following question: what are the minimal assumptions needed to construct statistically-hiding commitment schemes? Previously, it was known how to construct such schemes based on one-way permutations. We improve upon this by constructing statistically-hiding commitment schemes based on approximable-preimage-size one-way functions. These are one-way functions for which there is an efficient way to approximate the number of preimages of a given output. A special case (for which we show a somewhat simpler construction) is that of regular one-way functions where all outputs have the same number of preimages.We utilize two different approaches in constructing statistically-hiding commitment schemes. Our first approach proceeds by showing that the scheme of Naor et al. can be implemented using any one-way function having an output distribution which is “sufficiently similar” to uniform. We then construct one-way functions with this property from approximable-preimage-size one-way functions. Our second approach begins by constructing a commitment scheme which is statistically hiding against an honest-but-curious receiver. We then demonstrate a compiler which transforms any such commitment scheme into one which is statistically hiding even against a malicious receiver. This compiler and its analysis may be of independent interest.

Robust observations for object tracking - Han,Bohyung; Davis, Larry S. (Image Processing, 2005. ICIP 2005. IEEE International Conference on, 2005)
It is a difficult task to find an observation model that will perform well for long-term visual tracking. In this paper, we propose an adaptive observation enhancement technique based on likelihood images, which are derived from multiple visual features. The most discriminative likelihood image is extracted by principal component analysis (PCA) and incrementally updated frame by frame to reduce temporal tracking error. In the particle filter framework, the feasibility of each sample is computed using this most discriminative likelihood image before the observation process. Integral image is employed for efficient computation of the feasibility of each sample. We illustrate how our enhancement technique contributes to more robust observations through demonstrations.
Keywords: (numerical; adaptive; analysis; component; enhancement; filter; Filtering; framework; image; images; likelihood; methods); object; observation; particle; PCA; principal; tracking

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

Severity and Impact of Computer User Frustration: A Comparison of Student and Workplace Users (2002) - Lazar,Jonathan; Jones,Adam; Hackley,Mary; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
User frustration with information and computing technology is a pervasive and persistent problem. When computers crash, network congestion causes delays, and poor user interfaces trigger confusion there are dramatic consequences for individuals, organizations, and society. These frustrations not only cause personal dissatisfaction and loss of self-efficacy, but may disrupt workplaces, slow learning, and reduce participation in local and national communities. Our study of 107 student computer users and 50 workplace computer users shows high levels of frustration and loss of 1/3 to 1/2 of time spent. This paper reports on the incident-specific and user-specific causes of frustration, and they raise frustration severity. It examines the frustration impacts on the daily interactions of the users. The time lost and time to fix problem, and importance of task, strongly correlate with frustration levels for both student and workplace users. Differences between students and workplace users are discussed in the paper.
Keywords: Technical Report

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

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

Software synthesis from the dataflow interchange format - Hsu,C. J; Ko,M. Y; Bhattacharyya, Shuvra S. (Proceedings of the 2005 workshop on Software and compilers for embedded systems, 2005)

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

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

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

Toward on-line schema evolution for non-stop systems - Deshpande, Amol; Hicks, Michael W. (11th High Performance Transaction Systems Workshop, 2005)

Understanding source code evolution using abstract syntax tree matching - Neamtiu,Iulian; Foster, Jeffrey S.; Hicks, Michael W. (Proceedings of the 2005 international workshop on Mining software repositories, 2005)
Mining software repositories at the source code level can provide a greater understanding of how software evolves. We present a tool for quickly comparing the source code of different versions of a C program. The approach is based on partial abstract syntax tree matching, and can track simple changes to global variables, types and functions. These changes can characterize aspects of software evolution useful for answering higher level questions. In particular, we consider how they could be used to inform the design of a dynamic software updating system. We report results based on measurements of various versions of popular open source programs. including BIND, OpenSSH, Apache, Vsftpd and the Linux kernel.
Keywords: abstract syntax trees; software evolution; source code analysis

Universal Usability as a Stimulus to Advanced Interface Design (2001) - Shneiderman, Ben; Hochheiser,Harry (Institute for Systems Research Technical Reports, 2005)
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, we urge web designers to provide universal usability statements, to provide users with useful 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. We close with five proposals for future research.
Keywords: Technical Report

Universally composable password-based key exchange - Canetti,R.; Halevi,S.; Katz, Jonathan; Lindell,Y.; MacKenzie,P. (Advances in Cryptology–Eurocrypt 2005, 2005)
We propose and realize a definition of security for password-based key exchange within the framework of universally composable (UC) security, thus providing security guarantees under arbitrary composition with other protocols. In addition, our definition captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, it does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen by different parties. We also formulate a definition of password-based secure channels, and show that such a definition is achievable given password-based key exchange.Our protocol realizing the new definition of password-based key exchange is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that it is impossible to satisfy our definition in the “plain” model (e.g., without a common reference string).

Using Dynamic Tracing Sampling to Measure Long Running Programs - Odom, Jeffrey; Hollingsworth, Jeffrey K; DeRose,Luiz; Ekanadham, Kattamuri; Sbaraglia, Simone (Proceedings of the 2005 ACM/IEEE conference on Supercomputing, 2005)
Detailed cache simulation can be useful to both system developers and application writers to understand an application's performance. However, measuring long running programs can be extremely slow. In this paper we present a technique to use dynamic sampling of trace snippets throughout an application's execution. We demonstrate that our approach improves accuracy compared to sampling a few timesteps at the beginning of execution by judiciously choosing the frequency, as well as the points in the control flow, at which samples are collected. Our approach is validated using the SIGMA tracing and simulation framework for the IBM Power family of processors.
Keywords: data communications; design; experimentation; measurement; performance; tracing

VidMAP: video monitoring of activity with Prolog - Shet,V. D; Harwood,D.; Davis, Larry S. (Advanced Video and Signal Based Surveillance, 2005. AVSS 2005. IEEE Conference on, 2005)
This paper describes the architecture of a visual surveillance system that combines real time computer vision algorithms with logic programming to represent and recognize activities involving interactions amongst people, packages and the environments through which they move. The low level computer vision algorithms log primitive events of interest as observed facts, while the higher level Prolog based reasoning engine uses these facts in conjunction with predefined rules to recognize various activities in the input video streams. The system is illustrated in action on a multi-camera surveillance scenario that includes both security and safety violations.
Keywords: activities; algorithms; based; Computer; computerised; engine; higher; image; level; Logic; monitoring; multicamera; processing; programming; Prolog; PROLOG; reasoning; recognition; scenario; signal; streaming; streams; Surveillance; surveillance; system; video; VISION; vision; visual

Visual Specification of Queries for Finding Patterns in Time-Series Data (2001) - Hochheiser,Harry; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
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, directmanipulation 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.
Keywords: Technical Report

Abstracting workflows: unifying bioinformatics task conceptualization and specification through Semantic Web services - Hashmi,N.; Lee,S.; Cummings, Michael P. (W3C Workshop on Semantic Web for Life Sciences, 2004)

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

Adaptively-Secure, Non-Interactive Public-Key Encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Model reduction methods for vector autoregressive processes, 2004)

Automated cluster-based Web service performance tuning - Chung,I. -H; Hollingsworth, Jeffrey K (13th IEEE International Symposium on High performance Distributed Computing, 2004. Proceedings, 2004)
Active harmony provides a way to automate performance tuning. We apply the Active Harmony system to improve the performance of a cluster-based web service system. The performance improvement cannot easily be achieved by tuning individual components for such a system. The experimental results show that there is no single configuration for the system that performs well for all kinds of workloads. By tuning the parameters, Active Harmony helps the system adapt to different workloads and improve the performance up to 16%. For scalability, we demonstrate how to reduce the time when tuning a large system with many tunable parameters. Finally an algorithm is proposed to automatically adjust the structure of cluster-based web systems, and the system throughput is improved up to 70% using this technique.
Keywords: Active Harmony system; automated performance tuning; business; cluster-based Web service system; Clustering algorithms; Computer science; Educational institutions; electronic commerce; Internet; Middleware; performance evaluation; scalability; Throughput; Transaction databases; Web server; Web services; workstation clusters

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

Background modeling and subtraction by codebook construction - Kim,Kyungnam; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
We present a new fast algorithm for background modeling and subtraction. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. Our method can handle scenes containing moving backgrounds or illumination variations (shadows and highlights), and it achieves robust detection for compressed videos. We compared our method with other multimode modeling techniques.
Keywords: (signal); analysis; background; codebook; coding; colour; compression; construction; data; image; modeling; modeling; MOTION; multimode; quantisation; representation; sequence; sequences; subtraction; technique; video

Bidimensional Parameters and Local Treewidth - Fomin,E. D.D.F.V; Hajiaghayi, Mohammad T.; Thilikos,D. M (Latin 2004: Theoretical Informatics: 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004: Proceedings, 2004)

Bug driven bug finders - Williams, C. C; Hollingsworth, Jeffrey K (Proceedings of the International Workshop on Mining Software Repositories, 2004)

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

Building KidPad: an application for children's collaborative storytelling - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison (Software: Practice and Experience, 2004)

Challenges in Measuring HPCS Learner Productivity in an Age of Ubiquitous Computing: The HPCS Program - Asgari, S.; Basili, Victor R.; Carver, J.; Hochstein, L.; Hollingsworth, Jeffrey K; Zelkowitz, Marvin V (In Proceedings of ICSE Workshop on High Productivity Computing. May 2004, 2004)

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

Chosen-ciphertext security from identity-based encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Advances in Cryptology-Eurocrypt 2004, 2004)
We propose a simple and efficient construction of a CCA-secure public-key encryption scheme from any CPA-secure identity-based encryption (IBE) scheme. Our construction requires the underlying IBE scheme to satisfy only a relatively “weak” notion of security which is known to be achievable without random oracles; thus, our results provide a new approach for constructing CCA-secure encryption schemes in the standard model. Our approach is quite different from existing ones; in particular, it avoids non-interactive proofs of “well-formedness” which were shown to underlie most previous constructions. Furthermore, applying our conversion to some recently-proposed IBE schemes results in CCA-secure schemes whose efficiency makes them quite practical.Our technique extends to give a simple and reasonably efficient method for securing any binary tree encryption (BTE) scheme against adaptive chosen-ciphertext attacks. This, in turn, yields more efficient CCA-secure hierarchical identity-based and forward-secure encryption schemes in the standard model.

Data Centric Cache Measurement on the Intel ltanium 2 Processor - Buck, Bryan R; Hollingsworth, Jeffrey K (Proceedings of the 2004 ACM/IEEE conference on Supercomputing, 2004)
Processor speed continues to increase faster than the speed of access to main memory, making effective use of memory caches more important. Information about an applicationýs interaction with the cache is therefore critical to performance tuning. To be most useful, tools that measure this information should relate it to the source code level data structures in an application. We describe how to gather such information by using hardware performance counters to sample cache miss addresses, and present a new tool named Cache Scope that does this using the Intel Itanium 2 performance monitors. We present experimental results concerning Cache Scopeýs accuracy and perturbation of cache behavior. We also describe a case study of using Cache Scope to tune two applications, achieving 24% and 19% reductions in running time.

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

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

DIF: An interchange format for dataflow-based design tools - Hsu,C. J; Keceli,F.; Ko,M. Y; Shahparnia,S.; Bhattacharyya, Shuvra S. (Computer Systems: Architectures, Modeling, and Simulation, 2004)

Distortion management of real-time MPEG-4 video over downlink multicode CDMA networks - Su,Guan-Ming; Han,Zhu; Kwasinski,A.; M. Wu; Liu,K. J.R; Farvardin,N. (Communications, 2004 IEEE International Conference on, 2004)
In this paper, a protocol is designed to manage source rate/channel coding rate adaptation, code allocation, and power control to transmit real-time MPEG-4 FGS video over downlink multicode CDMA networks. We develop a fast adaptive scheme of distortion management to reduce the overall distortion received by all users subject, to the limited number of codes and maximal transmitted power. Compared with a modified greedy method in literature, our proposed algorithm can reduce the overall system's distortion by at least 45%.
Keywords: access; adaptation; allocation; CDMA; channel; code; coding; coding; combined; communication; compression; control; data; distortion; division; downlink; links; management; MPEG-4; multicode; multiple; networks; power; radio; rate; real-time; resource; source; source-channel; video; video; visual

Distributed prototyping from validated specifications - Hansel,David; Cleaveland, Rance; Smolka,Scott A. (Journal of Systems and Software, 2004)
We present vpl2cxx, a translator that automatically generates efficient, fully distributed C++ code from high-level system models specified in the mathematically well-founded VPL design language. As the Concurrency Workbench of the New Century (CWB-NC) verification tool includes a front-end for VPL, designers may use the full range of automatic verification and simulation checks provided by this tool on their VPL system designs before invoking the translator, thereby generating distributed prototypes from validated specifications. Besides being fully distributed, the code generated by vpl2cxx is highly readable and portable to a host of execution environments and real-time operating systems (RTOSes). This is achieved by encapsulating all generated code dealing with low-level interprocess communication issues in a library for synchronous communication, which in turn is built upon the adaptive communication environment (ACE) client-server network programming interface. Finally, example applications show that the performance of the generated code is very good, especially for prototyping purposes. We discuss two such examples, including the RETHER real-time Ethernet protocol for voice and video applications.

Divergence Unraveling for Word Alignment... - Dorr, Bonnie J; Ayan,N.F.; Habash,N. (Natural Language Engineering, 2004)
We describe the use of parallel text for divergence unraveling in word-level alignment. DUSTer (Divergence Unraveling for Statistical Translation) is a system that combines linguistic and statistical knowledge to resolve structural di#erences between languages, i.e., translation divergences, during the process of alignment. Our immediate goal is to induce word-level alignments that are more accurate than those produced by an existing state-ofthe -art statistical system. The long-term goal is to improve the output quality of statistical machine translation and lexical acquisition systems by using DUSTer as one possible input to a framework that accommodates multiple alignments. We show that a systematic characterization of alignment errors made by a statistical system validates the use of linguistically-motivated universal rules for identifying and handling divergences. These rules relate one or more linguistically-motivated categories associated with the (English) input words to those of another language (foreign language); the resulting match sets are used to infer corrected alignments. Using a human-aligned corpus as our gold standard, we demonstrate an improvement in alignments over an existing state-of-the-art alignment algorithm.

Divergent Gene Copies in the Asexual Class Bdelloidea (Rotifera) Separated Before the Bdelloid Radiation or Within Bdelloid Families - Welch,David B. Mark; Cummings, Michael P.; Hillis,David M; Meselson,Matthew (Proceedings of the National Academy of Sciences of the United States of AmericaPNAS, 2004)
Rotifers of the asexual class Bdelloidea are unusual in possessing two or more divergent copies of every gene that has been examined. Phylogenetic analysis of the heat-shock gene hsp82 and the TATA-box-binding protein gene tbp in multiple bdelloid species suggested that for each gene, each copy belonged to one of two lineages that began to diverge before the bdelloid radiation. Such gene trees are consistent with the two lineages having descended from former alleles that began to diverge after meiotic segregation ceased or from subgenomes of an alloploid ancestor of the bdelloids. However, the original analyses of bdelloid gene-copy divergence used only a single outgroup species and were based on parsimony and neighbor joining. We have now used maximum likelihood and Bayesian inference methods and, for hsp82, multiple outgroups in an attempt to produce more robust gene trees. Here we report that the available data do not unambiguously discriminate between gene trees that root the origin of hsp82 and tbp copy divergence before the bdelloid radiation and those which indicate that the gene copies began to diverge within bdelloid families. The remarkable presence of multiple diverged gene copies in individual genomes is nevertheless consistent with the loss of sex in an ancient ancestor of bdelloids.

Dynamic distortion control for 3-D embedded wavelet video over multiuser OFDM networks - Su,Guan-Ming; Han,Zhu; M. Wu; Liu,K. J.R (Global Telecommunications Conference, 2004. GLOBECOM '04. IEEE, 2004)
In this paper, we propose a system to transmit multiple 3D embedded wavelet video programs over downlink multiuser OFDM. We consider the fairness among users and formulate the problem as minimizing the users' maximal distortion subject to power, rate, and subcarrier constraints. By exploring frequency, time, and multiuser diversity in OFDM and flexibility of the 3D embedded wavelet video codec, the proposed algorithm can achieve fair video qualities among all users. Compared to a scheme similar to the current multiuser OFDM standard (IEEE 802.11a), the proposed scheme outperforms it by 1-5 dB on the worst received PSNR among all users and has much smaller PSNR deviation.
Keywords: 3D; 802.11a; channels; codec; codecs; communication; control; deviation; distortion; diversity; diversity; downlink; dynamic; embedded; fairness; Frequency; IEEE; LAN; maximal; minimax; minimization; modulation; multimedia; multiuser; OFDM; OFDM; PSNR; rate; reception; streaming; systems; techniques; theory; TIME; transforms; video; video; wavelet; wireless

Dynamic Query Tools for Time Series Data Sets: Timebox Widgets for Interactive Exploration - Hochheiser,Harry; Shneiderman, Ben (Information VisualizationInformation Visualization, 2004)
Timeboxes are rectangular widgets that can be used in direct-manipulation graphical user interfaces (GUIs) to specify query constraints on time series data sets. Timeboxes are used to specify simultaneously two sets of constraints: given a set of N time series profiles, a timebox covering time periods x1…x2 (x1 ≤ x2) and values y1…y2 (y1 ≤ y2) will retrieve only those n√N that have values y1 ≤ y2 during all times x1 ≤ x ≤ x2. TimeSearcher is an information visualization tool that combines timebox queries with overview displays, query-by-example facilities, and support for queries over multiple time-varying attributes. Query manipulation tools including pattern inversion and ‘leaders & laggards’ graphical bookmarks provide additional support for interactive exploration of data sets. Extensions to the basic timebox model that provide additional expressivity include variable time timeboxes, which can be used to express queries with variability in the time interval, and angular queries, which search for ranges of differentials, rather than absolute values. Analysis of the algorithmic requirements for providing dynamic query performance for timebox queries showed that a sequential search outperformed searches based on geometric indices. Design studies helped identify the strengths and weaknesses of the query tools. Extended case studies involving the analysis of two different types of data from molecular biology experiments provided valuable feedback and validated the utility of both the timebox model and the TimeSearcher tool. Timesearcher is available at http://www.cs.umd.edu/hcil/timesearcher
Keywords: angular queries; Bioinformatics; dynamic query; Graphical user interfaces; temporal data; time series; timeboxes; TimeSearcher; visual query

Efficient solution of poisson-boltzmann equation for electrostatics of large molecules - Hao,X.; Varshney, Amitabh (High-Performance Computing Symposium (April 2004), 2004)
Development of fast computational methods to solve thePoisson-Boltzmann equation (PBE) for molecular elec- trostatics is important because of the central role played by electrostatic interactions in many biological processes. The accuracy and stability of the solution to the PBE is quite sensitive to the boundary layer between the sol- vent and the solute which defines the solvent-accessible surface. In this paper, we propose a new interface- layer-focused PBE solver for efficiently computing the electrostatic potential for large molecules. Our method analytically constructs the solvent-accessible surface of molecules and then builds nested iso-surface layers out- wards and inwards from the surface using the distance field around the surface. We then develop a volume sim- plification algorithm to adaptively adjust the density of the irregular grid based on the importance to the PBE solution. We also generalize finite difference methods on our irregular grids using Taylor series expansions. Our algorithm achieves about three times speedup in the iter- ative solution process of PBE, with more accurate results on an analytical solvable testing case, compared with the popular optimized DelPhi program. Our approach can also be applied directly to solve partial differential equa- tions arising in other application domains.

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

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

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

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

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

iCLEF 2003 at Maryland: Translation selection and document selection - Dorr, Bonnie J; He,D.; Luo,J.; Oard, Douglas; Schwartz,R.; Wang,J.; Zajic, David (Comparative Evaluation of Multilingual Information Access Systems, 2004)

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

iCLEF 2004 at Maryland: Summarization design for interactive cross-language question answering - He,D.; Wang,J.; Luo,J.; Oard, Douglas (Proceeding of Cross Language Evaluation Forum (CLEF2004), 2004)

Implementation of the regularized structured total least squares algorithms for blind image deblurring - Mastronardi,N.; Lemmerling,P.; Kalsi,A.; O’Leary,D. P; Huffel,S. Van (Linear Algebra and its Applications, 2004)
The structured total least squares (STLS) problem has been introduced to handle problems involving structured matrices corrupted by noise. Often the problem is ill-posed. Recently, regularization has been proposed in the STLS framework to solve ill-posed blind deconvolution problems encountered in image deblurring when both the image and the blurring function have uncertainty. The kernel of the regularized STLS (RSTLS) problem is a least squares problem involving Block–Toeplitz–Toeplitz–Block matrices.In this paper an algorithm is described to solve this problem, based on a particular implementation of the generalized Schur Algorithm (GSA). It is shown that this new implementation improves the computational efficiency of the straightforward implementation of GSA from O(N2.5) to O(N2), where N is the number of pixels in the image.
Keywords: Block Toeplitz matrix; Displacement rank; Generalized Schur algorithm; Image deblurring; Structured total least squares; Tikhonov regularization

Incremental density approximation and kernel-based bayesian filtering for object tracking - Han,B.; Comaniciu, D.; Zhu,Y.; Davis, Larry S. (IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004)
Statistical density estimation techniques are used in manycomputer vision applications such as object tracking, back- ground subtraction, motion estimation and segmentation. The particle filter (Condensation) algorithm provides a gen- eral framework for estimating the probability density func- tions (pdf) of general non-linear and non-Gaussian systems. However, since this algorithm is based on a Monte Carlo ap- proach, where the density is represented by a set of random samples, the number of samples is problematic, especially for high dimensional problems. In this paper, we propose an alternative to the classical particle filter in which the un- derlying pdf is represented with a semi-parametric method based on a mode finding algorithm using mean-shift. A mode propagation technique is designed for this new representa- tion for tracking applications. A quasi-random sampling method [14] in the measurement stage is used to improve performance, and sequential density approximation for the measurements distribution is performed for efficient compu- tation. We apply our algorithm to a high dimensional color- based tracking problem, and demonstrate its performance by showing competitive results with other trackers.

Indexing distributed complex data for complex queries - Tanin,Egemen; Harwood,Aaron; Samet, Hanan (Proceedings of the 2004 annual national conference on Digital government research, 2004)
Peer-to-peer networks are becoming a common form of online data exchange. Querying data, mostly files, using keywords on peer-to-peer networks is well-known. But users cannot perform many types of queries on complex data and on many of the attributes of the data on such networks other than mostly exact-match queries. We introduce a distributed hashing-based index for enabling more powerful accesses on complex data over peer-to-peer networks that we expect to be commonly deployed for digital government applications. Preliminary experiments show that our index scales well and we believe that it can be extended to obtain similar indices for many other data types for performing various complex queries, such as range queries.

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

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

Interactive binary instrumentation - Williams, C. C; Hollingsworth, Jeffrey K (Second International Workshop on Remote Analysis and Measurement of Software Systems (RAMSS), 2004)

Interactively Optimizing Signal-to-Noise Ratios in Expression Profiling: Project-Specific Algorithm Selection and Detection P-Value Weighting in Affymetrix Microarrays - Seo,Jinwook; Bakay,Marina; Chen,Yi-Wen; Hilmer,Sara; Shneiderman, Ben; Hoffman,Eric P (BioinformaticsBioinformatics, 2004)
Motivation: The most commonly utilized microarrays for mRNA profiling (Affymetrix) include ‘probe sets’ of a series of perfect match and mismatch probes (typically 22 oligonucleotides per probe set). There are an increasing number of reported ‘probe set algorithms’ that differ in their interpretation of a probe set to derive a single normalized ‘signal’ representative of expression of each mRNA. These algorithms are known to differ in accuracy and sensitivity, and optimization has been done using a small set of standardized control microarray data. We hypothesized that different mRNA profiling projects have varying sources and degrees of confounding noise, and that these should alter the choice of a specific probe set algorithm. Also, we hypothesized that use of the Microarray Suite (MAS) 5.0 probe set detection p-value as a weighting function would improve the performance of all probe set algorithms.Results: We built an interactive visual analysis software tool (HCE2W) to test and define parameters in Affymetrix analyses that optimize the ratio of signal (desired biological variable) versus noise (confounding uncontrolled variables). Five probe set algorithms were studied with and without statistical weighting of probe sets using the MAS 5.0 probe set detection p-values. The signal-to-noise ratio optimization method was tested in two large novel microarray datasets with different levels of confounding noise, a 105 sample U133A human muscle biopsy dataset (11 groups: mutation-defined, extensive noise), and a 40 sample U74A inbred mouse lung dataset (8 groups: little noise). Performance was measured by the ability of the specific probe set algorithm, with and without detection p-value weighting, to cluster samples into the appropriate biological groups (unsupervised agglomerative clustering with F-measure values). Of the total random sampling analyses, 50% showed a highly statistically significant difference between probe set algorithms by ANOVA [F(4,10) > 14, p < 0.0001], with weighting by MAS 5.0 detection p-value showing significance in the mouse data by ANOVA [F(1,10) > 9, p < 0.013] and paired t-test [t(9) = −3.675, p = 0.005]. Probe set detection p-value weighting had the greatest positive effect on performance of dChip difference model, ProbeProfiler and RMA algorithms. Importantly, probe set algorithms did indeed perform differently depending on the specific project, most probably due to the degree of confounding noise. Our data indicate that significantly improved data analysis of mRNA profile projects can be achieved by optimizing the choice of probe set algorithm with the noise levels intrinsic to a project, with dChip difference model with MAS 5.0 detection p-value continuous weighting showing the best overall performance in both projects. Furthermore, both existing and newly developed probe set algorithms should incorporate a detection p-value weighting to improve performance. Availability: The Hierarchical Clustering Explorer 2.0 is available at http://www.cs.umd.edu/hcil/hce/. Murine arrays (40 samples) are publicly available at the PEPR resource (http://microarray.cnmcresearch.org/pgadatatable.asp; http://pepr.cnmcresearch.org; Chen et al., 2004).

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

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

Lifting the burden of history from adaptive query processing - Deshpande, Amol; Hellerstein,Joseph M. (Proceedings of the Thirtieth international conference on Very large data bases - Volume 30, 2004)
Adaptive query processing schemes attempt to re-optimize query plans during the course of query execution. A variety of techniques for adaptive query processing have been proposed, varying in the granularity at which they can make decisions [8]. The eddy [1] is the most aggressive of these techniques, with the flexibility to choose tuple-by-tuple how to order the application of operators. In this paper we identify and address a fundamental limitation of the original eddies proposal: the burden of history in routing. We observe that routing decisions have long-term effects on the state of operators in the query, and can severely constrain the ability of the eddy to adapt over time. We then propose a mechanism we call STAIRs that allows the query engine to manipulate the state stored inside the operators and undo the effects of past routing decisions. We demonstrate that eddies with STAIRs achieve both high adaptivity and good performance in the face of uncertainty, outperforming prior eddy proposals by orders of magnitude.

Light Collages: Lighting Design for Effective Visualization - Lee,Chang Ha; Hao,Xuejun; Varshney, Amitabh (Proceedings of the conference on Visualization '04, 2004)
We introduce Light Collages ¿ a lighting design system for effective visualization based on principles of human perception. Artists and illustrators enhance perception of features with lighting that is locally consistent and globally inconsistent. Inspired by these techniques, we design the placement of light sources to convey a greater sense of realism and better perception of shape with globally inconsistent lighting. Our algorithm segments the objects into local surface patches and uses a number of perceptual heuristics, such as highlights, shadows, and silhouettes, to enhance the perception of shape. We show our results on scientific and sculptured datasets.
Keywords: inconsistent lighting; light placement; lighting design; proximity shadows; scientific illustration; silhouette enhancement

Low-dimensional embedding with extra information - Bǎdoiu,M.; Demaine,E. D; Hajiaghayi, Mohammad T.; Indyk,P. (Proceedings of the twentieth annual symposium on Computational geometry, 2004)

Maintaining RDF views - Deng,Y.; Hung,E.; V.S. Subrahmanian (Tech. Rep. CS-TR-4612 (UMIACS-TR-2004-54), 2004)
Resource Description Framework (RDF) has been recommended bythe World Wide Web Consortium for integrating web data. RDF specifications are increasingly being stored in RDF databases. Many applications will maintain views over RDF databases – these views may describe resources of interest to the owner of the views. As data about the resources available on the web is subject to frequent change, there is a need to incrementally maintain such views. We present algorithms to maintain materialized RDF views when data is inserted into, deleted from, or modified in RDF database instances. We have developed a prototype of our algorithms. For each of these three cases, we compare the performance of our algorithm against the naive approach of storing RDF data in a relational database and using the standard view maintenance algorithm

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

Multi-align: Combining Linguistic and Statistical Techniques to Improve Alignments for Adaptable MT - Ayan,Necip; Dorr, Bonnie J; Habash,Nizar (Machine Translation: From Real Users to ResearchMachine Translation: From Real Users to Research, 2004)
An adaptable statistical or hybrid MT system relies heavily on the quality of word-level alignments of real-world data. Statistical alignment approaches provide a reasonable initial estimate for word alignment. However, they cannot handle certain types of linguistic phenomena such as long-distance dependencies and structural differences between languages. We address this issue in Multi-Align, a new framework for incremental testing of different alignment algorithms and their combinations. Our design allows users to tune their systems to the properties of a particular genre/domain while still benefiting from general linguistic knowledge associated with a language pair. We demonstrate that a combination of statistical and linguistically-informed alignments can resolve translation divergences during the alignment process.

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

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

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

Object tracking by adaptive feature extraction - Han,Bohyung; Davis, Larry S. (Image Processing, 2004. ICIP '04. 2004 International Conference on, 2004)
Tracking objects in the high-dimensional feature space is not only computationally expensive but also functionally inefficient. Selecting a low-dimensional discriminative feature set is a critical step to improve tracker performance. A good feature set for tracking can differ from frame to frame due to the changes in the background against the tracked object, and due to an on-line algorithm that adaptively determines a advantageous distinctive feature set. In this paper, multiple heterogeneous features are assembled, and likelihood images are constructed for various subspaces of the combined feature space. Then, the most discriminative feature is extracted by principal component analysis (PCA) based on those likelihood images. This idea is applied to the mean-shift tracking algorithm [D. Comaniciu et al., June 2000], and we demonstrate its effectiveness through various experiments.
Keywords: adaptive; algorithm; analysis; colour; component; extraction; feature; feature; heterogeneous; image; image; likelihood; Mean-shift; object; online; principal; tracking; tracking

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

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

Performance study of ECC-based collusion-resistant multimedia fingerprinting - He,S.; Wu,M. (Proceedings of the 38th CISS, 2004)
Digital fingerprinting is a tool to protect multimediacontent from illegal redistribution by uniquely marking copies of the content distributed to each user. Fingerprinting based on error correction coding (ECC) handle the important issue of how to embed the fingerprint into host data in an abstract way known as the marking assumptions, which often do not fully account for multimedia specific issues. In this paper, we examine the performance of ECC based fingerprinting by considering both coding and embedding issues. We provide performance comparison of ECC-based scheme and a major alternative of orthogonal fingerprinting. As averaging is a feasible and cost-effective collusion attack against multimedia fingerprints yet is generally not considered in the ECC-based system, we also investigate the resistance against averaging collusion and identify avenues for improving collusion resistance.

Polylysogeny and prophage induction by secondary infection in Vibrio cholerae - Espeland,Eric M.; Lipp,Erin K.; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2004)
Strains of Vibrio cholerae O1, biotypes El Tor and classical, were infected with a known temperate phage (ΦP15) and monitored over a 15-day period for prophage induction. Over the course of the experiment two morphologically and three genomically distinct virus-like particles were observed from the phage-infected El Tor strain by transmission electron microscopy and field inversion gel electrophoresis, respectively, whereas only one phage, ΦP15, was observed from the infected classical strain. In the uninfected El Tor culture one prophage was spontaneously induced after 6 days. No induction in either strain was observed after treatment with mitomycin C. Data indicate that El Tor biotypes of V. cholerae may be polylysogenic and that secondary infection can promote multiple prophage induction. These traits may be important in the transfer of genetic material among V. cholerae by providing an environmentally relevant route for multiple prophage propagation and transmission.

Preschool children's use of mouse buttons - Hourcade,J. P; Bederson, Benjamin B.; Druin, Allison (CHI'04 extended abstracts on Human factors in computing systems, 2004)

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

Real-time rendering of translucent meshes - Hao,Xuejun; Varshney, Amitabh (ACM Trans. Graph., 2004)
Subsurface scattering is important for photo-realistic rendering of translucent materials. We make approximations to the BSSRDF model and propose a simple lighting model to simulate the effects on translucent meshes. Our approximations are based on the observation that subsurface scattering is relatively local due to its exponential falloff.In the preprocessing stage we build subsurface scattering neighborhood information, which includes all the vertices within effective scattering range from each vertex. We then modify the traditional local illumination model into a run-time two-stage process. The first stage involves computation of reflection and transmission of light on surface vertices. The second stage bleeds in scattering effects from a vertex's neighborhood to generate the final result. We then merge the run-time two-stage process into a run-time single-stage process using precomputed integrals, and reduce the complexity of our run-time algorithm to O(N), where N is the number of vertices. The selection of the optimum set size for precomputed integrals is guided by a standard imagespace error-metric. Furthermore, we show how to compress the precomputed integrals using spherical harmonics. We compensate for the inadequacy of spherical harmonics for storing high frequency components by a reference points scheme to store high frequency components of the precomputed integrals explicitly. With this approach, we greatly reduce memory usage without loss of visual quality under a high-frequency lighting environment and achieve interactive frame rates for medium-sized scenes. Our model is able to capture the most important features of subsurface scattering: reflection and transmission due to multiple scattering.
Keywords: BSSRDF; local illumination; reflection models; subsurface scattering

Reducing complexity assumptions for statistically-hiding commitment - Horvitz,O.; Katz, Jonathan; Koo,C. Y; Morselli,R. (In EUROCRYPT, 2004)
Determining the minimal assumptions needed to construct various cryptographic buildingblocks has been a focal point of research in theoretical cryptography. For most — but not all! — cryptographic primitives, complexity assumptions both necessary and sufficient for their existence are known. Here, we revisit the following, decade-old question: what are the minimal assumptions needed to construct a statistically-hiding bit commitment scheme? Previously, it was known how to construct such schemes based on any one-way permutation. In this work, we show that regular one-way functions suffice. We show two constructions of statistically-hiding commitment schemes from regular one-way functions. Our first construction is more direct, and serves as a “stepping-stone” for our second construction which has improved round complexity. Of independent interest, as part of our work we show a compiler transforming any commitment scheme which is statistically-hiding against an honest-but-curious receiver to one which is statistically-hiding against a malicious receiver. This demonstrates the equivalence of these two formulations of the problem.

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

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

Running on the bare metal with GeekOS - Hovemeyer, David; Hollingsworth, Jeffrey K; Bhattacharjee, Bobby (Proceedings of the 35th SIGCSE technical symposium on Computer science education, 2004)
Undergraduate operating systems courses are generally taught using one of two approaches: abstract or concrete. In the abstract approach, students learn the concepts underlying operating systems theory, and perhaps apply them using user-level threads in a host operating system. In the concrete approach, students apply concepts by working on a real operating system kernel. In the purest manifestation of the concrete approach, students implement operating system projects that run on real hardware.GeekOS is an instructional operating system kernel which runs on real hardware. It provides the minimum functionality needed to schedule threads and control essential devices on an x86 PC. On this foundation, we have developed projects in which students build processes, semaphores, a multilevel feedback scheduler, paged virtual memory, a filesystem, and inter-process communication. We use the Bochs emulator for ease of development and debugging. While this approach (tiny kernel run on an emulator) is not new, we believe GeekOS goes further towards the goal of combining realism and simplicity than previous systems have.
Keywords: education; emulation; Hardware; Operating systems

Schistosoma mansoni genome project: an update - LoVerde,Philip T.; Hirai,Hirohisa; Merrick,Joseph M; Lee,Norman H; El‐Sayed, Najib M. (Parasitology International, 2004)
A schistosome genome project was initiated by the World Health Organization in 1994 with the notion that the best prospects for identifying new targets for drugs, vaccines, and diagnostic development lie in schistosome gene discovery, development of chromosome maps, whole genome sequencing and genome analysis. Schistosoma mansoni has a haploid genome of 270 Mb contained on 8 pairs of chromosomes. It is estimated that the S. mansoni genome contains between 15 000 and 25 000 genes. There are approximately 16 689 ESTs obtained from diverse libraries representing different developmental stages of S. mansoni, deposited in the NCBI EST database. More than half of the deposited sequences correspond to genes of unknown function. Approximately 40-50% of the sequences form unique clusters, suggesting that approximately 20-25% of the total schistosome genes have been discovered. Efforts to develop low resolution chromosome maps are in progress. There is a genome sequencing program underway that will provide 3X sequence coverage of the S. mansoni genome that will result in approximately 95% gene discovery. The genomics era has provided the resources to usher in the era of functional genomics that will involve microarrays to focus on specific metabolic pathways, proteomics to identify relevant proteins and protein-protein interactions to understand critical parasite pathways. Functional genomics is expected to accelerate the development of control and treatment strategies for schistosomiasis.
Keywords: Chromosome mapping; Gene discovery; Genomics; Schistosoma mansoni

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

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

Sequential kernel density approximation through mode propagation: applications to background modeling - Han,B.; Comaniciu, D.; Davis, Larry S. (Proc. ACCV, 2004)
Density-based modeling of visual features is very commonin computer vision, either by using non-parametric techniques or through representing the underlying density function as a weighted sum of Gaussians. A number of real-time tasks such as background modeling or modeling the appearance of a moving target require sequential density estimation, where new data is incorporated in the model as it becomes avail- able. Nevertheless, current methods for updating the den- sity function either lack flexibility, by fixing the number of Gaussians in the mixture, or require large memory amounts, by maintaining a non-parametric representation of the den- sity. This paper presents an efficient method for recursive density approximation that relies on the propagation of the density modes. At each time step, the modes of the density are re-estimated and a Gaussian component is assigned to each mode. The covariance of each component is derived from the Hessian matrix estimated at the mode location. To detect the modes we employ the variable-bandwidth mean shift. While the proposed density representation is mem- ory efficient (which is typical for mixture densities), it in- herits the flexibility of non-parametric methods, by allow- ing the number of modes to adapt in time. We show that the same mode propagation principle applies for subspaces derived from eigen analysis. Extensive experimental back- ground modeling results demonstrate the performance of the method.

A serverless 3D world - Tanin,Egemen; Harwood,Aaron; Samet, Hanan; Nutanong,Sarana; Truong,Minh Tri (Proceedings of the 12th annual ACM international workshop on Geographic information systems, 2004)
Online multi-participant virtual-world systems have attracted significant interest from the Internet community but are hindered by their inability to efficiently support interactivity for a large number of participants. Current solutions divide a large virtual-world into a few mutually exclusive zones, with each zone controlled by a different server, and/or limit the number of participants per server or per virtual-world. Peer-to-Peer (P2P) systems are known to provide excellent scalability in a networked environment (one peer is introduced to the system by each participant), however current P2P applications can only provide file sharing and other forms of relatively simple data communications. In this paper, we present a generic 3D virtual-world application that runs on a P2P network with no central administration or server. Two issues are addressed by this paper to enable such a spatial application on a P2P network. First, we demonstrate how to index and query a 3D space on a dynamic distributed network. Second, we show how to build such a complex application from the ground level of a P2P routing algorithm. Our work leads to new directions for the development of online virtual-worlds that we believe can be used for many government, industry, and public domain applications.
Keywords: distributed hash tables; peer-to-peer systems; spatial data; virtual-worlds

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

Studying code development for high performance computing: the HPCS program - Carver, J.; Asgari, S.; Basili, Victor R.; Hochstein, L.; Hollingsworth, Jeffrey K; Shull, F.; Zelkowitz, Marvin V (First International Workshop On Software Engineering for High Performance Computing System Applications, 2004)

Symbolic MT With Statistical NLP Components - Dorr, Bonnie J; Habash,Nizar Y; Monz,Christof (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This reports provides an overview of the findings and software that have evolved from the "Symbolic MT with Statistical NLP Components" project over the last year. We present the major goals that have been achieved and discuss some of the open issues that we intend to address in the near future. This report also contains some details on the usage of some software that has been implemented during the project.
Keywords: *MACHINE TRANSLATION; computational linguistics; COMPUTER PROGRAMS; CYBERNETICS; DIVERGENCE UNRAVELING; GHMT(GENERATION-HEAVY MACHINE TRANSLATION); INFORMATION SCIENCE; linguistics; natural language; RESOURCE PROJECTION

TOSS: an extension of TAX with ontologies and similarity queries - Hung,Edward; Deng,Yu; V.S. Subrahmanian (Proceedings of the 2004 ACM SIGMOD international conference on Management of data, 2004)
TAX is perhaps the best known extension of the relational algebra to handle queries to XML databases. One problem with TAX (as with many existing relational DBMSs) is that the semantics of terms in a TAX DB are not taken into account when answering queries. Thus, even though TAX answers queries with 100% precision, the recall of TAX is relatively low. Our TOSS system improves the recall of TAX via the concept of a similarity enhanced ontology (SEO). Intuitively, an ontology is a set of graphs describing relationships (such as isa, partof, etc.) between terms in a DB. An SEO also evaluates how similarities between terms (e.g. "J. Ullman", "Jeff Ullman", and "Jeffrey Ullman") affect ontologies. Finally, we show how the algebra proposed in TAX can be extended to take SEOs into account. The result is a system that provides a much higher answer quality than TAX does alone (quality is defined as the square root of the product of precision and recall). We experimentally evaluate the TOSS system on the DBLP and SIGMOD bibliographic databases and show that TOSS has acceptable performance.
Keywords: ontologies; semantic integration of heterogeneous data; similarity enhancement; XML databases

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

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

Update operations on 3D simplicial decompositions of non-manifold objects - De Floriani, Leila; Hui,Annie (Proceedings of the ninth ACM symposium on Solid modeling and applications, 2004)
We address the problem of updating non-manifold mixed-dimensional objects, described by three-dimensional simplicial complexes embedded in 3D Euclidean space. We consider two local update operations, edge collapse and vertex split, which are the most common operations performed for simplifying a simplicial complex. We examine the effect of such operations on a 3D simplicial complex, and we describe algorithms for edge collapse and vertex split on a compact representation of a 3D simplicial complex, that we call the Non-Manifold Indexed data structure with Adjacencies (NMIA). We also discuss how to encode the information needed for performing a vertex split and an edge collapse on a 3D simplicial complex. The encoding of such information together with the algorithms for updating the NMIA data structure form the basis for defining progressive as well as multi-resolution representations for objects described by 3D simplicial complexes and for extracting variable-resolution object descriptions.

Use of Minimal Lexical Conceptual Structures for Single-Document Summarization - Dorr, Bonnie J; Habash,Nizar Y; Monz,Christof; Schwartz,Richard (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2004)
This reports provides an overview of the findings and software that have evolved from the Use of Minimal Lexical Conceptual Structures for Single-Document Summarization project over the last six months. We present the major goals that have been achieved and discuss some of the open issues that we intend to address in the near future. This report also contains some details on the usage of some software that has been implemented during the project.
Keywords: *COMPUTATIONAL LINGUISTICS; AUTOMATIC HEADLINE GENERATION; CYBERNETICS; DOCUMENT SUMMARIZATION; Information retrieval; INFORMATION SCIENCE; linguistics; Machine translation

Using Hardware Counters to Automatically Improve Memory Performance - Tikir, Mustafa M.; Hollingsworth, Jeffrey K (Proceedings of the 2004 ACM/IEEE conference on Supercomputing, 2004)
In this paper, we introduce a profile-driven online page migration scheme and investigate its impact on the performance of multithreaded applications. We use lightweight, inexpensive plug-in hardware counters to profile the memory access behavior of an application, and then migrate pages to memory local to the most frequently accessing processor. Using the Dyninst runtime instrumentation combined with hardware counters, we were able to add page migration capabilities to the system without having to modify the operating system kernel, or to re-compile application programs. This approach reduced the total number of non-local memory accesses of applications by up to 90%. Even on a system with small remote to local memory access latency rations, this resulted in up to 16% improvement in execution time.

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

Whole-genome shotgun assembly and comparison of human genome assemblies - Istrail,S.; Sutton,G. G; Florea,L.; Halpern,A. L; Mobarry,C. M; Lippert,R.; Walenz,B.; Shatkay,H.; Dew,I.; Miller,J. R; others (Proceedings of the National Academy of Sciences of the United States of America, 2004)

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

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

A 4-Year Study of the Epidemiology of Vibrio Cholerae in Four Rural Areas of Bangladesh - Sack,R. Bradley; Siddique,A. Kasem; Longini,Ira M.; Nizam,Azhar; Yunus,Md; M. Sirajul Islam; Morris,Jr; Ali,Afsar; Huq,Anwar; Nair,G. Balakrish; Qadri,Firdausi; Faruque,Shah M.; et al. (Journal of Infectious DiseasesJ Infect Dis., 2003)
How Vibrio cholerae spreads around the world and what determines its seasonal peaks in endemic areas are not known. These features of cholera have been hypothesized to be primarily the result of environmental factors associated with aquatic habitats that can now be identified. Since 1997, fortnightly surveillance in 4 widely separated geographic locations in Bangladesh has been performed to identify patients with cholera and to collect environmental data. A total of 5670 patients (53% <5 years of age) have been studied; 14.3% had cholera (10.4% due to V. cholerae O1 El Tor, 3.8% due to O139). Both serogroups were found in all locations; outbreaks were seasonal and often occurred simultaneously. Water-use patterns showed that bathing and washing clothes in tube-well water was significantly protective in two of the sites. These data will be correlated with environmental factors, to develop a model for prediction of cholera outbreaks

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

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

Approximating the domatic number - Feige,U.; Halldórsson,M.M.; Kortsarz,G.; Srinivasan, Aravind (SIAM Journal on Computing, 2003)
A set of vertices in a graph is a dominating set if every vertex outside the set hasa neighbor in the set. The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices, δ the minimum degree, and ∆ the maximum degree. We show that every graph has a domatic partition with (1 − o(1))(δ + 1)/ ln n dominating sets and, moreover, that such a domatic partition can be found in polynomial-time. This implies a (1 + o(1)) ln n-approximation algorithm for domatic number, since the domatic number is always at most δ+1. We also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every ϵ > 0, a (1 − ϵ) ln n-approximation implies that NP ⊆ DTIME(nO(log log n)). This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also show that every graph has a domatic partition with (1 − o(1))(δ + 1)/ ln ∆ dominating sets, where the “o(1)” term goes to zero as ∆ increases. This can be turned into an efficient algorithm that produces a domatic partition of Ω(δ/ ln ∆) sets.

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

Bringing Treasures to the Surface: Previews and Overviews in a Prototype for the Library of Congress National Digital Library - Marchionini,A.S.; Nation,D.; Karasik,S.; Cronnell,T.; Shneiderman, Ben; Spotfire,V.D.M.U.; Bederson, Benjamin B.; Data,T.S.; Hochheiser,H.; Shneiderman, Ben; others (The craft of information visualization: readings and reflections, 2003)

A categorial variation database for English - Habash,Nizar; Dorr, Bonnie J (Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1, 2003)
We describe our approach to the construction and evaluation of a large-scale database called "CatVar" which contains categorial variations of English lexemes. Due to the prevalence of cross-language categorial variation in multilingual applications, our categorial-variation resource may serve as an integral part of a diverse range of natural language applications. Thus, the research reported herein overlaps heavily with that of the machine-translation, lexicon-construction, and information-retrieval communities.We apply the information-retrieval metrics of precision and recall to evaluate the accuracy and coverage of our database with respect to a human-produced gold standard. This evaluation reveals that the categorial database achieves a high degree of precision and recall. Additionally, we demonstrate that the database improves on the linkability of Porter stemmer by over 30%.

CATVAR: A database of categorial variations for English - Habash,N.; Dorr, Bonnie J (Proceedings of the MT Summit, 2003)
We present a new large-scale database called “CatVar” (Habash and Dorr, 2003) which contains categorial variationsof English lexemes. Due to the prevalence of cross-language categorial variation in multilingual applications, our categorial-variation resource may serve as an integral part of a diverse range of natural language applications. Thus, the research reported herein overlaps heavily with that of the machine-translation, lexicon-construction, and information- retrieval communities. We demonstrate this database, embedded in a graphical interface; we also show a GUI for user input of corrections to the database.

Characterization of a Vibrio cholerae phage isolated from the coastal water of Peru - Talledo,Miguel; Rivera,Irma N. G.; Lipp,Erin K.; Neale,Angela; Karaolis,David; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2003)
A Vibrio cholerae bacteriophage, family Myoviridae, was isolated from seawater collected from the coastal water of Lima, Peru. Genome size was estimated to be 29 kbp. The temperate phage was specific to V. cholerae and infected 12/13 V. cholerae O1 strains and half of the four non-O1/non-O139 strains tested in this study. Vibrio cholerae O139 strains were resistant to infection and highest infection rates were obtained in low nutrient media amended with NaCl or prepared using seawater as diluent.

A collaborative digital library for children - Druin, Allison; Revelle,G.; Bederson, Benjamin B.; Hourcade,J. P; Farber,A.; Lee,J.; Campbell,D. (Journal of Computer Assisted Learning, 2003)

Comparing bootstrap and posterior probability values in the four-taxon case - Cummings, Michael P.; Handley,S. A; Myers,D. S; Reed,D. L; Rokas,A.; Winka,K. (Syst Biol, 2003)
Assessment of the reliability of a given phylogenetic hypothesis is an important step in phylogenetic analysis. Historically, the nonparametric bootstrap procedure has been the most frequently used method for assessing the support for specific phylogenetic relationships. The recent employment of Bayesian methods for phylogenetic inference problems has resulted in clade support being expressed in terms of posterior probabilities. We used simulated data and the four-taxon case to explore the relationship between nonparametric bootstrap values (as inferred by maximum likelihood) and posterior probabilities (as inferred by Bayesian analysis). The results suggest a complex association between the two measures. Three general regions of tree space can be identified: (1) the neutral zone, where differences between mean bootstrap and mean posterior probability values are not significant, (2) near the two-branch corner, and (3) deep in the two-branch corner. In the last two regions, significant differences occur between mean bootstrap and mean posterior probability values. Whether bootstrap or posterior probability values are higher depends on the data in support of alternative topologies. Examination of star topologies revealed that both bootstrap and posterior probability values differ significantly from theoretical expectations; in particular, there are more posterior probability values in the range 0.85-1 than expected by theory. Therefore, our results corroborate the findings of others that posterior probability values are excessively high. Our results also suggest that extrapolations from single topology branch-length studies are unlikely to provide any general conclusions regarding the relationship between bootstrap and posterior probability values.

Comparing user-assisted and automatic query translation - He,D.; Wang,J.; Oard, Douglas; Nossal,M. (Advances in cross-language information retrieval, 2003)

DART: a framework for regression testing "nightly/daily builds" of GUI applications - Memon, Atif M.; Banerjee,I.; Hashmi,N.; Nagarajan,A. (Software Maintenance, 2003. ICSM 2003. Proceedings. International Conference on, 2003)
"Nightly/daily building and smoke testing" have become widespread since they often reveal bugs early in the software development process. During these builds, software is compiled, linked, and (re)tested with the goal of validating its basic functionality. Although successful for conventional software, smoke tests are difficult to develop and automatically rerun for software that has a graphical user interface (GUI). In this paper, we describe a framework called DART (daily automated regression tester) that addresses the needs of frequent and automated re-testing of GUI software. The key to our success is automation: DART automates everything from structural GUI analysis; test case generation; test oracle creation; to code instrumentation; test execution; coverage evaluation; regeneration of test cases; and their re-execution. Together with the operating system's task scheduler, DART can execute frequently with little input from the developer/tester to retest the GUI software. We provide results of experiments showing the time taken and memory required for GUI analysis, test case and test oracle generation, and test execution. We also empirically compare the relative costs of employing different levels of detail in the GUI test cases.
Keywords: automated retesting; automatic test software; coverage evaluation; daily automated regression tester; DART; frequent retesting; graphical user interface; Graphical user interfaces; GUI software; instrumentation coding; program testing; regression testing; Software development management; Software development process; Software maintenance; Software quality; structural GUI analysis; Test Case Generation; test cases regeneration; Test execution; test oracle creation

Data-parallel polygonization - Hoel,Erik G.; Samet, Hanan (Parallel Computing, 2003)
Data-parallel algorithms are presented for polygonizing a collection of line segments represented by a data-parallel bucket PMR quadtree, a data-parallel R-tree, and a data-parallel R+-tree. Such an operation is useful in a geographic information system (GIS). A sample performance comparison of the three data-parallel structures for this operation is also given.
Keywords: Data-parallel algorithms; Hierarchical spatial data structures; Lines; Polygonization

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

Desparately seeking cebuano - Oard, Douglas; David Doermann; Dorr, Bonnie J; He,D.; Resnik, Philip; Weinberg, Amy; Byrne,W.; Khudanpur,S.; Yarowsky,D.; Leuski,A.; others (Third Conference on Human Language Technologies, 2003)
This paper describes an effort to rapidly de-velop language resources and component tech- nology to support searching Cebuano news sto- ries using English queries. Results from the first 60 hours of the exercise are presented.

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

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

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

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

Dynamic querying for pattern identification in microarray and genomic data - Hochheiser,H.; Baehrecke,E. H; Mount, Stephen M.; Shneiderman, Ben (2003 International Conference on Multimedia and Expo, 2003. ICME '03. Proceedings, 2003)
Data sets involving linear ordered sequences are a recurring theme in bioinformatics. Dynamic query tools that support exploration of these data sets can be useful for identifying patterns of interest. This paper describes the use of one such tool - timesearcher - to interactively explore linear sequence data sets taken from two bioinformatics problems. Microarray time course data sets involve expression levels for large numbers of genes over multiple time points. Timesearcher can be used to interactively search these data sets for genes with expression profiles of interest. The occurrence frequencies of short sequences of DNA in aligned exons can be used to identify sequences that play a role in the pre-mRNA splicing. Timesearcher can be used to search these data sets for candidate splicing signals.
Keywords: Bioinformatics; data sets; Displays; dynamic querying; expression profiles; Frequency; Gene expression; genes; Genetics; genomic data; Genomics; linear ordered sequences; macromolecules; medical signal processing; Mice; Microarray; pattern identification; pattern recognition; premRNA splicing; Query processing; sequences; Signal processing; splicing; TimeSearcher

Dynamic rebinding for marshalling and update, with destruct-time ? - Bierman,Gavin; Hicks, Michael W.; Sewell,Peter; Stoyle,Gareth; Wansbrough,Keith (Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, 2003)
Most programming languages adopt static binding, but for distributed programming an exclusive reliance on static binding is too restrictive: dynamic binding is required in various guises, for example when a marshalled value is received from the network, containing identifiers that must be rebound to local resources. Typically it is provided only by ad-hoc mechanisms that lack clean semantics.In this paper we adopt a foundational approach, developing core dynamic rebinding mechanisms as extensions to simply-typed call-by-value ? -calculus. To do so we must first explore refinements of the call-by-value reduction strategy that delay instantiation, to ensure computations make use of the most recent versions of rebound definitions. We introduce redex-time and destruct-time strategies. The latter forms the basis for a ?marsh calculus that supports dynamic rebinding of marshalled values, while remaining as far as possible statically-typed. We sketch an extension of ? marsh with concurrency and communication, giving examples showing how wrappers for encapsulating untrusted code can be expressed. Finally, we show that a high-level semantics for dynamic updating can also be based on the destruct-time strategy, defining a ?marsh calculus with simple primitives to provide type-safe updating of running code. We thereby establish primitives and a common semantic foundation for a variety of real-world dynamic rebinding requirements.
Keywords: distributed programming; dynamic binding; dynamic update; lambda calculus; marshalling; programming languages; serialisation

Electronic voting system usability issues - Bederson, Benjamin B.; Lee,B.; Sherman,R.M.; Herrnson,P.S.; Niemi,R.G. (Proceedings of the SIGCHI conference on Human factors in computing systems, 2003)

Energy reduction techniques for multimedia applications with tolerance to deadline misses - Hua,S.; Qu,G.; Bhattacharyya, Shuvra S. (Proceedings of the 40th annual Design Automation Conference, 2003)

Evaluating Translational Correspondence using Annotation Projection - Hwa,R.; Resnik, Philip; Weinberg, Amy; Kolak,O. (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2003)
Recently, statistical machine translation models have begun to take advantage of higherlevel 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 En- glish 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.

Exploring the probabilistic design space of multimedia systems - Shaoxiong Hua; Gang Qu; Bhattacharyya, Shuvra S. (14th IEEE International Workshop on Rapid Systems Prototyping, 2003. Proceedings, 2003)
In this paper, we propose the novel concept of probabilistic design for multimedia systems and a methodology to quickly explore such design space at an early design stage. The probabilistic design is motivated by the challenge of how to design, but not over-design, multimedia embedded systems while systematically incorporating such application's performance requirements, uncertainties in execution time, and tolerance for reasonable execution failures. Our goal is to bridge the gap between real-time analysis and embedded software implementation for rapid and economic (multimedia) system prototyping. Our method takes advantage of multimedia system's unique features mentioned above to relax the rigid hardware requirements for software implementation and eventually avoid over-designing the system.
Keywords: economic system prototyping; embedded software implementation; Embedded system; Energy consumption; execution time uncertainties; Hardware; multimedia embedded systems; multimedia system prototyping; multimedia systems; performance requirements; probabilistic design space; rapid system prototyping; Real time systems; real-time analysis; reasonable execution failure tolerance; Resource management; software prototyping; Space exploration; Streaming media; systems analysis; Timing; Uncertainty

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

Formalizing dynamic software updating - Bierman,G.; Hicks, Michael W.; Sewell,P.; Stoyle,G. (Proceedings of the Second International Workshop on Unanticipated Software Evolution (USE), 2003)
Dynamic software updating (DSU) enables running programs to beupdated with new code and data without interrupting their execution. A number of DSU systems have been designed, but there is still little rig- orous understanding of how to use DSU technology so that updates are safe. As a first step in this direction, we introduce a small update calculus with a precise mathematical semantics. The calculus is formulated as an extension of a typed lambda calculus, and supports updating technology similar to that of the programming language Erlang [2]. Our goal is to provide a simple yet expressive foundation for reasoning about dynam- ically updateable software. In this paper, we present the details of the calculus, give some examples of its expressive power, and discuss how it might be used or extended to guarantee safety properties.

A forward-secure public-key encryption scheme - Canetti,R.; Halevi,S.; Katz, Jonathan (Advances in Cryptology—Eurocrypt 2003, 2003)
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious and realistic concern. In an effort to mitigate the damage caused by exposure of secret data (e.g., keys) stored on such devices, the paradigm of forward security was introduced. In a forward-secure scheme, secret keys are updated at regular periods of time; furthermore, exposure of a secret key corresponding to a given time period does not enable an adversary to “break” the scheme (in the appropriate sense) for any prior time period. A number of constructions of forward-secure digital signature schemes, key-exchange protocols, and symmetric-key schemes are known.We present the first constructions of a (non-interactive) forward-secure public-key encryption scheme. Our main construction achieves security against chosen plaintext attacks under the decisional bilinear Diffie-Hellman assumption in the standard model. It is practical, and all complexity parameters grow at most logarithmically with the total number of time periods. The scheme can also be extended to achieve security against chosen ciphertext attacks.

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

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

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

HRTF personalization using anthropometric measurements - Zotkin,Dmitry N; Hwang,J.; Duraiswami, Ramani; Davis, Larry S. (Applications of Signal Processing to Audio and Acoustics, 2003 IEEE Workshop on., 2003)
Individualized head related transfer functions (HRTFs) are needed for accurate rendering of spatial audio, which is important in many applications. Since these are relatively tedious to acquire, they may not be acceptable for some applications. A number of studies have sought to perform simple customization of the HRTF. We propose and test a strategy for HRTF personalization, based on matching certain anthropometric ear parameters with the HRTF database, and the incorporation of a low-frequency "head-and-torso" model. We present preliminary tests aimed at evaluation of this customization. Results show that the approach improves both the accuracy of the localization and subjective perception of the virtual auditory scene.
Keywords: acoustic; anthropometric; audio; audio; auditory; Ear; functions; Head; head-and-torso; HRTF; individualized; localization; measurements; model; models; parameters; perception; personalization; physiological; processing; related; scattering; scene; signal; sound; spatial; subjective; transfer; virtual; wave

Hybrid Natural Language Generation from Lexical Conceptual Structures - Habash,Nizar; Dorr, Bonnie J; Traum,David (Machine Translation, 2003)
This paper describes Lexogen, a system for generating natural-languagesentences from Lexical Conceptual Structure, an interlingualrepresentation. The system has been developed as part of aChinese–English Machine Translation (MT) system; however, it isdesigned to be used for many other MT language pairs and naturallanguage applications. The contributions of this work include: (1)development of a large-scale Hybrid Natural Language Generation system withlanguage-independent components; (2) enhancements to an interlingualrepresentation and associated algorithm forgeneration from ambiguous input; (3) development of an efficientreusable language-independent linearization module with a grammardescription language that can be used with other systems; (4)improvements to an earlier algorithm forhierarchically mapping thematic roles to surface positions; and (5)development of a diagnostic tool for lexicon coverage and correctnessand use of the tool for verification of English, Spanish, and Chineselexicons. An evaluation of Chinese–English translation quality showscomparable performance with a commercial translation system. Thegeneration system can also be extended to other languages and this isdemonstrated and evaluated for Spanish.

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

Improved search heuristics for the sa-tree - Hjaltason,Gı́sli R.; Samet, Hanan (Pattern Recognition Letters, 2003)
The sa-tree is an interesting metric space indexing structure that is inspired by the Voronoi diagram. In essence, the sa-tree records a portion of the Delaunay graph of the data set, a graph whose vertices are the Voronoi cells, with edges between adjacent cells. An improvement is presented on the original search strategy for the sa-tree. This consists of details on the intuition behind the improvement as well as the original search strategy and a proof of their correctness. Furthermore, it is shown how to adapt an incremental nearest neighbor algorithm to the sa-tree, which allows computing nearest neighbor in a progressive manner. Unlike other adaptations, the resulting algorithm does not take the unnecessary steps to ensure that keys of “node” elements are monotonically non-decreasing.
Keywords: distance-based indexing; Metric spaces; Nearest neighbor algorithms

Improving the Arabidopsis genome annotation using maximal transcript alignment assemblies - Haas,Brian J.; Delcher,Arthur L.; Mount, Stephen M.; Wortman,Jennifer R.; Jr,Roger K. Smith; Hannick,Linda I.; Maiti,Rama; Ronning,Catherine M.; Rusch,Douglas B; Town,Christopher D.; Salzberg,Steven L.; White,Owen (Nucleic Acids ResearchNucl. Acids Res., 2003)
The spliced alignment of expressed sequence data to genomic sequence has proven a key tool in the comprehensive annotation of genes in eukaryotic genomes. A novel algorithm was developed to assemble clusters of overlapping transcript alignments (ESTs and full‐length cDNAs) into maximal alignment assemblies, thereby comprehensively incorporating all available transcript data and capturing subtle splicing variations. Complete and partial gene structures identified by this method were used to improve The Institute for Genomic Research Arabidopsis genome annotation (TIGR release v.4.0). The alignment assemblies permitted the automated modeling of several novel genes and >1000 alternative splicing variations as well as updates (including UTR annotations) to nearly half of the ∼27 000 annotated protein coding genes. The algorithm of the Program to Assemble Spliced Alignments (PASA) tool is described, as well as the results of automated updates to Arabidopsis gene annotations.

In vivo filtering of in vitro expression data reveals MyoD targets - Zhao,Po; Seo,Jinwook; Wang,Zuyi; Wang,Yue; Shneiderman, Ben; Hoffman,Eric P (Comptes Rendus Biologies, 2003)
A published set of downstream targets of MyoD defined in a well-controlled in vitro experiment was filtered for relevance to muscle regeneration using a 27-time-point in vivo murine regeneration series. Using interactive hierarchical and Bayes soft clustering, only a minority of the targets defined in vitro can be confirmed in vivo (∼50% of induced transcripts, and none of repressed transcripts). This approach provided strong support that 18 targets including of MyoD are biologically relevant during myoblast differentiation. To cite this article: P. Zhao et al., C. R. Biologies 326 (2003).
Keywords: clustering; expression profiling; Microarray; microréseaux; muscle regeneration; MyoD; profil d'expression; régénération musculaire; regroupement

Index-driven similarity search in metric spaces (Survey Article) - Hjaltason,Gisli R.; Samet, Hanan (ACM Trans. Database Syst., 2003)
Similarity search is a very important operation in multimedia databases and other database applications involving complex objects, and involves finding objects in a data set S similar to a query object q, based on some similarity measure. In this article, we focus on methods for similarity search that make the general assumption that similarity is represented with a distance metric d. Existing methods for handling similarity search in this setting typically fall into one of two classes. The first directly indexes the objects based on distances (distance-based indexing), while the second is based on mapping to a vector space (mapping-based approach). The main part of this article is dedicated to a survey of distance-based indexing methods, but we also briefly outline how search occurs in mapping-based methods. We also present a general framework for performing search based on distances, and present algorithms for common types of queries that operate on an arbitrary "search hierarchy." These algorithms can be applied on each of the methods presented, provided a suitable search hierarchy is defined.
Keywords: distance-based indexing; Hiearchical metric data structures; nearest neighbor queries; range queries; Ranking; similarity searching

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

Integrality ratio for group Steiner trees and directed steiner trees - Halperin,Eran; Kortsarz,Guy; Krauthgamer,Robert; Srinivasan, Aravind; Wang,Nan (Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, 2003)
We present an Ω(log2k) lower bound on the integrality ratio of the flow-based relaxation for the Group Steiner Tree problem, where k denotes the number of groups; this holds even for input graphs that are Hierarchically Well-Separated Trees, introduced by Bartal [Symp. Foundations of Computer Science, pp. 184--193, 1996], in which case this lower bound is tight. This relaxation appears to be the only one that have been studied for the problem, as well as for its generalization, the Directed Steiner Tree problem. For the latter problem, our results imply an Ω(log2n/(log logn)2) integrality ratio, where n is the number of vertices in the graph. For both problems, this is the first known lower bound on the integrality ratio that is superlogarithmic in the input size. We also show algorithmically that the integrality ratio for Group Steiner Tree is much better for certain families of instances, which helps pinpoint the types of instances that appear to be most difficult to approximate.

Interactive color mosaic and dendrogram displays for signal/noise optimization in microarray data analysis - Seo,J.; Bakay,M.; Zhao,P.; Chen,Y.W.; Clarkson,P.; Shneiderman, Ben; Hoffman,E.P. (Multimedia and Expo, 2003. ICME'03. Proceedings. 2003 International Conference on, 2003)
Data analysis and visualization is strongly influenced by noise and noise filters. There are multiple sources of oisein microarray data analysis, but signal/noise ratios are rarely optimized, or even considered. Here, we report a noise analysis of a novel 13 million oligonucleotide dataset - 25 human U133A (~500,000 features) profiles of patient muscle biposies. We use our recently described interactive visualization tool, the Hierarchical Clustering Explorer (HCE) to systemically address the effect of different noise filters on resolution of arrays into orrectbiological groups (unsupervised clustering into three patient groups of known diagnosis). We varied probe set interpretation methods (MAS 5.0, RMA), resent callfilters, and clustering linkage methods, and investigated the results in HCE. HCE interactive features enabled us to quickly see the impact of these three variables. Dendrogram displays showed the clustering results systematically, and color mosaic displays provided a visual support for the results. We show that each of these three variables has a strong effect on unsupervised clustering. For this dataset, the strength of the biological variable was maximized, and noise minimized, using MAS 5.0, 10% present call filter, and Average Group Linkage. We propose a general method of using interactive tools to identify the optimal signal/noise balance or the optimal combination of these three variables to maximize the effect of the desired biological variable on data interpretation.

Interactive subsurface scattering for translucent meshes - Hao,Xuejun; Baby,Thomas; Varshney, Amitabh (Proceedings of the 2003 symposium on Interactive 3D graphics, 2003)
We propose a simple lighting model to incorporate subsurface scattering effects within the local illumination framework. Subsurface scattering is relatively local due to its exponential falloff and has little effect on the appearance of neighboring objects. These observations have motivated us to approximate the BSSRDF model and to model subsurface scattering effects by using only local illumination. Our model is able to capture the most important features of subsurface scattering: reflection and transmission due to multiple scattering.In our approach we build the neighborhood information as a preprocess and modify the traditional local illumination model into a run-time two-stage process. In the first stage we compute the reflection and transmission of light on the surface. The second stage involves bleeding the scattering effects from a vertex's neighborhood to produce the final result. We then show how to merge the run-time two-stage process into a run-time single-stage process using precomputed integral. The complexity of our run-time algorithm is O(N), where N is the number of vertices. Using this approach, we achieve interactive frame rates with about one to two orders of magnitude speedup compared with the state-of-the-art methods.
Keywords: BSSRDF; local illumination; reflection models; subsurface scattering