Searching activity trajectory with keywords

Bolong Zheng, Kai Zheng*, Peter I Scheuermann, Xiaofang Zhou, Quoc Viet Hung Nguyen, Chenliang Li

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data has become unprecedentedly available. While finding relevant Point-of-Interests (PoIs) based on users’ locations and query keywords has been extensively studied in the past years, it is, however, largely untouched to explore the keyword queries in the context of activity trajectory database. In this paper, we study the problem of searching activity trajectories by keywords. Given a set of query keywords, a keyword-oriented query for activity trajectory (KOAT) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between KOAT and conventional spatial keyword queries is that there is no query location in KOAT, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel score function, called spatio-textual ranking function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the value of spatio-textual ranking function are proposed. In addition, we extend the proposed techniques of KOAT to support range-based query and order sensitive query, which can be applied for more practical applications. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

Original languageEnglish (US)
Pages (from-to)967-1000
Number of pages34
JournalWorld Wide Web
Volume22
Issue number3
DOIs
StatePublished - May 15 2019

Fingerprint

Trajectories
Scalability
Semantics

Keywords

  • Activity trajectory
  • Query processing
  • Spatial keyword query

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this

Zheng, B., Zheng, K., Scheuermann, P. I., Zhou, X., Nguyen, Q. V. H., & Li, C. (2019). Searching activity trajectory with keywords. World Wide Web, 22(3), 967-1000. https://doi.org/10.1007/s11280-018-0535-8
Zheng, Bolong ; Zheng, Kai ; Scheuermann, Peter I ; Zhou, Xiaofang ; Nguyen, Quoc Viet Hung ; Li, Chenliang. / Searching activity trajectory with keywords. In: World Wide Web. 2019 ; Vol. 22, No. 3. pp. 967-1000.
@article{b508207329b8417fb7439fe07880ef57,
title = "Searching activity trajectory with keywords",
abstract = "Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data has become unprecedentedly available. While finding relevant Point-of-Interests (PoIs) based on users’ locations and query keywords has been extensively studied in the past years, it is, however, largely untouched to explore the keyword queries in the context of activity trajectory database. In this paper, we study the problem of searching activity trajectories by keywords. Given a set of query keywords, a keyword-oriented query for activity trajectory (KOAT) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between KOAT and conventional spatial keyword queries is that there is no query location in KOAT, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel score function, called spatio-textual ranking function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the value of spatio-textual ranking function are proposed. In addition, we extend the proposed techniques of KOAT to support range-based query and order sensitive query, which can be applied for more practical applications. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.",
keywords = "Activity trajectory, Query processing, Spatial keyword query",
author = "Bolong Zheng and Kai Zheng and Scheuermann, {Peter I} and Xiaofang Zhou and Nguyen, {Quoc Viet Hung} and Chenliang Li",
year = "2019",
month = "5",
day = "15",
doi = "10.1007/s11280-018-0535-8",
language = "English (US)",
volume = "22",
pages = "967--1000",
journal = "World Wide Web",
issn = "1386-145X",
publisher = "Springer New York",
number = "3",

}

Zheng, B, Zheng, K, Scheuermann, PI, Zhou, X, Nguyen, QVH & Li, C 2019, 'Searching activity trajectory with keywords', World Wide Web, vol. 22, no. 3, pp. 967-1000. https://doi.org/10.1007/s11280-018-0535-8

Searching activity trajectory with keywords. / Zheng, Bolong; Zheng, Kai; Scheuermann, Peter I; Zhou, Xiaofang; Nguyen, Quoc Viet Hung; Li, Chenliang.

In: World Wide Web, Vol. 22, No. 3, 15.05.2019, p. 967-1000.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Searching activity trajectory with keywords

AU - Zheng, Bolong

AU - Zheng, Kai

AU - Scheuermann, Peter I

AU - Zhou, Xiaofang

AU - Nguyen, Quoc Viet Hung

AU - Li, Chenliang

PY - 2019/5/15

Y1 - 2019/5/15

N2 - Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data has become unprecedentedly available. While finding relevant Point-of-Interests (PoIs) based on users’ locations and query keywords has been extensively studied in the past years, it is, however, largely untouched to explore the keyword queries in the context of activity trajectory database. In this paper, we study the problem of searching activity trajectories by keywords. Given a set of query keywords, a keyword-oriented query for activity trajectory (KOAT) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between KOAT and conventional spatial keyword queries is that there is no query location in KOAT, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel score function, called spatio-textual ranking function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the value of spatio-textual ranking function are proposed. In addition, we extend the proposed techniques of KOAT to support range-based query and order sensitive query, which can be applied for more practical applications. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

AB - Driven by the advances in location positioning techniques and the popularity of location sharing services, semantic enriched trajectory data has become unprecedentedly available. While finding relevant Point-of-Interests (PoIs) based on users’ locations and query keywords has been extensively studied in the past years, it is, however, largely untouched to explore the keyword queries in the context of activity trajectory database. In this paper, we study the problem of searching activity trajectories by keywords. Given a set of query keywords, a keyword-oriented query for activity trajectory (KOAT) returns k trajectories that contain the most relevant keywords to the query and yield the least travel effort in the meantime. The main difference between KOAT and conventional spatial keyword queries is that there is no query location in KOAT, which means the search area cannot be localized. To capture the travel effort in the context of query keywords, a novel score function, called spatio-textual ranking function, is first defined. Then we develop a hybrid index structure called GiKi to organize the trajectories hierarchically, which enables pruning the search space by spatial and textual similarity simultaneously. Finally an efficient search algorithm and fast evaluation of the value of spatio-textual ranking function are proposed. In addition, we extend the proposed techniques of KOAT to support range-based query and order sensitive query, which can be applied for more practical applications. The results of our empirical studies based on real check-in datasets demonstrate that our proposed index and algorithms can achieve good scalability.

KW - Activity trajectory

KW - Query processing

KW - Spatial keyword query

UR - http://www.scopus.com/inward/record.url?scp=85043706462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85043706462&partnerID=8YFLogxK

U2 - 10.1007/s11280-018-0535-8

DO - 10.1007/s11280-018-0535-8

M3 - Article

AN - SCOPUS:85043706462

VL - 22

SP - 967

EP - 1000

JO - World Wide Web

JF - World Wide Web

SN - 1386-145X

IS - 3

ER -

Zheng B, Zheng K, Scheuermann PI, Zhou X, Nguyen QVH, Li C. Searching activity trajectory with keywords. World Wide Web. 2019 May 15;22(3):967-1000. https://doi.org/10.1007/s11280-018-0535-8