dc.contributor.author | Shi, Qingmin | en_US |
dc.contributor.author | JaJa, Joseph | en_US |
dc.date.accessioned | 2004-05-31T23:24:58Z | |
dc.date.available | 2004-05-31T23:24:58Z | |
dc.date.created | 2003-01 | en_US |
dc.date.issued | 2003-02-05 | en_US |
dc.identifier.uri | http://hdl.handle.net/1903/1254 | |
dc.description.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
$O( \log n\log m/\log\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 results include a linear size data structure that enables a query time of
$O( \log n\log m/\log\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.
Also UMIACS-TR-2003-08 | en_US |
dc.format.extent | 222886 bytes | |
dc.format.mimetype | application/postscript | |
dc.language.iso | en_US | |
dc.relation.ispartofseries | UM Computer Science Department; CS-TR-4438 | en_US |
dc.relation.ispartofseries | UMIACS; UMIACS-TR-2003-08 | en_US |
dc.title | A New Framework for Addressing Temporal Range Queries and Some Preliminary Results | en_US |
dc.type | Technical Report | en_US |
dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |