Combining preference and absolute judgements in a crowd-sourced setting - Ye, P; EDU, UMD; David Doermann (ics.uci.edu)
Abstract This paper addresses the problem of obtaining gold-standard labels of objects based on subjective judgements provided by humans. Assuming each object can be associated with an underlying score, the objective of this work is to predict the underlying ...

Comparison of Infant Gut and Skin Microbiota, Resistome and Virulome Between Neonatal Intensive Care Unit (NICU) Environments - Hourigan, Suchitra K.; Subramanian, Poorani; Hasan, Nur A.; Ta, Allison; Klein, Elisabeth; Chettout, Nassim; Huddleston, Kathi; Deopujari, Varsha; Levy, Shira; Baveja, R; Clemency, Nicole C.; Baker, Robin L.; et al. (Frontiers in Microbiology, 2018)

Application of a paper based device containing a new culture medium to detect Vibrio cholerae in water samples collected in Haiti - Briquaire, Romain; Rita R Colwell; Boncy, Jacques; Rossignol, Emmanuel; Dardy, Aline; Pandini, Isabelle; Villeval, François; Machuron, Jean-Louis; Huq, Anwar; Rashed, Shah; Vandevelde, Thierry; Rozand, Christine (Journal of Microbiological Methods, 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)

CRISPR-Cas and Contact-Dependent Secretion Systems Present on Excisable Pathogenicity Islands with Conserved Recombination Modules - Carpenter, Megan R.; Kalburge, Sai S.; Borowski, Joseph D.; Peters, Molly C.; Rita R Colwell; Boyd, E. Fidelma (Journal of Bacteriology, 2017)
Pathogenicity islands (PAIs) are mobile integrated genetic elements that contain a diverse range of virulence factors. PAIs integrate into the host chromosome at a tRNA locus that contains their specific bacterial attachment site, attB, via integrase-mediated site-specific recombination generating attL and attR sites. We identified conserved recombination modules (integrases and att sites) previously described in choleragenic Vibrio cholerae PAIs but with novel cargo genes. Clustered regularly interspaced short palindromic repeat (CRISPR)-associated proteins (Cas proteins) and a type VI secretion system (T6SS) gene cluster were identified at the Vibrio pathogenicity island 1 (VPI-1) insertion site in 19 V. cholerae strains and contained the same recombination module. Two divergent type I-F CRISPR-Cas systems were identified, which differed in Cas protein homology and content. The CRISPR repeat sequence was identical among all V. cholerae strains, but the CRISPR spacer sequences and the number of spacers varied. In silico analysis suggests that the CRISPR-Cas systems were active against phages and plasmids. A type III secretion system (T3SS) was present in 12 V. cholerae strains on a 68-kb island inserted at the same tRNA-serine insertion site as VPI-2 and contained the same recombination module. Bioinformatics analysis showed that two divergent T3SSs exist among the strains examined. Both the CRISPR and T3SS islands excised site specifically from the bacterial chromosome as complete units, and the cognate integrases were essential for this excision. These data demonstrated that identical recombination modules that catalyze integration and excision from the chromosome can acquire diverse cargo genes, signifying a novel method of acquisition for both CRISPR-Cas systems and T3SSs.

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.

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.

Environmental Surveillance for Toxigenic Vibrio cholerae in Surface Waters of Haiti - Hill, Vincent R.; Humphrys, Michael S.; Kahler, Amy M.; Boncy, Jacques; Tarr, Cheryl L.; Huq, Anwar; Chen, Arlene; Katz, Lee S.; Mull, Bonnie J.; Derado, Gordana; Haley, Bradd J.; Freeman, Nicole; et al. (The American Journal of Tropical Medicine and Hygiene, 2015)
Epidemic cholera was reported in Haiti in 2010, with no information available on the occurrence or geographic distribution of toxigenic Vibrio cholerae in Haitian waters. In a series of field visits conducted in Haiti between 2011 and 2013, water and plankton samples were collected at 19 sites. Vibrio cholerae was detected using culture, polymerase chain reaction, and direct viable count methods (DFA-DVC). Cholera toxin genes were detected by polymerase chain reaction in broth enrichments of samples collected in all visits except March 2012. Toxigenic V. cholerae was isolated from river water in 2011 and 2013. Whole genome sequencing revealed that these isolates were a match to the outbreak strain. The DFA-DVC tests were positive for V. cholerae O1 in plankton samples collected from multiple sites. Results of this survey show that toxigenic V. cholerae could be recovered from surface waters in Haiti more than 2 years after the onset of the epidemic.

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)

Can Optimally-Fair Coin Tossing Be Based on One-Way Functions? - Dana Dachman-Soled; Mahmoody, Mohammad; Malkin, Tal (Theory of Cryptography, 2014)
Coin tossing is a basic cryptographic task that allows two distrustful parties to obtain an unbiased random bit in a way that neither party can bias the output by deviating from the protocol or halting the execution. Cleve [STOC’86] showed that in any r round coin tossing protocol one of the parties can bias the output by Ω(1/r) through a “fail-stop” attack; namely, they simply execute the protocol honestly and halt at some chosen point. In addition, relying on an earlier work of Blum [COMPCON’82], Cleve presented an r-round protocol based on one-way functions that was resilient to bias at most O(1/r√)O(1/\sqrt r) . Cleve’s work left open whether ”‘optimally-fair’” coin tossing (i.e. achieving bias O(1/r) in r rounds) is possible. Recently Moran, Naor, and Segev [TCC’09] showed how to construct optimally-fair coin tossing based on oblivious transfer, however, it was left open to find the minimal assumptions necessary for optimally-fair coin tossing. The work of Dachman-Soled et al. [TCC’11] took a step toward answering this question by showing that any black-box construction of optimally-fair coin tossing based on a one-way functions with n-bit input and output needs Ω(n/logn) rounds. In this work we take another step towards understanding the complexity of optimally-fair coin-tossing by showing that this task (with an arbitrary number of rounds) cannot be based on one-way functions in a black-box way, as long as the protocol is ”‘oblivious’” to the implementation of the one-way function. Namely, we consider a natural class of black-box constructions based on one-way functions, called function oblivious, in which the output of the protocol does not depend on the specific implementation of the one-way function and only depends on the randomness of the parties. Other than being a natural notion on its own, the known coin tossing protocols of Blum and Cleve (both based on one-way functions) are indeed function oblivious. Thus, we believe our lower bound for function-oblivious constructions is a meaningful step towards resolving the fundamental open question of the complexity of optimally-fair coin tossing.
Keywords: Algorithm Analysis and Problem Complexity; black-box separations; Coin-Tossing; Computation by Abstract Devices; Data Encryption; Discrete Mathematics in Computer Science; One-Way Functions; Systems and Data Security

Microbial Community Profiling of Human Saliva Using Shotgun Metagenomic Sequencing - Hasan, Nur A.; Young, Brian A.; Minard-Smith, Angela T.; Saeed, Kelly; Li, Huai; Heizer, Esley M.; McMillan, Nancy J.; Isom, Richard; Abdullah, Abdul Shakur; Bornman, Daniel M.; Faith, Seth A.; Choi, Seon Young; et al. (PLoS ONE, 2014)
Human saliva is clinically informative of both oral and general health. Since next generation shotgun sequencing (NGS) is now widely used to identify and quantify bacteria, we investigated the bacterial flora of saliva microbiomes of two healthy volunteers and five datasets from the Human Microbiome Project, along with a control dataset containing short NGS reads from bacterial species representative of the bacterial flora of human saliva. GENIUS, a system designed to identify and quantify bacterial species using unassembled short NGS reads was used to identify the bacterial species comprising the microbiomes of the saliva samples and datasets. Results, achieved within minutes and at greater than 90% accuracy, showed more than 175 bacterial species comprised the bacterial flora of human saliva, including bacteria known to be commensal human flora but also Haemophilus influenzae, Neisseria meningitidis, Streptococcus pneumoniae, and Gamma proteobacteria. Basic Local Alignment Search Tool (BLASTn) analysis in parallel, reported ca. five times more species than those actually comprising the in silico sample. Both GENIUS and BLAST analyses of saliva samples identified major genera comprising the bacterial flora of saliva, but GENIUS provided a more precise description of species composition, identifying to strain in most cases and delivered results at least 10,000 times faster. Therefore, GENIUS offers a facile and accurate system for identification and quantification of bacterial species and/or strains in metagenomic samples.

On Minimal Assumptions for Sender-Deniable Public Key Encryption - Dana Dachman-Soled (Public-Key Cryptography – PKC 2014, 2014)
The primitive of deniable encryption was introduced by Canetti et al. (CRYPTO, 1997). Deniable encryption is an encryption scheme with the added feature that after transmitting a message m, both sender and receiver may produce random coins showing that the transmitted ciphertext was an encryption of any message m′ in the message space. Deniable encryption is a key tool for constructing incoercible protocols, since it allows a party to send one message and later provide apparent evidence to a coercer that a different message was sent. In addition, deniable encryption may be used to obtain adaptively-secure multiparty computation (MPC) protocols and is secure under selective-opening attacks. Different flavors such as sender-deniable and receiver-deniable encryption, where only the sender or receiver produce fake random coins, have been considered. Recently, over 15 years after the primitive was first introduced, Sahai and Waters (IACR Cryptology ePrint Archive, 2013), gave the first construction of sender-deniable encryption schemes with super-polynomial security, where an adversary has negligible advantage in distinguishing real and fake openings. Their construction is based on the construction of an indistinguishability obfuscator for general programs recently introduced in a breakthrough result of Garg et al. (FOCS, 2013). Although feasibility has now been demonstrated, the question of determining the minimal assumptions necessary for sender-deniable encryption with super-polynomial security remains open. The primitive of simulatable public key encryption (PKE), introduced by Damgård and Nielsen (CRYPTO, 2000), is a public key encryption scheme with additional properties that allow oblivious sampling of public keys and ciphertexts. It is one of the low-level primitives used to construct adaptively-secure MPC protocols and was used by O’Neill et al. in their construction of bi-deniable encryption in the multi-distributional model (CRYPTO, 2011). Moreover, the original construction of sender-deniable encryption with polynomial security given by Canetti et al. can be instantiated with simulatable PKE. Thus, a natural question to ask is whether it is possible to construct sender-deniable encryption with super-polynomial security from simulatable PKE. In this work, we investigate the possibility of constructing sender-deniable public key encryption from simulatable PKE in a black-box manner. We show that there is no black-box construction of sender-deniable public key encryption with super-polynomial security from simulatable PKE. This indicates that improving on the original construction of Canetti et al. requires the use of non-black-box techniques, stronger assumptions, or interaction, thus giving some evidence that strong assumptions such as those used by Sahai and Waters are necessary.
Keywords: Algorithm Analysis and Problem Complexity; black-box separation; Coding and Information Theory; Data Encryption; sender-deniable encryption; simulatable PKE; Systems and Data Security

Occurrence in Mexico, 1998–2008, of Vibrio cholerae CTX + El Tor carrying an additional truncated CTX prophage - Alam, Munirul; Rashed, Shah M; Mannan, Shahnewaj Bin; Islam, Tarequl; Lizarraga-Partida, Marcial L.; Delgado, Gabriela; Morales-Espinosa, Rosario; Mendez, Jose Luis; Navarro, Armando; Watanabe, Haruo; Ohnishi, Makoto; Hasan, Nur A.; et al. (Proceedings of the National Academy of Sciences, 2014)

Adaptive and Concurrent Secure Computation from New Adaptive, Non-malleable Commitments - Dana Dachman-Soled; Malkin, Tal; Raykova, Mariana; Venkitasubramaniam, Muthuramakrishnan (Advances in Cryptology - ASIACRYPT 2013, 2013)
We present a unified approach for obtaining general secure computation that achieves adaptive-Universally Composable (UC)-security. Using our approach we essentially obtain all previous results on adaptive concurrent secure computation, both in relaxed models (e.g., quasi-polynomial time simulation), as well as trusted setup models (e.g., the CRS model, the imperfect CRS model). This provides conceptual simplicity and insight into what is required for adaptive and concurrent security, as well as yielding improvements to set-up assumptions and/or computational assumptions in known models. Additionally, we provide the first constructions of concurrent secure computation protocols that are adaptively secure in the timing model, and the non-uniform simulation model. As a corollary we also obtain the first adaptively secure multiparty computation protocol in the plain model that is secure under bounded-concurrency. Conceptually, our approach can be viewed as an adaptive analogue to the recent work of Lin, Pass and Venkitasubramaniam [STOC ‘09], who considered only non-adaptive adversaries. Their main insight was that the non-malleability requirement could be decoupled from the simulation requirement to achieve UC-security. A main conceptual contribution of this work is, quite surprisingly, that it is still the case even when considering adaptive security. A key element in our construction is a commitment scheme that satisfies a strong definition of non-malleability. Our new primitive of concurrent equivocal non-malleable commitments, intuitively, guarantees that even when a man-in-the-middle adversary observes concurrent equivocal commitments and decommitments, the binding property of the commitments continues to hold for commitments made by the adversary. This definition is stronger than previous ones, and may be of independent interest. Previous constructions that satisfy our definition have been constructed in setup models, but either require existence of stronger encryption schemes such as CCA-secure encryption or require independent “trapdoors” provided by the setup for every pair of parties to ensure non-malleability. A main technical contribution of this work is to provide a construction that eliminates these requirements and requires only a single trapdoor.
Keywords: Algorithm Analysis and Problem Complexity; Applications of Mathematics; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; Systems and Data Security

Age-Related Differences in Performance with Touchscreens Compared to Traditional Mouse Input - Findlater,L.; Jon Froehlich; Fattal, K.; Wobbrock,J.O.; Dastyar, T. (CHI 2013 To Appear, 2013)
Despite the apparent popularity of touch screen for older adults, little is known about the psychomotor performance of these devices. We compare performance between older adults and younger adults in four desktop and touchscreen tasks: pointing, dragging, crossing and steering. On the touchscreen, we also examine pinch zoom. Our results show that while older adults were significantly slower than younger adults in general, the touchscreen reduced the performance gap relative to the desktop and mouse. Indeed, the touchscreen resulted in a significant movement time reduction of 35% over the mouse for older adults, compared to only 16% for younger adults. Error rates also decreased.

Clutter noise removal in binary document images - Agrawal, Mudit; David Doermann (International Journal on Document Analysis and Recognition (IJDAR), 2013)
Abstract The paper presents a clutter detection and removal algorithm for complex document images. This distance transform based technique aims to remove irregular and independent unwanted clutter while preserving the text content. The novelty of this approach is in its ...

Current Topics in Microbiology and Immunology One Health: The Human-Animal-Environment Interfaces in Emerging Infectious Diseases The Human Environment Interface: Applying Ecosystem Concepts to Health - Preston, Nicholas D.; Daszak, Peter; Rita R Colwell (Springer Berlin Heidelberg, 2013)

A Dataset for Quality Assessment of Camera Captured Document Images - Kumar, J; Ye, P; David Doermann (2013)
Abstract—With the proliferation of cameras on mobile devices there is an increased desire to image document pages as an alternative to scanning. However, the quality of captured document images is often lower than its scanned equivalent due to hardware limitations ...

Document Image Quality Assessment: A Brief Survey - Ye,Peng; David Doermann (International Conference on Document Analysis and Recognition (ICDAR), 2013)

Engaging Actively with Issues in the Responsible Conduct of Science: Lessons from International Efforts Are Relevant for Undergraduate Education in the United States - Clements, John D.; Connell, Nancy D.; Dirks, Clarissa; El-Faham, Mohamed; Hay, Alastair; Heitman, Elizabeth; Stith, James H.; Bond, Enriqueta C.; Rita R Colwell; Anestidou, Lida; Husbands, Jo L.; Labov, Jay B. (CBE—Life Sciences Education, 2013)
Numerous studies are demonstrating that engaging undergraduate students in original research can improve their achievement in the science, technology, engineering, and mathematics (STEM) fields and increase the likelihood that some of them will decide to pursue careers in these disciplines. Associated with this increased prominence of research in the undergraduate curriculum are greater expectations from funders, colleges, and universities that faculty mentors will help those students, along with their graduate students and postdoctoral fellows, develop an understanding and sense of personal and collective obligation for responsible conduct of science (RCS). This Feature describes an ongoing National Research Council (NRC) project and a recent report about educating faculty members in culturally diverse settings (Middle East/North Africa and Asia) to employ active-learning strategies to engage their students and colleagues deeply in issues related to RCS. The NRC report describes the first phase of this project, which took place in Aqaba and Amman, Jordan, in September 2012 and April 2013, respectively. Here we highlight the findings from that report and our subsequent experience with a similar interactive institute in Kuala Lumpur, Malaysia. Our work provides insights and perspectives for faculty members in the United States as they engage undergraduate and graduate students, as well as postdoctoral fellows, to help them better understand the intricacies of and connections among various components of RCS. Further, our experiences can provide insights for those who may wish to establish “train-the-trainer” programs at their home institutions.

Large-Scale Signature Matching Using Multi-stage Hashing - Du, Xianzhi; Abdalmageed, W; David Doermann (Document Analysis and Recognition (ICDAR), 2013 12th International Conference on, 2013)
In this paper, we propose a fast large-scale signature matching method based on locality sensitive hashing (LSH). Shape Context features are used to describe the structure of signatures. Two stages of hashing are performed to find the nearest neighbours for query signatures. In the first stage, we use M randomly generated hyper planes to separate shape context feature points into different bins, and compute a term-frequency histogram to represent the feature point distribution as a feature vector. In the second stage we again use LSH to categorize the high-level features into different classes. The experiments are carried out on two datasets - DS-I, a small dataset contains 189 signatures, and DS-II, a large dataset created by our group which contains 26,000 signatures. We show that our algorithm can achieve a high accuracy even when few signatures are collected from one same person and perform fast matching when dealing with a large dataset. View full abstract

Real-time No-Reference Image Quality Assessment based on Filter Learning - Ye,Peng; Kumar,Jayant; Kang,Le; David Doermann (International Conference on Computer Vision and Pattern Recognition (CVPR), 2013)

