Rapid, quantitative therapeutic screening for Alzheimer's enzymes enabled by optimal signal transduction with transistors - Le, Son T.; Morris, Michelle A.; Cardone, Antonio; Guros, Nicholas B.; Klauda, Jeffery B.; Sperling, Brent A.; Richter, Curt A.; Pant, Harish C.; Balijepalli, Arvind (The Analyst, 2020)

Quantum Capacitance-Limited MoS2 Biosensors Enable Remote Label-Free Enzyme Measurements - Le, Son T; Guros, Nicholas B; Bruce, Robert C; Cardone, Antonio; Amin, Niranjana D; Zhang, Siyuan; Klauda, Jeffery; Pant, Harish C; Richter, Curt A; Balijepalli, Arvind (Nanoscale, 2019)

Spores and soil from six sides: interdisciplinarity and the environmental biology of anthrax (Bacillus anthracis) - Carlson, Colin J.; Getz, Wayne M.; Kausrud, Kyrre L.; Cizauskas, Carrie A.; Blackburn, Jason K.; Bustos Carrillo, Fausto A.; Rita R Colwell; Easterday, W. Ryan; Ganz, Holly H.; Kamath, Pauline L.; Økstad, Ole A.; Turner, Wendy C.; et al. (Biological Reviews, 2018)
Environmentally transmitted diseases are comparatively poorly understood and managed, and their ecology is particularly understudied. Here we identify challenges of studying environmental transmission and persistence with a six‐sided interdisciplinary review of the biology of anthrax (Bacillus anthracis). Anthrax is a zoonotic disease capable of maintaining infectious spore banks in soil for decades (or even potentially centuries), and the mechanisms of its environmental persistence have been the topic of significant research and controversy. Where anthrax is endemic, it plays an important ecological role, shaping the dynamics of entire herbivore communities. The complex eco‐epidemiology of anthrax, and the mysterious biology of Bacillus anthracis during its environmental stage, have necessitated an interdisciplinary approach to pathogen research. Here, we illustrate different disciplinary perspectives through key advances made by researchers working in Etosha National Park, a long‐term ecological research site in Namibia that has exemplified the complexities of the enzootic process of anthrax over decades of surveillance. In Etosha, the role of scavengers and alternative routes (waterborne transmission and flies) has proved unimportant relative to the long‐term persistence of anthrax spores in soil and their infection of herbivore hosts. Carcass deposition facilitates green‐ups of vegetation to attract herbivores, potentially facilitated by the role of anthrax spores in the rhizosphere. The underlying seasonal pattern of vegetation, and herbivores' immune and behavioural responses to anthrax risk, interact to produce regular ‘anthrax seasons’ that appear to be a stable feature of the Etosha ecosystem. Through the lens of microbiologists, geneticists, immunologists, ecologists, epidemiologists, and clinicians, we discuss how anthrax dynamics are shaped at the smallest scale by population genetics and interactions within the bacterial communities up to the broadest scales of ecosystem structure. We illustrate the benefits and challenges of this interdisciplinary approach to disease ecology, and suggest ways anthrax might offer insights into the biology of other important pathogens. Bacillus anthracis, and the more recently emerged Bacillus cereus biovar anthracis, share key features with other environmentally transmitted pathogens, including several zoonoses and panzootics of special interest for global health and conservation efforts. Understanding the dynamics of anthrax, and developing interdisciplinary research programs that explore environmental persistence, is a critical step forward for understanding these emerging threats.

Characterization of Two Cryptic Plasmids Isolated in Haiti from Clinical Vibrio cholerae Non-O1/Non-O139 - Ceccarelli, Daniela; Garriss, Genevieve; Choi, Seon Y.; Hasan, Nur A.; Stepanauskas, Ramunas; Pop, Mihai; Huq, Anwar; Rita R Colwell (Frontiers in Microbiology, 2017)

Comprehensive benchmarking and ensemble approaches for metagenomic classifiers - McIntyre, Alexa B. R.; Ounit, Rachid; Afshinnekoo, Ebrahim; Prill, Robert J.; Hénaff, Elizabeth; Alexander, Noah; Minot, Samuel S.; Danko, David; Foox, Jonathan; Ahsanuddin, Sofia; Tighe, Scott; Hasan, Nur A.; et al. (Genome Biology, 2017)

Genomic Methods and Microbiological Technologies for Profiling Novel and Extreme Environments for the Extreme Microbiome Project (XMP) - Tighe, Scott; Afshinnekoo, Ebrahim; Rock, Tara M.; McGrath, Ken; Alexander, Noah; McIntyre, Alexa; Ahsanuddin, Sofia; Bezdan, Daniela; Green, Stefan J.; Joye, Samantha; Stewart Johnson, Sarah; Baldwin, Don A.; et al. (Journal of Biomolecular Techniques : JBT, 2017)
The Extreme Microbiome Project (XMP) is a project launched by the Association of Biomolecular Resource Facilities Metagenomics Research Group (ABRF MGRG) that focuses on whole genome shotgun sequencing of extreme and unique environments using a wide variety of biomolecular techniques. The goals are multifaceted, including development and refinement of new techniques for the following: 1) the detection and characterization of novel microbes, 2) the evaluation of nucleic acid techniques for extremophilic samples, and 3) the identification and implementation of the appropriate bioinformatics pipelines. Here, we highlight the different ongoing projects that we have been working on, as well as details on the various methods we use to characterize the microbiome and metagenome of these complex samples. In particular, we present data of a novel multienzyme extraction protocol that we developed, called Polyzyme or MetaPolyZyme. Presently, the XMP is characterizing sample sites around the world with the intent of discovering new species, genes, and gene clusters. Once a project site is complete, the resulting data will be publically available. Sites include Lake Hillier in Western Australia, the “Door to Hell” crater in Turkmenistan, deep ocean brine lakes of the Gulf of Mexico, deep ocean sediments from Greenland, permafrost tunnels in Alaska, ancient microbial biofilms from Antarctica, Blue Lagoon Iceland, Ethiopian toxic hot springs, and the acidic hypersaline ponds in Western Australia.

The microbiomes of blowflies and houseflies as bacterial transmission reservoirs - Junqueira, AC; Ratan, Aakrosh; Acerbi, Enzo; Drautz-Moses, Daniela I.; Premkrishnan, BNV; Costea, PI; Linz, Bodo; Purbojati, Rikky W.; Paulo, Daniel F.; Gaultier, Nicolas E.; Subramanian, Poorani; Hasan, Nur A.; et al. (Scientific Reports, 2017)
Blowflies and houseflies are mechanical vectors inhabiting synanthropic environments around the world. They feed and breed in fecal and decaying organic matter, but the microbiome they harbour and transport is largely uncharacterized. We sampled 116 individual houseflies and blowflies from varying habitats on three continents and subjected them to high-coverage, whole-genome shotgun sequencing. This allowed for genomic and metagenomic analyses of the host-associated microbiome at the species level. Both fly host species segregate based on principal coordinate analysis of their microbial communities, but they also show an overlapping core microbiome. Legs and wings displayed the largest microbial diversity and were shown to be an important route for microbial dispersion. The environmental sequencing approach presented here detected a stochastic distribution of human pathogens, such as Helicobacter pylori, thereby demonstrating the potential of flies as proxies for environmental and public health surveillance.

Chitin promotes Mycobacterium ulcerans growth - Sanhueza, Daniel; Chevillon, Christine; Rita R Colwell; Babonneau, Jérémie; Marion, Estelle; Marsollier, Laurent; égan, çois (FEMS Microbiology Ecology, 2016)
Mycobacterium ulcerans (MU) is the causative agent of Buruli ulcer, an emerging human infectious disease. However, both the ecology and life cycle of MU are poorly understood. The occurrence of MU has been linked to the aquatic environment, notably water bodies affected by human activities. It has been hypothesized that one or a combination of environmental factor(s) connected to human activities could favour growth of MU in aquatic systems. Here, we tested in vitro the growth effect of two ubiquitous polysaccharides and five chemical components on MU at concentration ranges shown to occur in endemic regions. Real-time PCR showed that chitin increased MU growth significantly providing a nutrient source or environmental support for the bacillus, thereby, providing a focus on the association between MU and aquatic arthropods. Aquatic environments with elevated population of arthropods provide increased chitin availability and, thereby, enhanced multiplication of MU. If calcium very slightly enhanced MU growth, iron, zinc, sulphate and phosphate did not stimulate MU growth, and at the concentration ranges of this study would limit MU population in natural ecosystems.

Climate influence on Vibrio and associated human diseases during the past half-century in the coastal North Atlantic - Vezzulli, Luigi; Grande, Chiara; Reid, Philip C.; élaouët, Pierre; Edwards, Martin; öfle, Manfred G.; Brettar, Ingrid; Rita R Colwell; Pruzzo, Carla (Proceedings of the National Academy of Sciences, 2016)
Climate change is having a dramatic impact on marine animal and plant communities but little is known of its influence on marine prokaryotes, which represent the largest living biomass in the world oceans and play a fundamental role in maintaining life on our planet. In this study, for the first time to our knowledge, experimental evidence is provided on the link between multidecadal climatic variability in the temperate North Atlantic and the presence and spread of an important group of marine prokaryotes, the vibrios, which are responsible for several infections in both humans and animals. Using archived formalin-preserved plankton samples collected by the Continuous Plankton Recorder survey over the past half-century (1958–2011), we assessed retrospectively the relative abundance of vibrios, including human pathogens, in nine areas of the North Atlantic and North Sea and showed correlation with climate and plankton changes. Generalized additive models revealed that long-term increase in Vibrio abundance is promoted by increasing sea surface temperatures (up to ∼1.5 °C over the past 54 y) and is positively correlated with the Northern Hemisphere Temperature (NHT) and Atlantic Multidecadal Oscillation (AMO) climatic indices (P < 0.001). Such increases are associated with an unprecedented occurrence of environmentally acquired Vibrio infections in the human population of Northern Europe and the Atlantic coast of the United States in recent years.

Cross-talk among flesh-eating Aeromonas hydrophila strains in mixed infection leading to necrotizing fasciitis - Ponnusamy, Duraisamy; Kozlova, Elena V.; Sha, Jian; Erova, Tatiana E.; Azar, Sasha R.; Fitts, Eric C.; Kirtley, Michelle L.; Tiner, Bethany L.; Andersson, Jourdan A.; Grim, Christopher J.; Isom, Richard P.; Hasan, Nur A.; et al. (Proceedings of the National Academy of Sciences, 2016)
Necrotizing fasciitis (NF) caused by flesh-eating bacteria is associated with high case fatality. In an earlier study, we reported infection of an immunocompetent individual with multiple strains of Aeromonas hydrophila (NF1–NF4), the latter three constituted a clonal group whereas NF1 was phylogenetically distinct. To understand the complex interactions of these strains in NF pathophysiology, a mouse model was used, whereby either single or mixed A. hydrophila strains were injected intramuscularly. NF2, which harbors exotoxin A (exoA) gene, was highly virulent when injected alone, but its virulence was attenuated in the presence of NF1 (exoA-minus). NF1 alone, although not lethal to animals, became highly virulent when combined with NF2, its virulence augmented by cis-exoA expression when injected alone in mice. Based on metagenomics and microbiological analyses, it was found that, in mixed infection, NF1 selectively disseminated to mouse peripheral organs, whereas the other strains (NF2, NF3, and NF4) were confined to the injection site and eventually cleared. In vitro studies showed NF2 to be more effectively phagocytized and killed by macrophages than NF1. NF1 inhibited growth of NF2 on solid media, but ExoA of NF2 augmented virulence of NF1 and the presence of NF1 facilitated clearance of NF2 from animals either by enhanced priming of host immune system or direct killing via a contact-dependent mechanism.

Enrichment dynamics of Listeria monocytogenes and the associated microbiome from naturally contaminated ice cream linked to a listeriosis outbreak - Ottesen, Andrea; Ramachandran, Padmini; Reed, Elizabeth; White, James R.; Hasan, Nur; Subramanian, Poorani; Ryan, Gina; Jarvis, Karen; Grim, Christopher; Daquiqan, Ninalynn; Hanes, Darcy; Allard, Marc; et al. (BMC Microbiology, 2016)

Deep-sea hydrothermal vent bacteria related to human pathogenic Vibrio species - Hasan, Nur A.; Grim, Christopher J.; Lipp, Erin K.; Rivera, Irma N. G.; Chun, Jongsik; Haley, Bradd J.; Taviani, Elisa; Choi, Seon Young; Hoq, Mozammel; Munk, A. Christine; Brettin, Thomas S.; Bruce, David; et al. (Proceedings of the National Academy of Sciences, 2015)
Vibrio species are both ubiquitous and abundant in marine coastal waters, estuaries, ocean sediment, and aquaculture settings worldwide. We report here the isolation, characterization, and genome sequence of a novel Vibrio species, Vibrio antiquarius, isolated from a mesophilic bacterial community associated with hydrothermal vents located along the East Pacific Rise, near the southwest coast of Mexico. Genomic and phenotypic analysis revealed V. antiquarius is closely related to pathogenic Vibrio species, namely Vibrio alginolyticus, Vibrio parahaemolyticus, Vibrio harveyi, and Vibrio vulnificus, but sufficiently divergent to warrant a separate species status. The V. antiquarius genome encodes genes and operons with ecological functions relevant to the environment conditions of the deep sea and also harbors factors known to be involved in human disease caused by freshwater, coastal, and brackish water vibrios. The presence of virulence factors in this deep-sea Vibrio species suggests a far more fundamental role of these factors for their bacterial host. Comparative genomics revealed a variety of genomic events that may have provided an important driving force in V. antiquarius evolution, facilitating response to environmental conditions of the deep sea.

Hybrid Vibrio cholerae El Tor Lacking SXT Identified as the Cause of a Cholera Outbreak in the Philippines - Klinzing, David C.; Choi, Seon Young; Hasan, Nur A.; Matias, Ronald R.; Tayag, Enrique; Geronimo, Josefina; Skowronski, Evan; Rashed, Shah M.; Kawashima, Kent; Rosenzweig, C. Nicole; Gibbons, Henry S.; Torres, Brian C.; et al. (mBio, 2015)
Cholera continues to be a global threat, with high rates of morbidity and mortality. In 2011, a cholera outbreak occurred in Palawan, Philippines, affecting more than 500 people, and 20 individuals died. Vibrio cholerae O1 was confirmed as the etiological agent. Source attribution is critical in cholera outbreaks for proper management of the disease, as well as to control spread. In this study, three V. cholerae O1 isolates from a Philippines cholera outbreak were sequenced and their genomes analyzed to determine phylogenetic relatedness to V. cholerae O1 isolates from recent outbreaks of cholera elsewhere. The Philippines V. cholerae O1 isolates were determined to be V. cholerae O1 hybrid El Tor belonging to the seventh-pandemic clade. They clustered tightly, forming a monophyletic clade closely related to V. cholerae O1 hybrid El Tor from Asia and Africa. The isolates possess a unique multilocus variable-number tandem repeat analysis (MLVA) genotype (12-7-9-18-25 and 12-7-10-14-21) and lack SXT. In addition, they possess a novel 15-kb genomic island (GI-119) containing a predicted type I restriction-modification system. The CTXΦ-RS1 array of the Philippines isolates was similar to that of V. cholerae O1 MG116926, a hybrid El Tor strain isolated in Bangladesh in 1991. Overall, the data indicate that the Philippines V. cholerae O1 isolates are unique, differing from recent V. cholerae O1 isolates from Asia, Africa, and Haiti. Furthermore, the results of this study support the hypothesis that the Philippines isolates of V. cholerae O1 are indigenous and exist locally in the aquatic ecosystem of the Philippines.

Nontoxigenic Vibrio cholerae Non-O1/O139 Isolate from a Case of Human Gastroenteritis in the U.S. Gulf Coast - Hasan, Nur A.; Rezayat, Talayeh; Blatz, Peter J.; Choi, Seon Young; Griffitt, Kimberly J.; Rashed, Shah M.; Huq, Anwar; Conger, Nicholas G.; Rita R Colwell; Grimes, D. Jay (Journal of Clinical Microbiology, 2015)
An occurrence of Vibrio cholerae non-O1/O139 gastroenteritis in the U.S. Gulf Coast is reported here. Genomic analysis revealed that the isolate lacked known virulence factors associated with the clinical outcome of a V. cholerae infection but did contain putative genomic islands and other accessory virulence factors. Many of these factors are widespread among environmental strains of V. cholerae, suggesting that there might be additional virulence factors in non-O1/O139 V. cholerae yet to be determined. Phylogenetic analysis revealed that the isolate belonged to a phyletic lineage of environmental V. cholerae isolates associated with sporadic cases of gastroenteritis in the Western Hemisphere, suggesting a need to monitor non-O1/O139 V. cholerae in the interest of public health.

Occurrence and Diversity of Clinically Important Vibrio Species in the Aquatic Environment of Georgia - Kokashvili, Tamar; Whitehouse, Chris A.; Tskhvediani, Ana; Grim, Christopher J.; Elbakidze, Tinatin; Mitaishvili, Nino; Janelidze, Nino; Jaiani, Ekaterine; Haley, Bradd J.; Lashkhi, Nino; Huq, Anwar; Rita R Colwell; et al. (Frontiers in Public Health, 2015)

A unified initiative to harness Earth's microbiomes - Alivisatos, A. P.; Blaser, M. J.; Brodie, E. L.; Chun, M.; Dangl, J. L.; Donohue, T. J.; Dorrestein, P. C.; Gilbert, J. A.; Green, J. L.; Jansson, J. K.; Knight, R.; Maxon, M. E.; et al. (Science, 2015)

Use of Environmental Parameters to Model Pathogenic Vibrios in Chesapeake Bay - Zaitchik, B. F.; Guikema, S. D.; Haley, B. J.; Taviani, E.; Chen, A.; Brown, M.E.; Huq, A.; Rita R Colwell (Journal of Environmental Informatics, 2015)
Although the transportation sector is a major contributor to urban air pollution and global climate change due to its substantial energy consumptions, previous studies for evacuation practices in this sector seldom took environmental consequences into account. As an attempt in event-related evacuation planning under uncertainty, this study proposed an emission-mitigation-oriented fuzzy evacuation management (emoFEM) model. Comprehensive considerations over system efficiency, environmental protection, economic cost and resource availability were incorporated within a general modeling formulation to facilitate evacuation management in a systematic and compromise manner. Vague and ambiguous information embedded within evacuation problems could be quantified and directly communicated into the optimization process, greatly improving conventional tools for evacuation management under uncertainty. The proposed emoFEM model was then applied to a hypothetic but representative case. Useful solutions were generated, which could help identify timely, safe and cost-effective evacuation schemes without significant disturbances over normal municipal traffic and environmental quality. The advantages of emoFEM were further revealed through comparing its solutions with those from its deterministic counterpart.

Molecular diversity and predictability of Vibrio parahaemolyticus along the Georgian coastal zone of the Black Sea - Haley, Bradd J.; Kokashvili, Tamar; Tskshvediani, Ana; Janelidze, Nino; Mitaishvili, Nino; Grim, Christopher J.; Constantin_de_Magny, Guillaume; Chen, Arlene J.; Taviani, Elisa; Eliashvili, Tamar; Tediashvili, Marina; Whitehouse, Chris A.; et al. (Frontiers in Microbiology, 2014)
Vibrio parahaemolyticus is a leading cause of seafood-related gastroenteritis and is also an autochthonous member of marine and estuarine environments worldwide. One-hundred seventy strains of V. parahaemolyticus were isolated from water and plankton samples collected along the Georgian coast of the Black Sea during 28 months of sample collection. All isolated strains were tested for presence of tlh, trh, and tdh. A subset of strains were serotyped and tested for additional factors and markers of pandemicity. Twenty-six serotypes, five of which are clinically relevant, were identified. Although all 170 isolates were negative for tdh, trh, and the Kanagawa Phenomenon, 7 possessed the GS-PCR sequence and 27 the 850 bp sequence of V. parahaemolyticus pandemic strains. The V. parahaemolyticus population in the Black Sea was estimated to be genomically heterogeneous by rep-PCR and the serodiversity observed did not correlate with rep-PCR genomic diversity. Statistical modeling was used to predict presence of V. parahaemolyticus as a function of water temperature, with strongest concordance observed for Green Cape site samples (Percent of total variance = 70, P < 0.001). Results demonstrate a diverse population of V. parahaemolyticus in the Black Sea, some of which carry pandemic markers, with increased water temperature correlated to an increase in abundance of V. parahaemolyticus.

Stable isotope labeling of phosphoproteins for large-scale phosphorylation rate determination - Molden, Rosalynn C.; Goya, Jonathan; Zia Khan; Garcia, Benjamin A. (Molecular & Cellular Proteomics, 2014)
Signals that control response to stimuli and cellular function are transmitted through dynamic phosphorylation of thousands of proteins by protein kinases. Many techniques have been developed to study phosphorylation dynamics, including several mass spectrometry (MS)-based methods. Over the last few decades, substantial developments have been made in MS techniques for the large-scale identification of proteins and their post-translational modifications. Nevertheless, all of the current MS-based techniques for quantifying protein phosphorylation dynamics rely on the measurement of changes in peptide abundance levels and many methods suffer from low confidence in phosphopeptide identification due to poor fragmentation. Here we have optimized an approach for the Stable Isotope Labeling of Amino acids by Phosphate (SILAP) using [gamma-18O4]ATP in nucleo to determine global site-specific phosphorylation rates. The advantages of this metabolic labeling technique are: increased confidence in phosphorylated peptide identification, direct labeling of phosphorylation sites, measurement phosphorylation rates, and the identification of actively phosphorylated sites in a cell-like environment. In this study we calculated approximate rate constants for over 500 phosphorylation sites based on labeling progress curves. We measured a wide range of phosphorylation rate constants from 0.34 min-1 to 0.001 min-1. Finally, we applied SILAP to determine sites that have different phosphorylation kinetics during G1/S and M phase. We found that most sites have very similar phosphorylation rates under both conditions; however a small subset of sites on proteins involved in the mitotic spindle were more actively phosphorylated during M phase, while proteins involved in DNA replication and transcription were more actively phosphorylated during G1/S phase.
Keywords: DYNAMICS; Phosphoproteins*; Phosphoproteome; Phosphorylation; Post-translational modifications*; Signal Transduction*; turnover

Viewing Marine Bacteria, Their Activity and Response to Environmental Drivers from Orbit - Grimes, D. Jay; Ford, Tim E.; Rita R Colwell; Baker-Austin, Craig; Martinez-Urtaza, Jaime; Subramaniam, Ajit; Capone, Douglas G. (Microbial Ecology, 2014)
Satellite-based remote sensing of marine microorganisms has become a useful tool in predicting human health risks associated with these microscopic targets. Early applications were focused on harmful algal blooms, but more recently methods have been developed to interrogate the ocean for bacteria. As satellite-based sensors have become more sophisticated and our ability to interpret information derived from these sensors has advanced, we have progressed from merely making fascinating pictures from space to developing process models with predictive capability. Our understanding of the role of marine microorganisms in primary production and global elemental cycles has been vastly improved as has our ability to use the combination of remote sensing data and models to provide early warning systems for disease outbreaks. This manuscript will discuss current approaches to monitoring cyanobacteria and vibrios, their activity and response to environmental drivers, and will also suggest future directions.

Detection of Vibrio cholerae in environmental waters including drinking water reservoirs of Azerbaijan - Rashid, Ahmadov; Haley, Bradd J.; Rajabov, Mukhtar; Ahmadova, Sevinj; Gurbanov, Shair; Rita R Colwell; Huq, Anwar (Environmental Microbiology Reports, 2013)

Distribution of Virulence Genes in Clinical and Environmental Vibrio cholerae Strains in Bangladesh - Hasan, Nur A.; Ceccarelli, Daniela; Grim, Christopher J.; Taviani, Elisa; Choi, Jinna; Sadique, Abdus; Alam, Munirul; Siddique, Abul K.; Sack, R. Bradley; Huq, Anwar; Rita R Colwell (Applied and Environmental Microbiology, 2013)
Vibrio cholerae, an environmental organism, is a facultative human pathogen. Here, we report the virulence profiles, comprising 18 genetic markers, of 102 clinical and 692 environmental V. cholerae strains isolated in Bangladesh between March 2004 and January 2006, showing the variability of virulence determinants within the context of public health.

Identification of bacteria in enrichment cultures of sulfate reducers in the Cariaco Basin water column employing Denaturing Gradient Gel Electrophoresis of 16S ribosomal RNA gene fragments - Bozo-Hurtado, Lorelei; García-Amado, M; Chistoserdov, Andrei; Varela, Ramon; Narvaez, J; Rita R Colwell; Suárez, Paula (Aquatic Biosystems, 2013)
Background The Cariaco Basin is characterized by pronounced and predictable vertical layering of microbial communities dominated by reduced sulfur species at and below the redox transition zone. Marine water samples were collected in May, 2005 and 2006, at the sampling stations A (10°30′ N, 64°40′ W), B (10°40′ N, 64°45′ W) and D (10°43’N, 64°32’W) from different depths, including surface, redox interface, and anoxic zones. In order to enrich for sulfate reducing bacteria (SRB), water samples were inoculated into anaerobic media amended with lactate or acetate as carbon source. To analyze the composition of enrichment cultures, we performed DNA extraction, PCR-DGGE, and sequencing of selected bands. Results DGGE results indicate that many bacterial genera were present that are associated with the sulfur cycle, including Desulfovibrio spp., as well as heterotrophs belonging to Vibrio, Enterobacter, Shewanella, Fusobacterium, Marinifilum, Mariniliabilia, and Spirochaeta. These bacterial populations are related to sulfur coupling and carbon cycles in an environment of variable redox conditions and oxygen availability. Conclusions In our studies, we found an association of SRB-like Desulfovibrio with Vibrio species and other genera that have a previously defined relevant role in sulfur transformation and coupling of carbon and sulfur cycles in an environment where there are variable redox conditions and oxygen availability. This study provides new information about microbial species that were culturable on media for SRB at anaerobic conditions at several locations and water depths in the Cariaco Basin.

