Reconstructing an Order Book from Order Additions and Deletions
Summary
This document addresses the slow computation of order book statistics at each new order’s creation time. Repeatedly filtering the full order table for orders that were already created and had not yet completed is simple but inefficient. The proposed alternative is to process order flow in timestamp order and maintain the current book as orders are added and removed.
The outline groups additions and deletions by timestamp, carries the prior book forward, removes orders whose completion times fall in the interval, and inserts newly created orders. This supports calculating statistics from the active book without rebuilding it from the entire dataset for every row. The method is described as pseudocode rather than a complete implementation. It returns book states at creation timestamps; to capture states at intervening deletion times, the algorithm must also create intermediate snapshots. The answer further cautions that creation and completion times may already represent processed data, so reconstructing from earlier raw order events may be preferable.
Key ideas
- Repeatedly filtering all orders for every timestamp can be computationally expensive.
- An event-driven approach maintains the active book as orders arrive and complete.
- Group additions and deletions by timestamp to update book state incrementally.
- The outline captures creation-time snapshots and needs extensions for intervening completion times.
- Reliable reconstruction depends on understanding how the input order data was produced.
Tags
Full text
# Backtest: Fast Reconstruction of Order Book using Order Creation/Completion Data in Python
# Backtest: Fast Reconstruction of Order Book using Order Creation/Completion Data in Python
I am looking for a quick way to reconstruct the order book at the time of each new limit order creation.
The data I have is order creation and completion:
| OrderID | time_created | time_completed | price |
| a | 1 | 2 | 10 |
| b | 1 | 6 | 11 |
| c | 3 | 8 | 9 |
| d | 4 | 5 | 8 |
| e | 9 | 10 | 7 |
(Volume can be ignored here.) I would like to quickly find out the existing orders in the order book upon each new order's creation, and calculate distribution parameters based on them.
For example, for OrderID d, I would first find out that only orders b and c are still on the order book, because at time of order d's creation (t=4), a has been filled, b and c have been created but not filled, and e has not yet been created.
From there I would calculate distribution parameters, such as mean, median, percentiles etc. In the case of order d, the mean price of outstanding orders would be (11 + 9) / 2 = 10.
The most straightforward way that I can think of is to create a function that filters for the data of the unfilled orders, then extracts the distribution parameters. This function would then be iteratively applied to each row in the dataframe. For example:
```
def get_params(ser):
unfilled_orders = df[(df['time_created'] < ser['time_created']) & (df['time_completed'] > ser['time_created'])]
mean = unfilled_orders['price'].mean()
25perc = unfilled_orders['price'].quantile(0.25)
return pd.Series([mean, 25perc])
df.apply(get_params, axis=1)
```
However, the problem of this implementation is that it is too slow. Each row's result is highly related to the previous row's results, but this implementation does not make use of it. I am thinking if there is a faster solution, perhaps a solution based on a rolling (if we consider orders too old irrelevant) or expanding window? Thanks.
## Answer by lehalle (score 1)
https://quant.stackexchange.com/a/69119
In my opinion the best way to do it is to rebuild the orderbook from order flow.
But first of all it seems very strange that you start with this data frame, usually you do not know the deletion date at creation time. This means that the data have already been process, so if you really want to be fast you should go back to this previous step and rebuild the orderbook at this earlier stage.
The structure I will adopt is the following dictionary
```
{date1:
{'add': {order_id1: price, .... },
'del': {order_id1: price, .... }},
date2: ...
}
```
The pseudo code to fill this structure would be (and I shared an implementation in Colab)
```
for row in dataframe:
1. if it is a new 'creation_time': copy the "previous" dictionary
except for the orders that are in the del
2. insert this order_id in the 'add' section of its creation_time
(except if it is in the 'del' section
[would mean that you have orders that are
created and completed at the same timestamp]
)
3. insert this order_id in the 'del' section of its completion_time
```
It would be something like
```
for row in data_frame:
current_timestamp = row.creation_time
if current_timestamp > previous_timestamp:
# it is a new timestamp:
# 1. store the orderbook
full_oderbook[previous_timestamp] = current_orderbook
# 2. delete orders if needed
to_be_deleted = get_for_deletion(full_oderbook, previous_timestamp , current_timestamp)
for order_id in to_be_deleted:
current_orderbook.add.pop(order_id)
# 3. update orderbook
current_oderbook.add.update({row.order_id: row.price})
full_oderbook[row.completion_time].del.update({row.order_id: row.price})
# 4. keep track
previous_timestamp = current_timestamp
```
the `get_for_deletion` function selects the deletion between previous timestamp and current timestamp, its pseudo-code is there:
```
def get_for_deletion(full_orderbook, prev_timestamp , curr_timestamp):
return union(ob.del for ob.key between prev_timestamp and curr_timestamp)
```
The only drawback of this algorithm is that it only provide information date creation timestamps. You should check if they are deletion dates in between and create intermediate orderbooks (I let you do that by your own).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.