ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Online aggregation
Full text PdfPdf (1.92 MB)
Source International Conference on Management of Data archive
Proceedings of the 1997 ACM SIGMOD international conference on Management of data table of contents
Tucson, Arizona, United States
Pages: 171 - 182  
Year of Publication: 1997
ISBN:0-89791-911-4
Also published in ...
Authors
Joseph M. Hellerstein  Computer Science Division, University of California, Berkeley
Peter J. Haas  Almaden Research Center, IBM Research Division
Helen J. Wang  Computer Science Division, University of California, Berkeley
Sponsor
SIGMOD: ACM Special Interest Group on Management of Data
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 28,   Downloads (12 Months): 201,   Citation Count: 161
Additional Information:

abstract   references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/253260.253291
What is a DOI?

ABSTRACT

Aggregation in traditional database systems is performed in batch mode: a query is submitted, the system processes a large volume of data over a long period of time, and, eventually, the final answer is returned. This archaic approach is frustrating to users and has been abandoned in most other areas of computing. In this paper we propose a new online aggregation interface that permits users to both observe the progress of their aggregation queries and control execution on the fly. After outlining usability and performance requirements for a system supporting online aggregation, we present a suite of techniques that extend a database system to meet these requirements. These include methods for returning the output in random order, for providing control over the relative rate at which different aggregates are computed, and for computing running confidence intervals. Finally, we report on an initial implementation of online aggregation in POSTGRES.


REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

 
AAD+96
Sameet Agarwal , Rakesh Agrawal , Prasad Deshpande , Ashish Gupta , Jeffrey F. Naughton , Raghu Ramakrishnan , Sunita Sarawagi, On the Computation of Multidimensional Aggregates, Proceedings of the 22th International Conference on Very Large Data Bases, p.506-521, September 03-06, 1996
 
ACSW96
Alexander Aiken , Jolly Chen , Michael Stonebraker , Allison Woodruff, Tioga-2: A Direct Manipulation Database Visualization Environment, Proceedings of the Twelfth International Conference on Data Engineering, p.208-217, February 26-March 01, 1996
 
AZ96
Gennady Antoshenkov , Mohamed Ziauddin, Query processing and optimization in Oracle Rdb, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.229-237, December 1996  [doi>10.1007/s007780050026]
 
Bil86
P. Billingsley. Probability and Measure. Wiley, New York, second edition, 1986.
BM96
Roberto J. Bayardo, Jr. , Daniel P. Miranker, Processing queries for first-few answers, Proceedings of the fifth international conference on Information and knowledge management, p.45-52, November 12-16, 1996, Rockville, Maryland, United States  [doi>10.1145/238355.238372]
 
Bra84
Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
 
CCS93
E. F. Codd, S. B. Codd, and C. T. Sal- Icy. Providing OLAP (on-line analyticalprocessing) to user-analysts: an IT mandate.URL http://www.arborsoft.com/papers/coddTOC.htmI., I993.
 
CGL83
T. F. Chan, G. H. Golub, and R. J. LeVeque. Algorithms for computing the sample variance: Analysis and recommendation. Amer. Statist., 37:242-247, 1983.
 
CS96
Surajit Chaudhuri , Kyuseok Shim, Optimizing Queries with Aggregate Views, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.167-182, March 25-29, 1996
DKO+84
David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
 
GBLP96
Jim Gray , Adam Bosworth , Andrew Layman , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Total, Proceedings of the Twelfth International Conference on Data Engineering, p.152-159, February 26-March 01, 1996
 
GHQ95
Ashish Gupta , Venky Harinarayan , Dallan Quass, Aggregate-Query Processing in Data Warehousing Environments, Proceedings of the 21th International Conference on Very Large Data Bases, p.358-369, September 11-15, 1995
 
Haa96a
P. J. Haas. Hoeffding inequalities for join-selectivity estimation and online aggregation. IBM Research Report RJ 10040, IBM Almaden Research Center, San Jose, CA, 1996.
 
