ADAmol Deshpande

Amol Deshpande

*This is an algorithmically generated author record based on publicly available information.

Amol Deshpande has a total of 67 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Historical Graph Management

    by Udayan Khurana, Amol Deshpande

  • Model-Based Querying in Sensor Networks

    by Amol Deshpande, Carlos Guestrin, Samuel Madden

  • Open Access

    Historical Graph Management

    by Udayan Khurana, Amol Deshpande

  • Big Graph Analytics Platforms

    by Da Yan, Yingyi Bu, Yuanyuan Tian, Amol Deshpande

    Due to the growing need to process large graph and network datasets created by modern applications, recent years have witnessed a surging interest in developing big graph platforms. Tens of such big graph systems have already been developed, but there lacks a systematic categorization and comparison of these systems. This article provides a timely and comprehensive survey of existing big graph systems, and summarizes their key ideas and technical contributions from various aspects. In addition to the popular vertex-centric systems which espouse a think-like-a-vertex paradigm for developing parallel graph applications, this survey also covers other programming and computation models, contrasts those against each other, and provides a vision for the future research on big graph analytics platforms. This survey aims to help readers get a systematic picture of the landscape of recent big graph systems, focusing not just on the systems themselves, but also on the key innovations and design philosophies underlying them.


  • Open Access

    Catching Worms, Trojan Horses and PUPs: Unsupervised Detection of Silent Delivery Campaigns

    by Bum Jun Kwon, Virinchi Srinivas, Amol Deshpande, Tudor Dumitraş

    The growing commoditization of the underground economy has given rise to malware delivery networks, which charge fees for quickly delivering malware or unwanted software to a large number of hosts. To provide this service, a key method is the orchestration of silent delivery campaigns, which involve a group of downloaders that receive remote commands and that deliver their payloads without any user interaction. These campaigns have not been characterized systematically, unlike other aspects of malware delivery networks. Moreover, silent delivery campaigns can evade detection by relying on inconspicuous downloaders on the client side and on disposable domain names on the server side. We describe Beewolf, a system for detecting silent delivery campaigns from Internet-wide records of download events. The key observation behind our system is that the downloaders involved in these campaigns frequently retrieve payloads in lockstep. Beewolf identifies such locksteps in an unsupervised and deterministic manner. By exploiting novel techniques and empirical observations, Beewolf can operate on streaming data. We utilize Beewolf to study silent delivery campaigns at scale, on a data set of 33.3 million download events. This investigation yields novel findings, e.g. malware distributed through compromised software update channels, a substantial overlap between the delivery ecosystems for malware and unwanted software, and several types of business relationships within these ecosystems. Beewolf achieves over 92% true positives and fewer than 5% false positives. Moreover, Beewolf can detect suspicious downloaders a median of 165 days ahead of existing anti-virus products and payload-hosting domains a median of 196 days ahead of existing blacklists.

  • Open Access

    Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

    by Jian Li, Amol Deshpande

    We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of {\em risk-averse} or {\em risk-prone} behaviors, and instead we consider a more general objective which is to maximize the {\em expected utility} of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). Under the assumption that there is a pseudopolynomial time algorithm for the {\em exact} version of the problem (This is true for the problems mentioned above), we can obtain the following approximation results for several important classes of utility functions: (1) If the utility function $\uti$ is continuous, upper-bounded by a constant and $\lim_{x\rightarrow+\infty}\uti(x)=0$, we show that we can obtain a polynomial time approximation algorithm with an {\em additive error} $\epsilon$ for any constant $\epsilon>0$. (2) If the utility function $\uti$ is a concave increasing function, we can obtain a polynomial time approximation scheme (PTAS). (3) If the utility function $\uti$ is increasing and has a bounded derivative, we can obtain a polynomial time approximation scheme. Our results recover or generalize several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.