VLDB 2026 Conference Program

Large language models (LLMs) have advanced Text-to-SQL by enabling natural language interfaces to databases without task-specific fine-tuning. However, existing LLM-based systems remain unreliable, often generating SQL queries that are invalid under the database schema, referencing non-existent tables, attributes, functions, or values. Such errors persist because interactions with the database management system (DBMS) are typically limited to error messages, leaving it in a largely passive role during query refinement. This paper proposes SafeQL, \textit{a search-based refinement paradigm that redefines the role of the DBMS as an active guide in the refinement process}. Instead of regenerating entire queries after execution failure, SafeQL interprets DBMS feedback to incrementally repair only the erroneous components. Each refinement step is formulated as a guided search within a \textit{safe query space}, where candidate queries are progressively validated through DBMS execution, thereby converging to an executable query and preventing repeated regeneration of errors. Experiments on the Bird and Spider benchmarks show that SafeQL significantly improves execution accuracy and efficiency compared to regeneration-based methods.

Enterprises commonly deploy heterogeneous database systems, each of which owns a distinct SQL dialect with different syntax rules, built-in functions, and execution constraints. However, most existing NL2SQL methods assume a single canonical dialect (e.g., SQLite) and struggle to produce queries that are both semantically correct and executable on target engines. Prompt-based approaches tightly couple intent reasoning with dialect syntax, rule-based translators often degrade native operators into generic constructs, and multi-dialect fine-tuning suffers from cross-dialect interference. In this paper, we present Dial, a knowledge-grounded framework for dialect-specific NL2SQL. Dial introduces: (1) a Dialect-Aware Logical Query Planning module that converts natural language into a dialect-aware logical query plan via operator-level intent decomposition and divergence-aware specification; (2) HINT-KB, a hierarchical intent-aware knowledge base that organizes dialect knowledge into (𝑖)a canonical syntax reference, (𝑖𝑖)a declarative function repository, and (𝑖𝑖𝑖)a procedural constraint repository; and (3) an execution-driven debugging and semantic verification loop that separates syntactic recovery from logic auditing to prevent semantic drift. We construct DS-NL2SQL, a benchmark covering six major database systems with 2,218 dialect-specific test cases. Experimental results show that Dial consistently improves translation accuracy by 10.25% and dialect feature coverage by 15.77% over state-of-the-art baselines. The code is at https://github.com/weAIDB/Dial.

Natural Language to SQL (NL2SQL) technology empowers non-expert users to query relational databases without requiring SQL expertise. While large language models (LLMs) have greatly improved NL2SQL algorithms, their rapid development outpaces systematic evaluation, leaving a critical gap in understanding their effectiveness, efficiency, and limitations. To this end, we present NL2SQLBench, the first modular evaluation and benchmarking framework for LLM-enabled NL2SQL approaches. Specifically, we dissect NL2SQL systems into three core modules: Schema Selection, Candidate Generation, and Query Revision. For each module, we comprehensively review existing strategies and propose novel fine-grained metrics that systematically quantify module-level effectiveness and efficiency. We further implement these metrics in a flexible multi-agent framework, allowing configurable benchmarking across diverse NL2SQL approaches. Leveraging NL2SQLBench, we rigorously evaluate ten representative open-source methods on two datasets, the BIRD development set and the ScienceBenchmark development set, using two LLMs, DeepSeek-V3 and GPT-4o mini. We systematically assess each approach across the three core modules and evaluate multiple critical performance dimensions. Our evaluation reveals significant gaps in existing NL2SQL methods, highlighting not only substantial room for accuracy improvements but also the significant computational inefficiency, which severely hampers real-world adoption. Furthermore, our analysis identifies critical shortcomings in current benchmark datasets and evaluation rules, emphasizing issues such as inaccurate gold SQL annotations and limitations in existing evaluation rules. By synthesizing these detailed insights into a unified, transparent, and reproducible benchmarking, our study not only establishes a clear reference point for fair comparison across approaches but also serves as essential guidance for future targeted innovation in NL2SQL technology, thus advancing the practical deployment and real-world applicability of NL2SQL technologies.

Large Language Models (LLMs) have achieved impressive performance in translating natural language queries into executable SQL. However, these systems remain prone to deceptive failures: generating syntactically valid SQL that executes but fails to capture the user's intent. In this work, we argue that further progress can be made by focusing specifically on verification. In this paper, we formalize Text-to-SQL verification as a standalone task: assessing whether a candidate SQL query semantically satisfies a natural language request, without access to ground-truth labels. We propose and compare two modular verification strategies: Round-Trip Critique, which reverse-translates SQL into natural language to detect semantic drift, and Synthetic Execution Consistency, which uses unit-test-like synthetic inputs to ground verification in execution results. Our evaluation shows that these methods provide a robust signal for identifying incorrect queries, successfully flagging 64% of errors from a state-of-the-art generator and outperforming standard error detectors. We demonstrate two critical applications: (1) auditing foundational benchmarks (Spider, BIRD and KaggleDBQA), revealing that over two-thirds of "generator failures" actually stem from flawed benchmark labels, and (2) enabling Selective Generation, where a system uses verification signals to abstain from answering when confidence is low. Our results show that this paradigm significantly improves the quality of deployed data interfaces by transforming silent failures into explicit abstentions that alert the user to the failure and give them a chance to correct it.

Researchers have proposed numerous text-to-SQL techniques to streamline data analytics and accelerate the development of data-driven applications. To compare these techniques and select the best one for deployment, the community depends on public benchmarks and their leaderboards. Since these benchmarks heavily rely on human annotations during question construction and answer evaluation, the validity of the annotations is crucial. In this paper, we conduct an empirical study that (i) benchmarks annotation error rates for two widely used text-to-SQL benchmarks, BIRD and Spider 2.0-Snow, and (ii) corrects a subset of the BIRD development (Dev) set to measure the impact of annotation errors on text-to-SQL agent performance and leaderboard rankings. Through expert analysis, we show that BIRD Mini-Dev and Spider 2.0-Snow have error rates of 52.8% and 62.8%, respectively. We re-evaluate all 16 open-source agents from the BIRD leaderboard on both the original and the corrected BIRD Dev subsets. We show that performance changes range from −7% to 31% (in relative terms) and rank changes range from −9 to +9 positions. We further assess whether these impacts generalize to the full BIRD Dev set. We find that the rankings of agents on the uncorrected subset correlate strongly with those on the full Dev set (Spearman's 𝑟_𝑠 =0.85, 𝑝 =3.26e-5), whereas they correlate weakly with those on the corrected subset (Spearman's 𝑟_𝑠 =0.32, 𝑝 =0.23). These findings show that annotation errors can significantly distort reported performance and rankings, potentially misguiding research directions or deployment choices.

Large Language Models (LLMs) have become the standard for natural language interfaces to databases, but their effectiveness can be limited by context window constraints, especially for databases with large schemas. Schema subsetting or linking, which is the task of reducing the schema information provided to the LLM, has emerged as a strategy to address these limitations, yet its impact on NL-to-SQL performance remains unclear, particularly for very large schemas. In this paper, we systematically evaluate 7 real-world schema subsetting modules across 3 contemporary NL-to-SQL benchmarks, including Bird, Spider 2, and SNAILS, and we introduce BigBird--an expansion of the Bird benchmark datasets that provides additional data for evaluating subsetting of large schemas. We also introduce new subsetting-specific performance and efficiency metrics that enable in-depth evaluation of subsetting methods. Our analysis aligns with other recent work that suggests that most subsetting methods actually degrade NL-to-SQL execution accuracy from between 3% - 10% (model and method dependent) on smaller schemas, but also reveals that some subsetting methods can improve NL-to-SQL execution accuracy by up to 2% - 7% and others reduce token usage while generally maintaining the same execution accuracy performance as full-schema representations on large schemas. We also present SKALPEL, a prototype hybrid subsetting method that combines LLM-based question decomposition with semantic search, suggesting the potential for reduced token usage in NL-to-SQL workflows. These findings clarify the trade-offs of schema subsetting and motivate future research on scalable schema linking for large databases.

Cloud-based analytics now exposes an increasingly vast space of design choices. Key axes include provisioning (static vs. ephemeral), caching (capacity, tiering), scheduling (admission thresholds, parallelism), and pricing (reserved, on-demand, spot); each choice materially affects cost and performance. To navigate this complexity without deploying large-scale infrastructure, we present CloudGlide, a white-box simulation framework for systematically exploring cloud data analytics trade-offs. CloudGlide pairs a queueing-theoretic model with a discrete-event simulator (DES), ingesting real-world workload traces to provide cost and latency predictions under diverse configurations. Validated on industry traces and standard benchmarks, CloudGlide approximates behavior across existing architectures and supports rapid what-if analyses along the above axes, all without the prohibitive costs of live deployments.

Cloud database systems cannot rely on instance-local disks for write-ahead logging (WAL) durability, forcing WAL onto remote storage. Existing options are unsatisfying: remote block storage like EBS is easy to adopt but adds substantial write latency and cost, while object storage offers excellent durability and low storage cost but is impractical for OLTP due to high latency and per-append cost. Many cloud-native databases, therefore, depend on purpose-built logging backends, which are typically proprietary and tightly coupled to engine-specific replication and recovery protocols, limiting reuse. We present BtrLog, a reusable cloud logging service that combines low-latency durable appends with low-cost archival for the common single-writer architecture. BtrLog replicates log records across a quorum of SSD-backed log nodes in a single network round trip, reducing sensitivity to stragglers in commit latency. To minimize storage cost, log nodes archive records to object storage as large segments, which are written asynchronously and off the latency-critical write path. In our evaluation, BtrLog achieves lower latency than EBS and enables higher end-to-end transaction throughput when integrated into a DBMS.

Modern OLAP engines support arbitrary analytical workloads, but this flexibility incurs overhead from runtime schema interpretation, generic data representations, and abstraction layers, even in compiled-query systems. Workload-specific engines can eliminate these costs and exploit specialized data structures and algorithms for higher performance, yet have historically been too expensive to build manually. Recent advances in LLM-based code synthesis challenge this tradeoff, but naive prompting does not produce correct or efficient engines due to deep architectural dependencies and the need for systematic refinement. We present Bespoke OLAP, a fully autonomous synthesis pipeline that constructs high-performance OLAP engines tailored to a target workload through iterative performance evaluation and automated validation. Bespoke OLAP generates engines from scratch within minutes to hours and achieves order-of-magnitude speedups over DuckDB and Umbra, demonstrating that the generality tax extends beyond query compilation to storage layout and algorithmic design.

We present LiquidCache, a novel pushdown-based disaggregated caching system that evaluates filters on cache servers before transmitting data to compute nodes. Our key observation is that data decoding, not filter evaluation, is the primary bottleneck in existing systems. To address this challenge, we transcode Parquet data into a lightweight "Liquid" format and cache it for efficient filter evaluation. The Liquid format resides solely in the cache layer, requiring no changes to existing deployments and enabling easy adoption of new encodings without breaking compatibility. Through integration with Apache DataFusion and evaluation with ClickBench and TPC-H, we demonstrate that LiquidCache reduces cache CPU time by up to 10× without increasing memory footprint, and reduces network traffic by two orders of magnitudes compared to non-pushdown systems.

Workload traces from cloud data warehouse providers reveal that standard benchmarks such as TPC-H and TPC-DS fail to capture key characteristics of real-world workloads, including query repetition and string-heavy queries. In this paper, we introduce Redbench, a novel benchmark featuring a workload generator that reproduces real-world workload characteristics derived from traces released by cloud providers. Redbench integrates multiple workload generation techniques to tailor workloads to specific objectives, transforming existing benchmarks into realistic query streams that preserve intrinsic workload characteristics. By focusing on inherent workload signals rather than execution-specific metrics, Redbench bridges the gap between synthetic and real workloads. Our evaluation shows that (1) Redbench produces more realistic and reproducible workloads for cloud data warehouse benchmarking, and (2) Redbench reveals the impact of system optimizations across four commercial data warehouse platforms. We believe that Redbench provides a crucial foundation for advancing research on optimization techniques for modern cloud data warehouses

Data coverage and completeness are crucial data quality dimensions for machine learning (ML) applications. Data discovery allows retrieving relevant features from unstructured data lakes to augment the training data. However, existing methods are fragmented: they often target only individual ML tasks, decouple table retrieval from feature selection, and neglect inter-feature relationships, resulting in redundant, high-dimensional data. In this paper, we introduce Matryoshka, a holistic system that discovers and selects relevant features from data lakes for downstream ML applications. Matryoshka replaces costly join materialization with compact Gram matrix sketches and performs feature selection via incrementally fitted linear proxy models with correlation-based pruning, yielding redundancy-free feature sets for regression and classification. We evaluate Matryoshka on multiple data lakes of varying size and heterogeneity. Matryoshka improves downstream prediction quality by 18.5% on average while achieving the lowest geometric mean runtime and up to 120x faster execution on join-intensive workloads.

Dataset search often aims to identify joinable or unionable datasets to augment a given query table. State-of-the-art approaches rely on large language models (LLMs) to embed tables into vector representations and perform semantic similarity search. However, existing work assumes a centralized data repository with embeddings generated by a single, homogeneous pipeline. In contrast to this simplifying assumption, data repositories in the real world are decentralized across multiple data providers, each operating their own embedding pipelines. Given the rapid pace of LLM development and provider-specific fine-tuning, enforcing a standardized pipeline is unrealistic. We introduce FedAugment, a framework for table augmentation search over decentralized data repositories with heterogeneous embeddings. FedAugment constructs a representative set of training examples, embeds it using the individual providers' pipelines, and learns projection functions that align heterogeneous embeddings into a shared vector space via multi-view contrastive learning. Using these projections, all embeddings are mapped into a globally aligned space that supports unified vector similarity search. Compared to issuing independent top-k queries to each data provider, FedAugment enables the retrieval of a global top-k result across all repositories, avoiding redundant retrievals and enabling cost-efficient table augmentation search in decentralized settings.

Join discovery is a core task in data discovery, enabling data scientists to find columns that can be joined with a given query column. Early approaches focused on equi-joins, but data lakes and open-data repositories often contain columns whose values refer to the same entity but use different syntactic representations. To address this challenge, recent approaches discover semantically joinable columns but face a fundamental trade-off: methods that perform value-level comparisons accurately identify joinable columns but scale poorly to columns with high cardinality; column-level methods that encode an entire column into a single embedding are efficient but do not capture the fine-grained value alignment that determines whether a join is possible. We present MosaicJoin, a value-level semantic join discovery method that balances this tradeoff. MosaicJoin achieves scalability through a novel sketching strategy that approximates the joinability of a column pair without having to compare all values. At query time, MosaicJoin scores each candidate sketch using a joinability score at a cost bounded by the sketch size, making retrieval efficient even for high-cardinality columns. A query subsampling operator further reduces online search time with provable accuracy guarantees, enabling robust retrieval for large query columns. Extensive experiments show that MosaicJoin outperforms previously published methods across all benchmarks while running up to 66 times faster than other value-level methods. MosaicJoin requires no training or fine-tuning, and it scales robustly to query columns containing up to 57K values and data lake columns containing up to 1M values.

In data lakes, efficient data fusion is essential yet challenging in dynamic scenarios due to heterogeneous multi-source data. Batch-based methods ensure high accuracy but suffer from high latency, while emerging on-demand fusion approaches, despite offering real-time responsiveness, lack native support for incremental scenarios and often struggle with query evidence constraints. To overcome these issues, we propose IncreQueryFusion, an end-to-end on-demand fusion framework tailored for dynamic data lakes. First, it introduces a Temporal Index Evidence Retrieval module to incrementally retrieve and selectively expand evidence for subsequent fusion. Then, an adaptive aligned hierarchical fusion mechanism organizes data values and performs evidence-aware truth inference. Finally, a dynamic fusion truth maintenance algorithm refreshes fusion results efficiently without full recomputation. A comprehensive evaluation of established benchmarks and our newly constructed dynamic datasets demonstrates the effectiveness of IncreQueryFusion. It outperforms the state-of-the-art baseline in accuracy by 5\%-30\% on static workloads, while achieving speedups of over 10$\times$ against on-demand methods and over 100$\times$ against batch methods in dynamic scenarios.

Denial Constraints (DCs) form a highly expressive integrity rule language that subsumes many used formalisms such as keys and functional dependencies, making them widely adopted in applications that require the manipulation of rich sets of data constraints. This expressiveness has motivated the development of numerous algorithms for automatically discovering DCs from data, with particular emphasis on the discovery of approximate DCs to improve robustness to erroneous data. However, existing DC discovery algorithms exhibit computational costs that are quadratic in the number of tuples and exponential in the number of attributes, and most cannot accommodate changes in the data. Moreover, they often produce thousands of uninformative DCs. These limitations make current DC discovery algorithms difficult to use effectively on very large and dynamic databases. In this paper, we present LIMA, an approximate DC discovery algorithm that efficiently discovers DCs on very large and dynamic databases. LIMA uses statistical methods to infer properties of DCs from reduced samples, and introduces a novel discovery framework that exploits a more restrictive definition of DC validity to substantially reduce the cost of searching for valid DCs. We experimentally demonstrate that LIMA achieves significantly better scalability than current algorithms with respect to both rows and attributes, while also discovering higher-quality sets of DCs with precisions several orders of magnitude higher than the state of the art, both in static and in dynamic datasets.

Counting queries are ubiquitous in database systems, particularly for driving internal system optimization. Learned models for cardinality estimation rely heavily on large-scale training data, yet generating such data by executing massive batches of counting queries is expensive. We propose BaCon, an efficient algorithm for batch evaluation of counting queries on top of a database system, without modifying its internals. BaCon integrates the idea of factorized databases with a workload-aware domain quantization strategy, allowing it to evaluate batches of counting queries using compact data structures rather than materializing massive join results. BaCon's design is compatible with most database management system, and we have implemented it as a client-side application on PostgreSQL with a lightweight C-language UDF (user-defined function). This implementation delivers speedups between 2$\times$ and 178$\times$ over baselines and good performance across various workloads, making training and maintenance of learned cardinality estimation models significantly more practical.

Simpson's paradox has broad impact across many scientific domains. Existing detection methods overlook a key issue: many detected paradoxes may be redundant, arising from equivalent data subsets, identical subpopulation partitions, or correlated outcome variables, thereby obscure insights and increase computational cost. In this paper, we present a framework for finding non-redundant Simpson's paradoxes by formalizing three sources of redundancy—sibling child, separator, and statistic equivalence—and showing that pairwise redundancy forms an equivalence relation. We further propose a concise representation that groups redundant paradoxes and develop efficient algorithms combining depth-first population materialization with redundancy-aware discovery. Experiments on real and synthetic datasets show that redundancy is prevalent (over 40% in some cases), while our methods scale to millions of records, achieve up to 6.72 times speedup over brute-force approaches and identify robust paradoxes, enabling efficient discovery, compact summarization, and clear interpretation in multidimensional data.

Computing the correlation of two attributes in a large dataset is an important problem, with many applications, including exploratory analytics and dimensionality reduction. Among the well-known correlation measures, Kendall's Tau is the most robust one, as it is immune from parametric assumptions and outliers. On the other hand, computing Kendall's Tau for large-scale data becomes challenging (i) due to the superlinear cost of the state-of-the-art algorithm and (ii) because all data need to be memory-resident for efficient processing. In this paper, we address the problem via a geometric approach that partitions the data in the cells of a grid, and exploits the relative position of the cells to compute correlation information en masse. Our approach facilitates parallel and distributed computation of Kendall's correlation; we propose a scalable algorithm in this direction. Finally, we propose an efficient approximate algorithm with a provable error bound, which derives accurate results by a single pass over the grid statistics. Our experimental evaluation demonstrates the efficiency and scalability of our grid-based techniques compared to the state-of-the-art algorithm.

Matrix multiplication is a core operation in numerous applications, yet its exact computation becomes prohibitively expensive as data scales, especially in streaming environments where timeliness is critical. In many real-world scenarios, data arrives continuously, making it essential to focus on recent information via sliding windows. While existing approaches offer approximate solutions, they often suffer from suboptimal space complexities when extended to the sliding-window setting. In this work, we introduce SO-COD, a novel algorithm for approximate matrix multiplication (AMM) in the sliding-window streaming setting, where only the most recent data is retained for computation. Inspired by frequency estimation over sliding windows, our method tracks significant contributions, referred to as ``snapshots'', from incoming data and efficiently updates them as the window advances. Given matrices \(\boldsymbol{X} \in \mathbb{R}^{d_x \times n}\) and \(\boldsymbol{Y} \in \mathbb{R}^{d_y \times n}\) for computing \(\boldsymbol{X} \boldsymbol{Y}^T\), we analyze two data settings. In the \emph{normalized} setting, where each column of the input matrices has a unit \(L_2\) norm, SO-COD achieves an optimal space complexity of \( O\left(\frac{d_x+d_y}{\epsilon}\right) \). In the \emph{unnormalized} setting, where the square of column norms vary within a bounded range \([1, R]\), we show that the space requirement is \( O\left(\frac{d_x+d_y}{\epsilon}\log R\right) \), which matches the theoretical lower bound for an \(\epsilon\)-approximation guarantee. Time complexity analysis further shows that our SO-COD has comparable update time and superior query time compared to existing methods. Extensive experiments on synthetic and real-world datasets demonstrate that SO-COD effectively balances space cost and approximation error, making it a promising solution for large-scale streaming matrix multiplication.

Querying incomplete knowledge graphs with neural predictors is powerful but dangerous. Errors compound across multi-hop pipelines with no formal bound on the completeness of results. We introduce ConRAD, the first framework to enforce declarative marginal recall guarantees natively within a neural graph database query engine. Given a user-specified risk budget, ConRAD automatically derives per-operator prediction thresholds that satisfy the recall target in expectation over the query distribution, with finite-sample, distribution-free statistical validity via Conformal Risk Control, while maximizing end-to-end precision. To scale calibration across multi-operator query topologies, we introduce a quantile-space scalarization that reduces intractable high-dimensional threshold searches to a single parameter. We further design the conformal gate, a novel physical operator that dynamically bypasses neural inference when local graph evidence suffices, eliminating unnecessary model inferences in dense graph regions. Evaluated across three benchmarks and eight query topologies, ConRAD satisfies all risk budgets, with empirical recall falling below the target by at most 0.0547 across all settings. It reduces neural invocations to zero in near-complete graph regions, and achieves precision that matches or exceeds best-case static baselines that offer no guarantees and require manual threshold search.

Approximate nearest neighbor search (ANNS) is increasingly essential for AI-driven applications. In practice, ANNS is often coupled with label filtering to improve accuracy, relevance, and efficiency, a variant known as filtered ANNS or FANNS. Existing FANNS methods fall short in efficiency or accuracy. This is because, first, searching on a label-mixed index often converges to local minima due to label interference. Second, isolating and duplicating labels in the index inflates the index and incurs prohibitive memory overhead. Third, current join-based strategies for multi-filter search perform substantial wasted computation on unpromising candidates. We present BigFANN, a label-aware FANNS framework that achieves high speed and space efficiency, while retaining high accuracy. Our framework features a hybrid indexing scheme that introduces heterogeneous edge types and flexible IVF-graph indexing. Specifically, we construct graph indices with tunable combinations of exclusive and shared edges based on label characteristics. This method effectively minimizes label interference for single-filter search under a certain memory budget, ensuring high search accuracy and speed. In addition to heterogeneous edges, we adopt a hybrid of graph and IVF indices to deal with single- and multi-filter queries. Particularly, for multi-filter searches, we propose a join-free search strategy to eliminate wasted computation in the existing join-based strategy. Experimental results on various datasets show that BigFANN significantly outperforms state-of-the art FANNS frameworks, UNG and ParlayIVF^2, by up to 786× and 4× respectively, while achieving the same or better accuracy.

Modern retrieval systems increasingly require filtered vector search under arbitrary predicate constraints, where users filter results by attributes such as category, price, location, keywords, and their combinations. Existing solutions either specialize in a single predicate type (e.g., range or equality filters), rely on dense, high-overhead indexes, or fail to handle predicates with diverse selectivities. As a result, they fail to simultaneously achieve efficiency, scalability, and flexibility. In this paper, we propose CGIF, an index that efficiently supports approximate nearest neighbor search (ANNS) both with and without predicates, while preserving the lightweight and scalable structure of the widely adopted vector index HNSW. Our design builds on an observation from previous works that HNSW traversal naturally consists of two phases: (1) a navigation phase, where the search rapidly moves toward the query’s vicinity, and (2) a local exploration phase, where traversal expands locally to refine results. CGIF retains the original HNSW search strategy during navigation to efficiently reach the query region, and introduces a predicate-aware traversal during local exploration. When a neighbor does not satisfy the query predicates, CGIF replaces it with alternative candidates drawn via inverted-file (IVF) indexing, ensuring effective local exploration under diverse predicates. Extensive experiments on multiple real-world datasets show that CGIF consistently outperforms state-of-the-art filtered vector search methods, delivering up to 2× faster query performance while maintaining high recall across diverse predicate types and selectivities.

Real-world vector embeddings often carry additional label attributes, such as keywords and tags. In this context, label-hybrid approximate k-nearest neighbor (AKNN) search retrieves the top-k approximate nearest vectors to a query, subject to the constraint that their labels fully contain the query-label set. A naive solution builds a separate index for every query-label set, but the exponential growth of such sets makes this approach storage-prohibitive. To overcome this, we propose selectively indexing only a subset of query-label sets while still ensuring efficient processing for all queries. This is made possible by a key insight into label containment: an index built for a label set L can also serve any query whose label set L' is a superset of L, with query cost bounded by the elastic factor: the ratio between the number of vectors matching L and those matching L'. We formalize the index-selection task as a constrained optimization problem that chooses which label sets to index to satisfy space and query efficiency constraints. We prove the problem is NP-complete and propose efficient greedy algorithms for its efficiency- and space-constrained variants. Extensive experiments on real-world datasets show that our method achieves 10x–800x speedups over state-of-the-art techniques. Moreover, our approach is index-agnostic and can be seamlessly integrated into existing vector database systems.

Query cost estimation is a fundamental problem in data management with numerous applications in query execution, yet remains an open problem in vector Approximate Nearest Neighbor Search (ANNS). Cost estimation plays a critical role in ensuring the accuracy of ANNS results, reducing unnecessary search effort, and enabling cost-based optimization. In this paper, we define the problem of cost estimation in ANNS, analyze its challenges, and introduce ANNiE, a novel learned cost estimator designed for graph-based ANNS. ANNiE estimates the cost required to reach a specified recall target and couples its estimates with probabilistic quality guarantees. We show how ANNiE can be used to optimize search time by designing the first accuracy-guaranteed graph search algorithm. Our experimental evaluation with several workloads, demonstrates that ANNiE improves estimation accuracy by 6$\times$ over the baselines, while achieving the probabilistic guarantee. Moreover, the graph search of ANNiE, ANNiE-S, achieves a 2.3$\times$ speedup over the baselines, while automatically reaching each query's recall target.

Recent studies demonstrate the significant practical value of hybrid queries, which integrate vector search with structured filters (e.g., attribute and range filtering) for refined retrieval. However, current evaluations lack unified benchmarking standards and systematic assessment methodologies. Existing studies not only fail to cover mainstream algorithms but also omit systematic comparisons or in-depth analysis on different methods. To address this issue, we design a complete evaluation framework for hybrid queries. Our study introduces 15 hybrid query algorithms and systematically classifies them based on multiple dimensions, such as index organization and filtering strategy, providing a reference for the categorization of hybrid queries. In experiments, for attribute filtering, we construct standard attribute sets, enabling a unified comparison of algorithms in terms of index construction efficiency, query performance, and robustness. For range filtering, we also evaluate the algorithm performance across the 3 metrics through controlled variation of query ranges. Additionally, we conduct an in-depth analysis of the experimental results based on the underlying principles of algorithms. Extensive experimental results reveal the strengths and weaknesses of each algorithm. Based on the findings, we develop a set of practical guidelines for algorithm selection, offering reliable references for different application scenarios. Furthermore, we identify potential directions for improvement to address the current limitations of these algorithms.

Filtered approximate nearest neighbor (FANN) search must satisfy both vector similarity and structured predicates, yet evaluations remain brittle because real hybrid workloads are rarely shareable and existing benchmarks rely on ad-hoc synthetic or semi-real constructions. We argue that realism hinges on execution-driven query difficulty: failures in early filtering trigger over-fetching of additional candidates, shaping latency, throughput, and recall. Building on this insight, we propose Hardness, a query-level hardness metric that models the conditional execution chain via the over-fetch factor and extends naturally to strategy-conditioned settings. Across diverse datasets and hybrid strategies, 𝛼-Hardness exhibits strong monotonic alignment with empirical performance, while common proxies such as selectivity or attribute–vector correlation are frequently unstable or strategy-inconsistent. We further introduce HCBGen, a hardness-controlled benchmark generator that uses 𝛼-Hardness as an explicit control signal to synthesize workloads under coarse bias modes or to match a target hardness profile. Our experiments show that widely used benchmarks occupy a narrow, relatively easy portion of the hardness spectrum, masking robustness gaps that emerge under harder queries. Finally, we demonstrate that matching hardness distributions enables privacy-preserving proxy workloads that closely reproduce performance trends, bridging research benchmarks and real evaluation.

