6th International ICST Conference on Collaborative Computing: Networking, Applications, Worksharing

Research Article

Fixed-precision approximate continuous aggregate queries in peer-to-peer databases

Download95 downloads
  • @INPROCEEDINGS{10.4108/icst.collaboratecom.2010.2,
        author={Farnoush Banaei-Kashani and Cyrus Shahabi},
        title={Fixed-precision approximate continuous aggregate queries in peer-to-peer databases},
        proceedings={6th International ICST Conference on Collaborative Computing: Networking, Applications, Worksharing},
        publisher={IEEE},
        proceedings_a={COLLABORATECOM},
        year={2011},
        month={5},
        keywords={Histograms Meteorology Peer to peer computing Query processing},
        doi={10.4108/icst.collaboratecom.2010.2}
    }
    
  • Farnoush Banaei-Kashani
    Cyrus Shahabi
    Year: 2011
    Fixed-precision approximate continuous aggregate queries in peer-to-peer databases
    COLLABORATECOM
    ICST
    DOI: 10.4108/icst.collaboratecom.2010.2
Farnoush Banaei-Kashani1,*, Cyrus Shahabi1,*
  • 1: Computer Science Department, University of Southern California, Los Angeles, CA 90089
*Contact email: banaeika@usc.edu, shahabi@usc.edu

Abstract

In this paper, we propose an efficient sample-based approach to answer fixed-precision approximate continuous aggregate queries in peer-to-peer databases. First, we define practical semantics to formulate fixed-precision approximate continuous aggregate queries. Second, we propose "Digest", a two-tier system for correct and efficient query answering by sampling. At the top tier, we develop a query evaluation engine that uses the samples collected from the peer-to-peer database to continually estimate the running result of the approximate continuous aggregate query with guaranteed precision. For efficient query evaluation, we propose an extrapolation algorithm that predicts the evolution of the running result and adapts the frequency of the continual sampling occasions accordingly to avoid redundant samples. We also introduce a repeated sampling algorithm that draws on the correlation between the samples at successive sampling occasions and exploits linear regression to minimize the number of the samples derived at each occasion. At the bottom tier, we introduce a distributed sampling algorithm for random sampling (uniform and nonuniform) from peer-to-peer databases with arbitrary network topology and tuple distribution. Our sampling algorithm is based on the Metropolis Markov Chain Monte Carlo method that guarantees randomness of the sample with arbitrary small variation difference with the desired distribution, while it is comparable to optimal sampling in sampling cost/time. We evaluate the efficiency of Digest via simulation using real data.