Have you looked at graph databases and how would you compare them to your with Citrusleaf document store?
A similar-sized ad network, CPX Interactive is running ad requests on InfiniGraph: http://www.youtube.com/watch?v=88HCKQ73nFU&feature=relat...
Seems like graphing engine would give you a lot of native search / lookup functionality for free.