Publications | Subhadeep Sarkar

2026

ICDE
RangeReduce: Query-Driven LSM Compactions

Shubham Kaushik, Manos Athanassoulis, and Subhadeep Sarkar

In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2026

Log-structured merge (LSM) trees are widely used in the storage layer of modern ingestion-optimized data stores. The high ingestion throughput, however, comes at the cost of sub-optimal range query (RQ) performance. This is because LSM-trees arrange the data as a hierarchical collection of sorted runs, which implies that every RQ must (i) probe all sorted runs to locate the qualifying entries, (ii) scan and merge the entries from all qualifying runs, (iii) filter out the logically invalidated entries by updates and deletes on the fly, and (iv) return the most recent version of each qualifying key. This leads to high read amplification and significant redundant work in terms of superfluous I/Os to storage and wasted CPU cycles, which is exacerbated in the presence of updates and deletes. Additionally, during compactions, the same data is read and written multiple times, further amplifying the read and write amplification.
In this paper, we introduce RangeReduce, an RQ-optimized LSM-engine that uses RQs as a hint to compact data that is already read into memory as part of the query, and thereby, improves the overall performance of the storage engine. The key intuition is to take advantage of the I/Os and CPU cycles spent on reading and merging data from slow storage during RQs and write the RQ-qualifying data back as part of a single sorted run. Such RQ-driven compactions enable RangeReduce to (i) read less data from fewer sorted runs for subsequent RQs, (ii) reduce overall data movement (reads and writes) due to RQs and compactions, and (iii) improve space amplification, while (iv) significantly reducing compaction debt. Experiments show that RangeReduce offers up to 90% lower compaction debt, 12% less data movement, and 20% lower space amplification while improving average RQ latency by up to 18%.
@inproceedings{Shubham_icde, author = {Kaushik, Shubham and Athanassoulis, Manos and Sarkar, Subhadeep}, title = {RangeReduce: Query-Driven LSM Compactions}, booktitle = {Proceedings of the IEEE International Conference on Data Engineering ({ICDE})}, year = {2026}, publisher = {{IEEE}}, video = {https://www.youtube.com/watch?v=xgJ2g_CLjSQ}, }
DaMoN
ZARC: Re-inventing Zone Allocation for LSMs on ZNS SSD

Farhan S. Chowdhury, Shadman Saqib Eusuf, Subhadeep Sarkar, and Tarikul Islam Papon

In International Workshop on Data Management on New Hardware (DaMoN), 2026

Log-Structured Merge (LSM)-based storage engines offer high write throughput by storing the data on storage as immutable files that are opportunistically reorganized through compactions. Immutability of the files and their frequent garbage collection (GC), however, leads to a major performance bottleneck: high write amplification. This is further exacerbated by the device-level GC when LSM engines run on top of ZNS SSDs. While prior research has shown that compaction-aware file placement at the device level can reduce the overall write amplification, we point out that the proposed solutions are tuned exclusively for specific compaction strategies, SSD configurations, and workloads.
In this early-stage work, we highlight that for LSM engines on ZNS SSDs, performance is governed by a critical four-way trade-off between the compaction file picking policy (LSM-side) and the file placement, GC, and new zone allocation policies (ZNS-side). To this end, we introduce ZARC, a novel framework for Zone Allocation & Reclamation after Compaction that offers a continuum of hy- brid file placement policies to bring the overall write amplification closer to its theoretical lower bound and allows the user to navi- gate this vast design space for a given workload and configuration. ZARC’s hybrid file placement policies optimize performance for each LSM-level independently, leading to level-specific file placement, garbage collection, and zone allocation policies. Preliminary results from experimentation on ZenFS, a RocksDB file system for ZNS SSDs, show that ZARC’s hybrid file placement policies reduce data movement by up to 86% and ZARC-GC improves ZenFS garbage col- lection performance by (i) reclaiming sufficient free space and (ii) maintaining a small reserve of empty zones to prevent GC-induced stalls, and (iii) reducing GC-induced data movement by 8.6%.
@inproceedings{Farhan_damon, author = {Chowdhury, Farhan S. and Eusuf, Shadman Saqib and Sarkar, Subhadeep and Papon, Tarikul Islam}, title = {{ZARC}: Re-inventing Zone Allocation for LSMs on ZNS SSD}, booktitle = {International Workshop on Data Management on New Hardware ({DaMoN})}, year = {2026}, }

2025

TPCTC
Tectonic: Bridging Synthetic and Real-World Workloads for Key-Value Benchmarking

Alexander H. Ott, Shubham Kaushik, Boao Chen, and Subhadeep Sarkar

In Performance Evaluation and Benchmarking TPC Technology Conference (TPCTC), 2025

1

Key-value stores are the backbone of many modern SQLand NoSQL-based data systems, serving a variety of real-world applications. Despite their widespread adoption, existing key-value benchmarks fall short across multiple dimensions when accurately replicating complex and dynamic real-world workloads. For instance, state-of-the-art key-value benchmarks, such as YCSB, KVBench, and db_bench, are unable to (i) emulate dynamic workloads where the workload composition and distribution changes arbitrarily over time; (ii) generate composite keys with different prefix distributions; and (iii) generate workloads with varied degrees of data sortedness. These limitations result in inaccurate performance evaluations and limit the ability to understand how a commercial key-value store performs under dynamically shifting workloads.
In this paper, we introduce Tectonic, a highly configurable and resource-efficient Rust-based key-value workload generator designed to model the temporal, structural, and dynamic properties of real-world workloads. Tectonic offers (i) fine-grained control over data access patterns for inserts, updates, merges, point and range queries, and point and range deletes; (ii) configurable composite key generation/selection strategies; (iii) dynamic workload generation where the workload properties change over time; and (iv) generation of workloads with user-specified data sortedness. Tectonic does so (v) at a 2&times higher throughput than the state-of-the-art, (vi) while recording up to 84% lower main memory footprint. By bridging the gap between synthetic and production workloads, Tectonic enables in-depth analysis of key-value data systems under conditions that better reflect the demands of real-world applications. We benchmark Tectonic’s performance against YCSB and KVBench in terms of latency, resource utilization, and ability to emulate production workloads. The code for Tectonic is available at: https://github.com/SSDBrandeis/tectonic.
@inproceedings{DBLP:conf/tpctc/OttKCS25, author = {Ott, Alexander H. and Kaushik, Shubham and Chen, Boao and Sarkar, Subhadeep}, editor = {Nambiar, Raghunath and Poess, Meikel}, title = {Tectonic: Bridging Synthetic and Real-World Workloads for Key-Value Benchmarking}, booktitle = {Performance Evaluation and Benchmarking {TPC} Technology Conference ({TPCTC})}, series = {Lecture Notes in Computer Science}, volume = {16261}, pages = {69--88}, year = {2025}, publisher = {Springer}, isbn = {978-3-032-18070-4}, doi = {doi.org/10.1007/978-3-032-18070-4_5}, url = {https://doi.org/10.1007/978-3-032-18070-4_5}, }
EDBT
QuIT your B⁺-tree for the Quick Insertion Tree

Aneesh Raman, Konstantinos Karatsenidis, Shaolin Xie, Matthaios Olma, Subhadeep Sarkar, and Manos Athanassoulis

In Proceedings of the International Conference on Extending Database Technology (EDBT), 2025

3

Search trees, like B⁺-trees, are often used as index structures in data systems to improve query performance at the cost of index construction and maintenance. For state-of-the-art B⁺-tree designs used in commercial data systems, this cost is negligible if the data arrives as fully sorted on the index attribute. Further, production systems employ a fast-path ingestion technique for B⁺-trees that directly appends the incoming entries to the tail leaf if the data is fully sorted, drastically reducing the index construction cost. However, this is only effective if the incoming data arrives fully sorted or with an extremely small number of out-of-order entries. In addition, the state-of-the-art sortedness-aware design (SWARE) navigates a tradeoff between reads and writes by buffering incoming data to absorb near-sortedness, which comes at the cost of slower query performance and increased overall design complexity.
To address these challenges, we present Quick Insertion Tree (QuIT), a sortedness-aware indexing data structure that improves ingestion performance with minimal design complexity and no read overhead. QuIT maintains in memory a pointer to the predicted ordered-leaf (pole) that provides a sortedness-aware fast-path optimization, and facilitates faster index ingestion. The key benefit comes from accurately predicting pole throughout data ingestion. Further, QuIT achieves high memory utilization by maintaining tightly packed leaf nodes when the ingested data arrives as near-sorted. This, in turn, helps improve performance during range lookups. Overall, we demonstrate that QuIT outperforms B⁺-tree (SWARE) by up to 3× (2×) for ingestion, while maintaining the same point lookup performance (up to 1.23× faster). QuIT also accesses up to 2× fewer leaf nodes than the B⁺-tree during range lookups.
@inproceedings{DBLP:conf/edbt/RamanKXOSA25, author = {Raman, Aneesh and Karatsenidis, Konstantinos and Xie, Shaolin and Olma, Matthaios and Sarkar, Subhadeep and Athanassoulis, Manos}, editor = {Simitsis, Alkis and Kemme, Bettina and Queralt, Anna and Romero, Oscar and Jovanovic, Petar}, title = {QuIT your B<sup>+</sup>-tree for the Quick Insertion Tree}, booktitle = {Proceedings of the International Conference on Extending Database Technology ({EDBT})}, pages = {451--463}, publisher = {OpenProceedings.org}, year = {2025}, url = {https://doi.org/10.48786/edbt.2025.36}, doi = {10.48786/EDBT.2025.36}, timestamp = {Sat, 06 Sep 2025 20:31:17 +0200}, biburl = {https://dblp.org/rec/conf/edbt/RamanKXOSA25.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2024

DBTest
Anatomy of the LSM Memory Buffer: Insights & Implications

Shubham Kaushik and Subhadeep Sarkar

In Proceedings of the International Workshop on Testing Database Systems (DBTest), 2024

6

Log-structured merge (LSM) tree is an ingestion-optimized data structure that is widely used in modern NoSQL key-value stores. To support high throughput for writes, LSM-trees maintain an in-memory buffer that absorbs the incoming entries before writing them to slower secondary storage. We point out that the choice of the data structure and implementation of the memory buffer has a significant impact on the overall performance of LSM-based storage engines. In fact, even with the same implementation of the buffer, the performance of a storage engine can vary by up to several orders of magnitude if there is a shift in the input workload.
In this paper, we benchmark the performance of LSM-based storage engines with different memory buffer implementations and under different workload characteristics. We experiment with four buffer implementations, namely, (i) vector, (ii) skip-list, (iii) hash skip-list, and (iv) hash linked-list, and for each implementation, we vary any design choices (such as bucket count in a hash skip-list and prefix length in a hash linked-list). We present a comprehensive performance benchmark for each buffer configuration, and highlight how the relative performance of the different buffer implementations varies with a shift in input workload. Lastly, we present a guideline for selecting the appropriate buffer implementation for a given workload and performance goal.
@inproceedings{DBLP:conf/dbtest-ws/KaushikS24, author = {Kaushik, Shubham and Sarkar, Subhadeep}, title = {Anatomy of the {LSM} Memory Buffer: Insights {\&} Implications}, booktitle = {Proceedings of the International Workshop on Testing Database Systems ({DBT}est)}, pages = {23--29}, publisher = {{ACM}}, year = {2024}, url = {https://doi.org/10.1145/3662165.3662766}, doi = {10.1145/3662165.3662766}, timestamp = {Tue, 08 Apr 2025 11:34:11 +0200}, biburl = {https://dblp.org/rec/conf/dbtest-ws/KaushikS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
DBTest
KVBench: A Key-Value Benchmarking Suite

Zichen Zhu, Arpita Saha, Manos Athanassoulis, and Subhadeep Sarkar

In Proceedings of the International Workshop on Testing Database Systems (DBTest), 2024

12

Key-value stores are at the core of several modern NoSQL-based data systems, and thus, a comprehensive benchmark tool is of paramount importance in evaluating their performance under different workloads. Prior research reveals that real-world workloads have a diverse range of characteristics, such as the fraction of point queries that target non-existing keys, point and range deletes, as well as, different distributions for queries and updates, all of which have very different performance implications. State-of-the-art key-value workload generators, such as YCSB and db_bench, fail to generate workloads that emulate these practical workloads, limiting the dimensions on which we can benchmark the systems’ performance.
In this paper, we present KVBench, a novel synthetic workload generator that fills the gap between classical key-value workload generators and more complex real-life workloads. KVBench supports a wide range of operations, including point queries, range queries, inserts, updates, deletes, range deletes, and among these options, inserts, queries, and updates can be customized by different distributions. Compared to state-of-the-art key-value workload generators, KVBench offers a richer array of knobs, including the proportion of empty point queries, customized distributions for updates and queries, and range deletes with specific selectivity, constituting a significantly flexible framework that can better emulate real-world workloads.
@inproceedings{DBLP:conf/dbtest-ws/ZhuSAS24, author = {Zhu, Zichen and Saha, Arpita and Athanassoulis, Manos and Sarkar, Subhadeep}, title = {KVBench: {A} Key-Value Benchmarking Suite}, booktitle = {Proceedings of the International Workshop on Testing Database Systems ({DBT}est)}, pages = {9--15}, year = {2024}, publisher = {{ACM}}, doi = {10.1145/3662165.3662765}, url = {https://doi.org/10.1145/3662165.3662765}, timestamp = {Fri, 31 May 2024 21:05:30 +0200}, biburl = {https://dblp.org/rec/conf/dbtest-ws/ZhuSAS24.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2023

TODS
Enabling Timely and Persistent Deletion in LSM-Engines

Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis

ACM Transactions on Database Systems, 2023

9

Data-intensive applications have fueled the evolution of log-structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as second-class citizens. A delete operation inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM-engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion.
Further, LSM-engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written, leading to undesired latency spikes and increasing the overall operational cost of a database. Efficient and persistent deletion is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on data deletion, and (iii) en masse cloud deployment of data systems. Further, we document that LSM-based key-value engines perform suboptimally in presence of deletes in a workload. Tombstone-driven logical deletes, by design, are unable to purge the deleted entries in a timely manner, and retaining the invalidated entries perpetually affects the overall performance of LSM-engines in terms of space amplification, write amplification, and read performance. Moreover, the potentially unbounded latency for persistent deletes brings in critical privacy concerns in light of the data privacy protection regulations, such as the right to be forgotten in EU’s GDPR, the right to delete in California’s CCPA and CPRA, and deletion right in Virginia’s VCDPA. Toward this, we introduce the delete design space for LSM-trees and highlight the performance implications of the different classes of delete operations.
To address these challenges, in this article, we build a new key-value storage engine, Lethe+, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe+ supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17×-1.4×) and lower space amplification (2.1×-9.8×), with a modest increase in write amplification (between 4% and 25%) that can be further amortized to less than 1%. In addition, Lethe+ supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance or employing a costly full tree merge.
@article{DBLP:journals/tods/SarkarPSZA23, author = {Sarkar, Subhadeep and Papon, Tarikul Islam and Staratzis, Dimitris and Zhu, Zichen and Athanassoulis, Manos}, title = {Enabling Timely and Persistent Deletion in LSM-Engines}, journal = {ACM Transactions on Database Systems}, volume = {48}, number = {3}, pages = {8:1--8:40}, year = {2023}, doi = {10.1145/3599724}, url = {https://doi.org/10.1145/3599724}, timestamp = {Fri, 27 Oct 2023 20:40:00 +0200}, biburl = {https://dblp.org/rec/journals/tods/SarkarPSZA23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
SIGMOD
Acheron: Persisting Tombstones in LSM Engines

Zichen Zhu, Subhadeep Sarkar, and Manos Athanassoulis

In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2023

6

Modern NoSQL storage engines frequently employ log-structured merge (LSM) trees as their core data structures because they offer high ingestion rates and low latency for query processing. Client writes are captured in memory first and are gradually merged on disk in a level-wise manner. While this out-of-place paradigm sustains fast ingestion rates, it implements delete operations via inserting tombstones which logically invalidate older entries. Thus, obsolete data cannot be removed instantly and may be retained for an arbitrarily long time. Therefore, out-of-place deletion in LSM trees may, on the one hand, violate data privacy regulations (e.g., the right to be forgotten in EU’s GDPR, right to delete in California’s CCPA and CPRA), and on the other hand, it hurts performance.
In this paper, we develop Acheron, which demonstrates the performance implications of out-of-place deletes and how our method achieves timely persistent deletes. We integrate both prior state-of-the-art compaction policies and our recently presented method, FADE, into Acheron and visualize the life cycle of tombstones in LSM trees. Using the Acheron visualization, users can observe that the state of the art does not provide guarantees on when obsolete entries can be physically removed and also observe that FADE can achieve timely persistent deletes without full tree compaction. Users can further customize the workload, LSM tuning knobs, and disk parameters to investigate their impact on tombstones and performance. This demonstration provides key insights into the impact of tombstones on LSM-interested researchers and practitioners.
@inproceedings{DBLP:conf/sigmod/ZhuSA23, author = {Zhu, Zichen and Sarkar, Subhadeep and Athanassoulis, Manos}, editor = {Das, Sudipto and Pandis, Ippokratis and Candan, K. Sel{\c{c}}uk and Amer{-}Yahia, Sihem}, title = {Acheron: Persisting Tombstones in {LSM} Engines}, booktitle = {Proceedings of the {ACM SIGMOD} International Conference on Management of Data}, pages = {131--134}, publisher = {{ACM}}, year = {2023}, url = {https://doi.org/10.1145/3555041.3589719}, doi = {10.1145/3555041.3589719}, timestamp = {Thu, 15 Jun 2023 21:56:55 +0200}, biburl = {https://dblp.org/rec/conf/sigmod/ZhuSA23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
ICDE
The LSM Design Space and its Read Optimizations

Subhadeep Sarkar, Niv Dayan, and Manos Athanassoulis

In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2023

27

Log-structured merge (LSM) trees have emerged as one of the most commonly used storage-based data structures in modern data systems as they offer high throughput for writes and good utilization of storage space. However, LSM-trees were not originally designed to facilitate efficient reads. Thus, state-of-the-art LSM engines employ numerous optimization techniques to make reads efficient. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with the various optimization techniques and hybrid designs adopted by LSM engines to accelerate reads.
Toward this, we first discuss the basic LSM operations and their access patterns. We then discuss techniques and designs that optimize point and range lookups in LSM-trees: (i) index and (ii) filter data structures, (iii) caching, and (iv) read- friendly data layouts. Next, we present the performance tradeoff between writes and reads, outlining the rich design space of the LSM paradigm and how one can navigate it to improve query performance. We conclude by discussing practical problems and open research challenges. This will be a 1.5-hour tutorial.
@inproceedings{DBLP:conf/icde/SarkarDA23, author = {Sarkar, Subhadeep and Dayan, Niv and Athanassoulis, Manos}, title = {The {LSM} Design Space and its Read Optimizations}, booktitle = {Proceedings of the IEEE International Conference on Data Engineering ({ICDE})}, pages = {3578--3584}, publisher = {{IEEE}}, year = {2023}, url = {https://doi.org/10.1109/ICDE55515.2023.00273}, doi = {10.1109/ICDE55515.2023.00273}, timestamp = {Sun, 02 Nov 2025 21:27:15 +0100}, biburl = {https://dblp.org/rec/conf/icde/SarkarDA23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
ICDE
Indexing for Near-Sorted Data

Aneesh Raman, Subhadeep Sarkar, Matthaios Olma, and Manos Athanassoulis

In Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2023

10

Indexing in modern data systems facilitates efficient query processing when the selection predicate is on an indexed key. As new data is ingested, indexes are gradually populated with incoming entries. In that respect, indexing can be perceived as the process of adding structure to incoming, otherwise unsorted data. Adding structure, however, comes at a cost. Instead of simply appending the incoming entries, we insert them into the index. If the ingestion order matches the indexed attribute order, the ingestion cost is entirely redundant and can be avoided altogether (e.g., via bulk loading in a B⁺-tree). However, classical tree index designs do not benefit when incoming data comes with an implicit ordering that is close to being sorted, but not fully sorted.
In this paper, we study how indexes can exploit near-sortedness. Particularly, we identify sortedness as a resource that can accelerate index ingestion. We propose a new sortedness-aware (SWARE) design paradigm that combines opportunistic bulk loading, index appends, variable node fill and split factors, and an intelligent buffering scheme, to optimize ingestion and read queries in a tree index in the presence of near-sortedness. We apply SWARE to two state-of-the-art search trees (B⁺-tree and B^ε-tree), and we demonstrate that their Sortedness-Aware counterparts (SA B⁺-tree and SA B^ε-tree) outperform their respective baselines by up to 8.8× (SA B⁺-tree) and 7.8× (SA B^ε-tree) for a write-heavy workload in the presence of data sortedness, while offering competitive read performance, leading to overall benefits between 1.3×-5× for mixed read/write workloads with near-sorted data. Overall, we highlight that SWARE can be applied to other tree-like data structures to accelerate index ingestion and improve their performance in the presence of data sortedness.
@inproceedings{DBLP:conf/icde/RamanSOA23, author = {Raman, Aneesh and Sarkar, Subhadeep and Olma, Matthaios and Athanassoulis, Manos}, title = {Indexing for Near-Sorted Data}, booktitle = {Proceedings of the IEEE International Conference on Data Engineering ({ICDE})}, pages = {1475--1488}, publisher = {{IEEE}}, year = {2023}, url = {https://doi.org/10.1109/ICDE55515.2023.00117}, doi = {10.1109/ICDE55515.2023.00117}, timestamp = {Sun, 02 Nov 2025 21:27:15 +0100}, biburl = {https://dblp.org/rec/conf/icde/RamanSOA23.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2022

DEBull
Building Deletion-Compliant Data Systems

Manos Athanassoulis, Subhadeep Sarkar, Tarikul Islam Papon, Zichen Zhu, and Dimitris Staratzis

IEEE Data Engineering Bulletin, 2022

23

Most modern data systems have been designed with two goals in mind – fast ingestion and low-latency query processing. The first goal has led to the development of a plethora of write-optimized data stores that employ the out-of-place paradigm. Due to their write-optimized design, out-of-place data systems perform deletes logically via invalidation, and retain the invalid data for arbitrarily long. However, due to the recent enactment of new data privacy regulations, the requirement of timely deletion of user data has become central. The right to be forgotten (in EU’s GDPR), right to delete (in California’s CCPA and CPRA), or deletion right (in Virginia’s VCDPA) mandates service providers to persistently delete a user’s data within a pre-set time duration. Logical deletion in out-of-place data systems, however, does not offer guarantees for timely and persistent deletion, and attempting to enforce it using existing tools leads to poor performance and increased operational costs.
In this paper, we present a new framework for building deletion-compliant data systems from a holistic perspective. We analyze the new regulations and the requirements derived from the new policies, and we propose changes in the application and the system layer of data management. We outline the new types of deletion requests that need to be supported, the query language modifications needed to be able to request for timely persistent data deletion, and the system-level changes needed to realize timely and persistent deletes. The proposed framework for deletion compliance lays the groundwork for a new class of data systems that can offer system-level guarantees for user data privacy. We present recent results spanning all layers of the framework: the requirements and the application layer target any database system, while the system layer discussion is geared towards out-of-place systems. Finally, we conclude with a discussion on the next steps and the open challenges on building deletion-compliant data systems.
@article{DBLP:journals/debu/AthanassoulisSP22, author = {Athanassoulis, Manos and Sarkar, Subhadeep and Papon, Tarikul Islam and Zhu, Zichen and Staratzis, Dimitris}, title = {Building Deletion-Compliant Data Systems}, journal = {{IEEE} Data Engineering Bulletin}, volume = {45}, number = {1}, pages = {21--36}, year = {2022}, timestamp = {Sun, 06 Oct 2024 21:26:11 +0200}, biburl = {https://dblp.org/rec/journals/debu/AthanassoulisSP22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
EDBT
Query Language Support for Timely Data Deletion

Subhadeep Sarkar and Manos Athanassoulis

In Proceedings of the International Conference on Extending Database Technology (EDBT), 2022

20

A key driver of modern data systems is the requirement for fast ingestion while ensuring low-latency query processing. This has led to the birth of write-optimized data stores that realize ingestion (inserts, updates, and deletes) in an out-of-place manner. Deletes in such out-of-place data stores are performed logically via invalidation while retaining the invalidated data for arbitrarily long. At the same time, with new policy changes, such as the introduction of the right to be forgotten (in EU’s GDPR), the right to delete (in California’s CCPA and CPRA), and the deletion right (in Virginia’s VCDPA), the importance of timely and persistent deletion of user data has become critical.
In this paper, we point out that state-of-the-art query languages lack the necessary support to express a user’s preferences for data retention and deletion. Toward this, we first identify two classes of deletes: (i) retention-based deletion and (ii) on-demand deletion, that need to be supported for regulation compliance. Next, we present the challenges in transforming these user deletion requirements into application-level specifications. For this, we propose query language extensions that can express both on-demand and timely persistent deletion of user data. Finally, we discuss how the application and system level modifications work hand-in-hand under the privacy regulations and act as stepping stones toward designing deletion-compliant data systems.
@inproceedings{DBLP:conf/edbt/SarkarA22, author = {Sarkar, Subhadeep and Athanassoulis, Manos}, editor = {Stoyanovich, Julia and Teubner, Jens and Guagliardo, Paolo and Nikolic, Milos and Pieris, Andreas and M{\"{u}}hlig, Jan and {\"{O}}zcan, Fatma and Schelter, Sebastian and Jagadish, H. V. and Zhang, Meihui}, title = {Query Language Support for Timely Data Deletion}, booktitle = {Proceedings of the International Conference on Extending Database Technology ({EDBT})}, pages = {2:429--2:434}, publisher = {OpenProceedings.org}, year = {2022}, url = {https://doi.org/10.48786/edbt.2022.35}, doi = {10.48786/EDBT.2022.35}, timestamp = {Tue, 04 Nov 2025 17:13:50 +0100}, biburl = {https://dblp.org/rec/conf/edbt/SarkarA22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, video = {https://www.youtube.com/watch?v=aUZ_SCPOtWo}, }
SIGMOD
Compactionary: A Dictionary for LSM Compactions

Subhadeep Sarkar, Kaijie Chen, Zichen Zhu, and Manos Athanassoulis

In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022

28

Log-structured merge (LSM) trees are widely used as the storage layer of production NoSQL data stores, as they offer efficient ingestion performance. To enable competitive read performance and reduce space amplification, LSM-trees periodically re-organize data layout on disk iteratively, through compactions. Compactions are at the heart of every LSM-based storage engine, fundamentally influencing their performance in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. However, the process of compaction in LSM-engines is often treated as a black-box that is rarely exposed as a tuning knob. In this paper, we demonstrate Compactionary, a dictionary for LSM compactions, outlining the implications of compactions on performance, and how different LSM tunings and workloads influence compactions.
Compactionary breaks down the LSM compaction black-box, expressing compactions as an ensemble of four first-order design choices: (i) when to compact, (ii) how to organize the data after compaction, (iii) how much data to compact, and (iv) which data to compact. We configure Compactionary to demonstrate the operational flow of a family of state-of-the-art LSM compaction strategies and how each strategy influences the performance of the storage engine. The participants can (i) customize the workload, (ii) configure the LSM tuning, and (iii) switch between advanced compaction options, to understand individually the impacts of the different factors on performance. Further, to engage the interested participants, we extend the demonstration by allowing the participants (i) to create custom hybrid compaction strategies, as well as (ii) to configure the settings separately for each strategy in an individual analysis phase. The demo is available at https://disc-projects.bu.edu/compactionary/#interactiveDemo.
@inproceedings{DBLP:conf/sigmod/SarkarCZA22, author = {Sarkar, Subhadeep and Chen, Kaijie and Zhu, Zichen and Athanassoulis, Manos}, editor = {Ives, Zachary G. and Bonifati, Angela and Abbadi, Amr El}, title = {Compactionary: {A} Dictionary for {LSM} Compactions}, booktitle = {Proceedings of the {ACM SIGMOD} International Conference on Management of Data}, pages = {2429--2432}, publisher = {{ACM}}, year = {2022}, url = {https://doi.org/10.1145/3514221.3520169}, doi = {10.1145/3514221.3520169}, timestamp = {Sun, 02 Nov 2025 21:27:21 +0100}, biburl = {https://dblp.org/rec/conf/sigmod/SarkarCZA22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
SIGMOD
Dissecting, Designing, and Optimizing LSM-based Data Stores

Subhadeep Sarkar and Manos Athanassoulis

In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2022

38

Log-structured merge (LSM) trees have emerged as one of the most commonly used disk-based data structures in modern data systems. LSM-trees employ out-of-place ingestion to support high throughput for writes, while their immutable file structure allows for good utilization of disk space. Thus, the log-structured paradigm has been widely adopted in state-of-the-art NoSQL, relational, spatial, and time-series data systems. However, despite their popularity, there is a lack of pedagogical textbook-like material on LSM designs. The goal of this tutorial is to present the fundamental principles of the LSM paradigm along with a digest of optimizations and new designs proposed in recent research and adopted by modern LSM engines. This will serve as introductory material for non-experts, and as a roadmap to cutting-edge LSM results for the LSM-aware researchers and practitioners.
Toward this, we first discuss in detail the basic operations (inserts, updates, deletes, point and range queries), their access patterns and their paths through the LSM data structure. We then dive into the details of recent research on optimizing each of those operations. We first discuss techniques and designs that optimize data ingestion, and then, we discuss new data structures that optimize read queries. Finally, we present the rich design space of the log-structured paradigm and outline how to navigate it and tune LSM-based systems. We conclude with a discussion on open challenges on LSM systems. This will be a 1.5-hour tutorial.
@inproceedings{DBLP:conf/sigmod/SarkarA22, author = {Sarkar, Subhadeep and Athanassoulis, Manos}, editor = {Ives, Zachary G. and Bonifati, Angela and Abbadi, Amr El}, title = {Dissecting, Designing, and Optimizing LSM-based Data Stores}, booktitle = {Proceedings of the {ACM SIGMOD} International Conference on Management of Data}, pages = {2489--2497}, publisher = {{ACM}}, year = {2022}, url = {https://doi.org/10.1145/3514221.3522563}, doi = {10.1145/3514221.3522563}, timestamp = {Sun, 02 Nov 2025 21:27:21 +0100}, biburl = {https://dblp.org/rec/conf/sigmod/SarkarA22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, video = {https://www.youtube.com/watch?v=Al3krW4Sh3Q}, }
TPCTC
BoDS: A Benchmark on Data Sortedness

Aneesh Raman, Konstantinos Karatsenidis, Subhadeep Sarkar, Matthaios Olma, and Manos Athanassoulis

In Performance Evaluation and Benchmarking TPC Technology Conference (TPCTC), 2022

8

Indexes in data systems accelerate data access by adding structure to otherwise unstructured data at the cost of index construction and maintenance. Data systems, and particularly, the underlying indexing data structures are designed to offer favorable ingestion (and query) performance for the two extremes of data sortedness, i.e., unsorted data (often assumed to follow a uniform random distribution) or fullysorted data. However, in practice, data may arrive with an intermediate degree of pre-sortedness. In such cases, where data arrives nearly (but not necessarily fully) sorted, the intuition is that the indexing cost should be lower than when ingesting unsorted data. Such sortedness-aware index designs lack from the literature. In fact, there is a need for a framework to explore how index designs may be able to exploit pre-existing sortedness during data ingestion to amortize the index construction cost.
In this paper, we present Benchmark on Data Sortedness, BoDS for short, that highlights the performance of data systems in terms of index construction and navigation costs when operating on data ingested with variable sortedness. To quantify data sortedness, we use the stateof-the-art (K,L)-sortedness metric. Specifically, BoDS benchmarks the indexing performance of a data system as we vary the two fundamental components of the metric: (i) K, that measures how many elements are out-of-order in a data collection; and (ii) L, that measures by how much the out-of-order entries are displaced from their respective in-order positions; as well as (iii) the distribution of L. We present in detail the benchmark, and we run it on PostgreSQL, a popular, production-grade relational database system. Unsurprisingly, we observe that PostgreSQL cannot exploit data sortedness; however, through our experiments we show the headroom for improvement, and we lay the groundwork for experimentation with sortedness-aware index designs. The code for BoDS is available at: https://github.com/BU-DiSC/bods.
@inproceedings{DBLP:conf/tpctc/RamanKSOA22, author = {Raman, Aneesh and Karatsenidis, Konstantinos and Sarkar, Subhadeep and Olma, Matthaios and Athanassoulis, Manos}, editor = {Nambiar, Raghunath and Poess, Meikel}, title = {BoDS: {A} Benchmark on Data Sortedness}, booktitle = {Performance Evaluation and Benchmarking {TPC} Technology Conference ({TPCTC})}, series = {Lecture Notes in Computer Science}, pages = {17--32}, publisher = {Springer}, year = {2022}, url = {https://doi.org/10.1007/978-3-031-29576-8\_2}, doi = {10.1007/978-3-031-29576-8\_2}, timestamp = {Thu, 01 May 2025 20:26:39 +0200}, biburl = {https://dblp.org/rec/conf/tpctc/RamanKSOA22.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
HPTS
Toward Building Deletion Compliant Data Systems

Subhadeep Sarkar

In International Workshop on High Performance Transaction Systems (HPTS), 2022

Modern data systems are designed around the silent underlying assumption of perpetual data retention. Systems are designed to offer high performance for data ingestion and queries, while deletion of data is realized by simply logically invalidating the target entries (instead of modifying them in place). This has severe implications on the privacy front, especially, in light of the newly enforced privacy regulations which are aimed toward enabling the users to express their preferences about the deletion of their data. In this paper, we present our vision of enabling privacy-through-deletion as a design element in modern data systems empowering them with the ability to ensure timely and persistent deletion of data, and we envision doing so without hurting performance or increasing operational cost.
@inproceedings{Sarkar_HPTS22, author = {Sarkar, Subhadeep}, title = {Toward Building Deletion Compliant Data Systems}, booktitle = {International Workshop on High Performance Transaction Systems ({HPTS})}, year = {2022}, month = oct, }

2021

VLDB
Constructing and Analyzing the LSM Compaction Design Space

Subhadeep Sarkar, Dimitris Staratzis, Zichen Zhu, and Manos Athanassoulis

Proceedings of the VLDB Endowment, 2021

90

Log-structured merge (LSM) trees offer efficient ingestion by appending incoming data, and thus, are widely used as the storage layer of production NoSQL data stores. To enable competitive read performance, LSM-trees periodically re-organize data to form a tree with levels of exponentially increasing capacity, through iterative compactions. Compactions fundamentally influence the performance of an LSM-engine in terms of write amplification, write throughput, point and range lookup performance, space amplification, and delete performance. Hence, choosing the appropriate compaction strategy is crucial and, at the same time, hard as the LSM compaction design space is vast, largely unexplored, and has not been formally defined in the literature. As a result, most LSM-based engines use a fixed compaction strategy, typically hand-picked by an engineer, which decides how and when to compact data.
In this paper, we present the design space of LSM-compactions, and evaluate state-of-the-art compaction strategies with respect to key performance metrics. Toward this goal, our first contribution is to introduce a set of four design primitives that can formally define any compaction strategy: (i) the compaction trigger, (ii) the data layout, (iii) the compaction granularity, and (iv) the data movement policy. Together, these primitives can synthesize both existing and completely new compaction strategies. Our second contribution is to experimentally analyze 10 compaction strategies. We present 12 observations and 7 high-level takeaway messages, which show how LSM systems can navigate the compaction design space.
@article{DBLP:journals/pvldb/SarkarSZA21, author = {Sarkar, Subhadeep and Staratzis, Dimitris and Zhu, Zichen and Athanassoulis, Manos}, title = {Constructing and Analyzing the {LSM} Compaction Design Space}, journal = {Proceedings of the {VLDB} Endowment}, volume = {14}, number = {11}, pages = {2216--2229}, year = {2021}, doi = {10.14778/3476249.3476274}, timestamp = {Sat, 30 Sep 2023 10:24:10 +0200}, biburl = {https://dblp.org/rec/journals/pvldb/SarkarSZA21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, video = {https://www.youtube.com/watch?v=Ok1_ADEclFc}, }
Systems J.
i-MAC: In-Body Sensor MAC in Wireless Body Area Networks for Healthcare IoT

Sudip Misra, Pradyumna Kumar Bishoyi, and Subhadeep Sarkar

IEEE Systems Journal, 2021

The application of Internet-of-Things (IoT) technology in modern healthcare environment has given rise to a new paradigm known as healthcare IoT. The wireless body area network (WBAN) is one of the basic building blocks of IoT-based healthcare system, comprising many wearable (on-body) and implant (in-body) sensors placed in or around patient body connected to a hub for physiological signal monitoring. In in-body sensor-based WBAN, guaranteeing quality-of-service and prolonging network lifetime are major impediments due to the sensor location and limited battery capacity. In this article, we propose a novel energy-efficient medium access control (MAC) protocol for IEEE 802.15.6 standard complaint in-body sensor-based WBAN. Typically, the in-body sensor-based WBAN communication is hub-initiated; however, in case of an emergency event, the in-body sensor node transmits an emergency frame arbitrarily without sensing the channel. This inadvertent in-body sensor-initiated transmission has a very high probability of collision with the ongoing hub-initiated transmission, and/or another in-body sensor-initiated emergency frame transmission. This results in emergency frame retransmission and consequently affects the node’s energy consumption and lifetime. To alleviate this issue, we propose a modified superframe structure, in which separate access phases are introduced for the emergency event and regular event. In case of an emergency event, a novel emergency event handling scheme and a ranking and priority assignment protocol is proposed to detect and address the critical event of in-body sensors. To minimize the collision, a scheduled access mechanism is proposed according to the criticality of the node. Performance analysis of the proposed in-body sensor MAC is done in terms of latency and overall power consumption, in case of both emergency and regular events.
@article{DBLP:journals/sj/MisraBS21, author = {Misra, Sudip and Bishoyi, Pradyumna Kumar and Sarkar, Subhadeep}, title = {i-MAC: In-Body Sensor {MAC} in Wireless Body Area Networks for Healthcare IoT}, journal = {{IEEE} Systems Journal}, volume = {15}, number = {3}, pages = {4413--4420}, year = {2021}, url = {https://doi.org/10.1109/JSYST.2020.3020306}, doi = {10.1109/JSYST.2020.3020306}, timestamp = {Sat, 30 Sep 2023 10:26:46 +0200}, biburl = {https://dblp.org/rec/journals/sj/MisraBS21.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2020

SIGMOD
Lethe: A Tunable Delete-Aware LSM Engine

Subhadeep Sarkar, Tarikul Islam Papon, Dimitris Staratzis, and Manos Athanassoulis

In Proceedings of the ACM SIGMOD International Conference on Management of Data, 2020

104

Data-intensive applications fueled the evolution of log structured merge (LSM) based key-value engines that employ the out-of-place paradigm to support high ingestion rates with low read/write interference. These benefits, however, come at the cost of treating deletes as a second-class citizen. A delete inserts a tombstone that invalidates older instances of the deleted key. State-of-the-art LSM engines do not provide guarantees as to how fast a tombstone will propagate to persist the deletion. Further, LSM engines only support deletion on the sort key. To delete on another attribute (e.g., timestamp), the entire tree is read and re-written. We highlight that fast persistent deletion without affecting read performance is key to support: (i) streaming systems operating on a window of data, (ii) privacy with latency guarantees on the right-to-be-forgotten, and (iii) en masse cloud deployment of data systems that makes storage a precious resource.
To address these challenges, in this paper, we build a new key-value storage engine, Lethe, that uses a very small amount of additional metadata, a set of new delete-aware compaction policies, and a new physical data layout that weaves the sort and the delete key order. We show that Lethe supports any user-defined threshold for the delete persistence latency offering higher read throughput (1.17-1.4x) and lower space amplification (2.1-9.8x), with a modest increase in write amplification (between 4% and 25%). In addition, Lethe supports efficient range deletes on a secondary delete key by dropping entire data pages without sacrificing read performance nor employing a costly full tree merge.
@inproceedings{DBLP:conf/sigmod/SarkarPSA20, author = {Sarkar, Subhadeep and Papon, Tarikul Islam and Staratzis, Dimitris and Athanassoulis, Manos}, editor = {Maier, David and Pottinger, Rachel and Doan, AnHai and Tan, Wang{-}Chiew and Alawini, Abdussalam and Ngo, Hung Q.}, title = {Lethe: {A} Tunable Delete-Aware {LSM} Engine}, booktitle = {Proceedings of the {ACM SIGMOD} International Conference on Management of Data}, pages = {893--908}, publisher = {{ACM}}, year = {2020}, url = {https://doi.org/10.1145/3318464.3389757}, doi = {10.1145/3318464.3389757}, timestamp = {Sat, 15 Nov 2025 13:48:26 +0100}, biburl = {https://dblp.org/rec/conf/sigmod/SarkarPSA20.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, video = {https://www.youtube.com/watch?v=P0qUS2BwATg}, }

2019

CRC Press
Sensors, Cloud, and Fog: The Enabling Technologies for the Internet of Things

Sudip Misra, Subhadeep Sarkar, and Subarna Chatterjee

CRC Press, Taylor & Francis Group, 2019

8

This book provides an in-depth understanding of Internet of Things (IoT) technology. It highlights several of today’s research and technological challenges of translating the concept of the IoT into a practical, technologically feasible, and business-viable solution. It introduces two novel technologies – sensor-cloud and fog computing – as the crucial enablers for the sensing and compute backbone of the IoT. The book discusses these two key enabling technologies of IoT that include a wide range of practical design issues and the futuristic possibilities and directions involving sensor networks and cloud and fog computing environments towards the realization and support of IoT.
@book{books/crc/MisraSC19, author = {Misra, Sudip and Sarkar, Subhadeep and Chatterjee, Subarna}, title = {Sensors, Cloud, and Fog: The Enabling Technologies for the Internet of Things}, publisher = {{CRC} Press, Taylor \& Francis Group}, year = {2019}, url = {https://www.routledge.com/Sensors-Cloud-and-Fog-The-Enabling-Technologies-for-the-Internet-of-Things/Misra-Sarkar-Chatterjee/p/book/9780367196127}, purchase = {https://www.routledge.com/Sensors-Cloud-and-Fog-The-Enabling-Technologies-for-the-Internet-of-Things/Misra-Sarkar-Chatterjee/p/book/9780367196127}, }

2018

TCC
Assessment of the Suitability of Fog Computing in the Context of Internet of Things

Subhadeep Sarkar, Subarna Chatterjee, and Sudip Misra

IEEE Transactions on Cloud Computing, 2018

This work performs a rigorous, comparative analysis of the fog computing paradigm and the conventional cloud computing paradigm in the context of the Internet of Things (IoT), by mathematically formulating the parameters and characteristics of fog computing – one of the first attempts of its kind. With the rapid increase in the number of Internet-connected devices, the increased demand of real-time, low-latency services is proving to be challenging for the traditional cloud computing framework. Also, our irreplaceable dependency on cloud computing demands the cloud data centers (DCs) always to be up and running which exhausts huge amount of power and yield tons of carbon dioxide (CO2) gas. In this work, we assess the applicability of the newly proposed fog computing paradigm to serve the demands of the latency-sensitive applications in the context of IoT. We model the fog computing paradigm by mathematically characterizing the fog computing network in terms of power consumption, service latency, CO2 emission, and cost, and evaluating its performance for an environment with high number of Internet-connected devices demanding real-time service. A case study is performed with traffic generated from the 100 highest populated cities being served by eight geographically distributed DCs. Results show that as the number of applications demanding real-time service increases, the fog computing paradigm outperforms traditional cloud computing. For an environment with 50% applications requesting for instantaneous, real-time services, the overall service latency for fog computing is noted to decrease by 50:09%. However, it is mentionworthy that for an environment with less percentage of applications demanding for low-latency services, fog computing is observed to be an overhead compared to the traditional cloud computing. Therefore, the work shows that in the context of IoT, with high number of latency-sensitive applications fog computing outperforms cloud computing.
@article{DBLP:journals/tcc/SarkarCM18, author = {Sarkar, Subhadeep and Chatterjee, Subarna and Misra, Sudip}, title = {Assessment of the Suitability of Fog Computing in the Context of Internet of Things}, journal = {{IEEE} Transactions on Cloud Computing}, volume = {6}, number = {1}, pages = {46--59}, year = {2018}, url = {https://doi.org/10.1109/TCC.2015.2485206}, doi = {10.1109/TCC.2015.2485206}, timestamp = {Fri, 09 Apr 2021 18:29:19 +0200}, biburl = {https://dblp.org/rec/journals/tcc/SarkarCM18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
iThings
Towards Enforcement of the EU GDPR: Enabling Data Erasure

Subhadeep Sarkar, Jean-Pierre Banâtre, Louis Rilling, and Christine Morin

In IEEE International Conference on Internet of Things (iThings), 2018

35

With the emergence of the Internet of Things (IoT), an increasing need for preserving the privacy of personal data has been realized. In this context, the EU has recently published the general data protection regulation (GDPR), which ensures strengthening of the privacy rights of the data subjects concerning their personal data. In this paper, we present the importance of having a holistic solution aimed towards the enforcement of the GDPR. As a first step towards the enforcement of the GDPR, we present the research challenges in facilitating the erasure of data as per the right to erasure. We also propose the envisaged technical solutions to work through the challenges.
@inproceedings{DBLP:conf/ithings/SarkarBRM18, author = {Sarkar, Subhadeep and Ban{\^{a}}tre, Jean{-}Pierre and Rilling, Louis and Morin, Christine}, title = {Towards Enforcement of the {EU} {GDPR:} Enabling Data Erasure}, booktitle = {{IEEE} International Conference on Internet of Things ({iThings})}, pages = {222--229}, publisher = {{IEEE}}, year = {2018}, url = {https://doi.org/10.1109/Cybermatics\_2018.2018.00067}, doi = {10.1109/CYBERMATICS\_2018.2018.00067}, timestamp = {Sun, 25 Oct 2020 22:47:28 +0100}, biburl = {https://dblp.org/rec/conf/ithings/SarkarBRM18.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2017

PhD Thesis
Analysis of Delay in Wireless Communication for Healthcare Systems

Subhadeep Sarkar

Indian Institute of Technology Kharagpur, 2017

Recently, the IEEE 802.15.6 Task Group introduced a new set of physical layer and medium access control sublayer protocols for wireless communication involving wireless body area networks (WBANs). The IEEE 802.15.6 standard is designed specifically to support short-range (within 10 m), ultra-low power wireless communications with very high data rate (up to 10 Mbps) within or in the vicinity of human body. The fundamental changes proposed through the standard are introduction of eight user priorities (UPs) based on the traffic designation, and the corresponding sets of minimum and maximum values for the contention window. However, one of the most important changes introduced through the standard is the work-flow of the IEEE 802.15.6 CSMA/CA MAC protocol, where a transmitting node may lock its backoff counter under certain conditions and unlock the same upon the resumption of favorable conditions, which is unlike any previously known CSMA/CA protocol.
The thesis investigates the impact of the backoff counter locking mechanism on the transmission latency in the IEEE 802.15.6 CSMA/CA protocol and proposes a solution to the problem. As a first step, a discrete-time Markov chain (DTMC) is designed to model the different states of a node operating in the standard. The thesis proposes the Fair and Latency-aware backOff cOunter Decrement (FLOOD) algorithm, which optimizes the delay incurred during frame transmission. The thesis also proposes the Priority-based Allocation of Time-Slots (PATS) algorithm, a context-aware frame transmission algorithm based on the constant model hawk-dove evolutionary game, which ensures prioritized transmission of data frames based on the criticality of the transmitting WBAN. Together, FLOOD and PATS lead to transmission of data frames with minimum delay incurred while ensuring prioritized transmission for critical WBANs.
@phdthesis{Sarkar_PhD_IITKgp17, author = {Sarkar, Subhadeep}, title = {Analysis of Delay in Wireless Communication for Healthcare Systems}, school = {Indian Institute of Technology Kharagpur}, year = {2017}, url = {http://www.idr.iitkgp.ac.in/xmlui/handle/123456789/8373}, }
Comm Lett
Privacy-Aware Blind Cloud Framework for Advanced Healthcare

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra, and Rajesh Kudupudi

IEEE Communications Letters, 2017

21

This letter proposes a novel privacy-aware “blind” cloud infrastructure to be utilized for storage, processing, and organization of health data. Traditional healthcare systems rely on cloud computing servers for back-end storage and processing. However, cloud servers are heavily vulnerable to privacy threats and the problem is even more intense as physiological data carry sensitive information. To resolve the aforementioned issue, this letter proposes the blind cloud framework. The goal is to take advantage of the enormous computing and storage abilities of the cloud servers, and yet maintain data anonymity simultaneously. To preserve the privacy of the medical data, the cloud server is forcefully blinded, i.e., the identities of the patients are masked off and a pseudo-identity is generated, thereby, obtaining unidentified in-cloud data for storage and analysis. We also propose a parallel method to be executed within the non-cloud servers for efficient and lossless identity management and retrieval. Results indicate that the performance of the processes of pseudo-identity generation and identity retrieval is independent of the data volumes, and negligibly vary with the increase in the number of the clients of the system.
@article{DBLP:journals/icl/SarkarCMK17, author = {Sarkar, Subhadeep and Chatterjee, Subarna and Misra, Sudip and Kudupudi, Rajesh}, title = {Privacy-Aware Blind Cloud Framework for Advanced Healthcare}, journal = {{IEEE} Communications Letters}, volume = {21}, number = {11}, pages = {2492--2495}, year = {2017}, url = {https://doi.org/10.1109/LCOMM.2017.2739141}, doi = {10.1109/LCOMM.2017.2739141}, timestamp = {Mon, 26 Oct 2020 08:28:19 +0100}, biburl = {https://dblp.org/rec/journals/icl/SarkarCMK17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
Comp Net
Optimal decision rule-based ex-ante frequency hopping for jamming avoidance in wireless sensor networks

Prasenjit Bhavathankar, Subhadeep Sarkar, and Sudip Misra

Computer Networks, Elsevier, 2017

In this paper, we consider a static wireless sensor network (WSN) affected by a constant, static jammer. Both the nodes in the network and the jammer are capable of switching frequencies. Existing literature mostly thrive on mechanisms with a mutually pre-decided hopping-sequence or on random frequency-hopping techniques. However, these mechanisms often fall short in the context of energy-constrained WSNs. We propose a frequency-hopping strategy based on the optimal decision rule. The proposed solution takes into account the individual decision profiles of all the concerned nodes, and finally, makes the decision for the welfare of the overall network. The objective is to find an optimal frequency hopping rule to obtain the maximum throughput. We observe that the packet delivery ratio of the network improves by approximately 30% after the application of the optimal decision rule for frequency-hopping. The overall network energy consumption is also improved by approximately 53% by the application of the proposed solution approach, as observed from the results.
@article{DBLP:journals/cn/BhavathankarSM17, author = {Bhavathankar, Prasenjit and Sarkar, Subhadeep and Misra, Sudip}, title = {Optimal decision rule-based ex-ante frequency hopping for jamming avoidance in wireless sensor networks}, journal = {Computer Networks, Elsevier}, volume = {128}, pages = {172--185}, year = {2017}, url = {https://doi.org/10.1016/j.comnet.2017.03.009}, doi = {10.1016/J.COMNET.2017.03.009}, timestamp = {Fri, 09 Apr 2021 18:25:56 +0200}, biburl = {https://dblp.org/rec/journals/cn/BhavathankarSM17.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2016

Pulse
From Micro to Nano: The Evolution of Wireless Sensor-Based Health Care

Subhadeep Sarkar and Sudip Misra

IEEE Pulse, 2016

115

Over the past decade, embedded systems and microelectromechanical systems have evolved in a radical way, redefining our standard of living and enhancing the quality of life. Health care, among various other fields, has benefited vastly from this technological development. The concept of using sensors for health care purposes originated in the late 1980s when sensors were developed to measure certain physiological parameters associated with the human body. In traditional sensor nodes, the signal sources are mostly different environmental phenomena (such as temperature, vibration, and luminosity) or man-made events (such as intrusion and mobile target tracking), whereas in case of the physiological sensors, the signal source is living human tissue. These sensor nodes, as their primary sensing element, have a diaphragm that converts pressure into displacement. This displacement, in turn, is subsequently transformed into an electrical signal. The concept of wireless physiological sensor nodes, however, gained popularity in the mid-2000s, with the sensed data from the nodes transmitted to the hub via a wireless medium. The network formed by this heterogeneous set of wireless body sensor nodes is termed a wireless body-area network (WBAN). Each WBAN is essentially a composition of multiple wireless body sensor nodes and a single hub. The hub is primarily responsible for acquisition of the raw sensed data from all the component sensor nodes and first-level aggregation of the data before transmitting the aggregated data for further analysis to a remote data acquisition center. Here, we outline the evolution of WBANs in the context of modern health care and its convergence with nanotechnology.
@article{journals/pulse/SarkarM16, author = {Sarkar, Subhadeep and Misra, Sudip}, title = {From Micro to Nano: The Evolution of Wireless Sensor-Based Health Care}, journal = {{IEEE} Pulse}, volume = {7}, number = {1}, pages = {21--25}, year = {2016}, month = jan, publisher = {Institute of Electrical and Electronics Engineers ({IEEE})}, issn = {2154-2287}, doi = {10.1109/MPUL.2015.2498498}, url = {https://doi.org/10.1109/MPUL.2015.2498498}, }
IET Net
Theoretical modelling of fog computing: a green computing paradigm to support IoT applications

Subhadeep Sarkar and Sudip Misra

IET Networks, 2016

In this study, the authors focus on theoretical modelling of the fog computing architecture and compare its performance with the traditional cloud computing model. Existing research works on fog computing have primarily focused on the principles and concepts of fog computing and its significance in the context of internet of things (IoT). This work, one of the first attempts in its domain, proposes a mathematical formulation for this new computational paradigm by defining its individual components and presents a comparative study with cloud computing in terms of service latency and energy consumption. From the performance analysis, the work establishes fog computing, in collaboration with the traditional cloud computing platform, as an efficient green computing platform to support the demands of the next generation IoT applications. Results show that for a scenario where 25% of the IoT applications demand real-time, low-latency services, the mean energy expenditure in fog computing is 40.48% less than the conventional cloud computing model.
@article{DBLP:journals/iet-net/SarkarM16, author = {Sarkar, Subhadeep and Misra, Sudip}, title = {Theoretical modelling of fog computing: a green computing paradigm journal = {{IET} Networks}, volume = {5}, number = {2}, pages = {23--29}, year = {2016}, url = {https://doi.org/10.1049/iet-net.2015.0034}, doi = {10.1049/IET-NET.2015.0034}, timestamp = {Fri, 09 Apr 2021 18:31:02 +0200}, biburl = {https://dblp.org/rec/journals/iet-net/SarkarM16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
GLOBECOM
Resource Allocation for Wireless Body Area Networks in Presence of Selfish Agents

Subhadeep Sarkar, Sudip Misra, and Mohammad S. Obaidat

In 2016 IEEE Global Communications Conference (GLOBECOM), 2016

In medical emergency situations, fair distribution of resources in a multi-tenant scenario is crucial. In such resource-constrained situations, these organizations may behave in a non-cooperative and selfish manner to maximize their individual incentives at the cost of the overall system welfare. Existing research works on dynamic resource allocation, have mostly assumed that the participating agents always behave truthfully, and place bids in accordance with their actual requirements. In practice, this assumption may not always hold true, as organizations have positive incentives for overstating. We design an algorithm, grounded in the theory of distributed mechanism design, to effectively alleviate untruthful demeanor of the organizations. The proposed resource allocation algorithm allows such organizations to maximize their individual incentives only by acting truthfully, whilst the overall system welfare is also maximized. The mechanism designed is resilient to selfish behavior of the organizations, and ensures voluntary participation of the organizations in the auction. It is also incentive compatible in nature, and dictates a truthful incentive-payment scheme.
@inproceedings{DBLP:conf/globecom/SarkarMO16, author = {Sarkar, Subhadeep and Misra, Sudip and Obaidat, Mohammad S.}, title = {Resource Allocation for Wireless Body Area Networks in Presence of Selfish Agents}, booktitle = {2016 {IEEE} Global Communications Conference ({GLOBECOM})}, pages = {1--6}, publisher = {{IEEE}}, year = {2016}, url = {https://doi.org/10.1109/GLOCOM.2016.7842222}, doi = {10.1109/GLOCOM.2016.7842222}, timestamp = {Fri, 09 Apr 2021 18:45:53 +0200}, biburl = {https://dblp.org/rec/conf/globecom/SarkarMO16.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
Patent
A Privacy-Aware Ambulatory Healthcare System Using Wireless Body Area Networks (WBANs)

Subhadeep Sarkar, Subarna Chatterjee, Sudip Misra, Ezaj A. Ansari, Dipayan Ghatak, and Saurav Sarkar

Indian Patent, File no.: 201631000214, 2016

The proposed invention relates to the development of a Wireless Body Area Network (WBAN)-equipped "blind" cloud system to enhance the existing ambulatory healthcare system without having extensive infrastructural dependence. As per the traditional healthcare techniques of the country, the diagnosis of a patient commences only after s/he is admitted to a medical unit or hospital. Thus, in cases of extreme criticality or medical emergency, the patient often undergoes tremendous inconvenience which may even be fatal. The proposed invention aims at introducing a novel ambulatory healthcare system coupled with the recent technological advancements. The idea behind this invention is to provide majorly unmanned, automated, pervasive, remote, real-time ambulatory healthcare services. After getting into an ambulance, a patient would be made to wear a set of easy, light-weighted, and convenient wireless body sensor nodes which would form a WBAN, and would instantaneously initiate the capturing the patient’s physiological data. These data would be fed to remote cloud servers in real time from where it would undergo a perfunctory analysis. To enhance the precision of the analytics, the invention envisions gathering a real-time medical history of the patient through a simple, form-based interface (with assistance from a paramedic). Based on the data criticality and medical history, voice or text-based feedback directives will be delivered at the patient’s end and will be executed by the paramedic within the ambulance. The invention is strongly dependent on cloud computing technology as the cloud servers serve as the primary hubs of storage and computation of the system. However, to address the issues related to security, data confidentiality, and vulnerability of cloud computing, the invention proposes to develop a completely "blind" cloud platform. The goal is to take advantage of the enormous computing and storage abilities of the cloud servers by maintaining data anonymity simultaneously. To preserve the privacy of the medical data, we propose an intelligent method to mask the identity of the patients, i.e., the users of the system, and thereby, obtaining unidentified data for storage and analysis. We also propose a parallel method to be executed within the non-cloud servers for efficient and lossless identity management and retrieval.
@misc{Sarkar_IndianPatent16, author = {Sarkar, Subhadeep and Chatterjee, Subarna and Misra, Sudip and Ansari, Ezaj A. and Ghatak, Dipayan and Sarkar, Saurav}, title = {A Privacy-Aware Ambulatory Healthcare System Using Wireless Body Area Networks (WBANs)}, year = {2016}, month = jan, howpublished = {Indian Patent, File no.: 201631000214}, }

2015

TC
Performance Analysis of IEEE 802.15.6 MAC Protocol under Non-Ideal Channel Conditions and Saturated Traffic Regime

Subhadeep Sarkar, Sudip Misra, Bitan Bandyopadhyay, Chandan Chakraborty, and Mohammad S. Obaidat

IEEE Transactions on Computers, 2015

Recently, the IEEE 802.15.6 Task Group introduced a new wireless communication standard that provides a suitable framework specifically to support the requirements of wireless body area networks (WBANs). The standardization dictates the physical (PHY) layer and medium access control (MAC) layer protocols for WBAN-based communications. Unlike the pre-existing wireless communication standards, IEEE 802.15.6 standardization supports short-range, extremely low power wireless communication with high quality of service and support for high data rates upto 10 Mbps in the vicinity of living tissues. In this work, we construct a discrete-time Markov chain (DTMC) that efficiently depicts the states of an IEEE 802.15.6 CSMA/CA-based WBAN. Following this, we put forward a thorough analysis of the standard in terms of reliability, throughput, average delay, and power consumption. The work concerns non-ideal channel characteristics and a saturated network traffic regime. The major shortcoming of the existing literature on Markov chain-based analysis of IEEE 802.15.6 is that the authors did not take into consideration the time spent by a node awaiting the acknowledgement frame after transmission of a packet, until time-out occurs. Also, most of the work assume that ideal channel characteristics persist for the network which is hardly the case in practice. This work remains distinctive as we take into account the waiting time of a node after it transmits a packet while constructing the DTMC. Based on the DTMC, we perform a user priority (UP)-wise analysis, and justify the importance of the standard from a medical perspective.
@article{DBLP:journals/tc/SarkarMBCO15, author = {Sarkar, Subhadeep and Misra, Sudip and Bandyopadhyay, Bitan and Chakraborty, Chandan and Obaidat, Mohammad S.}, title = {Performance Analysis of {IEEE} 802.15.6 {MAC} Protocol under Non-Ideal Channel Conditions and Saturated Traffic Regime}, journal = {{IEEE} Transactions on Computers}, volume = {64}, number = {10}, pages = {2912--2925}, year = {2015}, url = {https://doi.org/10.1109/TC.2015.2389806}, doi = {10.1109/TC.2015.2389806}, timestamp = {Fri, 09 Apr 2021 18:33:24 +0200}, biburl = {https://dblp.org/rec/journals/tc/SarkarMBCO15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
JBHI
Priority-Based Time-Slot Allocation in Wireless Body Area Networks During Medical Emergency Situations: An Evolutionary Game-Theoretic Perspective

Sudip Misra and Subhadeep Sarkar

IEEE Journal of Biomedical and Health Informatics, 2015

In critical medical emergency situations, wireless body area network (WBAN) equipped health monitoring systems treat data packets with critical information regarding patients’ health in the same way as data packets bearing regular healthcare information. This snag results in a higher average waiting time for the local data processing units (LDPUs) transmitting data packets of higher importance. In this paper, we formulate an algorithm for Priority-based Allocation of Time Slots (PATS) that considers a fitness parameter characterizing the criticality of health data that a packet carries, energy consumption rate for a transmitting LDPU, and other crucial LDPU properties. Based on this fitness parameter, we design the constant model hawk-dove game that ensures prioritizing the LDPUs based on crucial properties. In comparison with the existing works on priority-based wireless transmission, we measure and take into consideration the urgency, seriousness, and criticality associated with an LDPU and, thus, allocate transmission time slots proportionately. We show that the number of transmitting LDPUs in medical emergency situations can be reduced by 25.97%, in comparison with the existing time-division-based techniques.
@article{DBLP:journals/titb/MisraS15, author = {Misra, Sudip and Sarkar, Subhadeep}, title = {Priority-Based Time-Slot Allocation in Wireless Body Area Networks During Medical Emergency Situations: An Evolutionary Game-Theoretic Perspective}, journal = {{IEEE} Journal of Biomedical and Health Informatics}, volume = {19}, number = {2}, pages = {541--548}, year = {2015}, url = {https://doi.org/10.1109/JBHI.2014.2313374}, doi = {10.1109/JBHI.2014.2313374}, timestamp = {Mon, 26 Oct 2020 08:44:33 +0100}, biburl = {https://dblp.org/rec/journals/titb/MisraS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
ICC
Quantification of Node Misbehavior in Wireless Sensor Networks: A Social Choice-based Approach

Subarna Chatterjee, Subhadeep Sarkar, and Sudip Misra

In IEEE International Conference on Communication (ICC) Workshops, 2015

3

This work focuses on the quantification of node misbehavior in wireless sensor networks (WSNs). Misbehaving nodes are common within WSNs which are once detected, are penalized and in some cases eliminated from the network. However, node misbehavior might be relative i.e., a node may exhibit maliciousness or selfishness only to a specific set of nodes and may function normally for the rest. In these cases, a complete elimination of the node from the network is unfair. This work mitigates the aforesaid problem and mathematically evaluates the extent of misbehavior of a node through the proposed Metric of Misbehavior (MoM). Based on the Theory of Social Choice, the proposed algorithm considers the misbehaving nodes as the voting alternatives and the normally behaving nodes as the voters. Based on majority ranking of social choice, eventually MoM is obtained for every alternative in a fair manner.
@inproceedings{DBLP:conf/icc/ChatterjeeSM15, author = {Chatterjee, Subarna and Sarkar, Subhadeep and Misra, Sudip}, title = {Quantification of Node Misbehavior in Wireless Sensor Networks: {A} Social Choice-based Approach}, booktitle = {{IEEE} International Conference on Communication ({ICC}) Workshops}, pages = {1479--1484}, publisher = {{IEEE}}, year = {2015}, url = {https://doi.org/10.1109/ICCW.2015.7247388}, doi = {10.1109/ICCW.2015.7247388}, timestamp = {Sun, 25 Oct 2020 22:46:06 +0100}, biburl = {https://dblp.org/rec/conf/icc/ChatterjeeSM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2014

Cloud Comp
Evacuation and Emergency Management Using a Federated Cloud

Subhadeep Sarkar, Subarna Chatterjee, and Sudip Misra

IEEE Cloud Computing, 2014

10

Contemporary disaster relief techniques fall significantly short in terms of efficiency and timeliness. In a postdisaster scenario, the generation and transmission of voluminous data at a high velocity impacts the communication framework. This work exploits the benefits of opportunistic communication and efficient big data management policies, focusing on the collaboration of multiple private and/or public clouds of diverse nature to perform damage assessment and determine the spatial distribution of the live victims and their physical and mental status. Based on the analytics, real-time decision making of the rescue operation is achieved.
@article{DBLP:journals/cloudcomp/SarkarCM14, author = {Sarkar, Subhadeep and Chatterjee, Subarna and Misra, Sudip}, title = {Evacuation and Emergency Management Using a Federated Cloud}, journal = {{IEEE} Cloud Computing}, volume = {1}, number = {4}, pages = {68--76}, year = {2014}, url = {https://doi.org/10.1109/MCC.2014.72}, doi = {10.1109/MCC.2014.72}, timestamp = {Mon, 26 Oct 2020 08:33:07 +0100}, biburl = {https://dblp.org/rec/journals/cloudcomp/SarkarCM14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }
GLOBECOM
Analysis of Reliability and Throughput under Saturation Condition of IEEE 802.15.6 CSMA/CA for Wireless Body Area Networks

Subhadeep Sarkar, Sudip Misra, Chandan Chakraborty, and Mohammad S. Obaidat

In IEEE Global Communications Conference (GLOBECOM), 2014

23

The standardization of the IEEE 802.15.6 protocol for wireless body area networks (WBANs) dictates the physical layer and medium access control layer standards from the communication perspective. The standard supports short-range, extremely low power wireless communication with high quality of service and data rates upto 10 Mbps in the vicinity of any living tissue. In this paper, we develop a discrete-time Markov model for the accurate analysis of reliability and throughput of an IEEE 802.15.6 CSMA/CA-based WBAN under saturation condition. Existing literature on Markov chain-based analysis of IEEE 802.15.6, however, do not take into consideration the time a node spends waiting for the immediate acknowledgement frame after transmission of a packet, until time-out occurs. In this work, we take into consideration the waiting time for a node after its transmission, and accordingly modified the structure of the discrete-time Markov chain (DTMC). We also show that as the payload length increases, the reliability of a node decreases; whereas its throughput sharply increases.
@inproceedings{DBLP:conf/globecom/SarkarMCO14, author = {Sarkar, Subhadeep and Misra, Sudip and Chakraborty, Chandan and Obaidat, Mohammad S.}, title = {Analysis of Reliability and Throughput under Saturation Condition of {IEEE} 802.15.6 {CSMA/CA} for Wireless Body Area Networks}, booktitle = {{IEEE} Global Communications Conference ({GLOBECOM})}, pages = {2405--2410}, publisher = {{IEEE}}, year = {2014}, url = {https://doi.org/10.1109/GLOCOM.2014.7037168}, doi = {10.1109/GLOCOM.2014.7037168}, timestamp = {Sun, 25 Oct 2020 22:56:47 +0100}, biburl = {https://dblp.org/rec/conf/globecom/SarkarMCO14.bib}, bibsource = {dblp computer science bibliography, https://dblp.org}, }

2026

RangeReduce: Query-Driven LSM Compactions

ZARC: Re-inventing Zone Allocation for LSMs on ZNS SSD

2025

Tectonic: Bridging Synthetic and Real-World Workloads for Key-Value Benchmarking

QuIT your B+-tree for the Quick Insertion Tree

2024

Anatomy of the LSM Memory Buffer: Insights & Implications

KVBench: A Key-Value Benchmarking Suite

2023

Enabling Timely and Persistent Deletion in LSM-Engines

Acheron: Persisting Tombstones in LSM Engines

The LSM Design Space and its Read Optimizations

Indexing for Near-Sorted Data

2022

Building Deletion-Compliant Data Systems

Query Language Support for Timely Data Deletion

Compactionary: A Dictionary for LSM Compactions

Dissecting, Designing, and Optimizing LSM-based Data Stores

BoDS: A Benchmark on Data Sortedness

Toward Building Deletion Compliant Data Systems

2021

Constructing and Analyzing the LSM Compaction Design Space

i-MAC: In-Body Sensor MAC in Wireless Body Area Networks for Healthcare IoT

2020

Lethe: A Tunable Delete-Aware LSM Engine

2019

Sensors, Cloud, and Fog: The Enabling Technologies for the Internet of Things

2018

Assessment of the Suitability of Fog Computing in the Context of Internet of Things

Towards Enforcement of the EU GDPR: Enabling Data Erasure

2017

Analysis of Delay in Wireless Communication for Healthcare Systems

Privacy-Aware Blind Cloud Framework for Advanced Healthcare

Optimal decision rule-based ex-ante frequency hopping for jamming avoidance in wireless sensor networks

2016

From Micro to Nano: The Evolution of Wireless Sensor-Based Health Care

Theoretical modelling of fog computing: a green computing paradigm to support IoT applications

Resource Allocation for Wireless Body Area Networks in Presence of Selfish Agents

A Privacy-Aware Ambulatory Healthcare System Using Wireless Body Area Networks (WBANs)

2015

Performance Analysis of IEEE 802.15.6 MAC Protocol under Non-Ideal Channel Conditions and Saturated Traffic Regime

Priority-Based Time-Slot Allocation in Wireless Body Area Networks During Medical Emergency Situations: An Evolutionary Game-Theoretic Perspective

Quantification of Node Misbehavior in Wireless Sensor Networks: A Social Choice-based Approach

2014

Evacuation and Emergency Management Using a Federated Cloud

Analysis of Reliability and Throughput under Saturation Condition of IEEE 802.15.6 CSMA/CA for Wireless Body Area Networks

QuIT your B⁺-tree for the Quick Insertion Tree