Abstract

We consider the planar convex hull range query problem. Let P be a set of points in the plane. We preprocess these points into a data structure such that given an orthogonal range query, we can report the convex hull of the points in the range in O (log2 n+ h) time, where h is the size of the output. The data structure uses O (n log n) space. This improves the previous bound of O (log5 n+ h) time and O (n log2 n) space. Given a range query, it also supports extreme points in a given direction, tangent queries through a given point, and line-hull intersection queries on the points in the range in time O (log2 n) for each orthogonal query and O (log n) time for each additional query on that range. These problems have not been studied before.

Abstract

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we call Max-LPA, both in terms of its convergence time and in terms of the “quality” of the communities detected. Max-LPA is an instance of a class of community detection algorithms called label propagation algorithms. As far as we know, most analysis of label propagation algorithms thus far has been empirical in nature and in this paper we seek a theoretical understanding of label propagation algorithms. In our main result, we define a clustered version of Erdös-Rényi random graphs with clusters V 1, V 2, …, V k where the probability p, of an edge connecting nodes within a cluster V i is higher than p′, the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on p and p′ ( p=Ω(1n1/4−ϵ) for any ε > 0, p′ = O(p 2), where n is the number of nodes), Max-LPA detects the clusters V 1, V 2, …, V n in just two rounds. Based on this and on empirical results, we conjecture that Max-LPA can correctly and quickly identify communities on clustered Erdös-Rényi graphs even when the clusters are much sparser, i.e., with p=clognn for some c > 1.

Abstract

Sorting has been a topic of immense research value since the inception of Computer Science. Hybrid computing on multicore architectures involves computing simultaneously on a tightly coupled heterogeneous collection of devices. In this work, we consider a multicore CPU along with a many core GPU as our experimental hybrid platform. In this work, we present a hybrid comparison based sorting algorithm which utilizes a many-core GPU and a multi-core CPU to perform sorting. The algorithm is broadly based on splitting the input list according to a large number of splitters followed by creating independent sub lists. Sorting the independent sub lists results in sorting the entire original list. On a CPU+GPU platform consisting of an Intel i7 980 and an Nvidia GTX 580, our algorithm achieves a 20% gain over the current best known comparison sort result that was published by Davidson et. al. [In Par 2012]. On the above experimental platform, our results are better by 40% on average over a similar GPU-alone algorithm proposed by Leischner et. al. [IPDPS 2010]. Our results also show that our algorithm and its implementation scale with the size of the input. We also show that such performance gains can be obtained on other hybrid CPU+GPU platforms.

Abstract

We consider the problem of reporting convex hull points in an orthogonal range query in two dimensions. Formally, let $ P $ be a set of $ n $ points in $\mathbb {R}^{2} $. A point lies on the convex hull of a point set $ S $ if it lies on the boundary of the minimum convex polygon formed by $ S $. In this paper, we are interested in finding the points that lie on the boundary of the convex hull of the points in $ P $ that also fall with in an orthogonal range $[x_ {lt}, x_ {rt}]\times {}[y_b, y_t] $. We propose a $ O (n\log^{2} n) $ space data structure that can support reporting points on a convex hull inside an orthogonal range query, in time $ O (\log^{3} n+ h) $. Here $ h $ is the size of the output. This work improves the result of (Brass et al. 2013)\cite {brass} that builds a data structure that uses $ O (n\log^{2} n) $ space and has a $ O (\log^{5} n+ h) $ query time. Additionally, we show that our data structure can be modified slightly to solve other related problems. For instance, for counting the number of points on the convex hull in an orthogonal query rectangle, we propose an $ O (n\log^{2} n) $ space data structure that can be queried upon in $ O (\log^{3} n) $ time. We also propose a $ O (n\log^{2} n) $ space data structure that can compute the $ area $ and $ perimeter $ of the convex hull inside an orthogonal range query in $ O (\log^{3} n $) time.

Abstract

The shared whiteboard model for distributed computing is one of the recent interesting models to be proposed (See Becker et al. (SPAA 2012)). In its basic form, this model allows all nodes to write a message of no more than O(log n) bits on a whiteboard that every node can read. However, each node can write at most once. In this model, a variety of problems from graphs are shown to be either possible or impossible. In this paper we extend the work of Becker et al. to allow for nodes to write on the shared whiteboard more than once. However, each node can write at most O(log n) bits at any one instant. Interestingly, in this model, we show that allowing just two rounds of writing on the whiteboard, one can color the vertices of a d-degenerate graph using d+1 colors. Similarly, we show that two rounds suffice to find maximal independent set (MIS), whereas 2-ruling sets can be computed in one round in simultaneous synchronous models. Finally, we show that for finding connected components in a graph, even O(1) rounds is not enough in general. We show that any deterministic algorithm that follows certain rules requires at least Omega(log nlog log n) rounds to find the connected components of an n-vertex graph. At the same time, we show the existence of a O(log n) round algorithm for the same. Thus, our results indicate that the multi-round shared whiteboard model has interesting consequences.

