Finding map regions with high density of query keywords

Abstract

We consider the problem of finding map regions that best match query keywords. This region search problem can be applied in many practical scenarios such as shopping recommendation, searching for tourist attractions, and collision region detection for wireless sensor networks. While conventional map search retrieves isolate locations in a map, users frequently attempt to find regions of interest instead, e.g., detecting regions having too many wireless sensors to avoid collision, or finding shopping areas featuring various merchandise or tourist attractions of different styles. Finding regions of interest in a map is a non-trivial problem and retrieving regions of arbitrary shapes poses particular challenges. In this paper, we present a novel region search algorithm, dense region search (DRS), and its extensions, to find regions of interest by estimating the density of locations containing the query keywords in the region. Experiments on both synthetic and real-world datasets demonstrate the effectiveness of our algorithm.

Keywords

Map search / Region search / Region recommendation / Spatial keyword search / Geographic information system / Location-based service

References

[1] Aggarwal, A., Imai, H., Katoh, N., , 1989. Finding k points with minimum spanning trees and related problems. Proc. 5th Annual Symp. on Computational Geometry, p.283–291. https://doi.org/10.1145/73833.73865

[2] Agrawal, R., Gehrke, J., Gunopulos, D., , 1998. Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD Rec., 27(2):94-105. https://doi.org/10.1145/276304.276314

[3] Ankerst, M., Breunig, M.M., Kriegel, H.P., , 1999. Optics: ordering points to identify the clustering structure. SIGMOD Rec., 28(2):49–60. https://doi.org/10.1145/304182.304187

[4] Aurenhammer, F., 1991. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Comput. Surv., 23(3):345–405. https://doi.org/10.1145/116873.116880

[5] Chen, L.S., Cong, G., Jensen, C.S., , 2013. Spatial keyword query processing: an experimental evaluation. Proc. VLDB Endowm., 6(3):217–228. https://doi.org/10.14778/2535569.2448955

[6] Chen, Y.Y., Suel, T., Markowetz, A., 2006. Efficient query processing in geographic web search engines. Proc. ACM SIGMOD Int. Conf. on Management of Data, p.277–288. https://doi.org/10.1145/1142473.1142505

[7] Cheng, C.H., Fu, A.W., Zhang, Y., 1999. Entropy-based subspace clustering for mining numerical data. Proc. 5th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.84–93. https://doi.org/10.1145/312129.312199

[8] Christoforaki, M., He, J., Dimopoulos, C., , 2011. Text vs. space: efficient geo-search query processing. Proc. 20th ACM Int. Conf. on Information and Knowledge Management, p.423–432. https://doi.org/10.1145/2063576.2063641

[9] Cong, G., Jensen, C.S., Wu, D.M., 2009. Efficient retrieval of the top-k most relevant spatial web objects. Proc. VLDB Endowm., 2(1):337–348. https://doi.org/10.14778/1687627.1687666

[10] Ester, M., Kriegel, H.P., Sander, J., , 1996. A densitybased algorithm for discovering clusters in large spatial databases with noise. Proc. 2nd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.226–231.

[11] Fan, J., Li, G.L., Zhou, L.Z., , 2012. SEAL: spatiotextual similarity search. Proc. VLDB Endowm., 5(9):824–835. https://doi.org/10.14778/2311906.2311910

[12] Feige, U., Seltser, M., 1997. On the densest k-subgraph problem. Technical Report, the Weizmann Institute, Rehovot.

[13] Feige, U., Kortsarz, G., Peleg, D., 2001. The dense ksubgraph problem. Algorithmica, 29:410–421. https://doi.org/10.1007/s004530010050

[14] Guo, D.S., Peuquet, D.J., Gahegan, M., 2003. ICEAGE: interactive clustering and exploration of large and highdimensional geodata. GeoInformatica, 7(3):229–253. https://doi.org/10.1023/A:1025101015202

[15] Hinneburg, A., Keim, D.A., 1999. Optimal grid-clustering: towards breaking the curse of dimensionality in highdimensional clustering. Proc. 25th Int. Conf. on Very Large Data Bases, p.506–517.

[16] Jones, C.B., Purves, R., Ruas, A., , 2002. Spatial information retrieval and geographical ontologies an overview of the SPIRIT project. Proc. 25th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.387–388. https://doi.org/10.1145/564437.564457

[17] Joshi, T., Joy, J., Kellner, T., , 2008. Crosslingual location search. Proc. 31st Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.211–218. https://doi.org/10.1145/1390334.1390372

