Search

In this paper, we present an OLAP framework for trajectories of moving objects. We introduce a new operator GROUP_TRAJECTORIES for group-by operations on trajectories and present three implementation alternatives for computing groups of trajectories for group-by aggregation: group by overlap, group by intersection, and group by overlap and intersection. We also present an interactive OLAP environment for resolution drill-down/roll-up on sets of trajectories and parameter browsing. Using generated and real life moving data sets, we evaluate the performance of our GROUP_TRAJECTORIES operator. An implementation of our new interactive OLAP environment for trajectories can be accessed at http://OLAP-T.cgmlab.org .

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 challenge in order to minimize view maintenance and query processing costs. Some existing approaches are applicable only for small problems, which are far from reality. In this paper we introduce a new approach for materialized view selection using Parallel Simulated Annealing (PSA) that selects views from an input Multiple View Processing Plan (MVPP). With PSA, we are able to perform view selection on MVPPs having hundreds of queries and thousands of views. Also, in our experimental study we show that our method provides a significant improvement in the quality of the obtained set of materialized views over existing heuristic and sequential simulated annealing algorithms.

Protein-protein interactions (PPIs) play a critical role in many cellular functions. A number of experimental techniques have been applied to discover PPIs; however, these techniques are expensive in terms of time, money, and expertise. There are also large discrepancies between the PPI data collected by the same or different techniques in the same organism. We therefore turn to computational techniques for the prediction of PPIs. Computational techniques have been applied to the collection, indexing, validation, analysis, and extrapolation of PPI data. This chapter will focus on computational prediction of PPI, reviewing a number of techniques including PIPE, developed in our own laboratory. For comparison, the conventional large-scale approaches to predict PPIs are also briefly discussed. The chapter concludes with a discussion of the limitations of both experimental and computational methods of determining PPIs.

When dealing with hard computational problems (NP-complete or worse), Scientists, Engineers and other users of software provided by Computer Scientists care most about how large a problem instance a particular method is able to solve in reasonable time. In this talk, we discuss the contributions and deficiencies of current fixed parameter tractability methods within this context.

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 used in other circumstances as well, including the (i) use of extremal combinatorics (known results from graph theory) in order to obtain very small kernels, (ii) use of known exact algorithms for the (nonparameterized) minimum dominating set problem, and (iii) use of exponential space. Parameterized by the size kd of the non-blocking set, we obtain an algorithm that runs in time ${\mathcal O}^{*}(1.4123^{k_{d}})$ when allowing exponential space.

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 [6,7], and compare our implementation with the straightforward greedy method and a solution based on linear programming [3]. Our experiments show that the best results are obtained by using the refined branching method in [7] together with interleaving (re-kernelization). We also observe an interesting lack of monotonicity in the running times for “yes” instances with increasing values of k.

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(ckn3) where c=10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due to Raman, Saurabh and Subramanian, has a parameter function of the form 2O( klogk / loglogk). Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general “annotated” form of the problem, where a subset of the vertices may be marked as not to belong to the feedback set. We also establish “exponential optimality” for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT =M[1].

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 Vertex Cover. In the case of Set Splitting, we improve the best previous \({\mathcal O}^*(72^k)\) FPT algorithm due to Dehne, Fellows and Rosamond [DFR03], to \({\mathcal O}^*(8^k)\) by an approach based on greedy localization in conjunction with modeled crown reduction. In the case of Vertex Cover, we describe a new approach to 2k kernelization based on iterative compression and crown reduction, providing a potentially useful alternative to the Nemhauser-Trotter 2k kernelization.

Dehne et al. present a BSP/CGM algorithm for computing a spanning tree and the connected components of a graph, that requires O(log p) communication rounds, where p is the number of processors. It requires the solution of the Euler tour problem which in turn is based on the solution of the list ranking problem. We present a new approach that does not need to solve the Euler tour or the list ranking problem. It is based on the integer sorting algorithm which can be implemented efficiently on the BSP/CGM model [1].

