{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T17:25:58Z","timestamp":1770744358424,"version":"3.49.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,8,5]],"date-time":"2019-08-05T00:00:00Z","timestamp":1564963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSPATIAL Special"],"published-print":{"date-parts":[[2019,8,5]]},"abstract":"<jats:p>In this paper, we study the spatial pattern matching (SPM) query. Given a set D of spatial objects (e.g., houses and shops), each with a textual description, we aim at finding all combinations of objects from D that match a user-defined spatial pattern P. A pattern P is a graph whose vertices represent spatial objects, and edges denote distance relationships between them. The SPM query returns the instances that satisfy P. An example of P can be \"a house within 10-minute walk from a school, which is at least 2km away from a hospital\". The SPM query can benefit users such as house buyers, urban planners, and archaeologists. We first formally formulate the SPM problem, and then propose efficient query algorithms. We also develop an online system, called SpaceKey, which is based on the SPM query, to support some real applications such as property searching. Finally, we point out a list of possible research directions for future work.<\/jats:p>","DOI":"10.1145\/3355491.3355493","type":"journal-article","created":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:20:55Z","timestamp":1565094055000},"page":"3-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Spatial pattern matching"],"prefix":"10.1145","volume":"11","author":[{"given":"Yun","family":"Li","sequence":"first","affiliation":[{"name":"Nanjing University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,8,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448955"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498281"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2324897"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00035"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2492561"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00180"},{"key":"e_1_2_1_10_1","volume-title":"VLDB Journal","author":"Fang Y.","year":"2019","unstructured":"Y. Fang , Y. Li , R. Cheng , G. Cong , and N. Mamoulis . Evaluating pattern matching queries for spatial databases . In VLDB Journal . Springer-Verlag New York, Inc. , 2019 . Y. Fang, Y. Li, R. Cheng, G. Cong, and N. Mamoulis. Evaluating pattern matching queries for spatial databases. In VLDB Journal. Springer-Verlag New York, Inc., 2019."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_12_1","first-page":"45","article-title":"Matching structure and semantics: A survey on graph-based pattern matching","volume":"6","author":"Gallagher B.","year":"2006","unstructured":"B. Gallagher . Matching structure and semantics: A survey on graph-based pattern matching . AAAI FS , 6 : 45 -- 53 , 2006 . B. Gallagher. Matching structure and semantics: A survey on graph-based pattern matching. AAAI FS, 6:45--53, 2006.","journal-title":"AAAI FS"},{"key":"e_1_2_1_13_1","volume-title":"The urban pattern","author":"Gallion A. B.","year":"1950","unstructured":"A. B. Gallion and S. Eisner . The urban pattern ; city planning and design,. 1950 . A. B. Gallion and S. Eisner. The urban pattern; city planning and design,. 1950."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723723"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465275"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.172"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260812"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816695"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.77"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687727"}],"container-title":["SIGSPATIAL Special"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355491.3355493","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355491.3355493","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:34Z","timestamp":1750202614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355491.3355493"}},"subtitle":["a new direction for finding spatial objects"],"short-title":[],"issued":{"date-parts":[[2019,8,5]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,8,5]]}},"alternative-id":["10.1145\/3355491.3355493"],"URL":"https:\/\/doi.org\/10.1145\/3355491.3355493","relation":{},"ISSN":["1946-7729"],"issn-type":[{"value":"1946-7729","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,5]]},"assertion":[{"value":"2019-08-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}