Mohammed Eunus Ali
Abstract
We introduce a new type of query for a location-based social network platform. Consider a scenario in which a group of users is trying to find a common meeting location, yet attempting to include all group members is introducing a significant traveling cost to most of them. In this article, we formulate a new query type called the consensus query, which can be used to help users explore these trade-off options to find a solution upon which everyone can agree. Specifically, we study the problem of evaluating consensus queries in the context of nearest neighbor queries, where the group is interested in finding a meeting place that minimizes the travel distance for at least a specified number of group members. To help the group in selecting a suitable solution, the major challenge is to find optimal subgroups of all allowable subgroup sizes, i.e., greater or equal to the minimum specified subgroup size, that minimize the travel distances. We develop incremental algorithms to evaluate in one pass the optimal query subgroups of different sizes along with their corresponding nearest data points. These subsets, which are evaluated by the location-based service provider, constitute the answer set that is returned to the group. The group then collaboratively selects the final answer from the candidate answer set. An extensive experimental study shows the efficiency and effectiveness of our proposed techniques.
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’90). 322--331.Google Scholar
Digital Library
- Xin Cao, Gao Cong, Christian S. Jensen, and Beng Chin Ooi. 2011. Collective spatial keyword querying. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’11). 373--384.Google ScholarDigital Library
- Lisi Chen, Gao Cong, Christian S. Jensen, and Dingming Wu. 2013. Spatial keyword query processing: An experimental evaluation. Proceedings of the VLDB Endowment 6, 3, 217--228.Google ScholarDigital Library
- Chi-Yin Chow, Jie Bao, and Mohamed F. Mokbel. 2010. Towards location-based social networking services. In Proceedings of the 2nd ACM SIGSPATIAL International Workshop on LBSN. 31--38.Google Scholar
- Ke Deng, Shazia Wasim Sadiq, Xiaofang Zhou, Hu Xu, Gabriel Pui Cheong Fung, and Yansheng Lu. 2012. On group nearest group query processing. IEEE Transactions on Knowledge and Data Engineering 24, 2, 295--308.Google ScholarDigital Library
- Ian De Felipe, Vagelis Hristidis, and Naphtali Rishe. 2008. Keyword search on spatial databases. In Proceedings of the 24th International Conference on Data Engineering (ICDE’08). 656--665.Google ScholarDigital Library
- Facebook Places. 2016. Retrieved March 20, 2016 from http://www.facebook.com/, http://www.facebook.com/places/.Google Scholar
- Sébastien Ferré and Alice Hermann. 2011. Semantic search: Reconciling expressive querying and exploratory search. In The Semantic Web—ISWC 2011. Lecture Notes in Computer Science, Vol. 7031. Springer, 177--192.Google ScholarCross Ref
- Foursquare. 2016. Retrieved March 20, 2016 from http://foursquare.com/.Google Scholar
- Mike Gartrell, Xinyu Xing, Qin Lv, Aaron Beach, Richard Han, Shivakant Mishra, and Karim Seada. 2010. Enhancing group recommendation by incorporating social relationship interactions. In Proceedings of the 16th ACM International Conference on Supporting Group Work (GROUP’10). 97--106.Google ScholarDigital Library
- Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’84). 47--57.Google ScholarDigital Library
- Tanzima Hashem, Tahrima Hashem, Mohammed Eunus Ali, and Lars Kulik. 2013. Group trip planning queries in spatial databases. In Proceedings of the 13th International Conference on Advances in Spatial and Temporal Databases (SSTD’13). 259--276.Google ScholarCross Ref
- Gisli R. Hjaltason and Hanan Samet. 1995. Ranking in spatial databases. In Proceedings of the 4th International Symposium on Advances in Spatial Databases (SSD’95). 83--95.Google ScholarDigital Library
- Anthony Jameson and Barry Smyth. 2007. Recommendation to groups. In The Adaptive Web. Springer, 596--627.Google ScholarDigital Library
- Christian S. Jensen, Jan Kolářvr, Torben Bach Pedersen, and Igor Timko. 2003. Nearest neighbor queries in road networks. In Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems (GIS’03). 1--8.Google ScholarDigital Library
- Anastasios Kementsietsidis, Frank Neven, Dieter Van de Craen, and Stijn Vansummeren. 2008. Scalable multi-query optimization for exploratory queries over federated scientific databases. Proceedings of the VLDB Endowment 1, 1, 16--27.Google ScholarDigital Library
- Mohammad Kolahdouzan and Cyrus Shahabi. 2004. Voronoi-based K nearest neighbor search for spatial network databases. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB’04). 840--851.Google ScholarDigital Library
- Yang Li, Feifei Li, Ke Yi, Bin Yao, and Min Wang. 2011. Flexible aggregate similarity search. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’11). 1009--1020.Google ScholarDigital Library
- Sarah Masud, Farhana Murtaza Choudhury, Mohammed Eunus Ali, and Sarana Nutanong. 2013. Maximum visibility queries in spatial databases. In Proceedings of the IEEE 29th International Conference on Data Engineering (ICDE’13). 637--648.Google ScholarDigital Library
- Dimitris Papadias, Qiongmao Shen, Yufei Tao, and Kyriakos Mouratidis. 2004. Group nearest neighbor queries. In Proceedings of the 20th International Conference on Data Engineering (ICDE’04). 301--310.Google ScholarDigital Library
- Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, and Chun Kit Hui. 2005. Aggregate nearest neighbor queries in spatial databases. ACM Transactions on Database Systems 30, 2, 529--576.Google ScholarDigital Library
- Dimitris Papadias, Jun Zhang, Nikos Mamoulis, and Yufei Tao. 2003. Query processing in spatial network databases. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB’03). 802--813.Google ScholarDigital Library
- João B. Rocha-Junior and Kjetil Nørvåg. 2012. Top-k spatial keyword queries on road networks. In Proceedings of the 15th International Conference on Extending Database Technology (EDBT’12). 168--179.Google Scholar
- Nick Roussopoulos, Stephen Kelley, and Frédéric Vincent. 1995. Nearest neighbor queries. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’95). 71--79.Google ScholarDigital Library
- Takeshi Sakaki, Makoto Okazaki, and Yutaka Matsuo. 2010. Earthquake shakes Twitter users: Real-time event detection by social sensors. In Proceedings of the 19th International Conference on World Wide Web (WWW’10). 851--860.Google ScholarDigital Library
- Thomas Seidl and Hans-Peter Kriegel. 1998. Optimal multi-step k-nearest neighbor search. SIGMOD Record 27, 2, 154--165.Google ScholarDigital Library
- Jing Shan, Donghui Zhang, and Betty Salzberg. 2003. On spatial-range closest-pair query. In Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science, Vol. 2750. Springer, 252--269.Google Scholar
- Ben Shneiderman. 1994. Dynamic queries for visual information seeking. IEEE Software 11, 6, 70--77.Google ScholarDigital Library
- Xiance Si, Edward Y. Chang, Zoltán Gyöngyi, and Maosong Sun. 2010. Confucius and its intelligent disciples: Integrating social with search. Proceedings of the VLDB Endowment 3, 2, 1505--1516.Google ScholarDigital Library
- Wechat. 2016. Retrieved March 20, 2016 from http://web.wechat.com/.Google Scholar
- E Welzl. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science. Lecture Notes in Computer Science, Vol. 555. Springer, 359--370.Google Scholar
- Chenyi Xia, Hongjun Lu, Beng Chin Ooi, and Jin Hu. 2004. Gorder: An efficient method for KNN join processing. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB’04). 756--767.Google Scholar
- De-Nian Yang, Chih-Ya Shen, Wang-Chien Lee, and Ming-Syan Chen. 2012. On socio-spatial group query for location-based social networks. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’12). 949--957.Google ScholarDigital Library
- Man Lung Yiu, Nikos Mamoulis, and Dimitris Papadias. 2005. Aggregate nearest neighbor queries in road networks. IEEE Transactions on Knowledge and Data Engineering 17, 820--833.Google ScholarDigital Library
- Tjalling J. Ypma. 1995. Historical development of the Newton-Raphson method. SIAM Review 37, 4, 531--551.Google ScholarDigital Library
- Zhiyong Yu, Zhiwen Yu, Xingshe Zhou, and Yuichi Nakamura. 2009. Handling conditional preferences in recommender systems. In Proceedings of the 14th International Conference on Intelligent User Interfaces (IUI’09). 407--412.Google ScholarDigital Library
- Jinzeng Zhang, Xiaofeng Meng, Xuan Zhou, and Dongqi Liu. 2012. Co-spatial searcher: Efficient tag-based collaborative spatial search on geo-social network. In Proceedings of the 17th International Conference on Database Systems for Advanced Applications (DASFAA’12), Vol. Part 1. 560--575.Google ScholarDigital Library
- Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Data Engineering Bulletin 33, 2, 32--39.Google Scholar
Index Terms
- Spatial Consensus Queries in a Collaborative Environment
Recommendations
Geo-Social K-Cover Group Queries for Collaborative Spatial Computing
With the rapid development of location-aware mobile devices, ubiquitous Internet access and social computing technologies, lots of users' personal information, such as location data and social data, has been readily accessible from various mobile ...
Batch processing of Top-k Spatial-textual Queries
GeoRich'15: Second International ACM Workshop on Managing and Mining Enriched Geo-Spatial DataTop-k spatial-textual queries have received significant attention in the research community. Several techniques to efficiently process this class of queries are now widely used in a variety of applications. However, the problem of how best to process ...
Distance join queries on spatial networks
GIS '06: Proceedings of the 14th annual ACM international symposium on Advances in geographic information systemsThe result of a distance join operation on two sets of objects R, S on a spatial network G is a set P of object pairs pq, p É R, q É S such that the distance of an object pair pq is the shortest distance from p to q in G. Several variations to the ...
Comments