bluuebunny/crossref_metadata_2025 huggingface dataset:
Protocol of the Nurses’ Mental Health Study (NMHS): a nationwide hospital multicentre prospective cohort study
Authors: Ning Meng , Li Xuting , Chen Zengyu , Yang Jiaxin , Yu Qiang , Huang Chongmei , Chen Yamin , Tian Yusheng , Li Ya-Min , Xiao Shuiyuan
Published: February 2025

Introduction

Due to high workload, shift work and shortage of human resources, nurses are vulnerable to various mental health problems which are significantly related to their physical health, patient safety and healthcare quality. The long-term monitoring of nurses’ mental health and identifying its risk factors are necessary. Accounting for more than one-fifth of global nurses, Chinese nurses have a demanding healthcare workload, especially in tertiary hospitals, yet there is no national cohort concerning their mental health and associated factors. This study (Nurses’ Mental Health Study, NMHS) aims to investigate the mental health of Chinese nurses in tertiary hospitals and to identify the risk and protective factors.

Methods and analysis

NMHS is a multicentre prospective cohort study which plans to recruit at least 30 000 registered nurses from 62 tertiary hospitals using the cluster sampling method. Baseline data collection will be implemented through online questionnaires after obtaining informed consent from each participant. Variables including sociodemographic information, work-related factors, health status, lifestyle habits, objective experiences, family and social relations, current affairs opinions and overall evaluation will be collected. Annual follow-up will be conducted via a questionnaire link to monitor subsequent changes in nurses’ mental health and related factors.

Patient and public involvement statement

No patient and public involvement in the study design.

Ethics and dissemination

This study was approved by the Institute Review Board from the ethical committee of The Second Xiangya Hospital of Central South University (E20230048) and NMHS will be performed in line with Helsinki Declarations. The results of NMHS will inform nursing research and practice by providing evidence to nurse managers, healthcare organisations and the government about the target mental health outcomes for early prevention and intervention.

Trial registration number

This study has been registered at the Chinese Clinical Trail Registry (ID: ChiCTR2300072142,https://www.chictr.org.cn/showproj.html?proj=192676).
Perturbations in $$\textbf{O}(D,D)$$ string cosmology from double field theory
Authors: Angus Stephen , Mukohyama Shinji
Published: February 2025

The low-energy limit of string theory contains additional gravitational degrees of freedom, a skew-symmetric tensor B-field and a scalar dilaton, that are not present in general relativity. Together with the metric, these three fields are naturally embedded in the

$$\textbf{O}(D,D)$$

O
(
D
,
D
)

-symmetric framework of double field theory. The

$$\textbf{O}(D,D)$$

O
(
D
,
D
)

symmetry uniquely prescribes the interactions between the extended gravitational sector and other matter, leading to novel features beyond conventional string cosmology. In this work we present the equations of motion for linear perturbations around

$$\textbf{O}(D,D)$$

O
(
D
,
D
)

string cosmological backgrounds in

$$D=4$$

D
=
4

under a scalar-vector-tensor decomposition. We obtain analytic solutions in the superhorizon limit for scalar perturbations around various homogeneous and isotropic background solutions, including some candidate models for bouncing cosmologies. The generalized energy–momentum tensor includes source terms for the B-field and dilaton, and we show how the resulting generalized conservation laws modify the conditions for conservation of curvature perturbations.
PACMMOD V3, N1 (SIGMOD), February 2025: Editorial
Authors: Abouzied Azza , Hellerstein Joseph M. , Agrawal Divyakant
Published: February 2025

The Proceedings of the ACM on Management of Data (PACMMOD) is concerned with the principles, algorithms, techniques, systems, and applications of database management systems, data management technology, and science and engineering of data. It includes articles reporting cutting-edge data management, data engineering, and data science research.

We are pleased to present the 1st issue of Volume 3 of PACMMOD. This issue contains papers that were submitted to the SIGMOD research track in July 2024.

Papers accepted in this issue are part of the pool of presentation candidates in the research track of the ACM SIGMOD Conference on Management of Data 2025, to be held in Berlin, Germany.
λ-Tune: Harnessing Large Language Models for Automated Database System Tuning
Authors: Giannakouris Victor , Trummer Immanuel
Published: February 2025

We introduce λ-Tune, a framework that leverages Large Language Models (LLMs) for automated database system tuning. The design of λ-Tune is motivated by the capabilities of the latest generation of LLMs. Different from prior work, leveraging LLMs to extract tuning hints for single parameters, λ-Tune generates entire configuration scripts, based on a large input document, describing the tuning context. λ-Tune generates alternative configurations, using a principled approach to identify the best configuration, out of a small set of candidates. In doing so, it minimizes reconfiguration overheads and ensures that evaluation costs are bounded as a function of the optimal run time. By treating prompt generation as a cost-based optimization problem, λ-Tune conveys the most relevant context to the LLM while bounding the number of input tokens and, therefore, monetary fees for LLM invocations. We compare λ-Tune to various baselines, using multiple benchmarks and PostgreSQL and MySQL as target systems for tuning, showing that λ-Tune is significantly more robust than prior approaches.
A Local Search Approach to Efficient (
k,p
)-Core Maintenance
Authors: Zhang Chenghan , Zhu Yuanyuan , Chang Lijun
Published: February 2025

The ((
k,p
))-core model was recently proposed to capture engagement dynamics by considering both intra-community interactions (i.e., the
k
-core structure) and inter-community interactions (i.e., the
p
-fraction property). It is a refinement of the classic
k
-core, by introducing an extra parameter
p
to customize the engagement within a community at a finer granularity. In this paper, we study the problem of maintaining all (k,p)-cores (essentially, maintaining the p-numbers for all vertices) for dynamic graphs. The existing Global approach conducts a global peeling, almost from scratch, for all vertices whose old p-numbers are within a computed range [p
-
,p
+
], and thus is inefficient. We propose a new Local approach which conducts local searches starting from the two end-points of the newly inserted or deleted edge, and then iteratively expands the search frontier by including their neighbors. Our algorithm is designed based on several fundamental properties that we prove in this paper to characterize the necessary condition for a vertex's p-number to change. Compared to Global, our Local approach implicitly obtains the optimal affected p-number range [p
-
*
,p
+
*
] ⊆ [p
-
,p
+
], and further skips many vertices whose p-numbers are within this range. Experimental results show that Local is on average two orders of magnitude faster than Global.
B-Trees Are Back: Engineering Fast and Pageable Node Layouts
Authors: Müller Marcus , Benson Lawrence , Leis Viktor
Published: February 2025

