bluuebunny/crossref_metadata_2025 huggingface dataset:
Analysis of Low-Frequency Bandgap Characteristics of Novel Epoxy-Based Metamaterial Plate Structure
Authors: Wang Qian , Miao Linchang , Zheng Haizhong , Zhang Benben , Lei Kaiyun
Published: May 2024

An epoxy-based metamaterial plate structure with local resonance is designed in this paper. The bandgap of the bending wave ranges from 36.46[Formula: see text]Hz to 110.55[Formula: see text]Hz. Through the optimization design of the oscillators in the plate structure, the starting bandgap moves to 19.79[Formula: see text]Hz, and the band gap width is 72[Formula: see text]Hz. The dispersion curve and frequency response function were calculated by finite element method (FEM). On this basis, the plane wave expansion method formula of the structural model was derived, and the equivalent model of spring-mass model was established. The results show that the calculation results of the three methods of the epoxide metamaterial plate structure were basically consistent, and the correctness of these methods was verified mutually. The methods derived in this paper bring great convenience and diversity to the application of plate structure. The article proposes a low-frequency wide bandgap thick plate structure model.
Cofiniteness of generalized local cohomology modules
Authors: Shen Jingwen , Yang Xiaoyan
Published: May 2024

Let [Formula: see text] be an ideal of a commutative noetherian ring [Formula: see text] and [Formula: see text] two [Formula: see text]-modules with [Formula: see text] finitely generated. It is shown that if either [Formula: see text] is an [Formula: see text]-cofinite module of dimension [Formula: see text] for all [Formula: see text], or [Formula: see text] is a principal ideal and [Formula: see text] is finitely generated for all [Formula: see text], or [Formula: see text] is finitely generated and [Formula: see text] for all [Formula: see text], then the [Formula: see text]-module [Formula: see text] is [Formula: see text]-cofinite for all [Formula: see text].
On the conjecture of groups with the same number of centralizers
Authors: Ahmadkhah N. , Zarrin M.
Published: May 2024

For any group [Formula: see text], let [Formula: see text] denote the set of all centralizers of [Formula: see text]. K. Khoramshahi and M. Zarrin [Groups with the same number of centralizers, J. Algebra Appl. 20 (2021) 2150012], posed the following conjecture: Let [Formula: see text] and [Formula: see text] be finite groups. Is it true that if [Formula: see text] and [Formula: see text], then [Formula: see text] is isoclonic to [Formula: see text]? In this paper, among other things, we give a negative answer to this conjecture.
PACMMOD Volume 2 Issue 3: Editorial
Authors: Agrawal Divyakant , Meliou Alexandra , Sudarshan S.
Published: May 2024

Welcome to Issue 3 of Volume 2 of the Proceedings of the ACM on Management of Data. This issue has papers submitted to the SIGMOD research track of PACMMOD, whose submission deadline was October 15, 2023. Out of 287 submissions in this round, a total of 70 articles were accepted and are presented in this issue. We provide statistics of paper submissions and acceptance, by primary subject area, across all submissions to the SIGMOD research track of PACMMOD in 2023. Accepted papers from this pool have been invited for presentation at the ACM SIGMOD 2024 conference to be held from 9th to 14th June 2024, in Santiago, Chile.
Missing Data Imputation with Uncertainty-Driven Network
Authors: Wang Jianwei , Zhang Ying , Wang Kai , Lin Xuemin , Zhang Wenjie
Published: May 2024

We study the problem of missing data imputation, which is a fundamental task in the area of data quality that aims to impute the missing data to achieve the completeness of datasets. Though the recent distribution-modeling-based techniques (e.g., distribution generation and distribution matching) can achieve state-of-the-art performance in terms of imputation accuracy, we notice that (1) they deploy a sophisticated deep learning model that tends to be overfitting for missing data imputation; (2) they directly rely on a global data distribution while overlooking the local information.

Driven by the inherent variability in both missing data and missing mechanisms, in this paper, we explore the uncertain nature of this task and aim to address the limitations of existing works by proposing an uNcertainty-driven netwOrk for Missing data Imputation, termed NOMI. NOMI has three key components, i.e., the retrieval module, the neural network gaussian process imputator (NNGPI) and the uncertainty-based calibration module. NOMI~ runs these components sequentially and in an iterative manner to achieve a better imputation performance. Specifically, in the retrieval module, NOMI~ retrieves local neighbors of the incomplete data samples based on the pre-defined similarity metric. Subsequently, we design NNGPI~ that merges the advantages of both the Gaussian Process and the universal approximation capacity of neural networks. NNGPI~ models the uncertainty by learning the posterior distribution over the data to impute missing values while alleviating the overfitting issue. Moreover, we further propose an uncertainty-based calibration module that utilizes the uncertainty of the imputator on its prediction to help the retrieval module obtain more reliable local information, thereby further enhancing the imputation performance. We also demonstrate that our NOMI~ can be reformulated as an instance of the well-known Expectation Maximization (EM) algorithm, highlighting the strong theoretical foundation of our proposed methods. Extensive experiments are conducted over 12 real-world datasets. The results demonstrate the excellent performance of NOMI in terms of both accuracy and efficiency.
ACORN: Performant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data
Authors: Patel Liana , Kraft Peter , Guestrin Carlos , Zaharia Matei
Published: May 2024

