Skip to main content
Top

2019 | OriginalPaper | Chapter

A Measure and Conquer Algorithm for the Minimum User Spatial-Aware Interest Group Query Problem

Authors : Chih-Yang Huang, Po-Chuan Chien, Yen Hung Chen

Published in: New Trends in Computer Technologies and Applications

Publisher: Springer Singapore

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Location-based social networks are important issues in the recent decade. In modern social networks, websites such as Twitter, Facebook, and Plurk, attempt to get the accurate address positions from their users, and try to reduce the gap between virtuality and reality. This paper mainly aims at both the interests of Internet users and their real positions. This issue is called the spatial-aware interest group query problem (SIGQP). Given a user set U with n users, a keywords set W with m words, and a spatial objects set S with s items, each of which contains one or multiple keywords. If a user checks in a certain spatial object, it means the user could be interested in that part of keywords, which is countable to clarify the interests of the user. The SIGQP then tries to find a k-user set \(U_{k}\), \(k \le n\), such that the union of keywords of these k users will equal to W, and additionally, the diameter (longest Euclidean distance of two arbitrary users in \(U_k\)) should be as small as possible. The SIGQP has been proved as NP-Complete, and two heuristic algorithms have been proposed. Extended from SIGQP, the main problem of this paper prioritizes in finding the smallest k for \(U_{k}\) to cover all the keywords, with the users’ distance as the secondary criterion, called as “minimum user spatial-aware interest group query problem” (MUSIGQP). This paper further designs an exact algorithm on a measure-&-conquer-based method to precisely solve this problem, and a performance analysis is given.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Chen, L., Cong, G., Jensen, C.S., Wu, D.: Spatial keyword query processing: an experimental evaluation. In: Proceedings of the VLDB Endowment, vol. 6, pp. 217–228. VLDB Endowment (2013) Chen, L., Cong, G., Jensen, C.S., Wu, D.: Spatial keyword query processing: an experimental evaluation. In: Proceedings of the VLDB Endowment, vol. 6, pp. 217–228. VLDB Endowment (2013)
2.
go back to reference Chen, S.J., Lin, L.: Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Trans. Eng. Manag. 51(2), 111–124 (2004)MathSciNetCrossRef Chen, S.J., Lin, L.: Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Trans. Eng. Manag. 51(2), 111–124 (2004)MathSciNetCrossRef
3.
go back to reference Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. Proc. VLDB Endow. 2(1), 337–348 (2009)CrossRef Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. Proc. VLDB Endow. 2(1), 337–348 (2009)CrossRef
4.
go back to reference Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M.: Closest pair queries in spatial databases. In: ACM SIGMOD Record, vol. 29, pp. 189–200. ACM (2000) Corral, A., Manolopoulos, Y., Theodoridis, Y., Vassilakopoulos, M.: Closest pair queries in spatial databases. In: ACM SIGMOD Record, vol. 29, pp. 189–200. ACM (2000)
5.
go back to reference De Felipe, I., Hristidis, V., Rishe, N.: Keyword search on spatial databases. In: IEEE 24th International Conference on Data Engineering, ICDE 2008, pp. 656–665. IEEE (2008) De Felipe, I., Hristidis, V., Rishe, N.: Keyword search on spatial databases. In: IEEE 24th International Conference on Data Engineering, ICDE 2008, pp. 656–665. IEEE (2008)
6.
go back to reference Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)CrossRef Feige, U.: A threshold of ln n for approximating set cover. J. ACM (JACM) 45(4), 634–652 (1998)CrossRef
7.
go back to reference Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM (JACM) 56(5), 25 (2009)MathSciNetCrossRef Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM (JACM) 56(5), 25 (2009)MathSciNetCrossRef
8.
go back to reference Garey, M.R., Johnson, D.S.: Computers and y: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). Computers and Intractability, vol. 340 (1979) Garey, M.R., Johnson, D.S.: Computers and y: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences). Computers and Intractability, vol. 340 (1979)
9.
go back to reference Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms 37(1), 66–84 (2000)MathSciNetCrossRef Garg, N., Konjevod, G., Ravi, R.: A polylogarithmic approximation algorithm for the group steiner tree problem. J. Algorithms 37(1), 66–84 (2000)MathSciNetCrossRef
10.
go back to reference Hjaltason, G.R., Samet, H.: Incremental distance join algorithms for spatial databases. In: ACM SIGMOD Record, vol. 27, pp. 237–248. ACM (1998) Hjaltason, G.R., Samet, H.: Incremental distance join algorithms for spatial databases. In: ACM SIGMOD Record, vol. 27, pp. 237–248. ACM (1998)
11.
go back to reference Hjaltason, G.R., Samet, H.: Distance browsing in spatial databases. ACM Trans. Database Syst. (TODS) 24(2), 265–318 (1999)CrossRef Hjaltason, G.R., Samet, H.: Distance browsing in spatial databases. ACM Trans. Database Syst. (TODS) 24(2), 265–318 (1999)CrossRef
12.
go back to reference Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Approx. Algorithms NP-Hard Probl. 94–143 (1997) Hochbaum, D.S.: Approximating covering and packing problems: set cover, vertex cover, independent set, and related problems. Approx. Algorithms NP-Hard Probl. 94–143 (1997)
13.
go back to reference Karpiński, M., Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problems, vol. 9. Oxford University Press, Oxford (1998)MATH Karpiński, M., Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problems, vol. 9. Oxford University Press, Oxford (1998)MATH
14.
go back to reference Katayama, N., Satoh, S.: The SR-tree: an index structure for high-dimensional nearest neighbor queries. In: ACM Sigmod Record, vol. 26, no. 2, pp. 369–380 (1997)CrossRef Katayama, N., Satoh, S.: The SR-tree: an index structure for high-dimensional nearest neighbor queries. In: ACM Sigmod Record, vol. 26, no. 2, pp. 369–380 (1997)CrossRef
15.
go back to reference Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, vol. 30, pp. 840–851. VLDB Endowment (2004) Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases, vol. 30, pp. 840–851. VLDB Endowment (2004)
16.
go back to reference Lappas, T., Liu, K., Terzi, E.: Finding a team of experts in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 467–476. ACM (2009) Lappas, T., Liu, K., Terzi, E.: Finding a team of experts in social networks. In: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 467–476. ACM (2009)
17.
go back to reference Li, C.T., Shan, M.K.: Team formation for generalized tasks in expertise social networks. In: 2010 IEEE Second International Conference on Social Computing (SocialCom), pp. 9–16. IEEE (2010) Li, C.T., Shan, M.K.: Team formation for generalized tasks in expertise social networks. In: 2010 IEEE Second International Conference on Social Computing (SocialCom), pp. 9–16. IEEE (2010)
18.
go back to reference Li, Y., Wu, D., Xu, J., Choi, B., Su, W.: Spatial-aware interest group queries in location-based social networks. Data Knowl. Eng. 92, 20–38 (2014)CrossRef Li, Y., Wu, D., Xu, J., Choi, B., Su, W.: Spatial-aware interest group queries in location-based social networks. Data Knowl. Eng. 92, 20–38 (2014)CrossRef
20.
go back to reference Long, C., Wong, R.C.W., Wang, K., Fu, A.W.C.: Collective spatial keyword queries: a distance owner-driven approach. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 689–700. ACM (2013) Long, C., Wong, R.C.W., Wang, K., Fu, A.W.C.: Collective spatial keyword queries: a distance owner-driven approach. In: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 689–700. ACM (2013)
21.
go back to reference Martins, B., Silva, M.J., Andrade, L.: Indexing and ranking in Geo-IR systems. In: Proceedings of the 2005 Workshop on Geographic Information Retrieval, pp. 31–34. ACM (2005) Martins, B., Silva, M.J., Andrade, L.: Indexing and ranking in Geo-IR systems. In: Proceedings of the 2005 Workshop on Geographic Information Retrieval, pp. 31–34. ACM (2005)
22.
go back to reference Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265–294 (1978)MathSciNetCrossRef Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265–294 (1978)MathSciNetCrossRef
23.
go back to reference Pagel, B.U., Six, H.W., Toben, H., Widmayer, P.: Towards an analysis of range query performance in spatial data structures. In: Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 214–221. ACM (1993) Pagel, B.U., Six, H.W., Toben, H., Widmayer, P.: Towards an analysis of range query performance in spatial data structures. In: Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 214–221. ACM (1993)
24.
go back to reference Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group nearest neighbor queries. In: Proceedings of the 20th International Conference on Data Engineering, pp. 301–312. IEEE (2004) Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group nearest neighbor queries. In: Proceedings of the 20th International Conference on Data Engineering, pp. 301–312. IEEE (2004)
26.
go back to reference Ross, P.E.: Top 11 technologies of the decade. IEEE Spectrum 48(1), 27–63 (2011)CrossRef Ross, P.E.: Top 11 technologies of the decade. IEEE Spectrum 48(1), 27–63 (2011)CrossRef
27.
go back to reference Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: ACM Sigmod Record, vol. 24, pp. 71–79. ACM (1995)CrossRef Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: ACM Sigmod Record, vol. 24, pp. 71–79. ACM (1995)CrossRef
28.
go back to reference Shin, H., Moon, B., Lee, S.: Adaptive multi-stage distance join processing. In: ACM SIGMOD Record, vol. 29, pp. 343–354. ACM (2000) Shin, H., Moon, B., Lee, S.: Adaptive multi-stage distance join processing. In: ACM SIGMOD Record, vol. 29, pp. 343–354. ACM (2000)
29.
go back to reference Tao, Y., Xiao, X., Cheng, R.: Range search on multidimensional uncertain data. ACM Trans. Database Syst. (TODS) 32(3), 15 (2007)CrossRef Tao, Y., Xiao, X., Cheng, R.: Range search on multidimensional uncertain data. ACM Trans. Database Syst. (TODS) 32(3), 15 (2007)CrossRef
30.
go back to reference Wu, D., Cong, G., Jensen, C.S.: A framework for efficient spatial web object retrieval. VLDB J. 21(6), 797–822 (2012)CrossRef Wu, D., Cong, G., Jensen, C.S.: A framework for efficient spatial web object retrieval. VLDB J. 21(6), 797–822 (2012)CrossRef
31.
go back to reference Wu, D., Yiu, M.L., Jensen, C.S., Cong, G.: Efficient continuously moving top-k spatial keyword query processing. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 541–552. IEEE (2011) Wu, D., Yiu, M.L., Jensen, C.S., Cong, G.: Efficient continuously moving top-k spatial keyword query processing. In: 2011 IEEE 27th International Conference on Data Engineering (ICDE), pp. 541–552. IEEE (2011)
32.
go back to reference Yang, D.N., Shen, C.Y., Lee, W.C., Chen, M.S.: 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, pp. 949–957. ACM (2012) Yang, D.N., Shen, C.Y., Lee, W.C., Chen, M.S.: 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, pp. 949–957. ACM (2012)
33.
go back to reference Zhou, Y., Xie, X., Wang, C., Gong, Y., Ma, W.Y.: Hybrid index structures for location-based web search. In: Proceedings of the 14th ACM International Conference on Information and Knowledge Management, pp. 155–162. ACM (2005) Zhou, Y., Xie, X., Wang, C., Gong, Y., Ma, W.Y.: Hybrid index structures for location-based web search. In: Proceedings of the 14th ACM International Conference on Information and Knowledge Management, pp. 155–162. ACM (2005)
Metadata
Title
A Measure and Conquer Algorithm for the Minimum User Spatial-Aware Interest Group Query Problem
Authors
Chih-Yang Huang
Po-Chuan Chien
Yen Hung Chen
Copyright Year
2019
Publisher
Springer Singapore
DOI
https://doi.org/10.1007/978-981-13-9190-3_47

Premium Partner