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

34 Citations (Scopus)
170 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