کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657921 | 690117 | 2005 | 13 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A new framework for addressing temporal range queries and some preliminary results
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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(lognlogm+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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 109-121
Journal: Theoretical Computer Science - Volume 332, Issues 1â3, 28 February 2005, Pages 109-121
نویسندگان
Qingmin Shi, Joseph JaJa,