Applications increasingly leverage mixed-modality data, and must jointly search over vector data, such as embedded images, text and video, as well as structured data, such as attributes and keywords. Proposed methods for this hybrid search setting either suffer from poor performance or support a severely restricted set of search predicates (e.g., only small sets of equality predicates), making them impractical for many applications. To address this, we present ACORN, an approach for performant and predicate-agnostic hybrid search. ACORN builds on Hierarchical Navigable Small Worlds (HNSW), a state-of-the-art graph-based approximate nearest neighbor index, and can be implemented efficiently by extending existing HNSW libraries. ACORN introduces the idea of predicate subgraph traversal to emulate a theoretically ideal, but impractical, hybrid search strategy. ACORN's predicate-agnostic construction algorithm is designed to enable this effective search strategy, while supporting a wide array of predicate sets and query semantics. We systematically evaluate ACORN on both prior benchmark datasets, with simple, low-cardinality predicate sets, and complex multi-modal datasets not supported by prior methods. We show that ACORN achieves state-of-the-art performance on all datasets, outperforming prior methods with 2--1,000× higher throughput at a fixed recall. Our code is available at: https://github.com/stanford-futuredata/ACORN.
Banzhaf Values for Facts in Query Answering
Authors: Abramovich Omer , Deutch Daniel , Frost Nave , Kara Ahmet , Olteanu Dan
Published: May 2024

Quantifying the contribution of database facts to query answers has been studied as means of explanation. The Banzhaf value, originally developed in Game Theory, is a natural measure of fact contribution, yet its efficient computation for select-project-join-union queries is challenging. In this paper, we introduce three algorithms to compute the Banzhaf value of database facts: an exact algorithm, an anytime deterministic approximation algorithm with relative error guarantees, and an algorithm for ranking and top-k. They have three key building blocks: compilation of query lineage into an equivalent function that allows efficient Banzhaf value computation; dynamic programming computation of the Banzhaf values of variables in a Boolean function using the Banzhaf values for constituent functions; and a mechanism to compute efficiently lower and upper bounds on Banzhaf values for any positive DNF function.

We complement the algorithms with a dichotomy for the Banzhaf-based ranking problem: given two facts, deciding whether the Banzhaf value of one is greater than of the other is tractable for hierarchical queries and intractable for non-hierarchical queries.

We show experimentally that our algorithms significantly outperform exact and approximate algorithms from prior work, most times up to two orders of magnitude. Our algorithms can also cover challenging problem instances that are beyond reach for prior work.
CodeS: Towards Building Open-source Language Models for Text-to-SQL
Authors: Li Haoyang , Zhang Jing , Liu Hanbing , Fan Ju , Zhang Xiaokang , Zhu Jun , Wei Renjie , Pan Hongyan , Li Cuiping , Chen Hong
Published: May 2024

Language models have shown promising performance on the task of translating natural language questions into SQL queries (Text-to-SQL). However, most of the state-of-the-art (SOTA) approaches rely on powerful yet closed-source large language models (LLMs), such as ChatGPT and GPT-4, which may have the limitations of unclear model architectures, data privacy risks, and expensive inference overheads. To address the limitations, we introduce CodeS, a series of pre-trained language models with parameters ranging from 1B to 15B, specifically designed for the text-to-SQL task. CodeS is a fully open-source language model, which achieves superior accuracy with much smaller parameter sizes. This paper studies the research challenges in building CodeS. To enhance the SQL generation abilities of CodeS, we adopt an incremental pre-training approach using a specifically curated SQL-centric corpus. Based on this, we address the challenges of schema linking and rapid domain adaptation through strategic prompt construction and a bi-directional data augmentation technique. We conduct comprehensive evaluations on multiple datasets, including the widely used Spider benchmark, the newly released BIRD benchmark, robustness-diagnostic benchmarks such as Spider-DK, Spider-Syn, Spider-Realistic, and Dr.Spider, as well as two real-world datasets created for financial and academic applications. The experimental results show that our CodeS achieves new SOTA accuracy and robustness on nearly all challenging text-to-SQL benchmarks.
Continual Observation of Joins under Differential Privacy
Authors: Dong Wei , Chen Zijun , Luo Qiyao , Shi Elaine , Yi Ke
Published: May 2024

The problem of continual observation under differential privacy has been studied extensively in the literature. However, all existing works, with the exception of [28,51], have only studied the simple counting query and its derivatives. Join queries, which are arguably the most important class of queries in relational databases, have only been considered in [28,51], but the solutions offered there have two limitations: First, they only support a few specific graph pattern queries, which are special cases of joins. Second, they require hard degree/frequency constraints on the graph/database instance, and the privatized query answers have errors proportional to these constraints.

