Integrating categorical resource types into a P2P desktop grid system - Kim,Jik-Soo; Nam,Beomseok; Marsh,M.; Keleher,P.; Bhattacharjee, Bobby; Sussman, Alan (Grid Computing, 2008 9th IEEE/ACM International Conference on, 2008)
We describe and evaluate a set of protocols that implement a distributed, decentralized desktop grid. Incoming jobs are matched with system nodes through proximity in an N-dimensional resource space. This work improves on prior work by (1) efficiently accommodating node and job characterizations that include both continuous and categorical resource types, and (2) scaling gracefully to large system sizes even with highly non-uniform distributions of job and node types. We use extensive simulation results to show that the resulting system handles both continuous and categorical constraints efficiently, and that the new scalability techniques are effective.
Keywords: computing; peer-to-peer; computing; protocols; computing; protocols; scalability; desktop; Grid; grid; distributed; grid; peer-to-peer; N-dimensional; resource; space; P2P; system; categorical; technique; grid; types; decentralized

Learning Abstract Properties of Swarm Systems - Miner,D.; desJardins, Marie (Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, 2008)

Matchmaking and implementation issues for a P2P desktop grid - Marsh,M.; Kim,Jik-Soo; Nam,Beomseok; Jaehwan Lee; Ratanasanya,S.; Bhattacharjee, Bobby; Keleher,P.; Richardson,D.; Wellnitz,D. (Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on, 2008)
We present some recent and ongoing work in our decentralized desktop computing grid project. Specifically, we discuss matching jobs with compute nodes in a peer-to-peer grid of heterogeneous platforms, and the implementation of our algorithms in a concrete system.
Keywords: computing; computing; computing; peer-to-peer; desktop; grid; decentralized; grid; grid; grid; peer-to-peer; P2P

Maternal depletion of CTCF reveals multiple functions during oocyte and preimplantation embryo development - Wan,Le-Ben; Pan,Hua; Hannenhalli, Sridhar; Cheng,Yong; Ma,Jun; Fedoriw,Andrew; Lobanenkov,Victor; Latham,Keith E.; Schultz,Richard M.; Bartolomei,Marisa S. (Development, 2008)
CTCF is a multifunctional nuclear factor involved in epigenetic regulation. Despite recent advances that include the systematic discovery of CTCF-binding sites throughout the mammalian genome, the in vivo roles of CTCF in adult tissues and during embryonic development are largely unknown. Using transgenic RNAi, we depleted maternal stores of CTCF from growing mouse oocytes, and identified hundreds of misregulated genes. Moreover, our analysis suggests that CTCF predominantly activates or derepresses transcription in oocytes. CTCF depletion causes meiotic defects in the egg, and mitotic defects in the embryo that are accompanied by defects in zygotic gene expression, and culminate in apoptosis. Maternal pronuclear transfer and CTCF mRNA microinjection experiments indicate that CTCF is a mammalian maternal effect gene, and that persistent transcriptional defects rather than persistent chromosomal defects perturb early embryonic development. This is the first study detailing a global and essential role for CTCF in mouse oocytes and preimplantation embryos.

Measures and Risk Indicators for Early Insight into Software Safety. Development of Fault-Tolerant Systems - Basili, Victor R.; Marotta,Frank; Dangle,Kathleen; Esker,Linda; Rus,Ioana (ABERDEEN TEST CENTER MD, 2008)
Software contributes an ever-increasing level of functionality and control in today's systems. This increased use of software can dramatically increase the complexity and time needed to evaluate the safety of a system. Although the actual system safety cannot be verified during its development, measures can reveal early insights into potential safety problems and risks. An approach for developing early software safety measures is presented in this article. The approach and the example software measures presented are based on experience working with the safety engineering group on a large Department of Defense program.
Keywords: *SOFTWARE ENGINEERING; *SYSTEM SAFETY; COMPUTER PROGRAMMING AND SOFTWARE; fault tolerant computing; INDICATORS; measurement; REPRINTS; risk; SAFETY ENGINEERING

Model Based Design Verification: A Monitor Based Approach - Ackermann,Chris; Ray,Arnab; Cleaveland, Rance; Heit,Jürgen; Martin,Christopher; Shelton,Charles (SAE International, 2008)
This paper assesses the utility of an automated functional verification methodology in the design of a body electronics application. The use of design models as detailed specifications for software is gaining steady acceptance in the automotive industry because of the advantages it offers in terms of rapid system prototyping and automatic code generation. This paper argues that such modeling effort can also be used to provide support for design verification, so that errors may be pinpointed before they find their way into code, when they become much harder and more expensive to isolate, diagnose and repair.

Modeling Transfer Relationships Between Learning Tasks for Improved Inductive Transfer - Eaton,Eric; desJardins, Marie; Lane,Terran (Machine Learning and Knowledge Discovery in DatabasesMachine Learning and Knowledge Discovery in Databases, 2008)
In this paper, we propose a novel graph-based method for knowledge transfer. We model the transfer relationships between source tasks by embedding the set of learned source models in a graph using transferability as the metric. Transfer to a new problem proceeds by mapping the problem into the graph, then learning a function on this graph that automatically determines the parameters to transfer to the new learning task. This method is analogous to inductive transfer along a manifold that captures the transfer relationships between the tasks. We demonstrate improved transfer performance using this method against existing approaches in several real-world domains.

Morphological analysis of terrains based on discrete curvature and distortion - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Magillo,Paola (Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008)
In order to characterize the morphology of a triangulated terrain, we define several discrete estimators that mimic mean and Gaussian curvatures in the discrete case. We start from concentrated curvature, a discrete notion of Gaussian curvature for polyhedral surfaces, defined by Troyanov [7]. Since concentrated curvature does not depend on the local geometric shape of the terrain, we introduce Ccurvature that allows us to obtain discrete counterparts of both Gaussian and mean curvature. Finally, we define distortion, which behaves as an approximation of mean curvature. We apply all such measures to the analysis of the morphology of triangulated terrains.
Keywords: curvature; Morphology; terrain modeling

Multiple alternative sentence compressions and word-pair antonymy for automatic text summarization and recognizing textual entailment - Mohammad,S.; Dorr, Bonnie J; Egan,M.; Jimmy Lin; Zajic, David (Proceedings of the Text Analysis Conference (TAC-2008), Gaithersburg, MD, 2008)
The University of Maryland participatedin three tasks organized by the Text Anal- ysis Conference 2008 (TAC 2008): (1) the update task of text summarization; (2) the opinion task of text summariza- tion; and (3) recognizing textual entail- ment (RTE). At the heart of our summa- rization system is Trimmer, which gener- ates multiple alternative compressed ver- sions of the source sentences that act as candidate sentences for inclusion in the summary. For the first time, we investi- gated the use of automatically generated antonym pairs for both text summariza- tion and recognizing textual entailment. We used an antonymy feature in both the opinion summarization task and for rec- ognizing textual entailment. More coher- ent summaries resulted when using the antonymy feature as compared to when not using it. However, performance on ROUGE dropped. The RTE system per- formed almost equally well when using antonyms from WordNet and when using automatically generated antonyms.

NANO: Network Access Neutrality Observatory - Tariq,M.B.; Motiwala,M.; Feamster, Nick (Georgia Institute of Technology, 2008)
This paper tackles a technical problem that is of growing interest in light of the ongoing network neutrality debate: We aim to develop a system that can reliably determine whether particular ISP is discriminating against a service using only passive measurements from end-hosts. This problem presents significant challenges because many types of discrimination can often resemble commonplace performance degradations (e.g., resulting from failure or misconfiguration). To distinguish discrimination from degradation, we propose a statistical method to estimate causal effect and develop a system, NANO, based on this method. NANO aggregates passive measurements from end-hosts, stratifies the measurements to account for possible confounding factors, and distinguishes when an ISP is discriminating against a particular service or group of clients. Preliminary simulation results demonstrate the promise of NANO for both detecting various types of discrimination and absolving an ISP when it is not discriminating.

Nitric oxide production from surface recombination of oxygen and nitrogen atoms - Pejaković,D. A; Marschall,J.; Duan,L.; Martin, M.P (Journal of Thermophysics and Heat Transfer, 2008)

Optimal Cryptographic Hardness of Learning Monotone Functions - Dana Dachman-Soled; Lee, Homin K.; Malkin, Tal; Servedio, Rocco A.; Wan, Andrew; Wee, Hoeteck (Automata, Languages and Programming, 2008)
A wide range of positive and negative results have been established for learning different classes of Boolean functions from uniformly distributed random examples. However, polynomial-time algorithms have thus far been obtained almost exclusively for various classes of monotone functions, while the computational hardness results obtained to date have all been for various classes of general (nonmonotone) functions. Motivated by this disparity between known positive results (for monotone functions) and negative results (for nonmonotone functions), we establish strong computational limitations on the efficient learnability of various classes of monotone functions. We give several such hardness results which are provably almost optimal since they nearly match known positive results. Some of our results show cryptographic hardness of learning polynomial-size monotone circuits to accuracy only slightly greater than 1/2+1/n‾‾√1/2 + 1/\sqrt{n} ; this accuracy bound is close to optimal by known positive results (Blum et al., FOCS ’98). Other results show that under a plausible cryptographic hardness assumption, a class of constant-depth, sub-polynomial-size circuits computing monotone functions is hard to learn; this result is close to optimal in terms of the circuit size parameter by known positive results as well (Servedio, Information and Computation ’04). Our main tool is a complexity-theoretic approach to hardness amplification via noise sensitivity of monotone functions that was pioneered by O’Donnell (JCSS ’04).
Keywords: Data structures; Data Structures, Cryptology and Information Theory; Discrete Mathematics in Computer Science; Numeric Computing; Software Engineering/Programming and Operating Systems; Theory of computation

An Optimal Incremental Algorithm for Minimizing Lateness with Rejection - Khuller, Samir; Mestre,J. (Algorithms-ESA 2008, 2008)
This paper re-examines the classical problem of minimizing maximum lateness which is defined as follows: given a collection of n jobs with processing times and due dates, in what order should they be processed on a single machine to minimize maximum lateness? The lateness of a job is defined as its completion time minus its due date. This problem can be solved easily by ordering the jobs in non-decreasing due date order. We now consider the following question: which subset of k jobs should we reject to reduce the maximum lateness by the largest amount? While this problem can be solved optimally in polynomial time, we show the following surprising result: there is a fixed permutation of the jobs, such that for all k, if we reject the first k jobs from this permutation, we derive an optimal solution for the problem in which we are allowed to reject k jobs. This allows for an incremental solution in which we can keep incrementally rejecting jobs if we need a solution with lower maximum lateness value. Moreover, we also develop an optimal O(n logn) time algorithm to find this permutation.

Path splicing - Motiwala,Murtaza; Elmore,Megan; Feamster, Nick; Vempala,Santosh (SIGCOMM Comput. Commun. Rev., 2008)
We present path splicing, a new routing primitive that allows network paths to be constructed by combining multiple routing trees ("slices") to each destination over a single network topology. Path splicing allows traffic to switch trees at any hop en route to the destination. End systems can change the path on which traffic is forwarded by changing a small number of additional bits in the packet header. We evaluate path splicing for intradomain routing using slices generated from perturbed link weights and find that splicing achieves reliability that approaches the best possible using a small number of slices, for only a small increase in latency and no adverse effects on traffic in the network. In the case of interdomain routing, where splicing derives multiple trees from edges in alternate backup routes, path splicing achieves near-optimal reliability and can provide significant benefits even when only a fraction of ASes deploy it. We also describe several other applications of path splicing, as well as various possible deployment paths.
Keywords: multi-path routing; path diversity; path splicing

Position Paper: Improving Browsing Environment Compliance Evaluations for Websites - Eaton,C.; Memon, Atif M. (Relation, 2008)
Though it would be ideal for web pages to render and function con-sistently across heterogeneous browsing environments, the browser, browser version, and operating system used to navigate and interact with web content is known to have a significant impact on the subsequent level of user accessibil- ity. While research endeavors directed toward improving web accessibility have generally focused on addressing usability issues for individuals with physical limitations, providing accessible information and services for the en- tire web population also encompasses addressing the limitations of devices and platforms used to deploy web pages. We propose that more research be in- vested in the latter issue to facilitate the development of effective tools for de- tecting browsing environment influenced usability issues before inaccessible pages are released in the field.

Relationships between Test Suites, Faults, and Fault Detection in GUI Testing - Strecker,J.; Memon, Atif M. (Software Testing, Verification, and Validation, 2008 1st International Conference on, 2008)
Software-testing researchers have long sought recipes for test suites that detect faults well. In the literature, empirical studies of testing techniques abound, yet the ideal technique for detecting the desired kinds of faults in a given situation often remains unclear. This work shows how understanding the context in which testing occurs, in terms of factors likely to influence fault detection, can make evaluations of testing techniques more readily applicable to new situations. We present a methodology for discovering which factors do statistically affect fault detection, and we perform an experiment with a set of test-suite- and fault-related factors in the GUI testing of two fielded, open-source applications. Statement coverage and GUI-event coverage are found to be statistically related to the likelihood of detecting certain kinds of faults.
Keywords: Fault detection; fault-related factors; Graphical user interfaces; GUI testing; program testing; software-testing; test suites; test-suite-related factors

Resolving arthropod phylogeny: exploring phylogenetic signal within 41 kb of protein-coding nuclear gene sequence - Regier,J. C; Shultz,J. W; Ganley,A. R.D; Hussey,A.; Shi,D.; Ball,B.; Zwick,A.; Stajich,J. E; Cummings, Michael P.; Martin,J. W; Cunningham,CW (Syst Biol, 2008)
This study attempts to resolve relationships among and within the four basal arthropod lineages (Pancrustacea, Myriapoda, Euchelicerata, Pycnogonida) and to assess the widespread expectation that remaining phylogenetic problems will yield to increasing amounts of sequence data. Sixty-eight regions of 62 protein-coding nuclear genes (approximately 41 kilobases (kb)/taxon) were sequenced for 12 taxonomically diverse arthropod taxa and a tardigrade outgroup. Parsimony, likelihood, and Bayesian analyses of total nucleotide data generally strongly supported the monophyly of each of the basal lineages represented by more than one species. Other relationships within the Arthropoda were also supported, with support levels depending on method of analysis and inclusion/exclusion of synonymous changes. Removing third codon positions, where the assumption of base compositional homogeneity was rejected, altered the results. Removing the final class of synonymous mutations–first codon positions encoding leucine and arginine, which were also compositionally heterogeneous–yielded a data set that was consistent with a hypothesis of base compositional homogeneity. Furthermore, under such a data-exclusion regime, all 68 gene regions individually were consistent with base compositional homogeneity. Restricting likelihood analyses to nonsynonymous change recovered trees with strong support for the basal lineages but not for other groups that were variably supported with more inclusive data sets. In a further effort to increase phylogenetic signal, three types of data exploration were undertaken. (1) Individual genes were ranked by their average rate of nonsynonymous change, and three rate categories were assigned–fast, intermediate, and slow. Then, bootstrap analysis of each gene was performed separately to see which taxonomic groups received strong support. Five taxonomic groups were strongly supported independently by two or more genes, and these genes mostly belonged to the slow or intermediate categories, whereas groups supported only by a single gene region tended to be from genes of the fast category, arguing that fast genes provide a less consistent signal. (2) A sensitivity analysis was performed in which increasing numbers of genes were excluded, beginning with the fastest. The number of strongly supported nodes increased up to a point and then decreased slightly. Recovery of Hexapoda required removal of fast genes. Support for Mandibulata (Pancrustacea + Myriapoda) also increased, at times to "strong" levels, with removal of the fastest genes. (3) Concordance selection was evaluated by clustering genes according to their ability to recover Pancrustacea, Euchelicerata, or Myriapoda and analyzing the three clusters separately. All clusters of genes recovered the three concordance clades but were at times inconsistent in the relationships recovered among and within these clades, a result that indicates that the a priori concordance criteria may bias phylogenetic signal in unexpected ways. In a further attempt to increase support of taxonomic relationships, sequence data from 49 additional taxa for three slow genes (i.e., EF-1 alpha, EF-2, and Pol II) were combined with the various 13-taxon data sets. The 62-taxon analyses supported the results of the 13-taxon analyses and provided increased support for additional pancrustacean clades found in an earlier analysis including only EF-1 alpha, EF-2, and Pol II.

A Scalable Projective Bundle Adjustment Algorithm using the L infinity Norm - Mitra, K.; Chellapa, Rama (Computer Vision, Graphics Image Processing, 2008. ICVGIP '08. Sixth Indian Conference on, 2008)
The traditional bundle adjustment algorithm for structure from motion problem has a computational complexity of O((m+n)3) per iteration and memory requirement of O(mn(m+n)), where m is the number of cameras and n is the number of structure points. The sparse version of bundle adjustment has a computational complexity of O(m3+mn) per iteration and memory requirement of O(mn). Here we propose an algorithm that has a computational complexity of O(mn(radicm+radicn)) per iteration and memory requirement of O(max(m,n)). The proposed algorithm is based on minimizing the Linfin norm of reprojection error. It alternately estimates the camera and structure parameters, thus reducing the potentially large scale optimization problem to many small scale subproblems each of which is a quasi-convex optimization problem and hence can be solved globally. Experiments using synthetic and real data show that the proposed algorithm gives good performance in terms of minimizing the reprojection error and also has a good convergence rate.
Keywords: adjustment; algorithm; structure; bundle; complexity; convex; complexity; iteration; error; scalable; estimation; estimation; cameras; computational; Linfin; method; large; methods; parameter; norm; camera; computational; OPTIMIZATION; parameter; problem; memory; problem; projection; problem; reprojection; programming; image; projective; reconstruction; iterative; reconstruction; quasiconvex; requirement; motion; scale

Searching Electronic Health Records for Temporal Patterns in Patient Histories: A Case Study with Microsoft Amalga - Plaisant, Catherine; Lam,Stanley; Shneiderman, Ben; Smith,Mark S.; Roseman,David; Marchand,Greg; Gillam,Michael; Feied,Craig; Handler,Jonathan; Rappaport,Hank (AMIA Annual Symposium ProceedingsAMIA Annu Symp Proc, 2008)
As electronic health records (EHR) become more widespread, they enable clinicians and researchers to pose complex queries that can benefit immediate patient care and deepen understanding of medical treatment and outcomes. However, current query tools make complex temporal queries difficult to pose, and physicians have to rely on computer professionals to specify the queries for them. This paper describes our efforts to develop a novel query tool implemented in a large operational system at the Washington Hospital Center (Microsoft Amalga, formerly known as Azyxxi). We describe our design of the interface to specify temporal patterns and the visual presentation of results, and report on a pilot user study looking for adverse reactions following radiology studies using contrast.

Seasonal Cholera from Multiple Small Outbreaks, Rural Bangladesh - Stine,O. Colin; Alam,Munirul; Tang,Li; Nair,G. Balakrish; Siddique,A. Kasem; Faruque,Shah M.; Huq,Anwar; Rita R Colwell; Sack,R. Bradley; Morris,J. Glenn (Emerging Infectious DiseasesEmerg Infect Dis, 2008)
Clinical and environmental Vibrio cholerae organisms collected from February 2004 through April 2005 were systematically isolated from 2 rural Bangladeshi locales. Their genetic relatedness was evaluated at 5 loci that contained a variable number of tandem repeats (VNTR). The observed minimal overlap in VNTR patterns between the 2 communities was consistent with sequential, small outbreaks from local sources.

Securing enterprise networks using traffic tainting - Ramachandran,A.; Mundada,Y.; Tariq,M.B.; Feamster, Nick (Special Interest Group on Data Communication, 2008)
Enterprise networks are vulnerable to attacks ranging from dataleaks to the spread of malware to insider threats. Previous defenses have largely focused on securing hosts; unfortunately, when hosts are compromised, these defenses become ineffective. Rather than attempting to harden the host against every possible attack (which is impractical) or constraining the software that can run on a host (which is inconvenient), we place a small amount of trusted code on the host to assist with tracking the provenance of network traf- fic, moving the rest of the trust and function to the network. We present Pedigree, a system that tracks information flow across pro- cesses and hosts within a network by annotating traffic with taints that reflect the process that generated the traffic and the inputs that process has taken (we call this function traffic tainting). A tagger on the host annotates network traffic with information about the “taints” that the sending process has acquired. Network devices act as arbiters to take appropriate actions (e.g., blocking) based on the taints associated with the traffic and the enterprise network’s secu- rity policy. We have implemented Pedigree’s host-based tagger as a Linux kernel module and the arbiter using the OpenFlow platform. This demonstration presents a prototype deployment of Pedigree that identifies and prevents both sensitive data leaks and the spread of malware in a typical enterprise network setting. The demon- stration will show that Pedigree can defend against these attacks without significant overhead at the host or the filtering device.

Sequence diversity and evolution of multigene families in Trypanosoma cruzi - Cerqueira,Gustavo C.; Bartholomeu,Daniella C.; DaRocha,Wanderson D.; Hou,Lihua; Freitas-Silva,Danielle M.; Machado,Carlos Renato; El‐Sayed, Najib M.; Teixeira,Santuza M.R. (Molecular and Biochemical Parasitology, 2008)
Several copies of genes belonging to three multigene families present in the genome of Trypanosoma cruzi were sequenced and comparatively analyzed across six different strains of the parasite belonging to the T. cruzi I lineage (Colombiana, Silvio X10 and Dm28c), the T. cruzi II lineage (Esmeraldo and JG) and a hybrid strain (CL Brener). For all three gene families analyzed, our results support the division in T. cruzi I and II lineages. Furthermore, in agreement with its hybrid nature, sequences derived from the CL Brener clone clustered together with T. cruzi II sequences as well as with a third group of sequences. Paralogous sequences encoding Amastin, an amastigote surface glycoprotein and TcAG48, an antigenic RNA binding protein, which are clustered in the parasite genome, present higher intragenomic variability in T. cruzi II and CL Brener strains, when compared to T. cruzi I strains. Paralogous sequences derived from the TcADC gene family, which encode various isoforms of adenylyl cyclases and are dispersed throughout the T. cruzi genome, exhibit similar degree of variability in all strains, except in the CL Brener strain, in which the sequences were more divergent. Several factors including mutation rates and gene conversion mechanisms, acting differently within the T. cruzi population, may contribute to create such distinct levels of sequence diversity in multigene families that are clustered in the T. cruzi genome.
Keywords: Amastin; Gene conversion; Genetic diversity; Multigene families; Trypanosoma cruzi

Sex and Age Dimorphism of Myocardial Gene Expression in Nonischemic Human Heart Failure - Fermin,David R.; Barac,Ana; Lee,Sangjin; Polster,Sean P.; Hannenhalli, Sridhar; Bergemann,Tracy L.; Grindle,Suzanne; Dyke,David B.; Pagani,Francis; Miller,Leslie W.; Tan,Sarah; dos Remedios,Cris; et al. (Circulation: Cardiovascular Genetics, 2008)
Background— We report the first comprehensive analysis of gene expression differences by sex and age in left ventricular samples from 102 patients with dilated cardiomyopathy.Methods and Results— Gene expression data (HG-U133A gene chip, Affymetrix) were analyzed from 30 females and 72 males from 3 separate centers. More than 1800 genes displayed sexual dimorphism in the heart (adjusted P value <0.05). A significant number of these genes were highly represented in gene ontology pathways involved in ion transport and G-protein-coupled receptor signaling. Localization of these genes revealed enrichment on both the sex chromosomes as well as chromosomes 3, 4, and 14. The second goal of this study was to determine the effect of age on gene expression. Within the female cohort, >140 genes were differentially expressed in the <55 years age group compared with the >55 years age group. These genes were highly represented in gene ontology pathways involved in DNA damage. In contrast, zero genes in the male cohort <55 years met statistical significance when compared with the >55 years age group.Conclusions— Gene expression in dilated cardiomyopathy displayed evidence of sexual dimorphism similar to other somatic tissues and age dimorphism within the female cohort.

Soft syntactic constraints for hierarchical phrased-based translation - Marton,Y.; Resnik, Philip (Proceedings of ACL-08: HLT, 2008)

The soma terror organization portal (stop): Social network and analytic tools for the real-time analysis of terror groups - Martinez,V.; Simari,G.; Sliva,A.; V.S. Subrahmanian (First Intl. Workshop on Social Computing, Behavioral Modeling and Prediction, 2008)
Stochastic Opponent Modeling Agents (SOMA) have been proposed as a paradigm for reasoning about cultural groups, terror groups, and other socioeconomic-political-military organizations worldwide. In this paper, we describe the SOMA Terror Organization Portal (STOP). STOP provides a single point of contact through which analysts may access data about terror groups world wide. In order to analyze this data, SOMA provides three major components: the SOMA Extraction Engine (SEE), the SOMA Adversarial Forecast Engine (SAFE), and the SOMA Analyst NEtwork (SANE) that allows analysts to find other analysts doing similar work, share findings with them, and let consensus findings emerge. This paper describes the STOP framework.

The SOMA Terror Organization Portal (STOP): social network and analytic tools for the real-time analysis of terror groups - Sliva,A.; V.S. Subrahmanian; Martinez,V.; Simari,G. I (Social Computing, Behavioral Modeling, and Prediction, 2008)
Stochastic Opponent Modeling Agents (SOMA) have been proposed as a paradigm for reasoning about cultural groups, terror groups, and other socioeconomic-political-military organizations worldwide. In this paper, we describe the SOMA Terror Organization Portal (STOP). STOP provides a single point of contact through which analysts may access data about terror groups world wide. In order to analyze this data, SOMA provides three major components: the SOMA Extraction Engine (SEE), the SOMA Adversarial Forecast Engine (SAFE), and the SOMA Analyst NEtwork (SANE) that allows analysts to find other analysts doing similar work, share findings with them, and let consensus findings emerge. This paper describes the STOP framework.

Space-time tradeoffs for proximity searching in doubling spaces - Arya,S.; Mount, Dave; Vigneron,A.; Xia,J. (Algorithms-ESA 2008, 2008)
We consider approximate nearest neighbor searching in metric spaces of constant doubling dimension. More formally, we are given a set S of n points and an error bound ε> 0. The objective is to build a data structure so that given any query point q in the space, it is possible to efficiently determine a point of S whose distance from q is within a factor of (1 + ε) of the distance between q and its nearest neighbor in S. In this paper we obtain the following space-time tradeoffs. Given a parameter γ ∈ [2,1/ε], we show how to construct a data structure of space nO(dim)log(1) space that can answer queries in time O(log(n))+(1())O(dim) . This is the first result that offers space-time tradeoffs for approximate nearest neighbor queries in doubling spaces. At one extreme it nearly matches the best result currently known for doubling spaces, and at the other extreme it results in a data structure that can answer queries in time O(log(n/ε)), which matches the best query times in Euclidean space. Our approach involves a novel generalization of the AVD data structure from Euclidean space to doubling space.

Stochastic opponent modeling agents: A case study with Hamas - Mannes,A.; Sliva,A.; V.S. Subrahmanian; Wilkenfeld,J. (Proceedings of ICCCD, 2008)
Stochastic Opponent Modeling Agents (SOMA) have beenproposed as a paradigm for reasoning about cultural groups, terror groups, and other socio-economic-political-military organizations worldwide. In this paper, we describe a case study that shows how SOMA was used to model the behavior of the terrorist organization, Hamas. Our team, consisting of a mix of computer scientists, policy experts, and political scientists, were able to understand new facts about Hamas of which even seasoned Hamas experts may not have been aware. This paper briefly overviews SOMA rules, explains how several thousand SOMA rules for Hamas were automatically derived, and then describes a few key findings about Hamas, enabled by this framework.

Streaming algorithms for k-center clustering with outliers and with anonymity - Matthew McCutchen,R.; Khuller, Samir (Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 2008)
Clustering is a common problem in the analysis of large data sets. Streaming algorithms, which make a single pass over the data set using small working memory and produce a clustering comparable in cost to the optimal offline solution, are especially useful. We develop the first streaming algorithms achieving a constant-factor approximation to the cluster radius for two variations of the k-center clustering problem. We give a streaming (4 + ε)-approximation algorithm using O(ε − 1 kz) memory for the problem with outliers, in which the clustering is allowed to drop up to z of the input points; previous work used a random sampling approach which yields only a bicriteria approximation. We also give a streaming (6 + ε)-approximation algorithm using O(ε − 1 ln (ε − 1) k + k 2) memory for a variation motivated by anonymity considerations in which each cluster must contain at least a certain number of input points.

Structural Sampling for Statistical Software Testing - Baskiotis,N.; Sebag,M.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)
Structural Statistical Software Testing exploits the control flow graph of the program being tested to construct test cases. While test cases can easily be extracted from {em feasible paths} in the control flow graph, that is, paths which are actually exerted for some values of the program input, the feasible path region is a tiny fraction of the graph paths (less than $10^{-5}]$ for medium size programs). The S4T algorithm presented in this paper aims to address this limitation; as an Active Relational Learning Algorithm, it uses the few feasible paths initially available to sample new feasible paths. The difficulty comes from the non-Markovian nature of the feasible path concept, due to the long-range dependencies between the nodes in the control flow graph. Experimental validation on real-world and artificial problems demonstrates significant improvements compared to the state of the art.

Structured machine learning: the next ten years - Dietterich,T. G; Domingos,P.; Getoor, Lise; Muggleton,S.; Tadepalli,P. (Machine Learning, 2008)
The field of inductive logic programming (ILP) has made steady progress, since the first ILP workshop in 1991, based on a balance of developments in theory, implementations and applications. More recently there has been an increased emphasis on Probabilistic ILP and the related fields of Statistical Relational Learning (SRL) and Structured Prediction. The goal of the current paper is to consider these emerging trends and chart out the strategic directions and open problems for the broader area of structured machine learning for the next 10 years.

The swarm application framework - Miner,D.; desJardins, Marie (In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (Student Abstract, 2008)
The Swarm Application Framework (SAF) is a tool that makes the development of swarm applications more intuitive. Traditionally, swarm applications are created by programming several low-level rules. This approach leads to several problems in designing and testing swarms, which serve as inspiration for the features of SAF. SAF encourages a new paradigm for designing swarm applications: engineers can interact with a swarm at the abstract (swarm) level instead of the individual (agent) level. In this paper, we discuss the design of the framework, how agents and rules in SAF operate, and a planned rule abstraction feature.

TERp system description - Snover,M.; Madnani,N.; Dorr, Bonnie J; Schwartz,R. (MetricsMATR workshop at AMTA, 2008)
This paper describes TER-Plus (TERp) the University of Maryland / BBN Technologies submission for the NIST Metric MATR 2008 workshop on automatic machine translation evaluation metrics. TERp is an extension of Translation Edit Rate (TER) that builds off of the success of TER as an evaluation metric and alignment tool while addressing several of its weaknesses through the use of paraphrases, morphological stemming, and synonyms, as well as edit costs that are optimized to correlate better with various types of human judgments.

Test case generator for GUITAR - Hackner,Daniel R.; Memon, Atif M. (Companion of the 30th international conference on Software engineering, 2008)
As GUIs become more popular, the need for GUI testing tools becomes greater. Many current GUI test generation techniques require proprietary tools and can be hard to use to their fullest potential. This paper outlines a new test case generation strategy, which enables testers to automatically produce cases in a widely used format. We hope that this strategy will encourage more complete GUI testing.
Keywords: code coverage; event-flow; Graphical user interfaces; gui ripping; integration tree; jfcunit; junit; Test Case Generation

Tradeoffs in Approximate Range Searching Made Simpler - Arya,S.; Fonseca,G.; Mount, Dave (Computer Graphics and Image Processing, 2008. SIBGRAPI '08. XXI Brazilian Symposium on, 2008)
Range searching is a fundamental problem in computational geometry. The problem involves preprocessing a set of n points in R^d into a data structure, so that it is possible to determine the subset of points lying within a given query range. In approximate range searching, a parameter eps epsiv gt; 0 is given, and for a given query range R the points lying within distance eps diam(R) of the range's boundary may be counted or not. In this paper we present three results related to the issue of tradeoffs in approximate range searching. First, we introduce the range sketching problem. Next, we present a space-time tradeoff for smooth convex ranges, which generalize spherical ranges. Finally, we show how to modify the previous data structure to obtain a space-time tradeoff for simplex ranges. In contrast to existing results, which are based on relatively complex data structures, all three of our results are based on simple, practical data structures.
Keywords: approximate range searching; computational geometry; data structure; Data structures; query range

Trade-offs in matching jobs and balancing load for distributed desktop grids - Kim,Jik-Soo; Nam,Beomseok; Keleher,Peter; Marsh,Michael; Bhattacharjee, Bobby; Sussman, Alan (Future Generation Computer Systems, 2008)
Desktop grids can achieve tremendous computing power at low cost through opportunistic sharing of resources. However, traditional client–server Grid architectures do not deal with all types of failures, and do not always cope well with very dynamic environments. This paper describes the design of a desktop grid implemented over a modified Peer-to-Peer (P2P) architecture. The underlying P2P system is decentralized and inherently adaptable, giving the Grid robustness, scalability, and the ability to cope with dynamic environments, while still efficiently mapping application instances to available resources throughout the system.We use simulation to compare three different types of matching algorithms under differing workloads. Overall, the P2P approach produces significantly lower wait times than prior approaches, while adapting efficiently to the dynamic environment.
Keywords: Desktop grid; load balancing; Matchmaking; peer-to-peer computing; Resource discovery

Trellis: a platform for building flexible, fast virtual networks on commodity hardware - Bhatia,Sapan; Motiwala,Murtaza; Muhlbauer,Wolfgang; Mundada,Yogesh; Valancius,Vytautas; Bavier,Andy; Feamster, Nick; Peterson,Larry; Rexford,Jennifer (Proceedings of the 2008 ACM CoNEXT Conference, 2008)
We describe Trellis, a platform for hosting virtual networks on shared commodity hardware. Trellis allows each virtual network to define its own topology, control protocols, and forwarding tables, while amortizing costs by sharing the physical infrastructure. Trellis synthesizes two container-based virtualization technologies, VServer and NetNS, as well as a new tunneling mechanism, EGRE, into a coherent platform that enables high-speed virtual networks. We describe the design and implementation of Trellis and evaluate its packet-forwarding rates relative to other virtualization technologies and native kernel forwarding performance.

Upstream and downstream in unsteadiness of STBLI using DNS data in two con gurations - Martin, M.P; Priebe,S.; Wu,M. (46th AIAA Aerospace Sciences Meeting, 2008)
Statistical analysis of the upstream and downstream flow influence on shock unsteadiness in shock and turbulent boundary layer interactions are performed using DNS data of a compression corner Wu & Martin1 and a reflected shock case interaction. For both cases, the scaling proposed by Dussauge et al.2 for the characteristic low frequency applies. The statistical analysis for the compression corner shows that the unsteadiness of the shock is dominated by the downstream flow. The same analysis applied to the reflected shock case also indicates downstream influence. Additional studies are required to fully characterize the reflected shock case DNS data.

Upstream and downstream influence on the unsteadiness of STBLI using DNS data in two configurations - Martin, M.P; Priebe,S.; Wu,M. (AIAA Paper 2008-0719, 46, h, 2008)

Using a pilot study to derive a GUI model for automated testing - Xie,Qing; Memon, Atif M. (ACM Transactions on Software Engineering and Methodology (TOSEM), 2008)
Graphical user interfaces (GUIs) are one of the most commonly used parts of today's software. Despite their ubiquity, testing GUIs for functional correctness remains an understudied area. A typical GUI gives many degrees of freedom to an end-user, leading to an enormous input event interaction space that needs to be tested. GUI test designers generate and execute test cases (modeled as sequences of user events) to traverse its parts; targeting a subspace in order to maximize fault detection is a nontrivial task. In this vein, in previous work, we used informal GUI code examination and personal intuition to develop an event-interaction graph (EIG). In this article we empirically derive the EIG model via a pilot study, and the resulting EIG validates our intuition used in previous work; the empirical derivation process also allows for model evolution as our understanding of GUI faults improves. Results of the pilot study show that events interact in complex ways; a GUI's response to an event may vary depending on the context established by preceding events and their execution order. The EIG model helps testers to understand the nature of interactions between GUI events when executed in test cases and why certain events detect faults, so that they can better traverse the event space. New test adequacy criteria are defined for the EIG; new algorithms use these criteria and EIG to systematically generate test cases that are shown to be effective on four fielded open-source applications.
Keywords: Graphical user interfaces; model-based testing; test minimization; Test suite management

Validation of a DNS code for wall-bounded turbulence including finite-rate reactions and surface catalysis - Duan,L.; Martin, M.P (AIAA Paper 2008, 2008)
This paper discusses the constitutive relations, surface catalytic model,and numerical methods for direct numerical simulation (DNS) of wall- bounded turbulence including finite-rate chemistry and gas-surface in- teraction. The validation of the code is provided for the mean flow by comparison to similarity solutions and laminar hypersonic boundary layer solutions, for the surface catalysis by comparison to analytic solutions for the one-dimensional diffusion-reaction equation, and for turbulent bound- ary layers by comparison to empirical predictions.

Variational Bayes via Propositionalization - Sato,T.; Kameya,Y.; Kurihara,K.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Kersting,K.; Muggleton,S. H (Probabilistic, Logical and Relational Learning-A Further Synthesis, 2008)

Vibrio cholerae non‐O1, non‐O139 strains isolated before 1992 from Varanasi, India are multiple drug resistant, contain intSXT, dfr18 and aadA5 genes - Mohapatra,Harapriya; Mohapatra,Saswat S.; Mantri,Chinmay K.; Rita R Colwell; Singh,Durg V. (Environmental Microbiology, 2008)
In this study, we report the presence of the SXT element and Class I integron in Vibrio cholerae non-O1, non-O139 strains isolated from Varanasi, India. Isolates were resistant to cotrimoxazole, trimethoprim and/or streptomycin, furazolidone and ampicillin. None contained plasmids. Polymerase chain reaction (PCR) and DNA sequencing revealed the presence of antibiotic resistance gene cassettes, aadA1, aadA2, aadA5 and dfrA15, in the Class I integron and SXT, an integrative conjugative element containing dfr18, sulII and strAB, in three and six of the isolates respectively. Conjugation experiments, followed by PCR analysis of transconjugants, provided evidence for the transferable nature of intSXT and associated antibiotic resistance gene cassettes. This is the first report of the occurrence of SXT ICE, dfr18, sulII, strAB and aadA5 genes in environmental V. cholerae non-O1, non-O139 strains from Varanasi, India, that had been isolated before 1992.

Why Do Hubs in the Yeast Protein Interaction Network Tend To Be Essential: Reexamining the Connection between the Network Topology and Essentiality - Zotenko,Elena; Mestre,Julian; O'Leary, Dianne P.; Przytycka,Teresa M. (PLoS Comput BiolPLoS Comput Biol, 2008)
Analysis of protein interaction networks in the budding yeast Saccharomyces cerevisiae has revealed that a small number of proteins, the so-called hubs, interact with a disproportionately large number of other proteins. Furthermore, many hub proteins have been shown to be essential for survival of the cell—that is, in optimal conditions, yeast cannot grow and multiply without them. This relation between essentiality and the number of neighbors in the protein–protein interaction network has been termed the centrality-lethality rule. However, why are such hubs essential? Jeong and colleagues [1] suggested that overrepresentation of essential proteins among high-degree nodes can be attributed to the central role that hubs play in mediating interactions among numerous, less connected proteins. Another view, proposed by He and Zhang, suggested that that the majority of proteins are essential due to their involvement in one or more essential protein–protein interactions that are distributed uniformly at random along the network edges [2]. We find that none of the above reasons determines essentiality. Instead, the majority of hubs are essential due to their involvement in Essential Complex Biological Modules, a group of densely connected proteins with shared biological function that are enriched in essential proteins. This study sheds new light on the topological complexity of protein interaction networks.

Aggregates in Generalized Temporally Indeterminate Databases - Udrea,Octavian; Majkić,Zoran; Subrahmanian,V. (Scalable Uncertainty ManagementScalable Uncertainty Management, 2007)
Dyreson and Snodgrass as well as Dekhtyar et. al. have provided a probabilistic model (as well as compelling example applications) for why there may be temporal indeterminacy in databases. In this paper, we first propose a formal model for aggregate computation in such databases when there is uncertainty not just in the temporal attribute, but also in the ordinary (non-temporal) attributes. We identify two types of aggregates: event correlated aggregates, and non event correlated aggregations, and provide efficient algorithms for both of them. We prove that our algorithms are correct, and we present experimental results showing that the algorithms work well in practice.
Keywords: Computer; Science

Agile Quality Assurance Techniques for GUI-Based Applications - Memon, Atif M.; Xie,Q. (Agile software development quality assuranceAgile software development quality assurance, 2007)

Assessment of WENO methods with shock-confining filtering for LES of compressible turbulence - Grube,N. E; Taylor,E. M; Martin, M.P (AIAA Paper 2007, 2007)

Automated gui testing guided by usage profiles - Brooks,Penelope A.; Memon, Atif M. (Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, 2007)
Most software developed in recent years has a graphical userinterface (GUI). The only way for the end-user to interact with the software application is through the GUI. Hence, acceptance and system testing of the software requires GUI testing. This paper presents a new technique for testing of GUI applications. Information on the actual usage of the application, in the form of "usage profiles," is used to ensure that a new version of the application will function correctly. Usage profiles, sequences of events that end-users execute on a GUI, are used to develop a probabilistic usage model of the application. An algorithm uses the model to generate test cases that represent events the user is most likely to execute. Reverse engineering methods are used to extract the underlying structure of the application. An empirical study on four open source GUI applications reveals that test suites generated from the probabilistic model are 0.2-22% of the size of test suites produced directly from usage profiles. Furthermore, the test suites generated from the model detect more faults per test case than those detected directly from the usage profiles, and detect faults not detected by the original profiles
Keywords: event-driven software; GUI testing; usage profiles

Beyond single-appearance schedules: Efficient DSP software synthesis using nested procedure calls - Ko,M. Y; Murthy,P. K; Bhattacharyya, Shuvra S. (ACM Transactions on Embedded Computing Systems (TECS), 2007)

CARA: A Cultural-Reasoning Architecture - V.S. Subrahmanian; Albanese,Massimiliano; Martinez,Mar?a Vanina; Nau, Dana S.; Reforgiato,Diego; Simari,Gerardo I.; Sliva,Amy; Udrea,Octavian; Wilkenfeld,Jonathan (IEEE Intelligent Systems, 2007)
The Cognitive Architecture for Reasoning about Adversaries supports methods to gather data about different cultural groups and learn the intensity of those groups' opinions on various topics. It also lets users build and extract models of those groups' behavior and continuously refine those models through shared multiperson learning experiences. Researchers have applied the architecture to develop cultural-reasoning applications for example, a game that teaches soldiers about cultural norms in an Afghan village.
Keywords: cultural reasoning; opinion extraction; opponent modeling

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

Children's interests and concerns when using the international children's digital library: a four-country case study - Druin, Allison; Weeks,A.; Massey,S.; Bederson, Benjamin B. (Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, 2007)

Combining outputs from multiple machine translation systems - Rosti,A.V.I.; Ayan,N.F.; Xiang,B.; Matsoukas,S.; Schwartz,R.; Dorr, Bonnie J (Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference, 2007)
Currently there are several approaches tomachine translation (MT) based on differ- ent paradigms; e.g., phrasal, hierarchical and syntax-based. These three approaches yield similar translation accuracy despite using fairly different levels of linguistic knowledge. The availability of such a variety of systems has led to a growing interest toward finding better translations by combining outputs from multiple sys- tems. This paper describes three differ- ent approaches to MT system combina- tion. These combination methods oper- ate on sentence, phrase and word level exploiting information from N -best lists, system scores and target-to-source phrase alignments. The word-level combination provides the most robust gains but the best results on the development test sets (NIST MT05 and the newsgroup portion of GALE 2006 dry-run) were achieved by combining all three methods.

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

A computational survey of candidate exonic splicing enhancer motifs in the model plant Arabidopsis thaliana - Pertea,Mihaela; Mount, Stephen M.; Salzberg,Steven L. (BMC Bioinformatics, 2007)
Algorithmic approaches to splice site prediction have relied mainly on the consensus patterns found at the boundaries between protein coding and non-coding regions. However exonic splicing enhancers have been shown to enhance the utilization of nearby splice sites.

Computing most probable worlds of action probabilistic logic programs: scalable estimation for 10^30,000 worlds - Khuller, Samir; Martinez,M.; Nau, Dana S.; Sliva,Amy; Simari,Gerardo; Subrahmanian,V. (Annals of Mathematics and Artificial Intelligence, 2007)
The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called and to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a “binary” algorithm that applies a binary search style heuristic in conjunction with the Naive, and algorithms to quickly find worlds that may not be “most probable.” We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of are very accurate and also very fast: more than 10 30,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups.
Keywords: Computer science

COMPUTING PERFECT AND STABLE MODELS USING ORDERED MODEL TREES - Fernández1,José Alberto; Minker, Jack; Yahya,Adnan (Computational Intelligence, 2007)
Ordered model trees were introduced as a normal form for disjunctive deductive databases. They were also used to facilitate the computation of minimal models for disjunctive theories by exploiting the order imposed on the Herbrand base of the theory. In this work we show how the order on the Herbrand base can be used to compute perfect models of a disjunctive stratified finite theory. We are able to compute the stable models of a general finite theory by combining the order on the elements of the Herbrand base with previous results that had shown that the stable models of a theory T can be computed as the perfect models of a corresponding disjunctive theory ɛT resulting from applying the so called evidential transformation to T. While other methods consider many models that are rejected at the end, the use of atom ordering allows us to guarantee that every model generated belongs to the class of models being computed. As for negation-free databases, the ordered tree serves as the canonical representation of the database.
Keywords: disjunctive database; model tree; ordered model tree; perfect model; stable model

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

CONVEX: Context vectors as a paradigm for learning group behaviors based on similarity - Martinez,V.; Simari,G. I; Sliva,A.; V.S. Subrahmanian (IEEE Intelligent Systems, 2007)

COST: An Approach for Camera Selection and Multi-Object Inference Ordering in Dynamic Scenes - Gupta,Abhinav; Mittal,Anurag; Davis, Larry S. (Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on, 2007)
Development of multiple camera based vision systems for analysis of dynamic objects such as humans is challenging due to occlusions and similarity in the appearance of a person with the background and other people- visual "confusion". Since occlusion and confusion depends on the presence of other people in the scene, it leads to a dependency structure where there are often loops in the resulting Bayesian network. While approaches such as loopy belief propagation can be used for inference, they are computationally expensive and convergence is not guaranteed in many situations. We present a unified approach, COST, that reasons about such dependencies and yields an order for the inference of each person in a group of people and a set of cameras to be used for inferences for a person. Using the probabilistic distribution of the positions and appearances of people, COST performs visibility and confusion analysis for each part of each person and computes the amount of information that can be computed with and without more accurate estimation of the positions of other people. We present an optimization problem to select set of cameras and inference dependencies for each person which attempts to minimize the computational cost under given performance constraints. Results show the efficiency of COST in improving the performance of such systems and reducing the computational resources required.

Covering array sampling of input event sequences for automated gui testing - Xun Yuan; Cohen,Myra; Memon, Atif M. (Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, 2007)
This paper describes a new automated technique to generate test cases for GUIs by using covering arrays (CAs). The key motivation is to generate long GUI event sequences that are systematically sampled at a particular coverage strength. CAs, to date, have not been effectively used in sampling event driven systems such as GUIs which maintain state. We leverage a "stateless" abstraction of GUIs that allows us to use CAs. Once the CAs have been generated, we reuse the abstractions to reinsert ordering relationships between GUI events, thereby creating executable test cases. A feasibility study on a well-studied GUI-based application shows that the new technique is able to detect a large number of previously undetected faults
Keywords: covering arrays; event driven software; GUI testing

Creating a Robust Desktop Grid using Peer-to-Peer Services - Kim,J.-S.; Nam,B.; Marsh,M.; Keleher,P.; Bhattacharjee, Bobby; Richardson,D.; Wellnitz,D.; Sussman, Alan (Parallel and Distributed Processing Symposium, 2007. IPDPS 2007. IEEE International, 2007)
The goal of the work described in this paper is to design and build a scalable infrastructure for executing grid applications on a widely distributed set of resources. Such grid infrastructure must be decentralized, robust, highly available, and scalable, while efficiently mapping application instances to available resources in the system. However, current desktop grid computing platforms are typically based on a client-server architecture, which has inherent shortcomings with respect to robustness, reliability and scalability. Fortunately, these problems can be addressed through the capabilities promised by new techniques and approaches in peer-to-peer (P2P) systems. By employing P2P services, our system allows users to submit jobs to be run in the system and to run jobs submitted by other users on any resources available in the system, essentially allowing a group of users to form an ad-hoc set of shared resources. The initial target application areas for the desktop grid system are in astronomy and space science simulation and data analysis.
Keywords: allocation; architecture; load; balancing; peer-to-peer; client-server; computing; peer-to-peer; computing; resource; desktop; grid; scalable; infrastructure; client-server; system; robust; systems; grid

Cross-layer latency minimization in wireless networks with SINR constraints - Chafekar,Deepti; Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, 2007)
Recently, there has been substantial interest in the design of cross-layer protocols for wireless networks. These protocols optimize certain performance metric(s) of interest (e.g. latency, energy, rate) by jointly optimizing the performance of multiple layers of the protocol stack. Algorithm designers often use geometric-graph-theoretic models for radio interference to design such cross-layer protocols. In this paper we study the problem of designing cross-layer protocols for multi-hop wireless networks using a more realistic Signal to Interference plus Noise Ratio (SINR) model for radio interference. The following cross-layer latency minimization problem is studied: Given a set V of transceivers, and a set of source-destination pairs, (i) choose power levels for all the transceivers, (ii) choose routes for all connections, and (iii) construct an end-to-end schedule such that the SINR constraints are satisfied at each time step so as to minimize the make-span of the schedule (the time by which all packets have reached their respective destinations). We present a polynomial-time algorithm with provable worst-case performance guarantee for this cross-layer latency minimization problem. As corollaries of the algorithmic technique we show that a number of variants of the cross-layer latency minimization problem can also be approximated efficiently in polynomial time. Our work extends the results of Kumar et al. (Proc. SODA, 2004) and Moscibroda et al. (Proc. MOBIHOC, 2006). Although our algorithm considers multiple layers of the protocol stack, it can naturally be viewed as compositions of tasks specific to each layer --- this allows us to improve the overall performance while preserving the modularity of the layered structure.
Keywords: cross-layer design; end-to-end scheduling; Interference; SINR model; Wireless networks

Deductive Databases - Grant,John; Minker, Jack (Wiley Encyclopedia of Computer Science and EngineeringWiley Encyclopedia of Computer Science and Engineering, 2007)
Keywords: answer set semantics; Datalog; deductive database; disjunctive database; extended database

Designing and comparing automated test oracles for GUI-based software applications - Xie,Qing; Memon, Atif M. (ACM Trans. Softw. Eng. Methodol., 2007)
Test designers widely believe that the overall effectiveness and cost of software testing depends largely on the type and number of test cases executed on the software. This article shows that the test oracle, a mechanism that determines whether a software is executed correctly for a test case, also significantly impacts the fault detection effectiveness and cost of a test case. Graphical user interfaces (GUIs), which have become ubiquitous for interacting with today's software, have created new challenges for test oracle development. Test designers manually “assert” the expected values of specific properties of certain GUI widgets in each test case; during test execution, these assertions are used as test oracles to determine whether the GUI executed correctly. Since a test case for a GUI is a sequence of events, a test designer must decide: (1) what to assert; and (2) how frequently to check an assertion, for example, after each event in the test case or after the entire test case has completed execution. Variations of these two factors significantly impact the fault-detection ability and cost of a GUI test case. A technique to declaratively specify different types of automated GUI test oracles is described. Six instances of test oracles are developed and compared in an experiment on four software systems. The results show that test oracles do affect the fault detection ability of test cases in different and interesting ways: (1) Test cases significantly lose their fault detection ability when using “weak” test oracles; (2) in many cases, invoking a “thorough” oracle at the end of test case execution yields the best cost-benefit ratio; (3) certain test cases detect faults only if the oracle is invoked during a small “window of opportunity” during test execution; and (4) using thorough and frequently-executing test oracles can compensate for not having long test cases.
Keywords: Graphical user interfaces; GUI state; GUI testing; test oracles; User interfaces; widgets

Detecting stochastically scheduled activities in video - Albanese, M.; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Udrea,O. (International Joint Conference on Artificial Intelligence, 2007)
The ability to automatically detect activities invideo is of increasing importance in applications such as bank security, airport tarmac security, bag- gage area security and building site surveillance. We present a stochastic activity model composed of atomic actions which are directly observable through image understanding primitives. We focus on answering two types of questions: (i) what are the minimal sub-videos in which a given action is identified with probability above a certain thresh- old and (ii) for a given video, can we decide which activity from a given set most likely occurred? We provide the MPS algorithm for the first problem, as well as two different algorithms (naiveMPA and MPA) to solve the second. Our experimental re- sults on a dataset consisting of staged bank robbery videos (described in [Vu et al., 2003]) show that our algorithms are both fast and provide high qual- ity results when compared to human reviewers.

Developing a Computer Science Department at the University of Maryland - Minker, Jack (Annals of the History of Computing, IEEE, 2007)
This article describes the first six years of the Computer Science Department, established in 1973 at the University of Maryland. The department evolved out of the Computer Science Center, which had been instituted in February 1962. In 1980, the National Academy of Sciences judged the department as being among the leading computer science departments in the US.
Keywords: administrative; data; department; educational; MARYLAND; processing; Science; University; computer

Direct-dependency-based software compatibility testing - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, 2007)
Software compatibility testing is an important quality assurance task aimed at ensuring that component-based software systems build and/or execute properly across a broad range of user system configurations. Because each configuration can involve multiple components with different versions, and because there are complex and changing interdependencies between components and their versions, it is generally infeasible to test all potential configurations. Therefore, compatibility testing usually means examining only a handful of default or popular configurations to detect problems, and as a result costly errors can and do escape to the field This paper presents an improved approach to compatibility testing called RACHET. We formally model the configuration space for component-based systems and use the model to generate test plans covering user-specified portion of the space - the example in this paper is covering all it direct dependencies between components. The test plan is executed efficiently in parallel, by distributing work so as to best utilize test resources. We conducted experimentsand simulation studies applying our approach to a large-scale data management middleware system. The results showed that for this system RACHET discovered incompatibilities between components at a small fraction of the cost for exhaustive testing without compromising test quality
Keywords: compatibility testing; component-based software system

