bluuebunny/crossref_metadata_2025 huggingface dataset:
T-Rex: Optimizing Pattern Search on Time Series
Authors: Huang Silu , Zhu Erkang , Chaudhuri Surajit , Spiegelberg Leonhard
Published: June 2023

Pattern search is an important class of queries for time series data. Time series patterns often match variable-length segments with a large search space, thereby posing a significant performance challenge. The existing pattern search systems, for example, SQL query engines supporting MATCH_RECOGNIZE, are ineffective in pruning the large search space of variable-length segments. In many cases, the issue is due to the use of a restrictive query language modeled on time series points and a computational model that limits search space pruning. We built T-ReX to address this problem using two main building blocks: first, a MATCH_RECOGNIZE language extension that exposes the notion of segment variable and adds new operators, lending itself to better optimization; second, an executor capable of pruning the search space of matches and minimizing total query time using an optimizer. We conducted experiments using 5 real-world datasets and 11 query templates, including those from existing works. T-ReX outperformed an optimized NFA-based pattern search executor by 6x in median query time and an optimized tree-based executor by 19X.
Design Guidelines for Correct, Efficient, and Scalable Synchronization using One-Sided RDMA
Authors: Ziegler Tobias , Nelson-Slivon Jacob , Leis Viktor , Binnig Carsten
Published: June 2023

Remote data structures built with one-sided Remote Direct Memory Access (RDMA) are at the heart of many disaggregated database management systems today. Concurrent access to these data structures by thousands of remote workers necessitates a highly efficient synchronization scheme. Remarkably, our investigation reveals that existing synchronization schemes display substantial variations in performance and scalability. Even worse, some schemes do not correctly synchronize, resulting in rare and hard-to-detect data corruption. Motivated by these observations, we conduct the first comprehensive analysis of one-sided synchronization techniques and provide general principles for correct synchronization using one-sided RDMA. Our research demonstrates that adherence to these principles not only guarantees correctness but also results in substantial performance enhancements.
Theories and Principles Matter: Towards Visually Appealing and Effective Abstraction of Property Graph Queries
Authors: Ma Jiebing , S Bhowmick Sourav , Choi Byron , Tay Lester
Published: June 2023

Existing visual abstraction of a property graph query by representing it as a labeled atomic graph (LAG) has great potential to democratize the usage of property graph databases as it enables user-friendly visual query formulation without demanding the need to learn a property graph query language e.g., Cypher. Unfortunately, existing LAG-based query interfaces do not embrace HCI principles and psychology theories to inform their design and as a result may have adverse impact on their usability and aesthetics. In this paper, we depart from the classical theory- and principles-oblivious LAG abstraction to present a novel theory-informed visual abstraction called labeled composite graph (LCG) to address this limitation. It realizes a novel and extensible visual shape definition language called VEDA to create and maintain an LCG systematically, guided by a variety of theories and principles from HCI, visualization and psychology. We build a novel LCG-based visual property graph query interface for Cypher called SIERRA and demonstrate through a user study its superiority to an industrial-strength LAG-based query interface for property graphs w.r.t. usability, aesthetics and efficient query formulation.
Efficient Star-based Truss Maintenance on Dynamic Graphs
Authors: Sun Zitan , Huang Xin , Liu Qing , Xu Jianliang
Published: June 2023

K-truss is a useful notion of dense subgraphs, which can represent cohesive parts of a graph in a hierarchical way. In practice, in order to enable various truss-based applications to answer queries faster, the edge trussnesses are computed in advance. However, real-world graphs may not always be static and often have edges inserted or removed, leading to costly truss maintenance of recomputing all edge trussnesses. In this paper, we focus on dynamic graphs with star insertions/deletions, where a star insertion can represent a newly joined user with friend connections in social networks or a recently published paper with cited references in citation networks. To tackle such star-based truss maintenance, we propose a new structure of AffBall based on the local structure of an inserted/deleted star motif. With AffBall, we make use of the correlation of inserted edges to compute the trussnesses of the inner edges surrounding the star. Then, we analyze the onion layer of k-truss and conduct truss maintenance for the edges beyond the star, which can be efficiently achieved with a time complexity related to the number of the edges that change the onion layer. Moreover, we extend star-based truss maintenance to handle general updates and single-edge insertions/deletions. Extensive experiments on real-world dynamic graphs verify the effectiveness and efficiency of proposed algorithms against state-of-the-art truss maintenance algorithms.
QaaD (Query-as-a-Data): Scalable Execution of Massive Number of Small Queries in Spark
Authors: Park Yeonsu , Tak Byungchul , Han Wook-Shin
Published: June 2023

