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

36 Citations (Scopus)
233 Downloads (Pure)


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)
Number of pages12
Publication statusPublished - 2014
EventInternational Conference on Very Large Data Bases - Hangzhou, China
Duration: 01 Sep 201405 Sep 2014


ConferenceInternational Conference on Very Large Data Bases


Dive into the research topics of 'Retrieving Regions of Interest for User Exploration'. Together they form a unique fingerprint.

Cite this