論文の概要: Linked Array Tree: A Constant-Time Search Structure for Big Data

• arxiv url: http://arxiv.org/abs/2504.00828v1
• Date: Tue, 01 Apr 2025 14:15:55 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-03 13:17:39.057175
• Title: Linked Array Tree: A Constant-Time Search Structure for Big Data
• Title（参考訳）: Linked Array Tree:ビッグデータの定時間検索構造
• Authors: Songpeng Liu,
• Abstract要約: Linked Array Tree (LAT) は、検索、挿入、削除操作の時間的複雑さを実現するために設計された新しいデータ構造である。 LATの低メモリオーバーヘッドとポインタ重構造の回避は、大規模かつ集中的なワークロードに適しています。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• 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.
• Abstract（参考訳）: データボリュームが急速に増加するにつれて、レッドブラックツリーやB+ツリーのような従来の検索アルゴリズムは、特にストレージアクセスが集中したビッグデータシナリオにおいて、パフォーマンス上の課題に直面する。 本稿では,検索,挿入,削除操作の時間的複雑さを実現するために設計された新しいデータ構造であるLinked Array Tree(LAT)を提案する。 LATは、疎結合やデータ移動を必要とせずに直接アクセスパスを可能にする、非移動階層レイアウトを利用する。 メモリオーバーヘッドの低減とポインタ重構造の回避により、大規模かつ集中的なワークロードに適している。 並列または並列条件下では特にテストされていないが、構造体の静的レイアウトと非干渉操作は、そのような環境において潜在的な利点を示唆している。 本稿では,LATの構造とアルゴリズムをまず紹介し,検索,挿入,削除操作における時間的複雑さを詳細に分析する。 最後に、データ集約的およびスパースな使用シナリオにまたがる実験結果を示し、LATの実用性能を評価する。

関連論文リスト

• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  そこで本研究では,様々なレベルで参照文書を整理し,表現するためのツリーベース手法を提案する。 我々の手法はReTreeverと呼ばれ、クエリと参照ドキュメントが同様のツリーブランチに割り当てられるように、バイナリツリーの内部ノード毎のルーティング関数を共同で学習する。 我々の評価では、ReTreeverは一般的に完全な表現精度を保っている。
  論文  参考訳（メタデータ） (2025-02-11T21:35:13Z)
• Score-matching-based Structure Learning for Temporal Data on Networks [17.166362605356074]
  因果発見は経験的データと背景知識から因果関係を確立するための重要な第一歩である。 現在のスコアマッチングベースのアルゴリズムは、主に独立および同一に分散された(d.d.)データを分析するために設計されている。 我々はDAGの葉ノードのための新しい親フィンディングサブルーチンを開発し、プロセスの最も時間を要する部分である刈り込みステップを著しく加速した。
  論文  参考訳（メタデータ） (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]
  長期の文脈能力は、大規模言語モデル(LLM)にとって重要な能力である この研究は、現在の手法の分類を提供し、長いコンテキストタスクの7つのカテゴリにまたがる10以上の最先端のアプローチを評価する。
  論文  参考訳（メタデータ） (2024-07-01T17:59:47Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• From Specific to Generic Learned Sorted Set Dictionaries: A Theoretically Sound Paradigm Yelding Competitive Data Structural Boosters in Practice [0.0]
  我々は学習されたセット辞書に焦点をあてる。 我々は、既知の専門用語を補完する新しいパラダイムを提案し、任意のSorted Set Dictionaryの学習版を作成できる。
  論文  参考訳（メタデータ） (2023-09-02T13:52:53Z)
• Autoregressive Search Engines: Generating Substrings as Document Identifiers [53.0729058170278]
  自動回帰言語モデルは、回答を生成するデファクト標準として現れています。 これまでの研究は、探索空間を階層構造に分割する方法を探究してきた。 本研究では,検索空間の任意の構造を強制しない代替として,経路内のすべてのngramを識別子として使用することを提案する。
  論文  参考訳（メタデータ） (2022-04-22T10:45:01Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。 我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。 提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
  論文  参考訳（メタデータ） (2021-12-05T06:42:48Z)
• A Hierarchical Approach to Scaling Batch Active Search Over Structured Data [0.5076419064097732]
  本稿では,能動探索を大規模なバッチサイズに拡張するために,帯域幅アルゴリズムに基づく汎用階層型フレームワークを提案する。 HBBSの応用は、大規模なバッチ実験が研究プロセスに欠かせない現代生物学に重点を置いている。
  論文  参考訳（メタデータ） (2020-07-20T16:50:25Z)
• Succinct Trit-array Trie for Scalable Trajectory Similarity Search [3.2197141014728805]
  膨大なトラジェクトリの集合の類似性探索は、これらのデータセットを知識に変えるのに不可欠である。 この問題に対処するため, トラジェクトリトアレイトリエ (tSTAT) のトラジェクトリ・インデクシングについて述べる。 tSTATは,最先端の類似性探索法と比較して優れた性能を示す。
  論文  参考訳（メタデータ） (2020-05-21T21:42:30Z)
• Progressively Pretrained Dense Corpus Index for Open-Domain Question Answering [87.32442219333046]
  本稿では,段落エンコーダを事前学習するための簡易かつ資源効率の高い手法を提案する。 本手法は,事前学習に7倍の計算資源を使用する既存の高密度検索法より優れている。
  論文  参考訳（メタデータ） (2020-04-30T18:09:50Z)
• Qd-tree: Learning Data Layouts for Big Data Analytics [33.07610112749939]
  本稿では、クエリデータルーティングツリー(qd-tree)と呼ばれる新しいフレームワークを提案し、この問題に対処する。 実験により、qd木は現在のブロッキング方式と比較して1桁以上の物理的スピードアップを提供できることが示された。
  論文  参考訳（メタデータ） (2020-04-22T23:42:59Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。