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

Research output: Contribution to conferencePaper

12 Downloads (Pure)

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.
Original languageEnglish
Number of pages8
Publication statusPublished - 8 Jul 2018
Event2018 IEEE Congress on Evolutionary Computation - Rio de Janeiro, Brazil
Duration: 8 Jul 201813 Jul 2018
http://www.ecomp.poli.br/~wcci2018/

Conference

Conference2018 IEEE Congress on Evolutionary Computation
CountryBrazil
CityRio de Janeiro
Period8/07/1813/07/18
Internet address

Fingerprint

Data structures
Labels
Storage allocation (computer)
Scalability
Data storage equipment
Computer simulation

Keywords

  • trie-based data structures
  • indexing
  • discrete sets
  • elementary shortest path problem

Cite this

@conference{a6b827bba0884b2b9e190b6a6c80b2aa,
title = "Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints",
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.",
keywords = "trie-based data structures, indexing, discrete sets, elementary shortest path problem",
author = "Polnik, {Mateusz Damian} and Annalisa Riccardi",
year = "2018",
month = "7",
day = "8",
language = "English",
note = "2018 IEEE Congress on Evolutionary Computation ; Conference date: 08-07-2018 Through 13-07-2018",
url = "http://www.ecomp.poli.br/~wcci2018/",

}

Polnik, MD & Riccardi, A 2018, 'Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints' Paper presented at 2018 IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, 8/07/18 - 13/07/18, .

Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints. / Polnik, Mateusz Damian; Riccardi, Annalisa.

2018. Paper presented at 2018 IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil.

Research output: Contribution to conferencePaper

TY - CONF

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

AU - Polnik, Mateusz Damian

AU - Riccardi, Annalisa

PY - 2018/7/8

Y1 - 2018/7/8

N2 - 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.

AB - 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.

KW - trie-based data structures

KW - indexing

KW - discrete sets

KW - elementary shortest path problem

M3 - Paper

ER -

Polnik MD, Riccardi A. Indexing discrete sets in a label setting algorithm for solving the elementary shortest path problem with resource constraints. 2018. Paper presented at 2018 IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil.