bluuebunny/crossref_metadata_2025 huggingface dataset:
GIO: Generating Efficient Matrix and Frame Readers for Custom Data Formats by Example
Authors: Fathollahzadeh Saeed , Boehm Matthias
Published: June 2023

Data Scientists deal with a wide variety of file data formats and data representations. Probably the most difficult to handle are custom data formats that liberally define their own particular flat or nested structure with multiple custom delimiters, multi-line records, or undocumented semantics of attribute sequences, co-appearances, and repetitions. As a prerequisite for exploratory ML model training, data scientists need to map these data representations into regular frames or matrices. Unfortunately, existing tools and frameworks provide only limited support for aiding this process, which causes redundant manual efforts and unnecessary data quality issues. In this paper, we initiate work on automatic matrix and frame reader generation by example. A user provides a sample of raw text data and its mapped matrix or frame representation. Our GIO framework then first identifies the mapping rules from raw to structured data, and subsequently generates source code of an efficient, multi-threaded reader for reading full raw datasets of this format. In order to facilitate manual improvements, both the mapping rules, and generated reader can be modified as needed. Our experiments show that GIO is able to correctly identify the mapping rules for basic text formats like CSV, LibSVM, MatrixMarket; custom text formats from publishing, automotive, and health care; as well as various nested formats such as JSON and XML. Additionally, the automatically generated readers yield competitive performance compared to hand-coded readers and tuned libraries like RapidJSON.
rkHit: Representative Query with Uncertain Preference
Authors: Xiao Xingxing , Li Jianzhong
Published: June 2023

A top-k query retrieves the k tuples with highest scores according to a user preference, defined as a scoring function. It is difficult for a user to precisely specify the scoring function. Instead, obtaining the distribution on scoring functions, i.e., the preference distribution, has been extensively explored in many fields.

Motivated by this, we introduce the uniform (r,k)-hit (UrkHit) problem. Given a preference distribution, UrkHit aims to select a representative set of r tuples to maximize the probability of containing a tuple attractive to the user. We say a tuple attracts a user, if it is a top-k tuple for the scoring function adopted by the user. Further, we generalize UrkHit and propose the (r,k)-hit (rkHit) problem with an additional penalty function to model the user satisfaction with the tuple ranked i-th. rkHit aims to maximize the expected user satisfaction with the representative set. In 2D space, we design an exact algorithm 2DH for rkHit, indicating rkHit is in P for d=2. We show that rkHit is NP-hard when d\ge3. In 3D space, assuming a uniform preference distribution, we propose a (1-1/e)-approximation algorithm 3DH based on space partitioning. In addition, we propose an approximate algorithm MDH suitable for any dimension and distribution, which creatively combines the ideas of sampling and clustering. It relaxes the approximation guarantee slightly. Comprehensive experiments demonstrate the efficiency and effectiveness of our algorithms.
HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs
Authors: Yang Yajun , Li Hanxiao , Zhu Xiangju , Wang Junhu , Wang Xin , Gao Hong
Published: June 2023

Reachability query is a fundamental problem and has been well studied on static graphs. However, in the real world, the graphs are not static but always evolving over time. In this paper, we study the problem of historical reachability query on evolving graphs. We propose a novel index, named HR-Index, which integrates complete and correct historical reachability information of the evolving graph. A historical reachability query on an evolving graph can be converted into a static reachability query on its HR-Index and thus query efficiency can be improved significantly. We also propose two optimization techniques to reduce the size of HR-Index effectively. We confirm the effectiveness and efficiency of our method through conducting extensive experiments on real-life datasets. Experimental results show both vertex and edge size of HR-Index are far smaller than that of the evolving graphs and our method has at least an order of magnitude improvement in time and space efficiency compared to the state-of-the-art method.
Automating and Optimizing Data-Centric What-If Analyses on Native Machine Learning Pipelines
Authors: Grafberger Stefan , Groth Paul , Schelter Sebastian
Published: June 2023

Software systems that learn from data with machine learning (ML) are used in critical decision-making processes. Unfortunately, real-world experience shows that the pipelines for data preparation, feature encoding and model training in ML systems are often brittle with respect to their input data. As a consequence, data scientists have to run different kinds of data centric what-if analyses to evaluate the robustness and reliability of such pipelines, e.g., with respect to data errors or preprocessing techniques. These what-if analyses follow a common pattern: they take an existing ML pipeline, create a pipeline variant by introducing a small change, and execute this pipeline variant to see how the change impacts the pipeline's output score. The application of existing analysis techniques to ML pipelines is technically challenging as they are hard to integrate into existing pipeline code and their execution introduces large overheads due to repeated work.

We propose mlwhatif to address these integration and efficiency challenges for data-centric what-if analyses on ML pipelines. mlwhatif enables data scientists to declaratively specify what-if analyses for an ML pipeline, and to automatically generate, optimize and execute the required pipeline variants. Our approach employs pipeline patches to specify changes to the data, operators and models of a pipeline. Based on these patches, we define a multi-query optimizer for efficiently executing the resulting pipeline variants jointly, with four subsumption-based optimization rules. Subsequently, we detail how to implement the pipeline variant generation and optimizer of mlwhatif. For that, we instrument native ML pipelines written in Python to extract dataflow plans with re-executable operators.

