Understanding the High-Performance-Computing Community: A Software Engineer's Perspective - Basili, Victor R.; Carver, J. C; Cruzes, D.; Hochstein, L. M; Hollingsworth, Jeffrey K; Shull, F.; Zelkowitz, Marvin V (Software, IEEE, 2008)
Computational scientists developing software for HPC systems face unique software engineering issues. Attempts to transfer SE technologies to this domain must take these issues into account.
Keywords: community; software; computational; engineering; engineering; software; Science; software; high-performance-computing

User-assisted query translation for interactive cross-language information retrieval - Oard, Douglas; He,Daqing; Wang,Jianqiang (Information Processing & Management, 2008)
Interactive Cross-Language Information Retrieval (CLIR), a process in which searcher and system collaborate to find documents that satisfy an information need regardless of the language in which those documents are written, calls for designs in which synergies between searcher and system can be leveraged so that the strengths of one can cover weaknesses of the other. This paper describes an approach that employs user-assisted query translation to help searchers better understand the system’s operation. Supporting interaction and interface designs are introduced, and results from three user studies are presented. The results indicate that experienced searchers presented with this new system evolve new search strategies that make effective use of the new capabilities, that they achieve retrieval effectiveness comparable to results obtained using fully automatic techniques, and that reported satisfaction with support for cross-language searching increased. The paper concludes with a description of a freely available interactive CLIR system that incorporates lessons learned from this research.
Keywords: Cross-language information retrieval; Machine translation; User studies

Using wearable sensors and real time inference to understand human recall of routine activities - Klasnja,Predrag; Harrison,Beverly L.; LeGrand,Louis; LaMarca,Anthony; Jon Froehlich; Hudson,Scott E. (Proceedings of the 10th international conference on Ubiquitous computing, 2008)
Keywords: empirical evaluation; ESM; experience sampling method; recall accuracy; self-reports; survey frequency; user study

Verified enforcement of automaton-based information release policies - Swamy,N.; Hicks, Michael W. (Proceedings of the 2008 Workshop on Programming Languages and Analysis for Security. ACM Press, 2008)
Many organizations specify information release policies to describe the terms under which sensitive information may bereleased to other organizations. This paper presents a new approach for ensuring that security-critical software correctly enforces its information release policy. Our approach has two parts. First, an information release policy is specified as a security automaton written in a new language called AIR. Second, we enforce an AIR policy by translating it into an API for programs written in λAIR, a core formalism for a functional programming language. λAIR uses a novel combination of dependent, affine, and singleton types to ensure that the API is used correctly. As a consequence we can certify that programs written in λAIR meet the requirements of the original AIR policy specification.

Visualizing Functional Data with an Application to eBay’s Online Auctions - Chen,Chun-houh; Härdle,Wolfgang; Unwin,Antony; Jank,Wolfgang; Shmueli,Galit; Plaisant, Catherine; Shneiderman, Ben (Handbook of Data VisualizationHandbook of Data Visualization, 2008)
Technological advances in the measurement, collection, and storage of data have led tomore andmore complex data structures. Examples of such structures include measurements of the behavior of individuals over time, digitized two- or three-dimensional images of the brain, and recordings of three- or even four-dimensional movements of objects traveling through space and time. Such data, although recorded in a discrete fashion, are usually thought of as continuous objects that are represented by functional relationships. This gave rise to functional data analysis (FDA), which was made popular by the monographs of Ramsay and Silverman (1997, 2002), where the center of interest is a set of curves, shapes, objects, or, more generally, a set of functional observations , in contrast to classical statistics where interest centers on a set of data vectors. In that sense, functional data is not only different from the data structure studied in classical statistics, but it actually generalizes it. Many of these new data structures require new statistical methods to unveil the information that they carry.

Adaptive Detection for Group-Based Multimedia Fingerprinting - He,Shan; M. Wu (Signal Processing Letters, IEEE, 2007)
Grouping strategy has been proposed recently to leverage the prior knowledge on collusion pattern to improve collusion resistance in multimedia fingerprinting. However, the improvement is not consistent, as reduced performance of the existing group-based fingerprinting schemes than the non-grouped ones is observed when the grouping does not match the true collusion pattern well. In this letter, we propose a new adaptive detection method, where the threshold for the group detection can be adjusted automatically according to the detection statistics that reflect the underlying collusion pattern. Experimental results show that the proposed adaptive detection outperforms nonadaptive detection and provides consistent performance improvement over non-grouped orthogonal fingerprinting schemes under various collusion scenarios.
Keywords: adaptive; computing; security; data; detection; collusion; detection; group-based; fingerprinting; copy; fingerprinting; grouping; multimedia; of; orthogonal; pattern; detection; protection; multimedia; statistics; group; strategy; nongrouped

Analysis of Nonlinear Collusion Attacks on Fingerprinting Systems for Compressed Multimedia - Varna,A.L.; He,Shan; Swaminathan,A.; M. Wu (Image Processing, 2007. ICIP 2007. IEEE International Conference on, 2007)
In this paper, we analyze the effect of various collusion attacks on fingerprinting systems for compressed multimedia. We evaluate the effectiveness of the collusion attacks in terms of the probability of detection and accuracy in estimating the host signal. Our analysis shows that applying averaging collusion on copies of moderately compressed content gives a highly accurate estimation of the host, and can effectively remove the embedded fingerprints. Averaging is thus the best choice for an attacker as the probability of detection and the distortion introduced are the lowest.
Keywords: attacks; data; coding; multimedia; coding; security; collusion; compressed; compression; image; data; watermarking; fingerprinting; multimedia; data; of; systems; nonlinear

Analyzing information flow - Hicks, Michael W. (Conference on Programming Language Design and Implementation: Proceedings of the 2007 workshop on Programming languages and analysis for security, 2007)

Appendix to CMod: Modular Information Hiding and Type-Safe Linking for C - Srivastava,S.; Hicks, Michael W.; Foster, Jeffrey S. (Technical Reports of the Computer Science Department, 2007)
This brief note is an appendix to the paper "CMod: Modular Information Hiding and Type-Safe Linking for C." It consists of the proof of soundness for the formal language presented in that paper.

Applying Software Reliability Models on Security Incidents - Condon,E.; Michel Cukier; He,Tao (2007)
Computer and network security incidents have increasing financial consequences as demand for network accessibility and connectivity to resources continues to rise. These security incidents can lead to direct financial losses either through data theft of personal and/or proprietary information as well as a reputational damage which may negatively impact stock prices or consumer confidence in a company. This paper examines a large set of security incident data using tools from the software reliability community. We look at applying Non-Homogenous Poisson Process (NHPP) models as a method for describing the reliability growth process. We examine the full set of incidents as well as subsets of the data based on incident types. We look at using the Laplace test to guide selection of the appropriate models. Then, based on the trend results, we apply various NHPP models (i.e., Goel-Okumutu, S-Shaped, Duane, and K-Stage Curve) to illustrate the relevance of using these models to fit the incident data and to predict future incidents.
Keywords: computer security incidents; consumer confidence; data theft; network security incidents; nonhomogenous Poisson process; reliability growth process; reputational damage; security of data; software reliability; stock prices

Automated detection of persistent kernel control-flow attacks - Petroni,Jr.,Nick L.; Hicks, Michael W. (Proceedings of the 14th ACM conference on Computer and communications security, 2007)
This paper presents a new approach to dynamically monitoring operating system kernel integrity, based on a property called state-based control-flow integrity (SBCFI). Violations of SBCFI signal a persistent, unexpected modification of the kernel's control-flow graph. We performed a thorough analysis of 25 Linux rootkits and found that 24 (96%) employ persistent control-flow modifications; an informal study of Windows rootkits yielded similar results. We have implemented SBCFI enforcement as part of the Xen and VMware virtual machine monitors. Our implementation detected all the control-flow modifying rootkits we could install, while imposing unnoticeable overhead for both a typical web server workload and CPU-intensive workloads when operating at 10 second intervals.
Keywords: CFI; integrity; Kernel; rootkit; virtualization

Automatic software interference detection in parallel applications - Tabatabaee, Vahid; Hollingsworth, Jeffrey K (Proceedings of the 2007 ACM/IEEE conference on Supercomputing, 2007)
We present an automated software interference detection methodology for Single Program, Multiple Data (SPMD) parallel applications. Interference comes from the system and unexpected processes. If not detected and corrected such interference may result in performance degradation. Our goal is to provide a reliable metric for software interference that can be used in soft-failure protection and recovery systems. A unique feature of our algorithm is that we measure the relative timing of application events (i.e. time between MPI calls) rather than system level events such as CPU utilization. This approach lets our system automatically accommodate natural variations in an application's utilization of resources. We use performance irregularities and degradation as signs of software interference. However, instead of relying on temporal changes in performance, our system detects spatial performance degradation across multiple processors. We also include a case study that demonstrates our technique's effectiveness, resilience and robustness.

Bio-STEER: A Semantic Web workflow tool for Grid computing in the life sciences - Lee,S.; Wang,T. D; Hashmi,N.; Cummings, Michael P. (Future Generation Comp Syst, 2007)
Life science research is becoming evermore computationally intensive. Hence, from a computational resource perspective, Grid computing provides a logical approach to meeting many of the computational needs of life science research. However, there are several barriers to the widespread use of Grid computing in life sciences. In this paper, we attempt to address one particular barrier: the difficulty of using Grid computing by life scientists. Life science research often involves connecting multiple applications together to form a workflow. This process of constructing a workflow is complex. When combined with the difficulty of using Grid services, composing a meaningful workflow using Grid services can present a challenge to life scientists. Our proposed solution is a Semantic Web-enabled computing environment, called Bio-STEER. In BioSTEER, bioinformatics Grid services are mapped to Semantic Web services, described in OWL-S. We also defined an ontology in OWL to model bioinformatics applications. A graphical user interface helps to construct a scientific workflow by showing a list of services that are semantically sound: that is, the output of one service is semantically compatible with the input of the connecting service. Bio-STEER can help users take full advantaue of Grid services through a user-friendly graphical user interface (GUI), which allows them to easily construct the workflows they need. (c) 2006 Elsevier B.V. All rights reserved.
Keywords: client/server; distributed; environments; integrated; interface; management; semantics; services; systems; user; web-base; workflow

Cell breathing in wireless LANs: Algorithms and evaluation - Hajiaghayi, Mohammad T.; Mirrokni,S. V.; Saberi,A.; Bahl,P.; Jain,K.; Qiu,L. (IEEE Transactions on Mobile Computing, 2007)

Characterization of Ehp, a Secreted Complement Inhibitory Protein from Staphylococcus aureus - Hammel,Michal; Sfyroera,Georgia; Pyrpassopoulos,Serapion; Ricklin,Daniel; Ramyar,Kasra X.; Pop, Mihai; Jin,Zhongmin; Lambris,John D.; Geisbrecht,Brian V. (Journal of Biological Chemistry, 2007)
We report here the discovery and characterization of Ehp, a new secreted Staphylococcus aureus protein that potently inhibits the alternative complement activation pathway. Ehp was identified through a genomic scan as an uncharacterized secreted protein from S. aureus, and immunoblotting of conditioned S. aureus culture medium revealed that the Ehp protein was secreted at the highest levels during log-phase bacterial growth. The mature Ehp polypeptide is composed of 80 residues and is 44% identical to the complement inhibitory domain of S. aureus Efb (extracellular fibrinogen-binding protein). We observed preferential binding by Ehp to native and hydrolyzed C3 relative to fully active C3b and found that Ehp formed a subnanomolar affinity complex with these various forms of C3 by binding to its thioester-containing C3d domain. Site-directed mutagenesis demonstrated that Arg75 and Asn82 are important in forming the Ehp·C3d complex, but loss of these side chains did not completely disrupt Ehp/C3d binding. This suggested the presence of a second C3d-binding site in Ehp, which was mapped to the proximity of Ehp Asn63. Further molecular level details of the Ehp/C3d interaction were revealed by solving the 2.7-Å crystal structure of an Ehp·C3d complex in which the low affinity site had been mutationally inactivated. Ehp potently inhibited C3b deposition onto sensitized surfaces by the alternative complement activation pathway. This inhibition was directly related to Ehp/C3d binding and was more potent than that seen for Efb-C. An altered conformation in Ehp-bound C3 was detected by monoclonal antibody C3-9, which is specific for a neoantigen exposed in activated forms of C3. Our results suggest that increased inhibitory potency of Ehp relative to Efb-C is derived from the second C3-binding site in this new protein.

Chosen-ciphertext security from identity-based encryption - Boneh,D.; Canetti,R.; Halevi,S.; Katz, Jonathan (SIAM Journal on Computing, 2007)
We propose simple and efficient CCA-secure public-key encryption schemes (i.e., schemessecure against adaptive chosen-ciphertext attacks) based on any identity-based encryption (IBE) scheme. Our constructions have ramifications of both theoretical and practical interest. First, our schemes give a new paradigm for achieving CCA-security; this paradigm avoids “proofs of well-formedness” that have been shown to underlie previous constructions. Second, instantiating our construction using known IBE constructions we obtain CCA-secure encryption schemes whose performance is competitive with the most efficient CCA-secure schemes to date. Our techniques extend naturally to give an efficient method for securing IBE schemes (even hierarchical ones) against adaptive chosen-ciphertext attacks. Coupled with previous work, this gives the first efficient constructions of CCA-secure IBE schemes.

Colluding Fingerprinted Video using the Gradient Attack - He,Shan; Kirovski,D.; M. Wu (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)
Digital fingerprinting is an emerging tool to protect multimedia content from unauthorized distribution by embedding a unique fingerprint into each user's copy. Although several fingerprinting schemes have been proposed in related work, disproportional effort has been targeted towards identifying effective collusion attacks on fingerprinting schemes. Recent introduction of the gradient attack has refined the definition of an optimal attack and demonstrated strong effect on direct-sequence, uniformly distributed, and Gaussian spread spectrum fingerprints when applied to synthetic signals. In this paper, we apply the gradient attack on an existing well-engineered video fingerprinting scheme, refine the attack procedure, and demonstrate that the gradient attack is effective on Laplace fingerprints. Finally, we explore an improvement on fingerprint design to thwart the gradient attack. Results suggest that Laplace fingerprint should be avoided. However, we show that a signal mixed of Laplace and Gaussian fingerprints may serve as a design strategy to disable the gradient attack and force pirates into averaging as a form of adversary collusion.
Keywords: attack; multimedia; attacks; digital; content; data; video; distribution; fingerprint; effort; gradient; fingerprinted; fingerprinting; disproportional; fingerprints; colluding; fingerprints; Laplace; Gaussian; identification; multimedia; of; processing; protection; unauthorized; signal; spectrum; spread; systems; security; video; collusion

Collusion-Resistant Dynamic Fingerprinting for Multimedia - He,Shan; M. Wu (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)
This paper considers protecting multimedia content from unauthorized redistribution in subscription based services, where adversaries work together to pirate multiple multimedia programs during a subscription period. Collusion-resistant fingerprinting is an emerging tool for traitor tracing. However, most of the existing fingerprinting works did not consider multiple rounds of interaction between collusion and detection. In this paper, we exploit the temporal dimension and propose a dynamic fingerprinting scheme that adjusts the fingerprint design based on the detection result of previously pirated signal. We also examine colluders' strategies to combat the tracing by dynamic fingerprinting. Both analytical and simulation results show that the proposed dynamic fingerprinting provides better collusion resistance than conventional static fingerprinting
Keywords: based; collusion-resistant; communication; security; data; dimension; traitor; dynamic; fingerprinting; multiple; multimedia; of; piracy; subscription; program; redistribution; multimedia; services; temporal; tracing; unauthorized

Collusion-Resistant Fingerprinting for Compressed Multimedia Signals - Varna,A.L.; He,Shan; Swaminathan,A.; M. Wu; Lu,Haiming; Lu,Zengxiang (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)
Most existing collusion-resistant fingerprinting techniques are for fingerprinting uncompressed signals. In this paper, we first study the performance of the traditional Gaussian based spread spectrum sequences for fingerprinting compressed signals and show that the system can be easily defeated by averaging or taking the median of a few copies. To overcome the collusion problem for compressed multimedia host signals, we propose a technique called anti-collusion dithering to mimic an uncompressed signal. Results show higher probability of catching a colluder using the proposed scheme compared to using Gaussian based fingerprints.
Keywords: based; compression; Gaussian; compression; multimedia; dithering; collusion-resistant; fingerprinting; multimedia; Gaussian; processes; data; sequences; anticollusion; signals; spectrum; spread; systems

Collusion-Resistant Video Fingerprinting for Large User Group - He,Shan; M. Wu (Information Forensics and Security, IEEE Transactions on, 2007)
Digital fingerprinting protects multimedia content from illegal redistribution by uniquely marking copies of the content distributed to users. Most existing multimedia fingerprinting schemes consider a user set on the scale of thousands. However, in such real-world applications as video-on-demand distribution, the number of potential users can be as many as 10-100 million. This large user size demands not only strong collusion resistance but also high efficiency in fingerprint construction, and detection, which makes most existing schemes incapable of being applied to these applications. A recently proposed joint coding and embedding fingerprinting framework provides a promising balance between collusion resistance, efficient construction, and detection, but several issues remain unsolved for applications involving a large group of users. In this paper, we explore how to employ the joint coding and embedding framework and develop practical algorithms to fingerprint video in such challenging settings as to accommodate more than ten million users and resist hundreds of users' collusion. We investigate the proper code structure for large-scale fingerprinting and propose a trimming detection technique that can reduce the decoding computational complexity by more than three orders of magnitude at the cost of less than 0.5% loss in detection probability under moderate to high watermark-to-noise ratios. Both analytic and experimental results show a high potential of joint coding and embedding to meet the needs of real-world large-scale fingerprinting applications.
Keywords: code; coding-embedding; coding; video; communication; video; complexity; decoding; digital; complexity; digital; computational; content; trimming; demand; watermarking; DETECTION; distribution; computational; fingerprinting; fingerprinting; decoding; fingerprinting; joint; framework; large; group; multimedia; identification; multimedia; on; signatures; fingerprint; structure; collusion-resistant; technique; video-on-demand; user; video

Combining provenance and security policies in a web-based document management system - Corcoran,B.J.; Swamy,N.; Hicks, Michael W. (On-line Proceedings of the Workshop on Principles of Provenance (PrOPr), 2007)

COMPUTATIONAL BIOLOGY - Leparc,GG; Mitra,RD; Vardhanabhuti,S.; Wang,J.; Hannenhalli, Sridhar; Smit,S.; Widmann,J.; Knight,R.; Wu,S.; Zhang,Y.; others (Nucleic acids research, 2007)

Concurrently-secure blind signatures without random oracles or setup assumptions - Hazay,C.; Katz, Jonathan; Koo,C. Y; Lindell,Y. (Theory of Cryptography, 2007)
We show a new protocol for blind signatures in which security is preserved even under arbitrarily-many concurrent executions. The protocol can be based on standard cryptographic assumptions and is the first to be proven secure in a concurrent setting (under any assumptions) without random oracles or a trusted setup assumption such as a common reference string. Along the way, we also introduce new definitions of security for blind signature schemes.This research was supported by US-Israel Binational Science Foundation grant #2004240. Work of the first author was also supported by an Eshkol fellowship from the Israel Ministry of Science and Technology. Work of the second author was also supported by NSF CAREER award #0447075.

Conducting In Situ Evaluations for and With Ubiquitous Computing Technologies - Consolvo,Sunny; Harrison,Beverly; Smith,Ian; Chen,Mike Y.; Everitt,Katherine; Jon Froehlich; Landay,James A. (International Journal of Human-Computer Interaction, 2007)
Abstract To evaluate ubiquitous computing technologies, which may be embedded in the environment, embedded in objects, worn, or carried by the user throughout everyday life, it is essential to use methods that accommodate the often unpredictable, real-world environments in which the technologies are used. This article discusses how we have adapted and applied traditional methods from psychology and human-computer interaction, such as Wizard of Oz and Experience Sampling, to be more amenable to the in situ evaluations of ubiquitous computing applications, particularly in the early stages of design. The way that ubiquitous computing technologies can facilitate the in situ collection of self-report data is also discussed. Although the focus is on ubiquitous computing applications and tools for their assessment, it is believed that the in situ evaluation tools that are proposed will be generally useful for field trials of other technology, applications, or formative studies that are concerned with collecting data in situ.Abstract To evaluate ubiquitous computing technologies, which may be embedded in the environment, embedded in objects, worn, or carried by the user throughout everyday life, it is essential to use methods that accommodate the often unpredictable, real-world environments in which the technologies are used. This article discusses how we have adapted and applied traditional methods from psychology and human-computer interaction, such as Wizard of Oz and Experience Sampling, to be more amenable to the in situ evaluations of ubiquitous computing applications, particularly in the early stages of design. The way that ubiquitous computing technologies can facilitate the in situ collection of self-report data is also discussed. Although the focus is on ubiquitous computing applications and tools for their assessment, it is believed that the in situ evaluation tools that are proposed will be generally useful for field trials of other technology, applications, or formative studies that are concerned with collecting data in situ.