Learned index has received much attention due to its often dramatic performance and space-efficiency improvements over traditional index designs. Its strength is rooted in its ability of using computation with models or functions, rather than key search, to obtain the position of a search key in a sorted key array. However, the models or functions cannot compute the correct position without errors. Instead, they can only help determine a key scope where last-mile local search is required to find the search key. Both model computation and the last-mile search can be expensive and limit the index’s performance potential. To unlock the full potential of learned index, we propose LiBox, which groups keys in a sorted array into boxes so that (1) the box that covers a search key can be identified without any error by a linear regression function; (2) the last-mile search in the box can be conducted using only one AVX-512 instruction. A learned index based on such a box structure can be highly efficient in which each key search takes a well-predictable number of instructions and memory accesses. In this paper, we present the design of a hierarchical box-based structure. Using moderately extra space in a box to accommodate irregular key distribution, LiBox can serve both read and write queries at the speed of array reference. Libox can also flexibly align its reorganization operation with read/write intensity distribution to support high-performance read by hiding the structural modification cost. We have implemented LiBox and extensively evaluated it. The experiment results show that it outperforms state-of-the-art learned indexes, such as ALEX and LIPP, and non-learned indexes such as ART by up to 1.4 – 4.5 times with similar or higher space efficiency.

Learned indexes improve data access efficiency by accelerating lookups and reducing memory usage, but integrating them with write-optimized Log-Structured Merge-trees (LSM-trees) remains challenging due to frequent compactions and intensive updates. We analyze this integration and identify two key mismatches. First, learned indexes reshape the conventional SSTable sizing trade-off in LSM-trees. In conventional LSM-trees, SSTable size drives the read/write trade-off, and this trade-off is amplified by level asymmetry between write-intensive upper levels and read-intensive deeper levels. Learned indexes make lookups less sensitive to SSTable size, thereby changing the traditional trade-off. Second, learned indexes typically employ fixed error bounds that cannot adapt to key distribution shifts caused by LSM-tree compactions, resulting in inefficient index construction and degraded lookup performance across different levels. Wild Turkey addresses these mismatches with two complementary mechanisms. Level-Aware Compaction (LAC) introduces a level-specific SSTable sizing strategy that aligns compaction granularity with the distinct read/write characteristics of each level. Building on LAC, Wild-Learning is a reinforcement learning (RL)-based controller that adaptively tunes both the LAC-degree and the per-SSTable error bound in response to evolving data distributions and system conditions. Together, these mechanisms co-tune compaction behavior and learned index construction to balance read and write performance under changing workloads. On SOSD datasets and YCSB workloads, Wild Turkey achieves up to 2.01x higher write throughput, 1.52x higher read throughput, 36\% less write stall time, and 78.4\% fewer compactions compared to state-of-the-art LSM-tree and learned index integration.

We consider the task of constructing a data structure for associating a static set of keys with values, while allowing arbitrary output values for queries involving keys outside the set. Compared to hash tables, these so-called static function data structures do not need to store the key set and thus use significantly less memory. Several techniques are known, with compressed static functions approaching the zero-order empirical entropy of the value sequence. In this paper, we introduce learned static functions, which use machine learning to capture correlations between keys and values. For each key, a model predicts a probability distribution over the values, from which we derive a key-specific prefix code to compactly encode the true value. The resulting codeword is stored in a classic static function data structure. This design allows learned static functions to break the zero-order entropy barrier while still supporting point queries. Our experiments show substantial space savings: up to one order of magnitude on real data, and up to three orders of magnitude on synthetic data.

Multi-set membership queries are ubiquitous in networking and database systems. Current solutions force a difficult compromise: hash tables guarantee correctness but suffer from high memory footprints, while filter-based approaches optimize space at the cost of probabilistic errors. In this paper, we propose STEM2, a fast and space-efficient data structure that achieves 100% query accuracy and can support dynamic key updates for multi-set membership queries. STEM2 utilizes a balanced binary tree architecture where each non-leaf node incorporates a novel Exact Binary Set Separator (XBSS) to partition keys into two disjoint groups. A key innovation of our design is a minimized hashing scheme that requires only two hash computations per key lookup, significantly reducing computational overhead. Additionally, STEM2 separates the control plane and the data plane: the control plane handles construction and dynamic updates, while the data plane is dedicated to serving efficient membership queries. Extensive experiments show that STEM2 achieves over 120 million operations per second (Mops) in lookup throughput, outperforming the state-of-the-art Coloring Embedder by 20% and the Ludo hashing by up to 21.6×, while maintaining compact memory cost and exact correctness.

For high-dimensional analytics queries in scientific domains, a full table scan is often seen as the only feasible execution path, even if result cardinalities are known to be small. In this paper, we argue for intersecting multiple indices built over medium-sized attribute subsets (Teams) as a means to produce a list of (candidate) tuple IDs for further processing. While this strategy is compatible with various index structures, significant discriminative power lies in the combined selectivity of multiple predicates. Akin to bitmap indices and VA-files, adopting simple and lightweight index approaches for each Team, instead of highly accurate but costly ones, still enables high overall selectivity and precision. Thus, the focus shifts away from individual indices towards their efficient intersection. Teams with just 1 member/attribute (bitmap indices) are outperformed for selective queries due to the inability to avoid access to large parts of the index. For example, Teams with 5 members are up to 6-7 times faster for 85 dimensions and require 1.58-2.07 times less storage. Team-based Indexing is most useful for queries with high selectivity and dimensionality, such as the search for rare objects.

Efficient evaluation of regular expressions (regex, for short) is crucial for text analysis, and n-gram indexes are fundamental to achieving fast regex evaluation performance. However, these indexes face scalability challenges because of the exponential number of possible n-grams that must be indexed. Many existing selection strategies, developed decades ago, have not been rigorously evaluated on contemporary large-scale workloads and lack comprehensive performance comparisons. Therefore, a uni"ed and comprehensive evaluation framework is necessary to compare these methods under the same experimental settings. This paper presents the "rst systematic evaluation of three representative n-gram selection strategies across "ve workloads, including real-time production logs and genomic sequence analysis. We examine their trade-o#s in terms of index construction time, storage overhead, false positive rates, and end-to-end query performance. Through empirical results, this study provides a modern perspective on existing n-gram based regular expression evaluation methods, extensive observations, valuable discoveries, and an adaptable testing framework to guide future research in this domain. We makeourimplementations of these methods and our test framework available as open-source at https://github.com/mush-zhang/RegexIndexComparison.

Approximate nearest neighbor search (ANNS) is a core problem in machine learning and information retrieval. GPUs offer a promising path to high-performance ANNS through massive parallelism and co-location with downstream applications, but current GPU indices face three limitations: inability to update without full rebuilds, lack of efficient quantization for high-dimensional vectors, and poor latency hiding due to data-dependent memory accesses. We present Jasper, a GPU-native ANNS system built on the Va- mana graph index that achieves both high query throughput and full updatability via three new techniques: (1) a batch-parallel con- struction algorithm enabling lock-free streaming insertions, (2) a GPU-efficient RaBitQ implementation that reduces memory foot- print up to 8×without random access penalties, and (3) an optimized search kernel with improved compute utilization and latency hiding. Across five datasets, Jasper achieves up to 1.93× higher throughput than CAGRA, the current state-of-the-art GPU index, while providing updatability that CAGRA lacks, constructs indices 2.4× faster on average, and delivers 19 –131× faster queries than BANG, the previous fastest GPU Vamana implementation.

Approximate nearest neighbor search (ANNS) on GPUs is gaining increasing popularity for modern retrieval and recommendation workloads that operate over massive high-dimensional vectors. Graph-based indexes deliver high recall and throughput but incur heavy build-time and storage costs. In contrast, cluster-based methods build and scale efficiently yet often need many probes for high recall, straining memory bandwidth and compute. Aiming to simultaneously achieve fast index build, high-throughput search, high recall, and low storage requirement for GPUs, we present IVF-RaBitQ (GPU), a GPU-native ANNS solution that integrates the cluster-based method IVF with RaBitQ quantization into an efficient GPU index build/search pipeline. Specifically, for index build, we develop a scalable GPU-native RaBitQ quantization method that enables fast and accurate low-bit encoding at scale. For search, we develop GPU-native distance computation schemes for RaBitQ codes and a fused search kernel to achieve high throughput with high recall. With IVF-RaBitQ implemented and integrated into the NVIDIA cuVS Library, experiments on cuVS Bench across multiple datasets show that IVF-RaBitQ offers a strong performance frontier in recall, throughput, index build time, and storage footprint. For Recall≈0.95, IVF-RaBitQ achieves 2.3× higher QPS than the state-of-the-art graph-based method CAGRA, while also constructing indices 7.5× faster on average. Compared to the cluster-based method IVF-PQ, IVF-RaBitQ delivers on average over 2.9× higher throughput while avoiding accessing the raw vectors for reranking.

High-dimensional approximate nearest neighbor (ANN) search is fundamental to modern AI applications including retrieval-augmented generation and recommendation systems. While vector quantization (VQ) methods excel at compressing vectors for efficient search, existing approaches face critical bottlenecks: prolonged indexing times due to expensive data-dependent training, slow query processing from quadratic distance computations, and poor scalability on large datasets. In this paper, we introduce a novel quantization framework that leverages the orthogonal Johnson-Lindenstrauss (JL) transformation to lay the foundation for resolving these bottlenecks. Our key insight is that the JL induces a predictable near-Gaussian distribution with independent dimensions, enabling quick codebook generation without expensive iterative training. Based on that, we propose two algorithms: JQ (JL-enhanced Quantization) achieves fast indexing through training-free codebook construction while maintaining provable distance error bounds; and JHQ (JL-enhanced Hierarchical Quantization) extends JQ with a two-level architecture that uses primary quantization for rapid candidate filtering and residual quantization for accurate refinement, achieving better query accuracy-speed tradeoff on large scale datasets. Finally, extensive experiments on six benchmark datasets with up to 3,072 dimensions demonstrate that our methods achieve 3–10$\times$ query speedup over state-of-the-art baselines at $\geq$95\% recall, with 10-30$\times$ index construction speedup. Particularly, JHQ excels on massive datasets, maintaining 2–10$\times$ higher queries-per-second at >90\% recall compared to JQ.

Approximate Nearest Neighbor (ANN) search is widely used in applications such as recommendation systems, search engines, and natural language processing. Indexing techniques like the Inverted File (IVF) offer efficiency at the cost of accuracy, yet lack formal mechanisms to quantify or control approximation error. Existing approaches that attempt to provide such guarantees typically rely on restrictive assumptions about underlying data distributions, which limits their generalizability. We introduce ConANN, the first framework to provide formal, distribution-free error guarantees for IVF-based ANN search by leveraging recent advances in Conformal Risk Control. Empirical evaluation across five standard benchmarks demonstrates that ConANN: (1) tightly controls approximation error, achieving a worst-case False Negative Rate deviation within 0.03 percentage points of the target; (2) provides formal guarantees without requiring expansion of the search space, and in some cases even reduces the number of probed clusters; (3) dynamically adapts the cluster probes required per query; and (4) incurs negligible overheads when compared to existing state-of-the-art baselines. ConANN is integrated into the FAISS vector search library, facilitating adoption in real-world ANN systems.

Large Language Models (LLMs) are powerful tools for processing data. However, LLMs are also complex black-boxes, returning answers to queries on data, without any indication for where the answer came from or whether it is trustworthy. We introduce the notion of provenance for data processing with LLMs. While existing heuristics (such as embedding similarity or directly asking an LLM) could provide some hints for where the answer was derived, they provide no guarantees that the answer can be derived using the identified provenance, and indeed, are often incorrect. Instead, we propose the notion of verifiable provenance wherein we identify a subset of the input text that reproduces the same (or equivalent) answer as that on the complete text, and introduce the notion of minimality, where the verifiable provenance is as small as possible. To identify such a provenance, a naive solution would require checking all possible subsets of the source data with the LLM, which is prohibitively expensive. We present BLIP, a bolt-on framework for efficiently inferring a small-sized verifiable provenance for any LLM-powered data processing task, with any LLM. As part of BLIP, we introduce eight strategies, each guaranteed to find a minimal verifiable provenance, as well as an adaptive strategy that combines their strengths to reduce cost further. We further extend BLIP to produce multiple minimal verifiable provenances. Experiments on seven datasets show that the provenance generated by BLIP is always guaranteed to reproduce the answer—achieving over 30% higher accuracy than the best-performing baseline with a comparable provenance size. Moreover, BLIP incurs a low cost, comparable to the original query on the original data.

Dense retrieval services underpin semantic search, recommendation, and retrieval-augmented generation, yet clients typically see only a top-k list with no auditable execution evidence. We present V3DB, a verifiable, versioned vector-search service that checks on demand whether an untrusted provider's approximate nearest-neighbor (ANN) result was produced by executing published IVF-PQ semantics on a committed snapshot. V3DB commits to each corpus snapshot and standardizes IVF-PQ into a fixed-shape, five-step query semantics. Given a public commitment and query embedding, the service returns top-k payloads and, when challenged, produces a succinct zero-knowledge proof that the output follows these semantics on the committed snapshot, without revealing corpus embeddings or private index contents to the verifier during audit. To make proving practical, V3DB avoids costly in-circuit sorting and random access with multiset equality/inclusion checks plus lightweight boundary conditions. Our Plonky2 prototype proves up to 22x faster and uses up to 40% less peak memory than the circuit-only baseline, with millisecond verification.

In recent years, there has been significant progress in the development of deep learning models over relational databases, including architectures based on heterogeneous graph neural networks (hetero-GNNs) and heterogeneous graph transformers. In effect, such architectures state how the database records and links (e.g., foreign-key references) translate into a large, complex numerical expression, involving numerous learnable parameters. This complexity makes it hard to explain, in human-understandable terms, how a model uses the available data to arrive at a given prediction. We present a novel framework for explaining machine-learning models over relational databases, where explanations are view definitions that highlight focused parts of the database that mostly contribute to the model's prediction. We establish such global abductive explanations by adapting the classic notion of determinacy by Nash, Segoufin, and Vianu (2010). In addition to tuning the tradeoff between determinacy and conciseness, the framework allows controlling the level of granularity by adopting different fragments of view definitions, such as ones highlighting whole columns, foreign keys between tables, relevant groups of tuples, and so on. We investigate the realization of the framework in the case of hetero-GNNs, and develop a model-specific approach via the notion of learnable masks. For comparison, we propose model agnostic heuristic baselines and show that our approach is both more efficient and achieves better explanation quality in most cases. Our extensive empirical evaluation on the RelBench collection across diverse domains and record-level tasks demonstrates both the usefulness of our explanations and the efficiency of their generation.

Data provenance (the process of determining the origin and derivation of data outputs) has applications across multiple domains including explaining database query results and auditing scientific workflows. Despite decades of research, provenance tracing remains challenging due to its high computational cost and storage requirements. In streaming systems such as Apache Flink, fine- grained provenance graphs can grow super-linearly with data volume, posing significant scalability challenges. We define temporal attribution, a new lightweight form of provenance, appropriate for certain tasks, such as monitoring dependencies between system components over time quantitatively. Temporal attribution enables time-focused analysis that does not require fine-grained, tuple-level dependency meta-data. Inspired by volume-based provenance tracking in Temporal Interaction Networks (TINs), we demonstrate TINs’ applicability in succinctly modeling quantified data exchanges between dataflow operators in stream data processing systems and in processing workflows, in general, over time. We classify data into discrete and liquid types, define five temporal provenance query types, and propose a state-based indexing approach. Our vision outlines research directions toward making this new form of temporal attribution a practical tool for large-scale dataflow analytics.

Data sharing is central to various applications such as fraud detection, ad matching, and improving patient care. However, each solution to data sharing is bespoke and cost-intensive, hampering value generation. We identify the lack of abstractions to control data release as the culprit of the problem. For example, it is common to have constraints on whether to share data that depend on the result of sharing, and evaluating these constraints requires sharing in the first place, leading to a standstill. To help people build solutions to a wide variety of data sharing applications, we propose programmable dataflows, which consist of two components. The first component is an abstraction, the contract, which agents use to communicate the intent of a data sharing action and evaluate its consequences before the dataflow takes place. This helps agents control the release of their data. The second component is a contract programming model (CPM), which allows agents to program data sharing applications catered to each problem’s needs with the contract abstraction. We describe how to deploy those applications on a data escrow to ensure data remains protected from unintended data releases. Our evaluation shows 1) the contract abstraction permits representing a wide range of sharing problems, 2) CPM permits writing programs for complex data sharing problems and 3) quantitatively, our improvements to CPM make sharing programs run efficiently.

Graph database management systems (GDBMSs) have been powering many data-driven applications. To ensure GDBMS reliability, several testing approaches have been proposed. However, they all suffer from two key limitations: (1) insufficient support for generating complex and valid queries to exercise deep GDBMS code, and (2) lack of general oracles to validate the execution correctness of arbitrary queries. In this paper, we propose a novel and practical approach, Dinkel, for thoroughly testing GDBMSs. Our approach consists of two core techniques. First, to generate complex and valid queries, we model two kinds of graph state, query context and graph schema, to describe the Cypher variables and the manipulated graph labels and properties. We generate queries clause-by-clause, and modify the graph states on the fly to ensure each clause references the correct state information. Second, to generally validate query results, we introduce two fine-grained query transformations: clause-level and expression-level transformations. These transformations can operate on arbitrary queries while preserving their semantics. Dinkel validates GDBMSs by checking whether the transformed query produces the same results as the original. We evaluated Dinkel on three well-known GDBMSs. In total, we found 127 bugs, among which 113 were confirmed, 84 were fixed, and 33 were logic bugs. Compared to existing approaches, Dinkel can cover over 70% more code and find substantially more bugs within a 48-hour testing campaign. We expect Dinkel’s powerful bug detection to lay a practical foundation for GDBMS testing.

Large Language Models (LLMs) promise to automate data engineering on tabular data, offering enterprises a valuable opportunity to cut the high costs of manual data handling. But the enterprise domain comes with unique challenges that existing LLM-based approaches for data engineering often overlook, such as large table sizes, more complex tasks, and the need for internal knowledge. To bridge these gaps, we identify key enterprise-specific challenges related to data, tasks, and background knowledge and extensively evaluate how they affect data engineering with LLMs. Our analysis reveals that LLMs face substantial limitations in real-world enterprise scenarios, with accuracy declining sharply. Our findings contribute to a systematic understanding of LLMs for enterprise data engineering to support their adoption in industry.

Knowledge Graph (KG) accuracy assessment is essential for ensuring data quality in downstream applications, yet remains prohibitively expensive due to annotation costs and scale. Large Language Models (LLMs), trained on vast corpora, offer cheap fact validation but remain unreliable as direct accuracy estimators due to hallucinations and knowledge gaps. We propose a novel approach that exploits LLM capabilities without relying on their correctness: using aggregated LLM predictions as stratification signals for sampling-based accuracy estimation. By partitioning KGs into internally homogeneous strata guided by aggregated LLM outputs, we achieve statistically significant cost reductions ranging from 11% to 54% over unstratified and topology-based baselines on real-world KGs. To scale beyond LLM computational constraints, we introduce a knowledge distillation strategy that transfers stratification signals to efficient student models, requiring annotation of only 0.25% of facts while maintaining signal quality. Experiments on six KGs spanning 20M+ triples demonstrate consistent improvements over SotA methods, with statistical guarantees on accuracy estimates.

Predicting missing cell values in tabular data is a fundamental problem in data cleaning. While state-of-the-art reasoning models show great promise in predicting missing values in tables, by reasoning holistically across rows and columns, they are costly to deploy at scale and tend to be overconfident, often generating hallucinated or false-positive predictions. In this paper, we observe that achieving high precision missing-value prediction in tables requires a distinct combination of three capabilities: (1) world knowledge, (2) text-based reasoning, and (3) code-based reasoning. We systematically explore design choices for combining these capabilities, and propose an Auto-Fill approach that post-trains three specialist small language models (SLMs), each optimized for one capability. We develop a calibrated ensemble mechanism that either dynamically selects the most confident specialist or abstains, ensuring high accuracy. Extensive experiments on 11 benchmarks with 2200 real tables drawn from diverse domains show that Auto-Fill achieves superior accuracy compared to state-of-the-art reasoning models (e.g., o3-pro, Gemini 3 Pro, and DeepSeek R1), while operating at a fraction (less than 1%) of the cost of these frontier models. Our results highlight the effectiveness of specialization and calibrated abstention in the important domain of tabular data.

Strings are the most common data type in modern database systems, yet they are often treated as an afterthought in high-performance data formats. While numerical data benefits from specialized, light-weight compression schemes, text is typically handled by general-purpose algorithms such as Zstd, LZ4, or Snappy, which require full-block decompression before processing. In this paper, we explore the potential of repurposing Large Language Model (LLM) tokenizers as a lightweight string compression scheme for databases, similar to FSST, but with a global token table shared across all tables and columns. Operators such as joins and aggregations can exploit this consistent encoding to defer decompression and process encoded values directly. We implement a global token table based on GPT-4’s tokenizer in Umbra and demonstrate execution time improvements of up to 2× on string-heavy workloads, while reducing storage and memory consumption by up to 1.65×. Tokenizers integrate well with other compression algorithms, such as FSST, OnPair, or Zstd, while maintaining good compression ratios and high decompression throughput exceeding 6 GB/s on a single CPU core.

Databases are integral to modern applications. They enable the efficient processing of vast amounts of data, making it possible to build services that support millions of users. However, these systems often comprise hundreds of interconnected tables, complicating maintenance and comprehension. To effectively operate them, having an overview of the database is of utmost importance. Database table clustering involves grouping semantically related tables, which simplifies many database management, analysis, and integration tasks. We present Schuyler, a system that clusters database tables by combining structural and semantic features of the database. Specifically, Schuyler fine-tunes a large language model in a self-supervised manner using triplet-loss to produce high-quality embeddings representing table semantics. Subsequently, these embeddings are clustered to achieve a database table clustering. Our approach requires no labeled training data and, thus, is applicable to arbitrary databases. To validate Schuyler and benchmark it against state-of-the-art competitors, we introduce a benchmark collection consisting of five real-world databases. These databases vary significantly in size (29–481 tables) and complexity (3–47 clusters) and reflect diverse real-world challenges. Our results demonstrate that Schuyler consistently achieves superior clustering performance, improving the state-of-the-art on average by 0.13 ARI (adjusted Rand index) and 0.10 AMI (adjusted mutual information).

Table Question Answering (TQA) aims to answer natural language questions over structured tables. Large Language Models (LLMs) enable promising solutions to this problem, with operator-centric solutions that generate table manipulation pipelines in a multi-step manner offering state-of-the-art performance. However, these solutions rely on multiple LLM calls, resulting in prohibitive latencies and computational costs. We propose Operation-R1, the first framework that trains lightweight LLMs (e.g., Qwen-4B/1.7B) via a novel variant of reinforcement learning with verifiable rewards to produce high-quality data-preparation pipelines for TQA in a single inference step. To train such an LLM, we first introduce a self-supervised rewarding mechanism to automatically obtain fine-grained pipeline-wise supervision signals for LLM training. We also propose variance-aware group resampling to mitigate training instability. To further enhance robustness of pipeline generation, we develop two complementary mechanisms: operation merge, which filters spurious operations through multi-candidate consensus, and adaptive rollback, which offers runtime protection against information loss in data transformation. Experiments on two benchmark datasets show that, with the same LLM backbone, Operation-R1 achieves average absolute accuracy gains of 9.55 and 6.08 percentage points over multi-step preparation baselines, with 79% table compression and a 2.2$\times$ reduction in monetary cost.

Table union search (TUS) identifies tables that can be meaningfully combined by row-wise union with a given query table and is a core operation in data discovery over data lakes. Yet what it means for two tables to be unionable is inherently ambiguous: domain experts disagree even on seemingly simple cases, and existing benchmarks collapse this disagreement into binary labels, omitting the behavioral context behind human decisions. We take a human-centered view of table unionability and study how humans, traditional TUS methods, and large language models (LLMs) interact on this task. We introduce TUNE (Table UNionability with human Evaluation), a benchmark of 464 expert judgments over 26 table pairs that records binary decisions, confidence scores, decision times, interaction traces, textual explanations, and post-survey reflections. Using TUNE, we (i) characterize human performance, overconfidence, and metacognitive quality (calibration and resolution); (ii) benchmark state-of-the-art TUS methods (Starmie, SANTOS, D3L), revealing complementary strengths and systematic misalignment with expert judgments; and (iii) evaluate four experimental scenarios that combine human behavioral signals and TUS features using classical ML models and LLMs. Our best configuration reaches 84% accuracy, improving over both human majority vote and the strongest standalone TUS method, while LLMs act as useful second opinions but are sensitive to conflicting signals. Overall, our results suggest that unionability labels reflect a structured yet imperfect human decision process and that hybrid human–model pipelines provide more reliable and interpretable unionability assessments.

Generating coherent and factually grounded text from structured data is a core challenge in natural language generation, with appli- cations in scientific communication, medical documentation, and automated reporting. Existing datasets primarily focus on open- domain or simplified table formats, limiting progress in more com- plex, high-stakes domains. We present SciTables, a new dataset and evaluation framework for scientific table-to-text generation, addressing the gap in existing resources that focus largely on open-domain or simplified tables. Our dataset is constructed from Computer Science papers on arXiv (2017–2023) and features complex tables rich in numeric, symbolic, and mathematical content paired with naturally occurring textual descriptions. We develop a scalable, semi-automated pipeline to extract, clean, and align tables with their associated text, preserving domain-specific language while minimizing annotation cost. The resulting benchmark poses realistic challenges for current models and supports evaluation beyond semantic similarity, including factual accuracy, relevance, and multiple forms of reasoning. We conduct extensive experiments with state-of-the-art generation models and show that while current models achieve strong semantic alignment with reference descriptions, they struggle with higher-order reasoning, aggregation, and factual grounding as table complexity increases. Our work provides a realistic and scalable benchmark for advancing faithful, informative, and reasoning-aware table-to-text generation in scientific domains.

Large-scale crowdsourcing with high-quality results, such as online surveys and data labeling tasks, is in wide demand. Existing techniques on task assignment result quality optimization, however, have addressed only a part of optimization space that does not necessarily reflect the real-world problem. For example, in reality, the proper worker set for task assignment and the workers’ submissions to the task are non-obvious in advance, which is not considered by existing techniques. Hence, this paper discusses a task assignment algorithm that dynamically probes the proper worker set(s) and worker submission models for the task to optimize task assignments in terms of quality, time, and expense. Specifically, we introduce CrowdBwO (Crowd Bandit with Optimization), a novel multi-armed bandit algorithm that is based on batched bandits and bandits with Knapsack and incorporates worker submission models. CrowdBwO dynamically determines and utilizes proper worker set(s) and worker submission models for each task under uncertainty to achieve high-performance crowdsourcing. We conducted extensive experiments with synthetic workers and real workers to evaluate CrowdBwO in two specific problem settings. Our extensive experimental results demonstrate that CrowdBwO is significant for real-world crowdsourcing and has a high performance.

For real-time analysis of up-to-date data, hybrid transaction/analytical processing (HTAP) systems have been extensively studied. In general, three techniques play a critical role in HTAP systems, which are resource isolation, consistency model, and data sharing. However, there still lacks a benchmark suite that could comprehensively cover the three techniques. The core challenges come from the requirements of: (a) consistent workload resource consumption (provide workloads with the same computational complexity); (b) query-oriented freshness evaluation (focus on the degree of version staleness in the range of queried data); (c) precise data sharing efficiency measurement (catch the synchronization status accurately). In this paper, we propose Vodka to address the above challenges. For resource isolation, we formalize the change of query cardinalities under dynamic modifications, and manipulate the cardinalities of various query operators to ensure consistent query complexity comparisons under any data size. For consistency model, we design a column value grained version management strategy based on which query-oriented freshness is calculated. For data sharing, we design a lightweight point query driven method to check the synchronization status accurately. We finally conduct extensive experiments on three representative systems to justify our designs and provide insights for future system developments.

TPCx-AI is an industry standard benchmark for evaluating the end-to-end performance of machine learning systems and the underlying hardware configurations. In the database community, individual parts of the dataset and the workloads are used to evaluate preprocessing methods and systems for fast inference. In both of these cases, the datasets and workloads are used based on the characteristics defined in the specification. Upon analysis of TPCx-AI's dataset and use cases, we observe that the official implementation of TPCx-AI's kit diverges from the specification, does not evaluate the capabilities of the system under test, and impacts the overall performance in a benchmark run. In this paper, we investigate the benchmarking debt accumulated in the TPCx-AI dataset and the workloads. We identify properties that impact the benchmark's performance, including runtime and quality of use cases, the defined metrics and their thresholds, workload discrepancies, and data errors. Our analysis shows that all use cases and datasets contain benchmarking debts, impacting the training and serving runtimes by up to 350x and 800x, respectively. By addressing these debts, we observe an end-to-end throughput increase of up to 3.8x over the default TPCx-AI implementation.

