CS Paper Radar

Fast Computation of Lowest Common Ancestor in Version Control Commit Graph

Stepan Polokhin, Ruslan Savchenko, Yuriy Chernyshov

cs.DS cs.SE ·submitted 2026-11-19 10:58 UTC · v1

Abstract

The problem of finding the lowest common ancestor in the commit graph arises when a user wants to merge two (or more) development branches: for example, to add their own development into a common branch. At that moment, the version control system must determine the merge base - the common ancestor of the latest commits of the branches, in order to show the mutual difference between the branches. The problem is complicated by the fact that the commit graph is not a tree but an arbitrary acyclic graph. Moreover, if there is no common ancestor, searching for one may require traversing the entire graph. Traversing a graph with several million vertices takes tens of seconds, which becomes noticeable to users. We show that the commit graph has additional structure - supporting branches - and that this can be used to speed up the algorithm. By extracting supporting branches, the graph can be preprocessed and the search for the lowest common ancestor can be significantly accelerated. Moreover, if removing the supporting branches decomposes the graph into connected components of bounded size, the lowest common ancestor query can be answered in time comparable to searching for a common ancestor within a single component only. We present an algorithm running in time $O(δ_Gm_c + n_s\log^2 n_s + m_s\log n_s)$ and requiring $O(d)$ preprocessed data per vertex, where $δ_G$ is the maximum out-degree of a vertex in $G$, $n_c$ and $m_c$ are the maximum numbers of vertices and edges in a connected component formed after removing the supporting branches, $n_s$ is the number of supporting branches, $m_s$ is the number of edges in the reachability graph between the supporting branches, and $d$ is the maximum number of supporting branches adjacent to any single component.

Closest papers

Nearest neighbours by meaning across the whole index.

KG-Commit: A Dynamic Knowledge Graph for Online Just-in-Time Software Defect Prediction

cs.SE ·2026-09-05 ·Mohsen Hesamolhokama, Mohammad Sina Beyrami Aghbash, Behnam Rohani, Mohammadamin Fazli, Jafar Habibi
hot direction similarity 0.66
Abstract

Just-in-time software defect prediction (JIT-SDP) aims to identify risky commits as they arrive and provide developers with timely feedback. This need for low latency has led most approaches to rely on commit-level information and overlook the broader project context in which a change occurs. Incorporating this context is challenging because it requires both efficient retrieval for incoming commits and continual maintenance as the repository evolves. We introduce KG-Commit, a dynamic knowledge graph that incrementally maintains repository history, within-file code structure, and commit semantics as the project evolves. It also uses an AST-delta mechanism to track structural changes between file edits and relies on lightweight graph inference running entirely on CPU. Our evaluation on 11 Apache software projects against six baselines shows that KG-Commit achieves the highest aggregate Macro-F1 (0.704), G-Mean (0.706), and AUC (0.809) using our selected inference pipeline. Under a realistic online protocol, it outperforms LR, HGB, RF, and DeepJIT on all 11 projects, LApredict on 10, and JITLine on 9 projects in Macro-F1, with the aggregate paired difference significant in every case. KG-Commit processes each commit in approximately 1.33~s, with a cost that remains stable as the graph grows and is compatible with commit rates observed in real-world projects. These findings show that rich project context can be efficiently maintained and exploited for online JIT-SDP.

0.27

Chronos: Efficient Bolt-on Branching Across Data Stores for Stateful Agentic Applications

cs.DB ·2026-09-14 ·Xinjing Zhou, Jason Mohoney, Samuel Madden, Michael Stonebraker, Lei Cao
similarity 0.56
Abstract

Data-centric applications increasingly use speculative execution to explore multiple candidate paths where each path modifies state distributed across heterogeneous data stores. This trend is intensified by the rise of tool-calling agents. Hence, applications need data systems that can create branches quickly, isolate state-modifying paths, and merge changes consistently across stores without imposing substantial query overhead. Existing systems provide only partial support, forcing applications to coordinate branches and merges manually, which increases overhead and risks inconsistent cross-store state. To solve this problem, we introduce Chronos, a bolt-on system that provides branching capability across heterogeneous data stores. We make two contributions. First, Chronos introduces a compact interval-based versioning technique that enables efficient branching and data sharing through simple query rewrite. Second, Chronos introduces a bolt-on architecture that separates branch management from data path within each store. Combined with interval-based versioning, this separation provides atomic cross-store visibility for merges and enables Chronos to support diverse data stores without modifying their engines. We implement Chronos for PostgreSQL, SQLite, DuckDB, Qdrant, and a DBMS-backed filesystem. We evaluate it using cross-store agent workflows, MCTS-style exploration, and per-store benchmarks. Chronos runs MCTS-style exploration up to 16.7x faster than existing approaches while maintaining practical query performance across the underlying stores. Under concurrent cross-store workflows, Chronos prevents partially visible merges while substantially outperforming serialized execution.

