Computing marginal distributions over continuous markov networks for statistical relational learning - Bröcheler,M.; Getoor, Lise (Advances in Neural Information Processing Systems (NIPS), 2010)
Continuous Markov random fields are a general formalism to model joint proba-bility distributions over events with continuous outcomes. We prove that marginal computation for constrained continuous MRFs is #P-hard in general and present a polynomial-time approximation scheme under mild assumptions on the struc- ture of the random field. Moreover, we introduce a sampling algorithm to com- pute marginal distributions and develop novel techniques to increase its effi- ciency. Continuous MRFs are a general purpose probabilistic modeling tool and we demonstrate how they can be applied to statistical relational learning. On the problem of collective classification, we evaluate our algorithm and show that the standard deviation of marginals serves as a useful measure of confidence.

COSI: Cloud Oriented Subgraph Identification in Massive Social Networks - Bröcheler,M.; Pugliese, A.; V.S. Subrahmanian (Advances in Social Networks Analysis and Mining (ASONAM), 2010 International Conference on, 2010)
Subgraph matching is a key operation on graph data. Social network (SN) providers may want to find all subgraphs within their social network that match certain query graph patterns. Unfortunately, subgraph matching is NP-complete, making its application to massive SNs a major challenge. Past work has shown how to implement subgraph matching on a single processor when the graph has 10-25M edges. In this paper, we show how to use cloud computing in conjunction with such existing single processor methods to efficiently match complex subgraphs on graphs as large as 778M edges. A cloud consists of one master compute node and k slave compute nodes. We first develop a probabilistic method to estimate probabilities that a vertex will be retrieved by a random query and that a pair of vertices will be successively retrieved by a random query. We use these probability estimates to define edge weights in an SN and to compute minimal edge cuts to partition the graph amongst k slave nodes. We develop algorithms for both master and slave nodes that try to minimize communication overhead. The resulting COSI system can answer complex queries over real-world SN data containing over 778M edges very efficiently.
Keywords: (online); answering; social; complexity; data; computing; edge; data; graph; estimation; query; handling; graph; matching; Internet; computational; matching; probability; query; network; subgraph; networking; NP-complete; cloud; pattern; probability; processing; social; theory; pattern; weight; graph

Crowdsourcing the evaluation of a domain-adapted named entity recognition system - Sayeed,Asad B.; Meyer,Timothy J.; Nguyen,Hieu C.; Buzek,Olivia; Weinberg, Amy (Association for Computational Linguistics, 2010)
Named entity recognition systems sometimes have difficulty when applied to data from domains that do not closely match the training data. We first use a simple rule-based technique for domain adaptation. Data for robust validation of the technique is then generated, and we use crowdsourcing techniques to show that this strategy produces reliable results even on data not seen by the rule designers. We show that it is possible to extract large improvements on the target data rapidly at low cost using these techniques.

Deploying sensor networks with guaranteed fault tolerance - Bredin,J. L; Demaine,E. D; Hajiaghayi, Mohammad T.; Rus,D. (IEEE/ACM Transactions on Networking (TON), 2010)

Design and Fabrication of a Multi-Material Compliant Flapping Wing Drive Mechanism for Miniature Air Vehicles - Bejgerowski,Wojciech; Gerdes,John W.; Gupta, Satyandra K.; Bruck,Hugh A.; Wilkerson,Stephen (ASME, 2010)
Successful realization of a flapping wing micro air vehicle (MAV) requires development of a light weight drive mechanism converting the rotary motion of the motor into flapping motion of the wings. Low weight of the drive mechanism is required to maximize the payload and battery capacity. In order to make flapping wing MAVs attractive in search, rescue, and recovery missions, they should be disposable from the cost point of view. Injection molded compliant drive mechanisms are an attractive design option to satisfy the weight, efficiency and cost requirements. In the past, we have successfully used multi-piece molding to create mechanisms utilizing distributed compliance for smaller MAVs. However, as the size of the MAV increases, mechanisms with distributed compliance exhibit excessive deformation. Therefore localizing rather than distributing the compliance in the mechanism becomes a more attractive option. Local compliance can be realized through multimaterial designs. A multi-material injection molded mechanism additionally offers reduction in the number of parts. This paper describes an approach for determining the drive mechanism shape and size that meets both the functional design and multi-material molding requirements. The design generated by the approach described in this paper was utilized to realize a flapping wing MAV with significant enhancements in the payload capabilities.

Design and implementation of embedded computer vision systems based on particle filters - Sankalita Saha; Bambha, Neal K.; Bhattacharyya, Shuvra S. (Computer Vision and Image Understanding, 2010)
Particle filtering methods are gradually attaining significant importance in a variety of embedded computer vision applications. For example, in smart camera systems, object tracking is a very important application and particle filter based tracking algorithms have shown promising results with robust tracking performance. However, most particle filters involve vast amount of computational complexity, thereby intensifying the challenges faced in their real-time, embedded implementation. Many of these applications share common characteristics, and the same system design can be reused by identifying and varying key system parameters and varying them appropriately. In this paper, we present a System-on-Chip (SoC) architecture involving both hardware and software components for a class of particle filters. The framework uses parameterization to enable fast and efficient reuse of the architecture with minimal re-design effort for a wide range of particle filtering applications as well as implementation platforms. Using this framework, we explore different design options for implementing three different particle filtering applications on field-programmable gate arrays (FPGAs). The first two applications involve particle filters with one-dimensional state transition models, and are used to demonstrate the key features of the framework. The main focus of this paper is on design methodology for hardware/software implementation of multi-dimensional particle filter application and we explore this in the third application which is a 3D facial pose tracking system for videos. In this multi-dimensional particle filtering application, we extend our proposed architecture with models for hardware/software co-design so that limited hardware resources can be utilized most effectively. Our experiments demonstrate that the framework is easy and intuitive to use, while providing for efficient design and implementation. We present different memory management schemes along with results on trade-offs between area (FPGA resource requirement) and execution speed.
Keywords: design space exploration; Particle filters; Reconfigurable platforms

Design and implementation of real-time signal processing applications on heterogeneous multiprocessor arrays - Wu, Hsiang-Huang; Chung-Ching Shen; Bhattacharyya, Shuvra S.; Compton, K.; Schulte, M.; Wolf, M.; Zhang, Tong (2010 Conference Record of the Forty Fourth Asilomar Conference on Signals, Systems and Computers (ASILOMAR), 2010)
Processing structures based on arrays of computational elements form an important class of architectures, which includes field programmable gate arrays (FPGAs), systolic arrays, and various forms of multicore processors. A wide variety of design methods and tools have been targeted to regular processing arrays involving homogeneous processing elements. In this paper, we introduce the concept of field programmable X arrays (FPXAs) as an abstract model for design and implementation of heterogeneous multiprocessor arrays for signal processing systems. FPXAs are abstract structures that can be targeted for implementation on application-specific integrated circuits, FPGAs, or other kinds of reconfigurable processors. FPXAs can also be mapped onto multicore processors for flexible emulation. We discuss the use of dataflow models as an integrated application representation and intermediate representation for efficient specification and mapping of signal processing systems on FPXAs. We demonstrate our proposed models and techniques with a case study involving the embedding of an application-specific FPXA system on an off-the-shelf FPGA device.
Keywords: application specific integrated circuits; application-specific integrated circuits; computational elements; Computer architecture; decoding; Field programmable gate arrays; field programmable X arrays; FPGA; FPXA; Integrated circuit modeling; Logic Design; microprocessor chips; multicore processors; multiprocessor arrays; real-time signal processing; reconfigurable architectures; reconfigurable processors; Routing; Signal processing; Signal processing systems; systolic arrays; Viterbi algorithm

Developing a Stochastic Dynamic Programming Framework for Optical Tweezer-Based Automated Particle Transport Operations - Banerjee,A. G.; Pomerance,A.; Losert,W.; Gupta,S.K. (Automation Science and Engineering, IEEE Transactions on, 2010)
Automated particle transport using optical tweezers requires the use of motion planning to move the particle while avoiding collisions with randomly moving obstacles. This paper describes a stochastic dynamic programming based motion planning framework developed by modifying the discrete version of an infinite-horizon partially observable Markov decision process algorithm. Sample trajectories generated by this algorithm are presented to highlight effectiveness in crowded scenes and flexibility. The algorithm is tested using silica beads in a holographic tweezer set-up and data obtained from the physical experiments are reported to validate various aspects of the planning simulation framework. This framework is then used to evaluate the performance of the algorithm under a variety of operating conditions.
Keywords: holographic tweezer set-up; holography; infinite-horizon partially observable Markov decision process algorithm; Markov processes; motion planning framework; optical tweezer-based automated particle transport operations; optical tweezers; radiation pressure; silica beads; stochastic dynamic programming framework; stochastic programming

Diversity and distribution of cholix toxin, a novel ADP‐ribosylating factor from Vibrio cholerae - Purdy,Alexandra E.; Balch,Deborah; Lizárraga‐Partida,Marcial Leonardo; Islam,Mohammad Sirajul; Martinez‐Urtaza,Jaime; Huq,Anwar; Rita R Colwell; Bartlett,Douglas H. (Environmental Microbiology Reports, 2010)
Non-toxigenic non-O1, non-O139 Vibrio cholerae strains isolated from both environmental and clinical settings carry a suite of virulence factors aside from cholera toxin. Among V. cholerae strains isolated from coastal waters of southern California, this includes cholix toxin, an ADP-ribosylating factor that is capable of halting protein synthesis in eukaryotic cells. The prevalence of the gene encoding cholix toxin, chxA, was assessed among a collection of 155 diverse V. cholerae strains originating from both clinical and environmental settings in Bangladesh and Mexico and other countries around the globe. The chxA gene was present in 47% of 83 non-O1, non-O139 strains and 16% of 72 O1/O139 strains screened as part of this study. A total of 86 chxA gene sequences were obtained, and phylogenetic analysis revealed that they fall into two distinct clades. These two clades were also observed in the phylogenies of several housekeeping genes, suggesting that the divergence observed in chxA extends to other regions of the V. cholerae genome, and most likely has arisen from vertical descent rather than horizontal transfer. Our results clearly indicate that ChxA is a major toxin of V. cholerae with a worldwide distribution that is preferentially associated with non-pandemic strains.

Don't Configure the Network, Program It! Domain-Specific Programming Languages for Network Systems - Feamster, Nick; Voellmy,A.; Agarwal,A.; Hudak,P.; Burnett,S.; Launchbury,J. (Yale University, 2010)
Network operators must configure networks to accomplish critical, complex, and often conflicting requirements: they must ensure good performance while maintaining security, and satisfy contractual obligations while ensuring profitable use of interdomain connections. Unfortunately, today they have no choice but to implement these high-level goals by configuring hundreds of individual network devices. These interact in complex and unexpected ways, often resulting in misconfigurations or downtime. We propose a new approach: rather than configure individual network devices, operators should program the network holistically, according to high-level policies. Towards this goal, we present Nettle, a system for clearly and concisely expressing network requirements together with mechanisms to control the network accordingly. At the lowest level, we rely on OpenFlow switches for programmable network hardware. On top of this layer, we build an extensible family of embedded domain-specific languages (EDSLs), each aimed at different operational concerns and provide convenient ways to sensibly combine expressions in these languages. We present a case study demonstrating a DSL for networks that provides fine-grained, dynamic access control policies.

Don't love thy nearest neighbor - Lumezanu,Cristian; Levin,Dave; Han,Bo; Spring, Neil; Bhattacharjee, Bobby (Proceedings of the 9th international conference on Peer-to-peer systems, 2010)

Dynamic and Multidimensional Dataflow Graphs - Bhattacharyya, Shuvra S.; Deprettere, Ed F.; Keinert, Joachim (Handbook of Signal Processing Systems, 2010)
Much of the work to date on dataflow models for signal processing system design has focused decidable dataflow models that are best suited for onedimensional signal processing. In this chapter, we review more general dataflow modeling techniques that are targeted to applications that include multidimensional signal processing and dynamic dataflow behavior. As dataflow techniques are applied to signal processing systems that are more complex, and demand increasing degrees of agility and flexibility, these classes of more general dataflow models are of correspondingly increasing interest. We begin with a discussion of two dataflow modeling techniques - multi-dimensional synchronous dataflow and windowed dataflow - that are targeted towards multidimensional signal processing applications. We then provide a motivation for dynamic dataflow models of computation, and review a number of specific methods that have emerged in this class of models. Our coverage of dynamic dataflowmodels in this chapter includes Boolean dataflow, the stream-based function model, CAL, parameterized dataflow, and enable-invoke dataflow.
Keywords: Communications Engineering, Networks; Computer Systems Organization and Communication Networks; Processor Architectures; Signal, Image and Speech Processing

The effect of packet loss on redundancy elimination in cellular wireless networks - Lumezanu,Cristian; Guo,Katherine; Spring, Neil; Bhattacharjee, Bobby (Proceedings of the 10th annual conference on Internet measurement, 2010)
Network-level redundancy elimination (RE) algorithms reduce traffic volume on bandwidth-constrained network paths by avoiding the transmission of repeated byte sequences. Previous work shows that RE can suppress the transmission of 20-50% bytes when deployed at ISP access links or between routers. In this paper, we focus on the challenges of deploying RE in cellular networks. The potential benefifit is substantial, since cellular networks have a growing subscriber base and network links, including wired backhaul, are often oversubscribed. Using three large traces captured at two North American and one European wireless network providers, we show that RE can reduce the bandwidth consumption of the majority of mobile users by at least 10%. However, cellular links have much higher packet loss rates than their wired counterparts, which makes applying RE much more difficult. Our experiments also show that the loss of only a few packets can disrupt RE and eliminate the bandwidth savings. We propose informed marking, a lightweight scheme that detects lost packets and prevents RE algorithms from using them for future encodings. We implement RE with informed marking and deploy it in a real-world cellular network. Our results show that with informed marking, more than 60% of the bandwidth savings of RE are preserved, even when packet loss rates are high.
Keywords: cellular networks; loss; redundancy elimination

An Efficient and Robust Algorithm for Shape Indexing and Retrieval - Biswas,S.; Aggarwal,G.; Chellapa, Rama (Multimedia, IEEE Transactions on, 2010)
Many shape matching methods are either fast but too simplistic to give the desired performance or promising as far as performance is concerned but computationally demanding. In this paper, we present a very simple and efficient approach that not only performs almost as good as many state-of-the-art techniques but also scales up to large databases. In the proposed approach, each shape is indexed based on a variety of simple and easily computable features which are invariant to articulations, rigid transformations, etc. The features characterize pairwise geometric relationships between interest points on the shape. The fact that each shape is represented using a number of distributed features instead of a single global feature that captures the shape in its entirety provides robustness to the approach. Shapes in the database are ordered according to their similarity with the query shape and similar shapes are retrieved using an efficient scheme which does not involve costly operations like shape-wise alignment or establishing correspondences. Depending on the application, the approach can be used directly for matching or as a first step for obtaining a short list of candidate shapes for more rigorous matching. We show that the features proposed to perform shape indexing can be used to perform the rigorous matching as well, to further improve the retrieval performance.
Keywords: activity; algorithm; shape; classification; human; databases; robust; estimation; large; indexing; shape; MATCHING; matching; image; methods; shape; pose; recognition; retrieval; image; retrieval; indexing; shape

Efficient static buffering to guarantee throughput-optimal FPGA implementation of synchronous dataflow graphs - Kee, Hojin; Bhattacharyya, Shuvra S.; Kornerup, J. (2010 International Conference on Embedded Computer Systems (SAMOS), 2010)
When designing DSP applications for implementation on field programmable gate arrays (FPGAs), it is often important to minimize consumption of limited FPGA resources while satisfying real-time performance constraints. In this paper, we develop efficient techniques to determine dataflow graph buffer sizes that guarantee throughput-optimal execution when mapping synchronous dataflow (SDF) representations of DSP applications onto FPGAs. Our techniques are based on a novel two-actor SDF graph Model (TASM), which efficiently captures the behavior and costs associated with SDF graph edges (flow-graph connections). With our proposed techniques, designers can automatically generate upper bounds on SDF graph buffer distributions that realize maximum achievable throughput performance for the corresponding applications. Furthermore, our proposed technique is characterized by low polynomial time complexity, which is useful for rapid prototyping in DSP system design.
Keywords: buffer memory; circuit complexity; Complexity theory; Computational modeling; data flow graphs; Digital signal processing; digital signal processing chips; DSP system design; efficient static buffering; Field programmable gate arrays; FPGA; graph buffer distributions; integrated circuit design; low polynomial time complexity; Random access memory; Schedules; SDF graph edges; Signal processing systems; Synchronous dataflow; synchronous dataflow graph mapping; Throughput; throughput-optimal execution; throughput-optimal FPGA implementation; two-actor SDF graph model; upper bounds

Electromagnetic Modeling of Ethernet Transformers - Bowen,D.; Mayergoyz, Issak D; Krafft,C. (Magnetics, IEEE Transactions on, 2010)
The unique features of Ethernet transformers are reviewed, and novel testing techniques for identification of lumped parameters of equivalent circuits are presented. To account for the distributed nature of the cross-winding and intrawinding capacitances, novel distributed models for electromagnetic analysis of Ethernet transformers are presented.
Keywords: analysis; electromagnetic; area; capacitances; lumped; circuits; ethernet; circuits; local; cross-winding; distributed; modeling; equivalent; models; electromagnetic; networks; lumped; networks; transformer; parameter; parameters; novel; techniques; capacitance; equivalent; Testing; transformers; intrawinding; windings; transformers

Energy-driven distribution of signal processing applications across wireless sensor networks - Chung-Ching Shen; Plishker, William L.; Ko,Dong-Ik; Bhattacharyya, Shuvra S.; Goldsman,Neil (ACM Trans. Sen. Netw., 2010)
Wireless sensor network (WSN) applications have been studied extensively in recent years. Such applications involve resource-limited embedded sensor nodes that have small size and low power requirements. Based on the need for extended network lifetimes in WSNs in terms of energy use, the energy efficiency of computation and communication operations in the sensor nodes becomes critical. Digital Signal Processing (DSP) applications typically require intensive data processing operations and as a result are difficult to implement directly in resource-limited WSNs. In this article, we present a novel design methodology for modeling and implementing computationally intensive DSP applications applied to wireless sensor networks. This methodology explores efficient modeling techniques for DSP applications, including data sensing and processing; derives formulations of Energy-Driven Partitioning (EDP) for distributing such applications across wireless sensor networks; and develops efficient heuristic algorithms for finding partitioning results that maximize the network lifetime. To address such an energy-driven partitioning problem, this article provides a new way of aggregating data and reducing communication traffic among nodes based on application analysis. By considering low data token delivery points and the distribution of computation in the application, our approach finds energy-efficient trade-offs between data communication and computation.
Keywords: DSP; Energy efficiency; network lifetime; Speech recognition; Wireless sensor networks

Error driven paraphrase annotation using Mechanical Turk - Buzek,O.; Resnik, Philip; Bederson, Benjamin B. (Proceedings of the NAACL HLT 2010 Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk, 2010)

Evaluation of information retrieval for E-discovery - Oard, Douglas; Baron,Jason R.; Hedin,Bruce; Lewis,David D.; Tomlinson,Stephen (Artificial Intelligence and Law, 2010)

Evolutionary framework for Lepidoptera model systems - Roe,A.; Weller,S.; Baixeras,J.; Brown,J. W; Cummings, Michael P.; Davis,DR; Horak,M; Kawahara,A. Y; Mitter,C; Parr,C.S.; Regier,J. C; Rubinoff,D; et al. (Genetics and Molecular Biology of LepidopteraGenetics and Molecular Biology of Lepidoptera, 2010)
“Model systems” are specific organisms upon which detailed studies have been conducted examining a fundamental biological question. If the studies are robust, their results can be extrapolated among an array of organisms that possess features in common with the subject organism. The true power of model systems lies in the ability to extrapolate these details across larger groups of organisms. In order to generalize these results, comparative studies are essential and require that model systems be placed into their evolutionary or phylogenetic context. This chapter examines model systems in the insect order Lepidoptera from the perspective of several different superfamilies. Historically, many species of Lepidoptera have been essential in the development of invaluable model systems in the fields of development biology, genetics, molecular biology, physiology, co-evolution, population dynamics, and ecology.

An Experimental Study of Color-Based Segmentation Algorithms Based on the Mean-Shift Concept - Bitsakos,K.; Fermüller, Cornelia; Aloimonos, J. (Computer Vision – ECCV 2010Computer Vision – ECCV 2010, 2010)
We point out a difference between the original mean-shift formulation of Fukunaga and Hostetler and the common variant in the computer vision community, namely whether the pairwise comparison is performed with the original or with the filtered image of the previous iteration. This leads to a new hybrid algorithm, called Color Mean Shift, that roughly speaking, treats color as Fukunaga’s algorithm and spatial coordinates as Comaniciu’s algorithm. We perform experiments to evaluate how different kernel functions and color spaces affect the final filtering and segmentation results, and the computational speed, using the Berkeley and Weizmann segmentation databases. We conclude that the new method gives better results than existing mean shift ones on four standard comparison measures ( improvement on RAND and BDE measures respectively for color images), with slightly higher running times ( ). Overall, the new method produces segmentations comparable in quality to the ones obtained with current state of the art segmentation algorithms.

Fault-Tolerant Facility Location: A Randomized Dependent LP-Rounding Algorithm - Byrka,Jaroslaw; Srinivasan, Aravind; Swamy,Chaitanya (Integer Programming and Combinatorial OptimizationInteger Programming and Combinatorial Optimization, 2010)

Finishing genomes with limited resources: lessons from an ensemble of microbial genomes - Nagarajan,Niranjan; Cook,Christopher; Di Bonaventura,Maria Pia; Ge,Hong; Richards,Allen; Bishop-Lilly,Kimberly A; DeSalle,Robert; Read,Timothy D.; Pop, Mihai (BMC Genomics, 2010)
While new sequencing technologies have ushered in an era where microbial genomes can be easily sequenced, the goal of routinely producing high-quality draft and finished genomes in a cost-effective fashion has still remained elusive. Due to shorter read lengths and limitations in library construction protocols, shotgun sequencing and assembly based on these technologies often results in fragmented assemblies. Correspondingly, while draft assemblies can be obtained in days, finishing can take many months and hence the time and effort can only be justified for high-priority genomes and in large sequencing centers. In this work, we revisit this issue in light of our own experience in producing finished and nearly-finished genomes for a range of microbial species in a small-lab setting. These genomes were finished with surprisingly little investments in terms of time, computational effort and lab work, suggesting that the increased access to sequencing might also eventually lead to a greater proportion of finished genomes from small labs and genomics cores.