We introduce SQL-Exchange, a framework for mapping SQL queries across different database schemas by preserving the source query structure while adapting domain-specific elements to align with the target schema. We investigate the conditions under which such mappings are feasible and beneficial, and examine their impact on enhancing the in-context learning performance of text-to-SQL systems as a downstream task. Our comprehensive evaluation across multiple model families and benchmark datasets---assessing structural alignment with source queries, execution validity on target databases, and semantic correctness---demonstrates that SQL-Exchange is effective across a wide range of schemas and query types. Our results further show that both in-context prompting with mapped queries and fine-tuning on mapped data consistently yield higher text-to-SQL performance than using examples drawn directly from the source schema.

We present the design and implementation of a RAG-based AI system benchmarking (RAGPerf) framework for characterizing the system behaviors of RAG pipelines. To facilitate detailed profiling and fine-grained performance analysis, RAGPerf decouples the RAG workflow into several modular components — embedding, indexing, retrieval, reranking, and generation. RAGPerf offers the flexibility for users to configure the core parameters of each component and examine their impact on the end-to-end query performance and quality. RAGPerf has a workload generator to model real-world scenarios by supporting diverse datasets (e.g., text, pdf, code, and audio), different retrieval and update ratios, and query distributions. RAGPerf also supports different embedding models, major vector databases such as LanceDB, Milvus, Qdrant, Chroma, and Elasticsearch, as well as different LLMs for content generation. It automates the collection of performance metrics (i.e., end-to-end query throughput, host/GPU memory footprint, and CPU/GPU utilization) and accuracy metrics (i.e., context recall, query accuracy, and factual consistency). We demonstrate the capabilities of RAGPerf through a comprehensive set of experiments and open source its codebase at GitHub. Our evaluation shows that RAGPerf incurs negligible performance overhead.

Materialized views (MVs) accelerate OLAP and data-warehouse workloads by precomputing reusable subexpressions, but practical MV-based query acceleration is a multi-stage pipeline: candidate enumeration, view selection under storage budgets, and query rewriting inside the optimizer. Existing evaluations typically study only parts of this pipeline and within a single system, leaving end-to-end trade-offs and cross-system behavior unclear. In this paper, we benchmark MV-based query rewriting by jointly evaluating enumeration, selection, and rewriting with a modular evaluation framework and by using controlled ablations. We also introduce a cross-engine protocol allowing us to compare systems that expose only execution plans by contrasting native optimizer-level rewriting with portable SQL rewriting baselines when available. Across representative academic methods and modern open-source and commercial systems, we find strong interaction effects between stages and large variability in rewriter MV usage and realized savings. We identify recurring failure modes that explain performance regressions after rewriting. Our results highlight which pipeline stages most often limit performance and provide evidence to guide future MV enumeration, selection, and rewriting designs.

Near-duplicate text alignment is the task of identifying, among the texts in a corpus, all the subsequences (\ie substrings) that are similar to a given query. Traditional approaches rely on seeding–extension–filtering heuristics, which lack accuracy guarantees and require many hard-to-tune parameters. Recent methods leverage min-hash techniques under the following hash-based framework: index by grouping all the subsequences using their min-hash, and for any query, use the index to find all the min-hash sketches that are similar to the query's sketch. These methods guarantee to report all the subsequences whose estimated \textit{unweighted} Jaccard similarity with the query exceeds a user-provided threshold and are efficient. However, they fail to account for token importance, or even token frequency, which limits their applicability in real-world scenarios where tokens carry weights, such as TF-IDF. To overcome this limitation, in this paper, we propose \mono, an approach that supports near-duplicate text alignment under \textit{weighted} Jaccard similarity using consistent weighted sampling. \mono achieves optimality within the above hash-based framework. For example, when token weights are proportional to their frequencies, \mono generates $O(n + n\log f_T)$ groups (in expectation due to hashing) for a text of length $n$, where $f_T$ is the maximum token frequency in the text. Each group takes $O(1)$ space and represents a few subsequences sharing the same consistent weighted sampling. We further prove that this bound is asymptotically tight: any algorithm must produce $\Omega(n + n \log f_T)$ groups in expectation in the worst case. Such an optimality over a wide range of weight functions is achieved based on multiple key insights into the hashing structure under consistent weighted sampling and is thus non-trivial. Extensive experiments demonstrate that \mono outperforms the state-of-the-art by up to $26\times$ in index construction time, reduces index size by up to $30\%$, and improves query latency by up to $3\times$, while exhibiting superior scalability.

Large Language Models (LLMs) are being increasingly used within data systems to process large datasets with text fields. A broad class of such tasks involves a semantic join—joining two tables based on a natural language predicate per pair of tuples, evaluated using an LLM. Semantic joins generalize tasks such as entity matching and record categorization, as well as more complex text understanding tasks. A naive implementation is expensive as it requires invoking an LLM for every pair of rows in the cross product. Existing approaches mitigate this cost by first applying embedding-based semantic similarity to filter candidate pairs, deferring to an LLM only when similarity scores are deemed inconclusive. However, these methods yield limited gains in practice, since semantic similarity may not reliably predict the join outcome—resulting in costs close to the naive approach. We propose Featurized-Decomposition Join (FDJ for short), a novel approach for performing semantic joins that significantly reduces cost while preserving quality. FDJ automatically extracts features and combines them into a logical expression in conjunctive normal form that we call a featurized decomposition to effectively prune out non-matching pairs. A featurized decomposition extracts key information from text records and performs inexpensive comparisons on the extracted features. We show how to use LLMs to automatically extract reliable features and compose them into logical expressions while providing statistical guarantees on the output result—an inherently challenging problem due to dependencies among features. Experiments on real-world datasets show up to 10 times reduction in cost compared with the state-of-the-art while providing the same quality guarantees.

A two-stage pipeline is commonly used to identify similar text passages in large document corpora: First, a fast approach produces potential matches, which are then examined in detail. Existing approaches for the first step consider only syntactic information and miss semantically similar passages that are syntactically dissimilar. To address this, we define the novel problem of semantic document alignment as a semantic set-similarity problem on k-width windows. For two documents S and T, an exhaustive baseline that evaluates all |S|x|T| window pairs is computationally infeasible since assessing the similarity of a single pair requires O(k³) time. We propose SeDA, which combines a sophisticated candidate generation technique with a bound cascade to drastically reduce the number of expensive window comparisons. It further exploits overlapping windows to efficiently compute both the bounds and the final similarity scores. Our empirical results on three large document corpora indicate that SeDA prunes over 99% of the window similarity computations, resulting in response-time improvements of 1.5-3 orders of magnitude over the baseline solution and 2-5 orders of magnitude over SBERT. Compared to purely syntactic competitors, SeDA provides competitive runtimes and achieves superior result quality, i.e., near-optimal F1-Score of precision/recall and matching the performance of purely semantic methods such as SBERT.

Large Language Models (LLMs) have recently shown strong performance on Entity Resolution (ER). Additionally, akin to their prowess in providing accurate predictions, these models often generate self-explanations alongside their predictions through prompting. While such self-explanations are appealing due to their negligible computational cost, their actual reliability remains largely unexplored. In this paper, we conduct the first large-scale, systematic evaluation of LLM self-explanations for ER, focusing on saliency-based and counterfactual explanations at both the attribute and token levels. Across three LLMs, ten datasets, and multiple prompting strategies, we show that self-explanations are often unstable, weakly faithful, and poorly aligned with counterfactual evidence, revealing a substantial gap between plausibility and causal relevance. We further demonstrate that established post-hoc explanation methods provide significantly higher trustworthiness, but at a prohibitive computational cost when applied to LLMs. To bridge this gap, we introduce \uncerta{}, a hybrid explanation framework that leverages self-explanations as priors to guide post-hoc exploration. \uncerta{} achieves explanation quality comparable to post-hoc methods while reducing cost by up to an order of magnitude.

Explanation techniques such as local interpretable model-agnostic explanation (LIME) provide reasons behind decisions made by machine-learning models. These methods typically use a set of features and their values as inputs and identify those that significantly influence the final decision. However, machine-learning models for entity matching operate on two sets of tokens or records, each representing an entity, to determine whether they refer to the same real-world entity. Explanations for entity-matching decisions are more convincing when they highlight contributing pairs of tokens within the pair of records, rather than focusing on individual tokens alone. In this sense, existing explanation techniques are insufficient for entity matching. Therefore, we propose a new method, Pair INterpretation for Entity matching (PINE), which takes two records as input, and outputs correlated token pairs as an explanation for an entity-matching decision. Our extensive experiments on public datasets demonstrate that the extracted token pairs exhibit strong correlations and serve as interpretable evidence for matching records.

Log-structured merge-trees (LSM-trees) are widely adopted in modern storage systems for high write throughput, but suffer from significant write amplification. Key-value (KV) separation mitigates this issue but introduces higher space overhead. To improve cost efficiency and resource elasticity, modern storage systems increasingly adopt compute-storage disaggregated architectures. However, disaggregation increases network overhead for data access, degrading write performance. It also prolongs garbage collection (GC), which increases the space cost of KV-separated LSM-trees. In this paper, we propose Terark-DS, a high-performance and storage-efficient KV separation storage engine on disaggregated storage. To achieve both high performance and low cost, Terark-DS employs differentiated redundancy based on LSM-tree access patterns, adaptive write-ahead logging that switches between serial and parallel modes for different batch sizes, and a network-efficient GC design to accelerate GC execution. Experiments show that Terark-DS outperforms existing disaggregated LSM-trees by 20.4%-63.9% in write throughput while reducing total costs by 22.7%-58.6%.

Key-value stores underpin a wide range of applications due to their simplicity and efficiency. Log-Structured Merge Trees (LSM-trees) dominate as their underlying structure, excelling at handling rapidly growing data. Recent research has focused on optimizing LSM-tree performance under static workloads with fixed read–write ratios. However, real-world workloads are highly dynamic, and existing workload-aware approaches often struggle to sustain optimal performance or incur substantial transition overhead when workload patterns shift. To address this, we propose ElasticLSM, which removes traditional LSM-tree structural constraints to allow more flexible management actions (i.e., compactions and write stalls) creating greater opportunities for continuous performance optimization. We further design Arce, a lightweight compaction decision engine that guides ElasticLSM in selecting the optimal action from its expanded action space. Building on these components, we implement ArceKV, a full-fledged key-value store atop RocksDB. Extensive evaluations demonstrate that ArceKV outperforms state-of-the-art compaction strategies across diverse workloads, delivering around 3$\times$ faster performance in dynamic scenarios.

High read and write performance is important for generic key-value stores, which are foundational to modern applications and databases. Yet, achieving high performance for mixed and dynamic workloads is challenging due to fundamental trade-offs between memory use and I/O for retrieval and updates. Past work emphasizes the trade-off between read- and write-optimization as expressed through primary data structure, in combination with read-memory trade-off mechanisms like caching and filtering. This raises re-tuning costs as optimal trade-off targets change, due to restructuring of stored data. We show that write-memory trade-off mechanisms are under-developed in current designs, and propose a new approach to dynamic key-value store optimization using a novel read-/write-balanced on-disk structure, the TurtleTree, and flexible read-/write-memory tuning knobs. We describe how to avoid in-memory bottlenecks to achieve high performance across a wide tuning range. When evaluated using YCSB, our prototype TurtleKV matches state-of-the-art SplinterDB for inserts, and is 5x/12x faster than RockDB/WiredTiger. In mixed workloads, TurtleKV is 16-25% faster than SplinterDB, >4x RocksDB, and 3-6x WiredTiger. TurtleKV is 2-9x faster than the others for point-query workloads, and has the best scan rate of the write-optimized systems tested.

Modern data-intensive applications, from microservices to real-time AI serving, demand consistently low tail latency from backend storage. However, Log-Structured Merge-tree (LSM)-based Key-Value Stores (KVSs) like RocksDB are structurally prone to unpredictable write stalls. These stalls stem from a fundamental architectural decoupling of foreground write ingress and background data reorganization. By design, the system absorbs foreground writes at maximum speed without monitoring its actual time-varying compaction capacity. As a result, it accumulates internal pressure until rigid capacity thresholds are breached, triggering reactive safeguards that abruptly freeze all foreground writes. Relying on this reactive ``stop-and-go'' approach induces a persistent limit-cycle behavior, undermining long-run predictability and strict latency guarantees. We reframe write stalls as a continuous control problem. S-RocksDB is a sustainable admission controller that regulates foreground ingress to match the system's time-varying compaction capacity. Since this capacity varies at runtime, S-RocksDB employs online reinforcement learning to discover a sustainable admission rate. To ensure safe learning, a three-state operational model (SAFE, SEMI-SAFE, UNSAFE) confines exploration to stable conditions and deploys deterministic guardrails before stalls can occur. In 24-hour evaluations, S-RocksDB reduces over 64.3 million stall events to just 69, bounds P99.99 tail latency to sub-0.11 ms, and delivers predictable throughput with the lowest resource footprint among all compared systems.

Log-Structured Merge-Trees (LSM-trees) dominate persistent key-value storage but suffer from high write amplification from 10x to 30x under random workloads due to repeated compaction. This overhead becomes prohibitive for large values with uniformly distributed keys, a workload common in content-addressable storage, deduplication systems, and blockchain validators. We present Tidehunter, a storage engine that eliminates value compaction by treating the Write-Ahead Log (WAL) as permanent storage rather than a temporary recovery buffer. Values are never overwritten; and small, lazily-flushed index tables map keys to WAL positions. Tidehunter introduces (a) lock-free writes that saturate NVMe drives through atomic allocation and parallel copying, (b) an optimistic index structure that exploits uniform key distributions for single-roundtrip lookups, and (c) epoch-based pruning that reclaims space without blocking writes. On a 1,TB dataset with 1,KB values, Tidehunter achieves 830K writes per second, that is 8.4x higher than RocksDB and 2.9x higher than BlobDB, while improving point queries by 1.7x and existence checks by 15.6x. We validate real-world impact by integrating Tidehunter into Sui, a high-throughput blockchain, where it maintains stable throughput and latency under loads that cause RocksDB-backed validators to collapse. Tidehunter is production-ready and is being deployed in production within Sui.

Subgraph matching is a core operation in graph analytics, supporting a broad spectrum of applications from social network analysis to bioinformatics. Recent GPU-based approaches accelerate subgraph matching by leveraging parallelism but rely on a coarse-grained execution model that suffers from scalability and efficiency issues due to high memory overhead and thread underutilization. In this paper, we propose gMatch, a hardware-efficient subgraph matching approach on GPUs. gMatch introduces a fine-grained execution model that reduces memory consumption and enables flexible task scheduling among threads. We further design warp-level batch exploration and lightweight load balancing to improve execution efficiency and scalability. Experiments on diverse workloads and real-world datasets show that gMatch outperforms state-of-the-art subgraph matching methods, including STMatch, T-DFS, and EGSM, in both performance and scalability. We also compare against state-of-the-art systems for mining small patterns, such as BEEP and G$^2$Miner. While these systems achieve better performance on small datasets, gMatch scales to substantially larger queries and datasets, where existing approaches degrade or fail to complete.

A temporal graph is an undirected graph where each edge is associated with a timestamp indicating when it occurs. As a fundamental topic in graph analysis, community search (CS) in temporal graphs has received much attention. Existing CS works on temporal graphs typically identify sets of vertices that form a $k$-core within a specific time window (temporal $k$-core). However, they overlook the duration of a temporal community, which is the continues time period that its members remain unchanged. Intuitively, the longer the duration of a temporal community, the higher its stability. Long-duration communities are useful in many areas, such as event detection and network analysis. In this paper, we introduce a novel community model, called temporal durable community (TDC), which is the temporal $k$-core with the longest duration in the temporal graph, and aim to efficiently find the TDC containing a query vertex. To solve this problem, we first propose a novel online algorithm based on binary search. We further develop two index structures that can quickly determine the duration of a given temporal $k$-core, followed by query algorithms. Experiments on ten real large temporal graphs show that our TDC model is effective for finding stable communities, and our index-based query algorithms are up to five orders of magnitude faster than the online algorithm.

Subgraph matching is a core task in graph analytics, widely used in domains such as biology, finance, and social networks. Existing top $k$ diversified methods typically focus on maximizing vertex coverage, but often return results in the same region, limiting topological diversity. We propose the Distance-Diversified Top-$k$ Subgraph Matching (DT$k$SM) problem, which selects $k$ isomorphic matches with maximal pairwise topological distances to better capture global graph structure. To address its computational challenges, we introduce the Partition based Distance Diversity (PDD) framework, which partitions the graph and retrieves diverse matches from distant regions. To further enhance efficiency, we develop two optimizations: embedding-driven partition filtering and densest-based partition selection over a Partition Adjacency Graph. Experiments on 12 real world datasets show our approach achieves up to four orders of magnitude speedup over baselines, with 95\% of results reaching 80\% of optimal distance diversity and 100\% coverage diversity.

The NP-hard problem of subgraph matching calls to detect all matchings of a smaller query graph within a larger data graph. The problem is fundamental in graph analysis and query answering, as it facilitates the understanding and analysis of the larger graph. Nevertheless, existing subgraph matching methods return results from one location of the graph before moving to another location, while the total results may be in the order of billions or even trillions; under these circumstances, existing methods may only present a portion of the results within reasonable time or space, which is not representative of the totality of results. This predicament leads to a biased representation of the data graph. In this paper, we study the problem of coverage in subgraph matching and propose Mix & Match (M&M) an algorithm that quickly returns results that are representative of the whole data graph. M&M achieves higher coverage employing a combination of global exploration, which prioritizes the exploration of nodes at the first level of backtracking that may enlarge coverage, and local exploration, which improves backtracking efficiency by pruning exploration paths that do not increase coverage. Our experimental study shows that M&M finds on average twice as many unique nodes as state-of-the-art algorithms in the same time.

We address the subgraph enumeration problem: given an unlabeled pattern graph 𝑝 and an unlabeled data graph 𝐺, find all subgraphs in 𝐺 isomorphic to 𝑝. Unlike labeled matching, the absence of label constraints creates exponentially larger search spaces with limited pruning opportunities. To address this challenge, we follow tree decomposition (TD) approaches that break complex patterns into smaller subgraphs (bags), compute matches for each bag, and join them to obtain final results. However, existing TD approaches suffer from suboptimal decomposition selection, incomplete symmetry-breaking usage, and expensive intermediate result materialization. We present MDSE (Minimal Decomposition-based Subgraph Enumeration) with three key contributions. We introduce minimal fractional hypertree decompositions (MinFHDs) that ensure compact bags and an efficient algorithm to explore all optimal-width decompositions. We develop new symmetry-breaking integration using complete rule sets with systematic selection for maximum pruning effect. To reduce materialization costs, we design MixJoin by embedding final result assembly within bag processing and formulate an enhanced cost model for attribute orders, incorporating both intersection and materialization overhead. Evaluation across 101 pattern graphs and 8 real-world datasets shows MDSE substantially outperforms existing algorithms.

LLMs enable an exciting new class of data processing applications over large collections of unstructured documents. Several new programming frameworks have enabled developers to build these applications by composing them out of semantic operators: a declarative set of AI-powered data transformations with natural language specifications. These include LLM-powered maps, filters, joins, etc. used for document processing tasks such as information extraction, summarization, and more. While systems of semantic operators have achieved strong performance on benchmarks, they can be difficult to optimize. An optimizer for this setting must determine how to physically implement each semantic operator in a way that optimizes the system globally. Existing optimizers are limited in the number of optimizations they can apply, and most (if not all) cannot optimize system quality, cost, or latency subject to constraint(s) on the other dimensions. In this paper we present Abacus, an extensible, cost-based optimizer which searches for the best implementation of a semantic operator system given a (possibly constrained) optimization objective. Abacus estimates operator performance by leveraging a minimal set of validation examples, prior beliefs about operator performance, and/or an LLM judge. We evaluate Abacus on document processing workloads in the biomedical and legal domains (BioDEX; CUAD) and multi-modal question answering (MMQA). We demonstrate that, on-average, systems optimized by Abacus achieve 6.7%-39.4% better quality and are 10.8x cheaper and 3.4x faster than the next best system.

Heuristic query rewriting has long complemented cost-based optimization to improve performance. Such rewrites transform SQL queries into semantically equivalent forms that are easier or faster to execute. Examples are standardizing expressions, eliminating redundancy, propagating constants, pushing down selections and projections, unnesting queries, and utilizing constraints. Modern DBMSs implement hundreds to thousands of such rules, but maintaining them is notoriously difficult. The interactions among rules are complex, and their static nature and application order prevent adaptation to specific query and database characteristics. Recent approaches that use large language models (LLMs) for query rewriting show promise but face challenges regarding the large search space, reliable query verification, and exploitation of metadata. We present ReSequel, an outer optimization layer on top of existing DBMSs to rewrite SQL queries using LLMs. ReSequel leverages catalog and statistical metadata to infer template-specific rules that guide the LLM toward effective query transformations. We generate, verify, and rank rewritten query variants on sampled data to ensure result correctness and runtime improvements. Our experiments cover eight benchmarks: JOB, TPC-H, Stats(-CEB), Public BI, IMDB, DSB, and StackOverflow; multiple DBMSs: PostgreSQL, MySQL, and DuckDB; as well as LLM-based query rewriting baselines. ReSequel yields workload-level speedups of up to 16x over native DBMSs and 22x over LLM-based systems, with individual queries exceeding 600x, across eight benchmarks and three DBMSs.

We present a benchmark targeting a novel class of systems: semantic query processing engines. Those systems rely inherently on generative and reasoning capabilities of state-of-the-art large language models (LLMs). They extend SQL with semantic operators, configured by natural language instructions, that are evaluated via LLMs and enable users to perform various operations on multimodal data. Our benchmark introduces diversity across three key dimensions: scenarios, modalities, and operators. Included are scenarios ranging from movie review analysis to car damage detection. Within these scenarios, we cover different data modalities, including images, audio, and text. Finally, the queries involve a diverse set of operators, including semantic filters, joins, mappings, ranking, and classification operators. We evaluated our benchmark on three academic systems (LOTUS, Palimpzest, and ThalamusDB) and one industrial system, Google BigQuery. Although these results reflect a snapshot of systems under continuous development, our study offers crucial insights into their current strengths and weaknesses, illuminating promising directions for future research.

Practitioners are increasingly turning to Extract-Load-Transform (ELT) pipelines with the widespread adoption of cloud data warehouses. However, designing these pipelines often involves significant manual work to ensure correctness. Recent advances in AI-based methods, which have shown strong capabilities in data tasks, such as text-to-SQL, present an opportunity to alleviate manual efforts in developing ELT pipelines. Unfortunately, current benchmarks in data engineering only evaluate isolated tasks, such as using data tools and writing data transformation queries, leaving a significant gap in evaluating AI agents for generating end-to-end ELT pipelines. To fill this gap, we introduce ELT-Bench, an end-to-end benchmark designed to assess the capabilities of AI agents to build ELT pipelines. ELT-Bench consists of 100 pipelines, including 835 source tables and 203 data models across various domains. By simulating realistic scenarios involving the integration of diverse data sources and the use of popular data tools, ELT-Bench evaluates AI agents’ abilities in handling complex data engineering workflows. AI agents must interact with databases and data tools, write code and SQL queries, and orchestrate every pipeline stage. We evaluate four representative code agents with six popular Large Language Models (LLMs) on ELT-Bench. The highest-performing agent, OpenHands CodeActAgent Claude-3.5-Sonnet, correctly generates only 11.3% of data models, with an average cost of $1.41 and 72.2 steps per pipeline. Our experimental results demonstrate the challenges of ELT-Bench and highlight the need for a more advanced AI agent to reduce manual effort in ELT workflows.

Recent advances in large language models (LLMs) transform how machine learning (ML) pipelines are developed and evaluated. LLMs enable a new type of workload, agentic pipeline search, in which autonomous or semi-autonomous agents generate, validate, and optimize complete data science pipelines. These agents predominantly operate over popular Python ML libraries and exhibit highly exploratory behavior. This results in thousands of executions for data profiling, pipeline generation, and iterative refinement of pipeline stages and hyperparameters. However, the existing Python-based ML ecosystem is built around libraries such as Pandas and scikit-learn, which are designed for human-centric, interactive, sequential workflows and remain constrained by Python¡¯s interpretive execution model, library-level isolation, and limited runtime support for executing large numbers of pipelines. Meanwhile, many high-performance ML systems proposed by the systems community either target narrow workload classes or require specialized programming models, which limits their integration with the Python ML ecosystem and makes them largely ill-suited for adoption by LLM-based agents. This growing mismatch exposes a fundamental systems challenge in supporting agentic pipeline search at scale. We therefore propose stratum, a unified system infrastructure that decouples pipeline execution from planning and reasoning during agentic pipeline search. Stratum integrates seamlessly with existing Python libraries, compiles batches of agent- or human-generated pipelines into optimized execution graphs, and efficiently executes them across heterogeneous backends, including a novel Rust-based runtime. We present stratum's architectural vision along with an early prototype, discuss key design decisions, and outline open challenges and research directions. Finally, preliminary experiments show that stratum can significantly speed up large-scale agentic pipeline search up to 16.6x.

Query optimization (QO) remains a fundamental challenge in the database community. Despite decades of research, cost-based QO (CQO) is still susceptible to performance regressions due to inherent inaccuracies in cardinality estimation, cost modeling, and plan enumeration. To mitigate the instability, modern databases employ SQL plan management (SPM), which reuses curated plans and bypasses CQO. However, there exists a fundamental issue in SPM: how can we efficiently identify the optimal plans to manage? The existing approach falls short due to low generalizability and poor interpretability. Thus, we argue for revisiting this problem from a novel perspective, where we intervene the sensitivity of CQO through well-designed cost scaling knobs. Nevertheless, this transformation poses three key challenges: (1) efficient search guidance, (2) comprehensive semantic utilization, and (3) cost-effective performance evaluation. To address these challenges, we propose OBELISK, an offline Bayesian optimization-informed query plannIng framework, with language model reasoning over cost scaling knobs. OBELISK is training-free and can efficiently find optimal query plan through a closed-loop process: a timeout-constrained Bayesian optimization technique to identify promising knob subspaces, thereby informing the search; a feedback-aware self-evolving reasoner to recommend knob configurations; and a lightweight evaluator with history-based admission gatekeeper to avoid redundant evaluations. Extensive experiments on well-established benchmarks demonstrate the effectiveness and superiority of OBELISK.

Machine learning for database systems has achieved significant success in various database components, such as cost estimation, query optimization, index selection, view recommendation, and semantic equivalence detection. However, these solutions typically focus on a single task and normally need a large amount of labeled data for the task to train machine learning models. Even if a solution can be adapted for a different task, it will require recollecting labeled data for each new task, which is typically much more time-consuming than model training. While dataset collection is relatively easier for some tasks, it can be prohibitively expensive for others. A natural solution is to use transfer learning techniques to adapt learned knowledge from one task to another. However, we show that naive transfer learning methods perform poorly and are only as good as training from scratch. Their failures are mainly due to three challenges: (1) the source model is not robust as it is optimized to its task only; (2) the size of the target dataset is small; and (3) the inevitable distribution shift when changing tasks. To overcome these challenges, we first study the task transfer problem in query plan representation and propose a new framework TATA for the problem. Specifically, to address the lack of robustness in the source model, TATA incorporates a self-supervised component during the pretraining stage. Specifically, we design a query plan decoder to reconstruct the original query plan from its representation, ensuring the model preserves key features. This leads to more robust and transferable query plan representations. Next, to address the issues of small datasets and distribution shift, TATA generates an arbitrary number of query plans for the target task and assigns them realistic pseudo labels. This is achieved by utilizing both strong database domain knowledge and available datasets. Through extensive experiments, we show that TATA delivers substantial improvements on task transfer, achieving up to 5× reduction in dataset collection cost when transferring from cost estimation to two representative target tasks: query optimization and index selection. We demonstrate compatibility with three distinct query plan representation models, establishing broader applicability than prior transfer approaches.

Query Plan Representation (QPR) is central to workload modeling, with various deep-learning based architectures proposed in the literature. Our work is motivated by two key observations: (i) the research community still lacks clarity on which model, if any, best suits the QPR problem; and (ii) while transformers have revolutionized many fields, their potential for QPR remains largely underexplored. This study examines the strengths and challenges of Graph Transformers for QPR. We introduce a new taxonomy that unifies deep-learning based QPR techniques along key design axes. Our benchmark analysis of common QPR architectures reveals that Graph Transformer Networks (GTNs) consistently outperform alternatives, but can degrade under limited training data. To address this, we propose novel data augmentation techniques to enhance training diversity and refine GTN architectures by replacing ineffective language-model-inspired components with techniques better suited for query plans. Evaluation on JOB, TPC-H, and TPC-DS benchmarks shows that with sufficient training data, enhanced GTNs outperform existing models for capturing complex queries (JOB Full and TPC-DS) and enable the query embedder trained on TPC-DS to generalize to TPC-H queries out of the box.

