@article {20313, title = {Genomic Methods and Microbiological Technologies for Profiling Novel and Extreme Environments for the Extreme Microbiome Project (XMP)}, journal = {Journal of Biomolecular Techniques : JBT}, volume = {28}, year = {2017}, month = {Jan-04-2017}, pages = {31 - 39}, abstract = {The Extreme Microbiome Project (XMP) is a project launched by the Association of Biomolecular Resource Facilities Metagenomics Research Group (ABRF MGRG) that focuses on whole genome shotgun sequencing of extreme and unique environments using a wide variety of biomolecular techniques. The goals are multifaceted, including development and refinement of new techniques for the following: 1) the detection and characterization of novel microbes, 2) the evaluation of nucleic acid techniques for extremophilic samples, and 3) the identification and implementation of the appropriate bioinformatics pipelines. Here, we highlight the different ongoing projects that we have been working on, as well as details on the various methods we use to characterize the microbiome and metagenome of these complex samples. In particular, we present data of a novel multienzyme extraction protocol that we developed, called Polyzyme or MetaPolyZyme. Presently, the XMP is characterizing sample sites around the world with the intent of discovering new species, genes, and gene clusters. Once a project site is complete, the resulting data will be publically available. Sites include Lake Hillier in Western Australia, the {\textquotedblleft}Door to Hell{\textquotedblright} crater in Turkmenistan, deep ocean brine lakes of the Gulf of Mexico, deep ocean sediments from Greenland, permafrost tunnels in Alaska, ancient microbial biofilms from Antarctica, Blue Lagoon Iceland, Ethiopian toxic hot springs, and the acidic hypersaline ponds in Western Australia.}, issn = {1524-0215}, doi = {10.7171/jbt.17-2801-004}, url = {https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5345951/}, author = {Tighe, Scott and Afshinnekoo, Ebrahim and Rock, Tara M. and McGrath, Ken and Alexander, Noah and McIntyre, Alexa and Ahsanuddin, Sofia and Bezdan, Daniela and Green, Stefan J. and Joye, Samantha and Stewart Johnson, Sarah and Baldwin, Don A. and Bivens, Nathan and Ajami, Nadim and Carmical, Joseph R. and Herriott, Ian Charold and Rita R Colwell and Donia, Mohamed and Foox, Jonathan and Greenfield, Nick and Hunter, Tim and Hoffman, Jessica and Hyman, Joshua and Jorgensen, Ellen and Krawczyk, Diana and Lee, Jodie and Levy, Shawn and Garcia-Reyero, {\`a}lia and Settles, Matthew and Thomas, Kelley and {\'o}mez, Felipe and Schriml, Lynn and Kyrpides, Nikos and Zaikova, Elena and Penterman, Jon and Mason, Christopher E.} } @article {20365, title = {Global diarrhoea action plan needs integrated climate-based surveillance}, journal = {The Lancet Global Health}, volume = {2}, year = {2014}, month = {Jan-02-2014}, pages = {e69 - e70}, issn = {2214109X}, doi = {10.1016/S2214-109X(13)70155-4}, url = {https://linkinghub.elsevier.com/retrieve/pii/S2214109X13701554}, author = {Akanda, Ali S and Jutla, Antarpreet S and Rita R Colwell} } @article {16266, title = {GAGE: A Critical Evaluation of Genome Assemblies and Assembly Algorithms}, journal = {Genome Research}, volume = {22}, year = {2012}, month = {2012}, pages = {557 - 567}, abstract = {New sequencing technology has dramatically altered the landscape of whole-genome sequencing, allowing scientists to initiate numerous projects to decode the genomes of previously unsequenced organisms. The lowest-cost technology can generate deep coverage of most species, including mammals, in just a few days. The sequence data generated by one of these projects consist of millions or billions of short DNA sequences (reads) that range from 50 to 150 nt in length. These sequences must then be assembled de novo before most genome analyses can begin. Unfortunately, genome assembly remains a very difficult problem, made more difficult by shorter reads and unreliable long-range linking information. In this study, we evaluated several of the leading de novo assembly algorithms on four different short-read data sets, all generated by Illumina sequencers. Our results describe the relative performance of the different assemblers as well as other significant differences in assembly difficulty that appear to be inherent in the genomes themselves. Three overarching conclusions are apparent: first, that data quality, rather than the assembler itself, has a dramatic effect on the quality of an assembled genome; second, that the degree of contiguity of an assembly varies enormously among different assemblers and different genomes; and third, that the correctness of an assembly also varies widely and is not well correlated with statistics on contiguity. To enable others to replicate our results, all of our data and methods are freely available, as are all assemblers used in this study.}, doi = {10.1101/gr.131383.111}, url = {http://genome.cshlp.org/content/22/3/557}, author = {Salzberg,Steven L. and Phillippy,Adam M and Zimin,Aleksey and Puiu,Daniela and Magoc,Tanja and Koren,Sergey and Treangen,Todd J and Schatz,Michael C and Delcher,Arthur L. and Roberts,Michael and Mar{\c c}ais,Guillaume and Pop, Mihai and Yorke,James A.} } @article {16267, title = {Gene Prediction with Glimmer for Metagenomic Sequences Augmented by Classification and Clustering}, journal = {Nucleic Acids ResearchNucl. Acids Res.}, volume = {40}, year = {2012}, month = {2012/01/01/}, pages = {e9-e9 - e9-e9}, abstract = {Environmental shotgun sequencing (or metagenomics) is widely used to survey the communities of microbial organisms that live in many diverse ecosystems, such as the human body. Finding the protein-coding genes within the sequences is an important step for assessing the functional capacity of a metagenome. In this work, we developed a metagenomics gene prediction system Glimmer-MG that achieves significantly greater accuracy than previous systems via novel approaches to a number of important prediction subtasks. First, we introduce the use of phylogenetic classifications of the sequences to model parameterization. We also cluster the sequences, grouping together those that likely originated from the same organism. Analogous to iterative schemes that are useful for whole genomes, we retrain our models within each cluster on the initial gene predictions before making final predictions. Finally, we model both insertion/deletion and substitution sequencing errors using a different approach than previous software, allowing Glimmer-MG to change coding frame or pass through stop codons by predicting an error. In a comparison among multiple gene finding methods, Glimmer-MG makes the most sensitive and precise predictions on simulated and real metagenomes for all read lengths and error rates tested.}, isbn = {0305-1048, 1362-4962}, doi = {10.1093/nar/gkr1067}, url = {http://nar.oxfordjournals.org/content/40/1/e9}, author = {Kelley,David R and Liu,Bo and Delcher,Arthur L. and Pop, Mihai and Salzberg,Steven L.} } @article {20374, title = {Genetic characteristics of drug-resistant Vibrio cholerae O1 causing endemic cholera in Dhaka, 2006-2011}, journal = {Journal of Medical Microbiology}, year = {2012}, month = {Jan-12-2012}, pages = {1736 - 1745}, abstract = {Vibrio cholerae O1 biotype El Tor (ET), causing the seventh cholera pandemic, was recently replaced in Bangladesh by an altered ET possessing ctxB of the Classical (CL) biotype, which caused the first six cholera pandemics. In the present study, V. cholerae O1 strains associated with endemic cholera in Dhaka between 2006 and 2011 were analysed for major phenotypic and genetic characteristics. Of 54 representative V. cholerae isolates tested, all were phenotypically ET and showed uniform resistance to trimethoprim/sulfamethoxazole (SXT) and furazolidone (FR). Resistance to tetracycline (TE) and erythromycin (E) showed temporal fluctuation, varying from year to year, while all isolates were susceptible to gentamicin (CN) and ciprofloxacin (CIP). Year-wise data revealed erythromycin resistance to be 33.3 \% in 2006 and 11 \% in 2011, while tetracycline resistance accounted for 33, 78, 0, 100 and 27 \% in 2006, 2007, 2008, 2009 and 2010, respectively; interestingly, all isolates tested were sensitive to TE in 2011, as observed in 2008. All V. cholerae isolates tested possessed genetic elements such as SXT, ctxAB, tcpA ET, rstR ET and rtxC; none had IntlI (Integron I). Double mismatch amplification mutation assay (DMAMA)-PCR followed by DNA sequencing and analysis of the ctxB gene revealed a point mutation at position 58 (C{\textrightarrow}A), which has resulted in an amino acid substitution from histidine (H) to asparagine (N) at position 20 (genotype 7) since 2008. Although the multi-resistant strains having tetracycline resistance showed minor genetic divergence, V. choleraestrains were clonal, as determined by a PFGE (NotI)-based dendrogram. This study shows 2008{\textendash}2010 to be the time of transition from ctxB genotype 1 to genotype 7 in V. cholerae ET causing endemic cholera in Dhaka, Bangladesh.}, issn = {0022-2615}, doi = {10.1099/jmm.0.049635-0}, url = {http://jmm.microbiologyresearch.org/content/journal/jmm/10.1099/jmm.0.049635-0}, author = {Rashed, S. M. and Mannan, S. B. and Johura, F.-T. and Islam, M. T. and Sadique, A. and Watanabe, H. and Sack, R. B. and Huq, A. and Rita R Colwell and Cravioto, A. and Alam, M.} } @article {20384, title = {Genomic analysis of ICE Vch Ban8: An atypical genetic element in Vibrio cholerae}, journal = {FEBS Letters}, year = {2012}, month = {Apr-06-2012}, pages = {1617 - 1621}, abstract = {Genomic islands (GIs) and integrative conjugative elements (ICEs) are major players in bacterial evolution since they encode genes involved in adaptive functions of medical or environmental importance. Here we performed the genomic analysis of ICEVchBan8, an unusual ICE found in the genome of a clinical non-toxigenic Vibrio cholerae O37 isolate. ICEVchBan8 shares most of its genetic structure with SXT/R391 ICEs. However, this ICE codes for a different integration/excision module is located at a different insertion site, and part of its genetic cargo shows homology to other pathogenicity islands of V. cholerae.}, doi = {10.1016/j.febslet.2012.03.064}, url = {http://doi.wiley.com/10.1016/j.febslet.2012.03.064}, author = {Taviani, Elisa and Spagnoletti, Matteo and Ceccarelli, Daniela and Haley, Bradd J. and Hasan, Nur A. and Chen, Arlene and Colombo, Mauro M. and Huq, Anwar and Rita R Colwell} } @article {20386, title = {Genomic diversity of 2010 Haitian cholera outbreak strains}, journal = {Proceedings of the National Academy of Sciences}, year = {2012}, month = {05/2012}, pages = {E2010 - E2017}, issn = {0027-8424}, doi = {10.1073/pnas.1207359109}, url = {http://www.pnas.org/cgi/doi/10.1073/pnas.1207359109}, author = {Hasan, N. A. and Choi, S. Y. and Eppinger, M. and Clark, P. W. and Chen, A. and Alam, M. and Haley, B. J. and Taviani, E. and Hine, E. and Su, Q. and Tallon, L. J. and Prosper, J. B. and Furth, K. and Hoq, M. M. and Li, H. and Fraser-Liggett, C. M. and Cravioto, A. and Huq, A. and Ravel, J. and Cebula, T. A. and Rita R Colwell} } @article {19718, title = {Genomic insights to SAR86, an abundant and uncultivated marine bacterial lineage.}, journal = {ISME J}, volume = {6}, year = {2012}, month = {2012 Jun}, pages = {1186-99}, abstract = {

Bacteria in the 16S rRNA clade SAR86 are among the most abundant uncultivated constituents of microbial assemblages in the surface ocean for which little genomic information is currently available. Bioinformatic techniques were used to assemble two nearly complete genomes from marine metagenomes and single-cell sequencing provided two more partial genomes. Recruitment of metagenomic data shows that these SAR86 genomes substantially increase our knowledge of non-photosynthetic bacteria in the surface ocean. Phylogenomic analyses establish SAR86 as a basal and divergent lineage of γ-proteobacteria, and the individual genomes display a temperature-dependent distribution. Modestly sized at 1.25-1.7 Mbp, the SAR86 genomes lack several pathways for amino-acid and vitamin synthesis as well as sulfate reduction, trends commonly observed in other abundant marine microbes. SAR86 appears to be an aerobic chemoheterotroph with the potential for proteorhodopsin-based ATP generation, though the apparent lack of a retinal biosynthesis pathway may require it to scavenge exogenously-derived pigments to utilize proteorhodopsin. The genomes contain an expanded capacity for the degradation of lipids and carbohydrates acquired using a wealth of tonB-dependent outer membrane receptors. Like the abundant planktonic marine bacterial clade SAR11, SAR86 exhibits metabolic streamlining, but also a distinct carbon compound specialization, possibly avoiding competition.

}, keywords = {Computational Biology, Gammaproteobacteria, Genome, Bacterial, Genomic Library, metagenomics, Oceans and Seas, Phylogeny, plankton, Rhodopsin, RNA, Ribosomal, 16S, Seawater}, issn = {1751-7370}, doi = {10.1038/ismej.2011.189}, author = {Dupont, Chris L and Rusch, Douglas B and Yooseph, Shibu and Lombardo, Mary-Jane and Richter, R Alexander and Valas, Ruben and Novotny, Mark and Yee-Greenbaum, Joyclyn and Jeremy D Selengut and Haft, Dan H and Halpern, Aaron L and Lasken, Roger S and Nealson, Kenneth and Friedman, Robert and Venter, J Craig} } @article {19660, title = {Global secretome analysis identifies novel mediators of bone metastasis}, journal = {Cell Research}, volume = {22}, year = {2012}, month = {2012/09//}, pages = {1339 - 1355}, abstract = {Bone is the one of the most common sites of distant metastasis of solid tumors. Secreted proteins are known to influence pathological interactions between metastatic cancer cells and the bone stroma. To comprehensively profile secreted proteins associated with bone metastasis, we used quantitative and non-quantitative mass spectrometry to globally analyze the secretomes of nine cell lines of varying bone metastatic ability from multiple species and cancer types. By comparing the secretomes of parental cells and their bone metastatic derivatives, we identified the secreted proteins that were uniquely associated with bone metastasis in these cell lines. We then incorporated bioinformatic analyses of large clinical metastasis datasets to obtain a list of candidate novel bone metastasis proteins of several functional classes that were strongly associated with both clinical and experimental bone metastasis. Functional validation of selected proteins indicated that in vivo bone metastasis can be promoted by high expression of (1) the salivary cystatins CST1, CST2, and CST4; (2) the plasminogen activators PLAT and PLAU; or (3) the collagen functionality proteins PLOD2 and COL6A1. Overall, our study has uncovered several new secreted mediators of bone metastasis and therefore demonstrated that secretome analysis is a powerful method for identification of novel biomarkers and candidate therapeutic targets.}, keywords = {bone, cancer, metastasis, proteomics, secretome}, isbn = {1001-0602}, url = {http://www.nature.com/cr/journal/v22/n9/abs/cr201289a.html}, author = {Blanco, Mario Andres and LeRoy, Gary and Zia Khan and Ale{\v c}kovi{\'c}, Ma{\v s}a and Zee, Barry M. and Garcia, Benjamin A. and Kang, Yibin} } @article {15917, title = {Gradient-based Image Recovery Methods from Incomplete Fourier Measurements}, journal = {IEEE Transactions on Image Processing}, volume = {PP}, year = {2012}, month = {2012///}, pages = {1 - 1}, abstract = {A major problem in imaging applications such as Magnetic Resonance Imaging (MRI) and Synthetic Aperture Radar (SAR) is the task of trying to reconstruct an image with the smallest possible set of Fourier samples, every single one of which has a potential time and/or power cost. The theory of Compressive Sensing (CS) points to ways of exploiting inherent sparsity in such images in order to achieve accurate recovery using sub- Nyquist sampling schemes. Traditional CS approaches to this problem consist of solving total-variation minimization programs with Fourier measurement constraints or other variations thereof. This paper takes a different approach: Since the horizontal and vertical differences of a medical image are each more sparse or compressible than the corresponding total-variational image, CS methods will be more successful in recovering these differences individually. We develop an algorithm called GradientRec that uses a CS algorithm to recover the horizontal and vertical gradients and then estimates the original image from these gradients. We present two methods of solving the latter inverse problem: one based on least squares optimization and the other based on a generalized Poisson solver. After a thorough derivation of our complete algorithm, we present the results of various experiments that compare the effectiveness of the proposed method against other leading methods.}, keywords = {Compressed sensing, Fourier transforms, Image coding, Image edge detection, Image reconstruction, L1{\textendash}minimization, minimization, Noise measurement, OPTIMIZATION, Poisson solver, Sparse recovery, Total variation, TV}, isbn = {1057-7149}, doi = {10.1109/TIP.2011.2159803}, author = {Patel, Vishal M. and Maleh,R. and Gilbert,A. C and Chellapa, Rama} } @article {12419, title = {Grammatical structures for word-level sentiment detection}, journal = {North American Association of Computational Linguistics}, year = {2012}, month = {2012///}, abstract = {Existing work in fine-grained sentiment anal- ysis focuses on sentences and phrases but ig- nores the contribution of individual words and their grammatical connections. This is because of a lack of both (1) annotated data at the word level and (2) algorithms that can leverage syn- tactic information in a principled way. We ad- dress the first need by annotating articles from the information technology business press via crowdsourcing to provide training and testing data. To address the second need, we propose a suffix-tree data structure to represent syntac- tic relationships between opinion targets and words in a sentence that are opinion-bearing. We show that a factor graph derived from this data structure acquires these relationships with a small number of word-level features. We demonstrate that our supervised model per- forms better than baselines that ignore syntac- tic features and constraints.}, author = {Jordan Boyd-Graber and Sayeed,Asad B. and Rusk,Bryan and Weinberg, Amy} } @article {15427, title = {Grey-box GUI Testing: Efficient Generation of Event Sequences}, journal = {arXiv:1205.4928}, year = {2012}, month = {2012/05/22/}, abstract = {Graphical user interfaces (GUIs), due to their event driven nature, present a potentially unbounded space of all possible ways to interact with software. During testing it becomes necessary to effectively sample this space. In this paper we develop algorithms that sample the GUI{\textquoteright}s input space by only generating sequences that (1) are allowed by the GUI{\textquoteright}s structure, and (2) chain together only those events that have data dependencies between their event handlers. We create a new abstraction, called an event-dependency graph (EDG) of the GUI, that captures data dependencies between event handler code. We develop a mapping between EDGs and an existing black-box user-level model of the GUI{\textquoteright}s workflow, called an event-flow graph (EFG). We have implemented automated EDG construction in a tool that analyzes the bytecode of each event handler. We evaluate our "grey-box" approach using four open-source applications and compare it with the current state-of-the-art EFG approach. Our results show that using the EDG reduces the number of test cases while still achieving at least the same coverage. Furthermore, we were able to detect 2 new bugs in the subject applications.}, keywords = {68N30, Computer Science - Software Engineering}, url = {http://arxiv.org/abs/1205.4928}, author = {Arlt,Stephan and Banerjee,Ishan and Bertolini,Cristiano and Memon, Atif M. and Sch{\"a}f,Martin} } @conference {18848, title = {Gripper synthesis for indirect manipulation of cells using Holographic Optical Tweezers}, year = {2012}, month = {2012/05//}, pages = {2749 - 2754}, abstract = {Optical Tweezers (OT) are used for highly accurate manipulations of biological cells. However, the direct exposure of cells to focused laser beam may negatively influence their biological functions. In order to overcome this problem, we generate multiple optical traps to grab and move a 3D ensemble of inert particles such as silica microspheres to act as a reconfigurable gripper for a manipulated cell. The relative positions of the microspheres are important in order for the gripper to be robust against external environmental forces and the exposure of high intensity laser on the cell to be minimized. In this paper, we present results of different gripper configurations, experimentally tested using our OT setup, that provide robust gripping as well as minimize laser intensity experienced by the cell. We developed a computational approach that allowed us to perform preliminary modeling and synthesis of the gripper configurations. The gripper synthesis is cast as a multi-objective optimization problem.}, doi = {10.1109/ICRA.2012.6225153}, author = {Chowdhury,Sagar and Svec,Petr and Wang,Chenlu and Losert,Wolfgang and Gupta, Satyandra K.} } @book {15187, title = {GameSec{\textquoteright}11: Proceedings of the Second international conference on Decision and Game Theory for Security}, year = {2011}, month = {2011///}, publisher = {Springer-Verlag}, organization = {Springer-Verlag}, address = {Berlin, Heidelberg}, isbn = {978-3-642-25279-2}, editor = {Baras,John S and Katz, Jonathan and Altman,Eitan} } @article {14613, title = {Gene Coexpression Network Topology of Cardiac Development, Hypertrophy, and FailureClinical Perspective}, journal = {Circulation: Cardiovascular GeneticsCirc Cardiovasc Genet}, volume = {4}, year = {2011}, month = {2011/02/01/}, pages = {26 - 35}, abstract = {Background{\textemdash} Network analysis techniques allow a more accurate reflection of underlying systems biology to be realized than traditional unidimensional molecular biology approaches. Using gene coexpression network analysis, we define the gene expression network topology of cardiac hypertrophy and failure and the extent of recapitulation of fetal gene expression programs in failing and hypertrophied adult myocardium.Methods and Results{\textemdash} We assembled all myocardial transcript data in the Gene Expression Omnibus (n=1617). Because hierarchical analysis revealed species had primacy over disease clustering, we focused this analysis on the most complete (murine) dataset (n=478). Using gene coexpression network analysis, we derived functional modules, regulatory mediators, and higher-order topological relationships between genes and identified 50 gene coexpression modules in developing myocardium that were not present in normal adult tissue. We found that known gene expression markers of myocardial adaptation were members of upregulated modules but not hub genes. We identified ZIC2 as a novel transcription factor associated with coexpression modules common to developing and failing myocardium. Of 50 fetal gene coexpression modules, 3 (6\%) were reproduced in hypertrophied myocardium and 7 (14\%) were reproduced in failing myocardium. One fetal module was common to both failing and hypertrophied myocardium. Conclusions{\textemdash} Network modeling allows systems analysis of cardiovascular development and disease. Although we did not find evidence for a global coordinated program of fetal gene expression in adult myocardial adaptation, our analysis revealed specific gene expression modules active during both development and disease and specific candidates for their regulation. }, keywords = {fetal, Gene expression, heart failure, hypertrophy, myocardium}, isbn = {1942-325X, 1942-3268}, doi = {10.1161/CIRCGENETICS.110.941757}, url = {http://circgenetics.ahajournals.org/content/4/1/26}, author = {Dewey,Frederick E and Perez,Marco V and Wheeler,Matthew T and Watt,Clifton and Spin,Joshua and Langfelder,Peter and Horvath,Steve and Hannenhalli, Sridhar and Cappola,Thomas P. and Ashley,Euan A} } @article {14619, title = {Genome-Wide Survey of Natural Selection on Functional, Structural, and Network Properties of Polymorphic Sites in Saccharomyces Paradoxus}, journal = {Molecular Biology and EvolutionMol Biol Evol}, volume = {28}, year = {2011}, month = {2011/09/01/}, pages = {2615 - 2627}, abstract = {Background. To characterize the genetic basis of phenotypic evolution, numerous studies have identified individual genes that have likely evolved under natural selection. However, phenotypic changes may represent the cumulative effect of similar evolutionary forces acting on functionally related groups of genes. Phylogenetic analyses of divergent yeast species have identified functional groups of genes that have evolved at significantly different rates, suggestive of differential selection on the functional properties. However, due to environmental heterogeneity over long evolutionary timescales, selection operating within a single lineage may be dramatically different, and it is not detectable via interspecific comparisons alone. Moreover, interspecific studies typically quantify selection on protein-coding regions using the Dn/Ds ratio, which cannot be extended easily to study selection on noncoding regions or synonymous sites. The population genetic-based analysis of selection operating within a single lineage ameliorates these limitations. Findings. We investigated selection on several properties associated with genes, promoters, or polymorphic sites, by analyzing the derived allele frequency spectrum of single nucleotide polymorphisms (SNPs) in 28 strains of Saccharomyces paradoxus. We found evidence for significant differential selection between many functionally relevant categories of SNPs, underscoring the utility of function-centric approaches for discovering signatures of natural selection. When comparable, our findings are largely consistent with previous studies based on interspecific comparisons, with one notable exception: our study finds that mutations from an ancient amino acid to a relatively new amino acid are selectively disfavored, whereas interspecific comparisons have found selection against ancient amino acids. Several of our findings have not been addressed through prior interspecific studies: we find that synonymous mutations from preferred to unpreferred codons are selected against and that synonymous SNPs in the linker regions of proteins are relatively less constrained than those within protein domains. Conclusions. We present the first global survey of selection acting on various functional properties in S. paradoxus. We found that selection pressures previously detected over long evolutionary timescales have also shaped the evolution of S. paradoxus. Importantly, we also make novel discoveries untenable via conventional interspecific analyses.}, keywords = {derived allele frequency, Evolution, natural selection, yeast}, isbn = {0737-4038, 1537-1719}, doi = {10.1093/molbev/msr085}, url = {http://mbe.oxfordjournals.org/content/28/9/2615}, author = {Vishnoi,Anchal and Sethupathy,Praveen and Simola,Daniel and Plotkin,Joshua B. and Hannenhalli, Sridhar} } @conference {14497, title = {G-PARE: A visual analytic tool for comparative analysis of uncertain graphs}, booktitle = {Visual Analytics Science and Technology (VAST), 2011 IEEE Conference on}, year = {2011}, month = {2011///}, pages = {61 - 70}, author = {Sharara,H. and Sopan,A. and Namata,G. and Getoor, Lise and Singh,L.} } @conference {13294, title = {GPU algorithms for diamond-based multiresolution terrain processing}, booktitle = {Eurographics Symposium on Parallel Graphics and Visualization}, year = {2011}, month = {2011///}, pages = {10 - 11}, abstract = {We present parallel algorithms for processing, extracting and rendering adaptively sampled regular terraindatasets represented as a multiresolution model defined by a super-square-based diamond hierarchy. This model represents a terrain as a nested triangle mesh generated through a series of longest edge bisections and encoded in an implicit hierarchical structure, which clusters triangles into diamonds and diamonds into super-squares. We decompose the problem into three parallel algorithms for performing: generation of the diamond hierarchy from a regularly distributed terrain dataset, selective refinement on the diamond hierarchy and generation of the corre- sponding crack-free triangle mesh for processing and rendering. We avoid the data transfer bottleneck common to previous approaches by processing all data entirely on the GPU. We demonstrate that this parallel approach can be successfully applied to interactive terrain visualization with a high tessellation quality on commodity GPUs. }, author = {Yal{\c c}{\i}n,M. A. and Weiss,K. and De Floriani, Leila} } @article {17180, title = {Graph Analytics-Lessons Learned and Challenges Ahead}, volume = {31}, year = {2011}, month = {2011///}, pages = {18 - 29}, abstract = {Graph analytics is one of the most influential and important R\&D topics in the visual analytics community. Researchers with diverse backgrounds from information visualization, human-computer interaction, computer graphics, graph drawing, and data mining have pursued graph analytics from scientific, technical, and social approaches. These studies have addressed both distinct and common challenges. Past successes and mistakes can provide valuable lessons for revising the research agenda. In this article, six researchers from four academic and research institutes identify graph analytics{\textquoteright} fundamental challenges and present both insightful lessons learned from their experience and good practices in graph analytics research. The goal is to critically assess those lessons and shed light on how they can stimulate research and draw attention to grand challenges for graph analytics. The article also establishes principles that could lead to measurable standards and criteria for research.}, keywords = {citation analysis, citespace, Computer Graphics, document analysis, graphics and multimedia, greengrid, jigsaw system, modeling, power grid analysis, semantic substrates, simulation, social networks, text analysis, Visualization}, isbn = {0272-1716}, author = {Wong,Pak Chung and Chen,Chaomei and Gorg,Carsten and Shneiderman, Ben and Stasko,John and Thomas,Jim} } @conference {17181, title = {Group-in-a-Box Layout for Multi-faceted Analysis of Communities}, booktitle = {Privacy, Security, Risk and Trust (PASSAT), 2011 IEEE Third International Conference on and 2011 IEEE Third International Confernece on Social Computing (SocialCom)}, year = {2011}, month = {2011/10/09/11}, pages = {354 - 361}, publisher = {IEEE}, organization = {IEEE}, abstract = {Communities in social networks emerge from interactions among individuals and can be analyzed through a combination of clustering and graph layout algorithms. These approaches result in 2D or 3D visualizations of clustered graphs, with groups of vertices representing individuals that form a community. However, in many instances the vertices have attributes that divide individuals into distinct categories such as gender, profession, geographic location, and similar. It is often important to investigate what categories of individuals comprise each community and vice-versa, how the community structures associate the individuals from the same category. Currently, there are no effective methods for analyzing both the community structure and the category-based partitions of social graphs. We propose Group-In-a-Box (GIB), a meta-layout for clustered graphs that enables multi-faceted analysis of networks. It uses the tree map space filling technique to display each graph cluster or category group within its own box, sized according to the number of vertices therein. GIB optimizes visualization of the network sub-graphs, providing a semantic substrate for category-based and cluster-based partitions of social graphs. We illustrate the application of GIB to multi-faceted analysis of real social networks and discuss desirable properties of GIB using synthetic datasets.}, keywords = {Algorithm design and analysis, category based social graph partitions, clustered graphs, clustering, Clustering algorithms, Communities, data visualisation, force-directed, gender, geographic location, graph layout algorithms, graph theory, group-in-a-box, group-in-a-box layout, Image edge detection, Layout, meta-layout, multifaceted community analysis, network subgraph visualization, network visualization, pattern clustering, profession, semantic substrates, Social network services, social networking (online), social networks, treemap space filling technique, Visualization}, isbn = {978-1-4577-1931-8}, doi = {10.1109/PASSAT/SocialCom.2011.139}, author = {Rodrigues,E.M. and Milic-Frayling,N. and Smith,M. and Shneiderman, Ben and Hansen,D.} } @article {15477, title = {GUI Interaction Testing: Incorporating Event Context}, journal = {Software Engineering, IEEE Transactions on}, volume = {37}, year = {2011}, month = {2011/08//july}, pages = {559 - 574}, abstract = {Graphical user interfaces (GUIs), due to their event-driven nature, present an enormous and potentially unbounded way for users to interact with software. During testing, it is important to $\#$x201C;adequately cover $\#$x201D; this interaction space. In this paper, we develop a new family of coverage criteria for GUI testing grounded in combinatorial interaction testing. The key motivation of using combinatorial techniques is that they enable us to incorporate $\#$x201C;context $\#$x201D; into the criteria in terms of event combinations, sequence length, and by including all possible positions for each event. Our new criteria range in both efficiency (measured by the size of the test suite) and effectiveness (the ability of the test suites to detect faults). In a case study on eight applications, we automatically generate test cases and systematically explore the impact of context, as captured by our new criteria. Our study shows that by increasing the event combinations tested and by controlling the relative positions of events defined by the new criteria, we can detect a large number of faults that were undetectable by earlier techniques.}, keywords = {automatic test case generation, automatic test pattern generation, combinatorial interaction testing, event driven nature, graphical user interface, Graphical user interfaces, GUI interaction testing, program testing}, isbn = {0098-5589}, doi = {10.1109/TSE.2010.50}, author = {Xun Yuan and Cohen,M. B and Memon, Atif M.} } @inbook {19194, title = {GasSense: Appliance-Level, Single-Point Sensing of Gas Activity in the Home}, booktitle = {Pervasive Computing}, series = {Lecture Notes in Computer Science}, volume = {6030}, year = {2010}, month = {2010}, pages = {265 - 282}, publisher = {Springer Berlin / Heidelberg}, organization = {Springer Berlin / Heidelberg}, abstract = {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{\textquoteright}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.}, isbn = {978-3-642-12653-6}, url = {http://dx.doi.org/10.1007/978-3-642-12654-3_16}, author = {Cohn,Gabe and Gupta,Sidhant and Jon Froehlich and Larson,Eric and Patel,Shwetak}, editor = {Flor{\'e}en,Patrik and Kr{\"u}ger,Antonio and Spasojevic,Mirjana} } @conference {13559, title = {GEDI - AGroundtruthing Environment for Document Images}, booktitle = {Ninth IAPRInternational Workshop on Document Analysis Systems (DAS 2010)}, year = {2010}, month = {2010///}, abstract = {In this paper, we describe a freely available highly configurable document image annotation tool called GEDI {\textendash} Groundtruthing Environment for Document Images. Its basic structure involves two types of files, an Image file, and a corresponding .xml file in GEDI format. When users begin ground truthing an image, they can configure the interface to allow the creation of different types of zones, each of which may have a custom set of {\textquotedblleft}attributes{\textquotedblright}. The output is compatible with the UMDDocLib architecture [2] and has been used in numerous funded and unfunded programs to create datasets in multiple languages. GEDI has been developed and released to the community as a comprehensive tool that we hope will ease the burden of document annotation and encourage additional sharing of data.}, author = {David Doermann and Zotkina,Elena and Huiping Li} } @article {12219, title = {A general framework for efficient geographic routing in wireless networks}, journal = {Computer Networks}, volume = {54}, year = {2010}, month = {2010/04/08/}, pages = {844 - 861}, abstract = {We propose a new link metric called normalized advance (NADV) for geographic routing in multihop wireless networks. NADV selects neighbors with the optimal trade-off between proximity and link cost. Coupled with the local next hop decision in geographic routing, NADV enables an adaptive and efficient cost-aware routing strategy. Depending on the objective or message priority, applications can use the NADV framework to minimize various types of link cost.We present efficient methods for link cost estimation and perform detailed experiments in simulated environments. Our results show that NADV outperforms current schemes in many aspects: for example, in high noise environments with frequent packet losses, the use of NADV leads to 81\% higher delivery ratio. When compared to centralized routing under certain settings, geographic routing using NADV finds paths whose cost is close to the optimum. We also conducted experiments in Emulab testbed and the results demonstrate that our proposed approach performs well in practice. }, keywords = {Geographic routing, Link cost estimation, Routing metric, Wireless multihop networks}, isbn = {1389-1286}, doi = {10.1016/j.comnet.2009.09.013}, url = {http://www.sciencedirect.com/science/article/pii/S1389128609002904}, author = {Lee,Seungjoon and Bhattacharjee, Bobby and Banerjee,Suman and Han,Bo} } @conference {17988, title = {General-purpose vs. gpu: Comparison of many-cores on irregular workloads}, booktitle = {Proceedings of the Second Usenix Workshop on Hot Topics in Parallelism}, year = {2010}, month = {2010///}, pages = {14 - 15}, abstract = {XMT1 is a general-purpose many-core parallel architec-ture. The foremost design objective for XMT was to meet the highest standards for ease of parallel programming. GPUs, on the other hand, have acquired a strong reputa- tion on performance, sometimes at the expense of ease- of-programming. The current paper presents a perfor- mance comparison on diverse workloads between XMT and an NVIDIA CUDA-enabled GPU. Configured with roughly the same amount of chip resources as the GPU, XMT achieves an average speedup of 6.05x on irregu- lar applications, while incurring an average slowdown of 2.07x on regular ones. Namely, XMT comes ahead for significant applications without having to pay a (possibly worthwhile) price for easier programming. This surpris- ing result suggests a yet untapped opportunity: A high- performance easy-to-program general-purpose 1000-core computer. }, author = {Caragea,G.C. and Keceli,F. and Tzannes,A. and Vishkin, Uzi} } @article {15478, title = {Generating Event Sequence-Based Test Cases Using GUI Runtime State Feedback}, journal = {Software Engineering, IEEE Transactions on}, volume = {36}, year = {2010}, month = {2010/02//jan}, pages = {81 - 95}, abstract = {This paper presents a fully automatic model-driven technique to generate test cases for graphical user interfaces (GUIs)-based applications. The technique uses feedback from the execution of a ??seed test suite,?? which is generated automatically using an existing structural event interaction graph model of the GUI. During its execution, the runtime effect of each GUI event on all other events pinpoints event semantic interaction (ESI) relationships, which are used to automatically generate new test cases. Two studies on eight applications demonstrate that the feedback-based technique 1) is able to significantly improve existing techniques and helps identify serious problems in the software and 2) the ESI relationships captured via GUI state yield test suites that most often detect more faults than their code, event, and event-interaction-coverage equivalent counterparts.}, keywords = {automatic model driven technique, event interaction coverage equivalent counterparts, event semantic interaction relationships, event sequence based test cases, Graphical user interfaces, GUI runtime state feedback, program testing, Software quality}, isbn = {0098-5589}, doi = {10.1109/TSE.2009.68}, author = {Xun Yuan and Memon, Atif M.} } @article {13779, title = {Generating Phrasal and Sentential Paraphrases: A Survey of Data-Driven Methods}, journal = {Computational Linguistics}, volume = {36}, year = {2010}, month = {2010///}, pages = {341 - 387}, abstract = {The task of paraphrasing is inherently familiar to speakers of all languages. Moreover, the task of automatically generating or extracting semantic equivalences for the various units of language{\textemdash}words, phrases, and sentences{\textemdash}is an important part of natural language processing (NLP) and is being increasingly employed to improve the performance of several NLP applications. In this article, we attempt to conduct a comprehensive and application-independent survey of data-driven phrasal and sentential paraphrase generation methods, while also conveying an appreciation for the importance and potential use of paraphrases in the field of NLP research. Recent work done in manual and automatic construction of paraphrase corpora is also examined. We also discuss the strategies used for evaluating paraphrase generation techniques and briefly explore some future trends in paraphrase generation.}, isbn = {0891-2017}, doi = {10.1162/coli_a_00002}, url = {http://dx.doi.org/10.1162/coli_a_00002}, author = {Madnani,Nitin and Dorr, Bonnie J} } @article {14584, title = {Genetic and Physiological Activation of Osmosensitive Gene Expression Mimics Transcriptional Signatures of Pathogen Infection in C. elegans}, journal = {PLoS ONEPLoS ONE}, volume = {5}, year = {2010}, month = {2010/02/02/}, pages = {e9010 - e9010}, abstract = {The soil-dwelling nematode C. elegans is a powerful system for comparative molecular analyses of environmental stress response mechanisms. Infection of worms with bacterial and fungal pathogens causes the activation of well-characterized innate immune transcriptional programs in pathogen-exposed hypodermal and intestinal tissues. However, the pathophysiological events that drive such transcriptional responses are not understood. Here, we show that infection-activated transcriptional responses are, in large part, recapitulated by either physiological or genetic activation of the osmotic stress response. Microarray profiling of wild type worms exposed to non-lethal hypertonicity identified a suite of genes that were also regulated by infection. Expression profiles of five different osmotic stress resistant (osr) mutants under isotonic conditions reiterated the wild type transcriptional response to osmotic stress and also showed substantial similarity to infection-induced gene expression under isotonic conditions. Computational, transgenic, and functional approaches revealed that two GATA transcription factors previously implicated in infection-induced transcriptional responses, elt-2 and elt-3, are also essential for coordinated tissue-specific activation of osmosensitive gene expression and promote survival under osmotically stressful conditions. Together, our data suggest infection and osmotic adaptation share previously unappreciated transcriptional similarities which might be controlled via regulation of tissue-specific GATA transcription factors.}, doi = {10.1371/journal.pone.0009010}, url = {http://dx.doi.org/10.1371/journal.pone.0009010}, author = {Rohlfing,Anne-Katrin and Miteva,Yana and Hannenhalli, Sridhar and Lamitina,Todd} } @article {12871, title = {Genome Sequence of Hybrid Vibrio Cholerae O1 MJ-1236, B-33, and CIRS101 and Comparative Genomics with V. Cholerae}, journal = {Journal of BacteriologyJ. Bacteriol.}, volume = {192}, year = {2010}, month = {2010/07/01/}, pages = {3524 - 3533}, abstract = {The genomes of Vibrio cholerae O1 Matlab variant MJ-1236, Mozambique O1 El Tor variant B33, and altered O1 El Tor CIRS101 were sequenced. All three strains were found to belong to the phylocore group 1 clade of V. cholerae, which includes the 7th-pandemic O1 El Tor and serogroup O139 isolates, despite displaying certain characteristics of the classical biotype. All three strains were found to harbor a hybrid variant of CTXΦ and an integrative conjugative element (ICE), leading to their establishment as successful clinical clones and the displacement of prototypical O1 El Tor. The absence of strain- and group-specific genomic islands, some of which appear to be prophages and phage-like elements, seems to be the most likely factor in the recent establishment of dominance of V. cholerae CIRS101 over the other two hybrid strains.}, isbn = {0021-9193, 1098-5530}, doi = {10.1128/JB.00040-10}, url = {http://jb.asm.org/content/192/13/3524}, author = {Grim,Christopher J. and Hasan,Nur A. and Taviani,Elisa and Haley,Bradd and Jongsik Chun and Brettin,Thomas S. and Bruce,David C. and Detter,J. Chris and Han,Cliff S. and Chertkov,Olga and Challacombe,Jean and Huq,Anwar and Nair,G. Balakrish and Rita R Colwell} } @article {19094, title = {Genomic characterization of the Yersinia genus}, journal = {Genome biology}, volume = {11}, year = {2010}, month = {2010}, author = {Chen, P.E. and Cook, C. and Stewart, A.C. and Nagarajan,N. and Sommer, D.D. and Pop, Mihai and Thomason, B. and Thomason, M.P.K. and Lentz, S. and Nolan, N. and others} } @conference {13262, title = {A geometric approach to curvature estimation on triangulated 3D shapes}, booktitle = {Int. Conf. on Computer Graphics Theory and Applications (GRAPP)}, year = {2010}, month = {2010///}, pages = {90 - 95}, abstract = {We present a geometric approach to define discrete normal, principal, Gaussian and mean curvatures, thatwe call Ccurvature. Our approach is based on the notion of concentrated curvature of a polygonal line and a simulation of rotation of the normal plane of the surface at a point. The advantages of our approach is its simplicity and its natural meaning. A comparison with widely-used discrete methods is presented. }, author = {Mesmoudi,M. M. and De Floriani, Leila and Magillo,P.} } @conference {16825, title = {Geotagging: using proximity, sibling, and prominence clues to understand comma groups}, booktitle = {Proceedings of the 6th Workshop on Geographic Information Retrieval}, series = {GIR {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {6:1{\textendash}6:8 - 6:1{\textendash}6:8}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Geotagging is the process of recognizing textual references to geographic locations, known as toponyms, and resolving these references by assigning each lat/long values. Typical geotagging algorithms use a variety of heuristic evidence to select the correct interpretation for each toponym. A study is presented of one such heuristic which aids in recognizing and resolving lists of toponyms, referred to as comma groups. Comma groups of toponyms are recognized and resolved by inferring the common threads that bind them together, based on the toponyms{\textquoteright} shared geographic attributes. Three such common threads are proposed and studied --- population-based prominence, distance-based proximity, and sibling relationships in a geographic hierarchy --- and examples of each are noted. In addition, measurements are made of these comma groups{\textquoteright} usage and variety in a large dataset of news articles, indicating that the proposed heuristics, and in particular the proximity and sibling heuristics, are useful for resolving comma group toponyms.}, keywords = {comma groups, geotagging, toponyms}, isbn = {978-1-60558-826-1}, doi = {10.1145/1722080.1722088}, url = {http://doi.acm.org/10.1145/1722080.1722088}, author = {Lieberman,Michael D. and Samet, Hanan and Sankaranayananan,Jagan} } @conference {16819, title = {Geotagging with local lexicons to build indexes for textually-specified spatial data}, booktitle = {Data Engineering (ICDE), 2010 IEEE 26th International Conference on}, year = {2010}, month = {2010/03//}, pages = {201 - 212}, abstract = {The successful execution of location-based and feature-based queries on spatial databases requires the construction of spatial indexes on the spatial attributes. This is not simple when the data is unstructured as is the case when the data is a collection of documents such as news articles, which is the domain of discourse, where the spatial attribute consists of text that can be (but is not required to be) interpreted as the names of locations. In other words, spatial data is specified using text (known as a toponym) instead of geometry, which means that there is some ambiguity involved. The process of identifying and disambiguating references to geographic locations is known as geotagging and involves using a combination of internal document structure and external knowledge, including a document-independent model of the audience{\textquoteright}s vocabulary of geographic locations, termed its spatial lexicon. In contrast to previous work, a new spatial lexicon model is presented that distinguishes between a global lexicon of locations known to all audiences, and an audience-specific local lexicon. Generic methods for inferring audiences{\textquoteright} local lexicons are described. Evaluations of this inference method and the overall geotagging procedure indicate that establishing local lexicons cannot be overlooked, especially given the increasing prevalence of highly local data sources on the Internet, and will enable the construction of more accurate spatial indexes.}, keywords = {data;Internet;data, databases;, databases;spatial, document, indexes;spatial, information, Internet;document-independent, knowledge;feature-based, lexicon, lexicons;location-based, locations;geotagging;inference, method;internal, methods;geographic, mining;geographic, model;external, model;textually-specified, queries;generic, queries;spatial, spatial, structure;local, systems;visual}, doi = {10.1109/ICDE.2010.5447903}, author = {Lieberman,M.D. and Samet, Hanan and Sankaranarayanan,J.} } @article {17179, title = {Getting serious about social media: strategies for increasing civic participation}, journal = {Proceedings of HCI}, year = {2010}, month = {2010///}, author = {Shneiderman, Ben} } @article {17970, title = {Global Contours}, volume = {CS-TR-4957}, year = {2010}, month = {2010/05/05/}, institution = {Department of Computer Science, University of Maryland, College Park}, abstract = {We present a multi-scale approach that uses Laplacian eigenvectorsto extract globally significant contours from an image. The input images are mapped into the Laplacian space by using Laplacian eigenvectors. This mapping causes globally significant pixels along the contours to expand in the Laplacian space. The measure of the expansion is used to compute the Global Contours. We apply our scheme to real color images and compare it with several other methods that compute image and color saliency. The contours calculated by our method reflect global properties of the image and are complementary to classic center-surround image saliency methods. We believe that hybrid image saliency algorithms that combine our method of Global Contours with center-surround image saliency algorithms will be able to better characterize the most important regions of images than those from just using contours calculated using bottom-up approaches. }, keywords = {Technical Report}, url = {http://drum.lib.umd.edu/handle/1903/10072}, author = {Bista, Sujal and Varshney, Amitabh} } @article {13958, title = {GPUML: Graphical processors for speeding up kernel machines}, journal = {Workshop on High Performance Analytics-Algorithms, Implementations, and Applications}, year = {2010}, month = {2010///}, abstract = {Algorithms based on kernel methods play a central rolein statistical machine learning. At their core are a num- ber of linear algebra operations on matrices of kernel functions which take as arguments the training and test- ing data. These range from the simple matrix-vector product, to more complex matrix decompositions, and iterative formulations of these. Often the algorithms scale quadratically or cubically, both in memory and op- erational complexity, and as data sizes increase, kernel methods scale poorly. We use parallelized approaches on a multi-core graphical processor (GPU) to partially address this lack of scalability. GPUs are used to scale three different classes of problems, a simple kernel- matrix-vector product, iterative solution of linear sys- tems of kernel function and QR and Cholesky decom- position of kernel matrices. Application of these accel- erated approaches in scaling several kernel based learn- ing approaches are shown, and in each case substantial speedups are obtained. The core software is released as an open source package, GPUML. }, author = {Srinivasan,B.V. and Hu,Q. and Duraiswami, Ramani} } @conference {18218, title = {Gradient descent approach for secure localization in resource constrained wireless sensor networks}, booktitle = {Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on}, year = {2010}, month = {2010/03//}, pages = {1854 - 1857}, abstract = {Many sensor network related applications require precise knowledge of the location of constituent nodes. In these applications, it is desirable for the wireless nodes to be able to autonomously determine their locations before they start sensing and transmitting data. Most localization algorithms rely on anchor nodes whose locations are known to determine the positions of the remaining nodes. In an adversarial scenario, some of these anchor nodes could be compromised and used to transmit misleading information aimed at preventing the accurate localization of the remaining sensors. In this paper, a computationally efficient algorithm to determine the location of sensors that can resist such attacks is described. The proposed algorithm combines gradient descent with a selective pruning of inconsistent measurements to achieve good localization accuracy. Simulation results show that the proposed algorithm has performance comparable to existing schemes while requiring less computational resources.}, keywords = {algorithms;resource, approach;localization, computational, constrained, descent, localization;gradient, methods;wireless, networks;, networks;secure, resources;gradient, sensor, wireless}, doi = {10.1109/ICASSP.2010.5495371}, author = {Garg,R. and Varna,A.L. and M. Wu} } @article {14370, title = {Graph Identification}, journal = {Advances in Intelligent Data Analysis IX: 9th International Symposium}, year = {2010}, month = {2010///}, pages = {6 - 6}, abstract = {There is a growing amount of observational data describing networks{\textendash} examples include social networks, communication networks, and biological networks. As the amount of available data increases, so has our interest in analyzing these networks in order to uncover (1) general laws that govern their structure and evolution, and (2) patterns and predictive models to develop better policies and practices. However, a fundamental challenge in dealing with this newly available observational data describing networks is that the data is often of dubious quality{\textendash}it is noisy and incomplete{\textendash}and before any analysis method can be applied, the data must be cleaned, missing information inferred and mistakes corrected. Skipping this cleaning step can lead to flawed conclusions for things as simple as degree distribution and centrality measures; for more complex analytic queries, the results are even more likely to be inaccurate and misleading.}, doi = {10.1007/978-3-642-13062-5_2}, author = {Getoor, Lise} } @conference {17751, title = {A graph-theoretic approach to protect static and moving targets from adversaries}, booktitle = {Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1}, series = {AAMAS {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {299 - 306}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, organization = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, abstract = {The static asset protection problem (SAP) in a road network is that of allocating resources to protect vertices, given any possible behavior by an adversary determined to attack those assets. The dynamic asset protection (DAP) problem is a version of SAP where the asset is following a fixed and widely known route (e.g., a parade route) and needs to be protected. We formalize what it means for a given allocation of resources to be "optimal" for protecting a desired set of assets, and show that randomly allocating resources to a single edge cut in the road network solves this problem. Unlike SAP, we show that DAP is not only an NP-complete problem, but that approximating DAP is also NP-hard. We provide the GreedyDAP heuristic algorithm to solve DAP and show experimentally that it works well in practice, using road network data for real cities.}, keywords = {adversarial reasoning, agent systems, game theory}, isbn = {978-0-9826571-1-9}, url = {http://dl.acm.org/citation.cfm?id=1838206.1838248}, author = {Dickerson,J. P. and Simari,G. I and V.S. Subrahmanian and Kraus,Sarit} } @conference {12484, title = {Group motion segmentation using a Spatio-Temporal Driving Force Model}, booktitle = {Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on}, year = {2010}, month = {2010/06//}, pages = {2038 - 2045}, abstract = {We consider the {\textquoteleft}group motion segmentation{\textquoteright} problem and provide a solution for it. The group motion segmentation problem aims at analyzing motion trajectories of multiple objects in video and finding among them the ones involved in a {\textquoteleft}group motion pattern{\textquoteright}. This problem is motivated by and serves as the basis for the {\textquoteleft}multi-object activity recognition{\textquoteright} problem, which is currently an active research topic in event analysis and activity recognition. Specifically, we learn a Spatio-Temporal Driving Force Model to characterize a group motion pattern and design an approach for segmenting the group motion. We illustrate the approach using videos of American football plays, where we identify the offensive players, who follow an offensive motion pattern, from motions of all players in the field. Experiments using GaTech Football Play Dataset validate the effectiveness of the segmentation algorithm.}, keywords = {activity, American, analysis;image, dataset;group, driving, football, force, model;image, MOTION, pattern;group, play, plays;GaTech, problem;spatiotemporal, recognition, recognition;image, segmentation;, segmentation;motion, trajectories;multiobject}, doi = {10.1109/CVPR.2010.5539880}, author = {Ruonan Li and Chellapa, Rama} } @article {15073, title = {A group signature scheme from lattice assumptions}, journal = {Advances in Cryptology-ASIACRYPT 2010}, year = {2010}, month = {2010///}, pages = {395 - 412}, abstract = {Group signature schemes allow users to sign messages on behalf of a group while (1) maintaining anonymity (within that group) with respect to an outside observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assumption), in the random oracle model. Towards our goal, we construct a new algorithm for sampling a basis for an orthogonal lattice, together with a trapdoor, that may be of independent interest.}, doi = {10.1007/978-3-642-17373-8_23}, author = {Gordon,S. and Katz, Jonathan and Vaikuntanathan,V.} } @conference {14446, title = {Growing a tree in the forest: constructing folksonomies by integrating structured metadata}, booktitle = {Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining}, series = {KDD {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {949 - 958}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {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}, isbn = {978-1-4503-0055-1}, doi = {10.1145/1835804.1835924}, url = {http://doi.acm.org/10.1145/1835804.1835924}, author = {Plangprasopchok,Anon and Lerman,Kristina and Getoor, Lise} } @conference {18341, title = {GUI testing using computer vision}, booktitle = {Proceedings of the 28th international conference on Human factors in computing systems}, series = {CHI {\textquoteright}10}, year = {2010}, month = {2010///}, pages = {1535 - 1544}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Testing a GUI{\textquoteright}s visual behavior typically requires human testers to interact with the GUI and to observe whether the expected results of interaction are presented. This paper presents a new approach to GUI testing using computer vision for testers to automate their tasks. Testers can write a visual test script that uses images to specify which GUI components to interact with and what visual feedback to be observed. Testers can also generate visual test scripts by demonstration. By recording both input events and screen images, it is possible to extract the images of components interacted with and the visual feedback seen by the demonstrator, and generate a visual test script automatically. We show that a variety of GUI behavior can be tested using this approach. Also, we show how this approach can facilitate good testing practices such as unit testing, regression testing, and test-driven development.}, keywords = {gui automation, GUI testing, test by demonstration}, isbn = {978-1-60558-929-9}, doi = {10.1145/1753326.1753555}, url = {http://doi.acm.org/10.1145/1753326.1753555}, author = {Chang,Tsung-Hsiang and Tom Yeh and Miller,Robert C.} } @article {14614, title = {Gene Profiling of Human Adipose Tissue During Evoked Inflammation In Vivo}, journal = {DiabetesDiabetes}, volume = {58}, year = {2009}, month = {2009/10/01/}, pages = {2211 - 2219}, abstract = {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{\textendash}99]) were upregulated (fold changes >1.0) during the lower-dose (LPS 0.6 ng/kg) validation study and 51 of 85 (59\% [49{\textendash}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. }, isbn = {0012-1797, 1939-327X}, doi = {10.2337/db09-0256}, url = {http://diabetes.diabetesjournals.org/content/58/10/2211}, author = {Shah,Rachana and Lu,Yun and Hinkle,Christine C and McGillicuddy,Fiona C and Kim,Roy and Hannenhalli, Sridhar and Cappola,Thomas P. and Heffron,Sean and Wang,XingMei and Mehta,Nehal N and Putt,Mary and Reilly,Muredach P} } @conference {13778, title = {Generating high-coverage semantic orientation lexicons from overtly marked words and a thesaurus}, booktitle = {Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2 - Volume 2}, series = {EMNLP {\textquoteright}09}, year = {2009}, month = {2009///}, pages = {599 - 608}, publisher = {Association for Computational Linguistics}, organization = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA}, abstract = {Sentiment analysis often relies on a semantic orientation lexicon of positive and negative words. A number of approaches have been proposed for creating such lexicons, but they tend to be computationally expensive, and usually rely on significant manual annotation and large corpora. Most of these methods use WordNet. In contrast, we propose a simple approach to generate a high-coverage semantic orientation lexicon, which includes both individual words and multi-word expressions, using only a Roget-like thesaurus and a handful of affixes. Further, the lexicon has properties that support the Polyanna Hypothesis. Using the General Inquirer as gold standard, we show that our lexicon has 14 percentage points more correct entries than the leading WordNet-based high-coverage lexicon (SentiWordNet). In an extrinsic evaluation, we obtain significantly higher performance in determining phrase polarity using our thesaurus-based lexicon than with any other. Additionally, we explore the use of visualization techniques to gain insight into the our algorithm beyond the evaluations mentioned above.}, isbn = {978-1-932432-62-6}, url = {http://dl.acm.org/citation.cfm?id=1699571.1699591}, author = {Mohammad,Saif and Dunne,Cody and Dorr, Bonnie J} } @article {18764, title = {Generating simplified trapping probability models from simulation of optical tweezers system}, journal = {Journal of Computing and Information Science in Engineering}, volume = {9}, year = {2009}, month = {2009///}, pages = {021003 - 021003}, author = {Banerjee,A. G. and Balijepalli,A. and Gupta,S.K. and LeBrun,T. W.} } @article {13780, title = {Generating surveys of scientific paradigms}, journal = {Proceedings of HLT-NAACL}, year = {2009}, month = {2009///}, abstract = {The number of research publications in var-ious disciplines is growing exponentially. Researchers and scientists are increasingly finding themselves in the position of having to quickly understand large amounts of tech- nical material. In this paper we present the first steps in producing an automatically gen- erated, readily consumable, technical survey. Specifically we explore the combination of citation information and summarization tech- niques. Even though prior work (Teufel et al., 2006) argues that citation text is unsuitable for summarization, we show that in the frame- work of multi-document survey creation, cita- tion texts can play a crucial role. }, author = {Mohammad,S. and Dorr, Bonnie J and Egan,M. and Hassan,A. and Muthukrishan,P. and Qazvinian,V. and Radev,D. and Zajic, David} } @article {16269, title = {Genome Assembly Reborn: Recent Computational Challenges}, journal = {Briefings in Bioinformatics}, volume = {10}, year = {2009}, month = {2009/07/01/}, pages = {354 - 366}, abstract = {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}, isbn = {1467-5463, 1477-4054}, doi = {10.1093/bib/bbp026}, url = {http://bib.oxfordjournals.org/content/10/4/354}, author = {Pop, Mihai} } @article {12896, title = {Genome assortment, not serogroup, defines Vibrio cholerae pandemic strains}, journal = {Nature}, year = {2009}, month = {2009///}, abstract = {Vibrio cholerae, the causative agent of cholera, is a bacterium autochthonous to the aquatic environment, and a serious public health threat. V. cholerae serogroup O1 is responsible for the previous two cholera pandemics, in which classical and El Tor biotypes were dominant in the 6th and the current 7th pandemics, respectively. Cholera researchers continually face newly emerging and re-emerging pathogenic clones carrying combinations of new serogroups as well as of phenotypic and genotypic properties. These genotype and phenotype changes have hampered control of the disease. Here we compare the complete genome sequences of 23 strains of V. cholerae isolated from a variety of sources and geographical locations over the past 98 years in an effort to elucidate the evolutionary mechanisms governing genetic diversity and genesis of new pathogenic clones. The genome-based phylogeny revealed 12 distinct V. cholerae phyletic lineages, of which one, designated the V. cholerae core genome (CG), comprises both O1 classical and EI Tor biotypes. All 7th pandemic clones share nearly identical gene content, i.e., the same genome backbone. The transition from 6th to 7th pandemic strains is defined here as a {\textquoteright}shift{\textquoteright} between pathogenic clones belonging to the same O1 serogroup, but from significantly different phyletic lineages within the CG clade. In contrast, transition among clones during the present 7th pandemic period can be characterized as a {\textquoteright}drift{\textquoteright} between clones, differentiated mainly by varying composition of laterally transferred genomic islands, resulting in emergence of variants, exemplified by V.cholerae serogroup O139 and V.cholerae O1 El Tor hybrid clones that produce cholera toxin of classical biotype. Based on the comprehensive comparative genomics presented in this study it is concluded that V. cholerae undergoes extensive genetic recombination via lateral gene transfer, and, therefore, genome assortment, not serogroup, should be used to define pathogenic V. cholerae clones.}, keywords = {59; CHOLERA; GENES; GENETICS; GENOTYPE; ISLANDS; ORIGIN; PHENOTYPE; PUBLIC HEALTH; RECOMBINATION; STRAINS; TOXINS}, url = {http://www.osti.gov/energycitations/servlets/purl/962365-icnke9/}, author = {Brettin,Thomas S[Los Alamos National Laboratory and Bruce,David C[Los Alamos National Laboratory and Challacombe,Jean F[Los Alamos National Laboratory and Detter,John C[Los Alamos National Laboratory and Han,Cliff S[Los Alamos National Laboratory and Munik,A. C[Los Alamos National Laboratory and Chertkov,Olga[Los Alamos National Laboratory and Meincke,Linda[Los Alamos National Laboratory and Saunders,Elizabeth[Los Alamos National Laboratory and Choi,Seon Y[SEOUL NATL UNIV and Haley,Bradd J[U MARYLAND and Taviani,Elisa[U MARYLAND and Jeon,Yoon-Seong[INTL VACCINE INST SEOUL and Kim,Dong Wook[INTL VACCINE INST SEOUL and Lee,Jae-Hak[SEOUL NATL UNIV and Walters,Ronald A[PNNL and Hug,Anwar[NATL INST CHOLERIC ENTERIC DIS and Rita R Colwell} } @inbook {12893, title = {The Genus Vibrio and Related Genera}, booktitle = {Practical handbook of microbiologyPractical handbook of microbiology}, year = {2009}, month = {2009///}, pages = {267 - 267}, publisher = {CRC Press}, organization = {CRC Press}, isbn = {9780849393655}, author = {Rita R Colwell and Chun,J.}, editor = {Goldman,Emanuel and Green,Lorrence H.} } @inbook {19605, title = {Graph Drawing for Security Visualization}, booktitle = {Graph Drawing}, series = {Lecture Notes in Computer Science}, year = {2009}, month = {2009/01/01/}, pages = {2 - 13}, publisher = {Springer Berlin Heidelberg}, organization = {Springer Berlin Heidelberg}, abstract = {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}, isbn = {978-3-642-00218-2, 978-3-642-00219-9}, url = {http://link.springer.com/chapter/10.1007/978-3-642-00219-9_2}, author = {Tamassia, Roberto and Palazzi, Bernardo and Charalampos Papamanthou}, editor = {Tollis, Ioannis G. and Patrignani, Maurizio} } @article {13371, title = {Graphical models for uncertain data}, journal = {Managing and Mining Uncertain Data}, year = {2009}, month = {2009///}, pages = {77 - 77}, author = {Deshpande, Amol and Getoor, Lise and Sen,P.} } @article {16759, title = {GrouPeer: Dynamic clustering of P2P databases}, journal = {Information Systems}, volume = {34}, year = {2009}, month = {2009/03//}, pages = {62 - 86}, abstract = {Sharing structured data in a P2P network is a challenging problem, especially in the absence of a mediated schema. The standard practice of answering a consecutively rewritten query along the propagation path often results in significant loss of information. On the opposite, the use of mediated schemas requires human interaction and global agreement, both during creation and maintenance. In this paper we present GrouPeer, an adaptive, automated approach to both issues in the context of unstructured P2P database overlays. By allowing peers to individually choose which rewritten version of a query to answer and evaluate the received answers, information-rich sources left hidden otherwise are discovered. Gradually, the overlay is restructured as semantically similar peers are clustered together. Experimental results show that our technique produces very accurate answers and builds clusters that are very close to the optimal ones by contacting a very small number of nodes in the overlay.}, keywords = {Peer-to-Peer databases, Query reformulation in P2P databases, Semantics in P2P query answering, Structured data in unstructured P2P overlays}, isbn = {0306-4379}, doi = {16/j.is.2008.04.002}, url = {http://www.sciencedirect.com/science/article/pii/S0306437908000252}, author = {Kantere,Verena and Tsoumakos,Dimitrios and Sellis,Timos and Roussopoulos, Nick} } @article {12975, title = {A GENEALOGICAL APPROACH TO QUANTIFYING LINEAGE DIVERGENCE}, journal = {Evolution}, volume = {62}, year = {2008}, month = {2008/09/01/}, pages = {2411 - 2422}, abstract = {We introduce a statistic, the genealogical sorting index (gsi), for quantifying the degree of exclusive ancestry of labeled groups on a rooted genealogy and demonstrate its application. The statistic is simple, intuitive, and easily calculated. It has a normalized range to facilitate comparisons among different groups, trees, or studies and it provides information on individual groups rather than a composite measure for all groups. It naturally handles polytomies and accommodates measures of uncertainty in phylogenetic relationships. We use coalescent simulations to explore the behavior of the gsi across a range of divergence times, with the mean value increasing to 1, the maximum value when exclusivity within a group reached monophyly. Simulations also demonstrate that the power to reject the null hypothesis of mixed genealogical ancestry increased markedly as sample size increased, and that the gsi provides a statistically more powerful measure of divergence than FST. Applications to data from published studies demonstrated that the gsi provides a useful way to detect significant exclusivity even when groups are not monophyletic. Although we describe this statistic in the context of divergence, it is more broadly applicable to quantify and assess the significance of clustering of observations in labeled groups on any tree.}, keywords = {Ancestral polymorphism, congruence, exclusivity, genealogy, lineage sorting, monophyly, paraphyly, Phylogeny, polyphyly, speciation, species}, isbn = {1558-5646}, doi = {10.1111/j.1558-5646.2008.00442.x}, url = {http://onlinelibrary.wiley.com/doi/10.1111/j.1558-5646.2008.00442.x/abstract}, author = {Cummings, Michael P. and Neel,Maile C and Shaw,Kerry L} } @article {13130, title = {A general method for sensor planning in multi-sensor systems: Extension to random occlusion}, journal = {International Journal of Computer Vision}, volume = {76}, year = {2008}, month = {2008///}, pages = {31 - 52}, abstract = {ystems utilizing multiple sensors are required in many domains. In this paper, we specifically concern ourselves with applications where dynamic objects appear randomly and the system is employed to obtain some user-specified characteristics of such objects. For such systems, we deal with the tasks of determining measures for evaluating their performance and of determining good sensor configurations that would maximize such measures for better system performance.We introduce a constraint in sensor planning that has not been addressed earlier: visibility in the presence of random occluding objects. occlusion causes random loss of object capture from certain necessitates the use of other sensors that have visibility of this object. Two techniques are developed to analyze such visibility constraints: a probabilistic approach to determine {\textquotedblleft}average{\textquotedblright} visibility rates and a deterministic approach to address worst-case scenarios. Apart from this constraint, other important constraints to be considered include image resolution, field of view, capture orientation, and algorithmic constraints such as stereo matching and background appearance. Integration of such constraints is performed via the development of a probabilistic framework that allows one to reason about different occlusion events and integrates different multi-view capture and visibility constraints in a natural way. Integration of the thus obtained capture quality measure across the region of interest yields a measure for the effectiveness of a sensor configuration and maximization of such measure yields sensor configurations that are best suited for a given scenario. The approach can be customized for use in many multi-sensor applications and our contribution is especially significant for those that involve randomly occurring objects capable of occluding each other. These include security systems for surveillance in public places, industrial automation and traffic monitoring. Several examples illustrate such versatility by application of our approach to a diverse set of different and sometimes multiple system objectives. }, author = {Mittal,A. and Davis, Larry S.} } @article {16717, title = {Generalizing Word Lattice Translation}, year = {2008}, month = {2008/02//}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {Word lattice decoding has proven useful in spoken language translation; we argue that it provides a compelling model for translation of text genres, as well. We extend lattice decoding to hierarchical phrase-based models, providing a unified treatment with phrase-based decoding by treating lattices as a case of weighted finite-state automata. In the process, we resolve a significant complication that lattice representations introduce in reordering models. Our experiments evaluating the approach demonstrate substantial gains for Chinese-English and Arabic-English translation.}, keywords = {*MACHINE TRANSLATION, *STATISTICAL MACHINE TRANSLATION, *WORD LATTICE TRANSLATION, grammars, HIERARCHICAL PHRASE-BASED MODELS, linguistics, MODELS, STATISTICAL PROCESSES}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA481994}, author = {Dyer,Christopher and Muresan,Smaranda and Resnik, Philip} } @article {16268, title = {Genome assembly forensics: finding the elusive mis-assembly}, journal = {Genome Biology}, volume = {9}, year = {2008}, month = {2008/03/14/}, pages = {R55 - R55}, abstract = {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.}, isbn = {1465-6906}, doi = {10.1186/gb-2008-9-3-r55}, url = {http://genomebiology.com/2008/9/3/R55}, author = {Phillippy,Adam M and Schatz,Michael C and Pop, Mihai} } @article {14617, title = {Genome-Wide Analysis of Natural Selection on Human Cis-Elements}, journal = {PLoS ONEPLoS ONE}, volume = {3}, year = {2008}, month = {2008///}, pages = {e3137 - e3137}, abstract = {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. }, doi = {10.1371/journal.pone.0003137}, url = {UR - http://dx.doi.org/10.1371/journal.pone.0003137,http://dx.doi.org/10.1371/journal.pone.0003137}, author = {Sethupathy,Praveen and Giang,Hoa and Plotkin,Joshua B. and Hannenhalli, Sridhar} } @article {16271, title = {Genome-Wide Analysis of Repetitive Elements in Papaya}, journal = {Tropical Plant Biology}, volume = {1}, year = {2008}, month = {2008///}, pages = {191 - 201}, abstract = {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 .}, isbn = {1935-9756}, url = {http://dx.doi.org/10.1007/s12042-008-9015-0}, author = {Nagarajan,Niranjan and Navajas-P{\'e}rez,Rafael and Pop, Mihai and Alam,Maqsudul and Ming,Ray and Paterson,Andrew and Salzberg,Steven} } @conference {19448, title = {Getting to Green: Understanding Resource Consumption in the Home}, booktitle = {UbiComp {\textquoteright}08}, series = {UbiComp {\textquoteright}08}, year = {2008}, month = {2008///}, pages = {242 - 251}, publisher = {ACM}, organization = {ACM}, abstract = {Rising global energy demands, increasing costs and limited natural resources mean that householders are more conscious about managing their domestic resource consumption. Yet, the question of what tools Ubicomp researchers can create for residential resource management remains open. To begin to address this omission, we present a qualitative study of 15 households and their current management practices around the water, electricity and natural gas systems in the home. We find that in-the-moment resource consumption is mostly invisible to householders and that they desire more real-time information to help them save money, keep their homes comfortable and be environmentally friendly. Designing for domestic sustainability therefore turns on improving the visibility of resource production and consumption costs as well as supporting both individuals and collectives in behavior change. Domestic sustainability also highlights the caveat of potentially creating a green divide by making resource management available only to those who can afford the technologies to support being green. Finally, we suggest that the Ubicomp community can contribute to the domestic and broader sustainability agenda by incorporating green values in designs and highlight the challenge of collecting data on being green.}, keywords = {domestic conservation, residential resource consumption, Sustainability}, isbn = {978-1-60558-136-1}, url = {http://doi.acm.org/10.1145/1409635.1409668}, author = {Marshini Chetty and Tran, David and Grinter, Rebecca E.} } @article {12903, title = {Global impact of Vibrio cholerae interactions with chitin}, journal = {Environmental Microbiology}, volume = {10}, year = {2008}, month = {2008/06/01/}, pages = {1400 - 1410}, abstract = {The interaction of Vibrio cholerae with chitin exemplifies for microbial ecology a successful bacteria{\textendash}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{\textendash}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.}, isbn = {1462-2920}, doi = {10.1111/j.1462-2920.2007.01559.x}, url = {http://onlinelibrary.wiley.com/doi/10.1111/j.1462-2920.2007.01559.x/full}, author = {Pruzzo,Carla and Vezzulli,Luigi and Rita R Colwell} } @conference {16421, title = {GoGoBot: group collaboration, multi-agent modeling, and robots}, booktitle = {Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: demo papers}, series = {AAMAS {\textquoteright}08}, year = {2008}, month = {2008///}, pages = {1715 - 1716}, publisher = {International Foundation for Autonomous Agents and Multiagent Systems}, organization = {International Foundation for Autonomous Agents and Multiagent Systems}, address = {Richland, SC}, abstract = {Multi-agent simulation is a powerful technique used to encode real-world simple rules in virtual agents and then simulate their interactions [1]. Participatory simulations are similar to multi-agent simulation except individuals play the role of virtual agents, sometimes in combination with these virtual agents [2]. Finally, the bifocal modeling framework has enabled the examination of agents embodied in physical entities using sensors and actuators [3]. All three of these technologies are concerned with the creation, manipulation, and development of agents in one form or another. Thus combining these three disparate systems in to one unified platform would be useful. Multi-agent simulation platforms, participatory simulations, and bifocal modeling have all been demonstrated separately in the past. However many extant systems are difficult if not impossible to integrate.}, keywords = {multi-agent simulation, participatory simulation, ROBOTICS}, url = {http://dl.acm.org/citation.cfm?id=1402744.1402780}, author = {Rand, William and Blikstein,Paulo and Wilensky,Uri} } @article {14425, title = {Group proximity measure for recommending groups in online social networks}, journal = {networks}, volume = {1}, year = {2008}, month = {2008///}, pages = {5 - 5}, abstract = {There are currently, thousands of online social networks (OSN)available, each of which hosts millions of users. Users make new friendship links, join groups on diverse topics, share opinions and thus help in building a big knowledge repository. In this paper we study the problem of defining proximity measure between groups (communities) of OSN. Understanding the proximity among the groups in OSN can reveal new insights into the structure of the network. We use this proximity measure in a novel way with other structural features of online groups to predict the evolving state of the network. One of the important task in the sphere of OSN is helping users in selecting groups of their interest, by making rec- ommendations. We utilize group proximity measure to propose a new framework for recommending groups to users of OSN. Finally we investigate the effectiveness of our methods in three real OSN: Flickr, Live Journal and You Tube. Our methods give promising results. }, author = {Saha,B. and Getoor, Lise} } @conference {12245, title = {Growth of the flickr social network}, booktitle = {Proceedings of the first workshop on Online social networks}, series = {WOSN {\textquoteright}08}, year = {2008}, month = {2008///}, pages = {25 - 30}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Online social networking sites like MySpace, Orkut, and Flickr are among the most popular sites on the Web and continue to experience dramatic growth in their user population. The popularity of these sites offers a unique opportunity to study the dynamics of social networks at scale. Having a proper understanding of how online social networks grow can provide insights into the network structure, allow predictions of future growth, and enable simulation of systems on networks of arbitrary size. However, to date, most empirical studies have focused on static network snapshots rather than growth dynamics. In this paper, we collect and examine detailed growth data from the Flickr online social network, focusing on the ways in which new links are formed. Our study makes two contributions. First, we collect detailed data covering three months of growth, encompassing 950,143 new users and over 9.7 million new links, and we make this data available to the research community. Second, we use a first-principles approach to investigate the link formation process. In short, we find that links tend to be created by users who already have many links, that users tend to respond to incoming links by creating links back to the source, and that users link to other users who are already close in the network.}, keywords = {growth, measurement, social networks}, isbn = {978-1-60558-182-8}, doi = {10.1145/1397735.1397742}, url = {http://doi.acm.org/10.1145/1397735.1397742}, author = {Mislove,Alan and Koppula,Hema Swetha and Gummadi,Krishna P. and Druschel,Peter and Bhattacharjee, Bobby} } @article {14620, title = {Guest Editors{\textquoteright} Introduction to the Special Section on Algorithms in Bioinformatics}, journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics}, volume = {5}, year = {2008}, month = {2008/12//Oct}, pages = {482 - 483}, keywords = {Abstracts, Algorithm design and analysis, Bioinformatics, Biological system modeling, biology computing, Computational Biology, Computational modeling, Computer science, Genomics, sequences}, isbn = {1545-5963}, doi = {10.1109/TCBB.2008.116}, author = {Giancarlo,Raffaele and Hannenhalli, Sridhar} } @article {14581, title = {GATA and Nkx factors synergistically regulate tissue-specific gene expression and development in vivo}, journal = {Development}, volume = {134}, year = {2007}, month = {2007/01/01/}, pages = {189 - 198}, abstract = {In vitro studies have suggested that members of the GATA and Nkx transcription factor families physically interact, and synergistically activate pulmonary epithelial- and cardiac-gene promoters. However, the relevance of this synergy has not been demonstrated in vivo. We show that Gata6-Titf1 (Gata6-Nkx2.1) double heterozygous (G6-Nkx DH) embryos and mice have severe defects in pulmonary epithelial differentiation and distal airway development, as well as reduced phospholipid production. The defects in G6-Nkx DH embryos and mice are similar to those observed in human neonates with respiratory distress syndromes, including bronchopulmonary dysplasia, and differential gene expression analysis reveals essential developmental pathways requiring synergistic regulation by both Gata6 and Titf1 (Nkx2.1). These studies indicate that Gata6 and Nkx2.1 act in a synergistic manner to direct pulmonary epithelial differentiation and development in vivo, providing direct evidence that interactions between these two transcription factor families are crucial for the development of the tissues in which they are co-expressed.}, doi = {10.1242/dev.02720}, url = {http://dev.biologists.org/content/134/1/189.abstract}, author = {Zhang,Yuzhen and Rath,Nibedita and Hannenhalli, Sridhar and Wang,Zhishan and Cappola,Thomas and Kimura,Shioko and Atochina-Vasserman,Elena and Lu,Min Min and Beers,Michael F. and Morrisey,Edward E.} } @conference {12580, title = {Gaussian Approximations for Energy-Based Detection and Localization in Sensor Networks}, booktitle = {Statistical Signal Processing, 2007. SSP {\textquoteright}07. IEEE/SP 14th Workshop on}, year = {2007}, month = {2007/08//}, pages = {655 - 659}, abstract = {Energy-based detection and estimation are crucial in sensor networks for sensor localization, target tracking, etc. In this paper, we present novel Gaussian approximations that are applicable to general energy-based source detection and localization problems in sensor networks. Using our approximations, we derive receiver operating characteristics curves and Cramer-Rao bounds, and we provide a factorized variational Bayes approximation to the location and source energy posterior for centralized or decentralized estimation. When the source signal and the sensor noise have uncorrelated Gaussian distributions, we demonstrate that the envelope of the sensor output can be accurately modeled with a multiplicative Gaussian noise model, which results in smaller estimation biases than the other Gaussian models typically used in the literature. We also prove that additive Gaussian noise models result in negatively biased speed estimates under the same signal assumptions, which can be circumvented by the proposed approximations.}, doi = {10.1109/SSP.2007.4301340}, author = {Cevher,Volkan and Chellapa, Rama and McClellan,James H.} } @conference {17774, title = {A general framework for reasoning about inconsistency}, booktitle = {Proceedings of the International Joint Conference on Artificial Intelligence}, year = {2007}, month = {2007///}, pages = {599 - 604}, abstract = {Numerous logics have been developed for reason-ing about inconsistency which differ in (i) the logic to which they apply, and (ii) the criteria used to draw inferences. In this paper, we propose a gen- eral framework for reasoning about inconsistency in a wide variety of logics including ones for which inconsistency resolution methods have not yet been studied (e.g. various temporal and epistemic log- ics). We start with Tarski and Scott{\textquoteright}s axiomatiza- tion of logics, but drop their monotonicity require- ments that we believe are too strong for AI. For such a logic L, we define the concept of an option. Options are sets of formulas in L that are closed and consistent according to the notion of consequence and consistency in L. We show that by defining an appropriate preference relation on options, we can capture several existing works such as Brewka{\textquoteright}s subtheories. We also provide algorithms to com- pute most preferred options. }, author = {V.S. Subrahmanian and Amgoud,L.} } @conference {18838, title = {Generating Multi-Stage Molding Plans for Articulated Assemblies}, year = {2007}, month = {2007/07//}, pages = {56 - 63}, abstract = {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 adds new constraints to the assembly planning problem. This paper introduces the problem of generating multi-stage molding plans for articulated assemblies. We present detailed algorithms for determining the molding sequence and intermediate assembly configurations.}, keywords = {articulated assemblies, articulated products, assembly planning, assembly planning problem, intermediate assembly configuration, moulding, multistage molding}, doi = {10.1109/ISAM.2007.4288449}, author = {Priyadarshi,A. K. and Gupta,S.K.} } @article {15279, title = {Genome Analysis Linking Recent European and African Influenza (H5N1) Viruses}, journal = {Emerging Infectious DiseasesEmerg Infect Dis}, volume = {13}, year = {2007}, month = {2007/05//}, pages = {713 - 718}, abstract = {Although linked, these viruses are distinct from earlier outbreak strains., To better understand the ecology and epidemiology of the highly pathogenic avian influenza virus in its transcontinental spread, we sequenced and analyzed the complete genomes of 36 recent influenza A (H5N1) viruses collected from birds in Europe, northern Africa, and southeastern Asia. These sequences, among the first complete genomes of influenza (H5N1) viruses outside Asia, clearly depict the lineages now infecting wild and domestic birds in Europe and Africa and show the relationships among these isolates and other strains affecting both birds and humans. The isolates fall into 3 distinct lineages, 1 of which contains all known non-Asian isolates. This new Euro-African lineage, which was the cause of several recent (2006) fatal human infections in Egypt and Iraq, has been introduced at least 3 times into the European-African region and has split into 3 distinct, independently evolving sublineages. One isolate provides evidence that 2 of these sublineages have recently reassorted.}, isbn = {1080-6040}, doi = {10.3201/eid1305.070013}, author = {Salzberg,Steven L. and Kingsford, Carl and Cattoli,Giovanni and Spiro,David J. and Janies,Daniel A. and Aly,Mona Mehrez and Brown,Ian H. and Couacy-Hymann,Emmanuel and De Mia,Gian Mario and Dung,Do Huu and Guercio,Annalisa and Joannis,Tony and Ali,Ali Safar Maken and Osmani,Azizullah and Padalino,Iolanda and Saad,Magdi D. and Savi{\'c},Vladimir and Sengamalay,Naomi A. and Yingst,Samuel and Zaborsky,Jennifer and Zorman-Rojs,Olga and Ghedin,Elodie and Capua,Ilaria} } @article {14618, title = {Genome-wide expression profiling and bioinformatics analysis of diurnally regulated genes in the mouse prefrontal cortex}, journal = {Genome Biology}, volume = {8}, year = {2007}, month = {2007/11/20/}, pages = {R247 - R247}, abstract = {The prefrontal cortex is important in regulating sleep and mood. Diurnally regulated genes in the prefrontal cortex may be controlled by the circadian system, by sleep:wake states, or by cellular metabolism or environmental responses. Bioinformatics analysis of these genes will provide insights into a wide-range of pathways that are involved in the pathophysiology of sleep disorders and psychiatric disorders with sleep disturbances.}, isbn = {1465-6906}, doi = {10.1186/gb-2007-8-11-r247}, url = {http://genomebiology.com/2007/8/11/R247}, author = {Yang,Shuzhang and Wang,Kai and Valladares,Otto and Hannenhalli, Sridhar and Bucan,Maja} } @conference {14404, title = {GeoDDupe: A Novel Interface for Interactive Entity Resolution in Geospatial Data}, booktitle = {Information Visualization, 2007. IV {\textquoteright}07. 11th International Conference}, year = {2007}, month = {2007/07//}, pages = {489 - 496}, abstract = {Due to the growing interest in geospatial data mining and analysis, data cleaning and integration in geospatial data is becoming an important issue. Geospatial entity resolution is the process of reconciling multiple location references to the same real world location within a single data source (deduplication) or across multiple data sources (integration). In this paper, we introduce an interactive tool called GeoDDupe which effectively combines automatic data mining algorithms for geospatial entity resolution with a novel network visualization supporting users{\textquoteright} resolution analysis and decisions. We illustrate the GeoDDupe interface with an example geospatial dataset and show how users can efficiently and accurately resolve location entities. Finally, the case study with two real-world geospatial datasets demonstrates the potential of GeoDDupe.}, keywords = {algorithms;data, cleaning;geospatial, data, entity, GeoDDupe;automatic, interfaces;, mining, mining;geography;user, mining;geospatial, resolution;interactive, tool;network, visualization;data}, doi = {10.1109/IV.2007.55}, author = {Kang,Hyunmo and Sehgal,V. and Getoor, Lise} } @article {18847, title = {Geometrical algorithms for automated design of side actions in injection moulding of complex parts}, journal = {Computer-Aided Design}, volume = {39}, year = {2007}, month = {2007/10//}, pages = {882 - 897}, abstract = {This paper describes algorithms for generating shapes of side actions to minimize a customizable injection moulding cost function. Given a set of undercut facets on a polyhedral part and the main mold opening directions, our approach works in the following manner: first, we compute candidate retraction space for every undercut facet. This space represents the set of candidate translation vectors that can be used by the side action to completely disengage from the undercut facet. As the next step, we generate a discrete set of feasible, nondominated retractions. Then we group the undercut facets into undercut regions by performing state space search over such retractions. This search step is performed by minimizing the given moulding cost function. After identifying the undercut regions, we generate the shapes of individual side actions. We believe that the results presented in this paper will provide the foundations for developing fully automated software for designing side actions.}, keywords = {Configuration spaces, Geometrical reasoning, Mould design}, isbn = {0010-4485}, doi = {10.1016/j.cad.2007.05.014}, url = {http://www.sciencedirect.com/science/article/pii/S0010448507001339}, author = {Banerjee,Ashis Gopal and Gupta, Satyandra K.} } @conference {19636, title = {Geometrical Characteristics of Regular Polyhedra: Application to EXAFS Studies of Nanoclusters}, booktitle = {X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference}, volume = {882}, year = {2007}, month = {2007/02/02/}, pages = {746 - 748}, publisher = {AIP Publishing}, organization = {AIP Publishing}, abstract = {EXAFS data modeling of nanoparticles can be done at a very high level of detail if regular polyhedral geometries are considered as possible structural models. Such geometries can be characterized by unique sequence of indices (coordination numbers) of the first few coordination shells that serve as a signature of a shape, size, morphology and packing model of atoms in the cluster. We wrote a suite of programs for cluster geometry generation and its pair radial distribution function analysis. The programs generate x,y,z coordinates and calculate the coordination numbers of the corresponding clusters for any order of a large number of regular polyhedra. We present the results for the first few nearest neighboring shells in the icosahedral, cuboctahedral, hcp structures for the small, 10{\textendash}1000 atom clusters.}, keywords = {Atomic and molecular clusters, Cluster Analysis, Cluster geometric structure, Extended X-ray absorption fine structure spectroscopy, nanoparticles, Numerical modeling, Particle distribution functions, Polyhedra, Signal generators}, url = {http://scitation.aip.org/content/aip/proceeding/aipcp/10.1063/1.2644651}, author = {Dana Dachman-Soled and Frenkel, Anatoly I.} } @conference {19637, title = {Geometry and Charge State of Mixed-Ligand Au13 Nanoclusters}, booktitle = {X-RAY ABSORPTION FINE STRUCTURE - XAFS13: 13th International Conference}, volume = {882}, year = {2007}, month = {2007/02/02/}, pages = {749 - 751}, publisher = {AIP Publishing}, organization = {AIP Publishing}, abstract = {The integration of synthetic, experimental and theoretical tools into a self-consistent data analysis methodology allowed us to develop unique new levels of detail in nanoparticle characterization. We describe our methods using an example of Au 13 monolayer-protected clusters (MPCs), synthesized by ligand exchange methods. The combination of atom counting methods of scanning transmission electron microscopy and Au L3-edge EXAFS allowed us to characterize these clusters as icosahedral, with surface strain reduced from 5\% (as in ideal, regular icosahedra) to 3\%, due to the interaction with ligands. Charge transfer from Au to the thiol and phosphine ligands was evidenced by S and P K-edge XANES. A comparison of total energies of bare clusters of different geometries was performed by equivalent crystal theory calculations.}, keywords = {Atom surface interactions, Charge transfer, Data analysis, Extended X-ray absorption fine structure spectroscopy, Gold, nanoparticles, Scanning transmission electron microscopy, Surface strains, Total energy calculations, X-ray absorption near edge structure}, url = {http://scitation.aip.org/content/aip/proceeding/aipcp/10.1063/1.2644652}, author = {Frenkel, A. I. and Menard, L. D. and Northrup, P. and Rodriguez, J. A. and Zypman, F. and Dana Dachman-Soled and Gao, S.-P. and Xu, H. and Yang, J. C. and Nuzzo, R. G.} } @conference {12136, title = {Get Your Experience Factory Ready for the Next Decade{\textendash}Ten Years after "How to Build and Run One"}, booktitle = {Companion to the proceedings of the 29th International Conference on Software Engineering}, series = {ICSE COMPANION {\textquoteright}07}, year = {2007}, month = {2007///}, pages = {167 - 168}, publisher = {IEEE Computer Society}, organization = {IEEE Computer Society}, address = {Washington, DC, USA}, abstract = {This one-day tutorial aims at industry practitioners, managers and developers alike, who want to learn more about how to successfully design, implement and run an Experience Factory, to systematically build up and manage the experience of an organization. State-of- the art methods and techniques on how to initially set-up or to further develop and improve an organization{\textquoteright}s Experience Factory are discussed. Participants should come from organizations (not only from the software domain) that are interested in implementing an Experience Factory to help effectively support improvement activities (such as TQM, ISO 9000, CMMI, SPICE, or TSP) to gain competitive advantages.}, isbn = {0-7695-2892-9}, doi = {10.1109/ICSECOMPANION.2007.41}, url = {http://dx.doi.org/10.1109/ICSECOMPANION.2007.41}, author = {Basili, Victor R. and Bomarius,Frank and Feldmann,Raimund L.} } @conference {19495, title = {Got Predictability?: Experiences with Fault-tolerant Middleware}, booktitle = {MC{\textquoteright}07 Proceedings of the 2007 ACM/IFIP/USENIX International Conference on Middleware Companion}, series = {MC {\textquoteright}07}, year = {2007}, month = {2007///}, pages = {20:1 - 20:22}, publisher = {ACM}, organization = {ACM}, abstract = {Unpredictability in COTS-based systems often manifests as occasional instances of uncontrollably-high response times. A particular category of COTS systems, fault-tolerant (FT) middleware, is used in critical enterprise and embedded applications where predictability is of paramount importance. Our prior empirical study, which used a client-server microbenchmark, suggested that hard bounds for the maximum latency are hard to establish a priori, but that the unpredictability may be confined to less than 1\% of the requests. In this paper, we present empirical data, from 7 different three-tier, FT-middleware applications, that shows strong evidence supporting this "magical 1\%" hypothesis. We conducted a controlled experiment with 7 teams of students from a graduate-level course at Carnegie Mellon University. Each team, starting from a common three-tier architecture, independently implemented and evaluated an original application using middleware (either CORBA or EJB) and a custom-implemented fault-tolerance mechanism (relying on either state-machine or primary-backup replication) for the middle-tier server. This experiment shows that unpredictability may not be avoidable, even in the absence of faults, and that, in some cases, the random latency outliers are larger than the time needed to recover from a fault. The data also reveals a statistically-significant result that, across all 7 applications, unpredictability is confined to the highest 1\% of the recorded end-to-end latencies and is not correlated with the request rate, the size of messages exchanged or the number of clients. This suggests that strict predictability is hard to achieve in FT-middleware systems and that developers of critical FT applications should focus on guaranteeing bounds for statistical measures, such as the 99th percentile of the latency.}, isbn = {978-1-59593-935-7}, url = {http://doi.acm.org/10.1145/1377943.1377957}, author = {Tudor Dumitras and Narasimhan, Priya} } @conference {13348, title = {A graph-based approach to vehicle tracking in traffic camera video streams}, booktitle = {Proceedings of the 4th workshop on Data management for sensor networks: in conjunction with 33rd International Conference on Very Large Data Bases}, series = {DMSN {\textquoteright}07}, year = {2007}, month = {2007///}, pages = {19 - 24}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Vehicle tracking has a wide variety of applications from law enforcement to traffic planning and public safety. However, the image resolution of the videos available from most traffic camera systems, make it difficult to track vehicles based on unique identifiers like license plates. In many cases, vehicles with similar attributes are indistinguishable from one another due to image quality issues. Often, network bandwidth and power constraints limit the frame rate, as well. In this paper, we discuss the challenges of performing vehicle tracking queries over video streams from ubiquitous traffic cameras. We identify the limitations of tracking vehicles individually in such conditions and provide a novel graph-based approach using the identity of neighboring vehicles to improve the performance. We evaluate our approach using streaming video feeds from live traffic cameras available on the Internet. The results show that vehicle tracking is feasible, even for low quality and low frame rate traffic cameras. Additionally, exploitation of the attributes of neighboring vehicles significantly improves the performance.}, isbn = {978-159593-911-1}, doi = {10.1145/1286380.1286386}, url = {http://doi.acm.org/10.1145/1286380.1286386}, author = {Shahri,Hamid Haidarian and Namata,Galileo and Navlakha,Saket and Deshpande, Amol and Roussopoulos, Nick} } @inbook {14411, title = {Graphical Models in a Nutshell}, booktitle = {Introduction to Statistical Relational LearningIntroduction to Statistical Relational Learning}, year = {2007}, month = {2007///}, pages = {13 - 13}, author = {Koller,D. and Friedman,N. and Getoor, Lise and Taskar,B.} } @article {13002, title = {Grid Services Base Library: A high-level, procedural application programming interface for writing Globus-based Grid services}, journal = {Future Generation Comp Syst}, volume = {23}, year = {2007}, month = {2007///}, pages = {517 - 522}, abstract = {The Grid Services Base Library (GSBL) is a procedural application programming interface (API) that abstracts many of the high-level functions performed by Globus Grid services, thus dramatically lowering the barriers to writing Grid services. The library has been extensively tested and used for computational biology research in a Globus Toolkit-based Grid system, in which no fewer than twenty Grid services written with this API are deployed.}, author = {Bazinet,A. L and Myers,D. S and Fuetsch,J. and Cummings, Michael P.} } @conference {17771, title = {GRIN: A graph based RDF index}, booktitle = {Proceedings of the National Conference on Artificial Intelligence}, volume = {22}, year = {2007}, month = {2007///}, pages = {1465 - 1465}, abstract = {RDF ({\textquotedblleft}Resource Description Framework{\textquotedblright}) is now a widelyused World Wide Web Consortium standard. However, methods to index large volumes of RDF data are still in their infancy. In this paper, we focus on providing a very lightweight indexing mechanism for certain kinds of RDF queries, namely graph-based queries where there is a need to traverse edges in the graph determined by an RDF database. Our approach uses the idea of drawing circles around selected {\textquotedblleft}center{\textquotedblright} vertices in the graph where the circle would encom- pass those vertices in the graph that are within a given dis- tance of the {\textquotedblleft}center{\textquotedblright} vertex. We come up with methods of finding such {\textquotedblleft}center{\textquotedblright} vertices and identifying the radius of the circles and then leverage this to build an index called GRIN. We compare GRIN with three existing RDF indexex: Jena, Sesame, and RDFBroker. We compared (i) the time to an- swer graph based queries, (ii) memory needed to store the index, and (iii) the time to build the index. GRIN outper- forms Jena, Sesame and RDFBroker on all three measures for graph based queries (for other types of queries, it may be worth building one of these other indexes and using it), at the expense of using a larger amount of memory when answering queries. }, author = {Udrea,O. and Pugliese, A. and V.S. Subrahmanian} } @conference {19449, title = {Grow and Know: Understanding Record-keeping Needs for Tracking the Development of Young Children}, booktitle = {SIGCHI {\textquoteright}07}, series = {CHI {\textquoteright}07}, year = {2007}, month = {2007///}, pages = {1351 - 1360}, publisher = {ACM}, organization = {ACM}, abstract = {From birth through age five, children undergo rapid development and learn skills that will influence them their entire lives. Regular visits to the pediatrician and detailed record-keeping can ensure that children are progressing and can identify early warning signs of developmental delay or disability. However, new parents are often overwhelmed with new responsibilities, and we believe there is an opportunity for computing technology to assist in this process. In this paper, we present a qualitative study aimed at uncovering some specific needs for record-keeping and analysis for new parents and their network of caregivers. Through interviews and focus groups, we have confirmed assumptions about the rationales parents have and the functions required for using technology for record-keeping. We also identify new themes, potential prototypes, and design guidelines for this domain.}, keywords = {children, design requirements, developmental delay, healthcare, qualitative study}, isbn = {978-1-59593-593-9}, url = {http://doi.acm.org/10.1145/1240624.1240830}, author = {Kientz, Julie A. and Arriaga, Rosa I. and Marshini Chetty and Hayes, Gillian R. and Richardson, Jahmeilah and Patel, Shwetak N. and Abowd, Gregory D.} } @article {12579, title = {Guest Editorial: Special Issue on Human Detection and Recognition}, journal = {Information Forensics and Security, IEEE Transactions on}, volume = {2}, year = {2007}, month = {2007/09//}, pages = {489 - 490}, abstract = {The 12 regular papers and three correspondences in this special issue focus on human detection and recognition. The papers represent gait, face (3-D, 2-D, video), iris, palmprint, cardiac sounds, and vulnerability of biometrics and protection against the spoof attacks.}, isbn = {1556-6013}, doi = {10.1109/TIFS.2007.905740}, author = {Bhanu, B. and Ratha,N. K and Kumar, V. and Chellapa, Rama and Bigun, J.} } @inbook {12632, title = {Gait Databases}, booktitle = {Human Identification Based on GaitHuman Identification Based on Gait}, year = {2006}, month = {2006///}, pages = {17 - 34}, abstract = {Naturally, the success and evolution of a new application relies largely on the dataset used for evaluation. The early gait databases were collected about 10 years before the time of writing. Then, computers had little power and memory costs were comparatively high. Clearly, this was before digital video and acquisition was based on analogue camcorder technology which resulted in frames being digitized individually. Since techniques were in their infancy, as in face recognition, early databases only had few subjects. The idea then was to determine whether recognition could be achieved at all {\textemdash} or not. At that stage we were not interested in the ramifications of recognition. There were two early databases which were developed independently: the UCSD data was recorded outdoors and the Southampton data was indoors, with subjects wearing special trousers. The current databases are considerably more advanced, but certainly benefited in their development for the early approaches.}, author = {Nixon, M.S. and Tan, T. and Chellapa, Rama} } @article {17968, title = {Geometry-dependent lighting}, journal = {Visualization and Computer Graphics, IEEE Transactions on}, volume = {12}, year = {2006}, month = {2006/04//march}, pages = {197 - 207}, abstract = {In this paper, we introduce geometry-dependent lighting that allows lighting parameters to be defined independently and possibly discrepantly over an object or scene based on the local geometry. We present and discuss light collages, a lighting design system with geometry-dependent lights for effective feature-enhanced visualization. Our algorithm segments the objects into local surface patches and places lights that are locally consistent but globally discrepant to enhance the perception of shape. We use spherical harmonics for efficiently storing and computing light placement and assignment. We also outline a method to find the minimal number of light sources sufficient to illuminate an object well with our globally discrepant lighting approach.}, keywords = {Computer-Assisted;Imaging, feature-enhanced visualization;geometry-dependent light;light collage;light placement;lighting design system;computational geometry;data visualisation;lighting;Algorithms;Computer Graphics;Image Enhancement;Image Interpretation, Three-Dimensional;Information Storage and Retrieval;Lighting;User-Computer Interface;}, isbn = {1077-2626}, doi = {10.1109/TVCG.2006.30}, author = {Lee,C. H and Hao,X. and Varshney, Amitabh} } @article {17908, title = {Geometry-guided computation of 3D electrostatics for large biomolecules}, journal = {Computer Aided Geometric Design}, volume = {23}, year = {2006}, month = {2006/08//}, pages = {545 - 557}, abstract = {Electrostatic interactions play a central role in biological processes. Development of fast computational methods to solve the underlying Poisson{\textendash}Boltzmann equation (PBE) is vital for biomolecular modeling and simulation package. In this paper, we propose new methods for efficiently computing the electrostatic potentials for large molecules by using the geometry of the molecular shapes to guide the computation. The accuracy and stability of the solution to the PBE is quite sensitive to the boundary layer between the solvent and the solute which defines the molecular surface. In this paper, we present a new interface-layer-focused PBE solver. First, we analytically construct the molecular surface of the molecule and compute a distance field from the surface. We then construct nested iso-surface layers outwards and inwards from the surface using the distance field. We have developed a volume simplification algorithm to adaptively adjust the density of the irregular grid based on the importance to the PBE solution. We have generalized the finite difference methods using Taylor series expansion on the irregular grids. Our algorithm achieves about three times speedup in the iterative solution process of PBE, with more accurate results on an analytical solvable testing case, compared with the popular optimized DelPhi program.}, keywords = {Finite difference methods, Iso-surface generation, Level-of-detail of hierarchy, Poisson{\textendash}Boltzmann equation, Scalar field, Tetrahedron decomposition}, isbn = {0167-8396}, doi = {10.1016/j.cagd.2006.04.003}, url = {http://www.sciencedirect.com/science/article/pii/S0167839606000434}, author = {Hao,Xuejun and Varshney, Amitabh} } @article {12160, title = {The Goal Question Metric Approach}, journal = {5th ACM-IEEE International Symposium on Empirical Software Engineering (ISESE{\textquoteright}06)}, year = {2006}, month = {2006///}, author = {Basili, Victor R. and Caldiera,G. and Rombach,H. D} } @conference {13781, title = {Going beyond AER: an extensive analysis of word alignments and their impact on MT}, booktitle = {Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics}, series = {ACL-44}, year = {2006}, month = {2006///}, pages = {9 - 16}, publisher = {Association for Computational Linguistics}, organization = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA}, abstract = {This paper presents an extensive evaluation of five different alignments and investigates their impact on the corresponding MT system output. We introduce new measures for intrinsic evaluations and examine the distribution of phrases and untranslated words during decoding to identify which characteristics of different alignments affect translation. We show that precision-oriented alignments yield better MT output (translating more words and using longer phrases) than recall-oriented alignments.}, doi = {10.3115/1220175.1220177}, url = {http://dx.doi.org/10.3115/1220175.1220177}, author = {Ayan,Necip Fazil and Dorr, Bonnie J} } @article {17736, title = {The Gram-Schmidt Algorithm and Its Variations}, volume = {UMIACS-TR-2004-84}, year = {2006}, month = {2006/01/13/}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {The Gram--Schmidt algorithm is a widely used method fororthogonalizing a sequence of vectors. It comes in two forms: classical Gram--Schmidt and modified Gram--Schmidt, each of whose operations can be ordered in different ways. This expository paper gives a systematic treatment of this confusing variety of algorithms. It also treats the numerical issue of loss of orthogonality and reorthogonalization as well as the implementation of column pivoting. }, keywords = {Technical Report}, url = {http://drum.lib.umd.edu/handle/1903/3036}, author = {Stewart, G.W.} } @article {12674, title = {Gait-based human identification using appearance matching}, journal = {Optical and Digital Techniques for Information Security}, year = {2005}, month = {2005///}, pages = {271 - 295}, abstract = {In this chapter, we present an appearance-based approach for recognizing human gait. Given the gait video of an individual, the images are binarized and the width of the outer contour of the silhouette of that individual is obtained for each image frame. Several gait features are derived from this basic width vector. Temporally ordered sequences of the feature vectors are then used to represent the gait of a person. While matching the feature templates for recognition, dynamic time-warping (DTW), which is a nonlinear time-normalization technique, is used to deal with naturally occurring changes in the walking speeds of individuals. The performance of the proposed method is tested on indoor as well as outdoor gait databases, and the efficacy of different gait features and their noise resilience is studied. The experiments also demonstrate the effect of change in the viewing angle and frame rate of data capture on the accuracy of gait recognition.}, author = {Kale, A. and Cuntoor, N. and Yegnanarayana,B. and Rajagopalan, A. and Chellapa, Rama} } @conference {18875, title = {Game-tree search with combinatorially large belief states}, volume = {19}, year = {2005}, month = {2005///}, pages = {254 - 254}, abstract = {In games such as kriegspiel chess (a chess variantwhere players have no direct knowledge of the op- ponent{\textquoteright}s pieces{\textquoteright} locations) the belief state{\textquoteright}s sizes dwarf those of other partial information games like bridge, scrabble, and poker{\textendash}and there is no easy way to generate states satisfying the given observa- tions. We show that statistical sampling approaches can be developed to do well in such games. We show that it is not necessary for the random sample to consist only of game boards that satisfy each and every one of a player{\textquoteright}s observations. In fact, we win 24\% more often by beginning with such completely consistent boards and gradually switching (as the game progressed) to boards that are merely consistent with the latest observation. This surprising result is explained by noting that as the game progresses, a board that is consistent with the last move becomes more and more likely to be consistent with the entire set of observations, even if we have no idea what sequence of moves might have actually generated this board. }, url = {http://www.ijcai.org/papers/0878.pdf}, author = {Parker,A. and Nau, Dana S. and V.S. Subrahmanian} } @article {14580, title = {Generalizations of Markov model to characterize biological sequences}, journal = {BMC Bioinformatics}, volume = {6}, year = {2005}, month = {2005///}, pages = {219 - 219}, abstract = {BACKGROUND:The currently used kth order Markov models estimate the probability of generating a single nucleotide conditional upon the immediately preceding (gap = 0) k units. However, this neither takes into account the joint dependency of multiple neighboring nucleotides, nor does it consider the long range dependency with gap>0.RESULT:We describe a configurable tool to explore generalizations of the standard Markov model. We evaluated whether the sequence classification accuracy can be improved by using an alternative set of model parameters. The evaluation was done on four classes of biological sequences - CpG-poor promoters, all promoters, exons and nucleosome positioning sequences. Using di- and tri-nucleotide as the model unit significantly improved the sequence classification accuracy relative to the standard single nucleotide model. In the case of nucleosome positioning sequences, optimal accuracy was achieved at a gap length of 4. Furthermore in the plot of classification accuracy versus the gap, a periodicity of 10-11 bps was observed which might indicate structural preferences in the nucleosome positioning sequence. The tool is implemented in Java and is available for download at ftp://ftp.pcbi.upenn.edu/GMM/.CONCLUSION:Markov modeling is an important component of many sequence analysis tools. We have extended the standard Markov model to incorporate joint and long range dependencies between the sequence elements. The proposed generalizations of the Markov model are likely to improve the overall accuracy of sequence analysis tools.}, isbn = {1471-2105}, doi = {10.1186/1471-2105-6-219}, url = {http://www.biomedcentral.com/1471-2105/6/219}, author = {Wang,Junwen and Hannenhalli, Sridhar} } @article {17177, title = {Generating and Querying Semantic Web Environments for Photo Libraries (2005)}, journal = {Institute for Systems Research Technical Reports}, year = {2005}, month = {2005///}, abstract = {Online photo libraries require a method to efficiently search a collection of photographs, and retrieve photos with similar attributes. Our motivation was to incorporate an existing collection of over 250 photographs of over 200 faculty members and events spanning 7 decades into a library called CS PhotoHistory that is available in hypertext and on the Semantic Web. In this paper, we identify challenges related to making this repository available on the Semantic Web, including issues of automation, modeling, and expressivity. Using CS PhotoHistory as a case study, we describe the process of creating an ontology and a querying interface for interacting with a digital photo library on the Semantic Web.}, keywords = {Technical Report}, url = {http://drum.lib.umd.edu/handle/1903/6538}, author = {Axelrod,Adam and Golbeck,Jennifer and Shneiderman, Ben} } @conference {18394, title = {Generating testable hypotheses from tacit knowledge for high productivity computing}, booktitle = {Proceedings of the second international workshop on Software engineering for high performance computing system applications}, series = {SE-HPCS {\textquoteright}05}, year = {2005}, month = {2005///}, pages = {17 - 21}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {In this research, we are developing our understanding of how the high performance computing community develops effective parallel implementations of programs by collecting the folklore within the community. We use this folklore as the basis for a series of experiments, which we expect, will validate or negate these assumptions.}, keywords = {folklore elicitation, high productivity development time experimental studies, hypothesis generation, tacit knowledge solicitation, testable hypotheses}, isbn = {1-59593-117-1}, doi = {10.1145/1145319.1145325}, url = {http://doi.acm.org/10.1145/1145319.1145325}, author = {Asgari, Sima and Hochstein, Lorin and Basili, Victor R. and Zelkowitz, Marvin V and Hollingsworth, Jeffrey K and Carver, Jeff and Shull, Forrest} } @article {14076, title = {The genetic map and comparative analysis with the physical map of Trypanosoma brucei}, journal = {Nucleic acids research}, volume = {33}, year = {2005}, month = {2005///}, pages = {6688 - 6688}, author = {MacLeod,A. and Tweedie,A. and McLellan,S. and Taylor,S. and Hall,N. and Berriman,M. and El-Sayed, Najib M. and Hope,M. and Turner,C. M.R and Tait,A.} } @article {14092, title = {The genome of the African trypanosome Trypanosoma brucei}, journal = {Science}, volume = {309}, year = {2005}, month = {2005///}, pages = {416 - 416}, author = {Berriman,M. and Ghedin,E. and Hertz-Fowler,C. and Blandin,G. and Renauld,H. and Bartholomeu,D. C and Lennard,N. J and Caler,E. and Hamlin,N. E and Haas,B. and others} } @article {19077, title = {The genome of the protist parasite Entamoeba histolytica}, journal = {Nature}, volume = {433}, year = {2005}, month = {2005}, pages = {865 - 868}, author = {Loftus,B. and Anderson,I. and Davies,R. and Alsmark,U. C.M and Samuelson,J. and Amedeo,P. and Roncaglia,P. and Berriman,M. and Hirt,R. P and Mann,B. J and others} } @article {16291, title = {The Genome Sequence of Trypanosoma Cruzi, Etiologic Agent of Chagas Disease}, journal = {ScienceScience}, volume = {309}, year = {2005}, month = {2005/07/15/}, pages = {409 - 415}, abstract = {Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50\% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.}, isbn = {0036-8075, 1095-9203}, doi = {10.1126/science.1112631}, url = {http://www.sciencemag.org/content/309/5733/409}, author = {El-Sayed, Najib M. and Myler,Peter J. and Bartholomeu,Daniella C. and Nilsson,Daniel and Aggarwal,Gautam and Tran,Anh-Nhi and Ghedin,Elodie and Worthey,Elizabeth A. and Delcher,Arthur L. and Blandin,Ga{\"e}lle and Westenberger,Scott J. and Caler,Elisabet and Cerqueira,Gustavo C. and Branche,Carole and Haas,Brian and Anupama,Atashi and Arner,Erik and {\r A}slund,Lena and Attipoe,Philip and Bontempi,Esteban and Bringaud,Fr{\'e}d{\'e}ric and Burton,Peter and Cadag,Eithon and Campbell,David A. and Carrington,Mark and Crabtree,Jonathan and Darban,Hamid and da Silveira,Jose Franco and de Jong,Pieter and Edwards,Kimberly and Englund,Paul T. and Fazelina,Gholam and Feldblyum,Tamara and Ferella,Marcela and Frasch,Alberto Carlos and Gull,Keith and Horn,David and Hou,Lihua and Huang,Yiting and Kindlund,Ellen and Klingbeil,Michele and Kluge,Sindy and Koo,Hean and Lacerda,Daniela and Levin,Mariano J. and Lorenzi,Hernan and Louie,Tin and Machado,Carlos Renato and McCulloch,Richard and McKenna,Alan and Mizuno,Yumi and Mottram,Jeremy C. and Nelson,Siri and Ochaya,Stephen and Osoegawa,Kazutoyo and Pai,Grace and Parsons,Marilyn and Pentony,Martin and Pettersson,Ulf and Pop, Mihai and Ramirez,Jose Luis and Rinta,Joel and Robertson,Laura and Salzberg,Steven L. and Sanchez,Daniel O. and Seyler,Amber and Sharma,Reuben and Shetty,Jyoti and Simpson,Anjana J. and Sisk,Ellen and Tammi,Martti T. and Tarleton,Rick and Teixeira,Santuza and Van Aken,Susan and Vogt,Christy and Ward,Pauline N. and Wickstead,Bill and Wortman,Jennifer and White,Owen and Fraser,Claire M. and Stuart,Kenneth D. and Andersson,Bj{\"o}rn} } @article {14071, title = {The Genome Sequence of Trypanosoma cruzi, Etiologic Agent of Chagas Disease}, journal = {Science}, volume = {309}, year = {2005}, month = {2005/07/15/}, pages = {409 - 415}, abstract = {Whole-genome sequencing of the protozoan pathogen Trypanosoma cruzi revealed that the diploid genome contains a predicted 22,570 proteins encoded by genes, of which 12,570 represent allelic pairs. Over 50\% of the genome consists of repeated sequences, such as retrotransposons and genes for large families of surface molecules, which include trans-sialidases, mucins, gp63s, and a large novel family (>1300 copies) of mucin-associated surface protein (MASP) genes. Analyses of the T. cruzi, T. brucei, and Leishmania major (Tritryp) genomes imply differences from other eukaryotes in DNA repair and initiation of replication and reflect their unusual mitochondrial DNA. Although the Tritryp lack several classes of signaling molecules, their kinomes contain a large and diverse set of protein kinases and phosphatases; their size and diversity imply previously unknown interactions and regulatory processes, which may be targets for intervention.}, doi = {10.1126/science.1112631}, url = {http://www.sciencemag.org/content/309/5733/409.abstract}, author = {El-Sayed, Najib M. and Myler,Peter J. and Bartholomeu,Daniella C. and Nilsson,Daniel and Aggarwal,Gautam and Tran,Anh-Nhi and Ghedin,Elodie and Worthey,Elizabeth A. and Delcher,Arthur L. and Blandin,Ga{\"e}lle and Westenberger,Scott J. and Caler,Elisabet and Cerqueira,Gustavo C. and Branche,Carole and Haas,Brian and Anupama,Atashi and Arner,Erik and {\r A}slund,Lena and Attipoe,Philip and Bontempi,Esteban and Bringaud,Fr{\'e}d{\'e}ric and Burton,Peter and Cadag,Eithon and Campbell,David A. and Carrington,Mark and Crabtree,Jonathan and Darban,Hamid and da Silveira,Jose Franco and de Jong,Pieter and Edwards,Kimberly and Englund,Paul T. and Fazelina,Gholam and Feldblyum,Tamara and Ferella,Marcela and Frasch,Alberto Carlos and Gull,Keith and Horn,David and Hou,Lihua and Huang,Yiting and Kindlund,Ellen and Klingbeil,Michele and Kluge,Sindy and Koo,Hean and Lacerda,Daniela and Levin,Mariano J. and Lorenzi,Hernan and Louie,Tin and Machado,Carlos Renato and McCulloch,Richard and McKenna,Alan and Mizuno,Yumi and Mottram,Jeremy C. and Nelson,Siri and Ochaya,Stephen and Osoegawa,Kazutoyo and Pai,Grace and Parsons,Marilyn and Pentony,Martin and Pettersson,Ulf and Pop, Mihai and Ramirez,Jose Luis and Rinta,Joel and Robertson,Laura and Salzberg,Steven L. and Sanchez,Daniel O. and Seyler,Amber and Sharma,Reuben and Shetty,Jyoti and Simpson,Anjana J. and Sisk,Ellen and Tammi,Martti T. and Tarleton,Rick and Teixeira,Santuza and Van Aken,Susan and Vogt,Christy and Ward,Pauline N. and Wickstead,Bill and Wortman,Jennifer and White,Owen and Fraser,Claire M. and Stuart,Kenneth D. and Andersson,Bj{\"o}rn} } @article {19073, title = {The genome sequence of Trypanosoma cruzi, etiologic agent of Chagas disease}, journal = {Science}, volume = {309}, year = {2005}, month = {2005}, author = {El-Sayed, N.M. and Myler,P. J and Bartholomeu,D. C and Nilsson,D. and Aggarwal,G. and Tran,A. N and Ghedin,E. and Worthey,E. A and Delcher,A. L and Blandin,G. and others} } @article {14616, title = {Genome-Wide Analysis of Chromosomal Features Repressing Human Immunodeficiency Virus Transcription}, journal = {Journal of VirologyJ. Virol.}, volume = {79}, year = {2005}, month = {2005/06/01/}, pages = {6610 - 6619}, abstract = {We have investigated regulatory sequences in noncoding human DNA that are associated with repression of an integrated human immunodeficiency virus type 1 (HIV-1) promoter. HIV-1 integration results in the formation of precise and homogeneous junctions between viral and host DNA, but integration takes place at many locations. Thus, the variation in HIV-1 gene expression at different integration sites reports the activity of regulatory sequences at nearby chromosomal positions. Negative regulation of HIV transcription is of particular interest because of its association with maintaining HIV in a latent state in cells from infected patients. To identify chromosomal regulators of HIV transcription, we infected Jurkat T cells with an HIV-based vector transducing green fluorescent protein (GFP) and separated cells into populations containing well-expressed (GFP-positive) or poorly expressed (GFP-negative) proviruses. We then determined the chromosomal locations of the two classes by sequencing 971 junctions between viral and cellular DNA. Possible effects of endogenous cellular transcription were characterized by transcriptional profiling. Low-level GFP expression correlated with integration in (i) gene deserts, (ii) centromeric heterochromatin, and (iii) very highly expressed cellular genes. These data provide a genome-wide picture of chromosomal features that repress transcription and suggest models for transcriptional latency in cells from HIV-infected patients.}, isbn = {0022-538X, 1098-5514}, doi = {10.1128/JVI.79.11.6610-6619.2005}, url = {http://jvi.asm.org/content/79/11/6610}, author = {Lewinski,M. K and Bisgrove,D. and Shinn,P. and Chen,H. and Hoffmann,C. and Hannenhalli, Sridhar and Verdin,E. and Berry,C. C and Ecker,J. R and Bushman,F. D} } @article {14566, title = {Genome-wide analysis of retroviral DNA integration}, journal = {Nat Rev MicroNat Rev Micro}, volume = {3}, year = {2005}, month = {2005/11//}, pages = {848 - 858}, isbn = {1740-1526}, doi = {10.1038/nrmicro1263}, url = {http://dx.doi.org/10.1038/nrmicro1263}, author = {Bushman,Frederic and Lewinski,Mary and Ciuffi,Angela and Barr,Stephen and Leipzig,Jeremy and Hannenhalli, Sridhar and Hoffmann,Christian} } @conference {18571, title = {Geographic locality of IP prefixes}, booktitle = {Proceedings of the 5th ACM SIGCOMM conference on Internet Measurement}, series = {IMC {\textquoteright}05}, year = {2005}, month = {2005///}, pages = {13 - 13}, publisher = {USENIX Association}, organization = {USENIX Association}, address = {Berkeley, CA, USA}, abstract = {Information about the geographic locality of IP prefixes can be useful for understanding the issues related to IP address allocation, aggregation, and BGP routing table growth. In this paper, we use traceroute data and geographic mappings of IP addresses to study the geographic properties of IP prefixes and their implications on Internet routing. We find that (1) IP prefixes may be too coarse-grained for expressing routing policies, (2) address allocation policies and the granularity of routing contribute significantly to routing table size, and (3) not considering the geographic diversity of contiguous prefixes may result in overestimating the opportunities for aggregation in the BGP routing table.}, url = {http://dl.acm.org/citation.cfm?id=1251086.1251099}, author = {Freedman,Michael J. and Vutukuru,Mythili and Feamster, Nick and Balakrishnan,Hari} } @article {18845, title = {Geometric algorithms for computing cutter engagement functions in 2.5D milling operations}, journal = {Computer-Aided Design}, volume = {37}, year = {2005}, month = {2005/12//}, pages = {1469 - 1480}, abstract = {Cutter engagement is a measure that describes what portion of the cutter is involved in machining at a given instant of time. During profile milling of complex geometries, cutter engagement varies significantly along the cutter path. Cutter engagement information helps in determining the efficiency of the cutter path and also helps in improving it by adjusting the feed rate. This paper describes geometric algorithms for computing piece-wise continuous closed-form cutter engagement functions for 2.5D milling operations. The results produced by our algorithm are compared with the results obtained by discrete simulations of the cutting process and appear to match very well.}, keywords = {Cutter engagement, Cutter path planning, Feed rate adjustments}, isbn = {0010-4485}, doi = {10.1016/j.cad.2005.03.001}, url = {http://www.sciencedirect.com/science/article/pii/S0010448505000801}, author = {Gupta, Satyandra K. and Saini,Sunil K. and Spranklin,Brent W. and Yao,Zhiyang} } @article {18846, title = {Geometric algorithms for containment analysis of rotational parts}, journal = {Computer-Aided Design}, volume = {37}, year = {2005}, month = {2005/02//}, pages = {213 - 230}, abstract = {This paper describes a system and underlying algorithms to perform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank-orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used by designers and process planners to find an existing part that can be used as a stock to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products.}, keywords = {COMPUTER AIDED DESIGN, geometric reasoning, Part containment, Shape signatures, Shape similarity}, isbn = {0010-4485}, doi = {10.1016/j.cad.2004.06.007}, url = {http://www.sciencedirect.com/science/article/pii/S0010448504001186}, author = {Karnik,Mukul and Gupta, Satyandra K. and Magrab,Edward B.} } @article {12934, title = {Global microbial ecology of Vibrio cholerae}, journal = {Oceans and health: pathogens in the marine environment}, year = {2005}, month = {2005///}, pages = {297 - 305}, abstract = {The disease cholera can no longer be considered a simple equation of bacteria and human host, but represents a complex network that includes global weather patterns, aquatic reservoirs, phages, zooplankton, collective behavior of surface-attached cells, an adaptable genome, and the deep sea inter alia. This interesting characterization emerges from a view of biological systems termed biocomplexity (Colwell, 2002a, b). The holistic approach to understanding cholera integrates contributions from experts in many fields, with multiple points of view, in models for prediction, prevention, and treatment of the disease that Vibrio cholerae causes. The spiral form shown in Figure 12.1 symbolizes the nonlinear manner in which the many parts of such a model interact. It also shows that these interactions often occur across many different scales.}, doi = {10.1007/0-387-23709-7_12}, author = {Rita R Colwell} } @conference {18882, title = {Going far, logically}, volume = {19}, year = {2005}, month = {2005///}, pages = {615 - 615}, abstract = {There are numerous applications where we need toensure that multiple moving objects are sufficiently far apart. Furthermore, in many moving object do- mains, there is positional indeterminacy {\textemdash} we are not 100\% sure exactly when a given moving object will be at a given location. [Yaman et al., 2004] provided a logic of motion but did not provide algo- rithms to ensure that moving objects are kept suf- ficiently far apart. In this paper, we extend their logic to include a {\textquotedblleft}far{\textquotedblright} predicate. We develop the CheckFar algorithm that checks if any given two objects will always be sufficiently far apart at dur- ing a time interval. We have run a set of experi- ments showing that our CheckFar algorithm scales very well. }, url = {http://www.cs.umd.edu/~nau/papers/yaman2005going.pdf}, author = {Yaman,F. and Nau, Dana S. and V.S. Subrahmanian} } @conference {17794, title = {A graph theoretical foundation for integrating RDF ontologies}, booktitle = {PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE}, volume = {20}, year = {2005}, month = {2005///}, pages = {1442 - 1442}, abstract = {RDF ontologies are rapidly increasing in number. We studythe problem of integrating two RDF ontologies under a given set H of Horn clauses that specify semantic relationships be- tween terms in the ontology, as well as under a given set of negative constraints. We formally define the notion of a {\textquotedblleft}wit- ness{\textquotedblright} to the integrability of two RDF ontologies under such constraints. A witness represents a way of integrating the ontologies together. We define a {\textquotedblleft}minimal{\textquotedblright} witnesses and provide the polynomial CROW (Computing RDF Ontology Witness) algorithm to find a witness. We report on the per- formance of CROW both on DAML, SchemaWeb and Onto- Broker ontologies as well as on synthetically generated data. The experiments show that CROW works very well on real- life ontologies and scales to massive ontologies. }, author = {Udrea,O. and Deng,Y. and Ruckhaus,E. and V.S. Subrahmanian} } @article {13001, title = {Grid computing}, journal = {EDUCAUSE Review}, volume = {40}, year = {2005}, month = {2005///}, pages = {116 - 117}, author = {Cummings, Michael P. and Huskamp,J. C} } @article {18219, title = {Group-based joint coding and embedding technique for multimedia fingerprinting}, journal = {Proc. SPIE}, volume = {5681}, year = {2005}, month = {2005///}, pages = {96 - 105}, abstract = {This paper proposes a group-based fingerprinting scheme employing a joint coding and embedding strategy totrace multimedia distribution and proactively prevent the leak of multimedia information. Taking advantage of the prior knowledge on the collusion pattern, we construct compact fingerprints that consist of user sub-codeword and group sub-codeword and are embedded in host signal via spread spectrum technique. The detection is done in two levels, which identifies guilty groups through correlation and then narrows down to specific colluders through minimum distance decoding. Experimental results show that the proposed method provides higher collusion resistance than the existing non-grouped fingerprint codes. }, author = {He,S. and Wu,M.} } @article {13223, title = {Gait recognition using image self-similarity}, journal = {EURASIP J. Appl. Signal Process.}, volume = {2004}, year = {2004}, month = {2004/01//}, pages = {572 - 585}, abstract = {Gait is one of the few biometrics that can be measured at a distance, and is hence useful for passive surveillance as well as biometric applications. Gait recognition research is still at its infancy, however, and we have yet to solve the fundamental issue of finding gait features which at once have suffcient discrimination power and can be extracted robustly and accurately from low-resolution video. This paper describes a novel gait recognition technique based on the image self-similarity of a walking person. We contend that the similarity plot encodes a projection of gait dynamics. It is also correspondence-free, robust to segmentation noise, and works well with low-resolution video. The method is tested on multiple data sets of varying sizes and degrees of diffculty. Performance is best for fronto-parallel viewpoints, whereby a recognition rate of 98\% is achieved for a data set of 6 people, and 70\% for a data set of 54 people.}, keywords = {behavioral biometrics, gait recognition, human identification at a distance, human movement analysis, pattern recognition}, isbn = {1110-8657}, doi = {10.1155/S1110865704309236}, url = {http://dx.doi.org/10.1155/S1110865704309236}, author = {BenAbdelkader,Chiraz and Cutler,Ross G. and Davis, Larry S.} } @article {12715, title = {Gait-based human identification from a monocular video sequence}, journal = {Handbook on Pattern Recognition and Computer Vision}, year = {2004}, month = {2004///}, abstract = {Human gait is a spatio-temporal phenomenon that characterizes the motion char-acteristics of an individual. It is possible to detect and measure gait even in low- resolution video. In this chapter, we discuss algorithms for identifying people by their gait from a monocular video sequence. Human identification using gait, sim- ilar to text-based speaker identification, involves different individuals performing the same task and a template-matching approach is suitable for such problems. In situations where the amount of training data is limited, we demonstrate the utility of a simple width feature for gait recognition. By virtue of their determin- istic nature, template matching methods have limited noise resilience. In order to deal with noise we introduce a systematic approach to gait recognition by building representations for the structural and dynamic components of gait using exemplars and hidden Markov models (HMMs). The above methods assume that an exact side-view of the subject is available in the probe sequence. For the case when the person walks at an arbitrary angle far away from the camera we present a view invariant gait recognition algorithm which is based on synthesizing a side view of a person from an arbitrary monocular view. }, author = {Kale, A. and Sundaresan, A. and Roy Chowdhury, A.K. and Chellapa, Rama} } @conference {12293, title = {A game-theoretic framework for analyzing trust-inference protocols}, booktitle = {Workshop on Economics of Peer-to-Peer Systems}, year = {2004}, month = {2004///}, abstract = {We propose a novel game-theoretic framework foranalyzing the robustness of trust-inference protocols in the presence of adversarial (but rational) users. To the best of our knowledge, this is the first such framework which simultaneously (1) admits a rigor- ous and precise definition, thereby enabling formal proofs of security (in various adversarial settings) for specific trust-inference protocols; (2) is flexible enough to accommodate a full range of (realistic) ad- versarial behavior and network models; and (3) is ap- propriate for decentralized networks, and in particu- lar does not posit a trusted, centralized party with complete knowledge of the system history. We also show some preliminary results regarding the design of trust-inference protocols which can be rigorously proven secure within our model. In addition to establishing a solid foundation for future work, our framework also enables a rigorous and objective comparison among existing trust inference protocols. }, author = {Morselli,R. and Katz, Jonathan and Bhattacharjee, Bobby} } @article {14876, title = {Generalized photometric stereo and its application to face recognition}, journal = {International Journal of Computer Vision}, year = {2004}, month = {2004///}, abstract = {Most photometric stereo algorithms employ a Lambertian reflectance model witha varying albedo field and involve the appearances of only one object. The recovered albedos and surface normals are object-specific and appearances not belonging to the object cannot be easily handled. We generalize photometric stereo algorithms to handle all appearances of all objects in a class, in particular the human face class, by assuming that albedos and surface normals of all objects in the class be rank-constrained, i.e. lie in a subspace. Rank constraints lead us to a factorization of an observation matrix that consists of exemplar images of different objects under different illuminations. To fully recover the subspace bases or class- specific albedos and surface normals, we employ integrability and face symmetry constraints and propose a linearized algorithm. This algorithm takes into account the effects of the varying albedo field by approximating the integrability terms using only the surface normals. We then apply our generalized photometric stereo algorithm for recognizing faces under illumination variations. As far as recognition is concerned, we can utilize a bootstrap set which is just a collection of 2D image observations to avoid an explicit requirement that 3D information be available. We obtain good recognition results using the PIE database. }, author = {Zhou, S. and Chellapa, Rama and Jacobs, David W.} } @article {15179, title = {A generic construction for intrusion-resilient public-key encryption}, journal = {Topics in Cryptology{\textendash}CT-RSA 2004}, year = {2004}, month = {2004///}, pages = {1997 - 1997}, abstract = {In an intrusion-resilient cryptosystem [10], two entities (a user and a base) jointly evolve a secret decryption key; this provides very strong protection against an active attacker who can break into the user and base repeatedly and even simultaneously. Recently, a construction of an intrusion-resilient public-key encryption scheme based on specific algebraic assumptions has been shown [6]. We generalize this previous work and present a more generic construction for intrusion-resilient public-key encryption from any forward-secure public-key encryption scheme satisfying a certain homomorphic property.}, doi = {10.1007/978-3-540-24660-2_7}, author = {Dodis,Y. and Franklin,M. and Katz, Jonathan and Miyaji,A. and Yung,M.} } @conference {13035, title = {Generic sentence fusion is an ill-defined summarization task}, booktitle = {Proceedings of the Text Summarization Branches Out Workshop at ACL}, volume = {4}, year = {2004}, month = {2004///}, pages = {96 - 103}, author = {Daum{\'e}, Hal and Marcu,D.} } @article {18843, title = {Geometric algorithms for automated design of multi-piece permanent molds}, journal = {Computer-Aided Design}, volume = {36}, year = {2004}, month = {2004/03//}, pages = {241 - 260}, abstract = {Multi-piece molds, which consist of more than two mold pieces, are capable of producing very complex parts{\textemdash}parts that cannot be produced by the traditional molds. The tooling cost is also low for multi-piece molds, which makes it a candidate for pre-production prototyping and bridge tooling. However, designing multi-piece molds is a time-consuming task. This article describes geometric algorithms for automated design of multi-piece molds. A multi-piece mold design algorithm has been developed to automate several important mold-design steps: finding parting directions, locating parting lines, creating parting surfaces, and constructing mold pieces. This algorithm constructs mold pieces based on global accessibility analysis results of the part and therefore guarantees the disassembly of the mold pieces. A software system has been developed, which has been successfully tested on several complex industrial parts.}, keywords = {mold design, Multi-piece molds, spatial partitioning}, isbn = {0010-4485}, doi = {10.1016/S0010-4485(03)00107-6}, url = {http://www.sciencedirect.com/science/article/pii/S0010448503001076}, author = {Priyadarshi,Alok K. and Gupta, Satyandra K.} } @article {18844, title = {Geometric algorithms for automated design of rotary-platen multi-shot molds}, journal = {Computer-Aided Design}, volume = {36}, year = {2004}, month = {2004/10//}, pages = {1171 - 1187}, abstract = {This paper describes algorithms for automated design of rotary-platen type of multi-shot molds for manufacturing multi-material objects. The approach behind our algorithms works in the following manner. First, we classify the given multi-material object into several basic types based on the relationships among different components in the object. For every basic type, we find a molding sequence based on the precedence constraints resulting due to accessibility and disassembly requirements. Then, starting from the last mold stage, we generate the mold pieces for every mold stage. We expect that algorithms described in this paper will provide the necessary foundations for automating the design of rotary-platen molds.}, keywords = {geometric reasoning, mold design, Multi-shot molds}, isbn = {0010-4485}, doi = {10.1016/j.cad.2003.11.003}, url = {http://www.sciencedirect.com/science/article/pii/S0010448503002331}, author = {Li,Xuejun and Gupta, Satyandra K.} } @conference {18788, title = {Geometric Containment Analysis for Rotational Parts}, year = {2004}, month = {2004///}, abstract = {This paper describes a system and underlying algorithms toperform geometric containment analysis to determine if a newly designed rotational part can be manufactured from a part in an existing database of rotational parts. Only material removal of the database part is considered in order to obtain the newly designed part from the database part. The system uses a three-step algorithm to test for containment. The first step analyzes feasibility of containment using bounding cylinders. If the bounding cylinder of the query part is bigger than the part in the database, then the database part cannot contain the query part and it is eliminated from consideration. The second step analyzes feasibility of containment by ignoring off-axis features. Any part that fails to satisfy containment at this stage is eliminated from consideration. The third step analyzes the remaining parts from the database for feasibility of containment by including the off-axis features. Finally, the system rank- orders all the database parts that can contain the query part based on their volume differences with the query part. The system described in this paper can be used to find an existing part from which to manufacture a newly designed part. This capability is expected to significantly reduce proliferation of parts, to improve manufacturing responsiveness, and to reduce the cost of new products. }, url = {ftp://ftp.eng.umd.edu/:/home/glue/s/k/skgupta/pub/Publication/DETC04_Karnik.pdf}, author = {Karnik,M. and Gupta,S.K. and Magrab,E. B.} } @article {18648, title = {A global-state-triggered fault injector for distributed system evaluation}, journal = {Parallel and Distributed Systems, IEEE Transactions on}, volume = {15}, year = {2004}, month = {2004/07//}, pages = {593 - 605}, abstract = {Validation of the dependability of distributed systems via fault injection is gaining importance because distributed systems are being increasingly used in environments with high dependability requirements. The fact that distributed systems can fail in subtle ways that depend on the state of multiple parts of the system suggests that a global-state-based fault injection mechanism should be used to validate them. However, global-state-based fault injection is challenging since it is very difficult in practice to maintain the global state of a distributed system at runtime with minimal intrusion into the system execution. We present Loki, a global-state-based fault injector, which has been designed with the goals of low intrusion, high precision, and high flexibility. Loki achieves these goals by utilizing the ideas of partial view of global state, optimistic synchronization, and offline analysis. In Loki, faults are injected based on a partial, view of the global state of the system, and a post-runtime analysis is performed to place events and injections into a single global timeline and to discard experiments with incorrect fault injections. Finally, the experiments with correct fault injections are used to estimate user-specified performance and dependability measures. A flexible measure language has been designed that facilitates the specification of a wide range of measures.}, keywords = {distributed processing, distributed system evaluation, fault tolerant computing, global-state-based fault injection mechanism, Loki, offline clock synchronization, performance evaluation, post-runtime analysis, Synchronisation, system recovery, user-specified performance}, isbn = {1045-9219}, doi = {10.1109/TPDS.2004.14}, author = {Chandra,Ramesh and Lefever,R.M. and Joshi,K.R. and Michel Cukier and Sanders,W. H.} } @article {18220, title = {Group-oriented fingerprinting for multimedia forensics}, journal = {EURASIP J. Appl. Signal Process.}, volume = {2004}, year = {2004}, month = {2004/01//}, pages = {2153 - 2173}, abstract = {Digital fingerprinting of multimedia data involves embedding information in the content signal and offers protection to the digital rights of the content by allowing illegitimate usage of the content to be identified by authorized parties. One potential threat to fingerprinting is collusion, whereby a group of adversaries combine their individual copies in an attempt to remove the underlying fingerprints. Former studies indicate that collusion attacks based on a few dozen independent copies can confound a fingerprinting system that employs orthogonal modulation. However, in practice an adversary is more likely to collude with some users than with other users due to geographic or social circumstances. To take advantage of prior knowledge of the collusion pattern, we propose a two-tier group-oriented fingerprinting scheme where users likely to collude with each other are assigned correlated fingerprints. Additionally, we extend our construction to represent the natural social and geographic hierarchical relationships between users by developing a more flexible tree-structure-based fingerprinting system. We also propose a multistage colluder identification scheme by taking advantage of the hierarchial nature of the fingerprints. We evaluate the performance of the proposed fingerprinting scheme by studying the collusion resistance of a fingerprinting system employing Gaussian-distributed fingerprints. Our results show that the group-oriented fingerprinting system provides the superior collusion resistance over a system employing orthogonal modulation when knowledge of the potential collusion pattern is available.}, keywords = {collusion resistance, group-oriented fingerprinting, multimedia fingerprinting, multimedia forensics, multistage colluder identification}, isbn = {1110-8657}, doi = {10.1155/S1110865704312151}, url = {http://dx.doi.org/10.1155/S1110865704312151}, author = {Wang,Z. Jane and M. Wu and Trappe,Wade and Liu,K. J.R} } @article {17600, title = {Guest editors{\textquoteright} foreword: special issue: 35th annual ACM symposium on theory of computing}, journal = {Journal of Computer and System Sciences}, volume = {69}, year = {2004}, month = {2004///}, pages = {305 - 305}, author = {Khanna,S. and Srinivasan, Aravind} } @conference {13558, title = {Gabor Filter Based Multi-class Classifier for Scanned Document Images}, booktitle = {7th International Conference on Document Analysis and Recognition (ICDAR)}, year = {2003}, month = {2003///}, pages = {968 - 972}, abstract = {When scanning documents with a large number of pagessuch as books, it is often feasible to provide a minimal number of training samples to personalize the system to compensate for global shifts in how the document was created or in scanning parameters. In this paper, we present a supervised multi-class classifier based on Gabor filters that is used to classify the scripts, font-faces, and font-styles (bold, italic, normal etc.) in an application where the classes are known. Classification is performed at the word level (glyphs separated by white space) given training samples of each class. This method was applied to a variety of bilingual dictionaries to identify different scripts, and simultaneously, to classify Roman scripts into bold, italic and normal font-styles. Experimental results show the effectiveness of this approach in increasing performance over classifiers trained for general documents. }, author = {Ma,H. and David Doermann} } @inbook {12741, title = {Gait Analysis for Human Identification}, booktitle = {Audio- and Video-Based Biometric Person AuthenticationAudio- and Video-Based Biometric Person Authentication}, series = {Lecture Notes in Computer Science}, volume = {2688}, year = {2003}, month = {2003///}, pages = {1058 - 1058}, publisher = {Springer Berlin / Heidelberg}, organization = {Springer Berlin / Heidelberg}, abstract = {Human gait is an attractive modality for recognizing people at a distance. In this paper we adopt an appearance-based approach to the problem of gait recognition. The width of the outer contour of the binarized silhouette of a walking person is chosen as the basic image feature. Different gait features are extracted from the width vector such as the dowsampled, smoothed width vectors, the velocity profile etc. and sequences of such temporally ordered feature vectors are used for representing a person{\textquoteright}s gait. We use the dynamic time-warping (DTW) approach for matching so that non-linear time normalization may be used to deal with the naturally-occuring changes in walking speed. The performance of the proposed method is tested using different gait databases.}, isbn = {978-3-540-40302-9}, url = {http://dx.doi.org/10.1007/3-540-44887-X_82}, author = {Kale, A. and Cuntoor, N. and Yegnanarayana,B. and Rajagopalan, AN and Chellapa, Rama}, editor = {Kittler,Josef and Nixon,Mark} } @article {18892, title = {A General Approach to Synthesize Problem-Specific Planners}, year = {2003}, month = {2003/10/27/}, institution = {Department of Computer Science, University of Maryland, College Park}, abstract = {In this paper, we describe a way to improve the performance of hand-tailorable planners by compiling each domain description into a separate domain-specific planner. We discuss why and when this approach can be useful, and we present experimental results showing that our approach produces significant increases in the speed of planning.}, keywords = {*PLANNING, *SOFTWARE ENGINEERING, Artificial intelligence, COMPUTER PROGRAMMING AND SOFTWARE, COMPUTER PROGRAMS, Logic, problem solving}, url = {http://stinet.dtic.mil/oai/oai?\&verb=getRecord\&metadataPrefix=html\&identifier=ADA455023}, author = {Ilghami,Okhtay and Nau, Dana S.} } @conference {16703, title = {A generative probabilistic OCR model for NLP applications}, booktitle = {Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume 1}, year = {2003}, month = {2003///}, pages = {55 - 62}, author = {Kolak,O. and Byrne,W. and Resnik, Philip} } @article {13000, title = {Genetic consequences of ecological reserve design guidelines: An empirical investigation}, journal = {Conserv Genet}, volume = {4}, year = {2003}, month = {2003///}, pages = {427 - 439}, abstract = {We assessed the genetic diversity consequences of applying ecological reserve design guidelines to four federally-listed globally-rare plant species. Consequences were measured using two metrics: proportion of all alleles and of common alleles included in reserves. Common alleles were defined as those alleles having a frequency of greater than or equal to0.05 in at least one population. Four conservation professionals applied ecological reserve guidelines to choose specific populations of each species for inclusion in reserves of size 1 to N - 1, where N is the total number of populations of each species. Information regarding genetic diversity was not used in selecting populations. The resulting reserve designs were compared to random designs, and the agreement among experts was assessed using Kendall{\textquoteright}s coefficient of concordance. Application of ecological reserve design guidelines proved mostly ineffective in capturing more genetic diversity than is captured selecting populations randomly. Meeting established targets for genetic diversity, such as one advocated by the Center for Plant Conservation, required larger numbers of populations than are suggested to be sufficient. Relative performance of expert designs differed among species and was dependent on whether the proportion of all alleles or of common alleles was used as a measure of diversity. Furthermore there was no significant concordance among experts in order in which populations were incorporated into reserves as experts differed in priority they placed on individual guidelines.}, keywords = {albens;, Astragulus, Bernardino, conservation, conservation;, design;, diversity;, Erigeron, Eriogonum, genetic, genetics;, goodmaniana;, Mountains, ovalifolium, Oxytheca, parishii, parishii;, plant, reserve, San, var., vineum;}, author = {Neel,M. C and Cummings, Michael P.} } @article {16290, title = {The genome sequence of Bacillus anthracis Ames and comparison to closely related bacteria}, journal = {Nature}, volume = {423}, year = {2003}, month = {2003/05/01/}, pages = {81 - 86}, abstract = {Bacillus anthracis is an endospore-forming bacterium that causes inhalational anthrax1. Key virulence genes are found on plasmids (extra-chromosomal, circular, double-stranded DNA molecules) pXO1 (ref. 2) and pXO2 (ref. 3). To identify additional genes that might contribute to virulence, we analysed the complete sequence of the chromosome of B. anthracis Ames (about 5.23 megabases). We found several chromosomally encoded proteins that may contribute to pathogenicity{\textemdash}including haemolysins, phospholipases and iron acquisition functions{\textemdash}and identified numerous surface proteins that might be important targets for vaccines and drugs. Almost all these putative chromosomal virulence and surface proteins have homologues in Bacillus cereus, highlighting the similarity of B. anthracis to near-neighbours that are not associated with anthrax4. By performing a comparative genome hybridization of 19 B. cereus and Bacillus thuringiensis strains against a B. anthracis DNA microarray, we confirmed the general similarity of chromosomal genes among this group of close relatives. However, we found that the gene sequences of pXO1 and pXO2 were more variable between strains, suggesting plasmid mobility in the group. The complete sequence of B. anthracis is a step towards a better understanding of anthrax pathogenesis.}, isbn = {0028-0836}, doi = {10.1038/nature01586}, url = {http://www.nature.com/nature/journal/v423/n6935/full/nature01586.html}, author = {Read,Timothy D. and Peterson,Scott N. and Tourasse,Nicolas and Baillie,Les W. and Paulsen,Ian T. and Nelson,Karen E. and Tettelin,Herv|[eacute]| and Fouts,Derrick E. and Eisen,Jonathan A. and Gill,Steven R. and Holtzapple,Erik K. and |[Oslash]|kstad,Ole Andreas and Helgason,Erlendur and Rilstone,Jennifer and Wu,Martin and Kolonay,James F. and Beanan,Maureen J. and Dodson,Robert J. and Brinkac,Lauren M. and Gwinn,Michelle and DeBoy,Robert T. and Madpu,Ramana and Daugherty,Sean C. and Durkin,A. Scott and Haft,Daniel H. and Nelson,William C. and Peterson,Jeremy D. and Pop, Mihai and Khouri,Hoda M. and Radune,Diana and Benton,Jonathan L. and Mahamoud,Yasmin and Jiang,Lingxia and Hance,Ioana R. and Weidman,Janice F. and Berry,Kristi J. and Plaut,Roger D. and Wolf,Alex M. and Watkins,Kisha L. and Nierman,William C. and Hazen,Alyson and Cline,Robin and Redmond,Caroline and Thwaite,Joanne E. and White,Owen and Salzberg,Steven L. and Thomason,Brendan and Friedlander,Arthur M. and Koehler,Theresa M. and Hanna,Philip C. and Kolst|[oslash]|,Anne-Brit and Fraser,Claire M.} } @article {15387, title = {Geometrical analysis of precessional switching and relaxation in uniformly magnetized bodies}, journal = {Magnetics, IEEE Transactions on}, volume = {39}, year = {2003}, month = {2003/09//}, pages = {2501 - 2503}, abstract = {Precessional switching and relaxation in a single-domain particle or film is studied by using the Landau-Lifshitz-Gilbert equation. The analysis of the switching process is based on the explicit knowledge of two integrals of motion for the magnetization dynamics in the conservative case. The knowledge of these integrals of motions enables one to carry out the geometrical analysis of the system and give the complete phase portrait. The relaxation process which occurs after the magnetization is reversed is analyzed by using geometrical methods and it is showed that the dynamical system exhibits entanglement of separatrices and riddled basins of attraction.}, keywords = {analysis;, attraction;, basins, bodies;, dynamical, dynamics;, entanglement;, equation;, film;, films;, geometrical, integrals, Landau-Lifshitz-Gilbert, magnetic, magnetisation, magnetization, magnetized, motion;, of, particle;, particles;, phase, portrait;, precessional, relaxation;, reversal;, riddled, separatrices;, single-domain, spin, switching;, system;, thin, uniformly}, isbn = {0018-9464}, doi = {10.1109/TMAG.2003.816453}, author = {Bertotti,G. and Mayergoyz, Issak D and Serpico,C. and d{\textquoteright}Aquino,M.} } @article {12337, title = {Goal-Driven Reconfiguration of Polymorphous Architectures}, journal = {Domain-specific processors: systems, architectures, modeling, and simulation}, volume = {20}, year = {2003}, month = {2003///}, pages = {151 - 151}, author = {Lohani,S. and Bhattacharyya, Shuvra S.} } @conference {13562, title = {Groundtruth Image Generation from Electronic Text (Demonstration)}, booktitle = {Symposium on Document Image Understanding Technology}, year = {2003}, month = {2003/04//}, pages = {309 - 312}, author = {David Doermann and Zi,G.} } @article {13234, title = {Guest editors{\textquoteright} Introduction to the special section on energy minimization methods in computer vision and pattern recognition}, journal = {Pattern Analysis and Machine Intelligence, IEEE Transactions on}, volume = {25}, year = {2003}, month = {2003/11//}, pages = {1361 - 1363}, isbn = {0162-8828}, doi = {10.1109/TPAMI.2003.1240110}, author = {Figueiredo,M.A.T. and Hancock,E.R. and Pelillo,M. and Zerubia, J.} } @article {15448, title = {GUI ripping: Reverse engineering of graphical user interfaces for testing}, journal = {Proceedings of the 10th working conference on reverse engineering (WCRE{\textquoteright}03)}, volume = {1095}, year = {2003}, month = {2003///}, pages = {17 - 00}, abstract = {Graphical user interfaces (GUIs) are important parts oftoday{\textquoteright}s software and their correct execution is required to ensure the correctness of the overall software. A popular technique to detect defects in GUIs is to test them by exe- cuting test cases and checking the execution results. Test cases may either be created manually or generated auto- matically from a model of the GUI. While manual testing is unacceptably slow for many applications, our experience with GUI testing has shown that creating a model that can be used for automated test case generation is difficult. We describe a new approach to reverse engineer a model represented as structures called a GUI forest, event-flow graphs and an integration tree directly from the executable GUI. We describe {\textquotedblleft}GUI Ripping{\textquotedblright}, a dynamic process in which the software{\textquoteright}s GUI is automatically {\textquotedblleft}traversed{\textquotedblright} by opening all its windows and extracting all their widgets (GUI objects), properties, and values. The extracted infor- mation is then verified by the test designer and used to auto- matically generate test cases. We present algorithms for the ripping process and describe their implementation in a tool suite that operates on Java and Microsoft Windows{\textquoteright} GUIs. We present results of case studies which show that our approach requires very little human intervention and is es- pecially useful for regression testing of software that is mod- ified frequently. We have successfully used the {\textquotedblleft}GUI Rip- per{\textquotedblright} in several large experiments and have made it avail- able as a downloadable tool. }, author = {Memon, Atif M. and Banerjee,I. and Nagarajan,A.} } @article {18572, title = {Guidelines for interdomain traffic engineering}, journal = {SIGCOMM Comput. Commun. Rev.}, volume = {33}, year = {2003}, month = {2003/10//}, pages = {19 - 30}, abstract = {Network operators must have control over the flow of traffic into, out of, and across their networks. However, the Border Gateway Protocol (BGP) does not facilitate common traffic engineering tasks, such as balancing load across multiple links to a neighboring AS or directing traffic to a different neighbor. Solving these problems is difficult because the number of possible changes to routing policies is too large to exhaustively test all possibilities, some changes in routing policy can have an unpredictable effect on the flow of traffic, and the BGP decision process implemented by router vendors limits an operator{\textquoteright}s control over path selection.We propose fundamental objectives for interdomain traffic engineering and specific guidelines for achieving these objectives within the context of BGP. Using routing and traffic data from the AT\&T backbone we show how certain BGP policy changes can move traffic in a predictable fashion, despite limited knowledge about the routing policies in neighboring AS{\textquoteright}s. Then, we show how operators can gain greater flexibility by relaxing some steps in the BGP decision process and ensuring that neighboring AS{\textquoteright}s send consistent advertisements at each peering location. Finally, we show that an operator can manipulate traffic efficiently by changing the routes for a small number of prefixes (or groups of related prefixes) that consistently receive a large amount of traffic.}, isbn = {0146-4833}, doi = {10.1145/963985.963988}, url = {http://doi.acm.org/10.1145/963985.963988}, author = {Feamster, Nick and Borkenhagen,Jay and Rexford,Jennifer} } @article {18837, title = {Generating 3D Models of MEMS Devices by Process Emulation}, volume = {ISR; TR 2002-57}, year = {2002}, month = {2002///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {MEMS designers often use numerical simulation for detecting errors in the mask layout. Numerical simulation involves generating 3D models of MEMS device from the mask layout and process description. The generated models can be meshed and simulated over different domains. This report describes an efficient algorithm that can generate 3D geometric models of MEMS devices. Specifically, the algorithm emulates the manufacturing of a single functional polysilicon layer MEMS devices using the MUMPSprocess.}, keywords = {Next-Generation Product Realization Systems}, url = {http://drum.lib.umd.edu//handle/1903/6285}, author = {Bellam,S. and Gupta, Satyandra K. and Priyadarshi,A. K.} } @article {13776, title = {Generating A Parsing Lexicon from an LCS-Based Lexicon}, journal = {LREC 2002 Workshop Proceedings: Linguistic Knowledge Acquisition and Representation: Bootstrapping Annotated Language Data}, year = {2002}, month = {2002///}, abstract = {This paper describes a technique for generating parsing lexicons for a principle-based parser (Minipar). Our approach mapslexical entries in a large LCS-based repository of semantically classified verbs to their corresponding syntactic patterns. A by-product of this mapping is a lexicon that is directly usable in the Minipar system. We evaluate the accuracy and coverage of this lexicon using LDOCE syntactic codes as a gold standard. We show that this lexicon is comparable to the hand-generated Minipar lexicon (i.e., similar recall and precision values). In a later experiment, we automate the process of mapping between the LCS-based repository and syntactic patterns. The advantage of automating the process is that the same technique can be applied directly to lexicons we have for other languages, for example, Arabic, Chinese, and Spanish. }, author = {Ayan,N.F. and Dorr, Bonnie J} } @article {13777, title = {Generating A Parsing Lexicon From Lexical-Conceptual Structure}, year = {2002}, month = {2002///}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {This paper describes the generation of a lexicon for a principle-based parser (Minipar[5,6]) using descriptions of verbs based on Lexical-Conceptual Structure (LCS [1,2]).1 We aim to determine how much syntactic information we can obtain from a semantic- based lexicon. More specifically, we aim to provide a general approach to projection of syntactic entries from semantic (language-independent) lexicons-and to test the effect of such lexicons on parser performance. Verbs are grouped together into classes-each denoted by an LCS representation adn the thematic grid. These are mapped systemat- ically into syntactic categories associated with entries in the Minipar parser. The main advantage of this LCS-to-syntax projection is language protability: We currently have LCS lexicons for English, Arabic, Spanish, and Chinese; thus, our LCS-projection ap- proach allows us to produce syntactic lexicons for parsing in each of these languages. For comparing the performance of the projection from the LCS to Minpar coes, we also generated the mappings for the codes of Longman{\textquoteright}s Directionary of Contemporary En- glish (LDOCE [8])-the most comprehensive online dictionary for syntactic categorization. Preliminary experiments indicate that our approach yields a categorization of verbs with 58\% precision and 65\% recall as measured against LDOCE-with an improved precision of 74\% when redundancy is removed. The next section presents a brief description of each code set we use. In Section 3, we explain how we generated Minipar codes from LCS representation. Finally, Section 4, discusses our experiments and results. }, author = {Ayan,N.F. and Dorr, Bonnie J} } @article {12752, title = {A generic approach to simultaneous tracking and verification in video}, journal = {Image Processing, IEEE Transactions on}, volume = {11}, year = {2002}, month = {2002/05//}, pages = {530 - 544}, abstract = {A generic approach to simultaneous tracking and verification in video data is presented. The approach is based on posterior density estimation using sequential Monte Carlo methods. Visual tracking, which is in essence a temporal correspondence problem, is solved through probability density propagation, with the density being defined over a proper state space characterizing the object configuration. Verification is realized through hypothesis testing using the estimated posterior density. In its most basic form, verification can be performed as follows. Given a measurement vector Z and two hypotheses H1 and H0, we first estimate posterior probabilities P(H0|Z) and P(H1|Z), and then choose the one with the larger posterior probability as the true hypothesis. Several applications of the approach are illustrated by experiments devised to evaluate its performance. The idea is first tested on synthetic data, and then experiments with real video sequences are presented, illustrating vehicle tracking and verification, human (face) tracking and verification, facial feature tracking, and image sequence stabilization.}, keywords = {approach;, Carlo, configuration;, correspondence, data;, density, density;, estimated, estimation;, evaluation;, extraction;, Face, facial, feature, generic, human, hypothesis, image, measurement, methods;, Monte, object, performance, posterior, probability, probability;, problem;, processing;, propagation;, recognition;, road, sequence, sequences;, sequential, signal, space;, stabilization;, state, synthetic, temporal, testing;, tracking;, vector;, vehicle, vehicles;, verification;, video, visual}, isbn = {1057-7149}, doi = {10.1109/TIP.2002.1006400}, author = {Li,Baoxin and Chellapa, Rama} } @article {12822, title = {Generic tools for verifying concurrent systems}, journal = {Science of Computer Programming}, volume = {42}, year = {2002}, month = {2002/01//}, pages = {39 - 47}, abstract = {Despite the enormous strides made in automatic verification technology over the past decade and a half, tools such as model checkers remain relatively underused in the development of software. One reason for this is that the bewildering array of specification and verification formalisms complicates the development and adoption by users of relevant tool support. This paper proposes a remedy to this state of affairs in the case of finite-state concurrent systems by describing an approach to developing customizable yet efficient verification tools.}, keywords = {Model checking, Operational semantics, Process algebra, Specification, verification, Verification tools}, isbn = {0167-6423}, doi = {10.1016/S0167-6423(01)00033-8}, url = {http://www.sciencedirect.com/science/article/pii/S0167642301000338}, author = {Cleaveland, Rance and Sims,Steven T.} } @article {16270, title = {Genome sequence and comparative analysis of the model rodent malaria parasite Plasmodium yoelii yoelii}, journal = {Nature}, volume = {419}, year = {2002}, month = {2002/10/03/}, pages = {512 - 519}, abstract = {Species of malaria parasite that infect rodents have long been used as models for malaria disease research. Here we report the whole-genome shotgun sequence of one species, Plasmodium yoelii yoelii, and comparative studies with the genome of the human malaria parasite Plasmodium falciparum clone 3D7. A synteny map of 2,212 P. y. yoelii contiguous DNA sequences (contigs) aligned to 14 P. falciparum chromosomes reveals marked conservation of gene synteny within the body of each chromosome. Of about 5,300 P. falciparum genes, more than 3,300 P. y. yoelii orthologues of predominantly metabolic function were identified. Over 800 copies of a variant antigen gene located in subtelomeric regions were found. This is the first genome sequence of a model eukaryotic parasite, and it provides insight into the use of such systems in the modelling of Plasmodium biology and disease.}, isbn = {0028-0836}, doi = {10.1038/nature01099}, url = {http://www.nature.com/nature/journal/v419/n6906/full/nature01099.html}, author = {Carlton,Jane M. and Angiuoli,Samuel V and Suh,Bernard B. and Kooij,Taco W. and Pertea,Mihaela and Silva,Joana C. and Ermolaeva,Maria D. and Allen,Jonathan E and Jeremy D Selengut and Koo,Hean L. and Peterson,Jeremy D. and Pop, Mihai and Kosack,Daniel S. and Shumway,Martin F. and Bidwell,Shelby L. and Shallom,Shamira J. and Aken,Susan E. van and Riedmuller,Steven B. and Feldblyum,Tamara V. and Cho,Jennifer K. and Quackenbush,John and Sedegah,Martha and Shoaibi,Azadeh and Cummings,Leda M. and Florens,Laurence and Yates,John R. and Raine,J. Dale and Sinden,Robert E. and Harris,Michael A. and Cunningham,Deirdre A. and Preiser,Peter R. and Bergman,Lawrence W. and Vaidya,Akhil B. and Lin,Leo H. van and Janse,Chris J. and Waters,Andrew P. and Smith,Hamilton O. and White,Owen R. and Salzberg,Steven L. and Venter,J. Craig and Fraser,Claire M. and Hoffman,Stephen L. and Gardner,Malcolm J. and Carucci,Daniel J.} } @article {16237, title = {Genome Sequence Assembly: Algorithms and Issues}, volume = {35}, year = {2002}, month = {2002///}, pages = {47 - 54}, abstract = {Ultimately, genome sequencing seeks to provide an organism{\textquoteright}s complete DNA sequence. Automation of DNA sequencing allowed scientists to decode entire genomes and gave birth to genomics, the analytic and comparative study of genomes. Although genomes can include billions of nucleotides, the chemical reactions researchers use to decode the DNA are accurate for only about 600 to 700 nucleotides at a time.The DNA reads that sequencing produces must then be assembled into a complete picture of the genome. Errors and certain DNA characteristics complicate assembly. Resolving these problemsentails an additional and costly finishing phase that involves extensive human intervention. Assembly programs can dramatically reduce this cost by taking into account additional informationobtained during finishing. Algorithms that can assemble millions of DNA fragments into gene sequences underlie the current revolution in biotechnology, helping researchers build the growingdatabase of complete genomes.}, isbn = {0018-9162}, author = {Pop, Mihai and Salzberg,Steven L. and Shumway,Martin} } @article {12962, title = {Genomic profiles of clinical and environmental isolates of Vibrio cholerae O1 in cholera-endemic areas of Bangladesh}, journal = {Proceedings of the National Academy of Sciences}, volume = {99}, year = {2002}, month = {2002///}, pages = {12409 - 12409}, abstract = {Diversity, relatedness, and ecological interactions of toxigenic Vibrio cholerae O1 populations in two distinctive habitats, the human intestine and the aquatic environment, were analyzed. Twenty environmental isolates and 42 clinical isolates were selected for study by matching serotype, geographic location of isolation in Bangladesh, and season of isolation. Genetic profiling was done by enterobacterial repetitive intergenic consensus sequence{\textendash}PCR, optimized for profiling by using the fully sequenced V. cholerae El Tor N16961 genome. Five significant clonal clusters of haplotypes were found from 57 electrophoretic types. Isolates from different areas or habitats intermingled in two of the five significant clusters. Frequencies of haplotypes differed significantly only between the environmental populations (exact test; P < 0.05). Analysis of molecular variance yielded a population genetic structure reflecting the differentiating effects of geographic area, habitat, and sampling time. Although a parameter confounding the latter differences explained 9\% of the total molecular variance in the entire population (P < 0.01), the net effect of habitat and time could not be separated because of the small number of environmental isolates included in the study. Five subpopulations from a single area were determined, and from these we were able to estimate a relative differentiating effect of habitat, which was small compared with the effect of temporal change. In conclusion, the resulting population structure supports the hypothesis that spatial and temporal fluctuations in the composition of toxigenic V. cholerae populations in the aquatic environment can cause shifts in the dynamics of the disease.}, isbn = {0027-8424, 1091-6490}, doi = {10.1073/pnas.192426499}, url = {http://www.pnas.org/content/99/19/12409}, author = {Zo,Y. G. and Rivera,I. N. G. and E. Russek-Cohen and Islam,M. S. and Siddique,A. K. and Yunus,M. and Sack,R. B. and Huq,A. and Rita R Colwell} } @conference {17178, title = {Getting real about speech: overdue or overhyped?}, booktitle = {CHI {\textquoteright}02 extended abstracts on Human factors in computing systems}, series = {CHI EA {\textquoteright}02}, year = {2002}, month = {2002///}, pages = {708 - 709}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {Speech has recently made headway towards becoming a more mainstream interface modality. For example, there is an increasing number of call center applications, especially in the airline and banking industries. However, speech still has many properties that cause its use to be problematic, such as its inappropriateness in both very quiet and very noisy environments, and the tendency of speech to increase cognitive load. Concerns about such problems are valid; however, they do not explain why the use of speech is so controversial in the HCI community. This panel would like to address the issues underlying the controversy around speech, by discussing the current state of the art, the reasons it is so difficult to build a good speech interface, and how HCI research can contribute to the development of speech interfaces.}, keywords = {cognitive load, social responses, speech interfaces}, isbn = {1-58113-454-1}, doi = {10.1145/506443.506557}, url = {http://doi.acm.org/10.1145/506443.506557}, author = {James,Frankie and Lai,Jennifer and Suhm,Bernhard and Balentine,Bruce and Makhoul,John and Nass,Clifford and Shneiderman, Ben} } @conference {13047, title = {GLEANS: A generator of logical extracts and abstracts for nice summaries}, booktitle = {Workshop on Automatic Summarization}, year = {2002}, month = {2002///}, pages = {9 - 14}, author = {Daum{\'e}, Hal and Echihabi,A. and Marcu,D. and Munteanu,D. and Soricut,R.} } @article {15438, title = {GUI testing: Pitfalls and process}, journal = {IEEE Computer}, volume = {35}, year = {2002}, month = {2002///}, pages = {87 - 88}, author = {Memon, Atif M.} } @conference {15319, title = {Gathering knowledge for a question answering system from heterogeneous information sources}, booktitle = {Proceedings of the workshop on Human Language Technology and Knowledge Management - Volume 2001}, series = {HLTKM {\textquoteright}01}, year = {2001}, month = {2001///}, pages = {9:1{\textendash}9:8 - 9:1{\textendash}9:8}, publisher = {Association for Computational Linguistics}, organization = {Association for Computational Linguistics}, address = {Stroudsburg, PA, USA}, abstract = {Although vast amounts of information are available electronically today, no effective information access mechanism exists to provide humans with convenient information access. A general, open-domain question answering system is a solution to this problem. We propose an architecture for a collaborative question answering system that contains four primary components: an annotations system for storing knowledge, a ternary expression representation of language, a transformational rule system for handling some complexities of language, and a collaborative mechanism by which ordinary users can contribute new knowledge by teaching the system new information. We have developed a initial prototype, called Webnotator, with which to test these ideas.}, doi = {10.3115/1118220.1118229}, url = {http://dx.doi.org/10.3115/1118220.1118229}, author = {Katz,Boris and Jimmy Lin and Felshin,Sue} } @conference {18799, title = {A geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects}, series = {SMA {\textquoteright}01}, year = {2001}, month = {2001///}, pages = {278 - 288}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {This paper describes a geometric algorithm for automated design of multi-stage molds for manufacturing multi-material objects. In multi-stage molding process, the desired multi-material object is produced by carrying out multiple molding operations in a sequence, adding one material in the target object in each mold-stage. We model multi-material objects as an assembly of single-material components. Each mold-stage can only add one type of material. Therefore, we need a sequence of mold-stages such that (1) each mold-stage only adds one single-material component either fully or partially, and (2) the molding sequence completely produces the desired object. In other to find a feasible mold-stage sequence, our algorithm decomposes the multi-material object into a number of homogeneous components to find a feasible sequence of homogeneous components that can be added in sequence to produce the desired multi-material object. Our algorithm starts with the final object assembly and considers removing components either completely or partially from the object one-at-a-time such that it results in the previous state of the object assembly. If the component can be removed from the target object leaving the previous state of the object assembly a connected solid then we consider such decomposition a valid step in the stage sequence. This step is recursively repeated on new states of the object assembly, until the object assembly reaches a state where it only consists of one component. When an object-decomposition has been found that leads to a feasible stage sequence, the gross mold for each stage is computed and decomposed into two or more pieces to facilitate the molding operation. We expect that our algorithm will provide a step towards automating the design of multi-stage molds and therefore will help in reducing the mold design lead-time for multi-stage molds.}, keywords = {geometric reasoning, mold design, spatial partitioning}, isbn = {1-58113-366-9}, doi = {10.1145/376957.376989}, url = {http://doi.acm.org/10.1145/376957.376989}, author = {Kumar,Malay and Gupta, Satyandra K.} } @conference {18802, title = {A geometric algorithm for selecting optimal set of cutters for multi-part milling}, series = {SMA {\textquoteright}01}, year = {2001}, month = {2001///}, pages = {130 - 139}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {For the manufacture of milled parts, it is well known that the size of the cutter significantly affects the machining time. However, for small-batch manufacturing, the time spent on loading tools into the tool magazine and establishing z-length compensation values is just as important. If we can select a set of milling tools that will produce good machining time on more than one type of parts, then several unnecessary machine-tool reconfiguration operations can be eliminated. This paper describes a geometric algorithm for finding an optimal set of cutters for machining a set of 2{\textonehalf}D parts. In selecting milling cutters we consider both the tool loading time and the machining time and generate solutions that allow us to minimize the total machining time. Our problem formulation addresses the general problem of how to cover a target region to be milled with a cylindrical cutter without intersecting with the obstruction region; this definition allows us to handle both open and closed edges in the target region. Our algorithm improves upon previous work in the tool selection area in following ways: (1) in selecting cutters, it accounts for the tool loading time, and (2) it can simultaneously consider multiple different parts and select the optimal set of cutters to minimize the total manufacturing time.}, keywords = {computer-aided process planning, milling cutter selection}, isbn = {1-58113-366-9}, doi = {10.1145/376957.376973}, url = {http://doi.acm.org/10.1145/376957.376973}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @inbook {14221, title = {Geometry of Eye Design: Biology and Technology}, booktitle = {Multi-Image Analysis}, series = {Lecture Notes in Computer Science}, volume = {2032}, year = {2001}, month = {2001///}, pages = {22 - 38}, publisher = {Springer Berlin / Heidelberg}, organization = {Springer Berlin / Heidelberg}, abstract = {Natural or artificial vision systems process the images that they collect with their eyes or cameras in order to derive information for performing tasks related to navigation and recognition. Since the way images are acquired determines how dificult it is to perform a visual task, and since systems have to cope with limited resources, the eyes used by a specific system should be designed to optimize subsequent image processing as it relates to particular tasks. Different ways of sampling light, i.e., different eyes, may be less or more powerful with respect to particular competences. This seems intuitively evident in view of the variety of eye designs in the biological world. It is shown here that a spherical eye (an eye or system of eyes providing panoramic vision) is superior to a camera-type eye (an eye with restricted field of view) as regards the competence of three-dimensional motion estimation. This result is derived from a statistical analysis of all the possible computational models that can be used for estimating 3D motion from an image sequence. The findings explain biological design in a mathematical manner, by showing that systems that fly and thus need good estimates of 3D motion gain advantages from panoramic vision. Also, insights obtained from this study point to new ways of constructing powerful imaging devices that suit particular tasks in robotics, visualization and virtual reality better than conventional cameras, thus leading to a new camera technology.}, isbn = {978-3-540-42122-1}, url = {http://dx.doi.org/10.1007/3-540-45134-X_2}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.}, editor = {Klette,Reinhard and Gimel{\textquoteright}farb,Georgy and Huang,Thomas} } @article {18312, title = {Gesture-Driven Control of Spaces and Objects in Collaborative Augmented Reality}, journal = {GMD{\textendash}Forschungszentrum Informationstechnik GmbH}, year = {2001}, month = {2001///}, pages = {49 - 49}, author = {Yacoob,Yaser and Davis, Larry S.} } @article {17924, title = {Guest Editor{\textquoteright}s Introduction: Special Issue on Visualization 2000}, journal = {IEEE Transactions on Visualization and Computer Graphics}, volume = {7}, year = {2001}, month = {2001///}, pages = {193 - 194}, isbn = {1077-2626}, doi = {http://doi.ieeecomputersociety.org/10.1109/TVCG.2001.942687}, author = {Varshney, Amitabh} } @article {12810, title = {GCCS: A graphical coordination language for system specification}, journal = {Coordination Languages and Models}, year = {2000}, month = {2000///}, pages = {207 - 212}, author = {Cleaveland, Rance and Du,X. and Smolka,S.} } @article {17675, title = {A Generalization of Saad{\textquoteright}s Theorem on Rayleigh-Ritz Approximations}, volume = {UMIACS-TR-99-78}, year = {2000}, month = {2000/02/04/}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {Let $(\lambda,x)$ be an eigenpair of the Hermitian matrix $A$ of order$n$ and let $(\mu,u)$ be a Ritz pair from a subspace $\clk$ of $\comp^{2}$. Saad has given a simple inequality bounding $\sin\angle(x,u)$ in terms of $\sin\angle(x,\clk)$. In this note we show that this inequality can be extended to an equally simple inequality for eigenspaces of non-Hermitian matrices. (Also cross-referenced as UMIACS-TR-99-78) }, keywords = {Technical Report}, url = {http://drum.lib.umd.edu/handle/1903/1050}, author = {Stewart, G.W.} } @article {16787, title = {Generating dynamic content at database-backed web servers}, journal = {ACM SIGMOD RecordSIGMOD Rec.}, volume = {29}, year = {2000}, month = {2000/03//}, pages = {26 - 31}, isbn = {01635808}, doi = {10.1145/344788.344794}, url = {http://dl.acm.org/citation.cfm?id=344794}, author = {Labrinidis,Alexandros and Roussopoulos, Nick} } @article {18960, title = {The genome sequence of Drosophila melanogaster}, journal = {Science}, volume = {287}, year = {2000}, month = {2000///}, pages = {2185 - 2185}, abstract = {The fly Drosophila melanogaster is one of the most intensively studied organisms in biology and serves as a model system for the investigation of many developmental and cellular processes common to higher eukaryotes, including humans. We have determined the nucleotide sequence of nearly all of the \~{}120-megabase euchromatic portion of theDrosophila genome using a whole-genome shotgun sequencing strategy supported by extensive clone-based sequence and a high-quality bacterial artificial chromosome physical map. Efforts are under way to close the remaining gaps; however, the sequence is of sufficient accuracy and contiguity to be declared substantially complete and to support an initial analysis of genome structure and preliminary gene annotation and interpretation. The genome encodes \~{}13,600 genes, somewhat fewer than the smaller Caenorhabditis elegansgenome, but with comparable functional diversity.}, isbn = {0036-8075, 1095-9203}, doi = {10.1126/science.287.5461.2185}, url = {http://www.sciencemag.org/content/287/5461/2185}, author = {Adams,M.D. and Celniker,S.E. and Holt,R.A. and Evans,C.A. and Gocayne,J.D. and Amanatides,P.G. and Scherer,S.E. and Li,P.W. and Hoskins,R.A. and Galle,R.F. and others} } @article {18979, title = {Genomic Sequence, Splicing, and Gene Annotation}, journal = {American Journal of Human GeneticsAm J Hum Genet}, volume = {67}, year = {2000}, month = {2000/10//}, pages = {788 - 792}, isbn = {0002-9297}, url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1287883/}, author = {Mount, Stephen M.} } @article {18800, title = {A Geometric Algorithm for Finding the Largest Milling Cutter}, volume = {ISR; TR 2000-40}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {In this paper, we describe a new geometric algorithm to determine the largest feasible cutter size for2-D milling operations to be performed using a single cutter. In particular:

1. We give a general definition of the problem as the task of covering a target region without interfering with anobstruction region. This definition encompasses the task of milling a general 2-D profile that includes bothopen and closed edges.

2. We discuss three alternative definitions of what it means for a cutter to be feasible, and explain which of thesedefinitions is most appropriate for the above problem.

3. We present a geometric algorithm for finding the maximal cutter for 2-D milling operations, and we show thatour algorithm is correct.}, keywords = {algorithms, computational geometry, computer aided manufacturing CAM, cutter selection, Manufacturing, Next-Generation Product Realization Systems, path planning}, url = {http://drum.lib.umd.edu//handle/1903/6137}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @conference {18770, title = {A geometric algorithm for finding the maximal cutter for 2-D milling operations}, year = {2000}, month = {2000///}, pages = {26 - 28}, abstract = {In this paper, we present a geometric algorithm of finding the maximal cutter for 2-Dmilling operations. Our algorithm works not only for the common closed pocket problem, but also for the general 2-D milling problems with open edges. We define the general 2-D milling process in terms of a {\textquotedblleft}target region{\textquotedblright} to be machined and an {\textquotedblleft}obstruction region{\textquotedblright} that should not intersect with the cutter during machining. Our algorithm finds the largest cutter that can cover the target region without interfering with the obstruction region. Finding the biggest cutter is expected to help in the selection of the right sets of tools and the right type of cutter trajectories, and thereby ensure high production rate and meet the required quality level. }, url = {http://www.cs.umd.edu/~nau/papers/yao2000geometric.pdf}, author = {Yao,Z. and Gupta,S.K. and Nau, Dana S.} } @article {18801, title = {A Geometric Algorithm for Multi-Part Milling Cutter Selection}, volume = {ISR; TR 2000-42}, year = {2000}, month = {2000///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {Mass customization results in smaller batch sizes in manufacturing that require large numbers of setup and tool changes. The traditional process planning that generates plans for one part at a time is no longer applicable.

In this paper, we propose the idea of process planning for small batch manufacturing, i.e., we simultaneously consider multiple parts and exploit opportunities for sharing manufacturing resources such that the process plan will be optimized over the entire set of parts. In particular, we discuss a geometric algorithm for multiple part cutter selection in 2-1/2D milling operations.

We define the 2-1/2D milling operations as covering the target region without intersecting with the obstruction region. This definition allows us to handle the open edge problem. Based on this definition, we first discuss the lower and upper bond of cutter sizes that are feasible for given parts. Then we introduce the geometric algorithm to find the coverable area for a given cutter. Following that, we discuss the approach of considering cutter loading time and changing time in multiple cutter selection for multiple parts. We represent the cutter selection problem as shortest path problem and use Dijkstra{\textquoteright}s algorithm to solve it. By using this algorithm, a set of cutters is selected to achieve the optimum machining cost for multiple parts.

Our research illustrates the multiple parts process planning approach that is suitable for small batch manufacturing. At the same time, the algorithm given in this paper clarifies the 2-1/2D milling problem and can also help in cutter path planning problem.}, keywords = {algorithms, computer aided manufacturing CAM, cutter selection, Manufacturing, multi-part process planning, Next-Generation Product Realization Systems, OPTIMIZATION}, url = {http://drum.lib.umd.edu//handle/1903/6139}, author = {Yao,Zhiyang and Gupta, Satyandra K. and Nau, Dana S.} } @conference {15591, title = {Geo-registration of Landsat data by robust matching of wavelet features}, booktitle = {Geoscience and Remote Sensing Symposium, 2000. Proceedings. IGARSS 2000. IEEE 2000 International}, volume = {4}, year = {2000}, month = {2000///}, pages = {1610 -1612 vol.4 - 1610 -1612 vol.4}, abstract = {The goal of our project is to build an operational system, which will provide a sub-pixel accuracy registration of Landsat-5 and Landsat-7 data. Integrated within an automated mass processing/analysis system for Landsat data (REALM), the input to our registration method consists of scenes that have been geometrically and radiometrically corrected, as well as pre-processed for the detection of clouds and cloud shadows. Such pre-processed scenes are then geo-registered relative to a database of Landsat chips. This paper describes our registration process, including the use of a database of landmark chips, a feature extraction performed by an overcomplete wavelet representation, and feature matching using statistically robust techniques. Knowing the approximate longitudes and latitudes of the four corners of the scene, a subset of chips which represent landmarks included in the scene are extracted from the database. For each of these selected landmark chips, a corresponding window is extracted from the scene, and each chip-window pair is registered using our robust wavelet feature matching. First results and future directions are presented in the paper}, keywords = {atmospheric techniques, automated mass processing/analysis system, chip-window pair, cloud shadows, Clouds, Feature extraction, feature matching, geo-registration, geometrically corrected scene, geophysical signal processing, Image matching, image registration, landmark chips, Landsat chips, Landsat data, Landsat-5 data, Landsat-7 data, overcomplete wavelet representation, pre-processed scenes, radiometrically corrected scene, REALM, Remote sensing, robust matching, robust wavelet feature matching, scenes, statistically robust techniques, sub-pixel accuracy registration, wavelet features, Wavelet transforms, window}, doi = {10.1109/IGARSS.2000.857287}, author = {Le Moigne,J. and Netanyahu,N. S and Masek,J. G and Mount, Dave and Goward,S. and Honzak,M.} } @article {16430, title = {GP+ echo+ subsumption= improved problem solving}, journal = {Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2000)}, year = {2000}, month = {2000///}, pages = {411 - 418}, abstract = {Real-time, adaptive control is a difficult problemthat can be addressed by EC architectures. We are interested in incorporating into an EC architecture some of the features that Holland{\textquoteright}s Echo architecture presents. Echo has been used to model everything from cultures to financial markets. However, the typical application of Echo is a simulation to observe the dynamics of the modeled elements such as found in control problems. We show in this paper that some aspects of Echo can be incorporated into Genetic Programming to solve control problems. The paper discusses EAGP (Echo Augmented Genetic Programming), a modified GP architecture that uses aspects of Echo, and subsumption. We demonstrate the usefulness of EAGP on a robot navigation problem }, author = {Punch,W.F. and Rand, William} } @conference {15386, title = {Gate leakage current simulation by Boltzmann transport equation and its dependence on the gate oxide thickness}, booktitle = {Simulation of Semiconductor Processes and Devices, 1999. SISPAD {\textquoteright}99. 1999 International Conference on}, year = {1999}, month = {1999///}, pages = {247 - 250}, abstract = {As device dimensions shrink toward 0.1 mu;m, gate oxides are becoming so thin that MOSFET gate leakage current and oxide degradation are becoming limiting issues. We provide a more rigorous way to calculate gate leakage current. To achieve this we build upon the Spherical Harmonic Method of modeling, which deterministically solves the Boltzmann equation for an entire device. The method gives the distribution function and is 1000 times faster than MC. Once the distribution function is calculated, the tunneling probability is derived from the first principle WKB method. The barrier lowering effect is accounted for by the method of image charges. We calculate gate leakage current as a function of DC bias. The thermionic and tunneling components are compared at different DC bias points. The dependence of gate leakage current on gate oxide thickness is simulated}, keywords = {30, angstrom;60, angstrom;Boltzmann, Bias, calculations;leakage, charges;spherical, component;tunneling, current, currents;semiconductor, dependence;method, dependence;MOSFET;barrier, device, effect;distribution, equation;DC, equation;MOSFET;WKB, function;first, harmonic, image, leakage, lowering, method, method;gate, model;thermionic, models;tunnelling;, of, oxide, principle, probability;Boltzmann, simulation;gate, thickness, transport, WKB}, doi = {10.1109/SISPAD.1999.799307}, author = {Han,Zhiyi and Lin,Chung-Kai and Goldsman,N. and Mayergoyz, Issak D and Yu,S. and Stettler,M.} } @article {17912, title = {Generalized View-Dependent Simplification}, journal = {Computer Graphics Forum}, volume = {18}, year = {1999}, month = {1999/09/01/}, pages = {83 - 94}, abstract = {We propose a technique for performing view-dependent geometry and topology simplifications for level-of-detail-based renderings of large models. The algorithm proceeds by preprocessing the input dataset into a binary tree, the view-dependence tree of general vertex-pair collapses. A subset of the Delaunay edges is used to limit the number of vertex pairs considered for topology simplification. Dependencies to avoid mesh foldovers in manifold regions of the input object are stored in the view-dependence tree in an implicit fashion. We have observed that this not only reduces the space requirements by a factor of two, it also highly localizes the memory accesses at run time. The view-dependence tree is used at run time to generate the triangles for display. We also propose a cubic-spline-based distance metric that can be used to unify the geometry and topology simplifications by considering the vertex positions and normals in an integrated manner.}, keywords = {Interactive Cut, Physically Based Modeling, Runge Kutta Method, Soft Tissue, Surgery Simulation, Tetrahedralization, Virtual Scalpel}, isbn = {1467-8659}, doi = {10.1111/1467-8659.00330}, url = {http://onlinelibrary.wiley.com/doi/10.1111/1467-8659.00330/abstract}, author = {El-Sana,Jihad and Varshney, Amitabh} } @article {12999, title = {Genes and other samples of DNA sequence data for phylogenetic inference}, journal = {The Biological Bulletin}, volume = {196}, year = {1999}, month = {1999/06//}, pages = {345 - 350}, author = {Cummings, Michael P. and Otto,S. P and Wakeley,J.} } @article {17702, title = {Gaussian Elimination, Perturbation Theory and Markov Chains}, volume = {UMIACS-TR-92-23}, year = {1998}, month = {1998/10/15/}, institution = {Instititue for Advanced Computer Studies, Univ of Maryland, College Park}, abstract = {The purpose of this paper is to describe the special problems thatemerge when Gaussian elimination is used to determinin the steady-state vector of a Markov chain. (Also cross-referenced as UMIACS-TR-92-23) }, keywords = {Technical Report}, url = {http://drum.lib.umd.edu/handle/1903/564}, author = {Stewart, G.W.} } @article {14102, title = {Genetic nomenclature for Trypanosoma and Leishmania.}, journal = {Molecular and biochemical parasitology}, volume = {97}, year = {1998}, month = {1998///}, pages = {221 - 221}, author = {Clayton,C. and Adams,M. and Almeida,R. and Baltz,T. and Barrett,M. and Bastien,P. and Belli,S. and Beverley,S. and Biteau,N. and Blackwell,J. and others} } @article {20053, title = {Genetic nomenclature for Trypanosoma and Leishmania.}, journal = {Mol Biochem Parasitol}, volume = {97}, year = {1998}, month = {1998 Nov 30}, pages = {221-4}, keywords = {Animals, Leishmania, Terminology as Topic, Trypanosoma}, issn = {0166-6851}, author = {Clayton, C and Adams, M and Almeida, R and Baltz, T and Barrett, M and Bastien, P and Belli, S and Beverley, S and Biteau, N and Blackwell, J and Blaineau, C and Boshart, M and Bringaud, F and Cross, G and Cruz, A and Degrave, W and Donelson, J and El-Sayed, N and Fu, G and Ersfeld, K and Gibson, W and Gull, K and Ivens, A and Kelly, J and Vanhamme, L} } @article {14241, title = {On the geometry of visual correspondence}, year = {1998}, month = {1998/10/15/undef}, abstract = {Image displacement fieldsoptical flow fields, stereo disparity fields, normal flow fieldsdue to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constraine d to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The go al of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views.}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @conference {15225, title = {Greedy strikes back: improved facility location algorithms}, booktitle = {Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms}, series = {SODA {\textquoteright}98}, year = {1998}, month = {1998///}, pages = {649 - 657}, publisher = {Society for Industrial and Applied Mathematics}, organization = {Society for Industrial and Applied Mathematics}, address = {Philadelphia, PA, USA}, isbn = {0-89871-410-9}, url = {http://dl.acm.org/citation.cfm?id=314613.315037}, author = {Guha,Sudipto and Khuller, Samir} } @article {18977, title = {Genetic depletion reveals an essential role for an SR protein splicing factor in vertebrate cells}, journal = {BioEssays}, volume = {19}, year = {1997}, month = {1997///}, pages = {189 - 192}, abstract = {SR proteins are essential for the splicing of messenger RNA precursors in vitro, where they also alter splice site selection in a concentration-dependent manner. Although experiments involving overexpression or dominant mutations have confirmed that these proteins can influence RNA processing decisions in vivo, similar results with loss-of-function mutations have been lacking. Now, a system for genetic depletion of the chicken B cell line DT40 has revealed that the SR protein ASF/SF2 (alternative splicing factor/splicing factor 2) is essential for viability in these cells(1). This study opens the way for a complete functional dissection of this protein, and other SR proteins, in vivo.}, isbn = {1521-1878}, doi = {10.1002/bies.950190302}, url = {http://onlinelibrary.wiley.com/doi/10.1002/bies.950190302/abstract}, author = {Mount, Stephen M.} } @conference {15593, title = {Geometric intersection}, booktitle = {Handbook of Discrete and Computational Geometry, chapter 33}, year = {1997}, month = {1997///}, pages = {615 - 632}, publisher = {CRC Press LLC, Boca}, organization = {CRC Press LLC, Boca}, abstract = {Detecting whether two geometric objects intersect and computing the region of intersection are fundamental problems in computational geometry. Geometric intersection problems arise naturally in a number of applications. Examples include geometric packing and covering, wire and component layout in VLSI, map overlay}, author = {Mount, Dave} } @article {14242, title = {On the Geometry of Visual Correspondence}, journal = {International Journal of Computer Vision}, volume = {21}, year = {1997}, month = {1997///}, pages = {223 - 247}, abstract = {Image displacement fields{\textemdash}optical flow fields, stereo disparity fields, normal flow fields{\textemdash}due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views.}, isbn = {0920-5691}, url = {http://dx.doi.org/10.1023/A:1007951901001}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @inbook {14265, title = {The geometry of visual space distortion}, booktitle = {Algebraic Frames for the Perception-Action CycleAlgebraic Frames for the Perception-Action Cycle}, series = {Lecture Notes in Computer Science}, volume = {1315}, year = {1997}, month = {1997///}, pages = {249 - 277}, publisher = {Springer Berlin / Heidelberg}, organization = {Springer Berlin / Heidelberg}, abstract = {The encounter of perception and action happens at the intermediate representations of space-time. In many of the computational models employed in the past, it has been assumed that a metric representation of physical space can be derived by visual means. Psychophysical experiments, as well as computational considerations, can convince us that the perception of space and shape has a much more complicated nature, and that only a distorted version of actual, physical space can be computed. This paper develops a computational geometric model that explains why such distortion might take place. The basic idea is that, both in stereo and motion, we perceive the world from multiple views. Given the rigid transformation between the views and the properties of the image correspondence, the depth of the scene can be obtained. Even a slight error in the rigid transformation parameters causes distortion of the computed depth of the scene. The unified framework introduced here describes this distortion in computational terms. We characterize the space of distortions by its level sets, that is, we characterize the systematic distortion via a family of iso-distortion surfaces which describes the locus over which depths are distorted by some multiplicative factor. Clearly, functions of the distorted space exhibiting some sort of invariance, produce desirable representations for biological and artificial systems [13]. Given that humans{\textquoteright} estimation of egomotion or estimation of the extrinsic parameters of the stereo apparatus is likely to be imprecise, the framework is used to explain a number of psychophysical experiments on the perception of depth from motion or stereo.}, isbn = {978-3-540-63517-8}, url = {http://dx.doi.org/10.1007/BFb0017872}, author = {Ferm{\"u}ller, Cornelia and LoongFah Cheong and Aloimonos, J.}, editor = {Sommer,Gerald and Koenderink,Jan} } @article {16926, title = {A grander goal: A thousand-fold increase in human capabilities}, journal = {Educom review}, volume = {32}, year = {1997}, month = {1997///}, pages = {4 - 10}, author = {Shneiderman, Ben} } @conference {13561, title = {Graphical Tools and Techniques for Querying Document Databases}, booktitle = {BSDIA}, year = {1997}, month = {1997///}, pages = {213 - 224}, author = {Sauvola,J. and David Doermann and Kauniskangas,H. and Shin,C. and Koivusaari,M. and Pietikainen,M.} } @article {18839, title = {Generating redesign suggestions to reduce setup cost: a step towards automated redesign}, journal = {Computer-Aided Design}, volume = {28}, year = {1996}, month = {1996/10//}, pages = {763 - 782}, abstract = {All mechanical designs pass through a series of formal and informal redesign steps, involving the analysis of functionality, manufacturability, cost and other life-cycle factors. The speed and efficacy of these steps has a major influence on the lead time of the product from conceptualization to launching. In this paper we propose a methodology for automatically generating redesign suggestions for reducing setup costs for machined parts.Given an interpretation of the design as a collection of machinable features, our approach is to generate alternate machining features by making geometric changes to the original features, and add them to the feature set of the original part to create an extended feature set. The designer may provide restrictions on the design indicating the type and extent of modifications allowed on certain faces and volumes, in which case all redesign suggestions generated by our approach honour those restrictions. By taking combinations of features from the extended feature set generated above, we can generate modified versions of the original design that still satisfy the designer{\textquoteright}s intent. By considering precedence constraints, we can estimate the setup time that will be required for each design. Any modified design whose setup time is less than that of the original design can be presented to the designer as a possible way to modify the original design. }, isbn = {0010-4485}, doi = {10.1016/0010-4485(95)00034-8}, url = {http://www.sciencedirect.com/science/article/pii/0010448595000348}, author = {Das,Diganta and Gupta, Satyandra K. and Nau, Dana S.} } @article {15220, title = {Graph and network algorithms}, journal = {ACM Computing Surveys}, volume = {28}, year = {1996}, month = {1996/03//}, pages = {43 - 45}, isbn = {0360-0300}, doi = {10.1145/234313.234334}, url = {http://doi.acm.org/10.1145/234313.234334}, author = {Khuller, Samir and Raghavachari,Balaji} } @article {17701, title = {Gauss, Statistics, and Gaussian Elimination}, journal = {Journal of Computational and Graphical Statistics}, volume = {4}, year = {1995}, month = {1995/03/01/}, pages = {1 - 11}, abstract = {Gaussian elimination is the algorithm of choice for the solution of dense linear systems of equations. However, Gauss himself originally introduced his elimination procedure as a way of determining the precision of least squares estimates and only later described the computational algorithm. This article tells the story of Gauss, his algorithm, and its relation to his probabilistic development of least squares.}, isbn = {1061-8600}, doi = {10.2307/1390624}, url = {http://www.jstor.org/stable/1390624}, author = {Stewart, G.W.} } @article {12384, title = {Generating compact code from dataflow specifications of multirate signal processing algorithms}, journal = {Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, volume = {42}, year = {1995}, month = {1995///}, pages = {138 - 150}, author = {Bhattacharyya, Shuvra S. and Buck,J. T and Ha,S. and Lee,E. A} } @article {12849, title = {Generating diagnostic information for behavioral preorders}, journal = {Distributed computing}, volume = {9}, year = {1995}, month = {1995///}, pages = {61 - 75}, author = {Celikkan,U. and Cleaveland, Rance} } @article {17977, title = {Generating levels of detail for large-scale polygonal models}, volume = {CS-1995-20}, year = {1995}, month = {1995///}, institution = {Department of Computer Science, Duke University, North Carolina}, abstract = {We present an e cient algorithm for generating various levels-of-detail approximations for agiven polygonal model. Our algorithm guarantees that all points of an approximation are within a user-speci able distance from the original model and all points of the original model are within a distance from the approximation. Each approximation attempts to minimize the total number of polygons required to satisfy the previous constraint. We show how the problem of generating levels- of-detail approximations reduces to the classic set partition problem. The various approximations are guaranteed to be topologically consistent with the input polygonal model. The approximations can be constrained by the user to preserve any desired edges of the input model. We also propose a method to compute an estimate of the quality of the approximation generated by our algorithm with respect to the optimal approximation satisfying the same constraints. We have implemented our algorithm and have obtained experimental results of multiresolution hierarchy generation on over a thousand polygonal objects from a CAD model of a notional submarine. }, author = {Varshney, Amitabh and Agarwal,P. K and Brooks Jr,F. P and Wright,W. V and Weber,H.} } @conference {13560, title = {Generating Synthetic Data for Text Analysis Systems}, booktitle = {SDAIR}, year = {1995}, month = {1995///}, pages = {449 - 467}, abstract = {In this paper we describe work on a sys-tem for modeling errors in the output of OCR systems. The project is motivated by the desire to evaluate the performance of various text analysis systems under varying, yet controlled conditions. We describe a set of symbol and page models which are used to degrade an ideal text by introducing er- rors which typically occur during scanning, decomposition and recognition of document images. A rst generation of the software is described which implements the page mod- els and allows the use of transition proba- bilities, either extracted from real data or generated synthetically, to corrupt text. }, author = {David Doermann and Yao,S.} } @article {18978, title = {Genetic enhancement of RNA-processing defects by a dominant mutation in B52, the Drosophila gene for an SR protein splicing factor.}, journal = {Molecular and Cellular BiologyMol. Cell. Biol.}, volume = {15}, year = {1995}, month = {1995/11/01/}, pages = {6273 - 6282}, abstract = {SR proteins are essential for pre-mRNA splicing in vitro, act early in the splicing pathway, and can influence alternative splice site choice. Here we describe the isolation of both dominant and loss-of-function alleles of B52, the gene for a Drosophila SR protein. The allele B52ED was identified as a dominant second-site enhancer of white-apricot (wa), a retrotransposon insertion in the second intron of the eye pigmentation gene white with a complex RNA-processing defect. B52ED also exaggerates the mutant phenotype of a distinct white allele carrying a 5{\textquoteright} splice site mutation (wDR18), and alters the pattern of sex-specific splicing at doublesex under sensitized conditions, so that the male-specific splice is favored. In addition to being a dominant enhancer of these RNA-processing defects, B52ED is a recessive lethal allele that fails to complement other lethal alleles of B52. Comparison of B52ED with the B52+ allele from which it was derived revealed a single change in a conserved amino acid in the beta 4 strand of the first RNA-binding domain of B52, which suggests that altered RNA binding is responsible for the dominant phenotype. Reversion of the B52ED dominant allele with X rays led to the isolation of a B52 null allele. Together, these results indicate a critical role for the SR protein B52 in pre-mRNA splicing in vivo.}, isbn = {0270-7306, 1098-5549}, url = {http://mcb.asm.org/content/15/11/6273}, author = {Peng,X. and Mount, Stephen M.} } @article {14615, title = {Genome Sequence Comparison and Scenarios for Gene Rearrangements: A Test Case}, journal = {Genomics}, volume = {30}, year = {1995}, month = {1995/11//}, pages = {299 - 311}, abstract = {As large portions of related genomes are being sequenced, methods for comparing complete or nearly complete genomes, as opposed to comparing individual genes, are becoming progressively more important. A major, widespread phenomenon in genome evolution is the rearrangement of genes and gene blocks. There is, however, no consistent method for genome sequence comparison combined with the reconstruction of the evolutionary history of highly rearranged genomes. We developed a schema for genome sequence comparison that includes three successive steps: (i) comparison of all proteins encoded in different genomes and generation of genomic similarity plots; (ii) construction of an alphabet of conserved genes and gene blocks; and (iii) generation of most parsimonious genome rearrangement scenarios. The approach is illustrated by a comparison of the herpesvirus genomes that constitute the largest set of relatively long, complete genome sequences available to date. Herpesviruses have from 70 to about 200 genes; comparison of the amino acid sequences encoded in these genes results in an alphabet of about 30 conserved genes comprising 7 conserved blocks that are rearranged in the genomes of different herpesviruses. Algorithms to analyze rearrangements of multiple genomes were developed and applied to the derivation of most parsimonious scenarios of herpesvirus evolution under different evolutionary models. The developed approaches to genome comparison will be applicable to the comparative analysis of bacterial and eukaryotic genomes as soon as their sequences become available.}, isbn = {0888-7543}, doi = {10.1006/geno.1995.9873}, url = {http://www.sciencedirect.com/science/article/pii/S0888754385798734}, author = {Hannenhalli, Sridhar and Chappey,Colombe and Koonin,Eugene V. and Pevzner,Pavel A.} } @conference {11982, title = {Global rigidity constraints in image displacement fields}, booktitle = {Proceedings of Fifth International Conference on Computer Vision, 1995}, year = {1995}, month = {1995/06/20/23}, pages = {245 - 250}, publisher = {IEEE}, organization = {IEEE}, abstract = {Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views}, keywords = {3D motion parameters, algorithms, Automation, Computer science, Computer vision, conic sections, curves, equal vectors, Fluid flow measurement, global geometric structure, global rigidity constraints, image displacement fields, Image motion analysis, Image segmentation, Image sequences, imaging surface, Laboratories, Layout, Motion estimation, Motion measurement, motion vectors, multiple views, normal flow fields, optical flow fields, regions, rigid motion, stereo disparity fields, Stereo vision, vectors, visual information recovery}, isbn = {0-8186-7042-8}, doi = {10.1109/ICCV.1995.466779}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @conference {14168, title = {Global rigidity constraints in image displacement fields}, booktitle = {, Fifth International Conference on Computer Vision, 1995. Proceedings}, year = {1995}, month = {1995/06/20/23}, pages = {245 - 250}, publisher = {IEEE}, organization = {IEEE}, abstract = {Image displacement fields-optical flow fields, stereo disparity fields, normal flow fields-due to rigid motion possess a global geometric structure which is independent of the scene in view. Motion vectors of certain lengths and directions are constrained to lie on the imaging surface at particular loci whose location and form depends solely on the 3D motion parameters. If optical flow fields or stereo disparity fields are considered, then equal vectors are shown to lie on conic sections. Similarly, for normal motion fields, equal vectors lie within regions whose boundaries also constitute conics. By studying various properties of these curves and regions and their relationships, a characterization of the structure of rigid motion fields is given. The goal of this paper is to introduce a concept underlying the global structure of image displacement fields. This concept gives rise to various constraints that could form the basis of algorithms for the recovery of visual information from multiple views}, keywords = {3D motion parameters, algorithms, Automation, Computer science, Computer vision, conic sections, curves, equal vectors, Fluid flow measurement, global geometric structure, global rigidity constraints, image displacement fields, Image motion analysis, Image segmentation, Image sequences, imaging surface, Laboratories, Layout, Motion estimation, Motion measurement, motion vectors, multiple views, normal flow fields, optical flow fields, regions, rigid motion, stereo disparity fields, Stereo vision, vectors, visual information recovery}, isbn = {0-8186-7042-8}, doi = {10.1109/ICCV.1995.466779}, author = {Ferm{\"u}ller, Cornelia and Aloimonos, J.} } @article {16378, title = {Going beyond integer programming with the Omega test to eliminate false data dependences}, journal = {IEEE Transactions on Parallel and Distributed Systems}, volume = {6}, year = {1995}, month = {1995/02//}, pages = {204 - 211}, abstract = {Array data dependence analysis methods currently in use generate false dependences that can prevent useful program transformations. These false dependences arise because the questions asked are conservative approximations to the questions we really should be asking. Unfortunately, the questions we really should be asking go beyond integer programming and require decision procedures for a subclass of Presburger formulas. In this paper, we describe how to extend the Omega test so that it can answer these queries and allow us to eliminate these false data dependences. We have implemented the techniques described here and believe they are suitable for use in production compilers}, keywords = {Algorithm design and analysis, Arithmetic, Computer science, Data analysis, false data dependences, integer programming, Linear programming, Omega test, Privatization, Production, production compilers, program compilers, Program processors, program testing, program transformations, Testing}, isbn = {1045-9219}, doi = {10.1109/71.342135}, author = {Pugh, William and Wonnacott,D.} } @article {17711, title = {On graded QR decompositions of products of matrices}, journal = {Electronic Transactions on Numerical Analysis}, volume = {3}, year = {1995}, month = {1995///}, pages = {39 - 49}, abstract = {This paper is concerned with the singular values and vectors of a product Mm =A1A2 ... Am of matrices of order n. The chief difficulty with computing them directly from Mm is that with increasing m the ratio of the small to the large singular values of Mm may fall below the rounding unit, so that the former are computed inaccurately. The solution proposed here is to compute recursively the factorization Mm = QRPT, where Q is orthogonal, R is a graded upper triangular, and PT is a permutation. }, author = {Stewart, G.W.} } @article {15218, title = {Graphbots: Mobility in discrete spaces}, journal = {Automata, Languages and Programming}, year = {1995}, month = {1995///}, pages = {593 - 604}, abstract = {Most previous theoretical work on motion planning has addressed the problem of path planning for geometrically simple robots in geometrically simple regions of Euclidean space (e.g., a planar region containing polygonal obstacles). In this paper we define a natural version of the motion planning problem in a graph theoretic setting. We establish conditions under which a ldquorobotrdquo or team of robots having a particular graph structure can move from any start location to any goal destination in a graph-structured space.}, doi = {10.1007/3-540-60084-1_108}, author = {Khuller, Samir and Rivlin,E. and Rosenfeld, A.} } @article {14824, title = {Generalizing invariants for 3-D to 2-D matching}, journal = {Applications of Invariance in Computer Vision}, year = {1994}, month = {1994///}, pages = {415 - 434}, abstract = {Invariant representations of images have proven useful in performing a variety of vision tasks. However, there are no general invariant functions when one considers a single 2-D image of a 3-D scene. One possible response to the lack of true invariants is to attempt to generalize the notion of an invariant by finding the most economical characterization possible of the set of all 2-D images that a group of 3-D features may produce. A true invariant exists when, for each model, we can represent all its images at a single point in some representational space. When this is not possible, it is still very useful to find the simplest and lowest-dimensional representation of each model{\textquoteright}s images.We show how this can be done for a variety of different types of model features, and types of projection models. Of particular interest, we show how to represent the set of images that a group of 3-D points produces by two lines (1-D subspaces), one in each of two orthogonal, high-dimensional spaces, where a single image group corresponds to one point in each space. We demonstrate the value of our results by applying them to a variety of vision problems. In particular, we describe a space-efficient indexing system that performs 3-D to 2-D matching by table lookup. We also show how to find a least squares solution to the structure-from-motion problem using point features that have associated orientations, such as corners. We show how to determine when a restricted class of models may give rise to an invariant function, and construct a model-based invariant for pairs of planar algebraic curves that are not coplanar. }, doi = {10.1007/3-540-58240-1_22}, author = {Jacobs, David W.} } @article {12784, title = {A generalized approach to real-time schedulability analysis}, journal = {IEEE Real-Time Systems Newsletter}, volume = {9}, year = {1993}, month = {1993///}, pages = {98 - 103}, author = {Fredette,A. N and Cleaveland, Rance} } @conference {18841, title = {Generation of alternative feature-based models and precedence orderings for machining applications}, series = {SMA {\textquoteright}93}, year = {1993}, month = {1993///}, pages = {465 - 466}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, isbn = {0-89791-584-4}, doi = {10.1145/164360.164520}, url = {http://doi.acm.org/10.1145/164360.164520}, author = {Gupta, Satyandra K. and Nau, Dana S.} } @article {15208, title = {Geometric knapsack problems}, journal = {Algorithmica}, volume = {10}, year = {1993}, month = {1993///}, pages = {399 - 427}, abstract = {We study a variety of geometric versions of the classical knapsack problem. In particular, we consider the following ldquofence enclosurerdquo problem: given a setS ofn points in the plane with valuesv i ge 0, we wish to enclose a subset of the points with a fence (a simple closed curve) in order to maximize the ldquovaluerdquo of the enclosure. The value of the enclosure is defined to be the sum of the values of the enclosed points minus the cost of the fence. We consider various versions of the problem, such as allowingS to consist of points and/or simple polygons. Other versions of the problems are obtained by restricting the total amount of fence available and also allowing the enclosure to consist of at mostM connected components. When there is an upper bound on the length of fence available, we show that the problem is NP-complete. We also provide polynomial-time algorithms for many versions of the fence problem when an unrestricted amount of fence is available.}, doi = {10.1007/BF01769706}, author = {Arkin,E. M and Khuller, Samir and Mitchell,J. S.B} } @conference {14174, title = {Global 3D motion estimation}, booktitle = {, 1993 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1993. Proceedings CVPR {\textquoteright}93}, year = {1993}, month = {1993/06/15/17}, pages = {415 - 421}, publisher = {IEEE}, organization = {IEEE}, abstract = {It is shown how a monocular observer can estimate its 3D motion relative to the scene by using normal flow measurements in a global and qualitative way. It is proved that local normal flow measurements form global patterns in the image plane. The position of these patterns is related to the 3D motion parameters. By locating some of these patterns, which depend only on subsets of the motion parameters, through a simple search technique, the 3D motion parameters can be found. The proposed algorithmic procedure is very robust, since it is not affected by small perturbations in the normal flow measurements. The direction of translation and the axis of rotation can be estimated with up to 100\% error in the image measurements}, keywords = {3D motion parameters, Automation, axis of rotation, Computer vision, direction of translation, Educational institutions, Equations, Fluid flow measurement, global 3D motion estimation, Laboratories, Layout, monocular observer, Motion estimation, Motion measurement, normal flow measurements, Robustness, Rotation measurement, search problems, search technique, State estimation}, isbn = {0-8186-3880-X}, doi = {10.1109/CVPR.1993.341097}, author = {Ferm{\"u}ller, Cornelia} } @article {16929, title = {A graphical filter/flow representation of Boolean queries: A prototype implementation and evaluation}, journal = {Journal of the American Society for Information Science}, volume = {44}, year = {1993}, month = {1993/07/01/}, pages = {327 - 339}, abstract = {One of the powerful applications of Boolean expression is to allow users to extract relevant information from a database. Unfortunately, previous research has shown that users have difficulty specifying Boolean queries. In an attempt to overcome this limitation, a graphical Filter/Flow representation of Boolean queries was designed to provide users with an interface that visually conveys the meaning of the Boolean operators (AND, OR, and NOT). This was accomplished by implementing a graphical interface prototype that uses the metaphor of water flowing through filters. Twenty subjects having no experience with Boolean logic participated in an experiment comparing the Boolean operations represented in the Filter/Flow interface with a text-only SQL interface. The subjects independently performed five comprehension tasks and five composition tasks in each of the interfaces. A significant difference (p < 0.05) in the total number of correct queries in each of the comprehension and composition tasks was found favoring Filter/Flow. {\textcopyright} 1993 John Wiley \& Sons, Inc.}, isbn = {1097-4571}, doi = {10.1002/(SICI)1097-4571(199307)44:6<327::AID-ASI3>3.0.CO;2-J}, url = {http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-4571(199307)44:6\%3C327::AID-ASI3\%3E3.0.CO;2-J/abstract;jsessionid=76B714851135D8044D4E03335B4D39A0.d01t04}, author = {Young,Degi and Shneiderman, Ben} } @article {16930, title = {A graphical query interface based on aggregation/generalization hierarchies}, journal = {Information Systems}, volume = {18}, year = {1993}, month = {1993/06//}, pages = {215 - 232}, abstract = {In order for automated information systems to be used effectively, they must be made easily accessible to a wide range of users and with short training periods. This work proposes a method of organizing documents based on the concepts of aggregation and generalization hierarchies. We propose a graphical user interface to provide a more intuitive form of Boolean query. This design is based on mapping the nodes of the aggregation hierarchy to Boolean intersection operations, mapping the nodes of the generalization hierarchy to Boolean union operations, and providing a concrete, graphical, manipulable representation of both of these node types. Finally, a working prototype interface was constructed and evaluated experimentally against a classical command-line Boolean query interface. In this formative evaluation with sixteen subjects, the graphical interface produced less than one-tenth the errors of the textual interface, on average. Significant differences in time spent specifying queries were not found. Observations and comments provide guidance for designers.}, keywords = {aggregation/generalization hierarchies, empirical test, Graphical user interfaces, visual queries}, isbn = {0306-4379}, doi = {10.1016/0306-4379(93)90018-V}, url = {http://www.sciencedirect.com/science/article/pii/030643799390018V}, author = {Weiland,William J and Shneiderman, Ben} } @inbook {16222, title = {Guide to Opportunities in Volunteer Archaeology: case study on the use of a hypertext system in a museum exhibit}, booktitle = {Sparks of innovation in human-computer interactionSparks of innovation in human-computer interaction}, year = {1993}, month = {1993///}, pages = {223 - 223}, publisher = {Intellect Books}, organization = {Intellect Books}, isbn = {9781567500783}, author = {Plaisant, Catherine} } @article {18836, title = {General of Machining Alternatives for Machinability Evaluation}, volume = {ISR; TR 1992-106}, year = {1992}, month = {1992///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {This paper presents a new methodology for evaluating the machinability of a machined part during the design stage of the product development cycle, so that problems related to machining can be recognized and corrected while the product is being designed. Our basic approach is to perform a systematic evaluation of machining alternatives throughout each step in the design stage. This involves three basic steps: (1) generate alternative interpretations of the design as different collections of machinable features, (2) generate the various possible sequences of machining operations capable of producing each interpretation, and (3) evaluate each operation sequence, to determine the relevant information on achievable quality and associated costs. The information provided by this analysis can be used not only to give feedback to the designer about problems that might arise with the machining, but also to provide information to the manufacturing engineer about alternative ways in which the part might be machined.}, keywords = {Automation, computer aided manufacturing, manufacturability, Manufacturing Systems}, url = {http://hdl.handle.net/1903/5287}, author = {Gupta, Satyandra K. and Nau, Dana S. and Zhang,G. M.} } @article {17546, title = {A Generalization of Brooks{\textquoteright} Theorem}, journal = {Computer Science Technical Reports}, year = {1992}, month = {1992/09//}, abstract = {Given a connected graph $G = (V, E)$ with $n$ vertices and maximum degree $\Delta$ such that $\Delta \geq$ 3 and $G$ is not a complete graph, Brooks{\textquoteright} theorem shows that $G$ is $\Delta$-colorable. We prove a generalization of this theorem: assume inductively that all but one vertex $v$ is colored; then, $v$ can be colored by considering the vertices (and their colors) in just an $O$ (log $n$) radius around $v$. Our proof uses a probabilistic technique to link the connectivity and diameter of "almost-regular" graphs, which could have other applications too.}, author = {Srinivasan, Aravind} } @article {18840, title = {Generation and Evaluation of Alternative Operation}, volume = {ISR; TR 1992-20}, year = {1992}, month = {1992///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {This paper presents a new and systematic approach to assist decision-making in selecting machining operation sequences. The approach is to produce alternative interpretations of design as different collections of machinable features, use these interpretations to generate alternative machining operation sequences, and evaluate the cost and achievable machining accuracy of each operations sequence. Given the operation sequences and their evaluations, it is then possible to calculate the performance measures of interest, and use these performance measures to select, from among the various alternatives, one or more of them that can best balance the need for a quality product against the need for efficient machining.}, keywords = {Automation, computer aided manufacturing, computer integrated manufacturing, Feature extraction, flexible manufacturing, Manufacturing, Manufacturing Systems, Solid modeling}, url = {http://drum.lib.umd.edu//handle/1903/5203}, author = {Nau, Dana S. and Zhang,G. M. and Gupta, Satyandra K.} } @article {18842, title = {Generation of Machining Alternatives for Machinability Evaluation}, volume = {ISR; TR 1992-106}, year = {1992}, month = {1992///}, institution = {Institute for Systems Research, University of Maryland, College Park}, abstract = {This paper presents a new methodology for evaluating the machinability of a machined part during the design stage of the product development cycle, so that problems related to machining can be recognized and corrected while the product is being designed. Our basic approach is to perform a systematic evaluation of machining alternatives throughout each step in the design stage. This involves three basic steps: (1) generate alternative interpretations of the design as different collections of machinable features, (2) generate the various possible sequences of machining operations capable of producing each interpretation, and (3) evaluate each operation sequence, to determine the relevant information on achievable quality and associated costs. The information provided by this analysis can be used not only to give feedback to the designer about problems that might arise with the machining, but also to provide information to the manufacturing engineer about alternative ways in which the part might be machined.}, keywords = {Automation, computer aided manufacturing, manufacturability, Manufacturing Systems}, url = {http://drum.lib.umd.edu//handle/1903/5287}, author = {Gupta, Satyandra K. and Nau, Dana S. and Zhang,G. M.} } @book {16928, title = {A Graphical Filter/flow Representation of Boolean Queries: A Prototype Implementation}, year = {1992}, month = {1992///}, publisher = {University of Maryland, Center for Automation Research, Computer Vision Laboratory}, organization = {University of Maryland, Center for Automation Research, Computer Vision Laboratory}, author = {Young,D. and Shneiderman, Ben} } @conference {18294, title = {Ground and airborne localization over rough terrain using random environmental range-measurements}, booktitle = {Pattern Recognition, 1992. Vol. I. Conference A: Computer Vision and Applications, Proceedings., 11th IAPR International Conference on}, year = {1992}, month = {1992///}, pages = {403 - 406}, author = {Yacoob,Yaser and Davis, Larry S.} } @book {12786, title = {Gdr: A visualization tool for graph algorithms}, year = {1991}, month = {1991///}, publisher = {Citeseer}, organization = {Citeseer}, author = {Stallmann,M. and Cleaveland, Rance and Hebbar,P.} } @article {12344, title = {Gabriel: A design environment for DSP}, journal = {Acoustics, Speech and Signal Processing, IEEE Transactions on}, volume = {37}, year = {1989}, month = {1989///}, pages = {1751 - 1762}, author = {Lee,E. A and Ho,W. H and Goei,E. E and Bier,J. C and Bhattacharyya, Shuvra S.} } @article {16521, title = {Generating plausible diagnostic hypotheses with self-processing causal networks}, journal = {Journal of Experimental \& Theoretical Artificial Intelligence}, volume = {1}, year = {1989}, month = {1989///}, pages = {91 - 112}, author = {Wald,J. and Farach,M. and Tagamets,M. and Reggia, James A.} } @article {14823, title = {Grouping for recognition}, journal = {AI Memos (1959 - 2004)}, year = {1989}, month = {1989///}, abstract = {This paper presents a new method of grouping edges in order to recognize objects. This grouping method succeeds on images of both two- and three- dimensional objects. So that the recognition system can consider first the collections of edges most likely to lead to the correct recognition of objects, we order groups of edges based on the likelihood that a single object produced them. The grouping module estimates this likelihood using the distance that separates edges and their relative orientation. This ordering greatly reduces the amount of computation required to locate objects and improves the system{\textquoteright}s robustness to error.}, url = {http://hdl.handle.net/1721.1/6525}, author = {Jacobs, David W.} } @article {16640, title = {A general-purpose simulation environment for developing connectionist models}, journal = {Simulation}, volume = {51}, year = {1988}, month = {1988///}, pages = {5 - 5}, author = {D{\textquoteright}Autrechy,C. L and Reggia, James A. and Sutton,G. G and Goodall,S. M} } @conference {15637, title = {Globally-Equiangular triangulations of co-circular points in 0(n log n) time}, booktitle = {Proceedings of the fourth annual symposium on Computational geometry}, series = {SCG {\textquoteright}88}, year = {1988}, month = {1988///}, pages = {143 - 152}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, isbn = {0-89791-270-5}, doi = {10.1145/73393.73408}, url = {http://doi.acm.org/10.1145/73393.73408}, author = {Mount, Dave and Saalfeld,A.} } @article {14867, title = {GROPER: A Grouping Based Object Recognition System for Two-Dimensional Objects}, journal = {IEEE Workshop on Computer Vision}, year = {1987}, month = {1987///}, pages = {164 - 169}, author = {Jacobs, David W.} } @article {16750, title = {GDDT--A graphical design and documentation tool for software development}, journal = {Computers \& Graphics}, volume = {8}, year = {1984}, month = {1984///}, pages = {309 - 323}, abstract = {This paper describes "The Graphical Design and Documentation Tool" (GDDT), a general purpose support system for design and documentation. Self documentation and ease of use are presented as important criteria for such tools. Interactive graphics is introduced as a methodology for creating and maintaining hierarchical representations. The graphical representations of various requirements specification techniques and design tools are supported by an extended network model which supports hierarchical decomposition of structures. GDDT is proposed as a general purpose design tool which supports the most common logical constructions of both requirements specification and design methodologies and yet has a high level human interface which makes it easy to learn and use.}, isbn = {0097-8493}, doi = {16/0097-8493(84)90013-X}, url = {http://www.sciencedirect.com/science/article/pii/009784938490013X}, author = {Roussopoulos, Nick and Kelley,Stephen} } @article {15700, title = {A generalized conjugate gradient algorithm for solving a class of quadratic programming problems}, journal = {Linear Algebra and its Applications}, volume = {34}, year = {1980}, month = {1980/12//}, pages = {371 - 399}, abstract = {In this paper we apply matrix splitting techniques and a conjugate gradient algorithm to the problem of minimizing a convex quadratic form subject to upper and lower bounds on the variables. This method exploits sparsity structure in the matrix of the quadratic form. Choices of the splitting operator are discussed, and convergence results are established. We present the results of numerical experiments showing the effectiveness of the algorithm on free boundary problems for elliptic partial differential equations, and we give comparisons with other algorithms.}, isbn = {0024-3795}, doi = {10.1016/0024-3795(80)90173-1}, url = {http://www.sciencedirect.com/science/article/pii/0024379580901731}, author = {O{\textquoteright}Leary, Dianne P.} } @book {11937, title = {A guide to major job accounting systems: the Logger system of the UNIVAC 1100 series operating system}, year = {1978}, month = {1978///}, publisher = {U.S. Dept. of Commerce, National Bureau of Standards : for sale by the Supt. of Docs., U.S. Govt. Print. Off.}, organization = {U.S. Dept. of Commerce, National Bureau of Standards : for sale by the Supt. of Docs., U.S. Govt. Print. Off.}, keywords = {Accounting, Business \& Economics / Accounting / General, Electronic digital computers, EXEC 8 (Electronic computer system), Reference / Questions \& Answers, Univac 1100 series (Computer), Univac computer}, author = {Mohr,Jeffrey Myron and Agrawala, Ashok K. and Flannagan,J. F.} } @inbook {15701, title = {A Generalized Conjugate Gradient Method for the Numerical Solution of Elliptic Partial Differential Equations}, booktitle = {Sparse Matrix ComputationsSparse Matrix Computations}, year = {1976}, month = {1976///}, pages = {309 - 332}, publisher = {Academic Press}, organization = {Academic Press}, address = {New York}, abstract = {We consider a generalized conjugate gradient method for solvingsparse, symmetric, positive-definite systems of linear equations, principally those arising from the discretization of boundary value problems for elliptic partial differential equations. The method is based on splitting off from the original coefficient matrix a symmetric, positive-definiteonethat corresponds to a more easily solvable system of equations, and then accelerating the associated iteration using conjugate gradients. Optimality and convergence properties are presented, and the relation to other methods is discussed. Several splittings for which the method seems particularly effective are also discussed, and for some, numerical examples are given }, author = {Concus,Paul and Golub, Gene H. and O{\textquoteright}Leary, Dianne P.}, editor = {Bunch,James R. and Rose,Donald J.} } @article {16005, title = {Group algebras and model theory}, journal = {Illinois journal of mathematics}, volume = {20}, year = {1976}, month = {1976///}, pages = {298 - 305}, author = {Perlis, Don} } @article {16927, title = {A graph theoretic model of data structures}, journal = {SIGIR Forum}, volume = {7}, year = {1972}, month = {1972/12//}, pages = {36 - 44}, abstract = {The widespread development of large shared data bases has proceeded mainly on empirical notions. Only in the past few years have there been attempts at formalizing the underlying concepts into a theory of data structures. The present models have been founded on the well-established mathematical theories of sets, relations and graphs, but few descriptions have been sufficiently developed to meet the needs of a complete theory of data structures. The set theoretic formalism offered by Childs(1) or Schwartz(2) or the relational model by Codd(3) are useful but fail to give a complete description of the complex structures found in modern data bases. The graph theoretic concepts found in papers by Harary and Hsiao(4) and Earley(5) are more appealing but need further elaboration. This paper is an attempt to develop a graph theoretic model into a useful formalism for describing and manipulating data structures.}, isbn = {0163-5840}, doi = {10.1145/1095495.1095499}, url = {http://doi.acm.org/10.1145/1095495.1095499}, author = {Heller,J. and Shneiderman, Ben} }