Characterizing and Exploiting Reference Locality in Data Stream Applications

In this paper, the authors investigate a new approach to process queries in data stream applications. They show that reference locality characteristics of data streams could be exploited in the design of superior and flexible data stream query processing techniques. They identify two different causes of reference locality: popularity over long time scales and temporal correlations over shorter time scales. An elegant mathematical model is shown to precisely quantify the degree of those sources of locality.