We experimentally evaluate mlwhatif, and find that its speedup scales linearly with the number of pipeline variants in applicable cases, and is invariant to the input data size. In end-to-end experiments with four analyses on more than 60 pipelines, we show speedups of up to 13x compared to sequential execution, and find that the speedup is invariant to the model and featurization in the pipeline. Furthermore, we confirm the low instrumentation overhead of mlwhatif.
InfiniFilter: Expanding Filters to Infinity and Beyond
Authors: Dayan Niv , Bercea Ioana , Reviriego Pedro , Pagh Rasmus
Published: June 2023

Filter data structures have been used ubiquitously since the 1970s to answer approximate set-membership queries in various areas of computer science including architecture, networks, operating systems, and databases. Such filters need to be allocated with a given capacity in advance to provide a guarantee over the false positive rate. In many applications, however, the data size is not known in advance, requiring filters to dynamically expand. This paper shows that existing methods for expanding filters exhibit at least one of the following flaws: (1) they entail an expensive scan over the whole data set, (2) they require a lavish memory footprint, (3) their query, delete and/or insertion performance plummets, (4) their false positive rate skyrockets, and/or (5)~they cannot expand indefinitely.

We introduce InfiniFilter, a new method for expanding filters that addresses these shortcomings. InfiniFilter is a hash table that stores a fingerprint for each entry. It doubles in size when it reaches capacity, and it sacrifices one bit from each fingerprint to map it to the expanded hash table. The core novelty is a new and flexible hash slot format that sets longer fingerprints to newer entries. This keeps the average fingerprint length long and thus the false positive rate stable. At the same time, InfiniFilter provides stable insertion/query/delete performance as it is comprised of a unified hash table. We implement InfiniFilter on top of Quotient Filter, and we demonstrate theoretically and empirically that it offers superior cost properties compared to existing methods: it better scales performance, the false positive rate, and the memory footprint, all at the same time.
ML2DAC: Meta-Learning to Democratize AutoML for Clustering Analysis
Authors: Treder-Tschechlov Dennis , Fritz Manuel , Schwarz Holger , Mitschang Bernhard
Published: June 2023

Analysts often struggle with the combined algorithm selection and hyperparameter optimization problem, a.k.a. CASH problem in literature. Typically, they execute several algorithms with varying hyperparameter settings to find configurations that show valuable results. Efficiently finding these configurations is a major challenge. In clustering analyses, analysts face the additional challenge to select a cluster validity index that allows them to evaluate clustering results in a purely unsupervised fashion. Many different cluster validity indices exist and each one has its benefits depending on the dataset characteristics. While experienced analysts might address these challenges using their domain knowledge and experience, especially novice analysts struggle with them. In this paper, we propose a new meta-learning approach to address these challenges. Our approach uses knowledge from past clustering evaluations to apply strategies that experienced analysts would exploit. In particular, we use meta-learning to (a) select a suitable clustering validity index, (b) efficiently select well-performing clustering algorithm and hyperparameter configurations, and (c) reduce the search space to suitable clustering algorithms. In the evaluation, we show that our approach significantly outperforms state-of-the-art approaches regarding accuracy and runtime.
Detock: High Performance Multi-region Transactions at Scale
Authors: Nguyen Cuong D. T. , Miller Johann K. , Abadi Daniel J.
Published: June 2023

Many globally distributed data stores need to replicate data across large geographic distances. Since synchronously replicating data across such distances is slow, those systems with high consistency requirements often geo-partition data and direct all linearizable requests to the primary region of the accessed data. This significantly improves performance for workloads where most transactions access data close to where they originate from. However, supporting serializable multi-geo-partition transactions is a challenge, and they often degrade the performance of the whole system. This becomes even more challenging when they conflict with single-partition requests, where optimistic protocols lead to high numbers of aborts, and pessimistic protocols lead to high numbers of distributed deadlocks. In this paper, we describe the design of concurrency control and deadlock resolution protocols, built within a practical, complete implementation of a geographically replicated database system called Detock, that enables processing strictly-serializable multi-region transactions with near-zero performance degradation at extremely high conflict and order of magnitude higher throughput relative to state-of-the art geo-replication approaches, while improving latency by up to a factor of 5.
Measuring Re-identification Risk
Authors: Carey CJ , Dick Travis , Epasto Alessandro , Javanmard Adel , Karlin Josh , Kumar Shankar , Muñoz Medina Andres , Mirrokni Vahab , Nunes Gabriel Henrique , Vassilvitskii Sergei , Zhong Peilin
Published: June 2023

