Use cases of ACTree
ACTree provides performance that improves the state of the art when the number of attribute-value pairs in the event is not much smaller than the dimensions of the attribute space. In other words, this algorithm is not suitable for e-commerce style publish-subscribe systems where each event has 10-20 pairs out of a dimensionality of thousands (specific algorithms have been developed to cater to this specific use case, such as BE-Tree, OpIndex or PSTree). However, many applications are not of this type, and for them ACTree is well-suited and likely more performant than other existing algorithms. Consider the following use cases:
- High-Frequency Trading. An organization receives price ticks with additional stock data such as volume, change in price, etc. Traders are subscribed to the system. An implementation of the brokering middleware using ACTree keeps an array of ACTrees (one for each company listed in the stock).
- Online advertising. We can model a page visit as an event, with a limited set of attributes including time, geo-location data, and user data. Subscribers in this case are potential advertisers. The system must decide which advertisement to display, for which it is critical that it knows which advertisements can be shown. This can be trivially implemented using ACTree. Additional logic can then be added to consider which of the advertisers is the most suitable.
- IoT. This is a very common use of publish-subscribe systems, and ACTree would also likely perform better than existing solutions. In this scenario, sensors send data periodically to a server, which must then decide whether or not to notify other connected devices or carry out further logic.
We show that for this type of scenario, where the cardinality of the event attribute space is similar to that of the entire attribute space, the performance of ACTree surpasses that of existing solutions by a large margin both in terms of matching efficiency and memory consumption.