抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
連続Fr’echet距離の下での時系列に対する近似近傍データ構造を研究した。達成可能な近似因子c>1およびクエリ半径rに対して,近似近傍データ構造を用いて,R(高時系列)におけるn曲線を前処理し,計算量mの各々を,Fr’echet距離cr内にある曲線を返すことによって,また,距離r内の入力に曲線が存在しないことのいずれかによって,複雑性kの曲線による質問に答える。両方の場合,回答は正しい。著者らの最初のデータ構造は,(5+ε)近似因子を達成し,nで空間を使用する。O(π ̄* ̄{-1}) ̄{k}+O(nm)とO(k)の問い合わせ時間がある。第二のデータ構造は(2+ε)近似因子を達成し,nで空間を使用する。O(m/kε) ̄k+O(nm)とO(k.2 ̄k)のクエリ時間がある。第3の肯定的結果は,O(nlogn+nm)における空間とO(klogn)におけるクエリ時間を達成する局所性感性ハッシュに基づく確率的データ構造であり,それはO(k)における近似因子によって質問を答えた。これらのデータ構造の全ては,Fr’echet距離の下でのクラスタリング時系列の問題のために最初に導入された署名の概念を利用する。さらに,この問題に対する下限を示した。2以下の近似因子を達成し,Lまでアーク長の曲線をサポートし,一定数のプローブを用いてクエリを回答するデータ構造を考察した。単語サイズに関する合理的な仮定の下で,そのようなデータ構造にはL ̄Ω(k)における空間が必要であることを示した。【JST・京大機械翻訳】