Large main memory capacity and even larger data sets have motivated hybrid storage systems, which serve most transactions from memory, but can seamlessly transition to flash storage. In such systems, the data structure of choice is usually a B-Tree with pageable nodes. Most academic B-Tree work considers only fixed size records, making them unsuitable for most practical applications. Given the prevalence of B-Trees, surprisingly few available implementations and benchmarks of optimized B-Trees cover variable-sized records. In this paper, we describe an efficient B-Tree implementation supporting variable-sized records containing six known node layout optimizations. We evaluate each optimization to guide future implementations, and propose an optimized adaptive layout that can even compete with pure in-memory structures for many workloads. Our results show that well-engineered B-Trees can efficiently handle both in-memory and out-of-memory workloads.
Computing Approximate Graph Edit Distance via Optimal Transport
Authors: Cheng Qihao , Yan Da , Wu Tianhao , Huang Zhongyi , Zhang Qin
Published: February 2025

Given a graph pair (G
1
, G
2
), graph edit distance (GED) is defined as the minimum number of edit operations converting G
1
to G
2
. GED is a fundamental operation widely used in many applications, but its exact computation is NP-hard, so the approximation of GED has gained a lot of attention. Data-driven learning-based methods have been found to provide superior results compared to classical approximate algorithms, but they directly fit the coupling relationship between a pair of vertices from their vertex features. We argue that while pairwise vertex features can capture the coupling cost (discrepancy) of a pair of vertices, the vertex coupling matrix should be derived from the vertex-pair cost matrix through a more well-established method that is aware of the global context of the graph pair, such as optimal transport. In this paper, we propose an ensemble approach that integrates a supervised learning-based method and an unsupervised method, both based on optimal transport. Our learning method, GEDIOT, is based on inverse optimal transport that leverages a learnable Sinkhorn algorithm to generate the coupling matrix. Our unsupervised method, GEDGW, models GED computation as a linear combination of optimal transport and its variant, Gromov-Wasserstein discrepancy, for node and edge operations, respectively, which can be solved efficiently without needing the ground truth. Our ensemble method, GEDHOT, combines GEDIOT and GEDGW to further boost the performance. Extensive experiments demonstrate that our methods significantly outperform the existing methods in terms of the performance of GED computation, edit path generation, and model generalizability.
Data Chunk Compaction in Vectorized Execution
Authors: Qiao Yiming , Zhang Huanchen
Published: February 2025

Modern analytical database management systems often adopt vectorized query execution engines that process columnar data in batches (i.e., data chunks) to minimize the interpretation overhead and improve CPU parallelism. However, certain database operators, especially hash joins, can drastically reduce the number of valid entries in a data chunk, resulting in numerous small chunks in an execution pipeline. These small chunks cannot fully enjoy the benefits of vectorized query execution, causing significant performance degradation. The key research question is when and how to compact these small data chunks during query execution. In this paper, we first model the chunk compaction problem and analyze the trade-offs between different compaction strategies. We then propose a learning-based algorithm that can adjust the compaction threshold dynamically at run time. To answer the ''how'' question, we propose a compaction method for the hash join operator, called logical compaction, that minimizes data movements when compacting data chunks. We implemented the proposed techniques in the state-of-the-art DuckDB and observed up to 63% speedup when evaluated using the Join Order Benchmark, TPC-H, and TPC-DS.
Dialogue Benchmark Generation from Knowledge Graphs with Cost-Effective Retrieval-Augmented LLMs
Authors: Omar Reham , Mangukiya Omij , Mansour Essam
Published: February 2025