Distributed ranked search - Gopalakrishnan,V.; Morselli,R.; Bhattacharjee, Bobby; Keleher,P.; Srinivasan, Aravind (High Performance Computing–HiPC 2007, 2007)
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 results, not necessarily 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 decentralized setting. We analyze the overhead of our approach, and quantify 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 scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to that of a centralized implementation.

Distributed Ranked Search - Gopalakrishnan,Vijay; Morselli,Ruggero; Bhattacharjee, Bobby; Keleher,Pete; Srinivasan, Aravind (High Performance Computing – HiPC 2007High Performance Computing – HiPC 2007, 2007)
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 results, not necessarily 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 decentralized setting. We analyze the overhead of our approach, and quantify 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 scale with little overhead to large systems, and b) the accuracy of the results obtained using distributed ranking is comparable to that of a centralized implementation.

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

Efficient implementation of an optimal interpolator for large spatial data sets - Memarsadeghi,N.; Mount, Dave (Computational Science–ICCS 2007, 2007)
Interpolating scattered data points is a problem of wide ranging interest. One of the most popular interpolation methods in geostatistics is ordinary kriging. The price for its statistical optimality is that the estimator is computationally very expensive. We demonstrate the space and time efficiency and accuracy of approximating ordinary kriging through the use of covariance tapering combined with iterative methods.

Efficient lookup on unstructured topologies - Morselli,R.; Bhattacharjee, Bobby; Marsh,M.A.; Srinivasan, Aravind (IEEE Journal on Selected Areas in Communications, 2007)
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 LMS. 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: Computer science; DHT; distributed algorithms; Distributed computing; distributed hash table; Least squares approximation; LMS; local minima search; lookup protocol; Network topology; node failures; Peer to peer computing; Performance analysis; Protocols; replication strategy; Resilience; Robustness; table lookup; telecommunication network topology; unstructured network topology

An empirical approach to evaluating web application compliance across diverse client platform configurations - Eaton,Cyntrica; Memon, Atif M. (International Journal of Web Engineering and Technology, 2007)
Web applications are the most widely used class of software today. Increased diversity of web-client platform configurations causes execution of web applications to vary unpredictably, creating a myriad of challenges for quality assurance during development. This paper presents a novel technique and an inductive model that leverages empirical data from fielded systems to evaluate web application correctness across multiple client configurations. The inductive model is based on HTML tags and represents how web applications are expected to execute in each client configuration based on the fielded systems observed. End-users and developers update this model by providing empirical data in the form of positive (correctly executing) and negative (incorrectly executing) instances of fielded web applications. The results of an empirical study show that the approach is useful and that popular web applications have serious client-configuration-specific flaws.

An empirical study of filesystem activity following a SSH compromise - Molina,J.; Gordon,J.; Chorin,X.; Michel Cukier (2007)
Monitoring filesystem data is a common method used to detect attacks. Once a computer is compromised, attackers will likely alter files, add new files or delete existing files. The changes that attackers make may target any part of the filesystem, including metadata along with files (e.g., permissions, ownerships and inodes). In this paper, we describe an empirical study that focused on SSH compromised attacks. First statistical data on the number of files targeted and the associated activity (e.g., read, write, delete, ownership and rights) is reported. Then, we refine the analysis to identify and understand patterns in the attack activity.
Keywords: attack activity; filesystem activity; filesystem data monitoring; intrusion detection systems evaluation; meta data; metadata; security of data; SSH compromised attacks

Evaluation of Traditional and Shock-Confining LES Filters using DNS Data of Compressible Turbulence - Taylor,E. M; Grube,N. E; Martin, M.P (Proceedings of 18th AIAA Computational Fluid Dynamics Conference, 2007)
Uniformly high-order-accurate filtering of fluid flow properties in the presence of shocksand shocklets is theoretically susceptible to the same problem that afflicts uniformly high- order-accurate numerical methods for approximating the convective terms of the Navier- Stokes equations: the introduction of new, non-physical extrema near discontinuities. Ex- tensive investigations have been conducted into myriad types of shock-capturing methods, which adaptively decrease their order of accuracy within shock-containing regions in order to maintain accuracy and stability over time. Inspired by such work, Grube et al. (AIAA 2007-4198) have proposed the conceptually similar idea of “shock-confining” filtering (SCF) for compressible large-eddy simulations (LES), in which a class of linear filters is subject to adaptive adjustments based on smoothness information provided by a weighted essen- tially non-oscillatory (WENO) method. In the current work, we utilize the turbulent flow fields produced by direct numerical simulations (DNS) of shock/isotropic-turbulence inter- action to perform preliminary a priori testing of these shock-confining filters against the corresponding linear filters. Although additional study, both a priori and a posteriori, is required to verify the necessity and suitability of SCF for LES, we conclude that linear filtering can indeed create serious qualitative discrepancies in global flow characteristics, discrepancies that are avoided by the use of SCF.

An event-flow model of GUI-based applications for testing - Memon, Atif M. (Software Testing, Verification and Reliability, 2007)
Graphical user interfaces (GUIs) are by far the most popular means used to interact with today's software. The functional correctness of a GUI is required to ensure the safety, robustness and usability of an entire software system. GUI testing techniques used in practice are resource intensive; model-based automated techniques are rarely employed. A key reason for the reluctance in the adoption of model-based solutions proposed by researchers is their limited applicability; moreover, the models are expensive to create. Over the past few years, the present author has been developing different models for various aspects of GUI testing. This paper consolidates all of the models into one scalable event-flow model and outlines algorithms to semi-automatically reverse-engineer the model from an implementation. Earlier work on model-based test-case generation, test-oracle creation, coverage evaluation, and regression testing is recast in terms of this model by defining event-space exploration strategies (ESESs) and creating an end-to-end GUI testing process. Three such ESESs are described: for checking the event-flow model, test-case generation, and test-oracle creation. Two demonstrational scenarios show the application of the model and the three ESESs for experimentation and application in GUI testing. Copyright © 2007 John Wiley & Sons, Ltd.
Keywords: event-driven software; event-flow graph; event-flow model; Graphical user interfaces; integration tree; Model checking; test oracles; test-case generation

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

Evolution of genes and genomes on the Drosophila phylogeny - Clark, A.G.; Eisen,M. B; Smith,D. R; Bergman, C.M.; Oliver, B.; Markow, T.A.; Kaufman, T.C.; Kellis, M.; Gelbart, W.; Iyer, V.N.; others (Nature, 2007)

Experimenting with software testbeds for evaluating new technologies - Lindvall,M.; Rus,I.; Donzelli,P.; Memon, Atif M.; Zelkowitz, Marvin V; Betin-Can,A.; Bultan,T.; Ackermann,C.; Anders,B.; Asgari, S.; Basili, Victor R. (Empirical Software Engineering, 2007)
The evolution of a new technology depends upon a good theoretical basis for developing the technology, as well as upon its experimental validation. In order to provide for this experimentation, we have investigated the creation of a software testbed and the feasibility of using the same testbed for experimenting with a broad set of technologies. The testbed is a set of programs, data, and supporting documentation that allows researchers to test their new technology on a standard software platform. An important component of this testbed is the Unified Model of Dependability (UMD), which was used to elicit dependability requirements for the testbed software. With a collection of seeded faults and known issues of the target system, we are able to determine if a new technology is adept at uncovering defects or providing other aids proposed by its developers. In this paper, we present the Tactical Separation Assisted Flight Environment (TSAFE) testbed environment for which we modeled and evaluated dependability requirements and defined faults to be seeded for experimentation. We describe two completed experiments that we conducted on the testbed. The first experiment studies a technology that identifies architectural violations and evaluates its ability to detect the violations. The second experiment studies model checking as part of design for verification. We conclude by describing ongoing experimental work studying testing, using the same testbed. Our conclusion is that even though these three experiments are very different in terms of the studied technology, using and re-using the same testbed is beneficial and cost effective.

Exploiting approximate transitivity of trust - Morselli,Ruggero; Bhattacharjee, Bobby; Katz, Jonathan; Marsh,Michael (Broadband Communications, Networks and Systems, 2007. BROADNETS 2007. Fourth International Conference on, 2007)
Social networks, of which webs of trust are a particular type, have been shown to be effective ways of moving information with minimal external configuration, setup, or management. For applications requiring information assurance, a web of trust is an appealing system architecture, since trust is an inherent component of both the network design and assurance. The trust in a typical web of trust is not transitive, however, making the construction of an application with strong assurance difficult or impossible. Instead, in this paper we examine a notion of weak assurance that can be provided by a web of trust, and might be #x201C;good enough #x201D; for many applications. As a motivating example, and to provide a more concrete basis for exposition, we present KeyChains, a peer-to-peer system that operates over a distributed web of trust to provide fully decentralized public key publishing and retrieval. In addition to weak assurance guarantees, KeyChains also provides an audit trail for public keys retrieved. Our analysis and simulations show that the resulting system is both efficient and secure.

A fast implementation of the ISODATA clustering algorithm - Memarsadeghi,N.; Mount, Dave; Netanyahu,N. S; Le Moigne,J.; de Berg,M. (International Journal of Computational Geometry and Applications, 2007)
Clustering is central to many image processing and remote sensing applications. isodatais one of the most popular and widely used clustering methods in geoscience applications, but it can run slowly, particularly with large data sets. We present a more efficient approach to isodata clustering, which achieves better running times by storing the points in a kd-tree and through a modification of the way in which the algorithm estimates the dispersion of each cluster. We also present an approximate version of the algorithm which allows the user to further improve the running time, at the expense of lower fidelity in computing the nearest cluster center to each point. We provide both theoretical and empirical justification that our modified approach produces clusterings that are very similar to those produced by the standard isodata approach. We also provide empirical studies on both synthetic data and remotely sensed Landsat and MODIS images that show that our approach has significantly lower running times.

Fast Robust Regression Algorithms for Problems with Toeplitz Structure - Mastronardi,Nicola; O'Leary, Dianne P. (Computational Statistics and Data Analysis, 2007)

Fault Detection Probability Analysis for Coverage-Based Test Suite Reduction - McMaster,S.; Memon, Atif M. (Software Maintenance, 2007. ICSM 2007. IEEE International Conference on, 2007)
Test suite reduction seeks to reduce the number of test cases in a test suite while retaining a high percentage of the original suite's fault detection effectiveness. Most approaches to this problem are based on eliminating test cases that are redundant relative to some coverage criterion. The effectiveness of applying various coverage criteria in test suite reduction is traditionally based on empirical comparison of two metrics derived from the full and reduced test suites and information about a set of known faults: (1) percentage size reduction and (2) percentage fault detection reduction, neither of which quantitatively takes test coverage data into account. Consequently, no existing measure expresses the likelihood of various coverage criteria to force coverage-based reduction to retain test cases that expose specific faults. In this paper, we develop and empirically evaluate, using a number of different coverage criteria, a new metric based on the "average expected probability of finding a fault" in a reduced test suite. Our results indicate that the average probability of detecting each fault shows promise for identifying coverage criteria that work well for test suite reduction.
Keywords: coverage-based test suite reduction; fault detection probability analysis; Fault diagnosis; force coverage-based reduction; percentage fault detection reduction; percentage size reduction; program testing; software reliability; statistical analysis

Faults' context matters - Strecker,Jaymie; Memon, Atif M. (Fourth international workshop on Software quality assurance: in conjunction with the 6th ESEC/FSE joint meeting, 2007)
When choosing a testing technique, practitioners want to know which one will detect the faults that matter most to them in the programs that they plan to test. Do empirical evaluations of testing techniques provide this information? More often than not, they report how many faults in a carefully chosen "representative" sample the evaluated techniques detect. But the population of faults that such a sample would represent depends heavily on the faults' context or environment---as does the cost of failing to detect those faults. If empirical studies are to provide information that a practitioner can apply outside the context of the study, they must characterize the faults studied in a way that translates across contexts. A testing technique's fault-detecting abilities could then be interpreted relative to the fault characterization. In this paper, we present a list of criteria that a fault characterization must meet in order to be fit for this task, and we evaluate several well-known fault characterizations against the criteria. Two families of characterizations are found to satisfy the criteria: those based on graph models of programs and those based on faults' detection by testing techniques.

Features generated for computational splice-site prediction correspond to functional elements - Dogan,Rezarta I.; Getoor,Lise; Wilbur,W. John; Mount, Stephen M. (BMC Bioinformatics, 2007)
Accurate selection of splice sites during the splicing of precursors to messenger RNA requires both relatively well-characterized signals at the splice sites and auxiliary signals in the adjacent exons and introns. We previously described a feature generation algorithm (FGA) that is capable of achieving high classification accuracy on human 3' splice sites. In this paper, we extend the splice-site prediction to 5' splice sites and explore the generated features for biologically meaningful splicing signals.

Filesystem activity following a SSH compromise: an empirical study of file sequences - Molina,Jesus; Chorin,Xavier; Michel Cukier (Springer-Verlag, 2007)
A common method used to detect intrusions is monitoring filesystem data. Once a computer is compromised, an attacker may alter files, add new files or delete existing ones. Attackers may target any part of the filesystem, including metadata along with files (e.g., permissions, ownerships and inodes). In this paper, we will describe an empirical study that focused on computer attack activity after a SSH compromise. Statistical data will be provided on the number of files targeted and the associated activity (e.g., read, write, delete, ownership and rights). We extend this analysis to include the sequence of files and activities targeted. We focused on the most frequent sequences of consecutive files and activities, then explored in greater detail the longer sequences using state machines. Finally, we developed a simple state machine representing three major observed attack activities (i.e., reconnaissance, malware download and password change) with the number of transitions and time for each transition. The analysis of individual and sequences of files and activities will help to better understand attack activity patterns resulting in more efficient intrusion detection.
Keywords: filesystem data; host intrusion detection systems; intrusion detection systems evaluation; SSH compromises

Finding Most Probable Worlds of Probabilistic Logic Programs - Khuller, Samir; Martinez,Vanina; Nau, Dana S.; Simari,Gerardo; Sliva,Amy; Subrahmanian,V. (Scalable Uncertainty Management, 2007)
Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a possible world that is most probable. Our first result shows that the problem of computing such ”maximally probable worlds” (MPW) is intractable. We subsequently show that we can often greatly reduce the size of the linear program used in past work (by Ng and Subrahmanian) and yet solve the problem exactly. However, the intractability results still make computational efficiency quite impossible. We therefore also develop several heuristics to solve the MPW problem and report extensive experimental results on the accuracy and efficiency of such heuristics.
Keywords: Computer science

Finding most probable worlds of probabilistic logic programs - Khuller, Samir; Martinez,V.; Nau, Dana S.; Simari,G.; Sliva,A.; Subrahmanian,V. (Scalable Uncertainty Management, 2007)
Probabilistic logic programs have primarily studied the problem of entailment of probabilistic atoms. However, there are some interesting applications where we are interested in finding a possible world that is most probable. Our first result shows that the problem of computing such ”maximally probable worlds” (MPW) is intractable. We subsequently show that we can often greatly reduce the size of the linear program used in past work (by Ng and Subrahmanian) and yet solve the problem exactly. However, the intractability results still make computational efficiency quite impossible. We therefore also develop several heuristics to solve the MPW problem and report extensive experimental results on the accuracy and efficiency of such heuristics.