Confidentiality-preserving rank-ordered search - Swaminathan,Ashwin; Mao,Yinian; Su,Guan-Ming; Gou,Hongmei; Varna,Avinash L.; He,Shan; M. Wu; Oard, Douglas (Proceedings of the 2007 ACM workshop on Storage security and survivability, 2007)
This paper introduces a new framework for confidentiality preserving rank-ordered search and retrieval over large document collections. The proposed framework not only protects document/query confidentiality against an outside intruder, but also prevents an untrusted data center from learning information about the query and the document collection. We present practical techniques for proper integration of relevance scoring methods and cryptographic techniques, such as order preserving encryption, to protect data collections and indices and provide efficient and accurate search capabilities to securely rank-order documents in response to a query. Experimental results on the W3C collection show that these techniques have comparable performance to conventional search systems designed for non-encrypted data in terms of search accuracy. The proposed methods thus form the first steps to bring together advanced information retrieval and secure search capabilities for a wide range of applications including managing data in government and business operations, enabling scholarly study of sensitive data, and facilitating the document discovery process in litigation.
Keywords: encrypted domain search; Ranked retrieval; secure index

Data Management in the Worldwide Sensor Web - Balazinska,Magdalena; Deshpande, Amol; Franklin,Michael J.; Gibbons,Phillip B.; Gray,Jim; Hansen,Mark; Liebhold,Michael; Nath,Suman; Szalay,Alexander; Tao,Vincent (IEEE Pervasive Computing, 2007)
Advances in hardware and miniaturization technologies have led to a rapid increase in the number of large-scale sensor network deployments around the world, bringing us closer to the vision of a worldwide sensor web. Exploiting the sensor web to its full potential, however, raises several hard data management challenges. Addressing these challenges requires a concerted multidisciplinary effort encompassing many computer science fields. This article outlines some of the key data management challenges of a worldwide sensor web. It also presents recent advances in data management research that aim to address these challenges. Hopefully, the scientific, ubiquitous computing, and sensor network communities will adopt some of these solutions for managing their data. The article also attempts to bring many of the remaining open issues to the attention of the database community. This article is part of a special issue on Building a Sensor-Rich World.
Keywords: data modeling; data streams; data uncertainty; distributed systems; interoperability; sensor networks

Dataflow-based mapping of computer vision algorithms onto FPGAs - Sen,M.; Corretjer,I.; Haim,F.; Saha,S.; Schlessman,J.; Lv,T.; Bhattacharyya, Shuvra S.; Wolf,W. (EURASIP Journal on Embedded Systems, 2007)

Defeating script injection attacks with browser-enforced embedded policies - Jim,Trevor; Swamy,Nikhil; Hicks, Michael W. (Proceedings of the 16th international conference on World Wide Web, 2007)
Web sites that accept and display content such as wiki articles or comments typically filter the content to prevent injected script code from running in browsers that view the site. The diversity of browser rendering algorithms and the desire to allow rich content make filtering quite difficult, however, and attacks such as the Samy and Yamanner worms have exploited filtering weaknesses. This paper proposes a simple alternative mechanism for preventing script injection called Browser-Enforced Embedded Policies (BEEP). The idea is that a web site can embed a policy in its pages that specifies which scripts are allowed to run. The browser, which knows exactly when it will run a script, can enforce this policy perfectly. We have added BEEP support to several browsers, and built tools to simplify adding policies to web applications. We found that supporting BEEP in browsers requires only small and localized modifications, modifying web applications requires minimal effort, and enforcing policies is generally lightweight.
Keywords: cross-site scripting; script injection; web application security

Diagnosing network disruptions with network-wide analysis - Huang,Yiyi; Feamster, Nick; Lakhina,Anukool; Xu,Jim (Jun) (SIGMETRICS Perform. Eval. Rev., 2007)
To maintain high availability in the face of changing network conditions, network operators must quickly detect, identify, and react to events that cause network disruptions. One way to accomplish this goal is to monitor routing dynamics, by analyzing routing update streams collected from routers. Existing monitoring approaches typically treat streams of routing updates from different routers as independent signals, and report only the "loud" events (i.e., events that involve large volume of routing messages). In this paper, we examine BGP routing data from all routers in the Abilene backbone for six months and correlate them with a catalog of all known disruptions to its nodes and links. We find that many important events are not loud enough to be detected from a single stream. Instead, they become detectable only when multiple BGP update streams are simultaneously examined. This is because routing updates exhibit network-wide dependencies. This paper proposes using network-wide analysis of routing information to diagnose (i.e., detect and identify) network disruptions. To detect network disruptions, we apply a multivariate analysis technique on dynamic routing information, (i.e., update traffic from all the Abilene routers) and find that this technique can detect every reported disruption to nodes and links within the network with a low rate of false alarms. To identify the type of disruption, we jointly analyze both the network-wide static configuration and details in the dynamic routing updates; we find that our method can correctly explain the scenario that caused the disruption. Although much work remains to make network-wide analysis of routing data operationally practical, our results illustrate the importance and potential of such an approach.
Keywords: anomaly detection; network management; statistical inference

Document Image Mosaicing with Mobile Phones - Hannuksela,J.; Sangi,P.; Heikkila,J.; Liu,X.; David Doermann (International Conference on Image Analysis and Processing (ICIAP'07), 2007)
This paper presents a novel user interaction oncept for document image scanning with mobile phones. A high resolution mosaic image is constructed in two main stages. Firstly, online camera motion estimation is applied on the phone to assist the user to capture small image batches of the document page. Automatic image stitching process with a help of estimated device motion is carried out to reconstruct the full view of the document. Experiments on document images captured and processed with the mosaicing software clearly show the feasibility of the approach.

Draft Genome of the Filarial Nematode Parasite Brugia Malayi - Ghedin,Elodie; Wang,Shiliang; Spiro,David; Caler,Elisabet; Zhao,Qi; Crabtree,Jonathan; Allen,Jonathan E; Delcher,Arthur L.; Guiliano,David B; Miranda-Saavedra,Diego; Angiuoli,Samuel V; Creasy,Todd; et al. (Science, 2007)
Parasitic nematodes that cause elephantiasis and river blindness threaten hundreds of millions of people in the developing world. We have sequenced the ∼90 megabase (Mb) genome of the human filarial parasite Brugia malayi and predict ∼11,500 protein coding genes in 71 Mb of robustly assembled sequence. Comparative analysis with the free-living, model nematode Caenorhabditis elegans revealed that, despite these genes having maintained little conservation of local synteny during ∼350 million years of evolution, they largely remain in linkage on chromosomal units. More than 100 conserved operons were identified. Analysis of the predicted proteome provides evidence for adaptations of B. malayi to niches in its human and vector hosts and insights into the molecular basis of a mutualistic relationship with its Wolbachia endosymbiont. These findings offer a foundation for rational drug design.

Efficient simulation of critical synchronous dataflow graphs - Hsu,C. J; Ko,M. Y; Bhattacharyya, Shuvra S.; Ramasubbu,S.; Pino,J. L (ACM Transactions on Design Automation of Electronic Systems (TODAES), 2007)

eHealth Research from the User’s Perspective - Hesse,Bradford W.; Shneiderman, Ben (American Journal of Preventive Medicine, 2007)
The application of information technology (IT) to issues of healthcare delivery has had a long and tortuous history in the United States. Within the field of eHealth, vanguard applications of advanced computing techniques, such as applications in artificial intelligence or expert systems, have languished in spite of a track record of scholarly publication and decisional accuracy. The problem is one of purpose, of asking the right questions for the science to solve. Historically, many computer science pioneers have been tempted to ask “what can the computer do?” New advances in eHealth are prompting developers to ask “what can people do?” How can eHealth take part in national goals for healthcare reform to empower relationships between healthcare professionals and patients, healthcare teams and families, and hospitals and communities to improve health equitably throughout the population? To do this, eHealth researchers must combine best evidence from the user sciences (human factors engineering, human–computer interaction, psychology, and usability) with best evidence in medicine to create transformational improvements in the quality of care that medicine offers. These improvements should follow recommendations from the Institute of Medicine to create a healthcare system that is (1) safe, (2) effective (evidence based), (3) patient centered, and (4) timely. Relying on the eHealth researcher’s intuitive grasp of systems issues, improvements should be made with considerations of users and beneficiaries at the individual (patient–physician), group (family–staff), community, and broad environmental levels.

An Environment of Conducting Families of Software Engineering Experiments - Hochstein, Lorin; Nakamura,Taiga; Shull, Forrest; Zazworka, Nico; Voelp,Martin; Zelkowitz, Marvin V; Basili, Victor R. (University of Maryland, College Park, 2007)
The classroom is a valuable resource for conducting software engineering experiments. However, coordinating a family of experiments in classroom environments presents a number of challenges to researchers. This paper describes an environment that simplifies the process of collecting, managing and sanitizing data from classroom experiments, while minimizing disruption to natural subject behavior. We have successfully used this environment to study the impact of parallel programming languages on programmer productivity at multiple universities across the United States.
Keywords: collecting data; managing data; parallel programming languages; sanitizing data; software engineering experiments; universities

Eukaryotic Transcriptional Regulation: Signals, Interactions, and Modules - Hannenhalli, Sridhar (Computational genomics: current methods, 2007)

Evaluating a cross-cultural children’s online book community: Lessons learned for sociability, usability, and cultural exchange - Komlodi,Anita; Hou,Weimin; Preece,Jenny; Druin, Allison; Golub,Evan; Alburo,Jade; Liao,Sabrina; Elkiss,Aaron; Resnik, Philip (Interacting with Computers, 2007)
The use of computers for human-to-human communication among adults has been studied for many years, but using computer technology to enable children from all over the world to talk to each other has rarely been discussed by researchers. The goal of our research is to fill this gap and explore the design and evaluation of children’s cross-language online communities via a case study of the International Children’s Digital Library Communities (ICDLCommunities). This project supports the development of communities for children (ages 7–11) that form around the International Digital Children’s Library (ICDL) book collection. In this community the children can learn about each others’ cultures and make friends even if they do not speak the same language. They can also read and create stories and ask and answer questions about these. From this evaluation study we learned that: (i) children are very interested in their counterparts in other countries and a remarkable amount of communication takes place even when they do not share a common language; (ii) representing their identity online in many different forms is particularly important to children when communicating in an online community; (iii) children enjoy drawing but representing stories in a sequence of diagrams is challenging and needs support; and (iv) asking and answering questions without language is possible using graphical templates. In this paper we present our findings and make recommendations for designing children’s cross-cultural online communities.
Keywords: children; Cross-cultural; Evaluation and design; International Children’s Digital Library; Online communities

Evolution of genes and genomes on the Drosophila phylogeny - Clark,Andrew G.; Eisen,Michael B.; Smith,Douglas R.; Bergman,Casey M.; Oliver,Brian; Markow,Therese A.; Kaufman,Thomas C.; Kellis,Manolis; Gelbart,William; Iyer,Venky N.; Pollard,Daniel A.; Sackton,Timothy B.; et al. (Nature, 2007)
Comparative analysis of multiple genomes in a phylogenetic framework dramatically improves the precision and sensitivity of evolutionary inference, producing more robust results than single-genome analyses can provide. The genomes of 12 Drosophila species, ten of which are presented here for the first time (sechellia, simulans, yakuba, erecta, ananassae, persimilis, willistoni, mojavensis, virilis and grimshawi), illustrate how rates and patterns of sequence divergence across taxa can illuminate evolutionary processes on a genomic scale. These genome sequences augment the formidable genetic tools that have made Drosophila melanogaster a pre-eminent model for animal genetics, and will further catalyse fundamental research on mechanisms of development, cell biology, genetics, disease, neurobiology, behaviour, physiology and evolution. Despite remarkable similarities among these Drosophila species, we identified many putatively non-neutral changes in protein-coding genes, non-coding RNA genes, and cis-regulatory regions. These may prove to underlie differences in the ecology and behaviour of these diverse species.

A forward-secure public-key encryption scheme - Canetti,R.; Halevi,S.; Katz, Jonathan (Journal of Cryptology, 2007)
Cryptographic computations are often carried out on insecure devices for which the threat of key exposure represents a serious concern. Forward security allows one to mitigate the damage caused by exposure of secret keys. In a forward-secure scheme, secret keys are updated at regular periods of time; exposure of the 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. We present the first constructions of (non-interactive) forward-secure public-key encryption schemes. Our main construction achieves security against chosen-plaintext attacks in the standard model, and all parameters of the scheme are poly-logarithmic in the total number of time periods. Some variants and extensions of this scheme are also given. We also introduce the notion of binary tree encryption and construct a binary tree encryption scheme in the standard model. Our construction implies the first hierarchical identity-based encryption scheme in the standard model. (The notion of security we achieve, however, is slightly weaker than that achieved by some previous constructions in the random oracle model.)

GATA and Nkx factors synergistically regulate tissue-specific gene expression and development in vivo - Zhang,Yuzhen; Rath,Nibedita; Hannenhalli, Sridhar; Wang,Zhishan; Cappola,Thomas; Kimura,Shioko; Atochina-Vasserman,Elena; Lu,Min Min; Beers,Michael F.; Morrisey,Edward E. (Development, 2007)
In vitro studies have suggested that members of the GATA and Nkx transcription factor families physically interact, and synergistically activate pulmonary epithelial- and cardiac-gene promoters. However, the relevance of this synergy has not been demonstrated in vivo. We show that Gata6-Titf1 (Gata6-Nkx2.1) double heterozygous (G6-Nkx DH) embryos and mice have severe defects in pulmonary epithelial differentiation and distal airway development, as well as reduced phospholipid production. The defects in G6-Nkx DH embryos and mice are similar to those observed in human neonates with respiratory distress syndromes, including bronchopulmonary dysplasia, and differential gene expression analysis reveals essential developmental pathways requiring synergistic regulation by both Gata6 and Titf1 (Nkx2.1). These studies indicate that Gata6 and Nkx2.1 act in a synergistic manner to direct pulmonary epithelial differentiation and development in vivo, providing direct evidence that interactions between these two transcription factor families are crucial for the development of the tissues in which they are co-expressed.

Genome-wide expression profiling and bioinformatics analysis of diurnally regulated genes in the mouse prefrontal cortex - Yang,Shuzhang; Wang,Kai; Valladares,Otto; Hannenhalli, Sridhar; Bucan,Maja (Genome Biology, 2007)
The prefrontal cortex is important in regulating sleep and mood. Diurnally regulated genes in the prefrontal cortex may be controlled by the circadian system, by sleep:wake states, or by cellular metabolism or environmental responses. Bioinformatics analysis of these genes will provide insights into a wide-range of pathways that are involved in the pathophysiology of sleep disorders and psychiatric disorders with sleep disturbances.

Grow and Know: Understanding Record-keeping Needs for Tracking the Development of Young Children - Kientz, Julie A.; Arriaga, Rosa I.; Marshini Chetty; Hayes, Gillian R.; Richardson, Jahmeilah; Patel, Shwetak N.; Abowd, Gregory D. (SIGCHI '07, 2007)
From birth through age five, children undergo rapid development and learn skills that will influence them their entire lives. Regular visits to the pediatrician and detailed record-keeping can ensure that children are progressing and can identify early warning signs of developmental delay or disability. However, new parents are often overwhelmed with new responsibilities, and we believe there is an opportunity for computing technology to assist in this process. In this paper, we present a qualitative study aimed at uncovering some specific needs for record-keeping and analysis for new parents and their network of caregivers. Through interviews and focus groups, we have confirmed assumptions about the rationales parents have and the functions required for using technology for record-keeping. We also identify new themes, potential prototypes, and design guidelines for this domain.
Keywords: children; design requirements; developmental delay; healthcare; qualitative study

Hood College, Master of Business Administration, 2005 Hood College, Master of Science (Computer Science), 2001 Hood College, Bachelor of Science (Computer Science), 1998 Frederick Community College, Associate in Arts (Business Administration), 1993 - Anderson,M. L; Schmill,M.; Oates,T.; Perlis, Don; Josyula,D.; Wright,D.; Human,S. W.T.D.N; Metacognition,L.; Fults,S.; Josyula,D. P (Proceedings of the Workshop on Metareasoning in Agent-Based Systems, 2007)

Human appearance modeling for matching across video sequences - Yu,Y.; Harwood,D.; Yoon,K.; Davis, Larry S. (Machine Vision and Applications, 2007)
We present an appearance model for establishing correspondence between tracks of people which may be taken at different places, at different times or across different cameras. The appearance model is constructed by kernel density estimation. To incorporate structural information and to achieve invariance to motion and pose, besides color features, an additional feature of path-length is used. To achieve illumination invariance, two types of illumination insensitive color features are discussed: brightness color feature and RGB rank feature. The similarity between a test image and an appearance model is measured by the information gain or Kullback–Leibler distance. To thoroughly represent the information contained in a video sequence with as little data as possible, a key frame selection and matching scheme is proposed. Experimental results demonstrate the important role of the path-length feature in the appearance model and the effectiveness of the proposed appearance model and matching method.

On implementing graph cuts on cuda - Hussein,M.; Varshney, Amitabh; Davis, Larry S. (First Workshop on General Purpose Processing on Graphics Processing Units, 2007)
The Compute Unified Device Architecture (CUDA)has enabled graphics processors to be explicitly programmed as general-purpose shared-memory multi-core processors with a high level of parallelism. In this paper, we present our preliminary results of implementing the Graph Cuts algorithm on CUDA. Our primary focus is on implementing Graph Cuts on grid graphs, which are extensively used in imaging applications. We first explain our implementation of breadth first search (BFS) graph traversal on CUDA, which is extensively used in our Graph Cuts implementation. We then present a basic implementation of Graph Cuts that succeeds to achieve absolute and relative speedups when used for foreground-background segmentation on synthesized images. Finally, we introduce two optimizations that utilize the special structure of grid graphs. The first one is lockstep BFS, which is used to reduce the overhead of BFS traversals. The second is cache emulation, which is a general technique to regularize memory access patterns and hence enhance memory access throughput. We experimentally show how each of the two optimizations can enhance the performance of the basic implementation on the image segmentation application.

Improving software quality with static analysis - Foster, Jeffrey S.; Hicks, Michael W.; Pugh, William (Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, 2007)
At the University of Maryland, we have been working to improve the reliability and security of software by developing new, effective static analysis tools. These tools scan software for bug patterns or show that the software is free from a particular class of defects. There are two themes common to our different projects: 1. Our ultimate focus is on utility: can a programmer actually improve the quality of his or her software using an analysis tool? The important first step toward answering this question is to engineer tools so that they can analyze existing, nontrivial programs, and to carefully report the results of such analyses experimentally. The desire to better understand a more human-centered notion of utility underlies much of our future work. 2. We release all of our tools open source. This allows other researchers to verify our results, and to reuse some or all of our implementations, which often required significant effort to engineer. We believe that releasing source code is important for accelerating the pace of research results software quality, and just as importantly allows feedback from the wider community. In this research group presentation, we summarize some recent work and sketch future directions.
Keywords: bug patterns; bugs; C; Data races; FFIs; java; modularity; network protocols; Software quality

Increasing the breadth: applying sensors, inference and self-report in field studies with the MyExperience tool - Jon Froehlich; Chen,Mike Y.; Consolvo,Sunny; Harrison,Beverly; Landay,James A. (Proceedings of the 1st international workshop on System evaluation for mobile platforms, 2007)
Keywords: In situ evaluation; context-aware systems; experience sampling method (ESM); field studies; Mobile computing; toolkits

Joint Uplink and Downlink Optimization for Real-Time Multiuser Video Streaming Over WLANs - Su,Guan-Ming; Han,Zhu; M. Wu; Liu,K. J.R (Selected Topics in Signal Processing, IEEE Journal of, 2007)
In this paper, a network-aware and source-aware video streaming system is proposed to support interactive multiuser communications within single-cell and multicell IEEE 802.11 networks. Unlike the traditional streaming video services, the strict delay constraints of an interactive video streaming system pose more challenges. These challenges include the heterogeneity of uplink and downlink channel conditions experienced by different users, the multiuser resource allocation of limited radio resources, the incorporation of the cross-layer design, and the diversity of content complexities exhibited by different video sequences. With the awareness of video content and network resources, the proposed system integrates cross-layer error protection mechanism and performs dynamic resource allocation across multiple users. We formulate the proposed system as to minimize the maximal end-to-end expected distortion received by all users, subject to maximal transmission power and delay constraints. To reduce the high dimensionality of the search space, fast multiuser algorithms are proposed to find the near-optimal solutions. Compared to the strategy without dynamically and jointly allocating bandwidth resource for uplinks and downlinks, the proposed framework outperforms by 2.18 7.95 dB in terms of the average received PSNR of all users and by 3.82 11.50 dB in terms of the lowest received PSNR among all users. Furthermore, the proposed scheme can provide more uniform video quality for all users and lower quality fluctuation for each received video sequence.
Keywords: 802.11; allocation; image; allocation; real-time; communications; maximal; distortion; multiuser; end-to-end; error; expected; IEEE; LAN; mechanism; downlink; multiuser; networks; WLAN; cross-layer; optimization; interactive; optimization; video; Protection; quality; video; resource; sequences; video; streaming; streaming; uplink; streaming; wireless; system; bandwidth; video

Layout-Accurate Design and Implementation of a High-Throughput Interconnection Network for Single-Chip Parallel Processing - Balkan,A.O.; Horak,M.N.; Gang Qu; Vishkin, Uzi (High-Performance Interconnects, 2007. HOTI 2007. 15th Annual IEEE Symposium on, 2007)
A mesh of trees (MoT) on-chip interconnection network has been proposed recently to provide high throughput between memory units and processors for single-chip parallel processing (Balkan et al., 2006). In this paper, we report our findings in bringing this concept to silicon. Specifically, we conduct cycle-accurate Verilog simulations to verify the analytical results claimed in (Balkan et al., 2006). We synthesize and obtain the layout of the MoT interconnection networks of various sizes. To further improve throughput, we investigate different arbitration primitives to handle load and store, the two most common memory operations. We also study the use of pipeline registers in large networks when there are long wires. Simulation based on full network layout demonstrates that significant throughput improvement can be achieved over the original proposed MoT interconnection network. The importance of this work lies in its validation of performance features of the MoT interconnection network, as they were previously shown to be competitive with traditional network solutions. The MoT network is currently used in an eXplicit multi-threading (XMT) on-chip parallel processor, which is engineered to support parallel programming. In that context, a 32-terminal MoT network could support up to 512 on-chip XMT processors. Our 8-terminal network that could serve 8 processor clusters (or 128 total processors), was also accepted recently for fabrication.
Keywords: description; design; mesh; interconnection; languages; multi-threading; multiprocessor; MoT; multi-threading; layout-accurate; network; on-chip; network; Verilog; networks; parallel; of; on-chip; Parallel; processing; processing; hardware; processor; parallel; processors; on-chip; programming; pipeline; registers; single-chip; simulations; eXplicit; TREES; XMT

Least squares preconditioners for stabilized discretizations of the Navier-Stokes equations - Elman, Howard; Howle, V. E; Shadid, J.; Silvester, D.; Tuminaro, R. (SIAM J. Sci. Comput, 2007)

Mapping the Interactions between Lys48 and Lys63-Linked Di-ubiquitins and a Ubiquitin-Interacting Motif of S5a - Haririnia,Aydin; D’Onofrio,Mariapina; Fushman, David (Journal of Molecular Biology, 2007)
Numerous cellular processes are regulated by (poly)ubiquitin-mediated signaling events, which involve a covalent modification of the substrate protein by a single ubiquitin or a chain of ubiquitin molecules linked via a specific lysine. Remarkably, the outcome of polyubiquitination is linkage-dependent. For example, Lys48-linked chains are the principal signal for proteasomal degradation, while Lys63-linked chains act as nonproteolytic signals. Despite significant progress in characterization of various cellular pathways involving ubiquitin, understanding of the structural details of polyubiquitin chain recognition by downstream cellular effectors is missing. Here we use NMR to study the interaction of a ubiquitin-interacting motif (UIM) of the proteasomal subunit S5a with di-ubiquitin, the simplest model for polyubiquitin chain, to gain insights into the mechanism of polyubiquitin recognition by the proteasome. We have mapped the binding interface and characterized the stoichiometry and the process of UIM binding to Lys48- and Lys63-linked di-ubiquitin chains. Our data provide the first direct evidence that UIM binding involves a conformational transition in Lys48-linked di-ubiquitin, which opens the hydrophobic interdomain interface. This allows UIM to enter the interface and bind directly to the same ubiquitin hydrophobic-patch surface as utilized in UIM:monoubiquitin complexes. The results indicate that up to two UIM molecules can bind di-ubiquitin, and the binding interface between UIM and ubiquitin units in di-ubiquitin is essentially the same for both Lys48- and Lys63-linked chains. Our data suggest possible structural models for the binding of UIM and of full-length S5a to di-ubiquitin.
Keywords: chemical shift perturbation mapping; polyubiquitin; S5a; ubiquitin; ubiquitin-interacting motif

An M-channel directional filter bank compatible with the contourlet and shearlet frequency tiling - Easley,G. R; Patel, Vishal M.; Healy Jr,D.M. (Proceedings of SPIE, 2007)

MetaProm: a neural network based meta-predictor for alternative human promoter prediction - Wang,Junwen; Ungar,Lyle; Tseng,Hung; Hannenhalli, Sridhar (BMC Genomics, 2007)
BACKGROUND:De novo eukaryotic promoter prediction is important for discovering novel genes and understanding gene regulation. In spite of the great advances made in the past decade, recent studies revealed that the overall performances of the current promoter prediction programs (PPPs) are still poor, and predictions made by individual PPPs do not overlap each other. Furthermore, most PPPs are trained and tested on the most-upstream promoters; their performances on alternative promoters have not been assessed.RESULTS:In this paper, we evaluate the performances of current major promoter prediction programs (i.e., PSPA, FirstEF, McPromoter, DragonGSF, DragonPF, and FProm) using 42,536 distinct human gene promoters on a genome-wide scale, and with emphasis on alternative promoters. We describe an artificial neural network (ANN) based meta-predictor program that integrates predictions from the current PPPs and the predicted promoters' relation to CpG islands. Our specific analysis of recently discovered alternative promoters reveals that although only 41% of the 3' most promoters overlap a CpG island, 74% of 5' most promoters overlap a CpG island.CONCLUSION:Our assessment of six PPPs on 1.06 x 109 bps of human genome sequence reveals the specific strengths and weaknesses of individual PPPs. Our meta-predictor outperforms any individual PPP in sensitivity and specificity. Furthermore, we discovered that the 5' alternative promoters are more likely to be associated with a CpG island.

Mutatis Mutandis: Safe and predictable dynamic software updating - Stoyle,Gareth; Hicks, Michael W.; Bierman,Gavin; Sewell,Peter; Neamtiu,Iulian (ACM Trans. Program. Lang. Syst., 2007)
This article presents Proteus, a core calculus that models dynamic software updating, a service for fixing bugs and adding features to a running program. Proteus permits a program's type structure to change dynamically but guarantees the updated program remains type-correct by ensuring a property we call con-freeness. We show how con-freeness can be enforced dynamically, and how it can be approximated via a novel static analysis. This analysis can be used to assess the implications of a program's structure on future updates in order to make update success more predictable. We have implemented Proteus for C, and briefly discuss our implementation which we have tested on several well-known programs.
Keywords: capability; dynamic software updating; proteus; Type inference; updateability analysis

MyExperience: a system for in situ tracing and capturing of user feedback on mobile phones - Jon Froehlich; Chen,Mike Y.; Consolvo,Sunny; Harrison,Beverly; Landay,James A. (Proceedings of the 5th international conference on Mobile systems, applications and services, 2007)
This paper presents MyExperience, a system for capturing both objective and subjective in situ data on mobile computing activities. MyExperience combines the following two techniques: 1) passive logging of device usage, user context, and environmental sensor readings, and 2) active context-triggered user experience sampling to collect in situ, subjective user feedback. MyExperience currently runs on mobile phones and supports logging of more than 140 event types, including: 1) device usage such as communication, application usage, and media capture, 2) user context such as calendar appointments, and 3) environmental sensing such as Bluetooth and GPS. In addition, user experience sampling can be targeted to moments of interest by triggering off sensor readings. We present several case studies of field deployments on people's personal phones to demonstrate how MyExperience can be used effectively to understand how people use and experience mobile technology.
Keywords: context-aware systems; experience sampling method (ESM); field studies; in situ evaluation; Mobile computing; SmartPhones; toolkit; usage logging; user surveys; user-centered design