Dialogue benchmarks are crucial in training and evaluating chatbots engaging in domain-specific conversations. Knowledge graphs (KGs) represent semantically rich and well-organized data spanning various domains, such as DBLP, DBpedia, and YAGO. Traditionally, dialogue benchmarks have been manually created from documents, neglecting the potential of KGs in automating this process. Some question-answering benchmarks are automatically generated using extensive preprocessing from KGs, but they do not support dialogue generation. This paper introduces Chatty-Gen, a novel multi-stage retrieval-augmented generation platform for automatically generating high-quality dialogue benchmarks tailored to a specific domain using a KG. Chatty-Gen decomposes the generation process into manageable stages and uses assertion rules for automatic validation between stages. Our approach enables control over intermediate results to prevent time-consuming restarts due to hallucinations. It also reduces reliance on costly and more powerful commercial LLMs. Chatty-Gen eliminates upfront processing of the entire KG using efficient query-based retrieval to find representative subgraphs based on the dialogue context. Our experiments with several real and large KGs demonstrate that C
hatty
-G
en
significantly outperforms state-of-the-art systems and ensures consistent model and system performance across multiple LLMs of diverse capabilities, such as GPT-4o, Gemini 1.5, Llama 3, and Mistral.
DISCES: Systematic Discovery of Event Stream Queries
Authors: Sattler Rebecca , Kleest-Meißner Sarah , Lange Steven , Schmid Markus L. , Schweikardt Nicole , Weidlich Matthias
Published: February 2025

The continuous evaluation of queries over an event stream provides the foundation for reactive applications in various domains. Yet, knowledge of queries that detect distinguished event patterns that are potential causes of the situation of interest is often not directly available. However, given a database of finite, historic (sub-)streams that have been gathered whenever a situation of interest was observed, one may aim at automatic discovery of the respective queries. Existing algorithms for event query discovery incorporate ad-hoc design choices, though, and it is unclear how their suitability for a database shall be assessed.

In this paper, we address this gap with DISCES, an algorithmic framework for event query discovery. DISCES outlines a design space for discovery algorithms, thereby making the design choices explicit. We instantiate the framework to derive four specific algorithms, which all yield correct and complete results, but differ in their runtime sensitivity. We therefore also provide guidance on how to select one of the algorithms for a given database based on a few of its essential properties. Our experiments using simulated and real-world data illustrate that our algorithms are indeed tailored to databases showing certain properties and solve the query discovery problem several orders of magnitude faster than existing approaches.
Disco: A Compact Index for LSM-trees
Authors: Zhong Wenshao , Chen Chen , Wu Xingbo , Eriksson Jakob
Published: February 2025

Many key-value stores and database systems use log-structured merge-trees (LSM-trees) as their storage engines because of their excellent write performance. However, the read performance of LSM-trees is suboptimal due to the overlapping sorted runs. Most existing efforts rely on filters to reduce unnecessary I/Os, but filters fundamentally do not help locate items and often become the bottleneck of the system. We identify that the lack of efficient index is the root cause of subpar read performance in LSM-trees. In this paper, we propose Disco: a compact index for LSM-trees. Disco indexes all the keys in an LSM-tree, so a query does not have to search every run of the LSM-tree. It records compact key representations to minimize the number of key comparisons so as to minimize cache misses and I/Os for both point and range queries. Disco guarantees that both point queries and seeks issue at most one I/O to the underlying runs, achieving an I/O efficiency close to a B
+
-tree. Disco improves upon REMIX's pioneering multi-run index design with additional compact key representations to help improve read performance. The representations are compact so the cost of persisting Disco to disk is small. Moreover, while a traditional LSM-tree has to choose a more aggressive compaction policy that slows down write performance to have better read performance, a Disco-indexed LSM-tree can employ a write-efficient policy and still have good read performance. Experimental results show that Disco can save I/Os and improve point and range query performance by up to 220% over RocksDB while maintaining efficient writes.
Efficient Maximum
s
-Bundle Search via Local Vertex Connectivity
Authors: Liu Yang , Huang Hejiao , Yu Kaiqiang , Liu Shengxin , Long Cheng
Published: February 2025

The
s
-bundle, as a cohesive subgraph model which relaxes the clique, remains connected whenever fewer than
n-s
vertices are removed, where
n
is the number of vertices inside. Finding the largest
s
-bundle is a fundamental problem and has diverse applications in various fields such as social network analysis, graph visualization, and bioinformatics. Existing studies for solving the problem follow the same branch-and-bound framework and improve the efficiency by developing pruning techniques. As a result, all share the same worst-case time complexity of
O*
(2

n

), where
O*
suppresses the polynomial factors. In this paper, we propose a new branch-and-bound algorithm, called SymBD, which achieves improved theoretical guarantees and practical performance. It adopts the existing Symmetric-BK branching strategy whose performance highly depends on the ordering of vertices. We explore various vertex orderings for improving the performance. In particular, we propose two novel vertex orderings based on the local vertex connectivity. With the proposed vertex orderings, SymBD improves the worst-case time complexity to
O*
(λ

n
s

) where λ

s

is strictly less than 2. To further boost the practical efficiency, we introduce a heuristic algorithm for computing a large initial solution and a divide-and-conquer strategy. Extensive experiments on 664 graphs demonstrate that our algorithm is up to five orders of magnitude faster than existing solutions.
Efficiently Counting Triangles in Large Temporal Graphs
Authors: Xia Yuyang , Fang Yixiang , Luo Wensheng
Published: February 2025

In many real-world applications (e.g., email networks, social networks, and phone call networks), the relationships between entities can be modeled as a temporal graph, in which each edge is associated with a timestamp representing the interaction time. As a fundamental task in temporal graph analysis, triangle counting has received much attention, and several triangle models have been developed, including δ-temporal triangle, sliding-window triangle, and (δ
1,3
, δ
1,2
, δ
2,3
)-temporal triangle. In particular, the δ-temporal triangle, requiring the gap of timestamps of any two edges within it to be bounded by a threshold δ, has been demonstrated effective in many real applications, such as cohesiveness analysis, transitivity, clustering coefficient, and graph classification. In this paper, we study fast algorithms for counting δ-temporal triangles in a given query time window. We first propose an online algorithm, which enumerates all edges in the graph and for each edge, calculates how many δ-temporal triangles end with the edge. We further develop an efficient index-based solution, which maps δ-temporal triangles into points of the 2-dimensional space and further compactly organizes these points using hierarchical structures. Besides, we study the problem of binary δ-temporal triangle counting by considering the existence of δ-temporal triangle among three vertices. Experiments on large temporal graphs show that our online algorithm is up to 70× faster than the state-of-the-art algorithm, and our index-based algorithm is up to 10
8
× faster than the online algorithm.
FastPDB: Towards Bag-Probabilistic Queries at Interactive Speeds
Authors: Huber Aaron , Kennedy Oliver , Rudra Atri , Zhao Zhuoyue , Feng Su , Glavic Boris
Published: February 2025

Probabilistic databases (PDBs) provide users with a principled way to query data that is incomplete or imprecise. In this work, we study computing expected multiplicities of query results over probabilistic databases under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. We employ concepts from fine-grained complexity to demonstrate that exact bag probabilistic query processing is fundamentally less efficient than deterministic bag query evaluation, but that fast approximations are possible by sampling monomials from a circuit representation of a result tuple's lineage. A remaining issue, however, is that constructing such circuits, while in PTIME, can nonetheless have significant overhead. To avoid this cost, we utilize approximate query processing techniques to directly sample monomials without materializing lineage upfront. Our implementation in
FastPDB
provides accurate anytime approximation of probabilistic query answers and scales to datasets orders of magnitude larger than competing methods.
Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art
Authors: Azizi Ilias , Echihabi Karima , Palpanas Themis
Published: February 2025

Vector data is prevalent across business and scientific applications, and its popularity is growing with the proliferation of learned embeddings. Vector data collections often reach billions of vectors with thousands of dimensions, thus, increasing the complexity of their analysis. Vector search is the backbone of many critical analytical tasks, and graph-based methods have become the best choice for analytical tasks that do not require guarantees on the quality of the answers. We briefly survey in-memory graph-based vector search, outline the chronology of the different methods and classify them according to five main design paradigms: seed selection, incremental insertion, neighborhood propagation, neighborhood diversification, and divide-and-conquer. We conduct an exhaustive experimental evaluation of twelve state-of-the-art methods on seven real data collections, with sizes up to 1 billion vectors. We share key insights about the strengths and limitations of these methods; e.g., the best approaches are typically based on incremental insertion and neighborhood diversification, and the choice of the base graph can hurt scalability. Finally, we discuss open research directions, such as the importance of devising more sophisticated data-adaptive seed selection and diversification strategies.
H-Rocks: CPU-GPU accelerated Heterogeneous RocksDB on Persistent Memory
Authors: Pandey Shweta , Basu Arkaprava
Published: February 2025

Persistent key-value stores (pKVS) such as RocksDB are critical to many internet-scale services. Recent works leveraged persistent memory (PM) to improve pKVS throughput. However, they are typically limited to CPUs.

