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

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

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

Genomic characterization of the Yersinia genus - Chen, P.E.; Cook, C.; Stewart, A.C.; Nagarajan,N.; Sommer, D.D.; Pop, Mihai; Thomason, B.; Thomason, M.P.K.; Lentz, S.; Nolan, N.; others (Genome biology, 2010)

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

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

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

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

On the importance of sharing negative results - Giraud-Carrier,C.; Dunham,M.H.; Atreya,A.; Elkan,C.; Perlich,C.; Swirszcz,G.; Shi,X.; Philip,S.Y.; Fürnkranz,J.; Sima,J.F. (SIGKDD explorations, 2010)

On the initialization methods of an exterior point algorithm for the assignment problem - Charalampos Papamanthou; Paparrizos, K.; Samaras, N.; Sifaleras, A. (International Journal of Computer Mathematics, 2010)
In this paper, we present a theoretical investigation and an extensive computational study of exterior point simplex algorithm (EPSA) initialization methods for the assignment problem (AP). We describe the exterior point algorithm using three different initialization methods. Effective implementations are explored for each initialization method. Then we perform an experimental evaluation on a large set of benchmark problems from the TSPLib 95 and OR Library collections. The results obtained demonstrate the advantages of the three initialization methods. Finally, we give a theoretical justification of the initialization methods efficiency. We explain theoretically the computational ranking for these methods.

Integrating structured metadata with relational affinity propagation - Plangprasopchok,A.; Lerman,K.; Getoor, Lise (In proceedings of AAAI Workshop on Statistical Relational AI, 2010)
Structured and semi-structured data describing entities, tax- onomies and ontologies appears in many domains. There is a huge interest in integrating structured information from multiple sources; however integrating structured data to in- fer complex common structures is a difficult task because the integration must aggregate similar structures while avoiding structural inconsistencies that may appear when the data is combined. In this work, we study the integration of struc- tured social metadata: shallow personal hierarchies specified by many individual users on the Social Web, and focus on in- ferring a collection of integrated, consistent taxonomies. We frame this task as an optimization problem with structural constraints. We propose a new inference algorithm, which we refer to as Relational Affinity Propagation (RAP) that ex- tends affinity propagation (Frey and Dueck 2007) by intro- ducing structural constraints. We validate the approach on a real-world social media dataset, collected from the photoshar- ing website Flickr. Our empirical results show that our pro- posed approach is able to construct deeper and denser struc- tures compared to an approach using only the standard affin- ity propagation algorithm.

Interactive information visualization for exploring and querying electronic health records: A systematic review - Rind,A.; Wang,T. D; Aigner,W.; Miksh,S.; Wongsuphasawat,K.; Plaisant, Catherine; Shneiderman, Ben (Human-Computer Interaction Lab, University of Maryland, 2010)
To overcome the complexity and scale of making medical decisions based on electronic health records (EHRs) a variety of visual methods have been proposed. This paper surveys twelve state-of-the-art information visualization systems described in the scientific literature and compares them based on a set of carefully selected criteria. It aims to systematically examine the systems’ strengths and weaknesses to inform future information visualization designs.We select twelve state-of-the-art information visualization systems from information visualization, medical information systems and human-computer interaction conferences and journals. We compare the systems using the following criteria: (1) data types covered, (2) multivariate analysis support, (3) number of patients records used (one or many), and (4) user intents addressed. The review describes the twelve systems in detail and evaluates the systems using the aforementioned criteria. We discuss how the systems differ in their features and highlight how these differences are related to their design and affect the user intent model. Examples of findings include: (1) most systems handle numerical or categorical data but not both, (2) most systems are specifically designed for looking at a single patient or multiple patients but not both, (3) most systems utilize horizontal time lines to represent time, (4) only systems that handle multiple patient records have good support for Filter, and (5) some specific user intents (e.g. the Encode and Connect intents) are rarely addressed. Based on our review results, we believe that effective information visualization can facilitate analysis of patient records, and we encourage the information visualization community to study the application of their systems and conduct more in depth evaluations. We identify potential future research topics in interactive support for data abstraction and medical tasks that involve looking at a single or multiple records. Finally, we propose to create a repository for data and tasks so benchmarks can be established for both academic and commercial patient record visualization systems.

Interlingual Annotation of Parallel Text Corpora: A New Framework for Annotation and Evaluation - Dorr, Bonnie J; Passonneau,Rebecca J.; Farwell,David; Green,Rebecca; Habash,Nizar; Helmreich,Stephen; Hovy,Eduard; Levin,Lori; Miller,Keith J.; Mitamura,Teruko; Rambow,Owen; Siddharthan,Advaith (Natural Language Engineering, 2010)
This paper focuses on an important step in the creation of a system of meaning representation and the development of semantically annotated parallel corpora, for use in applications such as machine translation, question answering, text summarization, and information retrieval. The work described below constitutes the first effort of any kind to annotate multiple translations of foreign-language texts with interlingual content. Three levels of representation are introduced: deep syntactic dependencies (IL0), intermediate semantic representations (IL1), and a normalized representation that unifies conversives, nonliteral language, and paraphrase (IL2). The resulting annotated, multilingually induced, parallel corpora will be useful as an empirical basis for a wide range of research, including the development and evaluation of interlingual NLP systems and paraphrase-extraction systems as well as a host of other research and development efforts in theoretical and applied linguistics, foreign language pedagogy, translation studies, and other related disciplines.

An Internet Wide View into DNS Lookup Patterns - Hao,S.; Feamster, Nick; Pandrangi,R. (VeriSign Labs, School of Computer Science, Georgia Tech, 2010)
This paper analyzes the DNS lookup patterns from a largeauthoritative top-level domain server and characterizes how the lookup patterns for unscrupulous domains may differ from those for legitimate domains. We examine domains for phishing attacks and spam and malware related domains, and see how these lookup patterns vary in terms of both their temporal and spatial characteristics. We find that malicious domains tend to exhibit more variance in the networks that look up these domains, and we also find that these domains become popular considerably more quickly after their initial registration time. We also note that miscreant domains ex- hibit distinct clusters, in terms to the networks that look up these domains. The distinct spatial and temporal character- istics of these domains, and their tendency to exhibit simi- lar lookup behavior, suggests that it may be possible to ulti- mately develop more effective blacklisting techniques based on these differing lookup patterns.

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

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

Making sense of archived e‐mail: Exploring the Enron collection with NetLens - Kang,Hyunmo; Plaisant, Catherine; Elsayed,Tamer; Oard, Douglas (Journal of the American Society for Information Science and Technology, 2010)
Informal communications media pose new challenges for information-systems design, but the nature of informal interaction offers new opportunities as well. This paper describes NetLens-E-mail, a system designed to support exploration of the content-actor network in large e-mail collections. Unique features of NetLens-E-mail include close coupling of orientation, specification, restriction, and expansion, and introduction and incorporation of a novel capability for iterative projection between content and actor networks within the same collection. Scenarios are presented to illustrate the intended employment of NetLens-E-mail, and design walkthroughs with two domain experts provide an initial basis for assessment of the suitability of the design by scholars and analysts.

ManyNets: an interface for multiple network analysis and visualization - Freire,Manuel; Plaisant, Catherine; Shneiderman, Ben; Golbeck,Jen (Proceedings of the 28th international conference on Human factors in computing systems, 2010)
Traditional network analysis tools support analysts in studying a single network. ManyNets offers these analysts a powerful new approach that enables them to work on multiple networks simultaneously. Several thousand networks can be presented as rows in a tabular visualization, and then inspected, sorted and filtered according to their attributes. The networks to be displayed can be obtained by subdivision of larger networks. Examples of meaningful subdivisions used by analysts include ego networks, community extraction, and time-based slices. Cell visualizations and interactive column overviews allow analysts to assess the distribution of attributes within particular sets of networks. Details, such as traditional node-link diagrams, are available on demand. We describe a case study analyzing a social network geared towards film recommendations by means of decomposition. A small usability study provides feedback on the use of the interface on a set of tasks issued from the case study.
Keywords: exploratory analysis; graphical user interface; Information Visualization; interaction; network analysis; table interface

The Metacognitive Loop: An Architecture for Building Robust Intelligent Systems - Shahri,Hamid Haidarian; Dinalankara,Wikum; Fults,Scott; Wilson,Shomir; Perlis, Don; Schmill,Matt; Oates,Tim; Josyula,Darsana; Anderson,Michael (2010 AAAI Fall Symposium Series, 2010)
The Metacognitive Loop: An Architecture for Building Robust Intelligent Systems
Keywords: commonsense; ontologies; robust intelligent systems

MetaPhyler: Taxonomic profiling for metagenomic sequences - Liu,Bo; Gibbons,T.; Ghodsi,M.; Pop, Mihai (2010 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), 2010)
A major goal of metagenomics is to characterize the microbial diversity of an environment. The most popular approach relies on 16S rRNA sequencing, however this approach can generate biased estimates due to differences in the copy number of the 16S rRNA gene between even closely related organisms, and due to PCR artifacts. The taxonomic composition can also be determined from whole-metagenome sequencing data by matching individual sequences against a database of reference genes. One major limitation of prior methods used for this purpose is the use of a universal classification threshold for all genes at all taxonomic levels. We propose that better classification results can be obtained by tuning the taxonomic classifier to each matching length, reference gene, and taxonomic level. We present a novel taxonomic profiler MetaPhyler, which uses marker genes as a taxonomic reference. Results on simulated datasets demonstrate that MetaPhyler outperforms other tools commonly used in this context (CARMA, Megan and PhymmBL). We also present interesting results obtained by applying MetaPhyler to a real metagenomic dataset.
Keywords: Bioinformatics; CARMA comparison; Databases; Genomics; Linear regression; marker genes; matching length; Megan comparison; metagenomic sequences; metagenomics; MetaPhyler; microbial diversity; microorganisms; molecular biophysics; molecular configurations; Pattern classification; pattern matching; phylogenetic classification; Phylogeny; PhymmBL comparison; reference gene database; Sensitivity; sequence matching; taxonomic classifier; taxonomic level; taxonomic profiling; whole metagenome sequencing data

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

Modelling Type 1a Supernova Light Curves - Rust,Bert W.; O'Leary, Dianne P.; Mullen,Katharine M. (Exponential Data Fitting and Its ApplicationsExponential Data Fitting and Its Applications, 2010)

Multiscale directional filtering of noisy InSAR phase images - Patel, Vishal M.; Easley,Glenn R; Chellapa, Rama (Proceedings of SPIE, 2010)
In this work, we present a new approach for the problem of interferometric phase noise reduction in synthetic aperture radar interferometry based on the shearlet representation. Shearlets provide a multidirectional and multiscale decomposition that have advantages when dealing with noisy phase fringes over standard filtering methods. Using a shearlet decomposition of a noisy phase image, we can adaptively estimate a phase representation in a multiscale and anisotropic fashion. Such denoised phase interferograms can be used to provide much better digital elevation maps (DEM). Experiments show that this method performs significantly better than many competitive methods.

New forms of Human-Computer Interaction for Visualizing Information - Reiterer,H.; Kerren,A.; Plaisant, Catherine; Stasko,J.T. (Information Visualization, 2010)
The Graphical User Interface (GUI) – although developed in research laboratories in the late 1970s – is still the dominant interaction paradigm in Information Visualization. We propose a new interaction paradigm called Blended Interaction. It combines ideas of Embodied Cognition, Multimodal Interaction, Reality-Based Interaction & Ubiquitous Computing. This is intended to stress that a single increase in the reality aspect of the interaction cannot go far enough. The particular challenge – and from the user's standpoint, the key advantage – lies in a meaningful marriage between the tested real-world options and the digital world. As a minimum this marriage must exist on the levels of the interaction, communication, of the way we solve problems with conventional tools (workflows), and of the design of the space or the architecture of buildings and places. The digital world often offers entirely new possibilities and takes the form of interactive devices of various shapes but also of intelligent everyday objects (e.g. the 'Internet of things'). In our view, interaction concepts can indeed offer a new quality of interaction, but only when the design of the interaction includes all these domains at the same time and with equal weighting. We test the suitability of our ideas of Blended Interaction concepts by using specific application examples that are being worked on as part of current research projects. Our experiences show that this new interaction paradigm has also great potential for interacting with visualization. For example, we have developed multi-touch scatter plots & facet maps for tangible user interfaces supporting the searching & browsing in Digital Libraries. We have embedded different visualizations into a Zoomable Object-oriented Information Landscape (ZOIL), which supports our vision of using visualizations on different displays of different size at the same time. We have developed specific kind of search tokens that supports collaborative search activities. For example, we try to address the following research questions: * How can future interactive InfoVis tools look like, especially in the light of the idea Blended Interaction? * How can future interactive InfoVis tools benefit from Multi-Displays & Multimodal environments used by Multiple Users? * What are the specific design requirements for multi-touch visualizations? * How can we support the collaborative use visualization tools?

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

Object Classification Using Taxonomies - Tsaparas,Panayiotis; Papadimitriou,Panagiotis; Fuxman,Ariel D.; Getoor, Lise; Agrawal,Rakesh (2010)
As provided herein objects from a source catalog, such as a provider's catalog, can be added to a target catalog, such as an enterprise master catalog, in a scalable manner utilizing catalog taxonomies. A baseline classifier determines probabilities for source objects to target catalog classes. Source objects can be assigned to those classes with probabilities that meet a desired threshold and meet a desired rate. A classification cost for target classes can be determined for respective unassigned source objects, which can comprise determining an assignment cost and separation cost for the source objects for respective desired target classes. The separation and assignment costs can be combined to determine the classification cost, and the unassigned source objects can be assigned to those classes having a desired classification cost.

Optimal Authenticated Data Structures with Multilinear Forms - Charalampos Papamanthou; Tamassia, Roberto; Triandopoulos, Nikos (Pairing-Based Cryptography - Pairing 2010, 2010)
Cloud computing and cloud storage are becoming increasingly prevalent. In this paradigm, clients outsource their data and computations to third-party service providers. Data integrity in the cloud therefore becomes an important factor for the functionality of these web services.Authenticated data structures, implemented with various cryptographic primitives, have been widely studied as a means of providing efficient solutions to data integrity problems (e.g., Merkle trees). In this paper, we introduce a new authenticated dictionary data structure that employs multilinear forms, a cryptographic primitive proposed by Silverberg and Boneh in 2003 [10], the construction of which, however, remains an open problem to date. Our authenticated dictionary is optimal, that is, it does not add any extra asymptotic cost to the plain dictionary data structure, yielding proofs of constant size, i.e., asymptotically equal to the size of the answer, while maintaining other relevant complexities logarithmic. Instead, solutions based on cryptographic hashing (e.g., Merkle trees) require proofs of logarithmic size [40]. Because multilinear forms are not known to exist yet, our result can be viewed from a different angle: if one could prove that optimal authenticated dictionaries cannot exist in the computational model, irrespectively of cryptographic primitives, then our solution would imply that cryptographically interesting multilinear form generators cannot exist as well (i.e., it can be viewed as a reduction). Thus, we provide an alternative avenue towards proving the nonexistence of multilinear form generators in the context of general lower bounds for authenticated data structures [40] and for memory checking [18], a model similar to the authenticated data structures model.
Keywords: Algorithm Analysis and Problem Complexity; authenticated dictionary; Coding and Information Theory; Computer Communication Networks; Data Encryption; Discrete Mathematics in Computer Science; multilinear forms; Systems and Data Security

PADS: A Probabilistic Activity Detection Framework for Video Data - Albanese, M.; Chellapa, Rama; Cuntoor, N.; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Udrea,O. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010)
There is now a growing need to identify various kinds of activities that occur in videos. In this paper, we first present a logical language called Probabilistic Activity Description Language (PADL) in which users can specify activities of interest. We then develop a probabilistic framework which assigns to any subvideo of a given video sequence a probability that the subvideo contains the given activity, and we finally develop two fast algorithms to detect activities within this framework. OffPad finds all minimal segments of a video that contain a given activity with a probability exceeding a given threshold. In contrast, the OnPad algorithm examines a video during playout (rather than afterwards as OffPad does) and computes the probability that a given activity is occurring (even if the activity is only partially complete). Our prototype Probabilistic Activity Detection System (PADS) implements the framework and the two algorithms, building on top of existing image processing algorithms. We have conducted detailed experiments and compared our approach to four different approaches presented in the literature. We show that-for complex activity definitions-our approach outperforms all the other approaches.
Keywords: Automated; Programming Languages; Video Recording; Computer-Assisted; Models; PADL; PADS; image processing algorithms; offPad algorithm; onPad algorithm; probabilistic activity description language; probabilistic activity detection framework; video data; video sequence; image sequences; object detection; probability; video surveillance; Algorit; Statistical; Movement; Pattern Recognition

Portfolio Selection Using Tikhonov Filtering to Estimate the Covariance Matrix - Park,Sungwoo; O'Leary, Dianne P. (SIAM Journal on Financial Mathematics, 2010)
Markowitz's portfolio selection problem chooses weights for stocks in a portfolio based on an estimated covariance matrix of stock returns. Our study proposes reducing noise in the estimation by using a Tikhonov filter function. In addition, we prevent rank deficiency of the estimated covariance matrix and propose a method for effectively choosing the Tikhonov parameter, which determines the filtering intensity. We put previous estimators into a common framework and compare their filtering functions for eigenvalues of the correlation matrix. We demonstrate the effectiveness of our estimator using stock return data from 1958 through 2007.
Keywords: covariance matrix estimate; Markowitz portfolio selection; ridge regression; Tikhonov regularization

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

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

Saliency Guided Summarization of Molecular Dynamics Simulations - Patro,R.; Ip,C. Y; Varshney, Amitabh; Hagen,H. (Scientific Visualization: Advanced Concepts, 2010)
We present a novel method to measure saliency in molecular dynamics simulation data. This saliency measure is based on a multiscale center-surround mechanism, which is fast and efficient to compute. We explore the use of the saliency function to guide the selection of representative and anomalous timesteps for summarization of simulations. To this end, we also introduce a multiscale keyframe selection procedure which automatically provides keyframes representing the simulation at varying levels of coarseness. We compare our saliency guided keyframe approach against other methods, and show that it consistently selects superior keyframes as measured by their predictive power in reconstructing the simulation.