Haa96b
P. J. Haas. Large-sample and deterministic confidence intervals for online aggregation. IBM Research Report RJ 10050, IBM Almaden Research Center, San Jose, CA, 1996.
HN96
Joseph M. Hellerstein , Jeffrey F. Naughton, Query execution techniques for caching expensive methods, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.423-434, June 04-06, 1996, Montreal, Quebec, Canada
 
HNSS96
Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996  [doi>10.1006/jcss.1996.0041]
HOD91
Wen-Chi Hou , Gultekin Ozsoyoglu , Erdogan Dogdu, Error-constrained COUNT query evaluation in relational databases, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.278-287, May 29-31, 1991, Denver, Colorado, United States
 
Hoe63
W. Hoeffding. Probability inequalities for sums of bounded random variables. J. Amer. Statist. Assoc., 58:13- 30, 1963.
HOT88
Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Statistical estimators for relational algebra expressions, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.276-287, March 1988, Austin, Texas, United States  [doi>10.1145/308386.308455]
HOT89
Wen-Chi Hou , Gultekin Ozsoyoglu , Baldeo K. Taneja, Processing aggregate relational queries with hard time constraints, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.68-77, June 1989, Portland, Oregon, United States
 
LNSS93
Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider , S. Seshadri, Efficient sampling strategies for relational database operations, Theoretical Computer Science, v.116 n.1, p.195-226, Aug. 2, 1993
Mye85
Brad A. Myers, The importance of percent-done progress indicators for computer-human interfaces, Proceedings of the SIGCHI conference on Human factors in computing systems, p.11-17, April 1985, San Francisco, California, United States
 
Olk93
F. Olken. Random Sampling from Databases. PhD thesis, University of California, Berkeley, 1993.
 
Pos95
Postgres95 home page,1995. UFI.L http://www, ki.net / postgres95.
SAC+79
P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts  [doi>10.1145/582095.582099]
SHP+96
Praveen Seshadri , Joseph M. Hellerstein , Hamid Pirahesh , T. Y. Cliff Leung , Raghu Ramakrishnan , Divesh Srivastava , Peter J. Stuckey , S. Sudarshan, Cost-based optimization for magic: algebra and implementation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.435-446, June 04-06, 1996, Montreal, Quebec, Canada
 
SPL96
Praveen Seshadri , Hamid Pirahesh , T. Y. Cliff Leung, Complex Query Decorrelation, Proceedings of the Twelfth International Conference on Data Engineering, p.450-458, February 26-March 01, 1996
 
VU92
Martin Vetterli , Kamil Metin Uz, Multiresolution coding techniques for digital television: a review, Multidimensional Systems and Signal Processing, v.3 n.2-3, p.161-187, May 1992  [doi>10.1007/BF01942041]
 
VL93
S. V. Vrbsky , J. W. S. Liu, APPROXIMATE: A Query Processor that Produces Monotonically Improving Approximate Answers, IEEE Transactions on Knowledge and Data Engineering, v.5 n.6, p.1056-1068, December 1993  [doi>10.1109/69.250091]
 
WA91
Annita N. Wilschut , Peter M. G. Apers, Dataflow query execution in a parallel main-memory environment, Proceedings of the first international conference on Parallel and distributed information systems, p.68-77, December 1991, Miami, Florida, United States
 
YL95
Weipeng P. Yan , Per-Åke Larson, Eager Aggregation and Lazy Aggregation, Proceedings of the 21th International Conference on Very Large Data Bases, p.345-357, September 11-15, 1995