Personal informatics in the wild: hacking habits for health & happiness - Li, Ian; Jon Froehlich; Larsen, Jakob E; Grevet, Catherine; Ramirez, Ernesto (CHI '13 Extended Abstracts on Human Factors in Computing Systems, 2013)
Abstract Personal informatics is a class of systems that help people collect personal information to improve self-knowledge. Improving self-knowledge can foster self-insight and promote positive behaviors, such as healthy living and energy conservation. The ...

Primate Transcript and Protein Expression Levels Evolve Under Compensatory Selection Pressures - Zia Khan; Ford, Michael J.; Cusanovich, Darren A.; Mitrano, Amy; Pritchard, Jonathan K.; Gilad, Yoav (Science, 2013)
Changes in gene regulation have likely played an important role in the evolution of primates. Differences in messenger RNA (mRNA) expression levels across primates have often been documented; however, it is not yet known to what extent measurements of divergence in mRNA levels reflect divergence in protein expression levels, which are probably more important in determining phenotypic differences. We used high-resolution, quantitative mass spectrometry to collect protein expression measurements from human, chimpanzee, and rhesus macaque lymphoblastoid cell lines and compared them to transcript expression data from the same samples. We found dozens of genes with significant expression differences between species at the mRNA level yet little or no difference in protein expression. Overall, our data suggest that protein expression levels evolve under stronger evolutionary constraint than mRNA levels.Don't Ape Protein Variation Changes in DNA and messenger RNA (mRNA) expression levels have been used to estimate evolutionary changes between species. However protein expression levels may better reflect selection on divergent and constrained phenotypes. Khan et al. (p. 1100, published online 17 October; see the Perspective by Vogel) measured the differences among and within species between mRNA expression and protein levels in humans, chimpanzees, and rhesus macaques, identifying protein transcripts that seem to be under lineage-specific constraint between humans and chimpanzees.

Spoiler Alert: Machine Learning Approaches to Detect Social Media Posts with Revelatory Information - Jordan Boyd-Graber; Glasgow, K; Zajac, J S (2013)
ABSTRACT Spoilers—critical plot information about works of fiction that “spoil” a viewer's enjoyment—have prompted elaborate conventions on social media to allow readers to insulate themselves from spoilers. However, these solutions depend on the ...

Why “Fiat-Shamir for Proofs” Lacks a Proof - Bitansky, Nir; Dana Dachman-Soled; Garg, Sanjam; Jain, Abhishek; Kalai, Yael Tauman; López-Alt, Adriana; Wichs, Daniel (Theory of Cryptography, 2013)
The Fiat-Shamir heuristic [CRYPTO ’86] is used to convert any 3-message public-coin proof or argument system into a non-interactive argument, by hashing the prover’s first message to select the verifier’s challenge. It is known that this heuristic is sound when the hash function is modeled as a random oracle. On the other hand, the surprising result of Goldwasser and Kalai [FOCS ’03] shows that there exists a computationally sound argument on which the Fiat-Shamir heuristic is never sound, when instantiated with any actual efficient hash function. This leaves us with the following interesting possibility: perhaps we can securely instantiates the Fiat-Shamir heuristic for all 3-message public-coin statistically sound proofs, even if we must fail for some computationally sound arguments. Indeed, this has been conjectured to be the case by Barak, Lindell and Vadhan [FOCS ’03], but we do not have any provably secure instantiation under any “standard assumption”. In this work, we give a broad black-box separation result showing that the security of the Fiat-Shamir heuristic for statistically sound proofs cannot be proved under virtually any standard assumption via a black-box reduction. More precisely: –If we want to have a “universal” instantiation of the Fiat-Shamir heuristic that works for all 3-message public-coin proofs, then we cannot prove its security via a black-box reduction from any assumption that has the format of a “cryptographic game”. –For many concrete proof systems, if we want to have a “specific” instantiation of the Fiat-Shamir heuristic for that proof system, then we cannot prove its security via a black box reduction from any “falsifiable assumption” that has the format of a cryptographic game with an efficient challenger.
Keywords: Algorithm Analysis and Problem Complexity; Computation by Abstract Devices; Data Encryption; Systems and Data Security

AGORA: Assembly Guided by Optical Restriction Alignment - Lin, H.C.; Goldstein, S.; Mendelowitz, L.; Zhou, S.; Wetzel, J.; Schwartz, D.C.; Pop, Mihai (BMC bioinformatics, 2012)
Genome assembly is difficult due to repeated sequences within the genome, which create ambiguities and cause the final assembly to be broken up into many separate sequences (contigs). Long range linking information, such as mate-pairs or mapping data, is necessary to help assembly software resolve repeats, thereby leading to a more complete reconstruction of genomes. Prior work has used optical maps for validating assemblies and scaffolding contigs, after an initial assembly has been produced. However, optical maps have not previously been used within the genome assembly process. Here, we use optical map information within the popular de Bruijn graph assembly paradigm to eliminate paths in the de Bruijn graph which are not consistent with the optical map and help determine the correct reconstruction of the genome.We developed a new algorithm called AGORA: Assembly Guided by Optical Restriction Alignment. AGORA is the first algorithm to use optical map information directly within the de Bruijn graph framework to help produce an accurate assembly of a genome that is consistent with the optical map information provided. Our simulations on bacterial genomes show that AGORA is effective at producing assemblies closely matching the reference sequences. Additionally, we show that noise in the optical map can have a strong impact on the final assembly quality for some complex genomes, and we also measure how various characteristics of the starting de Bruijn graph may impact the quality of the final assembly. Lastly, we show that a proper choice of restriction enzyme for the optical map may substantially improve the quality of the final assembly. Our work shows that optical maps can be used effectively to assemble genomes within the de Bruijn graph assembly framework. Our experiments also provide insights into the characteristics of the mapping data that most affect the performance of our algorithm, indicating the potential benefit of more accurate optical mapping technologies, such as nano-coding.

Automated synthesis of action selection policies for unmanned vehicles operating in adverse environments - Svec,Petr; Gupta, Satyandra K. (Autonomous Robots, 2012)
We address the problem of automated action selection policy synthesis for unmanned vehicles operating in adverse environments. We introduce a new evolutionary computation-based approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. The synthesis technique consists of the automated extraction of the vehicle’s exception states and Genetic Programming (GP) for automated composition and optimization of corrective sequences of commands in the form of macro-actions to be applied locally. The focus is specifically on automated synthesis of a policy for Unmanned Surface Vehicle (USV) to efficiently block the advancement of an intruder boat toward a valuable target. This task requires the USV to utilize reactive planning complemented by short-term forward planning to generate specific maneuvers for blocking. The intruder is human-competitive and exhibits a deceptive behavior so that the USV cannot exploit regularity in its attacking behavior. We compared the performance of a hand-coded blocking policy to the performance of a policy that was automatically synthesized. Our results show that the performance of the automatically generated policy exceeds the performance of the hand-coded policy and thus demonstrates the feasibility of the proposed approach.
Keywords: Computer science

Automatic Authentication of Banknotes - Roy,Ankush; Halder,Biswaiit; Garain,Utpal; David Doermann (IEEE Transactions on Information Forensics & Security, 2012)
In this paper, we address the problem of the automatic authentication of paper currency. Indian banknotes are used to show how a system can be developed for discriminating counterfeit notes from genuine notes. Image processing and pattern recognition techniques are designed to carefully analyze embedded security features. Experiments conducted on forensic samples show that a high precision low cost machine can be developed to address this problem. The analysis of current security features’ ability to protect against counterfeiting also suggest topics that should be considered in designing future currency notes.

BclAF1 restriction factor is neutralized by proteasomal degradation and microRNA repression during human cytomegalovirus infection - Lee, Song Hee; Kalejta, Robert F.; Kerry, Julie; Semmes, Oliver John; O’Connor, Christine M.; Zia Khan; Garcia, Benjamin A.; Shenk, Thomas; Murphy, Eain (Proceedings of the National Academy of Sciences, 2012)
Cell proteins can restrict the replication of viruses. Here, we identify the cellular BclAF1 protein as a human cytomegalovirus restriction factor and describe two independent mechanisms the virus uses to decrease its steady-state levels. Immediately following infection, the viral pp71 and UL35 proteins, which are delivered to cells within virions, direct the proteasomal degradation of BclAF1. Although BclAF1 reaccumulates through the middle stages of infection, it is subsequently down-regulated at late times by miR-UL112-1, a virus-encoded microRNA. In the absence of BclAF1 neutralization, viral gene expression and replication are inhibited. These data identify two temporally and mechanistically distinct functions used by human cytomegalovirus to down-regulate a cellular antiviral protein.
Keywords: innate immunity; intrinsic immunity; miRNA; Proteasome; UL82

Bioinformatics for the Human Microbiome Project - Gevers, Dirk; Pop, Mihai; Schloss, Patrick D.; Huttenhower, Curtis (PLoS Computational Biology, 2012)

A Blur-robust Descriptor with Applications to Face Recognition - Gopalan,R.; Taheri, S.; Turaga,P.; Chellapa, Rama (IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012)
Understanding the effect of blur is an important problem in unconstrained visual analysis. We address this problem in the context of image-based recognition, by a fusion of image-formation models, and differential geometric tools. First, we discuss the space spanned by blurred versions of an image and then under certain assumptions, provide a differential geometric analysis of that space. More specifically, we create a subspace resulting from convolution of an image with a complete set of orthonormal basis functions of a pre-specified maximum size (that can represent an arbitrary blur kernel within that size), and show that the corresponding subspaces created from a clean image and its blurred versions are equal under the ideal case of zero noise, and some assumptions on the properties of blur kernels. We then study the practical utility of this subspace representation for the problem of direct recognition of blurred faces, by viewing the subspaces as points on the Grassmann manifold and present methods to perform recognition for cases where the blur is both homogenous and spatially varying. We empirically analyze the effect of noise, as well as the presence of other facial variations between the gallery and probe images, and provide comparisons with existing approaches on standard datasets.
Keywords: Blur; convolution; Face; face recognition; Grassmann manifold; Kernel; Manifolds; NOISE; PROBES

Computational Extractors and Pseudorandomness - Dana Dachman-Soled; Gennaro, Rosario; Krawczyk, Hugo; Malkin, Tal (Theory of Cryptography, 2012)
Computational extractors are efficient procedures that map a source of sufficiently high min-entropy to an output that is computationally indistinguishable from uniform. By relaxing the statistical closeness property of traditional randomness extractors one hopes to improve the efficiency and entropy parameters of these extractors, while keeping their utility for cryptographic applications. In this work we investigate computational extractors and consider questions of existence and inherent complexity from the theoretical and practical angles, with particular focus on the relationship to pseudorandomness. An obvious way to build a computational extractor is via the “extract-then-prg” method: apply a statistical extractor and use its output to seed a PRG. This approach carries with it the entropy cost inherent to implementing statistical extractors, namely, the source entropy needs to be substantially higher than the PRG’s seed length. It also requires a PRG and thus relies on one-way functions. We study the necessity of one-way functions in the construction of computational extractors and determine matching lower and upper bounds on the “black-box efficiency” of generic constructions of computational extractors that use a one-way permutation as an oracle. Under this efficiency measure we prove a direct correspondence between the complexity of computational extractors and that of pseudorandom generators, showing the optimality of the extract-then-prg approach for generic constructions of computational extractors and confirming the intuition that to build a computational extractor via a PRG one needs to make up for the entropy gap intrinsic to statistical extractors. On the other hand, we show that with stronger cryptographic primitives one can have more entropy- and computationally-efficient constructions. In particular, we show a construction of a very practical computational extractor from any weak PRF without resorting to statistical extractors.
Keywords: Algorithm Analysis and Problem Complexity; Coding and Information Theory; Computer Communication Networks; Data Encryption; Math Applications in Computer Science; Systems and Data Security

Conversion of viable but nonculturable enteric bacteria to culturable by co‐culture with eukaryotic cells - Senoh,Mitsutoshi; Ghosh‐Banerjee,Jayeeta; Ramamurthy,Thandavarayan; Rita R Colwell; Miyoshi,Shin-ichi; Nair,G. Balakrish; Takeda,Yoshifumi (Microbiology and Immunology, 2012)
Viable but nonculturable (VBNC) Vibrio cholerae non-O1/non-O139, V. parahaemolyticus, enterohemorrhagic Escherichia coli, enterotoxigenic E. coli, enteropathogenic E. coli, Shigella flexneri, and Salmonella enterica were converted to the culturable state by co-culture with selected eukaryotic cells, e.g., HT-29, Caco-2, T84, HeLa, Intestine 407, and CHO cells.
Keywords: conversion to culturability; enteric bacteria; viable but nonculturable

Deep Sequencing of the Oral Microbiome Reveals Signatures of Periodontal Disease - Liu,B.; Faller, L.L.; Klitgord, N.; Mazumdar, V.; Ghodsi,M.; Sommer, D.D.; Gibbons, T.R.; Treangen, T.J.; Chang, Y.C.; Li,S. (PloS one, 2012)
The oral microbiome, the complex ecosystem of microbes inhabiting the human mouth, harbors several thousands of bacterial types. The proliferation of pathogenic bacteria within the mouth gives rise to periodontitis, an inflammatory disease known to also constitute a risk factor for cardiovascular disease. While much is known about individual species associated with pathogenesis, the system-level mechanisms underlying the transition from health to disease are still poorly understood. Through the sequencing of the 16S rRNA gene and of whole community DNA we provide a glimpse at the global genetic, metabolic, and ecological changes associated with periodontitis in 15 subgingival plaque samples, four from each of two periodontitis patients, and the remaining samples from three healthy individuals. We also demonstrate the power of whole-metagenome sequencing approaches in characterizing the genomes of key players in the oral microbiome, including an unculturable TM7 organism. We reveal the disease microbiome to be enriched in virulence factors, and adapted to a parasitic lifestyle that takes advantage of the disrupted host homeostasis. Furthermore, diseased samples share a common structure that was not found in completely healthy samples, suggesting that the disease state may occupy a narrow region within the space of possible configurations of the oral microbiome. Our pilot study demonstrates the power of high-throughput sequencing as a tool for understanding the role of the oral microbiome in periodontal disease. Despite a modest level of sequencing (~2 lanes Illumina 76 bp PE) and high human DNA contamination (up to ~90%) we were able to partially reconstruct several oral microbes and to preliminarily characterize some systems-level differences between the healthy and diseased oral microbiomes.

Ecology of Vibrio parahaemolyticus and Vibrio vulnificus in the Coastal and Estuarine Waters of Louisiana, Maryland, Mississippi, and Washington (United States) - Johnson, Crystal N.; Bowers, John C.; Griffitt, Kimberly J.; Molina, Vanessa; Clostio, Rachel W.; Pei, Shaofeng; Laws, Edward; Paranjpye, Rohinee N.; Strom, Mark S.; Chen, Arlene; Hasan, Nur A.; Huq, Anwar; et al. (Applied and Environmental Microbiology, 2012)
Vibrio parahaemolyticus and Vibrio vulnificus, which are native to estuaries globally, are agents of seafood-borne or wound infections, both potentially fatal. Like all vibrios autochthonous to coastal regions, their abundance varies with changes in environmental parameters. Sea surface temperature (SST), sea surface height (SSH), and chlorophyll have been shown to be predictors of zooplankton and thus factors linked to vibrio populations. The contribution of salinity, conductivity, turbidity, and dissolved organic carbon to the incidence and distribution of Vibrio spp. has also been reported. Here, a multicoastal, 21-month study was conducted to determine relationships between environmental parameters and V. parahaemolyticus and V. vulnificus populations in water, oysters, and sediment in three coastal areas of the United States. Because ecologically unique sites were included in the study, it was possible to analyze individual parameters over wide ranges. Molecular methods were used to detect genes for thermolabile hemolysin (tlh), thermostable direct hemolysin (tdh), and tdh-related hemolysin (trh) as indicators of V. parahaemolyticus and the hemolysin gene vvhA for V. vulnificus. SST and suspended particulate matter were found to be strong predictors of total and potentially pathogenic V. parahaemolyticus and V. vulnificus. Other predictors included chlorophyll a, salinity, and dissolved organic carbon. For the ecologically unique sites included in the study, SST was confirmed as an effective predictor of annual variation in vibrio abundance, with other parameters explaining a portion of the variation not attributable to SST.

Efficient FMM accelerated vortex methods in three dimensions via the Lamb-Helmholtz decomposition - Gumerov, Nail A.; Duraiswami, Ramani (arXiv:1201.5430, 2012)
Vortex element methods are often used to efficiently simulate incompressible flows using Lagrangian techniques. Use of the FMM (Fast Multipole Method) allows considerable speed up of both velocity evaluation and vorticity evolution terms in these methods. Both equations require field evaluation of constrained (divergence free) vector valued quantities (velocity, vorticity) and cross terms from these. These are usually evaluated by performing several FMM accelerated sums of scalar harmonic functions. We present a formulation of the vortex methods based on the Lamb-Helmholtz decomposition of the velocity in terms of two scalar potentials. In its original form, this decomposition is not invariant with respect to translation, violating a key requirement for the FMM. One of the key contributions of this paper is a theory for translation for this representation. The translation theory is developed by introducing "conversion" operators, which enable the representation to be restored in an arbitrary reference frame. Using this form, extremely efficient vortex element computations can be made, which need evaluation of just two scalar harmonic FMM sums for evaluating the velocity and vorticity evolution terms. Details of the decomposition, translation and conversion formulae, and sample numerical results are presented.
Keywords: Computer Science - Numerical Analysis; Mathematical Physics; Physics - Computational Physics; Physics - Fluid Dynamics

Efficient Verification of Web-content Searching Through Authenticated Web Crawlers - Goodrich, Michael T.; Charalampos Papamanthou; Nguyen, Duy; Tamassia, Roberto; Lopes, Cristina Videira; Ohrimenko, Olga; Triandopoulos, Nikos (Proc. VLDB Endow., 2012)
We consider the problem of verifying the correctness and completeness of the result of a keyword search. We introduce the concept of an authenticated web crawler and present its design and prototype implementation. An authenticated web crawler is a trusted program that computes a specially-crafted signature over the web contents it visits. This signature enables (i) the verification of common Internet queries on web pages, such as conjunctive keyword searches---this guarantees that the output of a conjunctive keyword search is correct and complete; (ii) the verification of the content returned by such Internet queries---this guarantees that web data is authentic and has not been maliciously altered since the computation of the signature by the crawler. In our solution, the search engine returns a cryptographic proof of the query result. Both the proof size and the verification time are proportional only to the sizes of the query description and the query result, but do not depend on the number or sizes of the web pages over which the search is performed. As we experimentally demonstrate, the prototype implementation of our system provides a low communication overhead between the search engine and the user, and fast verification of the returned results by the user.

Face Identification Using Large Feature Sets - Schwartz, W.R.; Guo,Huimin; Choi,Jonghyun; Davis, Larry S. (Image Processing, IEEE Transactions on, 2012)
With the goal of matching unknown faces against a gallery of known people, the face identification task has been studied for several decades. There are very accurate techniques to perform face identification in controlled environments, particularly when large numbers of samples are available for each face. However, face identification under uncontrolled environments or with a lack of training data is still an unsolved problem. We employ a large and rich set of feature descriptors (with more than 70 000 descriptors) for face identification using partial least squares to perform multichannel feature weighting. Then, we extend the method to a tree-based discriminative structure to reduce the time required to evaluate probe samples. The method is evaluated on Facial Recognition Technology (FERET) and Face Recognition Grand Challenge (FRGC) data sets. Experiments show that our identification method outperforms current state-of-the-art results, particularly for identifying faces acquired across varying conditions.
Keywords: (mathematics); approximations; trees; challenge; data; data; tree-based; discriminative; environments; face; feature; FERET; FRGC; grand; identification; least; recognition; recognition; least; sets; face; sets; facial; squares; squares; training; structure; uncontrolled; task; face; technology; multichannel; weighting; partial

A framework for human microbiome research - Methé, B.A.; Nelson,K. E; Pop, Mihai; Creasy, H.H.; Giglio, M.G.; Huttenhower, C.; Gevers, D.; Petrosino, J.F.; Abubucker, S.; Badger, J.H. (Nature, 2012)
A variety of microbial communities and their genes (the microbiome) exist throughout the human body, with fundamental roles in human health and disease. The National Institutes of Health (NIH)-funded Human Microbiome Project Consortium has established a population-scale framework to develop metagenomic protocols, resulting in a broad range of quality-controlled resources and data including standardized methods for creating, processing and interpreting distinct types of high-throughput metagenomic data available to the scientific community. Here we present resources from a population of 242 healthy adults sampled at 15 or 18 body sites up to three times, which have generated 5,177 microbial taxonomic profiles from 16S ribosomal RNA genes and over 3.5 terabases of metagenomic sequence so far. In parallel, approximately 800 reference strains isolated from the human body have been sequenced. Collectively, these data represent the largest resource describing the abundance and variety of the human microbiome, while providing a framework for current and future studies.

Global secretome analysis identifies novel mediators of bone metastasis - Blanco, Mario Andres; LeRoy, Gary; Zia Khan; Alečković, Maša; Zee, Barry M.; Garcia, Benjamin A.; Kang, Yibin (Cell Research, 2012)
Bone is the one of the most common sites of distant metastasis of solid tumors. Secreted proteins are known to influence pathological interactions between metastatic cancer cells and the bone stroma. To comprehensively profile secreted proteins associated with bone metastasis, we used quantitative and non-quantitative mass spectrometry to globally analyze the secretomes of nine cell lines of varying bone metastatic ability from multiple species and cancer types. By comparing the secretomes of parental cells and their bone metastatic derivatives, we identified the secreted proteins that were uniquely associated with bone metastasis in these cell lines. We then incorporated bioinformatic analyses of large clinical metastasis datasets to obtain a list of candidate novel bone metastasis proteins of several functional classes that were strongly associated with both clinical and experimental bone metastasis. Functional validation of selected proteins indicated that in vivo bone metastasis can be promoted by high expression of (1) the salivary cystatins CST1, CST2, and CST4; (2) the plasminogen activators PLAT and PLAU; or (3) the collagen functionality proteins PLOD2 and COL6A1. Overall, our study has uncovered several new secreted mediators of bone metastasis and therefore demonstrated that secretome analysis is a powerful method for identification of novel biomarkers and candidate therapeutic targets.
Keywords: bone; cancer; metastasis; proteomics; secretome

Gradient-based Image Recovery Methods from Incomplete Fourier Measurements - Patel, Vishal M.; Maleh,R.; Gilbert,A. C; Chellapa, Rama (IEEE Transactions on Image Processing, 2012)
A major problem in imaging applications such as Magnetic Resonance Imaging (MRI) and Synthetic Aperture Radar (SAR) is the task of trying to reconstruct an image with the smallest possible set of Fourier samples, every single one of which has a potential time and/or power cost. The theory of Compressive Sensing (CS) points to ways of exploiting inherent sparsity in such images in order to achieve accurate recovery using sub- Nyquist sampling schemes. Traditional CS approaches to this problem consist of solving total-variation minimization programs with Fourier measurement constraints or other variations thereof. This paper takes a different approach: Since the horizontal and vertical differences of a medical image are each more sparse or compressible than the corresponding total-variational image, CS methods will be more successful in recovering these differences individually. We develop an algorithm called GradientRec that uses a CS algorithm to recover the horizontal and vertical gradients and then estimates the original image from these gradients. We present two methods of solving the latter inverse problem: one based on least squares optimization and the other based on a generalized Poisson solver. After a thorough derivation of our complete algorithm, we present the results of various experiments that compare the effectiveness of the proposed method against other leading methods.
Keywords: Compressed sensing; Fourier transforms; Image coding; Image edge detection; Image reconstruction; L1–minimization; minimization; Noise measurement; OPTIMIZATION; Poisson solver; Sparse recovery; Total variation; TV

Gripper synthesis for indirect manipulation of cells using Holographic Optical Tweezers - Chowdhury,Sagar; Svec,Petr; Wang,Chenlu; Losert,Wolfgang; Gupta, Satyandra K. (2012)
Optical Tweezers (OT) are used for highly accurate manipulations of biological cells. However, the direct exposure of cells to focused laser beam may negatively influence their biological functions. In order to overcome this problem, we generate multiple optical traps to grab and move a 3D ensemble of inert particles such as silica microspheres to act as a reconfigurable gripper for a manipulated cell. The relative positions of the microspheres are important in order for the gripper to be robust against external environmental forces and the exposure of high intensity laser on the cell to be minimized. In this paper, we present results of different gripper configurations, experimentally tested using our OT setup, that provide robust gripping as well as minimize laser intensity experienced by the cell. We developed a computational approach that allowed us to perform preliminary modeling and synthesis of the gripper configurations. The gripper synthesis is cast as a multi-objective optimization problem.

InterPro in 2011: new developments in the family and domain prediction database. - Hunter, Sarah; Jones, Philip; Mitchell, Alex; Apweiler, Rolf; Attwood, Teresa K; Bateman, Alex; Bernard, Thomas; Binns, David; Bork, Peer; Burge, Sarah; de Castro, Edouard; Coggill, Penny; et al. (Nucleic Acids Res, 2012)
InterPro (http://www.ebi.ac.uk/interpro/) is a database that integrates diverse information about protein families, domains and functional sites, and makes it freely available to the public via Web-based interfaces and services. Central to the database are diagnostic models, known as signatures, against which protein sequences can be searched to determine their potential function. InterPro has utility in the large-scale analysis of whole genomes and meta-genomes, as well as in characterizing individual protein sequences. Herein we give an overview of new developments in the database and its associated software since 2009, including updates to database content, curation processes and Web and programmatic interfaces.
Keywords: Databases, Protein; Protein Structure, Tertiary; Proteins; Sequence Analysis, Protein; software; Terminology as Topic; User-Computer Interface

Vibrio cholerae in a historically cholera-free country - Haley, Bradd J.; Chen, Arlene; Grim, Christopher J.; Clark, Philip; Diaz, Celia M; Taviani, Elisa; Hasan, Nur A.; Sancomb, Elizabeth; Elnemr, Wessam M; Islam, Muhammad A.; Huq, Anwar; Rita R Colwell; et al. (Environmental Microbiology Reports, 2012)
We report the autochthonous existence of Vibrio cholerae in coastal waters of Iceland, a geothermally active country where cholera is absent and has never been reported. Seawater, mussel and macroalgae samples were collected close to, and distant from, sites where geothermal activity causes a significant increase in water temperature during low tides. Vibrio cholerae was detected only at geothermal‐influenced sites during low‐tides. None of the V. cholerae isolates encoded cholera toxin (ctxAB) and all were non‐O1/non‐O139 serogroups. However, all isolates encoded other virulence factors that are associated with cholera as well as extra‐intestinal V. cholerae infections. The virulence factors were functional at temperatures of coastal waters of Iceland, suggesting an ecological role. It is noteworthy that V. cholerae was isolated from samples collected at sites distant from anthropogenic influence, supporting the conclusion that V. cholerae is autochthonous to the aquatic environment of Iceland.

Linguistic Resources for Handwriting Recognition and Translation Evaluation - Song, Zhiyi; Ismael, Safa; Grimes, Stephen; David Doermann; Strassel,Stephanie (Eight International Conference on Language Resources and Evaluation (LREC'12), 2012)

Making Recommendations in a Microblog to Improve the Impact of a Focal User - Wu,Shanchan; Gong, Leanna; Rand, William; Raschid, Louiqa (6th ACM Conference on Recommender Systems (RecSys), 2012)
We present a microblog recommendation system that can help monitor users, track conversations, and potentially improve diffusion impact. Given a Twitter network of active users and their followers, and historical activity of tweets, retweets and mentions, we build upon a prediction tool to predict the Top K users who will retweet or mention a focal user, in the future [10]. We develop personalized recommendations for each focal user. We identify characteristics of focal users such as the size of the follower network, or the level of sentiment averaged over all tweets; both have an impact on the quality of personalized recommendations. We use (high) betweenness centrality as a proxy of attractive users to target when making recommendations. Our recommendations successfully identify a greater fraction of users with higher betweenness centrality, in comparison to the overall distribution of betweenness centrality of the ground truth users for some focal user.

Organizing User Search Histories - Hwang,Heasoo; Lauw,H. W; Getoor, Lise; Ntoulas,A. (Knowledge and Data Engineering, IEEE Transactions on, 2012)
Users are increasingly pursuing complex task-oriented goals on the web, such as making travel arrangements, managing finances, or planning purchases. To this end, they usually break down the tasks into a few codependent steps and issue multiple queries around these steps repeatedly over long periods of time. To better support users in their long-term information quests on the web, search engines keep track of their queries and clicks while searching online. In this paper, we study the problem of organizing a user's historical queries into groups in a dynamic and automated fashion. Automatically identifying query groups is helpful for a number of different search engine components and applications, such as query suggestions, result ranking, query alterations, sessionization, and collaborative search. In our approach, we go beyond approaches that rely on textual similarity or time thresholds, and we propose a more robust approach that leverages search query logs. We experimentally study the performance of different techniques, and showcase their potential, especially when combined together.
Keywords: alteration; query; analysis; user; engines; search; engines; text; goal; textual; group; historical; History; identification; query; information; interfaces; log; sessionization; task-oriented; organization; query; processing; search; query; query; user; quest; query; ranking; search; search; search; long-term; similarity; time; suggestion; result; threshold; user; Web; collaborative

Privacy in Social Networks - Zheleva,E.; Terzi,E.; Getoor, Lise (Synthesis Lectures on Data Mining and Knowledge Discovery, 2012)

Role of GbpA protein, an important virulence-related colonization factor, for Vibrio cholerae's survival in the aquatic environment - Stauder, Monica; Huq, Anwar; Pezzati, Elisabetta; Grim, Christopher J.; Ramoino, Paola; Pane, Luigi; Rita R Colwell; Pruzzo, Carla; Vezzulli, Luigi (Environmental Microbiology Reports, 2012)
Vibrio cholerae N‐acetyl glucosamine‐binding protein A (GbpA) is a chitin binding protein and a virulence factor involved in the colonization of human intestine. We investigated the distribution and genetic variations of gbpA in 488 V. cholerae strains of environmental and clinical origin, belonging to different serogroups and biotypes. We found that the gene is consistently present and highly conserved including an environmental V. cholerae‐related strain of ancestral origin. The gene was also consistently expressed in a number of representative V. cholerae strains cultured in laboratory aquatic microcosms under conditions simulating those found in temperate marine environments. Functional analysis carried out on V. cholerae O1 El Tor N16961 showed that GbpA is not involved in adhesion to inorganic surfaces but promotes interaction with environmental biotic substrates (plankton and bivalve hepatopancreas cells) representing known marine reservoir or host for the bacterium. It is suggested that the ability of GbpA to colonize human intestinal cells most probably originated from its primary function in the aquatic environment.

Rpn1 and Rpn2 coordinate ubiquitin processing factors at the proteasome - Rosenzweig,Rina; Bronner,Vered; Zhang,Daoning; Fushman, David; Glickman,Michael H. (Journal of Biological ChemistryJ. Biol. Chem., 2012)
Substrates tagged with (poly)ubiquitin for degradation can be targeted directly to the 26S proteasome where they are proteolysed. Independently, ubiquitin-conjugates may also be delivered by bivalent shuttles. The majority of shuttles attach to the proteasome through a ubiquitin-like domain (UBL) while anchoring cargo at a C-terminal polyubiquitin-binding domain(s). We found that two shuttles of this class, Rad23 and Dsk2, dock at two different receptors embedded within a single subunit of the 19S proteasome regulatory particle (RP), Rpn1. Their association/dissociation constants and affinities for Rpn1 are similar. In contrast, another UBL-containing protein, the deubiquitinase Ubp6, is also anchored by Rpn1, yet dissociates slower, thus behaving as a sometimes proteasome subunit distinct from transiently-associated shuttles. Two neighboring subunits, Rpn10 and Rpn13, show a marked preference for polyubiquitin over UBLs. Rpn10 attaches to the central solenoid portion of Rpn1 although this association is stabilized by the presence of a third subunit, Rpn2. Rpn13 binds directly to the C-terminal portion of Rpn2. These intrinsic polyubiquitin receptors may compete with substrate shuttles for their polyubiquitin-conjugates, thereby aiding release of the emptied shuttles. By binding multiple ubiquitin-processing factors simultaneously, Rpn1 is uniquely suited to coordinate substrate recruitment, deubiquitination, and movement towards the catalytic core. The broad range of affinities for ubiquitin, ubiquitin-like, and non-ubiquitin signals by adjacent yet non-overlapping sites all within the Base illustrates a hub of activity that coordinates the intricate relay of substrates within the proteasome, and consequently influences substrate residency time and commitment to degradation.
Keywords: deubiquitination; Proteasome; solenoid; Surface plasmon resonance (SPR); ubiquitin; Ubiquitin-dependent protease

Speeding Up Particle Trajectory Simulations under Moving Force Fields using GPUs - Patro,R.; Dickerson,J. P.; Bista,S.; Gupta,S.K.; Varshney, Amitabh (Journal of Computing and Information Science in Engineering, 2012)
In this paper, we introduce a GPU-based framework forsimulating particle trajectories under both static and dynamic force fields. By exploiting the highly parallel nature of the problem and making efficient use of the available hardware, our simulator exhibits a significant speedup over its CPU- based analog. We apply our framework to a specific experi- mental simulation: the computation of trapping probabilities associated with micron-sized silica beads in optical trapping workbenches. When evaluating large numbers of trajectories (4096), we see approximately a 356 times speedup of the GPU-based simulator over its CPU-based counterpart.

Structure, function and diversity of the healthy human microbiome - Huttenhower, C.; Gevers, D.; Knight,R.; Abubucker, S.; Badger, J.H.; Chinwalla, A.T.; Creasy, H.H.; Earl, A.M.; Fitzgerald, M.G.; Fulton, R.S.; others (Nature, 2012)
Studies of the human microbiome have revealed that even healthy individuals differ remarkably in the microbes that occupy habitats such as the gut, skin and vagina. Much of this diversity remains unexplained, although diet, environment, host genetics and early microbial exposure have all been implicated. Accordingly, to characterize the ecology of human-associated microbial communities, the Human Microbiome Project has analysed the largest cohort and set of distinct, clinically relevant body habitats so far. We found the diversity and abundance of each habitat’s signature microbes to vary widely even among healthy subjects, with strong niche specialization both within and among individuals. The project encountered an estimated 81–99% of the genera, enzyme families and community configurations occupied by the healthy Western microbiome. Metagenomic carriage of metabolic pathways was stable among individuals despite variation in community structure, and ethnic/racial background proved to be one of the strongest associations of both pathways and microbes with clinical metadata. These results thus delineate the range of structural and functional configurations normal in the microbial communities of a healthy population, enabling future characterization of the epidemiology, ecology and translational applications of the human microbiome.

Sub-cellular feature detection and automated extraction of collocalized actin and myosin regions - Martineau, Justin; Mokashi,Ronil; Chapman, David; Grasso, Michael; Brady,Mary; Yesha,Yelena; Yesha,Yaacov; Cardone, Antonio; Dima, Alden (the 2nd ACM SIGHIT symposiumProceedings of the 2nd ACM SIGHIT symposium on International health informatics - IHI '12, 2012)

TACI: Taxonomy-Aware Catalog Integration - Papadimitriou,P.; Tsaparas,P.; Fuxman,A.; Getoor, Lise (IEEE Transactions on Knowledge and Data Engineering (TKDE), 2012)
A fundamental data integration task faced by online commercial portals and commerce search engines is the integration of products coming from multiple providers to their product catalogs. In this scenario, the commercial portal has its own taxonomy (the “master taxonomy”), while each data provider organizes its products into a different taxonomy (the “provider taxonomy”). In this paper, we consider the problem of categorizing products from the data providers into the master taxonomy, while making use of the provider taxonomy information. Our approach is based on a taxonomy-aware processing step that adjusts the results of a text-based classifier to ensure that products that are close together in the provider taxonomy remain close in the master taxonomy. We formulate this intuition as a structured prediction optimization problem. To the best of our knowledge, this is the first approach that leverages the structure of taxonomies in order to enhance catalog integration. We propose algorithms that are scalable and thus applicable to the large datasets that are typical on the Web. We evaluate our algorithms on real-world data and we show that taxonomy-aware classification provides a significant improvement over existing approaches.

Two-server password-only authenticated key exchange - Katz, Jonathan; MacKenzie,Philip; Taban,Gelareh; Gligor,Virgil (Journal of Computer and System Sciences, 2012)
Typical protocols for password-based authentication assume a single server that stores all the information (e.g., the password) necessary to authenticate a user. An inherent limitation of this approach, assuming low-entropy passwords are used, is that the userʼs password is exposed if this server is ever compromised. To address this issue, it has been suggested to share a userʼs password information among multiple servers, and to have these servers cooperate (possibly in a threshold manner) when the user wants to authenticate. We show here a two-server version of the password-only key-exchange protocol of Katz, Ostrovsky, and Yung (the KOY protocol). Our work gives the first secure two-server protocol for the password-only setting (in which the user need remember only a password, and not the serversʼ public keys), and is the first two-server protocol (in any setting) with a proof of security in the standard model. Our work thus fills a gap left by the work of MacKenzie et al. (2006) [31] and Di Raimondo and Gennaro (2006) [16]. As an additional benefit of our work, we show modifications that improve the efficiency of the original KOY protocol.
Keywords: Key-exchange protocols; passwords

Verifying Search Results Over Web Collections - Goodrich, Michael T.; Nguyen, Duy; Ohrimenko, Olga; Charalampos Papamanthou; Tamassia, Roberto; Triandopoulos, Nikos; Lopes, Cristina Videira (arXiv:1204.5446 [cs], 2012)
Searching accounts for one of the most frequently performed computations over the Internet as well as one of the most important applications of outsourced computing, producing results that critically affect users' decision-making behaviors. As such, verifying the integrity of Internet-based searches over vast amounts of web contents is essential. We provide the first solution to this general security problem. We introduce the concept of an authenticated web crawler and present the design and prototype implementation of this new concept. An authenticated web crawler is a trusted program that computes a special "signature" $s$ of a collection of web contents it visits. Subject to this signature, web searches can be verified to be correct with respect to the integrity of their produced results. This signature also allows the verification of complicated queries on web pages, such as conjunctive keyword searches. In our solution, along with the web pages that satisfy any given search query, the search engine also returns a cryptographic proof. This proof, together with the signature $s$, enables any user to efficiently verify that no legitimate web pages are omitted from the result computed by the search engine, and that no pages that are non-conforming with the query are included in the result. An important property of our solution is that the proof size and the verification time both depend solely on the sizes of the query description and the query result, but not on the number or sizes of the web pages over which the search is performed. Our authentication protocols are based on standard Merkle trees and the more involved bilinear-map accumulators. As we experimentally demonstrate, the prototype implementation of our system gives a low communication overhead between the search engine and the user, and allows for fast verification of the returned results on the user side.
Keywords: Computer Science - Cryptography and Security

You'Re Capped: Understanding the Effects of Bandwidth Caps on Broadband Use in the Home - Marshini Chetty; Banks, Richard; Brush, A.J.; Donner, Jonathan; Grinter, Rebecca (SIGCHI '12, 2012)
Bandwidth caps, a limit on the amount of data users can upload and download in a month, are common globally for both home and mobile Internet access. With caps, each bit of data consumed comes at a cost against a monthly quota or a running tab. Yet, relatively little work has considered the implications of this usage-based pricing model on the user experience. In this paper, we present results from a qualitative study of households living with bandwidth caps. Our findings suggest home users grapple with three uncertainties regarding their bandwidth usage: invisible balances, mysterious processes, and multiple users. We discuss how these uncertainties impact their usage and describe the potential for better tools to help monitor and manage data caps. We conclude that as a community we need to cater for users under Internet cost constraints.
Keywords: Bandwidth; bandwidth cap; data cap; Internet; metered use; pricing; usage-based billing; usage-based pricing

Ability-based design: Concept, principles and examples - Wobbrock,J.O.; Kane,S.K.; Gajos,K.Z.; Harada,S.; Jon Froehlich (ACM Transactions on Accessible Computing (TACCESS), 2011)

Accurate and fast estimation of taxonomic profiles from metagenomic shotgun sequences - Liu,Bo; Gibbons,Theodore; Ghodsi,Mohammad; Treangen,Todd; Pop, Mihai (BMC Genomics, 2011)
A major goal of metagenomics is to characterize the microbial composition of an environment. The most popular approach relies on 16S rRNA sequencing, however this approach can generate biased estimates due to differences in the copy number of the gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from metagenomic shotgun sequencing data by matching individual reads against a database of reference sequences. One major limitation of prior computational methods used for this purpose is the use of a universal classification threshold for all genes at all taxonomic levels.

Active inference for retrieval in camera networks - Daozheng Chen; Bilgic,Mustafa; Getoor, Lise; Jacobs, David W.; Mihalkova,Lilyana; Tom Yeh (Person-Oriented Vision (POV), 2011 IEEE Workshop on, 2011)
We address the problem of searching camera network videos to retrieve frames containing specified individuals. We show the benefit of utilizing a learned probabilistic model that captures dependencies among the cameras. In addition, we develop an active inference framework that can request human input at inference time, directing human attention to the portions of the videos whose correct annotation would provide the biggest performance improvements. Our primary contribution is to show that by mapping video frames in a camera network onto a graphical model, we can apply collective classification and active inference algorithms to significantly increase the performance of the retrieval system, while minimizing the number of human annotations required.

Active inference for retrieval in camera networks - Daozheng Chen; Bilgic,M.; Getoor, Lise; Jacobs, David W.; Mihalkova,L.; Tom Yeh (Person-Oriented Vision (POV), 2011 IEEE Workshop on, 2011)
We address the problem of searching camera network videos to retrieve frames containing specified individuals. We show the benefit of utilizing a learned probabilistic model that captures dependencies among the cameras. In addition, we develop an active inference framework that can request human input at inference time, directing human attention to the portions of the videos whose correct annotation would provide the biggest performance improvements. Our primary contribution is to show that by mapping video frames in a camera network onto a graphical model, we can apply collective classification and active inference algorithms to significantly increase the performance of the retrieval system, while minimizing the number of human annotations required.
Keywords: active; annotation; probabilistic; frame; cameras; inference; inference; camera; mechanisms; probability; search; model; human; model; retrieval; network; graphical; problem; video; problems; video; processing; retrieval; video; signal; system; searching

Active progress bars: facilitating the switch to temporary activities - Hurter,Christophe; Girouard,Audrey; Riche,Nathalie; Plaisant, Catherine (Proceedings of the 2011 annual conference extended abstracts on Human factors in computing systems, 2011)
In this paper, we seek to find a better way of effective task management when a progress bar interrupts user's primary activity. We propose to augment progress bars with user controlled functionalities facilitating the switch to temporary activities. We detail a taxonomy of waiting period contexts and possible temporary tasks, then report on 5 participatory design, and a follow-up survey of 96 respondents. Finally we describe an early prototype of active progress bars, and report on initial use.
Keywords: Frustration; participatory design; progress bars; task switching

Active Surveying: A Probabilistic Approach for Identifying Key Opinion Leaders - Sharara,H.; Getoor, Lise; Norton,M. (Twenty-Second International Joint Conference on Artificial Intelligence, 2011)
Opinion leaders play an important role in influenc- ing people’s beliefs, actions and behaviors. Al- though a number of methods have been proposed for identifying influentials using secondary sources of information, the use of primary sources, such as surveys, is still favored in many domains. In this work we present a new surveying method which combines secondary data with partial knowl- edge from primary sources to guide the information gathering process. We apply our proposed active surveying method to the problem of identifying key opinion leaders in the medical field, and show how we are able to accurately identify the opinion lead- ers while minimizing the amount of primary data required, which results in significant cost reduction in data acquisition without sacrificing its integrity.

Adaptively secure broadcast, revisited - Garay,J. A; Katz, Jonathan; Kumaresan,R.; Zhou,H.S. (Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011)
We consider the classical problem of synchronous broadcast with dishonest majority, whena public-key infrastructure and digital signatures are available. In a surprising result, Hirt and Zikas (Eurocrypt 2010) recently observed that all existing protocols for this task are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. Moreover, they prove an impossibility result for adaptively secure broadcast in their setting. We argue that the communication model adopted by Hirt and Zikas is unrealistically pes- simistic. We revisit the problem of adaptively secure broadcast in a more natural synchronous model (with rushing), and show that broadcast is possible in this setting for an arbitrary num- ber of corruptions. Our positive result holds under a strong, simulation-based definition in the universal-composability framework. We also study the impact of adaptive attacks on protocols for secure multi-party computation where broadcast is used as a sub-routine.

Analyzing Incident Management Event Sequences with Interactive Visualization - Guerra Gómez,J.; Wongsuphasawat,K.; Wang,T. D; Pack,M.; Plaisant, Catherine (Transportation Research Board 90th Annual Meeting Compendium of Papers, 2011)
While traditional safety and incident analysis has mostly focused on incident attributesdata, such as the location and time of the incident, there are other aspects in incident response that are temporal in nature and are more difficult to analyze. We describe a visual analytics tool for temporal data exploration, called LifeFlow, used for the analysis of incident response data. LifeFlow provides user-controlled overviews of event sequences (e.g. notification, arrival, clearance etc). It allows analysts to interactively explore temporal patterns, find anomalies in sequences and compare management practices. This type of analysis can potentially lead to process improvements and save human lives. We used NCHRP traffic incident data with more than 200,000 incidents are reported by 8 different agencies in a period of about 28 months. Our experience suggest that even non expert analysts can spot many anomalies in the data using the LifeFlow overviews, and are able to rapidly ask many questions and find differences between agencies.

Aquatic Realm and Cholera - Huq,A.; Grim,C. J.; Rita R Colwell (Epidemiological and Molecular Aspects on Cholera, 2011)
Cholera is an ancient disease that can be severe and life threatening. It occurs predominantly in areas of the world where populations lack safe drinking water. Epidemics of cholera are linked with malnutrition, poor sanitation, and conditions resulting from natural disasters such as severe flooding. According to a report published by WHO in 2000 [1], cholera remains a major public health problem and is becoming increasingly important since the number of countries in which cholera is endemic continues to increase. Unfortunately, outbreaks of the disease continue into the twenty-first century with ominous portent in the wake of global climate change [1]. Yet cholera is a preventable disease if people have access to safe drinking water and are properly educated how to protect themselves from the risk of infection with vibrios. Cholera also is an easily treatable disease. Oral rehydration therapy, a solution containing glucose and appropriate salts, has proven to be effective for treatment of most cholera victims [2]. Nevertheless, each year, tens of thousands of people are victims of the disease, bringing this “curse of humankind” to modern civilization. Present understanding of cholera is based on studies conducted over the past three decades and significant new information has been gained concerning environmental factors associated with this disease, especially how to detect the bacterium and where it lives in the natural environment, outside the human gut, and what triggers the annual outbreaks that occur with remarkable regularity. Environmental research on Vibrio cholerae and cholera has provided insights for prediction and prevention of the disease it causes, while the race for effective vaccines against cholera continues.

Architecting for innovation - Koponen,Teemu; Shenker,Scott; Balakrishnan,Hari; Feamster, Nick; Ganichev,Igor; Ghodsi,Ali; Godfrey,P. Brighten; McKeown,Nick; Parulkar,Guru; Raghavan,Barath; Rexford,Jennifer; Arianfar,Somaya; et al. (SIGCOMM Comput. Commun. Rev., 2011)
We argue that the biggest problem with the current Internet architecture is not a particular functional deficiency, but its inability to accommodate innovation. To address this problem we propose a minimal architectural "framework" in which comprehensive architectures can reside. The proposed Framework for Internet Innovation (FII) --- which is derived from the simple observation that network interfaces should be extensible and abstract --- allows for a diversity of architectures to coexist, communicate, and evolve. We demonstrate FII's ability to accommodate diversity and evolution with a detailed examination of how information flows through the architecture and with a skeleton implementation of the relevant interfaces.
Keywords: diversity; Evolution; innovation; internet architecture

An assessment of systems and software engineering scholars and institutions (2003–2007 and 2004–2008) - Wong,W. Eric; Tse,T.H.; Glass,Robert L.; Basili, Victor R.; Chen,T.Y. (Journal of Systems and Software, 2011)
An ongoing, annual survey of publications in systems and software engineering identifies the top 15 scholars and institutions in the field over a 5-year period. Each ranking is based on the weighted scores of the number of papers published in TSE, TOSEM, JSS, SPE, EMSE, IST, and Software of the corresponding period. This report summarizes the results for 2003–2007 and 2004–2008. The top-ranked institution is Korea Advanced Institute of Science and Technology, Korea for 2003–2007, and Simula Research Laboratory, Norway for 2004–2008, while Magne Jørgensen is the top-ranked scholar for both periods.
Keywords: Research publications; Systems and software engineering; Top institutions; Top scholars

Automated Planning Logic Synthesis for Autonomous Unmanned Vehicles in Competitive Environments with Deceptive Adversaries - Svec,Petr; Gupta, Satyandra K. (New Horizons in Evolutionary Robotics, 2011)
We developed a new approach for automated synthesis of a planning logic for autonomous unmanned vehicles. This new approach can be viewed as an automated iterative process during which an initial version of a logic is synthesized and then gradually improved by detecting and fixing its shortcomings. This is achieved by combining data mining for extraction of vehicle’s states of failure and Genetic Programming (GP) technique for synthesis of corresponding navigation code. We verified the feasibility of the approach using unmanned surface vehicles (USVs) simulation. Our focus was specifically on the generation of a planning logic used for blocking the advancement of an intruder boat towards a valuable target. Developing autonomy logic for this behavior is challenging as the intruder’s attacking logic is human-competitive with deceptive behavior so the USV is required to learn specific maneuvers for specific situations to do successful blocking. We compared the performance of the generated blocking logic to the performance of logic that was manually implemented. Our results show that the new approach was able to synthesize a blocking logic with performance closely approaching the performance of the logic coded by hand.
Keywords: engineering

Boosting the scalability of botnet detection using adaptive traffic sampling - Zhang,Junjie; Luo,Xiapu; Perdisci,Roberto; Gu,Guofei; Lee,Wenke; Feamster, Nick (Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security, 2011)
Botnets pose a serious threat to the health of the Internet. Most current network-based botnet detection systems require deep packet inspection (DPI) to detect bots. Because DPI is a computational costly process, such detection systems cannot handle large volumes of traffic typical of large enterprise and ISP networks. In this paper we propose a system that aims to efficiently and effectively identify a small number of suspicious hosts that are likely bots. Their traffic can then be forwarded to DPI-based botnet detection systems for fine-grained inspection and accurate botnet detection. By using a novel adaptive packet sampling algorithm and a scalable spatial-temporal flow correlation approach, our system is able to substantially reduce the volume of network traffic that goes through DPI, thereby boosting the scalability of existing botnet detection systems. We implemented a proof-of-concept version of our system, and evaluated it using real-world legitimate and botnet-related network traces. Our experimental results are very promising and suggest that our approach can enable the deployment of botnet-detection systems in large, high-speed networks.
Keywords: adaptive sampling; botnet; intrusion detection; NETWORK SECURITY

A Canonical Form for Testing Boolean Function Properties - Dana Dachman-Soled; Servedio, Rocco A. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011)
In a well-known result Goldreich and Trevisan (2003) showed that every testable graph property has a “canonical” tester in which a set of vertices is selected at random and the edges queried are the complete graph over the selected vertices. We define a similar-in-spirit canonical form for Boolean function testing algorithms, and show that under some mild conditions property testers for Boolean functions can be transformed into this canonical form. Our first main result shows, roughly speaking, that every “nice” family of Boolean functions that has low noise sensitivity and is testable by an “independent tester,” has a canonical testing algorithm. Our second main result is similar but holds instead for families of Boolean functions that are closed under ID-negative minors. Taken together, these two results cover almost all of the constant-query Boolean function testing algorithms that we know of in the literature, and show that all of these testing algorithms can be automatically converted into a canonical form.
Keywords: Algorithm Analysis and Problem Complexity; Boolean functions; Computation by Abstract Devices; Computer Communication Networks; Computer Graphics; Data structures; Discrete Mathematics in Computer Science; property testing

A Case Study in Optimization of Gait and Physical Parameters for a Snake-Inspired Robot Based on a Rectilinear Gait - Hopkins,James K.; Spranklin,Brent W.; Gupta, Satyandra K. (Journal of mechanisms and robotics, 2011)
Physical parameters of the constituent modules and gait parameters affect the overall performance of snake-inspired robots. Hence, a system-level optimization model needs to concurrently optimize the module parameters and the gait. Incorporating a physics-based model of rectilinear gaits in the system-level optimization model is a computationally challenging problem. This paper presents a case study to illustrate how metamodels of the precomputed optimal rectilinear gaits can be utilized to reduce the complexity of the system-level optimization model. An example is presented to illustrate the importance of concurrently optimizing the module parameters and the gait to obtain the optimal performance for a given mission.

Collective graph identification - Namata,Galileo Mark; Kok,Stanley; Getoor, Lise (Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, 2011)
Data describing networks (communication networks, transaction networks, disease transmission networks, collaboration networks, etc.) is becoming increasingly ubiquitous. While this observational data is useful, it often only hints at the actual underlying social or technological structures which give rise to the interactions. For example, an email communication network provides useful insight but is not the same as the "real" social network among individuals. In this paper, we introduce the problem of graph identification, i.e., the discovery of the true graph structure underlying an observed network. We cast the problem as a probabilistic inference task, in which we must infer the nodes, edges, and node labels of a hidden graph, based on evidence provided by the observed network. This in turn corresponds to the problems of performing entity resolution, link prediction, and node labeling to infer the hidden graph. While each of these problems have been studied separately, they have never been considered together as a coherent task. We present a simple yet novel approach to address all three problems simultaneously. Our approach, called C3, consists of Coupled Collective Classifiers that are iteratively applied to propagate information among solutions to the problems. We empirically demonstrate that C3 is superior, in terms of both predictive accuracy and runtime, to state-of-the-art probabilistic approaches on three real-world problems.
Keywords: collective classification; entity resolution; link prediction; semi-supervised learning

Complete Fairness in Secure Two-Party Computation - Gordon,S. Dov; Hazay,Carmit; Katz, Jonathan; Lindell,Yehuda (Journal of the ACM, 2011)
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting. We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.
Keywords: cryptography; fairness; secure computation

A computational framework for authoring and searching product design specifications - Weissman,Alexander; Petrov,Martin; Gupta, Satyandra K. (Advanced Engineering Informatics, 2011)
The development of product design specifications (PDS) is an important part of the product development process. Incompleteness, ambiguity, or inconsistency in the PDS can lead to problems during the design process and may require unnecessary design iterations. This generally results in increased design time and cost. Currently, in many organizations, PDS are written using word processors. Since documents written by different authors can be inconsistent in style and word choice, it is difficult to automatically search for specific requirements. Moreover, this approach does not allow the possibility of automated design verification and validation against the design requirements and specifications.In this paper, we present a computational framework and a software tool based on this framework for writing, annotating, and searching computer-interpretable PDS. Our approach allows authors to write requirement statements in natural language to be consistent with the existing authoring practice. However, using mathematical expressions, keywords from predefined taxonomies, and other metadata the author of PDS can then annotate different parts of the requirement statements. This approach provides unambiguous meaning to the information contained in PDS, and helps to eliminate mistakes later in the process when designers must interpret requirements. Our approach also enables users to construct a new PDS document from the results of the search for requirements of similar devices and in similar contexts. This capability speeds up the process of creating PDS and helps authors write more detailed documents by utilizing previous, well written PDS documents. Our approach also enables checking for internal inconsistencies in the requirement statements.
Keywords: Engineering design; Product design specifications; Requirements engineering

Countering Botnets: Anomaly-Based Detection, Comprehensive Analysis, and Efficient Mitigation - Lee,Wenke; Dagon,David; Giffin,Jon; Feamster, Nick; Ollman,Gunter; Westby,Jody; Wesson,Rick; Vixie,Paul (GEORGIA TECH RESEARCH CORP ATLANTA, 2011)
We cover five general areas: (1) botnet detection, (2) botnet analysis, (3) botnet mitigation, (4) add-on tasks to the original contract, including the Conficker Working Group Lessons Learned, Layer-8 Exploration of Botnet Organization, and DREN research, and (5) commercialization in this paper. We have successfully developed new botnet detection and analysis capabilities in this project. These algorithms have been evaluated using real-world data, and have been put into actual, deployed systems. The most significant technical developments include a new dynamic reputation systems for DNS domains, a scalable anomaly detection system for botnet detection in very large network, and a transparent malware analysis system. In addition, on several occasions we have used our botnet data and analysis to help law enforcement agencies arrest botmasters. We also have had great success transitioning technologies to commercial products that are now used by government agencies, ISPs, and major corporations.
Keywords: *ELECTRONIC SECURITY; *INFORMATION SECURITY; *INTERNET; *INTRUSION DETECTION(COMPUTERS); algorithms; BGP ROUTE INJECTION; BGP(BORDER GATEWAY PROTOCOLS); BOTNET DETECTION; BOTNET TRACEBACK AND ATTRIBUTION; BOTNETS(MALWARE); CLIENT SERVER SYSTEMS; COMMUNICATIONS PROTOCOLS; COMPUTER PROGRAMMING AND SOFTWARE; COMPUTER SYSTEMS MANAGEMENT AND STANDARDS; CYBER ATTACKS; CYBER SECURITY; CYBERNETICS; CYBERTERRORISM; CYBERWARFARE; DATA PROCESSING SECURITY; DNS BASED MONITORING; DNS BASED REDIRECTION; DNS(DOMAIN NAME SYSTEMS); INFORMATION SCIENCE; INTERNET BROWSERS; ISP(INTERNET SERVICE PROVIDERS); MALWARE; MALWARE ANALYSIS; Online Systems; WUAFRLDHS1BOTN

Dataflow-Based Implementation of Layered Sensing Applications - Bhattacharyya, Shuvra S.; Chung-Ching Shen; Plishker,William; Sane, Nimish; Wu, Hsiang-Huang; Gu, Ruirui (2011)
This report describes a new dataflow-based technology and associated design tools for high-productivity design, analysis, and optimization of layered sensing software for signal processing systems. Our approach provides novel capabilities, based on the principles of task-level dataflow analysis, for exploring and optimizing interactions across application behavior; operational context; high performance embedded processing platforms, and implementation constraints. Particularly, we introduce and deliver novel software tools, called the targeted dataflow interchange format (TDIF) and Dataflow Interchange Format Markup Language (DIFML), for design and implementation of layered sensing and signal processing systems. The TDIF-CUDA (Compute Unified Device Architecture) environment is a graphics processing unit targeted software synthesis tool that provides a unique integration of dynamic dataflow modeling; retargetable actor construction; software synthesis; and instrumentation-based schedule evaluation and tuning. The DIFML package is a software package for the DIFML format, which is an Extensible Markup Language (XML)-based format for exchanging information between DIF and other tools.
Keywords: *COMPUTER AIDED DESIGN; *DATA FUSION; *DATAFLOW; *LAYERS; *SOFTWARE TOOLS; COMPUTER PROGRAMMING AND SOFTWARE; DETECTION; High performance computing; LAYERED SENSING; OPTIMIZATION; Signal processing; synthesis; T2KA

Declarative analysis of noisy information networks - Moustafa,W. E; Namata,G.; Deshpande, Amol; Getoor, Lise (2011 IEEE 27th International Conference on Data Engineering Workshops (ICDEW), 2011)
There is a growing interest in methods for analyzing data describing networks of all types, including information, biological, physical, and social networks. Typically the data describing these networks is observational, and thus noisy and incomplete; it is often at the wrong level of fidelity and abstraction for meaningful data analysis. This has resulted in a growing body of work on extracting, cleaning, and annotating network data. Unfortunately, much of this work is ad hoc and domain-specific. In this paper, we present the architecture of a data management system that enables efficient, declarative analysis of large-scale information networks. We identify a set of primitives to support the extraction and inference of a network from observational data, and describe a framework that enables a network analyst to easily implement and combine new extraction and analysis techniques, and efficiently apply them to large observation networks. The key insight behind our approach is to decouple, to the extent possible, (a) the operations that require traversing the graph structure (typically the computationally expensive step), from (b) the operations that do the modification and update of the extracted network. We present an analysis language based on Datalog, and show how to use it to cleanly achieve such decoupling. We briefly describe our prototype system that supports these abstractions. We include a preliminary performance evaluation of the system and show that our approach scales well and can efficiently handle a wide spectrum of data cleaning operations on network data.
Keywords: Cleaning; Data analysis; data cleaning operations; data management system; data mining; Databases; Datalog; declarative analysis; graph structure; information networks; Noise measurement; noisy information networks; Prediction algorithms; semantics; Syntactics

Design and fabrication of miniature compliant hinges for multi-material compliant mechanisms - Bejgerowski,Wojciech; Gerdes,John; Gupta, Satyandra K.; Bruck,Hugh (The International Journal of Advanced Manufacturing Technology, 2011)
Multi-material molding (MMM) enables the creation of multi-material mechanisms that combine compliant hinges, serving as revolute joints, and rigid links in a single part. There are three important challenges in creating these structures: (1) bonding between the materials used, (2) the ability of the hinge to transfer the required loads in the mechanism while allowing for the prescribed degree(s) of freedom, and (3) incorporating the process-specific requirements in the design stage. This paper presents the approach for design and fabrication of miniature compliant hinges in multi-material compliant mechanisms. The methodology described in this paper allows for the concurrent design of the part and the manufacturing process. For the first challenge, mechanical interlocking strategies are presented. For the second challenge, the development of a simulation-based optimization model of the hinge is presented, involving functional and manufacturing constrains. For the third challenge, the development of hinge positioning features and gate positioning constraints is presented. The developed MMM process is described, along with the main constraints and performance measures. This includes the process sequence, the mold cavity design, gate selection, and runner system development. A case study is presented to demonstrate the feasibility of creating multi-material mechanisms with miniature hinges serving as joints through MMM process. The approach described in this paper was utilized to design a drive mechanism for a flapping wing micro air vehicle. The methods described in this paper are applicable to any lightweight, load-bearing compliant mechanism manufactured using multi-material injection molding.
Keywords: engineering

Design methods for Wireless Sensor Network Building Energy Monitoring Systems - Cho, Inkeun; Chung-Ching Shen; Potbhare, S.; Bhattacharyya, Shuvra S.; Goldsman,N. (2011 IEEE 36th Conference on Local Computer Networks (LCN), 2011)
In this paper, we present a new energy analysis method for evaluating energy consumption of embedded sensor nodes at the application level and the network level. Then we apply the proposed energy analysis method to develop new energy management schemes in order to maximize lifetime for Wireless Sensor Network Building Energy Monitoring Systems (WSNBEMS). At the application level, we develop a new design approach that uses dataflow techniques to model the application-level interfacing behavior between the processor and sensors on an embedded sensor node. At the network level, we analyze the energy consumption of the IEEE 802.15.4 MAC functionality. Based on our techniques for modeling and energy analysis, we have implemented an optimized WSNBEMS for a real building, and validated our energy analysis techniques through measurements on this implementation. The performance of our implementation is also evaluated in terms of monitoring accuracy and energy consumption savings. We have demonstrated that by applying the proposed scheme, system lifetime can be improved significantly without affecting monitoring accuracy.
Keywords: Analytical models; application-level interfacing behavior; building energy monitoring system; Buildings; dataflow technique; embedded sensor node; energy analysis method; Energy consumption; energy management systems; Energy resolution; IEEE 802.15.4 MAC functionality; Monitoring; OPTIMIZATION; wireless sensor network; Wireless sensor networks; WSNBEMS; Zigbee

Design of Revolute Joints for In-Mold Assembly Using Insert Molding - Ananthanarayanan,A.; Ehrlich,L.; Desai,J. P.; Gupta,S.K. (Journal of Mechanical Design, 2011)

Differential adaptive diffusion: Understanding diversity and learning whom to trust in viral marketing - Sharara,H.; Rand, William; Getoor, Lise (Fifth International AAAI Conference on Weblogs and Social Media, 2011)
Viral marketing mechanisms use the existing social network between customers to spread information about products and encourage product adoption. Existing viral marketing models focus on the dynamics of the diffusion process, however they typically: (a) only consider a single product campaign and (b) fail to model the evolution of the social network, as the trust between individuals changes over time, during the course of multiple campaigns. In this work, we propose an adaptive vi- ral marketing model which captures: (1) multiple different product campaigns, (2) the diversity in customer preferences among different product categories, and (3) changing con- fidence in peers’ recommendations over time. By applying our model to a real-world network extracted from the Digg social news website, we provide insights into the effects of network dynamics on the different products’ adoption. Our experiments show that our proposed model outperforms ear- lier non-adaptive diffusion models in predicting future prod- uct adoptions. We also show how this model can be used to explore new viral marketing strategies that are more success- ful than classic strategies which ignore the dynamic nature of social networks.

Direct targeting of Sec23a by miR-200s influences cancer cell secretome and promotes metastatic colonization - Korpal, Manav; Ell, Brian J.; Buffa, Francesca M.; Ibrahim, Toni; Blanco, Mario A.; Celià-Terrassa, Toni; Mercatali, Laura; Zia Khan; Goodarzi, Hani; Hua, Yuling; Wei, Yong; Hu, Guohong; et al. (Nature Medicine, 2011)
Although the role of miR-200s in regulating E-cadherin expression and epithelial-to-mesenchymal transition is well established, their influence on metastatic colonization remains controversial. Here we have used clinical and experimental models of breast cancer metastasis to discover a pro-metastatic role of miR-200s that goes beyond their regulation of E-cadherin and epithelial phenotype. Overexpression of miR-200s is associated with increased risk of metastasis in breast cancer and promotes metastatic colonization in mouse models, phenotypes that cannot be recapitulated by E-cadherin expression alone. Genomic and proteomic analyses revealed global shifts in gene expression upon miR-200 overexpression toward that of highly metastatic cells. miR-200s promote metastatic colonization partly through direct targeting of Sec23a, which mediates secretion of metastasis-suppressive proteins, including Igfbp4 and Tinagl1, as validated by functional and clinical correlation studies. Overall, these findings suggest a pleiotropic role of miR-200s in promoting metastatic colonization by influencing E-cadherin–dependent epithelial traits and Sec23a-mediated tumor cell secretome.View full text

Disaggregated End-Use Energy Sensing for the Smart Grid - Jon Froehlich; Larson,E.; Gupta,S.; Cohn,G.; Reynolds,M.; Patel,S. (IEEE Pervasive Computing, 2011)
This article surveys existing and emerging disaggregation techniques for energy-consumption data and highlights signal features that might be used to sense disaggregated data in an easily installed and cost-effective manner.
Keywords: Calibration; disaggregated end-use energy sensing; Disaggregated energy sensing; disaggregation data techniques; Electricity; Energy consumption; Energy efficiency; energy-consumption data; Gas; Home appliances; Sensors; Smart grid; Smart grids; smart power grids; Sustainability; Water

DNACLUST: accurate and efficient clustering of phylogenetic marker genes - Ghodsi,Mohammadreza; Liu,Bo; Pop, Mihai (BMC Bioinformatics, 2011)
Clustering is a fundamental operation in the analysis of biological sequence data. New DNA sequencing technologies have dramatically increased the rate at which we can generate data, resulting in datasets that cannot be efficiently analyzed by traditional clustering methods.

Domain adaptation for object recognition: An unsupervised approach - Gopalan,R.; Ruonan Li; Chellapa, Rama (2011 IEEE International Conference on Computer Vision (ICCV), 2011)
Adapting the classifier trained on a source domain to recognize instances from a new target domain is an important problem that is receiving recent attention. In this paper, we present one of the first studies on unsupervised domain adaptation in the context of object recognition, where we have labeled data only from the source domain (and therefore do not have correspondences between object categories across domains). Motivated by incremental learning, we create intermediate representations of data between the two domains by viewing the generative subspaces (of same dimension) created from these domains as points on the Grassmann manifold, and sampling points along the geodesic between them to obtain subspaces that provide a meaningful description of the underlying domain shift. We then obtain the projections of labeled source domain data onto these subspaces, from which a discriminative classifier is learnt to classify projected data from the target domain. We discuss extensions of our approach for semi-supervised adaptation, and for cases with multiple source and target domains, and report competitive results on standard datasets.
Keywords: Data models; data representations; discriminative classifier; Feature extraction; Grassmann manifold; image sampling; incremental learning; labeled source domain; Manifolds; measurement; object category; Object recognition; Principal component analysis; sampling points; semisupervised adaptation; target domain; underlying domain shift; unsupervised approach; unsupervised domain adaptation; Unsupervised learning; vectors

A Dual Framework and Algorithms for Targeted Online Data Delivery - Roitman,Haggai; Gal,Avigdor; Raschid, Louiqa (IEEE Transactions on Knowledge and Data Engineering, 2011)
A variety of emerging online data delivery applications challenge existing techniques for data delivery to human users, applications, or middleware that are accessing data from multiple autonomous servers. In this paper, we develop a framework for formalizing and comparing pull-based solutions and present dual optimization approaches. The first approach, most commonly used nowadays, maximizes user utility under the strict setting of meeting a priori constraints on the usage of system resources. We present an alternative and more flexible approach that maximizes user utility by satisfying all users. It does this while minimizing the usage of system resources. We discuss the benefits of this latter approach and develop an adaptive monitoring solution Satisfy User Profiles (SUPs). Through formal analysis, we identify sufficient optimality conditions for SUP. Using real (RSS feeds) and synthetic traces, we empirically analyze the behavior of SUP under varying conditions. Our experiments show that we can achieve a high degree of satisfaction of user utility when the estimations of SUP closely estimate the real event stream, and has the potential to save a significant amount of system resources. We further show that SUP can exploit feedback to improve user utility with only a moderate increase in resource utilization.
Keywords: client/server multitier systems; distributed databases; online data delivery.; online information services

Dynamic Processing Allocation in Video - Daozheng Chen; Bilgic,M.; Getoor, Lise; Jacobs, David W. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2011)
Large stores of digital video pose severe computational challenges to existing video analysis algorithms. In applying these algorithms, users must often trade off processing speed for accuracy, as many sophisticated and effective algorithms require large computational resources that make it impractical to apply them throughout long videos. One can save considerable effort by applying these expensive algorithms sparingly, directing their application using the results of more limited processing. We show how to do this for retrospective video analysis by modeling a video using a chain graphical model and performing inference both to analyze the video and to direct processing. We apply our method to problems in background subtraction and face detection, and show in experiments that this leads to significant improvements over baseline algorithms.
Keywords: algorithms; digital; allocation; video; analysis; computer; background; detection; graphical; detection; resource; graphics; face; model; resource; processing; processing; face; recognition; object; signal; subtraction; baseline; video

Eighth workshop on mining and learning with graphs - Brefeld,Ulf; Getoor, Lise; Macskassy,Sofus A. (SIGKDD Explor. Newsl., 2011)
The Eighth Workshop on Mining and Learning with Graphs (MLG)1was held at KDD 2010 in Washington DC. It brought together a variete of researchers interested in analyzing data that is best represented as a graph. Examples include the WWW, social networks, biological networks, communication networks, and many others. The importance of being able to effectively mine and learn from such data is growing, as more and more structured and semi-structured data is becoming available. This is a problem across widely different fields such as economics, statistics, social science, physics and computer science, and is studied within a variety of sub-disciplines of machine learning and data mining including graph mining, graphical models, kernel theory, statistical relational learning, etc. The objective of this workshop was to bring together practitioners from these various fields and areas to foster a rich discussion of which problems we work on, how we frame them in the context of graphs, which tools and algorithms we apply and our general findings and lessons learned. This year's workshop was very successful with well over 100 attendees, excellent keynote speakers and papers. This is a rapidly growing area and we believe that this community is only in its infancy. We hope that the readers will join us next year for MLG 2011.
Keywords: data mining; dynamic network analysis; graph mining; kernel methods; link mining; machine learning; network analysis; pattern recognition; relational learning; scalable graph mining; statistical relational learning

Estimating Functional Agent-Based Models: An Application to Bid Shading in Online Markets Format - Guo,Wei; Jank,Wolfgang; Rand, William (Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2011), 2011)
Bid shading is a common strategy in online auctions to avoid the "winner’s curse". While almost all bidders shade their bids, at least to some degree, it is impossible to infer the degree and volume of shaded bids directly from observed bidding data. In fact, most bidding data only allows us to observe the resulting price process, i.e. whether prices increase fast (due to little shading) or whether they slow down (when all bidders shade their bids). In this work, we propose an agent-based model that simulates bidders with different bidding strategies and their interaction with one another. We calibrate that model (and hence estimate properties about the propensity and degree of shaded bids) by matching the emerging simulated price process with that of the observed auction data using genetic algorithms. From a statistical point of view, this is challenging because we match functional draws from simulated and real price processes. We propose several competing fitness functions and explore how the choice alters the resulting ABM calibration. We apply our model to the context of eBay auctions for digital cameras and show that a balanced fitness function yields the best results.
Keywords: Agent-based modeling; business; Calibration; Genetic algorithms; internet auctions; simulation

Evaluating visual and statistical exploration of scientific literature networks - Gove,R.; Dunne,C.; Shneiderman, Ben; Klavans,J.; Dorr, Bonnie J (2011 IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC), 2011)
Action Science Explorer (ASE) is a tool designed to support users in rapidly generating readily consumable summaries of academic literature. It uses citation network visualization, ranking and filtering papers by network statistics, and automatic clustering and summarization techniques. We describe how early formative evaluations of ASE led to a mature system evaluation, consisting of an in-depth empirical evaluation with four domain experts. The evaluation tasks were of two types: predefined tasks to test system performance in common scenarios, and user-defined tasks to test the system's usefulness for custom exploration goals. The primary contribution of this paper is a validation of the ASE design and recommendations to provide: easy-to-understand metrics for ranking and filtering documents, user control over which document sets to explore, and overviews of the document set in coordinated views along with details-on-demand of specific papers. We contribute a taxonomy of features for literature search and exploration tools and describe exploration goals identified by our participants.
Keywords: abstracting; academic literature; action science explorer; automatic clustering; citation analysis; citation network visualization; Communities; Context; custom exploration goal; Data visualization; Databases; Document filtering; document handling; document ranking; easy-to-understand metrics; empirical evaluation; Google; Graphical user interfaces; Information filtering; Information Visualization; Libraries; literature exploration; network statistics; paper filtering; paper ranking; scientific literature network; statistical exploration; summarization technique; user-defined tasks; visual exploration; Visualization

