Continuous nearest neighbor queries over sliding windows

This paper studies continuous monitoring of nearest neighbor (NN) queries over sliding window streams. According to this model, data points continuously stream in the system and they are considered valid only while they belong to a sliding window that contains (i) the W most recent arrivals (count-based), or (ii) the arrivals within a fixed interval W covering the most recent timestamps (time-based). The task of the query processor is to constantly maintain the result of long running NN queries among the valid data. We present two processing techniques that apply to both count-based and time-based windows. The first one adapts conceptual partitioning, the best existing method for continuous NN monitoring over update streams, to the sliding window model. The second techniqu