Sectored Random Projections for Cancelable Iris Biometrics - Pillai,J.K.; Patel, Vishal M.; Chellapa, Rama; Ratha,N. K (2010 IEEE International Conference on Acoustics Speech and Signal Processing (ICASSP), 2010)
Privacy and security are essential requirements in practical biometric systems. In order to prevent the theft of biometric patterns, it is desired to modify them through revocable and non invertible transformations called Cancelable Biometrics. In this paper, we propose an efficient algorithm for generating a Cancelable Iris Biometric based on Sectored Random Projections. Our algorithm can generate a new pattern if the existing one is stolen, retain the original recognition performance and prevent extraction of useful information from the transformed patterns. Our method also addresses some of the drawbacks of existing techniques and is robust to degradations due to eyelids and eyelashes.
Keywords: biometric pattern; Biometrics; Cancelable Biometrics; cancelable iris biometrics; data mining; data privacy; Degradation; Eyelashes; Eyelids; Iris; iris recognition; pattern recognition; privacy; random processes; Random Projections; Robustness; sectored random projection; Secure Biometrics; Security; security of data

Secure and robust iris recognition using random projections and sparse representations - Pillai, J.; Patel, Vishal M.; Chellapa, Rama; Ratha, N. (Pattern Analysis and Machine Intelligence, IEEE Transactions on, 2010)

Semantic Video Content Analysis - Albanese,Massimiliano; Turaga,Pavan; Chellapa, Rama; Pugliese,Andrea; Subrahmanian,V. (Video Search and MiningVideo Search and Mining, 2010)
In recent years, there has been significant interest in the area of automatically recognizing activities occurring in a camera’s field of view and detecting abnormalities. The practical applications of such a system could include airport tarmac monitoring, or monitoring of activities in secure installations, to name a few. The difficulty of the problem is compounded by several factors: detection of primitive actions in spite of changes in illumination, occlusions and noise; complexmultiagent interaction;mapping of higher-level activities to lower-level primitive actions; variations in which the same semantic activity can be performed. In this chapter, we develop a theory of semantic activity analysis that addresses each of these issues in an integrated manner. Specifically, we discuss ontological representations of knowledge of a domain, integration of domain knowledge and statistical models for achieving semantic mappings, definition of logical languages to describe activities, and design of frameworks which integrate all the above aspects in a coherent way, thus laying the foundations of effective Semantic Video Content Analysis systems.

Sensing Events Affecting Liquid Flow in a Liquid Distribution System - Patel,Shwetak N.; Fogarty,James A.; Jon Froehlich; Larson,Eric C. (University of Washington, 2010)
By monitoring pressure transients in a liquid within a liquid distribution system using only a single sensor, events such as the opening and closing of valves at specific fixtures are readily detected. The sensor, which can readily be coupled to a faucet bib, transmits an output signal to a computing device. Each such event can be identified by the device based by comparing characteristic features of the pressure transient waveform with previously observed characteristic features for events in the system. These characteristic features, which can include the varying pressure, derivative, and real Cepstrum of the pressure transient waveform, can be used to select a specific fixture where a valve open or close event has occurred. Flow to each fixture and leaks in the system can also be determined from the pressure transient signal. A second sensor disposed at a point disparate from the first sensor provides further event information.

Sequencing and Genome Assembly Using Next-Generation Technologies - Nagarajan,Niranjan; Pop, Mihai (Computational BiologyComputational Biology, 2010)
Several sequencing technologies have been introduced in recent years that dramatically outperform the traditional Sanger technology in terms of throughput and cost. The data generated by these technologies are characterized by generally shorter read lengths (as low as 35 bp) and different error characteristics than Sanger data. Existing software tools for assembly and analysis of sequencing data are, therefore, ill-suited to handle the new types of data generated. This paper surveys the recent software packages aimed specifically at analyzing new generation sequencing data.

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

Sparse representations and Random Projections for robust and cancelable biometrics - Patel, Vishal M.; Chellapa, Rama; Tistarelli,M. (Control Automation Robotics Vision (ICARCV), 2010 11th International Conference on, 2010)
In recent years, the theories of Sparse Representation (SR) and Compressed Sensing (CS) have emerged as powerful tools for efficiently processing data in non-traditional ways. An area of promise for these theories is biome #x0301;trie identification. In this paper, we review the role of sparse representation and CS for efficient biome #x0301;trie identification. Algorithms to perform identification from face and iris data are reviewed. By applying Random Projections it is possible to purposively hide the biome #x0301;trie data within a template. This procedure can be effectively employed for securing and protecting personal biome #x0301;trie data against theft. Some of the most compelling challenges and issues that confront research in biometrics using sparse representations and CS are also addressed.
Keywords: Biometric identification; Cancelable Biometrics; Compressed sensing; face data; face recognition; iris data; iris recognition; personal biometric data; Random Projections; robust biometrics; sparse representations

Sparsity inspired automatic target recognition - Patel, Vishal M.; Nasrabadi,Nasser M.; Chellapa, Rama (Proceedings of SPIE, 2010)
In this paper, we develop a framework for using only the needed data for automatic target recognition (ATR) algorithms using the recently developed theory of sparse representations and compressive sensing (CS). We show how sparsity can be helpful for efficient utilization of data, with the possibility of developing real-time, robust target classification. We verify the efficacy of the proposed algorithm in terms of the recognition rate on the well known Comanche forward-looking infrared (FLIR) data set consisting of ten different military targets at different orientations.

Structural and dynamic determinants of ligand binding and regulation of cyclin-dependent kinase 5 by pathological activator p25 and inhibitory peptide CIP. - Cardone, Antonio; Hassan, S A; Albers,R.W.; Sriram,R.D.; Pant,H.C. (Journal of molecular biology, 2010)
The crystal structure of the cdk5/p25 complex has provided information on possible molecular mechanisms of the ligand binding, specificity, and regulation of the kinase. Comparative molecular dynamics simulations are reported here for physiological conditions. This study provides new insight on the mechanisms that modulate such processes, which may be exploited to control pathological activation by p25. The structural changes observed in the kinase are stabilized by a network of interactions involving highly conserved residues within the cyclin-dependent kinase (cdk) family. Collective motions of the proteins (cdk5, p25, and CIP) and their complexes are identified by principal component analysis, revealing two conformational states of the activation loop upon p25 complexation, which are absent in the uncomplexed kinase and not apparent from the crystal. Simulations of the uncomplexed inhibitor CIP show structural rearrangements and increased flexibility of the interfacial loop containing the critical residue E240, which becomes fully hydrated and available for interactions with one of several positively charged residues in the kinase. These changes provide a rationale for the observed high affinity and enhanced inhibitory action of CIP when compared to either p25 or the physiological activators of cdk5.
Keywords: Crystallography, X-Ray; Cyclin-Dependent Kinase 5; Cyclin-Dependent Kinase Inhibitor Proteins; HUMANS; Ligands; molecular dynamics simulation; Nerve Tissue Proteins; Principal component analysis; Protein Binding; Protein Conformation

Summary of the first ACM SIGKDD workshop on knowledge discovery from uncertain data (U'09) - Pei,Jian; Getoor, Lise; de Keijzer,Ander (ACM SIGKDD Explorations Newsletter, 2010)

System and method for analysis of an opinion expressed in documents with regard to a particular topic - V.S. Subrahmanian; Picariello,Antonio; Dorr, Bonnie J; Reforgiato,Diego Recupero; Cesarano,Carmine; Sagoff,Amelia (2010)
System and method for analysis of an opinion expressed in documents on a particular topic computes opinion strength on a continuous numeric scale, or qualitatively. A variety of opinion scoring techniques are plugged in to score opinion expressing words and sentences in documents. These scores are aggregated to measure the opinion intensity of documents. Multilingual opinion analysis is supported by capability to concurrently identify and visualize the opinion intensity expressed in documents in multiple languages. A multi-dimensional representation of the measured opinion intensity is generated which is agreeable with multi-lingual domain.

Technology-Mediated Social Participation: Deep Science and Extreme Technology - Shneiderman, Ben (Active Media TechnologyActive Media Technology, 2010)
The dramatic success of social media such as Facebook, Twitter, YouTube, Flickr, blogs, and traditional discussion groups empowers individuals to become active in local and global communities. With modest redesign, these technologies can be harnessed to support national priorities such as healthcare/wellness, disaster response, community safety, energy sustainability, etc. This talk describes a research agenda for these topics that develops deep science questions and extreme technology challenges.

Understanding Interactive Legends: a Comparative Evaluation with Standard Widgets - Riche,Nathalie Henry; Lee,Bongshin; Plaisant, Catherine (Computer Graphics Forum, 2010)
Interactive information visualization systems rely on widgets to allow users to interact with the data and modify the representation. We define interactive legends as a class of controls combining the visual representation of static legends and interaction mechanisms of widgets. As interactive legends start to appear in popular websites, we categorize their designs for common data types and evaluate their effectiveness compare to standard widgets. Results suggest that 1) interactive legends can lead to faster perception of the mapping between data values and visual encodings and 2) interaction time is affected differently depending on the data type. Additionally, our study indicates superiority both in terms of perception and interaction of ordinal controls over numerical ones. Numerical techniques are mostly used in today's systems. By providing solutions to allowing users to modify ranges interactively, we believe that interactive legends make it possible to increase the use of ordinal techniques for visual exploration.
Keywords: H.5 [Information Interfaces and Presentation]: Miscellaneous—

Using symbolic evaluation to understand behavior in configurable software systems - Reisner,E.; Song,C.; Ma,K.K.; Foster, Jeffrey S.; Porter, Adam (Software Engineering, 2010 ACM/IEEE 32nd International Conference on, 2010)

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

VAST 2010 Challenge: Arms dealings and pandemics - Grinstein,G.; Konecni,S.; Scholtz,J.; Whiting,M.; Plaisant, Catherine (Visual Analytics Science and Technology (VAST), 2010 IEEE Symposium on, 2010)
The 5th VAST Challenge consisted of three mini-challenges that involved both intelligence analysis and bioinformatics. Teams could solve one, two or all three mini-challenges and assess the overall situation to enter the Grand Challenge. Mini-challenge one involved text reports about people and events giving information about arms dealers, situations in various countries and linkages between different countries. Mini-challenge two involved hospital admission and death records from various countries providing information about the spread of a world wide pandemic. Mini-challenge three involved genetic data to be used to identify the origin of the pandemic and the most dangerous viral mutations. The Grand Challenge was to determine how these various mini-challenges were connected. As always the goal was to analyze the data and provide novel interactive visualizations useful in the analytic process. We received 58 submissions in total and gave 15 awards.
Keywords: 2010; administrative; admission; intelligence; analysis; interactive; analysis; medical; challenge; arms; challenge; hospital; data; data; grand; dealings; bioinformatics; dangerous; mutations; death; processing; weapons; records; genetic; reports; bioinformatics; data; VAST; viral; visualizations; minichallenge; pandemics; text

Visual information seeking in multiple electronic health records: design recommendations and a process model - Wang,Taowei David; Wongsuphasawat,Krist; Plaisant, Catherine; Shneiderman, Ben (Proceedings of the 1st ACM International Health Informatics Symposium, 2010)
Current electronic health record (EHR) systems facilitate the storage, retrieval, persistence, and sharing of patient data. However, the way physicians interact with EHRs has not changed much. More specifically, support for temporal analysis of a large number of EHRs has been lacking. A number of information visualization techniques have been proposed to alleviate this problem. Unfortunately, due to their limited application to a single case study, the results are often difficult to generalize across medical scenarios. We present the usage data of Lifelines2,[22] our information visualization system, and user comments, both collected over eight different medical case studies. We generalize our experience into an information-seeking process model for multiple EHRs. Based on our analysis, we make recommendations to future information visualization designers for EHRs on design requirements and future research directions.
Keywords: design requriements; electronic health records; human-computer interaction (hci); Information Visualization

Visualizing Threaded Conversation Networks: Mining Message Boards and Email Lists for Actionable Insights - Hansen,Derek; Shneiderman, Ben; Smith,Marc (Active Media TechnologyActive Media Technology, 2010)
Analyzing complex online relationships is a difficult job, but new information visualization tools are enabling a wider range of users to make actionable insights from the growing volume of online data. This paper describes the challenges and methods for conducting analyses of threaded conversations such as found in enterprise message boards, email lists, and forums. After defining threaded conversation, we characterize the types of networks that can be extracted from them. We then provide 3 mini case studies to illustrate how actionable insights for community managers can be gained by applying the network analysis metrics and visualizations available in the free, open source NodeXL tool, which is a powerful, yet easy-to-use tool embedded in Excel 2007/2010.

WATTR: a method for self-powered wireless sensing of water activity in the home - Campbell,Tim; Larson,Eric; Cohn,Gabe; Jon Froehlich; Alcaide,Ramses; Patel,Shwetak N. (Proceedings of the 12th ACM international conference on Ubiquitous computing, 2010)
Keywords: power harvesting; sensing; water conservation

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

Why Did the Person Cross the Road (There)? Scene Understanding Using Probabilistic Logic Models and Common Sense Reasoning - Kembhavi,Aniruddha; Tom Yeh; Davis, Larry S. (Computer Vision – ECCV 2010, 2010)
We develop a video understanding system for scene elements, such as bus stops, crosswalks, and intersections, that are characterized more by qualitative activities and geometry than by intrinsic appearance. The domain models for scene elements are not learned from a corpus of video, but instead, naturally elicited by humans, and represented as probabilistic logic rules within a Markov Logic Network framework. Human elicited models, however, represent object interactions as they occur in the 3D world rather than describing their appearance projection in some specific 2D image plane. We bridge this gap by recovering qualitative scene geometry to analyze object interactions in the 3D world and then reasoning about scene geometry, occlusions and common sense domain knowledge using a set of meta-rules. The effectiveness of this approach is demonstrated on a set of videos of public spaces.

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

Advancing User-Centered Evaluation of Visual Analytic Environments Through Contests - Costello,Loura; Grinstein,Georges; Plaisant, Catherine; Scholtz,Jean (Information VisualizationInformation Visualization, 2009)
In this paper, the authors describe the Visual Analytics Science and Technology (VAST) Symposium contests run in 2006 and 2007 and the VAST 2008 and 2009 challenges. These contests were designed to provide researchers with a better understanding of the tasks and data that face potential end users. Access to these end users is limited because of time constraints and the classified nature of the tasks and data. In that respect, the contests serve as an intermediary, with the metrics and feedback serving as measures of utility to the end users. The authors summarize the lessons learned and the future directions for VAST Challenges.
Keywords: metrics; synthetic data; user-centered evaluation; visual analytics

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

Algorithms for generating multi-stage molding plans for articulated assemblies - Priyadarshi,Alok K.; Gupta, Satyandra K. (Robotics and Computer-Integrated Manufacturing, 2009)
Multi-stage molding is capable of producing better-quality articulated products at a lower cost. During the multi-stage molding process, assembly operations are performed along with the molding operations. Hence, it gives rise to a new type of planning problem. It is difficult to perform the planning manually because it involves evaluating large number of combinations and solving complex geometric reasoning problems. This paper investigates the problem of generating multi-stage molding plans for articulated assemblies. We present a planning framework that allows us to utilize constraints from experimentally proven molding plans. As a part of the planning problem, we determine the molding sequence and intermediate assembly configurations. We present algorithms for all the steps in the planning problem and characterize their computational complexities. Finally, we illustrate our approach with representative examples.
Keywords: In-mold assembly; mold design; Process planning

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

Arabic Cross-Document Coreference Resolution - Sayeed,A.; Elsayed,T.; Garera,N.; Alexander,D.; Xu,T.; Oard, Douglas; Yarowsky,D.; Piatko,C. (Proceedings of the ACL-IJCNLP 2009 Conference Short Papers$}$, 2009)

ARDB-Antibiotic Resistance Genes Database - Liu,B.; Pop, Mihai (Nucleic Acids Research, 2009)
The treatment of infections is increasingly compromised by the ability of bacteria to develop resistance to antibiotics through mutations or through the acquisition of resistance genes. Antibiotic resistance genes also have the potential to be used for bio-terror purposes through genetically modified organisms. In order to facilitate the identification and characterization of these genes, we have created a manually curated database—the Antibiotic Resistance Genes Database (ARDB)—unifying most of the publicly available information on antibiotic resistance. Each gene and resistance type is annotated with rich information, including resistance profile, mechanism of action, ontology, COG and CDD annotations, as well as external links to sequence and protein databases. Our database also supports sequence similarity searches and implements an initial version of a tool for characterizing common mutations that confer antibiotic resistance. The information we provide can be used as compendium of antibiotic resistance factors as well as to identify the resistance genes of newly sequenced genes, genomes, or metagenomes. Currently, ARDB contains resistance information for 13 293 genes, 377 types, 257 antibiotics, 632 genomes, 933 species and 124 genera. ARDB is available at http://ardb.cbcb.umd.edu/.

Block-diagonal preconditioning for spectral stochastic finite-element systems - Powell, C. E; Elman, Howard (IMA Journal of Numerical Analysis, 2009)

Collusion-free multiparty computation in the mediated model - Alwen,J.; Katz, Jonathan; Lindell,Y.; Persiano,G.; Shelat,A.; Visconti,I. (Advances in Cryptology-CRYPTO 2009, 2009)
Collusion-free protocols prevent subliminal communication (i.e., covert channels) between parties running the protocol. In the standard communication model, if one-way functions exist, then protocols satisfying any reasonable degree of privacy cannot be collusion-free. To circumvent this impossibility, Alwen, shelat and Visconti (CRYPTO 2008) recently suggested the mediated model where all communication passes through a mediator. The goal is to design protocols where collusion-freeness is guaranteed as long as the mediator is honest, while standard security guarantees hold if the mediator is dishonest. In this model, they gave constructions of collusion-free protocols for commitments and zero-knowledge proofs in the two-party setting.We strengthen the definition of Alwen et al., and resolve the main open questions in this area by showing a collusion-free protocol (in the mediated model) for computing any multi-party functionality.

Common effect of antipsychotics on the biosynthesis and regulation of fatty acids and cholesterol supports a key role of lipid homeostasis in schizophrenia - Polymeropoulos,Mihael H.; Licamele,Louis; Volpi,Simona; Mack,Kendra; Mitkus,Shruti N.; Carstea,Eugene D.; Getoor, Lise; Thompson,Andrew; Lavedan,Christian (Schizophrenia Research, 2009)
For decades, the dopamine hypothesis has gained the most attention in an attempt to explain the origin and the symptoms of schizophrenia. While this hypothesis offers an explanation for the relationship between psychotic symptoms and dopamine kinetics, it does not provide a direct explanation of the etiology of schizophrenia which remains poorly understood. Consequently, current antipsychotics that target neurotransmitter receptors, have limited and inconsistent efficacy. To gain insights into the mechanism of action of these drugs, we studied the expression profile of 12,490 human genes in a cell line treated with 18 antipsychotics, and compared it to that of a library of 448 other compounds used in a variety of disorders. Analysis reveals a common effect of antipsychotics on the biosynthesis and regulation of fatty acids and cholesterol, which is discussed in the context of a lipid hypothesis where alterations in lipid homeostasis might underlie the pathogenesis of schizophrenia. This finding may help research aimed at the development of novel treatments for this devastating disease.
Keywords: Antipsychotic action; Gene expression; Lipid homeostasis; Pathogenesis

