論文の概要: A fast algorithm for complex discord searches in time series: HOT SAX Time

• arxiv url: http://arxiv.org/abs/2101.10698v1
• Date: Tue, 26 Jan 2021 10:42:57 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-13 19:48:32.809249
• Title: A fast algorithm for complex discord searches in time series: HOT SAX Time
• Title（参考訳）: 時系列における複素不協和探索の高速アルゴリズム:HOT SAX Time
• Authors: Paolo Avogadro, Matteo Alessandro Dominoni
• Abstract要約: HOT SAX Time (HST) と呼ばれるアルゴリズムは実時間と合成時間で検証されている。 複雑な検索の場合、HSTはHOT SAXの100倍以上高速である可能性があります。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Time series analysis is quickly proceeding towards long and complex tasks. In recent years, fast approximate algorithms for discord search have been proposed in order to compensate for the increasing size of the time series. It is more interesting, however, to find quick exact solutions. In this research, we improved HOT SAX by exploiting two main ideas: the warm-up process, and the similarity between sequences close in time. The resulting algorithm, called HOT SAX Time (HST), has been validated with real and synthetic time series, and successfully compared with HOT SAX, RRA, SCAMP, and DADD. The complexity of a discord search has been evaluated with a new indicator, the cost per sequence (cps), which allows one to compare searches on time series of different lengths. Numerical evidence suggests that two conditions are involved in determining the complexity of a discord search in a non-trivial way: the length of the discords, and the noise/signal ratio. In the case of complex searches, HST can be more than 100 times faster than HOT SAX, thus being at the forefront of the exact discord search.
• Abstract（参考訳）: 時系列分析は、長く複雑なタスクに素早く進んでいます。 近年,時系列の増大を補うために,ディスコード探索のための高速近似アルゴリズムが提案されている。 しかし、より正確な解決策を見つけるのがより興味深い。 本研究では、ウォームアッププロセスと時間に近いシーケンス間の類似性という2つの主なアイデアを利用してHOT SAXを改善しました。 HOT SAX Time(HST)と呼ばれるこのアルゴリズムは、実時間および合成時間系列で検証され、HOT SAX、RRA、SCAMP、DADDとの比較に成功した。 不協和探索の複雑さを新しい指標であるシーケンス毎のコスト(cps)で評価することで、異なる長さの時系列での検索を比較することができる。 数値的証拠は、不一致探索の複雑さを非自明な方法で決定するために2つの条件が関与していることを示唆している:不一致の長さ、およびノイズ/信号比。 複雑な検索の場合、HSTはHOT SAXよりも100倍以上高速であり、したがって正確な不一致検索の最前線にいます。

関連論文リスト

• Energy and Time Complexity for Sorting Algorithms in Java [0.0]
  本稿では、ソートアルゴリズムにおける時間複雑性とエネルギー消費の関係について検討する。 これは、Bubble Sort、Counting Sort、Merge Sort、Quick SortというJavaで実装されたアルゴリズムに焦点を当てている。 カウントソート、マージソート、クイックソートのエネルギー消費の99%以上は、時間的複雑さに依存している。
  論文  参考訳（メタデータ） (2023-11-13T12:38:29Z)
• Sketching Multidimensional Time Series for Fast Discord Mining [37.342885653387604]
  多次元時系列間の不協和音マイニングのためのスケッチを提案する。 提案アルゴリズムはスループットを少なくとも1桁(50X)改善し、近似された解の品質に最小限の影響しか与えない。
  論文  参考訳（メタデータ） (2023-11-05T04:17:34Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing [49.73889315176884]
  本稿では、実行時の複雑さをアクション数にサブリニアに持つ最初の証明可能なLeast-Squares Value Iteration(LSVI)アルゴリズムを提示する。 我々は, 近似最大内積探索理論と強化学習の後悔分析との関係を構築する。
  論文  参考訳（メタデータ） (2021-05-18T05:23:53Z)
• Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
  既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。 提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
  論文  参考訳（メタデータ） (2021-03-03T22:42:15Z)
• Faster Person Re-Identification [68.22203008760269]
  本稿では,新しいハッシュコード検索戦略を定式化することによって,高速ReIDのための新しいソリューションを提案する。 より短いコードを使用して、より正確なReIDのいくつかのトップ候補を洗練するために、より広い一致の類似性を粗くランク付けし、より長いコードを使用する。 2つのデータセットに対する実験結果から,提案手法(CtF)は現在のハッシュReID法よりも8%精度が高いだけでなく,5倍高速であることがわかった。
  論文  参考訳（メタデータ） (2020-08-16T03:02:49Z)
• Fast top-K Cosine Similarity Search through XOR-Friendly Binary Quantization on GPUs [1.5828697880068703]
  このアルゴリズムは、浮動小数点数をエンコードするために、新しいXORフレンドリなバイナリ量子化法を用いる。 実験により,我々の量子化法は前処理時間を短縮し,探索手法の探索速度を近辺のアルゴリズムよりもはるかに速くすることがわかった。
  論文  参考訳（メタデータ） (2020-08-05T08:50: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)
• FastDTW is approximate and Generally Slower than the Algorithm it Approximates [11.689905300531917]
  動的時間ワープ(DTW)距離測定は、ほとんどのドメインにおいて、ほとんどのタスクに最適な尺度である。 最も引用されているアプローチの1つはFastDTWである。 任意の現実的なデータマイニングアプリケーションでは、近似的なFastDTWは正確なDTWよりもはるかに遅い。
  論文  参考訳（メタデータ） (2020-03-25T07:26:02Z)
• Exact Indexing of Time Series under Dynamic Time Warping [1.3300217947936062]
  シーケンス拡張とLB_Keoghをシームレスに組み合わせた新しい下界距離LB_Keogh+を提案する。 不等長列に使用することができ、計算複雑性が低い。 LB_Keogh+に基づいて、DTWの下での時系列の正確なインデックスを考案する。
  論文  参考訳（メタデータ） (2020-02-11T03:34:48Z)

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

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