Determine which users a user follows on new status event



I am developing a real-time analytics application for monitoring multiple users.

I have a single user stream following multiple users using with “followings” in order to capture events from any of their followers. When I get a new status event I would like to be able to determine which user (in my user stream) the user who just posted the new status is following.

For example:
The user stream is listening for events from user A and B or any of their followers.
If user C sends a new status I will see that on the user stream.
How am I supposed to know which user (A or B or both) user C is following?

I figured that using the REST APIs friendships/show resource may work the best for this issue. But that would require making calls requesting the relationship between the user in question and every user in my user stream. With the amount of users and tweets that I will be monitoring, I will quickly go over the given rate limit.

Any suggestions on how to better accomplish this?