0.06

PaB-tree: Parallel B+-tree with Batch Updates

cs.DS cs.DBcs.DC ·2026-11-06 ·Ziyang Men, Yan Gu, Yihan Sun, Helen Xu
similarity 0.56
Abstract

The B+-tree is a ubiquitous search index due to its provable I/O (cache) efficiency. Yet unlike batch-parallel binary search trees, which are both fast and widely available, no batch-parallel B+-tree offers strong empirical performance together with provable, near-optimal I/O efficiency. Prior B+-tree-based designs are either parallel but purely theoretical, with no high-performance implementation, or concurrent indexes such as the Bw-tree and Masstree, which run an order of magnitude slower on batch updates. We present PaB-tree, the first batch-parallel B+-tree with guarantees on work, span, and cache complexity alongside strong practical performance. Its core challenge -- repairing node overflows and underflows without eroding the tree's I/O advantage -- is resolved by one simple invariant: a repair never touches a sibling and is always pushed to the parent. A Promote primitive reduces batch construction and insertion to repeated node promotion, and batch deletion to reinsertion. Batch updates take O(B log_B n) work and O(log_B n) I/O per element, matching the sequential B+-tree bounds, with polylogarithmic span. Against highly-optimized parallel and concurrent baselines, PaB-tree delivers the best overall performance trade-off: up to 1.4x faster on construction and up to 3.6x faster on batch insertion than the strongest baseline, while preserving B+-tree query efficiency.

0.15

TraceVIC: Causal Reasoning over Code Evolution for Identifying Vulnerability-Inducing Commits

cs.SE cs.AI ·2026-09-22 ·Fnu Tanish, Samiha Shimmi, Samikshya Chapagain, Hamed Okhravi, Mona Rahimi +1 more
similarity 0.55
Abstract

Software vulnerabilities are often discovered long after they are introduced, making it difficult to identify the vulnerability-inducing commit (VIC) responsible for introducing the underlying vulnerable condition. Existing VIC identification techniques largely rely on git blame to trace vulnerable code through revision history and use positional heuristics, such as selecting its earliest or most recent modification. However, the true VIC may occur anywhere within this history, and vulnerable behavior may depend on code that evolves across multiple revisions. We therefore argue that VIC identification requires reasoning about how vulnerability-relevant code evolves, rather than simply where a candidate commit appears in the revision history. We present TraceVIC, a temporal graph-based approach for identifying and ranking VICs by reasoning over code evolution. TraceVIC first localizes likely root-cause lines and traces their histories across revisions, constructing graph representations that capture program structure within each revision and the evolution of vulnerability-relevant code across the history. It reasons over the resulting revision history, using temporal edges to preserve correspondences between program elements across consecutive revisions, and directly ranks candidate commits according to their contribution to the vulnerable condition. Ablation results show that modeling the full revision history improves F2 from 0.637 to 0.814. TraceVIC improves F2 by up to 28.7% over state-of-the-art methods and identifies a valid VIC for 78 of 79 vulnerabilities across four unseen C/C++ projects.

0.08

GitCF: Reducing Incomplete Changes by Exploiting Multiple Similarities Among Commits

cs.SE ·2026-09-29 ·Yuto Kitabayashi, Takashi Kobayashi
code/data similarity 0.54
Abstract

Software developers often struggle to identify all locations that their changes affect, and incomplete changes frequently result from these omissions. To mitigate this problem, several approaches have been proposed to recommend additional locations that should be modified together with a developer's current change. A large class of these techniques mines co-change rules from repository revision histories, but because they rely solely on which elements have been modified together, they cannot recommend elements that have rarely co-changed, and they disregard the textual information that accompanies commits. A second class of techniques does exploit textual information, but it derives it from the source code or from a change request rather than from commit history, and it does not use the developer's current change as its input. To address these limitations, we propose GitCF, a change recommendation method that compares a developer's current change with past changes in the revision history and recommends additional change locations by combining two sources of similarity: the set of modified elements and the textual content of commits, including commit messages, code diffs, and linked issue descriptions. We evaluate GitCF on 543 incomplete changes from 17 open-source projects, where an incomplete change denotes a commit in which an omitted modification is supplied in a later commit, comparing it against three co-change-rule-based techniques. GitCF outperforms the strongest baseline on all five metrics (MAP, Recall@10, Recall@20, Hit@10, and Hit@20); in particular, it raises Hit@10 from 0.322 to 0.403, and the improvement in average precision is statistically significant.

0.16

MergirafSemi: A Language-Agnostic Semistructured Merge Tool

cs.SE ·2026-08-11 ·Pedro Lopes, Paulo Borba, Paola Accioly, Guilherme Cavalcanti
similarity 0.53
Abstract · 11 pages, 4 tables, and 5 figures

