{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:02:16Z","timestamp":1772499736659,"version":"3.50.1"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,11]]},"abstract":"<jats:p>Important cloud services rely on spatial-keyword queries, containing a spatial predicate and arbitrary boolean keyword queries. In particular, we study the processing of such queries in main memory to support short response times. In contrast, current state-of-the-art spatial-keyword indexes and relational engines are designed for different assumptions. Rather than building a new spatial-keyword index, we employ a cost-based optimizer to process these queries using a spatial index and a keyword index. We address several technical challenges to achieve this goal. We introduce three operators as the building blocks to construct plans for main memory query processing. We then develop a cost model for the operators and query plans. We introduce five optimization techniques that efficiently reduce the search space and produce a query plan with low cost. The optimization techniques are computationally efficient, and they identify a query plan with a formal approximation guarantee under the common independence assumption. Furthermore, we extend the framework to exploit interesting orders. We implement the query optimizer to empirically validate our proposed approach using real-life datasets. The evaluation shows that the optimizations provide significant reduction in the average and tail latency of query processing: 7- to 11-fold reduction over using a single index in terms of 99th percentile response time. In addition, this approach outperforms existing spatial-keyword indexes, and DBMS query optimizers for both average and high-percentile response times.<\/jats:p>","DOI":"10.14778\/2850583.2850588","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"132-143","source":"Crossref","is-referenced-by-count":27,"title":["Processing and optimizing main memory spatial-keyword queries"],"prefix":"10.14778","volume":"9","author":[{"given":"Taesung","family":"Lee","sequence":"first","affiliation":[{"name":"Yonsei University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jin-woo","family":"Park","sequence":"additional","affiliation":[{"name":"POSTECH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanghoon","family":"Lee","sequence":"additional","affiliation":[{"name":"POSTECH"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seung-Won","family":"Hwang","sequence":"additional","affiliation":[{"name":"Yonsei University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sameh","family":"Elnikety","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxiong","family":"He","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"PostGIS PostGIS Spatial and Geographic Objects for PostgreSQL. http:\/\/postgis.net\/.  PostGIS PostGIS Spatial and Geographic Objects for PostgreSQL. http:\/\/postgis.net\/."},{"key":"e_1_2_1_2_1","unstructured":"PostgreSQL SQL Compliant Open Source Object-Relational Database Management System. http:\/\/www.postgresql.org\/.  PostgreSQL SQL Compliant Open Source Object-Relational Database Management System. http:\/\/www.postgresql.org\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/298514.298579"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575832_2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498698.1564507"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90071-5"},{"key":"e_1_2_1_7_1","first-page":"225","volume-title":"CIDR","volume":"5","author":"Boncz P. A.","year":"2005"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066184"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.68"},{"key":"e_1_2_1_10_1","first-page":"87","volume-title":"SSDBM","author":"Cary A.","year":"2010"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535569.2448955"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142505"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063641"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2408776.2408794"},{"key":"e_1_2_1_18_1","volume-title":"SODA","author":"Demaine E. D.","year":"2000"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/1938545.1938550"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.22"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/JRPROC.1952.273898"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735518"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1881867.1881914"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685289"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780195334548.001.0001","volume-title":"Catalan Numbers with Applications","author":"Koshy T.","year":"2008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497512"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007638"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066230"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247566"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2035253.2035270"},{"key":"e_1_2_1_31_1","volume-title":"Velocity","author":"Schurman E.","year":"2009"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/582095.582099"},{"issue":"4","key":"e_1_2_1_33_1","first-page":"323","article-title":"A comparison of techniques for calculating gradient and aspect from a gridded digital elevation model","volume":"3","author":"A. K.","year":"1989","journal-title":"IJGIS"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_13"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/22952.22955"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687633"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.172"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099584"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132956.1132959"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2850583.2850588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:17:35Z","timestamp":1672222655000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2850583.2850588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["10.14778\/2850583.2850588"],"URL":"https:\/\/doi.org\/10.14778\/2850583.2850588","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,11]]}}}