On Indexing Sliding Windows over Online Data Streams Lukasz Golab, Shaveen Garg, and M. Tamer Özsu   View Paper (PDF)   Return to Session 13: Indexing Techniques Abstract We consider indexing sliding windows in main memory over on-line data streams. Our proposed data structures and query semantics are based on a division of the sliding window into sub-windows. By classifying windowed operators according to their method of execution, we motivate the need for two types of windowed indices: those which provide a list of attribute values and their counts for answering set-valued queries, and those which provide direct access to tuples for answering attribute-valued queries. We propose and evaluate indices for both of these cases and show that our techniques are more efficient than executing windowed queries without an index. This research is partially supported by the Natural Sciences and Engineering Research Council of Canada (NSERC). ©2005 Association for Computing Machinery