Learning-Augmented Search Data Structures

• URL: http://arxiv.org/abs/2402.10457v2
• Date: Fri, 07 Mar 2025 16:10:36 GMT
• Title: Learning-Augmented Search Data Structures
• Abstract summary: We study the integration of machine learning advice to improve upon traditional data structure designed for efficient search queries.<n>We construct skip lists and KD trees that provably provides the optimal expected search time, within nearly a factor of two.<n>In fact, our learning-augmented skip lists and KD trees are still optimal up to a constant factor, even if the oracle is only accurate within a constant factor.
• Score: 14.015114340879544
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the integration of machine learning advice to improve upon traditional data structure designed for efficient search queries. Although there has been recent effort in improving the performance of binary search trees using machine learning advice, e.g., Lin et. al. (ICML 2022), the resulting constructions nevertheless suffer from inherent weaknesses of binary search trees, such as complexity of maintaining balance across multiple updates and the inability to handle partially-ordered or high-dimensional datasets. For these reasons, we focus on skip lists and KD trees in this work. Given access to a possibly erroneous oracle that outputs estimated fractional frequencies for search queries on a set of items, we construct skip lists and KD trees that provably provides the optimal expected search time, within nearly a factor of two. In fact, our learning-augmented skip lists and KD trees are still optimal up to a constant factor, even if the oracle is only accurate within a constant factor. We also demonstrate robustness by showing that our data structures achieves an expected search time that is within a constant factor of an oblivious skip list/KD tree construction even when the predictions are arbitrarily incorrect. Finally, we empirically show that our learning-augmented search data structures outperforms their corresponding traditional analogs on both synthetic and real-world datasets.

Related papers

• Scheduling Your LLM Reinforcement Learning with Reasoning Trees [18.720191133993715]
  We introduce Reasoning Score (r-score), which measures the query's learning difficulty based on the structure of its reasoning tree.<n>Based on the r-score, we propose the Reasoning Tree Schedule (Re-Schedule), a scheduling algorithm that constructs a curriculum progressing from structurally simple (high r-score) to complex (low r-score) queries.
  arXiv  Detail & Related papers  (2025-10-28T17:52:07Z)
• 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)
• Learning Decision Trees as Amortized Structure Inference [59.65621207449269]
  We propose a hybrid amortized structure inference approach to learn predictive decision tree ensembles given data. We show that our approach, DT-GFN, outperforms state-of-the-art decision tree and deep learning methods on standard classification benchmarks.
  arXiv  Detail & Related papers  (2025-03-10T07:05:07Z)
• A Query-Driven Approach to Space-Efficient Range Searching [12.760453906939446]
  We show that a near-linear sample of queries allows the construction of a partition tree with a near-optimal expected number of nodes visited during querying. We enhance this approach by treating node processing as a classification problem, leveraging fast classifiers like shallow neural networks to obtain experimentally efficient query times. Our algorithm, based on a sample of queries, builds a balanced tree with nodes associated with separators that minimize query stabs on expectation.
  arXiv  Detail & Related papers  (2025-02-19T12:01:00Z)
• BPP-Search: Enhancing Tree of Thought Reasoning for Mathematical Modeling Problem Solving [11.596474985695679]
  We release the StructuredOR dataset, annotated with comprehensive labels that capture the complete mathematical modeling process. We propose BPP-Search, an algorithm that integrates reinforcement learning into a tree-of-thought structure. In tree-based reasoning, BPP-Search excels in accuracy and efficiency, enabling faster retrieval of correct solutions.
  arXiv  Detail & Related papers  (2024-11-26T13:05:53Z)
• Discovering Data Structures: Nearest Neighbor Search and Beyond [18.774836778996544]
  We propose a general framework for end-to-end learning of data structures. Our framework adapts to the underlying data distribution and provides fine-grained control over query and space complexity. We first apply this framework to the problem of nearest neighbor search.
  arXiv  Detail & Related papers  (2024-11-05T16:50:54Z)
• Understanding Synthetic Context Extension via Retrieval Heads [51.8869530817334]
  We investigate fine-tuning on synthetic data for three long-context tasks that require retrieval and reasoning. We find that models trained on synthetic data fall short of the real data, but surprisingly, the mismatch can be interpreted. Our results shed light on how to interpret synthetic data fine-tuning performance and how to approach creating better data for learning real-world capabilities over long contexts.
  arXiv  Detail & Related papers  (2024-10-29T17:55:00Z)
