HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/2509
Title: Approximate temporal aggregation
Authors: Tao, Yufei
Papadias, Dimitris
Faloutsos, Christos
Keywords: Temporal aggregate queries
Time-evolving attribute
Approximation technique
Bounded error
Multiversion B-trees
Logarithmic worst-case query cost
Issue Date: Apr-2004
Citation: 20th International Conference on Data Engineering, p. 190-201
Abstract: Temporal aggregate queries retrieve summarized information about records with time-evolving attributes. Existing approaches have at least one of the following shortcomings: (i) they incur large space requirements, (ii) they have high processing cost and (iii) they are based on complex structures, which are not available in commercial systems. In this paper we solve these problems by approximation techniques with bounded error. We propose two methods: the first one is based on multiversion B-trees and has logarithmic worst-case query cost, while the second technique uses off-the-shelf B- and R-trees, and achieves the same performance in the expected case. We experimentally demonstrate that the proposed methods consume an order of magnitude less space than their competitors and are significantly faster, even for cases that the permissible error bound is very small.
Rights: © 2004 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
URI: http://hdl.handle.net/1783.1/2509
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
papadias4.pdfpre-published version172KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.