FPGA-based design and implementation of the 3GPP-LTE physical layer using parameterized synchronous dataflow techniques - Kee, Hojin; Bhattacharyya, Shuvra S.; Wong, I.; Yong Rao (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
Synchronous dataflow (SDF) is an ubiquitous dataflow model of computation that has been studied extensively for efficient simulation and software synthesis of DSP applications. In recent years, parameterized SDF (PSDF) has evolved as a useful framework for modeling SDF graphs in which arbitrary parameters can be changed dynamically. However, the potential to enable efficient hardware synthesis has been treated relatively sparsely in the literature for SDF and even more so for the newer, more general PSDF model. This paper investigates efficient FPGA-based design and implementation of the physical layer for 3GPP-Long Term Evolution (LTE), a next generation cellular standard. To capture the SDF behavior of the functional core of LTE along with higher level dynamics in the standard, we use a novel PSDF-based FPGA architecture framework. We implement our PSDF-based, LTE design framework using National Instrument's LabVIEW FPGA, a recently-introduced commercial platform for reconfigurable hardware implementation. We show that our framework can effectively model the dynamics of the LTE protocol, while also providing a synthesis framework for efficient FPGA implementation.
Keywords: 3G mobile communication; 3GPP-long term evolution; 3GPP-LTE physical layer; 4G communication systems; Computational modeling; data flow analysis; data flow graphs; Dataflow modeling; Digital signal processing; DSP applications; Field programmable gate arrays; FPGA architecture framework; FPGA implementation; FPGA-based design; Hardware; hardware synthesis; Instruments; LabVIEW FPGA; Logic Design; LTE; next generation cellular standard; parameterized synchronous data flow technique; Pervasive computing; Physical layer; Physics computing; Production; PSDF graph; reconfigurable hardware implementation; Runtime; software synthesis; Ubiquitous Computing; ubiquitous data flow model

A general framework for efficient geographic routing in wireless networks - Lee,Seungjoon; Bhattacharjee, Bobby; Banerjee,Suman; Han,Bo (Computer Networks, 2010)
We propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic routing, NADV enables an adaptive and efficient cost-aware routing strategy. Depending on the objective or message priority, applications can use the NADV framework to minimize various types of link cost.We present efficient methods for link cost estimation and perform detailed experiments in simulated environments. Our results show that NADV outperforms current schemes in many aspects: for example, in high noise environments with frequent packet losses, the use of NADV leads to 81% higher delivery ratio. When compared to centralized routing under certain settings, geographic routing using NADV finds paths whose cost is close to the optimum. We also conducted experiments in Emulab testbed and the results demonstrate that our proposed approach performs well in practice.
Keywords: Geographic routing; Link cost estimation; Routing metric; Wireless multihop networks

Genome Sequence of Hybrid Vibrio Cholerae O1 MJ-1236, B-33, and CIRS101 and Comparative Genomics with V. Cholerae - Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Haley,Bradd; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Detter,J. Chris; Han,Cliff S.; Chertkov,Olga; Challacombe,Jean; Huq,Anwar; et al. (Journal of BacteriologyJ. Bacteriol., 2010)
The genomes of Vibrio cholerae O1 Matlab variant MJ-1236, Mozambique O1 El Tor variant B33, and altered O1 El Tor CIRS101 were sequenced. All three strains were found to belong to the phylocore group 1 clade of V. cholerae, which includes the 7th-pandemic O1 El Tor and serogroup O139 isolates, despite displaying certain characteristics of the classical biotype. All three strains were found to harbor a hybrid variant of CTXΦ and an integrative conjugative element (ICE), leading to their establishment as successful clinical clones and the displacement of prototypical O1 El Tor. The absence of strain- and group-specific genomic islands, some of which appear to be prophages and phage-like elements, seems to be the most likely factor in the recent establishment of dominance of V. cholerae CIRS101 over the other two hybrid strains.

Global Contours - Bista, Sujal; Varshney, Amitabh (Department of Computer Science, University of Maryland, College Park, 2010)
We present a multi-scale approach that uses Laplacian eigenvectorsto extract globally significant contours from an image. The input images are mapped into the Laplacian space by using Laplacian eigenvectors. This mapping causes globally significant pixels along the contours to expand in the Laplacian space. The measure of the expansion is used to compute the Global Contours. We apply our scheme to real color images and compare it with several other methods that compute image and color saliency. The contours calculated by our method reflect global properties of the image and are complementary to classic center-surround image saliency methods. We believe that hybrid image saliency algorithms that combine our method of Global Contours with center-surround image saliency algorithms will be able to better characterize the most important regions of images than those from just using contours calculated using bottom-up approaches.
Keywords: Technical Report

Handbook of Signal Processing Systems - Bhattacharyya, Shuvra S.; Deprettere, Ed F. (Springer, 2010)
The Handbook is organized in four parts. The first part motivates representative applications that drive and apply state-of-the art methods for design and implementation of signal processing systems; the second part discusses architectures for implementing these applications; the third part focuses on compilers and simulation tools; and the fourth part describes models of computation and their associated design tools and methodologies.
Keywords: Computers / Information Theory; Technology & Engineering / Electrical; Technology & Engineering / Signals & Signal Processing

Holistic sentiment analysis across languages: multilingual supervised latent Dirichlet allocation - Jordan Boyd-Graber; Resnik, Philip (Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010)
In this paper, we develop multilingual supervised latent Dirichlet allocation (MlSLDA), a probabilistic generative model that allows insights gleaned from one language's data to inform how the model captures properties of other languages. MlSLDA accomplishes this by jointly modeling two aspects of text: how multilingual concepts are clustered into thematically coherent topics and how topics associated with text connect to an observed regression variable (such as ratings on a sentiment scale). Concepts are represented in a general hierarchical framework that is flexible enough to express semantic ontologies, dictionaries, clustering constraints, and, as a special, degenerate case, conventional topic models. Both the topics and the regression are discovered via posterior inference from corpora. We show MlSLDA can build topics that are consistent across languages, discover sensible bilingual lexical correspondences, and leverage multilingual corpora to better predict sentiment.

Identification of Pathogenic Vibrio Species by Multilocus PCR-Electrospray Ionization Mass Spectrometry and Its Application to Aquatic Environments of the Former Soviet Republic of Georgia - Whitehouse,Chris A.; Baldwin,Carson; Sampath,Rangarajan; Blyn,Lawrence B.; Melton,Rachael; Li,Feng; Hall,Thomas A.; Harpin,Vanessa; Matthews,Heather; Tediashvili,Marina; Jaiani,Ekaterina; Kokashvili,Tamar; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2010)
The Ibis T5000 is a novel diagnostic platform that couples PCR and mass spectrometry. In this study, we developed an assay that can identify all known pathogenic Vibrio species and field-tested it using natural water samples from both freshwater lakes and the Georgian coastal zone of the Black Sea. Of the 278 total water samples screened, 9 different Vibrio species were detected, 114 (41%) samples were positive for V. cholerae, and 5 (0.8%) samples were positive for the cholera toxin A gene (ctxA). All ctxA-positive samples were from two freshwater lakes, and no ctxA-positive samples from any of the Black Sea sites were detected.

Identifying Differentially Abundant Metabolic Pathways in Metagenomic Datasets - Liu,Bo; Pop, Mihai (Bioinformatics Research and Applications, 2010)
Enabled by rapid advances in sequencing technology, metagenomic studies aim to characterize entire communities of microbes bypassing the need for culturing individual bacterial members. One major goal of such studies is to identify specific functional adaptations of microbial communities to their habitats. Here we describe a powerful analytical method (MetaPath) that can identify differentially abundant pathways in metagenomic data-sets, relying on a combination of metagenomic sequence data and prior metabolic pathway knowledge. We show that MetaPath outperforms other common approaches when evaluated on simulated datasets. We also demonstrate the power of our methods in analyzing two, publicly available, metagenomic datasets: a comparison of the gut microbiome of obese and lean twins; and a comparison of the gut microbiome of infant and adult subjects. We demonstrate that the subpathways identified by our method provide valuable insights into the biological activities of the microbiome.

Image classification of vascular smooth muscle cells - Grasso,Michael A.; Mokashi,Ronil; Dalvi,Darshana; Cardone, Antonio; Dima,Alden A.; Bhadriraju,Kiran; Plant,Anne L.; Brady,Mary; Yesha,Yaacov; Yesha,Yelena (Proceedings of the 1st ACM International Health Informatics Symposium, 2010)
Keywords: cell biology; digital image processing; machine learning

Improving translation via targeted paraphrasing - Resnik, Philip; Buzek,O.; Hu,C.; Kronrod,Y.; Quinn,A.; Bederson, Benjamin B. (Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010)

On k-Column Sparse Packing Programs - Bansal,Nikhil; Korula,Nitish; Nagarajan,Viswanath; Srinivasan, Aravind (Integer Programming and Combinatorial OptimizationInteger Programming and Combinatorial Optimization, 2010)
We consider the class of packing integer programs (PIPs) that are column sparse, where there is a specified upper bound k on the number of constraints that each variable appears in. We give an improved (ek + o(k))-approximation algorithm for k-column sparse PIPs. Our algorithm is based on a linear programming relaxation, and involves randomized rounding combined with alteration. We also show that the integrality gap of our LP relaxation is at least 2k − 1; it is known that even special cases of k-column sparse PIPs are (klogk)-hard to approximate.We generalize our result to the case of maximizing monotone submodular functions over k-column sparse packing constraints, and obtain an e2ke−1+o(k) -approximation algorithm. In obtaining this result, we prove a new property of submodular functions that generalizes the fractionally subadditive property, which might be of independent interest.

Lazy binary-splitting: a run-time adaptive work-stealing scheduler - Tzannes,Alexandros; Caragea,George C.; Barua,Rajeev; Vishkin, Uzi (Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2010)
We present Lazy Binary Splitting (LBS), a user-level scheduler of nested parallelism for shared-memory multiprocessors that builds on existing Eager Binary Splitting work-stealing (EBS) implemented in Intel's Threading Building Blocks (TBB), but improves performance and ease-of-programming. In its simplest form (SP), EBS requires manual tuning by repeatedly running the application under carefully controlled conditions to determine a stop-splitting-threshold (sst)for every do-all loop in the code. This threshold limits the parallelism and prevents excessive overheads for fine-grain parallelism. Besides being tedious, this tuning also over-fits the code to some particular dataset, platform and calling context of the do-all loop, resulting in poor performance portability for the code. LBS overcomes both the performance portability and ease-of-programming pitfalls of a manually fixed threshold by adapting dynamically to run-time conditions without requiring tuning. We compare LBS to Auto-Partitioner (AP), the latest default scheduler of TBB, which does not require manual tuning either but lacks context portability, and outperform it by 38.9% using TBB's default AP configuration, and by 16.2% after we tuned AP to our experimental platform. We also compare LBS to SP by manually finding SP's sst using a training dataset and then running both on a different execution dataset. LBS outperforms SP by 19.5% on average. while allowing for improved performance portability without requiring tedious manual tuning. LBS also outperforms SP with sst=1, its default value when undefined, by 56.7%, and serializing work-stealing (SWS), another work-stealer by 54.7%. Finally, compared to serializing inner parallelism (SI) which has been used by OpenMP, LBS is 54.2% faster.
Keywords: Dynamic scheduling; load balancing; nested parallelism; thread scheduling; work stealing

Learning Through Application: The Maturing ofthe QIP in the SEL - Basili, Victor R. (Making Software: What Really Works, and Why We Believe ItMaking Software: What Really Works, and Why We Believe It, 2010)

A Lightweight Dataflow Approach for Design and Implementation of SDR Systems - Chung-Ching Shen; Plishker,William; Wu, Hsiang-Huang; Bhattacharyya, Shuvra S. (Wireless Innovation Conference and Product Exposition, Washington DC, USA, 2010)
Model-based design methods based on dataflow modelsof computation are attractive for design and implementation of wireless communication systems because of their intuitive correspondence to communication system block diagrams, and the formal structure that is exposed through formal dataflow representations (e.g., see [2]). In this paper, we introduce a novel lightweight dataflow (LWDF) programming model for model-based design and implementation of wireless communication and software-defined radio systems. The approach is suitable for improving the productivity of the design process; the agility with which designs can be retargeted across different platforms; and the quality of derived implementations. By “lightweight”, we meant that the programming model is designed to be minimally intrusive on existing design processes, and require minimal dependence on specialized tools or libraries. This allows designers to integrate and experiment with dataflow modeling approaches relatively quickly and flexibly into existing design methodologies and processes.

Linguistic Extensions of Topic Models - Jordan Boyd-Graber (Princeton University, 2010)
Topic models like latent Dirichlet allocation (LDA) provide a framework for analyzinglarge datasets where observations are collected into groups. Although topic modeling has been fruitfully applied to problems social science, biology, and computer vision, it has been most widely used to model datasets where documents are modeled as exchangeable groups of words. In this context, topic models discover topics, distribu- tions over words that express a coherent theme like “business” or “politics.” While one of the strengths of topic models is that they make few assumptions about the underlying data, such a general approach sometimes limits the type of problems topic models can solve. When we restrict our focus to natural language datasets, we can use insights from linguistics to create models that understand and discover richer language patterns. In this thesis, we extend LDA in three different ways: adding knowledge of word mean- ing, modeling multiple languages, and incorporating local syntactic context. These extensions apply topic models to new problems, such as discovering the meaning of ambiguous words, extend topic models for new datasets, such as unaligned multi- lingual corpora, and combine topic models with other sources of information about documents’ context.

Linking Software Development and Business Strategy Through Measurement - Basili, Victor R.; Lindvall,M.; Regardie,M.; Seaman,C.; Heidrich,J.; Munch,J.; Rombach,D.; Trendowicz,A. (Computer, 2010)
The GQM+Strategies approach extends the goal/question/metric paradigm for measuring the success or failure of goals and strategies, adding enterprise-wide support for determining action on the basis of measurement results. An organization can thus integrate its measurement program across all levels.
Keywords: approach; business; aspects; software; development; organisational; engineering; GQM+Strategies; program; software; strategy; enterprise; support; measurement; wide

Loop transformations for interface-based hierarchies IN SDF graphs - Piat, J.; Bhattacharyya, Shuvra S.; Raulet, M. (2010 21st IEEE International Conference on Application-specific Systems Architectures and Processors (ASAP), 2010)
Data-flow has proven to be an attractive computation model for programming digital signal processing (DSP) applications. A restricted version of data-flow, termed synchronous data-flow (SDF), offers strong compile-time predictability properties, but has limited expressive power. A new type of hierarchy (Interface-based SDF) has been proposed allowing more expressivity while maintaining its predictability. One of the main problems with this hierarchical SDF model is the lack of trade-off between parallelism and network clustering. This paper presents a systematic method for applying an important class of loop transformation techniques in the context of interface-based SDF semantics. The resulting approach provides novel capabilities for integrating parallelism extraction properties of the targeted loop transformations with the useful modeling, analysis, and code reuse properties provided by SDF.
Keywords: Application software; code generation; Computer architecture; Computer interfaces; Data-Flow programming; Digital signal processing; Loop parallelization; PARALLEL PROCESSING; Power engineering computing; Power system modeling; Processor scheduling; Programming profession; scheduling; SDF graph; system recovery

A Low-overhead Scheduling Methodology for Fine-grained Acceleration of Signal Processing Systems - Boutellier, Jani; Bhattacharyya, Shuvra S.; Silvén, Olli (Journal of Signal Processing Systems, 2010)
Fine-grained accelerators have the potential to deliver significant benefits in various platforms for embedded signal processing. Due to the moderate complexity of their targeted operations, these accelerators must be managed with minimal run-time overhead. In this paper, we present a methodology for applying flow-shop scheduling techniques to make effective, low-overhead use of fine-grained DSP accelerators. We formulate the underlying scheduling approach in terms of general flow-shop scheduling concepts, and demonstrate our methodology concretely by applying it to MPEG-4 video decoding. We present quantitative experiments on a soft processor that runs on a field-programmable gate array, and provide insight on trends and trade-offs among different flow-shop scheduling approaches when applied to run-time management of fine-grained acceleration.

LP-rounding algorithms for facility-location problems - Byrka,Jaroslaw; Ghodsi,Mohammadreza; Srinivasan, Aravind (arXiv:1007.3611, 2010)
We study LP-rounding approximation algorithms for metric uncapacitated facility-location problems. We first give a new analysis for the algorithm of Chudak and Shmoys, which differs from the analysis of Byrka and Aardal in that now we do not need any bound based on the solution to the dual LP program. Besides obtaining the optimal bifactor approximation as do Byrka and Aardal, we can now also show that the algorithm with scaling parameter equaling 1.58 is, in fact, an 1.58-approximation algorithm. More importantly, we suggest an approach based on additional randomization and analyses such as ours, which could achieve or approach the conjectured optimal 1.46...--approximation for this basic problem. Next, using essentially the same techniques, we obtain improved approximation algorithms in the 2-stage stochastic variant of the problem, where we must open a subset of facilities having only stochastic information about the future demand from the clients. For this problem we obtain a 2.2975-approximation algorithm in the standard setting, and a 2.4957-approximation in the more restricted, per-scenario setting. We then study robust fault-tolerant facility location, introduced by Chechik and Peleg: solutions here are designed to provide low connection cost in case of failure of up to $k$ facilities. Chechik and Peleg gave a 6.5-approximation algorithm for $k=1$ and a ($7.5k + 1.5$)-approximation algorithm for general $k$. We improve this to an LP-rounding $(k+5+4/k)$-approximation algorithm. We also observe that in case of oblivious failures the expected approximation ratio can be reduced to $k + 1.5$, and that the integrality gap of the natural LP-relaxation of the problem is at least $k + 1$.
Keywords: Computer Science - Data Structures and Algorithms

Maranello: practical partial packet recovery for 802.11 - Han,Bo; Schulman,Aaron; Gringoli,Francesco; Spring, Neil; Bhattacharjee, Bobby; Nava,Lorenzo; Ji,Lusheng; Lee,Seungjoon; Miller,Robert (Proceedings of the 7th USENIX conference on Networked systems design and implementation, 2010)
Partial packet recovery protocols attempt to repair corrupted packets instead of retransmitting them in their entirety. Recent approaches have used physical layer confidence estimates or additional error detection codes embedded in each transmission to identify corrupt bits, or have applied forward error correction to repair without such explicit knowledge. In contrast to these approaches, our goal is a practical design that simultaneously: (a) requires no extra bits in correct packets, (b) reduces recovery latency, except in rare instances, (c) remains compatible with existing 802.11 devices by obeying timing and backoff standards, and (d) can be incrementally deployed on widely available access points and wireless cards. In this paper, we design, implement, and evaluate Maranello, a novel partial packet recovery mechanism for 802.11. In Maranello, the receiver computes checksums over blocks in corrupt packets and bundles these checksums into a negative acknowledgment sent when the sender expects to receive an acknowledgment. The sender then retransmits only those blocks for which the checksum is incorrect, and repeats this partial retransmission until it receives an acknowledgment. Successful transmissions are not burdened by additional bits and the receiver needs not infer which bits were corrupted. We implemented Maranello using OpenFWWF (open source firmware for Broadcom wireless cards) and deployed it in a small testbed. We compare Maranello to alternative recovery protocols using a trace-driven simulation and to 802.11 using a live implementation under various channel conditions. To our knowledge, Maranello is the first partial packet recovery design to be implemented in commonly available firmware.

Measuring transitivity using untrained annotators - Madnani,Nitin; Jordan Boyd-Graber; Resnik, Philip (Proceedings of the NAACL HLT 2010 Workshop on Creating Speech and Language Data with Amazon's Mechanical Turk, 2010)
Hopper and Thompson (1980) defined a multi-axis theory of transitivity that goes beyond simple syntactic transitivity and captures how much "action" takes place in a sentence. Detecting these features requires a deep understanding of lexical semantics and real-world pragmatics. We propose two general approaches for creating a corpus of sentences labeled with respect to the Hopper-Thompson transitivity schema using Amazon Mechanical Turk. Both approaches assume no existing resources and incorporate all necessary annotation into a single system; this is done to allow for future generalization to other languages. The first task attempts to use language-neutral videos to elicit human-composed sentences with specified transitivity attributes. The second task uses an iterative process to first label the actors and objects in sentences and then annotate the sentences' transitivity. We examine the success of these techniques and perform a preliminary classification of the transitivity of held-out data.

Methods for efficient implementation of Model Predictive Control on multiprocessor systems - Gu, Ruirui; Bhattacharyya, Shuvra S.; Levine,W. S (2010 IEEE International Conference on Control Applications (CCA), 2010)
Model Predictive Control (MPC) has been used in a wide range of application areas including chemical engineering, food processing, automotive engineering, aerospace, and metallurgy. An important limitation on the application of MPC is the difficulty in completing the necessary computations within the sampling interval. Recent trends in computing hardware towards greatly increased parallelism offer a solution to this problem. This paper describes modeling and analysis tools to facilitate implementing the MPC algorithms on parallel computers, thereby greatly reducing the time needed to complete the calculations. The use of these tools is illustrated by an application to a class of MPC problems.
Keywords: Computational modeling; COMPUTERS; Equations; Hardware; Linear systems; Mathematical model; model predictive control; MPC algorithms; Multiprocessing systems; Multiprocessor systems; parallel computers; predictive control; Program processors

A modality lexicon and its use in automatic tagging - Baker,K.; Bloodgood,M.; Dorr, Bonnie J; Filardo,N.W.; Levin,L.; Piatko,C. (Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10), 2010)
This paper describes our resource-building results for an eight-week JHU Human Language Technology Center of Excellence SummerCamp for Applied Language Exploration (SCALE-2009) on Semantically-Informed Machine Translation. Specifically, we describe the construction of a modality annotation scheme, a modality lexicon, and two automated modality taggers that were built using the lexicon and annotation scheme. Our annotation scheme is based on identifying three components of modality: a trigger, a target and a holder. We describe how our modality lexicon was produced semi-automatically, expanding from an initial hand-selected list of modality trigger words and phrases. The resulting expanded modality lexicon is being made publicly available. We demonstrate that one tagger—a structure-based tagger—results in precision around 86% (depending on genre) for tagging of a standard LDC data set. In a machine translation application, using the structure-based tagger to annotate English modalities on an English-Urdu training corpus improved the translation quality score for Urdu by 0.3 Bleu points in the face of sparse training data.

Modeling perspective using adaptor grammars - Hardisty,Eric A.; Jordan Boyd-Graber; Resnik, Philip (Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, 2010)
Strong indications of perspective can often come from collocations of arbitrary length; for example, someone writing get the government out of my X is typically expressing a conservative rather than progressive viewpoint. However, going beyond unigram or bigram features in perspective classification gives rise to problems of data sparsity. We address this problem using nonparametric Bayesian modeling, specifically adaptor grammars (Johnson et al., 2006). We demonstrate that an adaptive naïve Bayes model captures multiword lexical usages associated with perspective, and establishes a new state-of-the-art for perspective classification results using the Bitter Lemons corpus, a collection of essays about mid-east issues from Israeli and Palestinian points of view.

Multidimensional data structures for spatial applications - Samet, Hanan (Algorithms and theory of computation handbookAlgorithms and theory of computation handbook, 2010)
An overview is presented of a number of representations of multidimensional data that arise in spatial applications. Multidimensional spatial data consists of points as well as objects that have extent such as line segments, rectangles, regions, and volumes. The points may have locational as well as nonlocational attributes. The focus is on spatial data which is a subset of multidimensional data consisting of points with locational attributes and objects with extent. The emphasis is on hierarchical representations based on the "divide-and-conquer" problem-solving paradigm. They are of interest because they enable focusing computational resources on the interesting subsets of data. Thus, there is no need to expend work where the payoff is small. These representations are of use in operations such as range searching and finding nearest neighbors.

Nfsight: netflow-based network awareness tool - Berthier,R.; Michel Cukier; Hiltunen,M.; Kormann,D.; Vesonder,G.; Sheleheda,D. (2010)
Network awareness is highly critical for network and se-curity administrators. It enables informed planning and management of network resources, as well as detection and a comprehensive understanding of malicious activ- ity. It requires a set of tools to efficiently collect, process, and represent network data. While many such tools al- ready exist, there is no flexible and practical solution for visualizing network activity at various granularities, and quickly gaining insights about the status of network as- sets. To address this issue, we developed Nfsight, a Net- Flow processing and visualization application designed to offer a comprehensive network awareness solution. Nfsight constructs bidirectional flows out of the unidi- rectional NetFlow flows and leverages these bidirectional flows to provide client/server identification and intrusion detection capabilities. We present in this paper the in- ternal architecture of Nfsight, the evaluation of the ser- vice, and intrusion detection algorithms. We illustrate the contributions of Nfsight through several case studies conducted by security administrators on a large univer- sity network.

