External memory priority queue

---

In computer science, an external memory priority queue is a priority queue stored completely or partially in external memory.

External memory priority queues are often used in combination with computing problems using large amounts of data when the use of internal priority queues would lead to paging. The random accesses of an ordinary priority queue are sufficient for memory accesses on fast internal storage but would cause a slowdown when accessing storage mediums on lower levels of the memory hierarchy.. External memory priority queues aim to optimize the use of multiple storage mediums on multiple levels of the memory hierarchy.

Route planning algorithms usually use a weighted graph as the problem instance. Shortest path queries are then used to find the optimal route between point A and B. These are often implemented as priority queues with the length of the path being the key and the deleteMin operation returning the shortest path in the queue. However, problem instances can be too large to fit into the internal memory and data needs to be transferred between the slow external memory and fast internal memory. Similarly, line sweep algorithms need to prioritize the line segments by their starting points and can use priority queues to do so (i.e. Bentley-Ottmann algorithm). The different line segments are inserted into the priority queue with the starting point as the key. Finding the lowest starting point of a segment can therefore be implemented using the deleteMin operation.

An efficient handling of batched updates is necessary to minimize the I/Os needed per update and is often realized using dynamic data structures like Sequence Heaps or Buffer Trees. External memory priority queue implementations are found in libraries for large data sets

Sequence Heaps

Elements recently inserted into the sequence heap proposed by Sanders are stored in an insert heap of size $m$. The insert heap works as a buffer such that most of the insert calls can be served from internal memory. When the insert heap is full, elements are transferred to the first group of sorted sequences. All sequences in a group are merged in a K-way merge algorithm. Because the sequences in the first group are of size $m$, this first merge group is able to store $mk$ elements. The result of the merge is a buffer of size $m$. To account for more elements in the priority queue than the first group of sorted sequences is able to handle, new k-way-merges and sorted sequences are introduced. For the Xth k-way-merge, the size of the sorted sequences is at most $m{k}^x$ but the resulting buffer is always of size $m$. These buffers represent a group of sorted sequences of the same size. They contain the smallest elements of the group. All these group buffers are merged in another R-way-merge, representing $R$ groups, resulting in a deletion buffer of size $m^{\prime }$. The deletion buffer is necessary for providing a fast deleteMin operation and avoiding the otherwise necessary external memory accesses with every call.

The elements that need to be accessed next are stored in internal memory while other elements are stored externally. This applies for a multitude of storage hierarchy models, be it the cache and random-access memory (RAM) or RAM and the disk storage. To optimize the performance of the sequence heaps presented in this example, $m$ has to be chosen according to the block size of the external storage. When $m$ is smaller than the block size, unused data is fetched from the disk. Therefore $m=xB$, depending on the size of the internal storage. Generally only the deletion buffer and the insert heap are stored in internal memory. The group buffers are swapped in and out when needed and the sorted sequences are stored exclusively in external memory.

DeleteMin

When deleting an element, the smallest elements of the deletion buffer and in the insert heap need to be compared. The resulting element is the smallest in the whole data structure and is then deleted. In case this empties the deletion buffer, all group buffers with less than $m^{\prime }$ elements need to be refilled from the corresponding sorted sequences using a k-way-merge first. Then the deletion buffer needs to be refilled from the group buffers using the R-way-merge. Because the elements in the sorted sequences are not smaller than the elements in the corresponding group buffers and the group buffers only contain elements that are not smaller than the ones in the deletion buffer, the heap property is fulfilled and the smallest element of the data structure is always found in the deletion buffer or the insertion heap.

Insert

Inserted elements are first put into the insertion heap. When this heap is full, it is merged with the deletion buffer and the group buffer of the first group and sorted. The smallest elements of this merge are placed in the deletion buffer and in the first group buffer. The rest is added to the first group as another sequence of size $m$. But now there might be more than $k$ sequences in the first group. In this case, all old sequences in the group are merged into one large sequence of size $km$ and moved to the second group. To not violate the heap priority, the group buffer of the second group is merged with the buffer of the first group and inserted into the first group as a new sequence. The group buffers are then refilled with the k-way-merge. This is also done recursively to free up space in higher level groups as more and more elements are inserted. When there are multiple groups that have been emptied due to an insert, the group buffers of all the modified groups need to be merged and put into the first group as a new sequence.

All I/Os needed for inserting one element, propagating it through the groups and deleting it are done in batched operations which splits up the cost between all elements in a block. The element is first inserted into the insert heap and then written to a sequence in the first group for a cost of $\frac{1}{B}$ writes. It is then transferred from one group to the next and needs to be read and wrote in every step. For $R$ groups this sums up to $\frac{2(R-1)}{B}$ I/Os. Lastly $\frac{1}{B}$ I/Os are needed to read the element into the group buffer. Each insertion leads to $\frac{2R}{B}$ I/Os in total.

Example

Animation of an insert into the sequence heap data structure

• Insert Heap contains (5, 13) and is now full.
• It is merged with the deletion buffer, the group buffer 1 and sorted resulting in (2, 5, 6, 10, 13). (2) is placed in the deletion buffer, (5, 6) in the group buffer. (10, 13) are placed into the first K-Way-Merge and it overflows.
• The old elements are merged resulting in 11,14,16,18. The new sorted sequence is added to K-Way-Merge 2.
• Group Buffers 1 and 2 are invalidated and merged into a new sequence (5, 5, 6, 15) in K-Way-Merge 1. (5, 5) is written into Group Buffer 1.
• Group Buffer 2 is now refilled from the sorted sequences of K-Way-Merge 2.

Buffer Trees

The buffer tree data structure developed by Arge aims to transform an internal memory tree data structure into an external version. Each node contains a buffer that is stored in external memory. The data structure is implemented as a (a,b)-tree with $a=\frac{m}{4}$ and $b=m$ (nodes have between $\frac{m}{4}$ and m children). Each parent also stores $k-1$ pivot elements. The leaf nodes also contain buffers but additionally have leaf blocks as children. Changes in the internal buffers are recorded with insert / delete flags. Before a buffer is processed all insert / delete pairs are removed.

Insert

Newly inserted elements are first placed into the internal insert buffer and marked as inserted. When the insert buffer contains $B$ elements, insert / delete pairs are removed and it is inserted into the buffer of the root element. In case this fills the buffer to at least $\frac{m}{2}$ blocks, it is emptied. Insert / delete pairs are removed and all leftover elements are partitioned according to the pivots elements and pushed down to the appropriate child node buffers. Children with more than $m$ blocks are also emptied recursively. To empty the leaf buffers, they are first sorted and merged with the leaf blocks. They are then rebalanced by splitting the nodes bottom-up recursively

DeleteMin

The minimum element is contained in any of the leftmost nodes. Therefore all buffers on the path from the root to the leftmost leaf have to be emptied similar to the insert process. Afterwards at least the $\frac{m}{4B}$ smallest elements in the tree are in the leaves of the leftmost parent. These can now be cached to serve the next $\frac{m}{4B}$ deleteMin operations from internal memory.

For the deleteMin operation $mlo{g}_m(n)$ I/Os are needed. This leads to an amortized cost of $\frac{mlo{g}_m(n)}{1/4mB}$ I/Os per element.

References

This article "External memory priority queue" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:External memory priority queue. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---