Complete Genome Sequence of Aggregatibacter (Haemophilus) Aphrophilus NJ8700 - Di Bonaventura,Maria Pia; DeSalle,Rob; Pop, Mihai; Nagarajan,Niranjan; Figurski,David H; Fine,Daniel H; Kaplan,Jeffrey B; Planet,Paul J (Journal of BacteriologyJ. Bacteriol., 2009)
We report the finished and annotated genome sequence of Aggregatibacter aphrophilus strain NJ8700, a strain isolated from the oral flora of a healthy individual, and discuss characteristics that may affect its dual roles in human health and disease. This strain has a rough appearance, and its genome contains genes encoding a type VI secretion system and several factors that may participate in host colonization.

A Comprehensive Evaluation Framework and a Comparative Study for Human Detectors - Hussein,M.; Porikli, F.; Davis, Larry S. (Intelligent Transportation Systems, IEEE Transactions on, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.
Keywords: classification; infrared; classifier; comprehensive; curve; INRIA; dataset; average; DET; DETECTION; detection; detector; image; error; Evaluation; framework; cropped; image; image; imaging; object; log; miss; person; rate; cascade; rate; feature; rate; multisize; resize; human; resize; miss; scanning; near-infrared; sliding-window; tradeoff; false-alarm; window; detection

Compressed sensing for Synthetic Aperture Radar imaging - Patel, Vishal M.; Easley,G. R; Healy,D. M; Chellapa, Rama (2009 16th IEEE International Conference on Image Processing (ICIP), 2009)
In this paper, we introduce a new Synthetic Aperture Radar (SAR) imaging modality that provides a high resolution map of the spatial distribution of targets and terrain based on a significant reduction in the number of transmitted and/or received electromagnetic waveforms. This new imaging scheme, which requires no new hardware components, allows the aperture to be compressed and presents many important applications and advantages among which include resolving ambiguities, strong resistance to countermeasures and interception, and reduced on-board storage constraints.
Keywords: Compressed sensing; High-resolution imaging; Image coding; image resolution; Optical imaging; Radar antennas; radar imaging; Radar polarimetry; Reflectivity; SAR; spatial distribution; synthetic aperture radar; synthetic aperture radar imaging

Computational linguistics for metadata building (CLiMB): using text mining for the automatic identification, categorization, and disambiguation of subject terms for image metadata - Klavans,J. L; Sheffield,C.; Abels,E.; Jimmy Lin; Passonneau,R.; Sidhu,T.; Soergel,D. (Multimedia Tools and Applications, 2009)
In this paper, we present a system using computational linguistic techniques to extract metadata for image access. We discuss the implementation, functionality and evaluation of an image catalogers’ toolkit, developed in the Computational Linguistics for Metadata Building (CLiMB) research project. We have tested components of the system, including phrase finding for the art and architecture domain, functional semantic labeling using machine learning, and disambiguation of terms in domain-specific text vis a vis a rich thesaurus of subject terms, geographic and artist names. We present specific results on disambiguation techniques and on the nature of the ambiguity problem given the thesaurus, resources, and domain-specific text resource, with a comparison of domain-general resources and text. Our primary user group for evaluation has been the cataloger expert with specific expertise in the fields of painting, sculpture, and vernacular and landscape architecture.

Computer Help at Home: Methods and Motivations for Informal Technical Support - Poole, Erika Shehan; Marshini Chetty; Morgan, Tom; Grinter, Rebecca E.; Edwards, W. Keith (SIGCHI '09, 2009)
Prior research suggests that people may ask their family and friends for computer help. But what influences whether and how a "helper" will provide help? To answer this question, we conducted a qualitative investigation of people who participated in computer support activities with family and friends in the past year. We describe how factors including maintenance of one's personal identity as a computer expert and accountability to one's social network determine who receives help and the quality of help provided. We also discuss the complex, fractured relationship between the numerous stakeholders involved in the upkeep of home computing infrastructures. Based on our findings, we provide implications for the design of systems to support informal help-giving in residential settings.
Keywords: help-giving; help-seeking; Home computing; identity management; social networks

Computing and visualizing a graph-based decomposition for non-manifold shapes - De Floriani, Leila; Panozzo,D.; Hui,A. (Graph-Based Representations in Pattern Recognition, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an effective support to modeling, analyzing and understanding non-manifold shapes.

A cost-effective lexical acquisition process for large-scale thesaurus translation - Jimmy Lin; Murray,G. C; Dorr, Bonnie J; Hajič,J.; Pecina,P. (Language resources and evaluation, 2009)
Thesauri and controlled vocabularies facilitate access to digital collections by explicitly representing the underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most thesauri precludes fully-automatic translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations to construct domain-specific lexical resources. This process is illustrated on a thesaurus of 56,000 concepts used to catalog a large archive of oral histories. We elicited human translations on a small subset of concepts, induced a probabilistic phrase dictionary from these translations, and used the resulting resource to automatically translate the rest of the thesaurus. Two separate evaluations demonstrate the acceptability of the automatic translations and the cost-effectiveness of our approach.

A dimension-independent library for building and manipulating multiresolution triangulations - De Floriani, Leila; Magillo,P.; Puppo,E. (Department of Computer Science and Information Science, University of Genoa, 2009)
A Multi-Triangulation (MT) is a general multiresolution model for representing k-dimensional geometricobjects through simplicial complexes. An MT integrates several alternative representations of an object, and provides simple methods for handling representations at variable resolution efficiently , thus offering a basis for the development of applications that need to manage the level-of-detail of complex objects. In this paper, we present an object-oriented library that provides an open-ended tool for building and manipulating object representations based on the MT.

Distributed Strategies for Channel Allocation and Scheduling in Software-Defined Radio Networks - Han,Bo; Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2009, 2009)
Equipping wireless nodes with multiple radios can significantly increase the capacity of wireless networks, by making these radios simultaneously transmit over multiple non-overlapping channels. However, due to the limited number of radios and available orthogonal channels, designing efficient channel assignment and scheduling algorithms in such networks is a major challenge. In this paper, we present provably-good distributed algorithms for simultaneous channel allocation of individual links and packet-scheduling, in software-defined radio (SDR) wireless networks. Our distributed algorithms are very simple to implement, and do not require any coordination even among neighboring nodes. A novel access hash function or random oracle methodology is one of the key drivers of our results. With this access hash function, each radio can know the transmitters' decisions for links in its interference set for each time slot without introducing any extra communication overhead between them. Further, by utilizing the inductive-scheduling technique, each radio can also backoff appropriately to avoid collisions. Extensive simulations demonstrate that our bounds are valid in practice.
Keywords: access hash function; Channel allocation; channel assignment algorithm; channel capacity; collision avoidance; Computer science; cryptography; distributed algorithm; distributed algorithms; Educational institutions; inductive-scheduling technique; Interference; interference set; packet scheduling algorithm; Peer to peer computing; Radio network; radio networks; radiofrequency interference; random oracle methodology; scheduling; Scheduling algorithm; simultaneous channel allocation; software radio; software-defined radio wireless network capacity; telecommunication congestion control; telecommunication security; Throughput; wireless channels; Wireless networks

Dynamic Provable Data Possession - Erway, Chris; Küp\ccü, Alptekin; Charalampos Papamanthou; Tamassia, Roberto (CCS '09 Proceedings of the 16th ACM Conference on Computer and Communications Security, 2009)
We consider the problem of efficiently proving the integrity of data stored at untrusted servers. In the provable data possession (PDP) model, the client preprocesses the data and then sends it to an untrusted server for storage, while keeping a small amount of meta-data. The client later asks the server to prove that the stored data has not been tampered with or deleted (without downloading the actual data). However, the original PDP scheme applies only to static (or append-only) files. We present a definitional framework and efficient constructions for dynamic provable data possession (DPDP), which extends the PDP model to support provable updates to stored data. We use a new version of authenticated dictionaries based on rank information. The price of dynamic updates is a performance change from O(1) to O(logn) (or O(nεlog n), for a file consisting of n blocks, while maintaining the same (or better, respectively) probability of misbehavior detection. Our experiments show that this slowdown is very low in practice (e.g. 415KB proof size and 30ms computational overhead for a 1GB file). We also show how to apply our DPDP scheme to outsourced file systems and version control systems (e.g. CVS).
Keywords: authenticated data structures; Authentication; integrity checking; outsourced storage; proof of retrievability; provable data possession; skip list

Efficient Robust Private Set Intersection - Dana Dachman-Soled; Malkin, Tal; Raykova, Mariana; Yung, Moti (Applied Cryptography and Network Security, 2009)
Computing Set Intersection privately and efficiently between two mutually mistrusting parties is an important basic procedure in the area of private data mining. Assuring robustness, namely, coping with potentially arbitrarily misbehaving (i.e., malicious) parties, while retaining protocol efficiency (rather than employing costly generic techniques) is an open problem. In this work the first solution to this problem is presented.
Keywords: Coding and Information Theory; Computer Communication Networks; Cryptographic protocols; Data Encryption; Data Structures, Cryptology and Information Theory; Information Systems Applications (incl.Internet); Privacy Preserving Data Mining; Secure Two-party Computation; Set Intersection; Systems and Data Security

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

Enhancing sparsity using gradients for compressive sensing - Patel, Vishal M.; Easley,G. R; Chellapa, Rama; Healy,D. M (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
In this paper, we propose a reconstruction method that recovers images assumed to have a sparse representation in a gradient domain by using partial measurement samples that are collected in the Fourier domain. A key improvement of this technique is that it makes use of a robust generalized Poisson solver that greatly aids in achieving a significantly improved performance over similar proposed methods. Experiments provided also demonstrate that this new technique is more flexible to work with either random or restricted sampling scenarios better than its competitors.
Keywords: analysis; gradient; domain; compressive; domain; image; Fourier; generalized; measurement; methods; methods; image; Poisson; reconstruction; image; reconstruction; partial; representation; Fourier; representation; sampling; samples; robust; scenarios; sparse; sensing; enhancing; solver; sampling; sparsity; gradient

Evidence for Bidentate Substrate Binding as the Basis for the K48 Linkage Specificity of Otubain 1 - Wang,Tao; Yin,Luming; Cooper,Eric M.; Lai,Ming-Yih; Dickey,Seth; Pickart,Cecile M.; Fushman, David; Wilkinson,Keith D.; Cohen,Robert E.; Wolberger,Cynthia (Journal of Molecular Biology, 2009)
Otubain 1 belongs to the ovarian tumor (OTU) domain class of cysteine protease deubiquitinating enzymes. We show here that human otubain 1 (hOtu1) is highly linkage-specific, cleaving Lys48 (K48)-linked polyubiquitin but not K63-, K29-, K6-, or K11-linked polyubiquitin, or linear α-linked polyubiquitin. Cleavage is not limited to either end of a polyubiquitin chain, and both free and substrate-linked polyubiquitin are disassembled. Intriguingly, cleavage of K48-diubiquitin by hOtu1 can be inhibited by diubiquitins of various linkage types, as well as by monoubiquitin. NMR studies and activity assays suggest that both the proximal and distal units of K48-diubiquitin bind to hOtu1. Reaction of Cys23 with ubiquitin-vinylsulfone identified a ubiquitin binding site that is distinct from the active site, which includes Cys91. Occupancy of the active site is needed to enable tight binding to the second site. We propose that distinct binding sites for the ubiquitins on either side of the scissile bond allow hOtu1 to discriminate among different isopeptide linkages in polyubiquitin substrates. Bidentate binding may be a general strategy used to achieve linkage-specific deubiquitination.
Keywords: deubiquitination; isopeptide; linkage specificity; otubain; polyubiquitin

Evidence for Coregulation of Myocardial Gene Expression by MEF2 and NFAT in Human Heart Failure / CLINICAL PERSPECTIVE - Putt,Mary E.; Hannenhalli, Sridhar; Lu,Yun; Haines,Philip; Chandrupatla,Hareesh R.; Morrisey,Edward E.; Margulies,Kenneth B.; Cappola,Thomas P. (Circulation: Cardiovascular Genetics, 2009)
Background— Pathological stresses induce heart failure in animal models through activation of multiple cardiac transcription factors (TFs) working cooperatively. However, interactions among TFs in human heart failure are less understood. Here, we use genomic data to examine the evidence that 5 candidate TF families coregulate gene expression in human heart failure.Methods and Results— RNA isolates from failing (n=86) and nonfailing (n=16) human hearts were hybridized with Affymetrix HU133A arrays. For each gene on the array, we determined conserved MEF2, NFAT, NKX , GATA , and FOX binding motifs within the −1-kb promoter region using human-murine sequence alignments and the TRANSFAC database. Across 9076 genes expressed in the heart, TF-binding motifs tended to cluster together in nonrandom patterns within promoters of specific genes (P values ranging from 10−2 to 10−21), suggesting coregulation. We then modeled differential expression as a function of TF combinations present in promoter regions. Several combinations predicted increased odds of differential expression in the failing heart, with the highest odds ratios noted for genes containing both MEF2 and NFAT binding motifs together in the same promoter region (peak odds ratio, 3.47; P=0.005).Conclusions— These findings provide genomic evidence for coregulation of myocardial gene expression by MEF2 and NFAT in human heart failure. In doing so, they extend the paradigm of combinatorial regulation of gene expression to the human heart and identify new target genes for mechanistic study. More broadly, we demonstrate how integrating diverse sources of genomic data yields novel insight into human cardiovascular disorders.

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

Finding Biologically Accurate Clusterings in Hierarchical Decompositions Using the Variation of Information - Navlakha,S.; White,J. R.; Nagarajan,N.; Pop, Mihai; Kingsford, Carl (Lecture Notes in Computer Science: Research in Computational Molecular Biology, 2009)

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

Gene Profiling of Human Adipose Tissue During Evoked Inflammation In Vivo - Shah,Rachana; Lu,Yun; Hinkle,Christine C; McGillicuddy,Fiona C; Kim,Roy; Hannenhalli, Sridhar; Cappola,Thomas P.; Heffron,Sean; Wang,XingMei; Mehta,Nehal N; Putt,Mary; Reilly,Muredach P (DiabetesDiabetes, 2009)
OBJECTIVE Adipose inflammation plays a central role in obesity-related metabolic and cardiovascular complications. However, few human adipose-secreted proteins are known to mediate these processes. We hypothesized that microarray mRNA profiling of human adipose during evoked inflammation could identify novel adipocytokines.RESEARCH DESIGN AND METHODS Healthy human volunteers (n = 14) were treated with intravenous endotoxin (3 ng/kg lipopolysaccharide [LPS]) and underwent subcutaneous adipose biopsies before and after LPS. On Affymetrix U133Plus 2.0 arrays, adipose mRNAs modulated >1.5-fold (with P < 0.00001) were selected. SignalP 3.0 and SecretomeP 2.0 identified genes predicted to encode secreted proteins. Of these, 86 candidates were chosen for validation in adipose from an independent human endotoxemia protocol (N = 7, with 0.6 ng/kg LPS) and for exploration of cellular origin in primary human adipocytes and macrophages in vitro. RESULTS Microarray identified 776 adipose genes modulated by LPS; 298 were predicted to be secreted. Of detectable prioritized genes, 82 of 85 (96% [95% CI 90–99]) were upregulated (fold changes >1.0) during the lower-dose (LPS 0.6 ng/kg) validation study and 51 of 85 (59% [49–70]) were induced greater than 1.5-fold. Treatment of primary adipocytes with LPS and macrophage polarization to M1 proinflammatory phenotype increased expression by 1.5-fold for 58 and 73% of detectable genes, respectively. CONCLUSIONS We demonstrate that evoked inflammation of human adipose in vivo modulated expression of multiple genes likely secreted by adipocytes and monocytes. These included established adipocytokines and chemokines implicated in recruitment and activation of lymphocytes, adhesion molecules, antioxidants, and several novel genes with unknown function. Such candidates may represent biomarkers and therapeutic targets for obesity-related complications.

Genome Assembly Reborn: Recent Computational Challenges - Pop, Mihai (Briefings in Bioinformatics, 2009)
Research into genome assembly algorithms has experienced a resurgence due to new challenges created by the development of next generation sequencing technologies. Several genome assemblers have been published in recent years specifically targeted at the new sequence data; however, the ever-changing technological landscape leads to the need for continued research. In addition, the low cost of next generation sequencing data has led to an increased use of sequencing in new settings. For example, the new field of metagenomics relies on large-scale sequencing of entire microbial communities instead of isolate genomes, leading to new computational challenges. In this article, we outline the major algorithmic approaches for genome assembly and describe recent developments in this domain.
Keywords: genome assembly; genome sequencing; next generation sequencing technologies

Graph Drawing for Security Visualization - Tamassia, Roberto; Palazzi, Bernardo; Charalampos Papamanthou (Graph Drawing, 2009)
With the number of devices connected to the internet growing rapidly and software systems being increasingly deployed on the web, security and privacy have become crucial properties for networks and applications. Due the complexity and subtlety of cryptographic methods and protocols, software architects and developers often fail to incorporate security principles in their designs and implementations. Also, most users have minimal understanding of security threats. While several tools for developers, system administrators and security analysts are available, these tools typically provide information in the form of textual logs or tables, which are cumbersome to analyze. Thus, in recent years, the field of security visualization has emerged to provide novel ways to display security-related information so that it is easier to understand. In this work, we give a preliminary survey of approaches to the visualization of computer security concepts that use graph drawing techniques.
Keywords: Algorithm Analysis and Problem Complexity; Computer Graphics; Data structures; Discrete Mathematics in Computer Science

HydroSense: infrastructure-mediated single-point sensing of whole-home water activity - Jon Froehlich; Larson,E.; Campbell,T.; Haggerty,C.; Fogarty,J.; Patel,S.N. (Proceedings of the 11th international conference on Ubiquitous computing, September, 2009)

Incremental covering array failure characterization in large configuration spaces - Fouché,S.; Cohen,M. B; Porter, Adam (Proceedings of the eighteenth international symposium on Software testing and analysis, 2009)

Index interactions in physical design tuning: modeling, analysis, and applications - Schnaitter,Karl; Polyzotis,Neoklis; Getoor, Lise (Proceedings of the VLDB Endowment, 2009)
One of the key tasks of a database administrator is to optimize the set of materialized indices with respect to the current workload. To aid administrators in this challenging task, commercial DBMSs provide advisors that recommend a set of indices based on a sample workload. It is left for the administrator to decide which of the recommended indices to materialize and when. This decision requires some knowledge of how the indices benefit the workload, which may be difficult to understand if there are any dependencies or interactions among indices. Unfortunately, advisors do not provide this crucial information as part of the recommendation. Motivated by this shortcoming, we propose a framework and associated tools that can help an administrator understand the interactions within the recommended set of indices. We formalize the notion of index interactions and develop a novel algorithm to identify the interaction relationships that exist within a set of indices. We present experimental results with a prototype implementation over IBM DB2 that demonstrate the efficiency of our approach. We also describe two new database tuning tools that utilize information about index interactions. The first tool visualizes interactions based on a partitioning of the index-set into non-interacting subsets, and the second tool computes a schedule that materializes the indices over several maintenance windows with maximal overall benefit. In both cases, we provide strong analytical results showing that index interactions can enable enhanced functionality.

Inexact Local Alignment Search over Suffix Arrays - Ghodsi,M.; Pop, Mihai (IEEE International Conference on Bioinformatics and Biomedicine, 2009. BIBM '09, 2009)
We describe an algorithm for finding approximate seeds for DNA homology searches. In contrast to previous algorithms that use exact or spaced seeds, our approximate seeds may contain insertions and deletions. We present a generalized heuristic for finding such seeds efficiently and prove that the heuristic does not affect sensitivity. We show how to adapt this algorithm to work over the memory efficient suffix array with provably minimal overhead in running time. We demonstrate the effectiveness of our algorithm on two tasks: whole genome alignment of bacteria and alignment of the DNA sequences of 177 genes that are orthologous in human and mouse. We show our algorithm achieves better sensitivity and uses less memory than other commonly used local alignment tools.
Keywords: bacteria; Bioinformatics; biology computing; Computational Biology; Costs; DNA; DNA homology searches; DNA sequences; Educational institutions; generalized heuristic; genes; Genetics; genome alignment; Genomics; human; inexact local alignment search; inexact seeds; local alignment; local alignment tools; memory efficient suffix array; microorganisms; molecular biophysics; mouse; Organisms; Sensitivity and Specificity; sequences; suffix array; USA Councils

Inexact Local Alignment Search over Suffix Arrays - Ghodsi,M.; Pop, Mihai (2009)

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

Integrating Statistics and Visualization for Exploratory Power: From Long-Term Case Studies to Design Guidelines - Perer,A.; Shneiderman, Ben (IEEE Computer Graphics and Applications, 2009)
Evaluating visual-analytics systems is challenging because laboratory-based controlled experiments might not effectively represent analytical tasks. One such system, Social Action, integrates statistics and visualization in an interactive exploratory tool for social network analysis. This article describes results from long-term case studies with domain experts and extends established design goals for information visualization.
Keywords: case studies; Control systems; Data analysis; data mining; data visualisation; Data visualization; data-mining; design guidelines; Employment; exploration; Filters; Guidelines; Information Visualization; insights; laboratory-based controlled experiments; Performance analysis; social network analysis; Social network services; social networking (online); social networks; SocialAction; statistical analysis; Statistics; visual analytics; visual-analytics systems; Visualization

Inverse halftoning using a shearlet representation - Easley,G. R; Patel, Vishal M.; Healy Jr,D.M. (Proceedings of SPIE, 2009)

Maintaining nets and net trees under incremental motion - Cho,M.; Mount, Dave; Park,E. (Algorithms and Computation, 2009)
The problem of maintaining geometric structures for points in motion has been well studied over the years. Much theoretical work to date has been based on the assumption that point motion is continuous and predictable, but in practice, motion is typically presented incrementally in discrete time steps and may not be predictable. We consider the problem of maintaining a data structure for a set of points undergoing such incremental motion. We present a simple online model in which two agents cooperate to maintain the structure. One defines the data structure and provides a collection of certificates, which guarantee the structure’s correctness. The other checks that the motion over time satisfies these certificates and notifies the first agent of any violations.We present efficient online algorithms for maintaining both nets and net trees for a point set undergoing incremental motion in a space of constant dimension. We analyze our algorithms’ efficiencies by bounding their competitive ratios relative to an optimal algorithm. We prove a constant factor competitive ratio for maintaining a slack form of nets, and our competitive ratio for net trees is proportional to the square of the tree’s height.

Modeling and visualization of human activities for multicamera networks - Sankaranarayanan,A. C; Patro,R.; Turaga,P.; Varshney, Amitabh; Chellapa, Rama (EURASIP Journal on Image and Video Processing, 2009)

Network-aware forward caching - Erman,Jeffrey; Gerber,Alexandre; Hajiaghayi, Mohammad T.; Pei,Dan; Spatscheck,Oliver (Proceedings of the 18th international conference on World wide web, 2009)
This paper proposes and evaluates a Network Aware Forward Caching approach for determining the optimal deployment strategy of forward caches to a network. A key advantage of this approach is that we can reduce the network costs associated with forward caching to maximize the benefit obtained from their deployment. We show in our simulation that a 37% increase to net benefits could be achieved over the standard method of full cache deployment to cache all POPs traffic. In addition, we show that this maximal point occurs when only 68% of the total traffic is cached. Another contribution of this paper is the analysis we use to motivate and evaluate this problem. We characterize the Internet traffic of 100K subscribers of a US residential broadband provider. We use both layer 4 and layer 7 analysis to investigate the traffic volumes of the flows as well as study the general characteristics of the applications used. We show that HTTP is a dominant protocol and account for 68% of the total downstream traffic and that 34% of that traffic is multimedia. In addition, we show that multimedia content using HTTP exhibits a 83% annualized growth rate and other HTTP traffic has a 53% growth rate versus the 26% over all annual growth rate of broadband traffic. This shows that HTTP traffic will become ever more dominent and increase the potential caching opportunities. Furthermore, we characterize the core backbone traffic of this broadband provider to measure the distance travelled by content and traffic. We find that CDN traffic is much more efficient than P2P content and that there is large skew in the Air Miles between POP in a typical network. Our findings show that there are many opportunties in broadband provider networks to optimize how traffic is delivered and cached.
Keywords: caching; Web

Object detection via boosted deformable features - Hussein,M.; Porikli, F.; Davis, Larry S. (Image Processing (ICIP), 2009 16th IEEE International Conference on, 2009)
It is a common practice to model an object for detection tasks as a boosted ensemble of many models built on features of the object. In this context, features are defined as subregions with fixed relative locations and extents with respect to the object's image window. We introduce using deformable features with boosted ensembles. A deformable features adapts its location depending on the visual evidence in order to match the corresponding physical feature. Therefore, deformable features can better handle deformable objects. We empirically show that boosted ensembles of deformable features perform significantly better than boosted ensembles of fixed features for human detection.
Keywords: boosted; detection; object; detection; statistics; detection; visual; ensembles; deformable; evidence; feature; extraction; object; features; human

Parametric Complexity of Sequence Assembly: Theory and Applications to Next Generation Sequencing - Nagarajan,Niranjan; Pop, Mihai (Journal of Computational Biology, 2009)
In recent years, a flurry of new DNA sequencing technologies have altered the landscape of genomics, providing a vast amount of sequence information at a fraction of the costs that were previously feasible. The task of assembling these sequences into a genome has, however, still remained an algorithmic challenge that is in practice answered by heuristic solutions. In order to design better assembly algorithms and exploit the characteristics of sequence data from new technologies, we need an improved understanding of the parametric complexity of the assembly problem. In this article, we provide a first theoretical study in this direction, exploring the connections between repeat complexity, read lengths, overlap lengths and coverage in determining the “hard” instances of the assembly problem. Our work suggests at least two ways in which existing assemblers can be extended in a rigorous fashion, in addition to delineating directions for future theoretical investigations.

Passive aggressive measurement with MGRP - Papageorge,Pavlos; McCann,Justin; Hicks, Michael W. (SIGCOMM Comput. Commun. Rev., 2009)
We present the Measurement Manager Protocol (MGRP), an in-kernel service that schedules and transmits probes on behalf of active measurement tools. Unlike prior measurement services, MGRP transparently piggybacks application packets inside the often significant amounts of empty padding contained in typical probes. Using MGRP thus combines the modularity, flexibility, and accuracy of standalone active measurement tools with the lower overhead of passive measurement techniques. Microbenchmark experiments show that the resulting bandwidth savings makes it possible to measure the network accurately, but faster and more aggressively than without piggybacking, and with few ill effects to piggybacked application or competing traffic. When using MGRP to schedule measurements on behalf of MediaNet, an overlay service that adaptively schedules media streams, we show MediaNet can achieve significantly higher streaming rates under the same network conditions.
Keywords: active; available bandwidth; kernel module; passive; piggybacking; probing; streaming; transport protocol

PERCEPTION AND NAVIGATION FOR AUTONOMOUS VEHICLES - Hussein,M.; Porikli, F.; Davis, Larry S. (IEEE Transactions on intelligent transportation systems, 2009)
We introduce a framework for evaluating human detectors that considers the practical application of a detector on a full image using multisize sliding-window scanning. We produce detection error tradeoff (DET) curves relating the miss detection rate and the false-alarm rate computed by deploying the detector on cropped windows and whole images, using, in the latter, either image resize or feature resize. Plots for cascade classifiers are generated based on confidence scores instead of on variation of the number of layers. To assess a method's overall performance on a given test, we use the average log miss rate (ALMR) as an aggregate performance score. To analyze the significance of the obtained results, we conduct 10-fold cross-validation experiments. We applied our evaluation framework to two state-of-the-art cascade-based detectors on the standard INRIA Person dataset and a local dataset of near-infrared images. We used our evaluation framework to study the differences between the two detectors on the two datasets with different evaluation methods. Our results show the utility of our framework. They also suggest that the descriptors used to represent features and the training window size are more important in predicting the detection performance than the nature of the imaging process, and that the choice between resizing images or features can have serious consequences.

Planning for Interactions among Autonomous Agents - Au,Tsz-Chiu; Kuter,Ugur; Nau, Dana S. (Programming Multi-Agent Systems, 2009)
AI planning research has traditionally focused on offline pl- anning for static single-agent environments. In environments where an agent needs to plan its interactions with other autonomous agents, planning is much more complicated, because the actions of the other agents can induce a combinatorial explosion in the number of contingencies that the planner will need to consider. This paper discusses several ways to alleviate the combinatorial explosion, and illustrates their use in several different kinds of multi-agent planning domains.
Keywords: Computer science

PrDB: Managing Large-Scale Correlated Probabilistic Databases (Abstract) - Deshpande, Amol (Scalable Uncertainty ManagementScalable Uncertainty Management, 2009)
Increasing numbers of real-world application domains are generating data that is inherently noisy, incomplete, and probabilistic in nature. Statistical inference and probabilistic modeling often introduce another layer of uncertainty on top of that. Examples of such data include measurement data collected by sensor networks, observation data in the context of social networks, scientific and biomedical data, and data collected by various online cyber-sources. Over the last few years, numerous approaches have been proposed, and several systems built, to integrate uncertainty into databases. However, these approaches typically make simplistic and restrictive assumptions concerning the types of uncertainties that can be represented. Most importantly, they often make highly restrictive independence assumptions, and cannot easily model rich correlations among the tuples or attribute values. Furthermore, they typically lack support for specifying uncertainties at different levels of abstractions, needed to handle large-scale uncertain datasets.

Prioritizing component compatibility tests via user preferences - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Software Maintenance, 2009. ICSM 2009. IEEE International Conference on, 2009)
Many software systems rely on third-party components during their build process. Because the components are constantly evolving, quality assurance demands that developers perform compatibility testing to ensure that their software systems build correctly over all deployable combinations of component versions, also called configurations. However, large software systems can have many configurations, and compatibility testing is often time and resource constrained. We present a prioritization mechanism that enhances compatibility testing by examining the ldquomost importantrdquo configurations first, while distributing the work over a cluster of computers. We evaluate our new approach on two large scientific middleware systems and examine tradeoffs between the new prioritization approach and a previously developed lowest-cost-configuration-first approach.
Keywords: compatibility testing prioritization; component configurations; computer clusters; Middleware; Middleware systems; object-oriented programming; program testing; software engineering; Software systems; third-party components; user preferences

Prioritizing Vulnerability Remediation by Determining Attacker-Targeted Vulnerabilities - Michel Cukier; Panjwani,S. (Security Privacy, IEEE, 2009)
This article attempts to empirically analyze which vulnerabilities attackers tend to target in order to prioritize vulnerability remediation. This analysis focuses on the link between malicious connections and vulnerabilities, where each connection is considered malicious. Attacks requiring multiple connections are counted as multiple attacks. As the number of connections increases, so does the cost of recovering from the intrusion. The authors deployed four honey pots for four months, each running a different Windows service pack with its associated set of vulnerabilities. They then performed three empirical analyses to determine the relationship between the number of malicious connections and the total number of vulnerabilities, the number of malicious connections and the number of the vulnerabilities for different services, and the number of known successful attacks and the number of vulnerabilities for different services.
Keywords: attacker-targeted vulnerabilities; intrusion detection; malicious connections; security of data; vulnerability remediation; Windows service pack

Proceedings of the 1st ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data - Pei,Jian; Getoor, Lise; de Keijzer,Ander (ACM, 2009)
The importance of uncertain data is growing quickly in many essential applications such as environmental surveillance, mobile object tracking and data integration. Recently, storing, collecting, processing, and analyzing uncertain data has attracted increasing attention from both academia and industry. Analyzing and mining uncertain data needs collaboration and joint effort from multiple research communities including reasoning under uncertainty, uncertain databases and mining uncertain data. For example, statistics and probabilistic reasoning can provide support with models for representing uncertainty. The uncertain database community can provide methods for storing and managing uncertain data, while research in mining uncertain data can provide data analysis tasks and methods. It is important to build connections among those communities to tackle the overall problem of analyzing and mining uncertain data. There are many common challenges among the communities. One is to understand the different modeling assumptions made, and how they impact the methods, both in terms of accuracy and efficiency. Different researchers hold different assumptions and this is one of the major obstacles in the research of mining uncertain data. Another is the scalability of proposed management and analysis methods. Finally, to make analysis and mining useful and practical, we need real data sets for testing. Unfortunately, uncertain data sets are often hard to get. The goal of the First ACM SIGKDD Workshop on Knowledge Discovery from Uncertain Data (U'09) is to discuss in depth the challenges, opportunities and techniques on the topic of analyzing and mining uncertain data. The theme of this workshop is to make connections among the research areas of uncertain databases, probabilistic reasoning, and data mining, as well as to build bridges among the aspects of models, data, applications, novel mining tasks and effective solutions. By making connections among different communities, we aim at understanding each other in terms of scientific foundation as well as commonality and differences in research methodology. The workshop program is very stimulating and exciting. We are pleased to feature two invited talks by pioneers in mining uncertain data. Christopher Jermaine will give an invited talk titled "Managing and Mining Uncertain Data: What Might We Do Better?" Matthias Renz will address the topic "Querying and Mining Uncertain Data: Methods, Applications, and Challenges". Moreover, 8 accepted papers in 4 full presentations and 4 concise presentations will cover a bunch of interesting topics and on-going research projects about uncertain data mining.

Querying timestamped event sequences by exact search or similarity-based search: design and empirical evaluation - Wongsuphasawat,K.; Plaisant, Catherine; Shneiderman, Ben (Human-Computer Interaction Lab, University of Maryland, 2009)

The reader-to-leader framework: Motivating technology-mediated social participation - Preece,J.; Shneiderman, Ben (AIS Transactions on Human-Computer Interaction, 2009)
Billions of people participate in online social activities. Most users participate as readers of discussion boards, searchers of blogposts, or viewers of photos. A fraction of users become contributors of user-generated content by writing consumer product reviews, uploading travel photos, or expressing political opinions. Some users move beyond such individual efforts to become collaborators, forming tightly connected groups with lively discussions whose outcome might be a Wikipedia article or a carefully edited YouTube video. A small fraction of users becomes leaders, who participate in governance by setting and upholding policies, repairing vandalized materials, or mentoring novices. We analyze these activities and offer the Reader-to-Leader Framework with the goal of helping researchers, designers, and managers understand what motivates technology-mediated social participation. This will enable them to improve interface design and social support for their companies, government agencies, and non-governmental organizations. These improvements could reduce the number of failed projects, while accelerating the application of social media for national priorities such as healthcare, energy sustainability, emergency response, economic development, education, and more.

Scheduling on Unrelated Machines under Tree-Like Precedence Constraints - Anil Kumar,V.; Marathe,Madhav; Parthasarathy,Srinivasan; Srinivasan, Aravind (Algorithmica, 2009)
We present polylogarithmic approximations for the R | prec | C max and R | prec |∑ j w j C j problems, when the precedence constraints are “treelike”—i.e., when the undirected graph underlying the precedences is a forest. These are the first non-trivial generalizations of the job shop scheduling problem to scheduling with precedence constraints that are not just chains. These are also the first non-trivial results for the weighted completion time objective on unrelated machines with precedence constraints of any kind . We obtain improved bounds for the weighted completion time and flow time for the case of chains with restricted assignment—this generalizes the job shop problem to these objective functions. We use the same lower bound of “congestion + dilation”, as in other job shop scheduling approaches (e.g. Shmoys, Stein and Wein, SIAM J. Comput. 23, 617–632, 1994 ). The first step in our algorithm for the R | prec | C max problem with treelike precedences involves using the algorithm of Lenstra, Shmoys and Tardos to obtain a processor assignment with the congestion + dilation value within a constant factor of the optimal. We then show how to generalize the random-delays technique of Leighton, Maggs and Rao to the case of trees. For the special case of chains, we show a dependent rounding technique which leads to a bicriteria approximation algorithm for minimizing the flow time, a notoriously hard objective function.

Searching for SNPs with cloud computing - Langmead,Ben; Schatz,Michael C; Jimmy Lin; Pop, Mihai; Salzberg,Steven L. (Genome Biology, 2009)
As DNA sequencing outpaces improvements in computer speed, there is a critical need to accelerate tasks like alignment and SNP calling. Crossbow is a cloud-computing software tool that combines the aligner Bowtie and the SNP caller SOAPsnp. Executing in parallel using Hadoop, Crossbow analyzes data comprising 38-fold coverage of the human genome in three hours using a 320-CPU cluster rented from a cloud computing service for about $85. Crossbow is available from http://bowtie-bio.sourceforge.net/crossbow/.

Semantic-based segmentation and annotation of 3d models - Papaleo,L.; De Floriani, Leila (Image Analysis and Processing–ICIAP 2009, 2009)
3D objects have become widely available and used in different application domains. Thus, it is becoming fundamental to use, integrate and develop techniques for extracting and maintaining their embedded knowledge. These techniques should be encapsulated in portable and intelligent systems able to semantically annotate the 3D object models in order to improve their usability and indexing, especially in innovative web cooperative environments. Lately, we are moving in this direction, with the definition and development of data structures, methods and interfaces for structuring and semantically annotating 3D complex models (and scenes) - even changing in time - according to ontology-driven metadata and following ontology-driven processes. Here, we concentrate on the tools for segmenting manifold 3D models and on the underline structural representation that we build and manipulate. We also describe the first prototype of an annotation tool which allows a hierarchical semantic-driven tagging of the segmented model and provides an interface from which the user can inspect and browse the entire segmentation graph.

Sensing opportunities for personalized feedback technology to reduce consumption - Jon Froehlich; Everitt,K.; Fogarty,J.; Patel,S.; Landay,J. (Proc. CHI Workshop on Defining the Role of HCI in the Challenge of Sustainability, 2009)

A set of tools for Representing, Decomposing and Visualizing non manifold Cellular Complexes - De Floriani, Leila; Panozzo,D.; Hui,A. (Department of Computer Science and Information Science, University of Genoa, 2009)
Modeling and understanding complex non-manifold shapes is a key issue in shape analysis and retrieval. The topological structure of a non-manifold shape can be analyzed through its decomposition into a collection of components with a simpler topology. Here, we consider a decomposition of a non-manifold shape into components which are almost manifolds, and we present a novel graph representation which highlights the non-manifold singularities shared by the components as well as their connectivity relations. We describe an algorithm for computing the decomposition and its associated graph representation. We present a new tool for visualizing the shape decomposition and its graph as an eﬀective support to modeling, analyzing and understanding non-manifold shapes. We describe a new data structure for non-manifold simplicial complex that we used in our decomposition software and we provide a complete description of all functionalities of the library we developed.

Shearlet-Based Deconvolution - Patel, Vishal M.; Easley,G. R; Healy,D. M (IEEE Transactions on Image Processing, 2009)
In this paper, a new type of deconvolution algorithm is proposed that is based on estimating the image from a shearlet decomposition. Shearlets provide a multidirectional and multiscale decomposition that has been mathematically shown to represent distributed discontinuities such as edges better than traditional wavelets. Constructions such as curvelets and contourlets share similar properties, yet their implementations are significantly different from that of shearlets. Taking advantage of unique properties of a new M-channel implementation of the shearlet transform, we develop an algorithm that allows for the approximation inversion operator to be controlled on a multiscale and multidirectional basis. A key improvement over closely related approaches such as ForWaRD is the automatic determination of the threshold values for the noise shrinkage for each scale and direction without explicit knowledge of the noise variance using a generalized cross validation (GCV). Various tests show that this method can perform significantly better than many competitive deconvolution algorithms.
Keywords: approximation inversion operator; contourlets; curvelets; Deconvolution; distributed discontinuities; generalized cross validation; image restoration; M-channel implementation; shearlet-based deconvolution; shearlets; Wavelet transforms; wavelets

Sparsity inspired selection and recognition of iris images - Pillai,J.K.; Patel, Vishal M.; Chellapa, Rama (Biometrics: Theory, Applications, and Systems, 2009. BTAS '09. IEEE 3rd International Conference on, 2009)
Iris images acquired from a partially cooperating subject often suffer from blur, occlusion due to eyelids, and specular reflections. The performance of existing iris recognition systems degrade significantly on these images. Hence it is essential to select good images from the incoming iris video stream, before they are input to the recognition algorithm. In this paper, we propose a sparsity based algorithm for selection of good iris images and their subsequent recognition. Unlike most existing algorithms for iris image selection, our method can handle segmentation errors and a wider range of acquisition artifacts common in iris image capture. We perform selection and recognition in a single step which is more efficient than devising separate specialized algorithms for the two. Recognition from partially cooperating users is a significant step towards deploying iris systems in a wide variety of applications.
Keywords: biometrics (access control); image recognition; Image segmentation; iris image recognition; iris image selection; iris video stream; sparsity inspired selection; video signal processing; video streaming

SPOT Databases: Efficient Consistency Checking and Optimistic Selection in Probabilistic Spatial Databases - Parker,A.; Infantes,G.; Grant,J.; V.S. Subrahmanian (Knowledge and Data Engineering, IEEE Transactions on, 2009)
Spatial probabilistic temporal (SPOT) databases are a paradigm for reasoning with probabilistic statements about where a vehicle may be now or in the future. They express statements of the form "Object O is in spatial region R at some time t with some probability in the interval [L,U]." Past work on SPOT databases has developed selection operators based on selecting SPOT atoms that are entailed by the SPOT database-we call this "cautious" selection. In this paper, we study several problems. First, we note that the runtime of consistency checking and cautious selection algorithms in past work is influenced greatly by the granularity of the underlying Cartesian space. In this paper, we first introduce the notion of "optimistic" selection, where we are interested in returning all SPOT atoms in a database that are consistent with respect to a query, rather than having an entailment relationship. We then develop an approach to scaling SPOT databases that has three main contributions: 1) We develop methods to eliminate variables from the linear programs used in past work, thus greatly reducing the size of the linear programs used-the resulting advances apply to consistency checking, optimistic selection, and cautious selection. 2) We develop a host of theorems to show how we can prune the search space when we are interested in optimistic selection. 3) We use the above contributions to build an efficient index to execute optimistic selection queries over SPOT databases. Our approach is superior to past work in two major respects: First, it makes fewer assumptions than all past works on this topic except that in. Second, our experiments, which are based on real-world data about ship movements, show that our algorithms are much more efficient than those in.
Keywords: Cartesian; checking; database; database; data; databases; databases; visual; indexing; inference; indexing; linear; integrity; database; mechanisms; linear; probabilistic; problem; spatial; problems; temporal; processing; search; program; optimistic; programming; probability; query; query; probabilistic; reasoning; search; selection; selection; consistency; space; cautious; temporal

Statistical Methods for Detecting Differentially Abundant Features in Clinical Metagenomic Samples - White,James Robert; Nagarajan,Niranjan; Pop, Mihai (PLoS Comput Biology, 2009)
The emerging field of metagenomics aims to understand the structure and function of microbial communities solely through DNA analysis. Current metagenomics studies comparing communities resemble large-scale clinical trials with multiple subjects from two general populations (e.g. sick and healthy). To improve analyses of this type of experimental data, we developed a statistical methodology for detecting differentially abundant features between microbial communities, that is, features that are enriched or depleted in one population versus another. We show our methods are applicable to various metagenomic data ranging from taxonomic information to functional annotations. We also provide an assessment of taxonomic differences in gut microbiota between lean and obese humans, as well as differences between the functional capacities of mature and infant gut microbiomes, and those of microbial and viral metagenomes. Our methods are the first to statistically address differential abundance in comparative metagenomics studies with multiple subjects, and we hope will give researchers a more complete picture of how exactly two environments differ.

The Story of One: Humanity scholarship with visualization and text analysis - Clement,T.; Plaisant, Catherine; Vuillemot,R. (Relation, 2009)

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

Task decomposition on abstract states, for planning under nondeterminism - Kuter,Ugur; Nau, Dana S.; Pistore,Marco; Traverso,Paolo (Artificial Intelligence, 2009)
Although several approaches have been developed for planning in nondeterministic domains, solving large planning problems is still quite difficult. In this work, we present a new planning algorithm, called Yoyo, for solving planning problems in fully observable nondeterministic domains. Yoyo combines an HTN-based mechanism for constraining its search and a Binary Decision Diagram (BDD) representation for reasoning about sets of states and state transitions.We provide correctness theorems for Yoyo, and an experimental comparison of it with MBP and ND-SHOP2, the two previously-best algorithms for planning in nondeterministic domains. In our experiments, Yoyo could easily deal with problem sizes that neither MBP nor ND-SHOP2 could scale up to, and could solve problems about 100 to 1000 times faster than MBP and ND-SHOP2.
Keywords: Binary decision diagrams; Hierarchical task-network (HTN) planning; Planning in nondeterministic domains

Temporal Summaries: Supporting Temporal Categorical Searching, Aggregation and Comparison - Wang,T. D; Plaisant, Catherine; Shneiderman, Ben; Spring, Neil; Roseman,D.; Marchand,G.; Mukherjee,V.; Smith,M. (IEEE Transactions on Visualization and Computer Graphics, 2009)
When analyzing thousands of event histories, analysts often want to see the events as an aggregate to detect insights and generate new hypotheses about the data. An analysis tool must emphasize both the prevalence and the temporal ordering of these events. Additionally, the analysis tool must also support flexible comparisons to allow analysts to gather visual evidence. In a previous work, we introduced align, rank, and filter (ARF) to accentuate temporal ordering. In this paper, we present temporal summaries, an interactive visualization technique that highlights the prevalence of event occurrences. Temporal summaries dynamically aggregate events in multiple granularities (year, month, week, day, hour, etc.) for the purpose of spotting trends over time and comparing several groups of records. They provide affordances for analysts to perform temporal range filters. We demonstrate the applicability of this approach in two extensive case studies with analysts who applied temporal summaries to search, filter, and look for patterns in electronic health records and academic records.
Keywords: Aggregates; Collaborative work; Computational Biology; Computer Graphics; Data analysis; data visualisation; Data visualization; Databases, Factual; Displays; Event detection; Filters; Heparin; History; Human computer interaction; Human-computer interaction; HUMANS; Information Visualization; Interaction design; interactive visualization technique; Medical Records Systems, Computerized; Pattern Recognition, Automated; Performance analysis; Springs; temporal categorical data visualization; temporal categorical searching; temporal ordering; temporal summaries; Thrombocytopenia; Time factors

Temporal Summaries: Supporting Temporal Categorical Searching, Aggregation and Comparison - Wang,T. D; Plaisant, Catherine; Shneiderman, Ben; Spring, Neil; Roseman,D.; Marchand,G.; Mukherjee,V.; Smith,M. (Visualization and Computer Graphics, IEEE Transactions on, 2009)
When analyzing thousands of event histories, analysts often want to see the events as an aggregate to detect insights and generate new hypotheses about the data. An analysis tool must emphasize both the prevalence and the temporal ordering of these events. Additionally, the analysis tool must also support flexible comparisons to allow analysts to gather visual evidence. In a previous work, we introduced align, rank, and filter (ARF) to accentuate temporal ordering. In this paper, we present temporal summaries, an interactive visualization technique that highlights the prevalence of event occurrences. Temporal summaries dynamically aggregate events in multiple granularities (year, month, week, day, hour, etc.) for the purpose of spotting trends over time and comparing several groups of records. They provide affordances for analysts to perform temporal range filters. We demonstrate the applicability of this approach in two extensive case studies with analysts who applied temporal summaries to search, filter, and look for patterns in electronic health records and academic records.
Keywords: Automated; Thrombocytopenia; Time Factors; Computerized; Pattern Recognition; Factual; Heparin; Humans; Medical Records Systems; interactive visualization technique; temporal categorical searching; temporal ordering; temporal summaries; data visualisation; human computer interaction; Computational Biology; Computer Graphics; Databases

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

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

Triaging Checklists: a Substitute for a PhD in Static Analysis - Phang,K.Y.; Foster, Jeffrey S.; Hicks, Michael W.; Sazawal,V. (Evaluation and Usability of Programming Languages and Tools (PLATEAU) PLATEAU 2009, 2009)
Static analysis tools have achieved great success in recentyears in automating the process of detecting defects in soft- ware. However, these sophisticated tools have yet to gain widespread adoption, since many of these tools remain too difficult to understand and use. In previous work, we dis- covered that even with an effective code visualization tool, users still found it hard to determine if warnings reported by these tools were true errors or false warnings. The fun- damental problem users face is to understand enough of the underlying algorithm to determine if a warning is caused by imprecision in the algorithm, a challenge that even experts with PhDs may take a while to achieve. In our current work, we propose to use triaging checklists to provide users with systematic guidance to identify false warnings by taking into account specific sources of imprecision in the particular tool. Additionally, we plan to provide checklist assistants, which is a library of simple analyses designed to aid users in an- swering checklist questions.

Ultrafast and memory-efficient alignment of short DNA sequences to the human genome - Langmead,Ben; Trapnell,Cole; Pop, Mihai; Salzberg,Steven L. (Genome Biology, 2009)
Bowtie is an ultrafast, memory-efficient alignment program for aligning short DNA sequence reads to large genomes. For the human genome, Burrows-Wheeler indexing allows Bowtie to align more than 25 million reads per CPU hour with a memory footprint of approximately 1.3 gigabytes. Bowtie extends previous Burrows-Wheeler techniques with a novel quality-aware backtracking algorithm that permits mismatches. Multiple processor cores can be used simultaneously to achieve even greater alignment speeds. Bowtie is open source http://bowtie.cbcb.umd.edu.

A unified approach to scheduling on unrelated parallel machines - Kumar,V. S. Anil; Marathe,Madhav V.; Parthasarathy,Srinivasan; Srinivasan, Aravind (J. ACM, 2009)
We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lp norm of the vector of machine-loads, for all 1 < p < ∞; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys & Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].
Keywords: Approximation algorithms; Randomized rounding; scheduling under multiple criteria

VAST 2009 challenge: An insider threat - Grinstein,G.; Scholtz,J.; Whiting,M.; Plaisant, Catherine (Visual Analytics Science and Technology, 2009. VAST 2009. IEEE Symposium on, 2009)
The 4th VAST Challenge centered on a cyber analytics scenario and offered three mini-challenges with datasets of badge and network traffic data, a social network including geospatial information, and security video. Teams could also enter the Grand challenge which combined all three datasets. In this paper, we summarize the dataset, the overall scenario and the questions asked in the challenges. We describe the judging process and new infrastructure developed to manage the submissions and compute accuracy measures in the social network mini challenge. We received 49 entries from 30 teams, and gave 23 different awards to a total of 16 teams.
Keywords: 2009; analytics; data; analytics; geospatial; challenge; cyber; data; security; information; information; human; interaction; network; interfaces; network; visual; traffic; user; VAST; video; social; visualisation; graphical

Video Compression and Retrieval of Moving Object Location Applied to Surveillance - Schwartz,W.; Pedrini,H.; Davis, Larry S. (Image Analysis and Recognition, 2009)
A major problem in surveillance systems is the storage requirements for video archival; videos are recorded continuously for long periods of time, resulting in large amounts of data. Therefore, it is essential to apply efficient compression techniques. Additionally, it is useful to be able to index the archived videos based on events. In general, such events are defined by the interaction among moving objects in the scene. Consequently, besides data compression, efficient ways of storing moving objects should be considered. We present a method that exploits both temporal and spatial redundancy of videos captured from static cameras to perform compression and subsequently allows fast retrieval of moving object locations directly from the compressed data. Experimental results show that the approach achieves high compression ratios compared to other existing video compression techniques without significant quality degradation and is fast due to the simplicity of the operations required for compression and decompression.

Visual-Analytics Evaluation - Plaisant, Catherine; Grinstein,G.; Scholtz,J. (Computer Graphics and Applications, IEEE, 2009)
Visual analytics (VA) is the science of analytical reasoning facilitated by interactive visual interfaces. Assessing VA technology's effectiveness is challenging because VA tools combine several disparate components, both low and high level, integrated in complex interactive systems used by analysts, emergency responders, and others. These components include analytical reasoning, visual representations, computer-human interaction techniques, data representations and transformations, collaboration tools, and especially tools for communicating the results of their use. VA tool users' activities can be exploratory and can take place over days, weeks, or months. Users might not follow a predefined or even linear work flow. They might work alone or in groups. To understand these complex behaviors, an evaluation can target the component level, the system level, or the work environment level, and requires realistic data and tasks. Traditional evaluation metrics such as task completion time, number of errors, or recall and precision are insufficient to quantify the utility of VA tools, and new research is needed to improve our VA evaluation methodology.
Keywords: analytic; analytics; evaluation; cognition; data; generation; user; interactive; interfaces; synthetic-data-set; reasoning; visual; systems; tools; visual; visual; visualisation; interactive

What puts the “meta” in metacognition? - Anderson,M. L; Perlis, Don (Behavioral and Brain Sciences, 2009)

What's being said near "Martha"? Exploring name entities in literary text collections - Vuillemot,R.; Clement,T.; Plaisant, Catherine; Kumar,A. (Visual Analytics Science and Technology, 2009. VAST 2009. IEEE Symposium on, 2009)
A common task in literary analysis is to study characters in a novel or collection. Automatic entity extraction, text analysis and effective user interfaces facilitate character analysis. Using our interface, called POSvis, the scholar uses word clouds and self-organizing graphs to review vocabulary, to filter by part of speech, and to explore the network of characters located near characters under review. Further, visualizations show word usages within an analysis window (i.e. a book chapter), which can be compared with a reference window (i.e. the whole book). We describe the interface and report on an early case study with a humanities scholar.
Keywords: analysis; humanities; analysis; literary; analysis; user; clouds; word; collection; name; entity; entity; part-of-speech; extraction; character; filtering; linguistics; text; filtering; self-organizing; graph; text; interface; vocabulary; word; interfaces; vocabulary; POSvis; automatic; scholar; literary; text; usage; data; visualisation; information

Within epsilon of optimal play in the cultaptation social learning game - Carr,Ryan; Raboin,Eric; Parker,Austin; Nau, Dana S. (International Foundation for Autonomous Agents and Multiagent Systems, 2009)
Social learning, in which members of a society learn by observing the behavior of others, is an important foundation for human culture, and is observed in many other species as well. It seems natural to assume that social learning evolved due to the inherent superiority of copying others' success rather than learning on one's own via trial-and-error innovation. However, there has also been substantial work questioning this intuition [3, 5, 1, 6, 4]. For example, blindly copying information from others is not useful if the information is wrong---or if it once was right but has since become outdated. Under what conditions does social learning outperform trial-and-error learning, and what kinds of social-learning strategies are likely to perform well?

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

Active logic semantics for a single agent in a static world - Anderson,Michael L.; Gomaa,Walid; Grant,John; Perlis, Don (Artificial Intelligence, 2008)
For some time we have been developing, and have had significant practical success with, a time-sensitive, contradiction-tolerant logical reasoning engine called the active logic machine (ALMA). The current paper details a semantics for a general version of the underlying logical formalism, active logic. Central to active logic are special rules controlling the inheritance of beliefs in general (and of beliefs about the current time in particular), very tight controls on what can be derived from direct contradictions (P&¬P), and mechanisms allowing an agent to represent and reason about its own beliefs and past reasoning. Furthermore, inspired by the notion that until an agent notices that a set of beliefs is contradictory, that set seems consistent (and the agent therefore reasons with it as if it were consistent), we introduce an "apperception function" that represents an agent's limited awareness of its own beliefs, and serves to modify inconsistent belief sets so as to yield consistent sets. Using these ideas, we introduce a new definition of logical consequence in the context of active logic, as well as a new definition of soundness such that, when reasoning with consistent premises, all classically sound rules remain sound in our new sense. However, not everything that is classically sound remains sound in our sense, for by classical definitions, all rules with contradictory premises are vacuously sound, whereas in active logic not everything follows from a contradiction.
Keywords: Active logic; Autonomous agents; Brittleness; Logic; Nonmonotonic logic; Paraconsistent logic; semantics; Soundness; TIME

Advances in multilingual and multimodal information retrieval - Peters,C.; Jijkoun,V.; Mandl,T.; Müller,H.; Oard, Douglas; Peñas,A.; Santos,D. (Lecture Notes in Computer Science, 2008)

An AGM-based belief revision mechanism for probabilistic spatio-temporal logics - Parker,A.; Infantes,G.; V.S. Subrahmanian; Grant,J. (Proceedings of the 23rd national conference on Artificial intelligence, 2008)

Algorithms for computing a parameterized st-orientation - Charalampos Papamanthou; Tollis, Ioannis G. (Theoretical Computer Science, 2008)
s t -orientations ( s t -numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an s t -orientation of a biconnected graph. In this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final s t -oriented graph, such as the length of the longest path. This work has many applications, including Graph Drawing and Network Routing, where the length of the longest path is vital in deciding certain features of the final solution. This work applies to other difficult problems as well, such as graph coloring and of course longest path. We present extended theoretical and experimental results which show that our technique is efficient and performs well in practice.
Keywords: Graph algorithms; Longest path; Planar graphs; s t -numberings

Algorithms for Generating Adaptive Projection Patterns for 3D Shape Measurement - Peng,T.; Gupta,S.K. (Journal of Computing and Information Science in Engineering, 2008)

Algorithms for Location Estimation Based on RSSI Sampling - Charalampos Papamanthou; Preparata, Franco P.; Tamassia, Roberto (Algorithmic Aspects of Wireless Sensor Networks, 2008)
In this paper, we re-examine the RSSI measurement model for location estimation and provide the first detailed formulation of the probability distribution of the position of a sensor node. We also show how to use this probabilistic model to efficiently compute a good estimation of the position of the sensor node by sampling multiple readings from the beacons (where we do not merely use the mean of the samples) and then minimizing a function with an acceptable computational effort. The results of the simulation of our method in TOSSIM indicate that the location of the sensor node can be computed in a small amount of time and that the quality of the solution is competitive with previous approaches.
Keywords: Algorithm Analysis and Problem Complexity; Computer Communication Networks; Data structures; Discrete Mathematics in Computer Science; Information Systems and Communication Service

Aligning temporal data by sentinel events: discovering patterns in electronic health records - Wang,Taowei David; Plaisant, Catherine; Quinn,Alexander J.; Stanchak,Roman; Murphy,Shawn; Shneiderman, Ben (Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)
Electronic Health Records (EHRs) and other temporal databases contain hidden patterns that reveal important cause-and-effect phenomena. Finding these patterns is a challenge when using traditional query languages and tabular displays. We present an interactive visual tool that complements query formulation by providing operations to align, rank and filter the results, and to visualize estimates of the intervals of validity of the data. Display of patient histories aligned on sentinel events (such as a first heart attack) enables users to spot precursor, co-occurring, and aftereffect events. A controlled study demonstrates the benefits of providing alignment (with a 61% speed improvement for complex tasks). A qualitative study and interviews with medical professionals demonstrates that the interface can be learned quickly and seems to address their needs.
Keywords: electronic health record; Evaluation; Information Visualization; search; temporal data; Uncertainty

Approximation Algorithms for Computing Capacity of Wireless Networks with SINR Constraints - Chafekar,D.; Kumart,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2008. The 27th Conference on Computer Communications, 2008)
A fundamental problem in wireless networks is to estimate its throughput capacity - given a set of wireless nodes, and a set of connections, what is the maximum rate at which data can be sent on these connections. Most of the research in this direction has focused on either random distributions of points, or has assumed simple graph-based models for wireless interference. In this paper, we study capacity estimation problem using the more general Signal to Interference Plus Noise Ratio (SINR) model for interference, on arbitrary wireless networks. The problem becomes much harder in this setting, because of the non-locality of the SINR model. Recent work by Moscibroda et al. (2006) has shown that the throughput in this model can differ from graph based models significantly. We develop polynomial time algorithms to provably approximate the total throughput in this setting.
Keywords: Algorithm design and analysis; approximation algorithm; Approximation algorithms; approximation theory; Computer networks; Computer science; graph theory; graph-based model; Interference constraints; polynomial time algorithm; Propagation losses; Protocols; radio networks; radiofrequency interference; signal to interference plus noise ratio; Signal to noise ratio; Throughput; wireless interference; wireless network; Wireless networks

Athos: Efficient Authentication of Outsourced File Systems: Information Security - Triandopoulos, Nikolaos; Goodrich, Michael T.; Charalampos Papamanthou; Tamassia, Roberto (Lecture Notes in Computer Science, 2008)

Authenticated Hash Tables - Charalampos Papamanthou; Tamassia, Roberto; Triandopoulos, Nikos (CCS '08 Proceedings of the 15th ACM Conference on Computer and Communications Security, 2008)
Hash tables are fundamental data structures that optimally answer membership queries. Suppose a client stores n elements in a hash table that is outsourced at a remote server so that the client can save space or achieve load balancing. Authenticating the hash table functionality, i.e., verifying the correctness of queries answered by the server and ensuring the integrity of the stored data, is crucial because the server, lying outside the administrative control of the client, can be malicious. We design efficient and secure protocols for optimally authenticating membership queries on hash tables: for any fixed constants 0 < ε < 1 and κ > 1/ε, the server can provide a proof of integrity of the answer to a (non-)membership query in constant time, requiring O(nε/logκε--1 n) time to treat updates, yet keeping the communication and verification costs constant. This is the first construction for authenticating a hash table with constant query cost and sublinear update cost. Our solution employs the RSA accumulator in a nested way over the stored data, strictly improving upon previous accumulator-based solutions. Our construction applies to two concrete data authentication models and lends itself to a scheme that achieves different trade-offs---namely, constant update time and O(nε/logκε n) query time for fixed ε > 0 and κ > 0. An experimental evaluation of our solution shows very good scalability.
Keywords: Authentication; hash tables; rsa accumulator; verification

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

Bioinformatics challenges of new sequencing technology - Pop, Mihai; Salzberg,Steven L. (Trends in Genetics, 2008)
New DNA sequencing technologies can sequence up to one billion bases in a single day at low cost, putting large-scale sequencing within the reach of many scientists. Many researchers are forging ahead with projects to sequence a range of species using the new technologies. However, these new technologies produce read lengths as short as 35–40 nucleotides, posing challenges for genome assembly and annotation. Here we review the challenges and describe some of the bioinformatics systems that are being proposed to solve them. We specifically address issues arising from using these technologies in assembly projects, both de novo and for resequencing purposes, as well as efforts to improve genome annotation in the fragmented assemblies produced by short read lengths.

Capacity of Asynchronous Random-Access Scheduling in Wireless Networks - Chafekar,D.; Levin,D.; Kumar,V. S.A; Marathe,M. V; Parthasarathy,S.; Srinivasan, Aravind (IEEE INFOCOM 2008. The 27th Conference on Computer Communications, 2008)
We study the throughput capacity of wireless networks which employ (asynchronous) random-access scheduling as opposed to deterministic scheduling. The central question we answer is: how should we set the channel-access probability for each link in the network so that the network operates close to its optimal throughput capacity? We design simple and distributed channel-access strategies for random-access networks which are provably competitive with respect to the optimal scheduling strategy, which is deterministic, centralized, and computationally infeasible. We show that the competitiveness of our strategies are nearly the best achievable via random-access scheduling, thus establishing fundamental limits on the performance of random- access. A notable outcome of our work is that random access compares well with deterministic scheduling when link transmission durations differ by small factors, and much worse otherwise. The distinguishing aspects of our work include modeling and rigorous analysis of asynchronous communication, asymmetry in link transmission durations, and hidden terminals under arbitrary link-conflict based wireless interference models.
Keywords: asynchronous random-access scheduling; channel access probability; Computer networks; Computer science; Educational institutions; Interference; Optimal scheduling; Peer to peer computing; probability; Processor scheduling; radio link; radio links; radio networks; Routing; scheduling; Throughput; throughput capacity; wireless channels; Wireless networks

CiCUTS: Combining System Execution Modeling Tools with Continuous Integration Environments - Hill,James H.; Schmidt,Douglas C.; Porter, Adam; Slaby,John M. (Engineering of Computer-Based Systems, IEEE International Conference on the, 2008)
System execution modeling (SEM) tools provide an effective means to evaluate the quality of service (QoS) of enterprise distributed real-time and embedded (DRE) systems. SEM tools facilitate testing and resolving performance issues throughout the entire development life-cycle, rather than waiting until final system integration. SEM tools have not historically focused on effective testing. New techniques are therefore needed to help bridge the gap between the early integration capabilities of SEM tools and testing so developers can focus on resolving strategic integration and performance issues, as opposed to wrestling with tedious and error-prone low-level testing concerns. This paper provides two contributions to research on using SEM tools to address enterprise DRE system integration challenges. First, we evaluate several approaches for combining continuous integration environments with SEM tools and describe CiCUTS, which combines the CUTS SEM tool with the CruiseControl .NET continuous integration environment. Second, we present a case study that shows how CiCUTS helps reduce the time and effort required to manage and execute integration tests that evaluate QoS metrics for a representative DRE system from the domain of shipboard computing. The results of our case study show that CiCUTS helps developers and testers ensure the performance of an example enterprise DRE system is within its QoS specifications throughout development, instead of waiting until system integration time to evaluate QoS.
Keywords: continuous integration; integration testing; serialized phasing; system execution modeling

Community response grid (CRG) for a university campus: Design requirements and implications - Wu,P.F.; Qu,Y.; Preece,J.; Fleischmann,K.; Golbeck,J.; Jaeger,P.; Shneiderman, Ben (Proceedings of the 5th International ISCRAM Conference, 2008)
This paper describes the initial stages of the participatory design of a community-oriented emergency responsesystem for a university campus. After reviewing related work and the current University emergency response system, this paper describes our participatory design process, discusses initial findings from a design requirement survey and from our interactions with different stakeholders, and proposes a Web interface design for a community response grid system. The prototyping of the system demonstrates the possibility of fostering a social-network-based community participation in emergency response, and also identifies concerns raised by potential users and by the professional responder community.

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

A Constrained Probabilistic Petri Net Framework for Human Activity Detection in Video - Albanese, M.; Chellapa, Rama; Moscato, V.; Picariello, A.; V.S. Subrahmanian; Turaga,P.; Udrea,O. (Multimedia, IEEE Transactions on, 2008)
Recognition of human activities in restricted settings such as airports, parking lots and banks is of significant interest in security and automated surveillance systems. In such settings, data is usually in the form of surveillance videos with wide variation in quality and granularity. Interpretation and identification of human activities requires an activity model that a) is rich enough to handle complex multi-agent interactions, b) is robust to uncertainty in low-level processing and c) can handle ambiguities in the unfolding of activities. We present a computational framework for human activity representation based on Petri nets. We propose an extension-Probabilistic Petri Nets (PPN)-and show how this model is well suited to address each of the above requirements in a wide variety of settings. We then focus on answering two types of questions: (i) what are the minimal sub-videos in which a given activity is identified with a probability above a certain threshold and (ii) for a given video, which activity from a given set occurred with the highest probability? We provide the PPN-MPS algorithm for the first problem, as well as two different algorithms (naive PPN-MPA and PPN-MPA) to solve the second. Our experimental results on a dataset consisting of bank surveillance videos and an unconstrained TSA tarmac surveillance dataset show that our algorithms are both fast and provide high quality results.
Keywords: activity; dataset; automated; detection; human; interactions; security; net; human; nets; image; Petri; probabilistic; processing; multiagent; processing; video; representation; low-level; representation; video; signal; Surveillance; surveillance; systems; constrained; systems; surveillance; tarmac; TSA; videos; Petri

Contextual effects for version-consistent dynamic software updating and safe concurrent programming - Neamtiu,Iulian; Hicks, Michael W.; Foster, Jeffrey S.; Pratikakis,Polyvios (Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, 2008)
This paper presents a generalization of standard effect systems that we call contextual effects. A traditional effect system computes the effect of an expression e. Our system additionally computes the effects of the computational context in which e occurs. More specifically, we computethe effect of the computation that has already occurred(the prior effect) and the effect of the computation yet to take place (the future effect). Contextual effects are useful when the past or future computation of the program is relevant at various program points. We present two substantial examples. First, we show how prior and future effects can be used to enforce transactional version consistency(TVC), a novel correctness property for dynamic software updates. TV Censures that programmer-designated transactional code blocks appear to execute entirely at the same code version, even if a dynamic update occurs in the middle of the block. Second, we show how future effects can be used in the analysis of multi-threaded programs to find thread-shared locations. This is an essential step in applications such as data race detection.
Keywords: computation effects; contextual effects; data race detection; dynamic software updating; type and effect systems; version consistency

Data Sonification for Users with Visual Impairment: A Case Study with Georeferenced Data - Zhao,Haixia; Plaisant, Catherine; Shneiderman, Ben; Lazar,Jonathan (ACM Trans. Comput.-Hum. Interact., 2008)
We describe the development and evaluation of a tool, iSonic, to assist users with visual impairment in exploring georeferenced data using coordinated maps and tables, augmented with nontextual sounds and speech output. Our in-depth case studies with 7 blind users during 42 hours of data collection, showed that iSonic enabled them to find facts and discover trends in georeferenced data, even in unfamiliar geographical contexts, without special devices. Our design was guided by an Action-by-Design-Component (ADC) framework, which was also applied to scatterplots to demonstrate its generalizability. Video and download is available at www.cs.umd.edu/hcil/iSonic/.
Keywords: auditory user interfaces; information seeking; Interactive sonification; universal usability; users with visual impairment

Designing community-based emergency communication system: A preliminary study - Fei Wu,P.; Qu,Y.; Fleischmann,K.; Golbeck,J.; Jaeger,P.; Preece,J.; Shneiderman, Ben (Proceedings of the American Society for Information Science and Technology, 2008)

Discrete Distortion in Triangulated 3‐Manifolds - Mesmoudi,Mohammed Mostefa; De Floriani, Leila; Port,Umberto (Computer Graphics Forum, 2008)
We introduce a novel notion, that we call discrete distortion, for a triangulated 3-manifold. Discrete distortion naturally generalizes the notion of concentrated curvature defined for triangulated surfaces and provides a powerful tool to understand the local geometry and topology of 3-manifolds. Discrete distortion can be viewed as a discrete approach to Ricci curvature for singular flat manifolds. We distinguish between two kinds of distortion, namely, vertex distortion, which is associated with the vertices of the tetrahedral mesh decomposing the 3-manifold, and bond distortion, which is associated with the edges of the tetrahedral mesh. We investigate properties of vertex and bond distortions. As an example, we visualize vertex distortion on manifold hypersurfaces in R4 defined by a scalar field on a 3D mesh. distance fields.
Keywords: I.3.3 [Computer Graphics]; I.3.5 [Computational Geometry and Object Modeling]

Distortion lower bounds for line embeddings - Mathieu, Claire; Charalampos Papamanthou (Information Processing Letters, 2008)
In this paper, we show how we can derive lower bounds and also compute the exact distortion for the line embeddings of some special metrics, especially trees and graphs with certain structure. Using linear programming to formulate a simpler version of the problem gives an interesting intuition and direction concerning the computation of general lower bounds for distortion into the line. We also show that our lower bounds on special cases of metrics are a lot better than previous lower bounds.
Keywords: combinatorial problems; Theory of computation

Dual role colonization factors connecting Vibrio cholerae's lifestyles in human and aquatic environments open new perspectives for combating infectious diseases - Vezzulli,Luigi; Guzmán,Carlos A; Rita R Colwell; Pruzzo,Carla (Current Opinion in Biotechnology, 2008)
Vibrio cholerae exhibits two distinctive lifestyles, one inside the milieu of the human intestine and the other in the aquatic environment. Recently, the existence of V. cholerae ligands involved in colonization of both human intestine and environmental chitin surfaces via the same binding specificity has been shown. Such molecules, here named ‘dual role colonization factors (DRCFs)’, are example of a tight connection between the two V. cholerae's lifestyles. It is suggested that DRCFs and, more generally, bacterial factors and pathways having roles in pathogenesis and in the out of the human body life may be promising targets for development of novel prophylactic or therapeutic interventions that may also affect V. cholerae fitness in its environmental reservoirs.

Effective and scalable software compatibility testing - Yoon,Il-Chul; Sussman, Alan; Memon, Atif M.; Porter, Adam (Proceedings of the 2008 international symposium on Software testing and analysis, 2008)
Today's software systems are typically composed of multiple components, each with different versions. Software compatibility testing is a quality assurance task aimed at ensuring that multi-component based systems build and/or execute correctly across all their versions' combinations, or configurations. Because there are complex and changing interdependencies between components and their versions, and because there are such a large number of configurations, it is generally infeasible to test all potential configurations. Consequently, in practice, compatibility testing examines only a handful of default or popular configurations to detect problems; as a result costly errors can and do escape to the field. This paper presents a new approach to compatibility testing, called Rachet. We formally model the entire configuration space for software systems and use the model to generate test plans to sample a portion of the space. In this paper, we test all direct dependencies between components and execute the test plan efficiently in parallel. We present empirical results obtained by applying our approach to two large-scale scientific middleware systems. The results show that for these systems Rachet scaled well and discovered incompatibilities between components, and that testing only direct dependences did not compromise test quality.
Keywords: component-based software system; software compatibility testing

Effective Visualization of File System Access-Control - Heitzmann, Alexander; Palazzi, Bernardo; Charalampos Papamanthou; Tamassia, Roberto (Visualization for Computer Security, 2008)
In this paper, we present a visual representation of access control permissions in a standard hierarchical file system. Our visualization of file permissions leverages treemaps, a popular graphical representation of hierarchical data. In particular, we present a visualization of access control for the NTFS file system that can help a non-expert user understand and manipulate file system permissions in a simple and effective way. While our examples are based on NTFS, our approach can be used for many other hierarchical file systems as well.
Keywords: Computer Communication Networks; Computer Imaging, Vision, Pattern Recognition and Graphics; data mining and knowledge discovery; Data Structures, Cryptology and Information Theory; Visualization

Efficient Integrity Checking of Untrusted Network Storage - Heitzmann, Alexander; Palazzi, Bernardo; Charalampos Papamanthou; Tamassia, Roberto (StorageSS '08 Proceedings of the 4th ACM International Workshop on Storage Security and Survivability, 2008)
Outsourced storage has become more and more practical in recent years. Users can now store large amounts of data in multiple servers at a relatively low price. An important issue for outsourced storage systems is to design an efficient scheme to assure users that their data stored at remote servers has not been tampered with. This paper presents a general method and a practical prototype application for verifying the integrity of files in an untrusted network storage service. The verification process is managed by an application running in a trusted environment (typically on the client) that stores just one cryptographic hash value of constant size, corresponding to the "digest" of an authenticated data structure. The proposed integrity verification service can work with any storage service since it is transparent to the storage technology used. Experimental results show that our integrity verification method is efficient and practical for network storage systems.
Keywords: authenticated data structures; data integrity; Security; untrusted outsourced storage

Enabling teachers to explore grade patterns to identify individual needs and promote fairer student assessment - Friedler,Sorelle A.; Tan,Yee Lin; Peer,Nir J.; Shneiderman, Ben (Computers & Education, 2008)
Exploring student test, homework, and other assessment scores is a challenge for most teachers, especially when attempting to identify cross-assessment weaknesses and produce final course grades. During the course, teachers need to identify subject weaknesses in order to help students who are struggling with a particular topic. This identification often needs to happen across multiple assessment data points and should be considered in comparison to the class’s progress as a whole. When determining grades, fairness to all is essential, but there are special needs for students who did poorly on one exam or had a steadily increasing grasp of the subject. We present eduViz, a visualization tool designed to help teachers explore and assign grades. Teachers can see the trajectory of student scores, the relationship of a particular student to the class, and use categories they have defined in order to filter their assessment information. Query response is immediate and all logical comparisons are possible. Teachers can easily compare their query to the class or per student average as well as view scores by raw point total or percentage. Additionally, eduViz provides a grade assignment interface which allows teachers to view sorted student scores in a scatterplot. This scatterplot is coupled with a unique partition slider which allows users to move color coordinated bands on the scatterplot to indicate grade ranges. As these grade ranges are set, a histogram is updated to show the number of students assigned to each grade range. These features give teachers new and powerful ways to explore and assign grades so that they can better understand student strengths and weaknesses and make the most of the time they have available. Interviews with 16 expert teachers indicate that eduViz is a success across fields, provides teachers with a useful tool to understand and help their classes, and encourages reflective practice.
Keywords: Evaluation methodologies; Human–computer interface; Improving classroom teaching; Pedagogical issues; Teaching/learning strategies

Enhancing In-Car Navigation Systems with Personal Experience - Bederson, Benjamin B.; Clamage,Aaron; Plaisant, Catherine (Transportation Research Record: Journal of the Transportation Research Board, 2008)
Computers are extremely powerful for data processing but less adept at handling problems that involve subjective reasoning. People, on the other hand, are good at such tasks. A framework is presented for adding subjective human experience to in-car navigation systems. People often rely on personal experience when planning trips, choosing the route that is fastest, prettiest, or recommended by a friend. A set of methods was developed to help people record personal driving history, add textual annotations describing subjective experiences, and share data with friends and family or even the broader community. Users can then learn from personal data or harness the multiplicity of individual experiences to enjoy new routes. This approach can be used in conjunction with traditional in-car navigation systems.

Evaluating Visual Analytics at the 2007 VAST Symposium Contest - Plaisant, Catherine; Grinstein,G.; Scholtz,J.; Whiting,M.; O'Connell,T.; Laskowski,S.; Chien,L.; Tat,A.; Wright,W.; Gorg,C.; Zhicheng Liu; Parekh,N.; et al. (Computer Graphics and Applications, IEEE, 2008)
In this article, we report on the contest's data set and tasks, the judging criteria, the winning tools, and the overall lessons learned in the competition. We believe that by organizing these contests, we're creating useful resources for researchers and are beginning to understand how to better evaluate VA tools. Competitions encourage the community to work on difficult problems, improve their tools, and develop baselines for others to build or improve upon. We continue to evolve a collection of data sets, scenarios, and evaluation methodologies that reflect the richness of the many VA tasks and applications.
Keywords: 2007; analytics; analytics; data; and; Contest; Visual; Science; Symposium; Technology; data; VAST; visualisation; visualization; visual

Experiences with building an intrusion-tolerant group communication system - Ramasamy,HariGovind V.; Pandey,Prashant; Michel Cukier; Sanders,William H. (Software: Practice and Experience, 2008)
There are many group communication systems (GCSs) that provide consistent group membership and reliable, ordered multicast properties in the presence of crash faults. However, relatively few GCS implementations are able to provide these properties in the presence of malicious faults resulting from intrusions. We describe the systematic transformation of a crash-tolerant GCS, namely C-Ensemble, into an intrusion-tolerant GCS, the ITUA GCS. To perform the transformation, we devised intrusion-tolerant versions of key group communication protocols. We then inserted implementations of the protocols into C-Ensemble and made significant changes to the rest of the C-Ensemble protocol stack to make the stack intrusion tolerant. We quantify the cost of providing intrusion-tolerant group communication in two ways. First, we quantify the implementation effort by presenting a detailed analysis of the amount of change required to the original C-Ensemble system. In doing so, we provide insight into the choice of building an intrusion-tolerant GCS from scratch versus building one by leveraging a crash-tolerant implementation. Second, we quantify the run-time performance cost of tolerating intrusions by presenting results from an experimental evaluation of the main intrusion-tolerant microprotocols. The results are analyzed to identify the parts that contribute the most overhead while providing intrusion tolerance during both normal operation and recovery from intrusions. Copyright © 2007 John Wiley & Sons, Ltd.
Keywords: distributed protocols; experimental evaluation; Fault tolerance; Group communication; intrusion tolerance

Exurbia from the bottom-up: Confronting empirical challenges to characterizing a complex system - Brown,Daniel G.; Robinson,Derek T.; An,Li; Nassauer,Joan I.; Zellner,Moira; Rand, William; Riolo,Rick; Page,Scott E.; Low,Bobbi; Wang,Zhifang (Geoforum, 2008)
We describe empirical results from a multi-disciplinary project that support modeling complex processes of land-use and land-cover change in exurban parts of Southeastern Michigan. Based on two different conceptual models, one describing the evolution of urban form as a consequence of residential preferences and the other describing land-cover changes in an exurban township as a consequence of residential preferences, local policies, and a diversity of development types, we describe a variety of empirical data collected to support the mechanisms that we encoded in computational agent-based models. We used multiple methods, including social surveys, remote sensing, and statistical analysis of spatial data, to collect data that could be used to validate the structure of our models, calibrate their specific parameters, and evaluate their output. The data were used to investigate this system in the context of several themes from complexity science, including have (a) macro-level patterns; (b) autonomous decision making entities (i.e., agents); (c) heterogeneity among those entities; (d) social and spatial interactions that operate across multiple scales and (e) nonlinear feedback mechanisms. The results point to the importance of collecting data on agents and their interactions when producing agent-based models, the general validity of our conceptual models, and some changes that we needed to make to these models following data analysis. The calibrated models have been and are being used to evaluate landscape dynamics and the effects of various policy interventions on urban land-cover patterns.
Keywords: Ecological effects; Land-cover change; Land-use change; spatial modeling; Urban sprawl

Figaro: A Novel Statistical Method for Vector Sequence Removal - White,James Robert; Roberts,Michael; Yorke,James A.; Pop, Mihai (Bioinformatics, 2008)
Motivation: Sequences produced by automated Sanger sequencing machines frequently contain fragments of the cloning vector on their ends. Software tools currently available for identifying and removing the vector sequence require knowledge of the vector sequence, specific splice sites and any adapter sequences used in the experiment—information often omitted from public databases. Furthermore, the clipping coordinates themselves are missing or incorrectly reported. As an example, within the ∼1.24 billion shotgun sequences deposited in the NCBI Trace Archive, as many as ∼735 million (∼60%) lack vector clipping information. Correct clipping information is essential to scientists attempting to validate, improve and even finish the increasingly large number of genomes released at a ‘draft’ quality level.Results: We present here Figaro, a novel software tool for identifying and removing the vector from raw sequence data without prior knowledge of the vector sequence. The vector sequence is automatically inferred by analyzing the frequency of occurrence of short oligo-nucleotides using Poisson statistics. We show that Figaro achieves 99.98% sensitivity when tested on ∼1.5 million shotgun reads from Drosophila pseudoobscura. We further explore the impact of accurate vector trimming on the quality of whole-genome assemblies by re-assembling two bacterial genomes from shotgun sequences deposited in the Trace Archive. Designed as a module in large computational pipelines, Figaro is fast, lightweight and flexible. Availability: Figaro is released under an open-source license through the AMOS package (http://amos.sourceforge.net/Figaro). Contact: mpop@umiacs.umd.edu

Formalizing Soundness of Contextual Effects - Pratikakis,Polyvios; Foster, Jeffrey S.; Hicks, Michael W.; Neamtiu,Iulian (Theorem Proving in Higher Order LogicsTheorem Proving in Higher Order Logics, 2008)
A contextual effect system generalizes standard type and effect systems: where a standard effect system computes the effect of an expression e , a contextual effect system additionally computes the prior and future effect of e , which characterize the behavior of computation prior to and following, respectively, the evaluation of e . This paper describes the formalization and proof of soundness of contextual effects, which we mechanized using the Coq proof assistant. Contextual effect soundness is an unusual property because the prior and future effect of a term e depends not on e itself (or its evaluation), but rather on the evaluation of the context in which e appears. Therefore, to state and prove soundness we must “match up” a subterm in the original typing derivation with the possibly-many evaluations of that subterm during the evaluation of the program, in a way that is robust under substitution. We do this using a novel typed operational semantics. We conjecture that our approach could prove useful for reasoning about other properties of derivations that rely on the context in which that derivation appears.

Genome assembly forensics: finding the elusive mis-assembly - Phillippy,Adam M; Schatz,Michael C; Pop, Mihai (Genome Biology, 2008)
We present the first collection of tools aimed at automated genome assembly validation. This work formalizes several mechanisms for detecting mis-assemblies, and describes their implementation in our automated validation pipeline, called amosvalidate. We demonstrate the application of our pipeline in both bacterial and eukaryotic genome assemblies, and highlight several assembly errors in both draft and finished genomes. The software described is compatible with common assembly formats and is released, open-source, at http://amos.sourceforge.net.

Genome-Wide Analysis of Natural Selection on Human Cis-Elements - Sethupathy,Praveen; Giang,Hoa; Plotkin,Joshua B.; Hannenhalli, Sridhar (PLoS ONEPLoS ONE, 2008)
It has been speculated that the polymorphisms in the non-coding portion of the human genome underlie much of the phenotypic variability among humans and between humans and other primates. If so, these genomic regions may be undergoing rapid evolutionary change, due in part to natural selection. However, the non-coding region is a heterogeneous mix of functional and non-functional regions. Furthermore, the functional regions are comprised of a variety of different types of elements, each under potentially different selection regimes.Using the HapMap and Perlegen polymorphism data that map to a stringent set of putative binding sites in human proximal promoters, we apply the Derived Allele Frequency distribution test of neutrality to provide evidence that many human-specific and primate-specific binding sites are likely evolving under positive selection. We also discuss inherent limitations of publicly available human SNP datasets that complicate the inference of selection pressures. Finally, we show that the genes whose proximal binding sites contain high frequency derived alleles are enriched for positive regulation of protein metabolism and developmental processes. Thus our genome-scale investigation provides evidence for positive selection on putative transcription factor binding sites in human proximal promoters.

Genome-Wide Analysis of Repetitive Elements in Papaya - Nagarajan,Niranjan; Navajas-Pérez,Rafael; Pop, Mihai; Alam,Maqsudul; Ming,Ray; Paterson,Andrew; Salzberg,Steven (Tropical Plant Biology, 2008)
Papaya ( Carica papaya L.) is an important fruit crop cultivated in tropical and subtropical regions worldwide. A first draft of its genome sequence has been recently released. Together with Arabidopsis , rice, poplar, grapevine and other genomes in the pipeline, it represents a good opportunity to gain insight into the organization of plant genomes. Here we report a detailed analysis of repetitive elements in the papaya genome, including transposable elements (TEs), tandemly-arrayed sequences, and high copy number genes. These repetitive sequences account for ∼56% of the papaya genome with TEs being the most abundant at 52%, tandem repeats at 1.3% and high copy number genes at 3%. Most common types of TEs are represented in the papaya genome with retrotransposons being the dominant class, accounting for 40% of the genome. The most prevalent retrotransposons are Ty3-gypsy (27.8%) and Ty1-copia (5.5%). Among the tandem repeats, microsatellites are the most abundant in number, but represent only 0.19% of the genome. Minisatellites and satellites are less abundant, but represent 0.68% and 0.43% of the genome, respectively, due to greater repeat length. Despite an overall smaller gene repertoire in papaya than many other angiosperms, a significant fraction of genes (>2%) are present in large gene families with copy number greater than 20. This repeat database clarified a major part of the papaya genome organization and partly explained the lower gene repertoire in papaya than in Arabidopsis .

Global impact of Vibrio cholerae interactions with chitin - Pruzzo,Carla; Vezzulli,Luigi; Rita R Colwell (Environmental Microbiology, 2008)
The interaction of Vibrio cholerae with chitin exemplifies for microbial ecology a successful bacteria–substrate interaction with complex and significant influence on the lifestyle of the bacterium. Chitin is one of the most abundant polymers on earth and possibly the most abundant in the aquatic environment, where its association with V. cholerae has provided the microorganism with a number of advantages, including food availability, adaptation to environmental nutrient gradients, tolerance to stress and protection from predators. Emergent properties of V. cholerae–chitin interactions occur at multiple hierarchical levels in the environment and include cell metabolic and physiological responses e.g. chemotaxis, cell multiplication, induction of competence, biofilm formation, commensal and symbiotic relationship with higher organisms, cycling of nutrients, and pathogenicity for humans and aquatic animals. As factors mediating virulence of V. cholerae for humans and aquatic animals derive from mechanisms of adaptation to its environment, at different levels of hierarchical scale, V. cholerae interactions with chitin represent a useful model for examination of the role of primary habitat selection in the development of traits that have been identified as virulence factors in human disease.

H (div) preconditioning for a mixed finite element formulation of the stochastic diffusion problem - Elman, Howard; Furnival, D. G; Powell, C. E (Citeseer, 2008)

Hosting virtual networks on commodity hardware - Bhatia,S.; Motiwala,M.; Muhlbauer,W.; Valancius,V.; Bavier,A.; Feamster, Nick; Peterson,L.; Rexford,J. (Georgia Institute of Technology, 2008)
This paper describes Trellis, a software platform for hostingmultiple virtual networks on shared commodity hardware. Trellis allows each virtual network to define its own topol- ogy, control protocols, and forwarding tables, which low- ers the barrier for deploying custom services on an isolated, reconfigurable, and programmable network, while amor- tizing costs by sharing the physical infrastructure. Trellis synthesizes two container-based virtualization technologies, VServer and NetNS, as well as a new tunneling mechanism, EGRE, into a coherent platform that enables high-speed vir- tual networks. We describe the design and implementation, of Trellis, including kernel-level performance optimizations, and evaluate its supported packet-forwarding rates against other virtualization technologies. We are in the process of upgrading the VINI facility to use Trellis. We also plan to release Trellis as part of MyVINI, a standalone software dis- tribution that allows researchers and application developers to deploy their own virtual network hosting platforms.

Implicit Flows: Can’t Live with ‘Em, Can’t Live without ‘Em - King,Dave; Hicks,Boniface; Hicks, Michael W.; Jaeger,Trent (Information Systems SecurityInformation Systems Security, 2008)
Verifying that programs trusted to enforce security actually do so is a practical concern for programmers and administrators. However, there is a disconnect between the kinds of tools that have been successfully applied to real software systems (such as taint mode in Perl and Ruby), and information-flow compilers that enforce a variant of the stronger security property of noninterference. Tools that have been successfully used to find security violations have focused on explicit flows of information, where high-security information is directly leaked to output. Analysis tools that enforce noninterference also prevent implicit flows of information, where high-security information can be inferred from a program’s flow of control. However, these tools have seen little use in practice, despite the stronger guarantees that they provide. To better understand why, this paper experimentally investigates the explicit and implicit flows identified by the standard algorithm for establishing noninterference. When applied to implementations of authentication and cryptographic functions, the standard algorithm discovers many real implicit flows of information, but also reports an extremely high number of false alarms, most of which are due to conservative handling of unchecked exceptions (e.g., null pointer exceptions). After a careful analysis of all sources of true and false alarms, due to both implicit and explicit flows, the paper concludes with some ideas to improve the false alarm rate, toward making stronger security analysis more practical.

Inconsistency management policies - Martinez,M. V; Parisi,F.; Pugliese, A.; Simari,G. I; V.S. Subrahmanian (Proc. 2008 Intl. Conference on Knowledge Representation and Reasoning (KR 2008), 2008)
Though there is much work on how inconsistency indatabases should be managed, there is good reason to believe that end users will want to bring their domain expertise and needs to bear in how to deal with inconsistencies. In this paper, we propose the concept of inconsistency management policies (IMPs). We show that IMPs are rich enough to spec- ify many types of inconsistency management methods pro- posed previously, but provide end users with tools that allow them to use the policies that they want. Our policies are also capable of allowing inconsistency to persist in the database or of eliminating more than a minimal subset of tuples involved in the inconsistency. We present a formal axiomatic definition of IMPs and present appropriate complexity results, together with results linking different IMPs together. We extend the relational algebra (RA) to incorporate IMPs and present the- oretical results showing how IMPs and classical RA operators interact.

Integrating statistics and visualization: case studies of gaining clarity during exploratory data analysis - Perer,Adam; Shneiderman, Ben (Proceedings of the twenty-sixth annual SIGCHI conference on Human factors in computing systems, 2008)
Although both statistical methods and visualizations have been used by network analysts, exploratory data analysis remains a challenge. We propose that a tight integration of these technologies in an interactive exploratory tool could dramatically speed insight development. To test the power of this integrated approach, we created a novel social network analysis tool, SocialAction, and conducted four long-term case studies with domain experts, each working on unique data sets with unique problems. The structured replicated case studies show that the integrated approach in SocialAction led to significant discoveries by a political analyst, a bibliometrician, a healthcare consultant, and a counter-terrorism researcher. Our contributions demonstrate that the tight integration of statistics and visualizations improves exploratory data analysis, and that our evaluation methodology for long-term case studies captures the research strategies of data analysts.
Keywords: case studies; Evaluation; exploratory data analysis; Information Visualization; social networks; Statistics

Interactive auditory data exploration: A framework and evaluation with geo-referenced data sonification - Zhao,H.; Plaisant, Catherine; Shneiderman, Ben; Lazar,J. (ACM Transactions on Computer-Human Interaction, 2008)
We describe an Action-by-Design-Component (ADC) framework to guide auditory interface designers for exploratory data analysis. The framework characterizes data interaction in the auditory mode as a set of Auditory Information Seeking Actions (AISAs). Contrasting AISAs with actions in visualizations, the framework also discusses design considerations for a set of Design Components to support AISAs. Applying the framework to geo-referenced data, we systematically explored and evaluated its design space. A data exploration tool, iSonic, was built for blind users. In depth case studies with 7 blind users, with over 42 hours of data collection, showed that iSonic enabled them to find facts and discover trends of geo-referenced data, even in unfamiliar geographical contexts, without special devices. The results also showed that blind users dramatically benefited from the rich set of task-oriented actions (AISAs) and the use of multiple highly coordinated data views provided by the ADC framework. Some widely used techniques in visualization, with appropriate adaptation, also work in the auditory mode. The application of the framework to scatterplots shows that the framework can be generalized and lead to the design of a unified auditory workspace for general exploratory data analysis. Readers can view a supplementary video demonstration of iSonic by visiting www.cs.umd.edu/hcil/iSonic/

A Java3D framework for inspecting and segmenting 3D models - De Floriani, Leila; Papaleo,Laura; Carissimi,Nicoló (Proceedings of the 13th international symposium on 3D web technology, 2008)
Models of 3D objects have become widely accessible in several disciplines within academia and industry, spanning from scientific visualization to entertainment. In the last few years, 3D models are often organized into digital libraries accessible over the network, and thus semantic annotation of such models becomes an important issue. A fundamental step in annotating a 3D model is to segment it into meaningful parts. In this work, we present a Java3D framework for inspecting and segmenting 3D objects represented in X3D format. In particular, we present a combination of segmentation and merging techniques for producing a feasible decomposition of the boundary of a 3D object. We represent such decomposition as a graph, that we call the segmentation graph which is the basis for semantic annotation. We describe also the interface we have developed to allow visualization and browsing of both the decomposition and the segmentation graph in order to understand the topological structure of the resulting decomposition.
Keywords: Java3D; object manipulation; Object segmentation; shape semantics; X3D

Kernel integral images: A framework for fast non-uniform filtering - Hussein,M.; Porikli, F.; Davis, Larry S. (Computer Vision and Pattern Recognition, 2008. CVPR 2008. IEEE Conference on, 2008)
Integral images are commonly used in computer vision and computer graphics applications. Evaluation of box filters via integral images can be performed in constant time, regardless of the filter size. Although Heckbert (1986) extended the integral image approach for more complex filters, its usage has been very limited, in practice. In this paper, we present an extension to integral images that allows for application of a wide class of non-uniform filters. Our approach is superior to Heckbertpsilas in terms of precision requirements and suitability for parallelization. We explain the theoretical basis of the approach and instantiate two concrete examples: filtering with bilinear interpolation, and filtering with approximated Gaussian weighting. Our experiments show the significant speedups we achieve, and the higher accuracy of our approach compared to Heckbertpsilas.
Keywords: approximated; equations; interpolation; filtering; bilinear; filtering; kernel; Gaussian; graphics; computer; images; approximation; integral; interpolation; computer; nonuniform; processing; integral; theory; filtering; theory; image; vision; fast; weighting

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

More Than Meets the Eye: Transforming the User Experience of Home Network Management - Poole, Erika Shehan; Marshini Chetty; Grinter, Rebecca E.; Edwards, W. Keith (Proceedings of the 7th ACM conference on Designing interactive systems, 2008)
As computing migrates from the workplace to the home, householders must tackle problems of home network maintenance. Often they lack the technical knowledge or motivation to complete these tasks, making the user experience of home network maintenance frustrating. In response to these difficulties, many householders rely on handwritten reminders or interactive networking tools that are ill-suited for the home environment. In this paper, we seek to understand how to design better home network management tools through a study of sketches created by 40 people in 18 households. In our study, we obtained information about householders' knowledge, practices and needs with respect to home networking. Based on our results, we present guidelines for transforming the user experience of home network management.
Keywords: home networks; sketching; troubleshooting

Mutations in the Hydrophobic Core of Ubiquitin Differentially Affect Its Recognition by Receptor Proteins - Haririnia,Aydin; Verma,Rati; Purohit,Nisha; Twarog,Michael Z.; Deshaies,Raymond J.; Bolon,Dan; Fushman, David (Journal of Molecular Biology, 2008)
Ubiquitin (Ub) is one of the most highly conserved signaling proteins in eukaryotes. In carrying out its myriad functions, Ub conjugated to substrate proteins interacts with dozens of receptor proteins that link the Ub signal to various biological outcomes. Here we report mutations in conserved residues of Ub's hydrophobic core that have surprisingly potent and specific effects on molecular recognition. Mutant Ubs bind tightly to the Ub-associated domain of the receptor proteins Rad23 and hHR23A but fail to bind the Ub-interacting motif present in the receptors Rpn10 and S5a. Moreover, chains assembled on target substrates with mutant Ubs are unable to support substrate degradation by the proteasome in vitro or sustain viability of yeast cells. The mutations have relatively little effect on Ub's overall structure but reduce its rigidity and cause a slight displacement of the C-terminal β-sheet, thereby compromising association with Ub-interacting motif but not with Ub-associated domains. These studies emphasize an unexpected role for Ub's core in molecular recognition and suggest that the diversity of protein–protein interactions in which Ub engages placed enormous constraints on its evolvability.
Keywords: hydrophobic core mutation; molecular recognition; proteasomal degradation; ubiquitin; ubiquitin receptors

A new multiresolution generalized directional filter bank design and application in image enhancement - Patel, Vishal M.; Easley,G. R; Healy,D. M (15th IEEE International Conference on Image Processing, 2008. ICIP 2008, 2008)
In this paper, we present an image enhancement technique based on a new multiscale generalized directional filter bank design. The design presented is a shift-invariant overcomplete representation, which is well suited to extracting geometric features such as edges. Special cases of this design method can be made to reduce to different and improved implementations of the shearlet and the contourlet transforms, which are known to represent certain classes of images optimally. Use of this new filter bank design has proven itself competitive in image restoration for noisy images and is well suited for distinguishing noise from weak edges. Experimental results show that our unique image enhancement technique out-performs wavelet and contourlet based enhancement methods.
Keywords: Algorithm design and analysis; Approximation error; Channel bank filters; contourlet transform; Design methodology; Discrete transforms; Feature extraction; Filter bank; Frequency; geometric feature extraction; Image Enhancement; IMAGE PROCESSING; image resolution; image restoration; Multidimensional digital filters; Multidimensional systems; multiresolution generalized directional filter bank design; shearlet transform; shift-invariant overcomplete representation; transforms; Wavelet transforms

NewsStand: a new view on news - Teitler,Benjamin E.; Lieberman,Michael D.; Panozzo,Daniele; Sankaranarayanan,Jagan; Samet, Hanan; Sperling,Jon (Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, 2008)
News articles contain a wealth of implicit geographic content that if exposed to readers improves understanding of today's news. However, most articles are not explicitly geotagged with their geographic content, and few news aggregation systems expose this content to users. A new system named NewsStand is presented that collects, analyzes, and displays news stories in a map interface, thus leveraging on their implicit geographic content. NewsStand monitors RSS feeds from thousands of online news sources and retrieves articles within minutes of publication. It then extracts geographic content from articles using a custom-built geotagger, and groups articles into story clusters using a fast online clustering algorithm. By panning and zooming in NewsStand's map interface, users can retrieve stories based on both topical significance and geographic region, and see substantially different stories depending on position and zoom level.
Keywords: clustering; geotagging; knowledge discovery; text mining

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

Pooled ANOVA - Last,Michael; Luta,Gheorghe; Orso,Alex; Porter, Adam; Young,Stan (Computational Statistics & Data Analysis, 2008)
We introduce Pooled ANOVA, a greedy algorithm to sequentially select the rare important factors from a large set of factors. Problems such as computer simulations and software performance tuning involve a large number of factors, few of which have an important effect on the outcome or performance measure. We pool multiple factors together, and test the pool for significance. If the pool has a significant effect we retain the factors for deconfounding. If not, we either declare that none of the factors are important, or retain them for follow-up decoding, depending on our assumptions and stage of testing. The sparser important factors are, the bigger the savings. Pooled ANOVA requires fewer assumptions than other, similar methods (e.g. sequential bifurcation), such as not requiring all important effects to have the same sign. We demonstrate savings of 25%-35% when compared to a conventional ANOVA, and also the ability to work in a setting where Sequential Bifurcation fails.

Promoting Insight-Based Evaluation of Visualizations: From Contest to Benchmark Repository - Plaisant, Catherine; Fekete,J.-D.; Grinstein,G. (Visualization and Computer Graphics, IEEE Transactions on, 2008)
Information visualization (InfoVis) is now an accepted and growing field, but questions remain about the best uses for and the maturity of novel visualizations. Usability studies and controlled experiments are helpful, but generalization is difficult. We believe that the systematic development of benchmarks will facilitate the comparison of techniques and help identify their strengths under different conditions. We were involved in the organization and management of three InfoVis contests for the 2003, 2004, and 2005 IEEE InfoVis Symposia, which requested teams to report on insights gained while exploring data. We give a summary of the state of the art of evaluation in InfoVis, describe the three contests, summarize their results, discuss outcomes and lessons learned, and conjecture the future of visualization contests. All materials produced by the contests are archived in the InfoVis benchmark repository.
Keywords: Computer-Assisted; Software; Software Validation; User-Computer Interface; Factual; Evaluation Studies as Topic; Image Interpretation; InfoVis contest; benchmark repository; information visualization; data visualisation; Algorithms; Benchmarking; Computer Graphics; Databases

The Randomized Coloring Procedure with Symmetry-Breaking - Pemmaraju,Sriram; Srinivasan, Aravind (Automata, Languages and ProgrammingAutomata, Languages and Programming, 2008)
A basic randomized coloring procedure has been used in probabilistic proofs to obtain remarkably strong results on graph coloring. These results include the asymptotic version of the List Coloring Conjecture due to Kahn, the extensions of Brooks’ Theorem to sparse graphs due to Kim and Johansson, and Luby’s fast parallel and distributed algorithms for graph coloring. The most challenging aspect of a typical probabilistic proof is showing adequate concentration bounds for key random variables. In this paper, we present a simple symmetry-breaking augmentation to the randomized coloring procedure that works well in conjunction with Azuma’s Martingale Inequality to easily yield the requisite concentration bounds. We use this approach to obtain a number of results in two areas: frugal coloring and weighted equitable coloring . A β-frugal coloring of a graph G is a proper vertex-coloring of G in which no color appears more than β times in any neighborhood. Let G = ( V , E ) be a vertex-weighted graph with weight function w : V →[0, 1] and let W = ∑ v ∈ V w ( v ). A weighted equitable coloring of G is a proper k -coloring such that the total weight of every color class is “large”, i.e., “not much smaller” than W / k ; this notion is useful in obtaining tail bounds for sums of dependent random variables.

A range of indicators for the evaluation of state health department Web-based data query systems - Plaisant, Catherine (Issues in Evaluating Health Department Web-based Data Query Systems: Working Papers, 2008)
This chapter explores the wide range of possible indicators (also called metrics) that can be used toevaluate state health department Web-based data query systems (WDQS). While the list of indicators we propose is not exhaustive, it strives to cast a wide net on the range of issues that should be considered when evaluating WDQS, from the richness of functionalities provided by the WDQS, to the usability of the WDQS, the level of human resources required to develop and maintain the WDQS, and the frequency and intensity of WDQS use.

The role of metacognition in robust AI systems - Schmill,M. D; Oates,T.; Anderson,M.; Fults,S.; Josyula,D.; Perlis, Don; Wilson,S. (AAAI-08 Workshop on Metareasoning,(Chicago, IL), 2008)

Role of transposable elements in trypanosomatids - Bringaud,Frédéric; Ghedin,Elodie; El‐Sayed, Najib M.; Papadopoulou,Barbara (Microbes and Infection, 2008)
Transposable elements constitute 2-5% of the genome content in trypanosomatid parasites. Some of them are involved in critical cellular functions, such as the regulation of gene expression in Leishmania spp. In this review, we highlight the remarkable role extinct transposable elements can play as the source of potential new functions.
Keywords: Cellular function; Domestication; Evolution; Gene expression; Leishmania; Regulation of mRNA stability; Retroposon; Transposable element; Trypanosoma

Scaffolding and Validation of Bacterial Genome Assemblies Using Optical Restriction Maps - Nagarajan,Niranjan; Read,Timothy D.; Pop, Mihai (Bioinformatics, 2008)
Motivation: New, high-throughput sequencing technologies have made it feasible to cheaply generate vast amounts of sequence information from a genome of interest. The computational reconstruction of the complete sequence of a genome is complicated by specific features of these new sequencing technologies, such as the short length of the sequencing reads and absence of mate-pair information. In this article we propose methods to overcome such limitations by incorporating information from optical restriction maps.Results: We demonstrate the robustness of our methods to sequencing and assembly errors using extensive experiments on simulated datasets. We then present the results obtained by applying our algorithms to data generated from two bacterial genomes Yersinia aldovae and Yersinia kristensenii. The resulting assemblies contain a single scaffold covering a large fraction of the respective genomes, suggesting that the careful use of optical maps can provide a cost-effective framework for the assembly of genomes. Availability: The tools described here are available as an open-source package at ftp://ftp.cbcb.umd.edu/pub/software/soma Contact: mpop@umiacs.umd.edu

Scaling RDF with Time - Pugliese,Andrea; Udrea,Octavian; V.S. Subrahmanian (Proceedings of the 17th international conference on World Wide Web, 2008)
The World Wide Web Consortium's RDF standard primarily consists of (subject, property, object) triples that specify the value that a given subject has for a given property. However, it is frequently the case that even for a fixed subject and property, the value varies with time. As a consequence, efforts have been made to annotate RDF triples with "valid time" intervals. However, to date, no proposals exist for efficient indexing of such temporal RDF databases. It is clearly beneficial to store RDF data in a relational DB - however, standard relational indexes are inadequately equipped to handle RDF's graph structure. In this paper, we propose the tGRIN index structure that builds a specialized index for temporal RDF that is physically stored in an RDBMS. Past efforts to store RDF in relational stores include Jena2 from HP, Sesame from OpenRDF.org, and 3store from the University of Southampton. We show that even when these efforts are augmented with well known temporal indexes like R+ trees, SR-trees, ST-index, and MAP21, the tGRIN index exhibits superior performance. In terms of index build time, tGRIN takes two thirds or less of the time used by any other system, and it uses a comparable amount of memory and less disk space than Jena, Sesame and 3store. More importantly, tGRIN can answer queries three to six times faster for average query graph patterns and five to ten times faster for complex queries than these systems.
Keywords: RDF indexing; resource description framework; temporal RDF

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

A self-help guide for autonomous systems - Anderson,M. L; Fults,S.; Josyula,D. P; Oates,T.; Perlis, Don; Wilson,S.; Wright,D. (AI Magazine, 2008)

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

Systematic yet flexible discovery: guiding domain experts through exploratory data analysis - Perer,Adam; Shneiderman, Ben (Proceedings of the 13th international conference on Intelligent user interfaces, 2008)
During exploratory data analysis, visualizations are often useful for making sense of complex data sets. However, as data sets increase in size and complexity, static information visualizations decrease in comprehensibility. Interactive techniques can yield valuable discoveries, but current data analysis tools typically support only opportunistic exploration that may be inefficient and incomplete. We present a refined architecture that uses systematic yet flexible (SYF) design goals to guide domain expert users through complex exploration of data over days, weeks and months. The SYF system aims to support exploratory data analysis with some of the simplicity of an e-commerce check-out while providing added flexibility to pursue insights. The SYF system provides an overview of the analysis process, suggests unexplored states, allows users to annotate useful states, supports collaboration, and enables reuse of successful strategies. The affordances of the SYF system are demonstrated by integrating it into a social network analysis tool employed by social scientists and intelligence analysts. The SYF system is a tool-independent component and can be incorporated into other data analysis tools.
Keywords: exploratory data analysis; guides; Information Visualization; social networks; systematic yet flexible; wizards

A topic-based Document Correlation Model - Jia,Xi-Ping; Peng,Hong; Zheng,Qi-Lun; Zhuolin Jiang; Li,Zhao (Machine Learning and Cybernetics, 2008 International Conference on, 2008)
Document correlation analysis is now a focus of study in text mining. This paper proposed a Document Correlation Model to capture the correlation between documents from topic level. The model represents the document correlation as the Optimal Matching of a bipartite graph, of which each partition is a document, each node is a topic, and each edge is the similarity between two topics. The topics of each document are retrieved by the Latent Dirichlet Allocation model and Gibbs sampling. Experiments on correlated document search show that the Document Correlation Model outperforms the Vector Space Model on two aspects: 1) it has higher average retrieval precision; 2) it needs less space to store a documentpsilas information.
Keywords: bipartite graph optimal matching; data mining; document correlation analysis; document retrieval; Gibbs sampling; Information retrieval; latent Dirichlet allocation model; text analysis; text mining; topic-based document correlation model

Towards Design and Fabrication of a Miniature MRI-Compatible Robot for Applications in Neurosurgery - Pappafotis,Nicholas; Bejgerowski,Wojciech; Gullapalli,Rao; Simard,J. Marc; Gupta, Satyandra K.; Desai,Jaydev P. (ASME, 2008)
Brain tumors are among the most feared complications of cancer and they occur in 20–40% of adult cancer patients. Despite numerous advances in treatment, the prognosis for these patients is poor, with a median survival of 4–8 months. The primary reasons for poor survival rate are the lack of good continuous imaging modality for intraoperative intracranial procedures and the inability to remove the complete tumor tissue due to its placement in the brain and the corresponding space constraints to reach it. Intraoperative magnetic resonance imaging (MRI) supplements the surgeon's visual and tactile senses in a way that no other imaging device can achieve resulting in less trauma to surrounding healthy brain tissue during surgery. To minimize the trauma to surrounding healthy brain tissue, it would be beneficial to operate through a narrow surgical corridor dissected by the neurosurgeon. Facilitating tumor removal by accessing regions outside the direct “line-of-sight” of the neurosurgical corridor will require a highly dexterous, small cross section, and MRI-compatible robot. Developing such a robot is extremely challenging task. In this paper we report a preliminary design of 6-DOF robot for possible application in neurosurgery. The robot actuators and body parts are constructed from MRI compatible materials. The current prototype is 0.36” in diameter and weighs only 0.0289 N (2.95 grams). The device was actuated using Flexinol® which is a shape memory alloy manufactured by Dynalloy, Inc. The end-effector forces ranged from 12 mN to 50 mN depending on the robot configuration. The end-effector force to robot weight ratio varied from 0.41 to 1.73. During trials the robot motion was repeatable and the range of motion of the robot was about 90 degrees for the end-effector when one side shape memory alloy (SMA) channel was actuated. The actuation time from the start to finish was about 2.5 s.

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

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

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