SPO-Join: Efficient Stream Inequality Join.

Stream inequality join aims to combine tuples coming from differ- ent streams based on inequality conditions and is a fundamental operator in distributed data stream processing. It is known to be computationally expensive as indexing data structures for determining matching tuples must be continuously updated. To significantly alleviate this problem, we propose SPO-Join, a novel solution that combines a mutable B+-tree for efficient insertions and an immutable sorted-array-based data structure for efficient searching. Furthermore, our proposed method is designed to be efficiently executed with distributed stream pro- cessing engines. Our experiments on real-world and synthesized datasets suggest that the proposed SPO-Join exhibits superior performance compared to state-of-the-art index-based stream inequality join solutions.