Fast Parallel Hypertree Decompositions in Logarithmic Recursion Depth

Abstract

Modern trends in data collection are bringing current mainstream techniques for database query processing to their limits. Consequently, various novel approaches for efficient query processing are being actively studied. One such approach is based on hypertree decompositions (HDs), which have been shown to carry great potential to process complex queries more efficiently and with stronger theoretical guarantees. However, using HDs for query execution relies on the difficult task of computing decompositions of the query structure, which guides the efficient execution of the query. From theoretical results we know that the performance of purely sequential methods is inherently limited, yet the problem is susceptible to parallelisation. In this paper we propose the first algorithm for computing hypertree decompositions that is well-suited for parallelisation. The proposed algorithm log-k-decomp requires only a logarithmic number of recursion levels and additionally allows for highly parallelised pruning of the search space by restriction to balanced separators. We provide detailed experimental evaluation over the HyperBench benchmark and demonstrate that our approach is highly effective especially for complex queries.

References in corpus (22)

• Very Deep Convolutional Networks for Large-Scale Image Recognition
• Practical Bayesian Optimization of Machine Learning Algorithms
• Distributed Representations of Sentences and Documents
• BPR: Bayesian Personalized Ranking from Implicit Feedback
• Estimating Continuous Distributions in Bayesian Classifiers
• DailyDialog: A Manually Labelled Multi-turn Dialogue Dataset
• What do we need to build explainable AI systems for the medical domain?
• Representation Learning for Attributed Multiplex Heterogeneous Network
• Fairness Testing: Testing Software for Discrimination
• Tuning for Software Analytics: is it Really Necessary?
• Collaborative Filtering and the Missing at Random Assumption
• Calendar.help: Designing a Workflow-Based Scheduling Agent with Humans in the Loop
• A Comparative Study of Programming Languages in Rosetta Code
• Knowledge-Preserving Incremental Social Event Detection via Heterogeneous GNNs
• Significant Otter: Understanding the Role of Biosignals in Communication
• Where are we in embedding spaces? A Comprehensive Analysis on Network Embedding Approaches for Recommender Systems
• Active Collaborative Filtering
• Project IRL: Playful Co-Located Interactions with Mobile Augmented Reality
• OtherTube: Facilitating Content Discovery and Reflection by Exchanging YouTube Recommendations with Strangers
• Joint Item Recommendation and Attribute Inference: An Adaptive Graph Convolutional Network Approach
• Generalized Group Profiling for Content Customization
• Leveraging the Defects Life Cycle to Label Affected Versions and Defective Classes

Cited by in corpus (13)

• COCOA: Cross Modality Contrastive Learning for Sensor Data
• Metrics for Dataset Demographic Bias: A Case Study on Facial Expression Recognition
• Sketched Reality: Sketching Bi-Directional Interactions Between Virtual and Physical Worlds with AR and Actuated Tangible UI
• Modeling Motivational Interviewing Strategies On An Online Peer-to-Peer Counseling Platform
• HoloBots: Augmenting Holographic Telepresence with Mobile Robots for Tangible Remote Collaboration in Mixed Reality
• Deep Person Generation: A Survey from the Perspective of Face, Pose and Cloth Synthesis
• Project IRL: Playful Co-Located Interactions with Mobile Augmented Reality
• Benchmarking Frameworks and Comparative Studies of Controller Area Network (CAN) Intrusion Detection Systems: A Review
• How Scientists Use Large Language Models to Program
• A Tool for Organizing Key Characteristics of Virtual, Augmented, and Mixed Reality for Human-Robot Interaction Systems: Synthesizing VAM-HRI Trends and Takeaways
• A Survey on Parallelism and Determinism
• Meta-GCN: A Dynamically Weighted Loss Minimization Method for Dealing with the Data Imbalance in Graph Neural Networks
• Tackling Fake News in Bengali: Unraveling the Impact of Summarization vs. Augmentation on Pre-trained Language Models