Abstract
Location-Based Services are often used to find proximal Points of Interest (PoI) – e.g., nearby restaurants, museums, etc. – in a plethora of applications. However, one may also desire that the returned proximal objects exhibit (likely) maximal and fine-grained semantic diversity. For instance, rather than picking several close-by attractions with similar features – e.g., restaurants with similar menus; museums with similar art exhibitions – a tourist may be more interested in a result set that could potentially provide more diverse types of experiences, for as long as they are within an acceptable distance from a given (current) location. So far, we introduced a topic modeling approach based on Latent Dirichlet Allocation, a generative statistical model, to effectively model and exploit a fine-grained notion of diversity, based on sets of keywords and/or reviews instead of a coarser user-given category. More importantly, for efficiency, we devised two novel indexing structures – Diversity Map and Diversity Aggregated R-tree. In turn, each of these enabled us to develop efficient algorithms to generate the answer-set for two novel categories of queries. While both queries focus on determining the recommended locations among a set of given PoIs that will maximize the semantic diversity within distance limits along a given road network, they each tackle a different variant. The first type of query is kDRQ, which finds k such PoIs with respect to a given user’s location. The second query kDPQ generates a path to be used to visit a sequence of k such locations (i.e., with max diversity), starting at the user’s current location.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abbar, S., et al.: Diverse near neighbor problem. In: SOCG, pp. 207–214 (2013)
Al-Mamun, A., Wu, H., Aref, W.G.: A tutorial on learned multi-dimensional indexes. In: ACM SIGSPATIAL (2020)
Alvares, L.O., Bogorny, V., Kuijpers, B., de Macedo, J.A.F., Moelans, B., Vaisman, A.: A model for enriching trajectories with semantic geographical information. In: ACM GIS, p. 22. ACM (2007)
Amagata, D., Hara, T.: Diversified set monitoring over distributed data streams. In: DEBS, pp. 1–12. ACM (2016)
Bao, J., Chow, C.Y., Mokbel, M.F., Ku, W.S.: Efficient evaluation of k-range nearest neighbor queries in road networks. In: MDM, pp. 115–124. IEEE (2010)
Benetis, R., Jensen, C.S., Karĉiauskas, G., Ŝaltenis, S.: Nearest and reverse nearest neighbor queries for moving objects. VLDB J. 15(3), 229–249 (2006)
Costa, C.F., Nascimento, M.A., Schubert, M.: Diverse nearest neighbors queries using linear skylines. GeoInformatica 22(4), 815–844 (2018)
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: ACM SIGMOD (1984)
Hu, H., Lee, D.L., Lee, V.: Distance indexing on road networks. In: VLDB, pp. 894–905. VLDB Endowment (2006)
Issa, H., Damiani, M.L.: Efficient access to temporally overlaying spatial and textual trajectories. In: MDM, pp. 262–271 (2016)
Jain, A., Sarda, P., Haritsa, J.R.: Providing diversity in k-nearest neighbor query results. In: PAKDD, pp. 404–413 (2004)
Kraska, T., Beutel, A., Chi, E.H., Dean, J., Polyzotis, N.: The case for learned index structures. In: Proceedings of the 2018 International Conference on Management of Data, pp. 489–504 (2018)
Kucuktunc, O., Ferhatosmanoglu, H.: \(\lambda \)-diverse nearest neighbors browsing for multidimensional data. TKDE 25, 481–493 (2013)
Lee, K.C.K., Lee, W.C., Leong, H.V.: Nearest surrounder queries. In: ICDE, p. 85 (2006)
Neto, F.R.A., Santos, C.A.: Understanding crowdsourcing projects: a systematic review of tendencies, workflow, and quality management. Inf. Proc. Manag. 54, 490–506 (2018)
Parent, C., et al.: Semantic trajectories modeling and analysis. ACM Comput. Surv. (CSUR) 45, 42 (2013)
Teng, X., Trajcevski, G., Kim, J., Züfle, A.: Semantically diverse path search. In: IEEE MDM (2020)
Teng, X., Yang, J., Kim, J.S., Trajcevski, G., Züfle, A., Nascimento, M.A.: Fine-grained diversification of proximity constrained queries on road networks. In: SSTD, pp. 51–60 (2019)
Vieira, M.R., et al.: On query result diversification. In: ICDE, pp. 1163–1174. IEEE (2011)
Wang, H., Fu, X., Xu, J., Lu, H.: Learned index for spatial queries. In: IEEE MDM (2019)
Yang, S., Cheema, M.A., Lin, X., Wang, W.: Reverse k nearest neighbors query processing: experiments and analysis. In: Proceedings of the VLDB Endow, pp. 605–616 (2015)
Zhang, C., et al.: Diversified spatial keyword search on road networks. In: EDBT, pp. 367–378 (2014)
Zheng, K., Shang, S., Yuan, N.J., Yang, Y.: Towards efficient search for activity trajectories. In: ICDE, pp. 230–241. IEEE (2013)
Acknowledgment
Research supported by NSF SWIFT grant 2030249.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Teng, X., Trajcevski, G. (2021). Semantically Diverse Constrained Queries. In: Bellatreche, L., et al. New Trends in Database and Information Systems. ADBIS 2021. Communications in Computer and Information Science, vol 1450. Springer, Cham. https://doi.org/10.1007/978-3-030-85082-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-030-85082-1_26
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-85081-4
Online ISBN: 978-3-030-85082-1
eBook Packages: Computer ScienceComputer Science (R0)