Time Windowed Data Structures

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.

Creator: 

Chanchary, Farah Habib

Date: 

2019

Abstract: 

We study time windowed data structures, where a timestamped input sequence can be preprocessed into a data structure based on a given predicate P, 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 match P. We refer to these queries as window 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, namely window decision problems, window reporting problems and window counting problems.

Considering an RE graph G=(|V|=n, |E|=m) as the input, where each edge in E has 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 the density, the number of k-stars, the approximation of h-index, the embeddedness, the neighborhood overlap and the number of influenced 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 convex c-gons. We study the windowed intersection decision problems for these objects. For a sequence of points in IRd, d ≥ 2, we solve some variations of the maximal layer problem, such as counting total number of points on the maximal layer, k-dominated and k-dominant points for some fixed integer k, and deciding if a given point belongs to a maximal layer Ly, where y = 1, 2 or y ≥ 3.

Subject: 

Computer Science

Language: 

English

Publisher: 

Carleton University

Thesis Degree Name: 

Doctor of Philosophy: 
Ph.D.

Thesis Degree Level: 

Doctoral

Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).