Model-based testing of community-driven open-source GUI applications - Xie,Q.; Memon, Atif M. (Software Maintenance, 2006. ICSM'06. 22nd IEEE International Conference on, 2006)
Although the World-Wide-Web (WWW) has significantly enhanced open-source software (OSS) development, it has also created new challenges for quality assurance (QA), especially for OSS with a graphical-user interface (GUI) front-end. Distributed communities of developers, connected by the WWW, work concurrently on loosely-coupled parts of the OSS and the corresponding GUI code. Due to the unprecedented code churn rates enabled by the WWW, developers may not have time to determine whether their recent modifications have caused integration problems with the overall OSS; these problems can often be detected via GUI integration testing. However, the resource-intensive nature of GUI testing prevents the application of existing automated QA techniques used during conventional OSS evolution. In this paper we develop new process support for three nested techniques that leverage developer communities interconnected by the WWW to automate model-based testing of evolving GUI-based OSS. The "innermost" technique (crash testing) operates on each code check-in of the GUI software and performs a quick and fully automatic integration test. The second technique {smoke testing) operates on each day's GUI build and performs functional "reference testing" of the newly integrated version of the GUI. The third (outermost) technique (comprehensive GUI testing) conducts detailed integration testing of a major GUI release. An empirical study involving four popular OSS shows that (1) the overall approach is useful to detect severe faults in GUI-based OSS and (2) the nesting paradigm helps to target feedback and makes effective use of the WWW by implicitly distributing QA

Multiuser cross-layer resource allocation for video transmission over wireless networks - Su,Guan-Ming; Man,Zhu; M. Wu; Liu,K. J.R (Network, IEEE, 2006)
With the advancement of video-compression technology and the wide deployment of wireless networks, there is an increasing demand for wireless video communication services, and many design challenges remain to be overcome. In this article, we discuss how to dynamically allocate resources according to the changing environments and requirements, so as to improve the overall system performance and ensure individual quality of service (QoS). Specifically, we consider two aspects with regard to design issues: cross-layer design, which jointly optimizes resource utilization from the physical layer to the application layer, and multiuser diversity, which explores source and channel heterogeneity for different users. We study how to efficiently transmit multiple video streams, encoded by current and future video codecs, over resource-limited wireless networks such as 3G/4G cellular system and future wireless local/metropolitan area networks (WLANs/WMANs)
Keywords: 3G; allocation; multiuser; allocation; video; cellular; channels; quality; codecs; video; coding; video; communication; 4G; communication; data; compression; diversity; cross-layer; diversity; physical; layer; multiple; layer; quality; mobile; networks; 3G; of; reception; multiuser; resource; service; resource; service; video; streaming; streams; multiuser; system; 4G; system; QoS; application; technology; wireless; transmission; video-compression; video

Multi-View Learning and Link Farm Discovery - Scheffer,T.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
The first part of this abstract focuses on estimation of mixture models for problems in which multiple views of the instances are available. Examples of this setting include clustering web pages or research papers that have intrinsic (text) and extrinsic (references) attributes. Mixture model estimation is a key problem for both semi-supervised and unsupervised learning. An appropriate optimization criterion quantifies the likelihood and the consensus among models in the individual views; maximizing this consensus minimizes a bound on the risk of assigning an instance to an incorrect mixture component. An EM algorithm maximizes this criterion. The second part of this abstract focuses on the problem of identifying link spam. Search engine optimizers inflate the page rank of a target site by spinning an artificial web for the sole purpose of providing inbound links to the target. Discriminating natural from artificial web sites is a difficult multi-view problem.

Multi-view Reconstruction of Static and Dynamic Scenes - Agrawal,M.; Mittal,A.; Davis, Larry S. (Handbook of Mathematical Models in Computer Vision, 2006)
We explore the reconstruction of a three-dimensional scene from multiple images captured from far away viewpoints (wide-baseline camera arrangement). Such an arrangement is required for complex scenes where the visibility flora any one viewpoint is not sufficient to adequately reconstruct the entire scene. Also, such an arrangement reduces the error in triangulation of the features, thereby improving the accuracy of reconstruction. Our emphasis is on algorithms that recover a volumetric model of the scene from calibrated cameras by explicitly modeling and detecting occlusions. We present a brief overview of the state of the art in such methods for multi-view reconstruction. In particular, algorithms based on a probabilistic framework have become quite popular and produce very accurate models. Several such probabilistic volume reconstruction methods will be described. For the dynamic parts of the scene, where an online reconstruction is needed, simpler methods are required. An important case of such scenes is that of walking people in a surveillance scenario. For this case, we present fast online algorithms that recover approximate shape and appearance models and 3D trajectories of people as they walk in the scene. Finally, we address the problem of optimal placement of cameras in order to acquire the best possible image data for the reconstruction of a given scene according to the particular task specification.

New DNS results of shockwave/turbulent boundary layer interaction - Wu,M.; Martin, M.P (3rd AIAA Flow Control Conference, 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

Numerical Analysis of Plasmon Resonances Based on Fast Multipole Method - Zhang,Zhenyu; Mayergoyz, Issak D; Gumerov, Nail A.; Duraiswami, Ramani (Electromagnetic Field Computation, 2006 12th Biennial IEEE Conference on, 2006)
A novel technique for the numerical analysis of plasmon resonances by using fast multipole method (FMM) is presented. This approach is based on the solution of eigenvalue problem for boundary integral equations, which can be naturally implemented by using the fast multipole method. Numerical examples that highlight the efficiency of the fast multipole implementation are reported
Keywords: analysis; plasmon; and; boundary; eigenfunctions; plasmons; equations; eigenvalue; equations; eigenvalues; integral; method; numerical; multipole; problem; fast; resonances; boundary

Numerical analysis of plasmon resonances in nanoparticles - Mayergoyz, Issak D; Zhang,Zhenyu (Magnetics, IEEE Transactions on, 2006)
Plasmon (electrostatic) resonances in nanoparticles are treated as an eigenvalue problem for a specific boundary integral equation. This leads to direct calculation of resonance values of permittivity and resonance frequency. The numerical technique is illustrated by examples of calculation of resonance frequencies for three-dimensional nanoparticles
Keywords: 3D; analysis; plasmon; and; boundary; eigenfunctions; electrostatics; nanoparticles; permittivity; surface; equation; boundary; equations; eigenvalues; integral; nanoparticles; eigenvalue; plasmon; problem; numerical; resonance; resonances; specific

A parallel implicit method for the direct numerical simulation of wall-bounded compressible turbulence - Martin, M.P; Candler,Graham V. (Journal of Computational Physics, 2006)
A new second-order accurate implicit temporal numerical scheme for the direct numerical simulation of turbulent flows is presented. The formulation of the implicit method and the corresponding tunable parameters are introduced. The numerical simulation results are compared with the results given by explicit Runge–Kutta schemes, theoretical results, and published experimental and numerical data. An assessment of the accuracy and performance of the method to simulate turbulent flows is made for temporally decaying isotropic turbulence and subsonic and supersonic turbulent boundary layers. Whereas no significant advantage over typical explicit time integration methods are found for the incompressible flows; it is shown that the implicit scheme yields significant reduction in computer cost while assuring time-accurate solutions for compressible turbulence simulations.
Keywords: direct numerical simulation; Implicit time integration; Wall-bounded turbulent flow

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.

Partially overlapped channels not considered harmful - Mishra,A.; Shrivastava,V.; Banerjee,S.; Arbaugh, William A. (Proceedings of the joint international conference on Measurement and modeling of computer systems, 2006)

Participatory design with proxies: developing a desktop-PDA system to support people with aphasia - Jordan Boyd-Graber; Nikolova,Sonya S.; Moffatt,Karyn A.; Kin,Kenrick C.; Lee,Joshua Y.; Mackey,Lester W.; Tremaine,Marilyn M.; Klawe,Maria M. (Proceedings of the SIGCHI conference on Human Factors in computing systems, 2006)
In this paper, we describe the design and preliminary evaluation of a hybrid desktop-handheld system developed to support individuals with aphasia, a disorder which impairs the ability to speak, read, write, or understand language. The system allows its users to develop speech communication through images and sound on a desktop computer and download this speech to a mobile device that can then support communication outside the home. Using a desktop computer for input addresses some of this population's difficulties interacting with handheld devices, while the mobile device addresses stigma and portability issues. A modified participatory design approach was used in which proxies, that is, speech-language pathologists who work with aphasic individuals, assumed the role normally filled by users. This was done because of the difficulties in communicating with the target population and the high variability in aphasic disorders. In addition, the paper presents a case study of the proxy-use participatory design process that illustrates how different interview techniques resulted in different user feedback.
Keywords: aphasia; assistive technology; multi-modal interfaces; participatory design

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.

Probabilistic, Logical and Relational Learning-Towards a Synthesis - De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H; Lloyd,J. W; Sears,T. D; Milch,B.; Marthi,B.; Russell,S.; Sontag,D. (Dagstuhl Seminar Proceedings, 2006)

Provable algorithms for parallel generalized sweep scheduling - Anil Kumar,V. S; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind; Zust,S. (Journal of Parallel and Distributed Computing, 2006)

Proximity problems on line segments spanned by points - Daescu,Ovidiu; Luo,Jun; Mount, Dave (Computational Geometry, 2006)
Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O ( n log n ) time, O ( n ) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S ∖ { q } in optimal O ( n log n ) time and O ( n ) space. Finally, we give an O ( n log n ) time, O ( n ) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O ( n log n + k ) time and O ( n + k ) space.
Keywords: Closest; Farthest; k closest lines; Minimum (maximum) area triangle; Proximity problem

Query Rewriting in the Semantic Web7 - Vidal,Maria Esther; Raschid, Louiqa; Marquez,Natalia; Cardenas,Marelis; Yao Wu (Data Engineering Workshops, 22nd International Conference on, 2006)
The widespread explosion of Web accessible resources has lead to a new challenge of locating all relevant resources and identifying the best ones to answer a query. This challenge has to address the difficult task of ranking the resources based on user needs, as well as the more expensive computational task of determining all the solutions to answer a query. In this paper, we define a Top K problem for query rewriting on the Semantic Web. We first introduce a three level data model composed of the ontology level, the physical level of the physical resources, and the data level composed of the entries in the different resources. We present a query language for Top K navigational queries over ontology concepts. We then sketch the outline of an efficient search algorithm to compute an approximation of the Top K rewriting options to produce source paths among the physical resources. We briefly discuss the results of an experimental study

Ranking search results in P2P systems - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (Technical Report, CR-TR-4779, Department of Computer Science, University of Maryland, 2006)
P2P deployments are a natural infrastructure for buildingdistributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well- known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results ob- tained using distributed ranking is comparable to a cen- tralized implementation.

Ranking search results in peer-to-peer systems - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (Technical Reports from UMIACS, 2006)
P2P deployments are a natural infrastructure for building distributed search networks. Proposed systems support locating and retrieving all results, but lack the information necessary to rank them. Users, however, are primarily interested in the most relevant, and not all possible results. Using random sampling, we extend a class of well-known information retrieval ranking algorithms such that they can be applied in this distributed setting. We analyze the overhead of our approach, and quantify exactly how our system scales with increasing number of documents, system size, document to node mapping (uniform versus non-uniform), and types of queries (rare versus popular terms). Our analysis and simulations show that a) these extensions are efficient, and can scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to a centralized implementation.

Resource Discovery Techniques in Distributed Desktop Grid Environments - Kim,Jik-Soo; Nam,Beomseok; Keleher,Peter; Marsh,Michael; Bhattacharjee, Bobby; Sussman, Alan (Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, 2006)
Desktop grids use opportunistic sharing to exploit large collections of personal computers and workstations across the Internet, achieving tremendous computing power at low cost. Traditional desktop grid systems are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. In this paper, we propose a decentralized, robust, highly available, and scalable infrastructure to match incoming jobs to available resources. Through a comparative analysis on the experimental results obtained via simulation of three different types of matchmaking algorithms under different workload scenarios, we show the trade-offs between effcient matchmaking and good load balancing in a fully decentralized, heterogeneous computational environment.

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.

Ring signatures: Stronger definitions, and constructions without random oracles - Bender,A.; Katz, Jonathan; Morselli,R. (Theory of Cryptography, 2006)
Ring signatures, first introduced by Rivest, Shamir, and Tauman, enable a user to sign a message so that a ring of possible signers (of which the user is a member) is identified, without revealing exactly which member of that ring actually generated the signature. In contrast to group signatures, ring signatures are completely “ad-hoc” and do not require any central authority or coordination among the various users (indeed, users do not even need to be aware of each other); furthermore, ring signature schemes grant users fine-grained control over the level of anonymity associated with any particular signature.This paper has two main areas of focus. First, we examine previous definitions of security for ring signature schemes and suggest that most of these prior definitions are too weak, in the sense that they do not take into account certain realistic attacks. We propose new definitions of anonymity and unforgeability which address these threats, and then give separation results proving that our new notions are strictly stronger than previous ones. Next, we show two constructions of ring signature schemes in the standard model: one based on generic assumptions which satisfies our strongest definitions of security, and a second, more efficient scheme achieving weaker security guarantees and more limited functionality. These are the first constructions of ring signature schemes that do not rely on random oracles or ideal ciphers.

Robust and secure image hashing - Swaminathan,A.; Mao,Yinian; M. Wu (Information Forensics and Security, IEEE Transactions on, 2006)
Image hash functions find extensive applications in content authentication, database search, and watermarking. This paper develops a novel algorithm for generating an image hash based on Fourier transform features and controlled randomization. We formulate the robustness of image hashing as a hypothesis testing problem and evaluate the performance under various image processing operations. We show that the proposed hash function is resilient to content-preserving modifications, such as moderate geometric and filtering distortions. We introduce a general framework to study and evaluate the security of image hashing systems. Under this new framework, we model the hash values as random variables and quantify its uncertainty in terms of differential entropy. Using this security framework, we analyze the security of the proposed schemes and several existing representative methods for image hashing. We then examine the security versus robustness tradeoff and show that the proposed hashing methods can provide excellent security and robustness.
Keywords: content-preserving; cryptography; differential; distortions; entropy; Filtering; Fourier; functions; hash; hashing; image; modifications; processing; secure; theory; transform; transforms

Routing for data delivery in dynamic networks - Mundur, Padma; Lee,S.; Seligman,M. (Proceedings of the IEEE MILCOM, 2006)

Routing in Delay Tolerant Networks Using Storage Domains - Mundur, Padma; Lee,Sookyoung; Seligman,Matthew (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2006)
In this paper, we present a routing algorithm for a class ofdynamic networks called the Delay Tolerant Networks (DTNs). The proposed algorithm takes into account the quintessential DTN characteristic namely, intermittent link connectivity. We modify the breadth first search (BFS) algorithm to take into account link state changes and find the quickest route between source and destination nodes. We adopt a message drop policy at intermediate nodes to incorporate storage constraint. We also introduce the idea of time-varying storage domains where all nodes connected for a length of time act as a single storage unit by sharing the aggregated storage capacity of the nodes. We evaluate the routing algorithm with and without storage domain in an extensive simulation. We analyze the performance using metrics such as delivery ratio, incomplete transfers with no routes and dropped messages. The DTN topology dynamics are analyzed by varying: number of nodes generating traffic, link probability, link availability through combinations of downtime/uptime values, storage per node, message size, and traffic. The delay performance of the proposed algorithms is conceptually the same as flooding-based algorithms but without the penalty of multiple copies. More significantly, we show that the Quickest Storage Domain (Quickest SD) algorithm distributes the storage demand across many nodes in the network topology, enabling balanced load and higher network utilization. In fact, we show that for the same level of performance, we can actually cut the storage requirement in half using the Quickest SD algorithm.
Keywords: Technical Report

Routing in intermittent network topologies - Mundur, Padma; Lee,Sookyoung; Seligman,Matthew (Proceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, 2006)
Keywords: delay tolerant network (DTN); performance evaluation; routing algorithms

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

Scalar Preisach Models of Hysteresis - Mayergoyz, Issak D (The Science of Hysteresis: Mathematical modeling and applications, 2006)

The Science of Hysteresis: Mathematical modeling and applications - Bertotti,Giorgio; Mayergoyz, Issak D (Academic Press, 2006)
Keywords: Business & Economics / Economics / Microeconomics; Hysteresis; Magnetism; Science / Physics / Magnetism

Security Issues in Cooperative Communications: Tracing Adversarial Relays - Mao,Yinian; M. Wu (Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006)
Cooperative communication system explores a new dimension of diversity in wireless communications to combat unfriendly wireless environment through strategic relays. While this emerging technology is promising in improving communication quality, some security problems inherent to cooperative relay also arise. In this paper we investigate the security issues in cooperative communications that consist of multiple relay nodes using decode-and-forward strategy. In particular, we consider the situation where one of the relay nodes is adversarial and tries to corrupt the communications by sending garbled signals. We show that the conventional physical-layer signal detection will not be effective in such a scenario, and the application-layer cryptography alone is not sufficient to identify the adversarial relay. To combat adversarial relay, we propose a cross-layer scheme that uses pseudo-random tracing symbols, with an adaptive signal detection rule at the physical layer, and direct sequence spread spectrum symbol construction at the application layer for tracing and identifying adversarial relay. Our experimental simulations show that the proposed tracing scheme is effective and efficient
Keywords: adaptive; Communication; communications; adaptive; construction; multiple; detection; adversarial; detection; decoding; radiocommunication; telecommunication; issues; strategic; nodes; pseudo-random; relay; relay; decode-and-forward; relays; cooperative; relays; wireless; security; sequence; signal; spectrum; spread; strategy; direct; symbol; symbols; security; system; cooperative; tracing

Septaplex PCR assay for rapid identification of Vibrio cholerae including detection of virulence and int SXT genes - Mantri,Chinmay K.; Mohapatra,Saswat S.; Ramamurthy,Thandavarayan; Ghosh,Raikamal; Rita R Colwell; Singh,Durg V. (FEMS Microbiology Letters, 2006)
In this study, we describe a septaplex PCR assay for rapid identification of Vibrio cholerae including detection of the virulence and intsxt genes. Conditions were optimized to amplify fragments of ISRrRNA (encoding for 16S–23S rRNA gene, Intergenic spacer regions), O1rfb (O1 serogroup specific rfb), O139rfb (O139 serogroup specific rfb), ctxA (cholera toxin subunit A), tcpA (toxin coregulated pilus), and intsxt (sxt integron) simultaneously in a single PCR. The septaplex PCR was evaluated using 211 strains of V. cholerae and six water samples for in situ testing. PCR results were correlated with genotype data obtained by individual PCR and slot-blot assays. The one-step PCR described here can be used to identify V. cholerae accurately and rapidly. Also, the virulence and intsxt genes can be simultaneously detected, providing a useful method for monitoring pathogenic, intsxt-positive and nonpathogenic, intsxt-negative V. cholerae serogroups both in the environment and clinical settings.
Keywords: DETECTION; intsxt; septaplex PCR; Vibrio cholerae; virulence

A structural approach to latency prediction - Madhyastha,Harsha V.; Anderson,Thomas; Krishnamurthy,Arvind; Spring, Neil; Venkataramani,Arun (Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, 2006)
Several models have been recently proposed for predicting the latency of end to end Internet paths. These models treat the Internet as a black-box, ignoring its internal structure. While these models are simple, they can often fail systematically; for example, the most widely used models use metric embeddings that predict no benefit to detour routes even though half of all Internet routes can benefit from detours.In this paper, we adopt a structural approach that predicts path latency based on measurements of the Internet's routing topology, PoP connectivity, and routing policy. We find that our approach outperforms Vivaldi, the most widely used black-box model. Furthermore, unlike metric embeddings, our approach successfully predicts 65% of detour routes in the Internet. The number of measurements used in our approach is comparable with that required by black box techniques, but using traceroutes instead of pings.
Keywords: internet topology; latency prediction; route measurements

Structure of social contact networks and their impact on epidemics - Eubank,S.; Kumar,V. S.A; Marathe,M. V; Srinivasan, Aravind; Wang,N. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 2006)
Traditional epidemiological research has focused on rate-based differential-equation models on completely mixing populations. In this paper, we outline an approach based on a combination of net- work theory and discrete-event simulations to study epidemics in large urban areas. We survey some of our results published in Nature (2004) and the Proc. ACM-SIAM Symposium on Discrete Algorithms (2004), and present some new results on: (i) mathematical properties of large social contact networks, as well as (ii) simulation-based dynamic anal- ysis of disease-spread in such networks. We identify a number of new measures that are significant for understanding epidemics and for devel- oping new strategies in policy planning. We also perform a very detailed structural analysis of the social contact networks produced by TRAN- SIMS, a simulator for detailed transportation/traffic studies, and study two random graph models to generate realistic social networks: Chung- Lu’s model and the configuration model. We also develop combinatorial formulations and approximation algorithms for quarantining, vaccina- tion and sensor placement, as aids to decision-making.

