Association for Computing Machinery
Query authentication is an essential component in Outsourced DataBase (ODB) systems. This paper introduces efficient index structures for authenticating aggregation queries over large datasets. First, the authors design an index that features good performance characteristics for static environments. Then, they propose more involved structures for the dynamic case. Their structures feature excellent performance for authenticating queries with multiple aggregate attributes and multiple selection predicates. Furthermore, their techniques cover a large number of aggregate types, including distributive aggregates (such as SUM, COUNT, MIN, and MAX), algebraic aggregates (such as the AVG), and holistic aggregates (such asMEDIAN and QUANTILE).