Efficient temporal counting with bounded error
Publication in refereed journal


摘要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) over right arrow (k), a count-query retrieves the number of objects that are alive at qt, and their keys fall in (q) over right arrow (k). We provide a method that accurately answers such queries, with error less than 1/epsilon + epsilon . N(alive)(q(t)), where Nalive(qt) is the number of objects alive at time qt, and e 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.
著者Tao YF, Xiao XK
期刊名稱VLDB Journal
出版社Springer Verlag (Germany)
頁次1271 - 1292
關鍵詞aggregate search; approximate query processing; temporal database
Web of Science 學科類別Computer Science; Computer Science, Hardware & Architecture; COMPUTER SCIENCE, HARDWARE & ARCHITECTURE; Computer Science, Information Systems; COMPUTER SCIENCE, INFORMATION SYSTEMS

上次更新時間 2021-27-02 於 23:34