[joshd]

Are you logging your queries? If you have enough searches you could build your own predictions. You're also proxying results, so you could use those to build an index too.

[jsatok]

I am logging queries. Do you have any tips/suggestions as to how to do my own predictions?

[yesbabyyes]

For each prefix, which app are people eventually satisified with?

E.g. if "in" often leads to instapaper, predict that, while if "ins" often eventually leads to "instantapp", that's the prediction for that prefix.