In this paper, we propose a new differentially private mechanism for continual observation of joins that overcomes these two limitations. Our mechanism supports arbitrary joins and predicates, and do not require any constraints to be given in advance, even over an infinite stream. More importantly, it yields an error that is proportional to the actual maximum degree/frequencies in the graph/database instance at the current time of observation. Such an instance-specific utility guarantee is much preferred for the continual observation problem, where the database size and the query answer may change significantly over time.
Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries
Authors: Heddes Mike , Nunes Igor , Givargis Tony , Nicolau Alex
Published: May 2024

With the increasing rate of data generated by critical systems, estimating functions on streaming data has become essential. This demand has driven numerous advancements in algorithms designed to efficiently query and analyze one or more data streams while operating under memory constraints. The primary challenge arises from the rapid influx of new items, requiring algorithms that enable efficient incremental processing of streams in order to keep up. A prominent algorithm in this domain is the AMS sketch. Originally developed to estimate the second frequency moment of a data stream, it can also estimate the cardinality of the equi-join between two relations. Since then, two important advancements are the Count sketch, a method which significantly improves upon the sketch update time, and secondly, an extension of the AMS sketch to accommodate multi-join queries. However, combining the strengths of these methods to maintain sketches for multi-join queries while ensuring fast update times is a non-trivial task, and has remained an open problem for decades as highlighted in the existing literature. In this work, we successfully address this problem by introducing a novel sketching method which has fast updates, even for sketches capable of accurately estimating the cardinality of complex multi-join queries. We prove that our estimator is unbiased and has the same error guarantees as the AMS-based method. Our experimental results confirm the significant improvement in update time complexity, resulting in orders of magnitude faster estimates, with equal or better estimation accuracy.
Efficient Approximation of Kemeny's Constant for Large Graphs
Authors: Xia Haisong , Zhang Zhongzhi
Published: May 2024

For an undirected graph, its Kemeny's constant is defined as the mean hitting time of random walks from one vertex to another chosen randomly according to the stationary distribution. Kemeny's constant exhibits numerous explanations from different perspectives and has found various applications in the field of complex networks. Due to the requirement of computing the inverse of the normalized Laplacian matrix, it is infeasible to get the accurate Kemeny's constant of large networks with millions of vertices. Existing methods either consume excessive memory space that are impractical for large-scale networks, or involve redundant simulation, leaving room for further optimization. In this paper, we propose two scalable Monte Carlo algorithms RefinedMC and ForestMC to approximate Kemeny's constant. RefinedMC makes several refinements based on the simulation of truncated random walks, significantly reducing the amount of required random walks, while ForestMC utilizes the newly discovered paradigm connecting Kemeny's constant with the inverse of corresponding Laplacian submatrix, which is considerably accurate. Extensive numerical experiments on model and realistic networks demonstrate that our approximation algorithms evidently outperform the baseline methods in terms of efficiency and accuracy.
Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee
Authors: Dai Qiangqiang , Li Rong-Hua , Cui Donghang , Liao Meihao , Qiu Yu-Xuan , Wang Guoren
Published: May 2024

A k-biplex is an induced subgraph of a bipartite graph which requires every vertex on the one side disconnecting at most k vertices on the other side. Enumerating all maximal k-biplexes in a bipartite graph is a fundamental operator in bipartite graph analysis and finds applications in various domains, including community detection, online recommendation, and fraud detection in finance networks. The state-of-the-art solutions for maximal k-biplex enumeration suffer from efficiency issues as k increases (k ≥ 2), with the time complexity of O(m 2
n
), where n (m) denotes the number of vertices (edges) in the bipartite graph. To address this issue, we propose two theoretically and practically efficient enumeration algorithms based on novel branching techniques. Specifically, we first devise a new branching rule as a fundamental component. Building upon this, we then develop a novel branch-and-bound enumeration algorithm to efficiently enumerate maximal k-biplexes. We prove that our algorithm achieves a worst-case time complexity of O(mα
k
n
), where α
k
< 2, thus significantly improving the time complexity compared to previous algorithms. To enhance the performance, we further propose an improved enumeration algorithm based on a novel pivot-based branching rule. Theoretical analysis reveals that our improved algorithm has a time complexity of O(mβ
k
n
), where β
k
is strictly less than α
k
. In addition, we also present several non-trivial optimization techniques, including graph reduction, upper-bounds based pruning, and ordering-based optimization, to further improve the efficiency of our algorithms. Finally, we conduct extensive experiments on 6 large real-world bipartite graphs to evaluate the efficiency and scalability of the proposed solutions. The results demonstrate that our improved algorithm achieves up to 5 orders of magnitude faster than the state-of-the-art solutions.
FairHash: A Fair and Memory/Time-efficient Hashmap
Authors: Shahbazi Nima , Sintos Stavros , Asudeh Abolfazl
Published: May 2024