• Pairing Clustered Inverted Indexes with kNN Graphs for Fast Approximate Retrieval over Learned Sparse Representations [8.796275989527054]
  We present Seismic, a highly-accurate approximate retrieval algorithm. Seismic is one to two orders of magnitude faster than state-of-the-art inverted index-based solutions. We introduce two innovations to Seismic's query processing: first, we traverse blocks in order of importance, rather than arbitrarily. Our extension, named SeismicWave, can reach almost-exact accuracy levels and is up to 2.2x faster than Seismic.
  arXiv  Detail & Related papers  (2024-08-08T13:14:39Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
  arXiv  Detail & Related papers  (2024-06-29T05:14:04Z)
• LIST: Learning to Index Spatio-Textual Data for Embedding based Spatial Keyword Queries [53.843367588870585]
  List K-kNN spatial keyword queries (TkQs) return a list of objects based on a ranking function that considers both spatial and textual relevance. There are two key challenges in building an effective and efficient index, i.e., the absence of high-quality labels and the unbalanced results. We develop a novel pseudolabel generation technique to address the two challenges.
  arXiv  Detail & Related papers  (2024-03-12T05:32:33Z)
• Found in the Middle: Permutation Self-Consistency Improves Listwise Ranking in Large Language Models [63.714662435555674]
  Large language models (LLMs) exhibit positional bias in how they use context. We propose permutation self-consistency, a form of self-consistency over ranking list outputs of black-box LLMs. Our approach improves scores from conventional inference by up to 7-18% for GPT-3.5 and 8-16% for LLaMA v2 (70B)
  arXiv  Detail & Related papers  (2023-10-11T17:59:02Z)
• From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice [0.0]
  We focus on Learned Sorted Set Dictionaries. We propose a novel paradigm that, complementing known specialized ones, can produce Learned versions of any Sorted Set Dictionary.
  arXiv  Detail & Related papers  (2023-09-02T13:52:53Z)
• Online List Labeling with Predictions [13.126494821223755]
  We show that predictions can be leveraged in the fundamental online list labeling problem. In the problem, n items arrive over time and must be stored in sorted order in an array of size Theta(n) We design a new list labeling data structure and bound its performance in two models.
  arXiv  Detail & Related papers  (2023-05-17T19:46:34Z)
• Online Learning of Optimally Diverse Rankings [63.62764375279861]
  We propose an algorithm that efficiently learns the optimal list based on users' feedback only. We show that after $T$ queries, the regret of LDR scales as $O((N-L)log(T))$ where $N$ is the number of all items.
  arXiv  Detail & Related papers  (2021-09-13T12:13:20Z)
• Visualizing hierarchies in scRNA-seq data using a density tree-biased autoencoder [50.591267188664666]
  We propose an approach for identifying a meaningful tree structure from high-dimensional scRNA-seq data. We then introduce DTAE, a tree-biased autoencoder that emphasizes the tree structure of the data in low dimensional space.
  arXiv  Detail & Related papers  (2021-02-11T08:48:48Z)
• Surprise: Result List Truncation via Extreme Value Theory [92.5817701697342]
  We propose a statistical method that produces interpretable and calibrated relevance scores at query time using nothing more than the ranked scores. We demonstrate its effectiveness on the result list truncation task across image, text, and IR datasets.
  arXiv  Detail & Related papers  (2020-10-19T19:15:50Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  We present a novel algorithm for learning optimal classification trees based on dynamic programming and search. Our approach uses only a fraction of the time required by the state-of-the-art and can handle datasets with tens of thousands of instances.
  arXiv  Detail & Related papers  (2020-07-24T17:06:55Z)
• Best-First Beam Search [78.71330480725668]
  We show that the standard implementation of beam search can be made up to 10x faster in practice. We propose a memory-reduced variant of Best-First Beam Search, which has a similar beneficial search bias in terms of downstream performance.
  arXiv  Detail & Related papers  (2020-07-08T05:56:01Z)
• RadixSpline: A Single-Pass Learned Index [84.84747738666263]
  We introduce RadixSpline (RS), a learned index that can be built in a single pass over the data. RS achieves competitive results on all datasets, despite the fact that it only has two parameters.
  arXiv  Detail & Related papers  (2020-04-30T01:56:54Z)
• Tree Echo State Autoencoders with Grammars [3.7280152311394827]
  Non-vectorial and discrete nature of trees makes it challenging to construct functions with tree-formed output. Existing autoencoding approaches fail to take the specific grammatical structure of tree domains into account. We propose tree echo state autoencoders (TES-AE), which are guided by a tree grammar and can be trained within seconds by virtue of reservoir computing.
  arXiv  Detail & Related papers  (2020-04-19T18:04:33Z)
• Increasing the Inference and Learning Speed of Tsetlin Machines with Clause Indexing [9.440900386313215]
  The Tsetlin Machine (TM) is a machine learning algorithm founded on the classical Tsetlin Automaton (TA) and game theory. We report up to 15 times faster classification and three times faster learning on MNIST and Fashion-MNIST image classification, and IMDb sentiment analysis.
  arXiv  Detail & Related papers  (2020-04-07T08:16:07Z)

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.