Exploiting Statically Schedulable Regions in Dataflow Programs - Gu, Ruirui; Janneck, Jörn W.; Raulet, Mickaël; Bhattacharyya, Shuvra S. (Journal of Signal Processing Systems, 2011)
Dataflow descriptions have been used in a wide range of Digital Signal Processing (DSP) applications, such as multi-media processing, and wireless communications. Among various forms of dataflow modeling, Synchronous Dataflow (SDF) is geared towards static scheduling of computational modules, which improves system performance and predictability. However, many DSP applications do not fully conform to the restrictions of SDF modeling. More general dataflow models, such as CAL (Eker and Janneck 2003), have been developed to describe dynamically-structured DSP applications. Such generalized models can express dynamically changing functionality, but lose the powerful static scheduling capabilities provided by SDF. This paper focuses on the detection of SDF-like regions in dynamic dataflow descriptions—in particular, in the generalized specification framework of CAL. This is an important step for applying static scheduling techniques within a dynamic dataflow framework. Our techniques combine the advantages of different dataflow languages and tools, including CAL (Eker and Janneck 2003), DIF (Hsu et al. 2005) and CAL2C (Roquier et al. 2008). In addition to detecting SDF-like regions, we apply existing SDF scheduling techniques to exploit the static properties of these regions within enclosing dynamic dataflow models. Furthermore, we propose an optimized approach for mapping SDF-like regions onto parallel processing platforms such as multi-core processors.
Keywords: Cal; Circuits and Systems; Computer Imaging, Vision, Pattern Recognition and Graphics; Dataflow; DIF; Electrical Engineering; Image Processing and Computer Vision; multicore processors; pattern recognition; Quasi-static scheduling; Signal, Image and Speech Processing