Spark big data processing platform is heavily used in today's IT services for various critical applications such as machine learning tasks for service recommendations or massive volumes of raw sales data analysis. Spark is designed to deliver high performance by enabling a high degree of parallelism while processing various heavy-weight queries that require homogeneous operations on large data. However, it has been observed that workloads made of small and short-running queries coming from various sources are becoming dominant in practice. Unfortunately, the current Spark architecture is unfit to process workloads made of a large number of small queries optimally due to excessive I/Os with small computations. We present a technique, called QaaD, that addresses this problem fundamentally by applying i) transparent conversion of workloads made of small queries into one with large queries and ii) dynamic partition size adjustment for runtime overhead minimization. For this, we introduce a new abstraction, microRDD, to support our design of query merging, the embedding of queries as part of data, and an opportunistic sharing of common input data among queries. Comprehensive evaluation using real-world data shows that QaaD is able to deliver 10.6x to 36.6x speed-up against standard Spark executions for small query workloads.
Exploratory Training: When Annotators Learn About Data
Authors: Shrestha Rajesh , Habibelahian Omeed , Termehchy Arash , Papotti Paolo
Published: June 2023

Data systems often present examples and solicit labels from users to learn a target model, i.e., active learning. However, due to the complexity of the underlying data, users may not initially have a perfect understanding of the effective model and do not know the accurate labeling. For example, a user who is training a model for detecting noisy or abnormal values may not perfectly know the properties of typical and clean values in the data. Users may improve their knowledge about the data and target model as they observe examples during training. As users gradually learn about the data and model, they may revise their labeling strategies. Current systems assume that users always provide correct labeling with potentially a fixed and small chance of annotation mistakes. Nonetheless, if the trainer revises its belief during training, such mistakes become significant and non-stationarity. Hence, current systems consume incorrect labels and may learn inaccurate models. In this paper, we build theoretical underpinnings and design algorithms to develop systems that collaborate with users to learn the target model accurately and efficiently. At the core of our proposal, a game-theoretic framework models the joint learning of user and system to reach a desirable eventual stable state, where both user and system share the same belief about the target model. We extensively evaluate our system using user studies over various real-world datasets and show that our algorithms lead to accurate results with a smaller number of interactions compared to existing methods.
Predicate Pushdown for Data Science Pipelines
Authors: Yan Cong , Lin Yin , He Yeye
Published: June 2023

Predicate pushdown is a widely adopted query optimization. Existing systems and prior work mostly use pattern-matching rules to decide when a predicate can be pushed through certain operators like join or groupby. However, challenges arise in optimizing for data science pipelines due to the widely used non-relational operators and user-defined functions (UDF) that existing rules would fail to cover. In this paper, we present MagicPush, which decides predicate pushdown using a search-verification approach.MagicPush searches for candidate predicates on pipeline input, which is often not the same as the predicate to be pushed down, and verifies that the pushdown does not change pipeline output with full correctness guarantees. Our evaluation on TPC-H queries and 200 real-world pipelines sampled from GitHub Notebooks shows that MagicPush substantially outperforms a strong baseline that uses a union of rules from prior work - it is able to discover new pushdown opportunities and better optimize 42 real-world pipelines with up to 99% reduction in running time, while discovering all pushdown opportunities found by the existing baseline on remaining cases.
High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations
Authors: Gao Jianyang , Long Cheng
Published: June 2023

Approximate K nearest neighbor (AKNN) search in the high-dimensional Euclidean vector space is a fundamental and challenging problem. We observe that in high-dimensional space, the time consumption of nearly all AKNN algorithms is dominated by that of the distance comparison operations (DCOs). For each operation, it scans full dimensions of an object and thus, runs in linear time wrt the dimensionality. To speed it up, we propose a randomized algorithm named ADSampling which runs in logarithmic time wrt the dimensionality for the majority of DCOs and succeeds with high probability. In addition, based on ADSampling we develop one generic and two algorithm-specific techniques as plugins to enhance existing AKNN algorithms. Both theoretical and empirical studies confirm that: (1) our techniques introduce nearly no accuracy loss and (2) they consistently improve the efficiency.
Shortest Paths Discovery in Uncertain Networks via Transfer Learning
Authors: Huang Shixun , Bao Zhifeng
Published: June 2023

Due to various reasons such as noisy measurement and privacy preservation, a network/graph is often uncertain such that each edge in the network has a probability of existence. In this paper, we study finding the most probable shortest path which has the highest probability of being the shortest path between a given pair of nodes in an uncertain network. Despite significant progress being made, this problem still suffers from the efficiency and scalability issue. To solve this problem, the state-of-the-art adopts a two-phase approach where Phase 1 generates some candidate paths and Phase 2 estimates their probabilities of being the shortest path and returns the one with the highest probability as the solution. Notably, Phase 2 requires a large number of simulations over all edges in the network and can easily dominate the cost of the whole process. In this paper, we aim to resolve the efficiency and scalability issue by optimizing Phase 2. Specifically, we first propose a non-learning based fast approximation technique which significantly reduces the number of samples for the probability estimation in each simulation. Afterwards, we further propose a learning-based method which can directly estimate the probability of each candidate path without costly simulations. Extensive experiments show that (1) compared to the state-of-the-art, our fast approximation technique and learning-based method can achieve up to 5x and 210x speedups in Phase 2 respectively while maintaining highly competitive or even equivalent results, (2) the training process is highly scalable and (3) the prediction function can work effectively under the problem settings different from the one it was trained.
PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy
Authors: Cai Kuntai , Xiao Xiaokui , Cormode Graham
Published: June 2023

