Continuous Spatial Query Processing: A Survey of Safe Region Based Techniques

Jianzhong Qi, Rui Zhang, Christian Søndergaard Jensen, Ramamohanarao Kotagiri, Jiayuan He

Research output: Contribution to journalJournal articleResearchpeer-review

2 Citations (Scopus)

Abstract

In the past decade, positioning system-enabled devices such as smartphones have become most prevalent. This functionality brings the increasing popularity of location-based services in business as well as daily applications such as navigation, targeted advertising, and location-based social networking. Continuous spatial queries serve as a building block for location-based services. As an example, an Uber driver may want to be kept aware of the nearest customers or service stations. Continuous spatial queries require updates to the query result as the query or data objects are moving. This poses challenges to the query efficiency, which is crucial to the user experience of a service. A large number of approaches address this efficiency issue using the concept of safe region. A safe region is a region within which arbitrary movement of an object leaves the query result unchanged. Such a region helps reduce the frequency of query result update and hence improves query efficiency. As a result, safe region-based approaches have been popular for processing various types of continuous spatial queries. Safe regions have interesting theoretical properties and are worth in-depth analysis. We provide a comparative study of safe region-based approaches. We describe how safe regions are computed for different types of continuous spatial queries, showing how they improve query efficiency. We compare the different safe region-based approaches and discuss possible further improvements.
Original languageEnglish
Article number64
JournalA C M Computing Surveys
Volume51
Issue number3
Number of pages39
ISSN0360-0300
DOIs
Publication statusPublished - 2018

Fingerprint

Query processing
Query Processing
Query
Location based services
Filling stations
Smartphones
Marketing
Navigation
Update
Processing
Social Networking
Industry
User Experience
Building Blocks
Positioning
Comparative Study
Driver
Customers

Keywords

  • Continuous kNN query
  • Continuous range query
  • Moving object
  • Moving query

Cite this

Qi, Jianzhong ; Zhang, Rui ; Jensen, Christian Søndergaard ; Kotagiri, Ramamohanarao ; He, Jiayuan. / Continuous Spatial Query Processing : A Survey of Safe Region Based Techniques. In: A C M Computing Surveys. 2018 ; Vol. 51, No. 3.
@article{0a3c966e9e064ac99faf29e0ffe284bf,
title = "Continuous Spatial Query Processing: A Survey of Safe Region Based Techniques",
abstract = "In the past decade, positioning system-enabled devices such as smartphones have become most prevalent. This functionality brings the increasing popularity of location-based services in business as well as daily applications such as navigation, targeted advertising, and location-based social networking. Continuous spatial queries serve as a building block for location-based services. As an example, an Uber driver may want to be kept aware of the nearest customers or service stations. Continuous spatial queries require updates to the query result as the query or data objects are moving. This poses challenges to the query efficiency, which is crucial to the user experience of a service. A large number of approaches address this efficiency issue using the concept of safe region. A safe region is a region within which arbitrary movement of an object leaves the query result unchanged. Such a region helps reduce the frequency of query result update and hence improves query efficiency. As a result, safe region-based approaches have been popular for processing various types of continuous spatial queries. Safe regions have interesting theoretical properties and are worth in-depth analysis. We provide a comparative study of safe region-based approaches. We describe how safe regions are computed for different types of continuous spatial queries, showing how they improve query efficiency. We compare the different safe region-based approaches and discuss possible further improvements.",
keywords = "Continuous kNN query, Continuous range query, Moving object, Moving query",
author = "Jianzhong Qi and Rui Zhang and Jensen, {Christian S{\o}ndergaard} and Ramamohanarao Kotagiri and Jiayuan He",
year = "2018",
doi = "10.1145/3193835",
language = "English",
volume = "51",
journal = "A C M Computing Surveys",
issn = "0360-0300",
publisher = "Association for Computing Machinery",
number = "3",

}

Continuous Spatial Query Processing : A Survey of Safe Region Based Techniques. / Qi, Jianzhong; Zhang, Rui; Jensen, Christian Søndergaard; Kotagiri, Ramamohanarao; He, Jiayuan.

In: A C M Computing Surveys, Vol. 51, No. 3, 64, 2018.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Continuous Spatial Query Processing

T2 - A Survey of Safe Region Based Techniques

AU - Qi, Jianzhong

AU - Zhang, Rui

AU - Jensen, Christian Søndergaard

AU - Kotagiri, Ramamohanarao

AU - He, Jiayuan

PY - 2018

Y1 - 2018

N2 - In the past decade, positioning system-enabled devices such as smartphones have become most prevalent. This functionality brings the increasing popularity of location-based services in business as well as daily applications such as navigation, targeted advertising, and location-based social networking. Continuous spatial queries serve as a building block for location-based services. As an example, an Uber driver may want to be kept aware of the nearest customers or service stations. Continuous spatial queries require updates to the query result as the query or data objects are moving. This poses challenges to the query efficiency, which is crucial to the user experience of a service. A large number of approaches address this efficiency issue using the concept of safe region. A safe region is a region within which arbitrary movement of an object leaves the query result unchanged. Such a region helps reduce the frequency of query result update and hence improves query efficiency. As a result, safe region-based approaches have been popular for processing various types of continuous spatial queries. Safe regions have interesting theoretical properties and are worth in-depth analysis. We provide a comparative study of safe region-based approaches. We describe how safe regions are computed for different types of continuous spatial queries, showing how they improve query efficiency. We compare the different safe region-based approaches and discuss possible further improvements.

AB - In the past decade, positioning system-enabled devices such as smartphones have become most prevalent. This functionality brings the increasing popularity of location-based services in business as well as daily applications such as navigation, targeted advertising, and location-based social networking. Continuous spatial queries serve as a building block for location-based services. As an example, an Uber driver may want to be kept aware of the nearest customers or service stations. Continuous spatial queries require updates to the query result as the query or data objects are moving. This poses challenges to the query efficiency, which is crucial to the user experience of a service. A large number of approaches address this efficiency issue using the concept of safe region. A safe region is a region within which arbitrary movement of an object leaves the query result unchanged. Such a region helps reduce the frequency of query result update and hence improves query efficiency. As a result, safe region-based approaches have been popular for processing various types of continuous spatial queries. Safe regions have interesting theoretical properties and are worth in-depth analysis. We provide a comparative study of safe region-based approaches. We describe how safe regions are computed for different types of continuous spatial queries, showing how they improve query efficiency. We compare the different safe region-based approaches and discuss possible further improvements.

KW - Continuous kNN query

KW - Continuous range query

KW - Moving object

KW - Moving query

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

U2 - 10.1145/3193835

DO - 10.1145/3193835

M3 - Journal article

VL - 51

JO - A C M Computing Surveys

JF - A C M Computing Surveys

SN - 0360-0300

IS - 3

M1 - 64

ER -