Hashmap is a fundamental data structure in computer science. There has been extensive research on constructing hashmaps that minimize the number of collisions leading to efficient lookup query time. Recently, the data-dependant approaches, construct hashmaps tailored for a target data distribution that guarantee to uniformly distribute data across different buckets and hence minimize the collisions. Still, to the best of our knowledge, none of the existing technique guarantees group fairness among different groups of items stored in the hashmap.

Therefore, in this paper, we introduce FairHash, a data-dependant hashmap that guarantees uniform distribution at the group-level across hash buckets, and hence, satisfies the statistical parity notion of group fairness. We formally define, three notions of fairness and, unlike existing work, FairHash satisfies all three of them simultaneously. We propose three families of algorithms to design fair hashmaps, suitable for different settings. Our ranking-based algorithms reduce the unfairness of data-dependant hashmaps without any memory-overhead. The cut-based algorithms guarantee zero-unfairness in all cases, irrespective of how the data is distributed, but those introduce an extra memory-overhead. Last but not least, the discrepancy-based algorithms enable trading off between various fairness notions. In addition to the theoretical analysis, we perform extensive experiments to evaluate the efficiency and efficacy of our algorithms on real datasets. Our results verify the superiority of FairHash compared to the other baselines on fairness at almost no performance cost.
GRF: A Global Range Filter for LSM-Trees with Shape Encoding
Authors: Wang Hengrui , Guo Te , Yang Junzhao , Zhang Huanchen
Published: May 2024

Log-structured merge-trees (LSM-trees) are widely used in key-value stores because of its excellent write performance. To reduce LSM-tree's read amplification due to overlapping sorted runs, each file (i.e., SSTable) in an LSM-tree is typically associated with a point or range filter to reduce unnecessary I/Os to the runs that do not contain the target key (range). However, as modern SSDs get faster, probing multiple in-memory filters per query often makes the system CPU bottlenecked, thus compromising the system's throughput. In this paper, we developed the Global Range Filter (GRF) for RocksDB that reduces the number of filter probes per query to one. We follow the pioneering Chucky's approach by storing the sorted run IDs within the filter. However, we identify two practical challenges in building a global range filter: correctness in multi-version concurrency control and efficiency in frequent updates. We solve both challenges by the novel Shape Encoding algorithm. With further optimizations, GRF achieves a dominating performance over the state-of-the-art filters under different workloads when integrated into RocksDB.
High Precision ≠ High Cost: Temporal Data Fusion for Multiple Low-Precision Sensors
Authors: Zhu Jingyu , Sun Yu , Song Shaoxu , Yuan Xiaojie
Published: May 2024

High-quality data are crucial for practical applications, but obtaining them through high-precision sensors comes at a high cost. To guarantee the trade-off between cost and precision, we may use multiple low-precision sensors to obtain the nearly accurate data fusion results at an affordable cost. The commonly used techniques, such as the Kalman filter and truth discovery methods, typically compute fusion values by combining all the observations according to predictions or sensor reliability. However, low-precision sensors can often cause outliers, and such methods combining all observations are susceptible to interference. To handle this problem, we select a single observation from multiple sensor readings as the fusion result for each timestamp. The selection strategy is guided by the maximum likelihood estimation, to determine the most probable changing trends of fusion results with adjacent timestamps. Our major contributions include (1) the problem formalization and NP-hardness analysis on finding the fusion result with the maximum likelihood w.r.t. local fusion models, (2) exact algorithms based on dynamic programming for tackling the problem, (3) efficient approximation methods with performance guarantees. Experiments on various real datasets and downstream applications demonstrate the superiority and practicality of our work in low-precision sensor data fusion.
Implementation Strategies for Views over Property Graphs
Authors: Han Soonbo , Ives Zachary G.
Published: May 2024

The need to query complex interactions and relationships has motivated interest in property graph database platforms. For some graph applications, graph views are required to abstract the data, e.g., to capture individual-level vs. organization-level relationships; or show single computational steps vs. composite workflows. Emerging efforts to standardize graph query languages have developed semantics and language constructs for graph views.

This paper considers the task of implementing such views using rewriting techniques --- both using existing property graph DBMSs and converting to relational RDBMSs. We consider both virtual and materialized views, ways of rewriting queries, and structures for indexing data. We also note a common use case of graph views, which involves preserving a graph except minor local transformations; we develop novel extensions and semantics for this. We evaluate and compare the performance of our techniques under a variety of workloads, and we compare existing graph and relational DBMS platforms.
Lorentz: Learned SKU Recommendation Using Profile Data
Authors: Glaze Nick , McNeely Tria , Zhu Yiwen , Gleeson Matthew , Serr Helen , Bhopi Rajeev , Krishnan Subru
Published: May 2024