Answering database queries while preserving privacy is an important problem that has attracted considerable research attention in recent years. A canonical approach to this problem is to use synthetic data. That is, we replace the input database R with a synthetic database R* that preserves the characteristics of R, and use R* to answer queries. Existing solutions for relational data synthesis, however, either fail to provide strong privacy protection, or assume that R contains a single relation. In addition, it is challenging to extend the existing single-relation solutions to the case of multiple relations, because they are unable to model the complex correlations induced by the foreign keys. Therefore, multi-relational data synthesis with strong privacy guarantees is an open problem.

In this paper, we address the above open problem by proposing PrivLava, the first solution for synthesizing relational data with foreign keys under differential privacy, a rigorous privacy framework widely adopted in both academia and industry. The key idea of PrivLava is to model the data distribution in R using graphical models, with latent variables included to capture the inter-relational correlations caused by foreign keys. We show that PrivLava supports arbitrary foreign key references that form a directed acyclic graph, and is able to tackle the common case when R contains a mixture of public and private relations. Extensive experiments on census data sets and the TPC-H benchmark demonstrate that PrivLava significantly outperforms its competitors in terms of the accuracy of aggregate queries processed on the synthetic data.
Scalable and Efficient Full-Graph GNN Training for Large Graphs
Authors: Wan Xinchen , Xu Kaiqiang , Liao Xudong , Jin Yilun , Chen Kai , Jin Xin
Published: June 2023

Graph Neural Networks (GNNs) have emerged as powerful tools to capture structural information from graph-structured data, achieving state-of-the-art performance on applications such as recommendation, knowledge graph, and search. Graphs in these domains typically contain hundreds of millions of nodes and billions of edges. However, previous GNN systems demonstrate poor scalability because large and interleaved computation dependencies in GNN training cause significant overhead in current parallelization methods. We present G3, a distributed system that can efficiently train GNNs over billion-edge graphs at scale. G3 introduces GNN hybrid parallelism which synthesizes three dimensions of parallelism to scale out GNN training by sharing intermediate results peer-to-peer in fine granularity, eliminating layer-wise barriers for global collective communication or neighbor replications as seen in prior works. G3 leverages locality-aware iterative partitioning and multi-level pipeline scheduling to exploit acceleration opportunities by distributing balanced workload among workers and overlapping computation with communication in both inter-layer and intra-layer training processes. We show via a prototype implementation and comprehensive experiments that G3 can achieve as much as 2.24x speedup in a 16-node cluster, and better final accuracy over prior works.
OM3: An Ordered Multi-level Min-Max Representation for Interactive Progressive Visualization of Time Series
Authors: Wang Yunhai , Wang Yuchun , Chen Xin , Zhao Yue , Zhang Fan , Wu Eugene , Fu Chi-Wing , Yu Xiaohui
Published: June 2023

We present a novel multi-level representation of time series called OM3 that facilitates efficient interactive progressive visualization of large data stored in a database and supports various interactions such as resizing, panning, zooming, and visual query. Based on our proposed line-segment aggregation, this representation can produce error-free line visualizations that preserve the shape of a time series in windows of arbitrary sizes. To reduce the interaction latency, we develop an incremental tree-based query strategy to support progressive visualizations, allowing a finer control on the accuracy-time tradeoff. We quantitatively compare OM3 with state-of-the-art methods, including a method implemented on a leading time-series database InfluxDB, in two settings with databases residing either in the local area network or on the cloud. Results show that OM^3 maintains a low latency within 300~ms on the web browser and a high data reduction ratio regardless of the data size (ranging from millions to billions of records), achieving around 1,000 times faster than the state-of-the-art methods on the largest dataset experimented with.
Scapin: Scalable Graph Structure Perturbation by Augmented Influence Maximization
Authors: Wang Yexin , Yang Zhi , Liu Junqi , Zhang Wentao , Cui Bin
Published: June 2023

