EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding Article Swipe
Jinchun Du
,
Bojie Shen
,
Muhammad Aamir Cheema
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2408.11341
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2408.11341
The Euclidean Shortest Path Problem (ESPP), which involves finding the shortest path in a Euclidean plane with polygonal obstacles, is a classic problem with numerous real-world applications. The current state-of-the-art solution, Euclidean Hub Labeling (EHL), offers ultra-fast query performance, outperforming existing techniques by 1-2 orders of magnitude in runtime efficiency. However, this performance comes at the cost of significant memory overhead, requiring up to tens of gigabytes of storage on large maps, which can limit its applicability in memory-constrained environments like mobile phones or smaller devices. Additionally, EHL's memory usage can only be determined after index construction, and while it provides a memory-runtime tradeoff, it does not fully optimize memory utilization. In this work, we introduce an improved version of EHL, called EHL*, which overcomes these limitations. A key contribution of EHL* is its ability to create an index that adheres to a specified memory budget while optimizing query runtime performance. Moreover, EHL* can leverage preknown query distributions, a common scenario in many real-world applications to further enhance runtime efficiency. Our results show that EHL* can reduce memory usage by up to 10-20 times without much impact on query runtime performance compared to EHL, making it a highly effective solution for optimal pathfinding in memory-constrained environments.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2408.11341
- https://arxiv.org/pdf/2408.11341
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4405426041
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4405426041Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2408.11341Digital Object Identifier
- Title
-
EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean PathfindingWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-08-21Full publication date if available
- Authors
-
Jinchun Du, Bojie Shen, Muhammad Aamir CheemaList of authors in order
- Landing page
-
https://arxiv.org/abs/2408.11341Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2408.11341Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2408.11341Direct OA link when available
- Concepts
-
Pathfinding, Search engine indexing, Euclidean geometry, Computer science, Artificial intelligence, Information retrieval, Theoretical computer science, Mathematics, Geometry, Graph, Shortest path problemTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4405426041 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2408.11341 |
| ids.doi | https://doi.org/10.48550/arxiv.2408.11341 |
| ids.openalex | https://openalex.org/W4405426041 |
| fwci | |
| type | preprint |
| title | EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11245 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9696000218391418 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2206 |
| topics[0].subfield.display_name | Computational Mechanics |
| topics[0].display_name | Advanced Numerical Analysis Techniques |
| topics[1].id | https://openalex.org/T10996 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9646000266075134 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1704 |
| topics[1].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[1].display_name | Computational Geometry and Mesh Generation |
| topics[2].id | https://openalex.org/T10601 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9584000110626221 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1707 |
| topics[2].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[2].display_name | Handwritten Text Recognition Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C25321074 |
| concepts[0].level | 4 |
| concepts[0].score | 0.8398135304450989 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1969601 |
| concepts[0].display_name | Pathfinding |
| concepts[1].id | https://openalex.org/C75165309 |
| concepts[1].level | 2 |
| concepts[1].score | 0.7336557507514954 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q2258979 |
| concepts[1].display_name | Search engine indexing |
| concepts[2].id | https://openalex.org/C129782007 |
| concepts[2].level | 2 |
| concepts[2].score | 0.558024525642395 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q162886 |
| concepts[2].display_name | Euclidean geometry |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.5338242053985596 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C154945302 |
| concepts[4].level | 1 |
| concepts[4].score | 0.32937130331993103 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[4].display_name | Artificial intelligence |
| concepts[5].id | https://openalex.org/C23123220 |
| concepts[5].level | 1 |
| concepts[5].score | 0.32723480463027954 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q816826 |
| concepts[5].display_name | Information retrieval |
| concepts[6].id | https://openalex.org/C80444323 |
| concepts[6].level | 1 |
| concepts[6].score | 0.3248326778411865 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[6].display_name | Theoretical computer science |
| concepts[7].id | https://openalex.org/C33923547 |
| concepts[7].level | 0 |
| concepts[7].score | 0.2610747516155243 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[7].display_name | Mathematics |
| concepts[8].id | https://openalex.org/C2524010 |
| concepts[8].level | 1 |
| concepts[8].score | 0.061693549156188965 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[8].display_name | Geometry |
| concepts[9].id | https://openalex.org/C132525143 |
| concepts[9].level | 2 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[9].display_name | Graph |
| concepts[10].id | https://openalex.org/C22590252 |
| concepts[10].level | 3 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q1058754 |
| concepts[10].display_name | Shortest path problem |
| keywords[0].id | https://openalex.org/keywords/pathfinding |
| keywords[0].score | 0.8398135304450989 |
| keywords[0].display_name | Pathfinding |
| keywords[1].id | https://openalex.org/keywords/search-engine-indexing |
| keywords[1].score | 0.7336557507514954 |
| keywords[1].display_name | Search engine indexing |
| keywords[2].id | https://openalex.org/keywords/euclidean-geometry |
| keywords[2].score | 0.558024525642395 |
| keywords[2].display_name | Euclidean geometry |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.5338242053985596 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[4].score | 0.32937130331993103 |
| keywords[4].display_name | Artificial intelligence |
| keywords[5].id | https://openalex.org/keywords/information-retrieval |
| keywords[5].score | 0.32723480463027954 |
| keywords[5].display_name | Information retrieval |
| keywords[6].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[6].score | 0.3248326778411865 |
| keywords[6].display_name | Theoretical computer science |
| keywords[7].id | https://openalex.org/keywords/mathematics |
| keywords[7].score | 0.2610747516155243 |
| keywords[7].display_name | Mathematics |
| keywords[8].id | https://openalex.org/keywords/geometry |
| keywords[8].score | 0.061693549156188965 |
| keywords[8].display_name | Geometry |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2408.11341 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2408.11341 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | text |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2408.11341 |
| locations[1].id | doi:10.48550/arxiv.2408.11341 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2408.11341 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5114073965 |
| authorships[0].author.orcid | |
| authorships[0].author.display_name | Jinchun Du |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Du, Jinchun |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5022748563 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-6551-5302 |
| authorships[1].author.display_name | Bojie Shen |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Shen, Bojie |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5047549903 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-2139-9121 |
| authorships[2].author.display_name | Muhammad Aamir Cheema |
| authorships[2].author_position | last |
| authorships[2].raw_author_name | Cheema, Muhammad Aamir |
| authorships[2].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2408.11341 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2024-12-16T00:00:00 |
| display_name | EHL*: Memory-Budgeted Indexing for Ultrafast Optimal Euclidean Pathfinding |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11245 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9696000218391418 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2206 |
| primary_topic.subfield.display_name | Computational Mechanics |
| primary_topic.display_name | Advanced Numerical Analysis Techniques |
| related_works | https://openalex.org/W4285687848, https://openalex.org/W4289994039, https://openalex.org/W2240526870, https://openalex.org/W3100156731, https://openalex.org/W2623016776, https://openalex.org/W1967962134, https://openalex.org/W3128311703, https://openalex.org/W3101047024, https://openalex.org/W2188505374, https://openalex.org/W1558342070 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2408.11341 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2408.11341 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | text |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2408.11341 |
| primary_location.id | pmh:oai:arXiv.org:2408.11341 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2408.11341 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | text |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2408.11341 |
| publication_date | 2024-08-21 |
| publication_year | 2024 |
| referenced_works_count | 0 |
| abstract_inverted_index.A | 127 |
| abstract_inverted_index.a | 13, 20, 101, 142, 158, 196 |
| abstract_inverted_index.In | 111 |
| abstract_inverted_index.an | 116, 137 |
| abstract_inverted_index.at | 54 |
| abstract_inverted_index.be | 92 |
| abstract_inverted_index.by | 42, 179 |
| abstract_inverted_index.in | 12, 47, 77, 161, 203 |
| abstract_inverted_index.is | 19, 132 |
| abstract_inverted_index.it | 99, 104, 195 |
| abstract_inverted_index.of | 45, 57, 65, 67, 119, 130 |
| abstract_inverted_index.on | 69, 187 |
| abstract_inverted_index.or | 83 |
| abstract_inverted_index.to | 63, 135, 141, 165, 181, 192 |
| abstract_inverted_index.up | 62, 180 |
| abstract_inverted_index.we | 114 |
| abstract_inverted_index.1-2 | 43 |
| abstract_inverted_index.Hub | 32 |
| abstract_inverted_index.Our | 170 |
| abstract_inverted_index.The | 0, 27 |
| abstract_inverted_index.and | 97 |
| abstract_inverted_index.can | 73, 90, 153, 175 |
| abstract_inverted_index.for | 200 |
| abstract_inverted_index.its | 75, 133 |
| abstract_inverted_index.key | 128 |
| abstract_inverted_index.not | 106 |
| abstract_inverted_index.the | 9, 55 |
| abstract_inverted_index.EHL* | 131, 152, 174 |
| abstract_inverted_index.EHL, | 120, 193 |
| abstract_inverted_index.Path | 3 |
| abstract_inverted_index.cost | 56 |
| abstract_inverted_index.does | 105 |
| abstract_inverted_index.like | 80 |
| abstract_inverted_index.many | 162 |
| abstract_inverted_index.much | 185 |
| abstract_inverted_index.only | 91 |
| abstract_inverted_index.path | 11 |
| abstract_inverted_index.show | 172 |
| abstract_inverted_index.tens | 64 |
| abstract_inverted_index.that | 139, 173 |
| abstract_inverted_index.this | 51, 112 |
| abstract_inverted_index.with | 16, 23 |
| abstract_inverted_index.10-20 | 182 |
| abstract_inverted_index.EHL's | 87 |
| abstract_inverted_index.EHL*, | 122 |
| abstract_inverted_index.after | 94 |
| abstract_inverted_index.comes | 53 |
| abstract_inverted_index.fully | 107 |
| abstract_inverted_index.index | 95, 138 |
| abstract_inverted_index.large | 70 |
| abstract_inverted_index.limit | 74 |
| abstract_inverted_index.maps, | 71 |
| abstract_inverted_index.plane | 15 |
| abstract_inverted_index.query | 37, 148, 156, 188 |
| abstract_inverted_index.these | 125 |
| abstract_inverted_index.times | 183 |
| abstract_inverted_index.usage | 89, 178 |
| abstract_inverted_index.which | 6, 72, 123 |
| abstract_inverted_index.while | 98, 146 |
| abstract_inverted_index.work, | 113 |
| abstract_inverted_index.(EHL), | 34 |
| abstract_inverted_index.budget | 145 |
| abstract_inverted_index.called | 121 |
| abstract_inverted_index.common | 159 |
| abstract_inverted_index.create | 136 |
| abstract_inverted_index.highly | 197 |
| abstract_inverted_index.impact | 186 |
| abstract_inverted_index.making | 194 |
| abstract_inverted_index.memory | 59, 88, 109, 144, 177 |
| abstract_inverted_index.mobile | 81 |
| abstract_inverted_index.offers | 35 |
| abstract_inverted_index.orders | 44 |
| abstract_inverted_index.phones | 82 |
| abstract_inverted_index.reduce | 176 |
| abstract_inverted_index.(ESPP), | 5 |
| abstract_inverted_index.Problem | 4 |
| abstract_inverted_index.ability | 134 |
| abstract_inverted_index.adheres | 140 |
| abstract_inverted_index.classic | 21 |
| abstract_inverted_index.current | 28 |
| abstract_inverted_index.enhance | 167 |
| abstract_inverted_index.finding | 8 |
| abstract_inverted_index.further | 166 |
| abstract_inverted_index.optimal | 201 |
| abstract_inverted_index.problem | 22 |
| abstract_inverted_index.results | 171 |
| abstract_inverted_index.runtime | 48, 149, 168, 189 |
| abstract_inverted_index.smaller | 84 |
| abstract_inverted_index.storage | 68 |
| abstract_inverted_index.version | 118 |
| abstract_inverted_index.without | 184 |
| abstract_inverted_index.However, | 50 |
| abstract_inverted_index.Labeling | 33 |
| abstract_inverted_index.Shortest | 2 |
| abstract_inverted_index.compared | 191 |
| abstract_inverted_index.devices. | 85 |
| abstract_inverted_index.existing | 40 |
| abstract_inverted_index.improved | 117 |
| abstract_inverted_index.involves | 7 |
| abstract_inverted_index.leverage | 154 |
| abstract_inverted_index.numerous | 24 |
| abstract_inverted_index.optimize | 108 |
| abstract_inverted_index.preknown | 155 |
| abstract_inverted_index.provides | 100 |
| abstract_inverted_index.scenario | 160 |
| abstract_inverted_index.shortest | 10 |
| abstract_inverted_index.solution | 199 |
| abstract_inverted_index.Euclidean | 1, 14, 31 |
| abstract_inverted_index.Moreover, | 151 |
| abstract_inverted_index.effective | 198 |
| abstract_inverted_index.gigabytes | 66 |
| abstract_inverted_index.introduce | 115 |
| abstract_inverted_index.magnitude | 46 |
| abstract_inverted_index.overcomes | 124 |
| abstract_inverted_index.overhead, | 60 |
| abstract_inverted_index.polygonal | 17 |
| abstract_inverted_index.requiring | 61 |
| abstract_inverted_index.solution, | 30 |
| abstract_inverted_index.specified | 143 |
| abstract_inverted_index.tradeoff, | 103 |
| abstract_inverted_index.determined | 93 |
| abstract_inverted_index.obstacles, | 18 |
| abstract_inverted_index.optimizing | 147 |
| abstract_inverted_index.real-world | 25, 163 |
| abstract_inverted_index.techniques | 41 |
| abstract_inverted_index.ultra-fast | 36 |
| abstract_inverted_index.efficiency. | 49, 169 |
| abstract_inverted_index.pathfinding | 202 |
| abstract_inverted_index.performance | 52, 190 |
| abstract_inverted_index.significant | 58 |
| abstract_inverted_index.applications | 164 |
| abstract_inverted_index.contribution | 129 |
| abstract_inverted_index.environments | 79 |
| abstract_inverted_index.limitations. | 126 |
| abstract_inverted_index.performance, | 38 |
| abstract_inverted_index.performance. | 150 |
| abstract_inverted_index.utilization. | 110 |
| abstract_inverted_index.Additionally, | 86 |
| abstract_inverted_index.applicability | 76 |
| abstract_inverted_index.applications. | 26 |
| abstract_inverted_index.construction, | 96 |
| abstract_inverted_index.environments. | 205 |
| abstract_inverted_index.outperforming | 39 |
| abstract_inverted_index.distributions, | 157 |
| abstract_inverted_index.memory-runtime | 102 |
| abstract_inverted_index.state-of-the-art | 29 |
| abstract_inverted_index.memory-constrained | 78, 204 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 3 |
| citation_normalized_percentile |