Exploiting statistical and relational information on the web and in social media - Getoor, Lise; Mihalkova,Lilyana (Proceedings of the fourth ACM international conference on Web search and data mining, 2011)
The popularity of Web 2.0, characterized by a proliferation of social media sites, and Web 3.0, with more richly semantically annotated objects and relationships, brings to light a variety of important prediction, ranking, and extraction tasks. The input to these tasks is often best seen as a (noisy) multi-relational graph, such as the click graph, defined by user interactions with Web sites; and the social graph, defined by friendships and affiliations on social media sites. This tutorial will provide an overview of statistical relational learning and inference techniques, motivating and illustrating them using web and social media applications. We will start by briefly surveying some of the sources of statistical and relational information on the web and in social media and will then dedicate most of the tutorial time to an introduction to representations and techniques for learning and reasoning with multi-relational information, viewing them through the lens of web and social media domains. We will end with a discussion of current trends and related fields, such as privacy in social networks.
Keywords: graph analysis; probabilistic inference; query log data; social media; statistical relational learning

Face Detection - Gopalan,Raghuraman; Schwartz,William R.; Chellapa, Rama; Srivastava,Ankur (Visual Analysis of HumansVisual Analysis of Humans, 2011)
Face detection in still images and videos has been extensively studied over the last two decades. Attributed to the recent proliferation of cameras in consumer applications, research in face detection has gradually transformed into more unconstrained settings, with the goal of achieving performance close to humans. This presents two main challenges: (i) in addition to modeling the facial characteristics, understanding the information portrayed by the surrounding scene is important in resolving visual ambiguities, and (ii) the computational time needed for decision making should be compatible for real-time applications, since detection is primarily a front-end process on which additional knowledge extraction is built upon. This chapter begins with a review of recent work in modeling face-specific information, including appearance-based methods used by sliding window classifiers, concepts from learning and local interest-point descriptors, and then focuses on representing the contextual information shared by faces with the surrounding scene. To provide better understanding of working concepts, we discuss a method for learning the semantic context shared by the face with other human body parts that facilitates reasoning under occlusion, and then present an image representation which efficiently encodes contour information to enable fast detection of faces. We conclude the chapter by discussing some existing challenges.

Face Tracking and Recognition in a Camera Network - Bhanu,Bir; Govindaraju,Venu (Multibiometrics for Human IdentificationMultibiometrics for Human Identification, 2011)

Face verification using large feature sets and one shot similarity - Guo,Huimin; Robson Schwartz,W.; Davis, Larry S. (Biometrics (IJCB), 2011 International Joint Conference on, 2011)
We present a method for face verification that combines Partial Least Squares (PLS) and the One-Shot similarity model[28]. First, a large feature set combining shape, texture and color information is used to describe a face. Then PLS is applied to reduce the dimensionality of the feature set with multi-channel feature weighting. This provides a discriminative facial descriptor. PLS regression is used to compute the similarity score of an image pair by One-Shot learning. Given two feature vector representing face images, the One-Shot algorithm learns discriminative models exclusively for the vectors being compared. A small set of unlabeled images, not containing images belonging to the people being compared, is used as a reference (negative) set. The approach is evaluated on the Labeled Face in the Wild (LFW) benchmark and shows very comparable results to the state-of-the-art methods (achieving 86.12% classification accuracy) while maintaining simplicity and good generalization ability.
Keywords: analysis; set; approximations; regression; descriptor; labeled; Face; feature; in; information; face; information; texture; least; LFW; PLS; PLS; recognition; least; regression; color; sets; one; shot; similarity; partial; squares; squares; shape; the; theory; verification; facial; wild; large

From slacktivism to activism: participatory culture in the age of social media - Rotman,Dana; Vieweg,Sarah; Yardi,Sarita; Chi,Ed; Preece,Jenny; Shneiderman, Ben; Pirolli,Peter; Glaisyer,Tom (Proceedings of the 2011 annual conference extended abstracts on Human factors in computing systems, 2011)
Social networking sites (e.g. Facebook), microblogging services (e.g. Twitter), and content-sharing sites (e.g. YouTube and Flickr) have introduced the opportunity for wide-scale, online social participation. Visibility of national and international priorities such as public health, political unrest, disaster relief, and climate change has increased, yet we know little about the benefits - and possible costs - of engaging in social activism via social media. These powerful social issues introduce a need for scientific research into technology mediated social participation. What are the actual, tangible benefits of "greening" Twitter profile pictures in support of the Iranian elections? Does cartooning a Facebook profile picture really raise awareness of child abuse? Are there unintended negative effects through low-risk, low-cost technology-mediated participation? And, is there a difference - in both outcome and engagement level - between different types of online social activism? This SIG will investigate technology mediated social participation through a critical lens, discussing both the potential positive and negative outcomes of such participation. Approaches to designing for increased participation, evaluating effects of participation, and next steps in scientific research directions will be discussed.
Keywords: activism; change; design; participation; slacktivism; social media

G-PARE: A visual analytic tool for comparative analysis of uncertain graphs - Sharara,H.; Sopan,A.; Namata,G.; Getoor, Lise; Singh,L. (Visual Analytics Science and Technology (VAST), 2011 IEEE Conference on, 2011)

Graph Analytics-Lessons Learned and Challenges Ahead - Wong,Pak Chung; Chen,Chaomei; Gorg,Carsten; Shneiderman, Ben; Stasko,John; Thomas,Jim (IEEE Computer Graphics and Applications, 2011)
Graph analytics is one of the most influential and important R&D topics in the visual analytics community. Researchers with diverse backgrounds from information visualization, human-computer interaction, computer graphics, graph drawing, and data mining have pursued graph analytics from scientific, technical, and social approaches. These studies have addressed both distinct and common challenges. Past successes and mistakes can provide valuable lessons for revising the research agenda. In this article, six researchers from four academic and research institutes identify graph analytics' fundamental challenges and present both insightful lessons learned from their experience and good practices in graph analytics research. The goal is to critically assess those lessons and shed light on how they can stimulate research and draw attention to grand challenges for graph analytics. The article also establishes principles that could lead to measurable standards and criteria for research.
Keywords: citation analysis; citespace; Computer Graphics; document analysis; graphics and multimedia; greengrid; jigsaw system; modeling; power grid analysis; semantic substrates; simulation; social networks; text analysis; Visualization

Helping Users Shop for ISPs with Internet Nutrition Labels - Sundaresan, Srikanth; Feamster, Nick; Teixeira, Renata; Tang, Anthony; Edwards, W. Keith; Grinter, Rebecca E.; Marshini Chetty; de Donato, Walter (ACM SIGCOMM Workshop on Home Networks '11, 2011)
When purchasing home broadband access from Internet service providers (ISPs), users must decide which service plans are most appropriate for their needs. Today, ISPs advertise their available service plans using only generic upload and download speeds. Unfortunately, these metrics do not always accurately reflect the varying performance that home users will experience for a wide range of applications. In this paper, we propose that each ISP service plan carry a "nutrition label" that conveys more comprehensive information about network metrics along many dimensions, including various aspects of throughput, latency, loss rate, and jitter. We first justify why these metrics should form the basis of a network nutrition label. Then, we demonstrate that current plans that are superficially similar with respect to advertised download rates may have different performance according to the label metrics. We close with a discussion of the challenges involved in presenting a nutrition label to users in a way that is both accurate and easy to understand.
Keywords: access networks; benchmarking; bismark; broadband networks; gateway measurements

A Hierarchical Algorithm for Fast Debye Summation with Applications to Small Angle Scattering - Gumerov, Nail A.; Berlin,Konstantin; Fushman, David; Duraiswami, Ramani (Technical Reports from UMIACS, 2011)
Debye summation, which involves the summation of sinc functions of distances between all pair of atoms in three dimensional space, arises in computations performed in crystallography, small/wide angle X-ray scattering (SAXS/WAXS) and small angle neutron scattering (SANS). Direct evaluation of Debye summation has quadratic complexity, which results in computational bottleneck when determining crystal properties, or running structure refinement protocols that involve SAXS or SANS, even for moderately sized molecules. We present a fast approximation algorithm that efficiently computes the summation to any prescribed accuracy epsilon in linear time. The algorithm is similar to the fast multipole method (FMM), and is based on a hierarchical spatial decomposition of the molecule coupled with local harmonic expansions and translation of these expansions. An even more efficient implementation is possible when the scattering profile is all that is required, as in small angle scattering reconstruction (SAS) of macromolecules. We examine the relationship of the proposed algorithm to existing approximate methods for profile computations, and provide detailed description of the algorithm, including error bounds and algorithms for stable computation of the translation operators. Our theoretical and computational results show orders of magnitude improvement in computation complexity over existing methods, while maintaining prescribed accuracy.
Keywords: Technical Report

Improving Classifier Performance by Autonomously Collecting Background Knowledge from the Web - Minton,S.N.; Michelson,M.; See,K.; Macskassy,S.; Gazen,B.C.; Getoor, Lise (2011 10th International Conference on Machine Learning and Applications Workshops, 2011)
Many websites allow users to tag data items to makethem easier to find. In this paper we consider the problem of classifying tagged data according to user-specified interests. We present an approach for aggregating background knowledge from the Web to improve the performance of a classier. In previous work, researchers have developed technology for extracting knowledge, in the form of relational tables, from semi- structured websites. In this paper we integrate this extraction technology with generic machine learning algorithms, showing that knowledge extracted from the Web can significantly benefit the learning process. Specifically, the knowledge can lead to better generalizations, reduce the number of samples required for supervised learning, and eliminate the need to retrain the system when the environment changes. We validate the approach with an application that classifies tagged Fickr data.

Instrumenting home networks - Calvert,Kenneth L.; Edwards,W. Keith; Feamster, Nick; Grinter,Rebecca E.; Deng,Ye; Zhou,Xuzi (SIGCOMM Comput. Commun. Rev., 2011)
In managing and troubleshooting home networks, one of the challenges is in knowing what is actually happening. Availability of a record of events that occurred on the home network before trouble appeared would go a long way toward addressing that challenge. In this position/work-in-progress paper, we consider requirements for a general-purpose logging facility for home networks. Such a facility, if properly designed, would potentially have other uses. We describe several such uses and discuss requirements to be considered in the design of a logging platform that would be widely supported and accepted. We also report on our initial deployment of such a facility.
Keywords: home network management; home network troubleshooting

Interaction of Vibrio cholerae non-O1/non-O139 with Copepods, Cladocerans and Competing Bacteria in the Large Alkaline Lake Neusiedler See, Austria - Kirschner,A. K. T.; Schauer,S.; Steinberger,B.; Wilhartitz,I.; Grim,C. J.; Huq,A.; Rita R Colwell; Herzig,A.; Sommer,R. (Microbial ecology, 2011)
Vibrio cholerae is a human pathogen and natural inhabitant of aquatic environments. Serogroups O1/O139 have been associated with epidemic cholera, while non-O1/non-O139 serogroups usually cause human disease other than classical cholera. V. cholerae non-O1/non-O139 from the Neusiedler See, a large Central European lake, have caused ear and wound infections, including one case of fatal septicaemia. Recent investigations demonstrated rapid planktonic growth of V. cholerae non-O1/non-O139 and correlation with zooplankton biomass. The aim of this study was to elucidate the interaction of autochthonous V. cholerae with two dominant crustacean zooplankton species in the lake and investigate the influence of the natural bacterial community on this interaction. An existing data set was evaluated for statistical relationships between zooplankton species and V. cholerae and co-culture experiments were performed in the laboratory. A new fluorescence in situ hybridisation protocol was applied for quantification of V. cholerae non-O1/non-O139 cells, which significantly reduced analysis time. The experiments clearly demonstrated a significant relationship of autochthonous V. cholerae non-O1/non-O139 with cladocerans by promoting growth of V. cholerae non-O1/non-O139 in the water and on the surfaces of the cladocerans. In contrast, copepods had a negative effect on the growth of V. cholerae non-O1/non-O139 via competing bacteria from their surfaces. Thus, beside other known factors, biofilm formation by V. cholerae on crustacean zooplankton appears to be zooplankton taxon specific and may be controlled by the natural bacterial community.

Kernel partial least squares for speaker recognition - Srinivasan,B.V.; Garcia-Romero,D.; Zotkin,Dmitry N; Duraiswami, Ramani (Twelfth Annual Conference of the International Speech Communication Association, 2011)
I-vectors are a concise representation of speaker characteristics. Recent advances in speaker recognition have utilized their ability to capture speaker and channel variability to develop efficient recognition engines. Inter-speaker relationships in the i-vector space are non-linear. Accomplishing effective speaker recognition requires a good modeling of these non-linearities and can be cast as a machine learning problem. In this paper, we propose a kernel partial least squares (kernel PLS, or KPLS) framework for modeling speakers in the i-vectors space. The resulting recognition system is tested across several conditions of the NIST SRE 2010 extended core data set and compared against state-of-the-art systems: Joint Factor Analysis (JFA), Probabilistic Linear Discriminant Analysis (PLDA), and Cosine Distance Scoring (CDS) classifiers. Improvements are shown.

Learning statistical models from relational data - Getoor, Lise; Mihalkova,Lilyana (Proceedings of the 2011 international conference on Management of data, 2011)
Statistical Relational Learning (SRL) is a subarea of machine learning which combines elements from statistical and probabilistic modeling with languages which support structured data representations. In this survey, we will: 1) provide an introduction to SRL, 2) describe some of the distinguishing characteristics of SRL systems, including relational feature construction and collective classification, 3) describe three SRL systems in detail, 4) discuss applications of SRL techniques to important data management problems such as entity resolution, selectivity estimation, and information integration, and 5) discuss connections between SRL methods and existing database research such as probabilistic databases.
Keywords: machine learning; probabilistic graphical models; statistical relational learning

Learning to predict web collaborations - Mihalkova,L.; Moustafa,W.; Getoor, Lise (Workshop on User Modeling for Web Applications (UMWA-11), 2011)
Much of the knowledge available on the web today comes asa result of fruitful collaborations among large groups of peo- ple. One of the most striking examples of successful web col- laboration is the online encyclopedia Wikipedia. The web is used as a collaboration platform by highly specialized blog- ging communities and by the scientific community. An im- portant reason for the richness of content generated through web collaborations is that the participants in such collabo- rations are not constrained by geographic location. Thus, like-minded individuals from across the world can join their efforts. This also means, however, that web collaborators of- ten do not know each other, and, thus, finding collaborators on the web is more difficult than it is with more traditional forms of collaboration that are initiated based on acquain- tance. This difficulty is further exacerbated by the fact that web collaborations tend to be more dynamic as participants join and abandon communities. We consider the task of rec- ommending project-specific potential collaborators to web users and propose an approach that is based on statistical relational learning. Our proposed model thus has the ad- vantages that it can include complex features composed of multiple properties and relationships of the entities, it can handle the high levels of noise and uncertainty inherent in user actions, and it allows for joint decision-making, which leads to more accurate predictions. To ensure scalability, our model is trained in an online fashion. We demonstrate the effectiveness of our approach on a data set collected from Wikipedia.

