Emergent optimization for open-world queries in stream grids

Abstract

Stream grids are wide-area grid computing environments that are fed by a set of newlinestream data sources. The two main contributors to stream data generation are (1) the large scale deployment of sensor networks for a wide range of applications newlinefrom monitoring geophysical activities to supply chain management, and (2) internet newlineapplications like financial tickers, transaction logs and network monitoring. newlineQueries arrive at the grid from users and applications external to the system, and newlineseek to tap into one or more data streams. In the literature, queries on stream data are usually classified into two distinct types; a lifetime query which is never revoked and a one-shot query which is transient in nature. The kind of queries considered in this work is of a third type called long-running continuous (LRC) queries, that we also term as open-world queries. These queries are neither short-lived nor infinitely long-lived. They live long enough to make the prospect of multi-query optimization meaningful. But queries may also terminate at any time, requiring re-optimization of the query plans. The queries are open from newlinethe grid perspective as the grid cannot control or predict: (1) arrival of a query newlinewith time, location, required data, and (2) query revocation. Query optimization newlinein such an environment has two major challenges: (a) optimizing in a multi-query newlineenvironment and (b) continuous optimization due to new query arrivals and revocations. Generating a globally optimal query plan is shown to be an intractable problem. newlineThis is compounded by the fact that the query plan would need to be recomputed newlinefrequently, with every new query arrival and existing query revocation. newlineHence, this work explores the idea of emergent optimization, where globally optimal newlinequery plans emerge as a result of local autonomous decisions taken by the grid newlinenodes.