New records of phytoplankton for Bangladesh. 3. Volvocales - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2007)
This study presents 21 species of Chlamydomonas, four species of Carteria, two species of each of Nephroselmis, Pyramidomonas and Scherffelia, and Collodictyon triciliatum, Polytoma minus, Tetrachloridium ? allorgei and Tetraselmis cordiformis. These species have been reported from some ponds of Mathbaria of Pirojpur and Bakerganj of Barisal districts in Bangladesh.

New records of phytoplankton for Bangladesh. 4. Chlorococcales - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasim,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2007)
This study presents three species from each of Schroederia, Monoraphidium and Ankistrodesmus, two species and one variety of Dictyosphaerium, two varieties of Pediastrum, and Tetraedron arthrodesmiforme var. contorta, Chlorotetraedron polymorphum, Myrmecia aquatica, Oocystis tainoensis, Nephrocytium spirale, Kirchneriella irregularis, Coelastrum indicum and Scenedesmus similagineus. These taxa have been reported from some ponds of Mathbaria of Pirojpur and Bakerganj of Barisal Districts in Bangladesh.

Oblivious routing on node-capacitated and directed graphs - Hajiaghayi, Mohammad T.; Kleinberg,R. D; R\äcke,H.; Leighton,T. (ACM Transactions on Algorithms (TALG), 2007)

Performance Measurement of Novice HPC Programmers Code - Alameh, Rola; Zazworka, Nico; Hollingsworth, Jeffrey K (Proceedings of the 3rd International Workshop on Software Engineering for High Performance Computing Applications, 2007)
Performance is one of the key factors of improving productivity in High Performance Computing (HPC). In this paper we discuss current studies in the field of performance measurement of codes captured in classroom experiments for the High Productivity Computing Project (HPCS). We give two examples of measurements introducing two new hypotheses: spending more effort doesn't always result in improvement of performance for novices; the use of higher level MPI functions promises better performance for novices. We also present a tool - the Automated Performance Measurement System (APMS). APMS helps to partially automate the measurement of the performance of a set of parallel programs with several inputs. The design and implementation of the tool is flexible enough to allow other researchers to conduct similar studies.
Keywords: measurement; performance; performance measures; product metrics; program analysis

Portcullis: protecting connection setup from denial-of-capability attacks - Parno, Bryan; Wendlandt, Dan; Elaine Shi; Perrig, Adrian; Maggs, Bruce; Hu, Yih-Chun (ACM, 2007)
Systems using capabilities to provide preferential service to selected flows have been proposed as a defense against large-scale network denial-of-service attacks. While these systems offer strong protection for established network flows, the Denial-of-Capability (DoC) attack, which prevents new capability-setup packets from reaching the destination, limits the value of these systems. Portcullis mitigates DoC attacks by allocating scarce link bandwidth for connection establishment packets based on per-computation fairness. We prove that a legitimate sender can establish a capability with high probability regardless of an attacker's resources or strategy and that no system can improve on our guarantee. We simulate full and partial deployments of Portcullis on an Internet-scale topology to confirm our theoretical results and demonstrate the substantial benefits of using per-computation fairness.
Keywords: network capability; per-computation fairness

Position and distance specificity are important determinants of cis-regulatory motifs in addition to evolutionary conservation - Vardhanabhuti,Saran; Wang,Junwen; Hannenhalli, Sridhar (Nucleic Acids Research, 2007)
Computational discovery of cis-regulatory elements remains challenging. To cope with the high false positives, evolutionary conservation is routinely used. However, conservation is only one of the attributes of cis-regulatory elements and is neither necessary nor sufficient. Here, we assess two additional attributes—positional and inter-motif distance specificity—that are critical for interactions between transcription factors. We first show that for a greater than expected fraction of known motifs, the genes that contain the motifs in their promoters in a position-specific or distance-specific manner are related, both in function and/or in expression pattern. We then use the position and distance specificity to discover novel motifs. Our work highlights the importance of distance and position specificity, in addition to the evolutionary conservation, in discovering cis-regulatory motifs.

Power optimization in fault-tolerant topology control algorithms for wireless multi-hop networks - Hajiaghayi, Mohammad T.; Immorlica,N.; Mirrokni,V. S (IEEE/ACM Transactions on Networking (TON), 2007)

Probabilistic design of multimedia embedded systems - Hua,S.; Qu,G.; Bhattacharyya, Shuvra S. (ACM Transactions on Embedded Computing Systems (TECS), 2007)

Probabilistic Fusion Tracking Using Mixture Kernel-Based Bayesian Filtering - Han,Bohyung; Joo,Seong-Wook; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Even though sensor fusion techniques based on particle filters have been applied to object tracking, their implementations have been limited to combining measurements from multiple sensors by the simple product of individual likelihoods. Therefore, the number of observations is increased as many times as the number of sensors, and the combined observation may become unreliable through blind integration of sensor observations - especially if some sensors are too noisy and non-discriminative. We describe a methodology to model interactions between multiple sensors and to estimate the current state by using a mixture of Bayesian filters - one filter for each sensor, where each filter makes a different level of contribution to estimate the combined posterior in a reliable manner. In this framework, an adaptive particle arrangement system is constructed in which each particle is allocated to only one of the sensors for observation and a different number of samples is assigned to each sensor using prior distribution and partial observations. We apply this technique to visual tracking in logical and physical sensor fusion frameworks, and demonstrate its effectiveness through tracking results.
Keywords: (numerical; adaptive; arrangement; Bayesian; Filtering; filtering; multiple; filters; probabilistic; fusion; fusion; tracking; integration; mixture; kernel-based; methods); sensor; methods; array; particle; processing; particle; sensors; object; signal; system; blind; techniques; visual; tracking; Bayes; tracking; particle; tracking; sensor

Probabilistic interval XML - Hung,Edward; Getoor, Lise; V.S. Subrahmanian (ACM Transactions on Computational Logic (TOCL), 2007)
Interest in XML databases has been expanding rapidly over the last few years. In this paper, we study the problem of incorporating probabilistic information into XML databases. We propose the Probabilistic Interval XML (PIXML for short) data model in this paper. Using this data model, users can express probabilistic information within XML markups. In addition, we provide two alternative formal model-theoretic semantics for PIXML data. The first semantics is a “global” semantics which is relatively intuitive, but is not directly amenable to computation. The second semantics is a “local” semantics which supports efficient computation. We prove several correspondence results between the two semantics. To our knowledge, this is the first formal model theoretic semantics for probabilistic interval XML. We then provide an operational semantics that may be used to compute answers to queries and that is correct for a large class of probabilistic instances.
Keywords: Semistructured Databases; XML

Randomized Algorithms and Probabilistic Analysis in Wireless Networking - Srinivasan, Aravind (Stochastic Algorithms: Foundations and ApplicationsStochastic Algorithms: Foundations and Applications, 2007)
Devices connected wirelessly, in various forms including computers, hand-held devices, ad hoc networks, and embedded systems, are expected to become ubiquitous all around us. Wireless networks pose interesting new challenges, some of which do not arise in standard (wired) networks. This survey discusses some key probabilistic notions – both randomized algorithms and probabilistic analysis – in wireless networking.

Recognizing Faces Across Age Progression - Ramanathan,Narayanan; Chellapa, Rama (Face Biometrics for Personal IdentificationFace Biometrics for Personal Identification, 2007)

Recovery in culture of viable but nonculturable Vibrio parahaemolyticus: regrowth or resuscitation? - Coutard,Fran|[ccedil]|ois; Crassous,Philippe; Droguet,Micka|[euml]|l; Gobin,Eric; Rita R Colwell; Pommepuy,Monique; Hervio-Heath,Dominique (The ISME Journal, 2007)
The objective of this study was to explore the recovery of culturability of viable but nonculturable (VBNC) Vibrio parahaemolyticus after temperature upshift and to determine whether regrowth or resuscitation occurred. A clinical strain of V. parahaemolyticus Vp5 was rendered VBNC by exposure to artificial seawater (ASW) at 4°C. Aliquots of the ASW suspension of cells (0.1, 1 and 10 ml) were subjected to increased temperatures of 20°C and 37°C. Culturability of the cells in the aliquots was monitored for colony formation on a rich medium and changes in morphology were measured by scanning (SEM) and transmission (TEM) electron microscopy. Samples of VBNC cells were fixed and examined by SEM, revealing a heterogeneous population comprising small cells and larger, flattened cells. Forty-eight hours after temperature upshift to 20°C or 37°C, both elongation and division by binary fission of the cells were observed, employing SEM and TEM, but only in the 10-ml aliquots. The results suggest that a portion of VBNC cells is able to undergo cell division. It is concluded that a portion of VBNC cells of V. parahaemolyticus subjected to cold temperatures remain viable. After temperature upshift, regrowth of those cells, rather than resuscitation of all bacteria of the initial inoculum, appears to be responsible for recovery of culturability of VBNC cells of V. parahaemolyticus. Nutrient in filtrates of VBNC cells is hypothesized to allow growth of the temperature-responsive cells, with cell division occurring via binary fission, but also including an atypical, asymmetric cell division.
Keywords: ecophysiology; ecosystems; environmental biotechnology; geomicrobiology; ISME J; microbe interactions; microbial communities; microbial ecology; microbial engineering; microbial epidemiology; microbial genomics; microorganisms

Scheduling to minimize gaps and power consumption - Demaine,E. D; Ghodsi,M.; Hajiaghayi, Mohammad T.; Sayedi-Roshkhar,A. S; Zadimoghaddam,M. (Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, 2007)

Schistosoma mansoni genome: Closing in on a final gene set - Haas,Brian J.; Berriman,Matthew; Hirai,Hirohisa; Cerqueira,Gustavo G.; LoVerde,Philip T.; El‐Sayed, Najib M. (Experimental Parasitology, 2007)
The Schistosoma mansoni genome sequencing consortium has recently released the latest versions of the genome assembly as well as an automated preliminary gene structure annotation. The combined datasets constitute a vast resource for researchers to exploit in a variety of post-genomic studies with an emphasis of transcriptomic and proteomic tools. Here we present an innovative method used for combining diverse sources of evidence including ab initio gene predictions, protein and transcript sequence homologies, and cross-genome sequence homologies between S. mansoni and Schistosoma japonicum to define a comprehensive list of protein-coding genes.
Keywords: Annotation; Gene finding; Genome; Schistosoma mansoni

A semantic web environment for digital shapes understanding - De Floriani, Leila; Hui,Annie; Papaleo,Laura; Huang,May; Hendler,James (Proceedings of the semantic and digital media technologies 2nd international conference on Semantic Multimedia, 2007)
In the last few years, the volume of multimedia content available on the Web significantly increased. This led to the need for techniques to handle such data. In this context, we see a growing interest in considering the Semantic Web in action and in the definition of tools capable of analyzing and organizing digital shape models. In this paper, we present a Semantic Web environment, be-SMART, for inspecting 3D shapes and for structuring and annotating such shapes according to ontology-driven metadata. Specifically, we describe in details the first module of be-SMART, the Geometry and Topology Analyzer, and the algorithms we have developed for extracting geometrical and topological information from 3D shapes. We also describe the second module, the Topological Decomposer, which produces a graph-based representation of the decomposition of the shape into manifold components. This is successively modified by the third and the fourth modules, which perform the automatic and manual segmentation of the manifold parts.
Keywords: digital shapes; semantic annotation; semantic web; shape analysis; shape understanding

Software configuration management using ontologies - Shahri,H. H; Hendler,J. A; Porter, Adam (3rd International Workshop on Semantic Web Enabled Software Engineering (SWESE 2007), Innsubruk, Austria, 2007)

Spliceosomal small nuclear RNA genes in 11 insect genomes - Mount, Stephen M.; Gotea,Valer; Lin,Chiao-Feng; Hernandez,Kristina; Makałowski,Wojciech (RNARNA, 2007)
A monthly journal publishing high-quality, peer-reviewed research on all topics related to RNA and its metabolism in all organisms
Keywords: honeybee; Insecta; secondary structure; snRNA; spliceosomal snRNA; U12 introns

Supporting elementary-age children's searching and browsing: Design and evaluation using the international children's digital library - Hutchinson,H.B.; Druin, Allison; Bederson, Benjamin B. (Journal of the American Society for Information Science and Technology, 2007)

Swarm Intelligence Systems Using Guided Self-Organization for Collective Problem Solving - RodrIGuez,A.; Grushin,A.; Reggia, James A.; HAUPTMAN,AMI; SIPPER,M.; PAN,Z.; Reggia, James A.; GAO,D.; DARABOS,C.; GIACOBINI,M.; others (Advances in Complex Systems, 2007)

