Retrieving regions of interest for user exploration

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

36 Citations (Scopus)

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 computing results efficiently and effectively.
Original languageEnglish
Pages (from-to)733-744
Number of pages12
JournalProceedings of the VLDB Endowment
Volume7
Issue number9
DOIs
Publication statusPublished - 1 Jan 2014

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Cite this