Bridging the gap between systems biology and medicine (2009)
Clermont, Gilles, Auffray, Charles, Moreau, Yves, Rocke, David M, Dalevi, Daniel, Dubhashi, Devdatt, ...
Abstract Systems biology has matured considerably as a discipline over the last decade, yet some of the key challenges separating current research efforts in systems biology and clinically useful...
www.dehne.net Motivated by the work of Ng et.al., and the recent success of Star-Cubing (Han et.al.), we further investigate the use of hybrid approaches for the parallel computation of very large...
A Coarse Grained Parallel Algorithm for Hausdorff Voronoi Diagrams (2008)
Frank Dehne, Anil Maheshwari, Ryan Taylor
Abstract — We present the first parallel algorithm for building a Hausdorff Voronoi diagram (HVD). Our algorithm is targeted towards cluster computing architectures and computes the Hausdorff...
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...
Construction of d-Dimensional Hyperoctrees on a Hypercube Multiprocessor (2008)
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 this...
Frank Dehne, Todd Eavis, Andrew Rau-chaplin, Olap Server
On-line Analytical Processing (OLAP) has become one of the most powerful and prominent technologies for knowledge discovery in VLDB (Very Large Database) environments. Central to the OLAP paradigm is...
Abstract Parallel Multi-Dimensional ROLAP Indexing ∗ (2008)
This paper addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present a distributed multi-dimensional ROLAP indexingscheme which is practical to implement, requires only...
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...
Nonblocker: Parameterized Algorithmics for Minimum Dominating Set (2008)
Elena Prieto, Complutense Madrid Spain, Awards Fellowships Honours, Frank Dehne, Michael Fellows, Henning Fernau, ...
COMPRESSING DATA CUBE IN PARALLEL OLAP SYSTEMS (2008)
Frank Dehne, Todd Eavis, Boyong Liang
This paper proposes an efficient algorithm to compress the cubes in the progress of the parallel data cube generation. This low overhead compression mechanism provides block-by-block and...
— contact author — Abstract (2008)
Ying Chen, Frank Dehne, A. Rau-chaplin, Todd Eavis
www.scs.carleton.ca/∼teavis 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...
SIMULATED ANNEALING FOR MATERIALIZED VIEW SELECTION IN DATA WAREHOUSING ENVIRONMENT (2008)
Roozbeh Derakhshan, Frank Dehne, Othmar Korn, Bela Stantic
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...
www.dehne.net In this demo we present the cgmOLAP server, the first fully functional parallel OLAP system able to build data cubes at a rate of more than 1 Terabyte per hour. cgmOLAP incorporates a...
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...
ALGORITHMS ON PC CLUSTERS AND SHARED MEMORY MACHINES (2008)
Albert Chan, Frank Dehne, Ryan Taylor, Albert Chan, Frank Dehne, Ryan Taylor
In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on Coarse Grained Multicomputer (CGM) algorithms. CGMgraph implements parallel methods...
Cooperative Caching for Grid Based Data Warehouses (2008)
Frank Dehne, Michael Lawrence, Andrew Rau-chaplin
In this paper we propose a grid-based OLAP application which distributes query computation across an enterprise grid. Our application follows a two-tiered process for answering queries based on...
To appear in Distributed and Parallel Databases 1 2 3 4 5 6 7 8 (2008)
Ying Chen, Frank Dehne, Todd Eavis, Andrew Rau-chaplin
We present “Pipe ’n Prune ” (PnP), a new hybrid method for iceberg-cube query computation. The novelty of our method is that it achieves a tight integration of topdown piping for data...
Implementing OLAP Query Fragment Aggregation and Recombination for the OLAP Enabled Grid (2008)
Michael Lawrence, Frank Dehne, Andrew Rau-chaplin
In this paper we propose a new query processing method for the OLAP Enabled Grid, which blends sophisticated cache extraction techniques and data grid scheduling to efficiently satisfy OLAP queries...
Vertex Cover, Frank Dehne, Mike Fellows, Frances Rosamond, Peter Shaw
Abstract. The two objectives of this paper are: (1) to articulate three new general techniques for designing FPT algorithms, and (2) to apply these to obtain new FPT algorithms for Set Splitting and...
COMPRESSING DATA CUBE IN PARALLEL OLAP SYSTEMS (2008)
Frank Dehne, Todd Eavis, Boyong Liang
This paper proposes an efficient algorithm to compress the cubes in the progress of the parallel data cube generation. This low overhead compression mechanism provides block-by-block and...
ABSTRACT Parallel Querying of ROLAP Cubes in the Presence of Hierarchies (2008)
Online Analytical Processing is a powerful framework for the analysis of organizational data. OLAP is often supported by a logical structure known as a data cube, a multidimensional data model that...
ABSTRACT Efficient Computation of View Subsets (2008)
Over the past ten to fifteen years, data warehouse platforms have grown enormously, both in terms of their importance and their sheer size. Traditionally, such systems have been based upon a...
Coarse Grained Parallel Algorithms For Graph Matching ∗ (2008)
Albert Chan, Frank Dehne, Prosenjit Bose, Markus Latzel
Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM...
SPR Distance Computation for Unrooted Trees (2008)
Glenn Hickey, Frank Dehne, Andrew Rau-chaplin, Christian Blouin
Abstract: 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...
A Template Based Static Coalition Protocol -- A (2008)
Avinash Shankaranarayanan Frank, Frank Dehne, Andrew Lewis
Problems such as resource and service discovery models, load balancing and scheduling, brokering are eminent in grid systems due to bottlenecks such as bandwidth and network traffic in the underlying...
The cgmCUBE Project: Optimizing Parallel Data Cube Generation for ROLAP (2008)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
On-line Analytical Processing (OLAP) has become one of the most powerful and prominent technologies for knowledge discovery in VLDB (Very Large Database) en- vironments. Central to the OLAP paradigm...
Simulated Annealing For Materialized View Selection In (2008)
Data Warehousing Environment, Roozbeh Derakhshan, Frank Dehne, Othmar Korn, Bela Stantic
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...
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...
Parallel Simulated Annealing for Materialized View Selection in Data Warehousing Environments (2008)
Derakhshan, Roozbeh, Stantic, Bela, Korn, Othmar Charles, Dehne, Frank
In order to facilitate efficient query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize represent a...
Parallel Simulated Annealing for Materialized View Selection in Data Warehousing Environments (2008)
Derakhshan, Roozbeh, Stantic, Bela, Korn, Othmar Charles, Dehne, Frank
In order to facilitate efficient query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize represent a...
Parallel Simulated Annealing for Materialized View Selection in Data Warehousing Environments (2008)
Derakhshan, Roozbeh, Stantic, Bela, Korn, Othmar Charles, Dehne, Frank
In order to facilitate efficient query processing, the information contained in data warehouses is typically stored as a set of materialized views. Deciding which views to materialize represent a...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (2007)
Exte Nd Ed, Frank Dehne, Wolfgang Dittrich, David Hutchinson, Anil Maheshwari
Frank Dehne 2 Wolfgang Dittrich 3 David Hutchinson 2;4 Anil Maheshwari 2;4 July 30, 1998 Abstract Block-wise access to data is a central theme in the design of efficient external memory (EM)...
Frank Dehne, Wolfgang Dittrich, David Hutchinson
Abstract. 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....
Distribution Sweeping on Clustered Machines with Hierarchical Memories (2007)
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...
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,...
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...
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...
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
arc Corresponding Author. Abstract. 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...
Distribution Sweeping on Clustered Machines with Hierarchical Memories (2007)
Frank Dehne, Stefano Mardegan, 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...
Construction of d-Dimensional Hyperoctrees on a Hypercube Multiprocessor (2007)
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...
Determining Maximum k-Width-Connectivity on (2007)
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...
Abstract. 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...
MESH SIMPLIFICATION IN PARALLEL (2007)
Council Canada, C. Langis, G. Roth, F. Dehne, Christian Langis, Gerhard Roth, ...
de l’information
A Parallel FPT Application For Clusters ∗ (2007)
James Cheetham, Ulrike Stege, Frank Dehne
Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods....
Construction of d-Dimensional Hyperoctrees on a Hypercube Multiprocessor (2007)
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 this...
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...
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...
An improved algorithm for Hausdorff Voronoi diagram for non-crossing sets ∗†‡ (2006)
Frank Dehne, Anil Maheshwari, Ryan Taylor
We present an improved algorithm for building a Hausdorff Voronoi diagram (HVD) for non-crossing objects. Our algorithm runs in O(nlog 4 n) time, where n is the total number of points defining the...
Improved Data Partitioning for Building Large ROLAP Data Cubes in Parallel (2006)
Ying Chen, Frank Dehne, Todd Eavis, A. 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...
nonblocker: Parameterized Algorithmics for (2006)
Minimum Dominating Set, Frank Dehne, Michael Fellows, Henning Fernau, Elena Prieto, Frances Rosamond
We provide parameterized algorithms for nonblocker, the parametric dual of the well known dominating set problem. We exemplify three methodologies for deriving parameterized algorithms that can be...
The Cluster Editing Problem: (2006)
Implementations And Experiments, Frank Dehne, Michael A. Langston, Xuemei Luo, Sylvain Pitre, Peter Shaw, ...
In this paper, we study the cluster editing problem which is fixed parameter tractable.
Guest Editor's Introduction (2006)
This paper reports on solving instances with more than 10,000 data items in a few hours. Keane, Page, Naughton, Travers and McInerney report on a fully cross platform coarse-grained distributed...
The cgmCUBE project: Optimizing parallel data cube generation for ROLAP (2006)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin, F. Dehne, T. Eavis
On-line Analytical Processing (OLAP) has become one of the most powerful and prominent technologies for knowledge discovery in VLDB (Very Large Database) environments. Central to the OLAP paradigm is...
The Cluster Editing Problem: (2006)
Implementations And Experiments, Frank Dehne, Michael A. Langston, Xuemei Luo, Sylvain Pitre, Peter Shaw, ...
In this paper, we study the cluster editing problem which is fixed parameter tractable. We present the first practical implementation of a FPT based method for cluster editing, using the approach in...
Bmc Bioinformatics, Sylvain Pitre, Frank Dehne, Albert Chan, Jim Cheetham, Alex Duong, ...
Research article PIPE: a protein-protein interaction prediction engine based on the re-occurring short polypeptide sequences between known interacting protein pairs
Improved data partitioning for building large ROLAP data cubes in parallel (2006)
Ying Chen, Frank Dehne, Todd Eavis, A. Rau-chaplin
www.cs.dal.ca / arc
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...
PnP: Parallel and external memory iceberg cube computation. ICDE (2005)
www.dehne.net Motivated by the work of Ng et.al. [2] and the recent success of another hybrid sequential method, Star-Cubing [4], we further investigate the use of hybrid approaches for the parallel...
An O(2^O(k) n³) FPT algorithm for the undirected feedback vertex set problem (2005)
Frank Dehne, Michael Fellows, Michael A. Langston, Frances Rosamond, Kim Stevens
We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c^k n³) where c = 10.567 and n is the...
Albert Chan, Frank Dehne, Ryan Taylor
library of parallel graph methods for PC clusters based on Coarse Grained Multicomputer (CGM) algorithms. CGM- graph implements parallel methods for various graph problems. Our implementations of...
PnP: Parallel and External Memory Iceberg Cube Computation (2005)
Ying Chen, Frank Dehne, Todd Eavis, Andrew Rau-Chaplin
this paper presents a PnP parallelization which (1) minimizes communication overhead, (2) balances work load, and (3) makes full use of our I/O manager by overlapping parallel computation and...
Maximizing a Voronoi Region: The Convex Case (2005)
Frank Dehne, Rolf Klein, Raimund Seidel
Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors...
An o(2 O(k) n 3 ) fpt algorithm for the undirected feedback vertex set problem (2005)
Fpt Algorithm For, Frank Dehne, Michael Fellows, Michael Langston, Frances Rosamond, Kim Stevens
We descri e analgori hm for the Feedback Vertex Set problem onundi rected graphs, parameteri zed by the si ze k of the feedback vertex set, that runsi nti me O(c )wherec =10.567 and n i the number of...
The complexity of implicit and space-efficient priority queues (2005)
Mortensen, Christian W, Pettie, Seth, Dehne, Frank, López-Ortiz, Alejandro, Sack, Jörg-Rüdiger
Building Large ROLAP Data Cubes in Parallel (2004)
Ying Chen, Frank Dehne, Todd Eavis, A. 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...
Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors (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...
Parallel ROLAP data cube construction on shared-nothing multiprocessors (2004)
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...
An O∗(2^O(k) ) FPT algorithm for the undirected feedback vertex set problem (2004)
Frank Dehne, Michael R. Fellows, Michael A. Langston, Frances A. Rosamond, Kim Stevens
We describe an algorithm for the FEEDBACK VERTEX SET problem on undirected graphs, parameterized by the size k of the feedback vertex set, that runs in time O(c^k n³) where c =10.567 and n is the...
Parallel multidimensional ROLAP indexing (2003)
This paper addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present a distributed multi-dimensional ROLAP indexingscheme which is practical to implement, requires only...
Parallel clustal w for pc clusters (2003)
James Cheetham, Frank Dehne, Andrew Rau-chaplin, Peter J. Taillon
Abstract. 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,...
Solving large FPT problems on coarse-grained parallel machines (2003)
James Cheetham, Frank Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon
An FPT Algorithm for Set Splitting (2003)
Frank Dehne, Michael R. Fellows, Frances A. Rosamond
Abstract. An FPT algorithm with a running time of O(n 4 +2 O(k) n 2.5) is described for the Set Splitting problem, parameterized by the number k of sets to be split. It is also shown that there can...
CGMgraph/CGMlib: Implementing and Testing CGM Graph Algorithms on PC Clusters (2003)
In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PCclu8(T9 based on CGM algo rithms. CGMgraph implements parallel methods for variou graph prob lems. Ou...
Parallel ROLAP Data Cube Construction on Shared-Nothing Multiprocessors (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...
Top-Down Computation Of Partial ROLAP Data Cubes (2003)
Frank Dehne School, Frank Dehne
The precomputation of the di#erent summary views of a data cube is critical to improving the response time of data cube queries for On-Line Analytical Processing (OLAP). The computation of the full...
Parallel clustal w for pc clusters (2003)
James Cheetham, Frank Dehne, Andrew Rau-chaplin, Peter J. Taillon
Abstract. 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,...
Parallel multidimensional ROLAP indexing (2003)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
Abstract. This paper addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present a distributed multi-dimensional ROLAP indexing scheme which is practical to implement,...
Bulk Synchronous Parallel Algorithms for the External Memory Model (2002)
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...
Maximizing a Vo24 Regio The Co vex Case Frank Dehne (2002)
Klein And Rdo, Frank Dehne, Rolf Klein, Raimund Seidel
Given a set S o s po7 ts in the plane, wheredo we place a new poK t, p, ino77) to maximize the areao itsregio in the Vo9730 diagramo S and p? We study the case where the Vo80(8 neighbo9 o p are in co...
Parallelizing the data cube (2002)
Frank Dehne, Todd Eavis, Susanne Hambrusch, Andrew Rau-chaplin
Abstract. This paper presents a general methodology for the e cient parallelization of existing data cube construction algorithms. We describe two di erent partitioning strategies, one for top-down...
Parallelizing the Data Cube (2002)
Frank Dehne, Todd Eavis, Susanne Hambrusch, Andrew Rau-Chaplin, Www. Dehne. Net
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...
Parallelizing the Data Cube (2002)
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...
Solving large FPT problems on coarse grained parallel machines (2002)
James Cheetham, Frank Dehne, Andrew Rau-chaplin, Ulrike Stege, Peter J. Taillon
Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods....
Computing partial data cubes for parallel data warehousing applications (2001)
Frank Dehne, Andrew Rau-chaplin
Abstract. 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...
Computing partial data cubes for parallel data warehousing applications (2001)
Frank Dehne, Andrew Rau-chaplin
Abstract. 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...
Coarse grained parallel on-line analytical processing (OLAP) for data mining (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
Abstract. 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...
Coarse grained parallel on-line analytical processing (OLAP) for data mining (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
Abstract. 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...
Coarse grained parallel on-line analytical processing (OLAP) for data mining (2001)
Frank Dehne, Andrew Rau-chaplin
Abstract. 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...
A Cluster Architecture for Parallel Data Warehousing (2001)
Frank Dehne Carleton, Frank Dehne, Todd Eavis
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...
Computing Partial Data Cubes for Parallel Data Warehousing Applications (2001)
Frank Dehne, Todd Eavis, Andrew Rau-chaplin
In this paper, we fo cu on an approach to On-Line Analytical Processing (OLAP) that is based on a database operator and data stru2=---- called thedatacu e. The datacube is a relational operator that...
Coarse grained parallel on-line analytical processing (OLAP) for data mining (2001)
Frank Dehne, Andrew Rau-chaplin
Abstract. 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...
Coarse Grained Parallel Graph Planarity Testing (2000)
Albert Chan, Frank Dehne, S. W. Song
Abstract 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...
Coarse Grained Parallel Graph Planarity Testing (2000)
Albert Chan, Frank Dehne, S. W. Song
Abstract 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...
MESH SIMPLIFICATION IN PARALLEL (2000)
Council Canada, C. Langis, G. Roth, F. Dehne, Christian Langis, Gerhard Roth, ...
de l’information
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...
Reducing i/o complexity by simulating coarse grained parallel algorithms (1999)
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...
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...
Mesh Simplification in Parallel (1999)
Frank Dehne, Christian Langis, Gerhard Roth
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...
Reducing i/o complexity by simulating coarse grained parallel algorithms (1999)
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...
Mesh Simplification in Parallel (1999)
Frank Dehne, Christian Langis, Gerhard Roth
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 (1999)
Frank Dehne, Christian Langis, Gerhard Roth
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...
Reducing I/O Complexity by Simulating Coarse Grained Parallel Algorithms (1999)
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...
Algorithmica (1999) 24: Guest Editor's Introduction (1999)
this paper, n refers to the problem size and p to the number of processors
Mesh Simplification In Parallel (1999)
Christian Langis Gerhard, 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...
Practical parallel algorithms for minimum spanning trees (1998)
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...
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...
Coarse grained parallel next element search (1997)
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...
Coarse grained parallel next element search (1997)
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...
Coarse grained parallel next element search (1997)
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...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1996)
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,...
Randomized Parallel List Ranking For Distributed Memory Multiprocessors (1996)
. 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 (1996)
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...
A Randomized Parallel 3D Convex Hull Algorithm for Coarse Grained Multicomputers (1995)
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 (1995)
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...
Experiences with the implementation of geometric algorithms (1995)
Mehlhorn, Kurt, Akl, Selim G., Dehne, Frank, Sack, Jörg-Rüdiger, Santoro, Nicola
Frank Dehne, Claire Kenyon, Andreas Fabri
Abstract * We present parallel computational geometry algorithms that are scalable, architecture independent, easy to implement, and have, with high probability, an optimal time complexity for...
A Guided Tour through MOKUM 2.0 (1994)
This report describes version 2.0 of the MOKUM language and system. This is still a working document which should evolve into a kind of `everything you want to know about MOKUM but which you are...
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 (1994)
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...
Distributed Cyclic Reference Counting (1994)
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...
Frank Dehne, Andrew Rau-chaplin, Andreas Fabri
We studyscalable 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) O(1) local...
Scalable Parallel Computational Geometry for Coarse Grained Multicomputers (1993)
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 Geometric Algorithms For Coarse Grained Multicomputers (1992)
E De Recherche, Route Des Lucioles, Frank Dehne, Frank Dehne, Andreas Fabri, Andreas Fabri, ...
Whereas most of the literature assumes that the number of processors p is a function of the problem size n, in scalable algorithms p becomes a parameter of the time complexity. This is a more...
Construction Of D-Dimensional Hyperoctrees On A Hypercube . . . (1992)
E De Recherche, Route Des Lucioles, Mostafa Nassar, Andrew Rau-chaplin, Rada Valiveti, Frank Dehne, ...
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...
"The Big Sweep": On the Power of the Wavefront Approach to Voronoi Diagrams (1992)
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...
Parallel processing of pointer based quadtrees (1991)
Frank Dehne, Afonso G. Ferreira, Andrew Rau-chaplin
This paper studies the parallel construction and manipulation of pointer based quadtrees on the hypercube multiprocessor. While parallel algorithms for the manipulation of a variant of linear...
Parallel Processing of Pointer Based (1991)
Quadtrees On Hypercube, Frank Dehne, Afonso G. Ferreira, Andrew Rau-chaplin
This paper studies the parallel construction and manipulation of pointer based quadtrees on the hypercube multiprocessor.
Parallel computational geometry and clustering methods. (1986)
Würzburg, Univ., Diss., 1986.
Coarse Grained Parallel Algorithms for Detecting Convex Bipartite Graphs (1928)
Edson Caceres, Albert Chan, Frank Dehne, Giuseppe Prencipe
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...
SPR Distance Computation for Unrooted Trees
Hickey, Glenn, Dehne, Frank, Rau-Chaplin, Andrew, Blouin, Christian
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...
Bridging the gap between systems biology and medicine
Clermont, Gilles, Auffray, Charles, Moreau, Yves, Rocke, David M, Dalevi, Daniel, Dubhashi, Devdatt, ...
Systems biology has matured considerably as a discipline over the last decade, yet some of the key challenges separating current research efforts in systems biology and clinically useful results are...