Hybrid Transactional-Analytical Processing (HTAP) has attracted growing attention from both academia and industry. Most HTAP systems adopt a dual-engine architecture, maintaining separate row and column engines to achieve workload isolation: row engines excel at transactional workloads, while column engines are optimized for analytical queries. For such systems, dispatching queries to the appropriate engine with ultra-low latency is highly desirable but remains challenging. Existing approaches often rely on traditional cost estimation, which is often inaccurate and fails to adapt to dynamic workload patterns. Moreover, they generally overlook resource balancing when dispatching workloads. In this paper, we present AQD, an online Adaptive Query Dispatcher framework. AQD operates in two phases: (1) in the offline phase, it trains a LightGBM classifier using self-paced, Taylor-weighted boosting that emphasizes costly mispredictions; (2) in the online phase, it employs a LinTS-Delta bandit to adapt to workload drift via execution feedback, while a Mahalanobis-based regulator ensures balanced CPU and memory utilization across the two engines. We integrate AQD into PolarDB and evaluate it on standard benchmarks as well as real-world datasets. Experimental results show that AQD reduces average query latency by over 90% compared to cost-threshold dispatching and improves HyBench score by 15% over the cost-threshold method and 9% over the current SOTA BRAD.

Quantum annealers offer a promising sampling-based computing paradigm for large-scale combinatorial optimization. However, directly using them to solve database optimization problems in real-time scenarios remains challenging due to strict hardware constraints and the opacity of commercial hybrid solvers. To address these challenges, we present QDBO, a white-box quantum-augmented database optimizer that directly leverages low-level quantum sampling on a quantum annealer. It first performs offline reduction to produce embeddable QUBO instances via multiple mapping strategies that trade off efficiency and quality. It then applies an online iterative relaxation correction procedure that uses sampling feedback to correct the reduced QUBO across iterations, enabling controllable quality improvements under varying time budgets. We integrate QDBO with the PostgreSQL query optimizer to construct Q²O-QDBO for join order optimization. Evaluations on the Join Order Benchmark (JOB) and the Cardinality Estimation Benchmark (CEB) show that Q²O-QDBO improves 62 out of 113 JOB queries, and achieves up to 49.36× execution-time speedup and 34.65× end-to-end speedup on the CEB workload. Evaluations on synthetic queries with up to 50 relations show that Q²O-QDBO achieves significantly lower end-to-end latency while maintaining similar solution quality compared with black-box quantum solvers. To demonstrate generality, we further integrate QDBO with PostgreSQL for index selection on TPC-H, where QDBO achieves up to 2.64× workload speedup over the empty-index baseline and outperforms classical and black-box solver baselines. These results demonstrate that using QDBO to solve large-scale database optimization problems in real-time settings is promising.

Modern high-performance OLTP systems are increasingly bottlenecked by kernel network stack and context switches arising from dispatching tasks between the network stack and DBMS worker threads. While kernel-bypass TCP stacks improve performance, they often sacrifice compatibility and robustness, in addition to leaving performance opportunities on the table due to TCP's byte-stream interface. We present \textbf{Tux}, a kernel-bypass networking stack designed for database systems that achieves high performance without giving up compatibility and robustness. \tux addresses these challenges by (1) introducing a message‑based transport protocol that decouples reliability from in‑order delivery and natively preserves message boundaries without framing or copy overhead inherent in byte-stream interface; (2) providing a flexible pushdown abstraction that lets database engines execute DBMS-specific logic directly on the network cores to avoid context-switch overhead and to exploit message-based interface; and (3) leveraging eBPF/XDP to reuse well‑maintained kernel NIC drivers for compatibility and operational ease. We implement \tux in a library called \libtux, offering both zero‑change “compatibility” mode and minimal‑change “pushdown” mode. Our implementation, \libtux, evaluated on VoltDB, Redis, ScyllaDB, Memcached, and LeanStore, improves throughput up to 2.3x, reduces median and 99th percentile latencies by up to 2.6x and 4.7x, compared to existing kernel-bypass systems with minimal modifications.

Data processing units, or DPUs, are equipped with hardware accelerators for compute-intensive data path tasks. Although DPUs’ SoC cores are wimpier than the host’s, hardware accelerators are typically orders of magnitude faster than CPUs. Harvesting DPU hardware accelerators for database systems could significantly increase throughput and save host CPU cycles. However, due to the heterogeneity of DPUs’ hardware configurations and performance characteristics, it is challenging to offer a unified and portable solution for cloud data processing systems to harvest the compute resources on DPUs across generations and vendors. Additionally, due to DPU resource constraints, offloaded compute tasks need to be carefully optimized and scheduled to achieve high efficiency and avoid performance regression. To address these challenges, we introduce two levels of abstraction: dpKernels, which are unified, efficient, and portable primitives that abstract DPU compute resources (i.e., hardware accelerators and SoC cores) for cloud data systems, and dpManager, an onboard management framework that abstracts specific DPU platforms for dpKernels to deliver their promises with optimized, scheduled, and cross-platform executions. The benefits of our proposal have been validated by the high performance of DPU-accelerated data processing for various workloads, systems, and DPU hardware.

This paper presents MGI, a general communication framework for performing data processing tasks in massive GPU infrastructures. Inter-GPU data transfer performance is crucial to multi-GPU data processing, and existing solutions repeatedly implement the same set of communication optimizations. MGI identifies these techniques and applies them judiciously behind a simple interface. Enabling MGI are (1) a central controller that models relevant hardware resources as an annotated graph and automates infrastructure- level optimizations to construct transfer plans and (2) a scalable data plane where buffers and executors are carefully designed to incorporate device- and link-level optimizations to execute data transfers efficiently. Our experiments on a variety of GPU infrastructures and workloads show that MGI significantly improves multi-GPU data processing performance compared to existing frameworks.

Ray tracing (RT) cores are a new type of hardware that have been actively integrated into modern GPUs. Recent studies have demonstrated that RT cores can deliver much higher performance than GPU CUDA cores and CPUs for general-purpose data processing tasks like table scan. In this paper, we propose RayDB, the first query engine that leverages RT cores to accelerate database query processing. RayDB transforms the core part of the query execution that involves multiple operators into one single ray tracing job. With a set of proposed encoding and ray launching techniques, RayDB effectively exploits RT cores to accelerate diverse workloads. Experimental results show that RayDB outperforms the state-of-the-art GPU-based query engine by up to 18.3×.

We study how modern database systems can leverage the Linux io_uring interface for efficient, low-overhead I/O. io_uring is an asynchronous system call batching interface that unifies storage and network operations, addressing limitations of existing Linux I/O interfaces. However, naively replacing traditional I/O interfaces with io_uring does not necessarily yield performance benefits. To demonstrate when io_uring delivers the greatest benefits and how to use it effectively in modern database systems, we evaluate it in two use cases: Integrating io_uring into a storage-bound buffer manager and using it for high-throughput data shuffling in network-bound analytical workloads. We further analyze how advanced io_uring features, such as registered buffers and passthrough I/O, affect end-to-end performance. Our study shows when low-level optimizations translate into tangible system-wide gains and how architectural choices influence these benefits. Building on these insights, we derive practical guidelines for designing I/O-intensive systems using io_uring and validate their effectiveness in a case study of PostgreSQL’s recent io_uring integration, where applying our guidelines yields a performance improvement of 14%.

Data Processing Units (DPUs) are PCIe network cards (SmartNICs) equipped with specialized hardware accelerators for data processing. DPUs offer the opportunity to process data near the hardware network stack (near-network). By enabling near-network computation, DPUs reduce CPU load and improve end-to-end performance, an increasingly attractive approach to trends like compute-storage disaggregation and real-time data ingestion. However, existing research on DPU-based processing often overlooks hardware acceleration or relies on static offloading to the ARM subsystem, leaving open questions about how best to split work (or co-process) with the host CPU. In this paper, we analyze near-network hardware acceleration with co-processing on DPUs, revealing that DPU performance varies significantly depending on input data types, task and query-imposed configurations. Through our micro-benchmark experiments, we explore partial offloads and co-processing strategies that demonstrate the trade-offs between higher throughput against reconfiguration overhead on DPUs. Our findings offer practical insights for data systems practitioners seeking to leverage near-network accelerators in data processing pipelines.

Recent standardization efforts for graph databases lead to standard query languages like GQL and SQL/PGQ, and constraint languages like Property Graph Constraints (PG-Constraints). In this paper, we embark on the study of repairing property graphs under PG-Constraints. We identify a significant subset of PG-Constraints, encoding denial constraints and including recursion as a key feature, while still permitting automata-based structural analyses of errors. We present a comprehensive repair pipeline for these constraints to repair Property Graphs, involving changes in the graph topology and leading to node, edge and, optionally, label deletions. We investigate three algorithmic strategies for the repair procedure, based on Integer Linear Programming (ILP), a naive, and an LP-guided greedy algorithm. Our experiments on various real-world datasets reveal that repairing with label deletions can achieve a 59% reduction in deletions compared to node/edge deletions. Moreover, the LP-guided greedy algorithm offers a runtime advantage of up to 97% compared to the ILP strategy, while matching the same quality.

Conjunctive regular path queries (CRPQs) form a critical backbone of modern graph query languages, integrating subgraph matching with regular path queries (RPQs). Despite their ubiquity in applications like social networks, finance, and scientific data analysis, CRPQ optimization lacks a unified framework, relying instead on heuristic combinations of disjoint techniques for subgraph matching and RPQs. This paper bridges this gap by introducing a novel algebraic optimization framework for CRPQs. We propose a hypergraph query model that enables composability, addressing a longstanding challenge in graph query languages including GQL and SQL/PGQ, and define six core operators (TI, KC, SJ, UNION, INV, and SCAN) to abstract CRPQ semantics. Leveraging algebraic transformation rules, we enumerate a rich space of equivalent query plans and devise a cost-based optimizer to select near-optimal plans for execution. Implemented based on MillenniumDB and Neo4j, our framework achieves significant speedups on CRPQs extracted from the WDBench and LDBC SNB benchmarks.

A property graph stores information in the form of a network of nodes and edges, annotated with labels and properties (i.e. attributes). Even though various forms of functional dependencies, uniqueness constraints, and keys have been proposed for graph data, no study has been hitherto undertaken that builds upon and utilizes these concepts to assemble a comprehensive proposal for graph normalization. An elementary proposal merely maps the nodes in the graph schema to a relational schema and deploys relational normalization techniques. Unfortunately, this proposal disregards the graph structure and thereby forfeits the opportunity for structural normalization. In this paper, we define five structural graph normal forms that extend relational normal forms building on concepts of keys and graph functional dependencies. Based on acyclic graph patterns, these normal forms apply to any data graph, address previously overlooked sources of inconsistency, and support structure-aware integrity preservation beyond node attributes. We showcase the applicability and effectiveness of these normal forms through experimentation.

Knowledge Graphs (KGs) model semantic relationships between entities and are widely used in tasks such as question answering, recommendation, and large language model training. As KGs grow to billions of triples, storing and querying them on local devices becomes infeasible and also raises privacy concerns. KG summarization methods produce compact representations, yet existing methods are either static or not attuned to user interests. In this paper, we propose Sankofa, a query-aware, incremental, and online KG summarization method. Sankofa maintains personalized summaries on-device by incrementally updating them in response to new queries and data using a random-walk-based adaptation of node-centric Personalized PageRank, efficiently identifying the most relevant nodes while bounding summary size. We provide formal guarantees for our PPR approximation and demonstrate experimentally that Sankofa outperforms existing personalized KG summarization techniques in both speed and accuracy, enabling adaptive, privacy-preserving KG summaries that evolve with user interests and dynamic knowledge graphs.

Ranging from batch scripts to computational notebooks, modern data science tools rely on massive and evolving object graphs that represent structured data, models, plots, and more. Persisting these objects is critical, not only to enhance system robustness against unexpected failures but also to support continuous, non-linear data exploration via versioning. Existing object persistence mechanisms (e.g., Pickle, Dill) rely on complete snapshotting, often redundantly storing unchanged objects during execution and exploration, resulting in significant inefficiency in both time and storage. Unlike DBMSs, data science systems lack centralized buffer managers that track dirty objects. Worse, object states span various locations such as memory heaps, shared memory, GPUs, and remote machines, making dirty object identification fundamentally more challenging. In this work, we propose a graph-based object store, named Chipmink, that acts like the centralized buffer manager. Unlike static pages in DBMSs, persistence units in Chipmink are dynamically induced by partitioning objects into appropriate subgroups (called pods), minimizing expected persistence costs based on object sizes and reference structure. These pods effectively isolate dirty objects, enabling efficient partial persistence. Our experiments show that Chipmink is general, supporting libraries that rely on shared memory, GPUs, and remote objects. Moreover, Chipmink achieves up to 36.5× smaller storage sizes and 12.4× faster persistence than the best baselines in real-world notebooks and scripts.

Graph database management systems (GDBMSes) are widely adopted for their efficient handling of graph traversal queries that capture complex relationships. Recently, a class of modern GDBMSes appeared that were designed to offer explicit support for schemaless property graph models (PGMs), providing users with a high degree of flexibility. However, GDBMSes in this class often suffer from performance bottlenecks in analytical database queries—typically involving operations such as group-by and aggregation. We argue that a major cause is that schemaless processing is not treated as a primary design requirement across the storage, query-processing, and optimization layers. To address this, we propose TurboLynx, a novel graph analytics engine that holistically integrates the schemaless property at every layer of the system—from storage to query processing and optimization. TurboLynx organizes graph data into cost-based clusters, called graphlets, and stores them in a columnar format. By adopting a graphlet-aware query optimizer and processor, TurboLynx efficiently handles both graph traversal and analytical workloads in a single system. Our comprehensive evaluation on LDBC SNB Interactive, TPC-H, and DBpedia demonstrates that TurboLynx outperforms state-of-the-art GDBMSes by up to 183.9x and leading RDBMSs by up to 41.27x.

Unstructured data is pervasive, but analytical queries demand structured representations, creating a significant extraction challenge. Existing methods like RAG lack schema awareness and struggle with cross-document alignment, leading to high error rates. We propose ReDD (Relational Deep Dive), a framework that dynamically discovers query-specific schemas, populates relational tables, and ensures error-aware extraction with provable guarantees. ReDD features a two-stage pipeline: (1) Iterative Schema Discovery (ISD) identifies minimal, joinable schemas tailored to each query, and (2) Tabular Data Population (TDP) extracts and corrects data using lightweight classifiers trained on LLM hidden states. A main contribution of ReDD is SCAPE, a statistically calibrated method for error detection with coverage guarantees, and SCAPE-HYB, a hybrid approach that optimizes the trade-off between accuracy and human correction costs. Experiments across diverse datasets demonstrate ReDD's effectiveness, reducing data extraction errors from up to 30% to below 1% while maintaining high schema completeness (100% recall) and precision. ReDD's modular design enables fine-grained control over accuracy-cost trade-offs, making it a robust solution for high-stakes analytical queries over unstructured corpora.

Unstructured database management systems (UDBMSes) leverage machine learning to apply the relational model to modalities beyond tables, such as documents, images and videos. Queries in a UDBMS consist of logical operators for which the UDBMS chooses physical implementations (e.g., different models) with the goal to optimize both query latency and accuracy. However, many operators only expose a coarse-grained set of implementations, forcing the UDBMS to excessively sacrifice either accuracy or latency without middle-ground options. For example, an entity matching operator can either be implemented through small, specialized models or large, general-purpose models (e.g., Large Language Models) --- while the former struggles on challenging inputs, the latter is more accurate but incurs orders of magnitude more computation. In this work, we aim to address this issue with model cascades, which seek to process “easy” inputs with small models and only resort to large models when necessary. However, cascades incur higher memory usage and additional data transfer between GPU memory and arithmetic units, which often slows queries compared to single models. To address this issue, we introduce Ken, a dedicated UDBMS execution engine that dynamically adapts its use of cascades to the query load, and optimizes the GPU placement and invocation scheduling of the cascade models. Compared to baselines, Ken achieves 1.7x - 3.3x latency reductions when combining similar models for a single operator, and 122x latency reductions when combining models with orders of magnitude size differences in a multi-operator query.

One year ago, we open-sourced DocETL, a declarative system for LLM-powered data processing that, as of November 2025, has 3.2K GitHub stars and users across domains (e.g., journalism, law, medicine, policy, finance, and urban planning). In DocETL, users build pipelines by composing operators described in natural language, also known as semantic operators, with an LLM executing each operator's logic. However, due to complexity in the operator or the data it operates on, LLMs often give inaccurate results. To address this challenge, DocETL introduced rewrite directives, or abstract rules that guide LLM agents in rewriting pipelines by decomposing operators or data. For example, decomposing a single filter("is this email sent from an executive and discussing fraud?") into the conjunction of two separate semantic filters may improve accuracy. However, DocETL only optimizes for accuracy, not cost. How do we optimize for both? We present MOAR (Multi-Objective Agentic Rewrites), a new optimizer for DocETL. To target cost optimization, we introduce two new categories of directives and extend all three existing categories with new ones, bringing the total to over 30 directives—more than doubling what DocETL originally had. Moreover, since operators can interact with each other unpredictably due to LLM behavior, optimizing operators or sub-pipelines individually can yield suboptimal overall plans. Recognizing this, we design a new global search algorithm that explores rewrites in the context of entire pipelines. Since the space of rewrites is infinite—pipelines can be rewritten in many ways, and each rewritten pipeline can itself be rewritten—our algorithm adapts a multi-armed bandit framework to prioritize which pipelines to rewrite. Across six workloads, MOAR achieves 27% higher accuracy than ABACUS, the next-best optimizer, while matching its best accuracy at 55% of its cost.

Unstructured data, such as text and images, are converted into high-dimensional vectors to capture their semantics for effective data retrieval. Approximate Nearest Neighbor Search (ANNS) over these vectors has become a fundamental technique in many domains, including retrieval-augmented generation and recommendation systems. With an ever-increasing volume of data, existing distributed solutions typically segment data across multiple machine nodes, handling query processing in a MapReduce-style approach. However, this approach suffers from reduced indexing efficiency and increased computational overhead, resulting in limited performance enhancement despite investing several times more resources. In this work, we propose RED-ANNS, a distributed ANNS approach on an RDMA network. The core idea is to maintain a logically full graph across a shared memory space of multiple nodes and utilize Remote Direct Memory Access (RDMA) to search the distributed graph, thereby avoiding the reduction in indexing efficiency caused by segmentation. The key to making this approach effective is to address the overhead associated with remote accesses. We reduce remote access frequency through locality-aware data placement and affinity-based query scheduling, while we hide remote access latency with a dependency-relaxed best-first search algorithm. Extensive experiments demonstrate that RED-ANNS achieves a performance improvement of up to 2.5× over MapReduce-style approaches and up to 5.3× over open source vector databases.

Learning over (distributed) relational tables (LRT) requires applying SQL queries that involve costly operations such as joins and unions to compose the training dataset, followed by model training atop the query results. This paradigm often introduces considerable computation, storage, and communication overhead that cannot be addressed by existing approaches. In this paper, we propose TablePuppet, a generic framework that can significantly reduce the overhead of LRT. We first formalize the LRT problem as learning over union of conjunctive queries (UCQ). We then decompose the learning process into two steps: (1) learning over join (LoJ), followed by (2) learning over union (LoU). In essence, LoJ pushes learning down to the individual tables being joined, while LoU further pushes learning down to the horizontal partitions/shards of each table. This two-step decomposition approach enables efficient distributed training without raw table sharing while preserving model accuracy. TablePuppet supports two standard ML optimization strategies, stochastic gradient descent (SGD) and alternating direction method of multipliers (ADMM), and can accommodate both centralized and distributed environments. In addition, TablePuppet introduces computation and communication optimizations to handle duplicate tuples introduced by joins, while further offering privacy guarantees for federated learning (FL) scenarios. Experimental evaluation results show that TablePuppet achieves comparable model accuracy to centralized baselines running directly on top of the SQL query results. Moreover, the SGD and ADMM algorithms implemented atop TablePuppet take less communication/training time to converge compared to the state-of-the-art approaches.

Labeled Property Graphs (LPGs) have gained widespread adoption, supported by the ongoing standardization of the Graph Query Language (GQL). As LPGs are frequently constructed through the integration of heterogeneous data sources, inconsistencies and errors may propagate into query results. To explain and validate such results, it is essential to determine which parts of the input graph contributed to a given answer -- an aspect captured by data provenance. In this paper, we present a formal definition of why-provenance tailored specifically to GQL, characterizing the fine-grained subgraph that contribute to a query answer. Building on the Core-GQL algebraic foundation, we further propose an efficient query-rewriting-based algorithm for computing provenance, leveraging the native execution capabilities of existing GQL-compliant graph database systems. Our extensive experimental evaluation demonstrates the feasibility and scalability of our approach, showing that provenance can be computed with moderate overhead that scales effectively with graph size.

Graph-based Approximate Nearest Neighbor Search (ANNS) indices must support continuous vector updates while maintaining both high search performance and low update overhead for real-world applications such as RAG systems and streaming services. Existing in-place update methods often lose search accuracy due to graph connectivity loss and suffer high overhead from expensive deletion operations. We propose CONDA, a dynamic graph-based index featuring a topology-aware pruning rule with bidirectional link reinforcement and a lightweight lazy deletion scheme. Extensive experiments demonstrate that CONDA improves search recall by up to 24.5% over state-of-the-art methods while achieving 1.90x higher update throughput.

Disk-based approximate nearest neighbor search (ANNS) incurs high I/O overhead due to frequent disk accesses during index traversal. Approximate caching, which reuses the results of past queries to serve future similar queries, offers a promising approach to bypass disk searches. However, existing approaches suffer from two limitations. First, their hit predicates fail to simultaneously achieve high throughput and high accuracy, as they do not adapt to the varying local neighbor density. Second, they lack an effective refresh mechanism to maintain cache correctness during vector updates. We present Aker, an approximate cache for disk-based ANNS. Aker addresses these limitations through two core design choices. First, we introduce a per-query similarity threshold that each cache entry dynamically adjusts based on cache hit patterns. This design enables Aker to adapt to neighborhood densities to preserve both efficiency and accuracy. Second, we propose del-consistency, a consistency model that applies deletions eagerly and insertions lazily. Under this model, Aker implements a low-overhead refresh mechanism that bounds cache staleness while preserving search accuracy. We integrate Aker into pgvector and evaluate it on representative workloads. Aker improves recall by up to 64 percentage points over prior solutions and increases QPS by up to 3.2×, while using 0.6× the memory of pgvector's shared buffers.

We study the k-nearest neighbors (kNN) search problem on the domain of sets. Given a query set, the goal is to retrieve the k most similar sets from a collection according to a specified similarity function. Most existing solutions for set similarity queries focus on range search or top-k joins, which typically assume and exploit high similarity thresholds. We observe that existing approaches for kNN search - as well as adaptations of range search and top-k algorithms - exhibit poor performance due to low selectivity of their filtering techniques and high index traversal costs. To address these limitations, we propose PAIL, a kNN search algorithm for sets that supports a wide range of similarity functions. PAIL implements the positional filter - a filter that was previously used for post-filtering of candidates returned by an index - directly into a novel index structure to effectively prune candidates. To efficiently traverse only the necessary parts of the index, PAIL leverages the monotonicity of the similarity functions with respect to positional information. This traversal enables early termination by ensuring that the index is accessed in descending order of similarity upper bounds. To reduce index access overhead, we propose size grouping and eager reading of index entries that relax filter tightness for improved overall performance. Extensive experiments across diverse datasets demonstrate that PAIL consistently outperforms competing algorithms by up to three orders of magnitude.

Approximate nearest neighbor search (ANNS) is a critical component in modern data-intensive applications, but its performance is often hindered by the use of a static query budget parameter. This one-size-fits-all approach, even if well-tuned, fails to account for the varying difficulty of individual queries, inevitably leading to suboptimal latency on easy queries and poor accuracy on hard ones. This paper introduces QBAT, a query-aware budget autotuner designed to resolve this dilemma. By analyzing query-specific features offline, QBAT dynamically allocates an appropriate budget for each query. We explore two predictive models: a highly accurate gradient-boosted decision tree and a simple, interpretable heuristic formula derived using the AlphaEvolve framework. These models can optimize budget allocation for both system performance or recall consistency priorities. Evaluations on large-scale datasets demonstrate that QBAT reduces total searched budget by up to 68.8% in the consistency mode on ScaNN, the state-of-the-art clustering-based ANNS method, while simultaneously enforcing a strict per-query recall target, a scenario where static budgets are notoriously inefficient and wasteful.

Approximate Nearest Neighbor Search (ANNS) underpins modern applications such as information retrieval and recommendation. With the rapid growth of vector data, efficient indexing for real-time vector search has become rudimentary. Existing CPU-based solutions support updates but suffer from low throughput, while GPU-accelerated systems deliver high performance but face challenges with dynamic updates and limited GPU memory, resulting in a critical performance gap for continuous, large-scale vector search requiring both accuracy and speed. In this paper, we present SVFusion, a GPU-CPU-disk collaborative framework for real-time vector search that bridges sophisticated GPU computation with online updates. SVFusion leverages a hierarchical vector index architecture that employs CPU-GPU co-processing, along with a workload-aware vector caching mechanism to maximize the efficiency of limited GPU memory. It further enhances performance through real-time coordination with CUDA multi-stream optimization and adaptive resource management, along with concurrency control that ensures data consistency under interleaved queries and updates. Empirical results demonstrate that SVFusion achieves significant improvements in query latency and throughput, exhibiting a 20.9$\times$ higher throughput on average and 1.3$\times$ to 50.7$\times$ lower latency compared to baseline methods, while maintaining high recall for large-scale datasets under various streaming workloads.

Approximate nearest neighbor (ANN) search on SSD-backed indexes is increasingly I/O-bound (I/O accounts for 70--90% of query latency). We present an I/O-first framework for disk-based ANN that organizes techniques along three dimensions: memory layout, disk layout, and search algorithm. We introduce a page-level complexity model that explains how page locality and path length jointly determine page reads, and we validate the model empirically. Using consistent implementations across four public datasets, we quantify both single-factor effects and cross-dimensional synergies. We find that (i) memory-resident navigation and dynamic width provide the strongest standalone gains; (ii) page shuffle and page search are weak alone but complementary together; and (iii) a principled composition, OctopusANN, substantially reduces I/O and achieves 4.1--37.9% higher throughput than the state-of-the-art system Starling and 87.5--149.5% higher throughput than DiskANN at matched Recall@10=90%. Finally, we distill actionable guidelines for selecting storage-centric or hybrid designs across diverse concurrency levels and accuracy constraints, advocating systematic composition rather than isolated tweaks when pushing the performance frontier of disk-based ANN.

GPUs are uniquely suited to accelerate (SQL) analytics workloads when datasets fit in the GPU High Bandwidth Memory (HBM). Unfortunately, GPU HBMs remain typically small when compared with lower-bandwidth CPU main memory. Current solutions to accelerate queries on large datasets include multi-GPU execution, processing smaller data batches, and hybrid execution with a connected device (e.g., CPUs). Unfortunately, these approaches are exposed to the limitations of lower main memory and host-to-device interconnect bandwidths, introduce additional I/O overheads, or incur higher costs. This is a substantial problem when trying to scale adoption of GPUs on larger datasets. Data compression can alleviate this bottleneck, but to avoid paying for costly decompression/decoding, an ideal solution must include computation primitives to operate directly on data in compressed form. This is the focus of our paper: a set of new methods for running queries directly on light-weight compressed data using schemes such as Run-Length Encoding (RLE), index encoding, bit-width reductions, and dictionary encoding. Our novelty includes operating on multiple RLE columns without decompression, handling heterogeneous column encodings, and leveraging PyTorch tensor operations for portability across devices. Experimental evaluations show speedups of an order of magnitude compared to state-of-the-art commercial CPU-only analytics systems, for real-world queries on a production dataset that would not fit into GPU memory uncompressed. This work paves the road for GPU adoption in a much broader set of use cases, and it is complementary to most other scale-out or fallback mechanisms.

The AI hardware boom has led modern data centers to adopt HPC-style architectures centered on distributed, GPU-centric computation. Large GPU clusters interconnected by fast RDMA networks and backed by high-bandwidth NVMe storage enable scalable computation and rapid access to storage-resident data. Tensor computation runtimes (TCRs), such as PyTorch, originally designed for AI workloads, have recently been shown to accelerate analytical workloads. However, prior work has primarily considered settings where the data fits in aggregated GPU memory. In this paper, we systematically study how TCRs can support scalable, distributed query processing for large-scale, storage-resident OLAP workloads. Although TCRs provide abstractions for network and storage I/O, naive use often underutilizes GPU and I/O bandwidth due to insufficient overlap between computation and data movement. As a core contribution, we present PystachIO, a prototype of a PyTorch-based distributed OLAP engine that combines fast network and storage I/O with key optimizations to maximize GPU, network, and storage utilization. Our evaluation shows up to 3x end-to-end speedups over existing distributed GPU-based query processing approaches.

