Querying Optimal Routes for Group Meetup

Bo Chen, Huaijie Zhu*, Wei Liu, Jian Yin, Wang Chien Lee, Jianliang XU

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Motivated by location-based social networks which allow people to access location-based services as a group, we study a novel variant of optimal sequenced route (OSR) queries, optimal sequenced route for group meetup (OSR-G) queries. OSR-G query aims to find the optimal meeting POI (point of interest) such that the maximum users’ route distance to the meeting POI is minimized after each user visits a number of POIs of specific categories (e.g., gas stations, restaurants, and shopping malls) in a particular order. To process OSR-G queries, we first propose an OSR-Based (OSRB) algorithm as our baseline, which examines every POI in the meeting category and utilizes existing OSR (called E-OSR) algorithm to compute the optimal route for each user to the meeting POI. To address the shortcomings (i.e., requiring to examine every POI in the meeting category) of OSRB, we propose an upper bound based filtering algorithm, called circle filtering (CF) algorithm, which exploits the circle property to filter the unpromising meeting POIs. In addition, we propose a lower bound based pruning (LBP) algorithm, namely LBP-SP which exploits a shortest path lower bound to prune the unqualified meeting POIs to reduce the search space. Furthermore, we develop an approximate algorithm, namely APS, to accelerate OSR-G queries with a good approximation ratio. Finally the experimental results show that both CF and LBP-SP outperform the OSRB algorithm and have high pruning rates. Moreover, the proposed approximate algorithm runs faster than the exact OSR-G algorithms and has a good approximation ratio.

Original languageEnglish
Pages (from-to)180-191
Number of pages12
JournalData Science and Engineering
Volume6
Issue number2
Early online date15 Mar 2021
DOIs
Publication statusPublished - Jun 2021

Scopus Subject Areas

  • Computational Mechanics
  • Computer Science Applications

User-Defined Keywords

  • Group meeting
  • Pruning algorithms
  • Route queries

Fingerprint

Dive into the research topics of 'Querying Optimal Routes for Group Meetup'. Together they form a unique fingerprint.

Cite this