Tanzima Hashem
ABSTRACT
A group of friends located at their working places may want to plan a trip to visit a shopping center, have dinner at a restaurant, watch a movie at a theater, and then finally return to their homes with the minimum total trip distance. For a group of spatially dispersed users a group trip planning (GTP) query returns points of interests (POIs) of different types such as a shopping center, a restaurant and a movie theater that minimize the aggregate trip distance for the group. The aggregate trip distance could be the sum or maximum of the trip distances of all users in the group, where the users travel from their source locations via the jointly visited POIs to their individual destinations. In this paper, we develop both optimal and approximation algorithms for GTP queries for both Euclidean space and road networks. Processing GTP queries in real time is a computational challenge as trips involve POIs of multiple types and computation of aggregate trip distances. We develop novel techniques to refine the POI search space for a GTP query based on geometric properties of ellipses, which in turn significantly reduces the number of aggregate trip distance computations. An extensive set of experiments on a real and synthetic datasets shows that our approach outperforms the most competitive approach on an average by three orders of magnitude in terms of processing time.
- California road network data: http://www.cs.fsu.edu/~lifeifei/tpq.html.Google Scholar
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. ThetextscR*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec., 19(2):322--331, 1990. Google ScholarDigital Library
- I. R. Brilhante, J. A. F. de Macêdo, F. M. Nardini, R. Perego, and C. Renso. Where shall we go today?: planning touristic tours with tripbuilder. In CIKM, pages 757--762, 2013. Google ScholarDigital Library
- H. Chen, W. Ku, M. Sun, and R. Zimmermann. The multi-rule partial sequenced route query. In SIGSpatial, page 10, 2008. Google ScholarDigital Library
- C.-Y. Chow, M. F. Mokbel, and W. G. Aref. Casper*: Query processing for location services without compromising privacy. TODS, 34(4):24:1--24:48, 2009. Google ScholarDigital Library
- A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- T. Hashem, M. E. Ali, L. Kulik, E. Tanin, and A. Quattrone. Protecting privacy for group nearest neighbor queries with crowdsourced data and computing. In UbiComp, pages 559--562, 2013. Google ScholarDigital Library
- T. Hashem, T. Hashem, M. E. Ali, and L. Kulik. Group trip planning queries in spatial databases. In SSTD, pages 259--276, 2013. Google ScholarDigital Library
- T. Hashem and L. Kulik. Safeguarding location privacy in wireless ad-hoc networks. In Ubicomp, pages 372--390, 2007. Google ScholarDigital Library
- T. Hashem, L. Kulik, and R. Zhang. Privacy preserving group nearest neighbor queries. In EDBT, pages 489--500, 2010. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Ranking in spatial databases. In SSD, pages 83--95, 1995. Google ScholarDigital Library
- R. Levin and Y. Kanza. TARS: traffic-aware route search. GeoInformatica, 18(3):461--500, 2014. Google ScholarDigital Library
- F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S. Teng. On trip planning queries in spatial databases. In SSTD, pages 273--290, 2005. Google ScholarDigital Library
- H. Li, H. Lu, B. Huang, and Z. Huang. Two ellipse-based pruning methods for group nearest neighbor queries. In GIS, pages 192--199, 2005. Google ScholarDigital Library
- J. Li, M. L. Yiu, and N. Mamoulis. Efficient notification of meeting points for moving groups via independent safe regions. In ICDE, pages 422--433, 2013. Google ScholarDigital Library
- X. Ma, S. Shekhar, H. Xiong, and P. Zhang. Exploiting a page-level upper bound for multi-type nearest neighbor queries. In GIS, pages 179--186, 2006. Google ScholarDigital Library
- H. Mahmud, A. M. Amin, M. E. Ali, T. Hashem, and S. Nutanong. A group based approach for path queries in road networks. In SSTD, pages 367--385, 2013. Google ScholarDigital Library
- S. Namnandorj, H. Chen, K. Furuse, and N. Ohbo. Efficient bounds in finding aggregate nearest neighbors. In DEXA, pages 693--700, 2008. Google ScholarDigital Library
- D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis. Group nearest neighbor queries. In ICDE, page 301, 2004. Google ScholarDigital Library
- D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao. Query processing in spatial network databases. In VLDB, pages 802--813, 2003. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Engineering generalized shortest path queries. In ICDE, pages 949--960, 2013. Google ScholarDigital Library
- M. N. Rice and V. J. Tsotras. Parameterized algorithms for generalized traveling salesman problems in road networks. In SIGSPATIAL, pages 114--123, 2013. Google ScholarDigital Library
- T. Seidl and H. Kriegel. Optimal multi-step k-nearest neighbor search. In SIGMOD, pages 154--165, 1998. Google ScholarDigital Library
- M. Sharifzadeh, M. Kolahdouzan, and C. Shahabi. The optimal sequenced route query. The VLDB Journal, 17(4):765--787, 2008. Google ScholarDigital Library
- N. Sultana, T. Hashem, and L. Kulik. Group nearest neighbor queries in the presence of obstacles. In SIGSPATIAL, pages 481--484, 2014. Google ScholarDigital Library
- M. Terrovitis, S. Bakiras, D. Papadias, and K. Mouratidis. Constrained shortest path computation. In SSTD, pages 181--199, 2005. Google ScholarDigital Library
- M. L. Yiu, N. Mamoulis, and D. Papadias. Aggregate nearest neighbor queries in road networks. IEEE TKDE, 17:820--833, 2005. Google ScholarDigital Library
- Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In SIGMOD, pages 181--192, 2003. Google ScholarDigital Library
Index Terms
- Efficient Computation of Trips with Friends and Families
Recommendations
Fairness Driven Efficient Algorithms for Sequenced Group Trip Planning Query Problem
AAMAS '23: Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent SystemsThe Group Trip Planning Query Problem (GTP) is a well-researched spatial database problem. Given a city road network with Point-of-Interests (PoIs) representing vertices divided into different categories, GTP aims to suggest one PoI from each category to ...
Activity-aware Ridesharing Group Trip Planning Queries for Flexible POIs
In recent years, ridesharing has become a popular model that enables users to share their rides with others. In this article, we introduce a novel ridesharing service, an Activity-aware Ridesharing Group Trip Planning (ARGTP) query, in road networks ...
Efficient Scheduling of Generalized Group Trips in Road Networks
Special Issue on Urban Mobility: Algorithms and SystemsIn this article, we introduce generalized group trip scheduling (GGTS) queries that enable friends and families to perform activities at different points of interest (POIs), such as a shopping center, a restaurant and a pharmacy with the minimum total ...
Comments