Finding map regions with high density of query keywords

Zhi YU; Can WANG; Jia-jun BU; Xia HU; Zhe WANG; Jia-he JIN

doi:10.1631/FITEE.1600043

Your Location：

Home >

Browse articles >

Finding map regions with high density of query keywords

Regular Papers | Updated：2022-05-19

- Finding map regions with high density of query keywords
- 地图关键字密集区域搜索技术
- Frontiers of Information Technology & Electronic Engineering Vol. 18, Issue 10, Pages: 1543-1555(2017)
- Affiliations：
  
  Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang Provincial Key Laboratory of Service Robot, College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China
  Hangzhou Science and Technology Information Research Institute, Hangzhou 310001, China
- Author bio：
  
  [ "YU Zhi, E-mail: yuzhirenzhe@zju.edu.cn" ]
  Can WANG, E-mail: wcan@zju.edu.cn
  [ "BU Jia-jun, E-mail: bjj@zju.edu.cn" ]
  [ "HU Xia, E-mail: huxia@hznet.com.cn" ]
  [ "WANG Zhe, E-mail: wangzhe89@zju.edu.cn" ]
  [ "JIN Jia-he, E-mail: jinjiahe@zju.edu.cn" ]
- Funds：
- DOI：10.1631/FITEE.1600043
  CLC： TP391
- Received：27 January 2016，
  
  Revised：2017-11-;3，
  
  Published：2017-10
- Accepted：
Scan QR Code
Zhi YU, Can WANG, Jia-jun BU, et al. Finding map regions with high density of query keywords[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1543-1555.
DOI：

Zhi YU, Can WANG, Jia-jun BU, et al. Finding map regions with high density of query keywords[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(10): 1543-1555. DOI： 10.1631/FITEE.1600043.

摘要

根据查询关键字找到相应地图区域，可以应用于购物推荐、旅游景点检索、无线传感网络冲突干扰区域检测等诸多场景。传统地图检索一般返回若干个兴趣点，而用户经常希望找到感兴趣的区域，比如不同风格的购物区域、推荐旅游景点区域，或查找无线节点最密集区域以避免无线网络冲突，等。由于区域形状不确定性等原因，地图区域检索是一个具有高度挑战性的问题。本文提出一种不规则区域检索算法DRS（dense region search）及其扩展形式，可高效预估搜索区域关键字密度，从而快速找到感兴趣的区域。在模拟和真实数据集上的试验证明，算法在不规则密集地图区域检索任务时有效。

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

references

A. Aggarwal , , , H. Imai , , , N. Katoh , , , 等 . . Finding k points with minimum spanning trees and related problems . . Proc. 5th Annual Symp. on Computational Geometry , , 1989 . . 283 - - 291 . . DOI: 10.1145/73833.73865 http://doi.org/10.1145/73833.73865 . .

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

M. Ankerst , , , M.M. Breunig , , , H.P. Kriegel , , , 等 . . Optics: ordering points to identify the clustering structure . . SIGMOD Rec. , , 1999 . . 28 ( ( 2 ): ): 49 - - 60 . . DOI: 10.1145/304182.304187 http://doi.org/10.1145/304182.304187 . .

F. Aurenhammer . . Voronoi diagrams—a survey of a fundamental geometric data structure . . ACM Comput. Surv. , , 1991 . . 23 ( ( 3 ): ): 345 - - 405 . . DOI: 10.1145/116873.116880 http://doi.org/10.1145/116873.116880 . .

L.S. Chen , , , G. Cong , , , C.S. Jensen , , , 等 . . Spatial keyword query processing: an experimental evaluation . . Proc. VLDB Endowm. , , 2013 . . 6 ( ( 3 ): ): 217 - - 228 . . DOI: 10.14778/2535569.2448955 http://doi.org/10.14778/2535569.2448955 . .

Y.Y. Chen , , , T. Suel , , , A. Markowetz . . Efficient query processing in geographic web search engines . . Proc. ACM SIGMOD Int. Conf. on Management of Data , , 2006 . . 277 - - 288 . . DOI: 10.1145/1142473.1142505 http://doi.org/10.1145/1142473.1142505 . .

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

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

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

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

J. Fan , , , G.L. Li , , , L.Z. Zhou , , , 等 . . SEAL: spatiotextual similarity search . . Proc. VLDB Endowm. , , 2012 . . 5 ( ( 9 ): ): 824 - - 835 . . DOI: 10.14778/2311906.2311910 http://doi.org/10.14778/2311906.2311910 . .

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

U. Feige , , , G. Kortsarz , , , D. Peleg . . The dense ksubgraph problem . . Algorithmica , , 2001 . . 29 410 - - 421 . . DOI: 10.1007/s004530010050 http://doi.org/10.1007/s004530010050 . .

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

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

C.B. Jones , , , R. Purves , , , A. Ruas , , , 等 . . 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 , , 2002 . . 387 - - 388 . . DOI: 10.1145/564437.564457 http://doi.org/10.1145/564437.564457 . .

T. Joshi , , , J. Joy , , , T. Kellner , , , 等 . . Crosslingual location search . . Proc. 31st Annual Int. ACM SIGIR Conf. on Research and Development in Information Retrieval , , 2008 . . 211 - - 218 . . DOI: 10.1145/1390334.1390372 http://doi.org/10.1145/1390334.1390372 . .

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

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

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

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

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

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

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

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

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

M.I. Shamos , , , D. Hoey . . Closest-point problems . . 16th Annual Symp. on Foundations of Computer Science , , 1975 . . 151 - - 162 . . DOI: 10.1109/sfcs.1975.8 http://doi.org/10.1109/sfcs.1975.8 . .

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

B. Thomee , , , A. Rae . . Uncovering locally characterizing regions within geotagged data . . Proc. 22nd Int. Conf. on World Wide Web , , 2013 . . 1285 - - 1296 . . DOI: 10.1145/2488388.2488500 http://doi.org/10.1145/2488388.2488500 . .

S. Vaid , , , C.B. Jones , , , H. Joho , , , 等 . . Spatio-textual indexing for geographical search on the web . . Advances in Spatial and Temporal Databases , , 2005 . . 218 - - 235 . . DOI: 10.1007/11535331_13 http://doi.org/10.1007/11535331_13 . .

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

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

J. Yuan , , , Y. Zheng , , , X. Xie . . 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 , , 2012 . . 186 - - 194 . . DOI: 10.1145/2339530.2339561 http://doi.org/10.1145/2339530.2339561 . .

F.Z. Zhang , , , D. Wilkie , , , Y. Zheng , , , 等 . . Sensing the pulse of urban refueling behavior . . Proc. ACM Int. Joint Conf. on Pervasive and Ubiquitous Computing , , 2013a . . 13 - - 22 . . DOI: 10.1145/2493432.2493448 http://doi.org/10.1145/2493432.2493448 . .

Q. Zhang , , , J.H. Kang , , , Y.Y. Gong , , , 等 . . Map search via a factor graph model . . Proc. 22nd ACM Int. Conf. on Information and Knowledge Management , , 2013b . . 69 - - 78 . . DOI: 10.1145/2505515.2505674 http://doi.org/10.1145/2505515.2505674 . .

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

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