GPU query backends achieve high throughput on analytical work- loads through massive parallelism, but lack indexing support that accelerates selective queries in CPU databases. Existing GPU index implementations face three limitations: (1) supporting conjunctive predicates only, (2) materializing intermediate results between in- dex access and query execution, and (3) assuming query boundaries align with pre-built index bins. We present a fused bitmap indexing approach that addresses these limitations. We introduce virtual query program that exe- cutes arbitrary boolean predicates with low overhead. We fuse index access with subsequent column lookups, joins, and aggre- gation, keeping intermediate results in registers and eliminating global-memory round-trips. To handle misaligned query bound- aries, we propose GPU friendly candidate checking that tracks three-valued row states (certain-in, certain-out, uncertain) through in-register boolean operations and verifies only the necessary can- didates, without accessing global memory. On Star Schema Benchmark SF=140 with RTX 5090 D, our fused bitmap index achieves up to 6.9× geometric-mean speed over our optimized non-indexed baseline built upon the Crystal GPU data- base query backend (Dense layout), and 4.3× with practical Sparse layout using less memory. Compared to current best compressed GPU bitmap implementation under perfect bin alignment (best case), our Sparse layout achieves 1.4× speed end-to-end. We show that generic elementwise-style GPU fusion achieves only 1.34× speed, while our pipeline reaches 3.19× with 0.8% overhead versus dedicated compile-time kernels. Results on an NVIDIA H800 server GPU show the approach remains stable across GPU architectures, with smaller but still consistent fusion benefits on server GPUs.

Graph Neural Networks (GNNs) have emerged as the state-of-the-art methodology for learning on graph-structured data, yet their performance is severely constrained by a fundamental mismatch between irregular graph sparsity and the rigid parallelism of modern hardware. While modern GPUs rely on Tensor Cores (TCs) to deliver massive computational throughput, these units demand strictly tiled, dense inputs—a requirement that conflicts with the extreme sparsity of real-world graphs. Existing frameworks fail to resolve this design conflict: they either fallback to legacy SIMT cores, leaving TCs underutilized, or they incur prohibitive memory bloat by forcing sparse data into dense tiles via excessive padding. To bridge this gap, we propose ThunderGNN, a hardware-aware acceleration system designed to reconcile graph irregularity with Tensor Core rigidity. ThunderGNN employs a unified co-design strategy comprising three key optimizations: (1) a sparsity-aware reordering algorithm that logically groups graph rows to maximize local density; (2) a Condensed Binarized Abstraction (CBA) storage layout that physically organizes the adjacency matrix into TC-aligned blocks without explicit zero-padding; and (3) a hardware-aware execution engine that efficiently streams compressed blocks directly into TCs. Extensive experiments on NVIDIA A100 GPUs demonstrate that ThunderGNN significantly outperforms state-of-the-art systems, achieving geometric mean speedups of 1.89X over DGL and 2.59X over PyG.

For the past two decades, the DB community has devoted substantial research to take advantage of cheap clusters of machines for distributed data analytics — we believe that we are at the beginning of a paradigm shift. The scaling laws and popularity of AI models lead to the deployment of incredibly powerful GPU clusters in commercial data centers. Compared to CPU-only solutions, these clusters deliver impressive improvements in per-node compute, memory bandwidth, and inter-node interconnect performance. In this paper, we study the problem of scaling analytical SQL queries on distributed clusters of GPUs, with the stated goal of establishing an upper bound on the likely performance gains. To do so, we build a prototype designed to maximize performance by leveraging ML/HPC best practices, such as group communication primitives for cross-device data movements. This allows us to conduct thorough performance experimentation to point our community towards a massive performance opportunity of at least 60x. To make these gains more relatable, before you can blink twice, our system can run all 22 queries of TPC-H at a 1TB scale factor!

Finding optimal join orders is among the most crucial steps to be performed by query optimisers. Though extensively studied in data management research, the problem remains far from solved: While query optimisers rely on exhaustive search methods to determine ideal solutions for small problems, such methods reach their limits once queries grow in size. Yet, large queries become increasingly common in real-world scenarios, and require suitable methods to generate efficient execution plans. While a variety of heuristics have been proposed for large-scale query optimisation, they suffer from degrading solution quality as queries grow in size, or feature highly sub-optimal worst-case behavior, as we will show. We propose a novel method based on the paradigm of mixed integer linear programming (MILP): By deriving a novel MILP model capable of optimising arbitrary bushy tree structures, we address the limitations of existing MILP methods for join ordering, and can rely on highly optimised MILP solvers to derive efficient tree structures that elude competing methods. To ensure optimisation efficiency, we embed our MILP method into a hybrid framework, which applies MILP solvers precisely where they provide the greatest advantage over competitors, while relying on more efficient methods for less complex optimisation steps. Thereby, our approach gracefully scales to extremely large query sizes joining up to 100 relations, and consistently achieves the most robust plan quality among a large variety of competing join ordering methods.

Minimizing intermediate results is critical for efficient multi-join query processing. Although the seminal Yannakakis algorithm offers strong guarantees for acyclic queries, cyclic queries remain an open challenge. In this paper, we propose SplitJoin, a framework that introduces split as a first-class query operator. By partitioning input tables into heavy and light parts, SplitJoin allows different data partitions to use distinct query plans, with the goal of reducing intermediate sizes using existing binary join engines. We systematically explore the design space for split-based optimizations, including threshold selection, split strategies, and join ordering after splits. Implemented as a front-end to DuckDB and Umbra, SplitJoin achieves substantial improvements: on DuckDB, SplitJoin completes 43 social network queries (vs. 29 natively), achieving 2.1x faster runtime and 7.9x smaller intermediates on average (up to 13.6x and 74x, respectively); on Umbra, it completes 45 queries (vs. 35), achieving 1.3x speedups and 1.2x smaller intermediates on average (up to 6.1x and 2.1x, respectively).

Datalog-based languages are regaining popularity as a powerful abstraction for expressing recursive computations in domains such as program analysis and graph processing. However, existing systems often face a trade-off between efficiency and extensibility. Engines like Souffle achieve high efficiency through domain-specific designs, but lack general-purpose flexibility. Others, like RecStep, offer modularity by layering Datalog on traditional databases, but struggle to integrate Datalog-specific optimizations. This paper bridges this gap by presenting FlowLog, a new Datalog engine that uses an explicit relational IR per-rule to cleanly separate recursive control (e.g., semi-naïve execution) from each rule's logical plan. This boundary lets us retain fine-grained, Datalog-aware optimizations at the logical layer, but also reuse off-the-shelf database primitives at execution. At the logical level (i.e. IR), we apply proven SQL optimizations, such as logic fusion and subplan reuse. To address high volatility in recursive workloads, we adopt a robustness-first approach that pairs a structural optimizer (avoiding worst-case joins) with sideways information passing (early filtering). Built atop Differential Dataflow—a mature framework for streaming analytics—FlowLog supports both batch and incremental Datalog and adds novel recursion-aware optimizations called Boolean (or algebraic) specialization. Our evaluation shows that FlowLog outperforms state-of-the-art Datalog engines and modern databases across a broad range of recursive workloads, achieving superior scalability while preserving a simple and extensible architecture.

Efficient join query execution remains a key challenge in modern database systems. Although a recent method, Robust Predicate Transfer (RPT), improves robustness against suboptimal join orders, it introduces significant overhead from redundant filter creation and inefficient data scanning. We present RPT+ that addresses these issues through three key improvements. First, we propose asymmetric transfer plans to reduce redundant Bloom filter constructions. Second, we design cascade filters to improve data scanning efficiency by enabling both block-level skipping and tuple-level filtering. Third, we introduce dynamic pipelines to allow runtime filter creation and transfer plan adjustment. We implemented RPT+ in DuckDB (v1.3.0) and evaluated it across multiple benchmarks, including the Join Order Benchmark (JOB), SQLStorm, TPC-H, and Appian. Compared to the baseline DuckDB, RPT+ achieves speedups of 1.47x on JOB, 1.28x on SQLStorm, 1.10x on TPC-H, and 1.01x on Appian. Importantly, it avoids the significant performance regressions observed with the original RPT. These results demonstrate that RPT+ not only improves query performance but also maintains the robustness of RPT across diverse workloads.

Window functions are among the most expressive features of modern SQL. Surprisingly, relatively little has been written about their optimization. Some techniques exist, such as pushing predicates through a window under ideal conditions, but known optimizations no longer apply when those conditions are even slightly unmet. We show that these limitations are not fundamental, but persist because a reasoning framework for window function optimization has been missing. We provide such a framework, introducing techniques we call Frame Analysis, Partition Analysis, and a new execution strategy called Co-Evaluation. These clarify when and how optimizations can be applied. Co-Evaluation, in particular, allows early evaluation of predicates even when they depend on the window function’s result. We present each technique and organize the re- sults as a table of algebraic equivalences for window functions. We test these optimizations in an open-source engine, where they never hurt performance and make certain common queries up to 40.7× faster, with larger tables yielding larger gains.

Graph Neural Networks (GNNs) have achieved great success in many applications, and mini-batch training has become the de facto standard for training GNNs on large-scale graphs. When developing mini-batch GNN training systems on CPU-GPU platforms, existing dedicated batching systems adopt a static workload-processor binding strategy, where the costly mini-batch preparation workload is exclusively assigned to either the CPU or the GPU. This leads to low utilization of CPU cores, PCIe bandwidth, and GPU computing capability, resulting in suboptimal training efficiency. To address this problem, we develop MorphGL, a novel GNN training system featuring a collective batching design. MorphGL adaptively dispatches the mini-batch preparation workload to both the CPU and GPU, ensuring that the workload distribution aligns with the CPU-GPU setup of the running machine for optimal efficiency. To maximize resource utilization, MorphGL employs the Dual-Buffer Scheduling algorithm to collectively schedule training stages across the CPU, PCIe, and GPU. Extensive experiments on three large real-world graphs with billions of edges and four machines with representative CPU-GPU configurations demonstrate that MorphGL consistently outperforms state-of-the-art GNN training systems, achieving up to 2.76x and 2.2x speedup over SALIENT and DUCATI, respectively.

Graph embedding maps graph nodes into low-dimensional vectors to support applications such as recommendation, fraud detection, and graph-based retrieval-augmented generation (GraphRAG). As graphs scale to billions of edges, scalable and efficient graph embedding has become increasingly important. Existing frameworks commonly adopt a sampling-training paradigm, in which mini-batches are constructed by sampling nodes and their neighbors. However, sampling is typically decoupled from evolving embedding quality, causing redundant exploration of well-trained regions while under-sampling undertrained nodes. At the system level, such decoupling further leads to excessive communication, serialized execution, and low resource utilization in distributed environments. We present FeLoG, a feedback loop-driven system for scalable distributed graph embedding. (1) FeLoG introduces feedback-coupled sampling and training, dynamically prioritizing undertrained nodes according to real-time embedding-quality feedback, thereby reducing redundant computation and accelerating convergence. (2) It employs activity-aware communication that compresses frequently occurring node sequences to reduce intra-machine PCIe traffic and selectively synchronizes frequently updated embeddings to reduce inter-machine communication. (3) It adopts a round-interleaved pipeline that overlaps next-round sampling with current-round training to improve CPU-GPU utilization. Experiments against six state-of-the-art baselines on large-scale graphs show that FeLoG achieves an average speedup of 27.9×, reduces communication cost by more than 53.1%, and sustains over 80% CPU-GPU utilization.

Multilayer (ML) graphs offer a convenient paradigm for modeling complex node-to-node interactions, such as social or semantic connections, as layers of a graph. In such graphs, FirmCore decomposition represents an established technique to identify cohesive groups of nodes with strong ties across layers. Unfortunately, the fastest FirmCore decomposition method fails to fully harness the resources, leading to underutilized and idle threads. Our main observation is that FirmCores enjoy a grid structure we call FC-Grid, which we exploit to distribute work among threads. Building on this structure, we introduce serial and parallel algorithms for multi-core CPUs, as well as the first GPU-based algorithm. Owing to this new design, our solutions show greatly improved performance and resource utilization. Our experiments on 12 datasets show 9× speedup on average for our serial version FC-Grid compared to existing serial methods. Furthermore, our parallel algorithm achieves an average 100.3× speedup over the state-of-the-art parallel algorithm. For the challenging NP-hard densest subgraph mining problem in ML graphs, our algorithms achieve 15× speedup on average.

With the growing adoption of graph neural networks (GNNs), explaining their predictions has become increasingly important. However, attributing predictions to specific edges or features remains computationally expensive. For example, classifying a node with 100 neighbors using a 3-layer GNN may involve identifying important edges from millions of candidate subgraphs. To address this challenge, we develop DistShap, a parallel algorithm that distributes Shapley value-based explanations across multiple GPUs. DistShap samples subgraphs in a distributed setting, executes GNN inference in parallel across GPUs, and solves a distributed least squares problem to compute edge importance scores. DistShap outperforms most existing GNN explanation methods in accuracy and is the first to scale to GNN models with millions of edges by using 128 GPUs.

Graph Neural Networks (GNNs) have become essential for solving graph-level tasks, such as classification and regression, across diverse domains including social networks and biology. However, existing GNNs struggle with the expressivity that captures complex structural patterns, and the generalization that ensures robust performance on diverse and noisy datasets. To address these challenges, we propose a novel GNN model that integrates a k-path rooted subgraph encoder, an adaptive graph contrastive learning approach, and a consistency-aware loss. The k-path rooted subgraph encoder enhances expressivity by capturing and distinguishing intricate substructures, with theoretical guarantees for counting paths and cycles. The adaptive graph contrastive learning framework improves generalization by generating domain-aware graph augmentations based on edge importance, while the consistency-aware loss ensures task-relevant properties are preserved across augmented views. Extensive experiments on 26 datasets spanning graph classification, regression, and realistic scenarios such as noise, class imbalance, and few-shot learning show that our model achieves superior performance against 18 state-of-the-art GNN models in both effectiveness and efficiency. The code is released in https://anonymous.4open.science/r/GEGNN.

Database Management Systems (DBMS) are crucial for efficient data management and access control, but their administration remains challenging for Database Administrators (DBAs). Tuning, in particular, is known to be difficult. Modern systems have many tuning parameters, but only a subset significantly impacts performance. Focusing on these influential parameters reduces the search space and optimizes performance. Current methods rely on costly warm-up phases and human expertise to identify important tuning parameters. In this paper, we present DOT, a dynamic knob selection and online sampling DBMS tuning algorithm. DOT uses Recursive Feature Elimination with Cross-Validation (RFECV) to prune low-importance tuning parameters and a Likelihood Ratio Test (LRT) strategy to balance exploration and exploitation. For parameter search, DOT uses a Bayesian Optimization (BO) algorithm to optimize configurations on-the-fly, eliminating the need for warm-up phases or prior knowledge (although existing knowledge can be incorporated). Experiments show that DOT achieves matching or outperforming performance compared to state-of-the-art tuners while substantially reducing tuning overhead.

Accurate performance prediction is critical for database tuning, resource provisioning, and performance debugging. Recent work applies machine learning to predict DBMS performance, but these models often require expensive retraining when deployment contexts change. We present Libra, an end-to-end transfer learning framework that builds accurate performance models with minimal target-context sampling. Libra addresses two key challenges: (1) selecting source contexts based on performance-relevant similarity, and (2) leveraging source context data without negative transfer. We introduce a novel context retrieval method based on $\pi$-profiles, which capture parameter sensitivity. Libra uses a multilayer perceptron to infer the target $\pi$-profile in one-shot, and compares it with those of past contexts to retrieve the most similar one. Libra then selects important parameters based on percentile performance ratios and focuses sampling on high-impact parameters to efficiently train the model. Experiments across 161 contexts (combination of 7 hardware environments and 23 workloads) show that Libra outperforms state-of-the-art methods in terms of sampling efficiency (up to 32$\times$ speedup) and prediction accuracy (95.6\% error reduction).

Apache Spark SQL is a cornerstone of modern big data analytics. However, optimizing Spark SQL performance is challenging due to its vast configuration space and the prohibitive cost of evaluating massive workloads. Existing tuning methods predominantly rely on full-fidelity evaluations, which are extremely time-consuming, often leading to suboptimal performance within practical budgets. While multi-fidelity optimization offers a potential solution, directly applying standard techniques—such as data volume reduction or early stopping—proves ineffective for Spark SQL as they fail to preserve performance correlations or represent true system bottlenecks. To address these challenges, we propose MFTune, an efficient multi-fidelity framework that introduces a query-based fidelity partitioning strategy, utilizing representative SQL subsets to provide accurate, low-cost proxies. To navigate the huge search space, MFTune incorporates a density-based optimization mechanism for automated knob and range compression, alongside an adapted transfer learning approach and a two-phase warm start to further accelerate the tuning process. Experimental results on TPC-H and TPC-DS benchmarks demonstrate that MFTune significantly outperforms five state-of-the-art tuning methods, identifying superior configurations within practical time constraints.

Log-Structured Merge (LSM) trees are used as the data structure of choice for key-value stores supporting a wide variety of applications. A common challenge for LSM-based systems is tuning them effectively, particularly as the complexity and number of tuning knobs increase. Prior work relies on expert-created cost models and expert-configured numerical solvers to produce high-quality tunings; however, these methods do not address tuning multiple instances at scale for various execution environments. On the other hand, using iterative learning, such as Bayesian Optimization (BO), relaxes the requirements for domain expertise and provides generalizability; however, it comes at a high cost, as it involves learning directly from database executions at deployment time. Furthermore, both approaches struggle with categorical tuning knobs that create a hard-to-navigate optimization space. To address these challenges, we introduce AXE, a novel learned LSM tuning paradigm that decomposes the tuning task into two steps. First, AXE trains a learned cost model using existing performance modeling or execution logs, acting as a surrogate cost function in the tuning process. Second, AXE efficiently generates arbitrarily many training samples for a learned tuner optimized to identify high-performance tunings using the learned cost model as its loss function. This task decomposition approach generalizes well for tuning simple and complex LSM designs and requires no retraining, allowing AXE to be used for tuning at scale. Compared to BO, AXE recommends higher performing tunings than BO 71% of the time while incurring 100× smaller tuning overhead. We further show that AXE requires less domain knowledge to produce optimal tunings than traditional expert-configured tuning pipelines. Lastly, we compare AXE to both state-of-the-art machine learning methods and analytical methods to show that AXE outperforms all other LSM tuning baselines.

