{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T15:45:56Z","timestamp":1746287156040,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T00:00:00Z","timestamp":1628899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W1237"],"award-info":[{"award-number":["W1237"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Paris Lodron University of Salzburg"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Inf Syst Front"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Computing path queries such as the shortest path in public transport networks is challenging because the path costs between nodes change over time. A reachability query from a node at a given start time on such a network retrieves all points of interest (POIs) that are reachable within a given cost budget. Reachability queries are essential building blocks in many applications, for example, group recommendations, ranking spatial queries, or geomarketing. We propose an efficient solution for reachability queries in public transport networks. Currently, there are two options to solve reachability queries. (1) Execute a modified version of Dijkstra\u2019s algorithm that supports time-dependent edge traversal costs; this solution is slow since it must expand edge by edge and does not use an index. (2) Issue a separate path query for each single POI, i.e., a single reachability query requires answering many path queries. None of these solutions scales to large networks with many POIs. We propose a novel and lightweight reachability index. The key idea is to partition the network into cells. Then, in contrast to other approaches, we expand the network cell by cell. Empirical evaluations on synthetic and real-world networks confirm the efficiency and the effectiveness of our index-based reachability query solution.<\/jats:p>","DOI":"10.1007\/s10796-021-10164-2","type":"journal-article","created":{"date-parts":[[2021,8,14]],"date-time":"2021-08-14T05:02:27Z","timestamp":1628917347000},"page":"11-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Speeding Up Reachability Queries in Public Transport Networks Using Graph Partitioning"],"prefix":"10.1007","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3194-6830","authenticated-orcid":false,"given":"Bezaye","family":"Tesfaye","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikolaus","family":"Augsten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mateusz","family":"Pawlik","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael H.","family":"B\u00f6hlen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian S.","family":"Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,8,14]]},"reference":[{"issue":"1","key":"10164_CR1","doi-asserted-by":"publisher","first-page":"754","DOI":"10.14778\/1687627.1687713","volume":"2","author":"S Amer-Yahia","year":"2009","unstructured":"Amer-Yahia, S., Roy, S.B., Chawlat, A., Das, G., & Yu, C. (2009). Group recommendation: Semantics and efficiency. Proceedings of the VLDB Endowment, 2(1), 754\u2013765.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"10164_CR2","doi-asserted-by":"crossref","unstructured":"Bast, H. (2009). Car or public transport - two worlds. In Efficient algorithms: Essays dedicated to kurt mehlhorn on the occasion of his 60th birthday (pp. 355\u2013367).","DOI":"10.1007\/978-3-642-03456-5_24"},{"key":"10164_CR3","doi-asserted-by":"crossref","unstructured":"Bast, H., Delling, D., Goldberg, A.V., M\u00fcller-Hannemann, M., Pajor, T., Sanders, P., Wagner, D., & Werneck, R.F. (2016). Route planning in transportation networks. In Algorithm engineering: Selected results and surveys (pp. 19\u201380).","DOI":"10.1007\/978-3-319-49487-6_2"},{"key":"10164_CR4","doi-asserted-by":"crossref","unstructured":"Bast, H., Hertel, M., & Storandt, S. (2016). Scalable transfer patterns. In Proceedings of the meeting on algorithm engineering and experiments (ALENEX) (pp. 15\u201329).","DOI":"10.1137\/1.9781611974317.2"},{"key":"10164_CR5","doi-asserted-by":"crossref","unstructured":"Bauer, V., Gamper, J., Loperfido, R., Profanter, S., Putzer, S., & Timko, I. (2008). Computing isochrones in multi-modal, schedule-based transport networks. In Proceedings of the ACM SIGSPATIAL international conference on advances in geographic information systems.","DOI":"10.1145\/1463434.1463524"},{"key":"10164_CR6","doi-asserted-by":"crossref","unstructured":"Blondel, V.D., Guillaume, J.-L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10).","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"10164_CR7","doi-asserted-by":"crossref","unstructured":"Cheng, J., Huang, S., Wu, H., & Fu, A.W. (2013). TF-Label: A topological-folding labeling scheme for reachability querying in a large graph. In Proceedings of the ACM SIGMOD international conference on management of data (pp. 193\u2013204).","DOI":"10.1145\/2463676.2465286"},{"issue":"5","key":"10164_CR8","doi-asserted-by":"publisher","first-page":"1338","DOI":"10.1137\/S0097539702403098","volume":"32","author":"E Cohen","year":"2003","unstructured":"Cohen, E., Halperin, E., Kaplan, H., & Zwick, U. (2003). Reachability and distance queries via 2-hop labels. SIAM Journal on Computing, 32(5), 1338\u20131355.","journal-title":"SIAM Journal on Computing"},{"key":"10164_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"10164_CR10","doi-asserted-by":"crossref","unstructured":"Gamper, J., B\u00f6hlen, M., Cometti, W., & Innerebner, M. (2011). Defining isochrones in multimodal spatial networks. In Proceedings of the ACM international conference on information and knowledge management (CIKM) (pp. 2381\u20132384).","DOI":"10.1145\/2063576.2063972"},{"key":"10164_CR11","doi-asserted-by":"crossref","unstructured":"Geisberger, R. (2010). Contraction of timetable networks with realistic transfers. In Proceedings of the international symposium on experimental algorithms (pp. 71\u201382).","DOI":"10.1007\/978-3-642-13193-6_7"},{"key":"10164_CR12","doi-asserted-by":"crossref","unstructured":"Jameson, A., & Smyth, B. (2007). Recommendation to groups. In The adaptive web: Methods and strategies of web personalization (pp. 596\u2013627).","DOI":"10.1007\/978-3-540-72079-9_20"},{"issue":"14","key":"10164_CR13","doi-asserted-by":"publisher","first-page":"1978","DOI":"10.14778\/2556549.2556578","volume":"6","author":"R Jin","year":"2013","unstructured":"Jin, R., & Wang, G. (2013). Simple, fast, and scalable reachability oracle. Proceedings of the VLDB Endowment, 6(14), 1978\u20131989.","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"1","key":"10164_CR14","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., & Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, 20(1), 359\u2013392.","journal-title":"SIAM Journal on Scientific Computing"},{"issue":"1","key":"10164_CR15","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G Karypis","year":"1998","unstructured":"Karypis, G., & Kumar, V. (1998). Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing, 48(1), 96\u2013129.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"1","key":"10164_CR16","first-page":"1","volume":"1","author":"DE Kaufmann","year":"1993","unstructured":"Kaufmann, D.E., & Smith, R.L. (1993). Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. Journal of Intelligent Transportation Systems, 1(1), 1\u201311.","journal-title":"Journal of Intelligent Transportation Systems"},{"key":"10164_CR17","doi-asserted-by":"publisher","first-page":"026113","DOI":"10.1103\/PhysRevE.69.026113","volume":"69","author":"MEJ Newman","year":"2004","unstructured":"Newman, M.E.J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69, 026113.","journal-title":"Physical Review E"},{"key":"10164_CR18","doi-asserted-by":"crossref","unstructured":"Seufert, S., Anand, A., Bedathur, S.J., & Weikum, G. (2013). FERRARI: Flexible and efficient reachability range assignment for graph indexing. In Proceedings of the IEEE international conference on data engineering (ICDE) (pp. 1009\u20131020).","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"10164_CR19","unstructured":"Strasser, B. (2016). Intriguingly simple and efficient time-dependent routing in road networks. arXiv:1606.06636."},{"key":"10164_CR20","unstructured":"Tesfaye, B., & Augsten, N. (2016). Reachability queries in public transport networks. In Proceedings of the 28th GI-Workshop Grundlagen von Datenbanken, N\u00f6rten Hardenberg, Germany, May 24-27, 2016, (Vol. 1594 pp. 109\u2013114)."},{"key":"10164_CR21","doi-asserted-by":"crossref","unstructured":"Tesfaye, B., Augsten, N., Pawlik, M., B\u00f6hlen, M. H., & Jensen, C.S. (2020). An efficient index for reachability queries in public transport networks. In Advances in databases and information systems - 24th european conference, ADBIS 2020, lyon, france, august 25-27, 2020, proceedings, (Vol. 12245 pp. 34\u201348).","DOI":"10.1007\/978-3-030-54832-2_5"},{"key":"10164_CR22","doi-asserted-by":"crossref","unstructured":"Traag, V.A., Waltman, L., & van Eck, N.J. (2019). From louvain to leiden: guaranteeing well-connected communities. Nature scientific reports 9.","DOI":"10.1038\/s41598-019-41695-z"},{"key":"10164_CR23","doi-asserted-by":"crossref","unstructured":"Wang, S., Lin, W., Yang, Y., Xiao, X., & Zhou, S. (2015). Efficient route planning on public transportation networks A labelling approach. In Proceedings of the ACM SIGMOD international conference on management of data (pp. 967\u2013982).","DOI":"10.1145\/2723372.2749456"},{"key":"10164_CR24","doi-asserted-by":"crossref","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., & Ke, Y. (2016). Reachability and time-based path queries in temporal graphs. In Proceedings of the IEEE international conference on data engineering (ICDE) (pp. 145\u2013156).","DOI":"10.1109\/ICDE.2016.7498236"},{"key":"10164_CR25","unstructured":"Zurich, & Berlin. (2020). GTFS. https:\/\/data.stadt-zuerich.ch\/dataset\/vbz_fahrplandaten_gtfs, https:\/\/daten.berlin.de\/datensaetze\/vbb-fahrplandaten-gtfs, Accessed January 31, 2020."}],"container-title":["Information Systems Frontiers"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10796-021-10164-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10796-021-10164-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10796-021-10164-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,15]],"date-time":"2022-03-15T08:26:58Z","timestamp":1647332818000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10796-021-10164-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,14]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10164"],"URL":"https:\/\/doi.org\/10.1007\/s10796-021-10164-2","relation":{},"ISSN":["1387-3326","1572-9419"],"issn-type":[{"type":"print","value":"1387-3326"},{"type":"electronic","value":"1572-9419"}],"subject":[],"published":{"date-parts":[[2021,8,14]]},"assertion":[{"value":"17 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2021","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of this paper was updated to include the funding note.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}