Nowadays, with the rapid development of GPS-equipped mobile devices, location-based social networks have been emerging to bridge the gap between the physical world and online social networking services. Various types of data, such as personal locations, check-ins, microblogs and social relations, have been available in location-based social networks. Efficiently managing and analyzing such data to meet users' daily query requirements become a challenging task. Among all the existing works in location-based social networks, group query is one of the most important research topics. In this thesis, we investigate query techniques for location-based services in social networking applications. Specifically, considering a location-based social network, we study spatial-aware interest group queries, geo-social {dollar}k{dollar}-cover group queries, and social-aware ridesharing group queries. Firstly, we study the spatial-aware interest group queries in location-based social networks. Recently, most of the location-based social networks release check-in services that allow users to share their visiting locations with their friends. These locations, considered as spatial objects, are usually associated with a few tags that describe the features of those locations. Utilizing such information, we propose a new type of \emph{Spatial-aware Interest Group} (SIG) query that retrieves a user group of size {dollar}k{dollar} where each user is interested in the query keywords and the users are close to each other in the Euclidean space. We prove this query problem is NP-complete, and develop two efficient algorithms IOAIR and DOAIR based on the IR-tree for the processing of SIG queries. We also validate the performance efficiency of the proposed query processing algorithms by empirical evaluation. Secondly, we study the problem of geo-social {dollar}k{dollar}-cover group queries for collaborative spatial computing. In this problem, we propose a novel type of geo-social queries, called \emph{Geo-Social K-Cover Group} (GSKCG) query, which is based on spatial containment and a new modeling of social relationships. Intuitively, given a set of spatial query points and an underlying social network, a GSKCG query finds a minimum user group in which the members satisfy certain social relationship and their associated regions can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-complete. We consequently explore a set of effective pruning strategies to derive an efficient algorithm for finding the optimal solution. Moreover, we design a novel index structure tailored to our problem to further accelerate query processing. Extensive experiments demonstrate that our algorithm achieves desirable performance on real-life datasets. Thirdly, we study the problem of social-aware ridesharing group queries. With the deep penetration of smartphones and geo-locating devices, ridesharing is envisioned as a promising solution to transportation-related problems such as congestion and air pollution for metropolitan cities. Despite the potential to provide significant societal and environmental benefits, ridesharing has not so far been as popular as expected. Notable barriers include the social discomfort and safety concerns when traveling with strangers. To overcome these barriers, in this thesis, we propose a new type of \emph{Social-aware Ridesharing Group} (SaRG) query which retrieves a group of riders by taking into account their social connections besides traditional spatial proximities. Because the SaRG query problem is NP-hard, we design an efficient algorithm with a set of powerful pruning techniques to tackle this problem. We also present several incremental strategies to accelerate the search speed by reducing the repeated computations. Moreover, we propose a novel index tailored to the proposed problem to further speed up the query processing. Experimental results on real datasets show that our proposed algorithms achieve desirable performance. The works of this thesis show that the group query processing techniques are effective, which would facilitate the wider deployment of such query services in real applications
| Identifer | oai:union.ndltd.org:hkbu.edu.hk/oai:repository.hkbu.edu.hk:etd_oa-1202 |
| Date | 26 June 2015 |
| Creators | Li, Yafei |
| Publisher | HKBU Institutional Repository |
| Source Sets | Hong Kong Baptist University |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Open Access Theses and Dissertations |
| Rights | The author retains all rights to this work. The author has signed an agreement granting HKBU a non-exclusive license to archive and distribute their thesis. |
Page generated in 0.002 seconds