The Life Game: Cognitive Strategies for Repeated Stochastic Games - Cheng,Kan-Leung; Zuckerman,I.; Nau, Dana S.; Golbeck,J. (2011)
Standard models in bio-evolutionary game theory involve repetitions of a single stage game (e.g., the Prisoner's Dilemma or the Stag Hunt); but it is clear that repeatedly playing the same stage game is not an accurate model of most individuals' lives. Rather, individuals' interactions with others correspond to many different kinds of stage games. In this work, we concentrate on discovering behavioral strategies that are successful for the life game, in which the stage game is chosen stochastically at each iteration. We present a cognitive agent model based on Social Value Orientation (SVO) theory. We provide extensive evaluations of our model's performance, both against standard agents from the game theory literature and against a large set of life-game agents written by students in two different countries. Our empirical results suggest that for life-game strategies to be successful in environments with such agents, it is important (i) to be unforgiving with respect to trust behavior and (ii) to use adaptive, fine-grained opponent models of the other agents.
Keywords: adaptive model; behavioral strategy; bioevolutionary game theory; cognitive agent model; fine-grained opponent model; game theory; iteration; iterative methods; life game; prisoner's dilemma; repeated stochastic games; social value orientation theory; stag hunt; stage game; Stochastic processes; trust behavior

LifeFlow: visualizing an overview of event sequences - Wongsuphasawat,Krist; Guerra Gómez,John Alexis; Plaisant, Catherine; Wang,Taowei David; Taieb-Maimon,Meirav; Shneiderman, Ben (Proceedings of the 2011 annual conference on Human factors in computing systems, 2011)
Event sequence analysis is an important task in many domains: medical researchers may study the patterns of transfers within the hospital for quality control; transportation experts may study accident response logs to identify best practices. In many cases they deal with thousands of records. While previous research has focused on searching and browsing, overview tasks are often overlooked. We introduce a novel interactive visual overview of event sequences called LifeFlow. LifeFlow is scalable, can summarize all possible sequences, and represents the temporal spacing of the events within sequences. Two case studies with healthcare and transportation domain experts are presented to illustrate the usefulness of LifeFlow. A user study with ten participants confirmed that after 15 minutes of training novice users were able to rapidly answer questions about the prevalence and temporal characteristics of sequences, find anomalies, and gain significant insight from the data.
Keywords: Information Visualization; overview visualization; temporal categorical data; timestamped event sequences

LifeFlow: visualizing an overview of event sequences (video preview) - Wongsuphasawat,Krist; Guerra Gómez,John Alexis; Plaisant, Catherine; Wang,Taowei; Taieb-Maimon,Meirav; Shneiderman, Ben (Proceedings of the 2011 annual conference extended abstracts on Human factors in computing systems, 2011)
Event sequence analysis is an important task in many domains: medical researchers may study the patterns of transfers within the hospital for quality control; transportation experts may study accident response logs to identify best practices. In many cases they deal with thousands of records. While previous research has focused on searching and browsing, overview tasks are often overlooked. We introduce a novel interactive visual overview of event sequences called LifeFlow. LifeFlow is scalable, can summarize all possible sequences, and represents the temporal spacing of the events within sequences. In this video, we show an example of patient transfer data and briefly demonstrate how to analyze them with LifeFlow. Please see [11] or visit http:www.cs.umd.eduhcillifeflow for more detail.
Keywords: emergency room; healthcare; Information Visualization; overview visualization; temporal categorical data; timestamped event sequences

Lightweight monadic programming in ML - Swamy,Nikhil; Guts,Nataliya; Leijen,Daan; Hicks, Michael W. (Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, 2011)
Many useful programming constructions can be expressed as monads. Examples include probabilistic modeling, functional reactive programming, parsing, and information flow tracking, not to mention effectful functionality like state and I/O. In this paper, we present a type-based rewriting algorithm to make programming with arbitrary monads as easy as using ML's built-in support for state and I/O. Developers write programs using monadic values of type m τ as if they were of type τ, and our algorithm inserts the necessary binds, units, and monad-to-monad morphisms so that the program type checks. Our algorithm, based on Jones' qualified types, produces principal types. But principal types are sometimes problematic: the program's semantics could depend on the choice of instantiation when more than one instantiation is valid. In such situations we are able to simplify the types to remove any ambiguity but without adversely affecting typability; thus we can accept strictly more programs. Moreover, we have proved that this simplification is efficient (linear in the number of constraints) and coherent: while our algorithm induces a particular rewriting, all related rewritings will have the same semantics. We have implemented our approach for a core functional language and applied it successfully to simple examples from the domains listed above, which are used as illustrations throughout the paper.
Keywords: coercion; coherence; monad; rewriting; type

Limits of computational differential privacy in the client/server setting - Groce,A.; Katz, Jonathan; Yerukhimovich,A. (Theory of Cryptography, 2011)
Differential privacy is a well established definition guaranteeing that queries to a database do not reveal “too much” information about specific individuals who have contributed to the database. The standard definition of differential privacy is information theoretic in nature, but it is natural to consider computational relaxations and to explore what can be achieved with respect to such notions. Mironov et al. (Crypto 2009) and McGregor et al. (FOCS 2010) recently introduced and studied several variants of computational differential privacy, and show that in the two-party setting (where data is split between two parties) these relaxations can offer significant advantages.Left open by prior work was the extent, if any, to which computational differential privacy can help in the usual client/server setting where the entire database resides at the server, and the client poses queries on this data. We show, for queries with output in ℝ n (for constant n) and with respect to a large class of utilities, that any computationally private mechanism can be converted to a statistically private mechanism that is equally efficient and achieves roughly the same utility.

Linear versus Mel Frequency Cepstral Coefficients for Speaker Recognition - Zhou,X.; Garcia-Romero,D.; Duraiswami, Ramani; Espy-Wilson,C.; Shamma,S. (IEEE Automatic Speech Recognition and Understanding Workshop, 2011)
Mel-frequency cepstral coefficients (MFCC) havebeen dominantly used in speaker recognition as well as in speech recognition. However, based on theories in speech production, some speaker characteristics associated with the structure of the vocal tract, particularly the vocal tract length, are reflected more in the high frequency range of speech. This insight suggests that a linear scale in frequency may provide some advantages in speaker recognition over the mel scale. Based on two state-of-the- art speaker recognition back-end systems (one Joint Factor Analysis system and one Probabilistic Linear Discriminant Analysis system), this study compares the performances between MFCC and LFCC (Linear frequency cepstral coefficients) in the NIST SRE (Speaker Recognition Evaluation) 2010 extended-core task. Our results in SRE10 show that, while they are complementary to each other, LFCC consistently outperforms MFCC, mainly due to its better performance in the female trials. This can be explained by the relatively shorter vocal tract in females and the resulting higher formant frequencies in speech. LFCC benefits more in female speech by better capturing the spectral characteristics in the high frequency region. In addition, our results show some advantage of LFCC over MFCC in reverberant speech. LFCC is as robust as MFCC in the babble noise, but not in the white noise. It is concluded that LFCC should be more widely used, at least for the female trials, by the mainstream of the speaker recognition community.

Maryland at FIRE 2011: Retrieval of OCRed Bengali - Garain,Utpal; David Doermann; Oard,Douglas D. (FIRE, 2011)
In this year's Forum for Information Retrieval Evaluation (FIRE), the University of Maryland participated in the Retrieval of Indic Script OCRed Text (RISOT) task to experiment with the retrieval of Bengali script OCR’d documents. The experiments focused on evaluating a retrieval strategy motivated by recent work on Cross-Language Information Retrieval (CLIR), but which makes use of OCR error modeling rather than parallel text alignment. The approach obtains a probability distribution over substitutions for the actual query terms that possibly correspond to terms in the document representation. The results reported indicate that this is a promising way of using OCR error modeling to improve CLIR.

Materializing multi-relational databases from the web using taxonomic queries - Michelson,Matthew; Macskassy,Sofus A.; Minton,Steven N.; Getoor, Lise (Proceedings of the fourth ACM international conference on Web search and data mining, 2011)
Recently, much attention has been given to extracting tables from Web data. In this problem, the column definitions and tuples (such as what "company" is headquartered in what "city,") are extracted from Web text, structured Web data such as lists, or results of querying the deep Web, creating the table of interest. In this paper, we examine the problem of extracting and discovering multiple tables in a given domain, generating a truly multi-relational database as output. Beyond discovering the relations that define single tables, our approach discovers and leverages "within column" set membership relations, and discovers relations across the extracted tables (e.g., joins). By leveraging within-column relations our method can extract table instances that are ambiguous or rare, and by discovering joins, our method generates truly multi-relational output. Further, our approach uses taxonomic queries to bootstrap the extraction, rather than the more traditional "seed instances." Creating seeds often requires more domain knowledge than taxonomic queries, and previous work has shown that extraction methods may be sensitive to which input seeds they are given. We test our approach on two real world domains: NBA basketball and cancer information. Our results demonstrate that our approach generates databases of relevant tables from disparate Web information, and discovers the relations between them. Further, we show that by leveraging the "within column" relation our approach can identify a significant number of relevant tuples that would be difficult to do so otherwise.
Keywords: discovering multi-relational data; multirelational data

A method for the detection of meaningful and reproducible group signatures from gene expression profiles - Licamele,L.; Getoor, Lise (Journal of Bioinformatics and Computational Biology, 2011)
Gene expression microarrays are commonly used to detect the biological signature of a disease or to gain a better understanding of the underlying mechanism of how a group of drugs treat a specific disease. The outcome of such experiments, e.g. the signature, is a list of differentially expressed genes. Reproducibility across independent experiments remains a challenge. We are interested in creating a method that can detect the shared signature of a group of expression profiles, e.g. a group of samples from individuals with the same disease or a group of drugs that treat the same therapeutic indication. We have developed a novel Weighted Influence — Rank of Ranks (WIMRR) method, and we demonstrate its ability to produce both meaningful and reproducible group signatures.

Multi-material compliant mechanisms for mobile millirobots - Vogtmann,Dana E.; Gupta, Satyandra K.; Bergbreiter,Sarah (2011)
This paper describes a new process for fabricating planar, multi-material, compliant mechanisms, intended for use in small scale robotics. The process involves laser cutting the mechanism geometry from a rigid material, and refilling the joint areas with a second, elastomeric material. This method allows for a large set of potential materials, with a wide range of material properties, to be used in combination to create mechanisms with highly tailored mechanical properties. These multi-material compliant mechanisms have minimum feature sizes of approximately 100 #x00B5;m and have demonstrated long lifetimes, easily surviving 100,000 bending cycles. We also present the first use of these compliant mechanisms in a 2.5cm #x00D7; 2.5cm #x00D7; 7.5cm, 6g hexapod. This hexapod has been demonstrated moving at speeds up to 6 cm/s, with a predicted maximum speed of up to 17 cm/s.

NetVisia: Heat Map & Matrix Visualization of Dynamic Social Network Statistics & Content - Gove,R.; Gramsky,N.; Kirby,R.; Sefer,E.; Sopan,A.; Dunne,C.; Shneiderman, Ben; Taieb-Maimon,M. (Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom), 2011)
Visualizations of static networks in the form of node-link diagrams have evolved rapidly, though researchers are still grappling with how best to show evolution of nodes over time in these diagrams. This paper introduces NetVisia, a social network visualization system designed to support users in exploring temporal evolution in networks by using heat maps to display node attribute changes over time. NetVisia's novel contributions to network visualizations are to (1) cluster nodes in the heat map by similar metric values instead of by topological similarity, and (2) align nodes in the heat map by events. We compare NetVisia to existing systems and describe a formative user evaluation of a NetVisia prototype with four participants that emphasized the need for tool tips and coordinated views. Despite the presence of some usability issues, in 30-40 minutes the user evaluation participants discovered new insights about the data set which had not been discovered using other systems. We discuss implemented improvements to NetVisia, and analyze a co-occurrence network of 228 business intelligence concepts and entities. This analysis confirms the utility of a clustered heat map to discover outlier nodes and time periods.
Keywords: business intelligence concept; business intelligence entity; competitive intelligence; data visualisation; dynamic networks; dynamic social network; heat map; Heating; Image color analysis; Information Visualization; Layout; matrix visualization; measurement; NetVisia system; network evolution; network visualization; node-link diagrams; outlier node; social network content; Social network services; social network statistics; social networking (online); social networks; static network visualization; time period; topological similarity; Training; usability; user evaluation; User interfaces

Network Clustering Approximation Algorithm Using One Pass Black Box Sampling - DuBois,Thomas; Golbeck,Jennifer; Srinivasan, Aravind (arXiv:1110.3563, 2011)
Finding a good clustering of vertices in a network, where vertices in the same cluster are more tightly connected than those in different clusters, is a useful, important, and well-studied task. Many clustering algorithms scale well, however they are not designed to operate upon internet-scale networks with billions of nodes or more. We study one of the fastest and most memory efficient algorithms possible - clustering based on the connected components in a random edge-induced subgraph. When defining the cost of a clustering to be its distance from such a random clustering, we show that this surprisingly simple algorithm gives a solution that is within an expected factor of two or three of optimal with either of two natural distance functions. In fact, this approximation guarantee works for any problem where there is a probability distribution on clusterings. We then examine the behavior of this algorithm in the context of social network trust inference.
Keywords: Computer Science - Social and Information Networks; Physics - Physics and Society

New models and algorithms for throughput maximization in broadcast scheduling - Chekuri,C.; Gal,A.; Im,S.; Khuller, Samir; Li,J.; McCutchen,R.; Moseley,B.; Raschid, Louiqa (Approximation and Online Algorithms, 2011)

NSF/IEEE-TCPP curriculum initiative on parallel and distributed computing: core topics for undergraduates - Prasad,S. K.; Chtchelkanova,A.; Das,S.; Dehne,F.; Gouda,M.; Gupta,A.; JaJa, Joseph F.; Kant,K.; La Salle,A.; LeBlanc,R.; others (Proceedings of the 42nd ACM technical symposium on Computer science education, 2011)

Occurrence of Vibrio cholerae in Municipal and Natural Waters and Incidence of Cholera in Azerbaijan - Gurbanov, Shair; Akhmadov, Rashid; Shamkhalova, Gulnara; Akhmadova, Sevinj; Haley, Bradd J.; Rita R Colwell; Huq, Anwar (EcoHealth, 2011)
Cholera, a waterborne disease caused by Vibrio cholerae, is an autochthonous member of the aquatic environment and predominantly reported from developing countries. Technical reports and proceedings were reviewed to determine the relationship between occurrence of V. cholerae in natural waters, including sources of municipal water, and cases of cholera in Azerbaijan. Water samples collected from different environmental sources from 1970 to 1998 were tested for V. cholerae and 0.73% (864/117,893) were positive. The results showed that in April of each year, when the air temperature rose by approximately 5°C, V. cholerae could be isolated. With each increase in air temperature, 6–8 weeks after, impact on cases of cholera was recorded. The incidence of cholera peaked when the air temperature reached >25°C during the month of September. It is concluded that a distinct seasonality in cholera incidence exists in Azerbaijan, with increased occurrence during warmer months.

Overview of the FIRE 2011 RISOTTask - Garain,Utpal; Paik,Jiaul; Pal,Tamaltaru; Majumder,Prasenjit; David Doermann; Oard, Douglas (FIRE, 2011)
RISOT was a pilot task in FIRE 2011 which focused on the retrieval of automatically recognized text from machine printed sources. The collection used for search was a subset of the FIRE 2008 and 2010 Bengali test collections that contained 92 topics and 62,825 documents. Two teams participated, submitting a total of 11 monolingual runs.

Piecing together the segmentation jigsaw using context - Chen,Xi; Jain, A.; Gupta,A.; Davis, Larry S. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
We present an approach to jointly solve the segmentation and recognition problem using a multiple segmentation framework. We formulate the problem as segment selection from a pool of segments, assigning each selected segment a class label. Previous multiple segmentation approaches used local appearance matching to select segments in a greedy manner. In contrast, our approach formulates a cost function based on contextual information in conjunction with appearance matching. This relaxed cost function formulation is minimized using an efficient quadratic programming solver and an approximate solution is obtained by discretizing the relaxed solution. Our approach improves labeling performance compared to other segmentation based recognition approaches.
Keywords: algorithms; image; approximation; formulation; greedy; function; information; cost; manner; image; programming; approximation; recognition; image; segmentation; segmentation; jigsaw; segmentation; quadratic; solution; contextual; theory; greedy

Predicting Trust and Distrust in Social Networks - DuBois,T.; Golbeck,J.; Srinivasan, Aravind (Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom), 2011)
As user-generated content and interactions have overtaken the web as the default mode of use, questions of whom and what to trust have become increasingly important. Fortunately, online social networks and social media have made it easy for users to indicate whom they trust and whom they do not. However, this does not solve the problem since each user is only likely to know a tiny fraction of other users, we must have methods for inferring trust - and distrust - between users who do not know one another. In this paper, we present a new method for computing both trust and distrust (i.e., positive and negative trust). We do this by combining an inference algorithm that relies on a probabilistic interpretation of trust based on random graphs with a modified spring-embedding algorithm. Our algorithm correctly classifies hidden trust edges as positive or negative with high accuracy. These results are useful in a wide range of social web applications where trust is important to user behavior and satisfaction.
Keywords: distrust prediction; Electronic publishing; Encyclopedias; graph theory; inference algorithm; Inference algorithms; inference mechanisms; Internet; negative trust; online social networks; positive trust; Prediction algorithms; probability; random graphs; security of data; social media; social networking (online); spring-embedding algorithm; Training; trust inference; trust probabilistic interpretation; user behavior; user satisfaction; user-generated content; user-generated interactions

Privacy in social networks: A survey - Zheleva,E.; Getoor, Lise (Social Network Data Analytics, 2011)
In this chapter, we survey the literature on privacy in social networks. We focus both on online social networks and online affiliation networks. We formally define the possible privacy breaches and describe the privacy attacks that have been studied. We present definitions of privacy in the context of anonymization together with existing anonymization techniques.

A probabilistic approach for learning folksonomies from structured data - Plangprasopchok,Anon; Lerman,Kristina; Getoor, Lise (Proceedings of the fourth ACM international conference on Web search and data mining, 2011)
Learning structured representations has emerged as an important problem in many domains, including document and Web data mining, bioinformatics, and image analysis. One approach to learning complex structures is to integrate many smaller, incomplete and noisy structure fragments. In this work, we present an unsupervised probabilistic approach that extends affinity propagation [7] to combine the small ontological fragments into a collection of integrated, consistent, and larger folksonomies. This is a challenging task because the method must aggregate similar structures while avoiding structural inconsistencies and handling noise. We validate the approach on a real-world social media dataset, comprised of shallow personal hierarchies specified by many individual users, collected from the photosharing website Flickr. Our empirical results show that our proposed approach is able to construct deeper and denser structures, compared to an approach using only the standard affinity propagation algorithm. Additionally, the approach yields better overall integration quality than a state-of-the-art approach based on incremental relational clustering.
Keywords: collective knowledge; data mining; folksonomies; social information processing; social metadata; taxonomies

Rapid understanding of scientific paper collections: integrating statistics, text analysis, and visualization - Dunne,C.; Shneiderman, Ben; Gove,R.; Klavans,J.; Dorr, Bonnie J (University of Maryland, Human-Computer Interaction Lab Tech Report HCIL-2011, 2011)
Keeping up with rapidly growing research fields, especially when there aremultiple interdisciplinary sources, requires substantial effort for researchers, program managers, or venture capital investors. Current theories and tools are directed at finding a paper or website, not gaining an understanding of the key papers, authors, controversies, and hypotheses. This report presents an effort to integrate statistics, text analytics, and visualization in a multiple coordinated window environment that supports exploration. Our prototype system, Action Science Explorer (ASE), provides an environment for demon- strating principles of coordination and conducting iterative usability tests of them with interested and knowledgeable users. We developed an under- standing of the value of reference management, statistics, citation context extraction, natural language summarization for single and multiple docu- ments, filters to interactively select key papers, and network visualization to see citation patterns and identify clusters. The three-phase usability study guided our revisions to ASE and led us to improve the testing methods.

Real-time dynamics simulation of unmanned sea surface vehicle for virtual environments - Thakur,A.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2011)

Recent advances and future challenges in automated manufacturing planning - Bourne,D.; Corney,J.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2011)

Role of Zooplankton Diversity in Vibrio Cholerae Population Dynamics and in the Incidence of Cholera in the Bangladesh Sundarbans - De Magny,Guillaume Constantin; Mozumder,Pronob K.; Grim,Christopher J.; Hasan,Nur A.; Naser,M. Niamul; Alam,Munirul; Sack,R. Bradley; Huq,Anwar; Rita R Colwell (Applied and Environmental Microbiology, 2011)
Vibrio cholerae, a bacterium autochthonous to the aquatic environment, is the causative agent of cholera, a severe watery, life-threatening diarrheal disease occurring predominantly in developing countries. V. cholerae, including both serogroups O1 and O139, is found in association with crustacean zooplankton, mainly copepods, and notably in ponds, rivers, and estuarine systems globally. The incidence of cholera and occurrence of pathogenic V. cholerae strains with zooplankton were studied in two areas of Bangladesh: Bakerganj and Mathbaria. Chitinous zooplankton communities of several bodies of water were analyzed in order to understand the interaction of the zooplankton population composition with the population dynamics of pathogenic V. cholerae and incidence of cholera. Two dominant zooplankton groups were found to be consistently associated with detection of V. cholerae and/or occurrence of cholera cases, namely, rotifers and cladocerans, in addition to copepods. Local differences indicate there are subtle ecological factors that can influence interactions between V. cholerae, its plankton hosts, and the incidence of cholera.

Scalable fast multipole methods on distributed heterogeneous architectures - Hu,Qi; Gumerov, Nail A.; Duraiswami, Ramani (High Performance Computing, Networking, Storage and Analysis (SC), 2011 International Conference for, 2011)
We fundamentally reconsider implementation of the Fast Multipole Method (FMM) on a computing node with a heterogeneous CPU-GPU architecture with multicore CPU(s) and one or more GPU accelerators, as well as on an interconnected cluster of such nodes. The FMM is a divide- and-conquer algorithm that performs a fast N-body sum using a spatial decomposition and is often used in a time- stepping or iterative loop. Using the observation that the local summation and the analysis-based translation parts of the FMM are independent, we map these respectively to the GPUs and CPUs. Careful analysis of the FMM is performed to distribute work optimally between the multicore CPUs and the GPU accelerators. We first develop a single node version where the CPU part is parallelized using OpenMP and the GPU version via CUDA. New parallel algorithms for creating FMM data structures are presented together with load balancing strategies for the single node and distributed multiple-node versions. Our implementation can perform the N-body sum for 128M particles on 16 nodes in 4.23 seconds, a performance not achieved by others in the literature on such clusters.
Keywords: accelerators; OpenMP; analysis; algorithm; iterative; and; architecture; CUDA; FMM; architectures; architectures; divide-and-conquer; based; conquer; CPU-GPU; CPU; scalable; data; fast; heterogeneous; loop; data; loop; multicore; methods; graphics; methods; multiprocessing; methods; time; multipole; parts; distributed; PROCESSING; stepping; structures; divide; structures; GPU; systems; parallel; translation; units; iterative

Secure computation with sublinear amortized work - Gordon,D.; Katz, Jonathan; Kolesnikov,V.; Malkin,T.; Raykova,M.; Vahlis,Y. (Cryptology ePrint Archive, Report 2011/482, 2011)
Traditional approaches to secure computation begin by representing the function f beingcomputed as a circuit. For any function f that depends on each of its inputs, this implies a protocol with complexity at least linear in the input size. In fact, linear running time is inherent for secure computation of non-trivial functions, since each party must “touch” every bit of their input lest information about other party’s input be leaked. This seems to rule out many interesting applications of secure computation in scenarios where at least one of the inputs is huge and sublinear-time algorithms can be utilized in the insecure setting; private database search is a prime example. We present an approach to secure two-party computation that yields sublinear-time proto- cols, in an amortized sense, for functions that can be computed in sublinear time on a random access machine (RAM). Furthermore, a party whose input is “small” is required to maintain only small state. We provide a generic protocol that achieves the claimed complexity, based on any oblivious RAM and any protocol for secure two-party computation. We then present an optimized version of this protocol, where generic secure two-party computation is used only for evaluating a small number of simple operations.

"Seeing" ENF: natural time stamp for digital video via optical sensing and signal processing - Garg,Ravi; Varna,Avinash L.; M. Wu (Proceedings of the 19th ACM international conference on Multimedia, 2011)
Electric Network Frequency (ENF) fluctuates slightly over time from its nominal value of 50 Hz/60 Hz. The fluctuations in the ENF remain consistent across the entire power grid even when measured at physically distant locations. The near-invisible flickering of fluorescent lights connected to the power mains reflect these fluctuations present in the ENF. In this paper, mechanisms using optical sensors and video cameras to record and validate the presence of the ENF fluctuations in fluorescent lighting are presented. Signal processing techniques are applied to demonstrate a high correlation between the fluctuations in the ENF signal captured from fluorescent lighting and the ENF signal captured directly from power mains supply. The proposed technique is then used to demonstrate the presence of the ENF signal in video recordings taken in various geographical areas. Experimental results show that the ENF signal can be used as a natural timestamp for optical sensor recordings and video surveillance recordings from indoor environments under fluorescent lighting. Application of the ENF signal analysis to tampering detection of surveillance video recordings is also demonstrated.
Keywords: electric network frequency; information forensics; timestamp; video authentication

