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.

Abstract

This paper initiates formal analysis of a simple, distributed algorithm for community detection on networks. We analyze an algorithm that we calltextsc {Max-LPA}, both in terms of its convergence time and in terms of the" quality" of the communities detected.textsc {Max-LPA} is an instance of a class of community detection algorithms calledtextit {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 ofer random graphs with clusters where the probability , of an edge connecting nodes within a cluster is higher than , the probability of an edge connecting nodes in distinct clusters. We show that even with fairly general restrictions on and ( for any , , where is the number of nodes),textsc {Max-LPA} detects the clusters in just two rounds. Based on this and on empirical results, we conjecture thattextsc {Max-LPA} can correctly and quickly identify communities on clustereder graphs even when the clusters are much sparser, ie, with for some .

Abstract

Graphics processing units (GPUs) provide large computational power at a very low price, which position GPUs well as an ubiquitous accelerator. However, GPUs are space constrained, and hence applications developed for GPUs are space sensitive. Space-constrained computational devices such as GPUs can greatly benefit from representations that reduce space consumption drastically. One such representation is the succinct representation of trees. Succinct representation of trees generally allows for operations such as parent queries, least common ancestor queries, and so on. Mapping such a robust representation to the GPU for targeted applications can lead to substantial improvement in problem sizes that are processed at a given point of time. Space-saving methods such as succinct data structures remain largely unexplored on the GPU. In this work, a succinct representation of ordered trees on the GPU is explored, with application to discrete range searching (DRS). Based on the succinct representations found applicable, a space--saving solution for DRS is presented here. In our method, DRS is mapped to a least common ancestor query on a Cartesian tree. For space-efficient DRS queries, we store the succinct representation of the Cartesian tree of an array. Our method uses a maximum of 7.5 bits of additional space per element. Furthermore, the speed-up achieved by our method is in the range of 20--25 for preprocessing and 25--35 for batch querying over a sequential implementation. Compared to an 8-threaded implementation, our preprocessing and querying methods obtain a speed-up of 6--8. We also study the applications of the DRS on the GPU. Efficient primitives expand the range of applications performed on the GPU. DRS is one such primitive with direct applications to string processing, document and text retrieval systems, and least common ancestor queries. We suggest that graph algorithms that use the least common ancestor, can be enabled on the GPU based on DRS primitive. We also show some applications of DRS in tree queries and string querying.

Abstract

Sparse matrix-sparse/dense matrix multiplications, spgemm and csrmm, respectively, among other applications find usage in various matrix formulations of graph problems. Considering the difficulties in executing graph problems and the duality between graphs and matrices, computations such as spgemm and csrmm have recently caught the attention of HPC community. These computations pose challenges such as load balancing, irregular nature of the computation, and difficulty in predicting the output size. It is even more challenging when combined with the GPU architectural constraints such as memory accesses, limited shared memory, strict SIMD and thread execution. To address these challenges on a GPU, we evaluate three possible variations of matrix multiplication (Row-Column, Column-Row, Row-Row) and perform suitable optimizations targeted at sparse matrices. Our experiments indicate that the Row-Row formulation, which mostly outperforms the other formulations, is 3.5x faster on average compared to an optimized multi-core implementation in the Intel MKL library. We extend the Row-Row formulation to a CPU+GPU hybrid algorithm that simultaneously utilizes the CPU also. In this direction, we present heuristics to find the right amount of work division between the CPU and the GPU. Our hybrid row-row formulation of the spgemm operation performs 5.5x faster on average when compared to the optimized multi-core implementation in the Intel MKL library. Our experience indicates that it is difficult to identify right amount of work division between the CPU and the GPU. We therefore investigate a subclass of sparse matrices, band matrices, and present an analytical method to identify a good work division when multiplying two band matrices. Our GPU csrmm operation performs 2.5x faster on average when compared to a corresponding implementation in the cusparse library, which outperforms the Intel MKL library implementation.

Abstract

Accurate segmentation of the cup region from retinal images is needed to derive relevant measurements for glaucoma assessment. A novel, depth discontinuity (in the retinal surface)-based approach to estimate the cup boundary is proposed in this paper. The proposed approach shifts focus from the cup region used by existing approaches to cup boundary. The given set of images, acquired sequentially, are related via a relative motion model and the depth discontinuity at the cup boundary is determined from cues such as motion boundary and partial occlusion. The information encoded by these cues is used to approximate the cup boundary with a set of best-fitting circles. The final boundary is found by considering points on these circles at different sectors using a confidence measure. Four different kinds of data sets ranging from synthetic to real image pairs, covering different multiview scenarios, have been used to evaluate the proposed method. The proposed method was found to yield an error reduction of 16% for cup-to-disk vertical diameter ratio (CDR) and 13% for cup-to-disk area ratio (CAR) estimation, over an existing monocular image-based cup segmentation method. The error reduction increased to 33% in CDR and 18% in CAR with the addition of a third view (image) which indicates the potential of the proposed approach.

Abstract

Retinopathy of prematurity (ROP) is a vascular disease in premature infants. This is characterized by abnormal vessel growth and subsequent fibrosis in the peripheral retina. The prognosis of ROP relies on information on the presence of abnormal growth and their location. Diagnosis is based on a series of images obtained with a wide field of view camera (such as RetCam), to capture the complete retina. In this paper, we present a novel and efficient hierarchal mosaicing algorithm, for neonatal images of varying quality. We employ a vessel-based quality metric and exploit the knowledge of the retinal structure to automatically select a subset of images from a given set, to construct a good quality mosaic. Such mosaics can aid the assessment of ROP by providing a comprehensive and complete view of the entire retina. The hierarchal approach underlying the method makes it possible to complete the mosaicing task in close to real time. The proposed method has been tested on 14 sets of data with each set consisting of 6-35 retinal images acquired using RetCam and the generated mosaics are found to be of good quality as validated by a clinical expert.

Abstract

The task of detecting peri-papillary indicators associated with the glaucoma is challenging due to the high degree of intra and inter-image variations commonly seen in colour retinal images. The existing approaches based on direct modeling of the region of interest failto handle such image variations which compromises detection accuracy.In this paper, a novel detection strategy is proposed which exploits the saliency property associated with these indicators. The region of interest is modeled as a region substantially different from the adjacent image regions. This dissimilarity information is derived at the feature level, be-tween the target and its adjacent regions. Based on the proposed strategy,two novel methods are presented for the detection of peri-papillary atrophy and RNFL defect from colour retinal images. Two different datasets have been used to evaluate the performance of developed solutions. The obtained results are encouraging and establish the strength of the pro-posed strategy in handling high degree of image variations. The preliminary results and comparative evaluation with direct modeling strategy show viability of proposed strategy to be used in the glaucoma assessment task.

Abstract

We designed, developed and evaluated an Augmentative and Alternative Communication (AAC) system,AutVisComm,for children with autism that can run on smart phones and tablets. An iterative de-sign and development process was followed, where the prototypes were developed in close collaboration with the user group, and the usability testing was gradually expanded to larger groups. In the last evaluation stage described here, twenty-four children with autism used AutVisCommto learn to request the desired object. We measured their learning rates and correlated them with their behavior traits (as observed by their teachers) like joint attention, symbolic processing and imitation.We found that their ability for symbolic processing did not correlate with the learning rate, but their ability for joint attention did. This suggests that this system (and this class of AACs) helps to compensate for a lack of symbolic processing, but not for a lack of joint-attention mechanism.