Scene Text Detection via Integrated Discrimination of Component Appearance and Consensus - Ye, Q; David Doermann (2013)
Abstract—In this paper, we propose an approach to scene text detection that leverages both the appearance and consensus of connected components. Component appearance is modeled with an SVM based dictionary classifier and the component consensus is ...

Segmenting time-lapse phase contrast images of adjacent NIH 3T3 cells. - Chalfoun, J; Kociolek, M; Dima, A; Halter, M; Cardone, Antonio; Peskin, A; Bajcsy, P; Brady, M. (Journal of microscopy, 2013)
We present a new method for segmenting phase contrast images of NIH 3T3 fibroblast cells that is accurate even when cells are physically in contact with each other. The problem of segmentation, when cells are in contact, poses a challenge to the accurate automation of cell counting, tracking and lineage modelling in cell biology. The segmentation method presented in this paper consists of (1) background reconstruction to obtain noise-free foreground pixels and (2) incorporation of biological insight about dividing and nondividing cells into the segmentation process to achieve reliable separation of foreground pixels defined as pixels associated with individual cells. The segmentation results for a time-lapse image stack were compared against 238 manually segmented images (8219 cells) provided by experts, which we consider as reference data. We chose two metrics to measure the accuracy of segmentation: the 'Adjusted Rand Index' which compares similarities at a pixel level between masks resulting from manual and automated segmentation, and the 'Number of Cells per Field' (NCF) which compares the number of cells identified in the field by manual versus automated analysis. Our results show that the automated segmentation compared to manual segmentation has an average adjusted rand index of 0.96 (1 being a perfect match), with a standard deviation of 0.03, and an average difference of the two numbers of cells per field equal to 5.39% with a standard deviation of 4.6%.
Keywords: Animals; Cell Adhesion; Cell Count; Cell Division; Cell Shape; Computational Biology; Fibroblasts; Image Processing, Computer-Assisted; Mice; Microscopy, Phase-Contrast; NIH 3T3 Cells; Reproducibility of results; Sensitivity and Specificity; Time-Lapse Imaging

Structural similarity for document image classification and retrieval - Kumar, Jayant; Ye, Peng; David Doermann (Pattern Recognition Letters, 2013)
Abstract This paper presents a novel approach to defining document image structural similarity for the applications of classification and retrieval. We first build a codebook of SURF descriptors extracted from a set of representative training images. We then encode ...

A study of unpredictability in fault-tolerant middleware - Tudor Dumitras; Narasimhan, Priya (Computer Networks, 2013)
In enterprise applications relying on fault-tolerant middleware, it is a common engineering practice to establish service-level agreements (SLAs) based on the 95th or the 99th percentiles of the latency, to allow a margin for unexpected variability. However, the extent of this unpredictability has not been studied systematically. We present an extensive empirical study of unpredictability in 16 distributed systems, ranging from simple transport protocols to fault-tolerant, middleware-based enterprise applications, and we show that the inherent unpredictability in the systems examined arises from at most 1% of the remote invocations. In the normal, fault-free operating mode most remote invocations have a predictable end-to-end latency, but the maximum latency follows unpredictable trends and is comparable with the time needed to recover from a fault. The maximum latency is not influenced by the system’s workload, cannot be regulated through configuration parameters and is not correlated with the system’s resource consumption. The high-latency outliers (up to three orders of magnitude higher than the average latency) have multiple causes and may originate in any component of the system. However, after filtering out 1% of the invocations with the highest recorded response-times, the latency becomes bounded with high statistical confidence (p < 0.01). We have verified this result on different operating systems (Linux 2.4, Linux 2.6, Linux-rt, TimeSys), middleware platforms (CORBA and EJB), programming languages (C, C++ and Java), replication styles (active and warm passive) and applications (e-commerce and online gaming). Moreover, this phenomenon occurs at all the layers of middleware-based systems, from the communication protocols to the business logic.
Keywords: Fault tolerance; latency; Middleware; Remote procedure call; Unpredictability

Unsupervised Classification of Structurally Similar Document Images - Kumar,Jayant; David Doermann (International Conference on Document Analysis and Recognition, 2013)

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

Ask WINE: Are We Safer Today? Evaluating Operating System Security Through Big Data Analysis - Tudor Dumitras; Efstathopoulos, Petros (LEET'12 Proceedings of the 5th USENIX conference on Large-Scale Exploits and Emergent Threats, 2012)
The Internet can be a dangerous place: 800,000 new malware variants are detected each day, and this number is growing at an exponential rate--driven by the quest for economic gains. However, over the past ten years operating-system vendors have introduced a number of security technologies that aim to make exploits harder and to reduce the attack surface of the platform. Faced with these two conflicting trends, it is difficult for end-users to determine what techniques make them safer from Internet attacks. In this position paper, we argue that to answer this question conclusively we must analyze field data collected on real hosts that are targeted by attacks--e.g., the approximately 50 million records of anti-virus telemetry available through Symantec's WINE platform. Such studies can characterize the factors that drive the production of malware, can help us understand the impact of security technologies in the real world and can suggest new security metrics, derived from field observations rather than small lab experiments, indicating how susceptible to attacks a computing platform may be.

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.

BEAGLE: An Application Programming Interface and High-Performance Computing Library for Statistical Phylogenetics - Ayres,Daniel L; Darling,Aaron; Zwickl,Derrick J; Beerli,Peter; Holder,Mark T; Lewis,Paul O; Huelsenbeck,John P; Ronquist,Fredrik; Swofford,David L; Cummings, Michael P.; Rambaut,Andrew; Suchard,Marc A (Systematic BiologySyst Biol, 2012)
Phylogenetic inference is fundamental to our understanding of most aspects of the origin and evolution of life, and in recent years, there has been a concentration of interest in statistical approaches such as Bayesian inference and maximum likelihood estimation. Yet, for large data sets and realistic or interesting models of evolution, these approaches remain computationally demanding. High-throughput sequencing can yield data for thousands of taxa, but scaling to such problems using serial computing often necessitates the use of nonstatistical or approximate approaches. The recent emergence of graphics processing units (GPUs) provides an opportunity to leverage their excellent floating-point computational performance to accelerate statistical phylogenetic inference. A specialized library for phylogenetic calculation would allow existing software packages to make more effective use of available computer hardware, including GPUs. Adoption of a common library would also make it easier for other emerging computing architectures, such as field programmable gate arrays, to be used in the future. We present BEAGLE, an application programming interface (API) and library for high-performance statistical phylogenetic inference. The API provides a uniform interface for performing phylogenetic likelihood calculations on a variety of compute hardware platforms. The library includes a set of efficient implementations and can currently exploit hardware including GPUs using NVIDIA CUDA, central processing units (CPUs) with Streaming SIMD Extensions and related processor supplementary instruction sets, and multicore CPUs via OpenMP. To demonstrate the advantages of a common API, we have incorporated the library into several popular phylogenetic software packages. The BEAGLE library is free open source software licensed under the Lesser GPL and available from http://beagle-lib.googlecode.com. An example client program is available as public domain software.
Keywords: Bayesian phylogenetics; gpu; maximum likelihood; parallel computing

Before We Knew It: An Empirical Study of Zero-day Attacks in the Real World - Bilge, Leyla; Tudor Dumitras (CCS '12 Proceedings of the 2012 ACM conference on Computer and Communications Security, 2012)
Little is known about the duration and prevalence of zero-day attacks, which exploit vulnerabilities that have not been disclosed publicly. Knowledge of new vulnerabilities gives cyber criminals a free pass to attack any target of their choosing, while remaining undetected. Unfortunately, these serious threats are difficult to analyze, because, in general, data is not available until after an attack is discovered. Moreover, zero-day attacks are rare events that are unlikely to be observed in honeypots or in lab experiments. In this paper, we describe a method for automatically identifying zero-day attacks from field-gathered data that records when benign and malicious binaries are downloaded on 11 million real hosts around the world. Searching this data set for malicious files that exploit known vulnerabilities indicates which files appeared on the Internet before the corresponding vulnerabilities were disclosed. We identify 18 vulnerabilities exploited before disclosure, of which 11 were not previously known to have been employed in zero-day attacks. We also find that a typical zero-day attack lasts 312 days on average and that, after vulnerabilities are disclosed publicly, the volume of attacks exploiting them increases by up to 5 orders of magnitude.
Keywords: full disclosure; vulnerabilities; zero-day attacks

On the Centrality of Off-Line E-Cash to Concrete Partial Information Games - Choi, Seung Geol; Dana Dachman-Soled; Yung, Moti (Security and Cryptography for Networks, 2012)
Cryptography has developed numerous protocols for solving “partial information games” that are seemingly paradoxical. Some protocols are generic (e.g., secure multi-party computation) and others, due to the importance of the scenario they represent, are designed to solve a concrete problem directly. Designing efficient and secure protocols for (off-line) e-cash, e-voting, and e-auction are some of the most heavily researched concrete problems, representing various settings where privacy and correctness of the procedure is highly important. In this work, we initiate the exploration of the relationships among e-cash, e-voting and e-auction in the universal composability (UC) framework, by considering general variants of the three problems. In particular, we first define ideal functionalities for e-cash, e-voting, and e-auction, and then give a construction of a protocol that UC-realizes the e-voting (resp., e-auction) functionality in the e-cash hybrid model. This (black-box) reducibility demonstrates the centrality of off-line e-cash and implies that designing a solution to e-cash may bear fruits in other areas. Constructing a solution to one protocol problem based on a second protocol problem has been traditional in cryptography, but typically has concentrated on building complex protocols on simple primitives (e.g., secure multi-party computation from Oblivious Transfer, signature from one-way functions, etc.). The novelty here is reducibility among mature protocols and using the ideal functionality as a design tool in realizing other ideal functionalities. We suggest this new approach, and we only consider the very basic general properties from the various primitives to demonstrate its viability. Namely, we only consider the basic coin e-cash model, the e-voting that is correct and private and relies on trusted registration, and e-auction relying on a trusted auctioneer. Naturally, relationships among protocols with further properties (i.e., extended functionalities), using the approach advocated herein, are left as open questions.
Keywords: Computer Appl. in Administrative Data Processing; Computer Communication Networks; Data Encryption; Management of Computing and Information Systems; Systems and Data Security

Class consistent k-means: Application to face and action recognition - Zhuolin Jiang; Zhe Lin; Davis, Larry S. (Computer Vision and Image Understanding, 2012)
A class-consistent k-means clustering algorithm (CCKM) and its hierarchical extension (Hierarchical CCKM) are presented for generating discriminative visual words for recognition problems. In addition to using the labels of training data themselves, we associate a class label with each cluster center to enforce discriminability in the resulting visual words. Our algorithms encourage data points from the same class to be assigned to the same visual word, and those from different classes to be assigned to different visual words. More specifically, we introduce a class consistency term in the clustering process which penalizes assignment of data points from different classes to the same cluster. The optimization process is efficient and bounded by the complexity of k-means clustering. A very efficient and discriminative tree classifier can be learned for various recognition tasks via the Hierarchical CCKM. The effectiveness of the proposed algorithms is validated on two public face datasets and four benchmark action datasets.
Keywords: Action recognition; Class consistent k-means; Discriminative tree classifier; face recognition; Supervised clustering

Computational Analysis of Terrorist Groups: Lashkar-e-Taiba - V.S. Subrahmanian; Mannes, Aaron; Sliva,Amy; Shakarian, Jana; Dickerson, John P. (Springer Publishing Company, Incorporated, 2012)
Computational Analysis of Terrorist Groups: Lashkar-e-Taiba provides an in-depth look at Web intelligence, and how advanced mathematics and modern computing technology can influence the insights we have on terrorist groups. This book primarily focuses on one famous terrorist group known as Lashkar-e-Taiba (or LeT), and how it operates. After 10 years of counter Al Qaeda operations, LeT is considered by many in the counter-terrorism community to be an even greater threat to the US and world peace than Al Qaeda. Computational Analysis of Terrorist Groups: Lashkar-e-Taiba is the first book that demonstrates how to use modern computational analysis techniques including methods for big data analysis. This book presents how to quantify both the environment in which LeT operate, and the actions it took over a 20-year period, and represent it as a relational database table. This table is then mined using sophisticated data mining algorithms in order to gain detailed, mathematical, computational and statistical insights into LeT and its operations. This book also provides a detailed history of Lashkar-e-Taiba based on extensive analysis conducted by using open source information and public statements. Each chapter includes a case study, as well as a slide describing the key results which are available on the authors web sites. Computational Analysis of Terrorist Groups: Lashkar-e-Taiba is designed for a professional market composed of government or military workers, researchers and computer scientists working in the web intelligence field. Advanced-level students in computer science will also find this valuable as a reference book.

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

Density-Based Multifeature Background Subtraction with Support Vector Machine - Han,Bohyung; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012)
Background modeling and subtraction is a natural technique for object detection in videos captured by a static camera, and also a critical preprocessing step in various high-level computer vision applications. However, there have not been many studies concerning useful features and binary segmentation algorithms for this problem. We propose a pixelwise background modeling and subtraction technique using multiple features, where generative and discriminative techniques are combined for classification. In our algorithm, color, gradient, and Haar-like features are integrated to handle spatio-temporal variations for each pixel. A pixelwise generative background model is obtained for each feature efficiently and effectively by Kernel Density Approximation (KDA). Background subtraction is performed in a discriminative manner using a Support Vector Machine (SVM) over background likelihood vectors for a set of features. The proposed algorithm is robust to shadow, illumination changes, spatial variations of background. We compare the performance of the algorithm with other density-based methods using several different feature combinations and modeling techniques, both quantitatively and qualitatively.
Keywords: algorithm; density-based; application; illumination; approximation; object; background; camera; support; change; kernel; Computer; density; detection; pixelwise; detection; support; extraction; image; feature; background; generative; Haar-like; likelihood; machine; Haar; machines; vectors; modeling; multifeature; segmentation; segmentation; object; subtraction; technique; discriminative; technique; high-level; techniques; spatial; transforms; cameras; computer; variation; spatio-temporal; variation; static; vector; vector; binary; VISION; vision; feature

Dimension-independent multi-resolution morse complexes - De Floriani, Leila; Čomić,L. (Computers & Graphics, 2012)

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 Password Authenticated Key Exchange via Oblivious Transfer - Canetti, Ran; Dana Dachman-Soled; Vaikuntanathan, Vinod; Wee, Hoeteck (Public Key Cryptography – PKC 2012, 2012)
We present a new framework for constructing efficient password authenticated key exchange (PAKE) protocols based on oblivious transfer (OT). Using this framework, we obtain: an efficient and simple UC-secure PAKE protocol that is secure against adaptive corruptions without erasures. efficient and simple PAKE protocols under the Computational Diffie-Hellman (CDH) assumption and the hardness of factoring. (Previous efficient constructions rely on hash proof systems, which appears to be inherently limited to decisional assumptions.) All of our constructions assume a common reference string (CRS) but do not rely on random oracles.
Keywords: adaptive security; Algorithm Analysis and Problem Complexity; Computer Communication Networks; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; oblivious transfer; Password Authenticated Key Exchange; search assumptions; Systems and Data Security; UC security

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

GAGE: A Critical Evaluation of Genome Assemblies and Assembly Algorithms - Salzberg,Steven L.; Phillippy,Adam M; Zimin,Aleksey; Puiu,Daniela; Magoc,Tanja; Koren,Sergey; Treangen,Todd J; Schatz,Michael C; Delcher,Arthur L.; Roberts,Michael; Marçais,Guillaume; Pop, Mihai; et al. (Genome Research, 2012)
New sequencing technology has dramatically altered the landscape of whole-genome sequencing, allowing scientists to initiate numerous projects to decode the genomes of previously unsequenced organisms. The lowest-cost technology can generate deep coverage of most species, including mammals, in just a few days. The sequence data generated by one of these projects consist of millions or billions of short DNA sequences (reads) that range from 50 to 150 nt in length. These sequences must then be assembled de novo before most genome analyses can begin. Unfortunately, genome assembly remains a very difficult problem, made more difficult by shorter reads and unreliable long-range linking information. In this study, we evaluated several of the leading de novo assembly algorithms on four different short-read data sets, all generated by Illumina sequencers. Our results describe the relative performance of the different assemblers as well as other significant differences in assembly difficulty that appear to be inherent in the genomes themselves. Three overarching conclusions are apparent: first, that data quality, rather than the assembler itself, has a dramatic effect on the quality of an assembled genome; second, that the degree of contiguity of an assembly varies enormously among different assemblers and different genomes; and third, that the correctness of an assembly also varies widely and is not well correlated with statistics on contiguity. To enable others to replicate our results, all of our data and methods are freely available, as are all assemblers used in this study.

Gene Prediction with Glimmer for Metagenomic Sequences Augmented by Classification and Clustering - Kelley,David R; Liu,Bo; Delcher,Arthur L.; Pop, Mihai; Salzberg,Steven L. (Nucleic Acids ResearchNucl. Acids Res., 2012)
Environmental shotgun sequencing (or metagenomics) is widely used to survey the communities of microbial organisms that live in many diverse ecosystems, such as the human body. Finding the protein-coding genes within the sequences is an important step for assessing the functional capacity of a metagenome. In this work, we developed a metagenomics gene prediction system Glimmer-MG that achieves significantly greater accuracy than previous systems via novel approaches to a number of important prediction subtasks. First, we introduce the use of phylogenetic classifications of the sequences to model parameterization. We also cluster the sequences, grouping together those that likely originated from the same organism. Analogous to iterative schemes that are useful for whole genomes, we retrain our models within each cluster on the initial gene predictions before making final predictions. Finally, we model both insertion/deletion and substitution sequencing errors using a different approach than previous software, allowing Glimmer-MG to change coding frame or pass through stop codons by predicting an error. In a comparison among multiple gene finding methods, Glimmer-MG makes the most sensitive and precise predictions on simulated and real metagenomes for all read lengths and error rates tested.

Genomic insights to SAR86, an abundant and uncultivated marine bacterial lineage. - Dupont, Chris L; Rusch, Douglas B; Yooseph, Shibu; Lombardo, Mary-Jane; Richter, R Alexander; Valas, Ruben; Novotny, Mark; Yee-Greenbaum, Joyclyn; Jeremy D Selengut; Haft, Dan H; Halpern, Aaron L; Lasken, Roger S; et al. (ISME J, 2012)
Bacteria in the 16S rRNA clade SAR86 are among the most abundant uncultivated constituents of microbial assemblages in the surface ocean for which little genomic information is currently available. Bioinformatic techniques were used to assemble two nearly complete genomes from marine metagenomes and single-cell sequencing provided two more partial genomes. Recruitment of metagenomic data shows that these SAR86 genomes substantially increase our knowledge of non-photosynthetic bacteria in the surface ocean. Phylogenomic analyses establish SAR86 as a basal and divergent lineage of γ-proteobacteria, and the individual genomes display a temperature-dependent distribution. Modestly sized at 1.25-1.7 Mbp, the SAR86 genomes lack several pathways for amino-acid and vitamin synthesis as well as sulfate reduction, trends commonly observed in other abundant marine microbes. SAR86 appears to be an aerobic chemoheterotroph with the potential for proteorhodopsin-based ATP generation, though the apparent lack of a retinal biosynthesis pathway may require it to scavenge exogenously-derived pigments to utilize proteorhodopsin. The genomes contain an expanded capacity for the degradation of lipids and carbohydrates acquired using a wealth of tonB-dependent outer membrane receptors. Like the abundant planktonic marine bacterial clade SAR11, SAR86 exhibits metabolic streamlining, but also a distinct carbon compound specialization, possibly avoiding competition.
Keywords: Computational Biology; Gammaproteobacteria; Genome, Bacterial; Genomic Library; metagenomics; Oceans and Seas; Phylogeny; plankton; Rhodopsin; RNA, Ribosomal, 16S; Seawater

A Hybrid System for Error Detection in Electronic Dictionaries - Zajic, David; David Doermann; Bloodgood,Michael; Rodrigues,Paul; Ye,Peng; Zotkina,Elena (Technical Reports of the Center for the Advanced Study of Language, 2012)
A progress report on CASL’s research on error detection in electronic dictionaries, including a hybrid system, application and evaluation on a second dictionary and a graphical user interface.

Identification of Coli Surface Antigen 23, a Novel Adhesin of Enterotoxigenic Escherichia coli - Del Canto, F.; Botkin, D.J.; Valenzuela, P.; Popov, V.; Ruiz-Perez, F.; Nataro, J.P.; Levine, M.M.; Stine, O.C.; Pop, Mihai; Torres, A.G.; others (Infection and immunity, 2012)
Enterotoxigenic Escherichia coli (ETEC) is an important cause of diarrhea, mainly in developing countries. Although there are 25 different ETEC adhesins described in strains affecting humans, between 15% and 50% of the clinical isolates from different geographical regions are negative for these adhesins, suggesting that additional unidentified adhesion determinants might be present. Here, we report the discovery of Coli Surface Antigen 23 (CS23), a novel adhesin expressed by an ETEC serogroup O4 strain (ETEC 1766a), which was negative for the previously known ETEC adhesins, albeit it has the ability to adhere to Caco-2 cells. CS23 is encoded by an 8.8-kb locus which contains 9 open reading frames (ORFs), 7 of them sharing significant identity with genes required for assembly of K88-related fimbriae. This gene locus, named aal (adhesion-associated locus), is required for the adhesion ability of ETEC 1766a and was able to confer this adhesive phenotype to a nonadherent E. coli HB101 strain. The CS23 major structural subunit, AalE, shares limited identity with known pilin proteins, and it is more closely related to the CS13 pilin protein CshE, carried by human ETEC strains. Our data indicate that CS23 is a new member of the diverse adhesin repertoire used by ETEC strains.

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 Classical Biotype Strains Reveal Distinct Signatures in Mexico - Alam,Munirul; Islam,M. Tarequl; Rashed,Shah Manzur; Johura,Fatema-Tuz; Bhuiyan,Nurul A.; Delgado,Gabriela; Morales,Rosario; Mendez,Jose Luis; Navarro,Armando; Watanabe,Haruo; Hasan,Nur-A.; Rita R Colwell; et al. (Journal of Clinical Microbiology, 2012)
Vibrio cholerae O1 Classical (CL) biotype caused the 5th and 6th, and probably the earlier cholera pandemics, before the El Tor (ET) biotype initiated the 7th pandemic in Asia in the 1970's by completely displacing the CL biotype. Although the CL biotype was thought to be extinct in Asia, and it had never been reported from Latin America, V. cholerae CL and ET biotypes, including hybrid ET were found associated with endemic cholera in Mexico between 1991 and 1997. In this study, CL biotype strains isolated from endemic cholera in Mexico, between 1983 and 1997 were characterized in terms of major phenotypic and genetic traits, and compared with CL biotype strains isolated in Bangladesh between 1962 and 1989. According to sero- and bio-typing data, all V. cholerae strains tested had the major phenotypic and genotypic characteristics specific for the CL biotype. Antibiograms revealed the majority of the Bangladeshi strains to be resistant to trimethoprim/sulfamethoxazole, furazolidone, ampicillin, and gentamycin, while the Mexican strains were sensitive to all of these drugs, as well as to ciprofloxacin, erythromycin, and tetracycline. Pulsed-field gel electrophoresis (PFGE) of NotI-digested genomic DNA revealed characteristic banding patterns for all the CL biotype strains, although the Mexican strains differed with the Bangladeshi strains in 1-2 DNA bands. The difference may be subtle, but consistent, as confirmed by the sub-clustering patterns in the PFGE-based dendrogram, and can serve as regional signature, suggesting pre-1991 existence and evolution of the CL biotype strains in the Americas, independent from that of Asia.

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.

Learning Document Structure for Retrieval and Classification - Kumar,Jayant; Ye,Peng; David Doermann (International Conference on Pattern Recognition (ICPR 2012), 2012)
In this paper, we present a method for the retrieval of document images with chosen layout characteristics. The proposed method is based on statistics of patch codewords over different regions of image. We begin with a set of wanted and a random set of unwanted images representative of a large heterogeneous collection. We then use raw-image patches extracted from the unlabeled images to learn a codebook. To model the spatial relationships between patches, the image is recursively partitioned horizontally and vertically, and a histogram of patch-codewords is computed in each partition. The resulting set of features give a high precision and recall for the retrieval of hand-drawn and machine-print table-documents, and unconstrained mixed form-type documents, when trained using a random forest classifier. We compare our method to the spatial-pyramid method, and show that the proposed approach for learning layout characteristics is competitive for document images.

Learning features for predicting OCR accuracy - Ye,Peng; David Doermann (International Conference on Pattern Recognition (ICPR), 2012)
In this paper, we present a new method for assessing the quality of degraded document images using unsupervised feature learning. The goal is to build a computational model to automatically predict OCR accuracy of a degraded document image without a reference image. Current approaches for this problem typically rely on hand-crafted features whose design is based on heuristic rules that may not be generalizable. In contrast, we explore an unsupervised feature learning framework to learn effective and efficient features for predicting OCR accuracy. Our experimental results, on a set of historic newspaper images, show that the proposed method outperforms a baseline method which combines features from previous works.

Learning Text-line Segmentation using Codebooks and Graph Partitioning - Kang,Le; Kumar,Jayant; Ye,Peng; David Doermann (International Conference on Frontiers in Handwriting Recognition (ICFHR), 2012)
In this paper, we present a codebook based method for handwritten text-line segmentation which uses image patches in the training data to learn a graph-based similarity for clustering. We first construct a codebook of image-patches using K-medoids, and obtain exemplars which encode local evidence. We then obtain the corresponding codewords for all patches extracted from a given image and construct a similarity graph using the learned evidence and partitioned to obtain textlines. Our learning based approach performs well on a field dataset containing degraded and un-constrained handwritten Arabic document images. Results on ICDAR 2009 segmentation contest dataset show that the method is competitive with previous approaches.

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)