We develop H-Rocks to judiciously leverage both the CPU and the Graphics Processing Unit (GPU) for accelerating a wide range of RocksDB operations. H-Rocks selectively accelerates performance-critical parts of RocksDB on the GPU. It uses operation sub-batching and key-value versioning to leverage GPU's parallelism while maintaining compatibility with RocksDB. It harnesses GPU's high-bandwidth memory while limiting data movement between the CPU and GPU. In YCSB workloads, H-Rocks outperforms CPU-based pKVSs like Viper, Plush, and pmem-RocksDB by 3-18×.
LCP: Enhancing Scientific Data Management with

L

ossy

C

ompression for

P

articles
Authors: Zhang Longtao , Li Ruoyu , Ren Congrong , Di Sheng , Liu Jinyang , Huang Jiajun , Underwood Robert , Grosset Pascal , Tao Dingwen , Liang Xin , Guo Hanqi , Cappello Franck , Zhao Kai
Published: February 2025

Many scientific applications opt for particles instead of meshes as their basic primitives to model complex systems composed of billions of discrete entities. Such applications span a diverse array of scientific domains, including molecular dynamics, cosmology, computational fluid dynamics, and geology. The scale of the particles in those scientific applications increases substantially thanks to the ever-increasing computational power in high-performance computing (HPC) platforms. However, the actual gains from such increases are often undercut by obstacles in data management systems related to data storage, transfer, and processing. Lossy compression has been widely recognized as a promising solution to enhance scientific data management systems regarding such challenges, although most existing compression solutions are tailored for Cartesian grids and thus have sub-optimal results on discrete particle data. In this paper, we introduce LCP, an innovative lossy compressor designed for particle datasets, offering superior compression quality and higher speed than existing compression solutions. Specifically, our contribution is threefold. (1) We propose LCP-S, an error-bound aware block-wise spatial compressor to efficiently reduce particle data size while satisfying the pre-defined error criteria. This approach is universally applicable to particle data across various domains, eliminating the need for reliance on specific application domain characteristics. (2) We develop LCP, a hybrid compression solution for multi-frame particle data, featuring dynamic method selection and parameter optimization. It aims to maximize compression effectiveness while preserving data quality as much as possible by utilizing both spatial and temporal domains. (3) We evaluate our solution alongside eight state-of-the-art alternatives on eight real-world particle datasets from seven distinct domains. The results demonstrate that our solution achieves up to 104% improvement in compression ratios and up to 593% increase in speed compared to the second-best option, under the same error criteria.
LeaFi: Data Series Indexes on Steroids with Learned Filters
Authors: Wang Qitong , Ileana Ioana , Palpanas Themis
Published: February 2025

The ever-growing collections of data series create a pressing need for efficient similarity search, which serves as the backbone for various analytics pipelines. Recent studies have shown that tree-based series indexes excel in many scenarios. However, we observe a significant waste of effort during search, due to suboptimal pruning. To address this issue, we introduce LeaFi, a novel framework that uses machine learning models to boost pruning effectiveness of tree-based data series indexes. These models act as learned filters, which predict tight node-wise distance lower bounds that are used to make pruning decisions, thus, improving pruning effectiveness. We describe the LeaFi-enhanced index building algorithm, which selects leaf nodes and generates training data to insert and train machine learning models, as well as the LeaFi-enhanced search algorithm, which calibrates learned filters at query time to support the user-defined quality target of each query. Our experimental evaluation, using two different tree-based series indexes and five diverse datasets, demonstrates the advantages of the proposed approach. LeaFi-enhanced data-series indexes improve pruning ratio by up to 20x and search time by up to 32x, while maintaining a target recall of 99%.
MAST: Towards Efficient Analytical Query Processing on Point Cloud Data
Authors: Li Jiangneng , Yuan Haitao , Cong Gao , Kiah Han Mao , Zhang Shuhao
Published: February 2025

The proliferation of 3D scanning technology, particularly within autonomous driving, has led to an exponential increase in the volume of Point Cloud (PC) data. Given the rich semantic information contained in PC data, deep learning models are commonly employed for tasks such as object queries. However, current query systems that support PC data types do not process queries on semantic information. Consequently, there is a notable gap in research regarding the efficiency of invoking deep models for each PC data query, especially when dealing with large-scale models and datasets. To address this issue, this work aims to design an efficient approximate approach for supporting PC analysis queries, including PC retrieval and aggregate queries. In particular, we propose a novel framework that delivers approximate query results efficiently by sampling core PC frames within a constrained budget, thereby minimizing the reliance on deep learning models. This framework is underpinned by rigorous theoretical analysis, providing error-bound guarantees for the approximate results if the sampling policy is preferred. To achieve this, we incorporate a multi-agent reinforcement learning-based approach to optimize the sampling procedure, along with an innovative reward design leveraging spatio-temporal PC analysis. Furthermore, we exploit the spatio-temporal characteristics inherent in PC data to construct an index that accelerates the query process. Extensive experimental evaluations demonstrate that our proposed method, MAST, not only achieves accurate approximate query results but also maintains low query latency, ensuring high efficiency.
Modyn: Data-Centric Machine Learning Pipeline Orchestration
Authors: Böther Maximilian , Robroek Ties , Gsteiger Viktor , Holzinger Robin , Ma Xianzhe , Tözün Pınar , Klimovic Ana
Published: February 2025

