Backtest: Fast Reconstruction of Order Book using Order Creation/Completion Data in Python

Question

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 1

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).