Compact user representations (such as embeddings) form the backbone of personalization services. In this work, we present a new theoretical framework to measure re-identification risk in such user representations. Our framework, based on hypothesis testing, formally bounds the probability that an attacker may be able to obtain the identity of a user from their representation. As an application, we show how our framework is general enough to model important real-world applications such as the Chrome's Topics API for interest-based advertising. We complement our theoretical bounds by showing provably good attack algorithms for re-identification that we use to estimate the re-identification risk in the Topics API. We believe this work provides a rigorous and interpretable notion of re-identification risk and a framework to measure it that can be used to inform real-world applications.
Free Join: Unifying Worst-Case Optimal and Traditional Joins
Authors: Wang Yisu Remy , Willsey Max , Suciu Dan
Published: June 2023

Over the last decade, worst-case optimal join (WCOJ) algorithms have emerged as a new paradigm for one of the most fundamental challenges in query processing: computing joins efficiently. Such an algorithm can be asymptotically faster than traditional binary joins, all the while remaining simple to understand and implement. However, they have been found to be less efficient than the old paradigm, traditional binary join plans, on the typical acyclic queries found in practice. Some database systems that support WCOJ use a hybrid approach: use WCOJ to process the cyclic subparts of the query (if any), and rely on traditional binary joins otherwise. In this paper we propose a new framework, called Free Join, that unifies the two paradigms. We describe a new type of plan, a new data structure (which unifies the hash tables and tries used by the two paradigms), and a suite of optimization techniques. Our system, implemented in Rust, matches or outperforms both traditional binary joins and WCOJ on standard query benchmarks.
Computing the Difference of Conjunctive Queries Efficiently
Authors: Hu Xiao , Wang Qichen
Published: June 2023

We investigate how to efficiently compute the difference result of two (or multiple) conjunctive queries, which is the last operator in relational algebra to be unraveled. The standard approach in practical database systems is to materialize the results for every input query as a separate set, and then compute the difference of two (or multiple) sets. This approach is bottlenecked by the complexity of evaluating every input query individually, which could be very expensive, particularly when there are only a few results in the difference. In this paper, we introduce a new approach by exploiting the structural property of input queries and rewriting the original query by pushing the difference operator down as much as possible. We show that for a large class of difference queries, this approach can lead to a linear-time algorithm, in terms of the input size and (final) output size, i.e., the number of query results that survive from the difference operator. We complete this result by showing the hardness of computing the remaining difference queries in linear time. Although a linear-time algorithm is hard to achieve in general, we also provide some heuristics that can provably improve the standard approach. At last, we compare our approach with standard SQL engines over graph and benchmark datasets. The experiment results demonstrate order-of-magnitude speedups achieved by our approach over the vanilla SQL engine.
XInsight: eXplainable Data Analysis Through The Lens of Causality
Authors: Ma Pingchuan , Ding Rui , Wang Shuai , Han Shi , Zhang Dongmei
Published: June 2023

In light of the growing popularity of Exploratory Data Analysis (EDA), understanding the underlying causes of the knowledge acquired by EDA is crucial. However, it remains under-researched. This study promotes a transparent and explicable perspective on data analysis, called eXplainable Data Analysis (XDA). For this reason, we present XInsight, a general framework for XDA. XInsight provides data analysis with qualitative and quantitative explanations of causal and non-causal semantics. This way, it will significantly improve human understanding and confidence in the outcomes of data analysis, facilitating accurate data interpretation and decision making in the real world. XInsight is a three-module, end-to-end pipeline designed to extract causal graphs, translate causal primitives into XDA semantics, and quantify the quantitative contribution of each explanation to a data fact. XInsight uses a set of design concepts and optimizations to address the inherent difficulties associated with integrating causality into XDA. Experiments on synthetic and real-world datasets as well as a user study demonstrate the highly promising capabilities of XInsight.
Deep Active Alignment of Knowledge Graph Entities and Schemata
Authors: Huang Jiacheng , Sun Zequn , Chen Qijin , Xu Xiaozhou , Ren Weijun , Hu Wei
Published: June 2023

Knowledge graphs (KGs) store rich facts about the real world. In this paper, we study KG alignment, which aims to find alignment between not only entities but also relations and classes in different KGs. Alignment at the entity level can cross-fertilize alignment at the schema level. We propose a new KG alignment approach, called DAAKG, based on deep learning and active learning. With deep learning, it learns the embeddings of entities, relations and classes, and jointly aligns them in a semi-supervised manner. With active learning, it estimates how likely an entity, relation or class pair can be inferred, and selects the best batch for human labeling. We design two approximation algorithms for efficient solution to batch selection. Our experiments on benchmark datasets show the superior accuracy and generalization of DAAKG and validate the effectiveness of all its modules.
Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches
Authors: Liao Meihao , Li Rong-Hua , Dai Qiangqiang , Chen Hongyang , Qin Hongchao , Wang Guoren
Published: June 2023