In response to diverse demands, cloud operators have significantly expanded the array of service offerings, often referred to as Stock Keeping Units (SKUs) available for computing resource configurations. Such diversity has led to increased complexity for customers to choose the appropriate SKU. In the analyzed system, only 43% of the resource capacity was rightly chosen. Although various automated solutions have attempted to resolve this issue, they often rely on the availability of enriched data, such as workload traces, which are unavailable for newly established services. Since these services amass a substantial volume of telemetry from existing users, cloud operators can leverage this information to better understand customer needs and mitigate the risk of over- or under-provisioning. Furthermore, customer satisfaction feedback serves as a crucial resource for continuous learning and improving the recommendation mechanism. In this paper, we present Lorentz, an intelligent SKU recommender for provisioning new compute resources that circumvents the need for workload traces. Lorentz leverages customer profile data to forecast resource capacities for new users based on detailed profiling of existing users. Furthermore, using a continuous learned feedback loop, Lorentz tailors capacity recommendations according to customer performance vs. cost preferences captured through satisfaction signals. Validated using the production data from provisioned VMs supporting Database Platform X, we demonstrate that Lorentz outperforms user selections and existing defaults, reducing slack by >60% without increasing throttling. Evaluated using synthetic data, Lorentz's personalization stage iteratively learns the user preferences over time with high accuracy.
Making In-Memory Learned Indexes Efficient on Disk
Authors: Zhang Jiaoyi , Su Kai , Zhang Huanchen
Published: May 2024

Learned indexes have been demonstrated to outperform traditional ones in memory-resident scenarios. However, recent studies show that they fail to outperform B+tree when extended to disks directly. In this paper, we argue that it is feasible to create efficient disk-based learned indexes by applying a set of general transformations and optimizations to existing in-memory ones. Through theoretical analysis and controlled experiments, we propose six transformation guidelines applicable to various state-of-the-art learned index structures to fully leverage the characteristics of disk storage. Our evaluation shows that the indexes developed by applying our guidelines achieve a Pareto improvement in both throughput and space efficiency compared to the traditional B+tree and previous implementations of disk-based learned indexes.
Materialized View Selection & View-Based Query Planning for Regular Path Queries
Authors: Pang Yue , Zou Lei , Yu Jeffrey Xu , Yang Linglin
Published: May 2024

A regular path query (RPQ) returns node pairs connected by a path whose edge label sequence satisfies the given regular expression. Given a workload of RPQs, selecting the shared subqueries as materialized views to precompute offline can speed up the online processing. Since the available memory is limited, we define the materialized view selection (MVS) problem for RPQs as minimizing the total workload query cost within a memory budget. To tackle the problem's NP-hardness, we design an efficient MVS algorithm based on heuristics. To prevent redundancies in the selected views, we devise the AND-OR directed acyclic graph with closure (AODC) as the multi-RPQ query plan representation for the workload, which encodes the relations between subqueries. In addition to detecting view redundancy, the AODC also incrementally updates itself during view selection. To support query planning, we design a scalable cost and cardinality estimation scheme for full-fledged RPQs, including Kleene closures. Our method, when applied to the Wikidata Query Logs, shows a 9.73× speedup in the total query processing time compared to ad-hoc processing, using the views it selects.
Optimizing Disjunctive Queries with Tagged Execution
Authors: Kim Albert , Madden Samuel
Published: May 2024