In this paper we present a parallel wavefront algorithm for computing an alignment between two strings A and C, with |A| = m and |C| = n. On a distributed memory parallel computer of p processors each with O((m + n)/p) memory, the proposed algorithm requires O(p) communication rounds and O(mn/p) local computing time. The novelty of this algorithm is based on a compromise between the workload of each processor and the number of communication rounds required, expressed by a parameter called α. The proposed algorithm is expressed in terms of this parameter that can be tuned to obtain the best overall parallel time in a given implementation. We show very promising experimental results obtained on a 64-node Beowulf machine. A characteristic of the wavefront communication requirement is that each processor communicates with few other processors. This makes it very suitable as a potential application for grid computing.

In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on CGM algorithms. CGMgraph implements parallel methods for various graph problems. Our implementations of deterministic list ranking, Euler tour, connected components, spanning forest, and bipartite graph detection are, to our knowledge, the first efficient implementations for PC clusters. Our library also includes CGMlib, a library of basic CGM tools such as sorting, prefix sum, one to all broadcast, all to one gather, h-Relation, all to all broadcast, array balancing, and CGM partitioning. Both libraries are available for download at http://cgm.dehne.net.

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 run on a range of distributed and shared memory parallel machines, from high-end parallel multiprocessors (e.g. Sunfire 6800, IBM SP2, etc.) to PC clusters, to simple networks of workstations. We have implemented pCLUSTAL using C and the MPI communication library, and tested it on a PC cluster. Our experimental evaluation shows that our pCLUSTAL code achieves similar or better speedup on a distributed memory PC clusters than the commercial SGI parallel Clustal on a shared memory SGI multiprocessor.

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 be no FPT algorithm for this problem with a running time of the form 2 o(k) n c unless the satisfiability of n-variable 3SAT instances can be decided in time 2 o(n).

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 for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter-processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel as is done in previous parallel approaches. In fact, after the initial load distribution phase, each processor can compute its assigned subcube without any communication with the other processors. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting. The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array. Experimental results presented show that our partitioning strategies generate a close to optimal load balance between processors.

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 efficient parallelization of existing data cube construction algorithms for OLAP. Experimental data indicate that our approach yield optimal speedup, even when run on a simple processor cluster connected via a standard switch.

In this paper we discuss what kind of information can be obtained from WordNet and what kind of information should be added to WordNet in order to make it better suitable for the support of the Color-X method. We will present an extension of WordNet (called WordNet++) which contains a number of special types of relationships that are not available in WordNet. Additionally, WordNet++ is instantiated with knowledge about some particular domain.

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 is used to construct all possible views of a given data set. Efficient algorithms for computing the entire datacube - both sequentially and in parallel - have recently been proposed. However, due to space and time constraints, the assumption that all 2d (where d = dimensions) views should be computed is often not valid in practice. As a result, algorithms for computing partial datacubes are required. In this paper, we describe a parallel algorithm for computing partial datacubes and provide preliminary experimental results based on an implementation in C and MPI.

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 whether a graph G is bipartite, and (2) determining whether a bipartite graph G is convex. Our algorithms require O(log p) and O(log2 p) communication rounds, respectively, and linear sequential work per round on a CGM with p processors and N/p local memory per processor, N=|G|. The algorithms assume that N/p ≥ pƐ for some fixed Ɛ > 0, which is true for all commercially available multiprocessors. Our results imply BSP algorithms with O(log p) and O(log2 p) supersteps, respectively, O(g log(p)N/p) communication time, and O(log(p)N/p) local computation time. Our algorithm for determining whether a bipartite graph is convex includes a novel, coarse grained parallel, version of the PQ tree data structure introduced by Booth and Lueker. Hence, our algorithm also solves, with the same time complexity as indicated above, the problem of testing the consecutive-ones property for (0, 1) matrices as well as the chordal graph recognition problem. These, in turn, have numerous applications in graph theory, DNA sequence assembly, database theory, and other areas.