In real-world machine learning (ML) pipelines, datasets are continuously growing. Models must incorporate this new training data to improve generalization and adapt to potential distribution shifts. The cost of model retraining is proportional to how frequently the model is retrained and how much data it is trained on, which makes the naive approach of retraining from scratch each time impractical. We present Modyn, a data-centric end-to-end machine learning platform. Modyn's ML pipeline abstraction enables users to declaratively describe policies for continuously training a model on a growing dataset. Modyn pipelines allow users to apply data selection policies (to reduce the number of data points) and triggering policies (to reduce the number of trainings). Modyn executes and orchestrates these continuous ML training pipelines. The system is open-source and comes with an ecosystem of benchmark datasets, models, and tooling. We formally discuss how to measure the performance of ML pipelines by introducing the concept of composite models, enabling fair comparison of pipelines with different data selection and triggering policies. We empirically analyze how various data selection and triggering policies impact model accuracy, and also show that Modyn enables high throughput training with sample-level data selection.
Parallel kd-tree with Batch Updates
Authors: Men Ziyang , Shen Zheqi , Gu Yan , Sun Yihan
Published: February 2025

The kd-tree is one of the most widely used data structures to manage multi-dimensional data. Due to the ever-growing data volume, it is imperative to consider parallelism in kd-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates.

The goal of this paper is to develop efficient in-memory kd-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel kd-tree), a parallel kd-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including
k
-nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree.

We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel kd-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code.
QURE: AI-Assisted and Automatically Verified UDF Inlining
Authors: Siddiqui Tarique , König Arnd Christian , Cao Jiashen , Yan Cong , Lahiri Shuvendu K.
Published: February 2025

User-defined functions (UDFs) extend the capabilities of SQL by improving code reusability and encapsulating complex logic, but can hinder the performance due to optimization and execution inefficiencies. Prior approaches attempt to address this by rewriting UDFs into native SQL, which is then inlined into the SQL queries that invoke them. However, these approaches are either limited to simple pattern matching or require the synthesis of complex verification conditions from procedural code, a process that is brittle and difficult to automate. This limits coverage and makes the translation approaches less extensible to previously unseen procedural constructs. In this work, we present QURE, a framework that (1) leverages large language models (LLMs) to translate UDFs to native SQL, and (2) introduces a novel formal verification method to establish equivalence between the UDF and its translation. QURE uses the semantics of SQL operators to automate the derivation of verification conditions, in turn resulting in broad coverage and high extensibility. We model a large set of imperative constructs, particularly those common in Python and Pandas UDFs, in an intermediate verification language, allowing for the verification of their SQL translation. In our empirical evaluation of Python and Pandas UDFs, equivalence is successfully verified for 88% of UDF-SQL pairs (the rest lack semantically-equivalent SQLs) and LLMs correctly translate 84% of the UDFs. Executing the translated UDFs achieves median performance improvements of 23x on single-node clusters and 12x on 12-node clusters compared to the original UDFs, while also significantly reducing out-of-memory errors.
Rapid Data Ingestion through DB-OS Co-design
Authors: Lim Kyungmin , Yoon Minseok , Kim Kihwan , Fekete Alan David , Jung Hyungsoo
Published: February 2025

Sequential data access for the rapid ingestion of large fact tables from storage is a pivotal yet resource-intensive operation in data warehouse systems, consuming substantial CPU cycles across various components of DBMSs and operating systems. Although bypassing these layers can eliminate access latency, concurrent access to the same table often results in redundant data fetching due to cache-bypassing data transfers. Thus, a new design for data access control is necessary to enhance rapid data ingestion in databases. To address this concern, we propose a novel DB-OS co-design that efficiently supports sequential data access at full device speed. Our approach, zicIO, liberates DBMSs from data access control by preparing required data just before DBMSs access it, while alleviating all known I/O latencies. The core of zicIO lies in its DB-OS co-design, which aims to (1) automate data access control and (2) relieve redundant data fetching through seamless collaboration between the DB and the OS. We implemented zicIO and integrated it with four databases to demonstrate its general applicability. The evaluation showed performance enhancements of up to 9.95x under TPC-H loads.
Reliable Text-to-SQL with Adaptive Abstention
Authors: Chen Kaiwen , Chen Yueting , Koudas Nick , Yu Xiaohui
Published: February 2025

