Qd-tree: Learning Data Layouts for Big Data Analytics

• URL: http://arxiv.org/abs/2004.10898v1
• Date: Wed, 22 Apr 2020 23:42:59 GMT
• Title: Qd-tree: Learning Data Layouts for Big Data Analytics
• Abstract summary: We propose a new framework called a query-data routing tree, or qd-tree, to address this problem. Experiments show that a qd-tree can provide physical speedups of more than an order of magnitude compared to current blocking schemes.
• Score: 33.07610112749939
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Corporations today collect data at an unprecedented and accelerating scale, making the need to run queries on large datasets increasingly important. Technologies such as columnar block-based data organization and compression have become standard practice in most commercial database systems. However, the problem of best assigning records to data blocks on storage is still open. For example, today's systems usually partition data by arrival time into row groups, or range/hash partition the data based on selected fields. For a given workload, however, such techniques are unable to optimize for the important metric of the number of blocks accessed by a query. This metric directly relates to the I/O cost, and therefore performance, of most analytical queries. Further, they are unable to exploit additional available storage to drive this metric down further. In this paper, we propose a new framework called a query-data routing tree, or qd-tree, to address this problem, and propose two algorithms for their construction based on greedy and deep reinforcement learning techniques. Experiments over benchmark and real workloads show that a qd-tree can provide physical speedups of more than an order of magnitude compared to current blocking schemes, and can reach within 2X of the lower bound for data skipping based on selectivity, while providing complete semantic descriptions of created blocks.

Related papers

• SafeLoad: Efficient Admission Control Framework for Identifying Memory-Overloading Queries in Cloud Data Warehouses [59.68732483257323]
  Memory overload is a common form of resource exhaustion in cloud data warehouses.<n>We propose SafeLoad, the first query admission control framework specifically designed to identify memory-overloading (MO) queries.<n>We show that SafeLoad achieves state-of-the-art prediction performance with low online and offline time overhead.
  arXiv  Detail & Related papers  (2026-01-05T08:29:51Z)
• Hierarchical Token Prepending: Enhancing Information Flow in Decoder-based LLM Embeddings [52.49524240846879]
  We propose Hierarchical Token Prepending to mitigate attention-level compression and readout-level over-squashing.<n>HTP partitions the input into blocks and prepends block-level summary tokens to subsequent blocks, creating pathways for backward information flow.<n>As a simple, architecture-agnostic method, HTP enhances both zero-shot and finetuned models, offering a scalable route to superior long-document embeddings.
  arXiv  Detail & Related papers  (2025-11-18T19:37:40Z)
• Linked Array Tree: A Constant-Time Search Structure for Big Data [0.0]
  Linked Array Tree (LAT) is a novel data structure designed to achieve constant-time complexity for search, insertion, and deletion operations. LAT's low memory overhead and avoidance of pointer-heavy structures make it well-suited for large-scale and intensive workloads.
  arXiv  Detail & Related papers  (2025-04-01T14:15:55Z)
• Differentially Private Learned Indexes [4.290415158471898]
  We address the problem of efficiently answering predicate queries on encrypted databases, those secured by Trusted Execution Environments (TEEs) A common strategy in modern databases to accelerate predicate queries is the use of indexes, which map attribute values (keys) to their corresponding positions in a sorted data array. Unfortunately, indexes cannot be directly applied to encrypted databases due to strong data dependent leakages. We propose leveraging learned indexes, a trending technique that repurposes machine learning models as indexing structures, to build more compact DP indexes.
  arXiv  Detail & Related papers  (2024-10-28T16:04:58Z)
• Data Aggregation for Hierarchical Clustering [0.3626013617212666]
  BETULA is a numerically stable version of the well known BIRCH data aggregation algorithm. It can be used to make HAC viable on systems with constrained resources with only small losses on clustering quality.
  arXiv  Detail & Related papers  (2023-09-05T19:39:43Z)
• LargeST: A Benchmark Dataset for Large-Scale Traffic Forecasting [65.71129509623587]
  Road traffic forecasting plays a critical role in smart city initiatives and has experienced significant advancements thanks to the power of deep learning. However, the promising results achieved on current public datasets may not be applicable to practical scenarios. We introduce the LargeST benchmark dataset, which includes a total of 8,600 sensors in California with a 5-year time coverage.
  arXiv  Detail & Related papers  (2023-06-14T05:48:36Z)
• WISK: A Workload-aware Learned Index for Spatial Keyword Queries [46.96314606580924]
  We propose WISK, a learned index for spatial keyword queries. We show that WISK achieves up to 8x speedup in querying time with comparable storage overhead.
  arXiv  Detail & Related papers  (2023-02-28T03:45:25Z)
• Fast Online Hashing with Multi-Label Projection [15.85793225585693]
  We propose a novel Fast Online Hashing (FOH) method which only updates the binary codes of a small part of the database. The experimental results show that the proposed FOH can achieve dramatic superiority on query time up to 6.28 seconds less than state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-12-03T03:19:28Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  Autoregressive language models are emerging as the de-facto standard for generating answers. Previous work has explored ways to partition the search space into hierarchical structures. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers.
  arXiv  Detail & Related papers  (2022-04-22T10:45:01Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes. Machine learning models are developed to approximate the position of each data record on the disk. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes.
  arXiv  Detail & Related papers  (2022-04-21T11:24:55Z)
• The Case for Learned Spatial Indexes [62.88514422115702]
  We use techniques proposed from a state-of-the art learned multi-dimensional index structure (namely, Flood) to answer spatial range queries. We show that (i) machine learned search within a partition is faster by 11.79% to 39.51% than binary search when using filtering on one dimension. We also refine using machine learned indexes is 1.23x to 1.83x times faster than closest competitor which filters on two dimensions.
  arXiv  Detail & Related papers  (2020-08-24T12:09:55Z)
• DA-NAS: Data Adapted Pruning for Efficient Neural Architecture Search [76.9225014200746]
  Efficient search is a core issue in Neural Architecture Search (NAS) We present DA-NAS that can directly search the architecture for large-scale target tasks while allowing a large candidate set in a more efficient manner. It is 2x faster than previous methods while the accuracy is currently state-of-the-art, at 76.2% under small FLOPs constraint.
  arXiv  Detail & Related papers  (2020-03-27T17:55:21Z)

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.