Generating data perturbations to graphs has become a useful tool for analyzing the robustness of Graph Neural Networks (GNNs). However, existing model-driven methodologies can be prohibitively expensive to apply in large graphs, which hinders the understanding of GNN robustness at scale. In this paper, we present Scapin, a data-driven methodology that opens up a new perspective by connecting graph structure perturbation for GNNs with augmented influence maximization-to either facilitate desirable spreads or curtail undesirable ones by adding or deleting a small set of edges. This connection not only allows us to perform data perturbation on GNNs with computation scalability but also provides nice interpretations. To transform such connections into efficient perturbation approaches for the new GNN setting, Scapin introduces a novel edge influence model, decomposed influence maximization objectives, and a principled algorithm for edge addition by exploiting submodularity of the objectives. Empirical studies demonstrate that Scapin can give orders of magnitude improvement over state-of-art methods in terms of runtime and memory efficiency, with comparable or even better performance.
Few-shot Text-to-SQL Translation using Structure and Content Prompt Learning
Authors: Gu Zihui , Fan Ju , Tang Nan , Cao Lei , Jia Bowen , Madden Sam , Du Xiaoyong
Published: June 2023

A common problem with adopting Text-to-SQL translation in database systems is poor generalization. Specifically, when there is limited training data on new datasets, existing few-shot Text-to-SQL techniques, even with carefully designed textual prompts on pre-trained language models (PLMs), tend to be ineffective. In this paper, we present a divide-and-conquer framework to better support few-shot Text-to-SQL translation, which divides Text-to-SQL translation into two stages (or sub-tasks), such that each sub-task is simpler to be tackled. The first stage, called the structure stage, steers a PLM to generate an SQL structure (including SQL commands such as SELECT, FROM, WHERE and SQL operators such as <", ?>") with placeholders for missing identifiers. The second stage, called the content stage, guides a PLM to populate the placeholders in the generated SQL structure with concrete values (including SQL identifies such as table names, column names, and constant values). We propose a hybrid prompt strategy that combines learnable vectors and fixed vectors (i.e., word embeddings of textual prompts), such that the hybrid prompt can learn contextual information to better guide PLMs for prediction in both stages. In addition, we design keyword constrained decoding to ensure the validity of generated SQL structures, and structure guided decoding to guarantee the model to fill correct content. Extensive experiments, by comparing with ten state-of-the-art Text-to-SQL solutions at the time of writing, show that SC-Prompt significantly outperforms them in the few-shot scenario. In particular, on the widely-adopted Spider dataset, given less than 500 labeled training examples (5% of the official training set), SC-Prompt outperforms the previous SOTA methods by around 5% on accuracy.
Exploiting Structure in Regular Expression Queries
Authors: Zhang Ling , Deep Shaleen , Floratou Avrilia , Gruenheid Anja , Patel Jignesh M. , Zhu Yiwen
Published: June 2023

Regular expression, or regex, is widely used to extract critical information from a large corpus of formatted text by finding patterns of interest. In tasks like log processing, the speed of regex matching is crucial. Data scientists and developers regularly use regex libraries that implement optimized regular expression matching using modern automata theory. However, computing state transitions in the underlying regex evaluation engine can be inefficient when a regex query contains a multitude of string literals. This inefficiency is further exasperated when analyzing large data volumes. This paper presents BLARE, Blazingly Fast Regular Expression, a regular expression matching framework that is inspired by the mechanisms that are used in database engines, which use a declarative framework to explore multiple equivalent execution plans, all of which produce the correct final result. Similarly, BLARE decomposes a regex into multiple regex and string components and then creates evaluation strategies in which the components can be evaluated in an order that is not strictly a left-to-right translation of the input regex query. Rather than using a cost-based optimization approach, BLARE uses an adaptive runtime strategy based on a multi-armed bandit approach to find an efficient execution plan. BLARE is also modular and can be built on top of any existing regex library. We implemented BLARE on four commonly used regex libraries, RE2, PCRE2, Boost Regex, and ICU Regex, and evaluated it using two production workloads and one open-source workload. BLARE was 1.6× to 3.7× faster than RE2 and 3.4× to 7.9× faster than Boost Regex. PCRE2 did not finish on one of the workloads, but on the remaining two workloads, BLARE improved the performance of PCRE2 by 3.1× to over 100×. For the open-source dataset, BLARE provided a speed up of 61.7× for ICU Regex. BLARE code is publicly available at https://github.com/mush-zhang/Blare.
Global and Local Differentially Private Release of Count-Weighted Graphs
Authors: Brito Felipe T. , Farias Victor A. E. , Flynn Cheryl , Majumdar Subhabrata , Machado Javam C. , Srivastava Divesh
Published: June 2023