Teaching cross-platform design and testing methods for embedded systems using DICE - Bhattacharyya, Shuvra S.; Plishker,William; Gupta, Ayush; Chung-Ching Shen (ACM, 2011)
DICE (the DSPCAD Integrative Command Line Environment) is a package of utilities that facilitates efficient management of software projects. Key areas of emphasis in DICE are cross-platform operation, support for projects that integrate heterogeneous programming languages, and support for applying and integrating different kinds of design and testing methodologies. The package is being developed at the University of Maryland to facilitate the research and teaching of methods for implementation, testing, evolution, and revision of engineering software. The platform- and language-independent focus of DICE makes it an effective vehicle for teaching high-productivity, high-reliability methods for design and implementation of embedded systems for a variety of courses. In this paper, we provide an overview of features of DICE --- particularly as they relate to testing driven design practices --- that are useful in embedded systems education, and discuss examples and experiences of applying the tool in courses at the University of Maryland aimed at diverse groups of students --- undergraduate programming concepts for engineers, graduate VLSI architectures (aimed at research-oriented students), and graduate FPGA system design (aimed at professional Master's students).

Temperature regulation of virulence factors in the pathogen Vibrio coralliilyticus - Kimes,Nikole E.; Grim,Christopher J.; Johnson,Wesley R.; Hasan,Nur A.; Tall,Ben D.; Kothary,Mahendra H.; Kiss,Hajnalka; Munk,A. Christine; Tapia,Roxanne; Green,Lance; Detter,Chris; Bruce,David C.; et al. (The ISME Journal, 2011)
Sea surface temperatures (SST) are rising because of global climate change. As a result, pathogenic Vibrio species that infect humans and marine organisms during warmer summer months are of growing concern. Coral reefs, in particular, are already experiencing unprecedented degradation worldwide due in part to infectious disease outbreaks and bleaching episodes that are exacerbated by increasing SST. For example, Vibrio coralliilyticus, a globally distributed bacterium associated with multiple coral diseases, infects corals at temperatures above 27 °C. The mechanisms underlying this temperature-dependent pathogenicity, however, are unknown. In this study, we identify potential virulence mechanisms using whole genome sequencing of V. coralliilyticus ATCC (American Type Culture Collection) BAA-450. Furthermore, we demonstrate direct temperature regulation of numerous virulence factors using proteomic analysis and bioassays. Virulence factors involved in motility, host degradation, secretion, antimicrobial resistance and transcriptional regulation are upregulated at the higher virulent temperature of 27 °C, concurrent with phenotypic changes in motility, antibiotic resistance, hemolysis, cytotoxicity and bioluminescence. These results provide evidence that temperature regulates multiple virulence mechanisms in V. coralliilyticus, independent of abundance. The ecological and biological significance of this temperature-dependent virulence response is reinforced by climate change models that predict tropical SST to consistently exceed 27 °C during the spring, summer and fall seasons. We propose V. coralliilyticus as a model Gram-negative bacterium to study temperature-dependent pathogenicity in Vibrio-related diseases.
Keywords: ecophysiology; ecosystems; environmental biotechnology; geomicrobiology; ISME J; microbe interactions; microbial communities; microbial ecology; microbial engineering; microbial epidemiology; microbial genomics; microorganisms

Toward improved aeromechanics simulations using recent advancements in scientific computing - Hu,Q.; Syal,M.; Gumerov, Nail A.; Duraiswami, Ramani; Leishman,J.G. (Proceedings 67th Annual Forum of the American Helicopter Society, 2011)

Trajectory planning with look-ahead for Unmanned Sea Surface Vehicles to handle environmental disturbances - Svec,P.; Schwartz,M.; Thakur,A.; Gupta,S.K. (2011)

TreeVersity: Comparing tree structures by topology and node's attributes differences - Gomez,J.A.G.; Buck-Coleman,A.; Plaisant, Catherine; Shneiderman, Ben (Visual Analytics Science and Technology (VAST), 2011 IEEE Conference on, 2011)
It is common to classify data in hierarchies, they provide a comprehensible way of understanding big amounts of data. From budgets to organizational charts or even the stock market, trees are everywhere and people find them easy to use. However when analysts need to compare two versions of the same tree structure, or two related taxonomies, the task is not so easy. Much work has been done on this topic, but almost all of it has been restricted to either compare the trees by topology, or by the node attribute values. With this project we are proposing TreeVersity, a framework for comparing tree structures, both by structural changes and by differences in the node attributes. This paper is based on our previous work on comparing traffic agencies using LifeFlow [1, 2] and on a first prototype of TreeVersity.
Keywords: (mathematics); agencies; tree; attributes; changes; topology; classification; hierarchy; node; classification; trees; comparison; pattern; differences; structural; differences; traffic; LifeFlow; TreeVersity; data; STRUCTURES

TreeVersity: Comparing tree structures by topology and node's attributes differences - Gomez,J.A.G.; Buck-Coleman,A.; Plaisant, Catherine; Shneiderman, Ben (2011 IEEE Conference on Visual Analytics Science and Technology (VAST), 2011)
It is common to classify data in hierarchies, they provide a comprehensible way of understanding big amounts of data. From budgets to organizational charts or even the stock market, trees are everywhere and people find them easy to use. However when analysts need to compare two versions of the same tree structure, or two related taxonomies, the task is not so easy. Much work has been done on this topic, but almost all of it has been restricted to either compare the trees by topology, or by the node attribute values. With this project we are proposing TreeVersity, a framework for comparing tree structures, both by structural changes and by differences in the node attributes. This paper is based on our previous work on comparing traffic agencies using LifeFlow [1, 2] and on a first prototype of TreeVersity.
Keywords: Computer science; data classification; Data visualization; Educational institutions; hierarchy; Image color analysis; LifeFlow; node attributes differences; Pattern classification; structural changes; Topology; topology attributes differences; traffic agencies; tree structures comparison; trees (mathematics); TreeVersity; Vegetation; Visualization

Tutorial-Graph Analytics — Lessons Learned and Challenges Ahead - Wong,P.C.; Chen,C.; Görg,C.; Shneiderman, Ben; Stasko,J.; Thomas,J. (IEEE Computer Graphics and Applications, 2011)

A Two Degree of Freedom Nanopositioner With Electrothermal Actuator for Decoupled Motion - Kim,Yong-Sik; Dagalakis,Nicholas G.; Gupta, Satyandra K. (ASME, 2011)
Building a two degree-of-freedom (2 DOF) MEMS nanopositioner with decoupled X-Y motion has been a challenge in nanopositioner design. In this paper a novel design concept on making the decoupled motion of the MEMS nanopositioner is suggested. The suggested nanopositioner has two electrothermal actuators and employs a fully nested motion platform with suspended anchors. The suggested MEMS nanopositioner is capable of delivering displacement from the electrothermal actuator to the motion platform without coupled motion between the two X-Y axes. The design concept, finite element analysis (FEA) results, fabrication procedures and the performance of the 2 DOF nanopositioner is presented. In order to test the nanopositioner moving platform decoupled motion, one actuator moves the platform by 60 µm, while the other actuator is kept at the same position. The platform position cross talk error was measured to be less than 1 µm standard deviation.

Understanding actor loyalty to event-based groups in affiliation networks - Sharara,H.; Singh,L.; Getoor, Lise; Mann,J. (Social Network Analysis and Mining, 2011)
In this paper, we introduce a method for analyzing the temporal dynamics of affiliation networks. We define affiliation groups which describe temporally related subsets of actors and describe an approach for exploring changing memberships in these affiliation groups over time. To model the dynamic behavior in these networks, we consider the concept of loyalty and introduce a measure that captures an actor’s loyalty to an affiliation group as the degree of ‘commitment’ an actor shows to the group over time. We evaluate our measure using three real world affiliation networks: a publication network, a senate bill cosponsorship network, and a dolphin network. The results show the utility of our measure for analyzing the dynamic behavior of actors and quantifying their loyalty to different time-varying affiliation groups.

Understanding Scientific Literature Networks: An Evaluation of Action Science Explorer - Gove,R.; Dunne,C.; Shneiderman, Ben; Klavans,J.; Dorr, Bonnie J (University of Maryland at College Park, 2011)
Action Science Explorer (ASE) is a tool designed to supportusers in rapidly generating readily consumable summaries of academic literature. The authors describe ASE and report on how early formative evaluations led to a mature system evaluation, consisting of an in-depth empirical evaluation with 4 domain expert participants. The user study tasks were of two types: predefined tasks to test system perfor- mance in common scenarios, and user-defined tasks to test the system’s usefulness for custom exploration goals. This paper concludes by describing ASE’s attribute ranking ca- pability which is a novel contribution for exploring scientific literature networks. It makes design recommendations to: give the users control over which documents to explore, easy- to-understand metrics for ranking documents, and overviews of the document set in coordinated views along with details- on-demand of specific papers.

Usability and Accessibility in Consumer Health Informatics: Current Trends and Future Challenges - Goldberg,Larry; Lide,Bettijoyce; Lowry,Svetlana; Massett,Holly A.; O'Connell,Trisha; Preece,Jennifer; Quesenbery,Whitney; Shneiderman, Ben (American Journal of Preventive Medicine, 2011)
It is a truism that, for innovative eHealth systems to have true value and impact, they must first and foremost be usable and accessible by clinicians, consumers, and other stakeholders. In this paper, current trends and future challenges in the usability and accessibility of consumer health informatics will be described. Consumer expectations of their healthcare providers and healthcare records in this new era of consumer-directed care will be explored, and innovative visualizations, assistive technologies, and other ways that healthcare information is currently being provided and/or shared will be described. Challenges for ensuring the usability of current and future systems will also be discussed. An innovative model for conducting systematic, timely, user-centered research on consumer-facing websites at the National Cancer Institute (NCI) and the ongoing efforts at the National Institute of Standards and Technology (NIST) to promote health information technology (HIT) usability standards and evaluation criteria will also be presented.

Using classifier cascades for scalable e-mail classification - Pujara,J.; Daumé, Hal; Getoor, Lise (Collaboration, Electronic Messaging, Anti-Abuse and Spam Conference, ACM International Conference Proceedings Series, 2011)
In many real-world scenarios, we must make judgments in the presence of computational constraints. One common computational constraint arises when the features used to make a judgment each have differing acquisition costs, but there is a fixed total budget for a set of judgments. Par- ticularly when there are a large number of classifications that must be made in a real-time, an intelligent strategy for optimizing accuracy versus computational costs is essential. E-mail classification is an area where accurate and timely results require such a trade-off. We identify two scenarios where intelligent feature acquisition can improve classifier performance. In granular classification we seek to clas- sify e-mails with increasingly specific labels structured in a hierarchy, where each level of the hierarchy requires a differ- ent trade-off between cost and accuracy. In load-sensitive classification, we classify a set of instances within an ar- bitrary total budget for acquiring features. Our method, Adaptive Classifier Cascades (ACC), designs a policy to combine a series of base classifiers with increasing compu- tational costs given a desired trade-off between cost and ac- curacy. Using this method, we learn a relationship between feature costs and label hierarchies, for granular classification and cost budgets, for load-sensitive classification. We eval- uate our method on real-world e-mail datasets with realistic estimates of feature acquisition cost, and we demonstrate su- perior results when compared to baseline classifiers that do not have a granular, cost-sensitive feature acquisition policy.

Value of information lattice: exploiting probabilistic independence for effective feature subset acquisition - Bilgic,Mustafa; Getoor, Lise (Journal of Artificial Intelligence Research, 2011)
We address the cost-sensitive feature acquisition problem, where misclassifying an instance is costly but the expected misclassification cost can be reduced by acquiring the values of the missing features. Because acquiring the features is costly as well, the objective is to acquire the right set of features so that the sum of the feature acquisition cost and misclassification cost is minimized. We describe the Value of Information Lattice (VOILA), an optimal and eficient feature subset acquisition framework. Unlike the common practice, which is to acquire features greedily, VOILA can reason with subsets of features. VOILA eficiently searches the space of possible feature subsets by discovering and exploiting conditional independence properties between the features and it reuses probabilistic inference computations to further speed up the process. Through empirical evaluation on five medical datasets, we show that the greedy strategy is often reluctant to acquire features, as it cannot forecast the benefit of acquiring multiple features in combination.

Variable remapping of images from very different sources - Wei Zhang; Yanlin Guo; Meth, R.; Sokoloff, H.; Pope, A.; Strat, T.; Chellapa, Rama (2011 18th IEEE International Conference on Image Processing (ICIP), 2011)
We present a system which registers image sequences acquired by very different sources, so that multiple views could be transformed to the same coordinates system. This enables the functionality of automatic object identification and confirmation across views and platforms. The capability of the system comes from three ingredients: 1) image context enlargement through temporal integration; 2) robust motion estimation using the G-RANSAC framework with a relaxed correspondence criteria; 3) constrained motion estimation within the G-RANSAC framework. The proposed system has worked successfully on thousands of frames from multiple collections with significant variations in scale and resolution.
Keywords: automatic object identification; Buildings; CAMERAS; Conferences; constrained motion estimation; coordinates system; Estimation; G-RANSAC framework; image context enlargement; Image Enhancement; image registration; image sequence registration; Image sequences; Motion estimation; Robustness; temporal integration; variable image remapping

Visual Exploration across Biomedical Databases - Lieberman,M.D.; Taheri, S.; Guo,Huimin; Mirrashed,F.; Yahav,I.; Aris,A.; Shneiderman, Ben (IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2011)
Though biomedical research often draws on knowledge from a wide variety of fields, few visualization methods for biomedical data incorporate meaningful cross-database exploration. A new approach is offered for visualizing and exploring a query-based subset of multiple heterogeneous biomedical databases. Databases are modeled as an entity-relation graph containing nodes (database records) and links (relationships between records). Users specify a keyword search string to retrieve an initial set of nodes, and then explore intra- and interdatabase links. Results are visualized with user-defined semantic substrates to take advantage of the rich set of attributes usually present in biomedical data. Comments from domain experts indicate that this visualization method is potentially advantageous for biomedical knowledge exploration.
Keywords: Bioinformatics; Biomedical computing; biomedical databases; cross-database exploration; Data exploration and discovery; Data visualization; database management systems; Databases, Factual; DNA; graph theory; Information Storage and Retrieval; information visualization.; Keyword search; medical computing; natural language processing; Proteins; semantic networks; semantics; sequences; text mining; User-Computer Interface; user-defined semantics; visual databases

Warming Oceans, Phytoplankton, and River Discharge: Implications for Cholera Outbreaks - Jutla,Antarpreet S.; Akanda,Ali S.; Griffiths,Jeffrey K.; Rita R Colwell; Islam,Shafiqul (The American Journal of Tropical Medicine and Hygiene, 2011)
Phytoplankton abundance is inversely related to sea surface temperature (SST). However, a positive relationship is observed between SST and phytoplankton abundance in coastal waters of Bay of Bengal. This has led to an assertion that in a warming climate, rise in SST may increase phytoplankton blooms and, therefore, cholera outbreaks. Here, we explain why a positive SST-phytoplankton relationship exists in the Bay of Bengal and the implications of such a relationship on cholera dynamics. We found clear evidence of two independent physical drivers for phytoplankton abundance. The first one is the widely accepted phytoplankton blooming produced by the upwelling of cold, nutrient-rich deep ocean waters. The second, which explains the Bay of Bengal findings, is coastal phytoplankton blooming during high river discharges with terrestrial nutrients. Causal mechanisms should be understood when associating SST with phytoplankton and subsequent cholera outbreaks in regions where freshwater discharge are a predominant mechanism for phytoplankton production.

Why is My Internet Slow?: Making Network Speeds Visible - Marshini Chetty; Haslem, David; Baird, Andrew; Ofoha, Ugochi; Sumner, Bethany; Grinter, Rebecca (SIGCHI '11, 2011)
With widespread broadband adoption, more households report experiencing sub-optimal speeds. Not only are slow speeds frustrating, they may indicate consumers are not receiving the services they are paying for from their internet service providers. Yet, determining the speed and source of slow-downs is difficult because few tools exist for broadband management. We report on results of a field trial with 10 households using a visual network probe designed to address these problems. We describe the results of the study and provide design implications for future tools. More importantly, we argue that tools like this can educate and empower consumers by making broadband speeds and sources of slow-downs more visible.
Keywords: broadband speed; broadband tools; home networks

Active inference for collective classification - Bilgic,M.; Getoor, Lise (AAAI’10, 2010)
Labeling nodes in a network is an important problem that has seen a growing interest. A number of methods that exploit both local and relational information have been developed for this task. Acquiring the labels for a few nodes at inference time can greatly improve the ac- curacy, however the question of figuring out which node labels to acquire is challenging. Previous approaches have been based on simple structural properties. Here, we present a novel technique, which we refer to as re- flect and correct, that can learn and predict when the un- derlying classification system is likely to make mistakes and it suggests acquisitions to correct those mistakes.

Active learning for networked data - Bilgic,M.; Mihalkova,L.; Getoor, Lise (ICML’10, 2010)
We introduce a novel active learning algo-rithm for classification of network data. In this setting, training instances are connected by a set of links to form a network, the labels of linked nodes are correlated, and the goal is to exploit these dependencies and accu- rately label the nodes. This problem arises in many domains, including social and biologi- cal network analysis and document classifica- tion, and there has been much recent interest in methods that collectively classify the nodes in the network. While in many cases labeled examples are expensive, often network infor- mation is available. We show how an active learning algorithm can take advantage of net- work structure. Our algorithm effectively ex- ploits the links between instances and the in- teraction between the local and collective as- pects of a classifier to improve the accuracy of learning from fewer labeled examples. We ex- periment with two real-world benchmark col- lective classification domains, and show that we are able to achieve extremely accurate re- sults even when only a small fraction of the data is labeled.

AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead - Horvitz,Eric; Getoor, Lise; Guestrin,Carlos; Hendler,James; Konstan,Joseph; Subramanian,Devika; Wellman,Michael; Kautz,Henry (AI Magazine, 2010)
AI Theory and Practice: A Discussion on Hard Challenges and Opportunities Ahead

Alignment and clustering of phylogenetic markers - implications for microbial diversity studies - White,James R; Navlakha,Saket; Nagarajan,Niranjan; Ghodsi,Mohammad-Reza; Kingsford, Carl; Pop, Mihai (BMC Bioinformatics, 2010)
Molecular studies of microbial diversity have provided many insights into the bacterial communities inhabiting the human body and the environment. A common first step in such studies is a survey of conserved marker genes (primarily 16S rRNA) to characterize the taxonomic composition and diversity of these communities. To date, however, there exists significant variability in analysis methods employed in these studies.

Articulation-Invariant Representation of Non-planar Shapes - Gopalan,Raghuraman; Turaga,Pavan; Chellapa, Rama (Computer Vision – ECCV 2010Computer Vision – ECCV 2010, 2010)
Given a set of points corresponding to a 2D projection of a non-planar shape, we would like to obtain a representation invariant to articulations (under no self-occlusions). It is a challenging problem since we need to account for the changes in 2D shape due to 3D articulations, viewpoint variations, as well as the varying effects of imaging process on different regions of the shape due to its non-planarity. By modeling an articulating shape as a combination of approximate convex parts connected by non-convex junctions, we propose to preserve distances between a pair of points by (i) estimating the parts of the shape through approximate convex decomposition, by introducing a robust measure of convexity and (ii) performing part-wise affine normalization by assuming a weak perspective camera model, and then relating the points using the inner distance which is insensitive to planar articulations. We demonstrate the effectiveness of our representation on a dataset with non-planar articulations, and on standard shape retrieval datasets like MPEG-7.

Audio visual scene analysis using spherical arrays and cameras. - O'donovan,Adam; Duraiswami, Ramani; Zotkin,Dmitry N; Gumerov, Nail A. (The Journal of the Acoustical Society of America, 2010)
While audition and vision are used together by living beings to make sense of the world, the observation of the world using machines in applications such as surveillance and robotics has proceeded largely separately. We describe the use of spherical microphone arrays as “audio cameras” and spherical array of video cameras as a tool to perform multi‐modal scene analysis that attempts to answer questions such as “Who?,”, “What?,” “Where?,” and “Why?.” Signal processing algorithms to identify the number of people and their identities and to isolate and dereverberate their speech using multi‐modal processing will be described. The use of graphics processor based signal processing allows for real‐time implementation of these algorithms. [Work supported by ONR.]

Authenticated broadcast with a partially compromised public-key infrastructure - Gordon,S.; Katz, Jonathan; Kumaresan,R.; Yerukhimovich,A. (Stabilization, Safety, and Security of Distributed Systems, 2010)
Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. Almost all existing protocols, however, do not distinguish between corrupted parties (who do not follow the protocol), and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly). We explore conditions under which it is possible to construct broadcast protocols that still provide the usual guarantees (i.e., validity/agreement) to the latter.Consider a network of n parties, where an adversary has compromised the secret keys of up to t c honest parties and, in addition, fully controls the behavior of up to t a other parties. We show that for any fixed t c  > 0, and any fixed t a , there exists an efficient protocol for broadcast if and only if 2t a  + min (t a , t c ) < n. (When t c  = 0, standard results imply feasibility.) We also show that if t c , t a are not fixed, but are only guaranteed to satisfy the bound above, then broadcast is impossible to achieve except for a few specific values of n; for these “exceptional” values of n, we demonstrate a broadcast protocol. Taken together, our results give a complete characterization of this problem.

Automated generation of an efficient MPEG-4 Reconfigurable Video Coding decoder implementation - Gu, Ruirui; Piat, J.; Raulet, M.; Janneck, J.W.; Bhattacharyya, Shuvra S. (2010 Conference on Design and Architectures for Signal and Image Processing (DASIP), 2010)
This paper proposes an automatic design flow from user-friendly design to efficient implementation of video processing systems. This design flow starts with the use of coarse-grain dataflow representations based on the CAL language, which is a complete language for dataflow programming of embedded systems. Our approach integrates previously developed techniques for detecting synchronous dataflow (SDF) regions within larger CAL networks, and exploiting the static structure of such regions using analysis tools in The Dataflow interchange format Package (TDP). Using a new XML format that we have developed to exchange dataflow information between different dataflow tools, we explore systematic implementation of signal processing systems using CAL, SDF-like region detection, TDP-based static scheduling, and CAL-to-C (CAL2C) translation. Our approach, which is a novel integration of three complementary dataflow tools - the CAL parser, TDP, and CAL2C - is demonstrated on an MPEG Reconfigurable Video Coding (RVC) decoder.
Keywords: automated generation; automatic design flow; CAL language; CAL networks; CAL-to-C translation; CAL2C translation; coarse-grain dataflow representations; Computational modeling; data flow computing; dataflow information; Dataflow programming; decoding; Digital signal processing; Libraries; MPEG-4 reconfigurable video coding decoder implementation; parallel languages; SDF detection; synchronous dataflow detection; TDP; TDP-based static scheduling; The Dataflow interchange format Package; Transform coding; user-friendly design; video coding; video processing systems; XML; XML format

cdec: A decoder, alignment, and learning framework for finite-state and context-free translation models - Dyer,C.; Weese,J.; Setiawan,H.; Lopez,A.; Ture,F.; Eidelman,V.; Ganitkevitch,J.; Blunsom,P.; Resnik, Philip (Proceedings of the ACL 2010 System Demonstrations, 2010)

Characterizing scattering coefficients numerically via the fast multipole accelerated boundary element method. - Gumerov, Nail A.; Duraiswami, Ramani (The Journal of the Acoustical Society of America, 2010)
Various panels are used in acoustical installations to provide desired characteristics to spaces to be used for listening. These panels have complex shapes with geometrical features that have sizes corresponding to wavelengths of sounds of interest. The complex interaction of acoustical waves with these shapes is what gives these surfaces their desirable properties. Experimental characterization of the acoustical properties of these surfaces under random and specular incidence is relatively time consuming. An alternate procedure is to numerically simulate the scattering behavior, and then computing the coefficients of interest from the simulation. A significant obstacle to such computations is the time taken for simulation. Fast multipole acceleration of boundary element methods [Gumerov & Duraiswami, J. Acoust. Soc. Am. 125 (2009)] is a promising approach to speeding up computations. We report on the application of this method to the computation of various scattering coefficients.

