ABSTRACT
In this paper, we introduce obstructed group nearest neighbor (OGNN) queries, that enable a group to meet at a point of interest (e.g., a restaurant) with the minimum aggregate travel distance in an obstructed space. In recent years, researchers have focused on developing algorithms for processing GNN queries in the Euclidean space and road networks, which ignore the impact of obstacles such as buildings and lakes in computing distances. We propose the first comprehensive approach to process an OGNN query. We present an efficient algorithm to compute aggregate obstructed distances, which is an essential component for processing OGNN queries. We exploit geometric properties to develop pruning techniques that reduce the search space and incur less processing overhead. We validate the efficacy and efficiency of our solution through extensive experiments using both real and synthetic datasets.
- M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer, 1997. Google ScholarDigital Library
- Y. Gao, B. Zheng, G. Chen, C. Chen, and Q. Li. Continuous nearest-neighbor search in the presence of obstacles. ACM Trans. Database Syst., 36(2):9, 2011. 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
- T. Hashem, L. Kulik, and R. Zhang. Countering overlapping rectangle privacy attack for moving knn queries. Inf. Syst., 38(3):430--453, 2013. Google ScholarDigital Library
- T. Lozano-Pérez and M. A. Wesley. An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM, 22(10):560--570, 1979. 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, pages 301--312, 2004. Google ScholarDigital Library
- W. Sun, C. Chen, B. Zheng, C. Chen, L. Zhu, W. Liu, and Y. Huang. Merged aggregate nearest neighbor query processing in road networks. In CIKM, pages 2243--2248, 2013. Google ScholarDigital Library
- H. Xu, Z. Li, Y. Lu, K. Deng, and X. Zhou. Group visible nearest neighbor queries in spatial databases. In WAIM, pages 333--344, 2010. Google ScholarDigital Library
- M. L. Yiu, N. Mamoulis, and D. Papadias. Aggregate nearest neighbor queries in road networks. IEEE Trans. Knowl. Data Eng., 17(6):820--833, 2005. Google ScholarDigital Library
- J. Zhang, D. Papadias, K. Mouratidis, and M. Zhu. Query processing in spatial databases containing obstacles. International Journal of Geographical Information Science, 19(10):1091--1111, 2005.Google ScholarCross Ref
Index Terms
- Group nearest neighbor queries in the presence of obstacles
Recommendations
Range-based Obstructed Nearest Neighbor Queries
SIGMOD '16: Proceedings of the 2016 International Conference on Management of DataIn this paper, we study a novel variant of obstructed nearest neighbor queries, namely, range-based obstructed nearest neighbor (RONN) search. A natural generalization of continuous obstructed nearest-neighbor (CONN), an RONN query retrieves the ...
Privacy preserving group nearest neighbor queries
EDBT '10: Proceedings of the 13th International Conference on Extending Database TechnologyUser privacy in location-based services has attracted great interest in the research community. We introduce a novel framework based on a decentralized architecture for privacy preserving group nearest neighbor queries. A group nearest neighbor (GNN) ...
Reverse k-nearest neighbor search in the presence of obstacles
In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN ...
Comments