Local Segmentation of Touching Characters using Contour based Shape Decomposition - Kang,Le; David Doermann; Cao,Huiagu; Prasad,Rohit; Natarajan,Prem (Document Analysis Systems, 2012)
We propose a contour based shape decomposition approach that provides local segmentation of touching characters. The shape contour is linearized into edgelets and edgelets are merged into boundary fragments. Connection cost between boundary fragments is obtained by considering local smoothness, connection length and a stroke-level property Similar Stroke Rate. Samples of connections among boundary fragments are randomly generated and the one with the minimum global cost is selected to produce optimal segmentation of the shape. To obtain a binary segmentation using this approach, we make an iterative search for the parameters that yields two components on a shape. Experimental results on a number of synthetic shape images and the LTP dataset showed that this contour based shape decomposition technique is promising and it is effective on providing local segmentation of touching characters.

Logo Retrieval in Document Images - Jain,Rajiv; David Doermann (Document Analysis Systems, 2012)
This paper presents a scalable algorithm for segmentation free logo retrieval in document images. The contributions of this paper include the use of the SURF feature for logo retrieval, a novel indexing algorithm for efficient retrieval of SURF features and a method to filter results using the orientation of local features and geometric constraints. Results demonstrate that logo retrieval can be performed with high accurately and efficiently scaled to a large datasets.

Media, Aggregators and the Link Economy: Strategic Hyperlink Formation in Content Networks - Dellarocas, Chris; Katona,Zsolt; Rand, William (Management Science, 2012)
A key property of the World Wide Web is the possibility for firms to place virtually costless links to third-party content as a substitute or complement to their own content. This ability to hyperlink has enabled new types of players, such as search engines and content aggregators, to successfully enter content ecosystems, attracting traffic and revenues by hosting links to the content of others. This, in turn, has sparked a heated controversy between content producers and aggregators regarding the legitimacy and social costs/benefits of uninhibited free linking. This work is the first to model the implications of interrelated and strategic hyper-linking and content investments. Our results provide a nuanced view of the much-touted “link economy,” highlighting both the beneficial consequences and the drawbacks of free hyperlinks for content producers and consumers. We show that content sites can reduce competition and improve profits by forming links to each other; in such networks one site makes high investments in content and other sites link to it. Interestingly, competitive dynamics often preclude the formation of link networks, even in settings where they would improve everyone’s profits. Furthermore, such networks improve economic efficiency only when all members have similar abilities to produce content; otherwise the less capable nodes can free-ride on the content of the more capable nodes, reducing profits for the capable nodes as well as the average content quality available to consumers. Within these networks, aggregators have both positive and negative effects. By making it easier for consumers to access good quality content they increase the appeal of the entire content ecosystem relative to the alternatives. To the extent that this increases the total traffic flowing into the content ecosystem, aggregators can help increase the profits of the highest quality content sites. At the same time, however, the market entry of aggregators takes away some of the revenue that would otherwise go to content sites. Finally, by placing links to only a subset of available content, aggregators further increase competitive pressure on content sites. Interestingly, this can increase the likelihood that such sites will then attempt to alleviate the competitive pressure by forming link networks.

Modality and Negation in SIMT Use of Modality and Negation in Semantically-Informed Syntactic MT - Baker,Kathryn; Bloodgood,Michael; Dorr, Bonnie J; Callison-Burch,Chris; Filardo,Nathaniel W.; Piatko,Christine; Levin,Lori; Miller,Scott (Computational Linguistics, 2012)
This paper describes the resource- and system-building efforts of an eight-week Johns Hopkins University Human Language Technology Center of Excellence Summer Camp for Applied Language Exploration (SCALE-2009) on Semantically-Informed Machine Translation (SIMT). We describe a new modality/negation (MN) annotation scheme, the creation of a (publicly available) MN lexicon, and two automated MN taggers that we built using the annotation scheme and lexicon. Our annotation scheme isolates three components of modality and negation: a trigger (a word that conveys modality or negation), a target (an action associated with modality or negation) and a holder (an experiencer of modality). We describe how our MN lexicon was semi-automatically produced and we demonstrate that a structure-based MN tagger results in precision around 86% (depending on genre) for tagging of a standard LDC data set.

No-Reference Image Quality Assessment using Visual Codebooks - Ye,P.; David Doermann (Image Processing, IEEE Transactions on, 2012)
The goal of no-reference objective image quality assessment (NR-IQA) is to develop a computational model that can predict the human perceived quality of distorted images accurately and automatically without any prior knowledge of reference images. Most existing NR-IQA approaches are distortionspecific (DS) and are typically limited to one or two specific types of distortions. In most practical applications, however, information about the distortion type is not really available. In this paper, we propose a general-purpose NR-IQA approach based on visual codebooks. A visual codebook consisting of Gabor filter based local features extracted from local image patches is used to capture complex statistics of a natural image. The codebook encodes statistics by quantizing the feature space and accumulating histograms of patch appearances. This method does not assume any specific types of distortions, however, when evaluating images with a particular type of distortion, it does require examples with the same or similar distortion for training. Experimental results demonstrate that the predicted quality score using our method is consistent with human perceived image quality. The proposed method is comparable to state-ofthe- art general purpose NR-IQA methods and outperforms the full-reference image quality metrics, peak signal-to-noise ratio (PSNR) and structural similarity index (SSIM) on the LIVE image quality assessment database.

Optimizing epidemic protection for socially essential workers - Barrett,Chris; Beckman,Richard; Bisset,Keith; Chen,Jiangzhuo; DuBois,Thomas; Eubank,Stephen; Kumar,V. S. Anil; Lewis,Bryan; Marathe,Madhav V.; Srinivasan, Aravind; Stretz,Paula E. (Proceedings of the 2nd ACM SIGHIT International Health Informatics Symposium, 2012)
Public-health policy makers have many tools to mitigate an epidemic's effects. Most related research focuses on the direct effects on those infected (in terms of health, life, or productivity). Interventions including treatment, prophylaxis, quarantine, and social distancing are well studied in this context. These interventions do not address indirect effects due to the loss of critical services and infrastructures when too many of those responsible for their day-to-day operations fall ill. We examine, both analytically and through simulation, the protection of such essential subpopulations by sequestering them, effectively isolating them into groups during an epidemic. We develop a framework for studying the benefits of sequestering and heuristics for when to sequester. We also prove a key property of sequestering placement which helps partition the subpopulations optimally. Thus we provide a first step toward determining how to allocate resources between the direct protection of a population, and protection of those responsible for critical services.
Keywords: epidemiology; OPTIMIZATION; public health informatics

The Provenance of WINE - Tudor Dumitras; Efstathopoulos, P. (Dependable Computing Conference (EDCC), 2012 Ninth European, 2012)
The results of cyber security experiments are often impossible to reproduce, owing to the lack of adequate descriptions of the data collection and experimental processes. Such provenance information is difficult to record consistently when collecting data from distributed sensors and when sharing raw data among research groups with variable standards for documenting the steps that produce the final experimental result. In the WINE benchmark, which provides field data for cyber security experiments, we aim to make the experimental process self-documenting. The data collected includes provenance information – such as when, where and how an attack was first observed or detected – and allows researchers to gauge information quality. Experiments are conducted on a common test bed, which provides tools for recording each procedural step. The ability to understand the provenance of research results enables rigorous cyber security experiments, conducted at scale.
Keywords: Benchmark testing; CYBER SECURITY; cyber security experiments; data attacks; data collection; dependability benchmarking; distributed databases; distributed sensors; experimental research; field data; information quality; MALWARE; Pipelines; provenance; provenance information; raw data sharing; research groups; security of data; self-documenting experimental process; sensor fusion; software; variable standards; WINE; WINE benchmark

A Random Forest System Combination Approach for Error Detection in Digital Dictionaries - Bloodgood,Michael; Ye,Peng; Rodrigues,Paul; Zajic, David; David Doermann (Innovative hybrid approaches to the processing of textual data, EACL 2012 Workshop, 2012)
When digitizing a print bilingual dictionary, whether via optical character recognition or manual entry, it is inevitable that errors are introduced into the electronic version that is created. We investigate automating the process of detecting errors in an XML representation of a digitized print dictionary using a hybrid approach that combines rule-based, feature-based, and language model-based methods. We investigate combining methods and show that using random forests is a promising approach. We find that in isolation, unsupervised methods rival the performance of supervised methods. Random forests typically require training data so we investigate how we can apply random forests to combine individual base methods that are themselves unsupervised without requiring large amounts of training data. Experiments reveal empirically that a relatively small amount of data is sufficient and can potentially be further reduced through specific selection criteria.

Recognizing Human Actions by Learning and Matching Shape-Motion Prototype Trees - Zhuolin Jiang; Zhe Lin; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2012)
A shape-motion prototype-based approach is introduced for action recognition. The approach represents an action as a sequence of prototypes for efficient and flexible action matching in long video sequences. During training, an action prototype tree is learned in a joint shape and motion space via hierarchical K-means clustering and each training sequence is represented as a labeled prototype sequence; then a look-up table of prototype-to-prototype distances is generated. During testing, based on a joint probability model of the actor location and action prototype, the actor is tracked while a frame-to-prototype correspondence is established by maximizing the joint probability, which is efficiently performed by searching the learned prototype tree; then actions are recognized using dynamic prototype sequence matching. Distance measures used for sequence matching are rapidly obtained by look-up table indexing, which is an order of magnitude faster than brute-force computation of frame-to-frame distances. Our approach enables robust action matching in challenging situations (such as moving cameras, dynamic backgrounds) and allows automatic alignment of action sequences. Experimental results demonstrate that our approach achieves recognition rates of 92.86 percent on a large gesture data set (with dynamic backgrounds), 100 percent on the Weizmann action data set, 95.77 percent on the KTH action data set, 88 percent on the UCF sports data set, and 87.27 percent on the CMU action data set.
Keywords: action prototype; actor location; brute-force computation; CMU action data set; distance measures; dynamic backgrounds; dynamic prototype sequence matching; flexible action matching; frame-to-frame distances; frame-to-prototype correspondence; hierarchical k-means clustering; human action recognition; Image matching; image recognition; Image sequences; joint probability model; joint shape; KTH action data set; large gesture data set; learning; learning (artificial intelligence); look-up table indexing; motion space; moving cameras; pattern clustering; prototype-to-prototype distances; shape-motion prototype-based approach; table lookup; training sequence; UCF sports data set; Video sequences; video signal processing; Weizmann action data set