Personalized PageRank (PPR) computation is a fundamental problem in graph analysis. The state-of-the-art algorithms for PPR computation are based on a bidirectional framework which include a deterministic forward push and a Monte Carlo sampling procedure. The Monte Carlo sampling procedure, however, often has a relatively-large variance, thus reducing the performance of the PPR computation algorithms. To overcome this issue, we develop two novel variance-reduced Monte Carlo techniques for PPR computation. Our first technique is to apply power iterations to reduce the variance of the Monte Carlo sampling procedure. We prove that conducting few power iterations can significantly reduce the variance of existing Monte Carlo estimators, only with few additional costs. Moreover, we show that such a simple and novel variance-reduced Monte Carlo technique can achieve comparable estimation accuracy and the same time complexity as the state-of-the-art bidirectional algorithms. Our second technique is a novel progressive sampling method which uses the historical information of former samples to reduce the variance of the Monte Carlo estimator. We develop several novel PPR computation algorithms by integrating both of these variance reduction techniques with two existing Monte Carlo sampling approaches, including random walk sampling and spanning forests sampling. Finally, we conduct extensive experiments on 5 real-life large graphs to evaluate our solutions. The results show that our algorithms can achieve much higher PPR estimation accuracy by using much less time, compared to the state-of-the-art bidirectional algorithms.
Popularity Ratio Maximization: Surpassing Competitors through Influence Propagation
Authors: Liao Hao , Bi Sheng , Wu Jiao , Zhang Wei , Zhou Mingyang , Mao Rui , Chen Wei
Published: June 2023

In this paper, we present an algorithmic study on how to surpass competitors in popularity by strategic promotions in social networks. We first propose a novel model, in which we integrate the Preferential Attachment (PA) model for popularity growth with the Independent Cascade (IC) model for influence propagation in social networks called PA-IC model. In PA-IC, a popular item and a novice item grab shares of popularity from the natural popularity growth via the PA model, while the novice item tries to gain extra popularity via influence cascade in a social network. The popularity ratio is defined as the ratio of the popularity measure between the novice item and the popular item. We formulate Popularity Ratio Maximization (PRM) as the problem of selecting seeds in multiple rounds to maximize the popularity ratio in the end. We analyze the popularity ratio and show that it is monotone but not submodular. To provide an effective solution, we devise a surrogate objective function and show that empirically it is very close to the original objective function while theoretically, it is monotone and submodular. We design two efficient algorithms, one for the overlapping influence and non-overlapping seeds (across rounds) setting and the other for the non-overlapping influence and overlapping seed setting, and further discuss how to deal with other models and problem variants. Our empirical evaluation further demonstrates that our proposed method consistently achieves the best popularity promotion compared to other methods. Our theoretical and empirical analyses shed light on the interplay between influence maximization and preferential attachment in social networks.
GuP: Fast Subgraph Matching by Guard-based Pruning
Authors: Arai Junya , Fujiwara Yasuhiro , Onizuka Makoto
Published: June 2023

Subgraph matching, which finds subgraphs isomorphic to a query, is crucial for information retrieval from data represented as a graph. To avoid redundant explorations in the data, existing methods restrict the search space by extracting candidate vertices and edges that may constitute isomorphic subgraphs. However, expensive computation is still required because candidate vertices induce many non-isomorphic subgraphs. In this paper, we propose GuP, a subgraph matching algorithm with pruning based on guards. A guard represents a pattern of intermediate search states that never lead to isomorphic subgraphs. By attaching a guard to each candidate vertex and edge, GuP adaptively filters out unnecessary candidates depending on the search state at each step. The experimental results show that GuP effectively reduces the search space and can answer difficult queries that state-of-the-art methods cannot answer within a practical time frame.
DeltaBoost: Gradient Boosting Decision Trees with Efficient Machine Unlearning
Authors: Wu Zhaomin , Zhu Junhui , Li Qinbin , He Bingsheng
Published: June 2023

As machine learning (ML) has been widely developed in real-world applications, the privacy of ML models draws an increasing concern. In this paper, we study how to forget specific data records from ML models to preserve the privacy of these data. Although some studies propose efficient unlearning algorithms on random forests and extremely randomized trees, Gradient Boosting Decision Trees (GBDT), which are widely used in practice, have not been explored. The efficient unlearning of GBDT faces two major challenges: 1) the training of each tree is deterministic and non-robust; 2) the training of a tree depends on all the previous trees. To solve the first challenge, we propose a robust GBDT-like ML model DeltaBoost that enables efficient and accurate deletion according to our theoretical analysis. For the second challenge, we design a training algorithm for DeltaBoost that minimizes the dependency among trees. Our experiments on five datasets demonstrate that DeltaBoost can remove data records from the trained model efficiently and effectively. Our unlearning approach achieves up to two orders of magnitude speedup compared to retraining GBDT. Besides, DeltaBoost produces competitive performance to existing decision-tree-based ML models.
SSIN: Self-Supervised Learning for Rainfall Spatial Interpolation
Authors: Li Jia , Shen Yanyan , Chen Lei , Ng Charles Wang Wai
Published: June 2023

