Xin Cao
Christian S. Jensen
Abstract
We consider an application scenario where points of interest (PoIs) each have a web presence and where a web user wants to identify a region that contains relevant PoIs that are relevant to a set of keywords, e.g., in preparation for deciding where to go to conveniently 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 interest, 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 heuristic 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.
- X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu. Spatial keyword querying. In ER, pages 16--29, 2012. Google Scholar
Digital Library
- X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige-based relevant spatial web objects. PVLDB, 3(1):373--384, 2010. Google ScholarDigital Library
- X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In SIGMOD, pages 373--384, 2011. Google ScholarDigital Library
- D.-W. Choi, C.-W. Chung, and Y. Tao. A scalable algorithm for maximizing range sum in spatial databases. PVLDB, 5(11):1088--1099, 2012. Google ScholarDigital Library
- G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2(1):337--348, 2009. Google ScholarDigital Library
- I. De Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, pages 656--665, 2008. Google ScholarDigital Library
- S. N. Durlauf and L. E. Blume. The New Palgrave Dictionary of Economics. Palgrave Macmillan, 2nd edition, 2008.Google Scholar
- N. Garg. A 3-approximation for the minimum tree spanning k vertices. In FOCS, pages 302--309, 1996. Google ScholarDigital Library
- M. X. Goemans and D. P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296--317, 1995. Google ScholarDigital Library
- R. Hariharan, B. Hore, C. Li, and S. Mehrotra. Processing spatial-keyword (SK) queries in geographic information retrieval (GIR) systems. In SSDBM, page 16, 2007. Google ScholarDigital Library
- J. Liu, G. Yu, and H. Sun. Subject-oriented top-k hot region queries in spatial dataset. In CIKM, pages 2409--2412, 2011. Google ScholarDigital Library
- C. Long, R. C.-W. Wong, K. Wang, and A. W.-C. Fu. Collective spatial keyword queries: a distance owner-driven approach. In SIGMOD Conference, pages 689--700, 2013. Google ScholarDigital Library
- J. M. Ponte and W. B. Croft. A language modeling approach to information retrieval. In SIGIR, pages 275--281, 1998. Google ScholarDigital Library
- R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi. Spanning trees short or small. In SODA, pages 546--555, 1994. Google ScholarDigital Library
- J. B. Rocha-Junior and K. Nørvåg. Top-k spatial keyword queries on road networks. In EDBT, pages 168--179, 2012. Google ScholarDigital Library
- Y. Tao, X. Hu, D. Choi, and C. Chung. Approximate MaxRS in spatial databases. PVLDB, 6(13):1546--1557, 2013. Google ScholarDigital Library
- X. Xiao, Q. Luo, Z. Li, X. Xie, and W.-Y. Ma. A large-scale study on map search logs. TWEB, 4(3):1--33, 2010. Google ScholarDigital Library
- D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, pages 688--699, 2009. Google ScholarDigital Library
- D. Zhang, B. C. Ooi, and A. K. H. Tung. Locating mapped resources in web 2.0. In ICDE, pages 521--532, 2010.Google ScholarCross Ref
- Y. Zhou, X. Xie, C. Wang, Y. Gong, and W.-Y. Ma. Hybrid index structures for location-based web search. In CIKM, pages 155--162, 2005. Google ScholarDigital Library
- J. Zobel and A. Moffat. Inverted files for text search engines. ACM Computing Surveys, 38(2):6, 2006. Google ScholarDigital Library
Recommendations
Description of interest regions with local binary patterns
This paper presents a novel method for interest region description. We adopted the idea that the appearance of an interest region can be well characterized by the distribution of its local features. The most well-known descriptor built on this idea is ...
Content based image retrieval based on relative locations of multiple regions of interest using selective regions matching
In this study, a novel technique for image retrieval based on selective regions matching using region codes is presented. All images in the database are uniformly divided into multiple regions and each region is assigned a 4-bit region code based upon ...
Description of interest regions with center-symmetric local binary patterns
ICVGIP'06: Proceedings of the 5th Indian conference on Computer Vision, Graphics and Image ProcessingLocal feature detection and description have gained a lot of interest in recent years since photometric descriptors computed for interest regions have proven to be very successful in many applications. In this paper, we propose a novel interest region ...
Comments