Companion vehicle discovery is a newly emerging intelligent transportation application. Aiming at it, this paper redefines the Platoon companion pattern over a special type of spatio-temporal data stream, or ANPR (automatic number plate recognition data). Accordingly, a PlatoonFinder algorithm is also proposed to mine Platoon companions over ANPR data stream instantly. First, Platoon discovery problem is transformed into frequent sequence mining problem with customized spatio-temporal constraints. Compared to traditional frequent sequence mining algorithms, this new algorithm can effectively handle complex spatio-temporal relationships among sequence elements rather than their positions. Second, the new algorithm also integrates several optimization techniques such as pseudo projection to greatly improve the efficiency. It can efficiently deal with high speed and large scale ANPR data stream so as to instantly discover Platoon companions. Experiments show that the latency of the algorithm is significantly lower than classic frequent pattern mining algorithms including Apriori and Prefixspan. Furthermore, it is also lower than the minimum time interval between any two real ANPR data records. Hence, the proposed algorithm can discover Platoon companions effectively and efficiently.