FastRAQ: A Fast Approach to Range-Aggregate Queries in Big Data Environments

摘要

Range-aggregate queries are to apply a certain aggregate function on all tuples within given query ranges. Existing approaches to range-aggregate queries are insufficient to quickly provide accurate results in big data environments. In this paper, we propose FastRAQ—a fast approach to range-aggregate queries in big data environments. FastRAQ first divides big data into independent partitions with a balanced partitioning algorithm, and then generates a local estimation sketch for each partition. When a range-aggregate query request arrives, FastRAQ obtains the result directly by summarizing local estimates from all partitions. FastRAQ has time complexity for data updates and time complexity for range-aggregate queries, where is the number of distinct tuples for all dimensions, is the partition number, and is the bucket number in the histogram. We implement the FastRAQ approach on the Linux platform, and evaluate its performance with about 10 billions data records. Experimental results demonstrate that FastRAQ provides range-aggregate query results within a time per- od two orders of magnitude lower than that of Hive, while the relative error is less than 3 percent within the given confidence interval.