Securing Circuits against Constant-Rate Tampering - Dana Dachman-Soled; Kalai, Yael Tauman (Advances in Cryptology – CRYPTO 2012, 2012)
We present a compiler that converts any circuit into one that remains secure even if a constant fraction of its wires are tampered with. Following the seminal work of Ishai et. al. (Eurocrypt 2006), we consider adversaries who may choose an arbitrary set of wires to corrupt, and may set each such wire to 0 or to 1, or may toggle with the wire. We prove that such adversaries, who continuously tamper with the circuit, can learn at most logarithmically many bits of secret information (in addition to black-box access to the circuit). Our results are information theoretic.
Keywords: circuit compiler; Computer Communication Networks; computers and society; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; PCP of proximity; side-channel attacks; Systems and Data Security; tampering

Sharpness Estimation for Document and Scene Images - Kumar,Jayant; Chen, Francine; David Doermann (International Conference on Pattern Recognition (ICPR 2012), 2012)
Images of document pages have different characteristics than images of natural scenes, and so the sharpness measures developed for natural scene images do not necessarily extend to document images primarily composed of text. We present an efficient and simple method for effectively estimating the sharpness/ blurriness of document images that also performs well on natural scenes. Our method can be used to predict the sharpness in scenarios where images are blurred due to camera-motion (or hand-shake), defocus, or inherent properties of the imaging system. The proposed method outperforms the perceptually-based, no-reference sharpness work of [1] and [4], which was shown to perform better than 14 other no-reference sharpness measures on the LIVE dataset.

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.

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)

Submodular Dictionary Learning for Sparse Coding - Zhuolin Jiang; Zhang, G.; Davis, Larry S. (IEEE conference on Computer Vision and Pattern Recognition, 2012)
A greedy-based approach to learn a compact and dis-criminative dictionary for sparse representation is pre- sented. We propose an objective function consisting of two components: entropy rate of a random walk on a graph and a discriminative term. Dictionary learning is achieved by finding a graph topology which maximizes the objec- tive function. By exploiting the monotonicity and submod- ularity properties of the objective function and the matroid constraint, we present a highly efficient greedy-based op- timization algorithm. It is more than an order of magni- tude faster than several recently proposed dictionary learn- ing approaches. Moreover, the greedy algorithm gives a near-optimal solution with a (1/2)-approximation bound. Our approach yields dictionaries having the property that feature points from the same class have very similar sparse codes. Experimental results demonstrate that our approach outperforms several recently proposed dictionary learning techniques for face, action and object category recognition.

A Temporal Pattern Search Algorithm for Personal History Event Visualization - Wang,T. D; Deshpande, Amol; Shneiderman, Ben (Knowledge and Data Engineering, IEEE Transactions on, 2012)
We present Temporal Pattern Search (TPS), a novel algorithm for searching for temporal patterns of events in historical personal histories. The traditional method of searching for such patterns uses an automaton-based approach over a single array of events, sorted by time stamps. Instead, TPS operates on a set of arrays, where each array contains all events of the same type, sorted by time stamps. TPS searches for a particular item in the pattern using a binary search over the appropriate arrays. Although binary search is considerably more expensive per item, it allows TPS to skip many unnecessary events in personal histories. We show that TPS's running time is bounded by O(m2n lg(n)), where m is the length of (number of events) a search pattern, and n is the number of events in a record (history). Although the asymptotic running time of TPS is inferior to that of a nondeterministic finite automaton (NFA) approach (O(mn)), TPS performs better than NFA under our experimental conditions. We also show TPS is very competitive with Shift-And, a bit-parallel approach, with real data. Since the experimental conditions we describe here subsume the conditions under which analysts would typically use TPS (i.e., within an interactive visualization program), we argue that TPS is an appropriate design choice for us.
Keywords: automaton-based approach; binary search; bit-parallel approach; data visualisation; electronic health records; event array; finite automata; interactive visualization program; Lifelines2 visualization tool; medical information systems; NFA approach; nondeterministic finite automaton; O(m2n lg(n)) problem; pattern matching; personal history event visualization; Shift-And approach; temporal pattern search algorithm; time stamp

Towards a cost model for network traffic - Motiwala,Murtaza; Dhamdhere,Amogh; Feamster, Nick; Lakhina,Anukool (SIGCOMM Comput. Commun. Rev., 2012)
We develop a holistic cost model that operators can use to help evaluate the costs of various routing and peering decisions. Using real traffic data from a large carrier network, we show how network operators can use this cost model to significantly reduce the cost of carrying traffic in their networks. We find that adjusting the routing for a small fraction of total flows (and total traffic volume) significantly reduces cost in many cases. We also show how operators can use the cost model both to evaluate potential peering arrangements and for other network operations problems.
Keywords: cost optimization; traffic cost model

Unsupervised Feature Learning Framework for No-reference Image Quality Assessment - Ye,Peng; Kumar,Jayant; Kang,Le; David Doermann (CVPR, 2012)
In this paper, we present an efficient general-purpose objective no-reference (NR) image quality assessment (IQA) framework based on unsupervised feature learning. The goal is to build a computational model to automatically predict human perceived image quality without a reference image and without knowing the distortion present in the image. Previous approaches for this problem typically rely on hand-crafted features which are carefully designed based on prior knowledge. In contrast, we use raw-image-patches extracted from a set of unlabeled images to learn a dictionary in an unsupervised manner. We use soft-assignment coding with max pooling to obtain effective image representations for quality estimation. The proposed algorithm is very computationally appealing, using raw image patches as local descriptors and using soft-assignment for encoding. Furthermore, unlike previous methods, our unsupervised feature learning strategy enables our method to adapt to different domains. CORNIA (Codebook Representation for No-Reference Image Assessment) was tested on LIVE database and shown to perform statistically better than full-reference quality measure structural similarity index (SSIM) and was shown to be comparable to state-of-the-art general purpose NR-IQA algorithms.

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

Accelerated evolution of 3'avian FOXE1 genes, and thyroid and feather specific expression of chicken FoxE1 - Yaklichkin,Sergey Yu; Darnell,Diana K; Pier,Maricela V; Antin,Parker B; Hannenhalli, Sridhar (BMC Evolutionary Biology, 2011)
The forkhead transcription factor gene E1 (FOXE1) plays an important role in regulation of thyroid development, palate formation and hair morphogenesis in mammals. However, avian FOXE1 genes have not been characterized and as such, codon evolution of FOXE1 orthologs in a broader evolutionary context of mammals and birds is not known.

Action recognition using Partial Least Squares and Support Vector Machines - Ramadan,S.; Davis, Larry S. (Image Processing (ICIP), 2011 18th IEEE International Conference on, 2011)
We introduce an action recognition approach based on Partial Least Squares (PLS) and Support Vector Machines (SVM). We extract very high dimensional feature vectors representing spatio-temporal properties of actions and use multiple PLS regressors to find relevant features that distinguish amongst action classes. Finally, we use a multi-class SVM to learn and classify those relevant features. We applied our approach to INRIA's IXMAS dataset. Experimental results show that our method is superior to other methods applied to the IXMAS dataset.
Keywords: analysis; support; approach; multiclass; approximations; regression; dataset; action; dimensional; extraction; feature; extraction; image; feature; high; INRIA; IXMAS; least; machines; machines; very; partial; properties; support; recognition; recognition; least; regressors; spatiotemporal; squares; SVM; multiple; vector; vectors

Ant Colony Optimization in a Changing Environment - Seymour,John Jefferson; Tuzo,Joseph; desJardins, Marie (2011 AAAI Fall Symposium Series, 2011)
Ant colony optimization (ACO) algorithms are computational problem-solving methods that are inspired by the complex behaviors of ant colonies; specifically, the ways in which ants interact with each other and their environment to optimize the overall performance of the ant colony. Our eventual goal is to develop and experiment with ACO methods that can more effectively adapt to dynamically changing environments and problems. We describe biological ant systems and the dynamics of their environments and behaviors. We then introduce a family of dynamic ACO algorithms that can handle dynamic modifications of their inputs. We report empirical results, showing that dynamic ACO algorithms can effectively adapt to time-varying environments.

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

AVSS 2011 demo session: A large-scale benchmark dataset for event recognition in surveillance video - Oh,Sangmin; Hoogs,Anthony; Perera,Amitha; Cuntoor,Naresh; Chen,Chia-Chih; Lee,Jong Taek; Mukherjee,Saurajit; Aggarwal, JK; Lee,Hyungtae; Davis, Larry S.; Swears,Eran; Wang,Xiaoyang; et al. (Advanced Video and Signal-Based Surveillance (AVSS), 2011 8th IEEE International Conference on, 2011)
We introduce to the surveillance community the VIRAT Video Dataset[1], which is a new large-scale surveillance video dataset designed to assess the performance of event recognition algorithms in realistic scenes1.

Bacillus Anthracis Comparative Genome Analysis in Support of the Amerithrax Investigation - Rasko,David A; Worsham,Patricia L; Abshire,Terry G; Stanley,Scott T; Bannan,Jason D; Wilson,Mark R; Langham,Richard J; Decker,R. Scott; Jiang,Lingxia; Read,Timothy D.; Phillippy,Adam M; Salzberg,Steven L.; et al. (Proceedings of the National Academy of SciencesPNAS, 2011)
Before the anthrax letter attacks of 2001, the developing field of microbial forensics relied on microbial genotyping schemes based on a small portion of a genome sequence. Amerithrax, the investigation into the anthrax letter attacks, applied high-resolution whole-genome sequencing and comparative genomics to identify key genetic features of the letters’ Bacillus anthracis Ames strain. During systematic microbiological analysis of the spore material from the letters, we identified a number of morphological variants based on phenotypic characteristics and the ability to sporulate. The genomes of these morphological variants were sequenced and compared with that of the B. anthracis Ames ancestor, the progenitor of all B. anthracis Ames strains. Through comparative genomics, we identified four distinct loci with verifiable genetic mutations. Three of the four mutations could be directly linked to sporulation pathways in B. anthracis and more specifically to the regulation of the phosphorylation state of Spo0F, a key regulatory protein in the initiation of the sporulation cascade, thus linking phenotype to genotype. None of these variant genotypes were identified in single-colony environmental B. anthracis Ames isolates associated with the investigation. These genotypes were identified only in B. anthracis morphotypes isolated from the letters, indicating that the variants were not prevalent in the environment, not even the environments associated with the investigation. This study demonstrates the forensic value of systematic microbiological analysis combined with whole-genome sequencing and comparative genomics.

Birdlets: Subordinate categorization using volumetric primitives and pose-normalized appearance - Farrell,R.; Oza,O.; Zhang,Ning; Morariu,V.I.; Darrell,T.; Davis, Larry S. (Computer Vision (ICCV), 2011 IEEE International Conference on, 2011)
Subordinate-level categorization typically rests on establishing salient distinctions between part-level characteristics of objects, in contrast to basic-level categorization, where the presence or absence of parts is determinative. We develop an approach for subordinate categorization in vision, focusing on an avian domain due to the fine-grained structure of the category taxonomy for this domain. We explore a pose-normalized appearance model based on a volumetric poselet scheme. The variation in shape and appearance properties of these parts across a taxonomy provides the cues needed for subordinate categorization. Training pose detectors requires a relatively large amount of training data per category when done from scratch; using a subordinate-level approach, we exploit a pose classifier trained at the basic-level, and extract part appearance and shape information to build subordinate-level models. Our model associates the underlying image pattern parameters used for detection with corresponding volumetric part location, scale and orientation parameters. These parameters implicitly define a mapping from the image pixels into a pose-normalized appearance space, removing view and pose dependencies, facilitating fine-grained categorization from relatively few training examples.
Keywords: appearance; Birdlets; category; categorization; subordinate-level; detection; pose; detectors; pose-normalized; distinctions; shape; estimation; extraction; pose; extraction; subordinate-level; information; model; salient; models; volumetric; pixels; part; poselet; primitives; computer; resolution; information; retrieval; object; scheme; volumetric; taxonomy; computer; vision; image

On the Black-Box Complexity of Optimally-Fair Coin Tossing - Dana Dachman-Soled; Lindell, Yehuda; Mahmoody, Mohammad; Malkin, Tal (Theory of Cryptography, 2011)
A fair two-party coin tossing protocol is one in which both parties output the same bit that is almost uniformly distributed (i.e., it equals 0 and 1 with probability that is at most negligibly far from one half). It is well known that it is impossible to achieve fair coin tossing even in the presence of fail-stop adversaries (Cleve, FOCS 1986). In fact, Cleve showed that for every coin tossing protocol running for r rounds, an efficient fail-stop adversary can bias the output by Ω(1/r). Since this is the best possible, a protocol that limits the bias of any adversary to O(1/r) is called optimally-fair. The only optimally-fair protocol that is known to exist relies on the existence of oblivious transfer, because it uses general secure computation (Moran, Naor and Segev, TCC 2009). However, it is possible to achieve a bias of O(1/r√)O(1/\sqrt{r}) in r rounds relying only on the assumption that there exist one-way functions. In this paper we show that it is impossible to achieve optimally-fair coin tossing via a black-box construction from one-way functions for r that is less than O(n/logn), where n is the input/output length of the one-way function used. An important corollary of this is that it is impossible to construct an optimally-fair coin tossing protocol via a black-box construction from one-way functions whose round complexity is independent of the security parameter n determining the security of the one-way function being used. Informally speaking, the main ingredient of our proof is to eliminate the random-oracle from “secure” protocols with “low round-complexity” and simulate the protocol securely against semi-honest adversaries in the plain model. We believe our simulation lemma to be of broader interest.
Keywords: Algorithm Analysis and Problem Complexity; black-box separations; Coding and Information Theory; coin tossing; Computer Communication Networks; Data Encryption; lower-bound; Math Applications in Computer Science; optimally-fair coin tossing; round-complexity; Systems and Data Security

Broadband internet performance: A view from the gateway - Sundaresan,S.; de Donato,W.; Feamster, Nick; Teixeira,R.; Crawford,S.; Pescapè,A. (SIGCOMM-Computer Communication Review, 2011)
We present the first study of network access link performance mea-sured directly from home gateway devices. Policymakers, ISPs, and users are increasingly interested in studying the performance of Internet access links. Because of many confounding factors in a home network or on end hosts, however, thoroughly understanding access network performance requires deploying measurement in- frastructure in users’ homes as gateway devices. In conjunction with the Federal Communication Commission’s study of broad- band Internet access in the United States, we study the throughput and latency of network access links using longitudinal measure- ments from nearly 4,000 gateway devices across 8 ISPs from a de- ployment of over 4,200 devices. We study the performance users achieve and how various factors ranging from the user’s choice of modem to the ISP’s traffic shaping policies can affect performance. Our study yields many important findings about the characteristics of existing access networks. Our findings also provide insights into the ways that access network performance should be measured and presented to users, which can help inform ongoing broader efforts to benchmark the performance of access networks.

Can Deliberately Incomplete Gene Sample Augmentation Improve a Phylogeny Estimate for the Advanced Moths and Butterflies (Hexapoda: Lepidoptera)? - Cho,Soowon; Zwick,Andreas; Regier,Jerome C; Mitter,Charles; Cummings, Michael P.; Yao,Jianxiu; Du,Zaile; Zhao,Hong; Kawahara,Akito Y; Weller,Susan; Davis,Donald R; Baixeras,Joaquin; et al. (Systematic BiologySyst Biol, 2011)
This paper addresses the question of whether one can economically improve the robustness of a molecular phylogeny estimate by increasing gene sampling in only a subset of taxa, without having the analysis invalidated by artifacts arising from large blocks of missing data. Our case study stems from an ongoing effort to resolve poorly understood deeper relationships in the large clade Ditrysia ( > 150,000 species) of the insect order Lepidoptera (butterflies and moths). Seeking to remedy the overall weak support for deeper divergences in an initial study based on five nuclear genes (6.6 kb) in 123 exemplars, we nearly tripled the total gene sample (to 26 genes, 18.4 kb) but only in a third (41) of the taxa. The resulting partially augmented data matrix (45% intentionally missing data) consistently increased bootstrap support for groupings previously identified in the five-gene (nearly) complete matrix, while introducing no contradictory groupings of the kind that missing data have been predicted to produce. Our results add to growing evidence that data sets differing substantially in gene and taxon sampling can often be safely and profitably combined. The strongest overall support for nodes above the family level came from including all nucleotide changes, while partitioning sites into sets undergoing mostly nonsynonymous versus mostly synonymous change. In contrast, support for the deepest node for which any persuasive molecular evidence has yet emerged (78–85% bootstrap) was weak or nonexistent unless synonymous change was entirely excluded, a result plausibly attributed to compositional heterogeneity. This node (Gelechioidea + Apoditrysia), tentatively proposed by previous authors on the basis of four morphological synapomorphies, is the first major subset of ditrysian superfamilies to receive strong statistical support in any phylogenetic study. A “more-genes-only” data set (41 taxa×26 genes) also gave strong signal for a second deep grouping (Macrolepidoptera) that was obscured, but not strongly contradicted, in more taxon-rich analyses.
Keywords: Ditrysia; gene sampling; Hexapoda; Lepidoptera; missing data; molecular phylogenetics; nuclear genes; taxon sampling

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 for query by image and text content: searching computer help using screenshots and keywords - Tom Yeh; White,Brandyn; San Pedro,Jose; Katz,Boriz; Davis, Larry S. (Proceedings of the 20th international conference on World wide web, 2011)
The multimedia information retrieval community has dedicated extensive research effort to the problem of content-based image retrieval (CBIR). However, these systems find their main limitation in the difficulty of creating pictorial queries. As a result, few systems offer the option of querying by visual examples, and rely on automatic concept detection and tagging techniques to provide support for searching visual content using textual queries. This paper proposes and studies a practical multimodal web search scenario, where CBIR fits intuitively to improve the retrieval of rich information queries. Many online articles contain useful know-how knowledge about computer applications. These articles tend to be richly illustrated by screenshots. We present a system to search for such software know-how articles that leverages the visual correspondences between screenshots. Users can naturally create pictorial queries simply by taking a screenshot of the application to retrieve a list of articles containing a matching screenshot. We build a prototype comprising 150k articles that are classified into walkthrough, book, gallery, and general categories, and provide a comprehensive evaluation of this system, focusing on technical (accuracy of CBIR techniques) and usability (perceived system usefulness) aspects. We also consider the study of added value features of such a visual-supported search, including the ability to perform cross-lingual queries. We find that the system is able to retrieve matching screenshots for a wide variety of programs, across language boundaries, and provide subjectively more useful results than keyword-based web and image search engines.
Keywords: content-based image retrieval; multimodal search; online help