Task-based evaluation of text summarization using Relevance Prediction - Hobson,Stacy President; Dorr, Bonnie J; Monz,Christof; Schwartz,Richard (Information Processing & Management, 2007)
This article introduces a new task-based evaluation measure called Relevance Prediction that is a more intuitive measure of an individual’s performance on a real-world task than interannotator agreement. Relevance Prediction parallels what a user does in the real world task of browsing a set of documents using standard search tools, i.e., the user judges relevance based on a short summary and then that same user—not an independent user—decides whether to open (and judge) the corresponding document. This measure is shown to be a more reliable measure of task performance than LDC Agreement, a current gold-standard based measure used in the summarization evaluation community. Our goal is to provide a stable framework within which developers of new automatic measures may make stronger statistical statements about the effectiveness of their measures in predicting summary usefulness. We demonstrate—as a proof-of-concept methodology for automatic metric developers—that a current automatic evaluation measure has a better correlation with Relevance Prediction than with LDC Agreement and that the significance level for detected differences is higher for the former than for the latter.
Keywords: Relevance prediction; Summarization evaluation; Summary usefulness

Techniques for Classifying Executions of Deployed Software to Support Software Engineering Tasks - Haran,Murali; Karr,Alan; Last,Michael; Orso,Alessandro; Porter, Adam; Sanil,Ashish; Fouch?,Sandro (IEEE Transactions on Software Engineering, 2007)
There is an increasing interest in techniques that support analysis and measurement of fielded software systems. These techniques typically deploy numerous instrumented instances of a software system, collect execution data when the instances run in the field, and analyze the remotely collected data to better understand the system's in-the-field behavior. One common need for these techniques is the ability to distinguish execution outcomes (e.g., to collect only data corresponding to some behavior or to determine how often and under which condition a specific behavior occurs). Most current approaches, however, do not perform any kind of classification of remote executions and either focus on easily observable behaviors (e.g., crashes) or assume that outcomes' classifications are externally provided (e.g., by the users). To address the limitations of existing approaches, we have developed three techniques for automatically classifying execution data as belonging to one of several classes. In this paper, we introduce our techniques and apply them to the binary classification of passing and failing behaviors. Our three techniques impose different overheads on program instances and, thus, each is appropriate for different application scenarios. We performed several empirical studies to evaluate and refine our techniques and to investigate the trade-offs among them. Our results show that 1) the first technique can build very accurate models, but requires a complete set of execution data; 2) the second technique produces slightly less accurate models, but needs only a small fraction of the total execution data; and 3) the third technique allows for even further cost reductions by building the models incrementally, but requires some sequential ordering of the software instances' instrumentation.
Keywords: execution classification; remote analysis/measurement.

Topological Decompositions for 3D Non-manifold Simplicial Shapes - Hui,Annie; De Floriani, Leila (Department of Computer Science, University of Maryland, College Park, 2007)
Modeling and understanding complex non-manifold shapes is a key issue in several applications including form-feature identification in CAD/CAE, and shape recognition for Web searching. Geometric shapes are commonly discretized as simplicial 2- or 3-complexes embedded in the 3D Euclidean space. The topological structure of a non-manifold simplicial shape can be analyzed through its decomposition into a collection of components with simpler topology. The granularity of the decomposition depends on the combinatorial complexity of the components. In this paper, we present topological tools for structural analysis of three-dimensional non-manifold shapes. This analysis is based on a topological decomposition at two different levels. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.
Keywords: Technical Report

Toward Specifying and Validating Cross-Domain Policies - Hicks, Michael W.; Swamy,N.; Tsang,S. (Technical Reports from UMIACS, 2007)
Formal security policies are extremely useful for two related reasons. First, they allow a policy to be considered in isolation, separate from programs under the purview of the policy and separate from the implementation of the policy's enforcement. Second, policies can be checked for compliance against higher-level security goals by using automated analyses. By contrast, ad hoc enforcement mechanisms (for which no separate policies are specified) enjoy neither benefit, and non-formal policies enjoy the first but not the second. We would like to understand how best to define (and enforce) multi-level security policies when information must be shared across domains that have varying levels of trust (the so-called "cross domain" problem). Because we wish to show such policies meet higher-level security goals with high assurance, we are interested in specifying cross domain policies formally, and then reasoning about them using automated tools. In this report, we briefly survey work that presents formal security policies with cross-domain concerns, in particular with respect to the problem of downgrading. We also describe correctness properties for such policies, all based on noninterference. Finally, we briefly discuss recently-developed tools for analyzing formal security policies; though no existing tools focus on the analysis of downgrading-oriented policies, existing research points the way to providing such support.

Towards a semantic web system for understanding real world representations - Papaleo,L.; De Floriani, Leila; Hendler,J.; Hui,A. (Proceedings of the Tenth International Conference on Computer Graphics and Artificial Intelligence, 2007)
As the volume of multimedia content available on the Web continues to increase, there is a clearneed for more advanced techniques for effective retrieval and management of such data. In this context, we see a growing interest in exploiting the potential of the Semantic Web in different research fields. But, on the other hand, there is a general lack of tools able to analyse, organize and understand digital shape models (especially 3D models) for easily populating repositories with complete and well-detailed metadata. Several steps are necessary to create and associate semantics with a shape and some of them are clearly context-dependent. In this paper, we present the design details of our new system, that we call be-SMART, for inspecting digital 3D shapes by extracting geometrical and topological information from them and for structuring and annotating these shapes using ontology-driven metadata. In particular, we describe the general structure of the system, the different modules and their mutual relations. We then concentrate on the first two modules of the system showing how the 3D models are annotated following ontology-driven metadata. We also provide motivations for further work in developing new techniques for both annotating and managing 3D models on the Web.

TREMOR—a tool for retrieving transcriptional modules by incorporating motif covariance - Singh,Larry N.; Wang,Li-San; Hannenhalli, Sridhar (Nucleic Acids Research, 2007)
A transcriptional module (TM) is a collection of transcription factors (TF) that as a group, co-regulate multiple, functionally related genes. The task of identifying TMs poses an important biological challenge. Since TFs belong to evolutionarily and structurally related families, TF family members often bind to similar DNA motifs and can confound sequence-based approaches to TM identification. A previous approach to TM detection addresses this issue by pre-selecting a single representative from each TF family. One problem with this approach is that closely related transcription factors can still target sufficiently distinct genes in a biologically meaningful way, and thus, pre-selecting a single family representative may in principle miss certain TMs. Here we report a method—TREMOR (Transcriptional Regulatory Module Retriever). This method uses the Mahalanobis distance to assess the validity of a TM and automatically incorporates the inter-TF binding similarity without resorting to pre-selecting family representatives. The application of TREMOR on human muscle-specific, liver-specific and cell-cycle-related genes reveals TFs and TMs that were validated from literature and also reveals additional related genes.

A two-level topological decomposition for non-manifold simplicial shapes - Hui,Annie; De Floriani, Leila (Proceedings of the 2007 ACM symposium on Solid and physical modeling, 2007)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis. Geometric shapes are commonly discretized as two- or three-dimensional simplicial complexes embedded in the 3D Euclidean space. The topological structure of a nonmanifold simplicial shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we present a topological decomposition of a shape at two different levels, with different degrees of granularity. We discuss the topological properties of the components at each level, and we present algorithms for computing such decompositions. We investigate the relations among the components, and propose a graph-based representation for such relations.
Keywords: Non-manifold modeling; shape decomposition; shape modeling; simplicial complexes

Ultrastructure of coccoid viable but non‐culturable Vibrio cholerae - Chaiyanan,Saipin; Chaiyanan,Sitthipan; Grim,Christopher; Maugel,Timothy; Huq,Anwar; Rita R Colwell (Environmental Microbiology, 2007)
Morphology of viable but non-culturable Vibrio cholerae was monitored for 2 years by scanning and transmission electron microscopy. Morphological changes included very small coccoid forms, after extended incubation at 4°C and room temperature, and sequential transformation from curved rods to irregular (∼1 μm) rods to ∼0.8 μm coccoid cells and, ultimately, to tiny coccoid forms (0.07–0.4 μm). Irregular rod-shaped and coccoid cells were equally distributed in microcosms during the first 30–60 days of incubation at both temperatures, but only coccoid cells were observed after incubation for 60 days at 4°C. When V. cholerae O1 and O139, maintained for 30–60 days at both temperatures, were heated to 45°C for 60 s, after serial passage through 0.45 μm and 0.1 μm filters, and plating on Luria–Bertania (LB) agar, only cells larger than 1 μm yielded colonies on LB agar. Approximately 0.1% of heat-treated cultures were culturable. Cell division in the smallest coccoid cells was observed, yielding daughter cells of equal size, whereas other coccoid cells revealed bleb-like, cell wall evagination, followed by transfer of nuclear material. Coccoid cells of V. cholerae O1 and O139 incubated at 4°C for more than 1 year remained substrate responsive and antigenic.

Universally-composable two-party computation in two rounds - Horvitz,Omer; Katz, Jonathan (Proceedings of the 27th annual international cryptology conference on Advances in cryptology, 2007)
Round complexity is a central measure of efficiency, and characterizing the round complexity of various cryptographic tasks is of both theoretical and practical importance. We show here a universally-composable (UC) protocol (in the common reference string model) for two-party computation of any functionality, where both parties receive output, using only two rounds. (This assumes honest parties are allowed to transmit messages simultaneously in any given round; we obtain a three-round protocol when parties are required to alternate messages.) Our results match the obvious lower bounds for the round complexity of secure two-party computation under any reasonable definition of security, regardless of what setup is used. Thus, our results establish that secure two-party computation can be obtained under a commonly-used setup assumption with maximal security (i.e., security under general composition) in a minimal number of rounds. To give but one example of the power of our general result, we observe that as an almost immediate corollary we obtain a two-round UC blind signature scheme, matching a result by Fischlin at Crypto 2006 (though, in contrast to Fischlin, we use specific number-theoretic assumptions).

Using a distributed quadtree index in peer-to-peer networks - Tanin,Egemen; Harwood,Aaron; Samet, Hanan (The VLDB Journal, 2007)
Peer-to-peer (P2P) networks have become a powerful means for online data exchange. Currently, users are primarily utilizing these networks to perform exact-match queries and retrieve complete files. However, future more data intensive applications, such as P2P auction networks, P2P job-search networks, P2P multiplayer games, will require the capability to respond to more complex queries such as range queries involving numerous data types including those that have a spatial component. In this paper, a distributed quadtree index that adapts the MX-CIF quadtree is described that enables more powerful accesses to data in P2P networks. This index has been implemented for various prototype P2P applications and results of experiments are presented. Our index is easy to use, scalable, and exhibits good load-balancing properties. Similar indices can be constructed for various multidimensional data types with both spatial and non-spatial components.
Keywords: Distributed data structures; peer-to-peer networks; quadtrees; spatial data structures

Variola virus topoisomerase: DNA cleavage specificity and distribution of sites in Poxvirus genomes - Minkah,Nana; Hwang,Young; Perry,Kay; Van Duyne,Gregory D.; Hendrickson,Robert; Lefkowitz,Elliot J.; Hannenhalli, Sridhar; Bushman,Frederic D. (Virology, 2007)
Topoisomerase enzymes regulate superhelical tension in DNA resulting from transcription, replication, repair, and other molecular transactions. Poxviruses encode an unusual type IB topoisomerase that acts only at conserved DNA sequences containing the core pentanucleotide 5'-(T/C)CCTT-3'. In X-ray structures of the variola virus topoisomerase bound to DNA, protein-DNA contacts were found to extend beyond the core pentanucleotide, indicating that the full recognition site has not yet been fully defined in functional studies. Here we report quantitation of DNA cleavage rates for an optimized 13 bp site and for all possible single base substitutions (40 total sites), with the goals of understanding the molecular mechanism of recognition and mapping topoisomerase sites in poxvirus genome sequences. The data allow a precise definition of enzyme-DNA interactions and the energetic contributions of each. We then used the resulting "action matrix" to show that favorable topoisomerase sites are distributed all along the length of poxvirus DNA sequences, consistent with a requirement for local release of superhelical tension in constrained topological domains. In orthopox genomes, an additional central cluster of sites was also evident. A negative correlation of predicted topoisomerase sites was seen relative to early terminators, but no correlation was seen with early or late promoters. These data define the full variola virus topoisomerase recognition site and provide a new window on topoisomerase function in vivo.
Keywords: Annotation of topoisomerase sites; Sequence specific recognition; Topoisomerase IB; Variola virus

Verified Enforcement of Security Policies for Cross-Domain Information Flows - Swamy,Nikhil; Hicks, Michael W.; Tsang,Simon (IEEE Military Communications Conference, 2007. MILCOM 2007, 2007)
We describe work in progress that uses program analysis to show that security-critical programs, such as cross-domain guards, correctly enforce cross-domain security policies. We are enhancing existing techniques from the field of Security-oriented Programming Languages to construct a new language for the construction of secure networked applications, SELINKS. In order to specify and enforce expressive and fine-grained policies, we advocate dynamically associating security labels with sensitive entities. Programs written in SELINKS are statically guaranteed to correctly manipulate an entity's security labels and to ensure that the appropriate policy checks mediate all operations that are performed on the entity. We discuss the design of our main case study : a web-based Collaborative Planning Application that will permit a collection of users, with varying security requirements and clearances, to access sensitive data sources and collaboratively create documents based on these sources.
Keywords: Collaboration; Computer languages; Data security; Educational institutions; Government; Information analysis; Information filtering; Information filters; Information security; Vehicles

Viable but nonculturable Vibrio cholerae O1 in biofilms in the aquatic environment and their role in cholera transmission - Alam,M.; Sultana,M.; Nair,G. B.; Siddique,A. K.; Hasan,N. A.; Sack,R. B.; Sack,D. A.; Ahmed,K. U.; Sadique,A.; Watanabe,H.; Rita R Colwell (Proceedings of the National Academy of Sciences, 2007)
Vibrio cholerae persists in aquatic environments predominantly in a nonculturable state. In this study coccoid, nonculturable V. cholerae O1 in biofilms maintained for 495 days in Mathbaria, Bangladesh, pond water became culturable upon animal passage. Culturability, biofilm formation, and the wbe, ctxA, and rstR2 genes were monitored by culture, direct fluorescent antibody (DFA), and multiplex PCR. DFA counts were not possible after formation of biofilm. Furthermore, wbe, but not ctxA, were amplifiable, even after incubation for 54 and 68 days at room temperature (≈25°C) and 4°C, respectively, when no growth was detectable. Slower biofilm formation and extended culturability were observed for cultures incubated at 4°C, compared with ≈25°C, suggesting biofilm production to be temperature dependent and linked to loss of culturability. Small colonies appearing after incubation in microcosms for 54 and 68 days at 25°C and 4°C, respectively, were wbe positive and ctxA and rstR2 negative, indicating loss of bacteriophage CTXΦ. The coccoid V. cholerae O1 observed as free cells in microcosms incubated for 495 days could not be cultured, but biofilms in the same microcosms yielded culturable cells. It is concluded that biofilms can act as a reservoir for V. cholerae O1 between epidemics because of its long-term viability in biofilms. In contrast to biofilms produced in Mathbaria pond water, V. cholerae O1 in biofilms present in cholera stools and incubated under identical conditions as the Mathbaria pond water biofilms could not be cultured after 2 months, indicating that those V. cholerae cells freshly discharged into the environment are significantly less robust than cells adapted to environmental conditions.Bangladesh bacteriophage CTXΦ DFA multiplex-PCR ctxA

Annotation compatibility working group report - Meyers,A.; Fang,A. C.; Ferro,L.; Kübler,S.; Jia-Lin,T.; Palmer,M.; Poesio,M.; Dolbey,A.; Schuler,K. K.; Loper,E.; Zinsmeister,H.; Penn,G.; et al. (Proceedings of the Workshop on Frontiers in Linguistically Annotated Corpora 2006, 2006)
This report explores the question of compatibility between annotation projects including translating annotation formalisms to each other or to common forms. Compatibility issues are crucial for systems that use the results of multiple annotation projects. We hope that this report will begin a concerted effort in the field to track the compatibility of annotation schemes for part of speech tagging, time annotation, treebanking, role labeling and other phenomena.

Appearance-based person recognition using color/path-length profile - Yoon,K.; Harwood,D.; Davis, Larry S. (Journal of Visual Communication and Image Representation, 2006)

Applications of Parameterized st-Orientations in Graph Drawing Algorithms - Charalampos Papamanthou; Tollis, Ioannis G. (Graph Drawing, 2006)
Many graph drawing algorithms use st-numberings (st-orien-tations or bipolar orientations) as a first step. An st-numbering of a biconnected undirected graph defines a directed graph with no cycles, one single source s and one single sink t. As there exist exponentially many st-numberings that correspond to a certain undirected graph G, using different st-numberings in various graph drawing algorithms can result in aesthetically different drawings with different area bounds. In this paper, we present results concerning new algorithms for parameterized st-orientations, their impact on graph drawing algorithms and especially in visibility representations.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