Large language models (LLMs) have revolutionized natural language interfaces for databases, particularly in text-to-SQL conversion. However, current approaches often generate unreliable outputs when faced with ambiguity or insufficient context.

We present Reliable Text-to-SQL (RTS), a novel framework that enhances query generation reliability by incorporating abstention and human-in-the-loop mechanisms. RTS focuses on the critical schema linking phase, which aims to identify the key database elements needed for generating SQL queries. It autonomously detects potential errors during the answer generation process and responds by either abstaining or engaging in user interaction. A vital component of RTS is the Branching Point Prediction (BPP) which utilizes statistical conformal techniques on the hidden layers of the LLM model for schema linking, providing probabilistic guarantees on schema linking accuracy.

We validate our approach through comprehensive experiments on the BIRD benchmark, demonstrating significant improvements in robustness and reliability. Our findings highlight the potential of combining transparent-box LLMs with human-in-the-loop processes to create more robust natural language interfaces for databases. For the BIRD benchmark, our approach achieves near-perfect schema linking accuracy, autonomously involving a human when needed. Combined with query generation, we demonstrate that near-perfect schema linking and a small query generation model can almost match SOTA accuracy achieved with a model orders of magnitude larger than the one we use.
Revisiting the Design of In-Memory Dynamic Graph Storage
Authors: Su Jixian , Hao Chiyu , Sun Shixuan , Zhang Hao , Gao Sen , Jiang Jiaxin , Chen Yao , Zhang Chenyi , He Bingsheng , Guo Minyi
Published: February 2025

The effectiveness of in-memory dynamic graph storage (DGS) for supporting concurrent graph read and write queries is crucial for real-time graph analytics and updates. Various methods have been proposed, for example, LLAMA, Aspen, LiveGraph, Teseo, and Sortledton. These approaches differ significantly in their support for read and write operations, space overhead, and concurrency control. However, there has been no systematic study to explore the trade-offs among these dimensions. In this paper, we evaluate the effectiveness of individual techniques and identify the performance factors affecting these storage methods by proposing a common abstraction for DGS design and implementing a generic test framework based on this abstraction. Our findings highlight several key insights: 1) Existing DGS methods exhibit substantial space overhead. For example, Aspen consumes 3.3-10.8x more memory than CSR, while the optimal fine-grained methods consume 4.1-8.9x more memory than CSR, indicating a significant memory overhead. 2) Existing methods often overlook memory access impact of modern architectures, leading to performance degradation compared to continuous storage methods. 3) Fine-grained concurrency control methods, in particular, suffer from severe efficiency and space issues due to maintaining versions and performing checks for each neighbor. These methods also experience significant contention on high-degree vertices. Our systematic study reveals these performance bottlenecks and outlines future directions to improve DGS for real-time graph analytics.
SecureXGB: A Secure and Efficient Multi-party Protocol for Vertical Federated XGBoost
Authors: Han Zongda , Cheng Xiang , Zhao Wenhong , Fu Jiaxin , He Zhaofeng , Su Sen
Published: February 2025

Extreme Gradient Boosting (XGBoost) demonstrates excellent performance in practice and is widely used in both industry and academic research. This extensive application has led to a growing interest in employing multi-party data to develop more robust XGBoost models. In response to increasing concerns about privacy leakage, secure vertical federated XGBoost is proposed. It employs secure multi-party computation techniques, such as secret sharing (SS), to allow multiple parties holding vertically partitioned data, i.e., disjoint features on the same samples, to collaborate in constructing an XGBoost model. However, the running efficiency is the primary obstacle to the practical application of existing protocols, especially in multi-party settings. The reason is that these protocols not only require the execution of data-oblivious computations to protect intermediate results, leading to high computational complexity, but also involve a large number of SS-based non-linear operations with high overheads, e.g., division operations in gain score calculation and comparison operations in best split selection. To this end, we present a secure and efficient multi-party protocol for vertical federated XGBoost, called SecureXGB, which can perform the collaborative training of an XGBoost model in an SS-friendly manner. In SecureXGB, we first propose a parallelizable multi-party permutation method, which can secretly and efficiently permute all samples before model training to reduce the reliance on data-oblivious computations. Then, we design a linear gain score that can be evaluated without involving division operations and has equivalent utility to the original gain score. Finally, we develop a synchronous best split selection method to secretly identify the best split with the maximum gain score using a minimal number of comparison operations. Experimental results demonstrate that SecureXGB can achieve better training efficiency than state-of-the-art protocols without the loss of model accuracy.
Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search
Authors: Wei Jiuqi , Lee Xiaodong , Liao Zhenyu , Palpanas Themis , Peng Botao
Published: February 2025