A case for query by image and text content: searching computer help using screenshots and keywords - Tom Yeh; White,Brandyn; San Pedro,Jose; Katz,Boriz; Davis, Larry S. (Proceedings of the 20th international conference on World wide web, 2011)
The multimedia information retrieval community has dedicated extensive research effort to the problem of content-based image retrieval (CBIR). However, these systems find their main limitation in the difficulty of creating pictorial queries. As a result, few systems offer the option of querying by visual examples, and rely on automatic concept detection and tagging techniques to provide support for searching visual content using textual queries.This paper proposes and studies a practical multimodal web search scenario, where CBIR fits intuitively to improve the retrieval of rich information queries. Many online articles contain useful know-how knowledge about computer applications. These articles tend to be richly illustrated by screenshots. We present a system to search for such software know-how articles that leverages the visual correspondences between screenshots. Users can naturally create pictorial queries simply by taking a screenshot of the application to retrieve a list of articles containing a matching screenshot. We build a prototype comprising 150k articles that are classified into walkthrough, book, gallery, and general categories, and provide a comprehensive evaluation of this system, focusing on technical (accuracy of CBIR techniques) and usability (perceived system usefulness) aspects. We also consider the study of added value features of such a visual-supported search, including the ability to perform cross-lingual queries. We find that the system is able to retrieve matching screenshots for a wide variety of programs, across language boundaries, and provide subjectively more useful results than keyword-based web and image search engines.
Keywords: content-based image retrieval; multimodal search; online help

Cell cycle dependent TN-C promoter activity determined by live cell imaging. - Halter, Michael; Sisan, Daniel R; Chalfoun, Joe; Stottrup, Benjamin L; Cardone, Antonio; Dima,Alden A.; Tona, Alessandro; Plant,Anne L.; Elliott, John T (Cytometry. Part A : the journal of the International Society for Analytical Cytology, 2011)
The extracellular matrix protein tenascin-C plays a critical role in development, wound healing, and cancer progression, but how it is controlled and how it exerts its physiological responses remain unclear. By quantifying the behavior of live cells with phase contrast and fluorescence microscopy, the dynamic regulation of TN-C promoter activity is examined. We employ an NIH 3T3 cell line stably transfected with the TN-C promoter ligated to the gene sequence for destabilized green fluorescent protein (GFP). Fully automated image analysis routines, validated by comparison with data derived from manual segmentation and tracking of single cells, are used to quantify changes in the cellular GFP in hundreds of individual cells throughout their cell cycle during live cell imaging experiments lasting 62 h. We find that individual cells vary substantially in their expression patterns over the cell cycle, but that on average TN-C promoter activity increases during the last 40% of the cell cycle. We also find that the increase in promoter activity is proportional to the activity earlier in the cell cycle. This work illustrates the application of live cell microscopy and automated image analysis of a promoter-driven GFP reporter cell line to identify subtle gene regulatory mechanisms that are difficult to uncover using population averaged measurements.
Keywords: Animals; cell cycle; Gene Expression Regulation; Green Fluorescent Proteins; Image Processing, Computer-Assisted; Mice; Microscopy, Fluorescence; Microscopy, Phase-Contrast; NIH 3T3 Cells; Promoter Regions, Genetic; Tenascin

CHI 2011 sustainability community invited panel: challenges ahead - Khan,Azam; Bartram,Lyn; Blevis,Eli; DiSalvo,Carl; Jon Froehlich; Kurtenbach,Gordon (2011 annual conference extended abstracts on Human factors in computing systems, 2011)
As part of a new CHI Sustainability Community, focused on environmental sustainability, this panel will discuss specific ways in which HCI research will be critical in finding solutions to this global challenge. While research to date has primarily focused on the end consumer, the panel will be challenged with enlarging the discussion to include the designer as a target user and to consider interfaces and interactions that support sustainable design and sustainable manufacturing, as well as sustainable consumption. Specifically, to make real progress, we seek to enumerate ways that HCI needs to grow, as well as to find ways that can help more HCI researchers to become involved.
Keywords: design; Environment; sustainability; community; user behavior

Citation Handling for Improved Summarization of Scientific Documents - Whidby,Michael; Zajic, David; Dorr, Bonnie J (Instititue for Advanced Computer Studies, Univ of Maryland, College Park, 2011)
In this paper we present the first steps toward improving summarizationof scientific documents through citation analysis and parsing. Prior work (Mohammad et al., 2009) argues that citation texts (sentences that cite other papers) play a crucial role in automatic summarization of a topical area, but did not take into account the noise introduced by the citations themselves. We demonstrate that it is possible to improve summarization output through careful handling of these citations. We base our experiments on the application of an improved trimming approach to summarization of citation texts extracted from Question-Answering and Dependency-Parsing documents. We demonstrate that confidence scores from the Stanford NLP Parser (Klein and Manning, 2003) are significantly improved, and that Trimmer (Zajic et al., 2007), a sentence-compression tool, is able to generate higher-quality candidates. Our summarization output is currently used as part of a larger system, Action Science Explorer (ASE) (Gove, 2011).
Keywords: Technical Report

Cloud software upgrades: Challenges and opportunities - Neamtiu, I.; Tudor Dumitras (2011 International Workshop on the Maintenance and Evolution of Service-Oriented and Cloud-Based Systems (MESOCA), 2011)
The fast evolution pace for cloud computing software is on a collision course with our growing reliance on cloud computing. On one hand, cloud software must have the agility to evolve rapidly, in order to remain competitive; on the other hand, more and more critical services become dependent on the cloud and demand high availability through firm Service Level Agreements (SLAs) for cloud infrastructures. This race between the needs to increase both the cloud upgrade frequency and the service availability is unsustainable. In this paper we highlight challenges and opportunities for upgrades in the cloud. We survey the release histories of several cloud applications to analyze their evolution pace, and we discuss the shortcomings with current cloud upgrade mechanisms. We outline several solutions for sustaining this evolution while improving availability, by focusing on the novel characteristics of cloud computing. By discussing several promising directions for realizing this vision, we propose a research agenda for the future of software upgrades in the cloud.
Keywords: Availability; Cloud computing; cloud computing software; cloud upgrade frequency; collision course; Electronic publishing; Encyclopedias; service level agreement; service-oriented architecture

Computing morse decompositions for triangulated terrains: an analysis and an experimental evaluation - Vitali,M.; De Floriani, Leila; Magillo,P. (Image Analysis and Processing–ICIAP 2011, 2011)
We consider the problem of extracting the morphology of a terrain discretized as a triangle mesh. We discuss first how to transpose Morse theory to the discrete case in order to describe the morphology of triangulated terrains. We review algorithms for computing Morse decompositions, that we have adapted and implemented for triangulated terrains. We compare the the Morse decompositions produced by them, by considering two different metrics.

A Corpus-Guided Framework for Robotic Visual Perception - Teo,C.L.; Yang, Y.; Daumé, Hal; Fermüller, Cornelia; Aloimonos, J. (Workshops at the Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011)

Correcting Errors in Digital Lexicographic Resources Using a Dictionary Manipulation Language - Zajic, David; Maxwell,Michael; David Doermann; Rodrigues,Paul; Bloodgood,Michael (Electronic lexicography in the 21st century: new applications for new users (eLEX2011), 2011)
We describe a paradigm for combining manual and automatic error correction of noisy structured lexicographic data. Modifications to the structure and underlying text of the lexicographic data are expressed in a simple, interpreted programming language. Dictionary Manipulation Language (DML) commands identify nodes by unique identifiers, and manipulations are performed using simple commands such as create, move, set text, etc. Corrected lexicons are produced by applying sequences of DML commands to the source version of the lexicon. DML commands can be written manually to repair one-off errors or generated automatically to correct recurring problems. We discuss advantages of the paradigm for the task of editing digital bilingual dictionaries.

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

Creating contextual help for GUIs using screenshots - Tom Yeh; Chang,Tsung-Hsiang; Xie,Bo; Walsh,Greg; Watkins,Ivan; Wongsuphasawat,Krist; Huang,Man; Davis, Larry S.; Bederson, Benjamin B. (Proceedings of the 24th annual ACM symposium on User interface software and technology, 2011)
Contextual help is effective for learning how to use GUIs by showing instructions and highlights on the actual interface rather than in a separate viewer. However, end-users and third-party tech support typically cannot create contextual help to assist other users because it requires programming skill and source code access. We present a creation tool for contextual help that allows users to apply common computer skills-taking screenshots and writing simple scripts. We perform pixel analysis on screenshots to make this tool applicable to a wide range of applications and platforms without source code access. We evaluated the tool's usability with three groups of participants: developers, in-structors, and tech support. We further validated the applicability of our tool with 60 real tasks supported by the tech support of a university campus.
Keywords: contextual help; help; pixel analysis

Cross Language Entity Linking - McNamee,Paul; Mayfield,James; Lawrie,Dawn; Oard, Douglas; David Doermann (IJCNLP: International Joint Conference on Natural Language Processing, 2011)
There has been substantial recent interest in aligning mentions of named entities in unstructured texts to knowledge base descriptors, a task commonly called entity linking. This technology is crucial for applications in knowledge discovery and text data mining. This paper presents experiments in the new problem of cross language entity linking, where documents and named entities are in a different language than that used for the content of the reference knowledge base. We have created a new test collection to evaluate cross-language entity linking performance in twenty-one languages. We present experiments that examine issues such as: the importance of transliteration; the utility of cross-language information retrieval; and, the potential benefit of multilingual named entity recognition. Our best model achieves performance which is 94% of a strong monolingual baseline.

Cross-Language Entity Linking in Maryland during a Hurricane - McNamee,Paul; Mayfield,James; Oard, Douglas; David Doermann; Xu,Tan; Wu,Ke (TAC, 2011)
Our team from the JHUHLTCOE and the University of Maryland submitted runs for all three variants of the TACKBP entity linking task. For the monolingual tasks, we essentially mirrored our HLTCOETAC-KBP 2010 submission, making only modest changes to accommodate differences in 2011, namely the requirement to cluster NIL responses, and the change in evaluation measure. However, our work on the cross-lingual task was significantly more involved, requiring development of robust, multiphased transliteration software, use of techniques in cross-language information retrieval, and reliance on a Chinese-to- English statistical machine translation system. In this paper we describe our work for the 2011 evaluation and the results we obtained.

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

A Decomposition-based Approach to Modeling and Understanding Arbitrary Shapes - Canino,D.; De Floriani, Leila (Eurographics Italian Chapter Conference 2011, 2011)

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)

Detecting Structural Irregularity in Electronic Dictionaries Using Language Modeling - Rodrigues,Paul; Zajic, David; Bloodgood,Michael; Ye,Peng; David Doermann (Electronic lexicography in the 21st century: new applications for new users (eLEX2011), 2011)
Dictionaries are often developed using Extensible Markup Language (XML)-based standards. Very often, these standards allow many high-level repeating elements to represent lexical entries, and utilize descendants of these repeating elements to represent the structure within each lexical entry, in the form of an XML tree. In many cases, dictionaries are published that have errors and inconsistencies that would be too expensive to find manually. This paper discusses a method for dictionary writers to audit structural regularity across entries in a dictionary, quickly, by using statistical language modelling. The approach learns the patterns of XML nodes that could occur within an XML tree, and then calculates the probability of each XML tree in the dictionary against these patterns to look for entries that diverge from the norm.

Dimension-independent simplification and refinement of Morse complexes - Čomić,Lidija; De Floriani, Leila (Graphical Models, 2011)
Ascending and descending Morse complexes, determined by a scalar field f defined over a manifold M, induce a subdivision of M into regions associated with critical points of f, and compactly represent the topology of M. We define two simplification operators on Morse complexes, which work in arbitrary dimensions, and we define their inverse refinement operators. We describe how simplification and refinement operators affect Morse complexes on M, and we show that these operators form a complete set of atomic operators to create and update Morse complexes on M. Thus, any operator that modifies Morse complexes on M can be expressed as a suitable sequence of the atomic simplification and refinement operators we have defined. The simplification and refinement operators also provide a suitable basis for the construction of a multi-resolution representation of Morse complexes.
Keywords: Morse complexes; Morse theory; Refinement; shape modeling; simplification; Topological representations

Discrete Curvature Estimators: an Experimental Evaluation - Mesmoudi,M. M.; De Floriani, Leila; Magillo,P. (Department of Computer Science and Information Science, University of Genoa, 2011)
In this paper, we consider a surface, embedded in 3D space, which is discretely approximatedas triangle mesh. We define a method for estimating mean and Gaussian curvatures of such a discrete surface, based on simulating the analytic definition of mean and Gaussian curvatures in the continuum. Such method leads to what we call mean and Gaussian Ccurvatures. We present experiments evaluating such curvatures.

Document Image Classification and Labeling using Multiple Instance Learning - Kumar,Jayant; Pillai,Jaishanker; David Doermann (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
The labeling of large sets of images for training or testing analysis systems can be a very costly and time-consuming process. Multiple instance learning (MIL) is a generalization of traditional supervised learning which relaxes the need for exact labels on training instances. Instead, the labels are required only for a set of instances known as bags. In this paper, we apply MIL to the retrieval and localization of signatures and the retrieval of images containing machine-printed text, and show that a gain of 15-20% in performance can be achieved over the supervised learning with weak-labeling. We also compare our approach to supervised learning with fully annotated training data and report a competitive accuracy for MIL. Using our experiments on real-world datasets, we show that MIL is a good alternative when the training data has only document-level annotation.

EAAI-10: The First Symposium on Educational Advances in Artificial Intelligence - desJardins, Marie; Sahami,Mehran; Wagstaff,Kiri (AI Magazine, 2011)
Keywords: education, AI, symposium

Educational advances in artificial intelligence - Sahami,Mehran; desJardins, Marie; Dodds,Zachary; Neller,Todd (Proceedings of the 42nd ACM technical symposium on Computer science education, 2011)
In 2010 a new annual symposium on Educational Advances in Artificial Intelligence (EAAI) was launched as part of the AAAI annual meeting. The event was held in cooperation with ACM SIGCSE and has many similar goals related to broadening and disseminating work in computer science education. EAAI has a particular focus, however, as the event is specific to educational work in Artificial Intelligence and collocated with a major research conference (AAAI) to promote more interaction between researchers and educators in that domain. This panel seeks to introduce participants to EAAI as a way of fostering more interaction between educational communities in computing. Specifically, the panel will discuss the goals of EAAI, provide an overview of the kinds of work presented at the symposium, and identify potential synergies between that EAAI and SIGCSE as a way of better linking the two communities going forward.
Keywords: artificial intelligence education; model AI assignments

Efficient and secure threshold-based event validation for vanets - Hsiao, H. C.; Studer, A.; Dubey, R.; Elaine Shi; Perrig, A. (2011)
Determining whether the number of vehicles reporting anevent is above a threshold is an important mechanism for VANETs, because many applications rely on a threshold number of notifications to reach agreement among vehicles, to determine the validity of an event, or to prevent the abuse of emergency alarms. We present the first efficient and se- cure threshold-based event validation protocol for VANETs. Quite counter-intuitively, we found that the z-smallest ap- proach offers the best tradeoff between security and effi- ciency since other approaches perform better for probabilis- tic counting. Analysis and simulation shows that our pro- tocol provides > 99% accuracy despite the presence of at- tackers, collection and distribution of alerts in less than 1 second, and negligible impact on network performance.

EFFICIENT PARALLEL NON-NEGATIVE LEAST SQUARES ON MULTI-CORE ARCHITECTURES - Luo,Y.; Duraiswami, Ramani (SIAM Journal on Scientific Computing, 2011)
We parallelize a version of the active-set iterative algorithm derived from the originalworks of Lawson and Hanson [Solving Least Squares Problems, Prentice-Hall, 1974] on multicore architectures. This algorithm requires the solution of an unconstrained least squares problem in every step of the iteration for a matrix composed of the passive columns of the original system matrix. To achieve improved performance, we use parallelizable procedures to efficiently update and downdate the QR factorization of the matrix at each iteration, to account for inserted and removed columns. We use a reordering strategy of the columns in the decomposition to reduce computation and memory access costs. We consider graphics processing units (GPUs) as a new mode for efficient parallel computations and compare our implementations to that of multicore CPUs. Both synthetic and nonsynthetic data are used in the experiments.

Energy efficient monitoring in sensor networks - Deshpande, Amol; Khuller, Samir; Malekian,A.; Toossi,M. (Algorithmica, 2011)
We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots), and activate each set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice.We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in α different sets (time-slots). This means that the battery life is extended by a factor of k, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation algorithms for this problem.

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

Face Tracking and Recognition in Video - Chellapa, Rama; Du,Ming; Turaga,Pavan; Zhou,Shaohua Kevin (Handbook of Face RecognitionHandbook of Face Recognition, 2011)
In this chapter, we describe the utility of videos in enhancing performance of image-based recognition tasks. We discuss a joint tracking-recognition framework that allows for using the motion information in a video to better localize and identify the person in the video using still galleries. We discuss how to jointly capture facial appearance and dynamics to obtain a parametric representation for video-to-video recognition. We discuss recognition in multi-camera networks where the probe and gallery both consist of multi-camera videos. Concluding remarks and directions for future research are provided.

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