The operation and maintenance (O&M) of database systems is critical to ensuring system availability and performance, typically requiring expert experience (e.g., identifying metric-to-anomaly relations) for effective diagnosis and recovery. However, existing automatic database O&M methods, including commercial products, cannot effectively utilize expert experience. On the one hand, rule-based methods only support basic O&M tasks (e.g., metric-based anomaly detection), which are mostly numerical equations and cannot effectively incorporate literal O&M experience (e.g., troubleshooting guidance in manuals). On the other hand, LLM-based methods, which retrieve fragmented information (e.g., standard documents + RAG), often generate inaccurate or generic results. To address these limitations, we present DBAIOps, a novel hybrid database O&M system that combines reasoning LLMs with knowledge graphs to achieve DBA-style diagnosis. First, DBAIOps introduces a heterogeneous graph model for representing the diagnosis experience, and proposes a semi-automatic graph construction algorithm to build that graph from thousands of documents. Second, DBAIOps develops a collection of (800+) reusable anomaly models that identify both directly alerted metrics and implicitly correlated experience and metrics. Third, for any given anomaly, DBAIOps employs an automatic graph evolution mechanism that explores the relevant paths over the graph and dynamically explores potential gaps (missing paths) without human intervention. Based on the explored diagnosis paths, DBAIOps leverages reasoning LLM (e.g., DeepSeek-R1) that inputs the relevant pathways, identifies root causes, and generates clear diagnosis reports for both DBAs and common users. Our evaluation over four mainstream database systems (Oracle, MySQL, PostgreSQL, DM8) demonstrates that DBAIOps outperforms state-of-the-art baselines, 34.85% and 47.22% higher in root cause and human evaluation accuracy, respectively. DBAIOps supports 25 database systems and has been deployed in 20 real-world scenarios, covering domains like finance, energy, and healthcare (https:// www.dbaiops.com).

Recent large language models (LLMs) are rapidly extending their context windows, yet inference throughput lags due to increasing GPU memory and bandwidth demands. This is because the key-value (KV) cache, an intermediate structure storing token representations, grows linearly with context length and requires an iterative linear scan for attention computation. A promising direction to accelerate long context inference is to exploit attention's inherent sparsity by offloading the KV cache to CPU memory and retrieving only a small subset of tokens important to the current generation step. However, prior sparse attention approaches struggle to balance accuracy and retrieval cost due to varying sparsity patterns and inefficient GPU-CPU memory management. We present RetroInfer, a vector storage engine that realizes a sparsity-based KV cache for long-context inference. RetroInfer introduces an Attention aWare VEctor index (wave index) which fundamentally improves the tradeoff between attention accuracy and retrieval cost through tripartite attention approximation, accuracy-bound attention estimation, and segmented clustering. We also design the wave buffer, a GPU-CPU buffer manager that assigns computation and manages data across heterogeneous hardware. We evaluate RetroInfer across a range of models and workloads, demonstrating up to 4.4x higher decoding throughput over full attention at 120K context and up to 12.2x over sparse attention baselines at 1 million tokens—all while preserving full-attention-level accuracy.

Serving long-context LLMs is challenging because request lengths and batch composition vary during token generation, causing the memory footprint to fluctuate significantly at runtime. Offloading KV caches to host memory limits effective memory usage, but existing static and predetermined offloading strategies cannot adapt to the rapidly shifting memory demands of long-context serving. This often leads to excessive CPU-to-GPU KV transfers that translate into latency spikes and frequent SLO violations. To address these challenges, we introduce OrbitFlow, a fine-grained and adaptive KV cache management system that meets latency SLOs in long-context LLM serving. OrbitFlow employs a lightweight ILP solver to decide which layers’ KV caches to retain on the GPU for each request, within memory capacity constraints. It continuously refines KV placements based on runtime feedback when the active plan becomes suboptimal during token generation. Under heavy load, OrbitFlow invokes a fallback mechanism to temporarily defer in-flight requests with large memory footprints, preserving overall SLO attainment. Our experiments demonstrate that OrbitFlow improves SLO attainment for TPOT and TBT by up to 66% and 48%, respectively, while reducing the 95th percentile latency by 38% and achieving up to 3.3× higher throughput compared to existing offloading methods.

Key-value (KV) caching is a widely used technique for boosting performance in database and storage systems. It keeps frequently accessed data in fast storage to minimize redundant data fetching and improve throughput. This same idea has been adopted in Large Language Models (LLMs), where it avoids recomputing the key and value states of previous tokens in attention heads during autoregressive decoding, thereby greatly accelerating inference. However, the KV cache in LLMs faces a significant challenge due to the substantial memory required to store these KV pairs in the inference process. This issue arises because each attention head in the LLM stores its own KV cache for all context tokens, leading to the cache size that grows linearly with sequence length. This has spurred research into efficient management of the KV cache of LLMs. One of the promising directions is KV cache budget allocation, with several approaches proposing head-level allocation as they recognize that different attention heads play distinct roles. However, these methods assess each head in isolation, overlooking their cooperative contributions within the model, which results in a deviation from their true impact. To address this limitation, we propose CoKV, a novel method that efficiently manages the KV cache in LLM inference by modeling the cooperation among attention heads as a cooperative game. By attributing the contribution of each head within the model in advance, CoKV can more effectively allocate the global KV cache budget in KV cache optimization techniques such as eviction and quantization. Extensive experiments demonstrate the effectiveness of CoKV on long-context benchmarks (e.g., LongBench, NIAH, and RULER) and mathematical reasoning benchmarks (e.g., GSM8K and MATH) across multiple model families, including Qwen, Llama, and Mistral.

The increasing deployment of large language models (LLMs) has magnified the computational and memory bottlenecks of autoregressive decoding, where low arithmetic intensity and bandwidth-bound kernels dominate inference cost. Weight pruning offers a promising remedy, but existing methods remain confined to either static pruning (SP)—which permanently removes redundant weights but lacks adaptivity—or dynamic pruning (DP)—which adapts to input sparsity but introduces runtime irregularity. This paper presents SPDP, a unified sparse-inference framework that integrates unstructured SP with input-adaptive DP for efficient LLM inference on GPUs. SPDP co-designs a new Tiled-Column-wise Bitmap Compressed (Tiled-CBC) format and two complementary GPU kernels: (1) a CUDA-core spMspV kernel featuring Hybrid Activation-aware Dynamic Shared-Memory Bitmap Decoding (HAD-SMBD) for fine-grained, runtime activation skipping, and (2) a Tensor-Core SpMM kernel optimized for prefill computation. This joint format–kernel design harmonizes static and dynamic sparsity, maintaining bandwidth-efficient memory access and high arithmetic intensity under both phases of LLM inference. Comprehensive evaluations on inference-optimized GPUs demonstrate that SPDP achieves 1.24×–1.37× average speedup (up to 2.51×) over state-of-the-art sparse frameworks such as SpInfer, while matching perplexity with up to 25\% higher sparsity. SPDP advances the inference efficiency–quality Pareto frontier, showing that unified static–dynamic pruning can deliver substantial throughput and performance-per-watt improvements in large-scale LLM serving.

The rise of compound AI serving that integrates multiple operators in a pipeline enables end-user applications such as generative AI- powered meeting companions, autonomous driving, and immersive gaming. These workloads span diverse deployment spaces, from cloud-only queries to edge-assisted ones across infrastructure tiers, often including both within an application. Achieving high service goodput—i.e., meeting service level objectives (SLOs) for pipeline latency, accuracy, and costs-requires joint planning of operators’ placement, configuration, and resource allocation. However, diverse SLOs, varying runtime environments (e.g., heterogeneous device speeds), and a large volume of queries competing for shared infrastructure explode the planning space, making real-time serving and cost-efficient deployment intractable with existing advances. This paper presents Compass, the first SLO-aware query planner that optimizes large-scale compound AI workloads across diverse deployment spaces. Compass decomposes the many-query, multi-SLO planning problem into tractable subproblems while preserving global decision quality, exploiting plan similarities within and across queries to slash the search steps. It further improves per-step efficiency with a plan profiler that performs selective profiling to achieve high-fidelity performance estimates at a fraction of the profiling cost. At runtime, Compass performs query-plan bipartite matching to maximize SLO goodput under resource contentions. Real-world evaluations show that Compass improves service goodput by 2.4–5.1x, reduces deployment costs by 3.8–4.5x, and accelerates planning by 4.2–10.5x, achieving service responsiveness within seconds and near-optimal decision quality.

Modern applications commonly leverage large, multi-modal foundation models. These applications often feature complex workflows that demand the storage and usage of similar models in multiple precisions. A straightforward approach is to maintain a separate file for each model precision (e.g., INT8, BF16), which is indeed the approach taken by many model providers such as HuggingFace and Ollama. However, this approach incurs excessive storage costs since a higher precision model (e.g., BF16) is a strict superset of a lower precision model (e.g., INT8) in terms of information. Unfortunately, simply maintaining only the higher-precision model and requiring every user to dynamically convert the model precision is not desirable because every user of lower precision models must pay the cost for model download and precision conversion. In this paper, we present QStore, a unified, lossless compression format for simultaneously storing a model in two (high and low) precisions efficiently. Instead of storing low-precision and high-precision models separately, QStore stores low-precision model and only the residual information needed to reconstruct high-precision models. The size of residual information is significantly smaller than the original high-precision models, thus, achieving high savings in storage cost. Moreover, Qstore does not compromise the speed of model loading. The low-precision models can be loaded quickly just like before. The high-precision models can also be reconstructed efficiently in memory by merging low-precision data and the residual with Qstore's lightweight decoding logic. We evaluate Qstore for compressing multiple precisions of popular foundation models, and show that Qstore reduces overall storage footprint by up to 2.2x (45% of the original size) while enabling up to 1.7x and 1.8x faster model saving and loading versus existing approaches.

The mining of pattern subgraphs, known as motifs, is a core task in the field of graph mining. Edges in real-world networks often have timestamps, so there is a need for temporal motif mining. A temporal motif is a richer structure that imposes timing constraints on the edges of the motif. Temporal motifs have used to analyze social networks, financial transactions, and biological networks. Motif counting in temporal graphs is particularly challenging. A graph with millions of edges can have trillions of temporal motifs, since the same edge can occur with multiple timestamps. There is a combinatorial explosion of possibilities, and state-of-the-art algorithms cannot manage motifs with more than four vertices. In this work, we present TIMEST: a general, fast, and accurate estimation algorithm to count temporal motifs of arbitrary sizes in temporal networks. Our approach introduces a temporal spanning tree sampler that leverages weighted sampling to generate substructures of target temporal motifs. This method carefully takes a subset of temporal constraints of the motif that can be jointly and efficiently sampled. TIMEST uses randomized estimation techniques to obtain accurate estimates of motif counts. We give theoretical guarantees on the running time and approximation guarantees of TIMEST. We perform an extensive experimental evaluation and show that TIMEST is both faster and more accurate than previous algorithms. Our CPU implementation exhibits an average speedup of 28X over state-of-the-art GPU implementation of the exact algorithm, and 6X speedup over SOTA approximate algorithms while consistently showcasing less than 5% error in most cases. For example, TIMEST can count the number of instances of a financial fraud temporal motif on a graph with about 10M edges in four minutes with 0.6% error, while exact methods take more than two days.

Temporal graphs serve as a critical foundation for modeling evolving interactions in domains ranging from financial networks to social media. Mining temporal motifs is essential for applications such as fraud detection, cybersecurity, and dynamic network analysis. However, conventional motif mining approaches treat each query independently, incurring significant redundant computations when similar substructures exist across multiple motifs. In this paper, we propose Mayura, a novel framework that unifies the mining of multiple temporal motifs by exploiting their inherent structural and temporal commonalities. Central to our approach is the Motif-Group Tree (MG-Tree), a hierarchical data structure that organizes related motifs and enables the reuse of common search paths, thereby reducing redundant computation. We propose a co-mining algorithm that leverages the MG-Tree and develop a flexible runtime capable of exploiting both CPU and GPU architectures for scalable performance. Empirical evaluations on diverse real-world datasets demonstrate that Mayura achieves substantial improvements over the state-of-the-art techniques that mine each motif individually, with an average speed-up of 2.4x on the CPU and 1.7x on the GPU, while maintaining the exactness required for high-stakes applications.

We study how to evaluate basic graph patterns (BGPs) over temporal labeled graphs--where each edge is associated with an interval of temporal validity--in a worst-case-optimal manner. We adopt a flexible query language in which users specify m quads of the form (subject, property, object, time), using constants or variables. The time component denotes the instant at which a particular edge is valid, and users may also include order relations between temporal constants or variables. The answer to such extended BGPs is the set of all valid variable assignments, including those that involve time. We describe an index structure that, for a temporal graph with N edges, requires O(N) space and can evaluate extended BGPs in worst-case optimal time O(Q* m log N), where Q* represents the maximum number of solutions for query Q over any temporal graph with the same number of instants of edge validities. We use our index to adapt Leapfrog Triejoin to the temporal graph setting and can therefore consider any variable evaluation ordering. Moreover, the same index yields worst-case-optimal guarantees for related query types, including snapshot evaluation, version queries, and other temporal variants. Experiments on real-world datasets show that our approach answers realistic queries in milliseconds with minimal space overhead.

Training memory-augmented Temporal Graph Neural Networks (M-TGNNs) efficiently and accurately remains challenging due to memory staleness, which arises when temporally dependent events are processed in the same batch and severely degrades accuracy at large batch sizes. We introduce PRISM, an M-TGNN training system that achieves staleness-freedom without giving up GPU parallelism by using multi-versioned memory vectors, so that each event in a batch can consume the memory version that is temporally consistent for it. PRISM formalizes a relaxed notion of staleness-freedom called lazy freshness, which allows for more parallelism than existing staleness-free approaches, and implements it through a multi-versioned memory refinement algorithm over a lightweight memory computation graph. On five temporal-graph benchmarks and three M-TGNN models (TGN, TNCN, APAN), PRISM improves the accuracy of existing models by up to 28% and surpasses the TGB leaderboard by 9.2%, while keeping training time competitive with parallel stale-memory systems (TGL, ETC) and consistently lower than stricter staleness-free baselines. PRISM thus provides a practical, staleness-free foundation for temporal graph learning.

Approximate Graph Pattern Mining (AGPM) is essential for analyzing large-scale graphs where exact counting is computationally prohibitive. While there exist numerous sampling-based AGPM systems, they all rely on uniform sampling and overlook the underlying probability distribution. This limitation restricts their scalability to a broader range of patterns. In this paper, we introduce AGIS, an extremely fast AGPM system capable of counting arbitrary patterns from huge graphs. AGIS employs structure-informed neighbor sampling, a novel sampling technique that deviates from uniformness but allocates specific sampling probabilities based on the pattern structure. We first derive the ideal sampling distribution for AGPM and then present a practical method to approximate it. Furthermore, we develop a method that balances convergence speed and computational overhead, determining when to use the approximated distribution. Experimental results demonstrate that AGIS significantly outperforms the state-of-the-art AGPM system, achieving 28.5x geometric mean speedup and more than 100,000x speedup in specific cases. Furthermore, AGIS is the only AGPM system that scales to graphs with tens of billions of edges and robustly handles diverse patterns, successfully providing accurate estimates within seconds. We will open-source AGIS to encourage further research in this field.

In this work, we present an efficient and cryptographically secure protocol for multi-key inner-join computation that addresses the limitations of existing approaches. Our protocol leverages established Circuit Private Set Intersection (PSI) techniques to privately compute left-joins over individual key columns. These results are then securely aggregated into a final inner-join table using a novel private permutation protocol, which achieves a speedup of approximately 2× to 4× over prior methods. To enhance utility without compromising privacy, we introduce a deduplication mechanism based on ordered left-joins, enabling first-key deduplication while revealing no sensitive matching information. We formally analyze the security of our construction in the semi-honest model. Furthermore, we optimize the equality testing subroutine, a core component of Circuit PSI, reducing its round complexity without an increase in computational overhead. Empirically, our system demonstrates strong scalability, processing up to 1.8 × 104 records of 4 keys per second per CPU core. This represents a significant improvement over industry solutions such as Google’s [24] and Meta’s [4], which are not only slower but also reveal more information about the input databases.

Secure multi-party computation (MPC) enables collaborative analytics over private datasets but faces critical efficiency barriers. State-of-the-art MPC protocols for query processing with joins incur prohibitive computational costs. While sampling-based approximate query processing has revolutionized plaintext analytics, its extension to secure settings remains unexplored. This paper proposes the first efficient and secure protocol for sampling over joins. The protocol achieves near-linear asymptotic complexity while preserving the confidentiality of input and metadata (e.g., degree and join sizes). It supports a wide range of queries, including multi-way joins, comparisons, and group-by operations, and is universally applicable across secure computation settings. Experiments demonstrate significant speedups over secure join-then-sample baselines. This work bridges the gap between theoretical secure computation and practical relational analytics, advancing scalable real-world secure collaborative analytics and learning scenarios.

Obliviousness has been regarded as an essential property in encrypted databases (EDBs) for mitigating leakage from access patterns. Yet despite decades of work, practical oblivious graph processing remains an open problem. In particular, all existing approaches fail to enable the design of index-free adjacency (IFA), i.e., each vertex preserves the physical positions of its neighbors. However, IFA has been widely recognized as necessary for efficient graph processing and is fundamental in native graph databases (e.g., Neo4j). In this work, we propose a core technique named delayed duplication to resolve the conflict between IFA and obliviousness. To the best of our knowledge, we are the first to address this conflict with both practicality and strict security. Based on the new technique, we utilize elaborate data structures to develop a new EDB named Grove for processing expressive graph queries. The experimental results demonstrate that incorporating IFA makes Grove impressively outperform the state-of-the-art work across multiple graph-processing tasks, such as the well-known neighbor query and t-hop query.

Enforcing fine-grained access control is critical for secure key-value (KV) stores in cloud environments, yet classical attribute-based encryption incurs significant overhead. We present SACK, a shielded framework leveraging Intel SGX to enable efficient, dynamic attribute-based access control (ABAC) for KV stores in untrusted cloud environments, while ensuring confidentiality, integrity, and freshness. SACK decouples access control and data management by performing ABAC with hardware-assisted shielded execution and leveraging KV separation for secure, efficient, and crash-consistent KV storage. We implement SACK as a middleware system that can run atop general KV stores. Experiments show that SACK achieves high-performance KV operations and lightweight renewal of access rights.

JSON Schemas provide useful guardrails for developers of Web APIs to guarantee that the semi-structured JSON input provided by clients matches a predefined structure. This is important both to ensure the correctness of the data received as input and also to avoid potential security issues from processing input that is not correctly validated. However, this validation process can be time-consuming and adds overhead to every request. Different keywords in the JSON Schema specification have complex interactions that may increase validation time. Since popular APIs may process thousands of requests per second and schemas change infrequently,we observe that we can resolve some of the complexity ahead of time in order to achieve faster validation. Our JSON Schema validator, Blaze, compiles complex schemas to an efficient representation in seconds to minutes, adding minimal overhead at build time. Blaze incorporates several unique optimizations to reduce the validation time by an average of approximately 10× compared existing validators on a variety of datasets. In some cases, Blaze achieves a reduction in validation time of multiple orders of magnitude compared to the next fastest validator. We also demonstrate that several popular validators produce incorrect results in some cases, while Blaze maintains strict adherence to the JSON Schema specification.

JSON is a popular data format for storing semi-structured data. We investigate the computational problem of JSON validation, which is the task of checking whether a JSON document adheres to a given schema. While there are several existing tools that support JSON validation, they implement offline algorithms that require loading the entire document in memory and creating the full parse tree before performing validation. This offline approach is constrained by the available system memory and is inappropriate when the data is presented as a stream. We propose an approach for performing streaming JSON validation that relies on a new class of pushdown automata that can process JSON documents in an online fashion. Our experimental results show that our approach uses substantially less memory and is faster than state-of-the-art tools.

Modern data processing spans two worlds: flat relational tables, served by decades of database research producing highly optimized query engines, and nested semi-structured data such as JSON, for which expressive query languages exist but compilation and optimization techniques have been applied far less comprehensively. We ask whether a single query language can express both regimes naturally while compiling to efficient native code. We build on Rhyme, a declarative language whose object-notation syntax mirrors the structure of query results, and contribute on three fronts. We refine Rhyme's semantics for generator binding and missing values, allowing co-iteration, inner/outer joins, and nested-loop traversals to be expressed under different uses of generator symbols. We show that Rhyme's prior dependency-driven loop scheduler can generate incorrect code on hierarchical queries, and present a new scheduler based on finer-grained per-statement constraints that ensures correctness. We introduce a gradual type system and a C code generation backend that emits tag-less, statically typed code and specializes data loading and internal data structures for idiomatic SQL patterns. On TPC-H, JSONBench, and additional hierarchical queries, our system matches state-of-the-art compiled engines on SQL workloads and outperforms modern JSON-capable databases and DSLs on hierarchical queries.

The ubiquitous deployment of cameras has led to explosive growth of video data, creating an urgent need to explore valuable content. Single-level queries are insufficient to extract comprehensive information, raising the demand for multi-level queries (existence, dynamic, similarity) within a single unified system. However, limited by the high complexity and redundancy of video, existing systems usually support single-level queries, while Vision-Language Models that support multi-level queries incur prohibitive computational overhead, making them infeasible for large-scale video datasets. To address these issues, we propose Craw, a framework for efficient multi-level queries on large-scale video datasets. Specifically, Craw (1) designs the Video Semantic Unit to encapsulate video semantics, (2) develops a semantic-preserving video segmentation algorithm, and (3) constructs a hybrid index framework integrating an inverted index with a cluster index layer for efficient query execution. Experimental results show that Craw outperforms the state-of-the-art (SOTA) by reducing query latency up to two orders of magnitude, while effectively supporting multi-level queries.

Handling large-scale scientific data in high-performance computing (HPC) environments poses significant challenges, including excessive I/O, high storage costs, and slow query performance. Traditional approaches often require full data decompression and scans, making them impractical for real-time or interactive analysis. To address these limitations, we introduce Eureka, a unified data-index co-compression framework that enables fine-grained access and efficient range queries on compressed scientific datasets. Eureka integrates spatial domain decomposition with block-wise error-bounded lossy compression to support selective decompression. It constructs a hierarchical AVL-tree index during compression to capture block-level value ranges, enabling fast pruning during query execution. To reduce metadata overhead, the index itself is also compressed while ensuring recall-preserving results. Experiments on six diverse HPC simulation datasets show that Eureka achieves up to 25× data compression and over 300× index compression, surpassing state-of-the-art compressors such as SZ3 and ZFP in rate-distortion performance. Additionally, Eureka delivers over 30× speedup for low-selectivity range queries, making it a scalable and efficient solution for modern scientific data analysis.

This paper demonstrates that adopting out-of-place writes is essential for database systems to fully leverage SSD performance and extend SSD lifespan. We propose a set of out-of-place optimizations that collectively reduce write amplification across both the DBMS and SSD layers. We redesign the in-place, B-tree-based LeanStore to write out-of-place and support these optimizations, and evaluate it on diverse OLTP benchmarks, dataset sizes, and SSDs. The final design improves throughput by 1.65–2.24× and reduces flash writes per operation by 6.2–9.8× on YCSB-A. On TPC-C with 15,000 warehouses, throughput improves by 2.45× while flash writes decrease by 7.2×. Finally, we show that the architecture can seamlessly support novel SSD interfaces such as ZNS and FDP.

Remote cache-stores have seen a dramatic rise in importance in recent years, fueled by a surge in data-driven applications. Most prior database research has focused on various aspects of traditional key-value stores with string values and a simple get/set based remote interface. However, modern cache-stores such as Redis offer a significantly richer interface that has witnessed unprecedented popularity and broad adoption across the developer community. The interface and use cases for such cache-stores in both end-user applications and large-scale services translate to new requirements on storage, scale, complex data type support, and durability. Garnet is a new cache-store that adopts the Redis wire protocol for compatibility, but rethinks from a database perspective how such a modern cache-store system should be designed from the ground up to meet these requirements. Research insights across the storage, network, and cluster stack allow Garnet to support the large Redis interface as a drop-in replacement, yet achieve stronger database features -- thread- and node-scalability, durability, transactions -- and better end-to-end performance (up to 100x higher throughput and 4x lower latency at high percentiles). These results translate to lower end-to-end costs for real-word applications and services.

On heterogeneous memory (CXL-HM) where fast memory (i.e., CPU-attached DRAM) and slow memory (e.g., remote NUMA memory, RDMA-connected memory, Persistent Memory (PM)) coexist, optimizing the placement of tree-structure indexes (e.g., B+ tree) is crucial to achieving high performance while enjoying memory expansion. Nowadays, CXL-based heterogeneous memory (CXL-HM) is emerging due to its high efficiency and memory semantics. Prior tree-structure index placement schemes for HM cannot effectively boost performance on CXL-HM, as they fail to adapt to the changes in hardware characteristics and semantics. Additionally, existing CXL-HM page-level data placement schemes are not efficient for tree-structure indexes due to the granularity mismatch between the tree nodes and the page. In this paper, we argue for a CXL native, tree-structure aware data placement scheme to optimize tree-structure indexes on CXL-HM. Our key insight is that the placement of tree-structure indexes on CXL-HM should match the tree's inherent characteristics with CXL-HM features. We present CXL-HM, a tree-structure aware, node-grained data placement scheme for tree-structure indexes on CXL-HM. With SIDLE, developers can easily adapt existing tree-structure indexes to CXL-HM. We have integrated the B+ tree and radix tree with SIDLE to demonstrate its effectiveness. Evaluations show that SIDLE improves throughput by up to 71% and reduces P99 latency by up to 81% compared with state-of-the-art data placement schemes (e.g., MEMTIS) and HM-optimized tree-structure indexes (e.g., PACTree) in YCSB and real-world workloads.

Achieving scalable performance in modern in-memory indexes is primarily limited by synchronization. Traditional synchronization approaches apply a single "one-size-fits-all" strategy, ignoring the diverse characteristics of different index operations. For instance, pessimistic lock coupling forces high atomic overhead on all tree traversals, even simple lookup operations. Meanwhile, optimistic queue-based locking, while efficient for lookups, suffers from performance collapse due to shared data movement during high-contention updates. This paper introduces OPAL, a hybrid operation-aware lock design for modern in-memory indexes. OPAL dynamically selects among three locking mechanisms within a single lock instance based on operation type: (i) optimistic version-based locking for read-only lookups; (ii) lightweight function-pointer-based batching for updates that eliminates shared data movement; and (iii) traditional MCS-based locking for structural modification operations (SMOs), such as node splits and merges, that naturally distributes contention across multiple index nodes. We evaluate OPAL on widely-used index structures: a B+ Tree and an Adaptive Radix Tree (ART). Compared to state-of-the-art optimistic locking, OPAL improves throughput by up to 2.43x and reduces latency by 80%.

Accelerating SQL query execution with GPUs is a central focus in database research. While prior systems have achieved notable speedups by offloading relational operators, the acceleration of the wide range of scalar functions that are supported by analytical engines remains unaddressed. Our analysis reveals that many scalar functions incur substantial computational overhead and often constitute the primary bottleneck in analytical queries on CPUs. This observation motivates a systematic exploration of the opportunities and challenges in accelerating scalar functions on GPUs. Unlike relational operators, which are few in number and standardized, production databases support hundreds of scalar functions. The absence of a standardized specification, combined with this diversity, renders manual GPU porting infeasible. To address this, we present an LLVM-MLIR-based compiler toolchain that automatically translates the CPU-based implementations of scalar functions from production databases into efficient GPU kernels while preserving their original semantics. Our approach lifts scalar functions to a high-level intermediate representation, applies resource-optimizing transformations, and generates GPU assembly code, supporting all relevant data types, parameters, and database context variables. As existing benchmarks do not sufficiently stress test scalar functions in analytical queries, we introduce a variant of TPC-H that utilizes scalar functions while preserving the original query intent. Integrating our GPU kernels into a state-of-the-art GPU database system, we demonstrate substantial performance gains over a leading CPU database that uses slightly more expensive hardware: 7.6× on enhanced TPC-H and 6.4× on production queries, further widening the gap between GPU and CPU databases. The generated kernels deliver performance comparable to hand-optimized GPU implementations, establishing our approach as a scalable and practical solution for accelerating scalar functions on GPUs.

Cache eviction algorithms play a critical role in the performance of modern data systems, yet their scalability is often limited by the high computational overhead associated with object promotions. Lazy Promotion techniques have emerged as relaxations of traditional Least-Recently-Used (LRU) methods, designed to alleviate lock contention and increase throughput. This work uses production traces from real-world systems to benchmark five Lazy Promotion strategies: Probabilistic-LRU, Batch-LRU, Delay-LRU, FIFO-reinsertion, and Random-LRU. We evaluate these techniques across miss ratio, scalability, promotion count, and a novel metric called promotion efficiency, which measures the number of hits per promotion. Our results reveal that Delay-LRU and FIFO-reinsertion significantly improve promotion efficiency, whereas Batch-LRU and Probabilistic-LRU struggle to reduce promotions without significantly increasing miss ratio. We further explore the impact of lazy promotion in advanced algorithms such as ARC and 2Q and make a similar observation. Moreover, we uncover substantial optimization potential, showing that most cache promotions are unnecessary when equipped with oracle knowledge. To further reduce promotions in LRU, we propose two novel enhancements—Delayed FIFO-reinsertion (D-FR) and Age-Guided Eviction (AGE)—that reduce promotions by 20—60% while achieving a similar or lower miss ratio.

Sorting is a core operator in large-scale data systems. As data increasingly exceeds main memory, external merge sort is essential, yet many implementations over-allocate memory and over-parallelize, decreasing efficiency. We present CrocSort, a byte-balanced parallel external merge sort with configurable memory and per-phase thread settings. Using analysis and experiments, we derive practical resource-configuration rules for selecting these settings from input size, memory budget, and thread cap. To balance parallel merge under skew, CrocSort reuses run sparse indexes for range partitioning to create a virtual total order over records. CrocSort also uses offset-value codes and related optimizations to reduce comparison work and, for prefix-redundant workloads, intermediate I/O volume. Across TPC-H and synthetic workloads on modern NVMe systems, CrocSort completes sorting at memory budgets where production systems abort, and the planner reduces unnecessary resource allocation compared to the greedy maximal approach across both tight- and ample-memory regimes.

CSV remains one of the most widely used formats for exchanging tabular data, making efficient CSV processing an important problem. Yet most CSV parsers are sequential, failing to exploit the parallelism of modern hardware. While parallel CSV parsing approaches have been proposed in the literature, none of these seem to be used in practice. Conversely, a simple idea for synchronization-free speculative parsing that is used for parallel parsing, e.g., in DuckDB, has never been described in the literature, nor has it been exploited efficiently. In this paper, we close this gap. We contribute a) a description of how real-world CSV files can be parsed in parallel on commodity multicore CPUs, b) a new programming model for general-purpose CSV parsers that unifies parallel parsing and parallel data processing into one pass over the data, and c) a new vectorization strategy with efficient index and zero-copy record construction to accelerate parsing. Our evaluation shows that csveee, our parser, outperforms widely-used CSV parsers in single- and multi-threaded performance, and scales near-linearly to achieve throughput of up to 180 GB/s – 22x faster than DuckDB – all while remaining practical for integration into real-world data processing systems.

Hash tables sit on the critical path of many systems, yet modern designs still force a trade-off between fast operations and high memory overhead. We revisit this trade-off and present Tiny Pointer Hash Tables (TPHT), a family of practical hash tables that make two ideas from theory work at system scale: compressing pointers down to a byte, and encoding keys compactly so less metadata is needed. We engineer these into two complementary designs. Chained-TPHT targets maximal space savings, and is to our knowledge the first simple and practical succinct hash table, achieving a footprint smaller than the raw key-value payload size with constant-time operations. Flattened-TPHT targets latency, keeping the common case within a single cache miss while retaining strong space efficiency. Both variants support dynamic resizing without global pauses and integrate cleanly with 64-bit keys and values. Across YCSB and microbenchmarks, TPHT advances the latencyspace Pareto frontier: Chained-TPHT reaches 105.4% space efficiency, and Flattened-TPHT achieves 83.4% space efficiency with up to 89.3% higher throughput than strong baselines. Together, these results show that techniques primarily known in theory can be turned into systems-ready hash tables that meaningfully reduce memory use while delivering state-of-the-art performance.

A \emph{tensor-relational} computation is a relational computation where individual tuples carry vectors, matrices, or higher-dimensional arrays. An advantage of tensor-relational computation is that the overall computation can be executed on top of a relational system, inheriting the system's ability to automatically handle very large inputs with high levels of sparsity while high-performance kernels (such as optimized matrix-matrix multiplication codes) can be used to perform most of the underlying mathematical operations. In this paper, we introduce upper-case-lower-case \texttt{EinSum}, which is a tensor-relational version of the classical Einstein Summation Notation. We study automatically re-writing a computation in Einstein Notation into upper-case-lower-case \texttt{EinSum} so that computationally intensive components are executed using efficient numerical kernels, while sparsity is managed relationally.

Efficiently computing group aggregations (i.e., GROUP BY) on modern architectures is critical for analytic database systems. Today, hash-based methods predominantly use a partitioned approach, in which incoming data is partitioned by key so that every row for a particular key is sent to the same partition. In this paper, we revisit a simpler strategy: a fully concurrent aggregation technique using a shared hash table. While approaches using general-purpose concurrent hash tables have generally been found to perform worse than partitioning-based approaches, we argue that the key ingredient is customizing the concurrent hash table for the specific task of group aggregation. Through experiments on synthetic workloads (varying key cardinality, skew, and thread count), we demonstrate that in morsel-driven systems, a purpose-built concurrent hash table can match or surpass partitioning-based techniques. We also analyze the operational characteristics of both techniques, including resizing costs and memory pressure. In the process, we derive practical guidelines for database implementers. Overall, our analysis indicates that fully concurrent group aggregation is a viable alternative to partitioning.

We present CAPS, a novel system for cost-aware pipeline selection in automated machine learning (AutoML). CAPS' approach is orthogonal to the search strategies used by existing AutoML frameworks, enabling seamless integration with them. This integration benefits AutoML systems by reducing computational waste---time spent evaluating inefficient pipelines or exceeding time or memory constraints---through lightweight performance and cost estimation. To incorporate cost-awareness into AutoML, \sys represents a set of pipelines as a directed hypergraph, estimates execution times for each function, and formulates the optimal subset selection as a constrained prize-collecting optimization problem. CAPS employs a simple yet effective greedy algorithm to approximate this optimal subset. Our evaluation shows that when CAPS prioritizes cost, it reduces waste up to 4x---saving up to 23 hours in 50 hours of pipeline evaluation. When CAPS balances the trade-off between performance and cost, it consistently achieves performance improvements of 5% to 15% over the state of the art within the same time budget across datasets. It also demonstrates that CAPS is compatible with complementary efficiency techniques such as early stopping and warm-starting, achieving speedups of up to 4.7x.

Structured data-quality issues—such as missing values correlated with demographics, culturally biased labels, or systemic selection biases—routinely degrade the reliability of machine-learning pipelines. Regulators now increasingly demand evidence that high-stakes systems can withstand these realistic, interdependent errors, yet current robustness evaluations typically use random or overly simplistic corruptions, leaving worst-case scenarios unexplored. We introduce Savage, a causally inspired framework that (i) formally models realistic data-quality issues through dependency graphs and flexible corruption templates, and (ii) systematically discovers corruption patterns that maximally degrade a target performance metric. Savage employs a bi-level optimization approach to efficiently identify vulnerable data subpopulations and fine-tune corruption severity, treating the full ML pipeline, including preprocessing and potentially non-differentiable models, as a black box. Extensive experiments across multiple datasets and ML tasks (data cleaning, fairness-aware learning, uncertainty quantification) demonstrate that even a small fraction (around 5%) of structured corruptions identified by Savage severely impacts model performance, far exceeding random or manually crafted errors, and invalidating core assumptions of existing techniques. Thus, Savage provides a practical tool for rigorous pipeline stress-testing, a benchmark for evaluating robustness methods, and actionable guidance for designing more resilient data workflows.

Data is a critical component of modern decision-making systems; system malfunctions (e.g., performance degradation and module failure) can often be traced back to a mismatch between the properties of the data and the assumptions of the system modules that process the data. For example, with the increasing use of open-source libraries to develop data science pipelines, common causes of system malfunctions include inappropriately configured data processing libraries for data cleaning tasks such as entity resolution or missing value imputation. Our objective is to resolve malfunctioning pipelines and improve their utility; we introduce PipeLens, a framework that leverages successful and unsuccessful runs of past pipelines for fixing pipeline malfunctions. PipeLens uses an acyclic graph representation of the pipeline and performs causal reasoning through interventions: when a system malfunctions with a given dataset, PipeLens modifies the pipeline (by changing its structure or the parameters of its modules) and observes the impact of this intervention on system behavior. To focus on useful interventions, we learn a proxy function that approximates the pipeline’s utility over a dataset and guides the search for the best intervention. Unlike traditional observational analysis that reports correlations between system parameters and their behavior, we provide causally verified root causes and suggest pipeline modifications that rectify malfunctions. Empirical evaluation on four data science tasks over four real-world datasets demonstrates that PipeLens consistently outperforms baselines in terms of interventions performed to repair malfunctions while maintaining practical running times.

The Shapley value provides a principled foundation for data valuation, but exact computation is #P-hard due to the exponential coalition space. Existing accelerations remain global and ignore a structural property of modern predictors: for a given test instance, only a small subset of training points influences the prediction. We formalize this model-induced locality through support sets defined by the model’s computational pathway (e.g., neighbors in KNN, leaves in trees, receptive fields in GNNs), showing that Shapley computation can be projected onto these supports without loss when locality is exact. This reframes Shapley evaluation as a structured data processing problem over overlapping support-induced subset families rather than exhaustive coalition enumeration. We prove that the intrinsic complexity of Local Shapley is governed by the number of distinct influential subsets, establishing an information-theoretic lower bound on retraining operations. Guided by this result, we propose LSMR (Local Shapley via Model Reuse), an optimal subset-centric algorithm that trains each influential subset exactly once via support mapping and pivot scheduling. For larger supports, we develop LSMR-A, a reuse-aware Monte Carlo estimator that remains unbiased with exponential concentration, with runtime determined by the number of distinct sampled subsets rather than total draws. Experiments across multiple model families demonstrate substantial retraining reductions and speedups while preserving high valuation fidelity.

Data-centric ML pipelines extend traditional machine learning (ML) pipelines---of feature transformations and ML model training---by outer loops for data cleaning, augmentation, and feature engineering to create high-quality input data. Existing lossless matrix compression applies lightweight compression schemes to numeric matrices and performs linear algebra operations such as matrix-vector multiplications directly on the compressed representation but struggles to efficiently rediscover structural data redundancy. Compressed operations are effective at fitting data in available memory, reducing I/O across the storage-memory-cache hierarchy, and improving instruction parallelism. The applied data cleaning, augmentation, and feature transformations provide a rich source of information about data characteristics such as distinct items, column sparsity, and column correlations. In this paper, we introduce BWARE---an extension of AWARE for workload-aware lossless matrix compression---that pushes compression through feature transformations and engineering to leverage information about structural transformations. Besides compressed feature transformations, we introduce a novel technique for lightweight morphing of a compressed representation into workload-optimized compressed representations without decompression. BWARE shows substantial end-to-end runtime improvements, reducing the execution time for training data-centric ML pipelines from days to hours.

