Cargando…

A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases

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 seman...

Descripción completa

Detalles Bibliográficos
Autores principales: Ke, Shengnan, Gong, Jun, Li, Songnian, Zhu, Qing, Liu, Xintao, Zhang, Yeting
Formato: Online Artículo Texto
Lenguaje:English
Publicado: MDPI 2014
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4168421/
https://www.ncbi.nlm.nih.gov/pubmed/25051028
http://dx.doi.org/10.3390/s140712990
_version_ 1782335538923044864
author Ke, Shengnan
Gong, Jun
Li, Songnian
Zhu, Qing
Liu, Xintao
Zhang, Yeting
author_facet Ke, Shengnan
Gong, Jun
Li, Songnian
Zhu, Qing
Liu, Xintao
Zhang, Yeting
author_sort Ke, Shengnan
collection PubMed
description 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 semantically complicated, 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-temporal R-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. Experimental results prove that HBSTR-tree outperforms TB*-tree in some aspects such as generation efficiency, query performance and query type.
format Online
Article
Text
id pubmed-4168421
institution National Center for Biotechnology Information
language English
publishDate 2014
publisher MDPI
record_format MEDLINE/PubMed
spelling pubmed-41684212014-09-19 A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases Ke, Shengnan Gong, Jun Li, Songnian Zhu, Qing Liu, Xintao Zhang, Yeting Sensors (Basel) Article 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 semantically complicated, 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-temporal R-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. Experimental results prove that HBSTR-tree outperforms TB*-tree in some aspects such as generation efficiency, query performance and query type. MDPI 2014-07-21 /pmc/articles/PMC4168421/ /pubmed/25051028 http://dx.doi.org/10.3390/s140712990 Text en © 2014 by the authors; licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution license (http://creativecommons.org/licenses/by/3.0/).
spellingShingle Article
Ke, Shengnan
Gong, Jun
Li, Songnian
Zhu, Qing
Liu, Xintao
Zhang, Yeting
A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title_full A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title_fullStr A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title_full_unstemmed A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title_short A Hybrid Spatio-Temporal Data Indexing Method for Trajectory Databases
title_sort hybrid spatio-temporal data indexing method for trajectory databases
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4168421/
https://www.ncbi.nlm.nih.gov/pubmed/25051028
http://dx.doi.org/10.3390/s140712990
work_keys_str_mv AT keshengnan ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT gongjun ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT lisongnian ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT zhuqing ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT liuxintao ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT zhangyeting ahybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT keshengnan hybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT gongjun hybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT lisongnian hybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT zhuqing hybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT liuxintao hybridspatiotemporaldataindexingmethodfortrajectorydatabases
AT zhangyeting hybridspatiotemporaldataindexingmethodfortrajectorydatabases