Fast Rule-line Removal using Integral Images and Support Vector Machines - Kumar,Jayant; David Doermann (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
In this paper, we present a fast and effective method for removing pre-printed rule-lines in handwritten document images. We use an integral-image representation which allows fast computation of features and apply techniques for large scale Support Vector learning using a data selection strategy to sample a small subset of training data. Results on both constructed and real-world data sets show that the method is effective for rule-line removal. We compare our method to a subspace-based method and show that better accuracy can be achieved in considerably less time. The integral-image based features proposed in the paper are generic and can be applied to other problems as well.

Gene Coexpression Network Topology of Cardiac Development, Hypertrophy, and FailureClinical Perspective - Dewey,Frederick E; Perez,Marco V; Wheeler,Matthew T; Watt,Clifton; Spin,Joshua; Langfelder,Peter; Horvath,Steve; Hannenhalli, Sridhar; Cappola,Thomas P.; Ashley,Euan A (Circulation: Cardiovascular GeneticsCirc Cardiovasc Genet, 2011)
Background— Network analysis techniques allow a more accurate reflection of underlying systems biology to be realized than traditional unidimensional molecular biology approaches. Using gene coexpression network analysis, we define the gene expression network topology of cardiac hypertrophy and failure and the extent of recapitulation of fetal gene expression programs in failing and hypertrophied adult myocardium.Methods and Results— We assembled all myocardial transcript data in the Gene Expression Omnibus (n=1617). Because hierarchical analysis revealed species had primacy over disease clustering, we focused this analysis on the most complete (murine) dataset (n=478). Using gene coexpression network analysis, we derived functional modules, regulatory mediators, and higher-order topological relationships between genes and identified 50 gene coexpression modules in developing myocardium that were not present in normal adult tissue. We found that known gene expression markers of myocardial adaptation were members of upregulated modules but not hub genes. We identified ZIC2 as a novel transcription factor associated with coexpression modules common to developing and failing myocardium. Of 50 fetal gene coexpression modules, 3 (6%) were reproduced in hypertrophied myocardium and 7 (14%) were reproduced in failing myocardium. One fetal module was common to both failing and hypertrophied myocardium. Conclusions— Network modeling allows systems analysis of cardiovascular development and disease. Although we did not find evidence for a global coordinated program of fetal gene expression in adult myocardial adaptation, our analysis revealed specific gene expression modules active during both development and disease and specific candidates for their regulation.
Keywords: fetal; Gene expression; heart failure; hypertrophy; myocardium

GPU algorithms for diamond-based multiresolution terrain processing - Yalçın,M. A.; Weiss,K.; De Floriani, Leila (Eurographics Symposium on Parallel Graphics and Visualization, 2011)
We present parallel algorithms for processing, extracting and rendering adaptively sampled regular terraindatasets represented as a multiresolution model defined by a super-square-based diamond hierarchy. This model represents a terrain as a nested triangle mesh generated through a series of longest edge bisections and encoded in an implicit hierarchical structure, which clusters triangles into diamonds and diamonds into super-squares. We decompose the problem into three parallel algorithms for performing: generation of the diamond hierarchy from a regularly distributed terrain dataset, selective refinement on the diamond hierarchy and generation of the corre- sponding crack-free triangle mesh for processing and rendering. We avoid the data transfer bottleneck common to previous approaches by processing all data entirely on the GPU. We demonstrate that this parallel approach can be successfully applied to interactive terrain visualization with a high tessellation quality on commodity GPUs.

Hawkeye and AMOS: Visualizing and Assessing the Quality of Genome Assemblies - Schatz,Michael C; Phillippy,Adam M; Sommer,Daniel D; Delcher,Arthur L.; Puiu,Daniela; Narzisi,Giuseppe; Salzberg,Steven L.; Pop, Mihai (Briefings in Bioinformatics, 2011)
Since its launch in 2004, the open-source AMOS project has released several innovative DNA sequence analysis applications including: Hawkeye, a visual analytics tool for inspecting the structure of genome assemblies; the Assembly Forensics and FRCurve pipelines for systematically evaluating the quality of a genome assembly; and AMOScmp, the first comparative genome assembler. These applications have been used to assemble and analyze dozens of genomes ranging in complexity from simple microbial species through mammalian genomes. Recent efforts have been focused on enhancing support for new data characteristics brought on by second- and now third-generation sequencing. This review describes the major components of AMOS in light of these challenges, with an emphasis on methods for assessing assembly quality and the visual analytics capabilities of Hawkeye. These interactive graphical aspects are essential for navigating and understanding the complexities of a genome assembly, from the overall genome structure down to individual bases. Hawkeye and AMOS are available open source at http://amos.sourceforge.net.
Keywords: assembly forensics; DNA Sequencing; genome assembly; visual analytics

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

IA*: An adjacency-based representation for non-manifold simplicial shapes in arbitrary dimensions - Canino,David; De Floriani, Leila; Weiss,Kenneth (Computers & Graphics, 2011)
We propose a compact, dimension-independent data structure for manifold, non-manifold and non-regular simplicial complexes, that we call the Generalized Indexed Data Structure with Adjacencies (IA⁎ data structure). It encodes only top simplices, i.e. the ones that are not on the boundary of any other simplex, plus a suitable subset of the adjacency relations. We describe the IA⁎ data structure in arbitrary dimensions, and compare the storage requirements of its 2D and 3D instances with both dimension-specific and dimension-independent representations. We show that the IA⁎ data structure is more cost effective than other dimension-independent representations and is even slightly more compact than the existing dimension-specific ones. We present efficient algorithms for navigating a simplicial complex described as an IA⁎ data structure. This shows that the IA⁎ data structure allows retrieving all topological relations of a given simplex by considering only its local neighborhood and thus it is a more efficient alternative to incidence-based representations when information does not need to be encoded for boundary simplices.
Keywords: Non-manifold data structures; simplicial complexes; Topological data structures

Image ranking and retrieval based on multi-attribute queries - Siddiquie,B.; Feris,R.S.; Davis, Larry S. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
We propose a novel approach for ranking and retrieval of images based on multi-attribute queries. Existing image retrieval methods train separate classifiers for each word and heuristically combine their outputs for retrieving multiword queries. Moreover, these approaches also ignore the interdependencies among the query terms. In contrast, we propose a principled approach for multi-attribute retrieval which explicitly models the correlations that are present between the attributes. Given a multi-attribute query, we also utilize other attributes in the vocabulary which are not present in the query, for ranking/retrieval. Furthermore, we integrate ranking and retrieval within the same formulation, by posing them as structured prediction problems. Extensive experimental evaluation on the Labeled Faces in the Wild(LFW), FaceTracer and PASCAL VOC datasets show that our approach significantly outperforms several state-of-the-art ranking and retrieval methods.
Keywords: datasets; image; datasets; PASCAL; faces; FaceTracer; in; methods; labeled; queries; image; ranking; image; retrieval; retrieval; the; VOC; wild; multiattribute

Increased gene sampling provides stronger support for higher-level groups within gracillariid leaf mining moths and relatives (Lepidoptera: Gracillariidae) - Kawahara,A. Y; Ohshima,I; Kawakita,A; Regier,J. C; Mitter,C; Cummings, Michael P.; Davis,DR; Wagner,DL; De Prinis,J; Lopez-Vaamonde,C (BMC Evol Biol, 2011)

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

An iterative algorithm for homology computation on simplicial shapes - Boltcheva,Dobrina; Canino,David; Merino Aceituno,Sara; Léon,Jean-Claude; De Floriani, Leila; Hétroy,Franck (Computer-Aided Design, 2011)
We propose a new iterative algorithm for computing the homology of arbitrary shapes discretized through simplicial complexes. We demonstrate how the simplicial homology of a shape can be effectively expressed in terms of the homology of its sub-components. The proposed algorithm retrieves the complete homological information of an input shape including the Betti numbers, the torsion coefficients and the representative homology generators.To the best of our knowledge, this is the first algorithm based on the constructive Mayer–Vietoris sequence, which relates the homology of a topological space to the homologies of its sub-spaces, i.e. the sub-components of the input shape and their intersections. We demonstrate the validity of our approach through a specific shape decomposition, based only on topological properties, which minimizes the size of the intersections between the sub-components and increases the efficiency of the algorithm.
Keywords: Computational topology; Generators; Mayer–Vietoris sequence; shape decomposition; simplicial complexes; Z -homology

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.

Kernel PLS regression for robust monocular pose estimation - Dondera,R.; Davis, Larry S. (Computer Vision and Pattern Recognition Workshops (CVPRW), 2011 IEEE Computer Society Conference on, 2011)
We evaluate the robustness of five regression techniques for monocular 3D pose estimation. While most of the discriminative pose estimation methods focus on overcoming the fundamental problem of insufficient training data, we are interested in characterizing performance improvement for increasingly large training sets. Commercially available rendering software allows us to efficiently generate large numbers of realistic images of poses from diverse actions. Inspired by recent work in human detection, we apply PLS and kPLS regression to pose estimation. We observe that kPLS regression incrementally approximates GP regression using the strongest nonlinear correlations between image features and pose. This provides robustness, and our experiments show kPLS regression is more robust than two GP-based state-of-the-art methods for pose estimation.
Keywords: (computer; 3D; analysis; rendering; correlations; projection; detection; monocular; detection; pose; estimation; Gaussian; estimation; nonlinear; estimation; regression; GP; graphics); images; rendering; latent; monocular; PLS; pose; process; Kernel; processes; object; regression; Gaussian; regression; human; software; robust; structures; realistic; to

Kernelized Renyi distance for subset selection and similarity scoring - Srinivasan,Balaji Vasan; Duraiswami, Ramani (Technical Reports of the Computer Science Department, 2011)
Renyi entropy refers to a generalized class of entropies that have beenused in several applications. In this work, we derive a non-parametric distance between distributions based on the quadratic Renyi entropy. The distributions are estimated via Parzen density estimates. The quadratic complexity of the distance evaluation is mitigated with GPU-based parallelization. This results in an efficiently evaluated non-parametric entropic distance - the kernelized Renyi distance or the KRD. We adapt the KRD into a similarity measure and show its application to speaker recognition. We further extend KRD to measure dissimilarities between distributions and illustrate its applications to statistical subset selection and dictionary learning for object recognition and pose estimation.
Keywords: Technical Report

A large-scale benchmark dataset for event recognition in surveillance video - Oh,Sangmin; Hoogs, A.; Perera,A.; Cuntoor, N.; Chen,Chia-Chih; Lee,Jong Taek; Mukherjee,S.; Aggarwal, JK; Lee,Hyungtae; Davis, Larry S.; Swears,E.; Wang,Xioyang; et al. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
We introduce a new large-scale video dataset designed to assess the performance of diverse visual event recognition algorithms with a focus on continuous visual event recognition (CVER) in outdoor areas with wide coverage. Previous datasets for action recognition are unrealistic for real-world surveillance because they consist of short clips showing one action by one individual [15, 8]. Datasets have been developed for movies [11] and sports [12], but, these actions and scene conditions do not apply effectively to surveillance videos. Our dataset consists of many outdoor scenes with actions occurring naturally by non-actors in continuously captured videos of the real world. The dataset includes large numbers of instances for 23 event types distributed throughout 29 hours of video. This data is accompanied by detailed annotations which include both moving object tracks and event examples, which will provide solid basis for large-scale evaluation. Additionally, we propose different types of evaluation modes for visual recognition tasks and evaluation metrics along with our preliminary experimental results. We believe that this dataset will stimulate diverse aspects of computer vision research and help us to advance the CVER tasks in the years ahead.
Keywords: algorithm; evaluation; CVER; databases; databases; video; dataset; moving; event; metrics; large-scale; object; recognition; recognition; diverse; recognition; video; scenes; surveillance; surveillance; visual; tasks; computer; tracks; outdoor; video; video; computer; vision; continuous; vision; image; visual

Learning a discriminative dictionary for sparse coding via label consistent K-SVD - Zhuolin Jiang; Zhe Lin; Davis, Larry S. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
A label consistent K-SVD (LC-KSVD) algorithm to learn a discriminative dictionary for sparse coding is presented. In addition to using class labels of training data, we also associate label information with each dictionary item (columns of the dictionary matrix) to enforce discriminability in sparse codes during the dictionary learning process. More specifically, we introduce a new label consistent constraint called `discriminative sparse-code error' and combine it with the reconstruction error and the classification error to form a unified objective function. The optimal solution is efficiently obtained using the K-SVD algorithm. Our algorithm learns a single over-complete dictionary and an optimal linear classifier jointly. It yields dictionaries so that feature points with the same class labels have similar sparse codes. Experimental results demonstrate that our algorithm outperforms many recently proposed sparse coding techniques for face and object category recognition under the same learning conditions.
Keywords: classification error; Dictionaries; dictionary learning process; discriminative sparse code error; face recognition; image classification; Image coding; K-SVD; label consistent; learning (artificial intelligence); object category recognition; Object recognition; optimal linear classifier; reconstruction error; singular value decomposition; Training data

Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions - Tzoumas,K.; Deshpande, Amol; Jensen,C. S (Proceedings of the VLDB Endowment, 2011)
As a result of decades of research and industrial development, mod-ern query optimizers are complex software artifacts. However, the quality of the query plan chosen by an optimizer is largely deter- mined by the quality of the underlying statistical summaries. Small selectivity estimation errors, propagated exponentially, can lead to severely sub-optimal plans. Modern optimizers typically maintain one-dimensional statistical summaries and make the attribute value independence and join uniformity assumptions for efficiently esti- mating selectivities. Therefore, selectivity estimation errors in to- day’s optimizers are frequently caused by missed correlations be- tween attributes. We present a selectivity estimation approach that does not make the independence assumptions. By carefully using concepts from the field of graphical models, we are able to fac- tor the joint probability distribution of all the attributes in the data- base into small, usually two-dimensional distributions. We describe several optimizations that can make selectivity estimation highly efficient, and we present a complete implementation inside Post- greSQL’s query optimizer. Experimental results indicate an order of magnitude better selectivity estimates, while keeping optimiza- tion time in the range of tens of milliseconds.

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.

Local Response Context Applied to Pedestrian Detection - Schwartz,W.; Davis, Larry S.; Pedrini,H. (Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications, 2011)
Appearing as an important task in computer vision, pedestrian detection has been widely investigated in the recent years. To design a robust detector, we propose a feature descriptor called Local Response Context (LRC). This descriptor captures discriminative information regarding the surrounding of the person’s location by sampling the response map obtained by a generic sliding window detector. A partial least squares regression model using LRC descriptors is learned and employed as a second classification stage (after the execution of the generic detector to obtain the response map). Experiments based on the ETHZ pedestrian dataset show that the proposed approach improves significantly the results achieved by the generic detector alone and is comparable to the state-of-the-art methods.

Machine Translation Evaluation and Optimization - Dorr, Bonnie J; Olive,Joseph; McCary,John; Christianson,Caitlin (Handbook of Natural Language Processing and Machine TranslationHandbook of Natural Language Processing and Machine Translation, 2011)
The evaluation of machine translation (MT) systems is a vital field of research, both for determining the effectiveness of existing MT systems and for optimizing the performance of MT systems. This part describes a range of different evaluation approaches used in the GALE community and introduces evaluation protocols and methodologies used in the program. We discuss the development and use of automatic, human, task-based and semi-automatic (human-in-the-loop) methods of evaluating machine translation, focusing on the use of a human-mediated translation error rate HTER as the evaluation standard used in GALE. We discuss the workflow associated with the use of this measure, including post editing, quality control, and scoring. We document the evaluation tasks, data, protocols, and results of recent GALE MT Evaluations. In addition, we present a range of different approaches for optimizing MT systems on the basis of different measures. We outline the requirements and specific problems when using different optimization approaches and describe how the characteristics of different MT metrics affect the optimization. Finally, we describe novel recent and ongoing work on the development of fully automatic MT evaluation metrics that have the potential to substantially improve the effectiveness of evaluation and optimization of MT systems.

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.

Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems - Li,Jian; Deshpande, Amol (2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011)
We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings over probabilistic graphs, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of risk averse or risk-prone behaviors, and instead we consider a more general objective which is to maximize the expected utility of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). We show that we can obtain a polynomial time approximation algorithm with additive error ϵ for any ϵ >; 0, if there is a pseudopolynomial time algorithm for the exact version of the problem (This is true for the problems mentioned above) and the maximum value of the utility function is bounded by a constant. Our result generalizes several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.
Keywords: Approximation algorithms; Approximation methods; combinatorial problems; Fourier series; knapsack problems; optimisation; OPTIMIZATION; polynomial approximation; polynomial time approximation algorithm; Polynomials; Random variables; stochastic combinatorial optimization; stochastic knapsack; stochastic shortest path; stochastic spanning tree; vectors

Method and System for Dereverberation of Signals Propagating in ... - O'donovan,Adam; Duraiswami, Ramani; Zotkin,Dmitry N (2011)
The dereverberation of signals in reverberating environments is carried out via acquiring the representation (image) of spatial distribution of the signals in space of interest and automatic identification of reflections of the source signal in the reverberative space. The technique relies on identification of prominent features at the image, as well as corresponding directions of propagation of signals manifested by the prominent features at the image, and computation of similarity metric between signals corresponding to the prominent features in the image. The time delays between the correlated signals (i.e., source signal and related reflections) are found and the signals are added coherently. Multiple beamformers operate on the source signal and corresponding reflections, enabling one to improve the signal-to-noise ratio in multi-path environments.

Model AI Assignments 2011 - Neller,Todd William; desJardins, Marie; Oates,Tim; Taylor,Matthew E (Second AAAI Symposium on Educational Advances in Artificial Intelligence, 2011)
The Model AI Assignments session seeks to gather and disseminate the best assignment designs of the Artificial Intelligence (AI) Education community. Recognizing that assignments form the core of student learning experience, we here present abstracts of three AI assignments from the 2011 session that are easily adoptable, playfully engaging, and flexible for a variety of instructor needs.

Modeling Multiresolution 3D Scalar Fields through Regular Simplex Bisection - Weiss,K.; De Floriani, Leila; Hagen,H. (Scientific Visualization: Interactions, Features, Metaphors, 2011)
We review modeling techniques for multiresolution three-dimensional scalar fields based on a dis-cretization of the field domain into nested tetrahedral meshes generated through regular simplex bisection. Such meshes are described through hierarchical data structures and their representa- tion is characterized by the modeling primitive used. The primary conceptual distinction among the different approaches proposed in the literature is whether they treat tetrahedra or clusters of tetrahedra, called diamonds, as the modeling primitive. We first focus on representations for the modeling primitive and for nested meshes. Next, we survey the applications of these meshes to modeling multiresolution 3D scalar fields, with an emphasis on interactive visualization. We also consider the relationship of such meshes to octrees. Finally, we discuss directions for further research

MOMMIE Knows Best: Systematic Optimizations for Verifiable Distributed Algorithms - Maniatis, Petros; Dietz, Michael; Charalampos Papamanthou (HotOS'13 Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, 2011)

Multi-agent event recognition in structured scenarios - Morariu,V.I.; Davis, Larry S. (Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, 2011)
We present a framework for the automatic recognition of complex multi-agent events in settings where structure is imposed by rules that agents must follow while performing activities. Given semantic spatio-temporal descriptions of what generally happens (i.e., rules, event descriptions, physical constraints), and based on video analysis, we determine the events that occurred. Knowledge about spatio-temporal structure is encoded using first-order logic using an approach based on Allen's Interval Logic, and robustness to low-level observation uncertainty is provided by Markov Logic Networks (MLN). Our main contribution is that we integrate interval-based temporal reasoning with probabilistic logical inference, relying on an efficient bottom-up grounding scheme to avoid combinatorial explosion. Applied to one-on-one basketball, our framework detects and tracks players, their hands and feet, and the ball, generates event observations from the resulting trajectories, and performs probabilistic logical inference to determine the most consistent sequence of events. We demonstrate our approach on 1hr (100,000 frames) of outdoor videos.
Keywords: Allen; analysis; Markov; descriptions; video; event; grounding; inference; semantic; interval; Logic; logic; interval-based; logic; Markov; logic; multi-agent; logical; networks; bottom-up; processes; formal; processing; reasoning; multiagent; reasoning; video; recognition; probabilistic; recognition; temporal; scheme; first-order; signal; spatio-temporal; systems; object; temporal

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

No-reference image quality assessment based on visual codebook - Ye,Peng; David Doermann (Image Processing (ICIP), 2011 18th IEEE International Conference on, 2011)
In this paper, we propose a new learning based No-Reference Image Quality Assessment (NR-IQA) algorithm, which uses a visual codebook consisting of robust appearance descriptors extracted from local image patches to capture complex statistics of natural image for quality estimation. We use Gabor filter based local features as appearance descriptors and the codebook method encodes the statistics of natural image classes by vector quantizing the feature space and accumulating histograms of patch appearances based on this coding. This method does not assume any specific types of distortion and experimental results on the LIVE image quality assessment database show that this method provides consistent and reliable performance in quality estimation that exceeds other state-of-the-art NR-IQA approaches and is competitive with the full reference measure PSNR.
Keywords: assessment; quality; codebook; Gabor; descriptors; complex; estimation; visual; extraction; image; filter; appearance; filters; feature; gabor; image; image; no-reference; patches; natural; QUALITY; statistics; local; texture

A novel feature descriptor based on the shearlet transform - Schwartz, W.R.; da Silva,R.D.; Davis, Larry S.; Pedrini,H. (Image Processing (ICIP), 2011 18th IEEE International Conference on, 2011)
Problems such as image classification, object detection and recognition rely on low-level feature descriptors to represent visual information. Several feature extraction methods have been proposed, including the Histograms of Oriented Gradients (HOG), which captures edge information by analyzing the distribution of intensity gradients and their directions. In addition to directions, the analysis of edge at different scales provides valuable information. Shearlet transforms provide a general framework for analyzing and representing data with anisotropic information at multiple scales. As a consequence, signal singularities, such as edges, can be precisely detected and located in images. Based on the idea of employing histograms to estimate the distribution of edge orientations and on the accurate multi-scale analysis provided by shearlet transforms, we propose a feature descriptor called Histograms of Shearlet Coefficients (HSC). Experimental results comparing HOG with HSC show that HSC provides significantly better results for the problems of texture classification and face identification.
Keywords: analysis; multiscale; analysis; object; classification; face; classification; image; classification; intensity; coefficients; image; descriptor; feature; detection; object; distribution; edge; EXTRACTION; extraction; image; gradient; gradients; histograms; identification; feature; methods; histograms; of; orientations; face; oriented; recognition; feature; recognition; shearlet; recognition; transforms; shearlet; singularities; texture; texture; object; transform; signal

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)

Object Detection and Tracking for Intelligent Video Surveillance - Kim,K.; Davis, Larry S. (Multimedia Analysis, Processing and Communications, 2011)
Appearing as an important task in computer vision, pedestrian detection has been widely investigated in the recent years. To design a robust detector, we propose a feature descriptor called Local Response Context (LRC). This descriptor captures discriminative information regarding the surrounding of the person’s location by sampling the response map obtained by a generic sliding window detector. A partial least squares regression model using LRC descriptors is learned and employed as a second classification stage (after the execution of the generic detector to obtain the response map). Experiments based on the ETHZ pedestrian dataset show that the proposed approach improves significantly the results achieved by the generic detector alone and is comparable to the state-of-the-art methods.

Offline Writer Identification using K-Adjacent Segments - Jain,Rajiv; David Doermann (International Conference on Document Analysis and Recognition, 2011)
This paper presents a method for performing offline writer identification by using K-adjacent segment (KAS) features in a bag-of-features framework to model a user’s handwriting. This approach achieves a top 1 recognition rate of 93% on the benchmark IAMEnglish handwriting dataset, which outperforms current state of the art features. Results further demonstrate that identification performance improves as the number of training samples increase, and additionally, that the performance of the KAS features extend to Arabic handwriting found in the MADCAT dataset.

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.

Partial least squares based speaker recognition system - Srinivasan,B.V.; Zotkin,Dmitry N; Duraiswami, Ramani (Snowbird Learning Workshop, 2011)

A partial least squares framework for speaker recognition - Srinivasan,B.V.; Zotkin,Dmitry N; Duraiswami, Ramani (Acoustics, Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on, 2011)
Modern approaches to speaker recognition (verification) operate in a space of "supervectors" created via concatenation of the mean vectors of a Gaussian mixture model (GMM) adapted from a universal background model (UBM). In this space, a number of approaches to model inter-class separability and nuisance attribute variability have been proposed. We develop a method for modeling the variability associated with each class (speaker) by using partial-least-squares - a latent variable modeling technique, which isolates the most informative subspace for each speaker. The method is tested on NIST SRE 2008 data and provides promising results. The method is shown to be noise-robust and to be able to efficiently learn the subspace corresponding to a speaker on training data consisting of multiple utterances.
Keywords: approximations; speaker; attribute; background; GMM; Gaussian; least; mixture; model; Gaussian; model; NIST; modeling; processes; least; recognition; recognition; speaker; separability; latent; squares; squares; partial-least-squares; speaker; SRE; interclass; technique; multiple; utterances; nuisance; variability; partial; variable; verification; universal

Photo-based mobile deixis system and related techniques - Darrell,Trevor J; Tom Yeh; Tollmar,Konrad (2011)
A mobile deixis device includes a camera to capture an image and a wireless handheld device, coupled to the camera and to a wireless network, to communicate the image with existing databases to find similar images. The mobile deixis device further includes a processor, coupled to the device, to process found database records related to similar images and a display to view found database records that include web pages including images. With such an arrangement, users can specify a location of interest by simply pointing a camera-equipped cellular phone at the object of interest and by searching an image database or relevant web resources, users can quickly identify good matches from several close ones to find an object of interest.

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

Playing to Program: Towards an Intelligent Programming Tutor for RUR-PLE - desJardins, Marie; Ciavolino,Amy; Deloatch,Robert; Feasley,Eliana (Second AAAI Symposium on Educational Advances in Artificial Intelligence, 2011)
Intelligent tutoring systems (ITSs) provide students with a one-on-one tutor, allowing them to work at their own pace, and helping them to focus on their weaker areas. The RUR1–Python Learning Environment (RUR-PLE), a game-like virtual environment to help students learn to program, provides an interface for students to write their own Python code and visualize the code execution (Roberge 2005). RUR-PLE provides a fixed sequence of learning lessons for students to explore. We are extending RUR-PLE to develop the Playing to Program (PtP) ITS, which consists of three components: (1) a Bayesian student model that tracks student competence, (2) a diagnosis module that provides tailored feedback to students, and (3) a problem selection module that guides the student’s learning process. In this paper, we summarize RUR-PLE and the PtP design, and describe an ongoing user study to evaluate the predictive accuracy of our student modeling approach.

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

The PR-star octree: a spatio-topological data structure for tetrahedral meshes - Weiss,Kenneth; De Floriani, Leila; Fellegara,Riccardo; Velloso,Marcelo (Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2011)
We propose the PR-star octree as a combined spatial data structure for performing efficient topological queries on tetrahedral meshes. The PR-star octree augments the Point Region octree (PR Octree) with a list of tetrahedra incident to its indexed vertices, i.e. those in the star of its vertices. Thus, each leaf node encodes the minimal amount of information necessary to locally reconstruct the topological connectivity of its indexed elements. This provides the flexibility to efficiently construct the optimal data structure to solve the task at hand using a fraction of the memory required for a corresponding data structure on the global tetrahedral mesh. Due to the spatial locality of successive queries in typical GIS applications, the construction costs of these runtime data structures are amortized over multiple accesses while processing each node. We demonstrate the advantages of the PR-star octree representation in several typical GIS applications, including detection of the domain boundaries, computation of local curvature estimates and mesh simplification.

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.

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 Efficient Multiparty Computing of Multivariate Polynomials and Applications - Dana Dachman-Soled; Malkin, Tal; Raykova, Mariana; Yung, Moti (Applied Cryptography and Network Security, 2011)
We present a robust secure methodology for computing functions that are represented as multivariate polynomials where parties hold different variables as private inputs. Our generic efficient protocols are fully black-box and employ threshold additive homomorphic encryption; they do not assume honest majority, yet are robust in detecting any misbehavior. We achieve solutions that take advantage of the algebraic structure of the polynomials, and are polynomial-time in all parameters (security parameter, polynomial size, polynomial degree, number of parties). We further exploit a “round table” communication paradigm to reduce the complexity in the number of parties. A large collection of problems are naturally and efficiently represented as multivariate polynomials over a field or a ring: problems from linear algebra, statistics, logic, as well as operations on sets represented as polynomials. In particular, we present a new efficient solution to the multi-party set intersection problem, and a solution to a multi-party variant of the polynomial reconstruction problem.
Keywords: additive homomorphic encryption; Algorithm Analysis and Problem Complexity; Computer Communication Networks; Data Encryption; Discrete Mathematics in Computer Science; Management of Computing and Information Systems; multiparty set intersection; multivariate polynomial evaluation; secret sharing; secure multiparty computation; Systems and Data Security; threshold cryptosystems

Segmentation of Handwritten Textlines in Presence of Touching Components - Kumar,Jayant; Kang,Le; David Doermann; Abd-Almageed, Wael (Intl. Conf. on Document Analysis and Recognition (ICDAR 11), 2011)
This paper presents an approach to textline extraction in handwritten document images which combines local and global techniques. We propose a graph-based technique to detect touching and proximity errors that are common with handwritten text lines. In a refinement step, we use Expectation-Maximization (EM) to iteratively split the error segments to obtain correct text-lines. We show improvement in accuracies using our correction method on datasets of Arabic document images. Results on a set of artificially generated proximity images show that the method is effective for handling touching errors in handwritten document images.

Selective transfer between learning tasks using task-based boosting - Eaton,E.; desJardins, Marie; others (Twenty-Fifth AAAI Conference on Artificial Intelligence, 2011)

Sensitivity analysis and explanations for robust query evaluation in probabilistic databases - Kanagal,B.; Li,J.; Deshpande, Amol (Proceedings of the 2011 international conference on Management of data, 2011)
Probabilistic database systems have successfully established them-selves as a tool for managing uncertain data. However, much of the research in this area has focused on efficient query evaluation and has largely ignored two key issues that commonly arise in uncer- tain data management: First, how to provide explanations for query results, e.g., “Why is this tuple in my result?” or “Why does this output tuple have such high probability?”. Second, the problem of determining the sensitive input tuples for the given query, e.g., users are interested to know the input tuples that can substantially alter the output, when their probabilities are modified (since they may be unsure about the input probability values). Existing systems pro- vide the lineage/provenance of each of the output tuples in addition to the output probabilities, which is a boolean formula indicating the dependence of the output tuple on the input tuples. However, lineage does not immediately provide a quantitative relationship and it is not informative when we have multiple output tuples. In this paper, we propose a unified framework that can handle both the issues mentioned above to facilitate robust query processing. We formally define the notions of influence and explanations and provide algorithms to determine the top-l influential set of variables and the top-l set of explanations for a variety of queries, including conjunctive queries, probabilistic threshold queries, top-k queries and aggregation queries. Further, our framework naturally enables highly efficient incremental evaluation when input probabilities are modified (e.g., if uncertainty is resolved). Our preliminary exper- imental results demonstrate the benefits of our framework for per- forming robust query processing over probabilistic databases.

Shape Codebook based Handwritten and Machine Printed Text Zone Extraction - Kumar,Jayant; Prasad,Rohit; Cao,Huiagu; Abd-Almageed, Wael; David Doermann; Natarajan,Prem (Document Recognition and Retrieval, 2011)
We present a novel method for extracting handwritten and printed text zones from noisy document images with mixed content. We use Triple-Adjacent-Segment (TAS) based features which encode local shape characteristics of text in a consistent manner. We first construct two different codebooks of the shape features extracted from a set of handwritten and printed text documents. In the next step, we compute the normalized histogram of codewords for each segmented zone and use it to train Support Vector Machine (SVM) classifier. Due to a codebook based approach, our method is robust to the background noise present in the image. The TAS features used are invariant to translation, scale and rotation of text. In our experimental results, we show that a pixel-weighted zone classification accuracy of 98% can be achieved for noisy Arabic documents. Further, we demonstrate the effectiveness of our method for document page classification and show that a high precision can be achieved for machine printed documents. The proposed method is robust to the size of zones, which may contain text content at word, line or paragraph level.

Simplex and Diamond Hierarchies: Models and Applications - Weiss,K.; De Floriani, Leila (Computer Graphics Forum, 2011)
Hierarchical spatial decompositions are a basic modelling tool in a variety of application domains. Several papers on this subject deal with hierarchical simplicial decompositions generated through regular simplex bisection. Such decompositions, originally developed for finite elements, are extensively used as the basis for multi-resolution models of scalar fields, such as terrains, and static or time-varying volume data. They have also been used as an alternative to quadtrees and octrees as spatial access structures. The primary distinction among all such approaches is whether they treat the simplex or clusters of simplices, called diamonds, as the modelling primitive. This leads to two classes of data structures and to different query approaches. We present the hierarchical models in a dimension-independent manner, and organize the description of the various applications, primarily interactive terrain rendering and isosurface extraction, according to the dimension of the domain.
Keywords: hierarchy of diamonds; hierarchy of simplices; I.3.5 [Computer Graphics]: Computational Geometry and Object Modelling— Hierarchy and geometric transformations; I.3.6 [Computer Graphics]: Methodology and Techniques—Graphics data structures and data types; interactive terrain visualization; mesh‐based multiresolution models; multiresolution isosurfaces; nested refinement schemes; Regular simplex bisection; scalar field visualization; spatial access structures

Simplifying morphological representations of 2D and 3D scalar fields - Čomić,Lidija; De Floriani, Leila; Iuricich,Federico (Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2011)
We describe a dual graph-based representation for the ascending and descending Morse complexes of a scalar field, and a compact and dimension-independent data structure based on it, which assumes a discrete representation of the field as a simplicial mesh. We present atomic dimension-independent simplification operators on the graph-based representation. Based on such operators, we have developed a simplification algorithm, which allows generalization of the ascending and descending Morse complexes at different levels of resolution. We show here the results of our implementation, discussing the computation times and the size of the resulting simplified graphs, also in comparison with the size of the original full-resolution graph.
Keywords: morphological representations; Morse complexes; multi-dimensional data sets; simplification

Smale-like decomposition and forman theory for discrete scalar fields - Čomić,L.; Mesmoudi,M.; De Floriani, Leila (Discrete Geometry for Computer Imagery, 2011)
Forman theory, which is a discrete alternative for cell complexes to the well-known Morse theory, is currently finding several applications in areas where the data to be handled are discrete, such as image processing and computer graphics. Here, we show that a discrete scalar field f, defined on the vertices of a triangulated multidimensional domain Σ, and its gradient vector field Grad f through the Smale-like decomposition of f [6], are both the restriction of a Forman function F and its gradient field Grad F that extends f over all the simplexes of Σ. We present an algorithm that gives an explicit construction of such an extension. Hence, the scalar field f inherits the properties of Forman gradient vector fields and functions from field Grad F and function F.

Smart task-driven video collection - Lim,Ser-Nam; Mittal,Anurag; Davis, Larry S. (2011)
A multi-camera system that collects images and videos of moving objects in dynamic and crowded scenes, subject to task constraints is disclosed. The system constructs “task visibility intervals” comprising information about what can be sensed in future time intervals. Methods for constructing these intervals applying prediction of future object motion and including consideration of factors such as object occlusion and camera control parameters are also disclosed. Using a plane-sweep algorithm, these atomic intervals can be combined in a method to form multi-task intervals, during which a single camera can collect videos suitable for multiple tasks simultaneously. Methods for fast camera scheduling that yield solutions within a small constant factor of an optimal solution are also disclosed.

Spam or ham?: characterizing and detecting fraudulent "not spam" reports in web mail systems - Ramachandran,Anirudh; Dasgupta,Anirban; Feamster, Nick; Weinberger,Kilian (Proceedings of the 8th Annual Collaboration, Electronic messaging, Anti-Abuse and Spam Conference, 2011)
Web mail providers rely on users to "vote" to quickly and col-laboratively identify spam messages. Unfortunately, spammers have begun to use bots to control large collections of compromised Web mail accounts not just to send spam, but also to vote "not spam" on incoming spam emails in an attempt to thwart collaborative filtering. We call this practice a vote gaming attack. This attack confuses spam filters, since it causes spam messages to be mislabeled as legitimate; thus, spammer IP addresses can continue sending spam for longer. In this paper, we introduce the vote gaming attack and study the extent of these attacks in practice, using four months of email voting data from a large Web mail provider. We develop a model for vote gaming attacks, explain why existing detection mechanisms cannot detect them, and develop a new, scalable clustering-based detection method that identifies compromised accounts that engage in vote-gaming attacks. Our method detected 1.1 million potentially compromised accounts with only a 0.17% false positive rate, which is nearly 10 times more effective than existing clustering methods used to detect bots that send spam from compromised Web mail accounts.

Stroke-like Pattern Noise Removal in Binary Document Images - Agrawal,Mudit; David Doermann (International Conference on Document Analysis and Recognition, 2011)
This paper presents a two-phased stroke-like pattern noise (SPN) removal algorithm for binary document images. The proposed approach aims at understanding script-independent prominent text component features using supervised classification as a first step. It then uses their cohesiveness and stroke-width properties to filter and associate smaller text components with them using an unsupervised classification technique. In order to perform text extraction, and hence noise removal, at diacritic-level, this divide-and-conquer technique does not assume the availability of accurate and large amounts of ground-truth data at component-level for training purposes. The method was tested on a collection of degraded and noisy, machine-printed and handwritten binary Arabic text documents. Results show pixel-level precision and recall of 98% and 97% respectively.

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

Template based Segmentation of Touching Components in Handwritten Text Lines - Kang,Le; David Doermann (11th Intl. Conf. on Document Analysis and Recognition (ICDAR'11), 2011)
In this paper, we present a template based approach to the segmentation of touching components in handwritten text lines. Local patches around touching components are identified and a dictionary is created consisting of template patches together with correct segmentations. We use two shape context based methods to compute similarity between input patches and dictionary templates to find the best match. The template's known segmentation is then transformed to segment the input patch. Experiments are carried on a dataset of touching text lines.

Toward a Standard Benchmark for Computer Security Research: The Worldwide Intelligence Network Environment (WINE) - Tudor Dumitras; Shou, Darren (BADGERS '11 Proceedings of the First Workshop on Building Analysis Datasets and Gathering Experience Returns for Security, 2011)
Unlike benchmarks that focus on performance or reliability evaluations, a benchmark for computer security must necessarily include sensitive code and data. Because these artifacts could damage systems or reveal personally identifiable information about the users affected by cyber attacks, publicly disseminating such a benchmark raises several scientific, ethical and legal challenges. We propose the Worldwide Intelligence Network Environment (WINE), a security-benchmarking approach based on rigorous experimental methods. WINE includes representative field data, collected worldwide from 240,000 sensors, for new empirical studies, and it will enable the validation of research on all the phases in the lifecycle of security threats. We tackle the key challenges for security benchmarking by designing a platform for repeatable experimentation on the WINE data sets and by collecting the metadata required for understanding the results. In this paper, we review the unique characteristics of the WINE data, we discuss why rigorous benchmarking will provide fresh insights on the security arms race and we propose a research agenda for this area.

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)

A trust model for supply chain management - Haghpanah,Y.; desJardins, Marie; others (The 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 3, 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 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.

A unified approach to ranking in probabilistic databases - Li,Jian; Saha,Barna; Deshpande, Amol (The VLDB Journal, 2011)
Ranking is a fundamental operation in data analysis and decision support and plays an even more crucial role if the dataset being explored exhibits uncertainty. This has led to much work in understanding how to rank the tuples in a probabilistic dataset in recent years. In this article, we present a unified approach to ranking and top-k query processing in probabilistic databases by viewing it as a multi-criterion optimization problem and by deriving a set of features that capture the key properties of a probabilistic dataset that dictate the ranked result. We contend that a single, specific ranking function may not suffice for probabilistic databases, and we instead propose two parameterized ranking functions, called PRF ¿ and PRF e, that generalize or can approximate many of the previously proposed ranking functions. We present novel generating functions-based algorithms for efficiently ranking large datasets according to these ranking functions, even if the datasets exhibit complex correlations modeled using probabilistic and/xor trees or Markov networks. We further propose that the parameters of the ranking function be learned from user preferences, and we develop an approach to learn those parameters. Finally, we present a comprehensive experimental study that illustrates the effectiveness of our parameterized ranking functions, especially PRF e, at approximating other ranking functions and the scalability of our proposed algorithms for exact or approximate ranking.
Keywords: Approximation techniques; Graphical models; Learning to rank; Probabilistic databases; Ranking

Using Agent-Based Simulation to Determine an Optimal Lane-Changing Strategy on a Multi-Lane Highway - Tuzo,J.; Seymour,J.; desJardins, Marie; others (2011 AAAI Fall Symposium Series, 2011)

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.

Vehicle Detection Using Partial Least Squares - Kembhavi,A.; Harwood,D.; Davis, Larry S. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2011)
Detecting vehicles in aerial images has a wide range of applications, from urban planning to visual surveillance. We describe a vehicle detector that improves upon previous approaches by incorporating a very large and rich set of image descriptors. A new feature set called Color Probability Maps is used to capture the color statistics of vehicles and their surroundings, along with the Histograms of Oriented Gradients feature and a simple yet powerful image descriptor that captures the structural characteristics of objects named Pairs of Pixels. The combination of these features leads to an extremely high-dimensional feature set (approximately 70,000 elements). Partial Least Squares is first used to project the data onto a much lower dimensional subspace. Then, a powerful feature selection analysis is employed to improve the performance while vastly reducing the number of features that must be calculated. We compare our system to previous approaches on two challenging data sets and show superior performance.
Keywords: aerial images; color probability maps; oriented gradients feature; partial least squares; powerful feature selection analysis; urban planning; vehicle detection; visual surveillance; gradient methods; image colour analysis; least squares approximations; road vehicle; Automated

Visualizing Missing Data: Graph Interpretation User Study - Drizd,Terence; Eaton,Cyntrica; Plaisant, Catherine (IFIP Lecture Notes in Computer Science (LNCS), 2011)
Visualizing Missing Data: Graph Interpretation User Study

Advanced tracking systems: computational approaches to be introduced to new series - HAMMOUD,R.; Porikli, F.; Davis, Larry S. (Augmented vision & reality, 2010)
Modern visual tracking systems implement a computational process that is often divided into several modules such as localization, tracking, recognition, behavior analysis and classification of events. This book will focus on recent advances in computational approaches for detection and tracking of human body, road boundaries and lane markers as well as on recognition of human activities, drowsiness and distraction state. This book is composed of seven distinct parts. Part I covers people localization algorithms in video sequences. Part II describes successful approaches for tracking people and bodyparts. The third part focuses on tracking of pedestrian and vehicles in outdoor images. Part IV describes recent methods to track lane markers and road boundaries. In part V, methods to track head, hand and facial features are reviewed. The last two parts cover the topics of automatic recognition and classification of activity, gesture, behavior, drowsiness and visual distraction state of humans.

Aligning Spatio-Temporal Signals on a Special Manifold - Ruonan Li; Chellapa, Rama (Computer Vision – ECCV 2010Computer Vision – ECCV 2010, 2010)
We investigate the spatio-temporal alignment of videos or features/signals extracted from them. Specifically, we formally define an alignment manifold and formulate the alignment problem as an optimization procedure on this non-linear space by exploiting its intrinsic geometry. We focus our attention on semantically meaningful videos or signals, e.g., those describing or capturing human motion or activities, and propose a new formalism for temporal alignment accounting for executing rate variations among realizations of the same video event. By construction, we address this static and deterministic alignment task in a dynamic and stochastic manner: we regard the search for optimal alignment parameters as a recursive state estimation problem for a particular dynamic system evolving on the alignment manifold. Consequently, a Sequential Importance Sampling iteration on the alignment manifold is designed for effective and efficient alignment. We demonstrate the performance on several types of input data that arise in vision problems.

An animated multivariate visualization for physiological and clinical data in the ICU - Ordóñez,Patricia; desJardins, Marie; Lombardi,Michael; Lehmann,Christoph U.; Fackler,Jim (Proceedings of the 1st ACM International Health Informatics Symposium, 2010)
Current visualizations of electronic medical data in the Intensive Care Unit (ICU) consist of stacked univariate plots of variables over time and a tabular display of the current numeric values for the corresponding variables and occasionally an alarm limit. The value of information is dependent upon knowledge of historic values to determine a change in state. With the ability to acquire more historic information, providers need more sophisticated visualization tools to assist them in analyzing the data in a multivariate fashion over time. We present a multivariate time series visualization that is interactive and animated, and has proven to be as effective as current methods in the ICU for predicting an episode of acute hypotension in terms of accuracy, confidence, and efficiency with only 30-60 minutes of training.
Keywords: computational physiology; Information Visualization; multivariate; time series

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.]

Automatic matched filter recovery via the audio camera - O'Donovan,A.E.; Duraiswami, Ramani; Zotkin,Dmitry N (Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, 2010)
The sound reaching the acoustic sensor in a realistic environment contains not only the part arriving directly from the sound source but also a number of environmental reflections. The effect of those on the sound is equivalent to a convolution with the room impulse response and can be undone via deconvolution - a technique known as matched filter processing. However, the filter is usually pre-computed in advance using known room geometry and source/receiver positions, and any deviations from those cause the performance to degrade significantly. In this work, an algorithm is proposed to compute the matched filter automatically using an audio camera - a microphone array based system that provides real-time audio images (essentially plots of steered response power in various directions) of environment. Acoustic sources, as well as their significant reflections, are revealed as peaks in the audio image. The reflections are associated with sound source(s) using an acoustic similarity metric, and an approximate matched filter is computed to align the reflections in time with the direct arrival. Preliminary experimental evaluation of the method is performed. It is shown that in case of two sources the reflections are identified correctly, the time delays recovered agree well with those computed from geometric constraints, and that the output SNR improves when the reflections are added coherently to the signal obtained by beamforming directly at the source.
Keywords: acoustic; array; real-time; arrays; transient; audio; camera; automatic; constraints; microphone; filter; filters; microphone; images; room; impulse; Matched; positions; acoustic; processing; cameras; matched; radiators; array; recovery; beamforming; geometric; response; response; sound; sensor; acoustic; signal; source; source/receiver; sources; audio

Broadening student enthusiasm for computer science with a great insights course - desJardins, Marie; Littman,Michael (Proceedings of the 41st ACM technical symposium on Computer science education, 2010)
We describe the "Great Insights in Computer Science" courses that are taught at Rutgers and UMBC. These courses were designed independently, but have in common a broad, engaging introduction to computing for non-majors. Both courses include a programming component to help the students gain an intuition for computational concepts, but neither is primarily programming focused. We present data to show that these courses attract a diverse group of students; are rated positively; and increase students' understanding of, and attitudes towards, computing and computational issues.
Keywords: attitudes towards computing; introductory courses

Building a dynamic reputation system for DNS - Antonakakis,M.; Perdisci,R.; Dagon,D.; Lee,W.; Feamster, Nick (19th Usenix Security Symposium, 2010)
The Domain Name System (DNS) is an essential protocolused by both legitimate Internet applications and cyber at- tacks. For example, botnets rely on DNS to support agile com- mand and control infrastructures. An effective way to disrupt these attacks is to place malicious domains on a “blocklist” (or “blacklist”) or to add a filtering rule in a firewall or net- work intrusion detection system. To evade such security coun- termeasures, attackers have used DNS agility, e.g., by using new domains daily to evade static blacklists and firewalls. In this paper we propose Notos, a dynamic reputation system for DNS. The premise of this system is that malicious, agile use of DNS has unique characteristics and can be distinguished from legitimate, professionally provisioned DNS services. No- tos uses passive DNS query data and analyzes the network and zone features of domains. It builds models of known legit- imate domains and malicious domains, and uses these models to compute a reputation score for a new domain indicative of whether the domain is malicious or legitimate. We have eval- uated Notos in a large ISP’s network with DNS traffic from 1.4 million users. Our results show that Notos can identify malicious domains with high accuracy (true positive rate of 96.8%) and low false positive rate (0.38%), and can identify these domains weeks or even months before they appear in public blacklists.

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 as codesigners of new technologies: Valuing the imagination to transform what is possible - Druin, Allison (New Directions for Youth Development, 2010)

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 genomic analysis reveals evidence of two novel Vibrio species closely related to V. cholerae - Bradd,H.; Christopher,G.; Nur,H.; Seon-Young,C.; Jongsik,C.; Thomas,B.; David,B.; Jean,C.; Chris,D. J.; Cliff,H.; Rita R Colwell (BMC Microbiology, 2010)
In recent years genome sequencing has been used to characterize new bacterial species, a method of analysis available as a result of improved methodology and reduced cost. Included in a constantly expanding list of Vibrio species are several that have been reclassified as novel members of the Vibrionaceae. The description of two putative new Vibrio species, Vibrio sp. RC341 and Vibrio sp. RC586 for which we propose the names V. metecus and V. parilis, respectively, previously characterized as non-toxigenic environmental variants of V. cholerae is presented in this study. Results Based on results of whole-genome average nucleotide identity (ANI), average amino acid identity (AAI), rpoB similarity, MLSA, and phylogenetic analysis, the new species are concluded to be phylogenetically closely related to V. cholerae and V. mimicus. Vibrio sp. RC341 and Vibrio sp. RC586 demonstrate features characteristic of V. cholerae and V. mimicus, respectively, on differential and selective media, but their genomes show a 12 to 15% divergence (88 to 85% ANI and 92 to 91% AAI) compared to the sequences of V. cholerae and V. mimicus genomes (ANI <95% and AAI <96% indicative of separate species). Vibrio sp. RC341 and Vibrio sp. RC586 share 2104 ORFs (59%) and 2058 ORFs (56%) with the published core genome of V. cholerae and 2956 (82%) and 3048 ORFs (84%) with V. mimicus MB-451, respectively. The novel species share 2926 ORFs with each other (81% Vibrio sp. RC341 and 81% Vibrio sp. RC586). Virulence-associated factors and genomic islands of V. cholerae and V. mimicus, including VSP-I and II, were found in these environmental Vibrio spp. Conclusions Results of this analysis demonstrate these two environmental vibrios, previously characterized as variant V. cholerae strains, are new species which have evolved from ancestral lineages of the V. cholerae and V. mimicus clade. The presence of conserved integration loci for genomic islands as well as evidence of horizontal gene transfer between these two new species, V. cholerae, and V. mimicus suggests genomic islands and virulence factors are transferred between these species.

Compressive Acquisition of Dynamic Scenes - Sankaranarayanan,Aswin; Turaga,Pavan; Baraniuk,Richard; Chellapa, Rama (Computer Vision – ECCV 2010Computer Vision – ECCV 2010, 2010)
Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals and images that enables sampling rates significantly below the classical Nyquist rate. Despite significant progress in the theory and methods of CS, little headway has been made in compressive video acquisition and recovery. Video CS is complicated by the ephemeral nature of dynamic events, which makes direct extensions of standard CS imaging architectures and signal models infeasible. In this paper, we develop a new framework for video CS for dynamic textured scenes that models the evolution of the scene as a linear dynamical system (LDS). This reduces the video recovery problem to first estimating the model parameters of the LDS from compressive measurements, from which the image frames are then reconstructed. We exploit the low-dimensional dynamic parameters (the state sequence) and high-dimensional static parameters (the observation matrix) of the LDS to devise a novel compressive measurement strategy that measures only the dynamic part of the scene at each instant and accumulates measurements over time to estimate the static parameters. This enables us to considerably lower the compressive measurement rate considerably. We validate our approach with a range of experiments including classification experiments that highlight the effectiveness of the proposed approach.

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

On Computing Compression Trees for Data Collection in Wireless Sensor Networks - Li,Jian; Deshpande, Amol; Khuller, Samir (2010 Proceedings IEEE INFOCOM, 2010)
We address the problem of efficiently gathering correlated data from a wireless sensor network, with the aim of designing algorithms with provable optimality guarantees, and understanding how close we can get to the known theoretical lower bounds. Our proposed approach is based on finding an optimal or a near-optimal compression tree for a given sensor network: a compression tree is a directed tree over the sensor network nodes such that the value of a node is compressed using the value of its parent. We focus on broadcast communication model in this paper, but our results are more generally applicable to a unicast communication model as well. We draw connections between the data collection problem and a previously studied graph concept called weakly connected dominating sets, and we use this to develop novel approximation algorithms for the problem. We present comparative results on several synthetic and real-world datasets showing that our algorithms construct near-optimal compression trees that yield a significant reduction in the data collection cost.
Keywords: Approximation algorithms; Base stations; Communications Society; Computer networks; Computer science; computing compression trees; Costs; data collection; Data communication; data compression; designing algorithms; Educational institutions; Entropy; graph concept; Monitoring; Protocols; trees (mathematics); weakly connected dominating sets; Wireless sensor networks

Confidence-based feature acquisition to minimize training and test costs - desJardins, Marie; MacGlashan,James; Wagstaff,Kiri L (Proceedings of the SIAM Conference on Data Mining, 2010)
We present Confidence-based Feature Acquisition (CFA), a novel supervised learning method for acquiring missing feature values when there is missing data at both training and test time. Previous work has considered the cases of missing data at training time (e.g., Active Feature Acquisition, AFA 8), or at test time (e.g., Cost-Sensitive Naive Bayes, CSNB 2), but not both. At training time, CFA constructs a cascaded ensemble of classifiers, starting with the zero-cost features and adding a single feature for each successive model. For each model, CFA selects a subset of training instances for which the added feature should be acquired. At test time, the set of models is applied sequentially (as a cascade), stopping when a user-supplied confidence threshold is met. We compare CFA to AFA, CSNB, and several other baselines, and find that CFAs accuracy is at least as high as the other methods, while incurring significantly lower feature acquisition costs.

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)

Context-Aware and Content-Based Dynamic Voronoi Page Segmentation - Agrawal,Mudit; David Doermann (The Nineth IAPRInternational Workshop on Document Analysis Systems, 2010)
This paper presents a dynamic approach to document page segmentation based on inter-component relationships, local patterns and context features. State-of-the art page segmentation algorithms segment zones based on local properties of neighboring connected components such as distance and orientation, and do not typically consider additional properties other than size. Our proposed approach uses a contextually aware and dynamically adaptive page segmentation scheme. The page is first over-segmented using a dynamically adaptive scheme of separation features based on [2] and adapted from [13]. A decision to form zones is then based on the context built from these local separation features and high-level content features. Zone-based evaluation was performed on sets of printed and handwritten documents in English and Arabic scripts with multiple font types, sizes and we achieved an increase of 15% over the accuracy reported in [2].