The acquisition of accurate rainfall distribution in space is an important task in hydrological analysis and natural disaster pre-warning. However, it is impossible to install rain gauges on every corner. Spatial interpolation is a common way to infer rainfall distribution based on available raingauge data. However, the existing works rely on some unrealistic pre-settings to capture spatial correlations, which limits their performance in real scenarios. To tackle this issue, we propose the SSIN, which is a novel data-driven self-supervised learning framework for rainfall spatial interpolation by mining latent spatial patterns from historical observation data. Inspired by the Cloze task and BERT, we fully consider the characteristics of spatial interpolation and design the SpaFormer model based on the Transformer architecture as the core of SSIN. Our main idea is: by constructing rich self-supervision signals via random masking, SpaFormer can learn informative embeddings for raw data and then adaptively model spatial correlations based on rainfall spatial context. Extensive experiments on two real-world raingauge datasets show that our method outperforms the state-of-the-art solutions. In addition, we take traffic spatial interpolation as another use case to further explore the performance of our method, and SpaFormer achieves the best performance on one large real-world traffic dataset, which further confirms the effectiveness and generality of our method.
Selection Pushdown in Column Stores using Bit Manipulation Instructions
Authors: Li Yinan , Lu Jianan , Chandramouli Badrish
Published: June 2023

Modern analytical database systems predominantly rely on column-oriented storage, which offers superior compression efficiency due to the nature of the columnar layout. This compression, however, creates challenges in decoding speed during query processing. Previous research has explored predicate pushdown on encoded values to avoid decoding, but these techniques are restricted to specific encoding schemes and predicates, limiting their practical use. In this paper, we propose a generic predicate pushdown approach that supports arbitrary predicates by leveraging selection pushdown to reduce decoding costs. At the core of our approach is a fast select operator capable of directly extracting selected encoded values without decoding, by using Bit Manipulation Instructions, an instruction set extension to the X86 architecture. We empirically evaluate the proposed techniques in the context of Apache Parquet using both micro-benchmarks and the TPC-H benchmark, and show that our techniques improve the query performance of Parquet by up to one order of magnitude with representative scan queries. Further experimentation using Apache Spark demonstrates speed improvements of up to 5.5X even for end-to-end queries involving complex joins.
Query-Guided Resolution in Uncertain Databases
Authors: Drien Osnat , Freiman Matanya , Amarilli Antoine , Amsterdamer Yael
Published: June 2023

We present a novel framework for uncertain data management. We start with a database whose tuple correctness is uncertain and an oracle that can resolve the uncertainty, i.e., decide if a tuple is correct or not. Such an oracle may correspond, e.g., to a data expert or to a crowdsourcing platform. We wish to use the oracle to clean the database with the goal of ensuring the correct answer for specific mission-critical queries. To avoid the prohibitive cost of cleaning the entire database and to minimize the expected number of calls to the oracle, we must carefully select tuples whose resolution would suffice to resolve the uncertainty in query results. In other words, we need a query-guided process for the resolution of uncertain data.

We develop an end-to-end solution to this problem, based on the derivation of query answers and on correctness probabilities for the uncertain data. At a high level, we first track Boolean provenance to identify which input tuples contribute to the derivation of each output tuple, and in what ways. We then design an active learning solution for iteratively choosing tuples to resolve, based on the provenance structure and on an evolving estimation of tuple correctness probabilities. We conduct an extensive experimental study to validate our framework in different use cases.
DiffPrep: Differentiable Data Preprocessing Pipeline Search for Learning over Tabular Data
Authors: Li Peng , Chen Zhiyi , Chu Xu , Rong Kexin
Published: June 2023

Data preprocessing is a crucial step in the machine learning process that transforms raw data into a more usable format for downstream ML models. However, it can be costly and time-consuming, often requiring the expertise of domain experts. Existing automated machine learning (AutoML) frameworks claim to automate data preprocessing. However, they often use a restricted search space of data preprocessing pipelines which limits the potential performance gains, and they are often too slow as they require training the ML model multiple times. In this paper, we propose DiffPrep, a method that can automatically and efficiently search for a data preprocessing pipeline for a given tabular dataset and a differentiable ML model such that the performance of the ML model is maximized. We formalize the problem of data preprocessing pipeline search as a bi-level optimization problem. To solve this problem efficiently, we transform and relax the discrete, non-differential search space into a continuous and differentiable one, which allows us to perform the pipeline search using gradient descent with training the ML model only once. Our experiments show that DiffPrep achieves the best test accuracy on 15 out of the 18 real-world datasets evaluated and improves the model's test accuracy by up to 6.6 percentage points.
GraphINC: Graph Pattern Mining at Network Speed
Authors: Hussein Rana , Lerner Alberto , Ryser Andre , Bürgi Lucas David , Blarer Albert , Cudre-Mauroux Philippe
Published: June 2023

