Realising the “smart city” vision requires applications that can efficiently disseminate context among millions of potentially mobile nodes. Numerous context dissemination algorithms exist based on flooding-, gossip- and overlay-based approaches. However, due to their message transmission (flooding, gossip) or control (overlay) overhead, they cannot support the amount of mobile nodes envisaged in urban-scale scenarios. This paper describes Adaptive Context Tries (ACT), a decentralised context dissemination middleware that balances message transmission and control overhead to support urban-scale context-aware applications. ACT achieves scalability using a dynamically constructed virtual overlay, structured as a retrieval tree (trie) on node identifiers (IDs), avoiding continuous overlay rebuilds due to mobility or nodes changes by removing the need for subscriptions. Through formal analysis and extensive large-scale simulations we show that unlike existing context dissemination algorithms ACT can handle dynamic context requirements in urban-scale scenarios.