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 (eg, 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 …