Abstract

The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Heterogeneous algorithms, often carefully handcrafted, have been designed for several important problems from parallel computing such as sorting, graph algorithms, matrix computations, and the like. A majority of these algorithms follow a work partitioning approach where the input is divided into appropriate sized parts so that individual devices can process the “right-sized” parts of the input. However, arriving at a good work partitioning is usually non-trivial and may crucially depend also on the input instance apart from the heterogeneous algorithm used. An extensive empirical search is not helpful as such an empirical search can potentially offset any gains accrued out of heterogeneous algorithms. Other recently proposed approaches too are in general inadequate. In this paper, we propose a simple and effective technique for work partitioning in the context of heterogeneous algorithms. Our technique is based on randomized sampling and therefore can adapt to both the algorithm used and the input instance. Our technique is generic in its applicability as we will demonstrate in this paper. We validate our technique on three problems: multiplying two unstructured sparse matrices (spmm), multiplying two scale-free sparse matrices, and finding the connected components of a graph (CC). For these problems, we show that using our method, we can find the required threshold that is under 10% away from the best possible thresholds respectively.

Abstract

In this paper, we present a novel N-gram (N> = 1) filtration technique for keyphrase extraction. To filter the sophisticated candidate keyphrases (N-grams), we introduce the combined use of: 1) statistical feature (obtained by using weighted betweenness centrality scores of words, which is generally used to identify the border nodes/edges in community detection techniques); 2) co-location strength (calculated by using nearest neighbour Dbpedia texts). We also introduce the use of N-gram (N> = 1) graph, which reduces the bias effect of lower length N-grams in the ranking process and preserves the semantics of words (phraseness), based upon local context. To capture the theme of the document and to reduce the effect of noisy terms in the ranking process, we apply an information theoretic framework for key-player detection on the proposed N-gram graph. Our experimental results show that the devised system performs better than the current state-of-the-art unsupervised systems and comparable/better than supervised systems.

Abstract

These days' discussion forums provide dependable solutions to the problems related to multiple domains and areas. However, due to the presence of huge amount of less-informative/inappropriate posts, the identification of the appropriate problem-solution pairs has become a challenging task. The emergence of a variety of topics, domains and areas has made the task of manual labelling of the problem solution-post pairs a very costly and time consuming task. To solve these issues, we concentrate on deep semantic and logical relation between terms. For this, we introduce a novel semantic correlation graph to represent the text. The proposed representation helps us in the identification of topical and semantic relation between terms at a fine grain level. Next, we apply the improved version of personalised pagerank using random walk with restarts. The main aim is to improve the rank score of terms having direct or indirect relation with terms in the given question. Finally, we introduce the use of the node overlapping version of GAAC to find the actual span of answer text. Our experimental results show that the devised system performs better than the existing unsupervised systems.

Abstract

Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.

Abstract

This paper extends recent work on vulnerability extrapolation. A surge in vulnerability exploits against old and new softwares, urges the importance of detection of vulnerabilities and possible attacks prior to the attacker. How sophisticated an exploit may be, an underlying prerequisite remains to be the presence of at least one memory corruption bug, serving as entry point for the exploit. Therefore several rigorous software testing techniques are borrowed to detect and eliminate software bugs as early as possible. Code similarity based bug detection is one of such techniques, which, in the parlance of software security, is also termed as vulnerability extrapolation. In this paper, we present a source code similarity based bug identification technique by considering code features that are relevant for security related bugs. Our technique works by enriching (augmenting) abstract syntax trees (ASTs) of functions by considering security relevant properties of the code. We show the effectiveness of the augmented AST based similarity approach over existing methods by evaluating proposed method on real-world applications.

Abstract

In this work we show that given a set S of n points with coordinates on an n × n grid, we can construct data structures for (i) reporting and (ii) counting the maximal points in an axes-parallel query rectangle in sub-logarithmic time. We assume our model of computation to be the word RAM with size of each word being log n bits.

Abstract

Multiplying two sparse matrices, denoted spmm, is a fundamental operation in linear algebra with several applications. Hence, efficient and scalable implementation of spmm has been a topic of immense research. Recent efforts are aimed at implementations on GPUs, multicore architectures, FPGAs, and such emerging computational platforms. Owing to the highly irregular nature of spmm, it is observed that GPUs and CPUs can offer comparable performance. In this paper, we study CPU+GPU heterogeneous algorithms for spmm where the matrices exhibit a scale-free nature. Focusing on such matrices, we propose an algorithm that multiplies two sparse matrices exhibiting scale-free nature on a CPU+GPU heterogeneous platform. Our experiments on a wide variety of real-world matrices from standard datasets show an average of 25% improvement over the best possible algorithm on a CPU+GPU heterogeneous platform. We show that our approach is both architecture-aware, and workload-aware.

Abstract

In extant quantum secret sharing protocols, once the secret is shared in a quantum network (qnet) it cannot be retrieved, even if the dealer wishes that his/her secret no longer be available in the network. For instance, if the dealer is part of two qnets, say Q1 and Q2 and he/she subsequently finds that Q2 is more reliable than Q1, he/she may wish to transfer all her secrets from Q1 to Q2. Known protocols are inadequate to address such a revocation. In this work we address this problem by designing a protocol that enables the source/dealer to bring back the information shared in the network, if desired. Unlike classical revocation, the no-cloning theorem automatically ensures that the secret is no longer shared in the network.

Abstract

In this work, we consider the problem of finding the closest pair (in L 1 metric) of points in an orthogonal query rectangle. Given a set of n static points on a U× U grid, we preprocess these points into a data structure of size O (m f (m) log 2 m) that can be queried in time O ((g (m)+ log log m) log 3 m), for m= O (n log U) and (i) f (m)= O (1) and g (m)= O (log ε m);(ii) f (m)= O (log log m) and g (m)= O (log log m);(iii) f (m)= O (log ε m) and g (m)= O (1). Here ε: 0< ε< 1 is a small but arbitrary constant.

Abstract

We present output sensitive techniques for the generalized reporting versions of the planar range maxima problem and the planar range convex hull problem. Our solutions are in the pointer machine model, for orthogonal range queries on a static point set. We solve the planar range maxima problem for two-sided, three-sided and four-sided queries. We achieve a query time of O(logn + c) using O(n) space for the two-sided case, where n denotes the number of stored points and c the number of colors reported. For the three-sided case, we achieve query time O(log2 n + clogn) using O(n) space while for four-sided queries we answer queries in O(log3 n + clog2 n) using O(nlogn) space. For the planar range convex hull problem, we provide a solution that answers queries in O(log2 n + clogn) time, using O(nlog2 n) space.