Show simple item record

dc.contributor.authorShi, Qingminen_US
dc.contributor.authorJaJa, Josephen_US
dc.date.accessioned2004-05-31T23:24:58Z
dc.date.available2004-05-31T23:24:58Z
dc.date.created2003-01en_US
dc.date.issued2003-02-05en_US
dc.identifier.urihttp://hdl.handle.net/1903/1254
dc.description.abstractGiven 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-08en_US
dc.format.extent222886 bytes
dc.format.mimetypeapplication/postscript
dc.language.isoen_US
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-4438en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-2003-08en_US
dc.titleA New Framework for Addressing Temporal Range Queries and Some Preliminary Resultsen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record