Succinct Trit-array Trie for Scalable Trajectory Similarity Search

• URL: http://arxiv.org/abs/2005.10917v2
• Date: Mon, 21 Sep 2020 21:01:47 GMT
• Title: Succinct Trit-array Trie for Scalable Trajectory Similarity Search
• Abstract summary: Similarity search of a large collection of trajectories is indispensable for turning these datasets into knowledge. To address this problem, we present the trajectory-indexing succinct trit-array trie (tSTAT) We show that tSTAT performs superiorly in comparison to state-of-the-art similarity search methods.
• Score: 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.

Related papers

• An Exploration Graph with Continuous Refinement for Efficient Multimedia Retrieval [0.0]
  This paper presents a "continuous refining Exploration Graph" (crEG)<n>It is a novel approach for rapidly constructing a compact exploration graph with state-of-the-art search performance.<n>Both algorithms are specifically designed to produce and operate on undirected graphs with even degrees.
  arXiv  Detail & Related papers  (2026-07-30T03:22:17Z)
• ETS: Efficient Tree Search for Inference-Time Scaling [61.553681244572914]
  One promising approach for test-time compute scaling is search against a process reward model. diversity of trajectories in the tree search process affects the accuracy of the search, since increasing diversity promotes more exploration. We propose Efficient Tree Search (ETS), which promotes KV sharing by pruning redundant trajectories while maintaining necessary diverse trajectories.
  arXiv  Detail & Related papers  (2025-02-19T09:30:38Z)
• TISIS : Trajectory Indexing for SImilarity Search [0.7373617024876725]
  Social media platforms enable users to share diverse types of information, including geolocation data. geolocation data can be leveraged to reconstruct the trajectory of a user's visited Points of Interest (POIs) Key requirement is the ability to measure the similarity between such trajectories.
  arXiv  Detail & Related papers  (2024-09-17T15:57:33Z)
• Relation-aware Ensemble Learning for Knowledge Graph Embedding [68.94900786314666]
  We propose to learn an ensemble by leveraging existing methods in a relation-aware manner. exploring these semantics using relation-aware ensemble leads to a much larger search space than general ensemble methods. We propose a divide-search-combine algorithm RelEns-DSC that searches the relation-wise ensemble weights independently.
  arXiv  Detail & Related papers  (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) is one of the most popular approximate nearest neighbor search techniques for high-dimensional spaces. An improved LSH-based index structure, called radius-optimized Locality Sensitive Hashing (roLSH) has been proposed to utilize Machine Learning.
  arXiv  Detail & Related papers  (2022-11-16T18:19:10Z)
• Search to Pass Messages for Temporal Knowledge Graph Completion [97.40256786473516]
  We propose to use neural architecture search (NAS) to design data-specific message passing architecture for temporal knowledge graphs (TKGs) completion. In particular, we develop a generalized framework to explore topological and temporal information in TKGs. We adopt a search algorithm, which trains a supernet structure by sampling single path for efficient search with less cost.
  arXiv  Detail & Related papers  (2022-10-30T04:05:06Z)
• Searching a High-Performance Feature Extractor for Text Recognition Network [92.12492627169108]
  We design a domain-specific search space by exploring principles for having good feature extractors. As the space is huge and complexly structured, no existing NAS algorithms can be applied. We propose a two-stage algorithm to effectively search in the space.
  arXiv  Detail & Related papers  (2022-09-27T03:49:04Z)
• Hierarchical Locality Sensitive Hashing for Structured Data: A Survey [8.045541999149002]
  Locality Sensitive Hashing (LSH) technique has been proposed to provide accurate estimators for various similarity measures between sets or vectors. In this paper, we explore the present progress of the research into hierarchical LSH algorithms.
  arXiv  Detail & Related papers  (2022-04-24T07:18:04Z)
• A Learned Index for Exact Similarity Search in Metric Spaces [25.330353637669386]
  LIMS is proposed to use data clustering and pivot-based data transformation techniques to build learned indexes. Machine learning models are developed to approximate the position of each data record on the disk. Extensive experiments on real-world and synthetic datasets demonstrate the superiority of LIMS compared with traditional indexes.
  arXiv  Detail & Related papers  (2022-04-21T11:24:55Z)
• $\beta$-DARTS: Beta-Decay Regularization for Differentiable Architecture Search [85.84110365657455]
  We propose a simple-but-efficient regularization method, termed as Beta-Decay, to regularize the DARTS-based NAS searching process. Experimental results on NAS-Bench-201 show that our proposed method can help to stabilize the searching process and makes the searched network more transferable across different datasets.
  arXiv  Detail & Related papers  (2022-03-03T11:47:14Z)
• Exploring Complicated Search Spaces with Interleaving-Free Sampling [127.07551427957362]
  In this paper, we build the search algorithm upon a complicated search space with long-distance connections. We present a simple yet effective algorithm named textbfIF-NAS, where we perform a periodic sampling strategy to construct different sub-networks. In the proposed search space, IF-NAS outperform both random sampling and previous weight-sharing search algorithms by a significant margin.
  arXiv  Detail & Related papers  (2021-12-05T06:42:48Z)
• Trilevel Neural Architecture Search for Efficient Single Image Super-Resolution [127.92235484598811]
  This paper proposes a trilevel neural architecture search (NAS) method for efficient single image super-resolution (SR) For modeling the discrete search space, we apply a new continuous relaxation on the discrete search spaces to build a hierarchical mixture of network-path, cell-operations, and kernel-width. An efficient search algorithm is proposed to perform optimization in a hierarchical supernet manner.
  arXiv  Detail & Related papers  (2021-01-17T12:19:49Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2020-05-28T04:12:43Z)
• Efficient Data Analytics on Augmented Similarity Triplets [0.48933451909251774]
  We propose an efficient method to extend the triplets data by inferring the hidden implicit information form the existing data. We also propose a novel set of algorithms for common data analysis tasks based on triplets.
  arXiv  Detail & Related papers  (2019-12-27T11:50:43Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.