[18] Khodaei, A., Shahabi, C., Li, C., 2010. Hybrid indexing and seamless ranking of spatial and textual features of web documents. LNCS, 6261:450–466. https://doi.org/10.1007/978-3-642-15364-8_37

[19] Komusiewicz, C., Sorge, M., 2012. Finding dense subgraphs of sparse graphs. Proc. 7th Int. Conf. on Parameterized and Exact Computation, p.242–251. https://doi.org/10.1007/978-3-642-33293-7_23

[20] Lee, D.T., 1982. On k-nearest neighbor Voronoi diagrams in the plane. IEEE Trans. Comput., 100(6):478–487. https://doi.org/10.1109/tc.1982.1676031

[21] Leung, K.W.T., Lee, D.L., Lee, W.C., 2011. CLR: a collaborative location recommendation framework based on co-clustering. Proc. 34th Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, p.305–314. https://doi.org/10.1145/2009916.2009960

[22] Li, Z.S., Lee, K.C., Zheng, B.H., , 2011. IR-tree: an efficient index for geographic document search. IEEE Trans. Knowl. Data Eng., 23(4):585–599. https://doi.org/10.1109/tkde.2010.149

[23] Mai, H.T., Kim, J., Roh, Y.J., , 2013. STHist-C: a highly accurate cluster-based histogram for two and three dimensional geographic data points. GeoInformatica, 17(2):325–352. https://doi.org/10.1007/s10707-012-0154-y

[24] Ortega, E., Otera, I., Mancebo, S., 2014. TITIM GIS-tool: a GIS-based decision support system for measuring the territorial impact of transport infrastructures. Exp. Syst. Appl., 41(16):7641–7652. https://doi.org/10.1016/j.eswa.2014.05.028

[25] Saoussen, K., Sami, F., Takwa, T., , 2014. Tabu-based GIS for solving the vehicle routing problem. Exp. Syst. Appl., 41(14):6483–6493. https://doi.org/10.1016/j.eswa.2014.03.028

[26] Schikuta, E., 1996. Grid-clustering: an efficient hierarchical clustering method for very large data sets. Proc. 13th Int. Conf. on Pattern Recognition, p.101–105. https://doi.org/10.1109/icpr.1996.546732

[27] Shamos, M.I., Hoey, D., 1975. Closest-point problems. 16th Annual Symp. on Foundations of Computer Science, p.151–162. https://doi.org/10.1109/sfcs.1975.8

[28] Son, L.H., 2014. Optimizing municipal solid waste collection using chaotic particle swarm optimization in GIS based environments: a case study at Danang city, Vietnam. Exp. Syst. Appl., 41(18):8062–8074. https://doi.org/10.1016/j.eswa.2014.07.020

[29] Thomee, B., Rae, A., 2013. Uncovering locally characterizing regions within geotagged data. Proc. 22nd Int. Conf. on World Wide Web, p.1285–1296. https://doi.org/10.1145/2488388.2488500

[30] Vaid, S., Jones, C.B., Joho, H., , 2005. Spatio-textual indexing for geographical search on the web. Advances in Spatial and Temporal Databases, p.218–235. https://doi.org/10.1007/11535331_13

[31] Wei, L.Y., Zheng, Y., Peng, W.C., 2012. Constructing popular routes from uncertain trajectories. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.195–203. https://doi.org/10.1145/2339530.2339562

[32] Wu, D.M., Yiu, M.L., Cong, G., , 2012. Joint top-k spatial keyword query processing. IEEE Trans. Knowl. Data Eng., 24(10):1889–1903. https://doi.org/10.1109/icde.2011.5767861

[33] Yuan, J., Zheng, Y., Xie, X., 2012. Discovering regions of different functions in a city using human mobility and POIs. Proc. 18th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, p.186–194. https://doi.org/10.1145/2339530.2339561

[34] Zhang, F.Z., Wilkie, D., Zheng, Y., , 2013a. Sensing the pulse of urban refueling behavior. Proc. ACM Int. Joint Conf. on Pervasive and Ubiquitous Computing, p.13–22. https://doi.org/10.1145/2493432.2493448

[35] Zhang, Q., Kang, J.H., Gong, Y.Y., , 2013b. Map search via a factor graph model. Proc. 22nd ACM Int. Conf. on Information and Knowledge Management, p.69–78. https://doi.org/10.1145/2505515.2505674

[36] Zhou, Y.H., Xie, X., Wang, C., , 2005. Hybrid index structures for location-based web search. Proc. 14th ACM Int. Conf. on Information and Knowledge Management, p.155–162. https://doi.org/10.1145/1099554.1099584

RIGHTS & PERMISSIONS

2017 Zhejiang University and Springer-Verlag GmbH Germany