{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T16:45:56Z","timestamp":1762015556380,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>\n            Shortest path query is one of the most fundamental queries in spatial network databases. There exist algorithms that can process shortest path queries in real time. However, many complex applications require more than just the calculation of a single shortest path. For example, one of the common ways to determine the importance (or price) of a vertex or an edge in spatial network is to use Vickrey pricing, which intuitively values the vertex\n            <jats:italic>v<\/jats:italic>\n            (or edge\n            <jats:italic>e<\/jats:italic>\n            ) based on how much harder for travelling from the sources to the destinations without using\n            <jats:italic>v<\/jats:italic>\n            (or\n            <jats:italic>e<\/jats:italic>\n            ). In such cases, the\n            <jats:italic>alternative shortest paths<\/jats:italic>\n            without using\n            <jats:italic>v<\/jats:italic>\n            (or\n            <jats:italic>e<\/jats:italic>\n            ) are required. In this article, we propose using a precomputation based approach for both single pair alternative shortest path and all pairs shortest paths processing. To compute the alternative shortest path between a source and a destination efficiently, a na\u00efive way is to precompute and store all alternative shortest paths between every pair of vertices avoiding every possible vertex (or edge), which requires\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ) space. Currently, the state of the art approach for reducing the storage cost is to choose a subset of the vertices as center points, and only store the single-source alternative shortest paths from those center points. Such approach has the space complexity of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ). We propose a storage scheme termed\n            <jats:italic>iSPQF<\/jats:italic>\n            , which utilizes shortest path quadtrees by observing the relationships between each avoiding vertex and its corresponding alternative shortest paths. We have reduced the space complexity from the na\u00efive\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            ) (or the state of the art\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>4<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            )) to\n            <jats:italic>O<\/jats:italic>\n            (min(\n            <jats:italic>\u03b3, L<\/jats:italic>\n            )\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            ) with comparable query performance of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>K<\/jats:italic>\n            ), where\n            <jats:italic>K<\/jats:italic>\n            is the number of vertices in the returned paths,\n            <jats:italic>L<\/jats:italic>\n            is the diameter of the spatial network, and\n            <jats:italic>\u03b3<\/jats:italic>\n            is a value that depends on the structure of the spatial network, which is empirically estimated to be 40 for real road networks. Experiments on real road networks have shown that the space cost of the proposed iSPQF is scalable, and both the algorithms based on iSPQF are efficient.\n          <\/jats:p>","DOI":"10.1145\/2389241.2389248","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Finding Alternative Shortest Paths in Spatial Networks"],"prefix":"10.1145","volume":"37","author":[{"given":"Kexin","family":"Xie","sequence":"first","affiliation":[{"name":"University of Queensland"}]},{"given":"Ke","family":"Deng","sequence":"additional","affiliation":[{"name":"University of Queensland"}]},{"given":"Shuo","family":"Shang","sequence":"additional","affiliation":[{"name":"University of Queensland"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Queensland"}]},{"given":"Kai","family":"Zheng","sequence":"additional","affiliation":[{"name":"University of Queensland"}]}],"member":"320","published-online":{"date-parts":[[2012,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90003-5"},{"volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Bernstein A.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536431"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.41.0025"},{"volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases (VLDB\u201905)","author":"Cho H.-J.","key":"e_1_2_1_5_1"},{"volume-title":"Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC\u201902)","author":"Chowdhury R. A.","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705429847"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Dijkstra E. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1 1 269--271. Dijkstra E. 1959. A note on two problems in connexion with graphs. Numerische mathematik 1 1 269--271.","DOI":"10.1007\/BF01386390"},{"volume-title":"Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909)","author":"Duan R.","key":"e_1_2_1_10_1"},{"volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Emek Y.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201996)","author":"Frigioni D.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1048"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Goldberg A. V.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS\u201901)","author":"Hershberger J.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186815"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases (VLDB\u201903)","author":"Papadias D.","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_21"},{"volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet H.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.53"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1097064.1097093"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687763"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389248","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2389241.2389248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:58Z","timestamp":1750239298000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2389241.2389248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2389241.2389248"],"URL":"https:\/\/doi.org\/10.1145\/2389241.2389248","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2011-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}