Artificial intelligence systems depend critically on high-quality data, yet real-world datasets are often imperfect. Label noise, such as incorrect or biased labels, can lead to suboptimal model decisions. While label noise has garnered increasing attention, existing research primarily examines random noise, employs simpler models, or relies on limited evaluation criteria. To address this, we introduce Fault Lines, a comprehensive, model-agnostic benchmark comprising 15 datasets systematically corrupted with diverse types of label noise, paired with an evaluation framework. This resource supports the evaluation of data cleaning pipelines and guides the design of models that are robust, in both performance and fairness, to label noise. We benchmark the robustness to label noise of 22 state-of-the-art classification models, including gradient boosting, transformers, and fairness-oriented models. Our findings show that many models maintain strong performance under high random noise (e.g., up to 40% noise leads to only a modest reduction in Robust GBDT performance). However, these models are significantly less robust to even small amounts of biased noise (<10%), which can cause substantial performance drops (e.g., 7% noise reduces ResNet’s AUC by 4.4% on average) or maintain apparent stability at the expense of severe fairness degradation (e.g., MLP’s Predictive Parity difference increases by ~700% under 30% biased noise in the ACS Unemployment dataset). We investigate how different model architectures handle the impact of biased noise. Notably, transformer-based models appear more robust than boosting models when handling biased noise, though this advantage depends on tuning and comes with higher variance. Finally, we identify key factors for ML practitioners to mitigate the effects of label noise, including model selection, dataset analysis, and preprocessing.

Efficient influence estimation and seed selection are crucial to social network advertising and are widely studied in data management. We focus on adaptive minimum cost seed selection (AMCSS), which selects seed nodes adaptively over multiple rounds, to reach a target number $\eta$ of influenced users while minimizing total seed cost. Prior work, notably ASTI with multi-root reverse reachable sets (mRR-sets), remains computationally expensive on large graphs, often taking hours to days even with CPU parallelism. We present GAAS, a GPU-accelerated method that integrates novel algorithmic and GPU-aware system designs to solve AMCSS in minutes. Processing mRR-sets involves irregular access patterns and variable-size samples, mismatching the GPU parallel architecture. Hence, we first develop a GPU-tailored mRR-set structure, GmRR, that assigns each thread block exclusive ownership of an equal-size segment with a circular layout, enabling efficient parallel mRR-set management while minimizing write contention. With GmRR, we design a GPU kernel ParallelGen to generate mRR-sets. Unlike prior work that regenerates mRR-sets from scratch in each round, we propose to update and reuse those from previous round, improving efficiency while requiring GPU-aware designs and rigorous theoretical analysis. Specifically, we design a ParallelUpdate kernel with theoretically grounded update rules that uses circular segment updates on GmRR for efficient mRR-set updates, together with a load-balancing scheme. We further devise a Select kernel for parallel seed selection. Integrating these together, GAAS efficiently solves AMCSS on GPUs with guarantees. Extensive experiments on large real-world graphs under different diffusion models show that GAAS is over an order of magnitude faster (up to 68.9$\times$) than parallel CPU and GPU baselines, while the seed cost is among the lowest.

Local subgraph counting computes the exact number of occurrences of a query graph around every vertex in a data graph. By capturing local higher‑order structure, it supports extensive applications in network analysis and graph learning. The fastest existing method, SCOPE, accelerates counting through query graph decomposition, but it is designed for single‑threaded CPU execution. As a result, it struggles on large graphs and cannot take advantage of modern GPU hardware. A naïve GPU adaptation is also ineffective: as the number of parallel GPU threads grows, the memory footprint of their intermediate results quickly drains the device memory. We develop a high‑performance GPU solution for local subgraph counting that preserves SCOPE’s tree‑decomposition framework while explicitly resolving the tension between massive GPU parallelism and limited device memory. Our approach compresses the intermediate join-and-aggregate results and proposes an insert‑failure restart mechanism that guarantees correctness under bounded memory. We further design a key‑mapping strategy that enables lock‑free hash tables for higher throughput, eventually integrating these components into a complete GPU execution framework capable of handling arbitrarily complex queries. Experiments show that our GPU‑accelerated method achieves up to a \revise{35$\times$ speedup over a multi-threaded SCOPE implementation}, reducing the processing time for a million‑scale graph from days to about 20 minutes and making local subgraph counting practical at large scale.

The emergence of link recommendation systems has triggered a line of research on strategic link insertion to enhance information diffusion in social networks. Existing literature assumes a seed set where all seed users are deterministically activated at the start of the campaign. However, uncertain seeding is being increasingly prevalent and can be used to model more general scenarios like users' defaulting behavior or discount-based marketing. To investigate how to augment the influence of uncertain seeds by link recommendation, we formulate a problem named \textit{influence maximization with augmentation for uncertain seeds} (IMAUS), which aims to insert $k$ edges incident to the uncertain seeds so as to maximize the influence of the given seeds. Due to the NP-hardness of the problem and the non-submodularity of the objective function, solving IMAUS is technically challenging. To address this, we resort to the sandwich strategy and propose two submodular bounding functions for the optimization objective. To overcome the \#P-hardness of the bounding functions computation, we provide two unbiased estimators for the bounding functions via non-trivial usage of reverse influence sampling and devise greedy algorithms equipped with several principled accelerating techniques to return $(1-1/\mathsf{e}-\varepsilon)$-approximations for maximizing the bounding functions. With the above design, we instantiate the sandwich framework in a joint baking manner to reduce repeated sampling. Extensive experiments on $6$ real-world datasets are conducted to validate the effectiveness and efficiency of the proposed methods. Specifically, our algorithm consistently produces a higher influence increment than the baselines and is able to return a size-$100$ edge set for a billion-size graph within $10$ minutes.

We study the problem of counting $k$-\emph{hyper}graphlets, an interesting but surprisingly ignored primitive, with the aim of understanding if efficient algorithms exist. To this end we consider \emph{color coding}, a well-known technique for approximately counting $k$-graphlets in graphs. Our first result is that, on hypergraphs, color coding encounters a \emph{quadratic barrier}: under the Orthogonal Vector Conjecture, no implementation of it can run in time sub-quadratic in the size of the input. We then introduce a simple property, $(\alpha,\beta)$-niceness, that hypergraphs from real-world datasets appear to satisfy for small values of $\alpha$ and $\beta$. Intuitively, an $(\alpha,\beta)$-nice hypergraph can be split into two sub-hypergraphs having respectively rank at most $\alpha$ and degree at most $\beta$. By applying different techniques to each sub-hypergraph and carefully combining the outputs, we show how to run color coding in time $2^{O(k)} \cdot \big(2^\beta |V| + \alpha^k |E| + \alpha^2 \beta \size{H}\big)$, where $H=(V,E)$ is the input hypergraph. Afterwards, we can sample colorful $k$-hypergraphlets uniformly in expected $k^{O(k)} \cdot (\beta^2+\ln |V|)$ time per sample. Experiments on real-world hypergraphs show that our algorithm neatly outperforms the naive quadratic algorithm, sometimes by more than an order of magnitude.

The maximum weight perfect matching (MWPM) problem in bipartite graphs has extensive applications in database, machine learning, financial markets, and other data-intensive domains, and serves as a general formulation of weighted matching problems. The Hungarian algorithm is widely adopted for solving bipartite MWPM, and substantial research efforts have focused on improving its sequential time complexity. As data volumes grow and real-time processing demands escalate, parallel solutions become increasingly essential. However, efficient parallelization remains highly nontrivial due to the algorithm's intricate execution patterns, inherently sequential data dependencies, frequent phase switching, and the single-path-per-iteration search constraint. These critical issues motivate us to develop X-Wim, a massively parallel framework. It is built on a new phase-decoupled approach that breaks the strong interleaving between algorithmic phases, eliminates frequent global updates, enables concurrent search for multiple disjoint paths, and incorporates an adaptive search strategy. These algorithmic design efforts lead to substantial performance gains, even in the single-threaded setting. Extensive experiments on real-world datasets indicate that X-Wim surpasses state-of-the-art baselines, achieving up to a 9.93x speedup with 1 core and up to a 56.3x speedup with 8 cores. It also exhibits strong scalability. In tests up to 96 cores, it achieves an average 1.70x speedup each time the number of threads doubles. To the best of our knowledge, X-Wim is the fastest solution for this class of graph algorithms.

SQL is declarative in nature and rich in its features. Writing semantically correct SQL queries and finding logical bugs in SQL are not easy, even for experienced programmers, who are often used to the mindset of working with general-purpose programming languages (GPLs). While there are many GPL debuggers, SQL debugging has received much less attention. In this paper, we present I-Rex, a SQL debugger that enables users to inspect the logical execution of SQL queries visually and interactively to identify and potentially fix logical bugs in the queries. I-Rex draws analogies to the debugging paradigm of GPLs (e.g., stepping, watchpoints, etc.), making it easier for programmers to adopt. However, unlike debugging GPLs, which involves executing the underlying program in full to the point of interest, I-Rex allows users to jump to arbitrary points of interest by leveraging the power of the database systems, through selective materialization and query rewrites. To simplify deployment, I-Rex acts as a lightweight middleware on top of the database system; it imposes no overhead to prepare a database for debugging and maintains no state in the database systems during debugging sessions. We demonstrate the effectiveness of I-Rex through performance experiments as well as a user study in an educational setting.

In many real-world scenarios, query results must satisfy domain-specific constraints, e.g., a minimum percentage of interview candidates selected based on their qualifications should be female. These requirements can be expressed as constraints over an arithmetic combination of aggregates evaluated on the result of the query. In this work, we study how to repair a query to fulfill such constraints by modifying its filter predicates. We introduce a novel query repair technique that leverages bounds on sets of candidate solutions and interval arithmetic to efficiently prune the search space. We demonstrate experimentally, that our technique significantly outperforms baselines that consider a single candidate at a time.

The ability of Graph Database Management Systems (GDBMSs) to efficiently store and query graph data has led to their widespread success. Unlike relational databases, GDBMSs model data as graphs and support expressive queries through graph traversal. Among the core functionalities, fixed-length and variable-length queries are particularly critical, as they underscore fundamental differences from traditional relational query execution. However, the correctness of such queries is notoriously difficult to ensure due to the intricate query semantics and the complexity of underlying optimizations like worst-case optimal joins. This paper presents a novel metamorphic testing approach named PATHTest that exploits result-equivalent transformations between fixed-length and variable-length queries. Specifically, PATHTest incorporates an iterative query generator that supports the generation of diverse and non-empty variable-length queries. During the mutation process, three transformation rules embedded within PATHTest help capture result-equivalent patterns between fixed- and variable-length queries, enhancing its capability to uncover both logical bugs and unexpected errors. Extensive evaluation on PATHTest across seven real-world, widely-used GDBMSs demonstrates the superiority of PATHTest, with 41 previously unknown bugs revealed, among which 24 are logic bugs, and 17 correspond to unexpected errors. To note, all 41 bugs are beyond the reach of the seven existing state-of-the-art testing approaches. By now, 29 of the 41 bugs have been confirmed, with 11 already fixed. Such evaluation results demonstrate the effectiveness and uniqueness of PATHTest in detecting bugs missed by existing testing approaches, contributing to the reliability of modern GDBMSs.

We need to rethink how users understand and develop queries. The growing diversity of users, the increasing complexity of query languages and data architectures - now aided by tools like LLMs - are challenging the traditional view of a highly-trained user writing queries in a controlled environment. Query formulation has become a more exploratory endeavor that needs to be researched and supported: an iterative cycle of designing, debugging, and maintaining queries. To ground this vision, we present an empirical analysis of query logs from the Wikidata Query Service, revealing common patterns of iterative query modification. Based on these findings, we propose a concrete research program with hypotheses, user studies, and research questions for query languages, engines, and interfaces. Our contributions include a curated query session dataset, a classification of exploratory-query patterns, and a roadmap for building system-level support for exploratory querying.

Data platforms have evolved by making data-intensive workloads native: SQL and query optimizers eliminated bespoke data-retrieval programs; Lakehouses added first-class support for ML training and serving over the same data. Prescriptive analytics (computing optimal actions subject to constraints over data) is equally data-intensive, yet remains outside the platform: every optimization problem requires a hand-built pipeline from data extraction to solver invocation, rebuilt from scratch whenever the data or the requirements change. We propose Decisionhouses, a new class of data infrastructure that makes prescriptive analytics native. A Decisionhouse provides (i) DeQL (Decision Query Language), a declarative SQL extension where users express decision problems over relational data; (ii) automatic formulation selection that exploits query and data semantics to pick the right problem class and solver—a choice that can change a query's complexity class from NP-hard to polynomial; and (iii) end-to-end integration of optimization into the data platform, from query parsing through solver execution. Decisionhouses can help address several challenges that have kept optimization outside data platforms, including pipeline brittleness, formulation expertise, structural blindness, and scalability cliffs, and make decision-making as accessible as querying data.

Modern data lakes have become essential for storing, managing, and analyzing massive amounts of heterogeneous data. As production data increasingly exhibits multimodal storage characteristics and multi-purpose access patterns, efficient management of such complexities becomes critical. However, current hybrid storage system-based data lakes face persistent challenges, including synchronization overhead, data correlation disruption, and escalating storage costs due to the involvement of multiple underlying storage systems. While columnar storage, central to data lakes, addresses hybrid-system inefficiencies, it struggles with the complexities of multimodal data storage and multi-purpose access. To tackle these challenges, we analyze access patterns across various scenarios and assess the issues in storing multimodal data. Based on these insights, we propose FlatStor, a FlatBuffers-based columnar Storage format with embedded indexing. It supports point access through indexing and handles multimodal data by vertically partitioning and treating each modality as a byte stream for storage. It also applies FSST compression, reducing storage overhead significantly. Benchmark evaluations reveal that FlatStor reduces the access latency by 99.6% and the storage overhead by 91.3% compared to Parquet in inference workloads. Furthermore, FlatStor outperforms LanceV2 with a 41.3% latency improvement, maintaining minimal additional overhead

Data lakes aim to avoid vendor lock-in and enable interoperability between different query engines on a single copy of data. While early data lakes were only collections of files in various formats, they have since evolved to incorporate some features traditionally associated with relational databases. Today, Apache Parquet is the de facto standard file format for relational data in data lakes. This standardization is fundamental to interoperability, but it comes at the cost of physical data independence because query engines integrate tightly with Parquet. As a result, adoption of novel approaches in the areas of file formats, access paths, and storage media has been limited. We propose the Active Data Lake architecture as a way to restore physical data independence and demonstrate its potential experimentally through three example optimizations.

Open Table Formats (OTFs) enable interoperability across systems by using object stores as a shared storage layer. They support OTF HTAP, in which complex queries execute concurrently with updates on the object store. However, existing OTFs provide transactional guarantees only for single-table transactions. Supporting transactions that access multiple tables typically requires external coordination services, which compromise interoperability and deployment independence. In this paper, we show that this trade-off is unnecessary. We present OTF-native mechanisms for multi-table atomicity, consistency, and isolation that rely solely on object-store primitives. We realize them in LakeVilla, a prototype that provides full ACID transactions while remaining compatible with existing OTF deployments. Our evaluation combines formal verification, extensive benchmarks, and an interoperability case study with Trino, showing that LakeVilla delivers strong transactional guarantees with low overhead, scalable concurrency, and compatibility with existing analytics engines.

Lakehouse systems unify the strengths of data lakes and data warehouses and are rapidly becoming a dominant architecture for analytic data management. The lakehouse architecture decouples system design into interoperable subsystems—execution engines(e.g., Spark, Trino, Presto) and table formats (e.g., Delta Lake, Iceberg, Hudi)—giving users flexibility to mix and match. However, jointly selecting and configuring these subsystems is hard: subsystem choices and configurations interact in complex ways, and online trial-and-error is costly (or infeasible when migration is required). Although there is extensive work on database tuning, most methods target a single subsystem and thus miss cross-dependencies; many also rely on iterative online tuning that is prohibitively expensive. In this work, we present LakeHelm, a zero-shot lakehouse advisor that jointly recommends an engine–format pair and its configuration without online feedback. LakeHelm uses a dual-gate Mixture-of-Experts model: separate gates specialize in engine and format choices, and experts learn configuration surrogates for each subsystem combination. To enhance generalization, we augment training data with generated SQL templates and synthesized workloads,layered atop collected runs that explore the configuration space. Evaluated across five standard benchmarks (TPC-DS, TPC-H, JOB, SSB, SSB-Flat), LakeHelm delivers competitive execution times—averaging 1.35× speedup over a fixed overall-best lakehouse configuration across a large number of workload variations. It achieves this via zero-shot inference on unseen workloads in seconds, without costly online experimentation.

Relational database systems often face a trade-off between supporting multi-table queries and frequent updates. Materialized join views can drastically speed up queries, but they slow down updates and may consume significant storage. Conversely, query-time joins over tables and their indexes optimizes update performance at the cost of query latency. Our recent study of two-table joins introduced “merged indexes” (a form of multi-table index) to break this trade-off, approaching the query performance of materialized views without sacrificing the update efficiency of traditional single-table indexes. This study generalizes this technique to “order-sharing pipelines”—multi-table joins and grouping operations on shared keys. By incorporating interesting orderings into the physical database design, merged indexes partially pre-compute these order-sharing pipelines, closely approaching the query performance of materialized views. Meanwhile, they match traditional indexes on update performance.

Differential Privacy (DP) is widely adopted in data management systems to enable data sharing with formal disclosure guarantees. A central systems challenge is understanding how DP noise translates into effective protection against inference attacks, since this directly determines achievable utility. Most existing analyses focus only on membership inference---capturing only a threat---or rely on reconstruction robustness (ReRo). However, under realistic assumptions, we show that ReRo can yield misleading risk estimates and violate claimed bounds, limiting their usefulness for principled DP calibration and auditing. This paper introduces reconstruction advantage, a unified risk metric that consistently captures risk across membership inference, attribute inference, and data reconstruction. We derive tight bounds that relate DP noise to adversarial advantage and characterize optimal adversarial strategies for arbitrary DP mechanisms and attacker knowledge. These results enable risk-driven noise calibration and provide a foundation for systematic DP auditing. We show that reconstruction advantage improves the accuracy and scope of DP auditing and enables more effective utility-privacy trade-offs in DP-enabled data management systems.

When creating public data products out of confidential datasets, inferential/posterior-based privacy definitions, such as Pufferfish, provide compelling privacy semantics when the data have correlations. However, such privacy definitions are rarely used in practice because they do not always compose. For example, it is possible to design algorithms for these privacy definitions that have no leakage when run once but reveal the entire dataset when run more than once. We prove necessary and sufficient conditions that must be added to ensure linear composition for Pufferfish mechanisms, hence avoiding such privacy collapse. These extra conditions turn out to be differential privacy-style inequalities, indicating that achieving both the interpretable semantics of Pufferfish for correlated data and composition benefits requires adapting differentially private mechanisms to Pufferfish. We show that such translation is possible through a concept called the $(a^\star(b), b)$-influence curve, and many existing differentially private algorithms can be translated with our framework into a composable Pufferfish algorithm. We illustrate the benefit of our new framework by designing composable Pufferfish algorithms for Markov chains that significantly outperform prior work.

Differential privacy (DP) has become the de facto standard for protecting sensitive data, providing strong guarantees that published statistics or models reveal limited information about any individual. However, privacy noise and restricted data access make it increasingly difficult to assess the fairness and reliability of private datasets. In this paper, we propose a formal framework for quantifying data unfairness under DP. We identify three core desiderata for unfairness measures based on previous work: positivity, monotonicity, and DP computability. We further instantiate them through three complementary measures: (1) a mutual information–based measure with a total variation distance proxy suitable for DP, (2) a data-repair–based measure approximated via a reduction to weighted MaxSAT, and (3) a top-$k$ tuple contribution measure that isolates the most influential records in fairness violations. We design privacy-preserving algorithms and analyze their sensitivity, accuracy, and efficiency. Extensive experiments on multiple real-world datasets demonstrate that our proposed measures faithfully approximate their non-private counterparts, effectively quantify bias under privacy constraints, and provide insights for data management.

Result diversification is crucial for generating informative, non-redundant data summaries and query outputs. Although its various formulations have been extensively studied across an array of data-driven disciplines, existing methods fail to address the privacy concerns that arise when the underlying data is sensitive. In this work, we initiate the study of result diversification under differential privacy, focusing on the max-sum diversification (MSD) problem, a widely adopted model with the objective of maximizing a linear combination of a submodular function, quantifying relevance, and the sum of pairwise distances between selected items, quantifying diversity. We propose differentially private algorithms for MSD under both cardinality and matroid constraints, achieving nearly optimal utility guarantees. At the same time, we design more efficient algorithms that maintain strong guarantees. Notably, the proposed algorithms are faster than existing non-private methods, making them appealing even in non-private settings. Experimental evaluations on real-world datasets demonstrate that the proposed approach achieves utility comparable to that of non-private baselines even under strong privacy guarantees, and significantly improves execution times for cardinality constraints.

Strong isolation guarantees, such as serializability and snapshot isolation, are essential for maintaining data consistency and integrity in modern databases. Verifying whether a database upholds its claimed guarantees is increasingly critical, as these guarantees form a contract between the vendor and its users. However, this task is challenging, particularly in black-box settings, where only observable system behavior is available and often involves uncertain dependencies between transactions. In this paper, we present VeriStrong, a fast verifier for strong database isolation. At its core is a novel formalism called hyper-polygraphs, which compactly captures both certain and uncertain transactional dependencies in database executions. Leveraging this formalism, we develop sound and complete encodings for verifying both serializability and snapshot isolation. To achieve high efficiency, VeriStrong tailors SMT solving to the characteristics of database workloads, in contrast to prior general-purpose approaches. Our extensive evaluation across diverse benchmarks shows that VeriStrong not only significantly outperforms state-of-the-art verifiers on the workloads they support, but also scales to large, general workloads beyond their reach, while maintaining high accuracy in detecting isolation anomalies.

Practical implementations of Isolation levels (ILs) might deviate from their theoretical definitions, resulting in isolation bugs. Triggering isolation bugs usually requires concurrent test cases, which causes high debugging complexity. These test cases typically contain numerous irrelevant operations, resulting in large and redundant raw cases that violate the three essential criteria for bug report submission, i.e., reproducibility, conciseness, and uniqueness. Achieving these criteria involves three key challenges: 1) deterministically reproduce bugs despite high concurrency; 2) efficiently reduce cases without losing bug-triggering operations; 3) accurately distinguish unique bugs from the bug reports having complex transaction behaviors. To address these challenges, we propose an isolation bug case reduction and deduplication framework Pisco. First, we propose to simulate the DBMS's internal state to infer the order of conflicting operations for deterministic bug reproduction. Second, we introduce a dependency-aware divide-and-conquer strategy for efficient case reduction. Finally, we design a domain knowledge-driven, multi-agent collaboration framework for accurate bug deduplication. Extensive experiments show that Pisco reduces the cases to their minimal forms in just 20.0%/33.3% of the time required by C-Reduce/DDMin and has a deduplication ratio of up to 91.6%.

There are two main approaches to scaling transactional database workloads: (1) a shared-nothing architecture with distributed transaction processing, or (2) an Aurora-style shared-storage architecture with separate compute and storage layers that scale independently. In option (2), the compute layer typically contains a single writer node and all other compute nodes are read-only. This may lead to scalability limits for write-intensive workloads, and introduces communication latency for write transactions that initiate far from the writer node. However, shared-nothing systems must pay the overhead of distributed coordination and commit protocols. In this paper, we discuss the design of a more scalable version of Aurora-style systems which supports multiple writer nodes managing geographically partitioned data. It yields many of the efficiency benefits of Aurora-style systems while removing the scalability bottleneck. Furthermore, geographic partitioning improves latency by over an order of magnitude for global applications in which clients from across the world can experience local write performance.

Large-scale data management systems rely on fault-tolerant protocols to ensure availability and consistency in the presence of node failures. However, standard protocols require majority quorums in every phase, making them impractical in environments with frequent failures, such as IoT networks. This paper presents Orca, a crash-fault-tolerant consensus protocol that integrates Raft-style log replication with Flexible Paxos quorum construction to maintain small replication quorums. Orca exploits the observation that node failures are often independent and temporally separated: by assuming that at most k nodes fail within a window too short for the system to detect the first failure, Orca fixes the replication quorum at k+1 nodes. As failures are detected, faulty nodes are temporarily excluded from the voting set and the election quorum is reduced accordingly, allowing the system to continue making progress as failures accumulate. Our evaluation across diverse workloads and fault scenarios demonstrates that Orca tolerates more failures than Raft and FlexiRaft while incurring negligible overhead.

Distributed NewSQL databases build SQL query engines on top of LSM-tree-based key-value stores to achieve fast and scalable online transaction processing. This requires efficient transaction support in the underlying storage engine, typically implemented using multi-version concurrency control (MVCC). However, existing in-memory MVCC schemes struggle with large write transactions due to high memory consumption and commit overhead, which can degrade insertion performance or even cause system crashes. Out-of-memory MVCC schemes alleviate these issues but suffer from expensive visibility checks under high concurrency, leading to performance degradation. In this paper, we propose a hybrid MVCC scheme that combines the fast visibility checks of in-memory MVCC with the low commit latency and memory usage of out-of-memory MVCC, enabling efficient transaction management. To integrate this design with LSM-tree-based key-value stores, we introduce several memory management techniques, including a transaction-aware data separation strategy, a stash region for uncommitted data, and a concurrent memtable flushing mechanism. We implement a prototype key-value store and extend YCSB to evaluate our design under various workloads. Experimental results demonstrate that our hybrid MVCC scheme combines the strengths of both approaches and delivers improved performance.

Location-tracking data from the Automatic Identification System, much of which is publicly available, plays a key role in a range of maritime safety and monitoring applications. However, the data suffers from missing values that hamper downstream applications. Imputing the missing values is challenging because the values of different heterogeneous attributes are updated at diverse rates, resulting in the occurrence of multi-scale dependencies among attributes. Existing imputation methods that assume similar update rates across attributes are unable to capture and exploit such dependencies, limiting their imputation accuracy. We propose MH-GIN, a Multi-scale Heterogeneous Graph-based Imputation Network that aims improve imputation accuracy by capturing multi-scale dependencies. Specifically, MH-GIN first extracts multi-scale temporal features for each attribute while preserving their intrinsic heterogeneous characteristics. Then, it constructs a multi-scale heterogeneous graph to explicitly model dependencies between heterogeneous attributes to enable more accurate imputation of missing values through graph propagation. Experimental results on two real-world datasets find that MH-GIN is capable of an average 57% reduction in imputation errors compared to state-of-the-art methods, while maintaining computational efficiency.

Reinforcement learning (RL) has become a promising approach for the Traffic Signal Control (TSC) problem, enabling agents (intersections) to learn control policies with dynamic traffic environments. However, existing RL-based methods typically rely solely on current traffic states and expected reward estimates, without leveraging predicted future traffic conditions for more effective decision-making. Therefore, we propose FutureLight, the first RL TSC framework that leverages future traffic data. Specifically, we design a macroscopic, signal-aware, and lane-level simulation FutureLight-RouteSys that efficiently and accurately estimates future traffic conditions. Then, the predicted results are embedded with FutureLight-Encoder into FutureLight-DQN through state augmentation, reward shaping, and hybrid value estimation, which combines simulated near-future rewards with bootstrapped near-future returns. Finally, we propose several pruning techniques to avoid redundant calculations and further improve overall training efficiency. Experimental results demonstrate that our proposed framework consistently improves traffic signal control performance, and also improves training efficiency by thirty times.

Trajectory data analysis, e.g., trajectory summarization, imputation, prediction, and classification, has been fundamental to widely used applications. Even though several research efforts have been dedicated to develop numerous algorithms for trajectory analysis, there is an apparent lack of full-fledged systems that support a myriad of trajectory analysis tasks. The main reason is that each introduced algorithm employs new methods and data structures that are tailored to one specific trajectory analysis task. This paper presents KAFY; a full-fledged system that supports a myriad of trajectory data analysis tasks. KAFY leverages the recent advances in Natural Language Processing (NLP) where the transformer architecture is introduced as a system infrastructure to build large language models that can be fine tuned to support various NLP tasks. The main idea of KAFY is that instead of training a transformer architecture with a (spoken) language to produce (language) models, it trains it with the (unspoken) trajectory language to produce (trajectory) models. KAFY is an extensible system where its users can extend it with more transformers and/or trajectory operations. The first release of KAFY employs three transformers and supports five trajectory operations. Experimental results from a real deployment of KAFY show that it either outperforms or gives similar performance to existing baselines in all its supported trajectory operations.

Modern applications frequently collect and analyze temporal data in the form of multivariate time series (MTS) – time series that contain multiple channels. A common task in this context is subsequence search, which involves identifying all MTS that contain subsequences highly similar to a query time series. In practical scenarios, not all channels of an MTS are relevant to every query. For instance, airplane sensors may gather data on a plethora of components and subsystems, but only a few of these are relevant to a specific query, such as identifying the cause of a malfunctioning landing gear, or a specific flight maneuver. Consequently, the relevant query channels are often specified at query time. In this work, we introduce the Multivariate Subsequence Index (MS-Index), a novel algorithm for nearest neighbor MTS subsequence search under Euclidean distance that supports ad-hoc selection of query channels. The algorithm is exact and demonstrates query performance that scales sublinearly to the number of query channels. We examine the properties of MS-Index with a thorough experimental evaluation over 34 datasets, and show that it outperforms the state-of-the-art one to two orders of magnitude for both raw and normalized subsequences.

