Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Geo-Social Ranking: functions and query processing

  • Regular Paper
  • Published:
The VLDB Journal Aims and scope Submit manuscript

Abstract

Given a query location q, Geo-Social Ranking (GSR) ranks the users of a Geo-Social Network based on their distance to q, the number of their friends in the vicinity of q, and possibly the connectivity of those friends. We propose a general GSR framework and four GSR functions that assign scores in different ways: (i) LC, which is a weighted linear combination of social (i.e., friendships) and spatial (i.e., distance to q) aspects, (ii) RC, which is a ratio combination of the two aspects, (iii) HGS, which considers the number of friends in coincident circles centered at q, and (iv) GST, which takes into account triangles of friends in the vicinity of q. We investigate the behavior of the functions, qualitatively assess their results, and study the effects of their parameters. Moreover, for each ranking function, we design a query processing technique that utilizes its specific characteristics to efficiently retrieve the top-k users. Finally, we experimentally evaluate the performance of the top-k algorithms with real and synthetic datasets.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

Notes

  1. The inclusion of \(v_i\) in the relevant set \(V_i\) simplifies the problem formulation in LC and RC.

  2. Note that the current range in RC depends on the friends already in \(V_i\), whereas the relevant range in LC is defined based only on w and C, and it is the same for all users.

  3. An arithmetico-geometric sequence is the result of the multiplication of a geometric progression with the corresponding terms of an arithmetic progression. The sequence exhibits geometric decay and approaches a maximum value of \(4 \cdot w\), i.e., \(\lim _{b \rightarrow \infty }D_{b} = 4\cdot w\). Other series (e.g., arithmetic, geometric) can also be applied.

  4. This optimization is specific to Eq. 8. Other bounds would apply for different series.

  5. A directed bold edge from \(v_i\) to \(v_j\) means that \(v_j \in V_i\).

  6. An analogy for the conventional h-index is two authors that have the same h-index, but the second has more citations.

  7. Analysis on real GeoSN datasets has shown that the distances between pairs of friends follow a power law [7].

  8. The Barabasi–Albert generator produces graphs with small expected number of triangles. Therefore, we assign high importance to the spatial proximity in order to avoid examining a large fraction of the dataset.

References

  1. Armenatzoglou, N., Papadopoulos, S., Papadias, D.: A general framework for geo-social query processing. In: VLDB (2013)

  2. Aurenhammer, F., Edelsbrunner, H.: An optimal algorithm for constructing the weighted voronoi diagram in the plane. Pattern Recogn. 17(2), 251–257 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  3. Babenko, M., Goldberg, A., Gupta, A., Nagarajan, V.: Algorithms for hub label optimization. In: Automata, Languages, and Programming, LNCS 7965, pp. 69–80 (2013)

  4. Babington, P.: The title of the work, vol. 4 of 10. 3rd edn., An optional note 7 (1993)

  5. Bornholdt, S., Schuster, H.G., Wiley, J.: Handbook of graphs and networks, vol. 2. Wiley, Berlin (2003)

    MATH  Google Scholar 

  6. Brown, C., Nicosia, V., Scellato, S., Noulas, A., Mascolo, C.: Where online friends meet: social communities in location-based networks. In: International AAAI Conference on Weblogs and Social Media (ICWSM) (2012)

  7. Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: SIGKDD (2011)

  8. Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. In: PVLDB (2009)

  9. Foursquare statistics. https://foursquare.com/about/

  10. GroupOn Now! deals available on Foursquare. https://blog.groupon.com/cities/groupon-now-deals-available-in-foursquare/

  11. Hirsch, J.E.: An index to quantify an individual’s scientific research output. PNAS 102(46), 16569–16572 (2005)

  12. Hu, X., Tao, Y., Chung, C.-W.: Massive graph triangulation. In: SIGMOD (2013)

  13. Kendall, M.G.: A new measure of rank correlation. Biometrika, 30, 81–93 (1938)

  14. Liu, W., Sun, W., Chen, C., Huang, Y., Jing, Y., Chen, K.: Circle of friend query in geo-social networks. In: DASFAA (2012)

  15. Mouratidis, K., Li, J., Tang, Y., Mamoulis, N.: Joint search by social and spatial proximity. IEEE Trans. Knowl. Data Eng. 16(10), 1169–1184 (2014)

    Google Scholar 

  16. Scellato, S., Mascolo, C., Musolesi, M., Latora, V.: Distance matters: geo-social metrics for online social networks. In: WOSN (2010)

  17. Scellato, S., Noulas, A., Lambiotte, R., Mascolo, C.: Socio-spatial properties of online location-based social networks. ICWSM 11, 329–336 (2011)

    Google Scholar 

  18. Scellato, S., Noulas, A., Mascolo, C.: Exploiting place features in link prediction on location-based social networks. In: SIGKDD (2011)

  19. Tao, Y., Zhang, J., Papadias, D., Mamoulis, N.: An efficient cost model for optimization of nearest neighbor search in low and medium dimensional spaces. IEEE Trans. Knowl. Data Eng. 16(10), 1169–1184 (2004)

    Article  Google Scholar 

  20. van Gennip, Y., Hunter, B., Ahn, R., Elliott, P., Luh, K., Halvorson, M., Reid, S., Valasik, M., Wo, J., Tita, G.E., et al.: Community detection using spectral clustering on sparse geosocial data. SIAM J. Appl. Math. 73(1), 67–83 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  21. Wang, H., Terrovitis, M., Mamoulis, N.: Location recommendation in location-based social networks using user check-in data. In: SIGSPATIAL pp. 364–373 (2013)

  22. Wu, D., Yiu, M., Jensen, C., Cong, G.: Efficient continuously moving top-k spatial keyword query processing. In: ICDE (2011)

  23. Yang, D.-N., Shen, C.-Y., Lee, W.-C., Chen, M.-S.: On socio-spatial group query for location-based social networks. In: SIGKDD (2012)

  24. Ye, M., Yin, P., Lee, W.-C., Lee, D.-L.: Exploiting geographical influence for collaborative point-of-interest recommendation. In: SIGIR (2011)

  25. Yiu, M.L., U, L.H., Šaltenis, S., Tzoumas, K.: Efficient proximity detection among mobile users via self-tuning policies. In: PVLDB (2010)

  26. Zhang, C., Shou, L., Chen, K., Chen, G., Bei, Y.: Evaluating geo-social influence in location-based social networks. In: CIKM (2012)

  27. Zheng, Y., Zhang, L., Ma, Z., Xie, X., Ma, W.: Recommending friends and locations based on individual location history. ACM Trans. Web (TWEB) 5(1), 5 (2011)

    Google Scholar 

  28. Zhou, Y., Xie, X., Wang, C., Gong, Y., Ma, W.-Y.: Hybrid index structures for location-based web search. In: CIKM (2005)

Download references

Acknowledgments

This work was supported by grant GRF 617412 from Hong Kong RGC.

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Hong Kong University of Science and Technology, Hong Kong, People’s Republic of China

    Nikos Armenatzoglou, Ritesh Ahuja & Dimitris Papadias

Authors
  1. Nikos Armenatzoglou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ritesh Ahuja
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dimitris Papadias
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dimitris Papadias.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Armenatzoglou, N., Ahuja, R. & Papadias, D. Geo-Social Ranking: functions and query processing. The VLDB Journal 24, 783–799 (2015). https://doi.org/10.1007/s00778-015-0400-7

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00778-015-0400-7

Keywords

Search

Navigation