Many complex natural and technological systems are commonly modeled as count-weighted graphs, where nodes represent entities, edges model relationships between them, and edge weights define some counting statistics associated with each relationship. As graph data usually contain sensitive information about entities, preserving privacy when releasing this type of data becomes an important issue. In this context, differential privacy (DP) has become the de facto standard for data release under strong privacy guarantees. When dealing with DP for weighted graphs, most state-of-the-art works assume that the graph topology is known. However, in several real-world applications, the privacy of the graph topology also needs to be ensured. In this paper, we aim to bridge the gap between DP and count-weighted graph data release, considering both graph structure and edge weights as private information. We first adapt the weighted graph DP definition to take into account the privacy of the graph structure. We then develop two novel approaches to privately releasing count-weighted graphs under the notions of global and local DP. We also leverage the post-processing property of DP to improve the accuracy of the proposed techniques considering graph domain constraints. Experiments using real-world graph data demonstrate the superiority of our approaches in terms of utility over existing techniques, enabling subsequent computation of a variety of statistics on the released graph with high utility, in some cases comparable to the non-private results.
QHL: A Fast Algorithm for Exact Constrained Shortest Path Search on Road Networks
Authors: Wang Libin , Wong Raymond Chi-Wing
Published: June 2023

Route planning is fundamental in our daily life. However, existing mapping applications focus on recommending routes by optimizing one single objective, which is inconsistent with some scenarios where users prefer the optimal route under a constraint. The constrained shortest path (CSP) query matches this requirement, but the query efficiencies of previous solutions are often low due to CSP's NP-hardness. In the era of big data, state-of-the-art indexes are getting larger to support faster query processing. Recent attempts to preprocess more intermediate results and reduce the number of table lookups have proved successful in solving the CSP. However, the best-known algorithm ignores some information in the CSP queries and tries to solve a more general problem before tackling the exact CSP. In this paper, we propose by far the fastest algorithm called QHL, which fully utilizes the pruning power of the CSP query information. Specifically, we preprocess our index by generating pruning conditions that can improve query efficiency. We also conducted extensive experiments on real-world datasets to demonstrate the superiority of our proposed algorithm. QHL could answer each CSP query in around 50 μs and run faster than the best-known algorithm by orders of magnitude.
GoodCore: Data-effective and Data-efficient Machine Learning through Coreset Selection over Incomplete Data
Authors: Chai Chengliang , Liu Jiabin , Tang Nan , Fan Ju , Miao Dongjing , Wang Jiayi , Luo Yuyu , Li Guoliang
Published: June 2023

Given a dataset with incomplete data (e.g., missing values), training a machine learning model over the incomplete data requires two steps. First, it requires a data-effective step that cleans the data in order to improve the data quality (and the model quality on the cleaned data). Second, it requires a data-efficient step that selects a core subset of the data (called coreset) such that the trained models on the entire data and the coreset have similar model quality, in order to improve the training efficiency. The first-data-effective-then-data-efficient methods are too costly, because they are expensive to clean the whole data; while the first-data-efficient-then-data-effective methods have low model quality, because they cannot select high-quality coreset for incomplete data.

In this paper, we investigate the problem of coreset selection over incomplete data for data-effective and data-efficient machine learning. The essential challenge is how to model the incomplete data for selecting high-quality coreset. To this end, we propose the GoodCore framework towards selecting a good coreset over incomplete data with low cost. To model the unknown complete data, we utilize the combinations of possible repairs as possible worlds of the incomplete data. Based on possible worlds, GoodCore selects an expected optimal coreset through gradient approximation without training ML models. We formally define the expected optimal coreset selection problem, prove its NP-hardness, and propose a greedy algorithm with an approximation ratio. To make GoodCore more efficient, we further propose optimization methods that incorporate human-in-the-loop imputation or automatic imputation method into our framework. Experimental results show the effectiveness and efficiency of our framework with low cost.
Data Stream Clustering: An In-depth Empirical Study
Authors: Wang Xin , Wang Zhengru , Wu Zhenyu , Zhang Shuhao , Shi Xuanhua , Lu Li
Published: June 2023

Data Stream Clustering (DSC) plays an important role in mining continuous and unlabeled data streams in real-world applications. Over the last decades, numerous DSC algorithms have been proposed with promising clustering accuracy and efficiency. Despite the significant differences among existing DSC algorithms, they are commonly built around four key design aspects: summarizing data structure, window model, outlier detection mechanism, and offline refinement strategy. However, there is a lack of empirical studies on these key design aspects in the same codebase using real-world workloads with distinct characteristics. As a result, it is difficult for researchers to improve upon the state-of-the-art. In this paper, we conduct such a study of DSC on its four key design aspects. We implemented state-of-the-art variants of all of these design choices in an open-sourced platform from scratch and evaluated them using both real-world and synthetic workloads. Our analysis identifies the fundamental issues and trade-offs of each design choice in terms of both accuracy and efficiency. We even find that combining flexible design choices led to the development of a new algorithm called Benne, which can be tuned to achieve either better accuracy or better efficiency compared to the state-of-the-art.
EARLY: Efficient and Reliable Graph Neural Network for Dynamic Graphs
Authors: Li Haoyang , Chen Lei
Published: June 2023