With the rapid advancement of large-scale scientific simulations, the massive volume of point cloud data generated has increasingly become a critical bottleneck for modern storage systems. Existing point cloud compression techniques used in data storage systems are designed for sparse geometry and rely on quantization schemes whose optimality assumptions do not hold for dense data. When applied at the compression layer to point clouds, this representation mismatch leads to fundamentally sub-optimal rate-distortion trade-offs that cannot be addressed through parameter tuning or framework-level adaptations. This issue arises in scientific data management pipelines for applications such as molecular dynamics simulations, which generate massive particle datasets forming dense distributions. Consequently, state-of-the-art compression methods fail to fully exploit the redundancies inherent in such data. We address this limitation by developing a theory of point cloud compressibility for dense data, characterizing fundamental rate-distortion behavior at the representation layer. Guided by this analysis, we introduce XnYZip, an error-bounded lossy compressor based on provably optimal Truncated Octahedron quantization, combined with a locality-aware encoding pipeline using space-filling curves and run-length encoding. Experiments on large-scale scientific datasets demonstrate consistent storage and performance improvements, achieving up to 3x higher compression ratios, 2.2x faster compression, and 1.2x faster decompression compared to state-of-the-art point cloud compressors.

The rise of cryptocurrencies like Bitcoin and Ethereum has driven interest in blockchain database technology, with smart contracts enabling the growth of decentralized finance (DeFi). However, research has shown that adversaries exploit transaction ordering to extract profits through attacks like front-running, sandwich attacks, and liquidation manipulation. This issue affects blockchains where block proposers have full control over transaction ordering. To address this, a more fair transaction ordering mechanism is essential. Existing fairness protocols, such as Pompe and Themis, operate on leader-based consensus protocols, which not only suffer from low throughput caused by single-leader bottleneck, but also give adversarial block proposers to manipulate transaction ordering. To address these limitations, we propose a new framework FairDAG that runs fairness protocols on top of DAG-based consensus protocols, which improves protocol performance in both throughput and fairness quality, leveraging the multi-proposer design and validity property of DAG-based consensus protocols. We conducted a comprehensive analytical and experimental evaluation of two FairDAG variants—FairDAG-AB and FairDAG-RL. Our results demonstrate that FairDAG outperforms prior fairness protocols in both throughput and fairness quality.

DAG-based BFT consensus has attracted growing interest in distributed data management systems for consistent replication in untrusted settings due to its high throughput and resilience to asynchrony. However, existing protocols still suffer from high communication overhead and long commit latency. In parallel, introducing minimal hardware trust has proven effective in reducing the complexity of BFT consensus. Inspired by these works, we present Fides, an asynchronous DAG-based BFT consensus protocol that, to our knowledge, is among the first to leverage TEEs to enhance both scalability and efficiency. Fides tolerates a minority of Byzantine replicas and achieves $O(\kappa n^2 + n^3)$ metadata communication complexity through a customized TEE-assisted Reliable Broadcast (T-RBC) primitive with linear communication complexity in one-step broadcast.Building on T-RBC, Fides redefines the DAG construction rules by reducing the reference requirement from $2f+1$ to $f+1$ between consecutive vertices. This new structure weakens DAG connectivity and invalidates traditional commit rules, so we formally abstract the problem and derive new theoretical bounds of liveness. We further propose a four-round commit rule that achieves the theoretically minimal commit latency. Besides, we design two additional primitives, T-RoundCert and T-Coin, to efficiently certify DAG references and replace the costly cryptographic common coin used in prior protocols.Comprehensive evaluations on geo-distributed and local testbeds show that Fides substantially outperforms state-of-the-art protocols, including Tusk, Bullshark, Mysticeti, Shoal++, RCC, Damysus, Achilles and HybridSet, achieving lower latency and higher throughput while preserving strong safety and liveness guarantees.

Trusted Execution Environments (TEEs) provide strong confidentiality and integrity guarantees to distributed data processing. Developers are increasingly using clusters of TEE-enabled workers for these applications. However, TEEs do not protect persistent state: a rollback attack may replace the current persistent state with a stale version. Conventional rollback detection systems interfere with the application’s steady-state performance either by adding high coordination overhead or log amplification. Our key insight is "Rollback attacks violate causality". Rollback attacks can be efficiently detected by causal logging, avoiding the coordination and log amplification overheads of prior solutions. We build HarborMaster, a high-performance rollback detection system for the TEE-based distributed computing clusters. HarborMaster offloads the job of rollback detection to a specialized auditing service that efficiently checks for rollback attacks using violations of causality in the TEE-based distributed computing workers. Running in AMD SEV-SNP Confidential VMs, HarborMaster only imposes 8–35% logging overhead and preserves the linear scaling properties of an unprotected distributed application.

Stateful stream processing engines are critical for real-time analytics but lack efficient mechanisms for runtime elasticity. The dominant "stop-the-world" model, used by systems like Apache Flink, requires halting applications globally for a long time, while recent on-the-fly protocols introduce severe trade-offs: proactive approaches impose a continuous resource tax by constantly replicating state, and existing reactive solutions suffer from architectural complexity and external dependencies. This paper introduces Fugue, a novel, self-contained reactive protocol that provides seamless and resource-efficient elasticity. The core of Fugue is a two-phase design that combines a pre-emptive background state transfer with an atomic, lightweight barrier-based cutover. By moving the bulk of an operator's state off the critical path and unifying the final ownership transfer with the system's native exactly-once synchronization mechanism, Fugue guarantees correctness with minimal disruption and steady-state overhead. We implemented Fugue in Apache Flink and our evaluation on realistic benchmarks shows it reconfigures a running query up to 40x faster than native Flink while maintaining over 95% of peak throughput. Compared to state-of-the-art baselines, Fugue reduces end-to-end migration latency by up to 14x, demonstrating a superior balance of robustness, performance, and operational simplicity.

An Authenticated Data Structure (ADS) enables a cloud service to generate a verification object (VO), allowing users to verify the correctness of query results. This is particularly valuable for data owners who wish to offload query processing to the cloud while remaining concerned about the trustworthiness of the results. In this paper, we address the problem of constructing ADS for a category of queries known as analytic queries, which operate over linear functions. Existing approaches require the data owner to build the ADS; however, the computational resources needed for this construction are often beyond the capabilities of many data owners–particularly those who are resource-constrained and thus choose outsourcing in the first place. Motivated by this challenge, we propose the concept of a Verifiable ADS (V-ADS), which delegates most of the ADS construction to the cloud while enabling the data owner to verify and sign the results with minimal effort. We present two techniques–baseline and advanced V-ADS–and demonstrate through theoretical analysis and experimental evaluation that these approaches substantially reduce the resource demands on the data owner.

The execution of streaming analytics workflows across large-scale IoT infrastructures poses unique challenges. Central data collection depletes the available bandwidth and leaves IoT device resources unutilized. Therefore, workflow execution should be performed in-network, assigning workflow operator execution on devices across the cloud-to-edge continuum. However, the vast scale of devices results in an exponential number of possible combinations of workflow operator assignments. On top of that, workflows are executed on dynamic environments where volatile data stream distributions and device churn may render a deployed plan inefficient and, therefore, rapid adaptation decisions are crucial. To address these challenges, we present APEROL, the first suite of parallel optimization algorithms for timely and efficient workflow execution in IoT environments. APEROL introduces a novel conceptualization of the optimization search space, coupled with a signature-based execution plan enumeration scheme, that enable scalable, parallel plan exploration. The suite includes exhaustive, heuristic, greedy, and random sampling algorithms, which are complementary in algorithm speed vs. plan quality trade-offs under different setups. The current implementation examines up to 2M candidate plans per second on commodity hardware. Experiments with 5 challenging workflows from 2 streaming benchmarks, over real and simulated networks ranging from 10s to 1000s sites show APEROL's effectiveness and timeliness.

Distributed data stream processing engines (DSPEs) operating over the cloud-edge continuum must deploy data processing operators across a distributed infrastructure. However, the volatile nature of these infrastructure nodes—where devices frequently join, leave, or move—can invalidate existing query operator-to-topology node mappings, leading to interruptions in query execution and potential data loss. To ensure continuous processing while maintaining correctness, DPSEs must dynamically adapt these mappings and redeploy (part of) affected queries. In this paper, we introduce incremental stream query deployment (ISQD), a framework that efficiently redeploys queries affected by topology changes. ISQD employs a greedy strategy to identify and redeploy only affected operators. It uses ad-hoc queries to migrate operator state seamlessly, and leverages reconfiguration markers to synchronize the redeployment process. Our evaluation shows that \texttt{ISQD} achieves up to 7.5x lower deployment latency and up to 39x lower event time latency compared to state-of-the-art approaches, even under high-frequency topology changes.

The Internet of Things (IoT) demands real-time, low-latency processing of data generated by thousands of heterogeneous, resource-constrained devices. In such dynamic environments, ensuring fault tolerance becomes critical, especially for safety-sensitive applications like disaster management or patient monitoring. However, existing centralized fault tolerance solutions face serious scalability challenges across large, hierarchically connected IoT topologies. In this paper, we present Meerkat, a network-aware fault-tolerance protocol explicitly designed for IoT environments. Meerkat achieves zero-downtime recovery via redundant operator execution on disjoint paths and efficient duplicate detection. It also includes dynamic load balancing that adapts operator placement to device volatility, ensuring fair resource use. Compared to state-of-the-art techniques, Meerkat sustains up to 70x higher throughput with only 28% network overhead. These results highlight Meerkat’s ability to deliver efficient fault tolerance with minimal overhead at IoT scale.

The detection of sequential patterns in data is a basic functionality of modern data processing systems for complex event processing (CEP), OLAP, and retrieval-augmented generation (RAG). In practice, the respective engines typically evaluate multiple shared patterns simultaneously, in order to improve the result quality for downstream applications. The evaluation of a large number of patterns under tight latency bounds is challenging, though, since matching needs to maintain state, i.e., intermediate results, that grow exponentially in the input size. Hence, systems turn to best-effort processing, striving for maximal recall under a latency bound. Existing techniques, however, consider patterns in isolation, neglecting the optimization potential induced by state sharing and corresponding interactions and interference across shared patterns. We describe Sharp, a state management library that employs state reduction for efficient best-effort pattern matching in shared patterns. To this end, Sharp incorporates state sharing between patterns through a new abstraction, coined pattern-sharing degree (PSD). At runtime, PSD facilitates the categorization and indexing of partial pattern matches. Once a latency bound is exceeded, Sharp realizes best-effort processing by using a cost model to select a subset of partial matches for further processing in constant time. In experiments with real-world data, Sharp achieves a recall of 95%, 93% and 72% for pattern matching in CEP, OLAP, and RAG applications, under a bound of 50% of the average processing latency.

Memory overload is a common form of resource exhaustion in cloud data warehouses. When database queries fail due to memory overload, it not only wastes critical resources such as CPU time but also disrupts the execution of core business processes, as memory-overloading (MO) queries are typically part of complex workflows. If such queries are identified in advance and scheduled to memory-rich serverless clusters, it can prevent resource wastage and query execution failure. Therefore, cloud data warehouses desire an admission control framework with high prediction precision, interpretability, efficiency, and adaptability to effectively identify memory-overloading queries. However, existing admission control frameworks primarily focus on scenarios like SLA satisfaction and resource isolation, with limited precision in identifying MO queries. Moreover, there is a lack of publicly available MO-labeled datasets with workloads for training and benchmarking. To tackle these challenges, we propose SafeLoad, the first query admission control framework specifically designed to identify MO queries. Alongside, we release SafeBench, an open-source, industrial-scale benchmark for this task, which includes 150 million real queries. SafeLoad first filters out memory-safe queries using the interpretable discriminative rule. It then applies a hybrid architecture that integrates both a global model and cluster-level models, supplemented by a misprediction correction module to identify MO queries. Additionally, a self-tuning quota management mechanism dynamically adjusts prediction quotas per cluster to improve precision. Experimental results show that SafeLoad achieves state-of-the-art prediction performance with low online and offline time overhead. Specifically, SafeLoad improves precision by up to 66% over the best baseline and reduces wasted CPU time by up to 8.09x compared to scenarios without SafeLoad.

The increasing number of large knowledge graphs (KGs) now available online requires methods for their efficient exploration. Most of these KGs offer online SPARQL endpoints for querying and exploring their data. In a typical scenario, the users issue coarse, exploratory queries at the beginning, refining them further in the sequel in order to find the answer to the question in mind. However, those coarse exploratory queries are costly to evaluate as they usually involve many results and take too much time to be answered, or even worse, they time out, limiting the exploration potential of the data they expose. In this paper, we present the LFS (Love-at-First-Sight) system, offering a unique solution to the aforementioned problem, enabling users to efficiently get the first answers to their queries. More specifically, we are the first to define the problem of constructing first-sight summaries (FSS), i.e., summaries able to provide rapidly, first answers to user queries, relying on existing query logs. We provide effective algorithms for constructing both exact and approximate FSS under budget constraints with theoretical guarantees. We analytically and experimentally demonstrate latency reductions of up to two orders of magnitude over SPARQL endpoints and one order of magnitude over relevant baselines.

Interactive graph search (IGS) has emerged as a powerful information retrieval paradigm for various applications. Given a hierarchy and an oracle that typically relies on human intelligence such as crowdsourcing, IGS aims to identify the most precise concept for an unknown object while minimizing interaction costs with the oracle. Most existing algorithms simplify the problem by assuming a perfect oracle that always provides correct answers. Others adopt an idealized noisy oracle that models noises as explicit error rates specified in advance and locate the target with Bayesian inference guided by a node-wise querying strategy. However, in real-world scenarios, the oracle inevitably makes mistakes and prior knowledge of the oracle is often limited. Moreover, the node-wise querying strategy that lacks holistic awareness of the search state and ignores the global hierarchical structure usually yields suboptimal queries. As a result, existing solutions suffer from significant accuracy degradation and prohibitive interaction costs. To address these challenges, we introduce IGS-RTA. We first formulate the problem based on search uncertainty, explicitly accounting for the randomness of the search state and hierarchical relations. We then propose a querying strategy that maximizes the expected uncertainty decrement. Our rigorous theoretical analysis establishes a logarithmic upper bound on the query complexity. In addition, to adapt to noisy settings with limited prior knowledge, we analyze oracle expertise and task difficulties, which characterize two groups of meta-factors that influence real query answering. We model their relationships using a probabilistic graphical model and design techniques to estimate these latent factors online. We evaluate IGS-RTA on two real-world datasets against six baselines. Results show that IGS-RTA improves search accuracy by up to 52% while reducing monetary costs by up to 8x.

Shortest path queries are a fundamental operation on graphs with numerous applications. Efficiently executing shortest path searches in RDBMS is challenging, as graphs can not only be static relations but might also occur as ad-hoc intermediate results of complex analytical queries. Especially single-pair shortest path queries are difficult to accelerate, because they require minimizing the search space and intermediate results cannot be shared e.g. for multiple destinations. To address these challenges, we present Nav-Index, an adaptive index for relational DBMS that accelerates large-scale shortest path queries with seamless integration into SQL and relational algebra. Nav-Index switches adaptively between three modes: an ad-hoc generic mode using Dijkstra's algorithm, an ad-hoc optimized mode for sparse graphs leveraging contraction hierarchies (CH), and a table index mode for static graphs also leveraging CHs. Graph DBMS typically provide specific implementations for such queries and are valuable for many workloads. In practice, however, existing systems show limited throughput for large-scale graphs such as road networks and offer limited optimization for analytical relational processing. Embedding Nav-Index into an RDBMS allows for a seamless composition with other relational operators, query decorrelation, cost-based optimization, morsel-driven parallelism, and pipelining. In the case of sparse graphs, Nav-Index's CH mode transforms the graph into a contraction hierarchy, allowing algorithmic speedups by orders of magnitude. We implemented Nav-Index into the compiling database system Umbra and evaluate Nav-Index extensively on road networks ranging from small cities to the whole planet and social graphs. In our experiments, Nav-Index outperforms all other database systems that we have tested by orders of magnitude due to algorithmic advantages and an efficient implementation. It can index the road network of Europe in under 12 minutes and Earth in less than 68 minutes, allowing planet-scale shortest path queries in milliseconds in a general-purpose RDBMS.

A fundamental challenge in data management is the efficient discovery of term relationships from massive, unstructured text corpora, a critical first step in knowledge graph construction. This discovery task, however, faces prohibitive computational barriers: the quadratic $O(N^2)$ complexity of an all-pairs analysis and the intractability of processing the full term-document matrix. While dimensionality reduction via embeddings offers a partial solution, the resulting vector proximity often captures broad thematic similarity, failing to isolate the precise co-occurrence signals required for high-quality relation extraction. This paper introduces CRAFT, a system that overcomes these limitations by re-casting term relatedness discovery as a scalable signal processing problem. CRAFT's methodology decouples the discovery process from both the term-document matrix and quadratic-time comparisons. First, it employs a randomized Fourier transform to sketch term occurrence signals directly into a low dimensional complex space, a process that provably preserves the inner products essential for correlation analysis without materializing the underlying matrix. Second, to break the quadratic barrier, CRAFT leverages the inherent sparsity of term relationships by formulating discovery as a compressed sensing task. This enables the recovery of significant correlations for any given term directly from its compressed sketch via an efficient Orthogonal Matching Pursuit algorithm, obviating the need for an all-pairs comparison. Our end-to-end implementation and comprehensive experimental evaluation show that CRAFT significantly outperforms modern baselines in both efficiency and precision, enabling high-quality relation discovery at a previously infeasible scale.

Given a metric space graph $G(V,E)$ in which only a subset of edge distances is known, we study a query-based model for answering lower bound distance queries on unknown edges, without access to any black-box distance oracle. For a queried pair of objects $(u,v)$ with unknown distance, the lower bound corresponds to the minimum feasible value of $d(u,v)$ that satisfies all known distances and the triangle inequality constraints. We develop algorithmic techniques that operate directly on the partially observed graph to answer such queries efficiently. Our framework carefully balances preprocessing overhead, query processing time, and tightness of the produced bounds, while providing provable guarantees under metric assumptions. The proposed methods significantly improve both theoretical understanding and practical performance for lower bound inference, as validated through extensive experiments on multiple large-scale real-world datasets.

Fairness has emerged as a formidable challenge in data-driven decisions. Many of the data problems, such as creating compact data summaries for approximate query processing, can be effectively tackled using concepts from computational geometry, such as $\varepsilon$-nets. However, these powerful tools have yet to be examined from the perspective of fairness. To fill this research gap, we add fairness to classical geometric approximation problems of $\varepsilon$-net, $\varepsilon$-sample, and geometric hitting set. We introduce and address two notions of group fairness: demographic parity, which requires preserving group proportions from the input distribution, and custom-ratios fairness, which demands satisfying arbitrary target ratios. We develop two algorithms to enforce fairness—one based on sampling and another on discrepancy theory. The sampling-based algorithm is faster and computes a fair $\varepsilon$-net of size which is only larger by a $\log(k)$ factor compared to the standard (unfair) $\varepsilon$-net, where $k$ is the number of demographic groups. The discrepancy-based algorithm is slightly slower (for bounded VC dimension), but it computes a smaller fair $\varepsilon$-net. Notably, we reduce the fair geometric hitting set problem to finding fair $\varepsilon$-nets. This results in a $O(\log \mathsf{OPT} \times \log k)$ approximation of a fair geometric hitting set. Additionally, we show that under certain input distributions, constructing fair $\varepsilon$-samples can be infeasible, highlighting limitations in fair sampling. Beyond the theoretical guarantees, our experimental results validate the practical effectiveness of the proposed algorithms. In particular, we achieve zero unfairness with only a modest increase in output size compared to the unfair setting.

Discretizing raw features into bucketized attributes is a common step before sharing a dataset. However, this process can inadvertently introduce bias and amplify unfairness in downstream tasks. In this paper, we address this issue by formulating the unbiased binning problem, which seeks bucketized attributes that satisfy group parity. We develop an efficient dynamic programming algorithm to solve this problem for equal-size binning. In practice, however, an unbiased binning may incur a high price of fairness or may not exist at all, particularly when group distributions differ substantially. To accommodate settings in which small deviations from perfect parity are acceptable, we introduce the epsilon-biased binning problem, which restricts group disparities across buckets to at most epsilon. We first present a dynamic programming algorithm, DP, that computes the optimal solution in quadratic time. While polynomial, DP does not scale to large datasets. To address this, we propose a practically scalable algorithm based on local search (LS) for epsilon-biased binning. A central component of LS is a divide-and-conquer algorithm (D&C) that quickly finds a solution in near-linear time. We prove that D&C always returns a valid solution whenever one exists. The LS algorithm then initiates a local search, using the D&C solution as the upper bound, to find the optimal solution. Our LS and D&C algorithms are general, and not limited to equal-size binning. To complement our theoretical analysis, we conduct extensive experiments on real-world and synthetic datasets. Besides confirming the efficiency of the algorithms, our experiments verify that while fairness-unaware binning can generate biased attribute representations, this bias can be significantly reduced at a negligible price of fairness.

Auditing algorithmic fairness is a critical challenge in high-stakes domains like hiring and credit scoring, especially given the intrinsic opacity of algorithmic decision-making systems. In this paper, we tackle the following problem: given a ranking of individuals, how can we assess whether the order is driven by protected attributes (e.g., gender or race) rather than task-relevant features, under a strict black-box assumption where the ranking mechanism cannot be queried? Building on kernel conditional independence and partial distance correlation, we introduce Condor, a model-agnostic audit framework. Condor first residualizes the ranking and protected attributes with respect to observables in a reproducing kernel Hilbert space. It then quantifies the remaining association via distance correlation on the residualized embeddings, returning a normalized effect-size score. This procedure captures general nonlinear dependencies without assuming access to latent scores, requires no hyperparameter fine-tuning, and naturally accommodates mixed continuous and categorical data. From Condor's effect-size score, we derive a hypothesis test for conditional independence. By combining this test with an unconditional independence test, auditors can achieve a comprehensive causal understanding of the protected attributes' influence. We validate our proposal on real and semi-synthetic datasets with controlled influence of the protected attributes on the ranking: our method reliably detects the influence of protected attributes, outperforming established statistical auditing baselines.

Estimating the number of distinct values in an attribute or a set of attributes is one of the classical and open problems of cost-based query optimizers (CBOs). Such estimations can be very difficult to make in the presence of query selection predicates without examining the complete dataset. It becomes even harder for a multi-dataset (i.e., join) query with selection predicates. Recent advances in CBOs have introduced sample-based approaches, which maintain stored samples on the underlying datasets to improve the accuracy of cardinality and selectivity estimation during query compilation. Leveraging these stored samples, this paper addresses the important yet challenging problem of estimating the number of distinct values in an attribute or a set of attributes in a multi-dataset query. We refer to our proposed sample-based approach as the MAMD (Multi-Attribute, Multi-Dataset) approach. The MAMD approach works for join queries with or without selection predicates and is also effective for estimating the number of distinct values in single-dataset queries. We present an experimental evaluation of the proposed MAMD approach with synthetic and real-world datasets, namely the TPC-H and the IMDB benchmark datasets. We demonstrate how it can estimate the number of distinct values with moderately low relative errors and with low storage overhead and execution time. We also investigate how the MAMD approach performs when we scale up the size of the database.

Machine learning can analyze vast amounts of data generated by IoT devices to identify patterns, make predictions, and enable real-time decision-making. This raises significant privacy concerns, necessitating the application of data minimization - a foundational principle in emerging data regulations, which mandates that service providers only collect data that is directly relevant and necessary for a specified purpose. Despite its importance, data minimization lacks a precise technical definition in the context of sensor data, where collections of weak signals make it challenging to apply a binary "relevant and necessary" rule. This paper provides a technical interpretation of data minimization in the context of sensor streams, explores practical methods for implementation, and addresses the challenges involved. Through our approach, we demonstrate that our framework can reduce user identifiability by up to 16.7% while maintaining accuracy loss below 1%, offering a viable path toward privacy-preserving IoT data processing.

Maximal clique enumeration is a fundamental graph mining task, but its utility is often limited by computational intractability and highly redundant output. To address these challenges, we introduce \emph{$\rho$-dense aggregators}, a novel approach that succinctly captures maximal clique structure. Instead of listing all cliques, we identify a small collection of clusters with edge density at least $\rho$ that collectively contain every maximal clique. In contrast to maximal clique enumeration, we prove that for all $\rho < 1$, every graph admits a $\rho$-dense aggregator of \emph{sub-exponential} size, $n^{O(\log_{1/\rho}n)}$, and provide an algorithm achieving this bound. For graphs with bounded degeneracy, a typical characteristic of real-world networks, our algorithm runs in near-linear time and produces near-linear size aggregators. We also establish a matching lower bound on aggregator size, proving our results are essentially tight. In an empirical evaluation on real-world networks, we demonstrate significant practical benefits for the use of aggregators: our algorithm is consistently faster than the state-of-the-art clique enumeration algorithm, with median speedups over $2.5\times$ for $\rho=0.1$ (and over $350\times$ in an extreme case), while delivering a much more concise structural summary.

The $k$-defective clique model relaxes the strict completeness constraint of the traditional clique by allowing up to $k$ missing edges, providing a robust formulation for detecting cohesive structures in noisy graphs. Consequently, the maximum $k$-defective clique problem has attracted significant attention. State-of-the-art exact algorithms predominantly adopt the branch-and-bound framework, which recursively partitions the current problem instance (or branch) into two sub-problems via a branching procedure, until each sub-problem becomes trivially solvable. However, this strategy often leads to excessive branching by overlooking intermediate sub-problems that are non-trivial yet efficiently solvable. While recent studies have attempted to refine branching procedures, they fail to address this structural redundancy. To address this, we propose BBRes, a framework that incorporates a novel early termination strategy into the recursive branching process. By employing a specialized polynomial-time solver to identify and resolve tractable sub-instances, BBRes effectively avoids redundant branching steps. Additionally, we design a tailored branching strategy that synergizes with this termination mechanism. As a result, BBRes achieves an improved theoretical worst-case time complexity. Furthermore, to enhance practical performance, we propose a tighter upper bound based on a novel double graph coloring method integrated with max-flow techniques, which is orthogonal to the branching framework. Extensive experiments demonstrate that BBRes achieves at least 2X speedup over state-of-the-art methods on a substantial fraction of the datasets.

A k-clique, defined as the set of k pairwise adjacent vertices, plays a fundamental role in the analysis of real-world networks. Many downstream tasks require computing the number of k-cliques, yet listing or exact counting is often computationally prohibitive on massive networks, making approximate counting the only scalable option. Existing algorithms for approximate k-clique counting primarily use the Monte Carlo method. These algorithms construct a sample space, which is a collection of k-vertex sets including all k-cliques. They then perform sample trials, where each trial consists of selecting a k-vertex set uniformly at random from the sample space and checking whether it forms a k-clique. However, existing algorithms suffer from huge sample spaces and expensive sample trials. In this paper, we present CREST, an efficient Monte Carlo algorithm for approximate k-clique counting. We introduce a suite of novel techniques to address the two main objectives: (1) obtaining a small sample space, and (2) reducing the cost of sample trials. We propose a novel sample space refinement strategy to obtain a smaller sample space, and a star-based sampling approach that addresses both of the main objectives. We also develop a combinatorial method to obtain exact clique counts for certain subgraphs, effectively reducing their sample spaces to the extreme. Moreover, we present a new stopping criterion that satisfies the target accuracy requirement with fewer samples. Extensive experiments on real-world networks demonstrate that CREST outperforms the state-of-the-art algorithm by up to two orders of magnitude in running time, while maintaining the specified accuracy requirement.

Counting \((p,q)\)-bicliques in bipartite graphs is crucial for a variety of applications, from recommendation systems to cohesive subgraph analysis. Yet, it remains computationally challenging due to the combinatorial explosion to exactly count the \((p,q)\)-bicliques. In many scenarios, e.g., graph kernel methods, however, exact counts are not strictly required. To design a scalable and high-quality approximate solution, we novelly resort to \emph{\((p,q)\)-broom}, a special spanning tree of the $(p,q)$-biclique, which can be counted via graph coloring and efficient dynamic programming. Based on the intermediate results of the dynamic programming, we propose an efficient sampling algorithm to derive the approximate $(p,q)$-biclique count from the \((p,q)\)-broom counts. Theoretically, our method offers unbiased estimates with provable error guarantees. Empirically, our solution outperforms existing approximation techniques in both accuracy (up to 8$\times$ error reduction) and runtime (up to 50$\times$ speedup) on nine real-world bipartite networks, providing a scalable solution for large-scale \((p,q)\)-biclique counting.