Despite decades of research into query optimization, optimizing queries with disjunctive predicate expressions remains a challenge. Solutions employed by existing systems (if any) are often simplistic and lead to much redundant work being performed by the execution engine. To address these problems, we propose a novel form of query execution called tagged execution. Tagged execution groups tuples into subrelations based on which predicates in the query they satisfy (or don't satisfy) and tags them with that information. These tags then provide additional context for query operators to take advantage of during runtime, allowing them to eliminate much of the redundant work performed by traditional engines and realize predicate pushdown optimizations for disjunctive predicates. However, tagged execution brings its own challenges, and the question of what tags to create is a nontrivial one. Careless creation of tags can lead to an exponential blowup in the tag space, with the overhead outweighing the benefits. To address this issue, we present a technique called tag generalization to minimize the space of tags. We implemented the tagged execution model with tag generalization in our system Basilisk, and our evaluation showed an average 2.7x speedup in runtime over the traditional execution model with up to a 19x speedup in certain situations.
Optimizing Time Series Queries with Versions
Authors: Kang Rui , Song Shaoxu
Published: May 2024

We show that the time-series database for industrial IoT data management exhibits intrinsic demands for integrating an automatic version control system, which introduces advanced data semantics and query optimization. In deployed IoT database instances, IoT data managed by an LSM tree is multi-leveled and multi-versioned due to network issues and erroneous IoT readings. For data semantics, each query merges versioned data according to query expressions or data block levels. For query optimization, we find that existing time-series databases relying on write-ahead-logs suboptimally execute data queries, due to their performance bottlenecks in merging numerous versioned data. In this paper, an algebra consisting of version operators addresses the semantics for time-series applications to evaluate and optimize physical query plans. We propose version reducibility as a key feature of executing consistent plans and evaluate the benefits of putting off data merges. We also show the integration of version queries to existing relational databases by translating them to standard SQL based on relational reducibility. Finally, our extended experiments show the effectiveness of optimizing execution plans over versioned data.
OTClean: Data Cleaning for Conditional Independence Violations using Optimal Transport
Authors: Pirhadi Alireza , Moslemi Mohammad Hossein , Cloninger Alexander , Milani Mostafa , Salimi Babak
Published: May 2024

Ensuring Conditional Independence (CI) constraints is pivotal for the development of fair and trustworthy machine learning models. In this paper, we introduce OTClean, a framework that harnesses optimal transport theory for data repair under CI constraints. Optimal transport theory provides a rigorous framework for measuring the discrepancy between probability distributions, thereby ensuring control over data utility. We formulate the data repair problem concerning CIs as a Quadratically Constrained Linear Program (QCLP) and propose an alternating method for its solution. However, this approach faces scalability issues due to the computational cost associated with computing optimal transport distances, such as the Wasserstein distance. To overcome these scalability challenges, we reframe our problem as a regularized optimization problem, enabling us to develop an iterative algorithm inspired by Sinkhorn's matrix scaling algorithm, which efficiently addresses high-dimensional and large-scale data. Through extensive experiments, we demonstrate the efficacy and efficiency of our proposed methods, showcasing their practical utility in real-world data cleaning and preprocessing tasks. Furthermore, we provide comparisons with traditional approaches, highlighting the superiority of our techniques in terms of preserving data utility while ensuring adherence to the desired CI constraints.
PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware
Authors: Cai Shuangyu , Tian Boyu , Zhang Huanchen , Gao Mingyu
Published: May 2024

Graph pattern matching is powerful and widely applicable to many application domains. Despite the recent algorithm advances, matching patterns in large-scale real-world graphs still faces the memory access bottleneck on conventional computing systems. Processing-in-memory (PIM) is an emerging hardware architecture paradigm that puts computing cores into memory devices to alleviate the memory wall issues. Real PIM hardware has recently become commercially accessible to the public. In this work, we leverage the real PIM hardware platform to build a graph pattern matching framework, PimPam, to benefit from its abundant computation and memory bandwidth resources. We propose four key optimizations in PimPam to improve its efficiency, including (1) load-aware task assignment to ensure load balance, (2) space-efficient and parallel data partitioning to prepare input data for PIM cores, (3) adaptive multi-threading collaboration to automatically select the best parallelization strategy during processing, and (4) dynamic bitmap structures that accelerate the key operations of set intersection. When evaluated on five patterns and six real-world graphs, PimPam outperforms the state-of-the-art CPU baseline system by 22.5x on average and up to 71.7x, demonstrating significant performance improvements.
Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning
Authors: Ding Zezhong , Xiang Yongan , Wang Shangyou , Xie Xike , Zhou S. Kevin
Published: May 2024

In the realm of distributed systems tasked with managing and processing large-scale graph-structured data, optimizing graph partitioning stands as a pivotal challenge. The primary goal is to minimize communication overhead and runtime cost. However, alongside the computational complexity associated with optimal graph partitioning, a critical factor to consider is memory overhead. Real-world graphs often reach colossal sizes, making it impractical and economically unviable to load the entire graph into memory for partitioning. This is also a fundamental premise in distributed graph processing, where accommodating a graph with non-distributed systems is unattainable. Currently, existing streaming partitioning algorithms exhibit a skew-oblivious nature, yielding satisfactory partitioning results exclusively for specific graph types. In this paper, we propose a novel streaming partitioning algorithm, the Skewness-aware Vertex-cut Partitioner (S5P ), designed to leverage the skewness characteristics of real graphs for achieving high-quality partitioning. S5P offers high partitioning quality by segregating the graph's edge set into two subsets, head and tail sets. Following processing by a skewness-aware clustering algorithm, these two subsets subsequently undergo a Stackelberg graph game. Our extensive evaluations conducted on substantial real-world and synthetic graphs demonstrate that, in all instances, the partitioning quality of S5P surpasses that of existing streaming partitioning algorithms, operating within the same load balance constraints. For example, S5P can bring up to a 51% improvement in partitioning quality compared to the top partitioner among the baselines. Lastly, we showcase that the implementation of S5P results in up to an 81% reduction in communication cost and a 130% increase in runtime efficiency for distributed graph processing tasks on PowerGraph.
RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search
Authors: Gao Jianyang , Long Cheng
Published: May 2024

Searching for approximate nearest neighbors (ANN) in the high-dimensional Euclidean space is a pivotal problem. Recently, with the help of fast SIMD-based implementations, Product Quantization (PQ) and its variants can often efficiently and accurately estimate the distances between the vectors and have achieved great success in the in-memory ANN search. Despite their empirical success, we note that these methods do not have a theoretical error bound and are observed to fail disastrously on some real-world datasets. Motivated by this, we propose a new randomized quantization method named RaBitQ, which quantizes D-dimensional vectors into D-bit strings. RaBitQ guarantees a sharp theoretical error bound and provides good empirical accuracy at the same time. In addition, we introduce efficient implementations of RaBitQ, supporting to estimate the distances with bitwise operations or SIMD-based operations. Extensive experiments on real-world datasets confirm that (1) our method outperforms PQ and its variants in terms of accuracy-efficiency trade-off by a clear margin and (2) its empirical performance is well-aligned with our theoretical analysis.
Revisiting B-tree Compression: An Experimental Study
Authors: Gao Chuqing , Ballijepalli Shreya , Wang Jianguo
Published: May 2024

B-trees are widely recognized as one of the most important index structures in database systems, providing efficient query processing capabilities. Over the past few decades, many techniques have been developed to enhance the efficiency of B-trees from various perspectives. Among them, B-tree compression is an important technique introduced as early as the 1970s to improve both space efficiency and query performance. Since then, several B-tree compression techniques have been developed. However, to our surprise, we have found that these B-tree compression techniques were never compared against each other in prior works. Consequently, many important questions remain unanswered, such as whether B-tree compression is truly effective or not. If it is effective, under what scenarios and which B-tree compression methods should be employed? In this paper, we conduct the first experimental evaluation of seven widely used B-tree compression techniques using both synthetic and real datasets. Based on our evaluation, we present lessons and insights that can be leveraged to guide system design decisions in modern databases regarding the use of B-tree compression.
Scalable Distributed Inverted List Indexes in Disaggregated Memory
Authors: Widmoser Manuel , Kocher Daniel , Augsten Nikolaus
Published: May 2024

Memory disaggregation separates compute (CPU) and main memory resources into disjoint physical units to enable elastic and independent scaling. Connected via high-speed RDMA-enabled networks, compute nodes can directly access remote memory. This setting often requires complex protocols with many network roundtrips as memory nodes have near-zero compute power.

In this paper, we design a scalable distributed inverted list index for disaggregated memory architectures. An inverted list index maps a set of terms to lists of documents that contain this term. Current solutions either partition the index horizontally or vertically with severe limitations in the disaggregated memory setting due to data and access skew, high network latency, or out-of-memory errors. Our method partitions lists into fixed-size blocks and spreads them across the memory nodes to balance skewed accesses. Block-based list processing keeps the memory footprint of compute nodes low and masks latency by interleaving remote accesses with expensive list operations. In addition, we propose efficient updates with optimistic concurrency control and read-write conflict detection. Our experiments confirm the efficiency and scalability of our method.
uBlade: Efficient Batch Processing for Uncertainty Graph Queries
Authors: Yao Siyuan , Li Yuchen , Sun Shixuan , Jiang Jiaxin , He Bingsheng
Published: May 2024

The study of uncertain graphs is crucial in diverse fields, including but not limited to protein interaction analysis, viral marketing, and network reliability. Processing queries on uncertain graphs presents formidable challenges due to the vast probabilistic space they encapsulate. While existing systems employ batch processing to address these challenges, their performance is often compromised by the suboptimal selection of parallel graph traversal methods, the excessive costs in random number generation, and additional workloads intrinsic to batch processing. In this paper, we introduce uBlade, an efficient batch-processing framework for uncertain graph queries on multi-core CPUs. uBlade utilizes the work-efficient graph traversal, achieving superior parallelism in the batch processing model. Additionally, our Quasi-Sampling technique reduces the random number generation cost by a factor of B, with O(B) denoting the batch size. We further examine the extra workload resulting from batch processing and introduce an efficient strategy to reorder possible worlds, minimizing this associated overhead. Through comprehensive evaluations, we showcase that uBlade achieves up to two orders of magnitude speedups against the state-of-the-art CPU and GPU-based solutions.
Wii: Dynamic Budget Reallocation In Index Tuning
Authors: Wang Xiaoying , Wu Wentao , Wang Chi , Narasayya Vivek , Chaudhuri Surajit
Published: May 2024

Index tuning aims to find the optimal index configuration for an input workload. It is often a time-consuming and resource-intensive process, largely attributed to the huge amount of "what-if" calls made to the query optimizer during configuration enumeration. Therefore, in practice it is desirable to set a budget constraint that limits the number of what-if calls allowed. This yields a new problem of budget allocation, namely, deciding on which query-configuration pairs (QCP's) to issue what-if calls. Unfortunately, optimal budget allocation is NP-hard, and budget allocation decisions made by existing solutions can be inferior. In particular, many of the what-if calls allocated by using existing solutions are devoted to QCP's whose what-if costs can be approximated by using cost derivation, a well-known technique that is computationally much more efficient and has been adopted by commercial index tuning software. This results in considerable waste of the budget, as these what-if calls are unnecessary. In this paper, we propose "Wii," a lightweight mechanism that aims to avoid such spurious what-if calls. It can be seamlessly integrated with existing configuration enumeration algorithms. Experimental evaluation on top of both standard industrial benchmarks and real workloads demonstrates that Wii can eliminate significant number of spurious what-if calls. Moreover, by reallocating the saved budget to QCP's where cost derivation is less accurate, existing algorithms can be significantly improved in terms of the final configuration found.
StarfishDB: A Query Execution Engine for Relational Probabilistic Programming
Authors: Ben Amara Ouael , Hadouaj Sami , Meneghetti Niccolò
Published: May 2024

We introduce StarfishDB, a query execution engine optimized for relational probabilistic programming. Our engine adopts the model of Gamma Probabilistic Databases, representing probabilistic programs as a collection of relational constraints, imposed against a generative stochastic process. We extend the model with the support for recursion, factorization and the ability to leverage just-in-time compilation techniques to speed up inference. We test our engine against a state-of-the-art sampler for Latent Dirichlet Allocation.
ThalamusDB: Approximate Query Processing on Multi-Modal Data
Authors: Jo Saehan , Trummer Immanuel
Published: May 2024

We introduce ThalamusDB, a novel approximate query processing system that processes complex SQL queries on multi-modal data. ThalamusDB supports SQL queries integrating natural language predicates on visual, audio, and text data. To answer such queries, ThalamusDB exploits a collection of zero-shot models in combination with relational processing. ThalamusDB utilizes deterministic approximate query processing, harnessing the relative efficiency of relational processing to mitigate the computational demands of machine learning inference. For evaluating a natural language predicate, ThalamusDB requests a small number of labels from users. User can specify their preferences on the performance objective regarding the three relevant metrics: approximation error, computation time, and labeling overheads. The ThalamusDB query optimizer chooses optimized plans according to user preferences, prioritizing data processing and requested labels to maximize impact. Experiments with several real-world data sets, taken from Craigslist, YouTube, and Netflix, show that ThalamusDB achieves an average speedup of 35.0x over MindsDB, an exact processing baseline, and outperforms ABAE, a sampling-based method, in 78.9% of cases.
Keep It Simple: Testing Databases via Differential Query Plans
Authors: Ba Jinsheng , Rigger Manuel
Published: May 2024

Query optimizers perform various optimizations, many of which have been proposed to optimize joins. It is pivotal that these optimizations are correct, meaning that they should be extensively tested. Besides manually written tests, automated testing approaches have gained broad adoption. Such approaches semi-randomly generate databases and queries. More importantly, they provide a so-called test oracle that can deduce whether the system's result is correct. Recently, researchers have proposed a novel testing approach called Transformed Query Synthesis (TQS) specifically designed to find logic bugs in join optimizations. TQS is a sophisticated approach that splits a given input table into several sub-tables and validates the results of the queries that join these sub-tables by retrieving the given table. We studied TQS's bug reports, and found that 14 of 15 unique bugs were reported by showing discrepancies in executing the same query with different query plans. Therefore, in this work, we propose a simple alternative approach to TQS. Our approach enforces different query plans for the same query and validates that the results are consistent. We refer to this approach as Differential Query Plan (DQP) testing. DQP can reproduce 14 of the 15 unique bugs found by TQS, and found 26 previously unknown and unique bugs. These results demonstrate that a simple approach with limited novelty can be as effective as a complex, conceptually appealing approach. Additionally, DQP is complementary to other testing approaches for finding logic bugs. 81% of the logic bugs found by DQP cannot be found by NoREC and TLP, whereas DQP overlooked 86% of the bugs found by NoREC and TLP. We hope that the practicality of our approach---we implemented in less than 100 lines of code per system---will lead to its wide adoption.
Towards Human-AI Teaming to Mitigate Alert Fatigue in Security Operations Centres
Authors: Baruwal Chhetri Mohan , Tariq Shahroz , Singh Ronal , Jalalvand Fatemeh , Paris Cecile , Nepal Surya
Published: May 2024

Security Operations Centres (SOCs) play a pivotal role in defending organisations against evolving cyber threats. They function as central hubs for detecting, analysing, and responding promptly to cyber incidents with the primary objective of ensuring the confidentiality, integrity, and availability of digital assets. However, they struggle against the growing problem of alert fatigue, where the sheer volume of alerts overwhelms SOC analysts and raises the risk of overlooking critical threats. In recent times, there has been a growing call for human-AI teaming, wherein humans and AI collaborate with each other, leveraging their complementary strengths and compensating for their weaknesses. The rapid advances in AI and the growing integration of AI-enabled tools and technologies within SOCs give rise to a compelling argument for the implementation of human-AI teaming within the SOC environment. Therefore, in this article, we present our vision for human-AI teaming to address the problem of alert fatigue in the SOC. We propose the 𝒜
2
𝒞 Framework, which enables flexible and dynamic decision making by allowing seamless transitions between automated, augmented, and collaborative modes of operation. Our framework allows AI-powered automation for routine alerts, AI-driven augmentation for expedited expert decision making, and collaborative exploration for tackling complex, novel threats. By implementing and operationalising 𝒜
2
𝒞, SOCs can significantly reduce alert fatigue while empowering analysts to efficiently and effectively respond to security incidents.