Skip to content
All library documents

Efficient Limit Order Queue Position Tracking with Prefix Sums

Article Quant Q&A · Author: Craig
Read the original

Summary

The document compares ways to track an order's rank and the volume ahead of or behind it in a limit order book queue. Storing order sizes makes updates constant-time but requires a linear scan to answer position queries. Storing prefix sums reverses that tradeoff: queries are constant-time, while updates may require changing many sums. A Fenwick tree supports both operations in logarithmic time.

The response favors prefix sums in some practical settings when queue-position queries are more time-sensitive than updates. It also notes that cancellations and executions may often involve orders near the back, reducing the work of updates in typical cases, and that queues may be short enough for a scan to be inexpensive. These are implementation considerations rather than universal performance guarantees; the best choice depends on queue length, operation mix, and application timing needs.

Key ideas

  • Storing order sizes gives constant-time updates but requires a linear scan for queue-position queries.
  • Prefix sums make position queries constant-time but can make updates linear in the queue length.
  • A Fenwick tree supports both querying and updating in logarithmic time.
  • Prefix sums may be practical when queries are more urgent than updates and queues are short.

Tags

Market microstructureExecutionHigh-frequency trading
Full text
# Efficiently Tracking Order Queue Position In a Limit Order Book Implementation


# Efficiently Tracking Order Queue Position In a Limit Order Book Implementation












There are a lot of posts on different ways to implement limit order books, though I never see any discussion on tracking a specific orders queue position efficiently. If I want to ask questions like:

- What position is order x at in queue y?

- How much volume is in front of and behind order x in queue y?

The only way I can think of doing this is to update each order in the queue with tracking values every time a add/modify/cancel occurs. But this would involve iterating the whole queue each time. Is there a better way?

## Answer by databento (score 1, accepted)

https://quant.stackexchange.com/a/80118

This is a classic prefix sum problem. You can:

- Store the order sizes. Get the position in O(n) and update in O(1).

- Store the prefix sums. Get the position in O(1) and update in O(n).

- Use a Fenwick tree. Do both in O(log n).

Often, the practical considerations favor approach (2). Why?

- Usually getting the position is more urgent to the application logic than making the update. You can defer update to after you compute signals, make strategy decision, or send order messages.

- Orders usually get pulled from towards the back of the queue and cancels usually dominate executions, so the average update is much cheaper than the worst case.

- The queue is usually short enough that there are not many orders to walk.

Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)

This summary was written by Stratmill's research agent from the original; it is not a copy of the source.