Michel Dumontier, James R. Green, Ashkan Golshani, Myron L. Smith, Nadereh Mir-Rashed, Md Alamgir, ...
Background High throughput yeast functional genomics experiments are revealing associations among tens to hundreds of genes using numerous experimental conditions. To fully understand how...
SPR Distance Computation for Unrooted Trees (2008)
Glenn Hickey, Frank Dehne, Andrew Rau-Chaplin, Christian Blouin
The subtree prune and regraft distance (dSPR) between phylogenetic trees is important both as a general means of comparing phylogenetic tree topologies as well as a measure of lateral gene transfer...
Pitre, Sylvain, Dehne, Frank, Chan, Albert, Cheetham, Jim, Duong, Alex, Emili, Andrew, ...
Abstract Background Identification of protein interaction networks has received considerable attention in the post-genomic era. The currently available biochemical approaches used to detect...
Simulated Annealing for Materialized View Selection in Data Warehousing Environment (2006)
Derakhshan, Roozbeh, Dehne, Frank, Korn, Othmar, Stantic, Bela, M.H. Hamza
In order to facilitate query processing, the information contained in datawarehouses is typically stored as a set of materialized views.Deciding which views to materialize presents a...
A Template Based Static Coalition Protocol - A3PviGrid (2006)
Shankaranarayanan, Avinash, Dehne, Frank, Lewis, Andrew
Yes
Simulated Annealing for Materialized View Selection in Data Warehousing Environment (2006)
Derakhshan, Roozbeh, Dehne, Frank, Korn, Othmar, Stantic, Bela
In order to facilitate query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize presents a considerable...
A Template Based Static Coalition Protocol - A3PviGrid (2006)
Shankaranarayanan, Avinash, Dehne, Frank, Lewis, Andrew
Yes
Simulated Annealing for Materialized View Selection in Data Warehousing Environment (2006)
Derakhshan, Roozbeh, Dehne, Frank, Korn, Othmar, Stantic, Bela
In order to facilitate query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize presents a considerable...
Concurrent Program Design in the Extended Theory of Owicki and Gries (2005)
Goldson, Doug, Dongol, Brijesh, Atkinson, Mike, Dehne, Frank
Feijen and van Gasteren have shown how to use the theory of Owicki and Gries to design concurrent programs, however, the lack of a formal theory of progress has meant that these designs are driven...
Distributed and Parallel Databases, 15, 219--236, 2004 c (2004)
The pre-computation of data cubes is critical to improving the response time of On-Line Analytical Processing (OLAP) systems and can be instrumental in accelerating data mining tasks in large data...
Http://www.elsevier.com/locate/jcss (2003)
Jamf Cheetham, Frank Dehne, Andrew Rau-chaplin, Ulrike Stege, Peter J. Taillon
Fixed-paramd er tractability (FPT) techniques have recently been successful in solving NP-comMBF. problem instances of practicalimct tance which were too large to be solved with previousmevio s. In...
An FPT Algorithm for Set Splitting (2003)
Frank Dehne, Michael R. Fellows, Frances A. Rosamond
An FPT algorithm with a running time of O(n is described for the Set Splitting problem, parameterized by the number k of sets to be split. It is also shown that there can be no FPT unless the...
Parallel CLUSTAL W for PC Clusters (2003)
James Cheetham, Frank Dehne, Andrew Rau-chaplin, Peter J. Taillon
This paper presents a parallel version of CLUSTAL W, called pCLUSTAL. In contrast to the commercial SGI parallel Clustal, which requires an expensive shared memory SGI multiprocessor, pCLUSTAL can be...
Coarse Grained Parallel Algorithms for (2003)
Edson Caceres, Albert Chan, Frank Dehne
In this paper, we present parallel algorithms for the coarse grained multicomputer (CGM) and the bulk synchronous parallel computer (BSP) for solving two well known graph problems: (1) determining...
Distributed Cyclic Reference Counting (2003)
We present a distributed cyclic reference counting algorithm which incorporates both, the correct management of cyclic data structures and the improvement of lazy mark-scan. The algorithm allows...
Parallelizing The Data Cube (2003)
Frank Dehne, Todd Eavis, Susanne Hambrusch, Andrew Rau-chaplin
This paper presents a general methodology for the efficient parallelization of existing data cubeconstruction algorithms.We describe two different partitioning strategies, one for top-down and one...
ParallelMulti-25933pQ655 (2003)
This paper addressests query performance issue for RelatYgIE OLAP (ROLAP)datgZYS22 We present adistYY utt multYgIEBB2VgtZ ROLAP indexingscheme which is practE9Z t implement requires only a...
Mesh Simplification In Parallel (2003)
This paper presents a parallel method for progressive mesh simplification. A progressive mesh (PM) is a continuous mesh representation of a given 3D object which makes it possible to efficiently...
Scalable And Architecture Independent Parallel Geometric Algorithms (2003)
Frank Dehne, Claire Kenyon, Andreas Fabri
We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly...
Coarse Grained Parallel On-Line Analytical (2003)
Frank Dehne, Andrew Rau-chaplin
We study the applicability of coarse grained parallel computing model (CGM) to on-line analytical processing (OLAP) for data mining. We present a general framework for the CGM which allows for the...
James Cheetham, Frank Dehne, Ulri E Stege, Peter J. Taiq
Fixed-param eter tractability (FPT ) techniques have recently been successful in solving NP-com' ete problem instances of practical im portance which were too large to be solved with previous ms...
Frank Dehne, Andreas Fabri, Mostafa Nassar, Andrew Rau-chaplin, Rada Valiveti
We present a parallel algorithm for the construction of the hyperoctree representing a d-dimensional object from a set of n (d ; 1)- dimensional hyperoctrees, representing adjacent crossections of...
Parallel Processing of Pointer Based (2003)
Frank Dehne, Afonso G. Ferreira, Andrew Rau-chaplin
This paper studies the parallel construction and manipulation of pointer based quadtrees on the hypercube multiprocessor.
We show that the wavefront approach to Voronoi diagrams (a deterministic line sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the...
Reducing I/O Complexity by Simulating (2003)
Frank Dehne, David Hutchinson, Anil Maheshwari, Wolfgang Dittrich
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Susanne E. Hambrusch, Frank Dehne
Let I be a binary image stored in a mesh of processors with one pixel per processor. Image I is k-width-connected if, informally,between any pair of 1-pixels there exists a path of width k (composed...
In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like...
Practical Parallel Algorithms for Minimum Spanning Trees (2003)
We study parallel algorithms for computing the minimum spanning tree of a weighted undirected graph G with n vertices and m edges. We consider an input graph G with m=n p, where p is the number of...
Parallel ROLAP Data Cube Construction On Shared-Nothing Multiprocessors Ying Chen (2003)
Ying Chen, Frank Dehne, Todd Eavis, Andrew Rau-chaplin
The pre-computation of data cubes is critical to improving the response time of On-Line Analytical Processing (OLAP) systems and can be instrumental in accelerating data mining tasks in large data...
Randomized Parallel List Ranking for Distributed Memory Multiprocessors (2003)
Wepresentarandomized parallel list ranking algorithm for distributed memory multiprocessors. A simple version requires, with high probability, log(3p)+logln(n) = ~ O(log p + log log n) communication...
Parallelizing the Data Cube (2003)
This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one...
Journal of Parallel and Distributed Computing 57, 224235 (1999) (2003)
This paper improves on op. cit. in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require only O((n#p)...
DOI: 10.1007/s00453-002-1009-y (2003)
Frank Dehne, Wolfgang Dittrich
External memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM...
Bulk Synchronous Parallel Algorithms for the External Memory Model (2003)
Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari, Bosch Telecom Gmbh
Blockwise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Enhancing Hyperlink Structure for Improving Web Performance (2002)
Miguel Vargas Martfn, Miguel Vargas Martin, Dr. Frank Dehne
this dissertation. iii To my mother, Rosario Martin Cuellar iv Acknowledgements I wish to sincerely thank my thesis supervisors, Dr. Evangelos Kranakis and Dr
Coarse Grained Parallel Graph Planarity Testing (2002)
Albert Chan, Frank Dehne, S. W. Song
We present a coarse grained parallel algorithm for planarity testing and planar embedding.
Distribution Sweeping on Clustered Machines with Hierarchical Memories (2002)
Frank Dehne, Stefano Mardegan And, Andrea Pietracaprina
This paper investigates the design of parallel algorithmic strategies that address the efficient use of both, memory hierarchies within each processor and a multilevel clustered structure of the...
Online Routing in Geometric Graphs (2002)
Patrick Ryan Morin, Dr. Frank Dehne
This thesis considers the problem of nding a path from a source to a destination in a graph in which only local information is available. This type of routing problem occurs regularly in robotics,...
Mesh Simplification In Parallel (2002)
Christian Langis, Gerhard Roth, Frank Dehne
This paper presents a parallel method for progressive mesh simplification. A progressive mesh (PM) is a continuous mesh representation of a given 3D object which makes it possible to efficiently...
Distribution Sweeping on Clustered Machines with Hierarchical Memories (2002)
Frank Dehne, Stefano Mardegan And, Andrea Pietracaprina
This paper investigates the design of parallel algorithmic strategies that address the efficient use of both, memory hierarchies within each processor and a multilevel clustered structure of the...
MultisearchTechniques: Parallel Data Structures on Mesh-Connected Computers (2001)
Mikhail J. Atallah, Frank Dehne, Russ Miller, Andrew Rau-chaplin, Jyh-jong Tsay
The multisearch problem is defined as follows. Givenadatastructure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path...
Computing Partial Data Cubes for Parallel Data Warehousing Applications (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
In this paper, we focus on an approach to On-Line Analytical Processing (OLAP) that is based on a database operator and data structure called the datacube. The datacube is a relational operator that...
Coarse Grained Parallel On-Line Analytical Processing (OLAP) For Data Mining (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
We study the applicability of coarse grained parallel computing model (CGM) to on-line analytical processing (OLAP) for data mining. We present a general framework for the CGM which allows for the...
A Cluster Architecture for Parallel Data Warehousing (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
We describe the parallel, cluster-based implementation of an algorithm for the computation of a database operator known as the datacube. Though a number of efficient sequential algorithms have...
Mesh Simplification In Parallel (2000)
This paper presents a parallel method for progressive mesh simplification. A progressive mesh (PM) is a continuous mesh representation of a given 3D object which makes it possible to efficiently...
Mesh Simplification In Parallel (2000)
This paper presents a parallel method for progressive mesh simplification. A progressive mesh (PM) is a continuous mesh representation of a given 3D object which makes it possible to efficiently...
Parallelizing The Data Cube (2000)
Frank Dehne, Todd Eavis, Susanne Hambrusch, Andrew Rau-chaplin
This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one...
A Coarse Grained Parallel Algorithm for Maximum Weight Matching in Trees (2000)
We present an efficient coarse grained parallel algorithm for computing a maximum weight matching in trees. A divide and conquer approach based on centroid decomposition of trees is used. Our...
Coarse Grained Parallel Graph Planarity Testing (2000)
Albert Chan, Frank Dehne, S. W. Song
We present a coarse grained parallel algorithm for planarity testing and planar embedding. The algorithm requires O(log 2 p) communication rounds and linear sequential work per round. It assumes that...
Scalable Parallel Computational Geometry for Coarse Grained Multicomputers (2000)
Frank Dehne, Andreas Fabri, Andrew Rau-chaplin
We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O( n p ) AE O(1) local...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (1999)
Frank Dehne, David Hutchinson, Anil Maheshwari, Wolfgang Dittrich, Bosch Telecom Gmbh
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1999)
We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP like model. We first describe a simple version which requires, with high probability,...
Parallel Processing of Pointer Based Quadtrees on Hypercube Multiprocessors (1999)
Frank Dehne, Afonso G. Ferreira, Andrew Rau-chaplin
This paper studies the parallel construction and manipulation of pointer based quadtrees on the hypercube multiprocessor.
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (1999)
Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
Block-wise access to data is a central theme in the design of efficient external memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In...
A Randomized Parallel 3D Convex Hull Algorithm For Coarse Grained Multicomputers (1999)
Frank Dehne, Xiaotie Deng, Patrick Dymond, Andreas Fabri, Ashfaq A. Khokhar
We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconection network and n=p local memory per...
Construction of d-Dimensional Hyperoctrees on a Hypercube Multiprocessor (1999)
Frank Dehne, Andreas Fabri, Mostafa Nassar, Andrew Rau-chaplin, Rada Valiveti
We present a parallel algorithm for the construction of the hyperoctree representing a d-dimensional object from a set of n (d Gamma 1)- dimensional hyperoctrees, representing adjacent crossections...
Practical Parallel Algorithms for Minimum Spanning Trees (1999)
We study parallel algorithms for computing the minimum spanning tree of a weighted undirected graph G with n vertices and m edges. We consider an input graph G with m=n p, where p is the number of...
Susanne E. Hambrusch, Frank Dehne
Let I be a n Theta n binary image stored in a n Theta n mesh of processors with one pixel per processor. Image I is k-width-connected if, informally, between any pair of 1-pixels there exists a path...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1999)
We present a randomized parallel list ranking algorithm for distributed memory multiprocessors. A simple version requires, with high probability, log(3p) + log ln(n) = ~ O(log p + log log n)...
Frank Dehne, Claire Kenyon, Andreas Fabri
We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for uniformly...
Coarse Grained Parallel Geometric Search (1999)
Albert Chan, Frank Dehne, Andrew Rau-chaplin
We present a parallel algorithm for solving the next element search problem on a set of line segments, using a BSP like model referred to as the Coarse Grained Multicomputer (CGM). The algorithm...
A Randomized Parallel 3D Convex Hull Algorithm For Coarse Grained Multicomputers (1998)
Frank Dehne, Xiaotie Deng, Patrick Dymond, Andreas Fabri, Ashfaq A. Khokhar
We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconection network and n=p local memory per...
A Randomized Parallel 3D Convex Hull Algorithm For Coarse Grained Multicomputers (1998)
Frank Dehne, Xiaotie Deng, Patrick Dymond, Andreas Fabri, Ashfaq A. Khokhar
We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconection network and n=p local memory per...
Scalable Parallel Computational Geometry for Coarse Grained Multicomputers (1998)
Frank Dehne, Andreas Fabri, Andrew Rau-chaplin
We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O( n p ) AE O(1) local...
Scalable Parallel Computational Geometry for Coarse Grained Multicomputers (1998)
Frank Dehne, Andreas Fabri, Andrew Rau-chaplin
We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O( n p ) AE O(1) local...
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms (1997)
Frank Dehne, Wolfgang Dittrich, David Hutchinson
External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. For certain large scale...
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms (1997)
Frank Dehne, Wolfgang Dittrich, David Hutchinson
External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. For certain large scale...
Distributed Cyclic Reference Counting (1997)
We present a distributed cyclic reference counting algorithm which incorporates both, the correct management of cyclic data structures and the improvement of lazy mark-scan. The algorithm allows...
A Randomized Parallel 3D Convex Hull Algorithm For Coarse Grained Multicomputers (1997)
Frank Dehne, Xiaotie Deng, Patrick Dymond, Andreas Fabri, Ashfaq A. Khokhar
We present a randomized parallel algorithm for constructing the 3D convex hull on a generic p-processor coarse grained multicomputer with arbitrary interconnection network and n=p local memory per...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1997)
We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP like model. We first describe a simple version which requires, with high probability,...
In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like...
Efficient External Memory Algorithms by Simulating Coarse-Grained Parallel Algorithms (1997)
Frank Dehne, Wolfgang Dittrich, David Hutchinson
External memory (EM) algorithms are designed for computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. For certain large scale...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1997)
. We present a randomized parallel list ranking algorithm for distributed memory multiprocessors. A simple version requires, with high probability, log(3p) + log ln(n) = ~ O(log p + log log n)...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1997)
We present a randomized parallel list ranking algorithm for distributed memory multiprocessors, using a BSP like model. We first describe a simple version which requires, with high probability,...
Distributed Cyclic Reference Counting (1996)
We present a distributed cyclic reference counting algorithm which incorporates both, the correct management of cyclic data structures and the improvement of lazy mark-scan. The algorithm allows...
In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like...
Scalable Parallel Computational Geometry for Coarse Grained Multicomputers (1995)
Frank Dehne, Andreas Fabri, Andrew Rau-chaplin
We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each process