Graph neural networks have been widely used to learn node representations for many real-world static graphs. In general, they learn node representations by recursively aggregating information from neighbors. However, graphs in many applications are dynamic, evolving with continuous graph events, such as node feature and graph structure updates. These events require the node representations to be updated accordingly. Currently, due to the real-time requirement, how to efficiently and reliably update node representations under continuous graph events is still an open problem. Recent studies propose two solutions to partially address this problem, but their performance is still limited. First, local-based GNNs only update the nodes directly involved in events, suffering from the quality-deficit issue, since they neglect the other nodes affected by these events. Second, neighbor-sampling GNNs propose to sample neighbors to accelerate neighbor aggregation computations, encountering the neighbor-redundant issue. These sampled neighbors may be similar and cannot reflect the distribution of all neighbors, leading that node representations aggregated on these redundant neighbors may differ from those aggregated on all neighbors. In this paper, we propose an efficient and reliable graph neural network, namely EARLY, to update node representations for dynamic graphs. We first identify the top-k influential nodes that are most affected by graph events. Then, to sample neighbors diversely, we propose a diversity-aware layer-wise sampling technique. We theoretically demonstrate that this technique can decrease the sampling expectation error and learn more reliable node representations. Therefore, the top-k nodes selection and diversity-aware sampling enable EARLY to efficiently update node representations in a reliable way. Extensive experiments on the five real-world graphs demonstrate the effectiveness and efficiency of our proposed EARLY.
FEC: Efficient Deep Recommendation Model Training with Flexible Embedding Communication
Authors: Ma Kaihao , Yan Xiao , Cai Zhenkun , Huang Yuzhen , Wu Yidi , Cheng James
Published: June 2023

Embedding-based deep recommendation models (EDRMs), which contain small dense models and large embedding tables, are widely used in industry. Embedding communication constitutes the main cost for the distributed training of EDRMs, and thus we propose two strategies to improve its efficiency, i.e.,embedding tiering andpre-fetching. In particular, embedding tiering uses AllReduce to communicate popular embeddings that are accessed frequently. This is counter-intuitive as embeddings belong to the sparse embedding tables, but reasonable because the access pattern of popular embeddings resembles dense models. Pre-fetching starts communication early for embeddings that receive no updates such that they are removed from the critical path of training. We implement embedding tiering and pre-fetching in a system called FEC and compare it with the state-of-the-art systems on real datasets. The results show that FEC consistently outperforms the existing methods on all datasets, and its speed can be up to 6.65x and 2.42x in terms of embedding communication time and training throughput compared with the best performing baseline.
On Querying Connected Components in Large Temporal Graphs
Authors: Xie Haoxuan , Fang Yixiang , Xia Yuyang , Luo Wensheng , Ma Chenhao
Published: June 2023

In this paper, for the first time, we introduce the concepts of window-CCs and window-SCCs on undirected and directed temporal graphs, respectively. We then study the queries of window-CC and window-SCC by developing several efficient index-based query solutions. The space costs of the best indices are linear to the sizes of the temporal graphs. The extensive experimental evaluation on 12 real-world datasets demonstrates the high efficiency and effectiveness of the proposed solutions. In the future, we will develop distributed index construction algorithms, which would be useful for very large temporal graphs containing billions of edges. In the future, we will implement our algorithms by using a distributed computing platform (e.g., Pregel), which would be very useful when the temporal graph is too large to be kept by a single machine.
LightTS: Lightweight Time Series Classification with Adaptive Ensemble Distillation
Authors: Campos David , Zhang Miao , Yang Bin , Kieu Tung , Guo Chenjuan , Jensen Christian S.
Published: June 2023

Due to the sweeping digitalization of processes, increasingly vast amounts of time series data are being produced. Accurate classification of such time series facilitates decision making in multiple domains. State-of-the-art classification accuracy is often achieved by ensemble learning where results are synthesized from multiple base models. This characteristic implies that ensemble learning needs substantial computing resources, preventing their use in resource-limited environments, such as in edge devices. To extend the applicability of ensemble learning, we propose the LightTS framework that compresses large ensembles into lightweight models while ensuring competitive accuracy. First, we propose adaptive ensemble distillation that assigns adaptive weights to different base models such that their varying classification capabilities contribute purposefully to the training of the lightweight model. Second, we propose means of identifying Pareto optimal settings w.r.t. model accuracy and model size, thus enabling users with a space budget to select the most accurate lightweight model. We report on experiments using 128 real-world time series sets and different types of base models that justify key decisions in the design of LightTS and provide evidence that LightTS is able to outperform competitors.
Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams
Authors: Fang Ziquan , Gong Shenghao , Chen Lu , Xu Jiachen , Gao Yunjun , Jensen Christian S.
Published: June 2023

Trajectory similarity queries, including similarity search and similarity join, offer a foundation for many geo-spatial applications. With the rapid increase of streaming trajectory data volumes, e.g., data from mobile phones, vessel monitoring, or traffic systems, many location-based services benefit from online similarity analytics over trajectory data streams, where moving objects continually emit real-time position data. However, most existing studies focus on offline settings, and thus several major challenges remain unanswered in an online setting. To this end, we describe Ghost, a distributed stream processing framework that enables generic, efficient, and scalable online trajectory similarity search and join.