Forming a Computer Science Center at the University of Maryland - Minker, Jack (IEEE Annals of the History of Computing, 2007)
The use of and first courses on computers at Maryland began in the 1940s. The Computer Science Center beginnings are examined in the context of founding director Werner C. Rheinboldt's noteworthy accomplishments to develop a computation facility with research and educational components, supported by John Menard, assistant director. William F. Atchison, who replaced Rheinboldt as Center director, continued these accomplishments.
Keywords: acm curriculum '68; federal grants; first cs courses; first cs director; formation of cs center; graduate/undergraduate education programs; loss of computer autonomy; planning a cs building; research; software developments

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

Gaussian Approximations for Energy-Based Detection and Localization in Sensor Networks - Cevher,Volkan; Chellapa, Rama; McClellan,James H. (Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on, 2007)
Energy-based detection and estimation are crucial in sensor networks for sensor localization, target tracking, etc. In this paper, we present novel Gaussian approximations that are applicable to general energy-based source detection and localization problems in sensor networks. Using our approximations, we derive receiver operating characteristics curves and Cramer-Rao bounds, and we provide a factorized variational Bayes approximation to the location and source energy posterior for centralized or decentralized estimation. When the source signal and the sensor noise have uncorrelated Gaussian distributions, we demonstrate that the envelope of the sensor output can be accurately modeled with a multiplicative Gaussian noise model, which results in smaller estimation biases than the other Gaussian models typically used in the literature. We also prove that additive Gaussian noise models result in negatively biased speed estimates under the same signal assumptions, which can be circumvented by the proposed approximations.

Geometry and Charge State of Mixed‐Ligand Au13 Nanoclusters - Frenkel, A. I.; Menard, L. D.; Northrup, P.; Rodriguez, J. A.; Zypman, F.; Dana Dachman-Soled; Gao, S.-P.; Xu, H.; Yang, J. C.; Nuzzo, R. G. (X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference, 2007)
The integration of synthetic, experimental and theoretical tools into a self‐consistent data analysis methodology allowed us to develop unique new levels of detail in nanoparticle characterization. We describe our methods using an example of Au 13 monolayer‐protected clusters (MPCs), synthesized by ligand exchange methods. The combination of atom counting methods of scanning transmission electron microscopy and Au L3‐edge EXAFS allowed us to characterize these clusters as icosahedral, with surface strain reduced from 5% (as in ideal, regular icosahedra) to 3%, due to the interaction with ligands. Charge transfer from Au to the thiol and phosphine ligands was evidenced by S and P K‐edge XANES. A comparison of total energies of bare clusters of different geometries was performed by equivalent crystal theory calculations.
Keywords: Atom surface interactions; Charge transfer; Data analysis; Extended X-ray absorption fine structure spectroscopy; Gold; nanoparticles; Scanning transmission electron microscopy; Surface strains; Total energy calculations; X-ray absorption near edge structure

Grid Services Base Library: A high-level, procedural application programming interface for writing Globus-based Grid services - Bazinet,A. L; Myers,D. S; Fuetsch,J.; Cummings, Michael P. (Future Generation Comp Syst, 2007)
The Grid Services Base Library (GSBL) is a procedural application programming interface (API) that abstracts many of the high-level functions performed by Globus Grid services, thus dramatically lowering the barriers to writing Grid services. The library has been extensively tested and used for computational biology research in a Globus Toolkit-based Grid system, in which no fewer than twenty Grid services written with this API are deployed.

Holding the Internet Accountable - Andersen,David; Balakrishnan,Hari; Feamster, Nick; Koponen,Teemu; Moon,Daekyong; Shenker,Scott (Proc. 6th ACM Workshop on Hot Topics in Networks (Hotnets-VI), 2007)
Today’s IP network layer provides little to no protection against misconfiguration or malice. Despite some progress in improving the robustness and security of the IP layer, misconfigurations and attacks still occur frequently. We show how a network layer that provides accountability, i.e., the ability to associate each action with the responsible entity, provides a firm foundation for defenses against misconfiguration and malice. We present the design of a network layer that incorporates accountability called AIP (Accountable Internet Protocol) and show how its features—notably, its use of self-certifying addresses— can improve both source accountability (the ability to trace actions to a particular end host and stop that host from misbehaving) and control-plane accountability (the ability to pinpoint and prevent attacks on routing).

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

Human activity understanding using visibility context - Morariu,V.I.; Prasad,V. S.N; Davis, Larry S. (IEEE/RSJ IROS Workshop: From sensors to human spatial concepts (FS2HSC), 2007)
Visibility in architectural layouts affects humannavigation, so a suitable representation of visibility context is useful in understanding human activity. Motivated by studies of spatial behavior, we use a set of features from visibility analysis to represent spatial context in the interpretation of human activity. An agent’s goal, belief about the world, trajectory and visible layout are considered to be random variables that evolve with time during the agent’s movement, and are modeled in a Bayesian framework. We design a search-based task in a sprite-world, and compare the results of our framework to those of human subject experiments. Our findings confirm that knowledge of spatial layout improves human interpretations of the trajectories (implying that visibility context is useful in this task). Since our framework demonstrates performance close to that of human subjects with knowledge of spatial layout, our findings confirm that our model makes adequate use of visibility context. In addition, the representation we use for visibility context allows our model to generalize well when presented with new scenes.

Hyperstereo algorithms for the perception of terrain drop-offs - Mohananchettiar,Arunkumar; Cevher,Volkan; CuQlock-Knopp,Grayson; Chellapa, Rama; Merritt,John (Proceedings of SPIE, 2007)
The timely detection of terrain drop-offs is critical for safe and efficient off-road mobility, whether with human drivers or with terrain navigation systems that use autonomous machine-vision. In this paper, we propose a joint tracking and detection machine-vision approach for accurate and efficient terrain drop-off detection and localization. We formulate the problem using a hyperstereo camera system and build an elevation map using the range map obtained from a stereo algorithm. A terrain drop-off is then detected with the use of optimal drop-off detection filters applied to the range map. For more robust results, a method based on multi-frame fusion of terrain drop-off evidence is proposed. Also presented is a fast, direct method that does not employ stereo disparity mapping. We compared our algorithm's detection of terrain drop-offs with time-code data from human observers viewing the same video clips in stereoscopic 3D. The algorithm detected terrain drop-offs an average of 9 seconds sooner, or 12m farther, than the human observers. This suggests that passive image-based hyperstereo machine-vision may be useful as an early warning system for off-road mobility.

Inferring aliasing and encapsulation properties for Java - Ma,K.K.; Foster, Jeffrey S. (ACM SIGPLAN Notices, 2007)

Interactive visual clustering - desJardins, Marie; MacGlashan,James; Ferraioli,Julia (Proceedings of the 12th international conference on Intelligent user interfaces, 2007)
Interactive Visual Clustering (IVC) is a novel method that allows a user to explore relational data sets interactively, in order to produce a clustering that satisfies their objectives. IVC combines spring-embedded graph layout with user interaction and constrained clustering. Experimental results on several synthetic and real-world data sets show that IVC yields better clustering performance than alternative methods.
Keywords: clustering; constraints; interaction

Jmin-image based color-texture segmentation using watershed and hierarchical clustering - Santos, T.T.; Morimoto, CH; Chellapa, Rama (Proceedings of the 8th International Symposium on Mathematical Morphology, 2007)

Joint Acoustic-Video Fingerprinting of Vehicles, Part I - Cevher, V.; Chellapa, Rama; McClellan, J.H. (Acoustics, Speech and Signal Processing, 2007. ICASSP 2007. IEEE International Conference on, 2007)
We address vehicle classification and measurement problems using acoustic and video sensors. In this paper, we show how to estimate a vehicle's speed, width, and length by jointly estimating its acoustic wave-pattern using a single passive sensor that records the vehicle's drive-by noise. The acoustic wave-pattern is approximated 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 the estimates of the vehicle engine RPM and number of cylinders to create a vehicle profile vector that forms an intuitive discriminatory feature space. In the companion paper, we discuss vehicle classification and mensuration based on silhouette extraction and wheel detection, using a video sensor. Vehicle speed estimation and classification results are provided using field data.
Keywords: acoustic; acoustic-video; components; joint; detection; acoustic; estimation; video; fingerprinting; passive; processing; processing; acoustic; sensor; vehicle; sensors; acoustic; sensors; wheel; SHAPE; signal; speed; transducers; video; wave-pattern; envelope

Learning and visualizing user preferences over sets - Wagstaff,K.; desJardins, Marie; Eaton,E.; Montminy,J. (American Association for Artificial Intelligence (AAAI), 2007)
In previous work, we introduced a representation language,DD-PREF, that balances preferences for particular items with preferences about the properties of the set. Specifically, DD- PREF permits the expression of preferences for depth (i.e., preferences for specific attribute values over others) and di- versity of sets (i.e., preferences for broad vs. narrow distri- butions of attribute values). We have also shown how pref- erences represented in DD-PREF can be learned from training data. In this paper, we present a new experimental method- ology, and give results in a Mars rover image domain. We also provide new visualizations of the learned preferences in this domain. Finally, we describe a Chinese restaurant menu domain for which we are currently gathering user data.

Leveraging data and structure in ontology integration - Udrea,Octavian; Getoor, Lise; Miller,Renée J. (Proceedings of the 2007 ACM SIGMOD international conference on Management of data, 2007)
There is a great deal of research on ontology integration which makes use of rich logical constraints to reason about the structural and logical alignment of ontologies. There is also considerable work on matching data instances from heterogeneous schema or ontologies. However, little work exploits the fact that ontologies include both data and structure. We aim to close this gap by presenting a new algorithm (ILIADS) that tightly integrates both data matching and logical reasoning to achieve better matching of ontologies. We evaluate our algorithm on a set of 30 pairs of OWL Lite ontologies with the schema and data matchings found by human reviewers. We compare against two systems - the ontology matching tool FCA-merge [28] and the schema matching tool COMA++ [1]. ILIADS shows an average improvement of 25% in quality over FCA-merge and a 11% improvement in recall over COMA++.
Keywords: Data integration; logical inference; ontology alignment; schema mapping; statistical inference

Measurement and analysis of online social networks - Mislove,Alan; Marcon,Massimiliano; Gummadi,Krishna P.; Druschel,Peter; Bhattacharjee, Bobby (Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, 2007)
Online social networking sites like Orkut, YouTube, and Flickr are among the most popular sites on the Internet. Users of these sites form a social network, which provides a powerful means of sharing, organizing, and finding content and contacts. The popularity of these sites provides an opportunity to study the characteristics of online social network graphs at large scale. Understanding these graphs is important, both to improve current systems and to design new applications of online social networks. This paper presents a large-scale measurement study and analysis of the structure of multiple online social networks. We examine data gathered from four popular online social networks: Flickr, YouTube, LiveJournal, and Orkut. We crawled the publicly accessible user links on each site, obtaining a large portion of each social network's graph. Our data set contains over 11.3 million users and 328 million links. We believe that this is the first study to examine multiple online social networks at scale. Our results confirm the power-law, small-world, and scale-free properties of online social networks. We observe that the indegree of user nodes tends to match the outdegree; that the networks contain a densely connected core of high-degree nodes; and that this core links small groups of strongly clustered, low-degree nodes at the fringes of the network. Finally, we discuss the implications of these structural properties for the design of social network based systems.
Keywords: analysis; measurement; social networks

Measuring variability in sentence ordering for news summarization - Madnani,Nitin; Passonneau,Rebecca; Ayan,Necip Fazil; Conroy,John M.; Dorr, Bonnie J; Klavans,Judith L.; O'Leary, Dianne P.; Schlesinger,Judith D. (Proceedings of the Eleventh European Workshop on Natural Language Generation, 2007)
The issue of sentence ordering is an important one for natural language tasks such as multi-document summarization, yet there has not been a quantitative exploration of the range of acceptable sentence orderings for short texts. We present results of a sentence reordering experiment with three experimental conditions. Our findings indicate a very high degree of variability in the orderings that the eighteen subjects produce. In addition, the variability of reorderings is significantly greater when the initial ordering seen by subjects is different from the original summary. We conclude that evaluation of sentence ordering should use multiple reference orderings. Our evaluation presents several metrics that might prove useful in assessing against multiple references. We conclude with a deeper set of questions: (a) what sorts of independent assessments of quality of the different reference orderings could be made and (b) whether a large enough test set would obviate the need for such independent means of quality assessment.

Method of three-dimensional object reconstruction from a video sequence using a generic model - Chellapa, Rama; Chowdhury,Amit K. Roy; Srinivasan,Sridhar (2007)
In a novel method of 3D modeling of an object from a video sequence using an SfM algorithm and a generic object model, the generic model is incorporated after the SfM algorithm generates a 3D estimate of the object model purely and directly from the input video sequence. An optimization framework provides for comparison of the local trends of the 3D estimate and the generic model so that the errors in the 3D estimate are corrected. The 3D estimate is obtained by fusing intermediate 3D reconstructions of pairs of frames of the video sequence after computing the uncertainty of the two frame solutions. The quality of the fusion algorithm is tracked using a rate-distortion function. In order to combine the generic model with the 3D estimate, an energy function minimization procedure is applied to the 3D estimate. The optimization is performed using a Metropolis-Hasting sampling strategy.

MobCast: Overlay Architecture for Seamless IP Mobility using Scalable Anycast Proxies - Lee,C.P.; Attrey,K.; Caballero,C.; Feamster, Nick; Mihail,M.; Copeland,J.A. (Wireless Communications and Networking Conference, 2007.WCNC 2007. IEEE, 2007)
We propose a routing overlay system, MobCast, for simple and efficient routing to mobile hosts. Mobcast nodes advertise the same address space at each proxy location, and each mobile host is assigned a "universal" IP address from this address space, so packets sent to a mobile host's universal IP address automatically go to the nearest proxy on the overlay. The overlay then delivers the packets to the mobile host. Our architecture enables seamless mobility for both micro and macro mobility. While our initial design is not as mature as Mobile IP, it shows great promise to solve the traditional problems of ingress routing, firewalls, NATs, and rapid mobility with much lower complexity. We present our design as a scalable and deployable alternative to mobile IP. In this paper, we focus on describing the MobCast system architecture. We form our arguments for scalability, handoff-speed, and simplicity, and give our initial results for scalability. We postpone a detailed discussion of MobCast's security model for future work.
Keywords: address space; handoff-speed; IP networks; MobCast; mobile hosts; mobile radio; overlay architecture; proxy location; routing overlay system; scalable anycast proxies; seamless IP mobility; telecommunication network routing; universal IP address

Multiple alternative sentence compressions for automatic text summarization - Madnani,N.; Zajic, David; Dorr, Bonnie J; Ayan,N.F.; Jimmy Lin (Proceedings of DUC, 2007)
We perform multi-document summariza-tion by generating compressed versions of source sentences as summary candi- dates and using weighted features of these candidates to construct summaries. We combine a parse-and-trim approach with a novel technique for producing multiple alternative compressions for source sen- tences. In addition, we use a novel method for tuning the feature weights that maxi- mizes the change in the ROUGE-2 score (∆ROUGE) between the already existing summary state and the new state that re- sults from the addition of the candidate under consideration. We also describe ex- periments using a new paraphrase-based feature for redundancy checking. Finally, we present the results of our DUC2007 submissions and some ideas for future work.

Multiresolution Terrain Processing and Visualization with VARIANT - De Floriani, Leila; Magillo,P. (Department of Computer and Information Sciences, University of Genova, Via Dodecaneso, 2007)
We present VARIANT (VAriable Resolution Interactive ANalysis of Terrain), a system forprocessing and visualizing terrains represented through Triangulated Irregular Networks (TINs) at multiple resolutions. Multiresolution refers to the possibility of dynamically varying the density of the TIN, and is used to enhance speed of computation while guaranteeing the accuracy needed by operations. VARIANT directly supports basic queries as well as some high-level operations, and it can be enriched with many other functionalities. It is built on the Multi- Triangulation (MT) Library, an extensible library for multiresolution geometric modeling.

Multi-scale dual morse complexes for representing terrain morphology - Danovaro,Emanuele; De Floriani, Leila; Vitali,Maria; Magillo,Paola (Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems, 2007)
We propose a new multi-scale terrain model, based on a hierarchical representation for the morphology of a terrain. The basis of our morphological model is a dual Morse decomposition of the terrain, composed by the stable and unstable manifolds defined by its critical points and its integral lines. We propose a two-level representation of the dual Morse decomposition and we define new simplification operators for the Morse decomposition which act on such representation. Based on these operators, we define a hierarchical morphology-based representation, that we call a Multi-scale Morse Complex (MMC). Results from our implementation of the MMC are presented.
Keywords: Morphology; multi-scale representations; terrain modeling

