Thanks for the video presentation.
The idea with the k^2 trees nicely translates this relational problem to a geometric problem.
An intuitive approach for representing ST and OT would be to just write the first and the third component of the triples
in two separate wavelet trees. With these wavelet trees, you can answer the same queries like (s, p, ?).
Thinking geometrically, wavelet trees and k^2 trees share the idea to divide the space geometrically (alphabet size times number of tuples).
So my question would be whether such a representation would be interesting to study.