Rajiv Gupta
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Rajiv Gupta has a total of 196 co-authors. Here are the top co-authors by number of shared publications:
Xiangyu Zhang
Purdue University, USA
28 shared publicationsMary Lou Soffa
26 shared publicationsMin Feng
Department of Computer Science, The University of California at Riverside, Engineering Bldg. Unit 2, Rm. 463, Riverside, CA 92521 USA
23 shared publicationsLaxmi N. Bhuyan
Department of Computer Science and Engineering, University of California Riverside, Riverside, CA, USA
20 shared publicationsVijay Nagarajan
19 shared publicationsChen Tian
Huawei US R&D Center, Santa Clara, CA, USA
17 shared publications
Latest Publications
- Open Access
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1272-1276
From Syntactic to Semantic Spectra for Fault Localization
Fault localization identifies program locations responsible for observed failures. Existing techniques often rely on structural proxies to correlate failures with execution behavior. Such proxies collapse when failures arise from violations of semantic intent, such as numeric invariants, value relations, and state or temporal consistency, without altering execution structure. In this paper, we propose SemLoc, a fault localization framework based on semantic spectra anchored to program structures. The key essence is that semantic properties can be inferred and explicitly indexed to program structure. SemLoc first infers domain-specific constraints from code, indexes them across functions, blocks, and dataflows, and evaluates them at runtime to identify violated invariants. It then applies counterfactual verification to refine localization by pruning inferred constraints that are incorrect or incomplete. Our preliminary results indicate that SemLoc reduces the candidate faulty lines by 74.4%, corresponding to 5.2× reduction compared with spectrum-based fault localization and 6.2× reduction compared with delta debugging, while matching the ground-truth faulty locations on all evaluated subjects. The investigation of semantic spectra indexed to program structure naturally generalizes to future spectra based on data characteristics, value distributions, or learned representations.
- 5 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1272-1276
Open AccessFrom Syntactic to Semantic Spectra for Fault Localization
Fault localization identifies program locations responsible for observed failures. Existing techniques often rely on structural proxies to correlate failures with execution behavior. Such proxies collapse when failures arise from violations of semantic intent, such as numeric invariants, value relations, and state or temporal consistency, without altering execution structure. In this paper, we propose SemLoc, a fault localization framework based on semantic spectra anchored to program structures. The key essence is that semantic properties can be inferred and explicitly indexed to program structure. SemLoc first infers domain-specific constraints from code, indexes them across functions, blocks, and dataflows, and evaluates them at runtime to identify violated invariants. It then applies counterfactual verification to refine localization by pruning inferred constraints that are incorrect or incomplete. Our preliminary results indicate that SemLoc reduces the candidate faulty lines by 74.4%, corresponding to 5.2× reduction compared with spectrum-based fault localization and 6.2× reduction compared with delta debugging, while matching the ground-truth faulty locations on all evaluated subjects. The investigation of semantic spectra indexed to program structure naturally generalizes to future spectra based on data characteristics, value distributions, or learned representations.
- Open Access
- 15 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 43-56
DeduBB: Binary Code Size Reduction via Post-Link Basic Block Deduplication
- 15 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 43-56
Open AccessDeduBB: Binary Code Size Reduction via Post-Link Basic Block Deduplication
- Open Access
- 1 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 405-417
PreFix: Optimizing the Performance of Heap-Intensive Applications
Analyses of heap-intensive applications show that a small fraction of heap objects account for the majority of heap accesses and data cache misses. Prior works like HDS and HALO have shown that allocating hot objects in separate memory regions can improve spatial locality leading to better application performance. However, these techniques are constrained in two primary ways, limiting their gains. First, these techniques have Imperfect Separation, polluting the hot memory region with several cold objects. Second, reordering of objects across allocations is not possible as the original object allocation order is preserved. This paper presents a novel technique that achieves near perfect separation of hot objects via a new context mechanism that efficiently identifies hot objects with high precision. This technique, named PreFix, is based upon Preallocating memory for a Fixed small number of hot objects. The program, guided by profiles, is instrumented to compute context information derived from dynamic object identifiers, that precisely identifies hot object allocations that are then placed at predetermined locations in the preallocated memory. The preallocated memory region for hot objects provides the flexibility to reorder objects across allocations and allows colocation of objects that are part of a hot data stream (HDS), improving spatial locality. The runtime overhead of identifying hot objects is not significant as this optimization is only focused on a small number of static hot allocation sites and dynamic hot objects. While there is an increase in the program's memory foot-print, it is manageable and can be controlled by limiting the size of the preallocated memory. In addition, PreFix incorporates an object recycling optimization that reuses the same preallocated space to store different objects whose lifetimes are not expected to overlap. Our experiments with 13 heap-intensive applications yield reductions in execution times ranging from 2.77% to 74%. On average PreFix reduces execution time by 21.7% compared to 7.3% by HDS and 14% by HALO. This is due to PreFix's precision in hot object identification, hot object colocation, and low runtime overhead.
- 1 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 405-417
Open AccessPreFix: Optimizing the Performance of Heap-Intensive Applications
Analyses of heap-intensive applications show that a small fraction of heap objects account for the majority of heap accesses and data cache misses. Prior works like HDS and HALO have shown that allocating hot objects in separate memory regions can improve spatial locality leading to better application performance. However, these techniques are constrained in two primary ways, limiting their gains. First, these techniques have Imperfect Separation, polluting the hot memory region with several cold objects. Second, reordering of objects across allocations is not possible as the original object allocation order is preserved. This paper presents a novel technique that achieves near perfect separation of hot objects via a new context mechanism that efficiently identifies hot objects with high precision. This technique, named PreFix, is based upon Preallocating memory for a Fixed small number of hot objects. The program, guided by profiles, is instrumented to compute context information derived from dynamic object identifiers, that precisely identifies hot object allocations that are then placed at predetermined locations in the preallocated memory. The preallocated memory region for hot objects provides the flexibility to reorder objects across allocations and allows colocation of objects that are part of a hot data stream (HDS), improving spatial locality. The runtime overhead of identifying hot objects is not significant as this optimization is only focused on a small number of static hot allocation sites and dynamic hot objects. While there is an increase in the program's memory foot-print, it is manageable and can be controlled by limiting the size of the preallocated memory. In addition, PreFix incorporates an object recycling optimization that reuses the same preallocated space to store different objects whose lifetimes are not expected to overlap. Our experiments with 13 heap-intensive applications yield reductions in execution times ranging from 2.77% to 74%. On average PreFix reduces execution time by 21.7% compared to 7.3% by HDS and 14% by HALO. This is due to PreFix's precision in hot object identification, hot object colocation, and low runtime overhead.
- Open Access
- 28 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 369-381
PANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search
Approximate Nearest-Neighbor Search (ANNS) has become the standard querying method in vector databases, especially with the recent surge in large-scale, high-dimensional data driven by LLM-based applications. Recently, graph-based ANNS has shown improved throughput by constructing a graph from the dataset, with edges representing the distances between data points, and using best-first or beam search algorithms for query evaluation. This work highlights that key aspects of the design space for both graph construction and search in graph-based ANNS remain under-explored. Specifically, the construction phase often neglects the potential temporal correlation between input queries and their results, while the search phase lacks a thorough exploration of beam search parameterization. To address these gaps, we present PANNS, a system that embeds temporal information in the proximity graph construction to capture query-result correlations. Moreover, it introduces a fully parameterized beam search algorithm, enabling extensive performance optimization. PANNS achieves up to a 3.7× improvement in query throughput over state-of-the-art graph-based ANNS methods, while maintaining equivalent recall levels. Furthermore, it reduces graph size by up to 30% without degrading query quality.
- 28 February 2025
- Published by Association for Computing Machinery (ACM)
- p. 369-381
Open AccessPANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search
Approximate Nearest-Neighbor Search (ANNS) has become the standard querying method in vector databases, especially with the recent surge in large-scale, high-dimensional data driven by LLM-based applications. Recently, graph-based ANNS has shown improved throughput by constructing a graph from the dataset, with edges representing the distances between data points, and using best-first or beam search algorithms for query evaluation. This work highlights that key aspects of the design space for both graph construction and search in graph-based ANNS remain under-explored. Specifically, the construction phase often neglects the potential temporal correlation between input queries and their results, while the search phase lacks a thorough exploration of beam search parameterization. To address these gaps, we present PANNS, a system that embeds temporal information in the proximity graph construction to capture query-result correlations. Moreover, it introduces a fully parameterized beam search algorithm, enabling extensive performance optimization. PANNS achieves up to a 3.7× improvement in query throughput over state-of-the-art graph-based ANNS methods, while maintaining equivalent recall levels. Furthermore, it reduces graph size by up to 30% without degrading query quality.
- Open Access
- 20 November 2024
- Published by Association for Computing Machinery (ACM)
- p. 915-932
IncBoost: Scaling Incremental Graph Processing for Edge Deletions and Weight Updates
Incremental query evaluation is key to efficiently processing rapidly changing graph data. By focusing on the parts of the query results affected by updates, it avoids unnecessary computations, allowing for faster query evaluation. While this technique works well in the cases of edge insertions, its benefit quickly diminishes when the volumes of edge deletions and edge weight updates increases. To address the above scalability issue, this work introduces several techniques for handling large update batches that include many edge deletions and weight updates. First, for edge deletions, this work introduces a bottom-up dependency tracing method to identify the affected vertices. Unlike the existing top-down tracing, it completely avoids traversing the underlying graph, thus more scalable for large deletion batches. Second, for edge weight updates, existing graph systems treat each weight change as an edge deletion (with old weight) followed by an edge insertion (with new weight). This "two-round" method is computationally excessive. This work shows that it is, in fact, possible to handle weight updates directly. Finally, this work shows the benefits of adjusting the processing strategy according to the update volume. We integrated the above ideas into a graph system called IncBoost. Based on our evaluation, IncBoost can scale incremental query evaluation to large update batches that represent 30-60% of the graph size. By contrast, the state-of-the-art streaming graph system (RisGraph) typically fails to yield benefits when the batch size reaches 5-15% of the graph size. Regarding the absolute processing time, IncBoost consistently outperforms RisGraph with 3.1× and 5.2× speedups for edge deletions and weight updates on large batches, respectively.
- 20 November 2024
- Published by Association for Computing Machinery (ACM)
- p. 915-932
Open AccessIncBoost: Scaling Incremental Graph Processing for Edge Deletions and Weight Updates
Incremental query evaluation is key to efficiently processing rapidly changing graph data. By focusing on the parts of the query results affected by updates, it avoids unnecessary computations, allowing for faster query evaluation. While this technique works well in the cases of edge insertions, its benefit quickly diminishes when the volumes of edge deletions and edge weight updates increases. To address the above scalability issue, this work introduces several techniques for handling large update batches that include many edge deletions and weight updates. First, for edge deletions, this work introduces a bottom-up dependency tracing method to identify the affected vertices. Unlike the existing top-down tracing, it completely avoids traversing the underlying graph, thus more scalable for large deletion batches. Second, for edge weight updates, existing graph systems treat each weight change as an edge deletion (with old weight) followed by an edge insertion (with new weight). This "two-round" method is computationally excessive. This work shows that it is, in fact, possible to handle weight updates directly. Finally, this work shows the benefits of adjusting the processing strategy according to the update volume. We integrated the above ideas into a graph system called IncBoost. Based on our evaluation, IncBoost can scale incremental query evaluation to large update batches that represent 30-60% of the graph size. By contrast, the state-of-the-art streaming graph system (RisGraph) typically fails to yield benefits when the batch size reaches 5-15% of the graph size. Regarding the absolute processing time, IncBoost consistently outperforms RisGraph with 3.1× and 5.2× speedups for edge deletions and weight updates on large batches, respectively.
- Open Access
- 20 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 68-81
SSRD: Shapes and Summaries for Race Detection in Concurrent Data Structures
Concolic testing combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. This approach has been extended to multithreaded programs for exposing data races. Multithreaded programs frequently rely upon concurrent dynamic data structures whose implementations may contain data races that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. The lack of support for exploring different data structure shapes compromises the detection of races. This paper presents a summarization-guided approach for concolic testing capable of efficiently exploring different dynamic data structure shapes to expose data races. Via unit testing of key functions, function summaries are generated that capture data structure shapes that cause various function paths to be exercised. The shapes are captured in the form of pointer-pointee relations among symbolic pointers. By reusing function summaries during concolic testing, much of the overhead of handling symbolic pointers and dynamic objects in summarized functions is avoided. The summary also contains symbolic memory accesses and synchronization events that guide application-level concolic testing first to identify and then confirm potential data races. We demonstrate the efficiency and efficacy of our approach via experiments with multithreaded programs performing concurrent operations on four widely used dynamic data structures - Skip List, Unrolled Linked List, Priority Queue, and AVL Tree. It increases the number of races detected from 34 to 74 in total in comparison to Cloud9, and reduces both constraints solving time and number of constraints needed to be solved via summarization.
- 20 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 68-81
Open AccessSSRD: Shapes and Summaries for Race Detection in Concurrent Data Structures
Concolic testing combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. This approach has been extended to multithreaded programs for exposing data races. Multithreaded programs frequently rely upon concurrent dynamic data structures whose implementations may contain data races that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. The lack of support for exploring different data structure shapes compromises the detection of races. This paper presents a summarization-guided approach for concolic testing capable of efficiently exploring different dynamic data structure shapes to expose data races. Via unit testing of key functions, function summaries are generated that capture data structure shapes that cause various function paths to be exercised. The shapes are captured in the form of pointer-pointee relations among symbolic pointers. By reusing function summaries during concolic testing, much of the overhead of handling symbolic pointers and dynamic objects in summarized functions is avoided. The summary also contains symbolic memory accesses and synchronization events that guide application-level concolic testing first to identify and then confirm potential data races. We demonstrate the efficiency and efficacy of our approach via experiments with multithreaded programs performing concurrent operations on four widely used dynamic data structures - Skip List, Unrolled Linked List, Priority Queue, and AVL Tree. It increases the number of races detected from 34 to 74 in total in comparison to Cloud9, and reduces both constraints solving time and number of constraints needed to be solved via summarization.
- Open Access
- 22 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 18-32
Core Graph: Exploiting Edge Centrality to Speedup the Evaluation of Iterative Graph Queries
- 22 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 18-32
Open AccessCore Graph: Exploiting Edge Centrality to Speedup the Evaluation of Iterative Graph Queries
- Open Access
- 28 October 2023
- Published by Association for Computing Machinery (ACM)
- p. 310-323
MEGA Evolving Graph Accelerator
Graph Processing is an emerging workload for applications working with unstructured data, such as social network analysis, transportation networks, bioinformatics and operations research. We examine the problem of graph analytics over evolving graphs, which are graphs that change over time. The problem is challenging because it requires evaluation of a graph query on a sequence of graph snapshots over a time window, typically to track the progression of a property over time. In this paper, we introduce MEGA, a hardware accelerator designed for efficiently evaluating queries over evolving graphs. MEGA leverages CommonGraph, a recently proposed software approach for incrementally processing evolving graphs that gains efficiency by avoiding the need to process expensive deletions by converting them into additions. MEGA supports incremental event-based streaming of edge additions as well as execution of multiple snapshots concurrently to support evolving graphs. We propose Batch-Oriented-Execution (BOE), a novel batch-update scheduling technique that activates snapshots that share batches simultaneously to achieve both computation and data reuse. We introduce optimizations that pack compatible batches together, and pipeline batch processing. To the best of our knowledge, MEGA is the first graph accelerator for evolving graphs that evaluates graph queries over multiple snapshots simultaneously. MEGA achieves 24 × -120 × speedup over CommonGraph. It also achieves speedups ranging from 4.08 × to 5.98 × over JetStream, a state-of-the-art streaming graph accelerator.
- 28 October 2023
- Published by Association for Computing Machinery (ACM)
- p. 310-323
Open AccessMEGA Evolving Graph Accelerator
Graph Processing is an emerging workload for applications working with unstructured data, such as social network analysis, transportation networks, bioinformatics and operations research. We examine the problem of graph analytics over evolving graphs, which are graphs that change over time. The problem is challenging because it requires evaluation of a graph query on a sequence of graph snapshots over a time window, typically to track the progression of a property over time. In this paper, we introduce MEGA, a hardware accelerator designed for efficiently evaluating queries over evolving graphs. MEGA leverages CommonGraph, a recently proposed software approach for incrementally processing evolving graphs that gains efficiency by avoiding the need to process expensive deletions by converting them into additions. MEGA supports incremental event-based streaming of edge additions as well as execution of multiple snapshots concurrently to support evolving graphs. We propose Batch-Oriented-Execution (BOE), a novel batch-update scheduling technique that activates snapshots that share batches simultaneously to achieve both computation and data reuse. We introduce optimizations that pack compatible batches together, and pipeline batch processing. To the best of our knowledge, MEGA is the first graph accelerator for evolving graphs that evaluates graph queries over multiple snapshots simultaneously. MEGA achieves 24 × -120 × speedup over CommonGraph. It also achieves speedups ranging from 4.08 × to 5.98 × over JetStream, a state-of-the-art streaming graph accelerator.
- Open Access
- 18 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-2
CommonGraph: Graph Analytics on Evolving Data (Abstract) | Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing
We consider the problem of graph analytics on evolving graphs. In this scenario, a query typically needs to be applied to different snapshots of the graph over an extended time window. We propose CommonGraph, an approach for efficient processing of queries on evolving graphs. We first observe that edge deletions are significantly more expensive than addition operations. CommonGraph converts all deletions to additions by finding a common graph that exists across all snapshots. After computing the query on this graph, to reach any snapshot, we simply need to add the missing edges and incrementally update the query results. CommonGraph also allows sharing of common additions among snapshots that require them, and breaks the sequential dependency inherent in the traditional streaming approach where snapshots are processed in sequence, enabling additional opportunities for parallelism. We incorporate the CommonGraph approach by extending the KickStarter streaming framework. CommonGraph achieves 1.38x-8.17x improvement in performance over Kickstarter across multiple benchmarks.
- 18 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 1-2
Open AccessCommonGraph: Graph Analytics on Evolving Data (Abstract) | Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing
We consider the problem of graph analytics on evolving graphs. In this scenario, a query typically needs to be applied to different snapshots of the graph over an extended time window. We propose CommonGraph, an approach for efficient processing of queries on evolving graphs. We first observe that edge deletions are significantly more expensive than addition operations. CommonGraph converts all deletions to additions by finding a common graph that exists across all snapshots. After computing the query on this graph, to reach any snapshot, we simply need to add the missing edges and incrementally update the query results. CommonGraph also allows sharing of common additions among snapshots that require them, and breaks the sequential dependency inherent in the traditional streaming approach where snapshots are processed in sequence, enabling additional opportunities for parallelism. We incorporate the CommonGraph approach by extending the KickStarter streaming framework. CommonGraph achieves 1.38x-8.17x improvement in performance over Kickstarter across multiple benchmarks.
- Open Access
- 18 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 25-26
Taming Misaligned Graph Traversals in Concurrent Graph Processing (Abstract) | Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing
This work introduces Glign, a runtime system that automatically aligns the graph traversals for concurrent queries. Glign introduces three levels of graph traversal alignment for iterative evaluation of concurrent queries. First, it synchronizes the accesses of different queries to the active parts of the graph within each iteration of the evaluation---intra-iteration alignment. On top of that, Glign leverages a key insight regarding the "heavy iterations" in query evaluation to achieveinter-iteration alignment andalignment-aware batching. The former aligns the iterations of different queries to increase the graph access sharing, while the latter tries to group queries of better graph access sharing into the same evaluation batch. Together, these alignment techniques can substantially boost the data locality of concurrent query evaluation. Based on our experiments, Glign outperforms the state-of-the-art concurrent graph processing systems Krill and GraphM by 3.6× and 4.7× on average, respectively.
- 18 July 2023
- Published by Association for Computing Machinery (ACM)
- p. 25-26
Open AccessTaming Misaligned Graph Traversals in Concurrent Graph Processing (Abstract) | Proceedings of the 2023 ACM Workshop on Highlights of Parallel Computing
This work introduces Glign, a runtime system that automatically aligns the graph traversals for concurrent queries. Glign introduces three levels of graph traversal alignment for iterative evaluation of concurrent queries. First, it synchronizes the accesses of different queries to the active parts of the graph within each iteration of the evaluation---intra-iteration alignment. On top of that, Glign leverages a key insight regarding the "heavy iterations" in query evaluation to achieveinter-iteration alignment andalignment-aware batching. The former aligns the iterations of different queries to increase the graph access sharing, while the latter tries to group queries of better graph access sharing into the same evaluation batch. Together, these alignment techniques can substantially boost the data locality of concurrent query evaluation. Based on our experiments, Glign outperforms the state-of-the-art concurrent graph processing systems Krill and GraphM by 3.6× and 4.7× on average, respectively.