{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:24:54Z","timestamp":1767137094556,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030548315","type":"print"},{"value":"9783030548322","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <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\/978-3-030-54832-2_5","type":"book-chapter","created":{"date-parts":[[2020,8,16]],"date-time":"2020-08-16T19:02:46Z","timestamp":1597604566000},"page":"34-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Efficient Index for Reachability Queries in Public Transport Networks"],"prefix":"10.1007","author":[{"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":[[2020,8,17]]},"reference":[{"key":"5_CR1","unstructured":"Zurich and Berlin GTFS. https:\/\/data.stadt-zuerich.ch\/dataset\/vbz_fahrplandaten_gtfs, https:\/\/daten.berlin.de\/datensaetze\/vbb-fahrplandaten-gtfs. Accessed 31 Jan 2020"},{"issue":"1","key":"5_CR2","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.: Group recommendation: semantics and efficiency. Proc. VLDB Endow. 2(1), 754\u2013765 (2009). https:\/\/doi.org\/10.14778\/1687627.1687713","journal-title":"Proc. VLDB Endow."},{"key":"5_CR3","doi-asserted-by":"publisher","unstructured":"Bast, H.: Car or public transport - two worlds. In: Efficient Algorithms: Essays Dedicated to Kurt Mehlhorn on the Occasion of His 60th Birthday, pp. 355\u2013367 (2009). https:\/\/doi.org\/10.1007\/978-3-642-03456-5_24","DOI":"10.1007\/978-3-642-03456-5_24"},{"key":"5_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","volume-title":"Algorithm Engineering","author":"H Bast","year":"2016","unstructured":"Bast, H., et al.: Route planning in transportation networks. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering. LNCS, vol. 9220, pp. 19\u201380. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49487-6_2"},{"key":"5_CR5","doi-asserted-by":"publisher","unstructured":"Bast, H., Hertel, M., Storandt, S.: Scalable transfer patterns. In: Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), pp. 15\u201329 (2016). https:\/\/doi.org\/10.1137\/1.9781611974317.2","DOI":"10.1137\/1.9781611974317.2"},{"key":"5_CR6","doi-asserted-by":"publisher","unstructured":"Bauer, V., Gamper, J., Loperfido, R., Profanter, S., Putzer, S., Timko, I.: Computing isochrones in multi-modal, schedule-based transport networks. In: Proceedings of the ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2008). https:\/\/doi.org\/10.1145\/1463434.1463524","DOI":"10.1145\/1463434.1463524"},{"key":"5_CR7","doi-asserted-by":"publisher","unstructured":"Blondel, V.D., Guillaume, J.L., Lambiotte, R., Lefebvre, E.: Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008(10) (2008). https:\/\/doi.org\/10.1088\/1742-5468\/2008\/10\/p10008","DOI":"10.1088\/1742-5468\/2008\/10\/p10008"},{"key":"5_CR8","doi-asserted-by":"publisher","unstructured":"Cheng, J., Huang, S., Wu, H., Fu, A.W.: 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 (2013). https:\/\/doi.org\/10.1145\/2463676.2465286","DOI":"10.1145\/2463676.2465286"},{"issue":"5","key":"5_CR9","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.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 1338\u20131355 (2003). https:\/\/doi.org\/10.1137\/S0097539702403098","journal-title":"SIAM J. Comput."},{"key":"5_CR10","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269\u2013271 (1959). https:\/\/doi.org\/10.1007\/BF01386390","journal-title":"Numerische Mathematik"},{"issue":"3","key":"5_CR11","first-page":"569","volume":"3","author":"I Flinsenberg","year":"2004","unstructured":"Flinsenberg, I., van der Horst, M., Lukkien, J., Verriet, J.: Creating graph partitions for fast optimum route planning. WSEAS Trans. Comput. 3(3), 569\u2013574 (2004)","journal-title":"WSEAS Trans. Comput."},{"key":"5_CR12","doi-asserted-by":"publisher","unstructured":"Gamper, J., B\u00f6hlen, M., Cometti, W., Innerebner, M.: Defining isochrones in multimodal spatial networks. In: Proceedings of the ACM International Conference on Information and Knowledge Management (CIKM), pp. 2381\u20132384 (2011). https:\/\/doi.org\/10.1145\/2063576.2063972","DOI":"10.1145\/2063576.2063972"},{"key":"5_CR13","doi-asserted-by":"publisher","unstructured":"Geisberger, R.: Contraction of timetable networks with realistic transfers. In: Proceedings of the International Symposium on Experimental Algorithms, pp. 71\u201382 (2010). https:\/\/doi.org\/10.1007\/978-3-642-13193-6_7","DOI":"10.1007\/978-3-642-13193-6_7"},{"key":"5_CR14","doi-asserted-by":"publisher","unstructured":"Jameson, A., Smyth, B.: Recommendation to groups. In: The Adaptive Web: Methods and Strategies of Web Personalization, pp. 596\u2013627 (2007). https:\/\/doi.org\/10.1007\/978-3-540-72079-9_20","DOI":"10.1007\/978-3-540-72079-9_20"},{"issue":"14","key":"5_CR15","doi-asserted-by":"publisher","first-page":"1978","DOI":"10.14778\/2556549.2556578","volume":"6","author":"R Jin","year":"2013","unstructured":"Jin, R., Wang, G.: Simple, fast, and scalable reachability oracle. Proc. VLDB Endow. 6(14), 1978\u20131989 (2013). https:\/\/doi.org\/10.14778\/2556549.2556578","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"5_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20(1), 359\u2013392 (1998). https:\/\/doi.org\/10.1137\/S1064827595287997","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"5_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10248079308903779","volume":"1","author":"DE Kaufmann","year":"1993","unstructured":"Kaufmann, D.E., Smith, R.L.: Fastest paths in time-dependent networks for intelligent vehicle-highway systems application. J. Intell. Transp. Syst. 1(1), 1\u201311 (1993). https:\/\/doi.org\/10.1080\/10248079308903779","journal-title":"J. Intell. Transp. Syst."},{"key":"5_CR18","doi-asserted-by":"publisher","unstructured":"Seufert, S., Anand, A., Bedathur, S.J., Weikum, G.: FERRARI: flexible and efficient reachability range assignment for graph indexing. In: Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 1009\u20131020 (2013). https:\/\/doi.org\/10.1109\/ICDE.2013.6544893","DOI":"10.1109\/ICDE.2013.6544893"},{"key":"5_CR19","unstructured":"Strasser, B.: Intriguingly simple and efficient time-dependent routing in road networks. CoRR abs\/1606.06636 (2016). http:\/\/arxiv.org\/abs\/1606.06636"},{"key":"5_CR20","doi-asserted-by":"publisher","unstructured":"Wang, S., Lin, W., Yang, Y., Xiao, X., Zhou, S.: 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 (2015). https:\/\/doi.org\/10.1145\/2723372.2749456","DOI":"10.1145\/2723372.2749456"},{"key":"5_CR21","doi-asserted-by":"publisher","unstructured":"Wu, H., Huang, Y., Cheng, J., Li, J., Ke, Y.: Reachability and time-based path queries in temporal graphs. In: Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 145\u2013156 (2016). https:\/\/doi.org\/10.1109\/ICDE.2016.7498236","DOI":"10.1109\/ICDE.2016.7498236"}],"updated-by":[{"DOI":"10.1007\/978-3-030-54832-2_17","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T00:00:00Z","timestamp":1597622400000}}],"container-title":["Lecture Notes in Computer Science","Advances in Databases and Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-54832-2_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T13:41:45Z","timestamp":1606743705000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-54832-2_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030548315","9783030548322"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-54832-2_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"17 August 2020","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The chapter was originally published without open access. With the author(s)\u2019 decision to opt for retrospective open access the copyright of the chapter changed to \u00a9 The Author(s) 2020 and the chapter is now available under a CC BY 4.0 license at link.springer.com","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ADBIS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Advances in Databases and Information Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Lyon","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"adbis2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/eric.univ-lyon2.fr\/adbis-tpdl-eda-2020\/adbis\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"152","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Due to the COVID-19 pandemic the conference was held online. Numbers for ADBIS, TPDL and EDA 2020 satellite events: full papers accepted: 26, short papers accepted: 5, submissions sent: 56","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}