Graph Pattern Mining (GPM) is a class of algorithms that identifies given shapes within a graph, e.g., cliques of a certain size. Any area of a graph can contain a shape of interest, but in real-world graphs, these shapes tend to be concentrated in areas deemed skewed. Because mining skewed areas can dominate GPM computations, the overwhelming majority of state-of-the-art GPM techniques break such areas into many small parts and load balance them across servers. This paper takes a diametrically opposite approach: we suggest a framework that concentrates rather than divides the skewed areas.

Our framework, called GraphINC, relies on two key innovations. First, it introduces a new graph partitioning scheme capable of separating the skewed area from the rest of the graph. Second, it offloads the skewed part onto a new class of hardware accelerator, a programmable network switch. We implemented our framework to leverage a commercial 100 Gbps switch and obtained results 6.5 to 52.4× faster thanks to our novel offloading technique.
DAMR: Dynamic Adjacency Matrix Representation Learning for Multivariate Time Series Imputation
Authors: Ren Xiaobin , Zhao Kaiqi , Riddle Patricia J. , Taskova Katerina , Pan Qingyi , Li Lianyan
Published: June 2023

Missing data imputation for location-based sensor data has attracted much attention in recent years. The state-of-the-art imputation methods based on graph neural networks have a priori assumption that the spatial correlations between sensor locations are static. However, real-world data sets often exhibit dynamic spatial correlations. This paper proposes a novel approach to capturing the dynamics of spatial correlations between geographical locations as a composition of the constant, long-term trends and periodic patterns. To this end, we design a new method called Dynamic Adjacency Matrix Representation (DAMR) that extracts various dynamic patterns of spatial correlations and represents them as adjacency matrices. The adjacency matrices are then aggregated and fed into a well-designed graph representation learning layer for predicting the missing values. Through extensive experiments on six real-world data sets, we demonstrate that DAMR reduces the MAE by up to 19.4% compared with the state-of-the-art methods for the missing value imputation task
Presto: A Decade of SQL Analytics at Meta
Authors: Sun Yutian , Meehan Tim , Schlussel Rebecca , Xie Wenlei , Basmanova Masha , Erling Orri , Rosa Andrii , Fan Shixuan , Zhong Rongrong , Thirupathi Arun , Collooru Nikhil , Wang Ke , Agarwal Sameer , Gupta Arjun , Logothetis Dionysios , Xirogiannopoulos Kostas , Dutta Amit , Gajjala Varun , Jain Rohit , Palakuzhy Ajay , Pandian Prithvi , Pershin Sergey , Saikia Abhisek , Shankhdhar Pranjal , Somanchi Neerad , Tailor Swapnil , Tan Jialiang , Viswanadha Sreeni , Wen Zac , Chattopadhyay Biswapesh , Fan Bin , Majeti Deepak , Pandit Aditi
Published: June 2023

Presto is an open-source distributed SQL query engine that supports analytics workloads involving multiple exabyte-scale data sources. Presto is used for low-latency interactive use cases as well as long-running ETL jobs at Meta. It was originally launched at Meta in 2013 and donated to the Linux Foundation in 2019. Over the last ten years, upholding query latency and scalability with the hyper growth of data volume at Meta as well as new SQL analytics requirements have raised impressive challenges for Presto. A top priority has been ensuring query reliability does not regress with the shift towards smaller, more elastic container allocation, which requires queries to run with substantially smaller memory headroom and can be preempted at any time. Additionally, new demands from machine learning, privacy, and graph analytics have driven Presto maintainers to think beyond traditional data analytics. In this paper, we discuss several successful evolutions in recent years that have improved Presto latency as well as scalability by several orders of magnitude in production at Meta. Some of the notable ones are hierarchical caching, native vectorized execution engines, materialized views, and Presto on Spark. With these new capabilities, we have deprecated or are in the process of deprecating various legacy query engines so that Presto becomes the single piece to serve interactive, ad-hoc, ETL, and graph processing workloads for the entire data warehouse.
Keep Your Distributed Data Warehouse Consistent at a Minimal Cost
Authors: Xu Zhichen , Gao Ying , Davidson Andrew
Published: June 2023

Large data warehouses store interdependent tables that are updated independently in response to business logic changes or late arrival of critical data. To keep the warehouse consistent, changes to upstream tables need to be propagated to downstream tables in a timely fashion. However, a naive change propagation algorithm can cause many unnecessary updates or recalculations of downstream tables, which drives up the cost of data warehouse management.

In this paper, we describe our solution that can ensure the eventual consistency of the data warehouse while avoiding unnecessary table updates. We also show that the optimal trade-off between computational cost reduction and meeting data freshness constraints can be found by solving a dynamic programming problem.

The proposed solution is currently in production to manage the YouTube Data Warehouse and has reduced update requests by 25% by eliminating non-trivial duplicates. These requests would have been carried out by large batch jobs over big data. Eliminating them has led to a proportionate reduction in computing resources.

