Efficient Temporal Counting with Bounded Error

Yufei Tao, Xiaokui Xiao

To appear in Very Large Data Base Journal (VLDBJ)

  
  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 q_k, a count-query retrieves the number of objects that are alive at q_t, and their keys fall in q_k. We provide a method that accurately answers such queries, with error less than 1/ε + ε×N_alive(q_t), 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_Bn) time, and supports each update in O(log_Bn) 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.