{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T05:44:22Z","timestamp":1694238262785},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,8]]},"abstract":"<jats:p>\n            Several services today are annotated with\n            <jats:italic>points of interest (PoIs)<\/jats:italic>\n            such as \"coffee shop\", \"park\", etc.\n            <jats:italic>A region of interest (RoI)<\/jats:italic>\n            is a neighborhood that contains PoIs relevant to the user. In this paper, we study the scenario where a user wants to identify the best RoI in a city. The user expresses relevance through a set of keywords denoting PoIs. Ideally, the RoI should be small enough in size such that the user can conveniently explore the PoIs. On the other hand, it should be as relevant as possible. How does one balance the importance of size versus relevance? To a user exploring the RoI on foot, size is more critical. However, for a user equipped with a vehicle, relevance is a more important factor. In this paper, we solve this dilemma through\n            <jats:italic>skyline subgraph queries<\/jats:italic>\n            on keyword-embedded road networks. Skyline subgraphs subsume the choice of optimization function for an RoI since the optimal RoI for any rational user is\n            <jats:italic>necessarily<\/jats:italic>\n            a part of the skyline set. Our analysis reveals that the problem of computing the skyline set is NP-hard. We overcome the computational bottleneck by proposing a polynomial-time approximation algorithm called\n            <jats:italic>SkyGraph.<\/jats:italic>\n            To further expedite the running time, we develop an index structure,\n            <jats:italic>Partner Index<\/jats:italic>\n            , that drastically prunes the search space and provides up to 3 orders of magnitude speed-up on real road networks over the baseline approach. The datasets and executables are available at http:\/\/www.cse.iitd.ac.in\/~sayan\/software.html.\n          <\/jats:p>","DOI":"10.14778\/3137628.3137647","type":"journal-article","created":{"date-parts":[[2017,9,7]],"date-time":"2017-09-07T13:35:53Z","timestamp":1504791353000},"page":"1382-1393","source":"Crossref","is-referenced-by-count":11,"title":["SkyGraph"],"prefix":"10.14778","volume":"10","author":[{"given":"Shiladitya","family":"Pande","sequence":"first","affiliation":[{"name":"IIT Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sayan","family":"Ranu","sequence":"additional","affiliation":[{"name":"IIT Delhi, New Delhi, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnab","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"IIT Kanpur, Kanpur, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225139"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920891"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732946"},{"key":"e_1_2_1_5_1","first-page":"87","volume-title":"SSDBM","author":"Cary A.","year":"2010","unstructured":"A. Cary , O. Wolfson , and N. Rishe . Efficient and scalable method for processing top-k spatial boolean queries . In SSDBM , pages 87 -- 95 . Springer , 2010 . A. Cary, O. Wolfson, and N. Rishe. Efficient and scalable method for processing top-k spatial boolean queries. In SSDBM, pages 87--95. Springer, 2010."},{"key":"e_1_2_1_6_1","first-page":"865","volume-title":"PVLDB","author":"Cho H.-J.","year":"2005","unstructured":"H.-J. Cho and C.-W. Chung . An efficient and scalable approach to cnn queries in a road network . In PVLDB , pages 865 -- 876 . VLDB Endowment , 2005 . H.-J. Cho and C.-W. Chung. An efficient and scalable approach to cnn queries in a road network. In PVLDB, pages 865--876. VLDB Endowment, 2005."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0696-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_1_10_1","first-page":"302","volume-title":"A 3-approximation for the minimum tree spanning k vertices. In focs","author":"Garg N.","year":"1996","unstructured":"N. Garg . A 3-approximation for the minimum tree spanning k vertices. In focs , volume 96 , pages 302 -- 309 , 1996 . N. Garg. A 3-approximation for the minimum tree spanning k vertices. In focs, volume 96, pages 302--309, 1996."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723723"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDBM.2007.22"},{"key":"e_1_2_1_13_1","first-page":"894","volume-title":"PVLDB","author":"Hu H.","year":"2006","unstructured":"H. Hu , D. L. Lee , and V. Lee . Distance indexing on road networks . In PVLDB , pages 894 -- 905 . VLDB Endowment , 2006 . H. Hu, D. L. Lee, and V. Lee. Distance indexing on road networks. In PVLDB, pages 894--905. VLDB Endowment, 2006."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11687238_14"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732993"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316762"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516476"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.243"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2426702"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465275"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315520"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247617"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.16"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.77"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447897"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498297"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113303"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505749"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3137628.3137647","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:00:50Z","timestamp":1672221650000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3137628.3137647"}},"subtitle":["retrieving regions of interest using skyline subgraph queries"],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":29,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.14778\/3137628.3137647"],"URL":"https:\/\/doi.org\/10.14778\/3137628.3137647","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}