Abstract

This paper considers the question of how many colors a distributed graph coloring algorithm would need to use if it had only k rounds available, for any positive integer k. In our main result, we present an algorithm that runs in O(k) rounds for any k bounded below by ©(log log n) and bounded above by O(√log n), and uses O(a Å n1/k) colors to color a graph with arboricity a. This result is optimal since the palette size matches the lower bound of Barenboim and Elkin (PODC 2008). This result is achieved via the use of several new results developed in this paper on coloring graphs whose edges have been acyclically oriented. For example, suppose that G is an n-vertex, acyclically oriented graph with maximum out-degree Δo. We present an algorithm that, for any k ≥ 2 loglog n, runs in O(k) rounds on G to produce an (i) O(Δo)-coloring when Δo Δ ©(maxkn2/k2log1+1/kn, 2k) and an (ii) O(Δo Å n2/k2)-coloring when Δo ∈ Ω(maxk log1+1/kn, 2k). These results are useful in any setting where it is possible to efficiently compute acyclic orientations of a graph with Δo << Δ. We derive non-trivial bounds on the palette size even when k < 2 loglog n. Our main technical contributions can be summarized as: (i) developing a k-round version of the algorithm of Kothapalli et al. (IPDPS 2006) which computes an O(?)-coloring of a graph in O(√log n) rounds, and (ii) developing an oriented version of the Brooks-Vizing coloring result of Grable and Panconesi (SODA 1998).

Abstract

We consider the dominating point set reporting problem in two-dimension. We propose a data structure for finding the set of dominating points inside a given orthogonal query rectangle. Given a set of n points in the plane, it supports 4-sided queries in O (log n+ k), where k is size of the output, using O (n log n) space. This work can be of application when range queries are generated using mobile devices with limited display capacity.

Abstract

In this work we study the problem of finding axesparallel regions of maximum density for weighted point sets in IR2 and IR3. The 2-d variant is motivated by applications in thermal analysis of VLSI chips.

Abstract

