論文の概要: Succinct Trit-array Trie for Scalable Trajectory Similarity Search
- arxiv url: http://arxiv.org/abs/2005.10917v2
- Date: Mon, 21 Sep 2020 21:01:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-01 00:10:56.159942
- Title: Succinct Trit-array Trie for Scalable Trajectory Similarity Search
- Title(参考訳): 拡張軌道類似性探索のためのサクシンクトリトアレイトライ
- Authors: Shunsuke Kanda, Koh Takeuchi, Keisuke Fujii and Yasuo Tabei
- Abstract要約: 膨大なトラジェクトリの集合の類似性探索は、これらのデータセットを知識に変えるのに不可欠である。
この問題に対処するため, トラジェクトリトアレイトリエ (tSTAT) のトラジェクトリ・インデクシングについて述べる。
tSTATは,最先端の類似性探索法と比較して優れた性能を示す。
- 参考スコア(独自算出の注目度): 3.2197141014728805
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Massive datasets of spatial trajectories representing the mobility of a
diversity of moving objects are ubiquitous in research and industry. Similarity
search of a large collection of trajectories is indispensable for turning these
datasets into knowledge. Locality sensitive hashing (LSH) is a powerful
technique for fast similarity searches. Recent methods employ LSH and attempt
to realize an efficient similarity search of trajectories; however, those
methods are inefficient in terms of search time and memory when applied to
massive datasets. To address this problem, we present the trajectory-indexing
succinct trit-array trie (tSTAT), which is a scalable method leveraging LSH for
trajectory similarity searches. tSTAT quickly performs the search on a tree
data structure called trie. We also present two novel techniques that enable to
dramatically enhance the memory efficiency of tSTAT. One is a node reduction
technique that substantially omits redundant trie nodes while maintaining the
time performance. The other is a space-efficient representation that leverages
the idea behind succinct data structures (i.e., a compressed data structure
supporting fast data operations). We experimentally test tSTAT on its ability
to retrieve similar trajectories for a query from large collections of
trajectories and show that tSTAT performs superiorly in comparison to
state-of-the-art similarity search methods.
- Abstract(参考訳): 移動物体の多様性のモビリティを表す空間軌道の膨大なデータセットは、研究や産業においてユビキタスである。
膨大なトラジェクトリの集合の類似性探索は、これらのデータセットを知識に変えるのに不可欠である。
局所性センシティブハッシュ(lsh)は高速類似性検索のための強力な技術である。
近年の手法ではlshを用い, トラジェクタの効率的な類似性探索を試みているが, 大規模データセットに適用した場合の探索時間やメモリの面では非効率である。
そこで本研究では,lshを軌道類似性探索に用いるスケーラブルな手法であるtstat(traveal-indexing succinct trit-array trie)を提案する。
tSTATは、Trueと呼ばれるツリーデータ構造を素早く検索する。
また,tSTATのメモリ効率を劇的に向上させる2つの新しい手法を提案する。
1つは、時間性能を維持しながら冗長なトライノードを実質的に省略するノード削減技術である。
もう一つは、簡潔なデータ構造(すなわち高速なデータ操作をサポートする圧縮データ構造)の背景にあるアイデアを活用する空間効率の表現である。
我々は, tSTAT を用いて, 大量のトラジェクトリからクエリに対して類似したトラジェクトリを検索できることを実験的に検証し, 最先端の類似性探索法と比較して, tSTAT が優れていることを示す。
関連論文リスト
- Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
我々は,既存の手法を関係性に配慮した方法で活用し,アンサンブルを学習することを提案する。
関係認識アンサンブルを用いてこれらのセマンティクスを探索すると、一般的なアンサンブル法よりもはるかに大きな検索空間が得られる。
本稿では,リレーショナルなアンサンブル重みを独立に検索する分割探索合成アルゴリズムRelEns-DSCを提案する。
論文 参考訳(メタデータ) (2023-10-13T07:40:12Z) - Experimental Analysis of Machine Learning Techniques for Finding Search
Radius in Locality Sensitive Hashing [0.9137554315375919]
局所感性ハッシュ (Locality Sensitive Hashing, LSH) は、高次元空間の近接探索技術として最も一般的なものの一つである。
機械学習を利用するために、半径最適化局所感性ハッシュ(roLSH)と呼ばれる改良されたLSHベースのインデックス構造が提案されている。
論文 参考訳(メタデータ) (2022-11-16T18:19:10Z) - Search to Pass Messages for Temporal Knowledge Graph Completion [97.40256786473516]
我々は、時間知識グラフ(TKG)の補完のために、NAS(Neural Architecture Search)を用いて、データ固有のメッセージパッシングアーキテクチャを設計することを提案する。
特に,TKGにおけるトポロジカルおよび時間的情報を探るための一般化されたフレームワークを開発する。
より低コストで効率的な探索のために単一経路をサンプリングし,スーパーネット構造を訓練する探索アルゴリズムを採用する。
論文 参考訳(メタデータ) (2022-10-30T04:05:06Z) - Searching a High-Performance Feature Extractor for Text Recognition
Network [92.12492627169108]
優れた特徴抽出器を持つための原理を探求し,ドメイン固有の検索空間を設計する。
空間は巨大で複雑な構造であるため、既存のNASアルゴリズムを適用することはできない。
本研究では,空間内を効率的に探索する2段階のアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-27T03:49:04Z) - A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
LIMSは、学習したインデックスを構築するために、データクラスタリングとピボットベースのデータ変換技術を使用することが提案されている。
機械学習モデルはディスク上の各データレコードの位置を近似するために開発された。
実世界のデータセットと合成データセットに関する大規模な実験は、従来の指標と比較してLIMSの優位性を示している。
論文 参考訳(メタデータ) (2022-04-21T11:24:55Z) - $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture
Search [85.84110365657455]
本研究では,DARTSに基づくNAS探索過程を正規化するために,ベータデカイと呼ばれるシンプルだが効率的な正規化手法を提案する。
NAS-Bench-201の実験結果から,提案手法は探索過程の安定化に有効であり,探索されたネットワークを異なるデータセット間で転送しやすくする。
論文 参考訳(メタデータ) (2022-03-03T11:47:14Z) - Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
本稿では,長距離接続を伴う複雑な検索空間上に探索アルゴリズムを構築する。
我々はtextbfIF-NAS という単純なアルゴリズムを提案し、異なるサブネットワークを構築するために周期的なサンプリング戦略を実行する。
提案した探索空間において、IF-NASはランダムサンプリングと従来の重み付け検索のアルゴリズムを有意差で上回っている。
論文 参考訳(メタデータ) (2021-12-05T06:42:48Z) - Trilevel Neural Architecture Search for Efficient Single Image
Super-Resolution [127.92235484598811]
本稿では,高効率単一画像超解像(SR)のための3レベルニューラルネットワーク探索法を提案する。
離散探索空間をモデル化するために、離散探索空間に新たな連続緩和を適用し、ネットワークパス、セル操作、カーネル幅の階層的混合を構築する。
階層型スーパーネット方式による最適化を行うため,効率的な探索アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-17T12:19:49Z) - A Practical Index Structure Supporting Fr\'echet Proximity Queries Among
Trajectories [1.9335262420787858]
我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。
計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。
本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
論文 参考訳(メタデータ) (2020-05-28T04:12:43Z) - Wise Sliding Window Segmentation: A classification-aided approach for
trajectory segmentation [11.174536284571802]
ワイズスライディングウィンドウ(WS-II)と呼ばれる教師付き軌道分割アルゴリズムを提案する。
WS-IIは軌道座標を処理し、空間と時間の変化を見つけ、エラー信号を生成する。
提案手法は,異なる領域の3つの実データに対して評価する。
論文 参考訳(メタデータ) (2020-03-23T12:55:40Z) - Efficient Data Analytics on Augmented Similarity Triplets [0.48933451909251774]
本稿では,既存のデータから隠された暗黙の情報を推測することで,三重項データを効率的に拡張する手法を提案する。
また,三重項に基づく共通データ解析タスクのための新しいアルゴリズムも提案する。
論文 参考訳(メタデータ) (2019-12-27T11:50:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。