Picture of boy being examining by doctor at a tuberculosis sanatorium

Understanding our future through Open Access research about our past...

Strathprints makes available scholarly Open Access content by researchers in the Centre for the Social History of Health & Healthcare (CSHHH), based within the School of Humanities, and considered Scotland's leading centre for the history of health and medicine.

Research at CSHHH explores the modern world since 1800 in locations as diverse as the UK, Asia, Africa, North America, and Europe. Areas of specialism include contraception and sexuality; family health and medical services; occupational health and medicine; disability; the history of psychiatry; conflict and warfare; and, drugs, pharmaceuticals and intoxicants.

Explore the Open Access research of the Centre for the Social History of Health and Healthcare. Or explore all of Strathclyde's Open Access research...

Image: Heart of England NHS Foundation Trust. Wellcome Collection - CC-BY.

Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints

Polnik, Mateusz Damian and Riccardi, Annalisa (2018) Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints. In: 2018 IEEE Congress on Evolutionary Computation, 2018-07-08 - 2018-07-13.

[img]
Preview
Text (Polnik-Riccardi-IEEE-CEC-2018-Indexing-discrete-sets-in-a-label-setting-algorithm-for-solving-the-elementary-shortest-path-problem)
Polnik_Riccardi_IEEE_CEC_2018_Indexing_discrete_sets_in_a_label_setting_algorithm_for_solving_the_elementary_shortest_path_problem.pdf
Accepted Author Manuscript

Download (1MB) | Preview

Abstract

Stopping exploration of the search space regions that can be proven to contain only inferior solutions is an important acceleration technique in optimization algorithms. This study is focused on the utility of trie-based data structures for indexing discrete sets that allow to detect such a state faster. An empirical evaluation is performed in the context of index operations executed by a label setting algorithm for solving the Elementary Shortest Path Problem with Resource Constraints. Numerical simulations are run to compare a trie with a HATtrie, a variant of a trie, which is considered as the fastest inmemory data structure for storing text in sorted order, further optimized for efficient use of cache in modern processors. Results indicate that a HAT-trie is better suited for indexing sparse multi dimensional data, such as sets with high cardinality, offering superior performance at a lower memory footprint. Therefore, HAT-tries remain practical when tries reach their scalability limits due to an expensive memory allocation pattern. Authors leave a final note on comparing and reporting credible time benchmarks for the Elementary Shortest Path Problem with Resource Constraints.