The proliferation and ever-increasing popularity of mobile devices have dramatically increased the potential for mobile crowdsourcing across a wide gamut of applications that are relevant to smart cities. While existing works have mostly focused on mobile crowdsourcing for queries involving a single given major task, the issue of addressing complex queries with multiple related large sub-tasks (with spatio-temporal dependencies) has received little attention. In this regard, the key contributions of the paper are three-fold. First, we present a scheme, designated as BMS (Broker-based processing of Multiple Sub-tasks), in which a broker coordinates the processing of multiple related large subtasks in a given query among a set of mobile peers. Second, we propose the DMS (Distributed processing of Multiple Sub-tasks) scheme in which the processing of multiple sub-tasks in a query occurs in a distributed manner without the existence of any brokers. Third, the results of our performance evaluation demonstrate the effectiveness of both of the proposed schemes in terms of relatively low query response times, high query success rates and reasonable communication costs. © 2010 ACM 1-58113-000-0/00/0010 $15.00.