Approximate Nearest Neighbor (ANN) search in high-dimensional Euclidean spaces is a fundamental problem with a wide range of applications. However, there is currently no ANN method that performs well in both indexing and query answering performance, while providing rigorous theoretical guarantees for the quality of the answers. In this paper, we first design SC-score, a metric that we show follows the Pareto principle and can act as a proxy for the Euclidean distance between data points. Inspired by this, we propose a novel ANN search framework called Subspace Collision (SC), which can provide theoretical guarantees on the quality of its results. We further propose SuCo, which achieves efficient and accurate ANN search by designing a clustering-based lightweight index and query strategies for our proposed subspace collision framework. Extensive experiments on real-world datasets demonstrate that both the indexing and query answering performance of SuCo outperform state-of-the-art ANN methods that can provide theoretical guarantees, performing 1-2 orders of magnitude faster query answering with only up to one-tenth of the index memory footprint. Moreover, SuCo achieves top performance (best for hard datasets) even when compared to methods that do not provide theoretical guarantees.
SymphonyQG: Towards Symphonious Integration of Quantization and Graph for Approximate Nearest Neighbor Search
Authors: Gou Yutong , Gao Jianyang , Xu Yuexuan , Long Cheng
Published: February 2025

Approximate nearest neighbor (ANN) search in high-dimensional Euclidean space has a broad range of applications. Among existing ANN algorithms, graph-based methods have shown superior performance in terms of the time-accuracy trade-off. However, they face performance bottlenecks due to the random memory accesses caused by the searching process on the graph indices and the costs of computing exact distances to guide the searching process. To relieve the bottlenecks, a recent method named NGT-QG makes an attempt by integrating quantization and graph. It (1) replicates and stores the quantization codes of a vertex's neighbors compactly so that they can be accessed sequentially, and (2) uses a SIMD-based implementation named FastScan to efficiently estimate distances based on the quantization codes in batch for guiding the searching process. While NGT-QG achieves promising improvements over the vanilla graph-based methods, it has not fully unleashed the potential of integrating quantization and graph. For instance, it entails a re-ranking step to compute exact distances at the end, which introduces extra random memory accesses; its graph structure is not jointly designed considering the in-batch nature of FastScan, which causes wastes of computation in searching. In this work, following NGT-QG, we present a new method named SymphonyQG, which achieves more symphonious integration of quantization and graph (e.g., it avoids the explicit re-ranking step and refines the graph structure to be more aligned with FastScan). Based on extensive experiments on real-world datasets, SymphonyQG establishes the new state-of-the-art in terms of the time-accuracy trade-off: at 95% recall, SymphonyQG achieves 1.5x-4.5x QPS compared with the most competitive baselines and achieves 3.5x-17x QPS compared with the classical library HNSWlib across all tested datasets. At the same time, its indexing is at least 8x faster than NGT-QG.
Ultraverse: An Efficient What-if Analysis Framework for Software Applications Interacting with Database Systems
Authors: Ko Ronny , Xiao Chuan , Onizuka Makoto , Lin Zhiqiang , Huang Yihe
Published: February 2025

Existing what-if analysis systems are predominantly tailored to operate on either only the application layer or only the database layer of software. This isolated approach limits their effectiveness in scenarios where intensive interaction between applications and database systems occurs. To address this gap, we introduce Ultraverse, a what-if analysis framework that seamlessly integrates both application and database layers. Ultraverse employs dynamic symbolic execution to effectively translate application code into compact SQL procedure representations, thereby synchronizing application semantics at both SQL and application levels during what-if replays. A novel aspect of Ultraverse is its use of advanced query dependency analysis, which serves two key purposes: (1) it eliminates the need to replay irrelevant transactions that do not influence the outcome, and (2) it facilitates parallel replay of mutually independent transactions, significantly enhancing the analysis efficiency. Ultraverse is applicable to existing unmodified database systems and legacy application codes. Our extensive evaluations of the framework have demonstrated remarkable improvements in what-if analysis speed, achieving performance gains ranging from 7.7x to 291x across diverse benchmarks.
User-Centric Property Graph Repairs
Authors: Pachera Amedeo , Bonifati Angela , Mauri Andrea
Published: February 2025

Property graphs serve as unifying abstractions for encoding, inspecting, and updating interconnected data with greater expressive power. They are increasingly popular across various application domains involving real users. However, graph data often contains inconsistencies that need proper transformations to address underlying constraint violations and often require specific domain knowledge. In this paper, we propose an interactive and user-centric approach to repair property graphs under denial constraints. Our approach includes a novel theoretical framework comprising a query-based inconsistency detection mechanism, a dependency graph for tracking violations, and an assignment algorithm facilitating multi-user property graph repairs by leveraging independent sets. We evaluate our approach through several experiments on real-world and synthetic datasets, considering different levels of user expertise and comparing against various baselines. Even with multiple non-oracle users, our approach outperforms existing interactive and non-interactive baselines by 30% on average in terms of repair quality. Additionally, we conduct a user study to assess real user performance in property graph repairs.