Efficient temporal counting with bounded error |
| |
Authors: | Yufei Tao Xiaokui Xiao |
| |
Affiliation: | (1) Department of Computer Science and Engineering, Chinese University of Hong Kong, New Territories, Hong Kong |
| |
Abstract: | This paper studies aggregate search in transaction time databases. Specifically, each object in such a database can be modeled
as a horizontal segment, whose y-projection is its search key, and its x-projection represents the period when the key was valid in history. Given a query timestamp q
t
and a key range , a count-query retrieves the number of objects that are alive at q
t
, and their keys fall in . We provide a method that accurately answers such queries, with error less than , where N
alive(q
t
) is the number of objects alive at time q
t
, and ɛ is any constant in (0, 1]. Denoting the disk page size as B, and n = N / B, our technique requires O(n) space, processes any query in O(log
B
n) time, and supports each update in O(log
B
n) amortized I/Os. As demonstrated by extensive experiments, the proposed solutions guarantee query results with extremely
high precision (median relative error below 5%), while consuming only a fraction of the space occupied by the existing approaches
that promise precise results. |
| |
Keywords: | Temporal database Aggregate search Approximate query processing |
本文献已被 SpringerLink 等数据库收录! |
|