Abstract
With the deep penetration of smartphones and geo-locating devices, ridesharing is envisioned as a promising solution to transportation-related problems in metropolitan cities, such as traffic congestion and air pollution. Despite the potential to provide significant societal and environmental benefits, ridesharing has not so far been as popular as expected. Notable barriers include social discomfort and safety concerns when traveling with strangers. To overcome these barriers, in this paper, we propose a new type of Social-aware Ridesharing Group (SaRG) queries which retrieve a group of riders by taking into account their social connections and spatial proximities. While SaRG queries are of practical usefulness, we prove that, however, the SaRG query problem is NP-hard. Thus, we design an efficient algorithm with a set of powerful pruning techniques to tackle this problem. We also present several incremental strategies to accelerate the search speed by reducing repeated computations. Moreover, we propose a novel index tailored to our problem to further speed up query processing. Experimental results on real datasets show that our proposed algorithms achieve desirable performance.
Original language | English |
---|---|
Pages (from-to) | 646-659 |
Number of pages | 14 |
Journal | IEEE Transactions on Services Computing |
Volume | 10 |
Issue number | 4 |
Early online date | 14 Dec 2015 |
DOIs | |
Publication status | Published - 1 Jul 2017 |
Scopus Subject Areas
- Hardware and Architecture
- Computer Science Applications
- Computer Networks and Communications
- Information Systems and Management
User-Defined Keywords
- group queries
- Location-based services
- query processing
- ridesharing
- social acquaintance