論文の概要: FastDTW is approximate and Generally Slower than the Algorithm it Approximates

• arxiv url: http://arxiv.org/abs/2003.11246v5
• Date: Sat, 3 Sep 2022 04:42:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-20 02:48:59.777349
• Title: FastDTW is approximate and Generally Slower than the Algorithm it Approximates
• Title（参考訳）: FastDTWは近似的であり、一般に近似アルゴリズムよりも遅い
• Authors: Renjie Wu and Eamonn J. Keogh
• Abstract要約: 動的時間ワープ(DTW)距離測定は、ほとんどのドメインにおいて、ほとんどのタスクに最適な尺度である。 最も引用されているアプローチの1つはFastDTWである。 任意の現実的なデータマイニングアプリケーションでは、近似的なFastDTWは正確なDTWよりもはるかに遅い。
• 参考スコア（独自算出の注目度）: 11.689905300531917
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many time series data mining problems can be solved with repeated use of distance measure. Examples of such tasks include similarity search, clustering, classification, anomaly detection and segmentation. For over two decades it has been known that the Dynamic Time Warping (DTW) distance measure is the best measure to use for most tasks, in most domains. Because the classic DTW algorithm has quadratic time complexity, many ideas have been introduced to reduce its amortized time, or to quickly approximate it. One of the most cited approximate approaches is FastDTW. The FastDTW algorithm has well over a thousand citations and has been explicitly used in several hundred research efforts. In this work, we make a surprising claim. In any realistic data mining application, the approximate FastDTW is much slower than the exact DTW. This fact clearly has implications for the community that uses this algorithm: allowing it to address much larger datasets, get exact results, and do so in less time.
• Abstract（参考訳）: 多くの時系列データマイニング問題は、距離測定を繰り返すことで解決できる。 そのようなタスクの例としては、類似性検索、クラスタリング、分類、異常検出、セグメンテーションなどがある。 20年以上にわたり、ほとんどのドメインにおいて、動的時間ワープ(DTW)距離測定がほとんどのタスクに最適な尺度であることが知られている。 古典的なDTWアルゴリズムは2次時間複雑性を持つため、その償却時間を削減するために多くのアイデアが導入された。 最も引用される近似アプローチの1つはfastdtwである。 FastDTWアルゴリズムは1000以上の励起を持ち、数百の研究で明確に使われている。 この作品では驚くべき主張をしている。 任意の現実的なデータマイニングアプリケーションでは、FastDTWは正確なDTWよりもはるかに遅い。 この事実は、このアルゴリズムを使用するコミュニティに明らかに影響している: はるかに大きなデータセットに対処し、正確な結果を得ることができ、少ない時間でそれを行うことができる。

関連論文リスト

• OTW: Optimal Transport Warping for Time Series [75.69837166816501]
  動的時間温暖化(DTW)は時系列間の距離を測定するための実用的な選択肢となっている。 最適アライメント行列を正確に計算する必要がある場合、それは避けられない二次時間複雑性に悩まされる。 我々は、OTW(Optimal Transport Warping)と呼ばれる、最適輸送フレームワークに基づく時系列データのための新しいメトリクスを導入する。
  論文  参考訳（メタデータ） (2023-06-01T12:45:00Z)
• Deep Declarative Dynamic Time Warping for End-to-End Learning of Alignment Paths [54.53208538517505]
  本稿では、動的時間ワープ(DTW)による時間的アライメントステップを含む時系列データのエンドツーエンド学習モデルについて述べる。 そこで我々は,2レベル最適化とDecDTWと呼ばれる深層宣言ネットワークに基づくDTW層を提案する。 この特性は、下流損失関数が最適アライメントパス自身で定義されるアプリケーションに特に有用であることを示す。
  論文  参考訳（メタデータ） (2023-03-19T21:58:37Z)
• Approximating DTW with a convolutional neural network on EEG data [9.409281517596396]
  動的時間ラッピング(DTW)の高速かつ微分可能な近似法を提案する。 提案手法は,計算効率が向上した他のDTW主近似と同等以上の精度が得られることを示す。
  論文  参考訳（メタデータ） (2023-01-30T13:27:47Z)
• GPU-accelerated Faster Mean Shift with euclidean distance metrics [1.3507758562554621]
  平均シフトアルゴリズムはクラスタリング問題の解法として広く用いられている。 従来の研究では,GPUを高速化する高速平均シフトアルゴリズムが提案されている。 本研究では,ユークリッド距離測定値を扱うために,従来のアルゴリズムを拡張し改良する。
  論文  参考訳（メタデータ） (2021-12-27T20:18:24Z)
• Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures [49.73889315176884]
  条件勾配法(CGM)は現代の機械学習で広く使われている。 ほとんどの取り組みは、全体の実行時間を短縮する手段として、イテレーションの数を減らすことに重点を置いています。 本稿では,多くの基本最適化アルゴリズムに対して,イテレーション毎のコストがパラメータ数にサブ線形である最初のアルゴリズムを示す。
  論文  参考訳（メタデータ） (2021-11-30T05:40:14Z)
• TC-DTW: Accelerating Multivariate Dynamic Time Warping Through Triangle Inequality and Point Clustering [6.502892821109196]
  今日最もよく使われているアルゴリズムは17年前に開発されたアルゴリズムである。 tc-dtwと名付けられた新しいソリューションは、三角不等式と点クラスタリングをアルゴリズム設計に導入する。 DTWをベースとした近接探索実験では、新しい解は最大98%(平均60%)のDTW距離計算を回避し、最大25倍(平均7.5倍)のスピードアップをもたらす。
  論文  参考訳（メタデータ） (2021-01-15T16:38:28Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
  動的時間ワープの下で時系列のモチーフを発見するための,最初のスケーラブルな正確な方法を提案する。 我々のアルゴリズムは、DTW計算の99.99%を許容できる。
  論文  参考訳（メタデータ） (2020-09-16T19:35:43Z)
• Faster Person Re-Identification [68.22203008760269]
  本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。 より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。 2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
  論文  参考訳（メタデータ） (2020-08-16T03:02:49Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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