One key advantage of our approach is that it can be used in a heterogeneous, distributed data warehouse environment where the operator software may not have complete control over the query processors. This is because our approach only relies on having dependency information for tables and can operate on the post-state of data sources.
GoldMiner: Elastic Scaling of Training Data Pre-Processing Pipelines for Deep Learning
Authors: Zhao Hanyu , Yang Zhi , Cheng Yu , Tian Chao , Ren Shiru , Xiao Wencong , Yuan Man , Chen Langshi , Liu Kaibo , Zhang Yang , Li Yong , Lin Wei
Published: June 2023

Training data pre-processing pipelines are essential to deep learning (DL). As the performance of model training keeps increasing with both hardware advancements (e.g., faster GPUs) and various software optimizations, the data pre-processing on CPUs is becoming more resource-intensive and a severe bottleneck of the pipeline. This problem is even worse in the cloud, where training jobs exhibit diverse CPU-GPU demands that usually result in mismatches with fixed hardware configurations and resource fragmentation, degrading both training performance and cluster utilization.

We introduce GoldMiner, an input data processing service for stateless operations used in pre-processing data for DL model training. GoldMiner decouples data pre-processing from model training into a new role called the data worker. Data workers facilitate scaling of data pre-processing to anywhere in a cluster, effectively pooling the resources across the cluster to satisfy the diverse requirements of training jobs. GoldMiner achieves this decoupling in a fully automatic and elastic manner. The key insight is that data pre-processing is inherently stateless, thus can be executed independently and elastically. This insight guides GoldMiner to automatically extract stateless computation out of a monolithic training program, efficiently disaggregate it across data workers, and elastically scale data workers to tune the resource allocations across jobs to optimize cluster efficiency. We have applied GoldMiner to industrial workloads, and our evaluation shows that GoldMiner can transform unmodified training programs to use data workers, accelerating individual training jobs by up to 12.1x. GoldMiner also improves average job completion time and aggregate GPU utilization by up to 2.5x and 2.1x in a 64-GPU cluster, respectively, by scheduling data workers with elasticity.
VeDB: A Software and Hardware Enabled Trusted Relational Database
Authors: Yang Xinying , Zhang Ruide , Yue Cong , Liu Yang , Ooi Beng Chin , Gao Qun , Zhang Yuan , Yang Hao
Published: June 2023

Blockchain-like ledger databases emerge in recent years as a more efficient alternative to permissioned blockchains. Conventional ledger databases mostly rely on authenticated structures such as the Merkle tree and transparency logs for supporting auditability, and hence they suffer from the performance problem. As opposed to conventional ledger DBMSes, we design VeDB - a high-performance verifiable software (Ve-S) and hardware (Ve-H) enabled DBMS with rigorous auditability for better user options and broad applications. In Ve-S, we devise a novel verifiable Shrubs array (VSA) with two-layer ordinals (serial numbers) which outperforms conventional Merkle tree-based models due to lower CPU and I/O cost. It enables rigorous auditability through its efficient credible timestamp range authentication method, and fine-grained data verification at the client side, which are lacking in state-of-the-art relational ledger databases. In Ve-H, we devise a non-intrusive trusted affiliation by TEE leveraging digest signing, monotonic counters, and trusted timestamps in VeDB, which supports both data notarization and lineage applications. The experimental results show that VeDB-VSA outperforms Merkle tree-based authenticated data structures (ADS) up to 70× and 3.7× for insertion and verification; and VeDB Ve-H data lineage verification is 8.5× faster than Ve-S.
What's the Difference? Incremental Processing with Change Queries in Snowflake
Authors: Akidau Tyler , Barbier Paul , Cseri Istvan , Hueske Fabian , Jones Tyler , Lionheart Sasha , Mills Daniel , Pauliukevich Dzmitry , Probst Lukas , Semmler Niklas , Sotolongo Dan , Zhang Boyuan
Published: June 2023

Incremental algorithms are the heart and soul of stream processing. Low latency results depend on the ability to react to the subset of changes in a dataset over time rather than reprocessing the entirety of a dataset as it evolves. But while the SQL language is well suited for representing streams of changes (via tables) and their application to tables over time (via DML), it entirely lacks a method to query the changes to a table or view in the first place.

In this paper, we present CHANGES queries and STREAM objects, Snowflake's primitives for querying and consuming incremental changes to table objects over time. CHANGES queries and STREAMs have been in use within Snowflake for three years, and see broad adoption across our customers. We describe the semantics of these primitives, discuss the implementation challenges, present an analysis of their usage at Snowflake, and contrast with other offerings.
PG-Schema: Schemas for Property Graphs
Authors: Angles Renzo , Bonifati Angela , Dumbrava Stefania , Fletcher George , Green Alastair , Hidders Jan , Li Bei , Libkin Leonid , Marsault Victor , Martens Wim , Murlak Filip , Plantikow Stefan , Savkovic Ognjen , Schmidt Michael , Sequeda Juan , Staworko Slawek , Tomaszuk Dominik , Voigt Hannes , Vrgoc Domagoj , Wu Mingxi , Zivkovic Dusan
Published: June 2023

