{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T06:14:24Z","timestamp":1769926464446,"version":"3.49.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>\n            The advent of location-based services has led to an increased demand for performing operations on spatial networks in real time. The challenge lies in being able to cast operations on spatial networks in terms of relational operators so that they can be performed in the context of a database. A linear-sized construct termed a path oracle is introduced that compactly encodes the\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            shortest paths between every pair of vertices in a spatial network having\n            <jats:italic>n<\/jats:italic>\n            vertices thereby reducing each of the paths to a single tuple in a relational database and enables finding shortest paths by repeated application of a single SQL SELECT operator. The construction of the path oracle is based on the observed coherence between the spatial positions of both source and destination vertices and the shortest paths between them which facilitates the aggregation of source and destination vertices into groups that share common vertices or edges on the shortest paths between them. With the aid of the Well-Separated Pair (WSP) technique, which has been applied to spatial networks using the network distance measure, a path oracle is proposed that takes\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>s<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) space, where\n            <jats:italic>s<\/jats:italic>\n            is empirically estimated to be around 12 for road networks, but that can retrieve an intermediate link in a shortest path in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time using a B-tree. An additional construct termed the path-distance oracle of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \u00b7 max(\n            <jats:italic>s<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            , 1\/\u03b5\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            )) (empirically (\n            <jats:italic>n<\/jats:italic>\n            \u00b7 max(12\n            <jats:sup>2<\/jats:sup>\n            , 2.5\/\u03b5\n            <jats:sup>2<\/jats:sup>\n            ))) is proposed that can retrieve an intermediate vertex as well as an \u03b5-approximation of the network distances in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time using a B-tree. Experimental results indicate that the proposed oracles are linear in\n            <jats:italic>n<\/jats:italic>\n            which means that they are scalable and can enable complicated query processing scenarios on massive spatial network datasets.\n          <\/jats:p>","DOI":"10.14778\/1687627.1687763","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1210-1221","source":"Crossref","is-referenced-by-count":89,"title":["Path oracles for spatial networks"],"prefix":"10.14778","volume":"2","author":[{"given":"Jagan","family":"Sankaranarayanan","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD"}]},{"given":"Hanan","family":"Samet","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}]},{"given":"Houman","family":"Alborzi","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"291","volume-title":"Proc. of SODA","author":"Callahan P. B.","year":"1993","unstructured":"P. B. Callahan and S. R. Kosaraju . Faster algorithms for some geometric graph problems in higher dimensions . In Proc. of SODA , pp. 291 -- 300 , Jan. 1993 . P. B. Callahan and S. R. Kosaraju. Faster algorithms for some geometric graph problems in higher dimensions. In Proc. of SODA, pp. 291--300, Jan. 1993."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559907"},{"key":"e_1_2_1_3_1","first-page":"865","volume-title":"Proc. of VLDB","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 . Proc. of VLDB , pp. 865 -- 876 , Sep. 2005 . H.-J. Cho and C.-W. Chung. An efficient and scalable approach to CNN queries in a road network. Proc. of VLDB, pp. 865--876, Sep. 2005."},{"key":"e_1_2_1_4_1","first-page":"235","volume-title":"Proc. of CCCG","author":"Fischer J.","year":"2005","unstructured":"J. Fischer and S. Har-Peled . Dynamic well-separated pair decomposition made easy . In Proc. of CCCG , pp. 235 -- 238 , Aug. 2005 . J. Fischer and S. Har-Peled. Dynamic well-separated pair decomposition made easy. In Proc. of CCCG, pp. 235--238, Aug. 2005."},{"key":"e_1_2_1_5_1","first-page":"156","volume-title":"Proc. of SODA","author":"Goldberg A. V.","year":"2005","unstructured":"A. V. Goldberg and C. Harrelson . Computing the shortest path: A* search meets graph theory . In Proc. of SODA , pp. 156 -- 165 , Jan. 2005 . A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In Proc. of SODA, pp. 156--165, Jan. 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.687976"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316762"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69497-7_12"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315520"},{"key":"e_1_2_1_10_1","volume-title":"Morgan-Kaufmann","author":"Samet H.","year":"2006","unstructured":"H. Samet . Foundations of Multidimensional and Metric Data Structures . Morgan-Kaufmann , San Francisco , 2006 . H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan-Kaufmann, San Francisco, 2006."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_12_1","volume-title":"UMD","author":"Sankaranarayanan J.","year":"2008","unstructured":"J. Sankaranarayanan . Scalable query processing on spatial networks. PhD thesis , UMD , College Park, MD , Apr. 2008 . J. Sankaranarayanan. Scalable query processing on spatial networks. PhD thesis, UMD, College Park, MD, Apr. 2008."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.53"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380798"},{"key":"e_1_2_1_15_1","unstructured":"U.S. Census Bureau. TIGER\/Line Files Census 2000. http:\/\/www.census.gov\/geo\/www\/tiger\/.  U.S. Census Bureau. TIGER\/Line Files Census 2000. http:\/\/www.census.gov\/geo\/www\/tiger\/."},{"key":"e_1_2_1_16_1","unstructured":"U.S. Geological Survey. Major Roads of the United States. http:\/\/nationalatlas.gov\/atlasftp.html.  U.S. Geological Survey. Major Roads of the United States. http:\/\/nationalatlas.gov\/atlasftp.html."},{"key":"e_1_2_1_17_1","series-title":"LNCS","first-page":"776","volume-title":"Proc. of ESA","author":"Wagner D.","year":"2003","unstructured":"D. Wagner and T. Willhalm . Geometric speed-up techniques for finding shortest paths in large sparse graphs . In Proc. of ESA , pp. 776 -- 787 , Sep. 2003 , vol. 2832 of LNCS . D. Wagner and T. Willhalm. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proc. of ESA, pp. 776--787, Sep. 2003, vol. 2832 of LNCS."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:36:13Z","timestamp":1672227373000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687763"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687763","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}