Open AccessContinuous sampling for online aggregation over multiple queries
Author(s) -
Sai Wu,
Beng Chin Ooi,
KianLee Tan
Publication year - 2010
Publication title -
citeseer x (the pennsylvania state university)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/1807167.1807238
Subject(s) - computer science , exploit , benchmark (surveying) , aggregate (composite) , node (physics) , cosmos (plant) , directed acyclic graph , graph , sampling (signal processing) , data mining , information retrieval , theoretical computer science , algorithm , filter (signal processing) , computer vision , art , materials science , computer security , geodesy , structural engineering , engineering , composite material , art history , geography
In this paper, we propose an online aggregation system called COSMOS (Continuous Sampling for Multiple queries in an Online aggregation System), to process multiple aggregate queries efficiently. In COSMOS, a dataset is first scrambled so that sequentially scanning the dataset gives rise to a stream of random samples for all queries. Moreover, COSMOS organizes queries into a dissemination graph to exploit the dependencies across queries. In this way, aggregates of queries closer to the root (source of data flow) can potentially be used to compute the aggregates of descendent/dependent queries. COSMOS applies some statistical approach to combine answers from ancestor nodes to generate the online aggregates for a node. COSMOS also offers a partitioning strategy to further salvage intermediate answers. We have implemented COSMOS and conducted an extensive experimental study in PostgreSQL. Our results on the TPC-H benchmark show the efficiency and effectiveness of COSMOS.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom