Retrieving Regions of Interest for User Exploration

Xin Cao, Gao Cong, Christian S. Jensen, Man Lung Yiu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Citations (Scopus)
123 Downloads (Pure)

Abstract

We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to iden- tify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conve- niently explore the PoIs. Motivated by this, we propose the length- constrained maximum-sum region (LCMSR) query that returns a spatial-network region that is located within a general region of in- terest, that does not exceed a given size constraint, and that best matches query keywords. Such a query maximizes the total weight of the PoIs in it w.r.t. the query keywords. We show that it is NP- hard to answer this query. We develop an approximation algorithm with a (5 + ǫ) approximation ratio utilizing a technique that scales node weights into integers. We also propose a more efficient heuris- tic algorithm and a greedy algorithm. Empirical studies on real data offer detailed insight into the accuracy of the proposed algorithms and show that the proposed algorithms are capable of computingresults efficiently and effectively.
Original languageEnglish
Title of host publicationProceedings of the VLDB Endowment (PVLDB)
Pages733-744
Number of pages12
Volume7
Publication statusPublished - 2014
EventInternational Conference on Very Large Data Bases - Hangzhou, China
Duration: 01 Sep 201405 Sep 2014

Conference

ConferenceInternational Conference on Very Large Data Bases
CountryChina
CityHangzhou
Period01/09/201405/09/2014

Cite this

Cao, X., Cong, G., Jensen, C. S., & Yiu, M. L. (2014). Retrieving Regions of Interest for User Exploration. In Proceedings of the VLDB Endowment (PVLDB) (Vol. 7, pp. 733-744)
Cao, Xin ; Cong, Gao ; Jensen, Christian S. ; Yiu, Man Lung. / Retrieving Regions of Interest for User Exploration. Proceedings of the VLDB Endowment (PVLDB). Vol. 7 2014. pp. 733-744
@inproceedings{1efc0dd9f5de425fadde38fca7fd2579,
title = "Retrieving Regions of Interest for User Exploration",
abstract = "We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to iden- tify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conve- niently explore the PoIs. Motivated by this, we propose the length- constrained maximum-sum region (LCMSR) query that returns a spatial-network region that is located within a general region of in- terest, that does not exceed a given size constraint, and that best matches query keywords. Such a query maximizes the total weight of the PoIs in it w.r.t. the query keywords. We show that it is NP- hard to answer this query. We develop an approximation algorithm with a (5 + ǫ) approximation ratio utilizing a technique that scales node weights into integers. We also propose a more efficient heuris- tic algorithm and a greedy algorithm. Empirical studies on real data offer detailed insight into the accuracy of the proposed algorithms and show that the proposed algorithms are capable of computingresults efficiently and effectively.",
author = "Xin Cao and Gao Cong and Jensen, {Christian S.} and Yiu, {Man Lung}",
year = "2014",
language = "English",
volume = "7",
pages = "733--744",
booktitle = "Proceedings of the VLDB Endowment (PVLDB)",

}

Cao, X, Cong, G, Jensen, CS & Yiu, ML 2014, Retrieving Regions of Interest for User Exploration. in Proceedings of the VLDB Endowment (PVLDB). vol. 7, pp. 733-744, International Conference on Very Large Data Bases, Hangzhou, China, 01/09/2014.

Retrieving Regions of Interest for User Exploration. / Cao, Xin; Cong, Gao; Jensen, Christian S.; Yiu, Man Lung.

Proceedings of the VLDB Endowment (PVLDB). Vol. 7 2014. p. 733-744.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Retrieving Regions of Interest for User Exploration

AU - Cao, Xin

AU - Cong, Gao

AU - Jensen, Christian S.

AU - Yiu, Man Lung

PY - 2014

Y1 - 2014

N2 - We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to iden- tify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conve- niently explore the PoIs. Motivated by this, we propose the length- constrained maximum-sum region (LCMSR) query that returns a spatial-network region that is located within a general region of in- terest, that does not exceed a given size constraint, and that best matches query keywords. Such a query maximizes the total weight of the PoIs in it w.r.t. the query keywords. We show that it is NP- hard to answer this query. We develop an approximation algorithm with a (5 + ǫ) approximation ratio utilizing a technique that scales node weights into integers. We also propose a more efficient heuris- tic algorithm and a greedy algorithm. Empirical studies on real data offer detailed insight into the accuracy of the proposed algorithms and show that the proposed algorithms are capable of computingresults efficiently and effectively.

AB - We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to iden- tify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conve- niently explore the PoIs. Motivated by this, we propose the length- constrained maximum-sum region (LCMSR) query that returns a spatial-network region that is located within a general region of in- terest, that does not exceed a given size constraint, and that best matches query keywords. Such a query maximizes the total weight of the PoIs in it w.r.t. the query keywords. We show that it is NP- hard to answer this query. We develop an approximation algorithm with a (5 + ǫ) approximation ratio utilizing a technique that scales node weights into integers. We also propose a more efficient heuris- tic algorithm and a greedy algorithm. Empirical studies on real data offer detailed insight into the accuracy of the proposed algorithms and show that the proposed algorithms are capable of computingresults efficiently and effectively.

M3 - Conference contribution

VL - 7

SP - 733

EP - 744

BT - Proceedings of the VLDB Endowment (PVLDB)

ER -

Cao X, Cong G, Jensen CS, Yiu ML. Retrieving Regions of Interest for User Exploration. In Proceedings of the VLDB Endowment (PVLDB). Vol. 7. 2014. p. 733-744