{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:54Z","timestamp":1750219854596,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T00:00:00Z","timestamp":1683936000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"eSSENCE strategic initiatives on eScience"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>More often than not, spatial objects are associated with some context, in the form of text, descriptive tags (e.g., points of interest, flickr photos), or linked entities in semantic graphs (e.g., Yago2, DBpedia). Hence, location-based retrieval should be extended to consider not only the locations but also the context of the objects, especially when the retrieved objects are too many and the query result is overwhelming. In this article, we study the problem of selecting a subset of the query result, which is the most representative. We argue that objects with similar context and nearby locations should proportionally be represented in the selection. Proportionality dictates the pairwise comparison of all retrieved objects and hence bears a high cost. We propose novel algorithms which greatly reduce the cost of proportional object selection in practice. In addition, we propose pre-processing, pruning, and approximate computation techniques that their combination reduces the computational cost of the algorithms even further. We theoretically analyze the approximation quality of our approaches. Extensive empirical studies on real datasets show that our algorithms are effective and efficient. A user evaluation verifies that proportional selection is more preferable than random selection and selection based on object diversification.<\/jats:p>","DOI":"10.1145\/3588434","type":"journal-article","created":{"date-parts":[[2023,3,17]],"date-time":"2023-03-17T12:08:57Z","timestamp":1679054937000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Proportionality on Spatial Data with Context"],"prefix":"10.1145","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9547-5137","authenticated-orcid":false,"given":"Georgios J.","family":"Fakas","sequence":"first","affiliation":[{"name":"Uppsala University, Uppsala, SWEDEN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2435-1863","authenticated-orcid":false,"given":"Georgios","family":"Kalamatianos","sequence":"additional","affiliation":[{"name":"Uppsala University, Uppsala, SWEDEN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,5,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_3_2_2","DOI":"10.1145\/3035918.3064032"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1007\/978-3-319-22363-6_23","volume-title":"Proceedings of the Advances in Spatial and Temporal Databases: 14th International Symposium SSTD","author":"Ahuja Ritesh","year":"2015","unstructured":"Ritesh Ahuja, Nikos Armenatzoglou, Dimitris Papadias, and George J. Fakas. 2015. Geo-social keyword search. In Proceedings of the Advances in Spatial and Temporal Databases: 14th International Symposium SSTD. 431\u2013450."},{"doi-asserted-by":"publisher","key":"e_1_3_3_4_2","DOI":"10.1145\/1242572.1242591"},{"doi-asserted-by":"publisher","key":"e_1_3_3_5_2","DOI":"10.1007\/s00778-020-00610-z"},{"key":"e_1_3_3_6_2","series-title":"Advances in Information Retrieval: 40th European Conference on IR Research, ECIR 2018","first-page":"684","volume":"10772","author":"Campos Ricardo","year":"2018","unstructured":"Ricardo Campos, V\u00edtor Mangaravite, Arian Pasquali, Al\u00edpio M\u00e1rio Jorge, C\u00e9lia Nunes, and Adam Jatowt. 2018. A text feature based automatic keyword extraction method for single documents. In Advances in Information Retrieval: 40th European Conference on IR Research, ECIR 2018(Lecture Notes in Computer Science, Vol. 10772). Springer, 684\u2013691."},{"doi-asserted-by":"publisher","key":"e_1_3_3_7_2","DOI":"10.14778\/2535569.2448955"},{"doi-asserted-by":"publisher","key":"e_1_3_3_8_2","DOI":"10.1007\/s10707-019-00373-y"},{"key":"e_1_3_3_9_2","first-page":"133","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Cheng Shiwen","year":"2014","unstructured":"Shiwen Cheng, Anastasios Arvanitis, Marek Chrobak, and Vagelis Hristidis. 2014. Multi-query diversification in microblogging posts. In Proceedings of the International Conference on Extending Database Technology. 133\u2013144."},{"key":"e_1_3_3_10_2","first-page":"17","volume-title":"Proceedings of the International Conference on Extending Database Technology","author":"Cheng Shiwen","year":"2016","unstructured":"Shiwen Cheng, Marek Chrobak, and Vagelis Hristidis. 2016. Slowing the firehose: Multi-dimensional diversity on social post streams. In Proceedings of the International Conference on Extending Database Technology. 17\u201328."},{"doi-asserted-by":"publisher","key":"e_1_3_3_11_2","DOI":"10.14778\/1687627.1687666"},{"doi-asserted-by":"publisher","key":"e_1_3_3_12_2","DOI":"10.1145\/2348283.2348296"},{"key":"e_1_3_3_13_2","first-page":"331","volume-title":"Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval","author":"Demidova Elena","year":"2010","unstructured":"Elena Demidova, Peter Fankhauser, Xuan Zhou, and Wolfgang Nejdl. 2010. DivQ: Diversification for keyword search over structured databases. In Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval. 331\u2013338."},{"doi-asserted-by":"publisher","key":"e_1_3_3_14_2","DOI":"10.1016\/j.is.2014.07.002"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1109\/ICDEW.2008.4498381","volume-title":"Proceedings of the 2008 IEEE 24th International Conference on Data Engineering Workshop","author":"Fakas Georgios J.","year":"2008","unstructured":"Georgios J. Fakas. 2008. Automated generation of object summaries from relational databases: A novel keyword searching paradigm. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering Workshop. IEEE Computer Society, 564\u2013567."},{"doi-asserted-by":"publisher","key":"e_1_3_3_16_2","DOI":"10.1016\/j.datak.2010.11.003"},{"doi-asserted-by":"publisher","key":"e_1_3_3_17_2","DOI":"10.1016\/j.datak.2017.08.002"},{"doi-asserted-by":"publisher","key":"e_1_3_3_18_2","DOI":"10.1109\/ICDE.2009.171"},{"issue":"2","key":"e_1_3_3_19_2","first-page":"1750002:1\u201317500","article-title":"Object summaries for keyword search","volume":"2","author":"Fakas Georgios J.","year":"2018","unstructured":"Georgios J. Fakas and Zhi Cai. 2018. Object summaries for keyword search. Encyclopedia with Semantic Computing and Robotic Intelligence 2, 2 (2018), 1750002:1\u20131750002:20.","journal-title":"Encyclopedia with Semantic Computing and Robotic Intelligence"},{"issue":"3","key":"e_1_3_3_20_2","first-page":"229","article-title":"Size-l object summaries for relational keyword search","volume":"5","author":"Fakas Georgios J.","year":"2011","unstructured":"Georgios J. Fakas, Zhi Cai, and Nikos Mamoulis. 2011. Size-l object summaries for relational keyword search. International Conference on Very Large Data Bases 5, 3 (2011), 229\u2013240.","journal-title":"International Conference on Very Large Data Bases"},{"doi-asserted-by":"publisher","key":"e_1_3_3_21_2","DOI":"10.1109\/TKDE.2013.110"},{"doi-asserted-by":"publisher","key":"e_1_3_3_22_2","DOI":"10.1145\/2723372.2737783"},{"doi-asserted-by":"publisher","key":"e_1_3_3_23_2","DOI":"10.1007\/s00778-016-0433-6"},{"issue":"2","key":"e_1_3_3_24_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0219649211002936","article-title":"Automated generation of personal data reports from relational databases","volume":"10","author":"Fakas Georgios J.","year":"2011","unstructured":"Georgios J. Fakas, Ben Cawley, and Zhi Cai. 2011. Automated generation of personal data reports from relational databases. Journal of Information & Knowledge Management 10, 2 (2011), 193\u2013208.","journal-title":"Journal of Information & Knowledge Management"},{"doi-asserted-by":"publisher","key":"e_1_3_3_25_2","DOI":"10.1007\/s10115-003-0090-0"},{"key":"e_1_3_3_26_2","first-page":"656","volume-title":"Proceedings of the International Council for Open and Distance Education","author":"Felipe Ian De","year":"2008","unstructured":"Ian De Felipe, Vagelis Hristidis, and Naphtali Rishe. 2008. Keyword search on spatial databases. In Proceedings of the International Council for Open and Distance Education. IEEE Computer Society, 656\u2013665."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/978-3-540-45072-6_18","volume-title":"Proceedings of the 17th International Symposium on Spatial and Temporal Databases","volume":"2750","author":"Hadjieleftheriou Marios","year":"2003","unstructured":"Marios Hadjieleftheriou, George Kollios, Dimitrios Gunopulos, and Vassilis J. Tsotras. 2003. On-line discovery of dense areas in spatio-temporal databases. In Proceedings of the 17th International Symposium on Spatial and Temporal Databases, Vol. 2750. 306\u2013324."},{"doi-asserted-by":"publisher","key":"e_1_3_3_28_2","DOI":"10.1007\/s00778-004-0151-3"},{"key":"e_1_3_3_29_2","first-page":"224","volume-title":"Proceedings of the 11th ACM Conference on Recommender Systems","author":"Han Jungkyu","year":"2017","unstructured":"Jungkyu Han and Hayato Yamana. 2017. Geographical diversification in POI recommendation: Toward improved coverage on interested areas. In Proceedings of the 11th ACM Conference on Recommender Systems. ACM, 224\u2013228."},{"issue":"4","key":"e_1_3_3_30_2","first-page":"15","article-title":"The KNDN problem: A quest for unity in diversity","volume":"32","author":"Haritsa Jayant R.","year":"2009","unstructured":"Jayant R. Haritsa. 2009. The KNDN problem: A quest for unity in diversity. IEEE Data Engineering Bulletin 32, 4 (2009), 15\u201322.","journal-title":"IEEE Data Engineering Bulletin"},{"doi-asserted-by":"publisher","key":"e_1_3_3_31_2","DOI":"10.1145\/2623330.2623610"},{"doi-asserted-by":"publisher","key":"e_1_3_3_32_2","DOI":"10.1016\/S0167-6377(97)00034-5"},{"doi-asserted-by":"publisher","key":"e_1_3_3_33_2","DOI":"10.1016\/j.artint.2012.06.001"},{"key":"e_1_3_3_34_2","first-page":"850","volume-title":"Proceedings of the International Conference on Very Large Data Base","author":"Hristidis Vagelis","year":"2003","unstructured":"Vagelis Hristidis, Luis Gravano, and Yannis Papakonstantinou. 2003. Efficient IR-style keyword search over relational databases. In Proceedings of the International Conference on Very Large Data Base. 850\u2013861."},{"key":"e_1_3_3_35_2","first-page":"670","volume-title":"Proceedings of the International Conference on Very Large Data Base","author":"Hristidis Vagelis","year":"2002","unstructured":"Vagelis Hristidis and Yannis Papakonstantinou. 2002. Discover: Keyword search in relational databases. In Proceedings of the International Conference on Very Large Data Base. 670\u2013681."},{"key":"e_1_3_3_36_2","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/978-3-540-24775-3_49","volume-title":"Proceedings of the Advances in Knowledge Discovery and Data Mining: 8th Pacific-Asia Conference","author":"Jain Anoop","year":"2004","unstructured":"Anoop Jain, Parag Sarda, and Jayant R. Haritsa. 2004. Providing diversity in k-nearest neighbor query results. In Proceedings of the Advances in Knowledge Discovery and Data Mining: 8th Pacific-Asia Conference. 404\u2013413."},{"doi-asserted-by":"publisher","key":"e_1_3_3_37_2","DOI":"10.1145\/3448016.3457309"},{"doi-asserted-by":"publisher","key":"e_1_3_3_38_2","DOI":"10.1109\/TKDE.2013.85"},{"key":"e_1_3_3_39_2","doi-asserted-by":"crossref","first-page":"1256","DOI":"10.1007\/978-3-319-17885-1_793","volume-title":"Proceedings of the Encyclopedia of GIS","author":"Kollios George","year":"2017","unstructured":"George Kollios, Vassilis J. Tsotras, and Dimitrios Gunopulos. 2017. Mobile object indexing. In Proceedings of the Encyclopedia of GIS. 1256\u20131266."},{"doi-asserted-by":"publisher","key":"e_1_3_3_40_2","DOI":"10.1109\/TKDE.2014.2302294"},{"doi-asserted-by":"publisher","key":"e_1_3_3_41_2","DOI":"10.5555\/2787930"},{"doi-asserted-by":"publisher","key":"e_1_3_3_42_2","DOI":"10.1038\/234034a0"},{"key":"e_1_3_3_43_2","first-page":"431","volume-title":"Facility Dispersion Problems: Heuristics and Special Cases","author":"Ravi S. S.","year":"1991","unstructured":"S. S. Ravi, Daniel J. Rosenkrantz, and Giri Kumar Tayi. 1991. Facility Dispersion Problems: Heuristics and Special Cases. 431\u2013450."},{"key":"e_1_3_3_44_2","doi-asserted-by":"crossref","first-page":"17:1\u201317:12","DOI":"10.1145\/3221269","volume-title":"Proceedings of the 30th International Conference on Scientific and Statistical Database Management","author":"Sacharidis Dimitris","year":"2018","unstructured":"Dimitris Sacharidis, Paras Mehta, Dimitrios Skoutas, Kostas Patroumpas, and Agn\u00e8s Voisard. 2018. Selecting representative and diverse spatio-textual posts over sliding windows. In Proceedings of the 30th International Conference on Scientific and Statistical Database Management. 17:1\u201317:12."},{"doi-asserted-by":"publisher","key":"e_1_3_3_45_2","DOI":"10.1145\/2882903.2882941"},{"key":"e_1_3_3_46_2","doi-asserted-by":"crossref","first-page":"4129","DOI":"10.1109\/BigData47090.2019.9006498","volume-title":"Proceedings of the 2019 IEEE International Conference on Big Data (Big Data)","author":"Siddique A. B.","year":"2019","unstructured":"A. B. Siddique, Ahmed Eldawy, and Vagelis Hristidis. 2019. Euler++: Improved selectivity estimation for rectangular spatial records. In Proceedings of the 2019 IEEE International Conference on Big Data (Big Data). 4129\u20134133."},{"doi-asserted-by":"publisher","key":"e_1_3_3_47_2","DOI":"10.1145\/3216122.3216167"},{"doi-asserted-by":"publisher","key":"e_1_3_3_48_2","DOI":"10.1145\/3274895.3274965"},{"key":"e_1_3_3_49_2","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/1739041.1739111","volume-title":"Proceedings of the 13th International Conference on Extending Database Technology","author":"Stefanidis Kostas","year":"2010","unstructured":"Kostas Stefanidis, Marina Drosou, and Evaggelia Pitoura. 2010. PerK: Personalized keyword search in relational databases through preferences. In Proceedings of the 13th International Conference on Extending Database Technology. 585\u2013596."},{"key":"e_1_3_3_50_2","first-page":"241","volume-title":"Proceedings of the EDBT Conference","author":"Stoyanovich Julia","year":"2018","unstructured":"Julia Stoyanovich, Ke Yang, and H. V. Jagadish. 2018. Online set selection with fairness and diversity constraints. In Proceedings of the EDBT Conference. 241\u2013252."},{"key":"e_1_3_3_51_2","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-3-642-12275-0_18","volume-title":"Proceedings of the Advances in Information Retrieval: 32nd European Conference on IR Research","volume":"5993","author":"Tang Jiayu","year":"2010","unstructured":"Jiayu Tang and Mark Sanderson. 2010. Evaluation and user preference study on spatial diversity. In Proceedings of the Advances in Information Retrieval: 32nd European Conference on IR Research, Vol. 5993. 179\u2013190."},{"key":"e_1_3_3_52_2","first-page":"969","volume-title":"Proceedings of the International Conference on Computing Methodologies and Communication (ICCMC)","author":"Thushara M. G.","year":"2019","unstructured":"M. G. Thushara, Tadi Mownika, and Ritika Mangamuru. 2019. A comparative study on different keyword extraction algorithms. In Proceedings of the International Conference on Computing Methodologies and Communication (ICCMC). 969\u2013973."},{"doi-asserted-by":"publisher","key":"e_1_3_3_53_2","DOI":"10.1007\/s10707-004-5622-6"},{"key":"e_1_3_3_54_2","first-page":"1163","volume-title":"Proceedings of the IEEE 27th International Conference on Data Engineering","author":"Vieira Marcos R.","year":"2011","unstructured":"Marcos R. Vieira, Humberto L. Razente, Maria C. N. Barioni, Marios Hadjieleftheriou, Divesh Srivastava, Caetano Traina, and Vassilis J. Tsotras. 2011. On query result diversification. In Proceedings of the IEEE 27th International Conference on Data Engineering. 1163\u20131174."},{"issue":"1","key":"e_1_3_3_55_2","first-page":"3052","article-title":"Identifying search keywords for finding relevant social media posts","volume":"30","author":"Wang Shuai","year":"2016","unstructured":"Shuai Wang, Zhiyuan Chen, Bing Liu, and Sherry Emery. 2016. Identifying search keywords for finding relevant social media posts. Proceedings of the AAAI Conference on Artificial Intelligence 30, 1 (Mar.2016), 3052\u20133058.","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"e_1_3_3_56_2","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/978-3-642-37453-1_32","volume-title":"Proceedings of the Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD (1)","volume":"7818","author":"Wu Lin","year":"2013","unstructured":"Lin Wu, Yang Wang, John Shepherd, and Xiang Zhao. 2013. An optimization method for proportionally diversifying search results. In Proceedings of the Advances in Knowledge Discovery and Data Mining: 17th Pacific-Asia Conference, PAKDD (1), Vol. 7818. 390\u2013401."},{"key":"e_1_3_3_57_2","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1007\/978-3-319-63564-4_12","volume-title":"Proceedings of the Web and Big Data: First International Joint Conference, APWeb\/WAIM (2)","volume":"10367","author":"Xing Xiaolu","year":"2017","unstructured":"Xiaolu Xing, Chaofeng Sha, and Junyu Niu. 2017. Improving topic diversity in recommendation lists: Marginally or proportionally? In Proceedings of the Web and Big Data: First International Joint Conference, APWeb\/WAIM (2), Vol. 10367. 142\u2013150."},{"key":"e_1_3_3_58_2","first-page":"367","volume-title":"Proceedings of theAdvances in Database Technology-EDBT 2014: 17th International Conference on Extending Database Technology","author":"Zhang Chengyuan","year":"2014","unstructured":"Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin Lin, Muhammad Aamir Cheema, and Xiaoyang Wang. 2014. Diversified spatial keyword search on road networks. In Proceedings of theAdvances in Database Technology-EDBT 2014: 17th International Conference on Extending Database Technology. 367\u2013378."},{"key":"e_1_3_3_59_2","doi-asserted-by":"crossref","first-page":"1619","DOI":"10.1145\/3132847.3132968","volume-title":"Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM","author":"Zheng Xin","year":"2017","unstructured":"Xin Zheng, Aixin Sun, Sibo Wang, and Jialong Han. 2017. Semi-supervised event-related tweet identification with dynamic keyword generation. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, CIKM. ACM, 1619\u20131628."},{"doi-asserted-by":"publisher","key":"e_1_3_3_60_2","DOI":"10.1145\/1097064.1097067"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588434","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588434","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:12Z","timestamp":1750178832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588434"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,13]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3588434"],"URL":"https:\/\/doi.org\/10.1145\/3588434","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2023,5,13]]},"assertion":[{"value":"2022-06-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-12","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}