More Web Proxy on the site http://driver.im/

research-article

Social-Spatial Group Queries with Keywords

Authors:

Sajid Hasan Apon,

Mohammed Eunus Ali,

Bishwamittra Ghosh,

Timos SellisAuthors Info & Claims

ACM Transactions on Spatial Algorithms and Systems (TSAS), Volume 8, Issue 1

Article No.: 1, Pages 1 - 32

https://doi.org/10.1145/3475962

Published: 26 October 2021 Publication History

Abstract

Social networks with location enabling technologies, also known as geo-social networks, allow users to share their location-specific activities and preferences through check-ins. A user in such a geo-social network can be attributed to an associated location (spatial), her preferences as keywords (textual), and the connectivity (social) with her friends. The fusion of social, spatial, and textual data of a large number of users in these networks provide an interesting insight for finding meaningful geo-social groups of users supporting many real-life applications, including activity planning and recommendation systems. In this article, we introduce a novel query, namely, Top-k Flexible Socio-Spatial Keyword-aware Group Query (SSKGQ), which finds the best k groups of varying sizes around different points of interest (POIs), where the groups are ranked based on the social and textual cohesiveness among members and spatial closeness with the corresponding POI and the number of members in the group. We develop an efficient approach to solve the SSKGQ problem based on our theoretical upper bounds on distance, social connectivity, and textual similarity. We prove that the SSKGQ problem is NP-Hard and provide an approximate solution based on our derived relaxed bounds, which run much faster than the exact approach by sacrificing the group quality slightly. Our extensive experiments on real data sets show the effectiveness of our approaches in different real-life settings.

References

[1]

Mohammed Eunus Ali, Egemen Tanin, Peter Scheuermann, Sarana Nutanong, and Lars Kulik. 2016. Spatial consensus queries in a collaborative environment. ACM Trans. Spatial Algor. Syst. 2, 1 (2016), 3:1–3:37. DOI:https://doi.org/10.1145/2829943

[2]

Marc Barthmy. 2011. Spatial networks. Phys. Rep. 499, 1 (2011), 1–101. DOI:

[3]

Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, and Alec Radford. 2020. Language Models are Few-Shot Learners. Retrieved from.

[4]

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). ACM, New York, NY, 373–384. DOI:https://doi.org/10.1145/1989323.1989363

[5]

Lisi Chen, Gao Cong, Christian S. Jensen, and Dingming Wu. 2013. Spatial keyword query processing: An experimental evaluation. Proc. VLDB Endow. 6, 3 (Jan. 2013), 217–228. DOI:https://doi.org/10.14778/2535569.2448955

[6]

Lu Chen, Chengfei Liu, Rui Zhou, Jianxin Li, Xiaochun Yang, and Bin Wang. 2018. Maximum co-located community search in large scale social networks. Proc. VLDB Endow. 11, 10 (June 2018), 1233–1246. DOI:https://doi.org/10.14778/3231751.3231755

Digital Library

[7]

X. Chen, C. Zhang, Y. Hu, B. Ge, and W. Xiao. 2016. Temporal social network: Group query processing. In Proceedings of the 27th International Workshop on Database and Expert Systems Applications (DEXA’16). 181–185. DOI:

[8]

Eunjoon Cho, Seth A. Myers, and Jure Leskovec. 2011. Friendship and mobility: User movement in location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11). ACM, New York, NY, 1082–1090. DOI:https://doi.org/10.1145/2020408.2020579

Digital Library

[9]

Blerim Cici, Athina Markopoulou, Enrique Frias-Martinez, and Nikolaos Laoutaris. 2014. Assessing the potential of ride-sharing using mobile and social data: A tale of four cities. In Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp’14). ACM, New York, NY, 201–211. DOI:https://doi.org/10.1145/2632048.2632055

[10]

I. De Felipe, V. Hristidis, and N. Rishe. 2008. Keyword search on spatial databases. In Proceedings of the IEEE 24th International Conference on Data Engineering. 656–665. DOI:https://doi.org/10.1109/ICDE.2008.4497474

[11]

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. Retrieved from.

[12]

Yixiang Fang, Reynold Cheng, Xiaodong Li, Siqiang Luo, and Jiafeng Hu. 2017. Effective community search over large spatial graphs. Proc. VLDB Endow. 10, 6 (Feb. 2017), 709–720. DOI:https://doi.org/10.14778/3055330.3055337