Children's roles using keyword search interfaces at home - Druin, Allison; Foss,E.; Hutchinson,H.; Golub,E.; Hatley,L. (Proceedings of the 28th international conference on Human factors in computing systems, 2010)

Clear Panels: a technique to design mobile application interactivity - Brown,Q.; Bonsignore,E.; Hatley,L.; Druin, Allison; Walsh,G.; Foss,E.; Brewer,R.; Hammer,J.; Golub,E. (Proceedings of the 8th ACM Conference on Designing Interactive Systems, 2010)

Comparative Genomics of Clinical and Environmental Vibrio Mimicus - Hasan,Nur A.; Grim,Christopher J.; Haley,Bradd J.; Jongsik Chun; Alam,Munirul; Taviani,Elisa; Mozammel Hoq; Munk,A. Christine; Rita R Colwell (Proceedings of the National Academy of SciencesPNAS, 2010)
Whether Vibrio mimicus is a variant of Vibrio cholerae or a separate species has been the subject of taxonomic controversy. A genomic analysis was undertaken to resolve the issue. The genomes of V. mimicus MB451, a clinical isolate, and VM223, an environmental isolate, comprise ca. 4,347,971 and 4,313,453 bp and encode 3,802 and 3,290 ORFs, respectively. As in other vibrios, chromosome I (C-I) predominantly contains genes necessary for growth and viability, whereas chromosome II (C-II) bears genes for adaptation to environmental change. C-I harbors many virulence genes, including some not previously reported in V. mimicus, such as mannose-sensitive hemagglutinin (MSHA), and enterotoxigenic hemolysin (HlyA); C-II encodes a variant of Vibrio pathogenicity island 2 (VPI-2), and Vibrio seventh pandemic island II (VSP-II) cluster of genes. Extensive genomic rearrangement in C-II indicates it is a hot spot for evolution and genesis of speciation for the genus Vibrio. The number of virulence regions discovered in this study (VSP-II, MSHA, HlyA, type IV pilin, PilE, and integron integrase, IntI4) with no notable difference in potential virulence genes between clinical and environmental strains suggests these genes also may play a role in the environment and that pathogenic strains may arise in the environment. Significant genome synteny with prototypic pre-seventh pandemic strains of V. cholerae was observed, and the results of phylogenetic analysis support the hypothesis that, in the course of evolution, V. mimicus and V. cholerae diverged from a common ancestor with a prototypic sixth pandemic genomic backbone.

Comparing and combining lighting insensitive approaches for face recognition - Gopalan,Raghuraman; Jacobs, David W. (Computer Vision and Image Understanding, 2010)
Face recognition under changing lighting conditions is a challenging problem in computer vision. In this paper, we analyze the relative strengths of different lighting insensitive representations, and propose efficient classifier combination schemes that result in better recognition rates. We consider two experimental settings, wherein we study the performance of different algorithms with (and without) prior information on the different illumination conditions present in the scene. In both settings, we focus on the problem of having just one exemplar per person in the gallery. Based on these observations, we design algorithms for integrating the individual classifiers to capture the significant aspects of each representation. We then illustrate the performance improvement obtained through our classifier combination algorithms on the illumination subset of the PIE dataset, and on the extended Yale-B dataset. Throughout, we consider galleries with both homogenous and heterogeneous lighting conditions.
Keywords: Classifier comparison and combination; face recognition; Gradient direction; lighting

COMPRESSIVE SENSING SYSTEM AND METHOD FOR BEARING ESTIMATION OF SPARSE SOURCES IN THE ANGLE DOMAIN - Cevher,Volkan; Gurbuz,Ali Cafer; McClellan,James H.; Chellapa, Rama (2010)
Compressive Sensing (CS) is an emerging area which uses a relatively small number of non-traditional samples in the form of randomized projections to reconstruct sparse or com-pressible signals. Direction-of-arrival (DOA) estimation is performed with an array of sensors using CS. Using random projections of the sensor data, along with a full waveform recording on one reference sensor, a sparse angle space scenario can be reconstructed, giving the number of sources and their DOA's. Signal processing algorithms are also developed and described herein for randomly deployable wireless sensor arrays that are severely constrained in communication bandwidth. There is a focus on the acoustic bearing estimation problem and it is shown that when the target bearings are modeled as a sparse vector in the angle space, functions of the low dimensional random projections of the microphone signals can be used to determine multiple source bearings as a solution of an 1]-norm minimization problem.

Computation of the head-related transfer function via the fast multipole accelerated boundary element method and its spherical harmonic representation - Gumerov, Nail A.; O'Donovan,Adam E.; Duraiswami, Ramani; Zotkin,Dmitry N (The Journal of the Acoustical Society of America, 2010)
The head-related transfer function (HRTF) is computed using the fast multipole accelerated boundary element method. For efficiency, the HRTF is computed using the reciprocity principle by placing a source at the ear and computing its field. Analysis is presented to modify the boundary value problem accordingly. To compute the HRTF corresponding to different ranges via a single computation, a compact and accurate representation of the HRTF, termed the spherical spectrum, is developed. Computations are reduced to a two stage process, the computation of the spherical spectrum and a subsequent evaluation of the HRTF. This representation allows easy interpolation and range extrapolation of HRTFs. HRTF computations are performed for the range of audible frequencies up to 20 kHz for several models including a sphere, human head models [the Neumann KU-100 (“Fritz”) and the Knowles KEMAR (“Kemar”) manikins], and head-and-torso model (the Kemar manikin). Comparisons between the different cases are provided. Comparisons with the computational data of other authors and available experimental data are conducted and show satisfactory agreement for the frequencies for which reliable experimental data are available. Results show that, given a good mesh, it is feasible to compute the HRTF over the full audible range on a regular personal computer.
Keywords: auditory evoked potentials; bioacoustics; boundary-elements methods; Ear; Harmonic analysis

A Computational Framework for Real-Time Unmanned Sea Surface Vehicle Motion Simulation - Thakur,Atul; Gupta, Satyandra K. (ASME, 2010)
Unmanned Sea Surface Vehicle (USSV) motion simulation in time domain is an important component of USSV design and operation. This capability is needed for hull design, operator training, controller synthesis and testing. Many applications such as simulators for operator training require real-time performance. Traditional approaches based on strip theory, although fast, abstract hulls into slender bodies, making the simulation results insensitive to changes in geometry. Computational fluid dynamics (CFD) based approaches are accurate but very slow. Potential flow based approaches are sensitive to hull geometry and take lesser amount of time than CFD based approaches. The motion simulation using potential flow theory involves following four main operations: (1) computation of dynamic pressure head due to fluid flow around the hull under the ocean wave, (2) computation of wet surface, (3) computing surface integral of dynamic pressure head over wet surface, and (4) solving the rigid body dynamics equation. First three operations depend upon the boat geometry complexity and need to be performed at each time step, making the simulation run very slow. In this paper, we investigate the problem of model simplification for real-time simulation of USSV model in time domain using potential flow theory, with arbitrary geometry under ocean waves with inviscid and irrotational flow. Using clustering based simplification scheme and parallel computing we obtained real time simulation performance.

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.

Connecting generations: developing co-design methods for older adults and children - Xie,B.; Druin, Allison; Fails,J.; Massey,S.; Golub,E.; Franckel,S.; Schneider,K. (Behaviour & Information Technology, 2010)

Constructing folksonomies by integrating structured metadata - Plangprasopchok,Anon; Lerman,Kristina; Getoor, Lise (Proceedings of the 19th international conference on World wide web, 2010)
Aggregating many personal hierarchies into a common taxonomy, also known as a folksonomy, presents several challenges due to its sparseness, ambiguity, noise, and inconsistency. We describe an approach to folksonomy learning based on relational clustering that addresses these challenges by exploiting structured metadata contained in personal hierarchies. Our approach clusters similar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. We study folksonomy learning using social metadata extracted from the photo-sharing site Flickr. We evaluate the learned folksonomy quantitatively by automatically comparing it to a reference taxonomy created by the Open Directory Project. Our empirical results suggest that the proposed approach improves upon the state-of-the-art folksonomy learning method.
Keywords: collective knowledge; data mining; folksonomies

Constructing Folksonomies by Integrating Structured Metadata with Relational Clustering - Plangprasopchok,A.; Lerman,K.; Getoor, Lise (Workshops at the Twenty-Fourth AAAI Conference on Artificial Intelligence, 2010)
Many social Web sites allow users to annotate the content with descriptive metadata, such as tags, and more recently also to organize content hierarchically. These types of struc- tured metadata provide valuable evidence for learning how a community organizes knowledge. For instance, we can ag- gregate many personal hierarchies into a common taxonomy, also known as a folksonomy, that will aid users in visual- izing and browsing social content, and also to help them in organizing their own content. However, learning from so- cial metadata presents several challenges: sparseness, ambi- guity, noise, and inconsistency. We describe an approach to folksonomy learning based on relational clustering that ad- dresses these challenges by exploiting structured metadata contained in personal hierarchies. Our approach clusters sim- ilar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. We study folksonomy learning using social metadata extracted from the photo-sharing site Flickr. We evaluate the learned folksonomy quantitatively by automatically comparing it to a reference taxonomy. Our empirical results suggest that the proposed framework, which addresses the challenges listed above, improves on existing folksonomy learning methods.

Context-Aware Query Recommendations - Ntoulas,Alexandros; Hwang,Heasoo; Getoor, Lise; Paparizos,Stelios; Lauw,Hady Wirawan (2010)
Described is a search-related technology in which context information regarding a user's prior search actions is used in making query recommendations for a current user action, such as a query or click. To determine whether each set or subset of context information is relevant to the user action, data obtained from a query log is evaluated. More particularly, a query transition (query-query) graph and a query click (query-URL) graph are extracted from the query log; vectors are computed for the current action and each context/sub-context and evaluated against vectors in the graphs to determine current action-to-context similarity. Also described is using similar context to provide the query recommendations, using parameters to control the similarity strictness, and/or whether more recent context information is more relevant than less recent context information, and using context information to distinguish between user sessions.

Conversion of viable but nonculturable Vibrio cholerae to the culturable state by co‐culture with eukaryotic cells - Senoh,Mitsutoshi; Ghosh‐Banerjee,Jayeeta; Ramamurthy,Thandavarayan; Hamabata,Takashi; Kurakawa,Takashi; Takeda,Makoto; Rita R Colwell; Nair,G. Balakrish; Takeda,Yoshifumi (Microbiology and Immunology, 2010)
VBNC Vibrio cholerae O139 VC-280 obtained by incubation in 1% solution of artificial sea water IO at 4°C for 74 days converted to the culturable state when co-cultured with CHO cells. Other eukaryotic cell lines, including HT-29, Caco-2, T84, HeLa, and Intestine 407, also supported conversion of VBNC cells to the culturable state. Conversion of VBNC V. cholerae O1 N16961 and V. cholerae O139 VC-280/pG13 to the culturable state, under the same conditions, was also confirmed. When VBNC V. cholerae O139 VC-280 was incubated in 1% IO at 4°C for up to 91 days, the number of cells converted by co-culture with CHO cells declined with each additional day of incubation and after 91 days conversion was not observed.
Keywords: conversion to culturability; co‐culture; eukaryotic cell; viable but nonculturable (VBNC) Vibrio cholerae

Deliberate Interactions: Characterizing Technology Use in Nairobi, Kenya - Wyche, Susan P.; Smyth, Thomas N.; Marshini Chetty; Aoki, Paul M.; Grinter, Rebecca E. (SIGCHI '10, 2010)
We present results from a qualitative study examining how professionals living and working in Nairobi, Kenya regularly use ICT in their everyday lives. There are two contributions of this work for the HCI community. First, we provide empirical evidence demonstrating constraints our participants encountered when using technology in an infrastructure-poor setting. These constraints are limited bandwidth, high costs, differing perceptions of responsiveness, and threats to physical and virtual security. Second, we use our findings to critically evaluate the "access, anytime and anywhere" construct shaping the design of future technologies. We present an alternative vision called deliberate interactions--a planned and purposeful interaction style that involves offline preparation and discuss ways ICT can support this online usage behavior.
Keywords: everyday technology; hci4d; Kenya; urban computing

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.

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

Developing Autonomy for Unmanned Surface Vehicles by Using Virtual Environments - Kavetsky,R.; Gupta,S.K. (ENERGETICS TECHNOLOGY CENTER INC LA PLATA MD, 2010)
We address the problem of automated synthesis of an action selection policy for an unmanned vehicle operating in an environment with a deceptive adversary. We introduce a new synthesis approach using which an initial version of the policy is automatically generated and then gradually refined by detecting and fixing its shortcomings. Our focus is specifically on automated synthesis of a policy used for blocking the advancement of an intruder boat toward a valuable target. The USV must generate specific maneuvers for blocking. The intruder is human competitive and exhibits a deceptive behavior so that the USV cannot exploit regularity in its attacking behavior. We compared the performance of a hand coded USVs blocking policy to the performance of a policy that was automatically synthesized. Our results show that the performance of the automatically generated USVs policy exceed the performance of the hand coded policy and thus demonstrates the feasibility of the proposed approach.

Discovery of novel Vibrio cholerae VSP‐II genomic islands using comparative genomic analysis - Taviani,Elisa; Grim,Christopher J.; Choi,Jinna; Jongsik Chun; Haley,Bradd; Hasan,Nur A.; Huq,Anwar; Rita R Colwell (FEMS Microbiology Letters, 2010)
This report describes Vibrio seventh pandemic island II (VSP-II) and three novel variants revealed by comparative genomics of 23 Vibrio cholerae strains and their presence among a large and diverse collection of V. cholerae isolates. Three VSP-II variants were reported previously and our results demonstrate the presence of three novel VSP-II in clinical and environmental V. cholerae marked by major deletions and genetic rearrangements. A new VSP-II cluster was found in the seventh pandemic V. cholerae O1 El Tor strain CIRS101, which is dominant (95%) among the recent (2004–2007) seven pandemic V. cholerae O1 El Tor isolates from two endemic sites, but was not found in older strains from the same region. Two other variants were found in V. cholerae TMA21 and RC385, two environmental strains from coastal Brazil and the Chesapeake Bay, respectively, the latter being prevalent among environmental V. cholerae non-O1/non-O139 and Vibrio mimicus. The results of this study indicate that the VSP-II island has undergone significant rearrangement through a complex evolutionary pathway in V. cholerae. Interestingly, one of the new VSP-II revealed the presence of ‘old’ and ‘new’V. cholerae O1 El Tor pandemic clones circulating in some of the areas where cholera is endemic.
Keywords: Vibrio cholerae; Vibrio mimicus; VPS‐II

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

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

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.

Exploring distributions: design and evaluation - Sopan,A.; Freire,M.; Taieb-Maimon,M.; Golbeck,J.; Shneiderman, Ben (University of Maryland, Human-Computer Interaction Lab Tech Report HCIL-2010-01, 2010)
Visual overviews of tables of numerical and categorical data have been proposed for tables with a single value per cell.In this paper we address the problem of exploring tables including columns consisting of distributions, e.g. the distributions of movie ratings or trust ratings in recommender systems, age distributions in demographic data, usage distributions in logs of telephone calls etc. We propose a novel way of displaying and interacting with distribution data, and present the results of a usability study that demonstrates the benefits of the interface in providing an overview of the data and facilitating the discovery of interesting clusters, patterns, outliers and relationships between columns.

Fast matrix-vector product based fgmres for kernel machines - Srinivasan,B.V.; Duraiswami, Ramani; Gumerov, Nail A. (Copper Mountain Conference on Iterative Methods, 2010)
Kernel based approaches for machine learning have gained huge interest in the past decades because of their robustness. In somealgorithms, the primary problem is the solution of a linear system involving the kernel matrix. Iterative Krylov approaches are often used to solve these efficiently [2, 3]. Fast matrix-vector products can be used to accelerate each Krylov iteration to further optimize the performance. In order to reduce the number of iterations of the Krylov approach, a preconditioner becomes necessary in many cases. Several researchers have proposed flexible preconditioning methods where the preconditioner changes with each iteration, and this class of preconditioners are shown to have good performance [6, 12]. In this paper, we use a Tikhonov regularized kernel matrix as a preconditioner for flexible GMRES [12] to solve kernel matrix based systems of equations. We use a truncated conjugate gradient (CG) method to solve the preconditioner system and further accelerate each CG iteration using fast matrix-vector products. The convergence of the proposed preconditioned GMRES is shown on synthetic data. The performance is further validated on problems in Gaussian process regression and radial basis function interpolation. Improvements are seen in each case.

Fast radial basis function interpolation via preconditioned Krylov iteration - Gumerov, Nail A.; Duraiswami, Ramani (SIAM Journal on Scientific Computing, 2010)
We consider a preconditioned Krylov subspace iterative algorithm presented by Faul,Goodsell, and Powell (IMA J. Numer. Anal. 25 (2005), pp. 1–24) for computing the coefficients of a radial basis function interpolant over N data points. This preconditioned Krylov iteration has been demonstrated to be extremely robust to the distribution of the points and the iteration rapidly convergent. However, the iterative method has several steps whose computational and memory costs scale as O(N2), both in preliminary computations that compute the preconditioner and in the matrix-vector product involved in each step of the iteration. We effectively accelerate the iterative method to achieve an overall cost of O(N log N). The matrix vector product is accelerated via the use of the fast multipole method. The preconditioner requires the computation of a set of closest points to each point. We develop an O(N log N) algorithm for this step as well. Results are presented for multiquadric interpolation in R2 and biharmonic interpolation in R3. A novel FMM algorithm for the evaluation of sums involving multiquadric functions in R2 is presented as well.

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.

From program verification to program synthesis - Srivastava,S.; Gulwani,S.; Foster, Jeffrey S. (ACM SIGPLAN Notices, 2010)

GasSense: Appliance-Level, Single-Point Sensing of Gas Activity in the Home - Cohn,Gabe; Gupta,Sidhant; Jon Froehlich; Larson,Eric; Patel,Shwetak (Pervasive Computing, 2010)
This paper presents GasSense, a low-cost, single-point sensing solution for automatically identifying gas use down to its source (e.g., water heater, furnace, fireplace). This work adds a complementary sensing solution to the growing body of work in infrastructure-mediated sensing. GasSense analyzes the acoustic response of a home’s government mandated gas regulator, which provides the unique capability of sensing both the individual appliance at which gas is currently being consumed as well as an estimate of the amount of gas flow. Our approach provides a number of appealing features including the ability to be easily and safely installed without the need of a professional. We deployed our solution in nine different homes and initial results show that GasSense has an average accuracy of 95.2% in identifying individual appliance usage.

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.

Gradient descent approach for secure localization in resource constrained wireless sensor networks - Garg,R.; Varna,A.L.; M. Wu (Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, 2010)
Many sensor network related applications require precise knowledge of the location of constituent nodes. In these applications, it is desirable for the wireless nodes to be able to autonomously determine their locations before they start sensing and transmitting data. Most localization algorithms rely on anchor nodes whose locations are known to determine the positions of the remaining nodes. In an adversarial scenario, some of these anchor nodes could be compromised and used to transmit misleading information aimed at preventing the accurate localization of the remaining sensors. In this paper, a computationally efficient algorithm to determine the location of sensors that can resist such attacks is described. The proposed algorithm combines gradient descent with a selective pruning of inconsistent measurements to achieve good localization accuracy. Simulation results show that the proposed algorithm has performance comparable to existing schemes while requiring less computational resources.
Keywords: algorithms; resource; approach; localization; computational; constrained; descent; localization; gradient; methods; wireless; networks; networks; secure; resources; gradient; sensor; wireless

Graph Identification - Getoor, Lise (Advances in Intelligent Data Analysis IX: 9th International Symposium, 2010)
There is a growing amount of observational data describing networks– examples include social networks, communication networks, and biological networks. As the amount of available data increases, so has our interest in analyzing these networks in order to uncover (1) general laws that govern their structure and evolution, and (2) patterns and predictive models to develop better policies and practices. However, a fundamental challenge in dealing with this newly available observational data describing networks is that the data is often of dubious quality–it is noisy and incomplete–and before any analysis method can be applied, the data must be cleaned, missing information inferred and mistakes corrected. Skipping this cleaning step can lead to flawed conclusions for things as simple as degree distribution and centrality measures; for more complex analytic queries, the results are even more likely to be inaccurate and misleading.

A group signature scheme from lattice assumptions - Gordon,S.; Katz, Jonathan; Vaikuntanathan,V. (Advances in Cryptology-ASIACRYPT 2010, 2010)
Group signature schemes allow users to sign messages on behalf of a group while (1) maintaining anonymity (within that group) with respect to an outside observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assumption), in the random oracle model. Towards our goal, we construct a new algorithm for sampling a basis for an orthogonal lattice, together with a trapdoor, that may be of independent interest.

Growing a tree in the forest: constructing folksonomies by integrating structured metadata - Plangprasopchok,Anon; Lerman,Kristina; Getoor, Lise (Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, 2010)
Many social Web sites allow users to annotate the content with descriptive metadata, such as tags, and more recently to organize content hierarchically. These types of structured metadata provide valuable evidence for learning how a community organizes knowledge. For instance, we can aggregate many personal hierarchies into a common taxonomy, also known as a folksonomy, that will aid users in visualizing and browsing social content, and also to help them in organizing their own content. However, learning from social metadata presents several challenges, since it is sparse, shallow, ambiguous, noisy, and inconsistent. We describe an approach to folksonomy learning based on relational clustering, which exploits structured metadata contained in personal hierarchies. Our approach clusters similar hierarchies using their structure and tag statistics, then incrementally weaves them into a deeper, bushier tree. We study folksonomy learning using social metadata extracted from the photo-sharing site Flickr, and demonstrate that the proposed approach addresses the challenges. Moreover, comparing to previous work, the approach produces larger, more accurate folksonomies, and in addition, scales better.
Keywords: collective knowledge; data mining; folksonomies; relational clustering; social information processing; social metadata; taxonomies

Higher-order graphical models for classification in social and affiliation networks - Zheleva,E.; Getoor, Lise; Sarawagi,S. (NIPS 2010 Workshop on Networks Across Disciplines: Theory and Applications, Whistler BC, Canada, 2010)
In this work we explore the application of higher-order Markov Random Fields(MRF) to classification in social and affiliation networks. We consider both friend- ship links and group membership for inferring hidden attributes in a collective inference framework. We explore different ways of using the social groups as ei- ther node features or to construct the graphical model structure. The bottleneck in applying higher-order MRFs to a domain with many overlapping large cliques is the complexity of inference which is exponential in the size of the largest clique. To circumvent the slow inference problem, we borrow recent advancements in the computer vision community to achieve fast approximate inference results. We provide preliminary results using a dataset from facebook which suggest that our higher-order MRF models are capturing the structural dependencies in the net- works and they yield higher accuracy than linear classifiers.

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.

Identifying Modifiers in Web Queries Over Structured Data - Paparizos,Stelios; Joshi,Amrula Sadanand; Getoor, Lise; Ntoulas,Alexandros (2010)
Described is using modifiers in online search queries for queries that map to a database table. A modifier (e.g., an adjective or a preposition) specifies the intended meaning of a target, in which the target maps to a column in that table. The modifier thus corresponds to one or more functions that determine which rows of data in the column match the query, e.g., “cameras under $400” maps to a camera (or product) table, and “under” is the modifier that represents a function (less than) that is used to evaluate a “price” target/data column. Also described are different classes of modifiers, and generating the dictionaries for a domain (corresponding to a table) via query log mining.

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