Skip to content

Latest commit

 

History

History
63 lines (51 loc) · 4.57 KB

queryheap_in_osrm.md

File metadata and controls

63 lines (51 loc) · 4.57 KB
Raw

QueryHeap In OSRM

QueryHeap In OSRM

Action Interfaces QueryHeap In OSRM
Insert Insert()
Find WasInserted()
Pop DeleteMin()

The Insert() operation can tell us how it works deeply:

    void Insert(NodeID node, Weight weight, const Data &data)
    {
        BOOST_ASSERT(node < std::numeric_limits<NodeID>::max());
        const auto index = static_cast<Key>(inserted_nodes.size());
        const auto handle = heap.push(std::make_pair(weight, index));
        inserted_nodes.emplace_back(HeapNode{handle, node, weight, data});
        node_index[node] = index;
    }

std::priority_queue vs. boost::heap::d_ary_heap

Dijkstra based algorithms require a Priority Queue structure to iterate by ascending ordered weight(i.e. cost). Most of implementations will use the standard one: std::priority_queue, but OSRM use boost::heap::d_ary_heap(4-ary) instead.

  • std::priority_queue
    std::priority_queue implemented based on std::make_heap, std::push_heap and std::pop_heap for Heap properties. It's actually a binary heap in STL implemtation.
    Since our Bidirectional A-Star Algorithm in routingcore will only need insert and pop_min operations, the most important for us is the algorithm complexity of std::push_heap and std::pop_heap.

    • std::push_heap: O(log(N))
    • std::pop_heap : O(log(N))

  • boost::heap::d_ary_heap
    boost::heap::d_ary_heap is a implementation of d-ary heap.

    • Below refers to wikipedia of d-ary heap:
      The d-ary heap or d-heap is a priority queue data structure, a generalization of the binary heap in which the nodes have d children instead of 2. Thus, a binary heap is a 2-heap, and a ternary heap is a 3-heap.
      This data structure allows decrease priority operations to be performed more quickly than binary heaps, at the expense of slower delete minimum operations. 4-heaps may perform better than binary heaps in practice, even for delete-min operations.
    • algorithm complexity of insert and pop_min operations of boost::heap::d_ary_heap:
      • push: O(log(N)/log(d))
      • pop: O(log(N)/log(d))

As above, 4-ary heap of QueryHeap is very similar with binary heap of std::priority_queue, the only difference between them is 4-ary vs 2-ary. Both push and pop of them have logarithmic algorithm complexity.
why 4-ary heap performs better than 2-ary heap for decrease() and extract-min()

TODO

  • there's another choice Fibonacci Heap may lead to better performance for Dijkstra, worthing to have a try. Time complexity is O(M + Nlog(N)(with N =|V| and M = |A|)
  • If arc lengths are integers bounded by C, multilevel buckets could achieve O(M + nlogC/loglogC)

References