Geo-Social K-Cover Group queries for collaborative spatial computing

Yafei Li; Rui Chen; Jianliang Xu; Qiao Huang; Haibo Hu; Byron Choi

doi:10.1109/ICDE.2016.7498399

Geo-Social K-Cover Group queries for collaborative spatial computing

Yafei Li, Rui Chen, Jianliang Xu, Qiao Huang, Haibo Hu, Byron Choi

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

8 Citations (Scopus)

Abstract

In this paper, we study a new type of Geo-Social K-Cover Group (GSKCG) queries that, given a set of query points and a social network, retrieves a minimum user group in which each user is socially related to at least k other users and the users' associated regions (e.g., familiar regions or service regions) can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-hard. 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.

Original language	English
Title of host publication	2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016
Publisher	IEEE
Pages	1510-1511
Number of pages	2
ISBN (Electronic)	9781509020195
DOIs	https://doi.org/10.1109/ICDE.2016.7498399
Publication status	Published - 22 Jun 2016
Externally published	Yes
Event	32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland Duration: 16 May 2016 → 20 May 2016

Conference

Conference	32nd IEEE International Conference on Data Engineering, ICDE 2016
Country/Territory	Finland
City	Helsinki
Period	16/05/16 → 20/05/16

ASJC Scopus subject areas

Artificial Intelligence
Computational Theory and Mathematics
Computer Graphics and Computer-Aided Design
Computer Networks and Communications
Information Systems
Information Systems and Management

More information

10.1109/ICDE.2016.7498399

Cite this

@inproceedings{d0907bde034f42089fb62130a64e91a3,

title = "Geo-Social K-Cover Group queries for collaborative spatial computing",

abstract = "In this paper, we study a new type of Geo-Social K-Cover Group (GSKCG) queries that, given a set of query points and a social network, retrieves a minimum user group in which each user is socially related to at least k other users and the users' associated regions (e.g., familiar regions or service regions) can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-hard. 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.",

author = "Yafei Li and Rui Chen and Jianliang Xu and Qiao Huang and Haibo Hu and Byron Choi",

year = "2016",

month = jun,

day = "22",

doi = "10.1109/ICDE.2016.7498399",

language = "English",

pages = "1510--1511",

booktitle = "2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016",

publisher = "IEEE",

address = "United States",

note = "32nd IEEE International Conference on Data Engineering, ICDE 2016 ; Conference date: 16-05-2016 Through 20-05-2016",

}

TY - GEN

T1 - Geo-Social K-Cover Group queries for collaborative spatial computing

AU - Li, Yafei

AU - Chen, Rui

AU - Xu, Jianliang

AU - Huang, Qiao

AU - Hu, Haibo

AU - Choi, Byron

PY - 2016/6/22

Y1 - 2016/6/22

N2 - In this paper, we study a new type of Geo-Social K-Cover Group (GSKCG) queries that, given a set of query points and a social network, retrieves a minimum user group in which each user is socially related to at least k other users and the users' associated regions (e.g., familiar regions or service regions) can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-hard. 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.

AB - In this paper, we study a new type of Geo-Social K-Cover Group (GSKCG) queries that, given a set of query points and a social network, retrieves a minimum user group in which each user is socially related to at least k other users and the users' associated regions (e.g., familiar regions or service regions) can jointly cover all the query points. Albeit its practical usefulness, the GSKCG query problem is NP-hard. 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.

UR - https://www.scopus.com/pages/publications/84980343517

U2 - 10.1109/ICDE.2016.7498399

DO - 10.1109/ICDE.2016.7498399

M3 - Conference article published in proceeding or book

SP - 1510

EP - 1511

BT - 2016 IEEE 32nd International Conference on Data Engineering, ICDE 2016

PB - IEEE

T2 - 32nd IEEE International Conference on Data Engineering, ICDE 2016

Y2 - 16 May 2016 through 20 May 2016

ER -

Geo-Social K-Cover Group queries for collaborative spatial computing

Abstract

Conference

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this