Non-visual exploration of geographic maps: Does sonification help? - Delogu,Franco; Palmiero,Massimiliano; Federici,Stefano; Plaisant, Catherine; Zhao,Haixia; Belardinelli,Olivetti (Disability & Rehabilitation: Assistive Technology, 2010)
Purpose. This study aims at evaluating the effectiveness of sonification as a mean to provide access to geo-referenced information to users with visual impairments.Method. Thiry-five participants (10 congenitally blind, 10 with acquired blindness and 15 blindfolded sighted) completed four tasks of progressive difficulty. During each task, participants first explored a sonified map by using either a tablet or a keyboard to move across regions and listened to sounds giving information about the current location. Then the participants were asked to identify, among four tactile maps, the one that crossmodally corresponds to the sonifed map they just explored. Finally, participants answered a self-report questionnaire of understanding and satisfaction. Results. Participants achieved high accuracy in all of the four tactile map discrimination tasks. No significant performance difference was found neither between subjects that used keyboard or tablet, nor between the three groups of blind and sighted participants. Differences between groups and interfaces were found in the usage strategies. High levels of satisfaction and understanding of the tools and tasks emerged from users' reports.

Obtaining valid safety data for software safety measurement and process improvement - Basili, Victor R.; Zelkowitz, Marvin V; Layman,Lucas; Dangle,Kathleen; Diep,Madeline (Proceedings of the 2010 ACM-IEEE International Symposium on Empirical Software Engineering and Measurement, 2010)
We report on a preliminary case study to examine software safety risk in the early design phase of the NASA Constellation spaceflight program. Our goal is to provide NASA quality assurance managers with information regarding the ongoing state of software safety across the program. We examined 154 hazard reports created during the preliminary design phase of three major flight hardware systems within the Constellation program. Our purpose was two-fold: 1) to quantify the relative importance of software with respect to system safety; and 2) to identify potential risks due to incorrect application of the safety process, deficiencies in the safety process, or the lack of a defined process. One early outcome of this work was to show that there are structural deficiencies in collecting valid safety data that make software safety different from hardware safety. In our conclusions we present some of these deficiencies.
Keywords: case study; NASA; risk analysis; safety metrics

Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage - Brakerski,Z.; Kalai,Y.T.; Katz, Jonathan; Vaikuntanathan,V. (Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, 2010)
In recent years, there has been a major effort to design cryptographic schemes that remain secure even when arbitrary information about the secret key is leaked (e.g., via side-channel attacks). We explore the possibility of achieving security under emphcontinual leakage from the emphentire secret key by designing schemes in which the secret key is updated over time. In this model, we construct public-key encryption schemes, digital signatures, and identity-based encryption schemes that remain secure even if an attacker can leak a constant fraction of the secret memory (including the secret key) in each time period between key updates. We also consider attackers who may probe the secret memory during the updates themselves. We stress that we allow unrestricted leakage, without the assumption that “only computation leaks information”. Prior to this work, constructions of public-key encryption schemes secure under continual leakage were not known even under this assumption.
Keywords: continual; cryptography; cryptography; public-key; encryption; key; key; digital; leakage; cryptographic; memory; schemes; digital; schemes; public-key; schemes; secret; signatures; identity-based; signatures; public

Overlay Networking and Resiliency - Bhattacharjee, Bobby; Rabinovich,M. (Guide to Reliable Internet Services and Applications, 2010)

Pose-robust albedo estimation from a single image - Biswas,S.; Chellapa, Rama (Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, 2010)
We present a stochastic filtering approach to perform albedo estimation from a single non-frontal face image. Albedo estimation has far reaching applications in various computer vision tasks like illumination-insensitive matching, shape recovery, etc. We extend the formulation proposed in that assumes face in known pose and present an algorithm that can perform albedo estimation from a single image even when pose information is inaccurate. 3D pose of the input face image is obtained as a byproduct of the algorithm. The proposed approach utilizes class-specific statistics of faces to iteratively improve albedo and pose estimates. Illustrations and experimental results are provided to show the effectiveness of the approach. We highlight the usefulness of the method for the task of matching faces across variations in pose and illumination. The facial pose estimates obtained are also compared against ground truth.
Keywords: 3D; albedo; estimation; estimation; shape; Face; filtering; face; image; single; image; stochastic; information; pose-robust; matching; pose; nonfrontal; pose; class-specific; recognition; filtering; recovery; single; statistics; computer; theory; pose; vision; illumination-insensitive

The pre‐seventh pandemic Vibrio cholerae BX 330286 El Tor genome: evidence for the environment as a genome reservoir - Haley,Bradd J.; Grim,Christopher J.; Hasan,Nur A.; Taviani,Elisa; Jongsik Chun; Brettin,Thomas S.; Bruce,David C.; Challacombe,Jean F.; Detter,J. Chris; Han,Cliff S.; Huq,Anwar; Nair,G. Balakrish; et al. (Environmental Microbiology Reports, 2010)
Vibrio cholerae O1 El Tor BX 330286 was isolated from a water sample in Australia in 1986, 9 years after an indigenous outbreak of cholera occurred in that region. This environmental strain encodes virulence factors highly similar to those of clinical strains, suggesting an ability to cause disease in humans. We demonstrate its high similarity in gene content and genome-wide nucleotide sequence to clinical V. cholerae strains, notably to pre-seventh pandemic O1 El Tor strains isolated in 1910 (V. cholerae NCTC 8457) and 1937 (V. cholerae MAK 757), as well as seventh pandemic strains isolated after 1960 globally. Here we demonstrate that this strain represents a transitory clone with shared characteristics between pre-seventh and seventh pandemic strains of V. cholerae. Interestingly, this strain was isolated 25 years after the beginning of the seventh pandemic, suggesting the environment as a genome reservoir in areas where cholera does not occur in sporadic, endemic or epidemic form.

Probabilistic similarity logic - Bröcheler,M.; Mihalkova,L.; Getoor, Lise (Proceedings of the Conference on Uncertainty in Artificial Intelligence, 2010)
Many machine learning applications require theability to learn from and reason about noisy multi-relational data. To address this, several ef- fective representations have been developed that provide both a language for expressing the struc- tural regularities of a domain, and principled sup- port for probabilistic inference. In addition to these two aspects, however, many applications also involve a third aspect–the need to reason about similarities–which has not been directly supported in existing frameworks. This paper introduces probabilistic similarity logic (PSL), a general-purpose framework for joint reason- ing about similarity in relational domains that incorporates probabilistic reasoning about sim- ilarities and relational structure in a principled way. PSL can integrate any existing domain- specific similarity measures and also supports reasoning about similarities between sets of en- tities. We provide efficient inference and learn- ing techniques for PSL and demonstrate its ef- fectiveness both in common relational tasks and in settings that require reasoning about similarity.

The problem with zoning: nonlinear effects of interactions between location preferences and externalities on land use and utility - Zellner,M.L.; Riolo,R.L.; Rand, William; Brown,D.G.; Page,S.E.; Fernandez,L.E. (Environment and Planning B: Planning and Design, 2010)

Rapid prototyping for digital signal processing systems using Parameterized Synchronous Dataflow graphs - Wu, Hsiang-Huang; Kee, Hojin; Sane, N.; Plishker,W.; Bhattacharyya, Shuvra S. (2010 21st IEEE International Symposium on Rapid System Prototyping (RSP), 2010)
Parameterized Synchronous Dataflow (PSDF) has been used previously for abstract scheduling and as a model for architecting embedded software and FPGA implementations. PSDF has been shown to be attractive for these purposes due to its support for flexible dynamic reconfiguration, and efficient quasi-static scheduling. To apply PSDF techniques more deeply into the design flow, support for comprehensive functional simulation and efficient hardware mapping is important. By building on the DIF (Dataflow Interchange Format), which is a design language and associated software package for developing and experimenting with dataflow-based design techniques for signal processing systems, we have developed a tool for functional simulation of PSDF specifications. This simulation tool allows designers to model applications in PSDF and simulate their functionality, including use of the dynamic parameter reconfiguration capabilities offered by PSDF. Based on this simulation tool, we also present a systematic design methodology for applying PSDF to the design and implementation of digital signal processing systems, with emphasis on FPGA-based systems for signal processing. We demonstrate capabilities for rapid and accurate prototyping offered by our proposed design methodology, along with its novel support for PSDF-based FPGA system implementation.
Keywords: abstract scheduling; Computational modeling; Computer architecture; data flow graphs; dataflow based design; dataflow interchange format; design flow; design language; Digital signal processing; digital signal processing systems; dynamic parameter reconfiguration; Dynamic scheduling; efficient hardware mapping; efficient quasistatic scheduling; Embedded software; embedded systems; Field programmable gate arrays; flexible dynamic reconfiguration; FPGA based systems; FPGA implementations; functional simulation; Hardware; parameterized synchronous dataflow graphs; rapid prototyping; Schedules; scheduling; semantics; simulation tool; software package; systematic design methodology

Resource-Aware Compiler Prefetching for Many-Cores - Caragea,G.C.; Tzannes,A.; Keceli,F.; Barua,R.; Vishkin, Uzi (Parallel and Distributed Computing (ISPDC), 2010 Ninth International Symposium on, 2010)
Super-scalar, out-of-order processors that can have tens of read and write requests in the execution window place significant demands on Memory Level Parallelism (MLP). Multi-and many-cores with shared parallel caches further increase MLP demand. Current cache hierarchies however have been unable to keep up with this trend, with modern designs allowing only 4-16 concurrent cache misses. This disconnect is exacerbated by recent highly parallel architectures (e.g. GPUs) where power and area per-core budget favor lighter cores with less resources. Support for hardware and software prefetch increase MLP pressure since these techniques overlap multiple memory requests with existing computation. In this paper, we propose and evaluate a novel Resource-Aware Prefetching (RAP) compiler algorithm that is aware of the number of simultaneous prefetches supported, and optimized for the same. We show that in situations where not enough resources are available to issue prefetch instructions for all references in a loop, it is more beneficial to decrease the prefetch distance and prefetch for as many references as possible, rather than use a fixed prefetched distance and skip prefetching for some references, as in current approaches. We implemented our algorithm in a GCC-derived compiler and evaluated its performance using an emerging fine-grained many-core architecture. Our results show that the RAP algorithm outperforms a well-known loop prefetching algorithm by up to 40.15% and the state-of-the art GCC implementation by up to 34.79%. Moreover, we compare the RAP algorithm with a simple hardware prefetching mechanism, and show improvements of up to 24.61%.
Keywords: algorithm; memory; architecture; hardware-software; architectures; parallel; architectures; resource; aware; caches; super-scalar; compiler; compiler; Multicore; compilers; parallel; GCC-derived; level; management; many-core; memories; storage; out-of-order; Parallel; parallelism; parallel; prefetch; loop; prefetching; prefetching; shared; processor; fine-grained; processors; multiprocessing; systems; optimising

The role of geometry in age estimation - Turaga,P.; Biswas,S.; Chellapa, Rama (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
Understanding and modeling of aging in human faces is an important problem in many real-world applications such as biometrics, authentication, and synthesis. In this paper, we consider the role of geometric attributes of faces, as described by a set of landmark points on the face, in age perception. Towards this end, we show that the space of landmarks can be interpreted as a Grassmann manifold. Then the problem of age estimation is posed as a problem of function estimation on the manifold. The warping of an average face to a given face is quantified as a velocity vector that transforms the average to a given face along a smooth geodesic in unit-time. This deformation is then shown to contain important information about the age of the face. We show in experiments that exploiting geometric cues in a principled manner provides comparable performance to several systems that utilize both geometric and textural cues. We show results on age estimation using the standard FG-Net dataset and a passport dataset which illustrate the effectiveness of the approach.
Keywords: age estimation; Aging; Biometrics; computational geometry; Face; Face Geometry; Facial animation; Feature extraction; function estimation problem; geometric face attributes; Geometry; Grassmann manifold; human face modeling; human face understanding; HUMANS; Mouth; regression; Regression analysis; SHAPE; Solid modeling; solid modelling; velocity vector

Scalable representation of dataflow graph structures using topological patterns - Sane, N.; Kee, Hojin; Seetharaman, G.; Bhattacharyya, Shuvra S. (2010 IEEE Workshop on Signal Processing Systems (SIPS), 2010)
Tools for designing signal processing systems with their semantic foundation in dataflow modeling often use high-level graphical user interface (GUI) or text based languages that allow specifying applications as directed graphs. Such graphical representations serve as an initial reference point for further analysis and optimizations that lead to platform-specific implementations. For large-scale applications, the underlying graphs often consist of smaller substructures that repeat multiple times. To enable more concise representation and direct analysis of such substructures in the context of high level DSP specification languages and design tools, we develop the modeling concept of topological patterns, and propose ways for supporting this concept in a high-level language. We augment the DIF language - a language for specifying DSP-oriented dataflow graphs - with constructs for supporting topological patterns, and we show how topological patterns can be effective in various aspects of embedded signal processing design flows using specific application examples.
Keywords: arrays; data flow graphs; Dataflow graphs; DIF language; Digital signal processing; directed graphs; DSP specification languages; embedded signal processing design flows; embedded systems; Field programmable gate arrays; graphical user interface; Graphical user interfaces; High-level languages; modelbased design; optimisation; optimizations; scalable dataflow graph structures representation; semantics; Signal processing; Signal processing systems; Specification languages; text based languages; Topological patterns; Topology; Transform coding

Selective excitation of LI2 by chirped laser pulses with all possible interstate radiative couplings - Chatterjee, Souvik; Bhattacharyya, Shuvra S. (The Journal of Chemical Physics, 2010)
We have numerically explored the feasibility and the mechanism of population transfer to the excited E 1Σg electronic state of Li2 from the v = 0 level of the ground electronic state X 1Σg using the A 1Σu state as an intermediate. In this system, the use of transform limited pulses with a frequency difference greater than the maximum Rabi frequency does not produce population transfer when all possible radiative couplings are taken into account. We have employed two synchronous pulses far detuned from the allowed transition frequencies, mainly with the lower frequency pulse positively chirped, and both pulses coupling the successive pair of states, X-A and A-E. The adiabaticity of the process has been investigated by a generalized Floquet calculation in the basis of 12 field dressed molecular states, and the results have been compared with those obtained from the full solution of time dependent Schrödinger equation. The conventional representation of the process in terms of three (or four) adiabatic potentials is not valid. It has been found that for cases of almost complete population transfer in full calculations with the conservation of the vibrational quantum number, adiabatic passage is attained with the 12 state Floquet model but not with the six state model. The agreement between the full calculations and the 12 state Floquet calculations is generally good when the transfer is adiabatic. Another characteristic feature of this work is the gaining of control over the vibrational state preparation in the final electronic state by careful tuning of the laser parameters as well as the chirp rate sign. This causes time dependent changes in the adiabatic potentials and nonadiabatic transfers can be made to occur between them.

Signal Processing on Platforms with Multiple Cores: Part 2-Applications and Design [From the Guest Editors] - Chen,Y.; Chakrabarti,C.; Bhattacharyya, Shuvra S.; Bougard, B. (IEEE Signal Processing Magazine, 2010)
Platforms with multiple cores are now prevalent everywhere from desktops and graphics processors to laptops and embedded systems. By adding more parallel computational resources while managing power consumption, multicore platforms offer better programmability, performance, and power efficiency. Signal processing systems of tomorrow will be and must be implemented on platforms with multiple cores. Writing efficient parallel applications that utilize the computing capability of many processing cores require some effort. Signal processing algorithm designers must understand the nuances of a multicore computing engine; only then can the tremendous computing power that such platforms provide be harnessed efficiently. To give a thorough perspective of the area, we have organized two special issues on this topic.
Keywords: Concurrent computing; Embedded system; Energy management; Graphics; Multicore processing; Portable computers; Resource management; Signal design; Signal processing; Signal processing algorithms

Signatures of Reputation - Bethencourt, John; Elaine Shi; Song, Dawn (Financial Cryptography and Data Security, 2010)
Keywords: Computer science

Simulating dynamic communication systems using the core functional dataflow model - Sane, N.; Chia-Jui Hsu; Pino,J. L; Bhattacharyya, Shuvra S. (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
The latest communication technologies invariably consist of modules with dynamic behavior. There exists a number of design tools for communication system design with their foundation in dataflow modeling semantics. These tools must not only support the functional specification of dynamic communication modules and subsystems but also provide accurate estimation of resource requirements for efficient simulation and implementation. We explore this trade-off - between flexible specification of dynamic behavior and accurate estimation of resource requirements - using a representative application employing an adaptive modulation scheme. We propose an approach for precise modeling of such applications based on a recently-introduced form of dynamic dataflow called core functional dataflow. From our proposed modeling approach, we show how parameterized looped schedules can be generated and analyzed to simulate applications with low run-time overhead as well as guaranteed bounded memory execution. We demonstrate our approach using the Advanced Design System from Agilent Technologies, Inc., which is a commercial tool for design and simulation of communication systems.
Keywords: adaptive modulation; Analytical models; Application software; Computational modeling; core functional dataflow model; Dataflow; dataflow modeling semantics; design tools; Digital signal processing; dynamic communication systems; functional specification; Hardware; modeling and simulation; Power system modeling; Predictive models; Processor scheduling; Production; Signal processing; software tools; wireless communication

On Stability of Magnetization Dynamics in Nanoparticles - Mayergoyz, Issak D; Serpico,C.; Bertotti,G. (Magnetics, IEEE Transactions on, 2010)
It is rigorously demonstrated that spatially uniform magnetization oscillations in sufficiently small ellipsoidal nanoparticles can be unconditionally stable with respect to spatially nonuniform perturbations. The proof reveals the dominant stabilizing effect of exchange field which is mathematically manifested through the Poincare inequality.
Keywords: (electron); magnetic; DYNAMICS; ellipsoidal; field; magnetization; inequality; exchange; INTERACTIONS; magnetization; nanoparticles; spatially; nonuniform; oscillations; spin-wave; particles; magnetisation; nanoparticles; spin; perturbations; exchange; perturbations; spatially; Poincare; stability; small; uniform; waves

Stochastic simulations with graphics hardware: Characterization of accuracy and performance - Balijepalli,A.; LeBrun,T. W.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2010)

Structural Assembly of Molecular Complexes Based on Residual Dipolar Couplings - Berlin,Konstantin; O’Leary,Dianne P.; Fushman, David (J. Am. Chem. Soc., 2010)
We present and evaluate a rigid-body molecular docking method, called PATIDOCK, that relies solely on the three-dimensional structure of the individual components and the experimentally derived residual dipolar couplings (RDCs) for the complex. We show that, given an accurate ab initio predictor of the alignment tensor from a protein structure, it is possible to accurately assemble a protein?protein complex by utilizing the RDCs? sensitivity to molecular shape to guide the docking. The proposed docking method is robust against experimental errors in the RDCs and computationally efficient. We analyze the accuracy and efficiency of this method using experimental or synthetic RDC data for several proteins, as well as synthetic data for a large variety of protein?protein complexes. We also test our method on two protein systems for which the structure of the complex and steric-alignment data are available (Lys48-linked diubiquitin and a complex of ubiquitin and a ubiquitin-associated domain) and analyze the effect of flexible unstructured tails on the outcome of docking. The results demonstrate that it is fundamentally possible to assemble a protein?protein complex solely on the basis of experimental RDC data and the prediction of the alignment tensor from 3D structures. Thus, despite the purely angular nature of RDCs, they can be converted into intermolecular distance/translational constraints. Additionally, we show a method for combining RDCs with other experimental data, such as ambiguous constraints from interface mapping, to further improve structure characterization of protein complexes.We present and evaluate a rigid-body molecular docking method, called PATIDOCK, that relies solely on the three-dimensional structure of the individual components and the experimentally derived residual dipolar couplings (RDCs) for the complex. We show that, given an accurate ab initio predictor of the alignment tensor from a protein structure, it is possible to accurately assemble a protein?protein complex by utilizing the RDCs? sensitivity to molecular shape to guide the docking. The proposed docking method is robust against experimental errors in the RDCs and computationally efficient. We analyze the accuracy and efficiency of this method using experimental or synthetic RDC data for several proteins, as well as synthetic data for a large variety of protein?protein complexes. We also test our method on two protein systems for which the structure of the complex and steric-alignment data are available (Lys48-linked diubiquitin and a complex of ubiquitin and a ubiquitin-associated domain) and analyze the effect of flexible unstructured tails on the outcome of docking. The results demonstrate that it is fundamentally possible to assemble a protein?protein complex solely on the basis of experimental RDC data and the prediction of the alignment tensor from 3D structures. Thus, despite the purely angular nature of RDCs, they can be converted into intermolecular distance/translational constraints. Additionally, we show a method for combining RDCs with other experimental data, such as ambiguous constraints from interface mapping, to further improve structure characterization of protein complexes.

SwitchBlade: a platform for rapid deployment of network protocols on programmable hardware - Anwer,Muhammad Bilal; Motiwala,Murtaza; Bin Tariq,Mukarram; Feamster, Nick (SIGCOMM Comput. Commun. Rev., 2010)
We present SwitchBlade, a platform for rapidly deploying custom protocols on programmable hardware. SwitchBlade uses a pipeline-based design that allows individual hardware modules to be enabled or disabled on the fly, integrates software exception handling, and provides support for forwarding based on custom header fields. SwitchBlade's ease of programmability and wire-speed performance enables rapid prototyping of custom data-plane functions that can be directly deployed in a production network. SwitchBlade integrates common packet-processing functions as hardware modules, enabling different protocols to use these functions without having to resynthesize hardware. SwitchBlade's customizable forwarding engine supports both longest-prefix matching in the packet header and exact matching on a hash value. SwitchBlade's software exceptions can be invoked based on either packet or flow-based rules and updated quickly at runtime, thus making it easy to integrate more flexible forwarding function into the pipeline. SwitchBlade also allows multiple custom data planes to operate in parallel on the same physical hardware, while providing complete isolation for protocols running in parallel. We implemented SwitchBlade using NetFPGA board, but SwitchBlade can be implemented with any FPGA. To demonstrate SwitchBlade's flexibility, we use SwitchBlade to implement and evaluate a variety of custom network protocols: we present instances of IPv4, IPv6, Path Splicing, and an OpenFlow switch, all running in parallel while forwarding packets at line rate.
Keywords: netfpga; network virtualization

Syntactic Topic Models - Jordan Boyd-Graber; Blei,David M. (arXiv:1002.4665v1, 2010)
The syntactic topic model (STM) is a Bayesian nonparametric model of language that discovers latent distributions of words (topics) that are both semantically and syntactically coherent. The STM models dependency parsed corpora where sentences are grouped into documents. It assumes that each word is drawn from a latent topic chosen by combining document-level features and the local syntactic context. Each document has a distribution over latent topics, as in topic models, which provides the semantic consistency. Each element in the dependency parse tree also has a distribution over the topics of its children, as in latent-state syntax models, which provides the syntactic consistency. These distributions are convolved so that the topic of each word is likely under both its document and syntactic context. We derive a fast posterior inference algorithm based on variational methods. We report qualitative and quantitative studies on both synthetic data and hand-parsed documents. We show that the STM is a more predictive model of language than current models based only on syntax or only on topics.
Keywords: Computer Science - Artificial Intelligence; Computer Science - Computation and Language; Mathematics - Statistics Theory

Toque: designing a cooking-based programming language for and with children - Tarkan,S.; Sazawal,V.; Druin, Allison; Golub,E.; Bonsignore,E. M; Walsh,G.; Atrash,Z. (Proceedings of the 28th international conference on Human factors in computing systems, 2010)

Tracking via object reflectance using a hyperspectral video camera - Nguyen,Hien Van; Banerjee, A.; Chellapa, Rama (2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2010)
Recent advances in electronics and sensor design have enabled the development of a hyperspectral video camera that can capture hyperspectral datacubes at near video rates. The sensor offers the potential for novel and robust methods for surveillance by combining methods from computer vision and hyperspectral image analysis. Here, we focus on the problem of tracking objects through challenging conditions, such as rapid illumination and pose changes, occlusions, and in the presence of confusers. A new framework that incorporates radiative transfer theory to estimate object reflectance and the mean shift algorithm to simultaneously track the object based on its reflectance spectra is proposed. The combination of spectral detection and motion prediction enables the tracker to be robust against abrupt motions, and facilitate fast convergence of the mean shift tracker. In addition, the system achieves good computational efficiency by using random projection to reduce spectral dimension. The tracker has been evaluated on real hyperspectral video data.
Keywords: Computer vision; electronic design; hyperspectral datacubes; hyperspectral image analysis; Hyperspectral imaging; Hyperspectral sensors; hyperspectral video camera; Image motion analysis; Image sensors; lighting; Motion estimation; motion prediction; Object detection; object reflectance tracking; random projection; Reflectivity; robust methods; Robustness; sensor design; spectral detection; Surveillance; tracking; Video surveillance

Utilizing Hierarchical Multiprocessing for Medical Image Registration - Plishker,W.; Dandekar,O.; Bhattacharyya, Shuvra S.; Shekhar,R. (IEEE Signal Processing Magazine, 2010)
This work discusses an approach to utilize hierarchical multiprocessing in the context of medical image registration. By first organizing application parallelism into a domain-specific taxonomy, an algorithm is structured to target a set of multicore platforms.The approach on a cluster of graphics processing units (GPUs) requiring the use of two parallel programming environments to achieve fast execution times is demonstrated.There is negligible loss in accuracy for rigid registration when employing GPU acceleration, but it does adversely effect our nonrigid registration implementation due to our usage of a gradient descent approach.
Keywords: Acceleration; application parallelism; Biomedical imaging; domain-specific taxonomy; GPU acceleration; gradient descent approach; Graphics processing unit; hierarchical multiprocessing; image registration; Magnetic resonance imaging; Medical diagnostic imaging; medical image processing; medical image registration; multicore platform set; Multicore processing; PARALLEL PROCESSING; parallel programming; Robustness; Signal processing algorithms; Ultrasonic imaging

VizWiz: nearly real-time answers to visual questions - Bigham,Jeffrey P.; Jayant,Chandrika; Ji,Hanjie; Little,Greg; Miller,Andrew; Miller,Robert C.; Miller,Robin; Tatarowicz,Aubrey; White,Brandyn; White,Samual; Tom Yeh (Proceedings of the 23nd annual ACM symposium on User interface software and technology, 2010)
The lack of access to visual information like text labels, icons, and colors can cause frustration and decrease independence for blind people. Current access technology uses automatic approaches to address some problems in this space, but the technology is error-prone, limited in scope, and quite expensive. In this paper, we introduce VizWiz, a talking application for mobile phones that offers a new alternative to answering visual questions in nearly real-time - asking multiple people on the web. To support answering questions quickly, we introduce a general approach for intelligently recruiting human workers in advance called quikTurkit so that workers are available when new questions arrive. A field deployment with 11 blind participants illustrates that blind people can effectively use VizWiz to cheaply answer questions in their everyday lives, highlighting issues that automatic approaches will need to address to be useful. Finally, we illustrate the potential of using VizWiz as part of the participatory design of advanced tools by using it to build and evaluate VizWiz::LocateIt, an interactive mobile tool that helps blind people solve general visual search problems.
Keywords: blind users; non-visual interfaces; real-time human computation

VizWiz::LocateIt - enabling blind people to locate objects in their environment - Bigham,Jeffrey P.; Jayant,Chandrika; Miller,Andrew; White,Brandyn; Tom Yeh (Computer Vision and Pattern Recognition Workshops (CVPRW), 2010 IEEE Computer Society Conference on, 2010)
Blind people face a number of challenges when interacting with their environments because so much information is encoded visually. Text is pervasively used to label objects, colors carry special significance, and items can easily become lost in surroundings that cannot be quickly scanned. Many tools seek to help blind people solve these problems by enabling them to query for additional information, such as color or text shown on the object. In this paper we argue that many useful problems may be better solved by directly modeling them as search problems, and present a solution called VizWiz::LocateIt that directly supports this type of interaction. VizWiz::LocateIt enables blind people to take a picture and ask for assistance in finding a specific object. The request is first forwarded to remote workers who outline the object, enabling efficient and accurate automatic computer vision to guide users interactively from their existing cellphones. A two-stage algorithm is presented that uses this information to guide users to the appropriate object interactively from their phone.

When is it better not to look ahead? - Nau, Dana S.; Luštrek,Mitja; Parker,Austin; Bratko,Ivan; Gams,Matjaž (Artificial Intelligence, 2010)
In situations where one needs to make a sequence of decisions, it is often believed that looking ahead will help produce better decisions. However, it was shown 30 years ago that there are “pathological” situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what combinations of factors have the biggest influence on whether lookahead pathology occurs, and (b) whether it occurs in real-world decision-making.This paper includes simulation results for several synthetic game-tree models, and experimental results for three well-known board games: two chess endgames, kalah (with some modifications to facilitate experimentation), and the 8-puzzle. The simulations show the interplay between lookahead pathology and several factors that affect it; and the experiments confirm the trends predicted by the simulation models. The experiments also show that lookahead pathology is more common than has been thought: all three games contain situations where it occurs.
Keywords: Game-tree search; Lookahead pathology; minimax

Who's Hogging the Bandwidth: The Consequences of Revealing the Invisible in the Home - Marshini Chetty; Banks, Richard; Harper, Richard; Regan, Tim; Sellen, Abigail; Gkantsidis, Christos; Karagiannis, Thomas; Key, Peter (SIGCHI '10, 2010)
As more technologies enter the home, householders are burdened with the task of digital housekeeping-managing and sharing digital resources like bandwidth. In response to this, we created and evaluated a domestic tool for bandwidth management called Home Watcher. Our field trial showed that when resource contention amongst different household members is made visible, people's understanding of bandwidth changes and household politics are revealed. In this paper, we describe the consequences of showing real time resource usage in a home, and how this varies depending on the social make up of the household.
Keywords: bandwidth monitoring; home broadband; home networks