Multiplying a sparse matrix with a vector (spmv for short) is a fundamental operation in many linear algebra kernels. Having an efficient spmv kernel on modern architectures such as the GPUs is therefore of principal interest. The computational challenges that spmv poses are significantlydifferent compared to that of the dense linear algebra kernels. Recent work in this direction has focused on designing data structures to represent sparse matrices so as to improve theefficiency of spmv kernels. However, as the nature of sparseness differs across sparse matrices, there is no clear answer as to which data structure to use given a sparse matrix. In this work, we address this problem by devising techniques to understand the nature of the sparse matrix and then choose appropriate data structures accordingly. By using our technique, we are able to improve the performance of the spmv kernel on an Nvidia Tesla GPU (C1060) by a factor of up to80% in some instances, and about 25% on average compared to the best results of Bell and Garland [3] on the standard dataset (cf. Williams et al. SC'07) used in recent literature. We also use our spmv in the conjugate gradient method and show an average 20% improvement compared to using HYB spmv of [3], on the dataset obtained from the The University of Florida Sparse Matrix Collection [9].

Abstract

The advent of multicore and many-core architectures saw them being deployed to speed-up computations across several disciplines and application areas. Prominent examples include semi-numerical algorithms such as sorting, graph algorithms, image processing, scientific computations, and the like. In particular, using GPUs for general purpose computations has attracted a lot of attention given that GPUs can deliver more than one TFLOP of computing power at very low prices. In this work, we use a new model of multicore computing called hybrid multicore computing where the computation is performed simultaneously a control device, such as a CPU, and an accelerator such as a GPU. To this end, we use two case studies to explore the algorithmic and analytical issues in hybrid multicore computing. Our case studies involve two different ways of designing hybrid multicore algorithms. The main contribution of this paper is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [Z. Wei, J. JaJa; IPDPS 2010]. Similarly, our hybrid algorithm for graph connected components is faster by 25% compared to the best known GPU implementation [26].

Abstract

Diabetic retinopathy is the leading cause of blindness in urban populations. Early diagnosis through regular screening and timely treatment has been shown to prevent visual loss and blindness. It is very difficult to cater to this vast set of diabetes patients, primarily because of high costs in reaching out to patients and a scarcity of skilled personnel. Telescreening offers a cost-effective solution to reach out to patients but is still inadequate due to an insufficient number of experts who serve the diabetes population. Developments toward fundus image analysis have shown promise in addressing the scarcity of skilled personnel for large-scale screening. This article aims at addressing the underlying issues in traditional telescreening to develop a solution that leverages the developments carried out in fundus image analysis.

Abstract

The most widely followed procedure for diagnosis and prognosis of dementia is structural neuro imaging of hippocampus by means of MR. Hippocampus segmentation is of wide interest as it enables quantitative assessment of the structure. In this paper, we propose an algorithm for hippocampus segmentation that is un-supervised and image driven. It is based on a hybrid approach which combines a coarse segmentation and surface evolution. A coarse solution is derived using region growing which is further refined using a modified version of the physics based water flow model (Liu and Nixon, 2007). The proposed method has been tested on a publicly available dataset. The performance of this method is assessed using Dice coefficient against the ground truth provided for 25 volume images. It is consistent across volumes and the average Dice values are comparable to a multi-atlas based method reported on a subset of the same dataset.

Abstract

Segmentation in echo-cardiographic images is a difficult task due to the presence of speckle noise, low contrast and blurring. We present a novel method based on clustering performed in the feature space. A new feature-based image representation is proposed. It is obtained by computing a local feature descriptor at every pixel location. This descriptor is derived using the Radon-Transform to effectively characterise local image context. Next, an un-supervised clustering is performed in the feature space to segment regions in the image. The performance of the proposed method is tested on both synthetic and real images. A comparison against well established feature descriptors is carried out to demonstrate the strengths and applicability of the proposed representation. Overall, the results indicate promise in the strategy of doing segmentation of noisy data in image descriptor space.

Abstract

Pneumoconiosis, a lung disease caused by the inhalation of dust, is mainly diagnosed using chest radiographs. The effects of using contralateral symmetric (CS) information present in chest radiographs in the diagnosis of pneumoconiosis are studied using an eye tracking experimental study. The role of expertise and the influence of CS information on the performance of readers with different expertise level are also of interest. Experimental subjects ranging from novices & medical students to staff radiologists were presented with 17 double and 16 single lung images, and were asked to give profusion ratings for each lung zone. Eye movements and the time for their diagnosis were also recorded. Kruskal-Wallis test (χ2(6) = 13.38, p = .038), showed that the observer error (average sum of absolute differences) in double lung images differed significantly across the different expertise categories when considering all the participants. Wilcoxon-signed rank test indicated that the observer error was significantly higher for single-lung images (Z = 3.13, p < .001) than for the double-lung images for all the participants. Mann-Whitney test (U = 28, p = .038) showed that the differential error between single and double lung images is significantly higher in doctors [staff & residents] than in non-doctors [others]. Thus, Expertise & CS information plays a significant role in the diagnosis of pneumoconiosis. CS information helps in diagnosing pneumoconiosis by reducing the general tendency of giving less profusion ratings. Training and experience appear to play important roles in learning to use the CS information present in the chest radiographs.

Abstract

Establishment of pairwise keys between sensor nodes in a sensor network is a difficult problem due to resource limitations of sensor nodes as well as vulnerability to physical captures of sensor nodes by the enemy. Public-key cryptosystems are not much suited for most resource-constrained sensor networks. Recently, elliptic curve cryptographic techniques show that public key cryptosystem is also feasible for resource-constrained sensor networks. However, most researchers accept that the symmetric key cryptosystems are viable options for resource-constrained sensor networks. In this paper, we first develop a basic principle to address the key pre-distribution problem in mobile sensor networks. Then, using this developed basic principle, we propose a scheme which takes the advantage of the post-deployment knowledge. Our scheme is a modified version of the key prioritization technique proposed by Liu and Ning. Our improved scheme provides reasonable network connectivity and security. Moreover, the proposed scheme works for any deployment topology.