Tradeoffs in Processing Queries and Supporting Updates over an ML-Enhanced R-tree

• URL: http://arxiv.org/abs/2502.09937v1
• Date: Fri, 14 Feb 2025 06:16:26 GMT
• Title: Tradeoffs in Processing Queries and Supporting Updates over an ML-Enhanced R-tree
• Authors: Abdullah Al-Mamun, Ch. Md. Rakin Haider, Jianguo Wang, Walid G. Aref,
• Abstract summary: This paper focuses on the R-tree multi-dimensional index structure as it is widely used for indexing multi-dimensional data.<n>The R-tree has been augmented with machine learning models to enhance the R-tree performance.<n>The AI+R-tree is an ML-enhanced R-tree index structure that augments a traditional disk-based R-tree with an ML model to enhance the R-tree's query processing performance.
• Score: 5.13844201935498
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Machine Learning (ML) techniques have been successfully applied to design various learned database index structures for both the one- and multi-dimensional spaces. Particularly, a class of traditional multi-dimensional indexes has been augmented with ML models to design ML-enhanced variants of their traditional counterparts. This paper focuses on the R-tree multi-dimensional index structure as it is widely used for indexing multi-dimensional data. The R-tree has been augmented with machine learning models to enhance the R-tree performance. The AI+R-tree is an ML-enhanced R-tree index structure that augments a traditional disk-based R-tree with an ML model to enhance the R-tree's query processing performance, mainly, to avoid navigating the overlapping branches of the R-tree that do not yield query results, e.g., in the presence of high-overlap among the rectangles of the R-tree nodes. We investigate the empirical tradeoffs in processing dynamic query workloads and in supporting updates over the AI+R-tree. Particularly, we investigate the impact of the choice of ML models over the AI+R-tree query processing performance. Moreover, we present a case study of designing a custom loss function for a neural network model tailored to the query processing requirements of the AI+R-tree. Furthermore, we present the design tradeoffs for adopting various strategies for supporting dynamic inserts, updates, and deletes with the vision of realizing a mutable AI+R-tree. Experiments on real datasets demonstrate that the AI+R-tree can enhance the query processing performance of a traditional R-tree for high-overlap range queries by up to 5.4X while achieving up to 99% average query recall.

Related papers

• TreeHop: Generate and Filter Next Query Embeddings Efficiently for Multi-hop Question Answering [27.37434534716611]
  TreeHop is an embedding-level framework for multi-hop question answering. TreeHop dynamically updates query embeddings by fusing semantic information from prior queries. TreeHop is a faster and more cost-effective solution for deployment in a range of knowledge-intensive applications.
  arXiv  Detail & Related papers  (2025-04-28T01:56:31Z)
• Reinforced Model Merging [53.84354455400038]
  We present an innovative framework termed Reinforced Model Merging (RMM), which encompasses an environment and agent tailored for merging tasks. By utilizing data subsets during the evaluation process, we addressed the bottleneck in the reward feedback phase, thereby accelerating RMM by up to 100 times.
  arXiv  Detail & Related papers  (2025-03-27T08:52:41Z)
• RASD: Retrieval-Augmented Speculative Decoding [5.3926068062773895]
  Speculative decoding accelerates inference in large language models (LLMs) This paper proposes RASD (Retrieval-Augmented Speculative Decoding), which adopts retrieval methods to enhance model-based speculative decoding.
  arXiv  Detail & Related papers  (2025-03-05T12:10:14Z)
• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  We propose a tree-based method for organizing and representing reference documents at various granular levels.<n>Our method, called ReTreever, jointly learns a routing function per internal node of a binary tree such that query and reference documents are assigned to similar tree branches.<n>Our evaluations show that ReTreever generally preserves full representation accuracy.
  arXiv  Detail & Related papers  (2025-02-11T21:35:13Z)
• Autoregressive Generation of Static and Growing Trees [49.93294993975928]
  We propose a transformer architecture and training strategy for tree generation.<n>The architecture processes data at multiple resolutions and has an hourglass shape, with middle layers processing fewer tokens than outer layers.<n>We extend this approach to perform image-to-tree and point-cloud-to-tree conditional generation and to simulate the tree growth processes, generating 4D trees.
  arXiv  Detail & Related papers  (2025-02-07T08:51:14Z)
• Optimized Feature Generation for Tabular Data via LLMs with Decision Tree Reasoning [53.241569810013836]
  We propose a novel framework that utilizes large language models (LLMs) to identify effective feature generation rules. We use decision trees to convey this reasoning information, as they can be easily represented in natural language. OCTree consistently enhances the performance of various prediction models across diverse benchmarks.
  arXiv  Detail & Related papers  (2024-06-12T08:31:34Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  In this paper we offer a new perspective on the well established agglomerative clustering algorithm, focusing on recovery of hierarchical structure. We recommend a simple variant of the standard algorithm, in which clusters are merged by maximum average dot product and not, for example, by minimum distance or within-cluster variance. We demonstrate that the tree output by this algorithm provides a bona fide estimate of generative hierarchical structure in data, under a generic probabilistic graphical model.
  arXiv  Detail & Related papers  (2023-05-24T11:05:12Z)
• Constructing Tree-based Index for Efficient and Effective Dense Retrieval [26.706985694158384]
  JTR stands for Joint optimization of TRee-based index and query encoding. We design a new unified contrastive learning loss to train tree-based index and query encoder in an end-to-end manner. Experimental results show that JTR achieves better retrieval performance while retaining high system efficiency.
  arXiv  Detail & Related papers  (2023-04-24T09:25:39Z)
• SETAR-Tree: A Novel and Accurate Tree Algorithm for Global Time Series Forecasting [7.206754802573034]
  In this paper, we explore the close connections between TAR models and regression trees. We introduce a new forecasting-specific tree algorithm that trains global Pooled Regression (PR) models in the leaves. In our evaluation, the proposed tree and forest models are able to achieve significantly higher accuracy than a set of state-of-the-art tree-based algorithms.
  arXiv  Detail & Related papers  (2022-11-16T04:30:42Z)
• The "AI+R"-tree: An Instance-optimized R-tree [8.645596995409647]
  This paper investigates to leverage Machine Learning techniques to enhance the performance of spatial indexes. We introduce a new AI-tree that transforms the search operation of an R-tree into a multi-label classification task. Experiments on real datasets demonstrate that the "AI+R"-tree can enhance the query performance over a traditional R-tree by up to 500%.
  arXiv  Detail & Related papers  (2022-07-01T17:08:17Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data [33.26284196513858]
  Learned indices have been proposed to replace classic index structures like B-Tree with machine learning (ML) models. We propose a fundamentally different way of using ML techniques to improve on the query performance of the classic R-Tree without the need of changing its structure or query processing algorithms.
  arXiv  Detail & Related papers  (2021-03-08T04:29:58Z)
• FREEtree: A Tree-based Approach for High Dimensional Longitudinal Data With Correlated Features [2.00191482700544]
  FREEtree is a tree-based method for high dimensional longitudinal data with correlated features. It exploits the network structure of the features by first clustering them using weighted correlation network analysis. It then conducts a screening step within each cluster of features and a selection step among the surviving features.
  arXiv  Detail & Related papers  (2020-06-17T07:28:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.