Abstract

Distributed algorithms for computing a maximal independent set of a graph have been very popular in the research community. Starting with the algorithm of Luby dating back to 25 years, several researchers have focused on distributed MIS algorithms for general graphs. with little success. Only recently, M'etevier et al. have proposed an algorithm for MIS in the distributed setting with a round complexity that matches Luby's algorithm asymptotically. However, very little is known about the relative performance of the algorithm of Luby and M'etevier in practice. Such a study can throw light on some aspects of the algorithms that are not brought out by a theoretical analysis. In this paper, we compare implementations of the algorithm of Luby and M'etevier and study their behavior on a class of random graphs and bipartite graphs. Further, we study how varying the probability that a node wishes to join the MIS in the case of Luby's algorithm affects the number of rounds required.

Abstract

Graph algorithms play a prominent role in several fields of sciences and engineering. Notable among them are graph traversal, finding the connected components of a graph, and computing shortest paths. There are several efficient implementations of the above problems on a variety of modern multiprocessor architectures. It can be noticed in recent times that the size of the graphs that correspond to real world data sets has been increasing. Parallelism offers only a limited succor to this situation as current parallel architectures have severe short-comings when deployed for most graph algorithms. At the same time, these graphs are also getting very sparse in nature. This calls for particular work efficient solutions aimed at processing large, sparse graphs on modern parallel architectures. In this paper, we introduce graph pruning as a technique that aims to reduce the size of the graph. Certain elements of the graph can be pruned depending on the nature of the computation. Once a solution is obtained for the pruned graph, the solution is extended to the entire graph. We apply the above technique on three fundamental graph algorithms: breadth first search (BFS), Connected Components (CC), and All Pairs Shortest Paths (APSP). To validate our technique, we implement our algorithms on a heterogeneous platform consisting of a multicore CPU and a GPU. On this platform, we achieve an average of 35% improvement compared to state-ofthe-art solutions. Such an improvement has the potential to speed up other applications that rely on these algorithms.

Abstract

In this work, we study the problem of reporting and counting maximal points in a query rectangle for a set of n integer points that lie on an n×n grid. A point is said to be maximal inside a query rectangle if it is not dominated by any other point inside the query rectangle. Our model of computation is unit-cost RAM model with word size of O(logn) bits. For the reporting version of the problem, we present a data structure of size words and support querying in time where k is the size of the output. For the counting version, we present a data structure of size words which supports querying in . Both the data structures are static in nature. The reporting version of the problem has been studied in [1] and [5]. To the best of our knowledge, this is the first sub-logarithmic result for the reporting version and the first work for the counting version of the problem.

Abstract

The use of manycore architectures and accelerators, such as GPUs, with good programmability has allowed them to be deployed for vital computational work. The ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks that we highlight in this paper. It is of high interest therefore to develop a parallel, quality PRNG that also works in an on demand model. In this paper we investigate a CPU+GPU hybrid technique to create an efficient PRNG. The basic technique we apply is that of random walks on expander graphs. Unlike existing generators available in the GPU programming environment, our generator can produce random numbers on demand as opposed to a onetime generation. Our approach produces 0.07 GNumbers per second. The quality of our generator is tested with industry standard tests. We also demonstrate two applications of our PRNG. We apply our PRNG to design a list ranking algorithm which demonstrates the on-demand nature of the algorithm and a Monte Carlo simulation which shows the high quality of our generator.

Abstract

We consider the problem of reporting and counting maximal points in a given orthogonal query range in two-dimensions. Our model of computation is the pointer machine model. Let P be a static set of n points in ℝ2. A point is maximal in P if it is not dominated by any other point in P. We propose a linear space data structure that can support counting the number of maximal points inside a 3-sided orthogonal query rectangle unbounded on its right in O(logn) time. For counting the number of maximal points in a 4-sided orthogonal query rectangle, we propose an O(n logn) space data structure that can be constructed in O(n logn) time and queried upon in O(logn) time. This work proposes the first data structure for counting the number of maximal points in a query range. Das et al. proposed a data structure for the counting version in the word RAM model [WALCOM 2012]. For the corresponding reporting versions, we propose a linear size data structure for reporting maximal points inside a 3-sided query range in time O(logn + k), where k is the size of the output. We propose an O(n logn) size data structure for reporting the maximal points in a 4-sided orthogonal query range in time O(logn + k), where k is the size of the output. The methods we propose for reporting maximal points are simpler than previous methods and meet the best known bounds.