Workshop on experimental evaluation of software and systems in computer science (Evaluate 2010) - Blackburn,Steven M.; Diwan,Amer; Hauswirth,Matthias; Memon, Atif M.; Sweeney,Peter F. (Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion, 2010)
We call ourselves 'computer scientists', but are we scientists? If we are scientists, then we must practice the scientific method. This includes a solid experimental evaluation. In our experience, our experimental methodology is ad hoc at best, and nonexistent at worst. This workshop brings together experts from different areas of computer science to discuss, explore, and attempt to identify the principles of sound experimental evaluation
Keywords: Evaluation; METHODOLOGY

Young Proteins Experience More Variable Selection Pressures Than Old Proteins - Vishnoi,Anchal; Kryazhimskiy,Sergey; Bazykin,Georgii A; Hannenhalli, Sridhar; Plotkin,Joshua B. (Genome ResearchGenome Res., 2010)
It is well known that young proteins tend to experience weaker purifying selection and evolve more quickly than old proteins. Here, we show that, in addition, young proteins tend to experience more variable selection pressures over time than old proteins. We demonstrate this pattern in three independent taxonomic groups: yeast, Drosophila, and mammals. The increased variability of selection pressures on young proteins is highly significant even after controlling for the fact that young proteins are typically shorter and experience weaker purifying selection than old proteins. The majority of our results are consistent with the hypothesis that the function of a young gene tends to change over time more readily than that of an old gene. At the same time, our results may be caused in part by young genes that serve constant functions over time, but nevertheless appear to evolve under changing selection pressures due to depletion of adaptive mutations. In either case, our results imply that the evolution of a protein-coding sequence is partly determined by its age and origin, and not only by the phenotypic properties of the encoded protein. We discuss, via specific examples, the consequences of these findings for understanding of the sources of evolutionary novelty.

Age progression in human faces: A survey - Ramanathan,N.; Chellapa, Rama; Biswas,S. (Journal of Visual Languages and Computing, 2009)
Facial aging, a new dimension that has recently beenadded to the problem of face recognition, poses interesting theo- retical and practical challenges to the research community. The problem which originally generated interest in the psychophysics and human perception community, has recently found enhanced interest in the computer vision community. How do humans perceive age ? What constitutes an age-invariant signature that can be derived from faces ? How compactly can the facial growth event be described ? How does facial aging impact recognition performance ? In this paper, we give a thorough analysis on the problem of facial aging and further provide a complete account of the many interesting studies that have been performed on this topic from different fields. We offer a comparative analysis of various approaches that have been proposed for problems such as age estimation, appearance prediction, face verification etc. and offer insights into future research on this topic.

Algorithms for extraction of nanowire lengths and positions from optical section microscopy image sequence - Peng,T.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. W. (Journal of Computing and Information Science in Engineering, 2009)

All Bits Are Not Equal - A Study of IEEE 802.11 Communication Bit Errors - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Bhattacharjee, Bobby; Miller,R.R. (INFOCOM 2009, IEEE, 2009)
In IEEE 802.11 Wireless LAN (WLAN) systems, techniques such as acknowledgement, retransmission, and transmission rate adaptation, are frame-level mechanisms designed for combating transmission errors. Recently sub-frame level mechanisms such as frame combining have been proposed by the research community. In this paper, we present results obtained from our bit error study for identifying sub-frame error patterns because we believe that identifiable bit error patterns can potentially introduce new opportunities in channel coding, network coding, forward error correction (FEC), and frame combining mechanisms. We have constructed a number of IEEE 802.11 wireless LAN testbeds and conducted extensive experiments to study the characteristics of bit errors and their location distribution. Conventional wisdom dictates that bit error probability is the result of channel condition and ought to follow corresponding distribution. However our measurement results identify three repeatable bit error patterns that are not induced by channel conditions. We have verified that such error patterns are present in WLAN transmissions in different physical environments and across different wireless LAN hardware platforms. We also discuss our current hypotheses for the reasons behind these bit error probability patterns and how identifying these patterns may help improving WLAN transmission robustness.
Keywords: 802.11; bit; coding; error; coding; forward; coding; subframe; combining; Communication; correction; frame; correction; wireless; error; errors; channel; errors; wireless; IEEE; LAN; LAN; channel; mechanisms; network; patterns; transmission; statistics; forward

Analytical Description of Quasi-Random Magnetization Relaxation to Equilibrium - Serpico,C.; d'Aquino,M.; Bertotti,G.; Mayergoyz, Issak D (Magnetics, IEEE Transactions on, 2009)
The Landau-Lifshitz (LL) dynamics of a uniformly magnetized particle is considered. The LL equation is written in the form of a Hamiltonian perturbed dynamical system. By using suitable averaging technique, the equation for the slow dynamics of the energy is derived. The averaging technique breaks up in the case of separatrix crossing. It is shown that, in the limit of small damping, the separatrix crossing can be described by using a probabilistic approach.
Keywords: approach; quasirandom; crossing; uniformly; dynamical; dynamics; averaging; Hamiltonian; magnetization; magnetized; particle; magnetic; particles; magnetic; perturbed; relaxation; magnetisation; probability; relaxation; separatrix; system; Landau-Lifshitz; technique; damping; probabilistic

Analyzing (social media) networks with NodeXL - Smith,Marc A.; Shneiderman, Ben; Milic-Frayling,Natasa; Mendes Rodrigues,Eduarda; Barash,Vladimir; Dunne,Cody; Capone,Tony; Perer,Adam; Gleave,Eric (Proceedings of the fourth international conference on Communities and technologies, 2009)
We present NodeXL, an extendible toolkit for network overview, discovery and exploration implemented as an add-in to the Microsoft Excel 2007 spreadsheet software. We demonstrate NodeXL data analysis and visualization features with a social media data sample drawn from an enterprise intranet social network. A sequence of NodeXL operations from data import to computation of network statistics and refinement of network visualization through sorting, filtering, and clustering functions is described. These operations reveal sociologically relevant differences in the patterns of interconnection among employee participants in the social media space. The tool and method can be broadly applied.
Keywords: excel; network analysis; social media; social network; spreadsheet; Visualization

Analyzing the process of installing rogue software - Berthier,R.; Arjona,J.; Michel Cukier (2009)
This practical experience report presents the results of an experiment aimed at understanding the sequence of malicious actions following a remote compromise. The type of rogue software installed during attacks was used to classify and understand sequences of malicious actions. For this experiment, we used four Linux target computers running SSH with simple passwords. During the eight-month data collection period, we recorded a total of 1,171 attack sessions. In these sessions, attackers typed a total of 20,335 commands that we categorized into 24 specific actions. These actions were analyzed based on the type of rogue software installed by attackers.
Keywords: Linux; Linux target computers; malicious actions; rogue software installation; security of data

An architectural level design methodology for smart camera applications - Saha,S.; Kianzad,V.; Schlessman,J.; Aggarwal,G.; Bhattacharyya, Shuvra S.; Chellapa, Rama; Wolf,W. (International Journal of Embedded Systems, 2009)
Today's embedded computing applications are characterised by increased functionality, and hence increased design complexity and processing requirements. The resulting design spaces are vast and designers are typically able to evaluate only small subsets of solutions due to lack of efficient design tools. In this paper, we propose an architectural level design methodology that provides a means for a comprehensive design space exploration for smart camera applications and enable designers to select higher quality solutions and provides substantial savings on the overall cost of the system. We present efficient, accurate and intuitive models for performance estimation and validate them with experiments.

An assessment of systems and software engineering scholars and institutions (2002–2006) - Wong,W. Eric; Tse,T.H.; Glass,Robert L.; Basili, Victor R.; Chen,T.Y. (Journal of Systems and Software, 2009)
This paper summarizes a survey of publications in the field of systems and software engineering from 2002 to 2006. The survey is an ongoing, annual event that identifies the top 15 scholars and institutions over a 5-year period. The rankings are calculated based on the number of papers published in TSE, TOSEM, JSS, SPE, EMSE, IST, and Software. The top-ranked institution is Korea Advanced Institute of Science and Technology, Korea, and the top-ranked scholar is Magne Jørgensen of Simula Research Laboratory, Norway.
Keywords: Research publications; Systems and software engineering; Top institutions; Top scholars

Better vocabularies for assistive communication aids: connecting terms using semantic networks and untrained annotators - Nikolova,Sonya; Jordan Boyd-Graber; Fellbaum,Christiane; Cook,Perry (Proceedings of the 11th international ACM SIGACCESS conference on Computers and accessibility, 2009)
The difficulties of navigating vocabulary in an assistive communication device are exacerbated for individuals with lexical access disorders like those due to aphasia. We present the design and implementation of a vocabulary network based on WordNet, a resource that attempts to model human semantic memory, that enables users to find words easily. To correct for the sparsity of links among words, we augment WordNet with additional connections derived from human judgments of semantic similarity collected in an online experiment. We evaluate the resulting system, the visual vocabulary for aphasia (ViVA), and describe its potential to adapt to a user's profile and enable faster search and improved navigation.
Keywords: adaptive tools; aphasia; assistive communication; semantic networks; visual vocabularies

Channel Access Throttling for Improving WLAN QoS - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Sensor, Mesh and Ad Hoc Communications and Networks, 2009. SECON '09. 6th Annual IEEE Communications Society Conference on, 2009)
The de facto QoS channel access method for the IEEE 802.11 Wireless LANs is the Enhanced Distributed Channel Access (EDCA) mechanism, which differentiates transmission treatments for data frames belonging to different traffic categories with four different levels of channel access priority. In this paper, we propose extending EDCA with Channel Access Throttling (CAT) for more flexible and efficient QoS support. By assigning different member stations different channel access parameters, CAT differentiates channel access priorities not between traffic categories but between member stations. Then by dynamically changing the channel access parameters of each member station based on a pre-computed schedule, CAT enables EDCA WLANs the benefits of scheduled access QoS. We also present evaluation results of CAT obtained from both simulations and experiments conducted using off-the-shelf WLAN hardware and open-source device driver. Our results show that CAT can proportionally partition channel capacity, significantly improve performance of multimedia applications, effectively achieve performance protection for admitted flows, and increase per cell VoIP call capacity by up to 41%.
Keywords: 802.11; access; area; call; capacity; data; capacity; quality; capacity; WLAN; categories; transmission; channel; device; distributed; driver; quality; facto; frames; de; IEEE; LAN; LAN; VoIP; local; mechanism; member; method; enhanced; multimedia; network; wireless; networks; channel; of; parameters; channel; priority; channel; QoS; QoS; channel; service; telecommunication; service; traffic; standards; telecommunication; stations; open-source; throttling; channel; traffic; wireless; treatments; wireless; wireless

Channel Access Throttling for Overlapping BSS Management - Han,Bo; Ji,Lusheng; Lee,Seungjoon; Miller,R.R.; Bhattacharjee, Bobby (Communications, 2009. ICC '09. IEEE International Conference on, 2009)
Multiple co-channel WLAN BSSes (i.e., WLAN cells) overlapping in coverage are generally considered undesirable because members of the OBSSes compete for channel access, which typically increases the contention level of wireless medium access and reduces overall system performance. In this paper, we propose to use channel access throttling (CAT) for managing Wireless LAN radio resources for overlapping BSSes (OBSSes). CAT provides an access point (AP) of each BSS with a mechanism to control channel access parameters of its member stations on the fly. By coordinating the CAT operations of the OBSS APs, we can enable privileged channel access to an individual BSS at a particular time, for example, by assigning high priority access parameters to member stations associated with the BSS. By controlling how much each BSS may be given the privileged channel access, we can also achieve a proportional partitioning of channel capacity among OBSSes. We present evaluation results obtained from both simulations and experiments using testbed built with commercial off-the-shelf (COTS) WLAN hardware and open-source device driver. Our results show that with CAT, not only can we proportionally partition channel capacity among the OBSSes, but also improve channel utilization efficiency and increase overall capacity.
Keywords: access; access; cellular; allocation; channel; BSS; capacity; computer; capacity; proportional; cell; open-source; channel; channels; co-channel; device; driver; overlapping; efficiency; high-priority; LAN; wireless; management; partition; management; wireless; medium; network; parameters; multiple; partitioning; radio; radio; channel; resources; wireless; throttling; channel; utilization; WLAN

Characterization and control of pin diameter during in-mold assembly of mesoscale revolute joints - Ananthanarayanan,A.; Gupta,S.K.; Bruck,H. A. (North American Manufacturing Research Institute, 2009)
Macro-scale revolute joints can be formed byfirst molding the hole and then molding the pin inside the hole. As the pin shrinks during the solidification process, it moves away from the hole and provides the clearance for the joint to function. The value of clearance in the macro- scale joint can be controlled by carefully selecting the process parameters and the material for the pin. However, in order for this strategy to work at the mesoscale, it requires the use of very thin cores to form sub-millimeter holes. Such thin cores are very difficult to make, are easily damaged during the molding process, and very difficult to retract from the hole. Our previous work has shown that making the pins first and then creating holes on the top of pins leads to successful mesoscale joints. This strategy is counter intuitive based on our experiences at the macro-scale. At the macroscale, as the hole shrinks on top of the pin, the joint is jammed. So a fundamental question is why this counter-intuitive strategy works at the mesoscale. In this paper we show that at the mesoscale, the joint jamming is prevented because of the deformation of the pin under the compressive loading during the second stage molding. We also describe features in the mold that can control the pin deformation and hence control the joint parameters. We present experimental data and computational models to show how mesoscale revolute joints can be formed.

Characterizing VLAN-induced sharing in a campus network - Bin Tariq,Mukarram; Mansy,Ahmed; Feamster, Nick; Ammar,Mostafa (Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, 2009)
Many enterprise, campus, and data-center networks have complex layer-2 virtual LANs ("VLANs") below the IP layer. The interaction between layer-2 and IP topologies in these VLANs introduces hidden dependencies between IP level network and the physical infrastructure that has implications for network management tasks such as planning for capacity or reliability, and for fault diagnosis. This paper characterizes the extent and effect of these dependencies in a large campus network. We first present the design and implementation of EtherTrace, a tool that we make publicly available, which infers the layer-2 topology using data passively collected from Ethernet switches. Using this tool, we infer the layer-2 topology for a large campus network and compare it with the IP topology. We find that almost 70% of layer-2 edges are shared by 10 or more IP edges, and a single layer-2 edge may be shared by as many as 34 different IP edges. This sharing of layer-2 edges and switches among IP paths commonly results from trunking multiple VLANs to the same access router, or from colocation of academic departments that share layer-2 infrastructure, but have logically separate IP subnet and routers. We examine how this sharing affects the accuracy and specificity of fault diagnosis. For example, applying network tomography to the IP topology to diagnose failures caused by layer-2 devices results in only 54% accuracy, compared to 100% accuracy when our tomography algorithm takes input across layers.
Keywords: network diagnosis; network virtualization; VLAN; vlan-induced dependency

Collective classification for text classification - Namata,G.; Sen,P.; Bilgic,M.; Getoor, Lise (Text Mining: Classification, Clustering, and ApplicationsText Mining: Classification, Clustering, and Applications, 2009)

Collective relational clustering - Bhattacharya,I.; Getoor, Lise (Constrained Clustering: Advances in Algorithms, Theory, and ApplicationsConstrained Clustering: Advances in Algorithms, Theory, and Applications, 2009)

Computational methods for modeling facial aging: A survey - Ramanathan,Narayanan; Chellapa, Rama; Biswas,Soma (Journal of Visual Languages & Computing, 2009)
Facial aging, a new dimension that has recently been added to the problem of face recognition, poses interesting theoretical and practical challenges to the research community. The problem which originally generated interest in the psychophysics and human perception community has recently found enhanced interest in the computer vision community. How do humans perceive age? What constitutes an age-invariant signature that can be derived from faces? How compactly can the facial growth event be described? How does facial aging impact recognition performance? In this paper, we give a thorough analysis on the problem of facial aging and further provide a complete account of the many interesting studies that have been performed on this topic from different fields. We offer a comparative analysis of various approaches that have been proposed for problems such as age estimation, appearance prediction, face verification, etc. and offer insights into future research on this topic.
Keywords: age estimation; Age progression; Craniofacial growth; face recognition

Connections between the lines: augmenting social networks with text - Chang,Jonathan; Jordan Boyd-Graber; Blei,David M. (Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, 2009)
Network data is ubiquitous, encoding collections of relationships between entities such as people, places, genes, or corporations. While many resources for networks of interesting entities are emerging, most of these can only annotate connections in a limited fashion. Although relationships between entities are rich, it is impractical to manually devise complete characterizations of these relationships for every pair of entities on large, real-world corpora. In this paper we present a novel probabilistic topic model to analyze text corpora and infer descriptions of its entities and of relationships between those entities. We develop variational methods for performing approximate inference on our model and demonstrate that our model can be practically deployed on large corpora such as Wikipedia. We show qualitatively and quantitatively that our model can construct and annotate graphs of relationships and make useful predictions.
Keywords: Graphical models; social network learning; statistical topic models

CPM: Adaptive Video-on-Demand with Cooperative Peer Assists and Multicast - Gopalakrishnan,V.; Bhattacharjee, Bobby; Ramakrishnan,K.K.; Jana,R.; Srivastava,D. (INFOCOM 2009, IEEE, 2009)
We present CPM, a unified approach that exploits server multicast, assisted by peer downloads, to provide efficient video-on-demand (VoD) in a service provider environment. We describe our architecture and show how CPM is designed to dynamically adapt to a wide range of situations including highly different peer-upload bandwidths, content popularity, user request arrival patterns, video library size, and subscriber population. We demonstrate the effectiveness of CPM using simulations (based on an actual implementation codebase) across the range of situations described above and show that CPM does significantly better than traditional unicast, different forms of multicast, as well as peer-to-peer schemes. Along with synthetic parameters, we augment our experiments using data from a deployed VoD service to evaluate the performance of CPM.
Keywords: assists; multicast; peer-to-peer; communication; peer-to-peer; computing; video; CPM; cooperative; demand; on; parameters; video-on-demand; multicast; peer; schemes; synthetic

CTCF binding site classes exhibit distinct evolutionary, genomic, epigenomic and transcriptomic features - Essien,Kobby; Vigneau,Sebastien; Apreleva,Sofia; Singh,Larry N.; Bartolomei,Marisa S.; Hannenhalli, Sridhar (Genome Biology, 2009)
CTCF (CCCTC-binding factor) is an evolutionarily conserved zinc finger protein involved in diverse functions ranging from negative regulation of MYC, to chromatin insulation of the beta-globin gene cluster, to imprinting of the Igf2 locus. The 11 zinc fingers of CTCF are known to differentially contribute to the CTCF-DNA interaction at different binding sites. It is possible that the differences in CTCF-DNA conformation at different binding sites underlie CTCF's functional diversity. If so, the CTCF binding sites may belong to distinct classes, each compatible with a specific functional role.

A Decoupled and Prioritized Stochastic Dynamic Programming Approach for Automated Transport of Multiple Particles Using Optical Tweezers - Banerjee,Ashis Gopal; Losert,Wolfgang; Gupta, Satyandra K. (ASME, 2009)
Automated transport of multiple particles using optical tweezers requires the use of motion planning to move them simultaneously while avoiding collisions amongst themselves and with randomly moving obstacles. This paper develops a decoupled and prioritized stochastic dynamic programming based motion planning framework by sequentially applying a partially observable Markov decision process algorithm on every particle that needs to be transported. An iterative version of a maximum bipartite graph matching algorithm is used to assign given goal locations to such particles. The algorithm for individual particle transport is validated using silica beads in a holographic tweezer set-up. Once the individual plans are computed, a three-step method consisting of clustering, classification, and branch and bound optimization is employed to determine the final collision-free paths. Simulation results in the form of sample trajectories and performance characterization plots are presented to illustrate the usefulness of the developed approach.

The design of ViVA: a mixed-initiative visual vocabulary for aphasia - Nikolova,Sonya; Jordan Boyd-Graber; Cook,Perry R. (Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, 2009)
In this paper, we present the design of ViVA, a visual vocabulary for aphasia. Aphasia is an acquired language disorder that causes variability of impairments affecting individual's ability to speak, comprehend, read and write. Existing communication aids lack flexibility and adequate customization functionality failing to address this variability and to satisfy individual user needs. We tackle these shortcomings by incorporating adaptive and adaptable capabilities in ViVA which is designed to assist communication for users suffering from aphasia. The visual vocabulary for aphasia implements a novel approach that organizes the words in the vocabulary according to user preferences, word usage and certain semantic measures, thus continuously tailoring the tool to the user's profile.
Keywords: adaptive and adaptable interfaces; assistive communication tools; multi-modal interfaces

Designing the reading experience for scanned multi-lingual picture books on mobile phones - Bederson, Benjamin B.; Quinn,A.; Druin, Allison (Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries, 2009)

Detecting network neutrality violations with causal inference - Bin Tariq,Mukarram; Motiwala,Murtaza; Feamster, Nick; Ammar,Mostafa (Proceedings of the 5th international conference on Emerging networking experiments and technologies, 2009)
We present NANO, a system that detects when ISPs apply policies that discriminate against specific classes of applications, users, or destinations. Existing systems for detecting discrimination are typically specific to an application or to a particular discrimination mechanism and rely on active measurement tests. Unfortunately, ISPs can change discrimination policies and mechanisms, and they can evade these tests by giving probe traffic higher priority. NANO detects ISP discrimination by passively collecting performance data from clients. To distinguish discrimination from other causes of degradation (e.g., overload, misconfiguration, failure), NANO establishes a causal relationship between an ISP and observed performance by adjusting for confounding factors. NANO agents deployed at participating clients across the Internet collect performance data for selected services and report this information to centralized servers, which analyze the measurements to establish causal relationship between an ISP and performance degradations. We have implemented NANO and deployed clients in a controlled environment on Emulab. We run a combination of controlled experiments on Emulab and wide-area experiments on PlanetLab that show that NANO can determine the extent and criteria for discrimination for a variety of discrimination policies and applications.
Keywords: causal inference; network neutrality

Distinguishing knowledge vs social capital in social media with roles and context - Barash,V.; Smith,M.; Getoor, Lise; Welser,H. T (Proceedings of the ICWSM, 2009)
Social media communities (e.g. Wikipedia, Flickr, Live Q&A) give rise to distinct types of content, foremost among which are relational content (discussion, chat) and factual content (answering questions, problem-solving). Both users and researchers are increasingly interested in developing strategies that can rapidly distinguish these types of content. While many text-based and structural strategies are possible, we extend two bodies of research that show how social context, and the social roles of answerers can predict content type. We test our framework on a dataset of manually labeled contributions to Microsoft's Live Q&A and find that it reliably extracts factual and relational messages from the data.

Do you know the way to SNA?: A process model for analyzing and visualizing social media data - Hansen,D. L; Rotman,D.; Bonsignore,E.; Milic-Frayling,N.; Rodrigues,E.M.; Smith,M.; Shneiderman, Ben (University of Maryland Tech Report: HCIL-2009-17, 2009)
Traces of activity left by social media users can shed lighton individual behavior, social relationships, and community efficacy. Tools and processes to analyze social traces are essential for enabling practitioners to study and nurture meaningful and sustainable social interaction. Yet such tools and processes remain in their infancy. We conducted a study of 15 graduate students who were learning to apply Social Network Analysis (SNA) to data from online communities. Based on close observations of their emergent practices, we derived the Network Analysis and Visualization (NAV) process model and identified stages where intervention from peers, experts, and an SNA tool were most useful. We show how the NAV model informs the design of SNA tools and services, education practices, and support for social media practitioners.

Electromagnetic Analysis of Plasmon-Resonance Based All-Optical Magnetic Recording - Mayergoyz, Issak D; Zhang,Zhenyu; McAvoy,P.; Bowen,D.; Krafft,C. (Magnetics, IEEE Transactions on, 2009)
The electromagnetic analysis of plasmon-resonance-based all-optical magnetic recording is performed. This analysis is based on the treatment of plasmon resonances as an eigenvalue problem for specific boundary integral equations. The plasmon modes which can be excited in circular nanoholes and cylindrical nanoshells by circularly polarized light are theoretically and numerically studied. Dramatic enhancement of circularly polarized light intensity on the nanoscale through the excitation of specific plasmon modes in uniaxial nanostructures is demonstrated.
Keywords: Ag; boundary; all-optical; analysis; magnetization; and; based; effects; nanoparticles; silver; surface; eigenfunctions; magnetic; equations; circular; equations; eigenvalues; integral; intensity; cylindrical; light; magnetic; modes; plasmon-resonance; nanoholes; circularly; nanoshells; eigenvalue; nanostructures; boundary; plasmon; polarized; problem; electromagnetic; recording; magnetisation; recording; silver; uniaxial; resonance; reversal; magneto-optical; reversals; nanoparticle; plasmon

The emergence of zoning policy games in exurban jurisdictions: Informing collective action theory - Zellner,Moira L.; Page,Scott E.; Rand, William; Brown,Daniel G.; Robinson,Derek T.; Nassauer,Joan; Low,Bobbi (Land Use Policy, 2009)
Theoretical urban policy literature predicts the likelihood of free riding in the management of common goods such as forested open space; such outcome is often characterized as a Prisoner's Dilemma game. Numerous cases exist in which neighboring jurisdictions cooperate to maintain public goods, challenging the expected results, yet theoretical explanations of these cases have not been fully developed. In this paper, we use an agent-based model to explore how underlying micro-behaviors affect the payoffs obtained by two neighboring municipalities in a hypothetical exurban area. Payoffs are measured in terms of regional forested space and of local tax revenue at the end of the agent-based simulations; the municipalities affect these payoffs through their choice of residential zoning policies and the spillover effect between the neighboring jurisdictions. Zoning restrictions influence the conversion of farmland into residential subdivisions of different types, and consequently the location of heterogeneous residential households in the region. Developers and residents respond to the changing landscape characteristics, thus establishing a feedback between early and future land-use patterns. The structure of the simulated payoffs is analyzed using standard game theory. Our analysis shows that a variety of games, in addition to Prisoner's Dilemma, can emerge between the neighboring jurisdictions. Other games encourage coordination or subsidization, offering some explanations for the unexpected observations. The game realized in any given context depends on the initial characteristics of the landscape, the value given to the objectives each township seeks to maximize, and the income distribution of the population.
Keywords: Agent-based modeling; game theory; Land-use policy; Local government cooperation; Scale interaction

Enhanced force measurement techniques to extend optical trapping towards nanoscale manipulation - Balijepalli,A.; LeBrun,T. W.; Gorman,J. J.; Gupta,S.K. (2009)
We have developed a new force measurement technique based on the random thermal motion of a nanoparticle in an optical trap. We demonstrate this method, in one-dimension, through numerical simulations and laboratory experiments. We show that computer simulations successfully recover the profile of the optical trapping force, beyond the inflection point of the trapping potential for a range of particle sizes. We show, through laboratory experiments, that this technique is effective in recovering higher order terms, in a power series expansion of the trapping force, beyond the widely reported linear trap stiffness. We also show that the first order (stiffness) term in our series expansion is consistent with values reported in the literature.
Keywords: Brownian motion; extend optical trapping; Fokker-Planck equation; force measurement; inflection point; linear trap stiffness; nanoparticle; nanoparticles; nanoscale manipulation; nanotechnology; optical trapping force; power series expansion; radiation pressure; random thermal motion

An evaluation of connection characteristics for separating network attacks - Berthier,Robin; Michel Cukier (International Journal of Security and Networks, 2009)
The goal of this paper is to evaluate the efficiency of connection characteristics to separate different attack families that target a single TCP port. Identifying the most relevant characteristics might allow statistically separating attack families without systematically using forensics. This study is based on a dataset collected over 117 days using a test-bed of two high interaction honeypots. The results indicated that to separate unsuccessful from successful attacks in malicious traffic: the number of bytes is a relevant characteristic; time-based characteristics are poor characteristics; using combinations of characteristics does not improve the efficiency of separating attacks.

Extreme polymorphism in a vaccine antigen and risk of clinical malaria: implications for vaccine development - Takala,S. L; Coulibaly,D.; Thera,M. A; Batchelor,A. H; Cummings, Michael P.; Escalante,A. A; Ouattara,A.; Traoré,K.; Niangaly,A.; Djimdé,A. A; Doumbo,OK; Plowe,CV (Sci Transl Med, 2009)
Vaccines directed against the blood stages of Plasmodium falciparum malaria are intended to prevent the parasite from invading and replicating within host cells. No blood-stage malaria vaccine has shown clinical efficacy in humans. Most malaria vaccine antigens are parasite surface proteins that have evolved extensive genetic diversity, and this diversity could allow malaria parasites to escape vaccine-induced immunity. We examined the extent and within-host dynamics of genetic diversity in the blood-stage malaria vaccine antigen apical membrane antigen-1 in a longitudinal study in Mali. Two hundred and fourteen unique apical membrane antigen-1 haplotypes were identified among 506 human infections, and amino acid changes near a putative invasion machinery binding site were strongly associated with the development of clinical symptoms, suggesting that these residues may be important to consider in designing polyvalent apical membrane antigen-1 vaccines and in assessing vaccine efficacy in field trials. This extreme diversity may pose a serious obstacle to an effective polyvalent recombinant subunit apical membrane antigen-1 vaccine.

Face Recognition from Video - Zhou,Shaohua Kevin; Chellapa, Rama; Aggarwal,Gaurav (The Essential Guide to Video Processing (Second Edition)The Essential Guide to Video Processing (Second Edition), 2009)

Fighting Spam with the NeighborhoodWatch DHT - Bender,A.; Sherwood,R.; Monner,D.; Goergen,N.; Spring, Neil; Bhattacharjee, Bobby (IEEE INFOCOM 2009, 2009)
In this paper, we present DHTBL, an anti-spam blacklist built upon a novel secure distributed hash table (DHT). We show how DHTBL can be used to replace existing DNS-based blacklists (DNSBLs) of IP addresses of mail relays that forward spam. Implementing a blacklist on a DHT improves resilience to DoS attacks and secures message delivery, when compared to DNSBLs. However, due to the sensitive nature of the blacklist, storing the data in a peer-to-peer DHT would invite attackers to infiltrate the system. Typical DHTs can withstand fail-stop failures, but malicious nodes may provide incorrect routing information, refuse to return published items, or simply ignore certain queries. The neighborhoodwatch DHT is resilient to malicious nodes and maintains the O(logiV) bounds on routing table size and expected lookup time. NeighborhoodWatch depends on two assumptions in order to make these guarantees: (1) the existence of an on-line trusted authority that periodically contacts and issues signed certificates to each node, and (2) for every sequence of k + 1 consecutive nodes in the ID space, at least one is alive and non-malicious. We show how NeighborhoodWatch maintains many of its security properties even when the second assumption is violated. Honest nodes in NeighborhoodWatch can detect malicious behavior and expel the responsible nodes from the DHT.
Keywords: Communications Society; computer crime; cryptography; Databases; IP addresses; IP networks; on-line trusted authority; Peer to peer computing; peer-to-peer computing; peer-to-peer distributed hash table; Postal services; Relays; Resilience; Routing; Security; table size routing; Unsolicited electronic mail

Finding Biologically Accurate Clusterings in Hierarchical Tree Decompositions Using the Variation of Information - Navlakha,Saket; White,James; Nagarajan,Niranjan; Pop, Mihai; Kingsford, Carl (Research in Computational Molecular Biology, 2009)
Hierarchical clustering is a popular method for grouping together similar elements based on a distance measure between them. In many cases, annotations for some elements are known beforehand, which can aid the clustering process. We present a novel approach for decomposing a hierarchical clustering into the clusters that optimally match a set of known annotations, as measured by the variation of information metric. Our approach is general and does not require the user to enter the number of clusters desired. We apply it to two biological domains: finding protein complexes within protein interaction networks and identifying species within metagenomic DNA samples. For these two applications, we test the quality of our clusters by using them to predict complex and species membership, respectively. We find that our approach generally outperforms the commonly used heuristic methods.

First Steps to Netviz Nirvana: Evaluating Social Network Analysis with NodeXL - Bonsignore,E. M; Dunne,C.; Rotman,D.; Smith,M.; Capone,T.; Hansen,D. L; Shneiderman, Ben (International Conference on Computational Science and Engineering, 2009. CSE '09, 2009)
Social Network Analysis (SNA) has evolved as a popular, standard method for modeling meaningful, often hidden structural relationships in communities. Existing SNA tools often involve extensive pre-processing or intensive programming skills that can challenge practitioners and students alike. NodeXL, an open-source template for Microsoft Excel, integrates a library of common network metrics and graph layout algorithms within the familiar spreadsheet format, offering a potentially low-barrier-to-entry framework for teaching and learning SNA. We present the preliminary findings of 2 user studies of 21 graduate students who engaged in SNA using NodeXL. The majority of students, while information professionals, had little technical background or experience with SNA techniques. Six of the participants had more technical backgrounds and were chosen specifically for their experience with graph drawing and information visualization. Our primary objectives were (1) to evaluate NodeXL as an SNA tool for a broad base of users and (2) to explore methods for teaching SNA. Our complementary dual case-study format demonstrates the usability of NodeXL for a diverse set of users, and significantly, the power of a tightly integrated metrics/visualization tool to spark insight and facilitate sense-making for students of SNA.
Keywords: Computer science; computer science education; data visualisation; Data visualization; Educational institutions; graph drawing; graph layout algorithm; Information services; Information Visualization; Internet; Libraries; Microsoft Excel open-source template; MILC; multi-dimensional in-depth long-term case studies; Netviz Nirvana; NodeXL; Open source software; Programming profession; SNA; social network analysis; Social network services; social networking (online); spreadsheet programs; structural relationship; teaching; visual analytics; visualization tool; Web sites

From New Zealand to Mongolia: Co-designing and deploying a digital library for the world's children - Druin, Allison; Bederson, Benjamin B.; Rose,A.; Weeks,A. (Special issue of Children, Youth and Environments: Children in Technological Environments: Interaction, Development, and Design, 2009)

Generating simplified trapping probability models from simulation of optical tweezers system - Banerjee,A. G.; Balijepalli,A.; Gupta,S.K.; LeBrun,T. W. (Journal of Computing and Information Science in Engineering, 2009)

Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains - Brettin,Thomas S[Los Alamos National Laboratory; Bruce,David C[Los Alamos National Laboratory; Challacombe,Jean F[Los Alamos National Laboratory; Detter,John C[Los Alamos National Laboratory; Han,Cliff S[Los Alamos National Laboratory; Munik,A. C[Los Alamos National Laboratory; Chertkov,Olga[Los Alamos National Laboratory; Meincke,Linda[Los Alamos National Laboratory; Saunders,Elizabeth[Los Alamos National Laboratory; Choi,Seon Y[SEOUL NATL UNIV; Haley,Bradd J[U MARYLAND; Taviani,Elisa[U MARYLAND; et al. (Nature, 2009)
Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a 'shift' between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a 'drift' between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.
Keywords: 59; CHOLERA; GENES; GENETICS; GENOTYPE; ISLANDS; ORIGIN; PHENOTYPE; PUBLIC HEALTH; RECOMBINATION; STRAINS; TOXINS

Hat guessing games - Butler,S.; Hajiaghayi, Mohammad T.; Kleinberg,R. D; Leighton,T. (SIAM review, 2009)

Identifying close friends on the internet - Baden,R.; Spring, Neil; Bhattacharjee, Bobby (Proc. of workshop on Hot Topics in Networks (HotNets-VIII), 2009)
Online Social Networks (OSNs) encourage users to createan online presence that reflects their offline identity. OSNs create the illusion that these online accounts correspond to the correct offline person, but in reality the OSN lacks the re- sources to detect impersonation. We propose that OSN users identify each other based on interaction and experience. We believe that impersonation can be thwarted by users who possess exclusive shared knowledge, secret informa- tion shared only between a pair of OSN friends. We describe existing protocols that use shared secrets to exchange public keys without revealing those secrets to attackers. We present results from a user study on Facebook to show that users do share exclusive knowledge with their Facebook friends and attackers are rarely able to guess that knowledge. Finally, we show that friend identification can be extended using a web of trust built on the OSN friend graph.

Improved approximation algorithms for prize-collecting Steiner tree and TSP - Archer,A.; Bateni,M. H; Hajiaghayi, Mohammad T.; Karloff,H. (2009 50th Annual IEEE Symposium on Foundations of Computer Science, 2009)

Improvement and analysis of computational methods for prediction of residual dipolar couplings - Berlin,Konstantin; O’Leary,Dianne P.; Fushman, David (Journal of Magnetic Resonance, 2009)
We describe a new, computationally efficient method for computing the molecular alignment tensor based on the molecular shape. The increase in speed is achieved by re-expressing the problem as one of numerical integration, rather than a simple uniform sampling (as in the PALES method), and by using a convex hull rather than a detailed representation of the surface of a molecule. This method is applicable to bicelles, PEG/hexanol, and other alignment media that can be modeled by steric restrictions introduced by a planar barrier. This method is used to further explore and compare various representations of protein shape by an equivalent ellipsoid. We also examine the accuracy of the alignment tensor and residual dipolar couplings (RDC) prediction using various ab initio methods. We separately quantify the inaccuracy in RDC prediction caused by the inaccuracy in the orientation and in the magnitude of the alignment tensor, concluding that orientation accuracy is much more important in accurate prediction of RDCs.
Keywords: Ab initio prediction; Alignment tensor; PALES; Residual dipolar coupling

Improving search effectiveness in the legal e-discovery process using relevance feedback - Zhao,F.C.; Oard, Douglas; Baron,J.R. (Proceedings of the global E-Discovery/E-Disclosure workshop on electronically stored information in discovery at the 12th international conference on artificial intelligence and law (ICAIL09 DESI Workshop). DESI Press, Barcelona, 2009)

In Situ Characterization and Modeling of Strains near Embedded Electronic Components During Processing and Break-in for Multifunctional Polymer Structures - Gershon,Alan L.; Gyger,Lawrence S.; Bruck,Hugh A.; Gupta, Satyandra K. (Advances in Mathematical Modeling and Experimental Methods for Materials and Structures, 2009)
Emerging molding concepts, such as in-mold assembly, are enabling electronic structures to be directly embedded in thermoplastic polymers to provide integrated packaging for better protection and a more multifunctional structure in “in-mold assembly processes”. During the molding process, stress can develop at the interface of the polymer and embedded electronic component due to shrinkage of the polymer that precipitates fracture or fatigue during the life cycle of the product. Additionally, the interaction between a mold and the polymer melt is altered in a multi-stage molding process where a polymer for superior impact protection can be molded over another polymer that is more compatible with the embedded electronic component. Currently, we do not fully understand the impact of various parameters governing the in-mold assembly process on the residual strains that develop in polymers around embedded electronic components in order to develop process models. Therefore, in this chapter experiments are presented that are designed and executed to measure the strains involved and the manner in which they develop. An in situ open mold experiment is employed using the full-field deformation technique of Digital Image Correlation (DIC) to characterize the displacement and corresponding strain fields that evolve near embedded electronic elements as the polymer shrinks from the molten to the solid state during processes and during break-in of the electronic component. It was determined that the use of multi-stage molding may reduce the residual stresses in addition to providing superior impact protection. However, there was a higher concentration of strain near the polymer-component interface during break-due to lower thermal conductivity. Experimental data was consistent with a thermomechanical model up until the point of failure.
Keywords: engineering

An Initial Characterization of Industrial Graphical User Interface Systems - Brooks,P.A.; Robinson,B.P.; Memon, Atif M. (Software Testing Verification and Validation, 2009. ICST '09. International Conference on, 2009)
To date we have developed and applied numerous model-based GUI testing techniques; however, we are unable to provide definitive improvement schemes to real-world GUI test planners, as our data was derived from open source applications, small compared to industrial systems. This paper presents a study of three industrial GUI-based software systems developed at ABB, including data on classified defects detected during late-phase testing and customer usage, test suites, and source code change metrics. The results show that (1) 50% of the defects found through the GUI are categorized as data access and handling, control flow and sequencing, correctness, and processing defects, (2) system crashes exposed defects 12-19% of the time, and (3) GUI and non-GUI components are constructed differently, in terms of source code metrics.
Keywords: Graphical user interfaces; GUI-based software systems; industrial graphical user interface systems; model-based GUI testing techniques; program testing; software metrics; source code change metrics

The Ins and Outs of Home Networking: The Case for Useful and Usable Domestic Networking - Grinter, Rebecca E.; Edwards, W. Keith; Marshini Chetty; Poole, Erika S.; Sung, Ja-Young; Yang, Jeonghwa; Crabtree, Andy; Tolmie, Peter; Rodden, Tom; Greenhalgh, Chris; Benford, Steve (ACM Trans. Comput.-Hum. Interact., 2009)
Householders are increasingly adopting home networking as a solution to the demands created by the presence of multiple computers, devices, and the desire to access the Internet. However, current network solutions are derived from the world of work (and initially the military) and provide poor support for the needs of the home. We present the key findings to emerge from empirical studies of home networks in the UK and US. The studies reveal two key kinds of work that effective home networking relies upon: one, the technical work of setting up and maintaining the home network, and the other, the collaborative and socially organized work of the home which the network is embedded in and supports. The two are thoroughly intertwined and rely upon one another for their realization, yet neither is adequately supported by current networking technologies and applications. Explication of the “work to make the home network work” opens up the design space for the continued integration of the home network in domestic life and elaboration of future support. Key issues for development include the development of networking facilities that do not require advanced networking knowledge, that are flexible and support the local social order of the home and the evolution of its routines, and which ultimately make the home network visible and accountable to household members.
Keywords: home networking; Human computer interaction

Integrated product and process design for a flapping wing drive mechanism - Bejgerowski,W.; Ananthanarayanan,A.; Mueller,D.; Gupta,S.K. (Journal of Mechanical Design, 2009)

Interacting with eHealth: towards grand challenges for HCI - André,P.; White,R.; Tan,D.; Berners-Lee,T.; Consolvo,S.; Jacobs,R.; Kohane,I.; Le Dantec,C.A.; Mamykina,L.; Marsden,G. (Proceedings of the 27th international conference extended abstracts on Human factors in computing systems, 2009)
While health records are increasingly stored electronically, we, as citizens, have little access to this data about ourselves. We are not used to thinking of these official records either as ours or as useful to us. We increasingly turn to the Web, however, to query any ache, pain or health goal we may have before consulting with health care professionals. Likewise, for proactive health care such as nutrition or fitness, or to find fellow-sufferers for post diagnosis support, we turn to online resources. There is a potential disconnect between points at which professional and lay eHealth data and resources intersect for preventative or proactive health care. Such gaps in information sharing may have direct impact on practices we decide to take up, the care we seek, or the support professionals offer. In this panel, we consider several places within proactive, preventative health care in particular HCI has a role towards enhancing health knowledge discovery and health support interaction. Our goal is to demonstrate how now is the time for eHealth to come to the forefront of the HCI research agenda.

Interlingual annotation of multilingual text corpora and FrameNet - Farwell,David; Dorr, Bonnie J; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Green,Rebecca; Levin,Lori; Miller,Keith; Mitamura,Teruko; Rambow,Owen; Reeder,Flo; Siddharthan,Advaith (Multilingual FrameNets in Computational LexicographyMultilingual FrameNets in Computational Lexicography, 2009)

Introducing a test suite similarity metric for event sequence-based test cases - Brooks,P.A.; Memon, Atif M. (Software Maintenance, 2009. ICSM 2009. IEEE International Conference on, 2009)
Most of today's event driven software (EDS) systems are tested using test cases that are carefully constructed as sequences of events; they test the execution of an event in the context of its preceding events. Because sizes of these test suites can be extremely large, researchers have developed techniques, such as reduction and minimization, to obtain test suites that are ldquosimilarrdquo to the original test suite, but smaller. Existing similarity metrics mostly use code coverage; they do not consider the contextual relationships between events. Consequently, reduction based on such metrics may eliminate desirable test cases. In this paper, we present a new parameterized metric, CONTeSSi(n) which uses the context of n preceding events in test cases to develop a new context-aware notion of test suite similarity for EDS. This metric is defined and evaluated by comparing four test suites for each of four open source applications. Our results show that CONT eSSi(n) is a better indicator of the similarity of EDS test suites than existing metrics.
Keywords: event driven software systems; event sequence-based test cases; open source systems; program testing; public domain software; software metrics; Software testing; test suite similarity metric

It's Not Easy Being Green: Understanding Home Computer Power Management - Marshini Chetty; Brush, A.J. Bernheim; Meyers, Brian R.; Johns, Paul (SIGCHI '09, 2009)
Although domestic computer use is increasing, most efforts to reduce energy use through improved power management have focused on computers in the workplace. We studied 20 households to understand how people use power management strategies on their home computers. We saw computers in the home, particularly desktop computers, are left on much more than they are actively used suggesting opportunities for economic and energy savings. However, for most of our participants, the economic incentives were too minor to motivate them to turn off devices when not in use, especially given other frustrations such as long boot up times. We suggest research directions for home computer power management that could help users be more green without having to dramatically change their home computing habits.
Keywords: home computer use; power management; Sustainability

Link-based active learning - Bilgic,M.; Getoor, Lise (NIPS Workshop on Analyzing Networks and Learning with Graphs, 2009)
Supervised and semi-supervised data mining techniques require labeled data.However, labeling examples is costly for many real-world applications. To ad- dress this problem, active learning techniques have been developed to guide the labeling process in an effort to minimize the amount of labeled data without sac- rificing much from the quality of the learned models. Yet, most of the active learning methods to date have remained relatively agnostic to the rich structure offered by network data, often ignoring the relationships between the nodes of a network. On the other hand, the relational learning community has shown that the relationships can be very informative for various prediction tasks. In this paper, we propose different ways of adapting existing active learning work to network data while utilizing links to select better examples to label.

Locality bounds on hamiltonians for stabilizer codes - Bullock,Stephen S.; O'Leary, Dianne P. (Quantum Info. Comput., 2009)
In this paper, we study the complexity of Hamiltonians whose groundstate is a stabilizer code. Weintroduce various notions of k-locality of a stabilizer code, inherited from the associated stabilizergroup. A choice of generators leads to a Hamiltonian with the code in its groundspace. We establishbounds on the locality of any other Hamiltonian whose groundspace contains such a code, whetheror not its Pauli tensor summands commute. Our results provide insight into the cost of creating anenergy gap for passive error correction and for adiabatic quantum computing. The results simplify inthe cases of XZ-split codes such as Calderbank-Shor-Steane stabilizer codes and topologically-orderedstabilizer codes arising from surface cellulations.

Maturing Software Engineering Knowledge through Classifications: A Case Study on Unit Testing Techniques - Vegas,S.; Juristo,N.; Basili, Victor R. (Software Engineering, IEEE Transactions on, 2009)
Classification makes a significant contribution to advancing knowledge in both science and engineering. It is a way of investigating the relationships between the objects to be classified and identifies gaps in knowledge. Classification in engineering also has a practical application; it supports object selection. They can help mature software engineering knowledge, as classifications constitute an organized structure of knowledge items. Till date, there have been few attempts at classifying in software engineering. In this research, we examine how useful classifications in software engineering are for advancing knowledge by trying to classify testing techniques. The paper presents a preliminary classification of a set of unit testing techniques. To obtain this classification, we enacted a generic process for developing useful software engineering classifications. The proposed classification has been proven useful for maturing knowledge about testing techniques, and therefore, SE, as it helps to: 1) provide a systematic description of the techniques, 2) understand testing techniques by studying the relationships among techniques (measured in terms of differences and similarities), 3) identify potentially useful techniques that do not yet exist by analyzing gaps in the classification, and 4) support practitioners in testing technique selection by matching technique characteristics to project characteristics.
Keywords: characteristic; project; characteristic; software; classification; matching; engineering; engineering; knowledge; software; technique; techniques; program; Testing; testing; software; testing; unit

MEASURING 1ST ORDER STRETCH WITH A SINGLE FILTER - Bitsakos,K.; Domke, J.; Fermüller, Cornelia; Aloimonos, J. (Relation, 2009)
We analytically develop a filter that is able to measurethe linear stretch of the transformation around a point, and present results of applying it to real signals. We show that this method is a real-time alternative solution for measuring local signal transformations. Experimentally, this method can accurately measure stretch, however, it is sensitive to shift.

Measuring differential gene expression by short read sequencing: quantitative comparison to 2-channel gene expression microarrays - Bloom, Joshua S.; Zia Khan; Kruglyak, Leonid; Singh, Mona; Caudy, Amy A. (BMC Genomics, 2009)
Background High-throughput cDNA synthesis and sequencing of poly(A)-enriched RNA is rapidly emerging as a technology competing to replace microarrays as a quantitative platform for measuring gene expression. Results Consequently, we compared full length cDNA sequencing to 2-channel gene expression microarrays in the context of measuring differential gene expression. Because of its comparable cost to a gene expression microarray, our study focused on the data obtainable from a single lane of an Illumina 1 G sequencer. We compared sequencing data to a highly replicated microarray experiment profiling two divergent strains of S. cerevisiae. Conclusion Using a large number of quantitative PCR (qPCR) assays, more than previous studies, we found that neither technology is decisively better at measuring differential gene expression. Further, we report sequencing results from a diploid hybrid of two strains of S. cerevisiae that indicate full length cDNA sequencing can discover heterozygosity and measure quantitative allele-specific expression simultaneously.
Keywords: Animal Genetics and Genomics; Life Sciences, general; Microarrays; Microbial Genetics and Genomics; Plant Genetics & Genomics; proteomics

Mesh-of-Trees and Alternative Interconnection Networks for Single-Chip Parallelism - Balkan,A.O.; Gang Qu; Vishkin, Uzi (Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2009)
In single-chip parallel processors, it is crucial to implement a high-throughput low-latency interconnection network to connect the on-chip components, especially the processing units and the memory units. In this paper, we propose a new mesh of trees (MoT) implementation of the interconnection network and evaluate it relative to metrics such as wire complexity, total register count, single switch delay, maximum throughput, tradeoffs between throughput and latency, and post-layout performance. We show that on-chip interconnection networks can provide higher bandwidth between processors and shared first-level cache than previously considered possible, facilitating greater scalability of memory architectures that require that. MoT is also compared, both analytically and experimentally, to some other traditional network topologies, such as hypercube, butterfly, fat trees and butterfly fat trees. When we evaluate a 64-terminal MoT network at 90-nm technology, concrete results show that MoT provides higher throughput and lower latency especially when the input traffic (or the on-chip parallelism) is high, at comparable area. A recurring problem in networking and communication is that of achieving good sustained throughput in contrast to just high theoretical peak performance that does not materialize for typical work loads. Our quantitative results demonstrate a clear advantage of the proposed MoT network in the context of single-chip parallel processing.
Keywords: 90; cache; single; complexity; multiprocessor; delay; single-chip; first-level; high-throughput; interconnection; low-latency; network; memory; network; shared; networks; network-on-chip; parallel; nm; wire; Parallel; parallelism; size; processing; processor; single-chip; switch; topologies; on-chip; units; mesh-of-trees; network

Microbial oceanography in a sea of opportunity - Bowler,Chris; Karl,David M.; Rita R Colwell (Nature, 2009)
Plankton use solar energy to drive the nutrient cycles that make the planet habitable for larger organisms. We can now explore the diversity and functions of plankton using genomics, revealing the gene repertoires associated with survival in the oceans. Such studies will help us to appreciate the sensitivity of ocean systems and of the ocean's response to climate change, improving the predictive power of climate models.
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

Modeling and Testing of Ethernet Transformers - Bowen,D.; Mayergoyz, Issak D; Zhang,Zhenyu; McAvoy,P.; Krafft,C.; Kroop,D. (Magnetics, IEEE Transactions on, 2009)
In this paper, novel techniques for the testing and identification of lumped parameters of equivalent circuits for Ethernet transformers are presented. It is demonstrated experimentally and theoretically that resonance phenomena may occur in the loop formed by leakage inductances and cross-winding capacitance. This resonance may corrupt the pass band of the transformers transfer characteristic for differential-mode signals.
Keywords: area; capacitance; differential-mode; characteristic; local; Ethernet; identification; lumped; inductances; lumped; networks; transformers; PARAMETERS; phenomena; transformers; signals; leakage; testing; resonance; transfer; transformers; cross-winding

Motifs and cis-regulatory modules mediating the expression of genes co-expressed in presynaptic neurons - Liu,Rui; Hannenhalli, Sridhar; Bucan,Maja (Genome Biology, 2009)
Hundreds of proteins modulate neurotransmitter release and synaptic plasticity during neuronal development and in response to synaptic activity. The expression of genes in the pre- and post-synaptic neurons is under stringent spatio-temporal control, but the mechanism underlying the neuronal expression of these genes remains largely unknown.

Multilingual topic models for unaligned text - Jordan Boyd-Graber; Blei,David M. (Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, 2009)
We develop the multilingual topic model for unaligned text (MuTo), a probabilistic model of text that is designed to analyze corpora composed of documents in two languages. From these documents, MuTo uses stochastic EM to simultaneously discover both a matching between the languages and multilingual latent topics. We demonstrate that MuTo is able to find shared topics on real-world multilingual corpora, successfully pairing related documents across languages. MuTo provides a new framework for creating multilingual topic models without needing carefully curated parallel corpora and allows applications built using the topic model formalism to be applied to a much wider class of corpora.

New records of phytoplankton for Bangladesh. 9. Some rare and a new species - Khondker,Moniruzzaman; Bhuiyan,Rauf Ahmed; Yeasmin,Jenat; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Bangladesh Journal of Plant Taxonomy, 2009)
Ten taxa belonging to Chlorophyceae, Cyanophyceae, Bacillariophyceae and Euglenophyceae, and one with an uncertain taxonomic position have been described in this paper. Of these, 10 taxa have been found to be globally rare and new records for Bangladesh, whereas Strombomonas islamii Khondker sp. nov. has been described as new to science.

Nonlinear Resonant and Chaotic Dynamics in Microwave Assisted Magnetization Switching - d'Aquino,M.; Serpico,C.; Bertotti,G.; Mayergoyz, Issak D; Bonin,R. (Magnetics, IEEE Transactions on, 2009)
The switching process of a uniformly magnetized magnetic nanoparticle is considered. The particle is subject to applied fields having both dc and linearly-polarized radio-frequency (RF) components. The possibility of using the RF power to obtain a reduced coercivity of the particle is related to the onset of chaotic magnetization dynamics for moderately low values of the RF field amplitude. Perturbation technique for the evaluation of the reduced coercive field is developed and applied to the microwave assisted switching of the particle. Numerical simulations confirm the predictions of the theory.
Keywords: amplitude; chaotic; components; magnetic; dynamical; dynamics; coercive; dynamics; numerical; field; field; coercivity; linearly-polarized; force; magnetic; magnetization; nanoparticle; microwave-assisted; particles; magnetic; radiofrequency; resonant; RF; simulations; perturbation; switching; nanoparticles; nonlinear; switching; nonlinear; systems; perturbation; technique; chaos; coercive; theory

An oscillatory hebbian network model of short-term memory - Winder,R. K; Reggia, James A.; Weems,S. A; Bunting,M. F (Neural computation, 2009)

Participatory simulation as a tool for agent-based simulation - Berland,M.; Rand, William (Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART-09), 2009)
Participatory simulation, as described by Wilensky & Stroup (1999c), is a form of agent-based simulation inwhich multiple humans control or design individual agents in the simulation. For instance, in a participatory simulation of an ecosystem, fifty participants might each control the intake and output of one agent, such that the food web emerges from the interactions of the human-controlled agents. We argue that participatory simulation has been under-utilized outside of strictly educational contexts, and that it provides myriad benefits to designers of traditional agent-based simulations. These benefits include increased robustness of the model, increased comprehensibility of the findings, and simpler design of individual agent behaviors. To make this argument, we look to recent research such as that from crowdsourcing (von Ahn, 2005) and the reinforcement learning of autonomous agent behavior (Abbeel, 2008).

Persona: an online social network with user-defined privacy - Baden,Randy; Bender,Adam; Spring, Neil; Bhattacharjee, Bobby; Starin,Daniel (Proceedings of the ACM SIGCOMM 2009 conference on Data communication, 2009)
Online social networks (OSNs) are immensely popular, with some claiming over 200 million users. Users share private content, such as personal information or photographs, using OSN applications. Users must trust the OSN service to protect personal information even as the OSN provider benefits from examining and sharing that information. We present Persona, an OSN where users dictate who may access their information. Persona hides user data with attribute-based encryption (ABE), allowing users to apply fine-grained policies over who may view their data. Persona provides an effective means of creating applications in which users, not the OSN, define policy over access to private data. We demonstrate new cryptographic mechanisms that enhance the general applicability of ABE. We show how Persona provides the functionality of existing online social networks with additional privacy benefits. We describe an implementation of Persona that replicates Facebook applications and show that Persona provides acceptable performance when browsing privacy-enhanced web pages, even on mobile devices.
Keywords: ABE; Facebook; OSN; persona; privacy; social networks

Persona : An Online Social Network with User-Defined Privacy Categories and Subject Descriptors - Starin,Daniel; Baden,Randy; Bender,Adam; Spring, Neil; Bhattacharjee, Bobby (Computer, 2009)
Online social networks (OSNs) are immensely popular, with some claiming over 200 million users. Users share private content, such as personal information or photographs, using OSN applications. Users must trust the OSN service to protect personal information even as the OSN provider benefits from examining and sharing that information. We present Persona, an OSN where users dictate who may access their information. Persona hides user data with attribute-based encryption (ABE), allowing users to apply fine-grained policies over who may view their data. Persona provides an effective means of creating applications in which users, not the OSN, define policy over access to private data. We demonstrate new cryptographic mechanisms that enhance the general applicability of ABE. We show how Persona provides the functionality of existing online social networks with additional privacy benefits. We describe an implementation of Persona that replicates Facebook applications and show that Persona provides acceptable performance when browsing privacy-enhanced web pages, even on mobile devices.

A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays - Zia Khan; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (Bioinformatics, 2009)
Motivation: High-throughput sequencing technologies place ever increasing demands on existing algorithms for sequence analysis. Algorithms for computing maximal exact matches (MEMs) between sequences appear in two contexts where high-throughput sequencing will vastly increase the volume of sequence data: (i) seeding alignments of high-throughput reads for genome assembly and (ii) designating anchor points for genome–genome comparisons.Results: We introduce a new algorithm for finding MEMs. The algorithm leverages a sparse suffix array (SA), a text index that stores every K-th position of the text. In contrast to a full text index that stores every position of the text, a sparse SA occupies much less memory. Even though we use a sparse index, the output of our algorithm is the same as a full text index algorithm as long as the space between the indexed suffixes is not greater than a minimum length of a MEM. By relying on partial matches and additional text scanning between indexed positions, the algorithm trades memory for extra computation. The reduced memory usage makes it possible to determine MEMs between significantly longer sequences. Availability: Source code for the algorithm is available under a BSD open source license at http://compbio.cs.princeton.edu/mems. The implementation can serve as a drop-in replacement for the MEMs algorithm in MUMmer 3. Contact: zkhan@cs.princeton.edu;mona@cs.princeton.edu Supplementary information: Supplementary data are available at Bioinformatics online.

Predicting the distribution of Vibrio spp. in the Chesapeake Bay: a Vibrio cholerae case study - Constantin de Magny,G.; Long,W.; Brown,C. W.; Hood,R. R.; Huq,A.; Murtugudde,R.; Rita R Colwell (EcoHealth, 2009)
Vibrio cholerae, the causative agent of cholera, is a naturally occurring inhabitant of the Chesapeake Bay and serves as a predictor for other clinically important vibrios, including Vibrio parahaemolyticus and Vibrio vulnificus. A system was constructed to predict the likelihood of the presence of V. cholerae in surface waters of the Chesapeake Bay, with the goal to provide forecasts of the occurrence of this and related pathogenic Vibrio spp. Prediction was achieved by driving an available multivariate empirical habitat model estimating the probability of V. cholerae within a range of temperatures and salinities in the Bay, with hydrodynamically generated predictions of ambient temperature and salinity. The experimental predictions provided both an improved understanding of the in situ variability of V. cholerae, including identification of potential hotspots of occurrence, and usefulness as an early warning system. With further development of the system, prediction of the probability of the occurrence of related pathogenic vibrios in the Chesapeake Bay, notably V. parahaemolyticus and V. vulnificus, will be possible, as well as its transport to any geographical location where sufficient relevant data are available.

Protein quantification across hundreds of experimental conditions - Zia Khan; Bloom, Joshua S.; Garcia, Benjamin A.; Singh, Mona; Kruglyak, Leonid (Proceedings of the National Academy of Sciences, 2009)
Quantitative studies of protein abundance rarely span more than a small number of experimental conditions and replicates. In contrast, quantitative studies of transcript abundance often span hundreds of experimental conditions and replicates. This situation exists, in part, because extracting quantitative data from large proteomics datasets is significantly more difficult than reading quantitative data from a gene expression microarray. To address this problem, we introduce two algorithmic advances in the processing of quantitative proteomics data. First, we use space-partitioning data structures to handle the large size of these datasets. Second, we introduce techniques that combine graph-theoretic algorithms with space-partitioning data structures to collect relative protein abundance data across hundreds of experimental conditions and replicates. We validate these algorithmic techniques by analyzing several datasets and computing both internal and external measures of quantification accuracy. We demonstrate the scalability of these techniques by applying them to a large dataset that comprises a total of 472 experimental conditions and replicates.
Keywords: kd-tree; orthogonal range query; quantitative proteomics; space partitioning data structures; tandem mass spectrometry

Reading tea leaves: How humans interpret topic models - Chang,J.; Jordan Boyd-Graber; Gerrish,S.; Wang,C.; Blei,D.M. (Proceedings of the 23rd Annual Conference on Neural Information Processing Systems, 2009)
Probabilistic topic models are a popular tool for the unsupervised analysis of text, providing both a predictive model of future text and a latent topic representation of the corpus. Practitioners typically assume that the latent space is semantically meaningful. It is used to check models, summarize the corpus, and guide explo- ration of its contents. However, whether the latent space is interpretable is in need of quantitative evaluation. In this paper, we present new quantitative methods for measuring semantic meaning in inferred topics. We back these measures with large-scale user studies, showing that they capture aspects of the model that are undetected by previous measures of model quality based on held-out likelihood. Surprisingly, topic models which perform better on held-out likelihood may infer less semantically meaningful topics.

Real-time shape retrieval for robotics using skip Tri-Grams - Li,Yi; Bitsakos,K.; Fermüller, Cornelia; Aloimonos, J. (IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009. IROS 2009, 2009)
The real time requirement is an additional constraint on many intelligent applications in robotics, such as shape recognition and retrieval using a mobile robot platform. In this paper, we present a scalable approach for efficiently retrieving closed contour shapes. The contour of an object is represented by piecewise linear segments. A skip Tri-Gram is obtained by selecting three segments in the clockwise order while allowing a constant number of segments to be ÃÂ¿skippedÃÂ¿ in between. The main idea is to use skip Tri-Grams of the segments to implicitly encode the distant dependency of the shape. All skip Tri-Grams are used for efficiently retrieving closed contour shapes without pairwise matching feature points from two shapes. The retrieval is at least an order of magnitude faster than other state-of-the-art algorithms. We score 80% in the Bullseye retrieval test on the whole MPEG 7 shape dataset. We further test the algorithm using a mobile robot platform in an indoor environment. 8 objects are used for testing from different viewing directions, and we achieve 82% accuracy.
Keywords: Bullseye retrieval test; Clocks; closed contour shape retrieval; Image retrieval; Image segmentation; Indexing; Information retrieval; Intelligent robots; Jacobian matrices; mobile robot; Mobile robots; MPEG 7 shape dataset; piecewise linear segments; Piecewise linear techniques; Real time systems; real-time shape retrieval; robot vision; SHAPE; shape recognition; shape representation; skip Tri-Grams; Testing

Reflect and correct: A misclassification prediction approach to active inference - Bilgic,Mustafa; Getoor, Lise (ACM Transactions on Knowledge Discovery from Data (TKDD), 2009)
Information diffusion, viral marketing, graph-based semi-supervised learning, and collective classification all attempt to model and exploit the relationships among nodes in a network to improve the performance of node labeling algorithms. However, sometimes the advantage of exploiting the relationships can become a disadvantage. Simple models like label propagation and iterative classification can aggravate a misclassification by propagating mistakes in the network, while more complex models that define and optimize a global objective function, such as Markov random fields and graph mincuts, can misclassify a set of nodes jointly. This problem can be mitigated if the classification system is allowed to ask for the correct labels for a few of the nodes during inference. However, determining the optimal set of labels to acquire is intractable under relatively general assumptions, which forces us to resort to approximate and heuristic techniques. We describe three such techniques in this article. The first one is based on directly approximating the value of the objective function of label acquisition and greedily acquiring the label that provides the most improvement. The second technique is a simple technique based on the analogy we draw between viral marketing and label acquisition. Finally, we propose a method, which we refer to as reflect and correct, that can learn and predict when the classification system is likely to make mistakes and suggests acquisitions to correct those mistakes. We empirically show on a variety of synthetic and real-world datasets that the reflect and correct method significantly outperforms the other two techniques, as well as other approaches based on network structural measures such as node degree and network clustering.
Keywords: active inference; collective classification; information diffusion; label acquisition; viral marketing

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

Robust Estimation of Albedo for Illumination-Invariant Matching and Shape Recovery - Biswas,S.; Aggarwal,G.; Chellapa, Rama (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2009)
We present a nonstationary stochastic filtering framework for the task of albedo estimation from a single image. There are several approaches in the literature for albedo estimation, but few include the errors in estimates of surface normals and light source direction to improve the albedo estimate. The proposed approach effectively utilizes the error statistics of surface normals and illumination direction for robust estimation of albedo, for images illuminated by single and multiple light sources. The albedo estimate obtained is subsequently used to generate albedo-free normalized images for recovering the shape of an object. Traditional shape-from-shading (SFS) approaches often assume constant/piecewise constant albedo and known light source direction to recover the underlying shape. Using the estimated albedo, the general problem of estimating the shape of an object with varying albedo map and unknown illumination source is reduced to one that can be handled by traditional SFS approaches. Experimental results are provided to show the effectiveness of the approach and its application to illumination-invariant matching and shape recovery. The estimated albedo maps are compared with the ground truth. The maps are used as illumination-invariant signatures for the task of face recognition across illumination variations. The recognition results obtained compare well with the current state-of-the-art approaches. Impressive shape recovery results are obtained using images downloaded from the Web with little control over imaging conditions. The recovered shapes are also used to synthesize novel views under novel illumination conditions.
Keywords: albedo estimation; error statistics; face recognition; illumination-invariant matching; nonstationary stochastic filtering; robust estimation; shape recovery; shape-from-shading approach; error statistics; face recognition; filtering theory; image matching; Algorithm; Automated; Photometry; Reproducibility of Results; Sensitivity and Specificity; Computer-Assisted; Imaging; Three-Dimensional; Lighting; Pattern Recognition

Running memory span: A comparison of behavioral capacity limits with those of an attractor neural network - Weems,Scott A.; Winder,Ransom K.; Bunting,Michael; Reggia, James A. (Cognitive Systems Research, 2009)
We studied a computational model of short term memory capacity that performs a simulated running memory span task using Hebbian learning and rapid decay of connection strengths to keep recent items active for later recall. This model demonstrates recall performance similar to humans performing the same task, with a capacity limit of approximately three items and a prominent recency effect. The model also shows that this capacity depends on decay to release the model from accumulating interference. Model findings are compared with data from two behavioral experiments that used varying task demands to tax memory capacity limits. Following additional theoretical predictions from the computational model, behavioral data support that when task demands require attention to be spread too thin to keep items available for later recall, capacity limits suffer. These findings are important both for understanding the mechanisms underlying short term memory capacity, and also to memory researchers interested in the role of attention in capacity limitations.
Keywords: Attractor neural network; Computational model; Running span; Short term memory; Working memory capacity

Salient Clustering for View-dependent Multiresolution Rendering - Barni,R.; Comba,J.; Varshney, Amitabh (Computer Graphics and Image Processing (SIBGRAPI), 2009 XXII Brazilian Symposium on, 2009)
Perceptual information is quickly gaining importance in mesh representation, analysis and rendering. User studies, eye tracking and other techniques are able to provide ever more useful insights for many user-centric systems, which form the bulk of computer graphics applications. In this work we build upon the concept of Mesh Saliency - an automatic measure of visual importance for triangle meshes based on models of low-level human visual attention - applying it to the problem of mesh segmentation and view-dependent rendering. We introduce a technique for segmentation that partitions an object into a set of face clusters, each encompassing a group of locally interesting features; Mesh Saliency is incorporated in a propagative mesh clustering framework, guiding cluster seed selection and triangle propagation costs and leading to a convergence of face clusters around perceptually important features. We compare our technique with different fully automatic segmentation algorithms, showing that it provides similar or better segmentation without the need for user input. We illustrate application of our clustering results through a saliency-guided view-dependent rendering system, achieving significant frame rate increases with little loss of visual detail.
Keywords: (computer; algorithms; cluster; analysis; mesh; attention; mesh; AUTOMATIC; centred; clustering; clustering; rendering; clustering; user-centric; clusters; low-level; dependent; design; framework; salient; graphics); user; graphics; face; human; information; propagative; mesh; multiresolution; rendering; image; representation; mesh; resolution; image; saliency; mesh; seed; segmentation; segmentation; pattern; segmentation; perceptual; selection; computer; system; view; visual

Scheduling to minimize staleness and stretch in real-time data warehouses - Bateni,M. H; Golab,L.; Hajiaghayi, Mohammad T.; Karloff,H. (Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, 2009)

Scope error detection and handling concerning software estimation models - Sarcia,Salvatore Alessandro; Basili, Victor R.; Cantone,Giovanni (Proceedings of the 2009 3rd International Symposium on Empirical Software Engineering and Measurement, 2009)
Over the last 25+ years, the software community has been searching for the best models for estimating variables of interest (e.g., cost, defects, and fault proneness). However, little research has been done to improve the reliability of the estimates. Over the last decades, scope error and error analysis have been substantially ignored by the community. This work attempts to fill this gap in the research and enhance a common understanding within the community. Results provided in this study can eventually be used to support human judgment-based techniques and be an addition to the portfolio. The novelty of this work is that, we provide a way of detecting and handling the scope error arising from estimation models. The answer whether or not scope error will occur is a pre-condition to safe use of an estimation model. We also provide a handy procedure for dealing with outliers as to whether or not to include them in the training set for building a new version of the estimation model. The majority of the work is empirically based, applying computational intelligence techniques to some COCOMO model variations with respect to a publicly available cost estimation data set in the PROMISE repository.

Semantically informed machine translation (SIMT) - Baker,K.; Bethard,S.; Bloodgood,M.; Brown,R.; Callison-Burch,C.; Coppersmith,G.; Dorr, Bonnie J; Filardo,W.; Giles,K.; Irvine,A.; others (SCALE summer workshop final report, Human Language Technology Center Of Excellence, 2009)

Serogroup, Virulence, and Genetic Traits of Vibrio Parahaemolyticus in the Estuarine Ecosystem of Bangladesh - Alam,Munirul; Chowdhury,Wasimul B.; Bhuiyan,N. A.; Islam,Atiqul; Hasan,Nur A.; Nair,G. Balakrish; Watanabe,H.; Siddique,A. K.; Huq,Anwar; Sack,R. Bradley; Akhter,M. Z.; Grim,Christopher J.; et al. (Applied and Environmental MicrobiologyAppl. Environ. Microbiol., 2009)
Forty-two strains of Vibrio parahaemolyticus were isolated from Bay of Bengal estuaries and, with two clinical strains, analyzed for virulence, phenotypic, and molecular traits. Serological analysis indicated O8, O3, O1, and K21 to be the major O and K serogroups, respectively, and O8:K21, O1:KUT, and O3:KUT to be predominant. The K antigen(s) was untypeable, and pandemic serogroup O3:K6 was not detected. The presence of genes toxR and tlh were confirmed by PCR in all but two strains, which also lacked toxR. A total of 18 (41%) strains possessed the virulence gene encoding thermostable direct hemolysin (TDH), and one had the TDH-related hemolysin (trh) gene, but not tdh. Ten (23%) strains exhibited Kanagawa phenomenon that surrogates virulence, of which six, including the two clinical strains, possessed tdh. Of the 18 tdh-positive strains, 17 (94%), including the two clinical strains, had the seromarker O8:K21, one was O9:KUT, and the single trh-positive strain was O1:KUT. None had the group-specific or ORF8 pandemic marker gene. DNA fingerprinting employing pulsed-field gel electrophoresis (PFGE) of SfiI-digested DNA and cluster analysis showed divergence among the strains. Dendrograms constructed using PFGE (SfiI) images from a soft database, including those of pandemic and nonpandemic strains of diverse geographic origin, however, showed that local strains formed a cluster, i.e., “clonal cluster,” as did pandemic strains of diverse origin. The demonstrated prevalence of tdh-positive and diarrheagenic serogroup O8:K21 strains in coastal villages of Bangladesh indicates a significant human health risk for inhabitants.

Signing a linear subspace: Signature schemes for network coding - Boneh,D.; Freeman,D.; Katz, Jonathan; Waters,B. (Public Key Cryptography–PKC 2009, 2009)
Network coding offers increased throughput and improved robustness to random faults in completely decentralized networks. In contrast to traditional routing schemes, however, network coding requires intermediate nodes to modify data packets en route; for this reason, standard signature schemes are inapplicable and it is a challenge to provide resilience to tampering by malicious nodes.We propose two signature schemes that can be used in conjunction with network coding to prevent malicious modification of data. Our schemes can be viewed as signing linear subspaces in the sense that a signature σ on a subspace V authenticates exactly those vectors in V. Our first scheme is (suitably) homomorphic and has constant public-key size and per-packet overhead. Our second scheme does not rely on random oracles and is based on weaker assumptions. We also prove a lower bound on the length of signatures for linear subspaces showing that our schemes are essentially optimal in this regard.

Speaking through pictures: images vs. icons - Ma,Xiaojuan; Jordan Boyd-Graber; Nikolova,Sonya; Cook,Perry R. (Proceedings of the 11th international ACM SIGACCESS conference on Computers and accessibility, 2009)
People with aphasia, a condition that impairs the ability to understand or generate written or spoken language, are aided by assistive technology that helps them communicate through a vocabulary of icons. These systems are akin to language translation systems, translating icon arrangements into spoken or written language and vice versa. However, these icon-based systems have little vocabulary breadth or depth, making it difficult for people with aphasia to apply their usage to multiple real world situations. Pictures from the web are numerous, varied, and easily accessible and thus, could potentially address the small size issues of icon-based systems. We present results from two studies that investigate this potential and demonstrate that images can be as effective as icons when used as a replacement for English language communication. The first study uses elderly subjects to investigate the efficacy of images vs. icons in conveying word meaning; the second study examines the retention of word-level meaning by both images and icons with a population of aphasics. We conclude that images collected from the web are as functional as icons in conveying information and thus, are feasible to use in assistive technology that supports people with aphasia.
Keywords: aphasia; computerized visual communication (C-VIC); visual communication (VIC)

A survey of CAD model simplification techniques for physics-based simulation applications - Thakur,Atul; Banerjee,Ashis Gopal; Gupta, Satyandra K. (Computer-Aided Design, 2009)
Automated CAD model simplification plays an important role in effectively utilizing physics-based simulation during the product realization process. Currently a rich body of literature exists that describe many successful techniques for fully-automatic or semi-automatic simplification of CAD models for a wide variety of applications. The purpose of this paper is to compile a list of the techniques that are relevant for physics-based simulations problems and to characterize them based on their attributes. We have classified them into the following four categories: techniques based on surface entity based operators, volume entity based operators, explicit feature based operators, and dimension reduction operators. This paper also presents the necessary background information in the CAD model representation to assist the new readers. We conclude the paper by outlining open research directions in this field.
Keywords: CAD model simplification; Physics-based simulation

Symbiotic relationships in internet routing overlays - Lumezanu,Cristian; Baden,Randy; Levin,Dave; Spring, Neil; Bhattacharjee, Bobby (Proceedings of the 6th USENIX symposium on Networked systems design and implementation, 2009)
We propose to construct routing overlay networks using the following principle: that overlay edges should be based on mutual advantage between pairs of hosts. Upon this principle, we design, implement, and evaluate Peer-Wise, a latency-reducing overlay network. To show the feasibility of PeerWise, we must show first that mutual advantage exists in the Internet: perhaps contrary to expectation, that there are not only "haves" and "have nots" of low-latency connectivity. Second, we must provide a scalable means of finding promising edges and overlay routes; we seek embedding error in network coordinates to expose both shorter-than-default "detour" routes and longer-than-expected default routes. We evaluate the cost of limiting PeerWise to mutually advantageous links, then build the intelligent components that put PeerWise into practice. We design and evaluate "virtual" network coordinates for destinations not participating in the overlay, neighbor selection algorithms to find promising relays, and relay selection algorithms to choose the neighbor to traverse for a good detour. Finally, we show that PeerWise is practical through a wide-area deployment and evaluation.

A systematic approach for designing multifunctional thermally conducting polymer structures with embedded actuators - Bejgerowski,W.; Gupta,S.K.; Bruck,H. A. (Journal of Mechanical Design, 2009)

System-level Clustering and Timing Analysis for GALS-based Dataflow Architectures - Shen,C.; Bhattacharyya, Shuvra S. (In Proceedings of the ACM International Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, Austin, Texas, February 2009., 2009)
In this paper, we propose an approach based ondataflow techniques for modeling application-specific, globally asynchronous, locally synchronous (GALS) architectures for digital signal processing (DSP) applications, and analyzing the performance of such architectures. Dataflow-based techniques are attractive for DSP applications because they allow applica- tion behavior to be represented formally, analyzed at a high level of abstraction, and synthesized to software/hardware implementations through an optimized, automated process. In our proposed methodology, we employ dataflow-based compu- tational models to expose relevant structure in the targeted applications, and facilitate the manual or automatic derivation of efficient implementations. We demonstrate the utility of our modeling and analysis techniques by applying them as core parts of a novel clustering algorithm that is geared towards optimizing the throughput of GALS-based DSP architectures.

Systems-compatible incentives - Levin,D.; Spring, Neil; Bhattacharjee, Bobby (Game Theory for Networks, 2009. GameNets '09. International Conference on, 2009)
Selfish participants in a distributed system attempt to gain from the system without regard to how their actions may affect others. To maintain desirable system-wide properties in the presence of selfish users, designers are increasingly turning to the powerful mechanisms offered by economics and game theory. Combining the two fields of economics and systems design introduces new challenges of achieving incentive-compatibility in systems we can deploy in today's Internet. In this paper, we explore the interactions between systems and the mechanisms that give users incentives to cooperate. Using findings from recent work on incentive-compatible systems, we discuss several economic mechanisms and assumptions: money, punishment, and altruism. We seek to understand when these mechanisms violate system properties. Among the potential pitfalls we present is a phenomenon we call the price of altruism: altruistic peers can impose a loss of social good in some systems. We also discuss systems-compatible mechanisms that have been used in real, distributed systems, and attempt to extract the underlying design principles that have led to their success.
Keywords: computing; incentives; game; Internet; distributed; system; distributed; systems; game; systems; systems-compatible; theory; incentive-compatible; theory; peer-to-peer

TACKing Together Efficient Authentication, Revocation, and Privacy in VANETs - Studer, A.; Elaine Shi; Bai, Fan; Perrig, A. (2009)
Vehicular ad hoc networks (VANETs) require a mechanism to help authenticate messages, identify valid vehicles, and remove malevolent vehicles. A public key infrastructure (PKI) can provide this functionality using certificates and fixed public keys. However, fixed keys allow an eavesdropper to associate a key with a vehicle and a location, violating drivers' privacy. In this work we propose a VANET key management scheme based on temporary anonymous certified keys (TACKs). Our scheme efficiently prevents eavesdroppers from linking a vehicle's different keys and provides timely revocation of misbehaving participants while maintaining the same or less overhead for vehicle-to-vehicle communication as the current IEEE 1609.2 standard for VANET security.
Keywords: ad hoc networks; data privacy; eavesdropper; IEEE 1609.2 standard; Message authentication; mobile radio; public key cryptography; public key infrastructure; remove malevolent vehicle; telecommunication security; temporary anonymous certified key; valid vehicle identification; VANET key management; VANET security; vehicle-to-vehicle communication; Vehicles; vehicular ad hoc network

A theory of typed coercions and its applications - Swamy,Nikhil; Hicks, Michael W.; Bierman,Gavin M. (Proceedings of the 14th ACM SIGPLAN international conference on Functional programming, 2009)
A number of important program rewriting scenarios can be recast as type-directed coercion insertion. These range from more theoretical applications such as coercive subtyping and supporting overloading in type theories, to more practical applications such as integrating static and dynamically typed code using gradual typing, and inlining code to enforce security policies such as access control and provenance tracking. In this paper we give a general theory of type-directed coercion insertion. We specifically explore the inherent tradeoff between expressiveness and ambiguity--the more powerful the strategy for generating coercions, the greater the possibility of several, semantically distinct rewritings for a given program. We consider increasingly powerful coercion generation strategies, work out example applications supported by the increased power (including those mentioned above), and identify the inherent ambiguity problems of each setting, along with various techniques to tame the ambiguities.
Keywords: coercion insertion; gradual typing; nonambiguity; provenance; type-directed translation

Three genomes from the phylum Acidobacteria provide insight into the lifestyles of these microorganisms in soils. - Ward, Naomi L; Challacombe, Jean F; Janssen, Peter H; Henrissat, Bernard; Coutinho, Pedro M; Wu, Martin; Xie, Gary; Haft, Daniel H; Sait, Michelle; Badger, Jonathan; Barabote, Ravi D; Bradley, Brent; et al. (Appl Environ Microbiol, 2009)
The complete genomes of three strains from the phylum Acidobacteria were compared. Phylogenetic analysis placed them as a unique phylum. They share genomic traits with members of the Proteobacteria, the Cyanobacteria, and the Fungi. The three strains appear to be versatile heterotrophs. Genomic and culture traits indicate the use of carbon sources that span simple sugars to more complex substrates such as hemicellulose, cellulose, and chitin. The genomes encode low-specificity major facilitator superfamily transporters and high-affinity ABC transporters for sugars, suggesting that they are best suited to low-nutrient conditions. They appear capable of nitrate and nitrite reduction but not N(2) fixation or denitrification. The genomes contained numerous genes that encode siderophore receptors, but no evidence of siderophore production was found, suggesting that they may obtain iron via interaction with other microorganisms. The presence of cellulose synthesis genes and a large class of novel high-molecular-weight excreted proteins suggests potential traits for desiccation resistance, biofilm formation, and/or contribution to soil structure. Polyketide synthase and macrolide glycosylation genes suggest the production of novel antimicrobial compounds. Genes that encode a variety of novel proteins were also identified. The abundance of acidobacteria in soils worldwide and the breadth of potential carbon use by the sequenced strains suggest significant and previously unrecognized contributions to the terrestrial carbon cycle. Combining our genomic evidence with available culture traits, we postulate that cells of these isolates are long-lived, divide slowly, exhibit slow metabolic rates under low-nutrient conditions, and are well equipped to tolerate fluctuations in soil hydration.
Keywords: Anti-Bacterial Agents; bacteria; Biological Transport; Carbohydrate Metabolism; Cyanobacteria; DNA, Bacterial; Fungi; Genome, Bacterial; Macrolides; Molecular Sequence Data; Nitrogen; Phylogeny; Proteobacteria; Sequence Analysis, DNA; sequence homology; Soil Microbiology

Together, Rpn10 and Dsk2 Can Serve as a Polyubiquitin Chain-Length Sensor - Zhang,Daoning; Chen,Tony; Ziv,Inbal; Rosenzweig,Rina; Matiuhin,Yulia; Bronner,Vered; Glickman,Michael H.; Fushman, David (Molecular Cell, 2009)
SummaryAs a signal for substrate targeting, polyubiquitin meets various layers of receptors upstream to the 26S proteasome. We obtained structural information on two receptors, Rpn10 and Dsk2, alone and in complex with (poly)ubiquitin or with each other. A hierarchy of affinities emerges with Dsk2 binding monoubiquitin tighter than Rpn10 does, whereas Rpn10 prefers the ubiquitin-like domain of Dsk2 to monoubiquitin, with increasing affinities for longer polyubiquitin chains. We demonstrated the formation of ternary complexes of both receptors simultaneously with (poly)ubiquitin and found that, depending on the ubiquitin chain length, the orientation of the resulting complex is entirely different, providing for alternate signals. Dynamic rearrangement provides a chain-length sensor, possibly explaining how accessibility of Dsk2 to the proteasome is limited unless it carries a properly tagged cargo. We propose a mechanism for a malleable ubiquitin signal that depends both on chain length and combination of receptors to produce tetraubiquitin as an efficient signal threshold.
Keywords: Proteins; signaling

Tool supported detection and judgment of nonconformance in process execution - Zazworka, N.; Basili, Victor R.; Shull, F. (Empirical Software Engineering and Measurement, 2009. ESEM 2009. 3rd International Symposium on, 2009)
In the past decades the software engineering community has proposed a large collection of software development life cycles, models, and processes. The goal of a major set of these processes is to assure that the product is finished within time and budget, and that a predefined set of functional and nonfunctional requirements (e.g. quality goals) are satisfied at delivery time. Based upon the assumption that there is a real relationship between the process applied and the characteristics of the product developed from that process, we developed a tool supported approach that uses process nonconformance detection to identify potential risks in achieving the required process characteristics. In this paper we present the approach and a feasibility study that demonstrates its use on a large-scale software development project in the aerospace domain. We demonstrate that our approach, in addition to meeting the criteria above, can be applied to a real system of reasonable size; can represent a useful and adequate set of rules of relevance in such an environment; and can detect relevant examples of process nonconformance that provide useful insight to the project manager.
Keywords: aerospace; community; tool; cycle; software; detection; software; development; domain; large-scale; engineering; execution; process; life; management; software; nonconformance; project; nonfunctional; requirement; process; software; supported; tools

Toward reconstructing the evolution of advanced moths and butterflies (Lepidoptera: Ditrysia): an initial molecular study - Regier,J. C; Zwick,A.; Cummings, Michael P.; Kawahara,A. Y; Cho,S.; Weller,S.; Roe,A.; Baixeras,J.; Brown,J. W; Parr,C.; Davis,DR; Epstein,M; et al. (BMC Evol Biol, 2009)
BACKGROUND: In the mega-diverse insect order Lepidoptera (butterflies and moths; 165,000 described species), deeper relationships are little understood within the clade Ditrysia, to which 98% of the species belong. To begin addressing this problem, we tested the ability of five protein-coding nuclear genes (6.7 kb total), and character subsets therein, to resolve relationships among 123 species representing 27 (of 33) superfamilies and 55 (of 100) families of Ditrysia under maximum likelihood analysis. RESULTS: Our trees show broad concordance with previous morphological hypotheses of ditrysian phylogeny, although most relationships among superfamilies are weakly supported. There are also notable surprises, such as a consistently closer relationship of Pyraloidea than of butterflies to most Macrolepidoptera. Monophyly is significantly rejected by one or more character sets for the putative clades Macrolepidoptera as currently defined (P < 0.05) and Macrolepidoptera excluding Noctuoidea and Bombycoidea sensu lato (P < or = 0.005), and nearly so for the superfamily Drepanoidea as currently defined (P < 0.08). Superfamilies are typically recovered or nearly so, but usually without strong support. Relationships within superfamilies and families, however, are often robustly resolved. We provide some of the first strong molecular evidence on deeper splits within Pyraloidea, Tortricoidea, Geometroidea, Noctuoidea and others.Separate analyses of mostly synonymous versus non-synonymous character sets revealed notable differences (though not strong conflict), including a marked influence of compositional heterogeneity on apparent signal in the third codon position (nt3). As available model partitioning methods cannot correct for this variation, we assessed overall phylogeny resolution through separate examination of trees from each character set. Exploration of "tree space" with GARLI, using grid computing, showed that hundreds of searches are typically needed to find the best-feasible phylogeny estimate for these data. CONCLUSION: Our results (a) corroborate the broad outlines of the current working phylogenetic hypothesis for Ditrysia, (b) demonstrate that some prominent features of that hypothesis, including the position of the butterflies, need revision, and (c) resolve the majority of family and subfamily relationships within superfamilies as thus far sampled. Much further gene and taxon sampling will be needed, however, to strongly resolve individual deeper nodes.

Triangle Inequality and Routing Policy Violations in the Internet - Lumezanu,Cristian; Baden,Randy; Spring, Neil; Bhattacharjee, Bobby (Passive and Active Network MeasurementPassive and Active Network Measurement, 2009)
Triangle inequality violations (TIVs) are the effect of packets between two nodes being routed on the longer direct path between them when a shorter detour path through an intermediary is available. TIVs are a natural, widespread and persistent consequence of Internet routing policies. By exposing opportunities to improve the delay between two nodes, TIVs can help myriad applications that seek to minimize end-to-end latency. However, sending traffic along the detour paths revealed by TIVs may influence Internet routing negatively. In this paper we study the interaction between triangle inequality violations and policy routing in the Internet. We use measured and predicted AS paths between Internet nodes to show that 25% of the detour paths exposed by TIVs are in fact available to BGP but are simply deemed “less efficient”. We also compare the AS paths of detours and direct paths and find that detours use AS edges that are rarely followed by default Internet paths, while avoiding others that BGP seems to prefer. Our study is important both for understanding the various interactions that occur at the routing layer as well as their effects on applications that seek to use TIVs to minimize latency.
Keywords: Computer; Science

Triangle inequality variations in the internet - Lumezanu,Cristian; Baden,Randy; Spring, Neil; Bhattacharjee, Bobby (Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, 2009)
Triangle inequality violations (TIVs) are important for latency sensitive distributed applications. On one hand, they can expose opportunities to improve network routing by finding shorter paths between nodes. On the other hand, TIVs can frustrate network embedding or positioning systems that treat the Internet as a metric space where the triangle inequality holds. Even though triangle inequality violations are both significant and curious, their study has been limited to aggregate data sets that combine measurements taken over long periods of time. The limitations of these data sets open crucial questions in the design of systems that exploit (or avoid) TIVs: are TIVs stable or transient? Or are they illusions caused by aggregating measurements taken at different times? We collect latency matrices at varying sizes and time granularities and study dynamic properties of triangle inequality violations in the Internet. We show that TIVs are not results of measurement error and that their number varies with time. We examine how latency aggregates of data measured over longer periods of time preserve TIVs. Using medians to compute violations eliminates most of the TIVs that appear sporadically during the measurement but it misses many of the ones that are present for more than five hours.
Keywords: latency; tiv; triangle inequality violation; variation

Understanding the design tradeoffs for cooperative streaming multicast - Nandi,A.; Bhattacharjee, Bobby; Druschel,P. (Technical report MPI-SWS-2009-002, Max Planck Institute for Software Systems, 2009)
Video streaming over the Internet is rapidly increasing in popular-ity, but the availability and quality of the content is limited by the high bandwidth cost for server-based solutions. Cooperative end- system multicast (CEM) has emerged as a promising paradigm for content distribution in the Internet, because the bandwidth over- head of disseminating content is shared among the participants of the CEM overlay network. Several CEM systems have been pro- posed and deployed, but the tradeoffs inherent in the different de- signs are not well understood. In this work, we provide a common framework in which different CEM design choices can be empirically and systematically evalu- ated. Our results show that all CEM protocols are inherently lim- ited in certain aspects of their performance. We distill our observa- tions into a novel model that explains the inherent tradeoffs of CEM design choices and provides bounds on the practical performance limits of any future CEM protocol. In particular, the model conjec- tures that no CEM design can simultaneously achieve all three of low overhead, low lag, and high streaming quality.

The Use of Empirical Studies in the Development of High End Computing Applications - Basili, Victor R.; Zelowitz,Marvin V (University of Maryland, College Park, 2009)
This report provides a description of the research and development activities towards learning much about the development and measurement of productivity in high performance computing environments. Many objectives were accomplished including the development of a methodology for measuring productivity in the parallel programming domain. This methodology was tested over 25 times at 8 universities across the United States and can be used to aid other researchers studying similar environments. The productivity measurement methodology incorporates both development time and performance into a single productivity number. An Experiment Manager tool for collecting data on the development of parallel programs, as well as a suite of tools to aid in the capture and analysis of such data was also developed. Lastly, several large scale development environments were studied in order to better understand the environment used to build large parallel programming applications. That work also included several surveys and interviews with many professional programmers in these environments.
Keywords: *COMPUTER PROGRAMMING; *EMPIRICAL STUDIES; *HPC(HIGH PERFORMANCE COMPUTING); *METHODOLOGY; *PARALLEL PROCESSING; *PARALLEL PROGRAMMING; *PRODUCTIVITY; *SOFTWARE ENGINEERING; *SOFTWARE METRICS; ADMINISTRATION AND MANAGEMENT; APMS(AUTOMATED PERFORMANCE MEASUREMENT SYSTEM); COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER SYSTEMS MANAGEMENT AND STANDARDS; data acquisition; efficiency; ENVIRONMENTS; HIGH END COMPUTING; HPCBUGBASE; HUMAN FACTORS ENGINEERING & MAN MACHINE SYSTEM; learning; measurement; MPI(MESSAGE PASSING INTERFACE); PARALLEL ORIENTATION; PE62303E; PROGRAMMERS; SE(SOFTWARE ENGINEERING); SUPERVISORS; TEST AND EVALUATION; TEST FACILITIES, EQUIPMENT AND METEORS; TIME; tools; United States; WUAFRLT810HECA

Using formal specifications to support testing - Hierons,Robert M.; Krause,Paul; Lüttgen,Gerald; Simons,Anthony J. H.; Vilkomir,Sergiy; Woodward,Martin R.; Zedan,Hussein; Bogdanov,Kirill; Bowen,Jonathan P.; Cleaveland, Rance; Derrick,John; Dick,Jeremy; et al. (ACM Computing Surveys, 2009)

Using uncertainty as a model selection and comparison criterion - Sarcia',Salvatore Alessandro; Basili, Victor R.; Cantone,Giovanni (Proceedings of the 5th International Conference on Predictor Models in Software Engineering, 2009)
Over the last 25+ years, software estimation research has been searching for the best model for estimating variables of interest (e.g., cost, defects, and fault proneness). This research effort has not lead to a common agreement. One problem is that, they have been using accuracy as the basis for selection and comparison. But accuracy is not invariant; it depends on the test sample, the error measure, and the chosen error statistics (e.g., MMRE, PRED, Mean and Standard Deviation of error samples). Ideally, we would like an invariant criterion. In this paper, we show that uncertainty can be used as an invariant criterion to figure out which estimation model should be preferred over others. The majority of this work is empirically based, applying Bayesian prediction intervals to some COCOMO model variations with respect to a publicly available cost estimation data set coming from the PROMISE repository.
Keywords: accuracy; Bayesian prediction intervals; Calibration; cost estimation; cost model; model evaluation; model selection; prediction interval; Uncertainty

Video-Based Face Recognition Algorithms - Chellapa, Rama; Bicego, M.; Turaga,P. (Handbook of Remote Biometrics, 2009)
Traditional face recognition systems have relied on a gallery of still images for learning and a probe of still images for recognition. While the advantage of using motion information in face videos has been widely recognized, computational models for video-based face recognition have only recently gained attention. This chapter reviews some recent advances in this novel framework. In particular, the utility of videos in enhancing performance of image-based tasks (such as recognition or localization) will be summarized. Subsequently, spatiotemporal video-based face recognition systems based on particle filters, hidden Markov models , and system theoretic approaches will be presented. Further, some useful face databases employable by researchers interested in this field will be described. Finally, some open research issues will be proposed and discussed.

Visibility constraints on features of 3D objects - Basri,R.; Felzenszwalb,P. F; Girshick,R. B; Jacobs, David W.; Klivans,C. J (Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, 2009)
To recognize three-dimensional objects it is important to model how their appearances can change due to changes in viewpoint. A key aspect of this involves understanding which object features can be simultaneously visible under different viewpoints. We address this problem in an image-based framework, in which we use a limited number of images of an object taken from unknown viewpoints to determine which subsets of features might be simultaneously visible in other views. This leads to the problem of determining whether a set of images, each containing a set of features, is consistent with a single 3D object. We assume that each feature is visible from a disk of viewpoints on the viewing sphere. In this case we show the problem is NP-hard in general, but can be solved efficiently when all views come from a circle on the viewing sphere. We also give iterative algorithms that can handle noisy data and converge to locally optimal solutions in the general case. Our techniques can also be used to recover viewpoint information from the set of features that are visible in different images. We show that these algorithms perform well both on synthetic data and images from the COIL dataset.
Keywords: 3D; algorithms; synthetic; complexity; iterative; constraints; computational; data; synthetic; dataset; NP-hard; image-based; features; COIL; framework; iterative; images; three-dimensional; methods; object; object; recognition; recognition; viewing; sphere; visibility

Visual Tag - BRETEY,STEVE; Kuhnly,Keith; Davis, Larry S. (2009)
An improved animal tag for application to an animal's ear which comprises a male portion that includes a flat segment and a projection segment, a female portion that includes a generally square or generally oval shaped flat segment and a raised segment with an aperture; wherein the projection segment of the male portion is adapted to be inserted through the animal's ear and into the aperture when pressure is applied thereto.

What a mesh: understanding the design tradeoffs for streaming multicast - Nandi,Animesh; Bhattacharjee, Bobby; Druschel,Peter (SIGMETRICS Perform. Eval. Rev., 2009)
Cooperative end-system multicast (CEM) is a promising paradigm for Internet video distribution. Several CEM systems have been proposed and deployed, but the tradeoffs inherent in the different designs are not well understood. In this work, we provide a common framework in which different CEM design choices can be empirically and systematically evaluated. Based on our results, we conjecture that all CEM systems must abide by a set of fundamental design constraints, which we express in a simple model. By necessity, existing system implementations couple the data- and control-planes and often use different transport protocols.

Accountable internet protocol (aip) - Andersen,David G.; Balakrishnan,Hari; Feamster, Nick; Koponen,Teemu; Moon,Daekyeong; Shenker,Scott (SIGCOMM Comput. Commun. Rev., 2008)
This paper presents AIP (Accountable Internet Protocol), a network architecture that provides accountability as a first-order property. AIP uses a hierarchy of self-certifying addresses, in which each component is derived from the public key of the corresponding entity. We discuss how AIP enables simple solutions to source spoofing, denial-of-service, route hijacking, and route forgery. We also discuss how AIP's design meets the challenges of scaling, key management, and traffic engineering.
Keywords: accountability; address; internet architecture; scalability; Security

The acl anthology reference corpus: A reference dataset for bibliographic research in computational linguistics - Bird,S.; Dale,R.; Dorr, Bonnie J; Gibson,B.; Joseph,M.T.; Kan,M.Y.; Lee,D.; Powley,B.; Radev,D.R.; Tan,Y.F. (Proc. of the 6th International Conference on Language Resources and Evaluation Conference (LREC’08), 2008)
The ACL Anthology is a digital archive of conference and journal papers in natural language processing and computational linguistics.Its primary purpose is to serve as a reference repository of research results, but we believe that it can also be an object of study and a platform for research in its own right. We describe an enriched and standardized reference corpus derived from the ACL Anthology that can be used for research in scholarly document processing. This corpus, which we call the ACL Anthology Reference Corpus (ACL ARC), brings together the recent activities of a number of research groups around the world. Our goal is to make the corpus widely available, and to encourage other researchers to use it as a standard testbed for experiments in both bibliographic and bibliometric research.

Adopting Curvilinear Component Analysis to Improve Software Cost Estimation Accuracy. Model, Application Strategy, and an Experimental Verification - Sarcia,Salvatore A.; Cantone,Giovanni; Basili, Victor R. (In G. Visaggio (Ed.), 12 th International Conference on Evaluation and Assessment in Software Engineering. BCS eWIC, 2008)
Cost estimation is a critical issue for software organizations. Good estimates can help us make more informed decisions (controlling and planning software risks), if they are reliable (correct) and valid (stable). In this study, we apply a variable reduction technique (based on auto-associative feed--forward neural networks – called Curvilinear component analysis) to log-linear regression functions calibrated with ordinary least squares. Based on a COCOMO 81 data set, we show that Curvilinear component analysis can improve the estimation model accuracy by turning the initial input variables into an equivalent and more compact representation. We show that, the models obtained by applying Curvilinear component analysis are more parsimonious, correct, and reliable.

An area-efficient high-throughput hybrid interconnection network for single-chip parallel processing - Balkan,Aydin O.; Gang Qu; Vishkin, Uzi (Proceedings of the 45th annual Design Automation Conference, 2008)
Single-chip parallel processing requires high bandwidth between processors and on-chip memory modules. A recently proposed Mesh-of-Trees (MoT) network provides high throughput and low latency at relatively high area cost. In this paper, we introduce a hybrid MoT-BF network that combines MoT network with the area efficient butterfly network. We prove that the hybrid network reduces MoT network's area cost. Cycle-accurate simulation and post-layout results all show that significant area reduction can be achieved with negligible performance degradation, when operating at same clock rate.
Keywords: hybrid networks; mesh-of-trees; on-chip networks

The ASC-Alliance Projects: A Case Study of Large-Scale Parallel Scientific Code Development - Hochstein, L.; Basili, Victor R. (Computer, 2008)
Computational scientists face many challenges when developing software that runs on large-scale parallel machines. However, software-engineering researchers haven't studied their software development processes in much detail. To better understand the nature of software development in this context, the authors examined five large-scale computational science software projects operated at the five ASC-Alliance centers.
Keywords: ASC-Alliance; code; development; large-scale; development; parallel; engineering; machines; software; Parallel; projects; computational; scale; Science; scientific; scientists; large; software; systems; parallel

An assessment of systems and software engineering scholars and institutions (2001–2005) - Wong,W. Eric; Tse,T.H.; Glass,Robert L.; Basili, Victor R.; Chen,T.Y. (Journal of Systems and Software, 2008)
This paper presents the findings of a five-year study of the top scholars and institutions in the systems and software engineering field, as measured by the quantity of papers published in the journals of the field in 2001–2005. The top scholar is Magne Jørgensen of Simula Research Laboratory, Norway, and the top institution is Korea Advanced Institute of Science and Technology, Korea.This paper is part of an ongoing study, conducted annually, that identifies the top 15 scholars and institutions in the most recent five-year period.
Keywords: Research publications; Systems and software engineering; Top institutions; Top scholars

BELIV'08: Beyond time and errors: novel evaluation methods for information visualization - Bertini,Enrico; Perer,Adam; Plaisant, Catherine; Santucci,Giuseppe (CHI '08 extended abstracts on Human factors in computing systems, 2008)
Information visualization systems allow users to produce insights, innovations and discoveries. Evaluating such tools is a challenging task and the goal of BELIV'08 is to make a step ahead in the comprehension of such a complex activity. Current evaluation methods exhibit noticeable limitations and researchers in the area experiment some frustration with evaluation processes that are time consuming and too often leading to unsatisfactory results. The most used evaluation metrics such as task time completion and number of errors appear insufficient to quantify the quality of an information visualization system; thus the name of the workshop: "beyond time and errors".
Keywords: Evaluation; Information Visualization

Bilateral symmetry of object silhouettes under perspective projection - Bitsakos,K.; Yi,H.; Yi,L.; Fermüller, Cornelia (19th International Conference on Pattern Recognition, 2008. ICPR 2008, 2008)
Symmetry is an important property of objects and is exhibited in different forms e.g., bilateral, rotational, etc. This paper presents an algorithm for computing the bilateral symmetry of silhouettes of shallow objects under perspective distortion, exploiting the invariance of the cross ratio to projective transformations. The basic idea is to use the cross ratio to compute a number of midpoints of cross sections and then fit a straight line through them. The goodness-of-fit determines the likelihood of the line to be the axis of symmetry. We analytically estimate the midpointpsilas location as a function of the vanishing point for a given object silhouette. Hence finding the symmetry axis amounts to a 2D search in the space of vanishing points. We present experiments on two datasets as well as Internet images of symmetric objects that validate our approach.
Keywords: Automation; bilateral symmetry; Computer vision; Frequency; Image analysis; Image coding; Image reconstruction; Internet; Internet images; Object detection; object silhouettes; perspective distortion; perspective projection; SHAPE; symmetric objects

Bittorrent is an auction: analyzing and improving bittorrent's incentives - Levin,Dave; LaCurts,Katrina; Spring, Neil; Bhattacharjee, Bobby (Proceedings of the ACM SIGCOMM 2008 conference on Data communication, 2008)
Incentives play a crucial role in BitTorrent, motivating users to upload to others to achieve fast download times for all peers. Though long believed to be robust to strategic manipulation, recent work has empirically shown that BitTorrent does not provide its users incentive to follow the protocol. We propose an auction-based model to study and improve upon BitTorrent's incentives. The insight behind our model is that BitTorrent uses, not tit-for-tat as widely believed, but an auction to decide which peers to serve. Our model not only captures known, performance-improving strategies, it shapes our thinking toward new, effective strategies. For example, our analysis demonstrates, counter-intuitively, that BitTorrent peers have incentive to intelligently under-report what pieces of the file they have to their neighbors. We implement and evaluate a modification to BitTorrent in which peers reward one another with proportional shares of bandwidth. Within our game-theoretic model, we prove that a proportional-share client is strategy-proof. With experiments on PlanetLab, a local cluster, and live downloads, we show that a proportional-share unchoker yields faster downloads against BitTorrent and BitTyrant clients, and that under-reporting pieces yields prolonged neighbor interest.
Keywords: auctions; bittorrent; incentive systems; proportional share; tit-for-tat

Collective Classification in Network Data - Sen,Prithviraj; Namata,Galileo; Bilgic,Mustafa; Getoor, Lise; Galligher,Brian; Eliassi-Rad,Tina (AI Magazine, 2008)
Collective Classification in Network Data

On the Comparison of Network Attack Datasets: An Empirical Analysis - Berthier,R.; Korman,D.; Michel Cukier; Hiltunen,M.; Vesonder,G.; Sheleheda,D. (2008)
Network malicious activity can be collected and reported by various sources using different attack detection solutions. The granularity of these solutions provides either very detailed information (intrusion detection systems, honeypots) or high-level trends (CAIDA, SANS). The problem for network security operators is often to select the sources of information to better protect their network. How much information from these sources is redundant and how much is unique? The goal of this paper is to show empirically that while some global attack events can be correlated across various sensors, the majority of incoming malicious activity has local specificities. This study presents a comparative analysis of four different attack datasets offering three different levels of granularity: 1) two high interaction honeynets deployed at two different locations (i.e., a corporate and an academic environment); 2) ATLAS which is a distributed network telescope from Arbor; and 3) Internet Protecttrade which is a global alerting service from AT amp;T.
Keywords: ATLAS; distributed network telescope; Internet; intrusion detection systems; network attack datasets; network malicious activity; network security operators; security of data

The Complete Genome Sequence of Thermococcus Onnurineus NA1 Reveals a Mixed Heterotrophic and Carboxydotrophic Metabolism - Lee,Hyun Sook; Kang,Sung Gyun; Bae,Seung Seob; Lim,Jae Kyu; Cho,Yona; Kim,Yun Jae; Jeon,Jeong Ho; Cha,Sun-Shin; Kwon,Kae Kyoung; Kim,Hyung-Tae; Park,Cheol-Joo; Lee,Hee-Wook; et al. (Journal of BacteriologyJ. Bacteriol., 2008)
Members of the genus Thermococcus, sulfur-reducing hyperthermophilic archaea, are ubiquitously present in various deep-sea hydrothermal vent systems and are considered to play a significant role in the microbial consortia. We present the complete genome sequence and feature analysis of Thermococcus onnurineus NA1 isolated from a deep-sea hydrothermal vent area, which reveal clues to its physiology. Based on results of genomic analysis, T. onnurineus NA1 possesses the metabolic pathways for organotrophic growth on peptides, amino acids, or sugars. More interesting was the discovery that the genome encoded unique proteins that are involved in carboxydotrophy to generate energy by oxidation of CO to CO2, thereby providing a mechanistic basis for growth with CO as a substrate. This lithotrophic feature in combination with carbon fixation via RuBisCO (ribulose 1,5-bisphosphate carboxylase/oxygenase) introduces a new strategy with a complementing energy supply for T. onnurineus NA1 potentially allowing it to cope with nutrient stress in the surrounding of hydrothermal vents, providing the first genomic evidence for the carboxydotrophy in Thermococcus.

Compressive sensing for background subtraction - Cevher, V.; Sankaranarayanan, A.; Duarte, M.; Reddy, D.; Baraniuk, R.; Chellapa, Rama (Computer Vision–ECCV 2008, 2008)
Compressive sensing (CS) is an emerging field that provides a framework for image recovery using sub-Nyquist sampling rates. The CS theory shows that a signal can be reconstructed from a small set of random projections, provided that the signal is sparse in some basis, e.g., wavelets. In this paper, we describe a method to directly recover background subtracted images using CS and discuss its applications in some communication constrained multi-camera computer vision problems. We show how to apply the CS theory to recover object silhouettes (binary background subtracted images) when the objects of interest occupy a small portion of the camera view, i.e., when they are sparse in the spatial domain. We cast the background subtraction as a sparse approximation problem and provide different solutions based on convex optimization and total variation. In our method, as opposed to learning the background, we learn and adapt a low dimensional compressed representation of it, which is sufficient to determine spatial innovations; object silhouettes are then estimated directly using the compressive samples without any auxiliary image reconstruction. We also discuss simultaneous appearance recovery of the objects using compressive measurements. In this case, we show that it may be necessary to reconstruct one auxiliary image. To demonstrate the performance of the proposed algorithm, we provide results on data captured using a compressive single-pixel camera. We also illustrate that our approach is suitable for image coding in communication constrained problems by using data captured by multiple conventional cameras to provide 2D tracking and 3D shape reconstruction results with compressive measurements.

Content-based assembly search: A step towards assembly reuse - Deshmukh,Abhijit S.; Banerjee,Ashis Gopal; Gupta, Satyandra K.; Sriram,Ram D. (Computer-Aided Design, 2008)
The increased use of CAD systems by product development organizations has resulted in the creation of large databases of assemblies. This explosion of assembly data is likely to continue in the future. In many situations, a text-based search alone may not be sufficient to search for assemblies and it may be desirable to search for assemblies based on the content of the assembly models. The ability to perform content-based searches on these databases is expected to help the designers in the following two ways. First, it can facilitate the reuse of existing assembly designs, thereby reducing the design time. Second, a lot of useful designs for manufacturing, and assembly knowledge are implicitly embedded in existing assemblies. Therefore a capability to locate existing assemblies and examine them can be used as a learning tool by designers to learn from the existing assembly designs. This paper describes a system for performing content-based searches on assembly databases. We identify templates for comprehensive search definitions and describe algorithms to perform content-based searches for mechanical assemblies. We also illustrate the capabilities of our system through several examples.
Keywords: Assembly characteristics; Assembly mating conditions; Content-based assembly search; Graph compatibility

CrossTalk: The Journal of Defense Software Engineering. Volume 21, Number 10, October 2008 - Basili, Victor R.; Dangle,K.; Esker,L.; Marotta,F.; Rus,I.; Brosgol,B. M; Jamin,S.; Arthur,J. D; Ravichandar,R.; Wisnosky,D. E (DTIC Document, 2008)

The Deployment of a Darknet on an Organization-Wide Network: An Empirical Analysis - Berthier,R.; Michel Cukier (2008)
Darknet sensors have the interesting property of collecting only suspicious traffic, including misconfiguration, backscatter and malicious traffic. The type of traffic collected highly depends on two parameters: the size and the location of the darknet sensor. The goals of this paper are to study empirically the relationship between these two parameters and to try to increase the volume of attackers detected by a given darknet sensor. Our empirical results reveal that on average, on a daily basis, 485 distinct external source IP addresses perform a TCP scan on one of the two /16 networks of our organizationpsilas network. Moreover, a given darknet sensor of 77 IP addresses deployed in the same /16 network collects on average attack traffic from 26% of these attackers.
Keywords: attack traffic; backscatter; darknet sensors; external source IP address; malicious traffic; organization network; organization-wide network; TCP scan; telecommunication congestion control; transmission control protocol; Transport protocols

Development of a multi-piece multi-gate mold for manufacturing a flapping wing drive-mechanism - Ananthanarayanan,A.; Bejgerowski,W.; Mueller,D.; Gupta,S.K. (Transactions of North American Manufacturing Research Institution of SME, 2008)
Successful realization a flapping wing microair vehicle (MAV) requires development of a light weight drive-mechanism that can convert the continuous rotary motion to oscillatory flapping motion. Molded compliant drive-mechanisms are an attractive design option because of manufacturing scalability and reduction in the number of parts. The unique characteristics of this mechanism require development of a complex multi-piece multi-gate mold design. This paper describes a systematic approach for determining the part shape and size, optimizing the mold pieces, and placing the gates on the multi-piece mold. The novel aspects of this work include (1) selecting non-critical shape features to optimize the mold design and (2) the use of sacrificial structural elements to reduce the impact of the weld lines on the structural performance. The mold developed using our approach was utilized to realize a working flapping wing MAV.

Discarte: a disjunctive internet cartographer - Sherwood,R.; Bender,A.; Spring, Neil (ACM SIGCOMM Computer Communication Review, 2008)