We propose a novel incremental online similarity computation (IOSC) mechanism to accelerate pair-wise streaming trajectory distance calculation, which supports a broad range of trajectory distance metrics. Compared with previous studies, IOSC reduces the complexity from quadratic to linear in terms of trajectory length. Building on this foundation, we propose histogram-based algorithms that exploit histogram indexes and a series of pruning bounds to enable streaming trajectory similarity search and join. Finally, we extend our methods to the distributed platform Flink for scalability, where a CostPartitioner is developed to ensure parallel processing and workload balancing. An experimental study using two real-life and one synthetic datasets shows that Ghost (i) acquires 6-20× efficiency/throughput gains and one order of magnitude memory overhead savings over state-of-the-art baselines, (ii) achieves 3--8× workload balancing gains on Flink, and (iii) exhibits low parameter sensitivity and high robustness.
LAQy: Efficient and Reusable Query Approximations via Lazy Sampling
Authors: Sanca Viktor , Chrysogelos Periklis , Ailamaki Anastasia
Published: June 2023

Modern analytical engines rely on Approximate Query Processing (AQP) to provide faster response times than the hardware allows for exact query answering. However, existing AQP methods impose steep performance penalties as workload unpredictability increases. Specifically, offline AQP relies on predictable workloads to create samples that match the queries in a priori to query execution, reducing query response times when queries match the expected workload. As soon as workload predictability diminishes, existing online AQP methods create query-specific samples with little reuse across queries, producing significantly smaller gains in response times. As a result, existing approaches cannot fully exploit the benefits of sampling under increased unpredictability.

We analyze sample creation and propose LAQy, a framework for building, expanding, and merging samples to adapt to the changes in workload predicates. We show the main parameters that affect the sample creation time and propose lazy sampling to overcome the unpredictability issues that cause fast-but-specialized samples to be query-specific. We evaluate LAQy by implementing it in an in-memory code-generation-based scale-up analytical engine to show the adaptivity and practicality of our framework in a modern system. LAQy speeds up online sampling processing as a function of sample reuse ranging from practically zero to full online sampling time and from 2.5x to 19.3x in a simulated exploratory workload.
Mitigating Filter Bubbles Under a Competitive Diffusion Model
Authors: Banerjee Prithu , Chen Wei , Lakshmanan Laks V.S.
Published: June 2023

While social networks greatly facilitate information dissemination, they are well known to have contributed to the phenomena of filter bubbles and echo chambers. This in turn can lead to societal polarization and erosion of trust in public institutions. Mitigating filter bubbles is an urgent open problem. Recently, approaches based on the influence maximization paradigm have been proposed in our community for mitigating filter bubbles by balancing exposure to opposing viewpoints. However, existing works ignore the inherent competition between the adoption of opposing viewpoints by users.

In this paper, we propose a realistic model for the filter bubble problem, which unlike previous work, captures thecompetition between opposing opinions propagating in a network as well as thecomplementary nature of the reward forexposing users to both those opinions. We formulate an optimization problem for mitigating filter bubbles under our model. We establish several evidences of the intrinsic difficulty in developing constant approximation to the problem and develop a heuristic and two instance-dependent approximation algorithms. Our experiments over 4 real datasets show that our heuristic far outperforms two state-of-the-art baselines as well as other algorithms in both efficiency and mitigating filter bubbles. We also empirically demonstrate that our best heuristic performs close to the optimal objective, which is obtained by utilizing the theoretical bounds of our approximation algorithms.
Maestro: Automatic Generation of Comprehensive Benchmarks for Question Answering Over Knowledge Graphs
Authors: Orogat Abdelghny , El-Roby Ahmed
Published: June 2023

Recently, there has been an upsurge in the number of knowledge graphs (KG) that can only be accessed by experts. Non-expert users lack an adequate understanding of the queried knowledge graph's vocabulary and structure, as well as the syntax of the structured query language used to express the user's information needs. To increase the user base of these KGs, a set of Question Answering (QA) systems that use natural language to query these knowledge graphs have been introduced. However, finding a benchmark that accurately evaluates the quality of a QA system is a difficult task due to (1) the high degree of variation in the fine-grained properties among the existing benchmarks, (2) the static nature of the existing benchmarks versus the evolving nature of KGs, and (3) the limited number of KGs targeted by existing benchmarks, which hinders the usability of QA systems in real-world deployment over KGs that are different from those that were used in the evaluation of the QA systems. In this paper, we introduce Maestro, a benchmark generation system for question answering over knowledge graphs. Maestro can generate a new benchmark for any KG given the KG and, optionally, a text corpus that covers this KG. The benchmark generated by Maestro is guaranteed to cover all the properties of the natural language questions and queries that were encountered in the literature as long as the targeted KG includes these properties. Maestro also generates high-quality natural language questions with various utterances that are on par with manually-generated ones to better evaluate QA systems.
Efficient GPU-Accelerated Subgraph Matching
Authors: Sun Xibo , Luo Qiong
Published: June 2023