Developers frequently face merge conflicts when integrating concurrent changes. Most merge tools rely on unstructured, line-based comparisons, often producing spurious conflicts and missing actual conflicts. To address these limitations, structure-aware merge tools have been proposed, which leverage syntactic representations to improve merge accuracy. However, fully structured tools may incur higher computational cost, and language-specific tools require significant development and maintenance effort. To balance these trade-offs, we propose MergirafSemi, a language-agnostic semistructured merge tool that captures structural information without requiring full structural modeling or language-specific implementations, and applies line-based merging within specific program regions, such as method bodies in Java. Our tool leverages lightweight Concrete Syntax Trees to guide merging decisions while preserving flexibility and efficiency across languages. We evaluate our tool through an empirical study on real-world merge scenarios across multiple programming languages, comparing it with unstructured, semistructured, and structured tools. Our results show that increasing structural granularity improves automatic conflict resolution but can also lead to more aggressive merge decisions, increasing the number of missed actual conflicts. In contrast, MergirafSemi achieves a more balanced trade-off, reducing spurious conflicts while maintaining competitive accuracy and better runtime performance in most common scenarios. Compared to an unstructured tool, it substantially reduces spurious conflicts, and when compared to a semistructured language-specific tool, it achieves comparable effectiveness while exhibiting more robust execution behavior and significantly lower runtime overhead.

0.10

Fast and Theoretically-Efficient Batch-Parallel Link-Cut Trees, Euler Tour Trees, and Treaps

cs.DS ·2026-09-13 ·Quinten De Man, Laxman Dhulipala
published similarity 0.53
Abstract

Parallel batch-dynamic trees are a fundamental building block in recent theoretical and practical advances in dynamic graph algorithms. However, all existing parallel batch-dynamic tree data structures, including Euler tour trees, UFO trees, topology trees, and rake-compress trees, are all significantly outperformed in the sequential setting by link-cut trees, which have been the sequential state-of-the-art for over 40 years. Despite their excellent performance in the sequential setting, designing efficient batch-parallel link-cut trees has remained a major open problem. In this paper, we close this gap by introducing MOJOS, a unified framework for theoretically- and practically-efficient parallel batch-dynamic trees. We exploit the fact that both Euler tour trees and link-cut trees rely on a common dynamic sequence abstraction that supports splitting and joining. We introduce a new batch-dynamic sequence built using treaps that achieves optimal work and depth, and outperforms existing parallel skip list and treap implementations for batch updates, queries, and memory usage. With MOJOS, we develop a new batch-parallel Euler tour tree algorithm that outperforms prior batch-dynamic tree implementations supporting subtree queries. Unlike prior batch-parallel Euler tour trees which rely on skip list's ability to represent cyclic sequences, MOJOS allows any batch-dynamic sequence data structure to be used as a drop-in replacement. Finally, we develop the first theoretically-efficient batch-parallel link-cut tree, which is also the first batch-dynamic data structure supporting path queries to achieve $O(\log n)$ depth for batch updates in the binary-forking model. Our link-cut tree implementation outperforms all known parallel batch-dynamic tree data structures supporting path queries.

0.29

Beyond Vector Similarity: Hierarchical Context-Aware Graph RAG vs Standard RAG in Enterprise Code Migration

cs.AI ·2026-09-11 ·Nilesh Jaiswal, Aniket Agrawal, Arjit Shukla, Divya Malhotra, Saurabh Garg +2 more
similarity 0.53
Abstract · 11 pages, 2 images, 3 tables

As enterprises modernize legacy monolithic systems to microservices, Large Language Models (LLMs) are heavily utilized for automated code translation. However, traditional vector-based Retrieval-Augmented Generation (Standard RAG) struggles to capture topological relationships. It fetches isolated chunks that sever inheritance chains, leading to high compilation failure rates. This paper introduces a Hierarchical Context-Resident Graph (HCRG) methodology to resolve these limitations. Our pipeline uses tree-sitter for Abstract Syntax Tree (AST) extraction, maps architectural edges into a Google Cloud Spanner Property Graph, and serializes this structure into a Gemini Context Cache for topological, parent-first code translation. We shift evaluation from naive text-overlap to a custom 7-metric Software Engineering framework. Traditional metrics like CodeBLEU (which scored 91% for both methods) effectively masked Standard RAG's structural failures behind syntactically plausible but broken code. Empirically, Graph RAG decisively mitigates dependency loss: API hallucination rates dropped from 56.4% to 16.2%, Dependency Resolution Quality improved from 34.8% to 65.9%, and Parent-Child Consistency rose from 26.7% to 45.5%. However, Graph RAG introduces specific trade-offs. The dense global context causes defensive over-engineering by the LLM, reducing Cyclomatic Complexity Consistency from 71.6% to 46.7%, and slightly degrades Docstring Preservation (67.0% to 61.0%). Ultimately, while trading code complexity for reduced hallucinations, Graph RAG provides a substantially more viable, architecturally sound path for automated enterprise codebase modernization.

0.21