#priority-queue #element #data-structures #discrete #optimization #pareto #sets

do_util

Discrete Optimization utilitary library (data-structures)

1 unstable release

0.1.0 Feb 7, 2022

#2164 in Algorithms

MIT license

54KB
1K SLoC

Discrete Optimization utility

Implements various useful data-structures for discrete optimization. This crate is in active development, Pull requests welcome :).

Set data-structures

Various data-structures to maintain efficiently sets

  • Sparse-set: Maintains sets of positive integers. Allows for O(1) insertion, deletion, counts, delete all but one element. This data-structure is expensive to create, but the operations are very fast. See this article for more information.

Benchmarks

Sub-set/Super-set queries

Allows performing quick sub-set or super-set queries.

  • List Simple naive list storage. Iterates over the whole list to find sub-sets/super-sets
  • Set-trie See this article for more information. It is fast for sub-set queries, slower for super-set queries. Is efficient if the number of elements in sets is small.
  • HAT-trie See this article for more information.

Benchmarks

Pareto priority-queues

Data-structures for quick insertion/removal/find-minimum/dominance-checks on an n-dimensional pareto front. Each element also provides a "guide" value that is used for minimum (resp. maximum) extraction.

Heavily inspired from the excellent pareto library for Python and C++ [1]. Each Pareto front stores elements such that no element dominates another. The main difference is that the data-structures in this crate allow to find the minimum element quickly. Moreover, using this crate, it is possible to define more general dominance rules in addition of the dimension dominance.

  • List Pareto front: Simple data-structure that simply stores the elements using a vector. This data-structure is straightforward, and usually works fine for small
  • Kd-tree: Data-structure in which each node contains an element and divides the space into 2 parts. This data-structure is efficient for many points.
  • Point-region-tree: Data-structure in which each node divides the space into 2**d subregions. This data-structure is efficient for many points, but requires an initial lower/upper bound on the dimensions.
  • R-tree: Data-structure in which elements are stored in bounding boxes. Bounding boxes may intersect.
  • R*-tree:

Benchmarks

Random n-dimensional points.

References

Alan Freitas, Efficient user-oriented Pareto fronts and Pareto archives based on spatial data structures, Swarm and Evolutionary Computation, Volume 65, 2021, 100915, ISSN 2210-6502, https://doi.org/10.1016/j.swevo.2021.100915. (https://www.sciencedirect.com/science/article/pii/S2210650221000766)

No runtime deps