Approximate Data Collection in Sensor Networks using Probabilistic Models - Chu,D.; Deshpande, Amol; Hellerstein,J. M; Wei Hong (Proceedings of the 22nd International Conference on Data Engineering, 2006. ICDE '06, 2006)
Wireless sensor networks are proving to be useful in a variety of settings. A core challenge in these networks is to minimize energy consumption. Prior database research has proposed to achieve this by pushing data-reducing operators like aggregation and selection down into the network. This approach has proven unpopular with early adopters of sensor network technology, who typically want to extract complete "dumps" of the sensor readings, i.e., to run "SELECT *" queries. Unfortunately, because these queries do no data reduction, they consume significant energy in current sensornet query processors. In this paper we attack the "SELECT " problem for sensor networks. We propose a robust approximate technique called Ken that uses replicated dynamic probabilistic models to minimize communication from sensor nodes to the network’s PC base station. In addition to data collection, we show that Ken is well suited to anomaly- and event-detection applications. A key challenge in this work is to intelligently exploit spatial correlations across sensor nodes without imposing undue sensor-to-sensor communication burdens to maintain the models. Using traces from two real-world sensor network deployments, we demonstrate that relatively simple models can provide significant communication (and hence energy) savings without undue sacrifice in result quality or frequency. Choosing optimally among even our simple models is NPhard, but our experiments show that a greedy heuristic performs nearly as well as an exhaustive algorithm.
Keywords: Batteries; Biological system modeling; Biosensors; data mining; Databases; Energy consumption; Intelligent networks; Intelligent sensors; Robustness; Wireless sensor networks

Atomic instructions in java - Hovemeyer,D.; Pugh, William; Spacco,J. (ECOOP 2002—Object-Oriented Programming, 2006)

Automatic web services composition using Shop2 - Hendler,J.; Nau, Dana S.; Parsia,B.; Sirin,E.; Wu,D. (Department of Computer Science, University of Maryland, College Park, 2006)
Semantic markup of Web services will enable the automation of various kinds of tasks, including discovery, composition, and execution of Web services. We describe how an AI planning system (SHOP2) can be used with DAML-S Web service descriptions to automatically compose Web services.

Block preconditioners based on approximate commutators - Elman, Howard; Howle, V. E; Shadid, J.; Shuttleworth, R.; Tuminaro, R. (SIAM Journal on Scientific Computing, 2006)

Building and querying a P2P virtual world - Tanin,E.; Harwood,A.; Samet, Hanan; Nayar,D.; Nutanong,S. (Geoinformatica, 2006)
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, and, in this paper, we demonstrate how this limitation can be bridged by indexing and querying a 3D virtual-world on a dynamic distributed network. We present an algorithm for 3D range queries as well as an algorithm for nearest neighbor queries. We also show how to build such a complex application from the ground level of a P2P routing algorithm.

Challenges in building an Arabic-English GHMT system with SMT components - Habash,N.; Dorr, Bonnie J; Monz,C. (Proceedings of the 11th Annual Conference of the European Association for Machine Translation (EAMT-2006), 2006)
The research context of this paper is de-veloping hybrid machine translation (MT) systems that exploit the advantages of linguistic rule-based and statistical MT systems. Arabic, as a morphologically rich language, is especially challenging even without addressing the hybridiza- tion question. In this paper, we describe the challenges in building an Arabic- English generation-heavy machine trans- lation (GHMT) system and boosting it with statistical machine translation (SMT) components. We present an extensive evaluation of multiple system variants and report positive results on the advantages of hybridization.

Combination can be hard: Approximability of the unique coverage problem - Demaine,E. D; Hajiaghayi, Mohammad T.; Feige,U.; Salavatipour,M. R (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

Comprehensive analysis of alternative splicing in rice and comparative analyses with Arabidopsis - Campbell,Matthew A.; Haas,Brian J.; Hamilton,John P.; Mount, Stephen M.; Buell,C. Robin (BMC Genomics, 2006)
Recently, genomic sequencing efforts were finished for Oryza sativa (cultivated rice) and Arabidopsis thaliana (Arabidopsis). Additionally, these two plant species have extensive cDNA and expressed sequence tag (EST) libraries. We employed the Program to Assemble Spliced Alignments (PASA) to identify and analyze alternatively spliced isoforms in both species.

Configuration and representation of large-scale dataflow graphs using the dataflow interchange format - Corretjer,I.; Hsu,C.; Bhattacharyya, Shuvra S. (Proceedings of the IEEE Workshop on Signal Processing Systems, Banff, Canada, 2006)

Conservation Patterns in cis-Elements Reveal Compensatory Mutations - Evans,Perry; Donahue,Greg; Hannenhalli, Sridhar (Comparative GenomicsComparative Genomics, 2006)
Transcriptional regulation critically depends on proper interactions between transcription factors (TF) and their cognate DNA binding sites or cis elements. A better understanding and modelling of the TF-DNA interaction is an important area of research. The Positional Weight Matrix (PWM) is the most common model of TF-DNA binding and it presumes that the nucleotide preferences at individual positions within the binding site are independent. However, studies have shown that this independence assumption does not always hold. If the nucleotide preference at one position depends on the nucleotide at another position, a chance mutation at one position should exert selection pressures at the other position. By comparing the patterns of evolutionary conservation at individual positions within cis elements, here we show that positional dependence within binding sites is highly prevalent. We also show that dependent positions are more likely to be functional, as evidenced by a higher information content and higher conservation. We discuss two examples—Elk-1 and SAP-1 where the inferred compensatory mutation is consistent with known TF-DNA crystal structure.

Context-sensitive correlation analysis for detecting races - Pratikakis,P.; Foster, Jeffrey S.; Hicks, Michael W. (Proceedings of the ACM Conference on Programming Language Design and Implementation (PLDI), 2006)

Creativity Support Tools: Report From a U.S. National Science Foundation Sponsored Workshop - Shneiderman, Ben; Fischer,Gerhard; Czerwinski,Mary; Resnick,Mitch; Myers,Brad; Candy,Linda; Edmonds,Ernest; Eisenberg,Mike; Giaccardi,Elisa; Hewett,Tom; Jennings,Pamela; Kules,Bill; et al. (International Journal of Human-Computer Interaction, 2006)
Creativity support tools is a research topic with high risk but potentially very high payoff. The goal is to develop improved software and user interfaces that empower users to be not only more productive but also more innovative. Potential users include software and other engineers, diverse scientists, product and graphic designers, architects, educators, students, and many others. Enhanced interfaces could enable more effective searching of intellectual resources, improved collaboration among teams, and more rapid discovery processes. These advanced interfaces should also provide potent support in hypothesis formation, speedier evaluation of alternatives, improved understanding through visualization, and better dissemination of results. For creative endeavors that require composition of novel artifacts (e.g., computer programs, scientific papers, engineering diagrams, symphonies, artwork), enhanced interfaces could facilitate exploration of alternatives, prevent unproductive choices, and enable easy backtracking. This U.S. National Science Foundation sponsored workshop brought together 25 research leaders and graduate students to share experiences, identify opportunities, and formulate research challenges. Two key outcomes emerged: (a) encouragement to evaluate creativity support tools through multidimensional in-depth longitudinal case studies and (b) formulation of 12 principles for design of creativity support tools.Creativity support tools is a research topic with high risk but potentially very high payoff. The goal is to develop improved software and user interfaces that empower users to be not only more productive but also more innovative. Potential users include software and other engineers, diverse scientists, product and graphic designers, architects, educators, students, and many others. Enhanced interfaces could enable more effective searching of intellectual resources, improved collaboration among teams, and more rapid discovery processes. These advanced interfaces should also provide potent support in hypothesis formation, speedier evaluation of alternatives, improved understanding through visualization, and better dissemination of results. For creative endeavors that require composition of novel artifacts (e.g., computer programs, scientific papers, engineering diagrams, symphonies, artwork), enhanced interfaces could facilitate exploration of alternatives, prevent unproductive choices, and enable easy backtracking. This U.S. National Science Foundation sponsored workshop brought together 25 research leaders and graduate students to share experiences, identify opportunities, and formulate research challenges. Two key outcomes emerged: (a) encouragement to evaluate creativity support tools through multidimensional in-depth longitudinal case studies and (b) formulation of 12 principles for design of creativity support tools.

Cross-Language Access to Recorded Speech in the MALACH Project - Oard, Douglas; Demner-Fushman,Dina; Hajič,Jan; Ramabhadran,Bhuvana; Gustman,Samuel; Byrne,William; Soergel,Dagobert; Dorr, Bonnie J; Resnik, Philip; Picheny,Michael (Text, Speech and DialogueText, Speech and Dialogue, 2006)
The MALACH project seeks to help users find information in a vast multilingual collections of untranscribed oral history interviews. This paper introduces the goals of the project and focuses on supporting access by users who are unfamiliar with the interview language. It begins with a review of the state of the art in crosslanguage speech retrieval; approaches that will be investigated in the project are then described. Czech was selected as the first non-English language to be supported, so results of an initial experiment with Czech/English cross-language retrieval are reported.

Deblurring Images: Matrices, Spectra, and Filtering - Hansen,Per Christian; Nagy,James G.; O'Leary, Dianne P. (SIAM Press, 2006)

A decomposition-based representation for 3D simplicial complexes - Hui,Annie; Vaczlavik,Lucas; De Floriani, Leila (Proceedings of the fourth Eurographics symposium on Geometry processing, 2006)
We define a new representation for non-manifold 3D shapes described by three-dimensional simplicial complexes, that we call the Double-Level Decomposition (DLD) data structure. The DLD data structure is based on a unique decomposition of the simplicial complex into nearly manifold parts, and encodes the decomposition in an efficient and powerful two-level representation. It is compact, and it supports efficient topological navigation through adjacencies. It also provides a suitable basis for geometric reasoning on non-manifold shapes. We describe an algorithm to decompose a 3D simplicial complex into nearly manifold parts. We discuss how to build the DLD data structure from a description of a 3D complex as a collection of tetrahedra, dangling triangles and wire edges, and we present algorithms for topological navigation. We present a thorough comparison with existing representations for 3D simplicial complexes.

Dense Subgraph Computation Via Stochastic Search: Application to Detect Transcriptional Modules - Everett,Logan; Wang,Li-San; Hannenhalli, Sridhar (BioinformaticsBioinformatics, 2006)
Motivation: In a tri-partite biological network of transcription factors, their putative target genes, and the tissues in which the target genes are differentially expressed, a tightly inter-connected (dense) subgraph may reveal knowledge about tissue specific transcription regulation mediated by a specific set of transcription factors—a tissue-specific transcriptional module. This is just one context in which an efficient computation of dense subgraphs in a multi-partite graph is needed.Result: Here we report a generic stochastic search based method to compute dense subgraphs in a graph with an arbitrary number of partitions and an arbitrary connectivity among the partitions. We then use the tool to explore tissue-specific transcriptional regulation in the human genome. We validate our findings in Skeletal muscle based on literature. We could accurately deduce biological processes for transcription factors via the tri-partite clusters of transcription factors, genes, and the functional annotation of genes. Additionally, we propose a few previously unknown TF-pathway associations and tissue-specific roles for certain pathways. Finally, our combined analysis of Cardiac, Skeletal, and Smooth muscle data recapitulates the evolutionary relationship among the three tissues. Contact:sridharh@pcbi.upenn.edu

Detection, Isolation, and Identification of Vibrio cholerae from the Environment - Huq,Anwar; Grim,Christopher; Rita R Colwell; Nair,G. Balakrish (Current Protocols in MicrobiologyCurrent Protocols in Microbiology, 2006)
Keywords: culturable; DETECTION; Environment; identification; isolation; nonculturable; viable; Vibrio cholerae

Differential Transcriptional Response to Nonassociative and Associative Components of Classical Fear Conditioning in the Amygdala and Hippocampus - Keeley,Michael B; Wood,Marcelo A; Isiegas,Carolina; Stein,Joel; Hellman,Kevin; Hannenhalli, Sridhar; Abel,Ted (Learning & MemoryLearn. Mem., 2006)
Classical fear conditioning requires the recognition of conditioned stimuli (CS) and the association of the CS with an aversive stimulus. We used Affymetrix oligonucleotide microarrays to characterize changes in gene expression compared to naive mice in both the amygdala and the hippocampus 30 min after classical fear conditioning and 30 min after exposure to the CS in the absence of an aversive stimulus. We found that in the hippocampus, levels of gene regulation induced by classical fear conditioning were not significantly greater than those induced by CS alone, whereas in the amygdala, classical fear conditioning did induce significantly greater levels of gene regulation compared to the CS. Computational studies suggest that transcriptional changes in the hippocampus and amygdala are mediated by large and overlapping but distinct combinations of molecular events. Our results demonstrate that an increase in gene regulation in the amygdala was partially correlated to associative learning and partially correlated to nonassociative components of the task, while gene regulation in the hippocampus was correlated to nonassociative components of classical fear conditioning, including configural learning.

A Dimension-Independent Representation for Multiresolution Nonmanifold Meshes - De Floriani, Leila; Hui,Annie (Journal of Computing and Information Science in Engineering, 2006)
We consider the problem of representing and manipulating nonmanifold objects of any dimension and at multiple resolutions. We present a modeling scheme based on (1) a multiresolution representation, called the vertex-based nonmanifold multitessellation, (2) a compact and dimension-independent data structure, called the Simplified Incidence Graph (SIG), and (3) an atomic mesh update operator, called vertex-pair contraction/vertex expansion. We propose efficient algorithms for performing the vertex-pair contraction on a simplicial mesh encoded as a SIG, and an effective representation for encoding this multiresolution model based on a compact encoding of vertex-pair contractions and vertex expansions.
Keywords: computational geometry; graph theory; mesh generation

A dimension-independent simplicial data structure for non-manifold shapes - Hui,Annie; De Floriani, Leila (Department of Computer Science, University of Maryland, College Park, 2006)
We consider the problem of representing and manipulating non-manifoldmulti-dimensional shapes, discretized as $d$-dimensional simplicial Euclidean complexes, for modeling finite element meshes derived from CAD models. We propose a dimension-independent data structure for simplicial complexes, that we call the {\em Incidence Simplicial (IS)} data structure. The IS data structure is scalable to manifold complexes, and supports efficient traversal and update algorithms for performing topological modifications, such as hole removal or dimension reduction. It has the same expressive power and performances as the incidence graph, commonly used for dimension-independent representation of simplicial and cell complexes, but it is much more compact. We present efficient algorithms for traversing, generating and updating a simplicial complex described as an IS data structure. We compare the IS data structure with dimension-independent and dimension-specific representations for simplicial complexes. Finally, we briefly discuss two applications that the IS data structure supports, namely decomposition of non-manifold objects for effective geometric reasoning, and multi-resolution modeling of non-manifold multi-dimensional shapes.
Keywords: Technical Report

The effect of crossover on the behavior of the GA in dynamic environments: a case study using the shaky ladder hyperplane-defined functions - Rand, William; Riolo,Rick; Holland,John H. (Proceedings of the 8th annual conference on Genetic and evolutionary computation, 2006)
One argument as to why the hyperplane-defined functions (hdf's) are a good testbed for the genetic algorithm (GA) is that the hdf's are built in the same way that the GA works. In this paper we test that hypothesis in a new setting by exploring the GA on a subset of the hdf's which are dynamic---the shaky ladder hyperplane-defined functions (sl-hdf's). In doing so we gain insight into how the GA makes use of crossover during its traversal of the sl-hdf search space. We begin this paper by explaining the sl-hdf's. We then conduct a series of experiments with various crossover rates and various rates of environmental change. Our results show that the GA performs better with than without crossover in dynamic environments. Though these results have been shown on some static functions in the past, they are re-confirmed and expanded here for a new type of function (the hdf) and a new type of environment (dynamic environments). Moreover we show that crossover is even more beneficial in dynamic environments than it is in static environments. We discuss how these results can be used to develop a richer knowledge about the use of building blocks by the GA.
Keywords: crossover; dynamic environments; Genetic algorithms; hyperplane-defined functions; search

Effect of transport at ambient temperature on detection and isolation of Vibrio cholerae from environmental samples - Alam,M.; Sadique,A.; Bhuiyan,N. A.; Nair,G. B.; Siddique,A. K.; Sack,D. A.; Ahsan,S.; Huq,A.; Sack,R. B.; Rita R Colwell; others (Applied and environmental microbiology, 2006)
It has long been assumed that prolonged holding of environmental samples at the ambient air temperature prior to bacteriological analysis is detrimental to isolation and detection of Vibrio cholerae, the causative agent of pandemic cholera. The present study was aimed at understanding the effect of transporting environmental samples at the ambient air temperature on isolation and enumeration of V. cholerae. For water and plankton samples held at ambient temperatures ranging from 31°C to 35°C for 20 h, the total counts did not increase significantly but the number of culturable V. cholerae increased significantly compared to samples processed within 1 h of collection, as measured by culture, acridine orange direct count, direct fluorescent-antibody-direct viable count (DFA-DVC), and multiplex PCR analyses. For total coliform counts, total bacterial counts, and DFA-DVC counts, the numbers did not increase significantly, but the culturable plate counts for V. cholerae increased significantly after samples were held at the ambient temperature during transport to the laboratory for analysis. An increase in the recovery of V. cholerae O1 and improved detection of V. cholerae O1 rfb and ctxA also occurred when samples were enriched after they were kept for 20 h at the ambient temperature during transport. Improved detection and isolation of toxigenic V. cholerae from freshwater ecosystems can be achieved by holding samples at the ambient temperature, an observation that has significant implications for tracking this pathogen in diverse aquatic environments.

Efficient simulation of critical synchronous dataflow graphs - Hsu,C. J; Ramasubbu,S.; Ko,M. Y; Pino,J. L; Bhattacharyya, Shuvra S. (Proceedings of the 43rd annual Design Automation Conference, 2006)

An empirical study to compare two parallel programming models - Hochstein, Lorin; Basili, Victor R. (Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, 2006)
While there are strong beliefs within the community about whether one particular parallel programming model is easier to use than another, there has been little research to analyze these claims empirically. Currently, the most popular paradigm is message-passing, as implemented by the MPI library [1]. However, MPI is considered to be difficult for developing programs, because it forces the programmer to work at a very low level of abstraction. One alternative parallel programming model is the PRAM model, which supports fine-grained parallelism and has a substantial history of algorithmic theory [2]. It is not possible to program current parallel machines using the PRAM model because modern architectures are not designed to support such a model efficiently. However, current trends towards multicore chips suggest that large-scale, fine-grained uniform-memory access parallel machines may soon be feasible. XMT-C is an extension of the C language that supports parallel directives to provide a PRAM-like model to the programmer. A prototype compiler exists that generates code which runs on a simulator for an XMT architecture [3].To better understand how much benefit a PRAM-like model could provide over a message-passing model, we conducted a feasibility study in an academic setting to compare the effort required to solve a particular problem. The questions under study were: can we measure the effort in developing a program using these two programming models and can we differentiate the amount of effort for each model?.The subjects participating in the study were divided up into two groups. One group solved a problem using the MPI library in either C,C++, or Fortran, and the other group solved the problem using XMT-C. The task was to write a function to multiply a sparse matrix with a dense vector. To obtain subjects, we leveraged existing graduate-level parallel programming courses at two different universities: University of California, Santa Barbara (UCSB), and University of Maryland (UMD). At UCSB, the students solved the problem in MPI, and at UMD, the students solved the same problem in XMT-C. The focus of the UCSB class was on developing parallel programs to run on the current generation of architectures, and the students were taught MPI, as well as other models. The focus of the UMD class was parallel algorithms in the PRAM model, and the students were taught XMT-C. The students were assigned to treatment groups by class. The study was integrated into each class, as the problem was a required assignment in each class.Subjects kept track of their effort with a self-reported effort log. We also collected automatic effort data by instrumenting the compilers, which recorded data at each compile. We computed three effort measures: self-reported, instrumented, and combined. Self-reported effort measures are based entirely on effort logs, instrumented effort measures are based entirely on timestamps from the instrumented compilers, and combined effort measures are based on compiler timestamps when the subject is working on the instrumented machine, and self-reported effort when the subject is working off the instrumented machine.The results of this preliminary study answer both of our questions in the positive. In this case, on average, students required less effort to solve the problem using XMT-C compared to MPI. The reduction in mean effort was approximately 50% for all three measures, which was statistically significant at the level of p < .05 using a t-test.This study demonstrates that the effect of programming model on effort can be directly measured through empirical studies with human subjects. While no single study can conclusively demonstrate the advantage of one programming model over another, a series of studies examining different models and different problems can provide insights into the relative strengths of parallel programming models in different contexts. The study described above is one of a series of such studies that we are currently conducting.
Keywords: effort; empirical study; HPC; Message-passing; MPI; parallel programming; PRAM; Productivity; XMT

Energy-efficient embedded software implementation on multiprocessor system-on-chip with multiple voltages - Hua,S.; Qu,G.; Bhattacharyya, Shuvra S. (ACM Transactions on Embedded Computing Systems (TECS), 2006)

Entity Resolution in Graphs - Bhattacharya,Indrajit; Getoor, Lise (Mining Graph DataMining Graph Data, 2006)
This chapter contains sections titled:Introduction Related Work Motivating Example for Graph-Based Entity Resolution Graph-Based Entity Resolution: Problem Formulation Similarity Measures for Entity Resolution Graph-Based Clustering for Entity Resolution Experimental Evaluation Conclusion References
Keywords: entity resolution in graphs; graph‐based clustering for entity resolution; graph‐based entity resolution problem

The evolution of the international children's digital library searching and browsing interface - Hutchinson,H.B.; Bederson, Benjamin B.; Druin, Allison (Proceedings of the 2006 conference on Interaction design and children, 2006)

Existential Label Flow Inference Via CFL Reachability - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W. (Static AnalysisStatic Analysis, 2006)
In programming languages, existential quantification is useful for describing relationships among members of a structured type. For example, we may have a list in which there exists some mutual exclusion lock l in each list element such that l protects the data stored in that element. With this information, a static analysis can reason about the relationship between locks and locations in the list even when the precise identity of the lock and/or location is unknown. To facilitate the construction of such static analyses, this paper presents a context-sensitive label flow analysis algorithm with support for existential quantification. Label flow analysis is a core part of many static analysis systems. Following Rehof et al, we use context-free language (CFL) reachability to develop an efficient O(n 3) label flow inference algorithm. We prove the algorithm sound by reducing its derivations to those in a system based on polymorphically-constrained types, in the style of Mossin. We have implemented a variant of our analysis as part of a data race detection tool for C programs.

Experiments to understand HPC time to development - Hochstein, Lorin; Nakamura,Taiga; Basili, Victor R.; Asgari, Sima; Zelkowitz, Marvin V; Hollingsworth, Jeffrey K; Shull, Forrest; Carver,Jeffrey; Voelp,Martin; Zazworka, Nico; Johnson,Philip (CTWatch Quarterly, 2006)
In order to understand how high performance computing (HPC) programs are developed, a series of experiments, using students in graduate level HPC classes, have been conducted at many universities in the US. In this paper we discuss the general process of conducting those experiments, give some of the early results of those experiments, and describe a web-based process we are developing that will allow us to run additional experiments at other universities and laboratories that will be easier to conduct and generate results that more accurately reflect the process of building HPC programs.
Keywords: hackystat; HPC; publications-journals

Exploring QIM-based anti-collusion fingerprinting for multimedia - Swaminathan,A.; He,S.; Wu,M. (Proceedings of SPIE, 2006)
Digital fingerprinting is an emerging technology to protect multimedia from unauthorizeduse by embedding a unique fingerprint signal into each user’s copy. A robust embedding algorithm is an important building block in order to make the fingerprint resilient to vari- ous distortions and collusion attacks. Spread spectrum embedding has been widely used for multimedia fingerprinting. In this paper, we explore another class of embedding methods – Quantization Index Modulation (QIM) for fingerprinting applications. We first employ Dither Modulation (DM) technique and extend it for embedding multiple symbols through a basic dither sequence design. We then develop a theoretical model and propose a new algorithm to improve the collusion resistance of the basic scheme. Simulation results show that the improvement algorithm enhances the collusion resistance, while there is still a performance gap with the existing spread spectrum based fingerprinting. We then explore coded fingerprinting based on spread transform dither modulation (STDM) embedding. Simulation results show that this coded STDM based fingerprinting has significant advantages over spread spectrum based fingerprinting under blind detection.

First Steps Toward an Electronic Field Guide for Plants - Haibin,Gaurav Agarwal; Agarwal,Gaurav; Ling,Haibin; Jacobs, David W.; Shirdhonkar,Sameer; Kress,W. John; Russell,Rusty; Belhumeur,Peter; Dixit,An; Feiner,Steve; Mahajan,Dhruv; Sunkavalli,Kalyan; et al. (Taxon, 2006)
this paper, we will describe our progress towards building a digital collection of the Smithsonian's type specimens, developing recognition algorithms that can match an image of a leaf to the species of plant from which it comes, and designing user interfaces for interacting with an electronic field guide. To start, we are developing a prototype electronic field guide for the flora of Plummers Island, a small, well-studied island in the Potomac River. This prototype system contains multiple images for each of about 130 species of plants on the island, and should soon grow to cover all 200+ species currently recorded (Shetler et al., 2005). Images of full specimens are available, as well as images of isolated leaves of each species. A zoomable user interface allows a user to browse these images, zooming in on ones of interest. Visual recognition algorithms assist a botanist in locating the specimens that are most relevant to identify the species of a plant. The system currently runs on a small hand-held computer. We will describe the components of this prototype, and also describe some of the future challenges we anticipate if we are to provide botanists in the field with all the resources that are now currently available in the world's museums and herbaria. Type Specimen Digital Collection The first challenge in producing our electronic field guide is to create a digital collection covering all of the Smithsonian's 85,000 vascular plant type specimens. For each type specimen, the database should eventually include systematically acquired high-resolution digital images of the specimen, textual descriptions, links to decision trees, images of live plants, and 3D models. Figure 1: On the left, our set-up at the Smithsonian for digitally photographing type specimens. On the...

Flow algorithms for two pipelined filter ordering problems - Condon,Anne; Deshpande, Amol; Hellerstein,Lisa; Wu,Ning (Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006)
Pipelined filter ordering is a central problem in database query optimization, and has received renewed attention recently in the context of environments such as the web, continuous high-speed data streams and sensor networks. We present algorithms for two natural extensions of the classical pipelined filter ordering problem: (1) a distributional type problem where the filters run in parallel and the goal is to maximize throughput, and (2) an adversarial type problem where the goal is to minimize the expected value of multiplicative regret. We show that both problems can be solved using similar flow algorithms, which find an optimal ordering scheme in time O(n2), where n is the number of filters. Our algorithm for (1) improves on an earlier O(n3 log n) algorithm of Kodialam.
Keywords: flow algorithms; Pipelined filter ordering; Query optimization; selection ordering

Functional Analysis of Hes-1 in Preadipocytes - Ross,David A; Hannenhalli, Sridhar; Tobias,John W; Cooch,Neil; Shiekhattar,Ramin; Kadesch,Tom (Molecular EndocrinologyMolecular Endocrinology, 2006)
Notch signaling blocks differentiation of 3T3-L1 preadipocytes, and this can be mimicked by constitutive expression of the Notch target gene Hes-1. Although considered initially to function only as a repressor, recent evidence indicates that Hes-1 can also activate transcription. We show here that the domains of Hes-1 needed to block adipogenesis coincide with those necessary for transcriptional repression. HRT1, another basic-helix-loop-helix protein and potential Hes-1 partner, was also induced by Notch in 3T3-L1 cells but did not block adipogenesis, suggesting that Hes-1 functions primarily as a homodimer or possibly as a heterodimer with an unknown partner. Purification of Hes-1 identified the Groucho/transducin-like enhancer of split family of corepressors as the only significant Hes-1 interacting proteins in vivo. An evaluation of global gene expression in preadipocytes identified approximately 200 Hes-1-responsive genes comprising roughly equal numbers of up-regulated and down-regulated genes. However, promoter analyses indicated that the down-regulated genes were significantly more likely to contain Hes-1 binding sites, indicating that Hes-1 is more likely to repress transcription of its direct targets. We conclude that Notch most likely blocks adipogenesis through the induction of Hes-1 homodimers, which repress transcription of key target genes.

Geometry-dependent lighting - Lee,C. H; Hao,X.; Varshney, Amitabh (Visualization and Computer Graphics, IEEE Transactions on, 2006)
In this paper, we introduce geometry-dependent lighting that allows lighting parameters to be defined independently and possibly discrepantly over an object or scene based on the local geometry. We present and discuss light collages, a lighting design system with geometry-dependent lights for effective feature-enhanced visualization. Our algorithm segments the objects into local surface patches and places lights that are locally consistent but globally discrepant to enhance the perception of shape. We use spherical harmonics for efficiently storing and computing light placement and assignment. We also outline a method to find the minimal number of light sources sufficient to illuminate an object well with our globally discrepant lighting approach.
Keywords: Computer-Assisted; Imaging; feature-enhanced visualization; geometry-dependent light; light collage; light placement; lighting design system; computational geometry; data visualisation; lighting; Algorithms; Computer Graphics; Image Enhancement; Image Interpretation; Three-Dimensional; Information Storage and Retrieval; Lighting; User-Computer Interface

Geometry-guided computation of 3D electrostatics for large biomolecules - Hao,Xuejun; Varshney, Amitabh (Computer Aided Geometric Design, 2006)
Electrostatic interactions play a central role in biological processes. Development of fast computational methods to solve the underlying Poisson–Boltzmann equation (PBE) is vital for biomolecular modeling and simulation package. In this paper, we propose new methods for efficiently computing the electrostatic potentials for large molecules by using the geometry of the molecular shapes to guide the computation. The accuracy and stability of the solution to the PBE is quite sensitive to the boundary layer between the solvent and the solute which defines the molecular surface. In this paper, we present a new interface-layer-focused PBE solver. First, we analytically construct the molecular surface of the molecule and compute a distance field from the surface. We then construct nested iso-surface layers outwards and inwards from the surface using the distance field. We have developed a volume simplification algorithm to adaptively adjust the density of the irregular grid based on the importance to the PBE solution. We have generalized the finite difference methods using Taylor series expansion on the irregular grids. Our algorithm achieves about three times speedup in the iterative solution process of PBE, with more accurate results on an analytical solvable testing case, compared with the popular optimized DelPhi program.
Keywords: Finite difference methods; Iso-surface generation; Level-of-detail of hierarchy; Poisson–Boltzmann equation; Scalar field; Tetrahedron decomposition

Heuristic search and information visualization methods for school redistricting - desJardins, Marie; Bulka,Blazej; Carr,Ryan; Hunt,Andrew; Rathod,Priyang; Rheingans,Penny (Proceedings of the 18th conference on Innovative applications of artificial intelligence - Volume 2, 2006)
We describe an application of AI search and information visualization techniques to the problem of school redistricting, in which students are assigned to home schools within a county or school district. This is a multicriteria optimization problem in which competing objectives must be considered, such as school capacity, busing costs, and socioeconomic distribution. Because of the complexity of the decision-making problem, tools are needed to help end users generate, evaluate, and compare alternative school assignment plans. A key goal of our research is to aid users in finding multiple qualitatively different redistricting plans that represent different tradeoffs in the decision space.We present heuristic search methods that can be used to find a set of qualitatively different plans, and give empirical results of these search methods on population data from the school district of Howard County, Maryland. We show the resulting plans using novel visualization methods that we have developed for summarizing and comparing alternative plans.

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

Identification and cross-species comparison of canine osteoarthritic gene regulatory cis-elements - Hannenhalli, Sridhar; Middleton,R.P.; Levy,S.; Perroud,B.; Holzwarth,J.A.; McDonald,K.; Hannah,S.S. (Osteoarthritis and Cartilage, 2006)
SummaryObjectiveTo better understand transcription regulation of osteoarthritis (OA) by examining common promoter motifs in canine osteoarthritic genes, to identify other genes containing these motifs and to assess the conservation of these motifs between canine, human, mouse and rat. Design Differentially expressed transcripts in canine OA were mapped to the human genome. We thus identified 20 orthologous human transcripts representing 19 up-regulated genes and 62 orthologous transcripts representing 60 down-regulated genes. The 5 kbp upstream regions of these transcripts were used to identify binding sites and build promoter models based on those sites. The human genome was subsequently searched for other transcripts likely to be regulated by the same promoter models. Orthologous transcripts were then identified in canine, rat and mouse for determination of potential cross-species conservation of binding sites comprising the promoter model. Results Four promoter models containing 5–6 transcripts and 5–8 common transcription factor binding sites were developed. They include binding sites for AP-4, AP-2α and γ, and E2F. Several hundred other human genes were found to contain these promoter motifs. Furthermore these motifs were significantly over represented in the orthologous genes in canine, rat and mouse genomes. Conclusions We have developed and applied a computational methodology to identify common promoter elements implicated in OA and shared amongst four higher vertebrates. The transcription factors associated with these binding sites and other genes driven by these promoter motifs have been implicated in OA, chondrocyte development and with other biological factors involved in the disease.
Keywords: Chondrocyte; Gene expression; Osteoarthritis; Promoter

Identifying domain-specific defect classes using inspections and change history - Nakamura,Taiga; Hochstein, Lorin; Basili, Victor R. (Proceedings of the 2006 ACM/IEEE international symposium on Empirical software engineering, 2006)
We present an iterative, reading-based methodology for analyzing defects in source code when change history is available. Our bottom-up approach can be applied to build knowledge of recurring defects in a specific domain, even if other sources of defect data such as defect reports and change requests are unavailable, incomplete or at the wrong level of abstraction for the purposes of the defect analysis. After defining the methodology, we present the results of an empirical study where our method was applied to analyze defects in parallel programs which use the MPI (Message Passing Interface) library to express parallelism. This library is often used in the domain of high performance computing, where there is much discussion but little empirical data about the frequency and severity of defect types. Preliminary results indicate the methodology is feasible and can provide insights into the nature of real defects. We present the results, derived hypothesis, and lessons learned.
Keywords: change history; code reading; domain specific defects; Inspection

An improved approximation algorithm for vertex cover with hard capacities - Gandhi,Rajiv; Halperin,Eran; Khuller, Samir; Kortsarz,Guy; Srinivasan, Aravind (Journal of Computer and System Sciences, 2006)
We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G = ( V , E ) , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy–Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.
Keywords: Approximation algorithms; Capacitated covering; Linear programming; Randomized rounding; Set cover; Vertex cover

Improved lower and upper bounds for universal TSP in planar metrics - Hajiaghayi, Mohammad T.; Kleinberg,R.; Leighton,T. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

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

Integrating data and interfaces to enhance understanding of government statistics: toward the national statistical knowledge network project briefing - Marchionini,G.; Haas,S.; Plaisant, Catherine; Shneiderman, Ben (Proceedings of 7th Annual International Conference on Digital Libraries (DG06), 2006)
This paper reports the results of work in the final no-costextension year of a digital government project that developed user interface models and prototypes to help people find and understand government statistics; proposed a Statistical Knowledge Network architecture that supports cross agency information access; and demonstrated models for government- academic collaboration.

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

Invited Talk: Deciphering Gene Regulatory Networks by in silico approaches - Hannenhalli, Sridhar (6th International Workshop on Data Mining in Bioinformatics (BIOKDD06), 2006)
Biological processes are controlled at various levels in the celland while these mechanisms are poorly understood, tran- scriptional control is widely recognized as an important com- ponent and a better understanding of which will provide an efficient means for the therapeutic intervention in disease processes. We have been focusing on various computational problems pertaining to transcriptional regulation, namely, (1) representation and identification of transcription factor binding sites,(2) PolII promoter prediction,(3) Predicting interaction among transcription factors,(4) Transcriptional modeling, ie identifying arrangements of TFs that co- regulate a set of transcripts. I will present a brief overview of the computational approaches and challenges as well as a number of applications including transcriptional regulation in memory storage, heart failure, and osteoarthritis.

Joint coding and embedding techniques for MultimediaFingerprinting - He,Shan; M. Wu (Information Forensics and Security, IEEE Transactions on, 2006)
Digital fingerprinting protects multimedia content from illegal redistribution by uniquely marking every copy of the content distributed to each user. The collusion attack is a powerful attack where several different fingerprinted copies of the same content are combined together to attenuate or even remove the fingerprints. One major category of collusion-resistant fingerprinting employs an explicit step of coding. Most existing works on coded fingerprinting mainly focus on the code-level issues and treat the embedding issues through abstract assumptions without examining the overall performance. In this paper, we jointly consider the coding and embedding issues for coded fingerprinting systems and examine their performance in terms of collusion resistance, detection computational complexity, and distribution efficiency. Our studies show that coded fingerprinting has efficient detection but rather low collusion resistance. Taking advantage of joint coding and embedding, we propose a permuted subsegment embedding technique and a group-based joint coding and embedding technique to improve the collusion resistance of coded fingerprinting while maintaining its efficient detection. Experimental results show that the number of colluders that the proposed methods can resist is more than three times as many as that of the conventional coded fingerprinting approaches.
Keywords: coding-embedding; coding; collusion-resistant; complexity; computational; data; DETECTION; embedded; EMBEDDING; fingerprinting; group-based; image; joint; multimedia; of; Security; subsegment; systems; technique; techniques

On the Least Median Square Problem - Erickson,Jeff; Har-Peled,Sariel; Mount, Dave (Discrete & Computational Geometry, 2006)
We consider the exact and approximate computational complexity of the multivariate least median-of-squares (LMS) linear regression estimator. The LMS estimator is among the most widely used robust linear statistical estimators. Given a set of n points in and a parameter k, the problem is equivalent to computing the narrowest slab bounded by two parallel hyperplanes that contains k of the points. We present algorithms for the exact and approximate versions of the multivariate LMS problem. We also provide nearly matching lower bounds for these problems. These lower bounds hold under the assumptions that k is Ω(n) and that deciding whether n given points in are affinely non-degenerate requires Ω(n d ) time.
Keywords: Mathematics and Statistics

Leveraging recurrent phrase structure in large-scale ontology translation - Murray,G. C; Dorr, Bonnie J; Jimmy Lin; Hajič,J.; Pecina,P. (Proceedings of the 11th Annual Conference of the European Association for Machine Translation, 2006)
This paper presents a process for leveraging structural relationships and reusablephrases when translating large-scale ontologies. Digital libraries are becoming more and more prevalent. An important step in providing universal access to such material is to pro- vide multi-lingual access to the underlying principles of organization via ontologies, thesauri, and controlled vocabularies. Machine translation of these resources requires high accuracy and a deep vocabulary. Human input is often required, but full manual translation can be slow and expensive. We report on a cost-effective approach to ontology translation. We describe our technique of prioritization, our process of collecting aligned translations and generating a new lexicon, and the resulting improvement to translation system output. Our preliminary evaluation indicates that this technique provides significant cost savings for human-assisted translation. The process we developed can be applied to ontologies in other domains and is easily incorporated into other translation systems.

Leveraging reusability: cost-effective lexical acquisition for large-scale ontology translation - Murray,G. Craig; Dorr, Bonnie J; Jimmy Lin; Hajič,Jan; Pecina,Pavel (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
Thesauri and ontologies provide important value in facilitating access to digital archives by representing underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most ontologies precludes fully-automated machine translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations when constructing domain-specific lexical resources. We evaluate the effectiveness of this process by producing a probabilistic phrase dictionary and translating a thesaurus of 56,000 concepts used to catalogue a large archive of oral histories. Our experiments demonstrate a cost-effective technique for accurate machine translation of large ontologies.

Lock inference for atomic sections - Hicks, Michael W.; Foster, Jeffrey S.; Pratikakis,P. (Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006)
To prevent unwanted interactions in multithreaded programs, pro-grammers have traditionally employed pessimistic, blocking con- currency primitives. Using such primitives correctly and efficiently is notoriously difficult. To simplify the problem, recent research proposes that programmers specify atomic sections of code whose executions should be atomic with respect to one another, without dictating exactly how atomicity enforced. Much work has explored using optimistic concurrency, or software transactions, as a means to implement atomic sections. This paper proposes to implement atomic sections using a static whole-program analysis to insert necessary uses of pessimistic con- currency primitives. Given a program that contains programmer- specified atomic sections and thread creations, our mutex infer- ence algorithm efficiently infers a set of locks for each atomic section that should be acquired (released) upon entering (exiting) the atomic section. The key part of this algorithm is determining which memory locations in the program could be shared between threads, and using this information to generate the necessary locks. To determine sharing, our analysis uses the notion of continuation effects to track the locations accessed after each program point. As continuation effects are flow sensitive, a memory location may be thread-local before a thread creation and thread-shared afterward. We prove that our algorithm is correct, and provides parallelism according to the precision of the points-to analysis. While our al- gorithm also attempts to reduce the number locks while preserving parallelism, we show that minimizing the number of locks is NP- hard.

LOCKSMITH: context-sensitive correlation analysis for race detection - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W. (SIGPLAN Not., 2006)
One common technique for preventing data races in multi-threaded programs is to ensure that all accesses to shared locations are consistently protected by a lock. We present a tool called LOCKSMITH for detecting data races in C programs by looking for violations of this pattern. We call the relationship between locks and the locations they protect consistent correlation, and the core of our technique is a novel constraint-based analysis that infers consistent correlation context-sensitively, using the results to check that locations are properly guarded by locks. We present the core of our algorithm for a simple formal language λ> which we have proven sound, and discuss how we scale it up to an algorithm that aims to be sound for all of C. We develop several techniques to improve the precision and performance of the analysis, including a sharing analysis for inferring thread locality; existential quantification for modeling locks in data structures; and heuristics for modeling unsafe features of C such as type casts. When applied to several benchmarks, including multi-threaded servers and Linux device drivers, LOCKSMITH found several races while producing a modest number of false alarm.
Keywords: context-sensitivity; correlation; locksmith; multi-threaded programming; race detection; Type inference

Machine Translation: Interlingual Methods - Dorr, Bonnie J; Hovy,E.; Levin,L. (Encyclopedia of Language & Linguistics (Second Edition)Encyclopedia of Language & Linguistics (Second Edition), 2006)
An interlingua is a notation for representing the content of a text that abstracts away from the characteristics of the language itself and focuses on the meaning (semantics) alone. Interlinguas are typically used as pivot representations in machine translation, allowing the contents of a source text to be generated in many different target languages. Because of the complexities involved, few interlinguas are more than demonstration prototypes, and only one has been used in a commercial MT system. In this article, we define the components of an interlingua and the principal issues faced by designers and builders of interlinguas and interlingua MT systems, illustrating with examples from operational systems and research prototypes. We discuss current efforts to annotate texts with interlingua-based information.
Keywords: approximate interlingua; compositionality; conceptual knowledge; cross-language divergences; interlingua; interlingual speech translation; language-independent representation; lexical-conceptual structure; Machine translation; ontology; predicate-argument structure; semantic annotation; semantic frames; semantic zones; text-meaning representations; THEMATIC ROLES

A mammalian promoter model links cis elements to genetic networks - Wang,Junwen; Hannenhalli, Sridhar (Biochemical and Biophysical Research Communications, 2006)
An accurate identification of gene promoters remains an important challenge. Computational approaches for this problem rely on promoter sequence attributes that are believed to be critical for transcription initiation. Here we report a probabilistic model that captures two important properties of promoters, not used by previous methods, viz., the location preference and co-occurrence of promoter elements. Additionally, we found that many of the position-specific DNA elements are strongly linked with the function of the gene product. For instance, a highly conserved motif CCTTT at -1 position is strongly associated with protein synthesis, cellular and tissue development. Our comparative analysis of promoter classes reveals that the promoters devoid of CpG islands are more conserved and have fewer alternative transcription start sites. The discovered links between promoter elements and gene function allows us to infer genetic networks from promoter elements. The web server for the PSPA promoter predictor is available at http://cagr.pcbi.upenn.edu/PSPA.
Keywords: conservation; Core promoter prediction; CpG island; Genetic networks; Position-specific motif; Propensity; Transcription factor binding site (TFBS)

Managing policy updates in security-typed languages - Swamy,N.; Hicks, Michael W.; Tse,S.; Zdancewic,S. (19th IEEE Computer Security Foundations Workshop, 2006, 2006)
This paper presents Rx, a new security-typed programming language with features intended to make the management of information-flow policies more practical. Security labels in Rx, in contrast to prior approaches, are defined in terms of owned roles, as found in the RT role-based trust-management framework. Role-based security policies allow flexible delegation, and our language Rx provides constructs through which programs can robustly update policies and react to policy updates dynamically. Our dynamic semantics use statically verified transactions to eliminate illegal information flows across updates, which we call transitive flows. Because policy updates can be observed through dynamic queries, policy updates can potentially reveal sensitive information. As such, Rx considers policy statements themselves to be potentially confidential information and subject to information-flow metapolicies
Keywords: Access control; Computer languages; Data security; Database systems; dynamic queries; dynamic semantics; Educational institutions; high level languages; Information security; information-flow policy management; Lattices; Network servers; Operating systems; policy update management; Robustness; role-based security policies; RT role-based trust-management framework; Rx security-typed programming language; security of data; statically verified transactions; transitive flows

Manufacturing of multi-material compliant mechanisms using multi-material molding - Gouker,Regina; Gupta, Satyandra K.; Bruck,Hugh; Holzschuh,Tobias (The International Journal of Advanced Manufacturing Technology, 2006)
Multi-material compliant mechanisms enable many new design possibilities. Significant progress has been made in the area of design and analysis of multi-material compliant mechanisms. What is now needed is a method to mass-produce such mechanisms economically. A feasible and practical way of producing such mechanisms is through multi-material molding. Devices based on compliant mechanisms usually consist of compliant joints. Compliant joints in turn are created by carefully engineering interfaces between a compliant and a rigid material. This paper presents an overview of multi-material molding technology and describes feasible mold designs for creating different types of compliant joints found in multi-material compliant mechanisms. It also describes guidelines essential to successfully utilizing the multi-material molding process for creating compliant mechanisms. Finally, practical applications for the use of multi-material molding to create compliant mechanisms are demonstrated.
Keywords: engineering

Mapping Multimedia Applications Onto Configurable Hardware With Parameterized Cyclo-Static Dataflow Graphs - Haim,F.; Sen,M.; Ko,Dong-Ik; Bhattacharyya, Shuvra S.; Wolf,W. (Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006)
This paper develops methods for model-based design and implementation of image processing applications. We apply our previously developed meta-modeling technique of homogeneous parameterized dataflow (HPDF) (M. Sen et al., 2005) to the framework of cyclostatic dataflow (CSDF) (G. Bilsen et al., 1996), and demonstrate this integrated modeling methodology through hardware mapping of a gesture recognition application. We also provide a comparative study between HPDF/CSDF-based representation of the gesture recognition application, and a previously developed version based on applying HPDF in conjunction with conventional synchronous dataflow (SDF) semantics (M. Sen et al., 2005)
Keywords: configurable hardware; Data communication; Gesture recognition; gesture recognition application; graph theory; hardware mapping; image processing applications; mapping multimedia applications; meta-modeling technique; model-based design; Multimedia communication; parameterized cyclo-static dataflow graphs

Model-based mapping of image registration applications onto configurable hardware - Hemaraj,Y.; Sen,M.; Shekhar,R.; Bhattacharyya, Shuvra S. (Signals, Systems and Computers, 2006. ACSSC'06. Fortieth Asilomar Conference on, 2006)

Model-based OpenMP implementation of a 3D facial pose tracking system - Saha,S.; Chung-Ching Shen; Chia-Jui Hsu; Aggarwal,G.; Veeraraghavan,A.; Sussman, Alan; Bhattacharyya, Shuvra S. (2006 International Conference on Parallel Processing Workshops, 2006. ICPP 2006 Workshops, 2006)
Most image processing applications are characterized by computation-intensive operations, and high memory and performance requirements. Parallelized implementation on shared-memory systems offer an attractive solution to this class of applications. However, we cannot thoroughly exploit the advantages of such architectures without proper modeling and analysis of the application. In this paper, we describe our implementation of a 3D facial pose tracking system using the OpenMP platform. Our implementation is based on a design methodology that uses coarse-grain dataflow graphs to model and schedule the application. We present our modeling approach, details of the implementation that we derived based on this modeling approach, and associated performance results. The parallelized implementation achieves significant speedup, and meets or exceeds the target frame rate under various configurations
Keywords: 3D facial pose tracking system; application modeling; application program interfaces; application scheduling; coarse-grain dataflow graphs; Concurrent computing; data flow graphs; Educational institutions; face recognition; IMAGE PROCESSING; image processing applications; Inference algorithms; Message passing; OpenMP platform; parallel implementation; PARALLEL PROCESSING; parallel programming; Particle tracking; Processor scheduling; SHAPE; shared memory systems; shared-memory systems; Solid modeling; tracking

Multiuser distortion management of layered video over resource limited downlink multicode-CDMA - Han,Z.; Su,Guan-Ming; Kwasinski,A.; M. Wu; Liu,K. J.R (Wireless Communications, IEEE Transactions on, 2006)
Transmitting multiple real-time encoded videos to multiple users over wireless cellular networks is a key driving force for developing broadband technology. We propose a new framework to transmit multiple users' video programs encoded by MPEG-4 FGS codec over downlink multicode CDMA networks in real time. The proposed framework jointly manages the rate adaptation of source and channel coding, CDMA code allocation, and power control. Subject to the limited system resources, such as the number of pseudo-random codes and the maximal power for CDMA transmission, we develop an adaptive scheme of distortion management to ensure baseline video quality for each user and further reduce the overall distortion received by all users. To efficiently utilize system resources, the proposed scheme maintains a balanced ratio between the power and code usages. We also investigate three special scenarios where demand, power, or code is limited, respectively. Compared with existing methods in the literature, the proposed algorithm can reduce the overall system's distortion by 14% to 26%. In the demand-limited case and the code-limited but power-unlimited case, the proposed scheme achieves the optimal solutions. In the power-limited but code-unlimited case, the proposed scheme has a performance very close to a performance upper bound
Keywords: (mobile; access; combined; allocation; broadband; case; layered; CDMA; cellular; code; codes; radio; codes; real-time; codes; telecommunication; coding; mobility; coding; video; coding; wireless; communication; control; pseudo-random; control; pseudonoise; control; video; distortion; division; downlink; encoded; limited; links; random; management; management; power; multicode-CDMA; source-channel; multiple; networks; broadband; networks; cellular; radio); power; radio; code; source-channel; technology; code-unlimited; video; multiuser; videos; resource

Multivalued default logic for identity maintenance in visual surveillance - Shet,V.; Harwood,D.; Davis, Larry S. (Computer Vision–ECCV 2006, 2006)
Recognition of complex activities from surveillance video requires detection and temporal ordering of its constituent “atomic” events. It also requires the capacity to robustly track individuals and maintain their identities across single as well as multiple camera views. Identity maintenance is a primary source of uncertainty for activity recognition and has been traditionally addressed via different appearance matching approaches. However these approaches, by themselves, are inadequate. In this paper, we propose a prioritized, multivalued, default logic based framework that allows reasoning about the identities of individuals. This is achieved by augmenting traditional appearance matching with contextual information about the environment and self identifying traits of certain actions. This framework also encodes qualitative confidence measures for the identity decisions it takes and finally, uses this information to reason about the occurrence of certain predefined activities in video.

A New Hardware Monitor Design to Measure Data Structure-Specific Cache Eviction Information - Buck, B. R; Hollingsworth, Jeffrey K (International Journal of High Performance Computing Applications, 2006)
In this paper, we propose a hardware performance monitor that provides support not only for measuring cache misses and the addresses associated with them, but also for determining what data is being evicted from the cache when a miss occurs. We describe how to use this hardware support to efficiently determine the cache behavior of application data structures at the source code level. We also present the results of a simulation-based study of this technique, in which we examined the overhead, perturbation of results, and usefulness of collecting this information.

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

Nuclear Envelope Dystrophies Show a Transcriptional Fingerprint Suggesting Disruption of Rb–MyoD Pathways in Muscle Regeneration - Bakay,Marina; Wang,Zuyi; Melcon,Gisela; Schiltz,Louis; Xuan,Jianhua; Zhao,Po; Sartorelli,Vittorio; Seo,Jinwook; Pegoraro,Elena; Angelini,Corrado; Shneiderman, Ben; Escolar,Diana; et al. (BrainBrain, 2006)
Mutations of lamin A/C (LMNA) cause a wide range of human disorders, including progeria, lipodystrophy, neuropathies and autosomal dominant Emery–Dreifuss muscular dystrophy (EDMD). EDMD is also caused by X-linked recessive loss-of-function mutations of emerin, another component of the inner nuclear lamina that directly interacts with LMNA. One model for disease pathogenesis of LMNA and emerin mutations is cell-specific perturbations of the mRNA transcriptome in terminally differentiated cells. To test this model, we studied 125 human muscle biopsies from 13 diagnostic groups (125 U133A, 125 U133B microarrays), including EDMD patients with LMNA and emerin mutations. A Visual and Statistical Data Analyzer (VISDA) algorithm was used to statistically model cluster hierarchy, resulting in a tree of phenotypic classifications. Validations of the diagnostic tree included permutations of U133A and U133B arrays, and use of two probe set algorithms (MAS5.0 and MBEI). This showed that the two nuclear envelope defects (EDMD LMNA, EDMD emerin) were highly related disorders and were also related to fascioscapulohumeral muscular dystrophy (FSHD). FSHD has recently been hypothesized to involve abnormal interactions of chromatin with the nuclear envelope. To identify disease-specific transcripts for EDMD, we applied a leave-one-out (LOO) cross-validation approach using LMNA patient muscle as a test data set, with reverse transcription–polymerase chain reaction (RT–PCR) validations in both LMNA and emerin patient muscle. A high proportion of top-ranked and validated transcripts were components of the same transcriptional regulatory pathway involving Rb1 and MyoD during muscle regeneration (CRI-1, CREBBP, Nap1L1, ECREBBP/p300), where each was specifically upregulated in EDMD. Using a muscle regeneration time series (27 time points) we develop a transcriptional model for downstream consequences of LMNA and emerin mutations. We propose that key interactions between the nuclear envelope and Rb and MyoD fail in EDMD at the point of myoblast exit from the cell cycle, leading to poorly coordinated phosphorylation and acetylation steps. Our data is consistent with mutations of nuclear lamina components leading to destabilization of the transcriptome in differentiated cells.
Keywords: EDMD = Emery–Dreifuss muscular dystrophy; emerin; Emery-Dreifuss muscular dystrophy; FSHD = fascioscapulohumeral muscular dystrophy; IDG = individual discriminatory genes; JDG = jointly discriminatory genes; lamin A/C; LGMD = limb-girdle muscular dystrophy; LOO = leave-one-out; RT–PCR = reverse transcription–polymerase chain reaction; VISDA = Visual and Statistical Data Analyzer; Skeletal muscle; wFC = weighted Fisher criterion

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

Observations about software development for high end computing - Carver, J. C; Hochstein, L. M; Kendall,R. P; Nakamura, T.; Zelkowitz, Marvin V; Basili, Victor R.; Post,D. E (CTWatch Quarterly, 2006)
In this paper, we have summarized our findings from a series of case studies conducted with ten ASC and MP Codes as a series of observations. Due to different environments in which each code is developed, some of the observations are consistent across code teams while others vary across code teams. Overall, we found high consistency among the ASC Codes and the MP Codes. Due to the different environments and foci of these projects, this result is both surprising and positive. In addition, despite the fact that a large majority of the developers on these teams have little or no formal training in software engineering, they have been able to make use of some basic software engineering principles. Further education and motivation could increase the use of these principles and further increase the quality of scientific and engineering software that has already demonstrated its value.Based on the positive results thus far, we have plans to conduct additional case studies to gather more data in support of or in contradiction to the observations presented in this paper. In future case studies, we will strive to investigate codes from additional domains, thereby allowing broader, more inclusive conclusions to be drawn.

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

Patterns of sequence conservation in presynaptic neural genes - Hadley,Dexter; Murphy,Tara; Valladares,Otto; Hannenhalli, Sridhar; Ungar,Lyle; Kim,Junhyong; Bućan,Maja (Genome Biology, 2006)
The neuronal synapse is a fundamental functional unit in the central nervous system of animals. Because synaptic function is evolutionarily conserved, we reasoned that functional sequences of genes and related genomic elements known to play important roles in neurotransmitter release would also be conserved.

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

PDR: A Performance Evaluation Method for Foreground-Background Segmentation Algorithms - Kim,K.; Chalidabhongse,T.H.; Harwood,D.; Davis, Larry S. (EURASIP Journal on Applied Signal Processing, 2006)
We introduce a performance evaluation methodologycalled Perturbation Detection Rate (PDR) analysis for measuring performance of foreground-background seg- mentation. It has some advantages over the commonly used Receiver Operation Characteristics (ROC) analy- sis. Specifically, it does not require foreground targets or knowledge of foreground distributions. It measures the sensitivity of a background subtraction algorithm in detecting possible low contrast targets against the background as a function of contrast, also depending on how well the model captures mixed (moving) back- ground events. We compare four background subtrac- tion algorithms using the methodology. The experimen- tal results show how PDR is used to measure perfor- mance with respect to detection sensitivity in interest- ing low contrast regions.

Practical dynamic software updating for C - Neamtiu,Iulian; Hicks, Michael W.; Stoyle,Gareth; Oriol,Manuel (SIGPLAN Not., 2006)
Software updates typically require stopping and restarting an application, but many systems cannot afford to halt service, or would prefer not to. Dynamic software updating (DSU) addresses this difficulty by permitting programs to be updated while they run. DSU is appealing compared to other approaches for on-line upgrades because it is quite general and requires no redundant hardware. The challenge is in making DSU practical: it should be flexible, and yet safe, efficient, and easy to use.In this paper, we present Ginseng, a DSU implementation for C that aims to meet this challenge. We compile programs specially so that they can be dynamically patched, and generate most of a dynamic patch automatically. Ginseng performs a series of analyses that when combined with some simple runtime support ensure that an update will not violate type-safety while guaranteeing that data is kept up-to-date. We have used Ginseng to construct and dynamically apply patches to three substantial open-source server programs---Very Secure FTP daemon, OpenSSH sshd daemon, and GNU Zebra. In total, we dynamically patched each program with three years' worth of releases. Though the programs changed substantially, the majority of updates were easy to generate. Performance experiments show that all patches could be applied in less than 5 ms, and that the overhead on application throughput due to updating support ranged from 0 to at most 32%.
Keywords: dynamic software updating; function indirection; loop extraction; type wrapping

The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema - Hajiaghayi, Mohammad T.; Jain,K. (Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, 2006)

A probabilistic analysis of trie-based sorting of large collections of line segments in spatial databases - Lindenbaum,M.; Samet, Hanan; Hjaltason,G. R (SIAM Journal on Computing, 2006)

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

Reconfigurable image registration on FPGA platforms - Sen,M.; Hemaraj,Y.; Bhattacharyya, Shuvra S.; Shekhar,R. (Biomedical Circuits and Systems Conference, 2006. BioCAS 2006. IEEE, 2006)

Recurring genomic breaks in independent lineages support genomic fragility - Hinsch,Hanno; Hannenhalli, Sridhar (BMC Evolutionary Biology, 2006)
Recent findings indicate that evolutionary breaks in the genome are not randomly distributed, and that certain regions, so-called fragile regions, are predisposed to breakages. Previous approaches to the study of genomic fragility have examined the distribution of breaks, as well as the coincidence of breaks with segmental duplications and repeats, within a single species. In contrast, we investigate whether this regional fragility is an inherent genomic characteristic and is thus conserved over multiple independent lineages.

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

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

Retroviral DNA Integration: Viral and Cellular Determinants of Target-Site Selection - Lewinski,Mary K; Yamashita,Masahiro; Emerman,Michael; Ciuffi,Angela; Marshall,Heather; Crawford,Gregory; Collins,Francis; Shinn,Paul; Leipzig,Jeremy; Hannenhalli, Sridhar; Berry,Charles C; Ecker,Joseph R; et al. (PLoS PathogPLoS Pathog, 2006)
Retroviruses differ in their preferences for sites for viral DNA integration in the chromosomes of infected cells. Human immunodeficiency virus (HIV) integrates preferentially within active transcription units, whereas murine leukemia virus (MLV) integrates preferentially near transcription start sites and CpG islands. We investigated the viral determinants of integration-site selection using HIV chimeras with MLV genes substituted for their HIV counterparts. We found that transferring the MLV integrase (IN) coding region into HIV (to make HIVmIN) caused the hybrid to integrate with a specificity close to that of MLV. Addition of MLV gag (to make HIVmGagmIN) further increased the similarity of target-site selection to that of MLV. A chimeric virus with MLV Gag only (HIVmGag) displayed targeting preferences different from that of both HIV and MLV, further implicating Gag proteins in targeting as well as IN. We also report a genome-wide analysis indicating that MLV, but not HIV, favors integration near DNase I–hypersensitive sites (i.e., +/− 1 kb), and that HIVmIN and HIVmGagmIN also favored integration near these features. These findings reveal that IN is the principal viral determinant of integration specificity; they also reveal a new role for Gag-derived proteins, and strengthen models for integration targeting based on tethering of viral IN proteins to host proteins.

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

A Scalable Multiuser Framework for Video Over OFDM Networks: Fairness and Efficiency - Su,Guan-Ming; Han,Zhu; M. Wu; Liu,K. J.R (Circuits and Systems for Video Technology, IEEE Transactions on, 2006)
In this paper, we propose a framework to transmit multiple scalable video programs over downlink multiuser orthogonal frequency division multiplex (OFDM) networks in real time. The framework explores the scalability of the video codec and multidimensional diversity of multiuser OFDM systems to achieve the optimal service objectives subject to constraints on delay and limited system resources. We consider two essential service objectives, namely, the fairness and efficiency. Fairness concerns the video quality deviation among users who subscribe the same quality of service, and efficiency relates to how to attain the highest overall video quality using the available system resources. We formulate the fairness problem as minimizing the maximal end-to-end distortion received among all users and the efficiency problem as minimizing total end-to-end distortion of all users. Fast suboptimal algorithms are proposed to solve the above two optimization problems. The simulation results demonstrated that the proposed fairness algorithm outperforms a time division multiple (TDM) algorithm by 0.5 3 dB in terms of the worst received video quality among all users. In addition, the proposed framework can achieve a desired tradeoff between fairness and efficiency. For achieving the same average video quality among all users, the proposed framework can provide fairer video quality with 1 1.8 dB lower PSNR deviation than a TDM algorithm
Keywords: algorithm; video; codec; video; coding; video; communication; deviation; downlink; deviation; OFDM; distortion; multidimensional; diversity; multiple; division; end-to-end; framework; time; Frequency; modulation; diversity; multiple; multiplex; multiuser; network; efficiency; networks; video; objectives; optimization; of; OFDM; orthogonal; over; problem; fairness; problem; maximal; problems; quality; programs; multiuser; PSNR; QUALITY; reception; image; resolution; optimisation; quality; scalable; service; service; scalable; service; video; systems; optimal; video

Seasonal Cholera Caused by Vibrio Cholerae Serogroups O1 and O139 in the Coastal Aquatic Environment of Bangladesh - Alam,Munirul; Hasan,Nur A.; Sadique,Abdus; Bhuiyan,N. A.; Ahmed,Kabir U.; Nusrin,Suraia; Nair,G. Balakrish; Siddique,A. K.; Sack,R. Bradley; Sack,David A.; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2006)
Since Vibrio cholerae O139 first appeared in 1992, both O1 El Tor and O139 have been recognized as the epidemic serogroups, although their geographic distribution, endemicity, and reservoir are not fully understood. To address this lack of information, a study of the epidemiology and ecology of V. cholerae O1 and O139 was carried out in two coastal areas, Bakerganj and Mathbaria, Bangladesh, where cholera occurs seasonally. The results of a biweekly clinical study (January 2004 to May 2005), employing culture methods, and of an ecological study (monthly in Bakerganj and biweekly in Mathbaria from March 2004 to May 2005), employing direct and enrichment culture, colony blot hybridization, and direct fluorescent-antibody methods, showed that cholera is endemic in both Bakerganj and Mathbaria and that V. cholerae O1, O139, and non-O1/non-O139 are autochthonous to the aquatic environment. Although V. cholerae O1 and O139 were isolated from both areas, most noteworthy was the isolation of V. cholerae O139 in March, July, and September 2004 in Mathbaria, where seasonal cholera was clinically linked only to V. cholerae O1. In Mathbaria, V. cholerae O139 emerged as the sole cause of a significant outbreak of cholera in March 2005. V. cholerae O1 reemerged clinically in April 2005 and established dominance over V. cholerae O139, continuing to cause cholera in Mathbaria. In conclusion, the epidemic potential and coastal aquatic reservoir for V. cholerae O139 have been demonstrated. Based on the results of this study, the coastal ecosystem of the Bay of Bengal is concluded to be a significant reservoir for the epidemic serogroups of V. cholerae.

Selection of Target Sites for Mobile DNA Integration in the Human Genome - Berry,Charles; Hannenhalli, Sridhar; Leipzig,Jeremy; Bushman,Frederic D. (PLoS Comput BiolPLoS Comput Biol, 2006)
DNA sequences from retroviruses, retrotransposons, DNA transposons, and parvoviruses can all become integrated into the human genome. Accumulation of such sequences accounts for at least 40% of our genome today. These integrating elements are also of interest as gene-delivery vectors for human gene therapy. Here we present a comprehensive bioinformatic analysis of integration targeting by HIV, MLV, ASLV, SFV, L1, SB, and AAV. We used a mathematical method which allowed annotation of each base pair in the human genome for its likelihood of hosting an integration event by each type of element, taking advantage of more than 200 types of genomic annotation. This bioinformatic resource documents a wealth of new associations between genomic features and integration targeting. The study also revealed that the length of genomic intervals analyzed strongly affected the conclusions drawn—thus, answering the question “What genomic features affect integration?” requires carefully specifying the length scale of interest.

Semi-Parametric Model-Based Clustering for DNA Microarray Data - Han,Bohyung; Davis, Larry S. (Pattern Recognition, 2006. ICPR 2006. 18th International Conference on, 2006)
Various clustering methods have been proposed for the analysis of gene expression data, but conventional clustering algorithms have several critical limitations; how to set parameters such as number of clusters, initial cluster centers, and so on. In this paper, we propose a semi-parametric model-based clustering algorithm in which the underlying model is a mixture of Gaussian. Each gene expression data builds a Gaussian kernel, and the uncertainty of microarray data is naturally integrated in the data representation. Our algorithm provides a principled method to automatically determine parameters - number of components in the mixture, mean, covariance, and weight of each Gaussian - by mean-shift procedure (Comaniciu and Meer, 1999) and curvature fitting. After the initialization, expectation maximization (EM) algorithm is employed for clustering to achieve maximum likelihood (ML). The performance of our algorithm is compared with standard EM algorithm using real data as well as synthetic data
Keywords: clustering; clustering; DNA; Gaussian; computing; genetics; pattern; data; Gaussian; data; maximum; DNA; Expression; fitting; data; kernel; Gaussian; likelihood; mean-shift; maximization; gene; Microarray; mixtures; curvature; model-based; procedure; semiparametric; processes; biology; representation; expectation

Severity and impact of computer user frustration: A comparison of student and workplace users - Lazar,Jonathan; Jones,Adam; Hackley,Mary; Shneiderman, Ben (Interacting with Computers, 2006)
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 exploratory study of 107 student computer users and 50 workplace computer users shows high levels of frustration and loss of 1/3–1/2 of time spent. This paper reports on the incident and individual factors that cause of frustration, and how 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, as are implications for researchers.
Keywords: Computer anxiety; Computer experience; Helpdesk; Training; User frustration; user interface design

Shared family calendars: Promoting symmetry and accessibility - Plaisant, Catherine; Clamage,Aaron; Hutchinson,Hilary Browne; Bederson, Benjamin B.; Druin, Allison (ACM Trans. Comput.-Hum. Interact., 2006)
We describe the design and use of a system facilitating the sharing of calendar information between remotely located, multi-generational family members. Most previous work in this area involves software enabling younger family members to monitor their parents. We have found, however, that older adults are equally if not more interested in the activities of younger family members. The major obstacle preventing them from participating in information sharing is the technology itself. Therefore, we developed a multi-layered interface approach that offers simple interaction to older users. In our system, users can choose to enter information into a computerized calendar or write it by hand on digital paper calendars. All of the information is automatically shared among everyone in the distributed family. By making the interface more accessible to older users, we promote symmetrical sharing of information among both older and younger family members. We present our participatory design process, describe the user interface, and report on an exploratory field study in three households of an extended family.
Keywords: calendar; digital paper; elderly; family technology; Home; layered interface; privacy; universal usability

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

System and method for locating a closest server in response to a client ... - Andrews,Matthew; Hofmann,Markus; Shepherd,Bruce; Srinivasan, Aravind; Winkler,Peter; Zane,Francis (2006)
A scalable system and method for locating a closest server in response to a client request via an interactive distribution network, such as the Internet, are provided. A closest content server is defined as having the least round trip time for responding to a client request. The system including a plurality of content servers; and a local server in communication with a plurality of clients, the local server acting as a proxy for communicating client requests from clients to a redirection server. Client network distance and load information is periodically collected at each content server in the network from clients communicating with each of the respective content servers. The redirection server periodically aggregates the network distance and load information from each content server to create client clusters from both current and previously aggregated network distance and load information. Each client cluster represents a division or partition of the total IP address space. Each...

Task taxonomy for graph visualization - Lee,Bongshin; Plaisant, Catherine; Parr,Cynthia Sims; Fekete,Jean-Daniel; Henry,Nathalie (Proceedings of the 2006 AVI workshop on BEyond time and errors: novel evaluation methods for information visualization, 2006)
Our goal is to define a list of tasks for graph visualization that has enough detail and specificity to be useful to: 1) designers who want to improve their system and 2) to evaluators who want to compare graph visualization systems. In this paper, we suggest a list of tasks we believe are commonly encountered while analyzing graph data. We define graph specific objects and demonstrate how all complex tasks could be seen as a series of low-level tasks performed on those objects. We believe that our taxonomy, associated with benchmark datasets and specific tasks, would help evaluators generalize results collected through a series of controlled experiments.
Keywords: Evaluation; graph visualization; task taxonomy

Top-down, bottom-up multivalued default reasoning for identity maintenance - Shet,Vinay D.; Harwood,David; Davis, Larry S. (Proceedings of the 4th ACM international workshop on Video surveillance and sensor networks, 2006)
Persistent tracking systems require the capacity to track individuals by maintaining identity across visibility gaps caused by occlusion events. In traditional computer vision systems, the flow of information is typically bottom-up. The low level image processing modules take video input, perform early vision tasks such as background subtraction and object detection,and pass this information to the high level reasoning module. This paper describes the architecture of a system that uses top-down information flow to perform identity maintenance across occlusion events. This system uses the high level reasoning module to provide control feedback to the low level image processing module to perform forensic analysis of archival video and actively acquire information required to arrive at identity decisions. This functionality is in addition to traditional bottom-up reasoning about identity, employing contextual cues and appearance matching, within the multivalued default logic framework proposed in [18]. This framework, in addition to bestowing upon the system the property of nonmonotonicity, also allows for it to qualitatively encode its confidence in the identity decisions it takes.
Keywords: default logic; identity maintenance; nonmonotonic reasoning; tracking; visual surveillance

Topology-based reasoning on non-manifold shapes - De Floriani, Leila; Hui,A.; Papaleo,L. (Proceedings of the 1st International Symposium on Shapes and Semantics, Matsushima, Japan, 2006)
Topological information is a promising resource to research in shape-understanding as it provides a high-level description of the characteristics of a shape, and such high-level description often has strong association with the semantics of an object. The Shape Acquisition and Processing (SAP) ontology has been designed to maintain useful information of a model. We propose here an extension to the SAP ontology, that addresses the non-manifold properties of a model. Useful information about the connectivity of an object can be obtained based on an analysis of its non- manifold properties, because the structure of a non-manifold object can be considered as a graph of manifold parts connected together at non-manifold joints. The manifold parts are often pieces that have strong semantic associations. In this work, we describe the type of non-manifold properties, the various types of connected components in a non-manifold object and their semantical significance. We address how the Euler’ characteristics of a non-manifold object can be found based on such information. All such information are extractable from a model using TopMesh, a tool that we have developed. In this work, we also describe the features of TopMesh, namely, all the topological properties it extracts.

Toward an enriched (and revitalized) sense of help: Summary of an ASIS&T 2005 panel session - Haas,Stephanie W; Denn,Sheila; Locke,David; Shneiderman, Ben; Brown,Laurie (Bulletin of the American Society for Information Science and Technology, 2006)

Toxigenic Vibrio Cholerae in the Aquatic Environment of Mathbaria, Bangladesh - Alam,Munirul; Sultana,Marzia; Nair,G. Balakrish; Sack,R. Bradley; Sack,David A.; Siddique,A. K.; Ali,Afsar; Huq,Anwar; Rita R Colwell (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2006)
Toxigenic Vibrio cholerae, rarely isolated from the aquatic environment between cholera epidemics, can be detected in what is now understood to be a dormant stage, i.e., viable but nonculturable when standard bacteriological methods are used. In the research reported here, biofilms have proved to be a source of culturable V. cholerae, even in nonepidemic periods. Biweekly environmental surveillance for V. cholerae was carried out in Mathbaria, an area of cholera endemicity adjacent to the Bay of Bengal, with the focus on V. cholerae O1 and O139 Bengal. A total of 297 samples of water, phytoplankton, and zooplankton were collected between March and December 2004, yielding eight V. cholerae O1 and four O139 Bengal isolates. A combination of culture methods, multiplex-PCR, and direct fluorescent antibody (DFA) counting revealed the Mathbaria aquatic environment to be a reservoir for V. cholerae O1 and O139 Bengal. DFA results showed significant clumping of the bacteria during the interepidemic period for cholera, and the fluorescent micrographs revealed large numbers of V. cholerae O1 in thin films of exopolysaccharides (biofilm). A similar clumping of V. cholerae O1 was also observed in samples collected from Matlab, Bangladesh, where cholera also is endemic. Thus, the results of the study provided in situ evidence for V. cholerae O1 and O139 in the aquatic environment, predominantly as viable but nonculturable cells and culturable cells in biofilm consortia. The biofilm community is concluded to be an additional reservoir of cholera bacteria in the aquatic environment between seasonal epidemics of cholera in Bangladesh.

Tracking Articulating Objects from Ground Vehicles using Mixtures of Mixtures - Abd-Almageed, Wael; Hussein,M.; Davis, Larry S. (Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on, 2006)
An algorithm for tracking articulating objects from moving camera platforms is presented. Mixtures of mixtures are used to model the appearance of the object and the background. The state of the object is tracked using a particle filter. Egomotion information are estimated and used to set the state variance of the particle filter. Results of tracking human objects from an unmanned ground vehicle are used to evaluate the tracking algorithm
Keywords: articulating; filter; unmanned; ground; information; mixtures; mixtures; particle; objects; of; operated; tracking; egomotion; vehicle; remotely; vehicles; robot; vision

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

Trusted declassification:: high-level policy for a security-typed language - Hicks,Boniface; King,Dave; McDaniel,Patrick; Hicks, Michael W. (Proceedings of the 2006 workshop on Programming languages and analysis for security, 2006)
Security-typed languages promise to be a powerful tool with which provably secure software applications may be developed. Programs written in these languages enforce a strong, global policy of noninterferencewhich ensures that high-security data will not be observable on low-security channels. Because noninterference is typically too strong a property, most programs use some form of declassification to selectively leak high security information, e.g. when performing a password check or data encryption. Unfortunately, such a declassification is often expressed as an operation within a given program, rather than as part of a global policy, making reasoning about the security implications of a policy more difficult.In this paper, we propose a simple idea we call trusted declassification in which special declassifier functions are specified as part of the global policy. In particular, individual principals declaratively specify which declassifiers they trust so that all information flows implied by the policy can be reasoned about in absence of a particular program. We formalize our approach for a Java-like language and prove a modified form of noninterference which we call noninterference modulo trusted methods. We have implemented our approach as an extension to Jif and provide some of our experience using it to build a secure e-mail client.
Keywords: noninterference modolo trusted methods; declassification; FJifP; information-flow control; Jif; security policy; security-typed languages; trusted declassification

Visualizing Graphs as Trees: Plant a Seed and Watch it Grow - Lee,Bongshin; Parr,Cynthia; Plaisant, Catherine; Bederson, Benjamin B. (Graph DrawingGraph Drawing, 2006)
TreePlus is a graph browsing technique based on a tree-style layout. It shows the missing graph structure using interaction techniques and enables users to start with a specific node and incrementally explore the local structure of graphs. We believe that it supports particularly well tasks that require rapid reading of labels.

Active Constrained Clustering by Examining Spectral Eigenvectors - Xu,Qianjun; desJardins, Marie; Wagstaff,Kiri (Discovery ScienceDiscovery Science, 2005)
This work focuses on the active selection of pairwise constraints for spectral clustering. We develop and analyze a technique for Active Constrained Clustering by Examining Spectral eigenvectorS (ACCESS) derived from a similarity matrix. The ACCESS method uses an analysis based on the theoretical properties of spectral decomposition to identify data items that are likely to be located on the boundaries of clusters, and for which providing constraints can resolve ambiguity in the cluster descriptions. Empirical results on three synthetic and five real data sets show that ACCESS significantly outperforms constrained spectral clustering using randomly selected constraints.

Adaptively-secure, non-interactive public-key encryption - Canetti,R.; Halevi,S.; Katz, Jonathan (Theory of Cryptography, 2005)
Adaptively-secure encryption schemes ensure secrecy even in the presence of an adversary who can corrupt parties in an adaptive manner based on public keys, ciphertexts, and secret data of already-corrupted parties. Ideally, an adaptively-secure encryption scheme should, like standard public-key encryption, allow arbitrarily-many parties to use a single encryption key to securely encrypt arbitrarily-many messages to a given receiver who maintains only a single short decryption key. However, it is known that these requirements are impossible to achieve: no non-interactive encryption scheme that supports encryption of an unbounded number of messages and uses a single, unchanging decryption key can be adaptively secure. Impossibility holds even if secure data erasure is possible.We show that this limitation can be overcome by updating the decryption key over time and making some mild assumptions about the frequency of communication between parties. Using this approach, we construct adaptively-secure, completely non-interactive encryption schemes supporting secure encryption of arbitrarily-many messages from arbitrarily-many senders. Our schemes additionally provide forward security and security against chosen-ciphertext attacks.

Algorithmic graph minor theory: Decomposition, approximation, and coloring - Demaine,E. D; Hajiaghayi, Mohammad T.; Kawarabayashi,K. (Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on, 2005)
At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.
Keywords: algorithmic graph minor theory; approximation algorithm; combinatorial polylogarithmic approximation; computational complexity; constant-factor approximation; graph algorithm; graph coloring; graph colouring; half-integral multicommodity flow; largest grid minor; maximization problem; minimization problem; polynomial-time algorithm; subexponential fixed-parameter algorithm; topological graph theory; treewidth

Are GSM phones THE solution for localization? - Varshavsky,A.; Chen,M.Y.; de Lara,E.; Jon Froehlich; Haehnel,D.; Hightower,J.; LaMarca,A.; Potter,F.; Sohn,T.; Tang,K.; others (Mobile Computing Systems and Applications, 2006. WMCSA'06. Proceedings. 7th IEEE Workshop on, 2005)

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

Automatic Mining of Source Code Repositories to Improve Bug Finding Techniques - Williams, Chadd C; Hollingsworth, Jeffrey K (IEEE Transactions on Software Engineering, 2005)
We describe a method to use the source code change history of a software project to drive and help to refine the search for bugs. Based on the data retrieved from the source code repository, we implement a static source code checker that searches for a commonly fixed bug and uses information automatically mined from the source code repository to refine its results. By applying our tool, we have identified a total of 178 warnings that are likely bugs in the Apache Web server source code and a total of 546 warnings that are likely bugs in Wine, an open-source implementation of the Windows API. We show that our technique is more effective than the same static analysis that does not use historical data from the source code repository.
Keywords: configuration control; debugging aids.; index terms- testing tools; version control

Background updating for visual surveillance - Kim,K.; Harwood,D.; Davis, Larry S. (Advances in Visual Computing, 2005)
Scene changes such as moved objects, parked vehicles, or opened/closed doors need to be carefully handled so that interesting foreground targets can be detected along with the short-term background layers created by those changes. A simple layered modeling technique is embedded into a codebook-based background subtraction algorithm to update a background model. In addition, important issues related to background updating for visual surveillance are discussed. Experimental results on surveillance examples, such as unloaded packages and unattended objects, are presented by showing those objects as short-term background layers.

Bayesian filtering and integral image for visual tracking - Han,B.; Yang,C.; Duraiswami, Ramani; Davis, Larry S. (Proceedings of the Worshop on Image Analysis for Multimedia Interactive Services (WIAMIS'05), 2005)
This paper describes contributions to two problems related tovisual tracking: control model design and observation process design. We describe the use of kernel-based Bayesian filtering for the tracking control procedure, and feature-based tracking to improve the observation process of tracking. In the kernel- based Bayesian filtering framework, the analytical represen- tation of density functions by density interpolation and density approximation for the likelihood and the posterior contributes to efficient sampling. Feature-based tracking combines rec- tangular features with edge oriented histogram so that the combined features are robust to illumination changes, partial occlusion, and clutter while capturing the spatial information of the target. The use of integral image allows the features to be efficiently evaluated. The effectiveness of both algorithms are demonstrated by object tracking results on real videos.

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

Bounds on the efficiency of black-box commitment schemes - Horvitz,O.; Katz, Jonathan (Automata, Languages and Programming, 2005)
Constructions of cryptographic primitives based on general assumptions (e.g., the existence of one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of perfectly-binding schemes. We present the bounds in an extension of the Impagliazzo-Rudich model; that is, we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a commitment scheme could be constructed “from scratch”). Our analysis is the first in the area to pertain directly to an information-theoretic component of the security notion.

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

Building a Coherent Data Pipeline in Microarray Data Analyses: Optimization of Signal/Noise Ratios Using an Interactive Visualization Tool and a Novel Noise Filtering Method (2003) - Seo,Jinwook; Bakay,Marina; Chen,Yi-Wen; Hilmer,Sara; Shneiderman, Ben; Hoffman,Eric P (Institute for Systems Research Technical Reports, 2005)
Motivation: Sources of uncontrolled noise strongly influence data analysis in microarray studies, yet signal/noise ratios are rarely considered in microarray data analyses. We hypothesized that different research projects would have different sources and levels of confounding noise, and built an interactive visual analysis tool to test and define parameters in Affymetrix analyses that optimize the ratio of signal (desired biological variable) versus noise (confounding uncontrolled variables). Results: Five probe set algorithms were studied with and without statistical weighting of probe sets using Microarray Suite (MAS) 5.0 probe set detection p values. The signal/noise optimization method was tested in two large novel microarray datasets with different levels of confounding noise; a 105 sample U133A human muscle biopsy data set (11 groups) (extensive noise), and a 40 sample U74A inbred mouse lung data set (8 groups) (little noise). Success was measured using F-measure value of success of unsupervised clustering into appropriate biological groups (signal). We show that both probe set signal algorithm and probe set detection p-value weighting have a strong effect on signal/noise ratios, and that the different methods performed quite differently in the two data sets. Among the signal algorithms tested, dChip difference model with p-value weighting was the most consistent at maximizing the effect of the target biological variables on data interpretation of the two data sets. Availability: The Hierarchical Clustering Explorer 2.0 is [url=http://www.cs.umd.edu/hcil/hce/]available[/url] online and the improved version of the Hierarchical Clustering Explorer 2.0 with p-value weighting and Fmeasure is available upon request to the first author. Murine arrays (40 samples) are publicly available at the [url=http://microarray.cnmcresearch.org/pgadatatable.asp]PEPR resource.[/url] (Chen et al., 2004).
Keywords: Technical Report

Building efficient and effective multimedia fingerprints via joint coding and embedding - He,Shan; M. Wu (Proceedings of the 7th workshop on Multimedia and security, 2005)
Digital fingerprinting protects multimedia content from illegal redistribution by uniquely marking every copy of the content distributed to each user. One major category of collusion-resistant fingerprinting employs an explicit step of coding. Most existing works on coded fingerprinting mainly focus on the code-level issues and treat the embedding issues through abstract assumptions without examining the overall performance. In this paper, we jointly consider the coding and embedding issues for coded fingerprinting systems and examine their performance in terms of collusion resistance, detection computational complexity, and distribution efficiency. Our studies show that coded fingerprinting has efficient detection but rather low collusion resistance. Taking advantage of joint coding and embedding, we propose two new techniques, namely, a Permuted Subsegment Embedding technique and a Group-based Joint Coding and Embedding (GRACE) technique, to improve the collusion resistance of coded fingerprinting while maintaining its efficient detection. Experimental results show that the number of colluders that the proposed methods can resist is more than three times as many as that of the conventional coded fingerprinting approaches.
Keywords: collusion resistance; error correcting code; multimedia fingerprinting

Combining self-reported and automatic data to improve programming effort measurement - Hochstein, Lorin; Basili, Victor R.; Zelkowitz, Marvin V; Hollingsworth, Jeffrey K; Carver, Jeff (Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, 2005)
Measuring effort accurately and consistently across subjects in a programming experiment can be a surprisingly difficult task. In particular, measures based on self-reported data may differ significantly from measures based on data which is recorded automatically from a subject's computing environment. Since self-reports can be unreliable, and not all activities can be captured automatically, a complete measure of programming effort should incorporate both classes of data. In this paper, we show how self-reported and automatic effort can be combined to perform validation and to measure total programming effort.
Keywords: effort; experimentation; human factors; manual approaches; measurement; process metrics; verification