New Trypanosoma cruzi Repeated Element That Shows Site Specificity for Insertion - Souza,Renata T.; Santos,Marcia R. M.; Lima,Fabio M.; El‐Sayed, Najib M.; Myler,Peter J.; Ruiz,Jeronimo C.; da Silveira,Jose Franco (Eukaryotic Cell, 2007)
A new family of site-specific repeated elements identified in Trypanosoma cruzi, which we named TcTREZO, is described here. TcTREZO appears to be a composite repeated element, since three subregions may be defined within it on the basis of sequence similarities with other T. cruzi sequences. Analysis of the distribution of TcTREZO in the genome clearly indicates that it displays site specificity for insertion. Most TcTREZO elements are flanked by conserved sequences. There is a highly conserved 68-bp sequence at the 5' end of the element and a sequence domain of [~]500 bp without a well-defined borderline at the 3' end. Northern blot hybridization and reverse transcriptase PCR analyses showed that TcTREZO transcripts are expressed as oligo(A)-terminated transcripts whose length corresponds to the unit size of the element (1.6 kb). Transcripts of [~]0.2 kb derived from a small part of TcTREZO are also detected in steady-state RNA. TcTREZO transcripts are unspliced and not translated. The copy number of TcTREZO sequences was estimated to be [~]173 copies per haploid genome. TcTREZO appears to have been assembled by insertions of sequences into a progenitor element. Once associated with each other, these subunits were amplified as a new transposable element. TcTREZO shows site specificity for insertion, suggesting that a sequence-specific endonuclease could be responsible for its insertion at a unique site.

Numerical Analysis of Nanoparticle-Structured Plasmon Waveguides of Light - Mayergoyz, Issak D; Zhang,Zhenyu (Magnetics, IEEE Transactions on, 2007)
A novel numerical approach to the analysis of nanoparticle-structured plasmon waveguides of light is presented. The extinct cross-sections and resonance (propagation) frequencies are computed for various geometries of these waveguides and compared with available experimental data. The computational results for resonance frequencies corresponding to different light polarizations are reported as well
Keywords: analysis; optical; analysis; resonant; cross-sections; light; Frequency; frequency; light; nanoparticle-structured; plasmon; polarisation; light; polarization; numerical; propagation; numerical; waveguides; light; waveguides; plasmonics; plasmons

Numerical Analysis of Plasmon Resonances in Metallic Nanoshells - Mayergoyz, Issak D; Zhang,Zhenyu (Magnetics, IEEE Transactions on, 2007)
A novel boundary integral equation-based technique for the direct computations of resonance frequencies for plasmon resonances in metallic nanoshells is presented. In this technique, the calculation of resonance frequencies is reduced to a generalized eigenvalue problem. Numerical results that demonstrate fairly good agreement with theoretical results and available experimental data are reported
Keywords: analysis; plasmon; and; boundary; eigenfunctions; nanostructured; equation-based; equations; eigenvalues; frequency; boundary; integral; materials; nanotechnology; plasmons; nanoshells; numerical; problems; metallic; resonance; resonant; techniques; eigenvalue

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

Optimal expected-case planar point location - Arya,S.; Malamatos,T.; Mount, Dave; Wong,K.C. (SIAM Journal on Computing, 2007)
Point location is the problem of preprocessing a planar polygonal subdivision S of size ninto a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. We consider this problem from the perspective of expected query time. We are given the probabilities pz that the query point lies within each cell z ∈ S. The entropy H of the resulting discrete probability distribution is the dominant term in the lower bound on the expected-case query time. We show that it is possible to achieve query time H + O( √ H + 1) with space O(n), which is optimal up to lower order terms in the query time. We extend this result to subdivisions with convex cells, assuming a uniform query distribution within each cell. In order to achieve space efficiency, we introduce the concept of entropy-preserving cuttings.

Optimization of nonlinear error for weighted essentially non-oscillatory methods in direct numerical simulations of compressible turbulence - Taylor,Ellen M.; Wu,Minwei; Martin, M.P (Journal of Computational Physics, 2007)
Weighted essentially non-oscillatory (WENO) methods have been developed to simultaneously provide robust shock-capturing in compressible fluid flow and avoid excessive damping of fine-scale flow features such as turbulence. Under certain conditions in compressible turbulence, however, numerical dissipation remains unacceptably high even after optimization of the linear component that dominates in smooth regions. We therefore construct and evaluate WENO schemes that also reduce dissipation due to one source of nonlinear error: the smoothness measurement that governs the application of stencil adaptation away from the linear optimal stencil. Direct numerical simulations (DNS) include a one-dimensional Euler solution and three-dimensional compressible isotropic turbulence. We find that the smoothness measurement modifications that we call the “relative smoothness limiter” and the “relative total variation limiter” each significantly enhance thez grid-convergence properties of WENO schemes while generating, respectively, small and moderate additional computational expense. Moreover, we observe these techniques to be broadly effective regardless of flow configuration.
Keywords: Compressible turbulence; direct numerical simulation; Limiters; Linear dissipation; Non-linear dissipation; Numerical dissipation; Shock capturing

Path splicing: Reliable connectivity with rapid recovery - Motiwala,M.; Feamster, Nick; Vempala,S. (ACM SIGCOMM HotNets VI, 2007)
We present path splicing, a primitive that constructs net-work paths from multiple independent routing processes that run over a single network topology. The routing processes compute distinct routing trees using randomly perturbed link weights. A few additional bits in packet headers give end systems access to a large number of paths. By changing these bits, nodes can redirect traffic without detailed knowl- edge of network paths. Assembling paths by “splicing” segments can yield up to an exponential improvement in path diversity for only a linear increase in storage and mes- sage complexity. We present randomized approaches for slice construction and failure recovery that achieve near- optimal performance and are extremely simple to config- ure. Our evaluation of path splicing on realistic ISP topolo- gies demonstrates a dramatic increase in reliability that ap- proaches the best possible using only a small number of slices and for only a small increase in latency.

Path splicing with network slicing - Feamster, Nick; Motiwala,M.; Vempala,S. (Proc. ACM SIGCOMM Hot-Nets, 2007)

Pointerless implementation of hierarchical simplicial meshes and efficient neighbor finding in arbitrary dimensions - Atalay,F. B; Mount, Dave; Mitchell,J. (International Journal of Computational Geometry and Applications, 2007)
We describe a pointerless representation of hierarchical regular simplicial meshes, basedon a bisection approach proposed by Maubach. We introduce a new labeling scheme, called an LPT code, which uniquely encodes the geometry of each simplex of the hi- erarchy, and we present rules to compute the neighbors of a given simplex efficiently through the use of these codes. In addition, we show how to traverse the associated tree and how to answer point location and interpolation queries. Our system works in arbitrary dimensions.

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

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

A practical approximation algorithm for the LMS line estimator - Mount, Dave; Netanyahu,Nathan S.; Romanik,Kathleen; Silverman,Ruth; Wu,Angela Y. (Computational Statistics & Data Analysis, 2007)
The problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. Robust estimators are widely used because of their lack of sensitivity to outlying data points. The least median-of-squares (LMS) regression line estimator is among the best known robust estimators. Given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0 < q ⩽ 1 . This problem is equivalent to finding the strip defined by two parallel lines of minimum vertical separation that encloses at least half of the points.The best known exact algorithm for this problem runs in O ( n 2 ) time. We consider two types of approximations, a residual approximation, which approximates the vertical height of the strip to within a given error bound ε r ⩾ 0 , and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound ε q ⩾ 0 . We present two randomized approximation algorithms for the LMS line estimator. The first is a conceptually simple quantile approximation algorithm, which given fixed q and ε q > 0 runs in O ( n log n ) time. The second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. We prove that when used as a quantile approximation, this algorithm's expected running time is O ( n log 2 n ) . We present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.
Keywords: Approximation algorithms; least median-of-squares regression; line arrangements; line fitting; randomized algorithms; robust estimation

Provable algorithms for joint optimization of transport, routing and MAC layers in wireless ad hoc networks - Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (Proc. DialM-POMC Workshop on Foundations of Mobile Computing, 2007)

