TY - CONF
T1 - Computing the Tree of Life: Leveraging the Power of Desktop and Service Grids
T2 - Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Y1 - 2011
A1 - Bazinet,A. L
A1 - Cummings, Michael P.
KW - (artificial
KW - (mathematics);user
KW - analysis;science
KW - BOINC
KW - computation;grid
KW - computational
KW - computing
KW - computing;information
KW - computing;machine
KW - data;grid
KW - estimation;portals;trees
KW - evolutionary
KW - Grid
KW - grids;service
KW - handling;evolutionary
KW - history;evolutionary
KW - intelligence);maximum
KW - interface;computational
KW - interfaces;
KW - jobs;HPC
KW - learning;maximum
KW - likelihood
KW - load;Internet;data
KW - method;molecular
KW - model;genetic
KW - model;substantial
KW - portal;service
KW - power;data
KW - project;life
KW - resource;lattice
KW - resource;Web
KW - sequence
KW - services;learning
KW - sets;evolutionary
KW - software;GARLI
KW - system;heterogeneous
KW - systematics;phylogenetic
KW - tree
AB - The trend in life sciences research, particularly in molecular evolutionary systematics, is toward larger data sets and ever-more detailed evolutionary models, which can generate substantial computational loads. Over the past several years we have developed a grid computing system aimed at providing researchers the computational power needed to complete such analyses in a timely manner. Our grid system, known as The Lattice Project, was the first to combine two models of grid computing - the service model, which mainly federates large institutional HPC resources, and the desktop model, which harnesses the power of PCs volunteered by the general public. Recently we have developed a "science portal" style web interface that makes it easier than ever for phylogenetic analyses to be completed using GARLI, a popular program that uses a maximum likelihood method to infer the evolutionary history of organisms on the basis of genetic sequence data. This paper describes our approach to scheduling thousands of GARLI jobs with diverse requirements to heterogeneous grid resources, which include volunteer computers running BOINC software. A key component of this system provides a priori GARLI runtime estimates using machine learning with random forests.
JA - Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
M3 - 10.1109/IPDPS.2011.344
ER -
TY - CONF
T1 - The half-edge tree: a compact data structure for level-of-detail tetrahedral meshes
T2 - Shape Modeling and Applications, 2005 International Conference
Y1 - 2005
A1 - Danovaro,E.
A1 - De Floriani, Leila
A1 - Magillo,P.
A1 - Puppo,E.
A1 - Sobrero,D.
A1 - Sokolovsky,N.
KW - application;
KW - compact
KW - computational
KW - data
KW - detection;
KW - edge
KW - encoding;
KW - generation;
KW - geometry;
KW - half-edge
KW - iterative
KW - level-of-detail
KW - mesh
KW - meshes;
KW - methods;
KW - model;
KW - structure;
KW - structures;
KW - tetrahedral
KW - tree
KW - tree;
AB - We propose a new data structure for the compact encoding of a level-of detail (LOD) model of a three-dimensional scalar field based on unstructured tetrahedral meshes. Such data structure, called a half-edge tree (HET), is built through the iterative application of a half-edge collapse, i.e. by contracting an edge to one of its endpoints. We also show that selective refined meshes extracted from an HET contain on average about 34% and up to 75% less tetrahedra than those extracted from an LOD model built through a general edge collapse.
JA - Shape Modeling and Applications, 2005 International Conference
M3 - 10.1109/SMI.2005.47
ER -
TY - CONF
T1 - Arbitrate-and-move primitives for high throughput on-chip interconnection networks
T2 - Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on
Y1 - 2004
A1 - Balkan,A.O.
A1 - Gang Qu
A1 - Vishkin, Uzi
KW - 8
KW - arbiter
KW - arbitrate-and-move
KW - architecture;
KW - asynchronous
KW - balanced
KW - binary
KW - circuit
KW - circuit;
KW - circuits;
KW - consumption;
KW - data
KW - explicit
KW - interconnection
KW - interconnections;
KW - leaf
KW - mesh-of-trees
KW - multi-threading;
KW - Multithreading
KW - n-leaf
KW - network;
KW - pipeline
KW - pipelined
KW - power
KW - primitive
KW - processing;
KW - reduced
KW - simulation;
KW - structures;
KW - synchronous
KW - synchrony
KW - system-on-chip;
KW - tree
KW - tree;
AB - An n-leaf pipelined balanced binary tree is used for arbitration of order and movement of data from n input ports to one output port. A novel arbitrate-and-move primitive circuit for every node of the tree, which is based on a concept of reduced synchrony that benefits from attractive features of both asynchronous and synchronous designs, is presented. The design objective of the pipelined binary tree is to provide a key building block in a high-throughput mesh-of-trees interconnection network for Explicit Multi Threading (XMT) architecture, a recently introduced parallel computation framework. The proposed reduced synchrony circuit was compared with asynchronous and synchronous designs of arbitrate-and-move primitives. Simulations with 0.18 mu;m technology show that compared to an asynchronous design, the proposed reduced synchrony implementation achieves a higher throughput, up to 2 Giga-Requests per second on an 8-leaf binary tree. Our circuit also consumes less power than the synchronous design, and requires less silicon area than both the synchronous and asynchronous designs.
JA - Circuits and Systems, 2004. ISCAS '04. Proceedings of the 2004 International Symposium on
VL - 2
M3 - 10.1109/ISCAS.2004.1329303
ER -
TY - CONF
T1 - Depth-first k-nearest neighbor finding using the MaxNearestDist estimator
T2 - Image Analysis and Processing, 2003.Proceedings. 12th International Conference on
Y1 - 2003
A1 - Samet, Hanan
KW - branch-and-bound
KW - data
KW - depth-first
KW - distance;
KW - DNA
KW - documents;
KW - estimation;
KW - estimator;
KW - finding;
KW - images;
KW - k-nearest
KW - matching;
KW - maximum
KW - MaxNearestDist
KW - mining;
KW - neighbor
KW - parameter
KW - pattern
KW - possible
KW - process;
KW - processing;
KW - query
KW - search
KW - searching;
KW - sequences;
KW - series;
KW - similarity
KW - text
KW - TIME
KW - tree
KW - video;
AB - Similarity searching is an important task when trying to find patterns in applications which involve mining different types of data such as images, video, time series, text documents, DNA sequences, etc. Similarity searching often reduces to finding the k nearest neighbors to a query object. A description is given of how to use an estimate of the maximum possible distance at which a nearest neighbor can be found to prune the search process in a depth-first branch-and-bound k-nearest neighbor finding algorithm. Using the MaxNearestDist estimator (Larsen, S. and Kanal, L.N., 1986) in the depth-first k-nearest neighbor algorithm provides a middle ground between a pure depth-first and a best-first k-nearest neighbor algorithm.
JA - Image Analysis and Processing, 2003.Proceedings. 12th International Conference on
M3 - 10.1109/ICIAP.2003.1234097
ER -
TY - CONF
T1 - PXML: a probabilistic semistructured data model and algebra
T2 - Data Engineering, 2003. Proceedings. 19th International Conference on
Y1 - 2003
A1 - Hung,E.
A1 - Getoor, Lise
A1 - V.S. Subrahmanian
KW - algebra;
KW - data
KW - databases;
KW - instances;
KW - model;
KW - models;
KW - probabilistic
KW - processing;
KW - PXML;
KW - query
KW - relational
KW - semistructured
KW - structures;
KW - tree
KW - XML;
AB - Despite the recent proliferation of work on semistructured data models, there has been little work to date on supporting uncertainty in these models. We propose a model for probabilistic semistructured data (PSD). The advantage of our approach is that it supports a flexible representation that allows the specification of a wide class of distributions over semistructured instances. We provide two semantics for the model and show that the semantics are probabilistically coherent. Next, we develop an extension of the relational algebra to handle probabilistic semistructured data and describe efficient algorithms for answering queries that use this algebra. Finally, we present experimental results showing the efficiency of our algorithms.
JA - Data Engineering, 2003. Proceedings. 19th International Conference on
M3 - 10.1109/ICDE.2003.1260814
ER -
TY - CONF
T1 - Efficient techniques for range search queries on earth science data
T2 - Scientific and Statistical Database Management, 2002. Proceedings. 14th International Conference on
Y1 - 2002
A1 - Shi,Qingmin
A1 - JaJa, Joseph F.
KW - based
KW - computing;
KW - content
KW - data
KW - data;
KW - databases;
KW - Earth
KW - factors;
KW - large
KW - mining
KW - mining;
KW - natural
KW - processing;
KW - queries;
KW - query
KW - range
KW - raster
KW - retrieval;
KW - scale
KW - Science
KW - sciences
KW - search
KW - spatial
KW - structures;
KW - tasks;
KW - temporal
KW - tree
KW - tree-of-regions;
KW - visual
AB - We consider the problem of organizing large scale earth science raster data to efficiently handle queries for identifying regions whose parameters fall within certain range values specified by the queries. This problem seems to be critical to enabling basic data mining tasks such as determining associations between physical phenomena and spatial factors, detecting changes and trends, and content based retrieval. We assume that the input is too large to fit in internal memory and hence focus on data structures and algorithms that minimize the I/O bounds. A new data structure, called a tree-of-regions (ToR), is introduced and involves a combination of an R-tree and efficient representation of regions. It is shown that such a data structure enables the handling of range queries in an optimal I/O time, under certain reasonable assumptions. We also show that updates to the ToR can be handled efficiently. Experimental results for a variety of multi-valued earth science data illustrate the fast execution times of a wide range of queries, as predicted by our theoretical analysis.
JA - Scientific and Statistical Database Management, 2002. Proceedings. 14th International Conference on
M3 - 10.1109/SSDM.2002.1029714
ER -
TY - CONF
T1 - SpaceTree: supporting exploration in large node link tree, design evolution and empirical evaluation
T2 - Information Visualization, 2002. INFOVIS 2002. IEEE Symposium on
Y1 - 2002
A1 - Plaisant, Catherine
A1 - Grosjean,J.
A1 - Bederson, Benjamin B.
KW - browser;
KW - camera
KW - data
KW - design
KW - diagrams;
KW - dynamic
KW - evolution;
KW - experiment;
KW - exploration;
KW - filter
KW - functions;
KW - graphical
KW - icons;
KW - integrated
KW - interfaces;
KW - large
KW - link
KW - movement;
KW - node
KW - novel
KW - optimized
KW - rescaling;
KW - search;
KW - SpaceTree;
KW - structures;
KW - topology;
KW - tree
KW - user
KW - visualisation;
KW - visualization;
AB - We present a novel tree browser that builds on the conventional node link tree diagrams. It adds dynamic rescaling of branches of the tree to best fit the available screen space, optimized camera movement, and the use of preview icons summarizing the topology of the branches that cannot be expanded. In addition, it includes integrated search and filter functions. This paper reflects on the evolution of the design and highlights the principles that emerged from it. A controlled experiment showed benefits for navigation to already previously visited nodes and estimation of overall tree topology.
JA - Information Visualization, 2002. INFOVIS 2002. IEEE Symposium on
M3 - 10.1109/INFVIS.2002.1173148
ER -
TY - CONF
T1 - Efficient approximate and dynamic matching of patterns using a labeling paradigm
T2 - Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
Y1 - 1996
A1 - Sahinalp,S. C
A1 - Vishkin, Uzi
KW - algorithm;replaced
KW - algorithmics;substrings;suffix
KW - algorithms;pattern
KW - approximate
KW - characters;dynamic
KW - characters;labeling
KW - characters;string
KW - complexity;indexing;parallel
KW - construction;computational
KW - data
KW - dictionary
KW - dynamic
KW - indexing;efficient
KW - matching;deleted
KW - matching;dynamic
KW - matching;efficient
KW - matching;inserted
KW - matching;string
KW - matching;tree
KW - paradigm;optimal
KW - Parallel
KW - pattern
KW - PROCESSING
KW - string
KW - structures;
KW - text
KW - tree
AB - A key approach in string processing algorithmics has been the labeling paradigm which is based on assigning labels to some of the substrings of a given string. If these labels are chosen consistently, they can enable fast comparisons of substrings. Until the first optimal parallel algorithm for suffix tree construction was given by the authors in 1994 the labeling paradigm was considered not to be competitive with other approaches. They show that this general method is also useful for several central problems in the area of string processing: approximate string matching, dynamic dictionary matching, and dynamic text indexing. The approximate string matching problem deals with finding all substrings of a text which match a pattern ldquo;approximately rdquo;, i.e., with at most m differences. The differences can be in the form of inserted, deleted, or replaced characters. The text indexing problem deals with finding all occurrences of a pattern in a text, after the text is preprocessed. In the dynamic text indexing problem, updates to the text in the form of insertions and deletions of substrings are permitted. The dictionary matching problem deals with finding all occurrences of each pattern set of a set of patterns in a text, after the pattern set is preprocessed. In the dynamic dictionary matching problem, insertions and deletions of patterns to the pattern set are permitted
JA - Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
M3 - 10.1109/SFCS.1996.548491
ER -
TY - CONF
T1 - Algorithms for fast vector quantization
T2 - Data Compression Conference, 1993. DCC '93.
Y1 - 1993
A1 - Arya,S.
A1 - Mount, Dave
KW - algorithm;
KW - algorithms;
KW - directed
KW - fast
KW - graph
KW - graph;
KW - graphs;
KW - Neighborhood
KW - performance;
KW - problems;
KW - quantisation;
KW - quantization;
KW - running
KW - search
KW - time;
KW - tree
KW - vector
AB - This paper shows that if one is willing to relax the requirement of finding the true nearest neighbor, it is possible to achieve significant improvements in running time and at only a very small loss in the performance of the vector quantizer. The authors present three algorithms for nearest neighbor searching: standard and priority k -d tree search algorithms and a neighborhood graph search algorithm in which a directed graph is constructed for the point set and edges join neighboring points
JA - Data Compression Conference, 1993. DCC '93.
M3 - 10.1109/DCC.1993.253111
ER -
TY - JOUR
T1 - VLSI implementation of a tree searched vector quantizer
JF - Signal Processing, IEEE Transactions on
Y1 - 1993
A1 - Kolagotla,R. K.
A1 - Yu,S.-S.
A1 - JaJa, Joseph F.
KW - (mathematics);
KW - 2
KW - 20
KW - chips;
KW - coding;
KW - compression;
KW - data
KW - design;
KW - digital
KW - image
KW - implementation;
KW - MHz;
KW - micron;
KW - PROCESSING
KW - quantisation;
KW - quantizer;
KW - searched
KW - signal
KW - tree
KW - TREES
KW - vector
KW - VLSI
KW - VLSI;
AB - The VLSI design and implementation of a tree-searched vector quantizer is presented. The number of processors needed is equal to the depth of the tree. All processors are identical, and data flow between processors is regular. No global control signals are needed. The processors have been fabricated using 2 mu;m N-well process on a 7.9 times;9.2 mm die. Each processor chip contains 25000 transistors and has 84 pins. The processors have been thoroughly tested at a clock frequency of 20 MHz
VL - 41
SN - 1053-587X
CP - 2
M3 - 10.1109/78.193225
ER -
TY - CONF
T1 - An improved classification tree analysis of high cost modules based upon an axiomatic definition of complexity
T2 - Software Reliability Engineering, 1992. Proceedings., Third International Symposium on
Y1 - 1992
A1 - Tian,Jianhui
A1 - Porter, Adam
A1 - Zelkowitz, Marvin V
KW - (mathematics);
KW - analysis;
KW - axiomatic
KW - classification
KW - classification;
KW - complexity;
KW - computational
KW - cost
KW - decision
KW - definition;
KW - high
KW - metrics;
KW - model;
KW - modules;
KW - overall
KW - program
KW - reliability;
KW - software
KW - subroutines;
KW - system
KW - tree
KW - TREES
AB - Identification of high cost modules has been viewed as one mechanism to improve overall system reliability, since such modules tend to produce more than their fair share of problems. A decision tree model has previously been used to identify such modules. In this paper, a previously developed axiomatic model of program complexity is merged with the previously developed decision tree process for an improvement in the ability to identify such modules. This improvement has been tested using data from the NASA Software Engineering Laboratory
JA - Software Reliability Engineering, 1992. Proceedings., Third International Symposium on
M3 - 10.1109/ISSRE.1992.285848
ER -