In this paper, we present deterministic parallel algorithms for the coarse grained multicomputer (CGM) and bulk-synchronous parallel computer (BSP) models which solve the following well known graph problems: (1) list ranking, (2) Euler tour construction, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, (7) 2-edge connectivity and biconnectivity (testing and component computation), and (8) cordai graph recognition (finding a perfect elimination ordering). The algorithms for Problems 1–7 require O(log p) communication rounds and linear sequential work per round. Our results for Problems 1 and 2 hold for arbitrary ratios \(\frac{n}{p}\), i.e. they are fully scalable, and for Problems 3–8 it is assumed that \(\frac{n}{p} \geqslant p^ \in ,{\mathbf{ }} \in {\mathbf{ }} > 0\), which is true for all commercially available multiprocessors. We view the algorithms presented as an important step towards the final goal of O(1) communication rounds. Note that, the number of communication rounds obtained in this paper is independent of n and grows only very slowly with respect to p. Hence, for most practical purposes, the number of communication rounds can be considered as constant. The result for Problem 1 is a considerable improvement over those previously reported. The algorithms for Problems 2–7 are the first practically relevant deterministic parallel algorithms for these problems to be used for commercially available coarse grained parallel machines.

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) communication rounds (h-relations with h=O(n/p)) and O(n/p) local computation. An improved version requires, with high probability, only r ≤ (4k+6) log (2/3p)+8=O(k log p) communication rounds where k= min{i ≥ 0¦ln(i+1)n ≤ (2/3p)2i+1}. Note that k < ln*(n) is an extremely small number. For \(n \leqslant 10^{10^{100} }\)and p ≥ 4, the value of k is at most 2. For a given number of processors, p, the number of communication rounds required is, for all practical purposes, independent of n. For \(n \leqslant 10^{10^{100} }\)and 4 ≤ p ≤ 2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118. We conjecture that the actual number of communications rounds will not exceed 50.

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 processors to run local mark-scan simultaneously without any need of synchronisation between phases of different local mark-scans either on the same processor or on different processors.

We show that the line sweep approach to Voronoi diagrams can be generalized to a very general class of distance measures called nice metrics. This class is more general than the previously studied convex distance functions. It includes e.g the Moscow metric.

In this paper, we study the problem of implementing standard data structures on a hypercube multiprocessor. We present a technique for efficiently executing multiple independant search processes on a class of graphs called ordered h-level graphs. We show how this technique can be utilized to implement a segment tree on a hypercube, thereby obtaining O(log2n) time algorithms for solving the next element search problem, the trapezoidal decomposition problem, the triangulation problem, and the (multiple) planar point location problem.

This paper discusses the construction of the 3-dimensional convex hull for a set of n points stored on a √n × √n mesh of processors. Lu has shown that this problem can be solved in √n log n time if all points are located on a sphere. Here, we solve, in the same time-complexity, the 3-dimensional convex hull problem for arbitrary point sets. Furthermore, we observe a time/space trade off: if each processor is allocated O(log n) space then √n time is sufficient to determine the 3-dimensional convex hull.

A systolic screen of size M is a √M × √M mesh-of-processors where each processing element Pij represents the pixel (i,j) of a digitized plane П of √M × √M pixels. In this paper we study the computation of the Voronoi diagram of a set of n planar objects represented by disjoint images contained in П. We present O(√M) time algorithms to compute the Voronoi diagram for a large class of object types (e.g., points, line segments, circles, ellipses, and polygons of constant size) and distance functions (e.g., all Lp metrices).

The Voronoi diagram of n sites on the surface of a cone has a combinatorial structure rather different from the planar one. We present a sweepcircle algorithm that enables its computation within optimal time O(n log n), using linear storage.

We survey computational geometry algorithms developed for various models of parallel computation including the PRAM, hypercube, mesh-of-processors, linear processor array, mesh of trees, and pyramid.

Recently, a growing interest in problems dealing with the movability of objects has been observed. Motion problems are manifold due to the variety of areas in which they may occur; among these areas are e.g. robotics, computer graphics, etc. One motion problem class recently being investigated is the separability problem.