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.
|Title of host publication||Proceedings of the VLDB Endowment (PVLDB)|
|Number of pages||12|
|Publication status||Published - 2014|
|Event||International Conference on Very Large Data Bases - Hangzhou, China|
Duration: 01 Sep 2014 → 05 Sep 2014
|Conference||International Conference on Very Large Data Bases|
|Period||01/09/2014 → 05/09/2014|