Property graphs have reached a high level of maturity, witnessed by multiple robust graph database systems as well as the ongoing ISO standardization effort aiming at creating a new standard Graph Query Language (GQL). Yet, despite documented demand, schema support is limited both in existing systems and in the first version of the GQL Standard. It is anticipated that the second version of the GQL Standard will include a rich DDL. Aiming to inspire the development of GQL and enhance the capabilities of graph database systems, we propose PG-Schema, a simple yet powerful formalism for specifying property graph schemas. It features PG-Schema with flexible type definitions supporting multi-inheritance, as well as expressive constraints based on the recently proposed PG-Keys formalism. We provide the formal syntax and semantics of PG-Schema, which meet principled design requirements grounded in contemporary property graph management scenarios, and offer a detailed comparison of its features with those of existing schema languages and graph database systems.
Vineyard: Optimizing Data Sharing in Data-Intensive Analytics
Authors: Yu Wenyuan , He Tao , Wang Lei , Meng Ke , Cao Ye , Zhu Diwen , Li Sanhong , Zhou Jingren
Published: June 2023

Modern data analytics and AI jobs become increasingly complex and involve multiple tasks performed on specialized systems. Sharing of intermediate data between different systems is often a significant bottleneck in such jobs. When the intermediate data is large, it is mostly exchanged through files in standard formats (e.g., CSV and ORC), causing high I/O and (de)serialization overheads. To solve these problems, we develop Vineyard, a high-performance, extensible, and cloud-native object store, trying to provide an intuitive experience for users to share data across systems in complex real-life workflows. Since different systems usually work on data structures (e.g., dataframes, graphs, hashmaps) with similar interfaces, and their computation logic is often loosely-coupled with how such interfaces are implemented over specific memory layouts, it enables Vineyard to conduct data sharing efficiently at a high level via memory mapping and method sharing. Vineyard provides an IDL named VCDL to facilitate users to register their own intermediate data types into Vineyard such that objects of the registered types can then be efficiently shared across systems in a polyglot workflow. As a cloud-native system, Vineyard is designed to work closely with Kubernetes, as well as achieve fault-tolerance and high performance in production environments. Evaluations on real-life datasets and data analytics jobs show that the above optimizations of Vineyard can significantly improve the end-to-end performance of data analytics jobs, by reducing their data-sharing time up to 68.4x.
Steered Training Data Generation for Learned Semantic Type Detection
Authors: Langenecker Sven , Sturm Christoph , Schalles Christian Schalles , Binnig Carsten
Published: June 2023

In this paper, we introduce STEER to adapt learned semantic type extraction approaches to a new, unseen data lake. STEER provides a data programming framework for semantic labeling which is used to generate new labeled training data with minimal overhead. At its core, STEER comes with a novel training data generation procedure called Steered-Labeling that can generate high quality training data not only for non-numeric but also for numerical columns. With this generated training data STEER is able to fine-tune existing learned semantic type extraction models. We evaluate our approach on four different data lakes and show that we can significantly improve the performance of two different types of learned models across all data lakes.
When Automatic Filtering Comes to the Rescue: Pre-Computing Company Competitor Pairs in Owler
Authors: Guo Jinsong , Jami Aditya , Kröll Markus , Schweizer Lukas , Paramonov Sergey , Aichinger Eric , Sferrazza Stefano , Scaccia Mattia , Reissfelder Stéphane , Cicek Eda , Grasso Giovanni , Gottlob Georg
Published: June 2023

Competitor data constitutes information significantly valuable for many business applications. Meltwater provides users with access to a large Company Information System (CIS), Owler, which contains competitor pairs and other useful information about companies. Meltwater has been seeking a practical solution to discover more competitor pairs in Owler. The first attempt, a fully-manual workflow (called MW_Manual) for finding more competitor pairs in Owler consisted of two manual steps: a filtering step that excludes obvious non-competitor company pairs, and a further inspection process that inspects each left company pair after the filtering step. MW_Manual was cost prohibitive because the results of the filtering step contained too many non-competitor pairs. Inspecting such non-competitor pairs caused an overhead to the overall workload. To reduce the manual workload, especially the required human effort in the manual inspection process, Meltwater has transformed MW_Manual into a semi-automatic workflow (called MW_CPFilter) by replacing the manual filtering with an automatic yet more precise process that adopts a system called CPFilter. This paper presents CPFilter, a system used in the filtering process of MW_CPFilter. CPFilter automatically pre-computes likely competitor pairs from existing competitor pairs in Owler. CPFilter combines (i) the generation of new competitor candidate pairs by inference from existing competitors and other company-specific knowledge, with (ii) the validation of each candidate competitor pair of two companies by checking whether or not empirical evidence that indicates the competitor relationships of these two companies can be found. CPFilter has three key advantages compared with the manual filtering process and previous works: (i) it resulted in a high workload reduction rate of 0.81, (ii) it is domain-independent so that it can be applied to different sectors in Owler, and (iii) its results are explainable so that humans can easily understand its results.