CITED BY  161
Michael Benedikt , Leonid Libkin, Exact and approximate aggregation in constraint query languages, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Björn T. Jónsson , Michael J. Franklin , Divesh Srivastava, Interaction of query evaluation and buffer management for information retrieval, ACM SIGMOD Record, v.27 n.2, p.118-129, June 1998
Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, ACM SIGMOD Record, v.29 n.2, p.463-474, June 2000
Donghui Zhang , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient aggregation over objects with extent, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, ACM SIGMOD Record, v.30 n.2, p.401-412, June 2001
Rolfe R. Schmidt , Cyrus Shahabi, How to evaluate multiple range-sum queries progressively, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Raymond T. Ng , Laks V. S. Lakshmanan , Jiawei Han , Alex Pang, Exploratory mining and pruning optimizations of constrained associations rules, ACM SIGMOD Record, v.27 n.2, p.13-24, June 1998
Yannis Sismanis , Antonios Deligiannakis , Nick Roussopoulos , Yannis Kotidis, Dwarf: shrinking the PetaCube, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
Johannes Gehrke , Flip Korn , Divesh Srivastava, On computing correlated aggregates over continual data streams, ACM SIGMOD Record, v.30 n.2, p.13-24, June 2001
Donghui Zhang , Dimitrios Gunopulos , Vassilis J. Tsotras , Bernhard Seeger, Temporal and spatio-temporal aggregations over data streams using multiple time granularities, Information Systems, v.28 n.1-2, p.61-84, 01 March 2003
Christopher R. Palmer , Christos Faloutsos, Density biased sampling: an improved method for data mining and clustering, ACM SIGMOD Record, v.29 n.2, p.82-92, June 2000
Ron Avnur , Joseph M. Hellerstein , Bruce Lo , Chris Olston , Bhaskaran Raman , Vijayshankar Raman , Tali Roth , Kirk Wylie, CONTROL: continuous output and navigation technology with refinement on-line, ACM SIGMOD Record, v.27 n.2, p.567-569, June 1998
Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States
Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, ACM SIGMOD Record, v.30 n.2, p.295-306, June 2001
Jun Rao , Kenneth A. Ross, Reusing invariants: a new strategy for correlated queries, ACM SIGMOD Record, v.27 n.2, p.37-48, June 1998
Gang Luo , Curt J. Ellmann , Peter J. Haas , Jeffrey F. Naughton, A scalable hash ripple join algorithm, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Francis Chu , Joseph Halpern , Johannes Gehrke, Least expected cost query optimization: what can we expect?, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, ACM SIGMOD Record, v.29 n.2, p.487-498, June 2000
Anna Fredrikson , Chris North , Catherine Plaisant , Ben Shneiderman, Temporal, geographical and categorical aggregations viewed through coordinated displays: a case study with highway incident data, Proceedings of the 1999 workshop on new paradigms in information visualization and manipulation in conjunction with the eighth ACM internation conference on Information and knowledge management, p.26-34, November 02-06, 1999, Kansas City, Missouri, United States
Raymond T. Ng , Alan Wagner , Yu Yin, Iceberg-cube computation with PC clusters, ACM SIGMOD Record, v.30 n.2, p.25-36, June 2001
Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, ACM SIGMOD Record, v.28 n.2, p.263-274, June 1999
Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, ACM SIGMOD Record, v.28 n.2, p.287-298, June 1999
Haifeng Yu , Amin Vahdat, Design and evaluation of a conit-based continuous consistency model for replicated services, ACM Transactions on Computer Systems (TOCS), v.20 n.3, p.239-282, August 2002
Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, ACM SIGMOD Record, v.28 n.2, p.275-286, June 1999
Leonidas Fegaras , David Levine , Sujoe Bose , Vamsi Chaluvadi, Query processing of streamed XML data, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Yong Yao , Johannes Gehrke, The cougar approach to in-network query processing in sensor networks, ACM SIGMOD Record, v.31 n.3, September 2002
Jorge R. Bernardino , Pedro S. Furtado , Henrique C. Madeira, Approximate Query Answering Using Data Warehouse Striping, Journal of Intelligent Information Systems, v.19 n.2, p.145-167, September 2002
Daniel Barbará , Xintao Wu, Loglinear-Based Quasi Cubes, Journal of Intelligent Information Systems, v.16 n.3, p.255-276, August 2001
Christian Hidber, Online association rule mining, ACM SIGMOD Record, v.28 n.2, p.145-156, June 1999
Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, ACM SIGMOD Record, v.28 n.2, p.193-204, June 1999
Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, ACM SIGMOD Record, v.28 n.2, p.239-250, June 1999
Noga Alon , Phillip B. Gibbons , Yossi Matias , Mario Szegedy, Tracking join and self-join sizes in limited storage, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.10-20, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Marin J. Strauss, Optimal and approximate computation of summary statistics for range aggregates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 2001, Santa Barbara, California, United States
Ratko Orlandic , Byunggu Yu, A retrieval technique for high-dimensional data and partially specified queries, Data & Knowledge Engineering, v.42 n.1, p.1-21, July 2002
Changzhou Wang , Xiaoyang Sean Wang, High-dimensional nearest neighbor search with remote data centers, Knowledge and Information Systems, v.4 n.4, p.440-465, October 2002
Etzard Stolte , Gustavo Alonso, Approximated trial and error analysis in scientific databases, Information Systems, v.28 n.1-2, p.137-157, 01 March 2003
Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Query Rewriting for SWIFT (First) Answers, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.694-714, September 2000
Yannis Sismanis , Antonios Deligiannakis , Yannis Kotidis , Nick Roussopoulos, Hierarchical dwarfs for the rollup cube, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
Laks V. S. Lakshmanan , Carson Kai-Sang Leung , Raymond T. Ng, Efficient dynamic mining of constrained frequent sets, ACM Transactions on Database Systems (TODS), v.28 n.4, p.337-389, December 2003
Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Approximation techniques for spatial data, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Jarek Gryz , Junjie Guo , Linqi Liu , Calisto Zuzarte, Query sampling in DB2 Universal Database, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, ACM SIGMOD Record, v.27 n.2, p.237-248, June 1998
Haixun Wang , Carlo Zaniolo, Nonmonotonic reasoning in LDL++, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Joseph M. Hellerstein , Ron Avnur , Andy Chou , Christian Hidber , Chris Olston , Vijayshankar Raman , Tali Roth , Peter J. Haas, Interactive Data Analysis: The Control Project, Computer, v.32 n.8, p.51-59, August 1999
Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002
Zhiyuan Chen , Flip Korn , Nick Koudas , S. Muthukrishnan, Generalized substring selectivity estimation, Journal of Computer and System Sciences, v.66 n.1, p.98-132, 01 February 2003
Gang Luo , Jeffrey F. Naughton , Curt J. Ellmann , Michael W. Watzke, Toward a progress indicator for database queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Peter J. Haas , Christian König, A bi-level Bernoulli scheme for database sampling, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Expressing and optimizing sequence queries in database systems, ACM Transactions on Database Systems (TODS), v.29 n.2, p.282-318, June 2004
Christopher Jermaine , Abhijit Pol , Subramanian Arumugam, Online maintenance of very large random samples, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Surajit Chaudhuri , Vivek Narasayya , Ravishankar Ramamurthy, Estimating progress of execution for SQL queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Zachary G. Ives , Alon Y. Halevy , Daniel S. Weld, Adapting to source properties in processing data integration queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Peter A. Tucker , David Maier , Tim Sheard , Leonidas Fegaras, Exploiting Punctuation Semantics in Continuous Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.555-568, March 2003
Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Janusz R. Getta , Ehsan Vossough, Optimization of data stream processing, ACM SIGMOD Record, v.33 n.3, September 2004
Chris Stolte , Diane Tang , Pat Hanrahan, Polaris: A System for Query, Analysis, and Visualization of Multidimensional Relational Databases, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.52-65, January 2002
Shivnath Babu , Jennifer Widom, Continuous queries over data streams, ACM SIGMOD Record, v.30 n.3, September 2001
Edith Cohen , Mayur Datar , Shinji Fujiwara , Aristides Gionis , Piotr Indyk , Rajeev Motwani , Jeffrey D. Ullman , Cheng Yang, Finding Interesting Associations without Support Pruning, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.64-78, January 2001
Minos Garofalakis , Phillip B. Gibbons, Probabilistic wavelet synopses, ACM Transactions on Database Systems (TODS), v.29 n.1, p.43-90, March 2004
Abhijit Pol , Christopher Jermaine, Relational confidence bounds are easy with the bootstrap, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