Subgraph matching is a basic operation in graph analytics, finding all occurrences of a query graph Q in a data graph G. A common approach is to first filter out non-candidate vertices in G, and then order the vertices in Q to enumerate results. Recent work has started to utilize the GPU to accelerate subgraph matching. However, the effectiveness of current GPU-based filtering and ordering methods is limited, and the result enumeration often runs out of memory quickly. To address these problems, we propose EGSM, an efficient approach to GPU-based subgraph matching. Specifically, we design a data structure Cuckoo trie to support dynamic maintenance of candidates for filtering, and order query vertices based on estimated numbers of candidate vertices on the fly. Furthermore, we perform a hybrid breadth-first and depth-first search with memory management for result enumeration. Consequently, EGSM significantly outperforms the state-of-the-art GPU-accelerated algorithms, including GSI and CuTS.
Efficient Query Re-optimization with Judicious Subquery Selections
Authors: Zhao Junyi , Zhang Huanchen , Gao Yihan
Published: June 2023

Query re-optimization is an adaptive query processing technique that re-invokes the optimizer at certain points in query execution. The goal is to dynamically correct the cardinality estimation errors using the statistics collected at runtime to adjust the query plan to improve the overall performance. We identify a key weakness in existing re-optimization algorithms: their subquery division and re-optimization trigger strategies rely heavily on the optimizer's initial plan, which can be far away from optimal. We, therefore, propose QuerySplit, a novel re-optimization algorithm that skips the potentially misleading global plan and instead generates subqueries directly from the logical plan as the basic re-optimization units. By developing a cost function that prioritizes the execution of less "damaging" subqueries, QuerySplit successfully postpones (sometimes avoids) the execution of complex large joins to maximize their probability of having smaller input sizes. We implemented QuerySplit in PostgreSQL and compared our solution against four state-of-the-art re-optimization algorithms using the Join Order Benchmark. Our experiments show that QuerySplit reduces the benchmark execution time by 35% compared to the second-best alternative. The performance gap between QuerySplit and an optimal optimizer is within 4%.
GeaFlow: A Graph Extended and Accelerated Dataflow System
Authors: Pan Zhenxuan , Wu Tao , Zhao Qingwen , Zhou Qiang , Peng Zhiwei , Li Jiefeng , Zhang Qi , Feng Guanyu , Zhu Xiaowei
Published: June 2023

GeaFlow is a distributed dataflow system optimized for streaming graph processing, and has been widely adopted at Ant Group, serving various scenarios ranging from risk control of financial activities to analytics on social networks and knowledge graphs. It is built on top of a base with full-fledged stateful stream processing capabilities, extended with a series of graph-aware optimizations to address the space explosion and programming complexity issues of conventional join-based approaches. We propose new state backends and streaming operators that facilitate processing on dynamic graph-structured datasets, reducing space consumed by states. We develop a hybrid domain-specific language that embeds Gremlin into SQL, supporting both table and graph abstractions over streaming data. In addition to streaming workloads, GeaFlow is also extensively used for some batch processing jobs. In the largest deployments to date, GeaFlow is able to process tens of millions of events per second and manage hundreds of terabytes of states.
Disaggregating RocksDB: A Production Experience
Authors: Dong Siying , P Shiva Shankar , Pan Satadru , Ananthabhotla Anand , Ekambaram Dhanabal , Sharma Abhinav , Dayal Shobhit , Parikh Nishant Vinaybhai , Jin Yanqin , Kim Albert , Patil Sushil , Zhuang Jay , Dunster Sam , Mahajan Akanksha , Chelluri Anirudh , Datye Chaitanya , Santana Lucas Vasconcelos , Garg Nitin , Gawde Omkar
Published: June 2023

As in the general industry, there is a trend in Meta's data centers to migrate data from locally attached SSDs to cloud storage. We extended RocksDB [26], a widely used open-source storage engine designed and built for local SSDs, to leverage disaggregated storage. RocksDB's design, such as its data and log files' access patterns, makes an append-only distributed file system a desirable underlying storage. At Meta, we built disaggregated RocksDB using Tectonic File System [35], which so far had mainly been used for our data warehouse and blob storage stacks. We identified that metadata overhead and tail latencies were Tectonic's major performance gaps and addressed them accordingly. We improved the reliability, performance and other requirements with both general and customized optimizations to the core engine in RocksDB. We also took the time to deeply understand the common challenges presented by applications running on RocksDB and implemented enhancements to address them. This architecture enabled RocksDB to adapt to a more distributed architecture for performance enhancements.