論文の概要: 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 が優れていることを示す。
関連論文リスト
- ETS: Efficient Tree Search for Inference-Time Scaling [61.553681244572914]
テストタイムの計算スケーリングにおいて有望なアプローチのひとつは、プロセス報酬モデルに対する検索である。
木探索過程における軌跡の多様性は、多様性の増大がさらなる探索を促進するため、探索の精度に影響を与える。
本稿では,冗長なトラジェクトリを抽出し,必要な多様なトラジェクトリを維持しながら,KVの共有を促進する効率的なツリー探索(ETS)を提案する。
論文 参考訳(メタデータ) (2025-02-19T09:30:38Z) - TISIS : Trajectory Indexing for SImilarity Search [0.7373617024876725]
ソーシャルメディアプラットフォームでは、位置情報データを含むさまざまな種類の情報を共有できる。
位置情報データは、ユーザの訪問した関心のポイント(POI)の軌跡を再構築するために利用することができる
鍵となる要件は、そのような軌道間の類似度を測定する能力である。
論文 参考訳(メタデータ) (2024-09-17T15:57:33Z) - 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) - 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) - Efficient Data Analytics on Augmented Similarity Triplets [0.48933451909251774]
本稿では,既存のデータから隠された暗黙の情報を推測することで,三重項データを効率的に拡張する手法を提案する。
また,三重項に基づく共通データ解析タスクのための新しいアルゴリズムも提案する。
論文 参考訳(メタデータ) (2019-12-27T11:50:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。