Search

Fast aggregation of data with many dimensions is a key component of many applications. The R-tree is the traditional data structure for indexing multi-dimensional data, but even the best R-tree variants suffer from performance degradation as the number of dimensions increases. The DC-tree addressed this issue by replacing Minimum Bounding Rectangle (MBR) keys with Minimum Describing Subsets (MDSs), which are less susceptible to overlap. This technique dramatically improves query performance with many dimensions, but at the cost of reduced insertion performance. Like most R-tree variants, this insertion overhead comes from expensive geometric comparisons while selecting the best child for insertion, or splitting over-full nodes. DC-trees, including the parallel PDC-tree, suffer even more from this overhead since MDSs are typically much more expensive to compare and manipulate than MBRs. This paper introduces the Hilbert PDC-tree, a parallel index structure for many-dimensional data that supports high-velocity data ingestion. This is achieved by avoiding geometric comparisons during insertion by instead inserting records based on the Hilbert index of their keys. This approach is similar to that of the Hilbert R-tree, but with special considerations for efficiently supporting many hierarchical dimensions. Additionally, a new node splitting algorithm significantly reduces overlap and improves query performance. Experiments show that the Hilbert PDC-tree scales well to a high number of dimensions, while supporting a much higher rate of ingestion and better query performance than the PDC-tree.

The importance of parallel algorithms has increased considerably due to the emergence of multi-core processors and many-core processors (GPUs).

In this paper we study the potential performance improvements for catastrophe modelling systems that can be achieved through parallelization on a Cell Processor. We studied and parallelized a critical section of catastrophe modelling, the so called "inner loop", and implemented it on a Cell Processor running on a regular Playstation 3 platform. The Cell Processor is known to be a challenging environment for software development. In particular, the small internal storage available at each SPE of the Cell Processor is a considerable challenge for catastrophe modelling because the catastrophe modelling algorithm requires frequent accesses to large lookup tables. Our parallel solution is a combination of multiple techniques: streaming data to the SPEs and parallelizing inner loop computations, building caches on the SPEs to store parts of the large catastrophe modelling lookup tables, vectorizing the computation on the SPEs, and double-buffering the file I/O. On a (Playstation 3) Cell Processor with six active SPEs and 4-way vectorization on each SPE (implying a maximum theoretical 24x speedup), we were able to measure a sustained 16x speedup for our parallel catastrophe modelling code over a wide range of data sizes for real life Japanese earthquake data.

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 algorithms are specially crafted for the EM situation. In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge by the ACM Working Group on Storage I/O for Large-Scale Computing. In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine. When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems.

This paper deals with the relationship between cluster analysis and computational geometry describing clustering strategies using a Voronoi diagram approach in general and a line separation approach to improve the efficiency in a special case. We state the following theorems : The set of all centralized 2-clusterings (S1,S2) of a planar point set S with |S1|=a and |S2|=b is exactly the set of all pairs of labels of opposite Voronoi polygons va(S1,S) and vb(S2,S) of Va(S) and Vb(S) respectively.An optimal centralized 2-clustering [centralized divisive hierarchical 2- clustering] can be constructed in O(n n1/2 log2n + UF(n) n n1/2 + PF(n)) [O(n n1/2 log3n + UF(n) n n1/2 + PF(n)) respectively] steps with PF(n) and UF(n) being the time complexity to compute and update a given clustering measure f.