IG-Tree

an efficient spatial keyword index for planning best path queries on road networks

Anasthasia Agnes Haryanto, Md Saiful Islam, David Taniar, Muhammad Aamir Cheema

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Due to the popularity of Spatial Databases, many search engine providers have started to expand their text searching capability to include geographical information. Because of this reason, many new queries on spatial objects affiliated with textual information, known as the Spatial Keyword Queries, have taken significant research interest in the past years. Unfortunately, most of existing works on Spatial Keyword Queries only focus on objects retrieval. There is barely any work on route planning queries, even though route planning is often needed in our daily life. In this research, we propose the Best Path Query, which we find the best optimum route from two different spatial locations that visits or avoids the objects that are specified by the textual data given by the user. We show that Best Path Query is an NP-Hard problem. We propose an efficient indexing technique, namely IG-Tree, and three different algorithms with different trade-offs to process the Best Path Queries on Road Networks. Our extensive experimental study demonstrates the efficiency and accuracy of our proposed approach.

Original languageEnglish
Pages (from-to)1359-1399
Number of pages41
JournalWorld Wide Web-Internet and Web Information Systems
Volume22
Issue number4
DOIs
Publication statusPublished - Jul 2019

Keywords

  • Best path
  • IG-Tree
  • Road networks
  • Spatial databases
  • Spatial keywords
  • Trip planning queries

Cite this

@article{9ae3e54c8044424a92977b15567a296c,
title = "IG-Tree: an efficient spatial keyword index for planning best path queries on road networks",
abstract = "Due to the popularity of Spatial Databases, many search engine providers have started to expand their text searching capability to include geographical information. Because of this reason, many new queries on spatial objects affiliated with textual information, known as the Spatial Keyword Queries, have taken significant research interest in the past years. Unfortunately, most of existing works on Spatial Keyword Queries only focus on objects retrieval. There is barely any work on route planning queries, even though route planning is often needed in our daily life. In this research, we propose the Best Path Query, which we find the best optimum route from two different spatial locations that visits or avoids the objects that are specified by the textual data given by the user. We show that Best Path Query is an NP-Hard problem. We propose an efficient indexing technique, namely IG-Tree, and three different algorithms with different trade-offs to process the Best Path Queries on Road Networks. Our extensive experimental study demonstrates the efficiency and accuracy of our proposed approach.",
keywords = "Best path, IG-Tree, Road networks, Spatial databases, Spatial keywords, Trip planning queries",
author = "Haryanto, {Anasthasia Agnes} and Islam, {Md Saiful} and David Taniar and Cheema, {Muhammad Aamir}",
year = "2019",
month = "7",
doi = "10.1007/s11280-018-0643-5",
language = "English",
volume = "22",
pages = "1359--1399",
journal = "World Wide Web-Internet and Web Information Systems",
issn = "1386-145X",
publisher = "Springer-Verlag London Ltd.",
number = "4",

}

IG-Tree : an efficient spatial keyword index for planning best path queries on road networks. / Haryanto, Anasthasia Agnes; Islam, Md Saiful; Taniar, David; Cheema, Muhammad Aamir.

In: World Wide Web-Internet and Web Information Systems, Vol. 22, No. 4, 07.2019, p. 1359-1399.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - IG-Tree

T2 - an efficient spatial keyword index for planning best path queries on road networks

AU - Haryanto, Anasthasia Agnes

AU - Islam, Md Saiful

AU - Taniar, David

AU - Cheema, Muhammad Aamir

PY - 2019/7

Y1 - 2019/7

N2 - Due to the popularity of Spatial Databases, many search engine providers have started to expand their text searching capability to include geographical information. Because of this reason, many new queries on spatial objects affiliated with textual information, known as the Spatial Keyword Queries, have taken significant research interest in the past years. Unfortunately, most of existing works on Spatial Keyword Queries only focus on objects retrieval. There is barely any work on route planning queries, even though route planning is often needed in our daily life. In this research, we propose the Best Path Query, which we find the best optimum route from two different spatial locations that visits or avoids the objects that are specified by the textual data given by the user. We show that Best Path Query is an NP-Hard problem. We propose an efficient indexing technique, namely IG-Tree, and three different algorithms with different trade-offs to process the Best Path Queries on Road Networks. Our extensive experimental study demonstrates the efficiency and accuracy of our proposed approach.

AB - Due to the popularity of Spatial Databases, many search engine providers have started to expand their text searching capability to include geographical information. Because of this reason, many new queries on spatial objects affiliated with textual information, known as the Spatial Keyword Queries, have taken significant research interest in the past years. Unfortunately, most of existing works on Spatial Keyword Queries only focus on objects retrieval. There is barely any work on route planning queries, even though route planning is often needed in our daily life. In this research, we propose the Best Path Query, which we find the best optimum route from two different spatial locations that visits or avoids the objects that are specified by the textual data given by the user. We show that Best Path Query is an NP-Hard problem. We propose an efficient indexing technique, namely IG-Tree, and three different algorithms with different trade-offs to process the Best Path Queries on Road Networks. Our extensive experimental study demonstrates the efficiency and accuracy of our proposed approach.

KW - Best path

KW - IG-Tree

KW - Road networks

KW - Spatial databases

KW - Spatial keywords

KW - Trip planning queries

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

U2 - 10.1007/s11280-018-0643-5

DO - 10.1007/s11280-018-0643-5

M3 - Article

VL - 22

SP - 1359

EP - 1399

JO - World Wide Web-Internet and Web Information Systems

JF - World Wide Web-Internet and Web Information Systems

SN - 1386-145X

IS - 4

ER -