Relating Complexity and Precision in Control Flow Analysis - David Van Horn; Mairson, Harry G. (ICFP '07 Proceedings of the 12th ACM SIGPLAN International Conference on Functional Programming, 2007)
We analyze the computational complexity of kCFA, a hierarchy of control flow analyses that determine which functions may be applied at a given call-site. This hierarchy specifies related decision problems, quite apart from any algorithms that may implement their solutions. We identify a simple decision problem answered by this analysis and prove that in the 0CFA case, the problem is complete for polynomial time. The proof is based on a nonstandard, symmetric implementation of Boolean logic within multiplicative linear logic (MLL). We also identify a simpler version of 0CFA related to η-expansion, and prove that it is complete for logarithmic space, using arguments based on computing paths and permutations. For any fixed k>0, it is known that kCFA (and the analogous decision problem) can be computed in time exponential in the program size. For k=1, we show that the decision problem is NP-hard, and sketch why this remains true for larger fixed values of k. The proof technique depends on using the approximation of CFA as an essentially nondeterministic computing mechanism, as distinct from the exactness of normalization. When k=n, so that the "depth" of the control flow analysis grows linearly in the program length, we show that the decision problem is complete for exponential time. In addition, we sketch how the analysis presented here may be extended naturally to languages with control operators. All of the insights presented give clear examples of how straightforward observations about linearity, and linear logic, may in turn be used to give a greater understanding of functional programming and program analysis.
Keywords: complexity; continuation; control flow analysis; eta expansion; geometry of interaction; linear logic; normalization; proofnet; static analysis

Reliable Effects Screening: A Distributed Continuous Quality Assurance Process for Monitoring Performance Degradation in Evolving Software Systems - Yilmaz,C.; Porter, Adam; Krishna,A. S; Memon, Atif M.; Schmidt,D. C; Gokhale,A.S.; Natarajan,B. (Software Engineering, IEEE Transactions on, 2007)
Developers of highly configurable performance-intensive software systems often use in-house performance-oriented "regression testing" to ensure that their modifications do not adversely affect their software's performance across its large configuration space. Unfortunately, time and resource constraints can limit in-house testing to a relatively small number of possible configurations, followed by unreliable extrapolation from these results to the entire configuration space. As a result, many performance bottlenecks escape detection until systems are fielded. In our earlier work, we improved the situation outlined above by developing an initial quality assurance process called "main effects screening". This process 1) executes formally designed experiments to identify an appropriate subset of configurations on which to base the performance-oriented regression testing, 2) executes benchmarks on this subset whenever the software changes, and 3) provides tool support for executing these actions on in-the-field and in-house computing resources. Our initial process had several limitations, however, since it was manually configured (which was tedious and error-prone) and relied on strong and untested assumptions for its accuracy (which made its use unacceptably risky in practice). This paper presents a new quality assurance process called "reliable effects screening" that provides three significant improvements to our earlier work. First, it allows developers to economically verify key assumptions during process execution. Second, it integrates several model-driven engineering tools to make process configuration and execution much easier and less error prone. Third, we evaluate this process via several feasibility studies of three large, widely used performance-intensive software frameworks. Our results indicate that reliable effects screening can detect performance degradation in large-scale systems more reliably and with significantly less resources than conventional t- echniques
Keywords: configuration subset; distributed continuous quality assurance process; evolving software systems; in house testing; main effects screening; performance bottlenecks; performance degradation monitoring; performance intensive software systems; process configuration; process execution; program testing; regression testing; reliable effects screening; software benchmarks; Software performance; software performance evaluation; Software quality; software reliability; tool support

Report on the Fourth International Workshop on Data Management for Sensor Networks (DMSN 2007) - Balazinska,Magdalena; Deshpande, Amol; Labrinidis,Alexandros; Luo,Qiong; Madden,Samuel; Yang,Jun (SIGMOD Rec., 2007)
Sensor networks enable an unprecedented level of access to the physical world, and hold tremendous potential to revolutionize many application domains. Research on sensor networks spans many areas of computer science, and there are now major conferences, e.g., IPSN and SenSys, devoted to sensor networks. However, there is no focused forum for discussion of early and innovative work on data management in sensor networks. The International Workshop on Data Management for Sensor Networks (DMSN), inaugurated in 2004, aims to fill this significant gap in the database and sensor network communities.

Semantics-Preserving Design of Embedded Control Software from Synchronous Models - Mangeruca,L.; Baleani,M.; Ferrari,A.; Sangiovanni-Vincentelli,A. (Software Engineering, IEEE Transactions on, 2007)
The design of embedded controllers is experiencing a growth in complexity as embedded systems increase their functionality while they become ubiquitous in electronic appliances, cars, airplanes, etc. As requirements become more challenging, mathematical models gain importance for mastering complexity. Among the different computational models proposed, synchronous models have proved to be the most widely used for control dominated applications. While synchronous models simplify the way of dealing with concurrency by decoupling functional and timing aspects, their software implementation on multitasking and multiprocessor platforms is far from straightforward, because of the asynchronous nature of most industrial software platforms. Known solutions in the literature either restrict the solution space or focus on special cases. We present a method for preserving the synchronous semantics through buffer-based intertask communication mechanisms, grounded on an abstraction of the target platform. This allows us to deal with any task set and, most importantly, being independent of the implementation, to explore the design space effectively.
Keywords: embedded control software; embedded systems; multiprocessing programs; multiprocessor; multitasking; semantics-preserving design; software engineering; software implementation; systems analysis

A Signal Processing and Randomization Perspective of Robust and Secure Image Hashing - M. Wu; Mao,Yinian; Swaminathan,Ashwin (Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on, 2007)
An image hash is a content-based compact representation of an image and finds applications in image authentication, watermarking, and image similarity comparison. This paper reviews representative approaches developed by the research community in constructing robust and secure image hash. A unified framework and case studies on representative image hash schemes are presented to demonstrate important roles of signal processing and controlled randomization in constructing and evaluating robust and secure hashing for visual data.

Signal Processing for Biometric Systems [DSP Forum] - Jain, A.K.; Chellapa, Rama; Draper, S.C.; Memon, N.; Phillips,P.J.; Vetro, A. (Signal Processing Magazine, IEEE, 2007)
This IEEE signal processing magazine (SPM) forum discuses signal processing applications, technologies, requirements, and standardization of biometric systems. The forum members bring their expert insights into issues such as biometric security, privacy, and multibiometric and fusion techniques. The invited forum members are Prof. Anil K. Jain of Michigan State University, Prof. Rama Chellappa of the University of Maryland, Dr. Stark C. Draper of theUniversity of Wisconsin in Madison, Prof. Nasir Memon of Polytechnic University, and Dr. P. Jonathon Phillips of the National Institute of Standards and Technology. The moderator of the forum is Dr. Anthony Vetro of Mitsubishi Electric Research Labs, and associate editor of SPM.
Keywords: (access; biometric; control); security; signal; forum; signal; magazine; PROCESSING; processing; security; biometric; standardization; fusion; systems; technique; multibiometric; technique; signal; technology; biometrics

A simple entropy-based algorithm for planar point location - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (ACM Transactions on Algorithms (TALG), 2007)
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this article, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.
Keywords: Entropy; expected-case complexity; Point location; polygonal subdivision; randomized algorithms; trapezoidal maps

Skoll: A Process and Infrastructure for Distributed Continuous Quality Assurance - Porter, Adam; Yilmaz,C.; Memon, Atif M.; Schmidt,D. C; Natarajan,B. (Software Engineering, IEEE Transactions on, 2007)
Software engineers increasingly emphasize agility and flexibility in their designs and development approaches. They increasingly use distributed development teams, rely on component assembly and deployment rather than green field code writing, rapidly evolve the system through incremental development and frequent updating, and use flexible product designs supporting extensive end-user customization. While agility and flexibility have many benefits, they also create an enormous number of potential system configurations built from rapidly changing component implementations. Since today's quality assurance (QA) techniques do not scale to handle highly configurable systems, we are developing and validating novel software QA processes and tools that leverage the extensive computing resources of user and developer communities in a distributed, continuous manner to improve software quality significantly. This paper provides several contributions to the study of distributed, continuous QA (DCQA). First, it shows the structure and functionality of Skoll, which is an environment that defines a generic around-the-world, around-the-clock QA process and several sophisticated tools that support this process. Second, it describes several novel QA processes built using the Skoll environment. Third, it presents two studies using Skoll: one involving user testing of the Mozilla browser and another involving continuous build, integration, and testing of the ACE+TAO communication software package. The results of our studies suggest that the Skoll environment can manage and control distributed continuous QA processes more effectively than conventional QA processes. For example, our DCQA processes rapidly identified problems that had taken the ACE+TAO developers much longer to find and several of which they had not found. Moreover, the automatic analysis of QA results provided developers information that enabled them to quickly find the root causes of problems
Keywords: ACE+TAO communication software package; component assembly; component deployment; distributed continuous quality assurance; distributed development teams; distributed processing; end-user customization; flexible product design; incremental development; object-oriented programming; Skoll; software engineering; Software quality; systems analysis

Soma models of the behaviors of stakeholders in the afghan drug economy: A preliminary report - Sliva,A.; Martinez,V.; Simari,G. I; V.S. Subrahmanian (Proc. 2007 Intl. Conf. on Computational Cultural Dynamics, 2007)
Most cultural reasoning today is done by anthropologists andsociologists who use their detailed knowledge of culture to make predictions about how a given group will respond to a given situation. The main problem with this is that experts in a particular culture or subculture are few and not readily accessible to the many who might suddenly need to tap their expertise (e.g. in cases of war or conflict). In this paper, we briefly describe how the SOMA (Stochastic Opponent Mod- eling Agents) paradigm proposed by the authors can and has been used to model the behaviors of various stake-holders in the drug trade in Afghanistan.

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

SplicePort--An interactive splice-site analysis tool - Dogan,R. I; Getoor, Lise; Wilbur,W. J; Mount, Stephen M. (Nucleic Acids Research, 2007)
SplicePort is a web-based tool for splice-site analysis that allows the user to make splice-site predictions for submitted sequences. In addition, the user can also browse the rich catalog of features that underlies these predictions, and which we have found capable of providing high classification accuracy on human splice sites. Feature selection is optimized for human splice sites, but the selected features are likely to be predictive for other mammals as well. With our interactive feature browsing and visualization tool, the user can view and explore subsets of features used in splice-site prediction (either the features that account for the classification of a specific input sequence or the complete collection of features). Selected feature sets can be searched, ranked or displayed easily. The user can group features into clusters and frequency plot WebLogos can be generated for each cluster. The user can browse the identified clusters and their contributing elements, looking for new interesting signals, or can validate previously observed signals. The SplicePort web server can be accessed at http://www.cs.umd.edu/projects/SplicePort and http://www.spliceport.org.

Stencil adaptation properties of a WENO scheme in direct numerical simulations of compressible turbulence - Taylor,E. M; Martin, M.P (Journal of Scientific Computing, 2007)

Stochastic Communication: A New Paradigm for Fault-Tolerant Networks-on-Chip - Bogdan, Paul; Dumitraş Tudor; Marculescu, Radu (VLSI Design, 2007)
As CMOS technology scales down into the deep-submicron (DSM) domain, the costs of design and verification for Systems-on-Chip (SoCs) are rapidly increasing. Relaxing the requirement of 100% correctness for devices and interconnects drastically reduces the costs of design but, at the same time, requires SoCs to be designed with some degree of system-level fault-tolerance. Towards this end, this paper introduces a novel communication paradigm for SoCs, called stochastic communication. This scheme separates communication from computation by allowing the on-chip interconnect to be designed as a reusable IP and also provides a built-in tolerance to DSM failures, without a significant performance penalty. By using this communication scheme, a large percentage of data upsets, packet losses due to buffers overflow, and severe levels of synchronization failures can be tolerated, while providing high levels of performance.

Storage routing for dtn congestion control - Seligman,M.; Fall,K.; Mundur, Padma (Wireless communications and mobile computing, 2007)

Structural Biology: Analysis of 'downhill' protein folding; Analysis of protein-folding cooperativity (Reply) - Sadqi,Mourad; Fushman, David; Muñoz,Victor (Nature, 2007)
Ferguson et al. and Zhou and Bai criticize the quality of our nuclear magnetic resonance (NMR) data and atom-by-atom analysis of global 'downhill' folding, also claiming that the data are compatible with two-state folding.
Keywords: Astronomy; astrophysics; Biochemistry; Bioinformatics; Biology; biotechnology; cancer; cell cycle; cell signalling.; climate change; Computational Biology; development; developmental biology; DNA; drug discovery; earth science; ecology; environmental science; Evolution; evolutionary biology; functional genomics; Genetics; Genomics; geophysics; immunology; interdisciplinary science; life; marine biology; materials science; medical research; medicine; metabolomics; molecular biology; molecular interactions; nanotechnology; Nature; neurobiology; neuroscience; palaeobiology; pharmacology; Physics; proteomics; quantum physics; RNA; Science; science news; science policy; signal transduction; structural biology; systems biology; transcriptomics

Surface Segmentation through Concentrated Curvature - Mesmoudi,M. M.; Danovaro,E.; De Floriani, Leila; Port,U. (Image Analysis and Processing, 2007. ICIAP 2007. 14th International Conference on, 2007)
Curvature is one of the most relevant notions that links the metric properties of a surface to its geometry and to its topology (Gauss-Bonnet theorem). In the literature, a variety of approaches exist to compute curvatures in the discrete case. Several techniques are computationally intensive or suffer from convergence problems. In this paper, we discuss the notion of concentrated curvature, introduced by Troyanov [24]. We discuss properties of this curvature and compare with a widely-used technique that estimates the Gaussian curvatures on a triangulated surface. We apply our STD method [13] for terrain segmentation to segment a surface by using different curvature approaches and we illustrate our comparisons through examples.
Keywords: curvature; convergence; curvatures; concentrated; Gauss-Bonnet; problems; surface; processes; image; segmentation; segmentation; terrain; segmentation; triangulated; surface; Gaussian; theorem; Gaussian

Target Tracking Using a Joint Acoustic Video System - Cevher, V.; Sankaranarayanan,A. C; McClellan, J.H.; Chellapa, Rama (Multimedia, IEEE Transactions on, 2007)
In this paper, a multitarget tracking system for collocated video and acoustic sensors is presented. We formulate the tracking problem using a particle filter based on a state-space approach. We first discuss the acoustic state-space formulation whose observations use a sliding window of direction-of-arrival estimates. We then present the video state space that tracks a target's position on the image plane based on online adaptive appearance models. For the joint operation of the filter, we combine the state vectors of the individual modalities and also introduce a time-delay variable to handle the acoustic-video data synchronization issue, caused by acoustic propagation delays. A novel particle filter proposal strategy for joint state-space tracking is introduced, which places the random support of the joint filter where the final posterior is likely to lie. By using the Kullback-Leibler divergence measure, it is shown that the joint operation of the filter decreases the worst case divergence of the individual modalities. The resulting joint tracking filter is quite robust against video and acoustic occlusions due to our proposal strategy. Computer simulations are presented with synthetic and field data to demonstrate the filter's performance
Keywords: (numerical; acoustic; adaptive; appearance; approach; synchronization; time-delay; data; delay; acoustic; divergence; acoustic; estimate; joint; estimation; hidden; feature; filter; sliding; Filtering; fusion; multitarget; fusion; synchronisation; target; highways; direction-of-arrival; Kullback-Leibler; methods); sensor; model; particle; processing; processing; automated; propagation; removal; optical; signal; system; multimodal; tracking; acoustic; tracking; direction-of-arrival; tracking; occlusion; online; tracking; particle; tracking; video; variable; visual; video; window; state-space

Task scheduling in large camera networks - Lim,S.N.; Davis, Larry S.; Mittal,A. (Computer Vision–ACCV 2007, 2007)
Visibility in architectural layouts affects humannavigation, so a suitable representation of visibility context is useful in understanding human activity. Motivated by studies of spatial behavior, we use a set of features from visibility analysis to represent spatial context in the interpretation of human activity. An agent’s goal, belief about the world, trajectory and visible layout are considered to be random variables that evolve with time during the agent’s movement, and are modeled in a Bayesian framework. We design a search-based task in a sprite-world, and compare the results of our framework to those of human subject experiments. Our findings confirm that knowledge of spatial layout improves human interpretations of the trajectories (implying that visibility context is useful in this task). Since our framework demonstrates performance close to that of human subjects with knowledge of spatial layout, our findings confirm that our model makes adequate use of visibility context. In addition, the representation we use for visibility context allows our model to generalize well when presented with new scenes.

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

Test suite prioritization by interaction coverage - Bryce,Renée C.; Memon, Atif M. (Workshop on Domain specific approaches to software test automation: in conjunction with the 6th ESEC/FSE joint meeting, 2007)
Event-driven software (EDS) is a widely used class of software that takes sequences of events as input, changes state, and outputs new event sequences. Managing the size of tests suites for EDS is difficult as the number of event combinations and sequences grow exponentially with the number of events. We propose a new testing technique that extends software interaction testing. Traditional software interaction testing systematically examines all t-way interactions of parameters for a program. This paper extends the notion to t-way interactions over sequences of events. The technique applies to many classes of software; we focus on that of EDS. As a proof-of-concept, we prioritize existing test suites for four GUI-based programs by t-way interaction coverage. We compare the rate of fault detection with that of several other prioritization criteria. Results show that prioritization by interaction coverage has the fastest rate of fault detection in half of our experiments, making the most impact when tests have high interaction coverage.
Keywords: t-way interaction coverage; combinatorial interaction testing; covering arrays; event driven software; test suite prioritization

A theoretical model of children's storytelling using physically-oriented technologies (SPOT) - Guha,M.L.; Druin, Allison; Montemayor,J.; Chipman,G.; Farber,A. (Journal of Educational Multimedia and Hypermedia, 2007)

To fill or not to fill: the gas station problem - Khuller, Samir; Malekian,A.; Mestre,J. (Algorithms–ESA 2007, 2007)
In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from s to t, or the cheapest tour visiting a given set of locations. Surprisingly, the problem of find the cheapest way to go from s to t can be solved in polynomial time and is not NP-complete. For most other versions however, the problem is NP-complete and we develop polynomial time approximation algorithms for these versions.

Tracing malicious relays in cooperative wireless communications - Mao,Y.; Wu,M. (Information Forensics and Security, IEEE Transactions on, 2007)

TREC 2007 ciQA Task: University of Maryland - Madnani,N.; Jimmy Lin; Dorr, Bonnie J (Proceedings of TREC, 2007)

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

Unicity Distance of Robust Image Hashing - Mao,Yinian; M. Wu (Information Forensics and Security, IEEE Transactions on, 2007)
An image hash is a randomized compact representation of image content and finds applications in image authentication, image and video watermarking, and image similarity comparison. Usually, an image-hashing scheme is required to be robust and secure, and the security issue is particularly important in applications, such as multimedia authentication, watermarking, and fingerprinting. In this paper, we investigate the security of image hashing from the perspective of unicity distance, a concept pioneered by Shannon in one of his seminal papers. Using two recently proposed image-hashing schemes as representatives, we show that the concept of unicity distance can be adapted to evaluate the security of image hashing. Our analysis shows that the secret hashing key, or its equivalent form, can be estimated with high accuracy when the key is reused several dozen times. The estimated unicity distance determines the maximum number of key reuses in the investigated hashing schemes. A countermeasure of randomized key initialization is discussed to avoid key reuse and strengthen the security of robust image hashing.
Keywords: authentication; image; authentication; randomized; coding; image; compact; comparison; multimedia; content; image; data; distance; watermarking; image; fingerprinting; image; hashing; unicity; image; initialization; robust; key; of; representation; randomized; representation; security; similarity

Using Content-Addressable Networks for Load Balancing in Desktop Grids - Kim,Jik-Soo; Keleher,Peter; Marsh,Michael; Bhattacharjee, Bobby; Sussman, Alan (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2007)
Desktop grids combine Peer-to-Peer and Grid computing techniques to improvethe robustness, reliability and scalability of job execution infrastructures. However, efficiently matching incoming jobs to available system resources and achieving good load balance in a fully decentralized and heterogeneous computing environment is a challenging problem. In this paper, we extend our prior work with a new decentralized algorithm for maintaining approximate global load information, and a job pushing mechanism that uses the global information to push jobs towards underutilized portions of the system. The resulting system more effectively balances load and improves overall system throughput. Through a comparative analysis of experimental results across different system configurations and job profiles, performed via simulation, we show that our system can reliably execute Grid applications on a distributed set of resources both with low cost and with good load balance.
Keywords: Technical Report

Using GUI Run-Time State as Feedback to Generate Test Cases - Xun Yuan; Memon, Atif M. (Software Engineering, 2007. ICSE 2007. 29th International Conference on, 2007)
This paper presents a new automated model-driven technique to generate test cases by using feedback from the execution of a "seed test suite" on an application under test (AUT). The test cases in the seed suite are designed to be generated automatically and executed very quickly. During their execution, feedback obtained from the AUT's run-time state is used to generate new, "improved" test cases. The new test cases subsequently become part of the seed suite. This "anytime technique" continues iteratively, generating and executing additional test cases until resources are exhausted or testing goals have been met. The feedback-based technique is demonstrated for automated testing of graphical user interfaces (GUIs). An existing abstract model of the GUI is used to automatically generate the seed test suite. It is executed; during its execution, state changes in the GUI pinpoint important relationships between GUI events, which evolve the model and help to generate new test cases. Together with a reverse- engineering algorithm used to obtain the initial model and seed suite, the feedback-based technique yields a fully automatic, end-to-end GUI testing process. A feasibility study on four large fielded open-source software (OSS) applications demonstrates that this process is able to significantly improve existing techniques and help identify/report serious problems in the OSS. In response, these problems have been fixed by the developers of the OSS in subsequent versions.
Keywords: application under test; automated test case generation; Feedback; feedback-based technique; Graphical user interfaces; GUI run-time state; model-driven technique; open-source software; program testing; public domain software; reverse engineering; reverse-engineering algorithm; seed test suite

Using paraphrases for parameter tuning in statistical machine translation - Madnani,Nitin; Ayan,Necip Fazil; Resnik, Philip; Dorr, Bonnie J (Proceedings of the Second Workshop on Statistical Machine Translation, 2007)
Most state-of-the-art statistical machine translation systems use log-linear models, which are defined in terms of hypothesis features and weights for those features. It is standard to tune the feature weights in order to maximize a translation quality metric, using held-out test sentences and their corresponding reference translations. However, obtaining reference translations is expensive. In this paper, we introduce a new full-sentence paraphrase technique, based on English-to-English decoding with an MT system, and we demonstrate that the resulting paraphrases can be used to drastically reduce the number of human reference translations needed for parameter tuning, without a significant decrease in translation quality.

Using paraphrases for parameter tuning in statistical machine translation - Madnani,N.; Ayan,N.F.; Resnik, Philip; Dorr, Bonnie J (Proceedings of the Second Workshop on Statistical Machine Translation, 2007)

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

Vision Geometry XV - Latecki,L.J.; Mount, Dave; Wu,A. Y (Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, 2007)

Alternative custodians for congestion control in delay tolerant networks - Seligman,Matthew; Fall,Kevin; Mundur, Padma (Proceedings of the 2006 SIGCOMM workshop on Challenged networks, 2006)
Keywords: delay tolerant network; Routing

Analysis of Shock Motion in a Compression Ramp Configuration using DNS data - Wu,M.; Martin, M.P (Bulletin of the American Physical Society, 2006)

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

Assessing the Attack Threat due to IRC Channels - Meyer,R.; Michel Cukier (2006)
This practical experience report presents the results of an investigation into the threat of attacks associated with the chat medium IRC. A combination of simulated users (i.e., bots), some configured with scripts that simulated conversations, and regular users were used. The average number of attacks per day a user on IRC can expect, the effect of channel activity, gender based on the name, and network type on the number of attacks were determined. The social structure of IRC channels and the types of users that use it were analyzed. The results indicate that attacks through IRC channels come from human users selecting targets rather than automated scripts targeting every user in a channel
Keywords: attack threat assessment; channel activity; client-server systems; computer crime; intrusion-resilient channels; IRC channels; IRC protocols; Protocols; telecommunication channels; telecommunication security

A Bayesian model for supervised clustering with the Dirichlet process prior - Daumé, Hal; Marcu,D. (Journal of Machine Learning Research, 2006)

Bayesian query-focused summarization - Daumé, Hal; Marcu,Daniel (Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, 2006)
We present BAYESUM (for "Bayesian summarization"), a model for sentence extraction in query-focused summarization. BAYESUM leverages the common case in which multiple documents are relevant to a single query. Using these documents as reinforcement for query terms, BAYESUM is not afflicted by the paucity of information in short queries. We show that approximate inference in BAYESUM is possible on large data sets and results in a state-of-the-art summarization system. Furthermore, we show how BAYESUM can be understood as a justified query expansion technique in the language modeling for IR framework.

Bootstrapping free-space optical networks - Liu,F.; Vishkin, Uzi; Milner,S. (Selected Areas in Communications, IEEE Journal on, 2006)
We introduce a challenging problem in establishing and initially configuring or bootstrapping a Free Space Optical (FSO) network. In such networks, it is assumed that each communication node is a base station, including a router and wireless optical communications hardware, and its number of transceivers is limited. In addition, the FSO networks are characterized by narrow beam, directional links (e.g., operating at 1550 nm) and support up to Gbps data rates. The problem of initially configuring the transceivers to form a connected topology is NP-complete because of the transceiver limitation. What makes this problem even more challenging is the need to configure the transceiver in a "distributed" fashion, because a node can have only direct knowledge of its neighbors. We have developed a fully distributed approximation algorithm, which constructs a spanning tree with maximal node degree at most one larger than that in the optimal solution. Due to its distributed nature, this algorithm outperforms known serial algorithms. For a graph with 200 nodes generated in some randomized model, speed-ups greater than 6 have been demonstrated.
Keywords: algorithm; free-space; algorithms; optical; approximation; communication; telecommunication; communications; configuration; randomized; FSO; base; hardware; distributed; model; spanning; network; network; network; node; connected; optical; router; optical; routing; telecommunication; searching; station; bootstrapping; communication; topology; distributed; topology; transceivers; tree; transceiver; tree; wireless

A bootstrapping model for directional wireless networks - Milner,S.; Llorca,J.; Anibha,A.; Vishkin, Uzi (Communications Letters, IEEE, 2006)
Initially configuring or bootstrapping a connected topology in directional wireless networks is a challenging problem, especially when nodes only have local connectivity information and a limited number of transceivers. This paper presents a scalable bootstrapping model which integrates: 1) a distributed bottom-up algorithm that constructs a spanning tree with degree at most one larger than the optimal 2) a resource discovery algorithm for efficient dissemination of local connectivity information, and 3) synchronization protocols to guarantee the efficient emergence of overall network connectivity from local interactions. We investigate the feasibility and scalability of the proposed model. Results are presented for different network systems, with varying size and signaling data rates.
Keywords: (mathematics); algorithm; resource; algorithm; spanning; bootstrapping; bottom-up; discovery; model; directional; network; distributed; networks; trees; protocols; protocols; radio; tree; synchronization; wireless

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

Characterization of the turbulence structure in supersonic boundary layers using DNS data - Ringuette,M. J; Martin, M.P; Smits,A. J.; Wu,M. (AIAA Paper, 2006)