Digital Library

[13]

Yixiang Fang, Reynold Cheng, Siqiang Luo, and Jiafeng Hu. 2016. Effective community search for large attributed graphs. Proc. VLDB Endow. 9, 12 (Aug. 2016), 1233–1244. DOI:https://doi.org/10.14778/2994509.2994538

Digital Library

[14]

Bishwamittra Ghosh, Mohammed Eunus Ali, Farhana Murtaza Choudhury, Sajid Hasan Apon, Timos Sellis, and Jianxin Li. 2018. The flexible socio spatial group queries. Proc. VLDB 12, 2 (2018), 99–111. Retrieved from http://www.vldb.org/pvldb/vol12/p99-ghosh.pdf.

Digital Library

[15]

Norio Katayama and Shin’ichi Satoh. 1997. The SR-tree: An index structure for high-dimensional nearest neighbor queries. SIGMOD Rec. 26, 2 (June 1997), 369–380. DOI:https://doi.org/10.1145/253262.253347

[16]

M. G. Kendall. 1938. A new measure of rank correlation. Biometrika 30, 1/2 (1938), 81–93. Retrieved from http://www.jstor.org/stable/2332226.

[17]

Junghoon Kim, Tao Guo, Kaiyu Feng, Gao Cong, Arijit Khan, and Farhana M. Choudhury. 2020. Densely connected user community and location cluster search in location-based social networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’20). Association for Computing Machinery, New York, NY, 2199–2209. DOI:https://doi.org/10.1145/3318464.3380603

[18]

Theodoros Lappas, Kun Liu, and Evimaria Terzi. 2009. Finding a team of experts in social networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’09). ACM, New York, NY, 467–476. DOI:https://doi.org/10.1145/1557019.1557074

[19]

Cheng-Te Li and Man-Kwan Shan. 2010. Team formation for generalized tasks in expertise social networks. In Proceedings of the IEEE 2nd International Conference on Social Computing (SOCIALCOM’10). IEEE Computer Society, Washington, DC, 9–16. DOI:https://doi.org/10.1109/SocialCom.2010.12

[20]

Y. Li, R. Chen, L. Chen, and J. Xu. 2017. Towards social-aware ridesharing group query services. IEEE Trans. Services Comput. 10, 4 (July 2017), 646–659. DOI:

[21]

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). Association for Computing Machinery, New York, NY, 1009–1020. DOI:https://doi.org/10.1145/1989323.1989429

[22]

Zhisheng Li, Ken C. K. Lee, Baihua Zheng, Wang-Chien Lee, Dik Lee, and Xufa Wang. 2011. IR-Tree: An efficient index for geographic document search. IEEE Trans. Knowl. Data Eng. 23, 4 (Apr. 2011), 585–599. DOI:https://doi.org/10.1109/TKDE.2010.149

Digital Library

[23]

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). IEEE Computer Society, Washington, DC, 301. Retrieved from http://dl.acm.org/citation.cfm?id=977401.978090.

Digital Library

[24]

Nick Roussopoulos, Stephen Kelley, and Frédéric Vincent. 1995. Nearest neighbor queries. SIGMOD Rec. 24, 2 (May 1995), 71–79. DOI:https://doi.org/10.1145/568271.223794

Digital Library

[25]

Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W. Cheung. 2014. Density-based place clustering in geo-social networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD’14). ACM, New York, NY, 99–110. DOI:https://doi.org/10.1145/2588555.2610497

[26]

Shi-Jie Chen and Li Lin. 2004. Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Trans. Eng. Manage. 51, 2 (May 2004), 111–124. DOI:

[27]

Alastair J. Walker. 1977. An efficient method for generating discrete random variables with general distributions. ACM Trans. Math. Softw. 3, 3 (Sept. 1977), 253–256. DOI:https://doi.org/10.1145/355744.355749

Digital Library

[28]

William Webber, Alistair Moffat, and Justin Zobel. 2010. A similarity measure for indefinite rankings. ACM Trans. Info. Syst. 28, 4, Article 20 (Nov. 2010), 38 pages. DOI:https://doi.org/10.1145/1852102.1852106

[29]

Dingqi Yang, Daqing Zhang, Zhiyong Yu, and Zhu Wang. 2013. A sentiment-enhanced personalized location recommendation system. In Proceedings of the 24th ACM Conference on Hypertext and Social Media (HT’13). ACM, New York, NY, 119–128. DOI:https://doi.org/10.1145/2481492.2481505

Digital Library

[30]

Dingqi Yang, Daqing Zhang, Zhiyong Yu, and Zhiwen Yu. 2013. Fine-grained preference-aware location search leveraging crowdsourced digital footprints from LBSNs. In Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing (UbiComp’13). ACM, New York, NY, 479–488. DOI:https://doi.org/10.1145/2493432.2493464

Digital Library

[31]

De-Nian Yang, Yi-Ling Chen, Wang-Chien Lee, and Ming-Syan Chen. 2011. On social-temporal group query with acquaintance constraint. Proc. VLDB Endow. 4, 6 (Mar. 2011), 397–408. DOI:https://doi.org/10.14778/1978665.1978671

Digital Library

[32]

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). ACM, New York, NY, 949–957. DOI:https://doi.org/10.1145/2339530.2339679

[33]

Qijun Zhu, Haibo Hu, Cheng Xu, Jianliang Xu, and Wang-Chien Lee. 2017. Geo-social group queries with minimum acquaintance constraints. VLDB J. 26, 5 (Oct. 2017), 709–727. DOI:https://doi.org/10.1007/s00778-017-0473-6

Digital Library

[34]

Armen Zzkarian and Andrew Kusiak. 1999. Forming teams: An analytical approach. IIE Trans. 31, 1 (Jan. 1999), 85–97. DOI:

Cited By

Zhu HLiu WYin JZheng LHuang XXu JLee W(2023)Continuous Geo-Social Group Monitoring in Dynamic LBSNsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.321884435:8(7815-7828)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3218844
Sun MTeng YZhao FQi JJiang DFan C(2023)Spatio-Textual Group Skyline QueryDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_3(34-50)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_3
D’Ulizia AGrifoni PFerri F(2021)Query Processing of Geosocial Data in Location-Based Social NetworksISPRS International Journal of Geo-Information10.3390/ijgi1101001911:1(19)Online publication date: 30-Dec-2021
https://doi.org/10.3390/ijgi11010019

Index Terms

Social-Spatial Group Queries with Keywords
1. Information systems
  1. Information retrieval
    1. Information retrieval query processing
  2. Information systems applications
    1. Spatial-temporal systems
      1. Location based services

Recommendations

Geo-social group queries with minimum acquaintance constraints

The prosperity of location-based social networking has paved the way for new applications of group-based activity planning and marketing. While such applications heavily rely on geo-social group queries (GSGQs), existing studies fail to produce a ...
A HITS-based POI recommendation algorithm for location-based social networks
ASONAM '13: Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining

Location-Based Social Networks (LBSNs), (also called as Geo-Social Networks), has been attracting more and more users by providing services that integrate social activities with location information. LBSN systems usually provide support for indicating ...
Spatial-aware interest group queries in location-based social networks
CIKM '12: Proceedings of the 21st ACM international conference on Information and knowledge management

Location-based social networks, such as Foursquare and Facebook Places, are bridging the gap between the physical world and online social networking services through acquired user locations. Some social networks released check-in services that allow ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Spatial Algorithms and Systems

ACM Transactions on Spatial Algorithms and Systems Volume 8, Issue 1

March 2022

184 pages

ISSN:2374-0353

EISSN:2374-0361

DOI:10.1145/3488003

Editor:
Walid G. Aref
Purdue University, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 October 2021

Accepted: 01 July 2021

Revised: 01 April 2021

Received: 01 July 2020

Published in TSAS Volume 8, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
319
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)5

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu HLiu WYin JZheng LHuang XXu JLee W(2023)Continuous Geo-Social Group Monitoring in Dynamic LBSNsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.321884435:8(7815-7828)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/TKDE.2022.3218844
Sun MTeng YZhao FQi JJiang DFan C(2023)Spatio-Textual Group Skyline QueryDatabase Systems for Advanced Applications. DASFAA 2023 International Workshops10.1007/978-3-031-35415-1_3(34-50)Online publication date: 17-Apr-2023
https://dl.acm.org/doi/10.1007/978-3-031-35415-1_3
D’Ulizia AGrifoni PFerri F(2021)Query Processing of Geosocial Data in Location-Based Social NetworksISPRS International Journal of Geo-Information10.3390/ijgi1101001911:1(19)Online publication date: 30-Dec-2021
https://doi.org/10.3390/ijgi11010019

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents