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 (72)

• Adam: A Method for Stochastic Optimization
• Very Deep Convolutional Networks for Large-Scale Image Recognition
• XGBoost: A Scalable Tree Boosting System
• Efficient Estimation of Word Representations in Vector Space
• Neural Machine Translation by Jointly Learning to Align and Translate
• DeepWalk: Online Learning of Social Representations
• TensorFlow: A system for large-scale machine learning
• Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
• Practical Bayesian Optimization of Machine Learning Algorithms
• Distributed Representations of Sentences and Documents
• Generative Adversarial Networks: An Overview
• BPR: Bayesian Personalized Ranking from Implicit Feedback
• HuggingFace's Transformers: State-of-the-art Natural Language Processing
• Estimating Continuous Distributions in Bayesian Classifiers
• Axiomatic Attribution for Deep Networks
• Teaching Machines to Read and Comprehend
• Deep Speech 2: End-to-End Speech Recognition in English and Mandarin
• Deep Facial Expression Recognition: A Survey
• ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks
• Sketch-based Manga Retrieval using Manga109 Dataset
• Normalizing Flows: An Introduction and Review of Current Methods
• VisualBERT: A Simple and Performant Baseline for Vision and Language
• VL-BERT: Pre-training of Generic Visual-Linguistic Representations
• DailyDialog: A Manually Labelled Multi-turn Dialogue Dataset
• What do we need to build explainable AI systems for the medical domain?
• NAIS: Neural Attentive Item Similarity Model for Recommendation
• The What-If Tool: Interactive Probing of Machine Learning Models
• Representation Learning for Attributed Multiplex Heterogeneous Network
• The Measure and Mismeasure of Fairness
• Deep Reinforcement Learning for Page-wise Recommendations
• Fairness Testing: Testing Software for Discrimination
• How Generative Adversarial Networks and Their Variants Work: An Overview
• RetainVis: Visual Analytics with Interpretable and Interactive Recurrent Neural Networks on Electronic Medical Records
• BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer
• Tuning for Software Analytics: is it Really Necessary?
• Automated Directed Fairness Testing
• Collaborative Filtering and the Missing at Random Assumption
• Representation Learning by Rotating Your Faces
• Twitter Sentiment Analysis via Bi-sense Emoji Embedding and Attention-based LSTM
• FairSight: Visual Analytics for Fairness in Decision Making
• DialogWAE: Multimodal Response Generation with Conditional Wasserstein Auto-Encoder
• Calendar.help: Designing a Workflow-Based Scheduling Agent with Humans in the Loop
• Preference-based Search using Example-Critiquing with Suggestions
• A Comparative Study of Programming Languages in Rosetta Code
• Knowledge-Preserving Incremental Social Event Detection via Heterogeneous GNNs
• 'I Just Want to Hack Myself to Not Get Distracted': Evaluating Design Interventions for Self-Control on Facebook
• A Sentiment-and-Semantics-Based Approach for Emotion Detection in Textual Conversations
• Deep Reinforcement Learning based Recommendation with Explicit User-Item Interactions Modeling
• Significant Otter: Understanding the Role of Biosignals in Communication
• Generalizing semi-supervised generative adversarial networks to regression using feature contrasting
• Multilingual Sentiment Analysis: An RNN-Based Framework for Limited Data
• Predicting Demographics, Moral Foundations, and Human Values from Digital Behaviors
• Learning Piece-wise Linear Models from Large Scale Data for Ad Click Prediction
• Effective and Efficient Dropout for Deep Convolutional Neural Networks
• Variational Transformers for Diverse Response Generation
• Semi-supervised Adversarial Learning to Generate Photorealistic Face Images of New Identities from 3D Morphable Model
• The JDDC Corpus: A Large-Scale Multi-Turn Chinese Dialogue Dataset for E-commerce Customer Service
• 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
• Model Slicing for Supporting Complex Analytics with Elastic Inference Cost and Resource Constraints
• OtherTube: Facilitating Content Discovery and Reflection by Exchanging YouTube Recommendations with Strangers
• Ab-initio quantum transport simulation of self-heating in single-layer 2-D materials
• Towards AutoML in the presence of Drift: first results
• Rafiki: Machine Learning as an Analytics Service System
• Joint Item Recommendation and Attribute Inference: An Adaptive Graph Convolutional Network Approach
• Learning to Collaborate: Multi-Scenario Ranking via Multi-Agent Reinforcement Learning
• Optimizing Prediction Intervals by Tuning Random Forest via Meta-Validation
• Generalized Group Profiling for Content Customization
• Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication
• Learning to Create Better Ads: Generation and Ranking Approaches for Ad Creative Refinement
• 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