, December 09-11, 2002, Boston, Massachusetts
Henrike Berthold , Sven Schmidt , Wolfgang Lehner , Claude-Joachim Hamann, Integrated resource management for data stream systems, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Minos Garofalakis , Amit Kumar, Deterministic wavelet thresholding for maximum-error metrics, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
Surajit Chaudhuri , Raghav Kaushik , Ravishankar Ramamurthy, When can we trust progress estimators for SQL queries?, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Ines Fernando Vega Lopez , Richard T. Snodgrass , Bongki Moon, Spatiotemporal Aggregate Computation: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.271-286, February 2005
Joseph M. Hellerstein , Wei Wang, Optimization of in-network data reduction, Proceeedings of the 1st international workshop on Data management for sensor networks: in conjunction with VLDB 2004, August 30-30, 2004, Toronto, Canada
Sudipto Guha, Space efficiency in synopsis construction algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Alfredo Cuzzocrea, Providing probabilistically-bounded approximate answers to non-holistic aggregate range queries in OLAP, Proceedings of the 8th ACM international workshop on Data warehousing and OLAP, November 04-05, 2005, Bremen, Germany
Christopher Jermaine , Alin Dobra , Abhijit Pol , Shantanu Joshi, Online estimation for subset-based SQL queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Xiaohui Yu , Calisto Zuzarte , Kenneth C. Sevcik, Towards estimating the number of distinct value combinations for a set of attributes, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Minos Garofalakis , Amit Kumar, Wavelet synopses for general error metrics, ACM Transactions on Database Systems (TODS), v.30 n.4, p.888-928, December 2005
João Pedro Costa , Pedro Furtado, DSQoS-distributed architecture providing QoS in summary warehouses, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA
Alfredo Cuzzocrea, Improving range-sum query evaluation on data cubes via polynomial approximation, Data & Knowledge Engineering, v.56 n.2, p.85-121, February 2006
Noga Alon , Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating arbitrary subset sums with few probes, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Christopher Jermaine , Alin Dobra , Subramanian Arumugam , Shantanu Joshi , Abhijit Pol, A disk-based join with probabilistic guarantees, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
Hua-Fu Li , Suh-Yin Lee , Man-Kwan Shan, DSM-PLW: single-pass mining of path traversal patterns over streaming web click-sequences, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.10, p.1474-1487, 14 July 2006
Vijayshankar Raman , Joseph M. Hellerstein, Partial results for online query processing, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Saket Navlakha , Rajeev Rastogi , Nisheeth Shrivastava, Graph summarization with bounded error, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
Foto N. Afrati , Paraskevas V. Lekeas , Chen Li, Adaptive-sampling algorithms for answering aggregation queries on Web sites, Data & Knowledge Engineering, v.64 n.2, p.462-490, February, 2008
Charu C. Aggarwal, On biased reservoir sampling in the presence of stream evolution, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Dushyanth Narayanan , Austin Donnelly , Richard Mortier , Antony Rowstron, Delay aware querying with seaweed, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Gang Luo, Efficient detection of empty-result queries, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Nesime Tatbul , Stan Zdonik, Window-aware load shedding for aggregation queries over data streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Matthew Denny , Michael J. Franklin, Adaptive execution of variable-accuracy functions, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
Jen-Yeu Chen , Gopal Pandurangan , Dongyan Xu, Robust computation of aggregates in wireless sensor networks: distributed randomized algorithms and analysis, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
Chengkai Li , Kevin Chen-Chuan Chang , Ihab F. Ilyas, Supporting ad-hoc ranking aggregates, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
Igor Timko , Curtis E. Dyreson , Torben Bach Pedersen, Pre-aggregation with probability distributions, Proceedings of the 9th ACM international workshop on Data warehousing and OLAP, November 10-10, 2006, Arlington, Virginia, USA
Antonios Deligiannakis , Minos Garofalakis , Nick Roussopoulos, Extended wavelets for multiple measures, ACM Transactions on Database Systems (TODS), v.32 n.2, p.10-es, June 2007
Christopher Jermaine , Alin Dobra , Subramanian Arumugam , Shantanu Joshi , Abhijit Pol, The Sort-Merge-Shrink join, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1382-1416, December 2006
Edith Cohen , Nick Duffield , Haim Kaplan , Carsten Lund , Mikkel Thorup, Sketching unaggregated data streams for subpopulation-size queries, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
Alfredo Cuzzocrea , Wei Wang, Approximate range---sum query answering on data cubes with probabilistic guarantees, Journal of Intelligent Information Systems, v.28 n.2, p.161-197, April 2007
Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Journal of Computer and System Sciences, v.73 n.3, p.245-264, May, 2007
Ying Hu , Seema Sundara , Jagannathan Srinivasan, Supporting time-constrained SQL queries in oracle, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
Christopher Jermaine, Robust estimation with sampling and approximate pre-aggregation, Proceedings of the 29th international conference on Very large data bases, p.886-897, September 09-12, 2003, Berlin, Germany
Sudipto Guha , Chulyun Kim , Kyuseok Shim, XWAVE: optimal and approximate extended wavelets, Proceedings of the Thirtieth international conference on Very large data bases, p.288-299, August 31-September 03, 2004, Toronto, Canada
Yan-Nei Law , Haixun Wang , Carlo Zaniolo, Query languages and data models for database sequences and data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.492-503, August 31-September 03, 2004, Toronto, Canada
Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
Haixun Wang , Carlo Zaniolo , Chang Richard Luo, ATLAS: a small but complete SQL extension for data mining and data streams, Proceedings of the 29th international conference on Very large data bases, p.1113-1116, September 09-12, 2003, Berlin, Germany
Jens-Peter Dittrich , Bernhard Seeger , David Scot Taylor , Peter Widmayer, Progressive merge join: a generic and non-blocking sort-based join algorithm, Proceedings of the 28th international conference on Very Large Data Bases, p.299-310, August 20-23, 2002, Hong Kong, China
Etzard Stolte , Gustavo Alonso, Efficient exploration of large scientific databases, Proceedings of the 28th international conference on Very Large Data Bases, p.622-633, August 20-23, 2002, Hong Kong, China
Don Carney , Uǧur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Greg Seidman , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Monitoring streams: a new class of data management applications, Proceedings of the 28th international conference on Very Large Data Bases, p.215-226, August 20-23, 2002, Hong Kong, China
Surajit Chaudhuri , Gautam Das , Vivek Narasayya, Optimized stratified sampling for approximate query processing, ACM Transactions on Database Systems (TODS), v.32 n.2, p.9-es, June 2007
Greg Barish , Craig A. Knoblock, Speculative plan execution for information gathering, Artificial Intelligence, v.172 n.4-5, p.413-453, March, 2008
Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online dynamic reordering, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.247-260, December 2000
Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Progressive evaluation of nested aggregate queries, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.3, p.261-278, December 2000
Kaushik Chakrabarti , Minos Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate query processing using wavelets, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.199-223, September 2001
Jochen Van den Bercken , Björn Blohsfeld , Jens-Peter Dittrich , Jürgen Krämer , Tobias Schäfer , Martin Schneider , Bernhard Seeger, XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.39-48, September 11-14, 2001
Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
Chris Olston , Jennifer Widom, Offering a Precision-Performance Tradeoff for Aggregation Queries over Replicated Data, Proceedings of the 26th International Conference on Very Large Data Bases, p.144-155, September 10-14, 2000
Haixun Wang , Carlo Zaniolo, Using SQL to Build New Aggregates and Extenders for Object- Relational Systems, Proceedings of the 26th International Conference on Very Large Data Bases, p.166-175, September 10-14, 2000
Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
Minos N. Garofalakis , Phillip B. Gibbon, Approximate Query Processing: Taming the TeraBytes, Proceedings of the 27th International Conference on Very Large Data Bases, p.725, September 11-14, 2001
Dimitrios Gunopulos , George Kollios , J. Tsotras , Carlotta Domeniconi, Selectivity estimators for multidimensional range queries over real attributes, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.137-154, April 2005
Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
Vijayshankar Raman , Bhaskaran Raman , Joseph M. Hellerstein, Online Dynamic Reordering for Interactive Data Processing, Proceedings of the 25th International Conference on Very Large Data Bases, p.709-720, September 07-10, 1999
Kian-Lee Tan , Cheng Hian Goh , Beng Chin Ooi, Online Feedback for Nested Aggregate Queries with Multi-Threading, Proceedings of the 25th International Conference on Very Large Data Bases, p.18-29, September 07-10, 1999
Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
Hüseyin Akcan , Alex Astashyn , Hervé Brönnimann, Deterministic algorithms for sampling count data, Data & Knowledge Engineering, v.64 n.2, p.405-418, February, 2008
Fei Xu , Christopher Jermaine, Randomized algorithms for data reconciliation in wide area aggregate query processing, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003
A. Sharaf , Jonathan Beaver , Alexandros Labrinidis , K. Chrysanthis, Balancing energy efficiency and quality of aggregate data in sensor networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.384-403, December 2004
Lixin Fu , Sanguthevar Rajasekaran, Evaluating holistic aggregators efficiently for very large datasets, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.2, p.148-161, May 2004
Joseph M. Hellerstein , Ron Avnur , Vijayshankar Raman, Informix under CONTROL: Online Query Processing, Data Mining and Knowledge Discovery, v.4 n.4, p.281-314, October 2000
Christoph Koch, Approximating predicates and expressive queries on probabilistic databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
Florin Rusu , Fei Xu , Luis Leopoldo Perez , Mingxi Wu , Ravi Jampani , Chris Jermaine , Alin Dobra, The DBO database system, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
Lihua Yuan , Chen-Nee Chuah , Prasant Mohapatra, ProgME: towards programmable network measurement, ACM SIGCOMM Computer Communication Review, v.37 n.4, October 2007
Chris Jermaine , Subramanian Arumugam , Abhijit Pol , Alin Dobra, Scalable approximate query processing with the DBO engine, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-54, November 2008
Ravi Jampani , Fei Xu , Mingxi Wu , Luis Leopoldo Perez , Christopher Jermaine , Peter J. Haas, MCDB: a monte carlo approach to managing uncertain data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
Man Lung Yiu , Nikos Mamoulis , Vagelis Hristidis, Extracting k most important groups from data efficiently, Data & Knowledge Engineering, v.66 n.2, p.289-310, August, 2008
Eric Lo , Ben Kao , Wai-Shing Ho , Sau Dan Lee , Chun Kit Chui , David W. Cheung, OLAP on sequence data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
Joseph M. Hellerstein , Michael Stonebraker , James Hamilton, Architecture of a Database System, Foundations and Trends in Databases, v.1 n.2, p.141-259, February 2007
Sudipto Guha, On the space---time of optimal, approximate and streaming algorithms for synopsis construction problems, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1509-1535, November 2008
Songyun Duan , Shivanath Babu, Processing forecasting queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Edith Cohen , Nick Duffield , Haim Kaplan , Carsten Lund , Mikkel Thorup, Algorithms and estimators for accurate summarization of internet traffic, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA
Naixue Xiong , Laurence T. Yang , Yingshu Li, ODMCA: An adaptive data mining control algorithm in multicarrier networks, Computer Communications, v.32 n.3, p.560-567, February, 2009
Nick Duffield , Carsten Lund , Mikkel Thorup, Priority sampling for estimation of arbitrary subset sums, Journal of the ACM (JACM), v.54 n.6, p.32-es, December 2007
Mingxi Wu , Christopher Jermaine, A Bayesian method for guessing the extreme values in a data set?, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
Elaheh Pourabbas , Arie Shoshani, Improving estimation accuracy of aggregate queries on data cubes, Proceeding of the ACM 11th international workshop on Data warehousing and OLAP, October 30-30, 2008, Napa Valley, California, USA
Ihab F. Ilyas , George Beskales , Mohamed A. Soliman, A survey of top-k query processing techniques in relational database systems, ACM Computing Surveys (CSUR), v.40 n.4, p.1-58, October 2008
Christopher Jermaine, Online Random Shuffling of Large Database Tables, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.73-84, January 2007
Abhijit Pol , Christopher Jermaine , Subramanian Arumugam, Maintaining very large random samples using the geometric file, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.997-1018, August 2008
Sudipto Guha , Hyoungmin Park , Kyuseok Shim, Wavelet synopsis for hierarchical range queries with workloads, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1079-1099, August 2008
Fei Xu , Christopher Jermaine , Alin Dobra, Confidence bounds for sampling-based group by estimates, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-44, August 2008
Mohamed A. Soliman , Ihab F. Ilyas , Kevin Chen--Chuan Chang, Probabilistic top-k and ranking-aggregate queries, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-54, August 2008
Katja Hose , Armin Roth , André Zeitz , Kai-Uwe Sattler , Felix Naumann, A research agenda for query processing in large-scale peer data management systems, Information Systems, v.33 n.7-8, p.597-610, November, 2008
Jürgen Krämer , Bernhard Seeger, Semantics and implementation of continuous sliding window queries over data streams, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-49, April 2009
Seungjae Lee , Changhwa Kim , Sangkyung Kim, New join operator definitions for sensor network databases, Proceedings of the 6th conference on Applications of electrical engineering, p.41-46, May 27-29, 2007, Istanbul, Turkey
Ramakrishna Varadarajan , Vagelis Hristidis , Louiqa Raschid , Maria-Esther Vidal , Luis Ibáñez , Héctor Rodríguez-Drumond, Flexible and efficient querying and ranking on hyperlinked data sources, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
Xuan Hong Dang , Wee-Keong Ng , Kok-Leong Ong, Online mining of frequent sets in data streams with error guarantee, Knowledge and Information Systems, v.16 n.2, p.245-258, July 2008
Chaitanya Mishra , Nick Koudas, The design of a query monitoring system, ACM Transactions on Database Systems (TODS), v.34 n.1, p.1-51, April 2009
Jun-Ki Min , Chun-Hee Lee , Chin-Wan Chung, AMID: Approximation of MultI-measured Data using SVD, Information Sciences: an International Journal, v.179 n.16, p.2833-2850, July, 2009
Mingxi Wu , Chris Jermaine, Guessing the extreme values in a data set: a Bayesian method and its applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.571-597, April 2009
Shantanu Joshi , Christopher Jermaine, Sampling-based estimators for subset-based queries, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.181-202, January 2009
Carlo Dell'Aquila , Francesco Di Tria , Ezio Lefons , Filippo Tangorra, Data reduction for data analysis, Proceedings of the 2nd conference on European computing conference, p.204-210, September 11-13, 2008, Malta
Greg Barish , Craig A. Knoblock, Learning value predictors for the speculative execution of information gathering plans, Proceedings of the 18th international joint conference on Artificial intelligence, p.3-9, August 09-15, 2003, Acapulco, Mexico
Wei Fan , Haixun Wang , Philip S. Yu , Shaw-Hwa Lo, Inductive learning in less than one sequential data scan, Proceedings of the 18th international joint conference on Artificial intelligence, p.595-600, August 09-15, 2003, Acapulco, Mexico

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.2 Installation Management
          Subjects: Performance and usage measurement


General Terms:
Algorithms, Design, Management, Measurement, Performance, Theory

Collaborative Colleagues:
Joseph M. Hellerstein: colleagues
Peter J. Haas: colleagues
Helen J. Wang: colleagues
This Article has also been published in:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player