Linked Array Tree: A Constant-Time Search Structure for Big Data

• URL: http://arxiv.org/abs/2504.00828v1
• Date: Tue, 01 Apr 2025 14:15:55 GMT
• Title: Linked Array Tree: A Constant-Time Search Structure for Big Data
• Abstract summary: Linked Array Tree (LAT) is a novel data structure designed to achieve constant-time complexity for search, insertion, and deletion operations.<n>LAT's low memory overhead and avoidance of pointer-heavy structures make it well-suited for large-scale and intensive workloads.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As data volumes continue to grow rapidly, traditional search algorithms, like the red-black tree and B+ Tree, face increasing challenges in performance, especially in big data scenarios with intensive storage access. This paper presents the Linked Array Tree (LAT), a novel data structure designed to achieve constant-time complexity for search, insertion, and deletion operations. LAT leverages a sparse, non-moving hierarchical layout that enables direct access paths without requiring rebalancing or data movement. Its low memory overhead and avoidance of pointer-heavy structures make it well-suited for large-scale and intensive workloads. While not specifically tested under parallel or concurrent conditions, the structure's static layout and non-interfering operations suggest potential advantages in such environments. This paper first introduces the structure and algorithms of LAT, followed by a detailed analysis of its time complexity in search, insertion, and deletion operations. Finally, it presents experimental results across both data-intensive and sparse usage scenarios to evaluate LAT's practical performance.

Related papers

• Organize then Retrieve: Hierarchical Memory Navigation for Efficient Agents [29.28371047415946]
  HORMA is a hierarchical organize-and-Retrieve Memory Agent for large language models.<n>It decomposes working memory into two stages: structured memory construction and navigation-based retrieval.<n>It consistently achieves better efficiency-performance trade-offs and generalizes effectively to unseen tasks.
  arXiv  Detail & Related papers  (2026-06-10T05:49:14Z)
• Coupled Hierarchical Search over Topology and Execution for Agentic Workflow Synthesis [64.2820121997882]
  We introduce HierFlow, a training-free, test-time hierarchical search architecture that automates agentic workflow design.<n> HierFlow maximizes efficiency through an intelligent gating module that selectively triggers execution-level searches based on contextual necessity.<n> Comprehensive testing across question answering, mathematical reasoning, and code generation benchmarks confirms that HierFlow consistently outperforms strong baselines.
  arXiv  Detail & Related papers  (2026-05-20T01:56:11Z)
• FlashResearch: Real-time Agent Orchestration for Efficient Deep Research [62.03819662340356]
  FlashResearch is a novel framework for efficient deep research.<n>It transforms sequential processing into parallel, runtime orchestration.<n>It can deliver up to a 5x speedup while maintaining comparable quality.
  arXiv  Detail & Related papers  (2025-10-02T00:15:39Z)
• ELITE: Embedding-Less retrieval with Iterative Text Exploration [5.8851517822935335]
  Large Language Models (LLMs) have achieved impressive progress in natural language processing.<n>Their limited ability to retain long-term context constrains performance on document-level or multi-turn tasks.
  arXiv  Detail & Related papers  (2025-05-17T08:48:43Z)
• 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)
• Efficient Long Context Language Model Retrieval with Compression [57.09163579304332]
  Long Context Language Models (LCLMs) have emerged as a new paradigm to perform Information Retrieval (IR)<n>We propose a new compression approach tailored for LCLM retrieval, which is trained to maximize the retrieval performance while minimizing the length of the compressed passages.<n>We show that CoLoR improves the retrieval performance by 6% while compressing the in-context size by a factor of 1.91.
  arXiv  Detail & Related papers  (2024-12-24T07:30:55Z)
• Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
  Causal discovery is a crucial initial step in establishing causality from empirical data and background knowledge.<n>Current score-matching-based algorithms are primarily designed to analyze independent and identically distributed (i.i.d.) data.<n>We have developed a new parent-finding subroutine for leaf nodes in DAGs, significantly accelerating the most time-consuming part of the process: the pruning step.
  arXiv  Detail & Related papers  (2024-12-10T12:36:35Z)
• KV Cache Compression, But What Must We Give in Return? A Comprehensive Benchmark of Long Context Capable Approaches [52.02764371205856]
  Long context capability is a crucial competency for large language models (LLMs) This work provides a taxonomy of current methods and evaluating 10+ state-of-the-art approaches across seven categories of long context tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:59:47Z)
• 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)
• Learning-Augmented Search Data Structures [14.015114340879544]
  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.
  arXiv  Detail & Related papers  (2024-02-16T05:27:13Z)
• 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)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• A Hierarchical Approach to Scaling Batch Active Search Over Structured Data [0.5076419064097732]
  We present a general hierarchical framework based on bandit algorithms to scale active search to large batch sizes. We focus our application of HBBS on modern biology, where large batch experimentation is often fundamental to the research process.
  arXiv  Detail & Related papers  (2020-07-20T16:50:25Z)
• Succinct Trit-array Trie for Scalable Trajectory Similarity Search [3.2197141014728805]
  Similarity search of a large collection of trajectories is indispensable for turning these datasets into knowledge. To address this problem, we present the trajectory-indexing succinct trit-array trie (tSTAT) We show that tSTAT performs superiorly in comparison to state-of-the-art similarity search methods.
  arXiv  Detail & Related papers  (2020-05-21T21:42:30Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  We propose a simple and resource-efficient method to pretrain the paragraph encoder. Our method outperforms an existing dense retrieval method that uses 7 times more computational resources for pretraining.
  arXiv  Detail & Related papers  (2020-04-30T18:09:50Z)
• Qd-tree: Learning Data Layouts for Big Data Analytics [33.07610112749939]
  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.
  arXiv  Detail & Related papers  (2020-04-22T23:42:59Z)

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.