Several important algebras in representation theory, like Iwahori-Hecke algebras of Weyl groups and Affine Hecke Algebras, can be realized as convolution algebras on flag varieties. Some of these constructions can be carried over to the 'mirabolic' setting to obtain other interesting algebras. We will discuss the convolution algebra of GL(V)-invariant functions on triples of two flags and a vector, which was first described by Solomon, and its connections to the cyclotomic Hecke algebras of Ariki and Koike.