A study of translation edit rate with targeted human annotation - Snover,M.; Dorr, Bonnie J; Schwartz,R.; Micciulla,L.; Makhoul,J. (Proceedings of Association for Machine Translation in the Americas, 2006)
We examine a new, intuitive measurefor evaluating machine-translation output that avoids the knowledge intensiveness of more meaning-based approaches, and the labor-intensiveness of human judg- ments. Translation Edit Rate (TER) mea- sures the amount of editing that a hu- man would have to perform to change a system output so it exactly matches a reference translation. We show that the single-reference variant of TER correlates as well with human judgments of MT quality as the four-reference variant of BLEU. We also define a human-targeted TER (or HTER) and show that it yields higher correlations with human judgments than BLEU—even when BLEU is given human-targeted references. Our results in- dicate that HTER correlates with human judgments better than HMETEOR and that the four-reference variants of TER and HTER correlate with human judg- ments as well as—or better than—a sec- ond human judgment does.

Studying the Characteristics of a "Good" GUI Test Suite - Xie,Qing; Memon, Atif M. (Software Reliability Engineering, 2006. ISSRE '06. 17th International Symposium on, 2006)
The widespread deployment of graphical-user interfaces (GUIs) has increased the overall complexity of testing. A GUI test designer needs to perform the daunting task of adequately testing the GUI, which typically has very large input interaction spaces, while considering tradeoffs between GUI test suite characteristics such as the number of test cases (each modeled as a sequence of events), their lengths, and the event composition of each test case. There are no published empirical studies on GUI testing that a GUI test designer may reference to make decisions about these characteristics. Consequently, in practice, very few GUI testers know how to design their test suites. This paper takes the first step towards assisting in GUI test design by presenting an empirical study that evaluates the effect of these characteristics on testing cost and fault detection effectiveness. The results show that two factors significantly effect the fault-detection effectiveness of a test suite: (1) the diversity of states in which an event executes and (2) the event coverage of the suite. Test designers need to improve the diversity of states in which each event executes by developing a large number of short test cases to detect the majority of "shallow" faults, which are artifacts of modern GUI design. Additional resources should be used to develop a small number of long test cases to detect a small number of "deep" faults
Keywords: Fault detection; Fault diagnosis; graphical user interface testing; Graphical user interfaces; program debugging; program testing

On Synchronization of Weighted Essentially Non-Oscillatory Methods - Taylor,E. M; Martin, M.P (36th AIAA Fluid Dynamics Conference and Exhibit, 2006)
Weighted essentially non-oscillatory (WENO) methods have been developed to simul-taneously provide robust shock-capturing in compressible fluid flow and avoid excessive damping of fine-scale flow features such as turbulence. Under certain conditions in com- pressible turbulence, however, numerical dissipation remains unacceptably high even after optimization of the linear component that dominates in smooth regions. We demonstrate that a significant nonlinear source of dissipation error is due to a WENO implementa- tion defect that we call the “synchronization deficiency,” and we develop and evaluate a preliminary technique to mitigate its effects. Direct numerical simulations (DNS) include one-dimensional test cases and three-dimensional compressible isotropic turbulence. Al- though we find the current formulation of our mitigation technique to be quite successful for the one-dimensional problems, its efficacy is more modest in the turbulence simulations, and its cost-to-benefit ratio is uncomfortably high. We believe, however, that with further work it will be possible to alleviate these drawbacks.

SYSTEM AND METHOD FOR FAST ILLUMINATION-INVARIANT BACKGROUND SUBTRACTION USING TWO VIEWS - Davis, Larry S.; Lim,S.N.; Mittal,A. (2006)
A method for eliminating errors in foreground object detection in digitized images comprises providing (1101) a reference camera and a secondary camera, vertically aligning each said camera with a baseline that is approximately perpendicular to a ground plane, wherein said reference camera is placed lower than said secondary camera, selecting (1104) a foreground pixel in a reference view of a first point in a foreground object, finding (1105) a conjugate pixel of the foreground pixel in a secondary view, using (1106) the foreground and conjugate pixels to determine an image base pixel of a base point in the reference view, wherein said base point is a point on the ground plane below the first point, and using (1107) the foreground and image base pixels to find a location where the ground plane is first visible.

Task-Driven Video Collection - Lim,Ser-Nam; Mittal,Anuarg; Davis, Larry S. (Technical Reports from UMIACS, 2006)
Vision systems are increasingly being deployed to perform complexsurveillance tasks. While improved algorithms are being developed to perform these tasks, it is also important that data suitable for these algorithms be acquired - a non-trivial task in a dynamic and crowded scene viewed by multiple PTZ cameras. In this paper, we describe a multi-camera system that collects images and videos of moving objects in such scenes, subject to task constraints. The system constructs "task visibility intervals" that contain information about what can be sensed in future time intervals. Constructing these intervals requires prediction of future object motion and consideration of several factors such as object occlusion and camera control parameters. Using a plane-sweep algorithm, these atomic intervals can be combined to form multi-task intervals, during which a single camera can collect videos suitable for multiple tasks simultaneously. Although cameras can then be scheduled based on the constructed intervals, finding an optimal schedule is a typical NP-hard problem. Due to this, and the lack of exact future information in a dynamic environment, we propose several methods for fast camera scheduling that yield solutions within a small constant factor of optimal. Experimental results illustrate system capabilities for both real and more complicated simulated scenarios.
Keywords: Technical Report

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

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

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

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

The turbulence structure of shockwave and boundary layer interaction in a compression corner - Martin, M.P; Smits,A.; Wu,M.; Ringuette,M. (44th AIAA Aerospace Meeting and Exhibit, 2006)
Shockwave and turbulent boundary layer interactions (STBLI) result in intense localizedheating rates and pressure loads, making them extremely important flow features that must be identified for engineering design. The absence of detailed and complete experimental and numerical data at the same flow and boundary conditions is one of the major stumbling blocks in the development of accurate turbulence models for the prediction of STBLI. We use a set of direct numerical simulation data (Wu & Martin, 2006) that has been validated against experiments (Bookey et al., 2005) at the same conditions to present detailed flow features of the STBLI over a compression corner at Mach 3 and low Reynolds number with Reθ=2100. Details regarding the evolution of the turbulence structure angle, characteristic streamwise length scales, and hairpin packets through the interaction are presented. The three-dimensionality of the turbulence field and main shock are illustrated and the strength of shocks and shocklets through the interaction are considered.

Vector Preisach models of hysteresis - Mayergoyz, Issak D (The Science of Hysteresis: Mathematical modeling and applications, 2006)

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

VoIP deregulation in South Africa: Implications for underserviced areas - Marshini Chetty; Blake, Edwin; McPhie, Ewan (Telecommunications Policy, 2006)
Several statutory restrictions have recently been lifted on the use of Voice over Internet Protocol (VoIP) in South Africa. Previously, VoIP could only be utilised by the incumbent telecommunications operator, Telkom, the Second National Operator (SNO) and under serviced area licensees (USALs). This means new opportunities and cost savings for both network service providers and consumers. However, in rural and remote regions, further liberalisation is required so that service providers can take advantage of wireless technologies to provide connectivity in these areas. This paper discusses the legislative environment in South Africa and around the world with respect to VoIP and Wireless Fidelity (WiFi). In addition, examples are provided of how these technologies have been combined to provide last mile solutions around the world and particularly in South Africa. The paper concludes that further liberalisation in the telecommunications environment in South Africa is required if the goal of providing affordable access in rural areas is to be attained. Specifically, it is recommended that wireless technologies be deregulated since the combination of VoIP and WiFi may benefit rural areas. Also, the paper finds that USALs may not be the right model for underserviced areas in South Africa. Lastly, it is apparent that applications drive development and dictate which technologies are relevant for rural areas.
Keywords: South Africa; VoIP; WiFi

What do high-level memory models mean for transactions? - Grossman,Dan; Manson,Jeremy; Pugh, William (Proceedings of the 2006 workshop on Memory system performance and correctness - MSPC '06, 2006)

Wireless Network Security and Interworking - Shin,M.; Ma,J.; Mishra,A.; Arbaugh, William A. (Proceedings of the IEEE, 2006)
A variety of wireless technologies have been standardized and commercialized, but no single technology is considered the best because of different coverage and bandwidth limitations. Thus, interworking between heterogeneous wireless networks is extremely important for ubiquitous and high-performance wireless communications. Security in interworking is a major challenge due to the vastly different security architectures used within each network. The goal of this paper is twofold. First, we provide a comprehensive discussion of security problems and current technologies in 3G and WLAN systems. Second, we provide introductory discussions about the security problems in interworking, the state-of-the-art solutions, and open problems.
Keywords: 3G mobile communication; 3G systems; Authentication; Bandwidth; Communication system security; computer network security; computer security; Data security; internetworking; Land mobile radio cellular systems; Paper technology; security architectures; security of data; telecommunication security; wireless communication; wireless communications; Wireless LAN; wireless network security; Wireless networks; wireless technologies; WLAN systems

The ABCs of AVDs: Geometric Retrieval Made Simple - Mount, Dave (Algorithms and Computation, 2005)
One of the best known structures in computational geometry is the Voronoi diagram. Given a set of n points in space, called sites, this is a subdivision that partitions space into n convex cells according which site is closest. The Voronoi diagram and its dual, the Delaunay triangulation are among the most fundamental proximity structures known, and have numerous uses in science. For example, applying point location to the subdivision defined by a Voronoi diagram answers nearest neighbor queries. Although they are popular in low dimensional spaces, there are various reasons why Voronoi diagrams are rarely used higher dimensions. First, the combinatorial complexity of the diagram grows rapidly, as fast as Ω(nd/2) in d-dimensional space. Second, the diagram does not admit a straightforward search structure in higher dimensions.

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.

Adaptive OCR with Limited User Feedback - Ma,Huanfeng; David Doermann (8th Int. Conf. on Document Analysis and Recognition (ICDAR'05), 2005)
A methodology is proposed for processing noisy printed documents with limited user feedback. Without the support of ground truth, a specific collection of scanned documents can be processed to extract character templates. The adaptiveness of this approach lies in that the extracted templates are used to train an OCR classifier quickly and with limited user feedback. Experimental results show that this approach is extremely useful for the processing of noisy documents with many touching characters.

Algorithmic aspects of capacity in wireless networks - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, 2005)
This paper considers two inter-related questions: (i) Given a wireless ad-hoc network and a collection of source-destination pairs {(si,ti)}, what is the maximum throughput capacity of the network, i.e. the rate at which data from the sources to their corresponding destinations can be transferred in the network? (ii) Can network protocols be designed that jointly route the packets and schedule transmissions at rates close to the maximum throughput capacity? Much of the earlier work focused on random instances and proved analytical lower and upper bounds on the maximum throughput capacity. Here, in contrast, we consider arbitrary wireless networks. Further, we study the algorithmic aspects of the above questions: the goal is to design provably good algorithms for arbitrary instances. We develop analytical performance evaluation models and distributed algorithms for routing and scheduling which incorporate fairness, energy and dilation (path-length) requirements and provide a unified framework for utilizing the network close to its maximum throughput capacity.Motivated by certain popular wireless protocols used in practice, we also explore "shortest-path like" path selection strategies which maximize the network throughput. The theoretical results naturally suggest an interesting class of congestion aware link metrics which can be directly plugged into several existing routing protocols such as AODV, DSR, etc. We complement the theoretical analysis with extensive simulations. The results indicate that routes obtained using our congestion aware link metrics consistently yield higher throughput than hop-count based shortest path metrics.
Keywords: capacity modeling; end-to-end scheduling; Linear programming; Wireless networks

Alignment link projection using transformation-based learning - Ayan,Necip Fazil; Dorr, Bonnie J; Monz,Christof (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)
We present a new word-alignment approach that learns errors made by existing word alignment systems and corrects them. By adapting transformation-based learning to the problem of word alignment, we project new alignment links from already existing links, using features such as POS tags. We show that our alignment link projection approach yields a significantly lower alignment error rate than that of the best performing alignment system (22.6% relative reduction on English-Spanish data and 23.2% relative reduction on English-Chinese data).

Applications of SHOP and SHOP2 - Nau, Dana S.; Au,T.-C.; Ilghami,O.; Kuter,U.; Wu,D.; Yaman,F.; Munoz-Avila,H.; Murdock,J. W. (Intelligent Systems, IEEE, 2005)
We design the simple hierarchical ordered planner (SHOP) and its successor, SHOP2, with two goals in mind: to investigate research issues in automated planning and to provide some simple, practical planning tools. SHOP and SHOP2 are based on a planning formalism called hierarchical task network planning. SHOP and SHOP2 use a search-control strategy called ordered task decomposition, which breaks tasks into subtasks and generates the plan's actions in the same order that the plan executor executes them. So, throughout the planning process, the planner can tell what the state of the world at each step of the plan.
Keywords: automated planning; hierarchical task network planning; ordered task decomposition; planning (artificial intelligence); problem solving; search-control strategy; simple hierarchical ordered planner; trees (mathematics); uncertainty handling

Approximation results for probabilistic survivability - Zhang,Y.; Manister,E.; Kraus,S.; V.S. Subrahmanian (Multi-Agent Security and Survivability, 2005 IEEE 2nd Symposium on, 2005)
As multiagent systems (MASs) are increasingly used in industrial applications, the need to make them more robust and resilient against disruption increases dramatically. The author has developed a probabilistic model (assuming complete ignorance of dependencies between node failures) of survivability based on deploying each agent in a MAS on one or more nodes. Finding a deployment that maximizes survivability is highly intractable for two reasons: firstly, computing the survivability of any deployment is intractable, and secondly, going through an exponential number of deployments to find the best one adds another layer of intractability. In this paper, we study what happens when node failures are independent. We show that computing survivability in this environment is still intractable. We propose various heuristics to compute the survivability of a given deployment. We have implemented and tested all these heuristics. We report on the advantages and disadvantages of different heuristics in different environmental settings.
Keywords: application; computing; failure; fault; heuristic; heuristics; industrial; model; multi-agent; multiagent; node; probabilistic; probability; programming; survivability; system; systems; testing; tolerant

Assessment of STBLI DNS data and comparison against experiments - Wu,M.; Taylor,E. M; Martin, M.P (AIAA paper, 2005)

Automating regression testing for evolving GUI software - Memon, Atif M.; Nagarajan,Adithya; Xie,Qing (Journal of Software Maintenance and Evolution: Research and Practice, 2005)
With the widespread deployment of broadband connections worldwide, software development and maintenance are increasingly being performed by multiple engineers, often working around-the-clock to maximize code churn rates. To ensure rapid quality assurance of such software, techniques such as ‘nightly/daily building and smoke testing’ have become widespread since they often reveal bugs early in the software development process. During these builds, a development version of the software is checked out from the source code repository tree, compiled, linked, and (re)tested with the goal of (re)validating its basic functionality. Although successful for conventional software, smoke tests are difficult to develop and automatically re-run for software that has a graphical user interface (GUI). In this paper, we describe a framework called DART (Daily Automated Regression Tester) that addresses the needs of frequent and automated re-testing of GUI software. The key to our success is automation: DART automates everything from structural GUI analysis, smoke-test-case generation, test-oracle creation, to code instrumentation, test execution, coverage evaluation, regeneration of test cases, and their re-execution. Together with the operating system's task scheduler, DART can execute frequently with little input from the developer/tester to re-test the GUI software. We provide results of experiments showing the time taken and memory required for GUI analysis, test case and test oracle generation, and test execution. We empirically compare the relative costs of employing different levels of detail in the GUI test oracle. We also show the events and statements covered by the smoke test cases. Copyright © 2005 John Wiley & Sons, Ltd.
Keywords: daily/nightly builds; event-flow graphs; Graphical user interfaces; GUI regression testing; GUI testing; smoke testing; Software quality

Average relative radiance transform for subpixel detection - Broadwater, J.; Meth, R.; Chellapa, Rama (Geoscience and Remote Sensing Symposium, 2005. IGARSS '05. Proceedings. 2005 IEEE International, 2005)

Bayesian summarization at DUC and a suggestion for extrinsic evaluation - Daumé, Hal; Marcu,D. (Document understanding conference, 2005)

The Bible and multilingual optical character recognition - Kanungo,T.; Resnik, Philip; Mao,S.; Kim,D.W.; Zheng,Q. (Communications of the ACM, 2005)

Call stack coverage for test suite reduction - McMaster,S.; Memon, Atif M. (Software Maintenance, 2005. ICSM'05. Proceedings of the 21st IEEE International Conference on, 2005)
Test suite reduction is an important test maintenance activity that attempts to reduce the size of a test suite with respect to some criteria. Emerging trends in software development such as component reuse, multi-language implementations, and stringent performance requirements present new challenges for existing reduction techniques that may limit their applicability. A test suite reduction technique that is not affected by these challenges is presented; it is based on dynamically generated language-independent information that can be collected with little run-time overhead. Specifically, test cases from the suite being reduced are executed on the application under test and the call stacks produced during execution are recorded. These call stacks are then used as a coverage requirement in a test suite reduction algorithm. Results of experiments on test suites for the space antenna-steering application show significant reduction in test suite size at the cost of a moderate loss in fault detection effectiveness.
Keywords: call stack coverage; component reuse; Fault detection; language-independent information; multi-language implementation; program testing; software development; software fault tolerance; Software maintenance; software reusability; space antenna-steering application; stringent performance requirement; systems analysis; test suite reduction algorithm

The Challenge of Personal Information Management - Dix,A.; Jones,W.; Czerwinski,M.; Teevan,J.; Plaisant, Catherine; Moran,TP (INTERACT'05: Communicating Naturally through Computers (Adjunct Proceedings), 2005)

Class-based access control for distributed video-on-demand systems - Mundur, Padma; Sood,A. K; Simon,R. (IEEE Transactions on Circuits and Systems for Video Technology, 2005)
The focus of this paper is the analysis of threshold-based admission control policies for distributed video-on-demand (VoD) systems. Traditionally, admission control methods control access to a resource based on the resource capacity. We have extended that concept to include the significance of an arriving request to the VoD system by enforcing additional threshold restrictions in the admission control process on request classes deemed less significant. We present an analytical model for computing blocking performance of the VoD system under threshold-based admission control. Extending the same methodology to a distributed VoD architecture we show through simulation that the threshold performance conforms to the analytical model. We also show that threshold-based analysis can work in conjunction with other request handling policies and are useful for manipulating the VoD performance since we are able to distinguish between different request classes based on their merit. Enforcing threshold restrictions with the option of downgrading blocked requests in a multirate service environment results in improved performance at the same time providing different levels of quality of service (QoS). In fact, we show that the downgrade option combined with threshold restrictions is a powerful tool for manipulating an incoming request mix over which we have no control into a workload that the VoD system can handle.
Keywords: Access control; Admission control; Analytical models; blocking performance; class-based access control; Computational modeling; Computer architecture; Computer science; Distributed control; Distributed video-on-demand (VoD) system; distributed video-on-demand system; multimedia systems; multirate service model; Performance analysis; QoS; quality of service; request handling policy; resource allocation; resource capacity; telecommunication congestion control; threshold-based admission control; video on demand

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

Constructing task visibility intervals for a surveillance system - Lim,Ser-Nam; Mittal,Anurag; Davis, Larry S. (Proceedings of the third ACM international workshop on Video surveillance & sensor networks, 2005)
One of the goals of a multi-camera surveillance system is to collect useful video clips of objects in the scene. Objects in the collected videos should be unobstructed, in the field of view of the given camera, and meet task-specific resolution requirement. For this purpose, we describe an algorithm that constructs "task visibility intervals", which are tuples of information about what to sense (task-object pairs), when to sense (feasible future temporal intervals to start a task) and how to sense (the camera to use and the corresponding viewing angles and focal length). The algorithm first looks for temporal intervals within which the angular extents of objects overlap each other, causing the object farthest from the given camera to be occluded. Outside these intervals, sub-intervals are then constructed such that feasible camera settings exist for capturing the object. Experimental results are provided to illustrate the system capabilities in constructing such task visibility intervals, followed by scheduling them using a greedy algorithm.
Keywords: scheduling; sensor

Content Index to Volume 18 - Kuniavsky,M.; Vaughan,M.; Bederson, Benjamin B.; Shneiderman, Ben; Rau,P.L.P.; from Menus,T.; Lane,D.M.; Napier,H.A.; Peres,S.C.; Sándor,A. (INTERNATIONAL JOURNAL OF HUMAN–COMPUTER INTERACTION, 2005)

Coordinated sensor deployment for improving secure communications and sensing coverage - Mao,Yinian; M. Wu (Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, 2005)
Sensor network has a great potential in applications such as habitat monitoring, wildlife tracking, building surveillance, and military combat. The design of a sensor network system involves several important issues, including the sensing coverage, node-to-node or node-to-base-station communications, and the security in information gathering and relay by the sensors. In this paper, we show that the system performance on these aspects depends closely on how the sensors are deployed in the field, and on how the sensor locations can be adjusted after the initial deployment. For static sensor deployment, we investigate the hexagon and square lattice topology and analyze their impact on secure connectivity and sensing coverage. For advanced sensing devices that allow for location adjustment after deployment, we have established a new framework for coordinated updates of sensor locations. We propose two new sensor location updating algorithms, the VFSec and the Weighted Centroid algorithm, to jointly optimize sensing coverage and secure connectivity. Simulation results show that these new algorithms provide superior tradeoff over the existing approaches that do not take security into considerations.
Keywords: key pre-distribution; location adjustment; secure communications; sensing coverage; sensor deployment

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

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

Data hiding in compiled program binaries for enhancing computer system performance - Swaminathan,A.; Mao,Y.; Wu,M.; Kailas,K. (Information Hiding, 2005)
Information hiding has been studied in many security applications such as authentication, copyright management and digital forensics. In this work, we introduce a new application where successful information hiding in compiled program binaries could bring system-wide performance improvements. Our goal is to enhance computer system performance by providing additional information to the processor, without changing the instruction set architecture. We first analyze the statistics of typical programs to demonstrate the feasibility of hiding data in them. We then propose several techniques to hide a large amount of data in the operand fields with very low computation and storage requirements during the extraction process. The data embedding is made reversible to recover the original instructions and to ensure the correct execution of the computer program. Our experiments on the SPEC CPU2000 benchmark programs show that up to 110K bits of information can be embedded in large programs with as little as 3K bits of additional run-time memory in the form of a simple look-up table.

A data model and query language to explore enhanced links and paths in life science sources - Mihaila,G.; Naumann,F.; Raschid, Louiqa; Vidal,M. E (Proceedings of the ACM SIGMOD Workshop on The Web and Databases (WebDB), 2005)

Design and implementation of a routing control platform - Caesar,Matthew; Caldwell,Donald; Feamster, Nick; Rexford,Jennifer; Shaikh,Aman; van der Merwe,Jacobus (Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation - Volume 2, 2005)
The routers in an Autonomous System (AS) must distribute the information they learn about how to reach external destinations. Unfortunately, today's internal Border Gateway Protocol (iBGP) architectures have serious problems: a "full mesh" iBGP configuration does not scale to large networks and "route reflection" can introduce problems such as protocol oscillations and persistent loops. Instead, we argue that a Routing Control Platform (RCP) should collect information about external destinations and internal topology and select the BGP routes for each router in an AS. RCP is a logically-centralized platform, separate from the IP forwarding plane, that performs route selection on behalf of routers and communicates selected routes to the routers using the unmodified iBGP protocol. RCP provides scalability without sacrificing correctness. In this paper, we present the design and implementation of an RCP prototype on commodity hardware. Using traces of BGP and internal routing data from a Tier-1 backbone, we demonstrate that RCP is fast and reliable enough to drive the BGP routing decisions for a large network. We show that RCP assigns routes correctly, even when the functionality is replicated and distributed, and that networks using RCP can expect comparable convergence delays to those using today's iBGP architectures.

Detection of denial-of-message attacks on sensor network broadcasts - McCune, J.M.; Elaine Shi; Perrig, A.; Reiter, M.K. (2005)
So far sensor network broadcast protocols assume a trustworthy environment. However in safety and mission-critical sensor networks this assumption may not be valid and some sensor nodes might be adversarial. In these environments, malicious sensor nodes can deprive other nodes from receiving a broadcast message. We call this attack a denial-of-message attack (DoM). In this paper we model and analyze this attack, and present countermeasures. We present SIS, a secure implicit sampling scheme that permits a broadcasting base station to probabilistically detect the failure of nodes to receive its broadcast, even if these failures result from an attacker motivated to induce these failures undetectably. SIS works by eliciting authenticated acknowledgments from a subset of nodes per broadcast, where the subset is unpredictable to the attacker and tunable so as to mitigate acknowledgment implosion on the base station. We use a game-theoretic approach to evaluate this scheme in the face of an optimal attacker that attempts to maximize the number of nodes it denies the broadcast while remaining undetected by the base station, and show that SIS significantly constrains such an attacker even in sensor networks exhibiting high intrinsic loss rates. We also discuss extensions that permit more targeted detection capabilities.
Keywords: authenticated acknowledgments; broadcast channels; broadcast protocols; broadcasting base station; countermeasures; denial-of-message attacks; DoM; game theory; game-theoretic approach; malicious sensor nodes; Mobile computing; optimal attacker; probabilistic detection; probability; Protocols; Sampling methods; secure implicit sampling; sensor network broadcasts; SIS; telecommunication security; Wireless sensor networks

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

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

Efficient lookup on unstructured topologies - Morselli,Ruggero; Bhattacharjee, Bobby; Srinivasan, Aravind; Marsh,Michael A (Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, 2005)
We present LMS, a protocol for efficient lookup on unstructured networks. Our protocol uses a virtual namespace without imposing specific topologies. It is more efficient than existing lookup protocols for unstructured networks, and thus is an attractive alternative for applications in which the topology cannot be structured as a Distributed Hash Table (DHT).We present analytic bounds for the worst-case performance of our protocol. Through detailed simulations (with up to 100,000 nodes), we show that the actual performance on realistic topologies is significantly better. We also show in both simulations and a complete implementation (which includes over five hundred nodes) that our protocol is inherently robust against multiple node failures and can adapt its replication strategy to optimize searches according to a specific heuristic. Moreover, the simulation demonstrates the resilience of LMS to high node turnover rates, and that it can easily adapt to orders of magnitude changes in network size. The overhead incurred by LMS is small, and its performance approaches that of DHTs on networks of similar size.
Keywords: distributed algorithms; lookup protocols; peer-to-peer networks; random walks

Efficient strategies for channel management in wireless lans - Mishra,A.; Brik,V.; Banerjee,S.; Srinivasan, Aravind; Arbaugh, William A. (UMD, CS Tech. Rep. CS-TR, 2005)
We define efficient algorithms for channel management (channelassignment and load balancing among APs) in 802.11-based WLANs that lead to better usage of the wireless spectrum. These algorithms (called CFAssign) are based on a “conflict-free set coloring” for- mulation that jointly perform load balancing along with channel assignment. Such a formulation has a number of advantages. First, it explicitly captures interference effects at clients. Next, it intrinsi- cally exposes opportunities for better channel re-use. Finally, algo- rithms based on this formulation do not depend on specific physical RF models and hence can be applied efficiently to a wide-range of in-building as well as outdoor scenarios. We have performed extensive packet-level simulations and mea- surements on a deployed wireless testbed of 70 APs to validate the performance of our proposed algorithms. We show that in ad- dition to single network scenarios, CFAssign algorithms are well suited for channel assignment in scenarios where multiple wireless networks share the same physical space and contend for the same frequency spectrum. Our results over a wide range of scenarios indicate that CFAssign reduces the interference at clients by about 50-70% in comparison to current best-known techniques.

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

EvoSTOC Contributions - Merkle,D.; Middendorf,M.; Scheidler,A.; Avigad,G.; Moshaiov,A.; Brauner,N.; Parsopoulos,K.E.; Vrahatis,M.N.; Rand, William; Riolo,R (Applications of evolutionary computing: EvoWorkshops 2005, EvoBIO, EvoCOMNET, EvoHOT, EvoIASP, EvoMUSART, and EvoSTOC, 2005)

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

Exploiting partially overlapping channels in wireless networks: Turning a peril into an advantage - Mishra,A.; Rozner,E.; Banerjee,S.; Arbaugh, William A. (Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement, 2005)

Extending User Understanding of Federal Statistics in Tables (2000) - Marchionini,Gary; Hert,Carol; Liddy,Liz; Shneiderman, Ben (Institute for Systems Research Technical Reports, 2005)
This paper describes progress toward improving user interfaces for US Federal government statistics that are presented in tables. Based on studies of user behaviors and needs related to statistical tables, we describe interfaces to assist diverse users with a range of statistical literacy to explore, find, understand, and use US Federal government statistics.
Keywords: Technical Report

Fast illumination-invariant background subtraction using two views: error analysis, sensor placement and applications - Lim,Ser-Nam; Mittal,A.; Davis, Larry S.; Paragios,N. (Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, 2005)
Background modeling and subtraction to detect new or moving objects in a scene is an important component of many intelligent video applications. Compared to a single camera, the use of multiple cameras leads to better handling of shadows, specularities and illumination changes due to the utilization of geometric information. Although the result of stereo matching can be used as the feature for detection, it has been shown that the detection process can be made much faster by a simple subtraction of the intensities observed at stereo-generated conjugate pairs in the two views. The methodology however, suffers from false and missed detections due to some geometric considerations. In this paper, we perform a detailed analysis of such errors. Then, we propose a sensor configuration that eliminates false detections. Algorithms are also proposed that effectively eliminate most detection errors due to missed detections, specular reflections and objects being geometrically close to the background. Experiments on several scenes illustrate the utility and enhanced performance of the proposed approach compared to existing techniques.
Keywords: analysis; application; background; cameras; configuration; DETECTION; detection; error; error; extraction; false; feature; handling; illumination-invariance; image; intelligent; matching; modeling; object; placement; processing; sensor; sensors; shadow; stereo; subtraction; video

Font identification using the grating cell texture operator - Ma,H.; David Doermann (SPIE Conference on Document Recogntion and Retreival XXII, 2005)
In this paper, a new feature extraction operator, the grating cell operator, is applied to analyze the texture features and classify fonts of scanned document images. This operator is compared with the isotropic Gabor filter which was also employed for font classification. In order to improve the performance, a back-propagation neural network (BPNN) classifier was applied and compared with the simple weighted Euclidean distance (WED) classifier. Experimental results for five fonts of three scripts show that the grating cell operator performs better than the isotropic Gabor filter, and the BPNN classifier can provide more accurate classification results than the WED classifier.

Forensic recovery of hard disk data by using the spin-stand imaging technique - Tse,Chun; Krafft,Charles; Mayergoyz, Issak D; McAvoy,Patrick; Tseng,Chun-Yang (Proceedings of SPIE, 2005)
An ex-situ technique for the drive-independent forensic recovery of data from failed hard drives has been developed.For drives which have suffered damage from a head crash or other mechanical problems and cannot be resuscitatedusing standard software, firmware, or part-replacement techniques, there is currently no commercially available meansto recover the data, even though the files are still stored on the magnetic disks. Here, we report on the results of a spinstandimaging based technology, where the failed disk is removed from its native drive, placed on a spin-stand, andscanned with a giant magnetoresistive head. After track centering, track following, signal detection, data decoding, errorcorrection, and sector mapping, the otherwise unrecoverable data can be retrieved to the computer operating system.Spin-stand based data imaging has the potential to provide recovery at data rates approaching those in the native driveand is a truly drive-independent method to recover hard disk data in a time-efficient manner.

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

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

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

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

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

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

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

The Hiero machine translation system: Extensions, evaluation, and analysis - Chiang,D.; Lopez,A.; Madnani,N.; Monz,C.; Resnik, Philip; Subotin,M. (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

Identifying Script on Word-Level with Informational Confidence - Jaeger,Stefan; Ma,Huanfeng; David Doermann (8th Int. Conf. on Document Analysis and Recognition, 2005)
In this paper, we present a multiple classifier system for script identification. Applying a Gabor filter analysis of textures on word-level, our system identifies Latin and non-Latin words in bilingual printed documents. The classifier system comprises four different architectures based on nearest neighbors, weighted Euclidean distances, Gaussian mixture models, and support vector machines. We report results for Arabic, Chinese, Hindi, and Korean script. Moreover, we show that combining informational confidence values using sum-rule can consistently outperform the best single recognition rate.

Improved approximation bounds for planar point pattern matching - Cho,M.; Mount, Dave (Algorithms and Data Structures, 2005)
We consider the well known problem of matching two planar point sets under rigid transformations so as to minimize the directed Hausdorff distance. This is a well studied problem in computational geometry. Goodrich, Mitchell, and Orletsky [GMO94] presented a very simple approximation algorithm for this problem, which computes transformations based on aligning pairs of points. They showed that their algorithm achieves an approximation ratio of 4. We consider a minor modification to their algorithm, which is based on aligning midpoints rather than endpoints. We show that this algorithm achieves an approximation ratio not greater than 3.13. Our analysis is sensitive to the ratio between the diameter of the pattern set and the Hausdorff distance, and we show that the approximation ratio approaches 3 in the limit. Finally, we provide lower bounds that show that our approximation bounds are nearly tight.

Induction of Word and Phrase Alignments for Automatic Document Summarization - Daumé, Hal; Marcu,Daniel (Computational Linguistics, 2005)

Iterative translation disambiguation for cross-language information retrieval - Monz,Christof; Dorr, Bonnie J (Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, 2005)
Finding a proper distribution of translation probabilities is one of the most important factors impacting the effectiveness of a cross-language information retrieval system. In this paper we present a new approach that computes translation probabilities for a given query by using only a bilingual dictionary and a monolingual corpus in the target language. The algorithm combines term association measures with an iterative machine learning approach based on expectation maximization. Our approach considers only pairs of translation candidates and is therefore less sensitive to data-sparseness issues than approaches using higher n-grams. The learned translation probabilities are used as query term weights and integrated into a vector-space retrieval system. Results for English-German cross-lingual retrieval show substantial improvements over a baseline using dictionary lookup without term weighting.
Keywords: cross-language retrieval; query formulation; term co-occurrence measures; term weighting; translation disambiguation

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

A large-scale exploration of effective global features for a joint entity detection and tracking model - Daumé, Hal; Marcu,D. (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)

Learning approximate preconditions for methods in hierarchical plans - Ilghami,Okhtay; Muñoz-Avila,Héctor; Nau, Dana S.; Aha,David W. (ACM, 2005)
A significant challenge in developing planning systems for practical applications is the difficulty of acquiring the domain knowledge needed by such systems. One method for acquiring this knowledge is to learn it from plan traces, but this method typically requires a huge number of plan traces to converge. In this paper, we show that the problem with slow convergence can be circumvented by having the learner generate solution plans even before the planning domain is completely learned. Our empirical results show that these improvements reduce the size of the training set that is needed to find correct answers to a large percentage of planning problems in the test set.

Learning as search optimization: approximate large margin methods for structured prediction - Daumé, Hal; Marcu,Daniel (Proceedings of the 22nd international conference on Machine learning, 2005)
Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence the-orems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.

Learning preconditions for planning from plan traces and HTN structure - Ilghami,Okhtay; Nau, Dana S.; Muñoz-Avila,Héctor; Aha,David W. (Computational Intelligence, 2005)
A great challenge in developing planning systems for practical applications is the difficulty of acquiring the domain information needed to guide such systems. This paper describes a way to learn some of that knowledge. More specifically, the following points are discussed. (1) We introduce a theoretical basis for formally defining algorithms that learn preconditions for Hierarchical Task Network (HTN) methods. (2) We describe Candidate Elimination Method Learner (CaMeL), a supervised, eager, and incremental learning process for preconditions of HTN methods. We state and prove theorems about CaMeL's soundness, completeness, and convergence properties. (3) We present empirical results about CaMeL's convergence under various conditions. Among other things, CaMeL converges the fastest on the preconditions of the HTN methods that are needed the most often. Thus CaMeL's output can be useful even before it has fully converged.
Keywords: candidate elimination; HTN planning; learning; version spaces

Magic bullets and golden rules: data sampling in molecular phylogenetics - Cummings, Michael P.; Meyer,A. (Zoology (Jena), 2005)
Data collection for molecular phylogenetic studies is based on samples of both genes and taxa. In an ideal world, with no limitations to resources, as many genes could be sampled as deemed necessary to address phylogenetic problems. Given limited resources in the real world, inadequate (in terms of choice of genes or number of genes) sequences or restricted taxon sampling can adversely affect the reliability or information gained in phylogenetics. Recent empirical and simulation-based studies of data sampling in molecular phylogenetics have reached differing conclusions on how to deal with these problems. Some advocated sampling more genes, others more taxa. There is certainly no 'magic bullet' that will fit all phylogenetic problems, and no specific 'golden rules' have been deduced, other than that single genes may not always contain sufficient phylogenetic information. However, several general conclusions and suggestions can be made. One suggestion is that the determination of a multiple, but moderate number (e.g., 6-10) of gene sequences might take precedence over sequencing a larger set of genes and thereby permit the sampling of more taxa for a phylogenetic study.

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

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

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

Mitigating risk of data loss in preservation environments - Moore,R.W.; JaJa, Joseph F.; Chadduck,R. (Mass Storage Systems and Technologies, 2005. Proceedings. 22nd IEEE / 13th NASA Goddard Conference on, 2005)
Preservation environments manage digital records for time periods that are much longer than that of a single vendor product. A primary requirement is the preservation of the authenticity and integrity of the digital records while simultaneously minimizing the cost of long-term storage, as the data is migrated onto successive generations of technology. The emergence of low-cost storage hardware has made it possible to implement innovative software systems that minimize risk of data loss and preserve authenticity and integrity. This paper describes software mechanisms in use in current persistent archives and presents an example based upon the NARA research prototype persistent archive.
Keywords: archives; authentication; authenticity; computing; data; databases; digital; distributed; environment; Grid; integrity; management; message; objects; persistent; preservation; record; risk; storage

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

NeurAlign: combining word alignments using neural networks - Ayan,Necip Fazil; Dorr, Bonnie J; Monz,Christof (Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, 2005)
This paper presents a novel approach to combining different word alignments. We view word alignment as a pattern classification problem, where alignment combination is treated as a classifier ensemble, and alignment links are adorned with linguistic features. A neural network model is used to learn word alignments from the individual alignment systems. We show that our alignment combination approach yields a significant 20--34% relative error reduction over the best-known alignment combination technique on English-Spanish and English-Chinese data.

A new approach to image fusion based on cokriging - Memarsadeghi,N.; Le Moigne,J.; Mount, Dave; Morisette,J. (Information Fusion, 2005 8th International Conference on, 2005)
We consider the image fusion problem involving remotely sensed data. We introduce cokriging as a method to perform fusion. We investigate the advantages of fusing Hyperion with ALI. This evaluation is performed by comparing the classification of the fused data with that of input images and by calculating well-chosen quantitative fusion quality metrics. We consider the invasive species forecasting system (ISFS) project as our fusion application. The fusion of ALI with Hyperion data is studied using PCA and wavelet-based fusion. We then propose utilizing a geostatistical based interpolation method called cokriging as a new approach for image fusion.
Keywords: ALI; analysis; based; cokriging; component; data; forecasting; fusion; fusion; geophysical; geostatistical; Hyperion; image; Interpolation; interpolation; invasive; ISFS; method; metrics; PCA; principal; processing; project; QUALITY; quantitative; remote; remotely; sensed; sensing; sensor; sensors; signal; species; system; techniques; transforms; wavelet; wavelet-based

New experimental data of STBLI at DNS/LES accessible Reynolds numbers - Bookey,P.; Wyckham,C.; Smits,A. J.; Martin, M.P (AIAA paper, 2005)

Preliminary Study of the SGS Time Scales for Compressible Boundary Layers using DNS Data - Martin, M.P (43rd AIAA Aerospace Sciences Meeting and Exhibit, 2005)
We use direct numerical simulation data of turbulent boundary layers and a priori testingto estimate the time scales that are associated with the subgrid-scale terms in the conser- vative form of the governing equations. The exact and modeled subgrid-scale terms are gathered from the filtered direct numerical simulation fields for several time steps. The model coefficients are evaluated using the Lagrangian averaging technique. We analyze the time scales directly by performing temporal autocorrelations along fluid particle paths. To assess the subgrid-scale models, we compare the time scales and the quantities given by the exact and modeled representations. It is found that in general, mixed models give a larger integral time scale than that of the exact terms and that the discrepancy is not related to the prescribed memory length associated with the evaluation of the model coefficients.

Preliminary Study of the Turbulence Structure in Supersonic Boundary Layers using DNS Data - Taylor,E. M; Martin, M.P; Smits,A. J. (35th AIAA Fluid Dynamics Conference, 2005)
Direct numerical simulation data are used to visualize coherent structures in turbulentboundary layers at Mach numbers from 0.3 to 7. Different criteria to identify the three- dimensional turbulence structure are selected. We find that using the discriminant of the velocity gradient tensor, the swirling strength and the λ2 criteria give nearly identical results, with λ2 identifying more structures very close to the wall.

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

A process and role-based taxonomy of techniques to make testable COTS components - Memon, Atif M. (Testing Commercial-Off-The-Shelf Components And SystemsTesting Commercial-Off-The-Shelf Components And Systems, 2005)

Rapid "crash testing" for continuously evolving GUI-based software applications - Xie,Q.; Memon, Atif M. (Software Maintenance, 2005. ICSM'05. Proceedings of the 21st IEEE International Conference on, 2005)
Several rapid-feedback-based quality assurance mechanisms are used to manage the quality of continuously evolving software. Even though graphical user interfaces (GUIs) are one of the most important parts of software, there are currently no mechanisms to quickly retest evolving GUI software. We leverage our previous work on GUI testing to define a new automatic GUI re-testing process called "crash testing" that is integrated with GUI evolution. We describe two levels of crash testing: (1) immediate feedback-based in which a developer indicates that a GUI bug was fixed in response to a previously reported crash; only select crash test cases are rerun and the developer is notified of the results in a matter of seconds, and (2) between code changes in which new crash test cases are generated on-the-fly and executed on the GUI. Since the code may be changed by another developer before all the crash tests have been executed, hence requiring restarting of the process, we use a simple rotation-based scheme to ensure that all crash tests are executed over a series of code changes. We show, via empirical studies, that our crash tests are effective at revealing serious problems in the GUI.
Keywords: crash testing; graphical user interface software retesting; Graphical user interfaces; GUI-based software application; immediate feedback; program testing; rapid-feedback-based quality assurance; software evolution; Software maintenance; software prototyping; Software quality

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

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

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

Search-based structured prediction as classification - Daumé, Hal; Langford,J.; Marcu,D. (NIPS Workshop on Advances in Structured Learning for Text and Speech Processing, Whistler, Canada, 2005)

Security of feature extraction in image hashing - Swaminathan,A.; Mao,Yinian; M. Wu (Acoustics, Speech, and Signal Processing, 2005. Proceedings. (ICASSP '05). IEEE International Conference on, 2005)
Security and robustness are two important requirements for image hash functions. We introduce "differential entropy" as a metric to quantify the amount of randomness in image hash functions and to study their security. We present a mathematical framework and derive expressions for the proposed security metric for various common image hashing schemes. Using the proposed security metric, we discuss the trade-offs between security and robustness in image hashing.
Keywords: cryptography; differential; digital; entropy; extraction; feature; functions; hash; hashing; image; metric; processing; randomness; robustness; Security; signature; signatures

A sentence-trimming approach to multi-document summarization - Zajic, David; Dorr, Bonnie J; Jimmy Lin; Monz,C.; Schwartz,R. (Proceedings of DUC2005, 2005)
We implemented an initial applicationof a sentence-trimming approach (Trim- mer) to the problem of multi-document summarization in the MSE2005 and DUC2005 tasks. Sentence trimming was incorporated into a feature-based summarization system, called Multi- Document Trimmer (MDT), by us- ing sentence trimming as both a pre- processing stage and a feature for sen- tence ranking. We demonstrate that we were able to port Trimmer easily to this new problem. Although the direct im- pact of sentence trimming was minimal compared to other features used in the system, the interaction of the other fea- tures resulted in trimmed sentences ac- counting for nearly half of the selected summary sentences.

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

Space-efficient and fast algorithms for multidimensional dominance reporting and counting - JaJa, Joseph F.; Mortensen,C.; Shi,Q. (Algorithms and Computation, 2005)
We present linear-space sub-logarithmic algorithms for handling the 3-dimensional dominance reporting and the 2-dimensional dominance counting problems. Under the RAM model as described in [M. L. Fredman and D. E. Willard. ldquoSurpassing the information theoretic bound with fusion treesrdquo, Journal of Computer and System Sciences, 47:424–436, 1993], our algorithms achieve O(log n/loglog n+f) query time for the 3-dimensional dominance reporting problem, where f is the output size, and O(log n/loglog n) query time for the 2-dimensional dominance counting problem. We extend these results to any constant dimension d ge 3, achieving O(n(log n/loglog n)d – 3) space and O((log n/loglog n)d – 2+ f) query time for the reporting case and O(n(log n/loglog n)d – 2) space and O((log n/loglog n)d – 1) query time for the counting case.

Space-time tradeoffs for approximate spherical range counting - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, 2005)
We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in Rd along with a positive approximation factor ε, the goal is to preprocess the points so that, given any Euclidean ball B, we can return the number of points of any subset of S that contains all the points within a (1 - ε)-factor contraction of B, but contains no points that lie outside a (1 + ε)-factor expansion of B.In many applications of range searching it is desirable to offer a tradeoff between space and query time. We present here the first such tradeoffs for approximate range counting queries. Given 0 < ε ≤ 1/2 and a parameter γ, where 2 ≤ γ ≤ 1/ε, we show how to construct a data structure of space O(nγd log (1/ε)) that allows us to answer ε-approximate spherical range counting queries in time O(log(nγ) + 1/(εγd-1). The data structure can be built in time O(nγd log (n/ε)) log (1/ε)). Here n, ε, and γ are asymptotic quantities, and the dimension d is assumed to be a fixed constant.At one extreme (low space), this yields a data structure of space O(n log (1/e)) that can answer approximate range queries in time O(logn + 1/(ed-1) which, up to a factor of O(n log (1/e) in space, matches the best known result for approximate spherical range counting queries. At the other extreme (high space), it yields a data structure of space O((n/ed) log(1/ε)) that can answer queries in time O(logn + 1/ε). This is the fastest known query time for this problem.We also show how to adapt these data structures to the problem of computing an ε-approximation to the kth nearest neighbor, where k is any integer from 1 to n given at query time. The space bounds are identical to the range searching results, and the query time is larger only by a factor of O(1/(εγ)).Our approach is broadly based on methods developed for approximate Voronoi diagrams (AVDs), but it involves a number of significant extensions from the context of nearest neighbor searching to range searching. These include generalizing AVD node-separation properties from leaves to internal nodes of the tree and constructing efficient generator sets through a radial decomposition of space. We have also developed new arguments to analyze the time and space requirements in this more general setting.

Studying the fault-detection effectiveness of GUI test cases for rapidly evolving software - Memon, Atif M.; Xie,Q. (Software Engineering, IEEE Transactions on, 2005)
Software is increasingly being developed/maintained by multiple, often geographically distributed developers working concurrently. Consequently, rapid-feedback-based quality assurance mechanisms such as daily builds and smoke regression tests, which help to detect and eliminate defects early during software development and maintenance, have become important. This paper addresses a major weakness of current smoke regression testing techniques, i.e., their inability to automatically (re)test graphical user interfaces (GUIs). Several contributions are made to the area of GUI smoke testing. First, the requirements for GUI smoke testing are identified and a GUI smoke test is formally defined as a specialized sequence of events. Second, a GUI smoke regression testing process called daily automated regression tester (DART) that automates GUI smoke testing is presented. Third, the interplay between several characteristics of GUI smoke test suites including their size, fault detection ability, and test oracles is empirically studied. The results show that: 1) the entire smoke testing process is feasible in terms of execution time, storage space, and manual effort, 2) smoke tests cannot cover certain parts of the application code, 3) having comprehensive test oracles may make up for not having long smoke test cases, and 4) using certain oracles can make up for not having large smoke test suites.
Keywords: daily automated regression tester; Fault diagnosis; fault-detection; formal specification; formal verification; Graphical user interfaces; GUI test cases; program testing; quality assurance mechanism; rapidly evolving software; smoke regression testing technique; software development; software fault tolerance; Software maintenance; software prototyping; Software quality; test oracles

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

Turning information visualization innovations into commercial products: lessons to guide the next success - Shneiderman, Ben; Rao,R.; Andrews,K.; Ahlberg,C.; Brodbeck,D.; Jewitt,T.; Mackinlay,J. (IEEE Symposium on Information Visualization, 2005. INFOVIS 2005, 2005)
As information visualization matures as an academic research field, commercial spinoffs are proliferating, but success stories are harder to find. This is the normal process of emergence for new technologies, but the panel organizers believe that there are certain strategies that facilitate success. To teach these lessons, we have invited several key figures who are seeking to commercialize information visualization tools. The panelists make short presentations, engage in a moderated discussion, and respond to audience questions.
Keywords: Books; commercial development; commercial product; Computer interfaces; Computer science; data visualisation; Data visualization; Educational institutions; exploratory data analysis; information visualization innovation; information visualization tool; innovation management; Laboratories; Management training; new technology emergence; Technological innovation; technology transfer; Turning; User interfaces

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

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

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

Using Non-random Associations for Predicting Latency in WANs - Raschid, Louiqa; Ye,Q.; Zadorozhny,V.; Gal,A.; Murthy,H. (Web Information Systems Engineering – WISE 2005, 2005)
In this paper, we propose a scalable performance management tool for Wide Area Applications. Our objective is to scalably identify non-random associations between pairs of individual Latency Profiles (iLPs) (i.e., latency distributions experienced by clients when connecting to a server) and exploit them in latency prediction. Our approach utilizes Relevance Networks (RNs) to manage tens of thousands of iLPs. Non-random associations between iLPs can be identified by topology-independent measures such as correlation and mutual information. We demonstrate that these non-random associations do indeed have a significant impact in improving the error of latency prediction.

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

Vision geometry XIII(San Jose CA, 18-19 January 2005) - Latecki,L.J.; Mount, Dave; Wu,A. Y (SPIE proceedings series, 2005)

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

Weighted coloring based channel assignment for WLANs - Mishra,A.; Banerjee,S.; Arbaugh, William A. (ACM SIGMOBILE Mobile Computing and Communications Review, 2005)

Adaptive Hindi OCRUsing Generalized Hausdorff Image Comparison - Ma,Huanfeng; David Doermann (ACMTransactions on Asian Language Information Processing, 2004)

Analyzing the number of samples required for an approximate Monte-Carlo LMS line estimator - Mount, Dave; Netanyahu,N. S; Zuck,E. (Theory and Applications of Recent Robust MethodsTheory and Applications of Recent Robust Methods, 2004)

Appearance tracking using adaptive models in a particle filter - Zhou, S.; Chellapa, Rama; Moghaddam, B. (Proc. of 6th Asian Conference on Computer Vision (ACCV), 2004)
The particle filter is a popular tool for visual tracking. Usually, the appearance model is eitherfixed or rapidly changing and the motion model is simply a random walk with fixed noise vari- ance. Also, the number of particles used is typically fixed. All these factors make the visual tracker unstable. To stabilize the tracker, we propose the following measures: an observation model arising from an adaptive noise variance, and adaptive number of particles. The adaptive- velocity is computed via a first-order linear predictor using the previous particle configuration. Tracking under occlusion is accomplished using robust statistics. Experimental results on track- ing visual objects in long video sequences such as vehicles, tank, and human faces demonstrate the effectiveness and robustness of our algorithm.

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

Applying permutation tests to tree-based statistical models: extending the R package rpart - Cummings, Michael P.; Myers,D. S; Mangelson,M (University of Maryland Institute for Advanced Computer Studies, 2004)
Tree-based statistical models are useful for evaluating relationships between predictor and response variables and for generating predictions when the response is unknown. However, current methods of constructing tree-based models do not provide a probabilistic assessment of the models produced. Here we describe our work to use permutation tests to quantitatively estimate the probability of tree-based statistical models. We have extended the rpart (recursive partitioning) package of the R system for statistical data analysis. This extension, rpart.permutation, executes the permutations in parallel, using MPI (Message Passing Interface) to greatly decrease the time necessary to complete the analysis.

ASPIRE: automated systematic protocol implementation robustness evaluation - Vasan,Arunchandar; Memon, Atif M. (Software Engineering Conference, 2004. Proceedings. 2004 Australian, 2004)
Network protocol implementations are susceptible to problems caused by their lack of ability to handle invalid inputs. We present ASPIRE: automated systematic protocol implementation robustness evaluation, an automated approach to pro-actively test protocol implementations by observing their responses to faulty protocol data units (PDUs) or messages. In contrast to existing approaches, we sample the faulty PDU space in a systematic manner, thus allowing us to evaluate protocol implementations in the face of a wider variety of faulty PDUs. We use a pruning strategy to reduce, from exponential, the size of the faulty PDU set to polynomial in the number of fields of a PDU. We have implemented the ASPIRE algorithms and evaluated them on implementations of HTTP (Apache, Google Web Server (GWS), and Microsoft IIS) and SMTP (Sendmail and Microsoft Exchange) protocols. Our results show that Apache, GWS, and IIS, although implementing the same protocol specification, behave differently on faulty HTTP PDUs; Sendmail and exchange are different in handling our faulty SMTP PDUs.
Keywords: algorithm; ASPIRE; automated systematic protocol; automated testing; fault tolerant computing; faulty PDU; formal specification; HTTP; implementation robustness evaluation; Internet; network protocol; protocol data unit; protocol specification; robustness testing; SMTP protocol; stateful protocols; stateless protocols; Transport protocols

Assessment of inflow boundary conditions for compressible turbulent boundary layers - Xu,S.; Martin, M.P (Physics of Fluids, 2004)

Automated GUI regression testing using AI planning - Memon, Atif M. (Artificial Intelligence Methods in Software TestingArtificial Intelligence Methods in Software Testing, 2004)

Automatic video summarization for wireless and mobile environments - Yong Rao; Mundur, Padma; Yesha,Y. (2004 IEEE International Conference on Communications, 2004)
In this paper, we propose a novel video summarization technique using which we can automatically generate high quality video summaries suitable for wireless and mobile environments. The significant contribution of this paper lies in the proposed clustering scheme. We use Delaunay diagrams to cluster multidimensional point data corresponding to the frame contents of the video. In contrast to the existing clustering techniques used for summarization, our clustering algorithm is fully automatic and well suited for batch processing. We illustrate the quality of our clustering and summarization scheme in an experiment using several video clips.
Keywords: automatic video summarization; batch processing; batch processing (computers); Clustering algorithms; Clustering methods; clustering scheme; Computer science; Delaunay diagram; graph theory; Gunshot detection systems; Image sequences; mesh generation; Mobile computing; mobile radio; multidimensional point data cluster; Multidimensional systems; Multimedia communication; video clip; video frame content; Video sequences; video signal processing; wireless mobile environment

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

BorderGuard: detecting cold potatoes from peers - Feamster, Nick; Mao,Zhuoqing Morley; Rexford,Jennifer (Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, 2004)
Internet Service Providers often establish contractual "peering" agreements, where they agree to forward traffic to each other's customers at no cost. Consistent route advertisement at all peering points is a common provision in these agreements, because it gives an AS the flexibility to select egress points for the traffic (e.g., performing "hot potato" routing). Verifying "consistent export" is challenging because route advertisements are exchanged at multiple peering points and may be modified by routing policies. In this paper, we propose two algorithms to detect inconsistent routes using routing and configuration data from an AS's border routers. The first algorithm requires access to all eBGP routes advertised by a peer. Because this data is often unavailable, we propose another algorithm that detects inconsistencies using readily available data. We have applied our algorithms to the routes advertised by the peers of AT&T's commercial IP backbone. Although a peer may intentionally send inconsistent advertisements to prevent its neighbor from performing hot-potato routing, we also discuss several configuration scenarios where a peer may inadvertently advertise inconsistent routes, despite having consistent export policies. Finally, we explain how simple modifications to the routers could make detection of inconsistent advertisements much easier than it is today.
Keywords: anomalies; BGP; inconsistent advertisement; peering

Buffer merging—a powerful technique for reducing memory requirements of synchronous dataflow specifications - Murthy,P. K; Bhattacharyya, Shuvra S. (ACM Transactions on Design Automation of Electronic Systems (TODAES), 2004)

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

The case for separating routing from routers - Feamster, Nick; Balakrishnan,Hari; Rexford,Jennifer; Shaikh,Aman; van der Merwe,Jacobus (Proceedings of the ACM SIGCOMM workshop on Future directions in network architecture, 2004)
Over the past decade, the complexity of the Internet's routing infrastructure has increased dramatically. This complexity and the problems it causes stem not just from various new demands made of the routing infrastructure, but also from fundamental limitations in the ability of today's distributed infrastructure to scalably cope with new requirements.The limitations in today's routing system arise in large part from the fully distributed path-selection computation that the IP routers in an autonomous system (AS) must perform. To overcome this weakness, interdomain routing should be separated from today's IP routers, which should simply forward packets (for the most part). Instead, a separate Routing Control Platform (RCP) should select routes on behalf of the IP routers in each AS and exchange reachability information with other domains.Our position is that an approach like RCP is a good way of coping with complexity while being responsive to new demands and can lead to a routing system that is substantially easier to manage than today. We present a design overview of RCP based on three architectural principles path computation based on a consistent view of network state, controlled interactions between routing protocol layers, and expressive specification of routing policies and discuss the architectural strengths and weaknesses of our proposal.
Keywords: BGP; interdomain routing; routing architecture

The CBP Parameter: A Module Characterization Approach for DSP Software Optimization - Bhattacharyya, Shuvra S.; Murthy,P. K (The Journal of VLSI Signal Processing, 2004)

Challenges in selecting paths for navigational queries: Trade-off of benefit of path versus cost of plan - Vidal,M. E; Raschid, Louiqa; Mestre,J. (Proceedings of the 7th International Workshop on the Web and Databases: colocated with ACM SIGMOD/PODS 2004, 2004)

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

Compact procedural implementation in DSP software synthesis through recursive graph decomposition - Ko,M. Y; Murthy,P. K; Bhattacharyya, Shuvra S. (Software and compilers for embedded systems: 8th international workshop, SCOPES 2004, Amsterdam, The Netherlands, September 2-3, 2004: proceedings, 2004)

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

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

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

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

Developing testing techniques for event-driven pervasive computing applications - Memon, Atif M. (Proceedings of The OOPSLA 2004 workshop on Building Software for Pervasive Computing (BSPC 2004), 2004)

Dimensionality Estimation in Hyperspectral Imagery Using Minimum Description Length - Broadwater,Joshua B; Meth,Reuven; Chellapa, Rama (MARYLAND UNIV COLLEGE PARK CENTER FOR AUTOMATION RESEARCH, 2004)
Numerous algorithms have been developed for hyperspectral automatic target recognition (ATR) applications. Many of these algorithms require estimation of a background subspace. The estimation of the background subspace has been addressed using multiple methods. but most of these methods assume a-priori knowledge of the background dimensionality. In order to automate the estimation of the background subspace. we present an algorithm based on minimum description length (MDL) that can identify the background dimension. Results show that the MDL criterion estimates the proper dimension of the background for ATR applications.
Keywords: *ALGORITHMS; *HYPERSPECTRAL IMAGERY; *TARGET DETECTION; *TARGET RECOGNITION; AUTOMATIC; BURIED OBJECTS; COMPONENT REPORTS; MINE DETECTION; NUMERICAL MATHEMATICS; SURFACE TARGETS.; SYMPOSIA; TARGET DIRECTION, RANGE AND POSITION FINDING

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

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

DNS of hypersonic turbulent boundary layers - Martin, M.P; others (AIAA Paper, 2004)

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

Dynamic join-exit amortization and scheduling for time-efficient group key agreement - Mao,Yinian; Sun,Yan; M. Wu; Liu,K. J.R (INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies, 2004)
We propose a time-efficient contributory key agreement framework for secure communications in dynamic groups. The proposed scheme employs a special join-tree/exit-tree topology in the logical key tree and effectively exploits the efficiency of amortized operations. We derive the optimal parameters and design an activation algorithm for the join and exit trees. We also show that the asymptotic average time cost per user join and leave event is theta;(log (log n)), where n is the group size. Our experiment results on both simulated user activities and the real MBone data have shown that the proposed scheme outperforms the existing tree-based schemes.
Keywords: agreement; asymptotic; average; communication; complexity; computational; cost; cryptography; dynamic; group; join-tree/exit-tree; key; logical; Multicast; network; secure; security; special; Telecommunication; TIME; time-efficient; topology; tree

Empirical evaluation of the fault-detection effectiveness of smoke regression test cases for GUI-based software - Memon, Atif M.; Xie,Qing (Software Maintenance, 2004. Proceedings. 20th IEEE International Conference on, 2004)
Daily builds and smoke regression tests have become popular quality assurance mechanisms to detect defects early during software development and maintenance. In previous work, we addressed a major weakness of current smoke regression testing techniques, i.e., their lack of ability to automatically (re)test graphical user interface (GUI) event interactions - we presented a GUI smoke regression testing process called daily automated regression tester (DART). We have deployed DART and have found several interesting characteristics of GUI smoke tests that we empirically demonstrate in this paper. We also combine smoke tests with different types of test oracles and present guidelines for practitioners to help them generate and execute the most effective combinations of test-case length and test oracle complexity. Our experimental subjects consist of four GUI-based applications. We generate 5000-8000 smoke tests (enough to be run in one night) for each application. Our results show that: (1) short GUI smoke tests with certain test oracles are effective at detecting a large number of faults; (2) there are classes of faults that our smoke test cannot detect; (3) short smoke tests execute a large percentage of code; and (4) the entire smoke testing process is feasible to do in terms of execution time and storage space.
Keywords: daily automated regression tester; daily builds; fault-detection effectiveness; graphical user interface; Graphical user interfaces; GUI-based software; program testing; Quality assurance; Regression analysis; smoke regression test cases; software development; software fault tolerance; Software maintenance; Software quality; software quality assurance; test oracle complexity; test oracles; test-case length

Enabling On-chip Diversity Through Architectural Communication Design - Tudor Dumitras; Kerner, Sam; Marculescu, Radu (ASP-DAC '04 Proceedings of the 2004 Asia and South Pacific Design Automation Conference, 2004)
In this paper, we explore a new concept, called on-chip diversity, and introduce a design methodology for such emerging systems. Simply speaking, on-chip diversity means mixing different architectures and/or technologies in a multiple voltage/frequency island setup in order to achieve the highest levels of performance, fault-tolerance and the needed flexibility in SoC design. As the main contribution, we present the challenges in implementing an efficient communication architecture for on-chip diversity and outline a unified framework which addresses some of these issues. We then provide comparative experimental results and make a qualitative analysis of different architectural choices in the design of the on-chip communication. Having the acoustic beamforming as driver application, we show that an efficient communication infrastructure can be constructed by carefully analyzing the characteristics of the application and the required levels of power, performance and fault-tolerance.

End-to-end analysis of distributed video-on-demand systems - Mundur, Padma; Simon,R.; Sood,A. K (IEEE Transactions on Multimedia, 2004)
The focus of the research presented in this paper is the end-to-end analysis of a distributed Video-on-Demand (VoD) system. We analyze the distributed architecture of a VoD system to design global request handling and admission control strategies and evaluate them using global metrics. The performance evaluation methodology developed in this paper helps in determining efficient ways of using all resources in the VoD architecture within the constraints of providing guaranteed high quality service to each request. For instance, our simulation results show that request handling policies based on limited redirection of blocked requests to other resources perform better than load sharing policies. We also show that request handling policies based on redirection have simpler connection establishment semantics than load sharing policies and, therefore, are easily incorporated into reservation or signaling protocols.
Keywords: Admission control; admission control strategies; Analytical models; Computer science; distributed architecture; distributed video-on-demand systems; end-to-end analysis; global request handling; High-speed networks; Network servers; Next generation networking; Performance analysis; performance evaluation methodology; Protocols; request handling; reservation protocols; resource allocation; Resource management; signaling protocols; telecommunication congestion control; video on demand; Video sharing

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

Evaluating web page reliability across varied browsing environments - Eaton,C.; Memon, Atif M. (Proceedings of the 15th IEEE International Symposium on Software Reliability Engineering (ISSRE'04), 2004)
Web page reliability is significantly influenced by thebrowser, browser version, and operating system incorpo- rated in end-user browsing environments. The tool we have developed evaluates reliability of web-bound content across various client platforms based on the relationship between two key accessibility factors: (1) the HTML tags that struc- ture a given web page and (2) the support provided for each tag in target browsing environments. To optimize evaluation accuracy, we have designed a learning mechanism that in- ductively acquires knowledge of tag support criteria based on observed samples of accessible (properly rendered) and inaccessible (faulty) web page source code. Our contribu- tion is expected to provide web developers with a basis for maximizing audience reach through improved awareness of the browsing environment profiles associated with dimin- ished accessibility to their websites.

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

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

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

Ferret: a host vulnerability checking tool - Sharma,Anil; Martin,J.R.; Anand,N.; Michel Cukier; Sanders,W. H. (2004)
Evaluation of computing system security requires knowledge of the vulnerabilities present in the system and of potential attacks against the system. Vulnerabilities can be classified based on their location as application vulnerabilities, network vulnerabilities, or host vulnerabilities. We describe Ferret, a new software tool for checking host vulnerabilities. Ferret helps system administrators by quickly finding vulnerabilities that are present on a host. It is designed and implemented in a modular way: a different plug-in module is used for each vulnerability checked, and each possible output format is specified by a plug-in module. As a result, Ferret is extensible, and can easily be kept up-to-date through addition of checks for new vulnerabilities as they are discovered; the modular approach also makes it easy to provide specific configurations of Ferret tailored to specific operating systems or use environments. Ferret is a freely available open-source software implemented in Perl.
Keywords: Ferret software tool; host vulnerability checking tool; open-source software; Perl; plug-in module; program verification; security auditing tool; security evaluation; security of data; software tools

Finite-element computation of nonlinear magnetic diffusion and its effects when coupled to electrical, mechanical, and hydraulic systems - Brauer,J.R.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 2004)
Finite elements are used to compute eddy currents and magnetic diffusion times in steel cylinders with nonlinear B–H curves. Computations are made of diffusion times versus current in a typical axisymmetric magnetic actuator, showing good agreement with recently published approximate analytical formulas. The computed nonlinear diffusion times are then used to derive an equivalent resistor that is used in a model of an electrohydraulic system. The diffusion time causes delays in the coupled mechanical and hydraulic responses.
Keywords: actuator; actuators; analysis; axisymmetric; B-H; coupled; currents; curves; cylinders; diffusion; diffusion; eddy; electrical; electrohydraulic; electrohydraulics; electromagnetic; element; equivalent; finite; finite-element; flux; hydraulic; magnetic; mechanical; methods; nonlinear; resistor; responses; steel; system; systems; times; transducers

A game-theoretic framework for analyzing trust-inference protocols - Morselli,R.; Katz, Jonathan; Bhattacharjee, Bobby (Workshop on Economics of Peer-to-Peer Systems, 2004)
We propose a novel game-theoretic framework foranalyzing the robustness of trust-inference protocols in the presence of adversarial (but rational) users. To the best of our knowledge, this is the first such framework which simultaneously (1) admits a rigor- ous and precise definition, thereby enabling formal proofs of security (in various adversarial settings) for specific trust-inference protocols; (2) is flexible enough to accommodate a full range of (realistic) ad- versarial behavior and network models; and (3) is ap- propriate for decentralized networks, and in particu- lar does not posit a trusted, centralized party with complete knowledge of the system history. We also show some preliminary results regarding the design of trust-inference protocols which can be rigorously proven secure within our model. In addition to establishing a solid foundation for future work, our framework also enables a rigorous and objective comparison among existing trust inference protocols.

A generic construction for intrusion-resilient public-key encryption - Dodis,Y.; Franklin,M.; Katz, Jonathan; Miyaji,A.; Yung,M. (Topics in Cryptology–CT-RSA 2004, 2004)
In an intrusion-resilient cryptosystem [10], two entities (a user and a base) jointly evolve a secret decryption key; this provides very strong protection against an active attacker who can break into the user and base repeatedly and even simultaneously. Recently, a construction of an intrusion-resilient public-key encryption scheme based on specific algebraic assumptions has been shown [6]. We generalize this previous work and present a more generic construction for intrusion-resilient public-key encryption from any forward-secure public-key encryption scheme satisfying a certain homomorphic property.

Generic sentence fusion is an ill-defined summarization task - Daumé, Hal; Marcu,D. (Proceedings of the Text Summarization Branches Out Workshop at ACL, 2004)

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

A hybrid algorithm for subpixel detection in hyperspectral imagery - Broadwater, J.; Meth, R.; Chellapa, Rama (Geoscience and Remote Sensing Symposium, 2004. IGARSS '04. Proceedings. 2004 IEEE International, 2004)
Numerous subpixel detection algorithms utilizing structured backgrounds have been developed over the past few years. These range from detection schemes based on spectral unmixing to generalized likelihood ratio tests. Spectral unmixing algorithms such as the Fully Constrained Least Squares (FCLS) algorithm have the advantage of physically modeling the interactions of spectral signatures based on reflectance/emittance spectroscopy. Generalized likelihood ratio tests like the Adaptive Matched Subspace Detector (AMSD) have the advantage of identifying targets that are statistically different from the background. Therefore, a hybrid detector based on both AMSD and FCLS was developed to take advantage of each detector's strengths. Results demonstrate that the hybrid detector achieved the lowest false alarm rates while also producing meaningful abundance estimates
Keywords: alarm; algorithm; abundance; algorithm; Fully; algorithm; hybrid; algorithm; statistical; AMSD; Adaptive; analysis; structured; approximations; maximum; backgrounds; subpixel; constrained; detection; alarm; detection; target; Detector; FCLS; detector; hyperspectral; estimation; estimation; emittance; identification; adaptive; imagery; reflectance; least; likelihood; Matched; matching; least; processing; geophysical; rate; generalized; ratio; signal; signatures; spectral; spectra; false; spectra; spectral; squares; subspace; systems; geophysical; techniques; image; tests; hybrid; unmixing

Image hashing resilient to geometric and filtering operations - Swaminathan,A.; Mao,Yinian; M. Wu (Multimedia Signal Processing, 2004 IEEE 6th Workshop on, 2004)
Image hash functions provide compact representations of images, which is useful for search and authentication applications. In this work, we have identified a general three step framework and proposed a new image hashing scheme that achieves a better overall performance than the existing approaches under various kinds of image processing distortions. By exploiting the properties of discrete polar Fourier transform and incorporating cryptographic keys, the proposed image hash is resilient to geometric and filtering operations, and is secure against guessing and forgery attacks.
Keywords: compact; cryptographic; cryptography; discrete; distortion; Filtering; Fourier; function; geometric; hash; image; key; key; operation; polar; PROCESSING; public; representation; theory; transform; transforms

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

Improving browsing environment compliance evaluations for websites - Eaton,C.; Memon, Atif M. (Proceedings of the International Workshop on Web Quality (WQ'04), 2004)
Identifying accessibility issues that can threaten universal website usability is criticalfor web service and content providers who wish to accommodate the diverse web audience. Detecting page-to-environment incompliance and modifying pages to promote universal accessibility is one important step in improving the process of exploration and navigation in the web user experience. To address this issue, we have designed a system that evaluates the accessibility of a web page in a given browsing environment based on knowledge of the HyperText Markup Language (HTML) tags that comprise the page and knowledge of the tag support provided in respective browsing environments. Given this approach, one of the most important aspects of the system is the comprehensive nature of tag support knowledge. The more support rules known, the more environment-specific bugs the system can accurately identify. In order to optimize knowledge of tag support criteria, we have also incorporated a learning mechanism that can inductively determine HTML tags that are unsupported in a given environment by observing both positive and negative examples of web page appearance and behavior.

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

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

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

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

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

Intra-personal kernel space for face recognition - Zhou,Shaohua; Chellapa, Rama; Moghaddam, B. (Automatic Face and Gesture Recognition, 2004. Proceedings. Sixth IEEE International Conference on, 2004)
Intra-personal space modeling proposed by Moghaddam et al. has been successfully applied in face recognition. In their work the regular principal subspaces are derived from the intra-personal spacce using a principal componen analysis and embedded in a probabilistic formulation. In this paper, we derive the principal subspace from the intro-personal kernel space by developing a probabilistic analysis for kernel principal components for face recognition. We test this algorithm on a subset of the FERET database with illumination and facial expression variations. The recognition performance demonstrates its advantage over other traditional subspace approaches.
Keywords: analysis; component; Expression; Face; facial; illumination; intra-personal; Kernel; lighting; principal; probabilistic; probability; recognition; space; variation

Links and paths through life sciences data sources - Lacroix,Z.; Murthy,H.; Naumann,F.; Raschid, Louiqa (Data Integration in the Life Sciences, 2004)

Local Adaption and Dissipation Properties of a Weighted Essentially Non-Oscillatory Scheme - Taylor,E. M; Martin, M.P; Weirs,V. G (34th AIAA Fluid Dynamics Conference and Exhibit, 2004)
We perform several direct numerical simulations (DNS) of decaying isotropic turbulencewith various initial turbulent mach numbers Mt using a modifiedi weighted essentially non-oscillatory (WENO) method. We then present a procedure for the identification of shock-containing and smooth regions where the WENO scheme should respectively engage its adaption mechanism and revert to its linear optimal stencil. Weirsi has previously proposed the centrality index CI and nonlinearity index NI as two quantitative measures of stencil adaption, and we analyze these values within the regions of interest in the DNS flow fields. Our preliminary results indicate that these indices are suitable for assessments of the local adaption and dissipation properties of the WENO method; however, further studies must be conducted over a wider range of compressible flow conditions.

Managing the 802.11 energy/performance tradeoff with machine learning - Monteleoni,C.; Balakrishnan,H.; Feamster, Nick; Jaakkola,T. (Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory, 2004)
This paper addresses the problem of managing the tradeoff betweenenergy consumption and performance in wireless devices implementingthe IEEE 802.11 standard. To save energy, the 802.11 specificationproposes a power-saving mode (PSM), where a device can sleep to saveenergy, periodically waking up to receive packets from a neighbor(e.g., an access point) that may have buffered packets for thesleeping device. Previous work has shown that a fixed polling time forwaking up degrades the performance of Web transfers, because networkactivity is bursty and time-varying. We apply a new online machinelearning algorithm to this problem and show, using ns simulation andtrace analysis, that it is able to adapt well to network activity. Thelearning process makes no assumptions about the underlying networkactivity being stationary or even Markov. Our learning power-savingalgorithm, LPSM, guides the learning using a "loss function" thatcombines the increased latency from potentially sleeping too long andthe wasted use of energy in waking up too soon. In our nssimulations, LPSM saved 7%-20% more energy than 802.11 in power-savingmode, with an associated increase in average latency by a factor of1.02, and not more than 1.2. LPSM is straightforward to implementwithin the 802.11 PSM framework.

Mandarin-English Information (MEI): investigating translingual speech retrieval - Meng,Helen M.; Chen,Berlin; Khudanpur,Sanjeev; Levow,Gina-Anne; Lo,Wai-Kit; Oard, Douglas; Schone,Patrick; Tang,Karen; Wang,Hsin-Min; Wang,Jianqiang (Computer Speech & Language, 2004)
This paper describes the Mandarin–English Information (MEI) project, where we investigated the problem of cross-language spoken document retrieval (CL-SDR), and developed one of the first English–Chinese CL-SDR systems. Our system accepts an entire English news story (text) as query, and retrieves relevant Chinese broadcast news stories (audio) from the document collection. Hence, this is a cross-language and cross-media retrieval task. We applied a multi-scale approach to our problem, which unifies the use of phrases, words and subwords in retrieval. The English queries are translated into Chinese by means of a dictionary-based approach, where we have integrated phrase-based translation with word-by-word translation. Untranslatable named entities are transliterated by a novel subword translation technique. The multi-scale approach can be divided into three subtasks – multi-scale query formulation, multi-scale audio indexing (by speech recognition) and multi-scale retrieval. Experimental results demonstrate that the use of phrase-based translation and subword translation gave performance gains, and multi-scale retrieval outperforms word-based retrieval.
Keywords: English–Chinese cross-language spoken document retrieval; Multi-scale spoken document retrieval

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

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

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

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

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

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

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