論文の概要: Efficient Cover Construction for Ball Mapper via Accelerated Range Queries

• arxiv url: http://arxiv.org/abs/2601.01405v1
• Date: Sun, 04 Jan 2026 07:04:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:22.326813
• Title: Efficient Cover Construction for Ball Mapper via Accelerated Range Queries
• Title（参考訳）: 高速化レンジクエリによるボールマッパーの効率的なカバー構成
• Authors: Jay-Anne Bulauan, John Rick Manzanares,
• Abstract要約: 範囲問合せの効率を向上させることにより,ボールマッパーのカバー構築を高速化する戦略について検討する。 本研究では,ボールツリーデータ構造を用いた階層的幾何学的プルーニングと,Facebook AIの類似度探索を用いたハードウェア対応距離計算という,Ball Mapperパイプラインに補完的な2つのアプローチを統合する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Ball Mapper is an widely used tool in topological data analysis for summarizing the structure of high-dimensional data through metric-based coverings and graph representations. A central computational bottleneck in Ball Mapper is the construction of the underlying cover, which requires repeated range queries to identify data points within a fixed distance of selected landmarks. As data sets grow in size and dimensionality, naive implementations of this step become increasingly inefficient. In this work, we study practical strategies for accelerating cover construction in Ball Mapper by improving the efficiency of range queries. We integrate two complementary approaches into the Ball Mapper pipeline: hierarchical geometric pruning using ball tree data structures, and hardware-aware distance computation using Facebook AI Similarity Search. We describe the underlying algorithms, discuss their trade-offs with respect to metric flexibility and dimensionality, and provide implementation details relevant to large-scale data analysis. Empirical benchmarks demonstrate that both approaches yield substantial speedups over the baseline implementation, with performance gains depending on data set size, dimensionality, and choice of distance function. These results improve the practical scalability of Ball Mapper without modifying its theoretical formulation and provide guidance for the efficient implementation of metric-based exploratory tools in modern data analysis workflows.
• Abstract（参考訳）: Ball Mapperは、計量に基づく被覆とグラフ表現を通じて高次元データの構造を要約する、トポロジデータ解析において広く使われているツールである。 Ball Mapperにおける中心的な計算ボトルネックは、選択されたランドマークの固定距離内のデータポイントを特定するために、繰り返し範囲クエリを必要とする、基礎となるカバーの構築である。 データセットのサイズと次元が大きくなるにつれて、このステップの単純な実装はますます非効率になる。 本研究では,範囲問合せの効率を向上させることにより,ボールマッパーのカバー構築を高速化する実践的戦略について検討する。 本研究では,ボールツリーデータ構造を用いた階層的幾何学的プルーニングと,Facebook AIの類似度探索を用いたハードウェア対応距離計算という,Ball Mapperパイプラインに補完的な2つのアプローチを統合する。 基礎となるアルゴリズムを解説し、計量の柔軟性と次元性に関してそれらのトレードオフを議論し、大規模データ分析に関する実装の詳細を提供する。 実験的なベンチマークでは、両方のアプローチがベースライン実装よりも大幅にスピードアップし、データセットのサイズ、次元、距離関数の選択によって性能が向上することを示した。 これらの結果は、理論的定式化を変更せずにボールマッパーの実用的スケーラビリティを改善し、現代のデータ解析ワークフローにおけるメートル法に基づく探索ツールの効率的な実装のためのガイダンスを提供する。

関連論文リスト

• Graph Vertex Embeddings: Distance, Regularization and Community Detection [0.0]
  グラフ埋め込みは、低次元空間における複雑なネットワーク構造を表現する強力なツールとして登場した。 異なる頂点間の位相的距離を忠実に捉えるフレキシブル距離関数の族を示す。 ベンチマークデータセットのホスト上でコミュニティ検出を行うことにより,提案手法の有効性を評価する。
  論文  参考訳（メタデータ） (2024-04-09T09:03:53Z)
• Differentiable Mapper For Topological Optimization Of Data Representation [33.33724208084121]
  我々は,Mapperグラフに対する最初のフィルタ最適化スキームを提供するためにトポロジを組み込んだ最近提案されたフレームワークを構築した。 複数のデータセット上でMapperグラフ表現を最適化することで,提案手法の有用性を示す。
  論文  参考訳（メタデータ） (2024-02-20T09:33:22Z)
• A distribution-guided Mapper algorithm [0.3683202928838613]
  本稿ではD-Mapperという分布誘導型Mapperアルゴリズムを提案する。 提案アルゴリズムは確率的モデルに基づく手法であり,非確率的手法の代替となる可能性がある。 数値実験により,D-Mapperは様々なシナリオにおいて従来のMapperアルゴリズムより優れていることが示された。
  論文  参考訳（メタデータ） (2024-01-19T17:07:05Z)
• Data-driven abstractions via adaptive refinements and a Kantorovich metric [extended version] [56.94699829208978]
  本稿では,動的システムのスマートでスケーラブルな抽象化のための適応的洗練手順を提案する。 最適構造を学ぶために、マルコフ連鎖の間のカントロビッチに着想を得た計量を定義する。 本稿では,従来の線形プログラミング手法よりも計算量が多くなることを示す。
  論文  参考訳（メタデータ） (2023-03-30T11:26:40Z)
• Robust Self-Tuning Data Association for Geo-Referencing Using Lane Markings [44.4879068879732]
  本稿では,データアソシエーションにおけるあいまいさを解消するための完全なパイプラインを提案する。 その中核は、測定のエントロピーに応じて探索領域に適応する堅牢な自己調整データアソシエーションである。 ドイツ・カールスルーエ市周辺の都市・農村のシナリオを実データとして評価した。
  論文  参考訳（メタデータ） (2022-07-28T12:29:39Z)
• Shapley-NAS: Discovering Operation Contribution for Neural Architecture Search [96.20505710087392]
  ニューラルアーキテクチャ探索のための演算寄与度(Shapley-NAS)を評価するためのShapley値に基づく手法を提案する。 提案手法は,光探索コストに比例して最先端の手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-06-20T14:41:49Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)
• Spatial Pyramid Based Graph Reasoning for Semantic Segmentation [67.47159595239798]
  セマンティックセグメンテーションタスクにグラフ畳み込みを適用し、改良されたラプラシアンを提案する。 グラフ推論は、空間ピラミッドとして構成された元の特徴空間で直接実行される。 計算とメモリのオーバーヘッドの利点で同等のパフォーマンスを実現しています。
  論文  参考訳（メタデータ） (2020-03-23T12:28:07Z)

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

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