A Hybrid spatio-temporal data indexing method for trajectory databases

Shengnan Ke, Jun Gong, Songnian Li, Qing Zhu, Xintao Liu, Yeting Zhang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

34 Citations (Scopus)

Abstract

In recent years, there has been tremendous growth in the field of indoor and outdoor positioning sensors continuously producing huge volumes of trajectory data that has been used in many fields such as location-based services or location intelligence. Trajectory data is massively increased and semanticallycomplicated, which poses a great challenge on spatio-temporal data indexing. This paper proposes a spatio-temporal data indexing method, named HBSTR-tree, which is a hybrid index structure comprising spatio-temporal R-tree, B*-tree and Hash table. To improve the index generation efficiency, rather than directly inserting trajectory points, we group consecutive trajectory points as nodes according to their spatio-temporal semantics and then insert them into spatio-temporal R-tree as leaf nodes. Hash table is used to manage the latest leaf nodes to reduce the frequency of insertion. A new spatio-temporal interval criterion and a new node-choosing sub-algorithm are also proposed to optimize spatio-temporalR-tree structures. In addition, a B*-tree sub-index of leaf nodes is built to query the trajectories of targeted objects efficiently. Furthermore, a database storage scheme based on a NoSQL-type DBMS is also proposed for the purpose of cloud storage. Experimentalresults prove that HBSTR-tree outperforms TB*-tree in some aspects such as generation efficiency, query performance and query type.
Original languageEnglish
Pages (from-to)12990-13005
Number of pages16
JournalSensors (Switzerland)
Volume14
Issue number7
DOIs
Publication statusPublished - 21 Jul 2014
Externally publishedYes

Keywords

  • B*-tree
  • Cloud storage
  • R-tree
  • Spatio-temporal data index
  • Trajectory

ASJC Scopus subject areas

  • Analytical Chemistry
  • Atomic and Molecular Physics, and Optics
  • Biochemistry
  • Instrumentation
  • Electrical and Electronic Engineering

Cite this