Accession Number:

AD1006922

Title:

A New Framework for Addressing Temporal Range Queries and Some Preliminary Results

Descriptive Note:

Technical Report

Corporate Author:

University of Maryland College Park United States

Personal Author(s):

Report Date:

2003-01-29

Pagination or Media Count:

14.0

Abstract:

Given a set of n objects, each characterized by d attributes specified at m fixed time instances, we are interested in the problem of designing space efficient indexing structures such that arbitrary temporal range search queries can be handled efficiently. When m 1, our problem reduces to the d-dimensional orthogonal search problem. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of Olog n log mlog log n f for one-sided queries when d 1, where f is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can be solved with a polylogarithmic query time using nonlinear space data structures.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE