論文の概要: Exact Indexing of Time Series under Dynamic Time Warping

• arxiv url: http://arxiv.org/abs/2002.04187v1
• Date: Tue, 11 Feb 2020 03:34:48 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-02 02:49:38.405326
• Title: Exact Indexing of Time Series under Dynamic Time Warping
• Title（参考訳）: 動的時間ゆがみ下における時系列の厳密な索引付け
• Authors: Zhengxin Li
• Abstract要約: シーケンス拡張とLB_Keoghをシームレスに組み合わせた新しい下界距離LB_Keogh+を提案する。 不等長列に使用することができ、計算複雑性が低い。 LB_Keogh+に基づいて、DTWの下での時系列の正確なインデックスを考案する。
• 参考スコア（独自算出の注目度）: 1.3300217947936062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic time warping (DTW) is a robust similarity measure of time series. However, it does not satisfy triangular inequality and has high computational complexity, severely limiting its applications in similarity search on large-scale datasets. Usually, we resort to lower bounding distances to speed up similarity search under DTW. Unfortunately, there is still a lack of an effective lower bounding distance that can measure unequal-length time series and has desirable tightness. In the paper, we propose a novel lower bounding distance LB_Keogh+, which is a seamless combination of sequence extension and LB_Keogh. It can be used for unequal-length sequences and has low computational complexity. Besides, LB_Keogh+ can extend sequences to an arbitrary suitable length, without significantly reducing tightness. Next, based on LB_Keogh+, an exact index of time series under DTW is devised. Then, we introduce several theorems and complete the relevant proofs to guarantee no false dismissals in our similarity search. Finally, extensive experiments are conducted on real-world datasets. Experimental results indicate that our proposed method can perform similarity search of unequal-length sequences with high tightness and good pruning power.
• Abstract（参考訳）: dynamic time warping (dtw) は時系列のロバストな類似性尺度である。 しかし、三角不等式を満足せず、計算複雑性が高く、大規模データセットの類似性探索における応用を厳しく制限している。 通常、DTWにおける類似性探索を高速化するために、境界距離を低くする。 残念なことに、不等長の時系列を測り、望ましい厳密性を持つ効果的な下界距離がまだ存在しない。 本稿では,シーケンス拡張とLB_Keoghをシームレスに組み合わせた,新しい下界距離LB_Keogh+を提案する。 不等長列に使用することができ、計算複雑性が低い。 加えて、LB_Keogh+はシーケンスを任意の適切な長さまで拡張できるが、タイトさは著しく低下しない。 次に、LB_Keogh+に基づいてDTWの下での時系列の正確なインデックスを考案する。 次に,いくつかの定理を導入し,類似性探索において虚偽の棄却がないことを保証するための,関連する証明を完結する。 最後に、実世界のデータセットで広範な実験が行われる。 実験結果から,提案手法は不等長列の類似性探索を行うことができることがわかった。

関連論文リスト

• Multiscale Dubuc: A New Similarity Measure for Time Series [1.024113475677323]
  マルチスケールDubuc距離測度を導入し、それがメートル法であることを証明する。 UCR時系列分類アーカイブから95のデータセットを使用して、MDDのパフォーマンスをEuD、LCSS、DTWと比較する。 我々の実験によると、MDDの全体的な成功はケース固有のカスタマイズなしで、データセットごとのウィンドウサイズを最適化したDTWに匹敵する。
  論文  参考訳（メタデータ） (2024-11-15T18:38:18Z)
• HyperAttention: Long-context Attention in Near-Linear Time [78.33061530066185]
  本稿では,長期的文脈の複雑さの増大に伴う計算課題に対処するため,HyperAttentionという近似的な注意機構を提案する。 実証的には、大規模なエントリを特定するためにLocality Sensitive Hashing(LSH)を使用して、HyperAttentionは既存のメソッドよりも優れています。 各種長文長データセットにおけるHyperAttentionの実証的性能を検証した。
  論文  参考訳（メタデータ） (2023-10-09T17:05:25Z)
• Does Long-Term Series Forecasting Need Complex Attention and Extra Long Inputs? [21.15722677855935]
  トランスフォーマーベースのモデルは、様々な時系列タスクにおいて印象的なパフォーマンスを達成した。 近年、LTSF(Long-Term Series Forecasting)タスクも注目されている。 トランスフォーマーベースの手法を要求される計算複雑性と長いシーケンスのため、LTSFタスクへの適用には2つの大きな問題がある。
  論文  参考訳（メタデータ） (2023-06-08T08:37:49Z)
• Matrix Profile XXVII: A Novel Distance Measure for Comparing Long Time Series [18.205595410817327]
  本稿では,シリーズにおけるパターン表現比較(Pattern Representation Comparison in Series)の略であるPRCISを紹介する。 PRCISは長い時系列の距離測定であり、辞書で時系列を要約する能力の最近の進歩を生かしている。
  論文  参考訳（メタデータ） (2022-12-09T23:02:23Z)
• Triformer: Triangular, Variable-Specific Attentions for Long Sequence Multivariate Time Series Forecasting--Full Version [50.43914511877446]
  本稿では,高い効率と精度を確保するために,三角形,可変特性に着目した注意点を提案する。 我々はTriformerが精度と効率の両方で最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2022-04-28T20:41:49Z)
• Elastic Product Quantization for Time Series [19.839572576189187]
  本稿では,時間ゆらぎの時間系列の効率的な類似度に基づく比較に製品量子化を用いることを提案する。 提案手法は, 時系列アプリケーションにおける弾性測度を, 高効率(メモリ使用量と時間の両方)で置き換える手法として現れる。
  論文  参考訳（メタデータ） (2022-01-04T09:23:06Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Matrix Profile XXII: Exact Discovery of Time Series Motifs under DTW [1.282368486390644]
  動的時間ワープの下で時系列のモチーフを発見するための,最初のスケーラブルな正確な方法を提案する。 我々のアルゴリズムは、DTW計算の99.99%を許容できる。
  論文  参考訳（メタデータ） (2020-09-16T19:35:43Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)
• 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)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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