@article {14932,
	title = {A new framework for addressing temporal range queries and some preliminary results},
	journal = {Theoretical Computer Science},
	volume = {332},
	year = {2005},
	month = {2005/02/28/},
	pages = {109 - 121},
	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 a class of 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 + 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 superlinear space data structures.},
	keywords = {algorithms, Data structures, Orthogonal range search, temporal data},
	isbn = {0304-3975},
	doi = {10.1016/j.tcs.2004.10.013},
	url = {http://www.sciencedirect.com/science/article/pii/S0304397504007005},
	author = {Shi,Qingmin and JaJa, Joseph F.}
}
