Israeli Queues

Source: https://arpitbhayani.me/blogs/israeli-queues Date: 2020-11-22

Explore Israeli Queues, a unique priority queue variation where elements join friends already waiting! Learn how they optimize batch processing.

A queue is a data structure that holds up elements for a brief period of time until a peripheral processing system is ready to process them. The most common implementation of a queue is a FIFO queue - First In First Out - that evicts the element that was inserted the first i.e. it evicts the one that has spent the most time in the queue. There are other variations of Queues one of which is called Priority Queue.

In Priority Queue, every element is associated with a priority, usually provided by the user during enqueueing; This associated priority is used during eviction where the element with the highest priority is evicted first during dequeuing.

In this essay, we take a detailed look into a variation of Priority Queue, fondly called Israeli Queues, where the priority of the element is defined by the affinity of it with one of its “friends” in the queue. Israeli Queues were first introduced in the paper by Boxma, O. J., Wal, van der, J., & Yechiali, U in the year 2007.