Time Windowed Data Structures

We studytime windowed data structures, where atimestampedinput sequence can be preprocessed into a data structure based on a given predicateP, so that for a query time interval specified at the query time, it can answer queries based on the inputs whose timestamps lie in the query interval and matchP. We refer to these queries aswindow queries. In this thesis, we consider several variations of these window queries for three types of inputs; they are relational event (RE) graphs, geometric objects (e.g., points, line segments, polygons) and set elements. We study three types of query problems, namelywindow decision problems,window reporting problemsandwindow counting problems.Considering an RE graph G=(|V|=n, |E|=m) as the input, where each edge inEhas a unique positive timestamp, we present data structures to answer the following window problems; (a) decision problems for monotone graph properties, such as disconnectedness and bipartiteness, (b) reporting problems for the minimum spanning tree, the minimum spanning interval, and the graph edit distance for spanning forests, and (c) subgraph counting problems to count the total number of subgraphs that match a given pattern, such as paths of length 2 and 3 (in bipartite graphs), quadrangles and complete subgraphs of some fixed order ℓ ≥ 3. We further present a general approach for analyzing various structural parameters of an RE graph slice, such as thedensity, the number ofk-stars, the approximation ofh-index, theembeddedness, theneighborhood overlapand the number ofinfluenced vertices, using the colored range searching data structures.We also study data structures that can answer window queries for a sequence of geometric objects, such as points, line segments and convexc-gons. We study thewindowed intersection decision problemsfor these objects. For a sequence of points inIRd, d ≥ 2, we solve some variations of the maximal layer problem, such as counting total number of points on the maximal layer,k-dominated andk-dominant points for some fixed integerk, and deciding if a given point belongs to a maximal layer Ly, where y = 1, 2 or y ≥ 3.