Seshadhri Comandur and I gave a tutorial titled “Subgraph counting: the methods behind the madness” surveying the state-of-the-art approaches to exact and approximate counting of subgraphs from massive graphs. You can find the material for our tutorial, including slides and bibliography here.
Our work on parallel algorithms for streaming random sampling has been accepted to Europar 2019. This presents parallel methods for a fundamental problem — reservoir sampling from a stream, and its variants, including sliding window. The algorithms are work-efficient and have low-depth (i.e. they are highly parallel). Parallelizing the “seemingly sequential” steps of these algorithms has some twists to it. Please check out our paper ( will post the final version soon) — joint work with Kanat Tangwongsan of Mahidol University, Thailand.
Our paper “Incremental Maintenance of Maximal Cliques in a Dynamic Graph” by Apurba Das, Michael Svendsen, and Srikanta Tirthapura, has been accepted to appear in the VLDB Journal. This work presents efficient algorithms for a fundamental graph mining problem — maintaining the set of maximal cliques within a dynamic graph whose edge set may change with time. The VLDB Journal is a top-tier journal in the area of database systems. Congrats, Apurba and Michael!
Apurba Das completed his PhD defense successfully on Thursday 3/14. His next stop is as a post-doctoral researcher at National University of Singapore. Congrats and best of luck for upcoming adventures.
Our paper “Weighted Reservoir Sampling from Distributed Streams” by Rajesh Jayaram, Gokarna Sharma, Srikanta Tirthapura, and David Woodruff has been accepted to appear at the ACM Symposium on Principles of Database Systems (PODS) 2019. This work provides message-optimal algorithms for maintaining a weighted random sample from distributed and streaming data. PODS is the premier conference in the area of database algorithms.
C. Seshadhri (UC Santa Cruz) and I will be giving a tutorial “Scalable Subgraph Counting: The Methods Behind The Madness” at the Web Conference (formerly WWW) on May 13th, 2019. Goal is to present algorithmic building blocks behind massive-scale subgraph counting.
Our paper titled “Stratified Random Sampling over Streaming and Stored Data”, by Trong Nguyen, Ming-Hung Shih, Divesh Srivastava, Srikanta Tirthapura and Bojian Xu has been accepted to appear in the International Conference on Extending Database Technology (EDBT) 2019. This paper addresses algorithms and lower bounds (inherent difficulties) for computing a stratified random sample on streaming data. Congrats Trong and Danny!
Our paper “Enumerating Top-k Quasi-Cliques” by Seyed-Vahid Sanei-Mehri, Apurba Das, and Srikanta Tirthapura, has been accepted to IEEE Bigdata Conference 2018 as a short paper. On the topic of finding dense subgraphs in a graph, this paper presents hardness results as well as algorithms for the problem of enumerating “quasi-cliques”, a relaxation of cliques in a graph. Congrats Vahid and Apurba!
Our paper titled “Shared-Memory Parallel Maximal Clique Enumeration”, by Apurba Das, Seyed-Vahid Sanei-Mehri, Srikanta Tirthapura, has been accepted to appear in IEEE International Conference on High Performance Computing, Data, and Analytics (HiPC) 2018. This work describes a shared-memory parallel method and implementation for finding maximal cliques (dense subgraphs) within a graph. Congrats, Apurba and Vahid!
Our paper titled “Variance-Reduced Stochastic Gradient Descent on Streaming Data”, by Ellango Jothimurugesan, Ashraf Tahmasbi, Phillip B. Gibbons, and Srikanta Tirthapura has been accepted to appear in the Thirty-second Conference on Neural Information Processing Systems (NIPS) 2018. This presents a method to continuously maintain a machine learning model on streaming data. Congrats, Ashraf!