A client-driven approach for channel management in wireless LANs - Mishra,A.; Brik,V.; Banerjee,S.; Srinivasan, Aravind; Arbaugh, William A. (IEEE Infocom, 2006)
We propose an efficient client-based approach for channel man-agement (channel assignment and load balancing) in 802.11-based WLANs that lead to better usage of the wireless spectrum. This approach is based on a “conflict set coloring” formulation that jointly performs load balancing along with channel assignment. Such a formulation has a number of advantages. First, it explicitly captures interference effects at clients. Next, it intrinsically ex- poses opportunities for better channel re-use. Finally, algorithms 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 addi- tion to single network scenarios, the conflict set coloring formu- lation is well suited for channel assignment where multiple wire- less networks share and contend for spectrum in the same physical space. Our results over a wide range of both simulated topologies and in-building testbed experiments indicate that our approach improves application level performance at the clients by upto three times (and atleast 50%) in comparison to current best-known tech- niques.

Client-driven channel management for wireless LANs - Mishra,Arunesh; Brik,Vladimir; Banerjee,Suman; Srinivasan, Aravind; Arbaugh, William A. (SIGMOBILE Mob. Comput. Commun. Rev., 2006)
With the explosive growth in the density of 802.11 access points (APs) in the form of hotspots and public/home access networks, coordinating the shared use of spectrum has become an important problem. The irregular coverage topologies present in WLANs due to the vagaries of the indoor RF environment make the channel assignment algorithms in cellular networks inapplicable [1, 2].

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

Constraint Integration for Multiview Pose Estimation of Humans with Self-Occlusions - Gupta,A.; Mittal,A.; Davis, Larry S. (3D Data Processing, Visualization, and Transmission, Third International Symposium on, 2006)
Detection of articulated objects such as humans is an important task in computer vision. We present a system that incorporates a variety of constraints in a unified multi- view framework to automatically detect humans in possibly crowded scenes. These constraints include the kinematic constraints, the occlusion of one part by another and the high correlation between the appearance of parts such as the two arms. The graphical structure (non-tree) obtained is optimized in a nonparametric belief propagation framework using prior based search.
Keywords: articulated; belief; constraint; multiview; detection; computer; detection; pose; estimation; estimation; nonparametric; framework; self-occlusion; computer; graphics; computer; method; graphical; methods; object; object; pose; propagation; structure; kinematic; vision; correlation

Constructing task visibility intervals for video surveillance - Lim,S.N.; Davis, Larry S.; Mittal,A. (Multimedia systems, 2006)
Vision systems are increasingly being deployed to perform complex surveillance 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 real-time 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. Such intervals can also be combined to form multi-task intervals, during which a single camera can collect videos suitable for multiple tasks simultaneously. Experimental results are provided to illustrate the system capabilities in constructing such task visibility intervals, followed by scheduling them using a greedy algorithm.

The cost of compatible refinement of simplex decomposition trees - Atalay,F.; Mount, Dave (Proceedings of the 15th International Meshing Roundtable, 2006)
A hierarchical simplicial mesh is a recursive decomposition of space into cells that are simplices. Such a mesh is compatible if pairs of neighboring cells meet along a single common face. Compatibility condition is important in many applications where the mesh serves as a discretization of a function. Enforcing compatibility involves refining the simplices of the mesh further, thus generates a larger mesh. We show that the size of a simplicial mesh grows by no more than a constant factor when compatibly refined. We prove a tight upper bound on the expansion factor for 2-dimensional meshes, and we sketch upper bounds for d-dimensional meshes.

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

Domain adaptation for statistical classifiers - Daumé, Hal; Marcu,D. (Journal of Artificial Intelligence Research, 2006)

Employing user profiles to test a new version of a GUI component in its context of use - Memon, Atif M. (Software Quality Journal, 2006)
Advancement in reusable component technology has had a significant impact on the development of complex graphical user interfaces (GUIs), which are front-ends to most of today’s software. Software developers can, with very little effort, integrate components into their software’s GUI. Problems, however, arise when new versions of GUI components replace their predecessors in an implementation. Often, the inclusion of a new version of a component breaks some part of the software, i.e., tasks that end-users were able to perform before modifications were made can no longer be performed. Software developers (who also happen to be component users) are unable to perform adequate regression testing in this context because of several factors, including lack of source code, environmental side-effects on GUI rendering, event-driven nature of GUIs, and large number of possible permutations of events. This paper presents a new technique that end-users’ quality assurance (QA) teams can employ to test the new version of a component in its application context by using the existing version as a baseline. The technique combines lightweight event-level dynamic profiling to collect user profiles in a transparent manner, GUI reverse engineering to extract the structure of the component’s GUI, test case execution to replay the collected profiles on the new version, and GUI oracles that collect properties from the existing version. Empirical studies demonstrate the practicality, usefulness, and limitations of the technique.

Evaluation of Multilingual and Multi-modal Information Retrieval-Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, Alicante, Spain, September 19-21, 2006, Revised Selected Papers - Peters,C.; Clough,P.; Gey,F.; Karlgren,J.; Magnini,B.; Oard, Douglas; De Rijke,M.; Stempfhuber,M. (Seventh Workshop of the Cross-Language Evaluation Forum, CLEF 2006, 2006)

Exploiting independence for branch operations in Bayesian learning of C&RTs - Angelopoulos,N.; Cussens,J.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
In this paper we extend a methodology for Bayesian learning via MCMC, with the ability to grow arbitrarily long branches in C&RT models. We are able to do so by exploiting independence in the model construction process. The ability to grow branches rather than single nodes has been noted as desirable in the literature. The most singular feature of the underline methodology used here in comparison to other approaches is the coupling of the prior and the proposal. The main contribution of this paper is to show how taking advantage of independence in the coupled process, can allow branch growing and swapping for proposal models.

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

Fuzzy svm ensembles for relevance feedback in image retrieval - Rao,Y.; Mundur, Padma; Yesha,Y. (Image and Video Retrieval, 2006)

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

Image fusion using cokriging - Memarsadeghi,N.; Le Moigne,J.; Mount, Dave (Geosci. and Remote Sens. Symp., 2006. IGARSS 2006. IEEE Int. Conf. on, 2006)

Image Registration and Fusion Studies for the Integration of Multiple Remote Sensing Data - Le Moigne,J.; Cole-Rhodes,A.; Eastman,R.; Jain,P.; Joshua,A.; Memarsadeghi,N.; Mount, Dave; Netanyahu,N.; Morisette,J.; Uko-Ozoro,E. (Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, 2006)
The future of remote sensing will see the development of spacecraft formations, and with this development will come a number of complex challenges such as maintaining precise relative position and specified attitudes. At the same time, there will be increasing needs to understand planetary system processes and build accurate prediction models. One essential technology to accomplish these goals is the integration of multiple source data. For this integration, image registration and fusion represent the first steps and need to be performed with very high accuracy. In this paper, we describe studies performed in both image registration and fusion, including a modular framework that was built to describe registration algorithms, a Web-based image registration toolbox, and the comparison of several image fusion techniques using data from the EO-1/ALI and Hyperion sensors
Keywords: ALI; EO-1; fusion studies; geophysical signal processing; Hyperion sensors; image registration; Internet; multiple remote sensing data; multiple source data; Remote sensing; Web-based image registration toolbox

On the importance of idempotence - Arya,Sunil; Malamatos,Theocharis; Mount, Dave (Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, 2006)
Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.
Keywords: Approximation algorithms; Idempotence; Range searching

Improved algorithms for data migration - Khuller, Samir; Kim,Y. A; Malekian,A. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2006)
Our work is motivated by the need to manage data on a collection of storage devices to handle dynamically changing demand. As demand for data changes, the system needs to automatically respond to changes in demand for different data items. The problem of computing a migration plan among the storage devices is called the data migration problem. This problem was shown to be NP-hard, and an approximation algorithm achieving an approximation factor of 9.5 was presented for the half-duplex communication model in [Khuller, Kim and Wan: Algorithms for Data Migration with Cloning, SIAM J. on Computing, Vol. 33(2):448–461 (2004)]. In this paper we develop an improved approximation algorithm that gives a bound of 6.5+o(1) using various new ideas. In addition, we develop better algorithms using external disks and get an approximation factor of 4.5. We also consider the full duplex communication model and develop an improved bound of 4 +o(1) for this model, with no external disks.

Initial findings from a three-year international case study exploring children's responses to literature in a digital library - Druin, Allison; Massey,S.; Weeks,A. C (Library trends, 2006)

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

JET: dynamic join-exit-tree amortization and scheduling for contributory key management - Mao,Yinian; Sun,Yan; M. Wu; Liu,K. J.R (IEEE/ACM Trans. Netw., 2006)
In secure group communications, the time cost associated with key updates in the events of member join and departure is an important aspect of quality of service, especially in large groups with highly dynamic membership. To achieve better time efficiency, we propose a join-exit-tree (JET) key management framework. First, a special key tree topology with join and exit subtrees is introduced to handle key updates for dynamic membership. Then, optimization techniques are employed to determine the capacities of join and exit subtrees for achieving the best time efficiency, and algorithms are designed to dynamically update the join and exit trees. We show that, on average, the asymptotic time cost for each member join/departure event is reduced to O(log (log n)) from the previous cost of O(log n), where n is the group size. Our experimental results based on simulated user activities as well as the real MBone data demonstrate that the proposed JET scheme can significantly improve the time efficiency, while maintaining low communication and computation cost, of tree-based contributory key management.
Keywords: contributory key management; dynamic tree topology; secure group communications; time efficiency

A joint signal processing and cryptographic approach to multimedia encryption - Mao,Yinian; M. Wu (Image Processing, IEEE Transactions on, 2006)
In recent years, there has been an increasing trend for multimedia applications to use delegate service providers for content distribution, archiving, search, and retrieval. These delegate services have brought new challenges to the protection of multimedia content confidentiality. This paper discusses the importance and feasibility of applying a joint signal processing and cryptographic approach to multimedia encryption, in order to address the access control issues unique to multimedia applications. We propose two atomic encryption operations that can preserve standard compliance and are friendly to delegate processing. Quantitative analysis for these operations is presented to demonstrate that a good tradeoff can be made between security and bitrate overhead. In assisting the design and evaluation of media security systems, we also propose a set of multimedia-oriented security scores to quantify the security against approximation attacks and to complement the existing notion of generic data security. Using video as an example, we present a systematic study on how to strategically integrate different atomic operations to build a video encryption system. The resulting system can provide superior performance over both generic encryption and its simple adaptation to video in terms of a joint consideration of security, bitrate overhead, and friendliness to delegate processing.
Keywords: access control; approximation attacks; atomic encryption operations; bitrate overhead; content distribution; cryptographic approach; delegate processing; delegate service providers; generic data security; media security systems; multimedia content confidentiality; m; Computer-Assisted; Computer-Assisted; Information Storage and Retrieval; Multimedia; Signal Processing

Keep Your Friends Close and Your Enemies Closer: The Art of Proximity Searching - Mount, Dave (Proceedings of the eighth Workshop on Algorithm Engineering and Experiments and the third Workshop on Analytic Algorithmics and Combinatorics, 2006)

KeyChains: A Decentralized Public-Key Infrastructure - Morselli,Ruggero; Bhattacharjee, Bobby; Katz, Jonathan; Marsh,Michael A (Technical Reports from UMIACS, UMIACS-TR-2006-12, 2006)
A Certification Authority (CA) can be used to certify keys and build apublic-key infrastructure (PKI) when all users trust the same CA. A decentralized PKI trades off absolute assurance on keys for independence from central control and improved scalability and robustness. The PGP ``web of trust'' model has been suggested as a decentralized certification system, and has been used with great success for secure email. Although the PGP web of trust model allows anyone to issue certificates which can be used to form certificate chains, the discovery and construction of certificate chains relies on centralized keyservers to store certificates and respond to queries. In this paper, we design and implement KeyChains, a peer-to-peer system which incorporates a novel lookup mechanism specifically tailored to the task of generating and retrieving certificate chains in completely unstructured networks. By layering our system on top of the web of trust model, we thus obtain the first PKI which is truly decentralized in all respects. Our analysis and simulations show that the resulting system is both efficient and secure.
Keywords: Technical Report

Learning through failure - Sato,T.; Kameya,Y.; De Raedt,L.; Dietterich,T.; Getoor, Lise; Muggleton,S. H (Probabilistic, Logical and Relational Learning-Towards a Synthesis, 2006)
PRISM, a symbolic-statistical modeling language we have been developing since '97, recently incorporated a program transformation technique to handle failure in generative modeling. I'll show this feature opens a way to new breeds of symbolic models, including EM learning from negative observations, constrained HMMs and finite PCFGs.

Learning to do HTN planning - Ilghami,O.; Nau, Dana S.; Munoz-Avila,H. (2006)
We describe HDL, an algorithm that learns HTN do- main descriptions by examining plan traces produced by an expert problem-solver. Prior work on learning HTN methods requires that all the methods’ informa- tion except for their preconditions be given in advance so that the learner can learn the preconditions. In con- trast, HDL has no prior information about the methods. In our experiments, in most cases HDL converged fully with no more than about 200 plan traces. Furthermore, even when HDL was given only half the plan traces it required to fully converge, it usually was able to pro- duce HTN methods that were sufficient to solve more than 3/4 of the planning problems in the test set.

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

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

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

Making a difference: integrating socially relevant projects into HCI teaching - Shneiderman, Ben; Bishop,Ann; Friedman,Batya; Lazar,Jonathan; Marsden,Gary; Nass,Cliff (CHI '06 extended abstracts on Human factors in computing systems, 2006)
Enriching courses on human-computer interaction with socially-relevant projects provides a compelling opportunity for students to improve their education and make socially beneficial contributions. By having clearly defined user communities outside the classroom, students have the chance to practice their interview, observation, and usability testing skills, while developing projects that continue beyond the semester. These projects often give students life-changing exposure to genuine needs and impressive results to include in their portfolio when seeking employment. Educators will present their strategies for arranging, supervising, and grading these projects. Students will describe their experience and how it influenced them.
Keywords: education; making a difference; relevance; service learning; social impact; team projects

MATHEMATICAL MODELS OF HYSTERESIS (DYNAMIC PROBLEMS IN HYSTERESIS) - Mayergoyz, Issak D (University of Maryland College Park, 2006)
This research has further advanced the current state of the art in the areas of dynamic aspects of hysteresis and nonlinear large scale magnetization dynamics. The results of this research will find important engineering applications in the areas of magnetic data storage technology and the emerging technology of “spintronics”. Our research efforts have been focused on the following tasks: • Study of fast (pulse) precessional switching of magnetization in magnetic materials. • Analysis of critical fields and critical angles for precessional switching of magnetization. • Development of inverse problem approach to the design of magnetic field pulses for precessional switching of magnetization. • Study of magnetization dynamics induced by spin polarized current injection. • Construction of complete stability diagrams for spin polarized current induced magnetization dynamics. • Development of the averaging technique for the analysis of the slow time scale magnetization dynamics. • Study of thermal effects on magnetization dynamics by using the theory of stochastic processes on graphs.

MauveDB: supporting model-based user views in database systems - Deshpande, Amol; Madden,Samuel (Proceedings of the 2006 ACM SIGMOD international conference on Management of data, 2006)
Real-world data --- especially when generated by distributed measurement infrastructures such as sensor networks --- tends to be incomplete, imprecise, and erroneous, making it impossible to present it to users or feed it directly into applications. The traditional approach to dealing with this problem is to first process the data using statistical or probabilistic models that can provide more robust interpretations of the data. Current database systems, however, do not provide adequate support for applying models to such data, especially when those models need to be frequently updated as new data arrives in the system. Hence, most scientists and engineers who depend on models for managing their data do not use database systems for archival or querying at all; at best, databases serve as a persistent raw data store.In this paper we define a new abstraction called model-based views and present the architecture of MauveDB, the system we are building to support such views. Just as traditional database views provide logical data independence, model-based views provide independence from the details of the underlying data generating mechanism and hide the irregularities of the data by using models to present a consistent view to the users. MauveDB supports a declarative language for defining model-based views, allows declarative querying over such views using SQL, and supports several different materialization strategies and techniques to efficiently maintain them in the face of frequent updates. We have implemented a prototype system that currently supports views based on regression and interpolation, using the Apache Derby open source DBMS, and we present results that show the utility and performance benefits that can be obtained by supporting several different types of model-based views in a database system.
Keywords: Query processing; regression; sensor networks; statistical models; uncertain data; views

Measuring human movement for biomechanical applications using markerless motion capture - Mündermann, L.; Corazza, S.; Chaudhari, A.M.; Andriacchi, T.P.; Sundaresan, A.; Chellapa, Rama (Proceedings of SPIE, 2006)
Modern biomechanical and clinical applications require the accurate capture of normal and pathological humanmovement without the artifacts associated with standard marker-based motion capture techniques such as soft tissue artifacts and the risk of artificial stimulus of taped-on or strapped-on markers. In this study, the need for new markerless human motion capture methods is discussed in view of biomechanical applications. Three different approaches for estimating human movement from multiple image sequences were explored. The first two approaches tracked a 3D articulated model in 3D representations constructed from the image sequences, while the third approach tracked a 3D articulated model in multiple 2D image planes. The three methods are systematically evaluated and results for real data are presented. The role of choosing appropriate technical equipment and algorithms for accurate markerless motion capture is critical. The implementation of this new methodology offers the promise for simple, time-efficient, and potentially more meaningful assessments of human movement in research and clinical practice.

Memory management for synthesis of DSP software - Murthy,P. K; Bhattacharyya, Shuvra S. (CRC, 2006)