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
Tracking join and self-join sizes in limited storage
Full text PdfPdf (1.40 MB)
Source Symposium on Principles of Database Systems archive
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents
Philadelphia, Pennsylvania, United States
Pages: 10 - 20  
Year of Publication: 1999
ISBN:1-58113-062-7
Authors
Noga Alon  Dept. of Mathematics, Tel Aviv University, Tel Aviv, Israel
Phillip B. Gibbons  Information Sciences Research, Bell Laboratories, Murray Hill, NJ
Yossi Matias  Dept. of Computer Science, Tel Aviv University, Tel Aviv, Israel
Mario Szegedy  Information Sciences Research, AT&T Labs, Florham Park, NJ
Sponsors
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 12,   Downloads (12 Months): 68,   Citation Count: 47
Additional Information:

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/303976.303978
What is a DOI?

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.

 
AGP99
S. Acharya, P. B. Gibbons, and V. Poosala. Congressional samples for approximate answering of group-by queries. Technical report, Bell Laboratories, Murray Hill, New Jersey, March 1999.
AGPR99
Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
AMS96
Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States  [doi>10.1145/237814.237823]
 
BDF+97
D. Barbar~, W. DuMouchel, C. Faloutsos, P. J. Haas, J. IVl. Hellerstein, Y. Ioannidis, H. V. Jagadish, T. Johnson, R. Ng, V. Poosala, K. A. Ross, and K. C. Sevcik. The New Jersey data reduction report. Bulletin of the Technical Committee on Data Engineering, 20(4):3-45, 1997.
GGMS96
Sumit Ganguly , Phillip B. Gibbons , Yossi Matias , Avi Silberschatz, Bifocal sampling for skew-resistant join size estimation, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.271-281, June 04-06, 1996, Montreal, Quebec, Canada
GM98a
Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
 
GM98b
Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
 
GMP97a
P.B. Gibbons, Y. Matias, and V. Poosala. Aqua project white paper. Technical report, Bell Laboratories, Murray Hill, New Jersey, December 1997.
 
GMP97b
Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
 
Goo89
I.J. Good. Surprise indexes and p-values. J. Statistical Computation and Simulation, 32:90- 92, 1989.
HH99
Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
HHW97
Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
HNSS93
Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Fixed-precision estimation of join selectivity, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.190-201, May 25-28, 1993, Washington, D.C., United States  [doi>10.1145/153850.153875]
 
HNSS95
Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
HÖT88
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]
IP95
Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
 
LN95
Richard J. Lipton , Jeffrey F. Naughton, Query size estimation by adaptive sampling, Journal of Computer and System Sciences, v.51 n.1, p.18-25, Aug. 1995
LNS90
Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
MRL98
Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
 
MS99
Y. Matias and E. Segal. Approximate iceberg queries. Technical report, Department of Computer Science, Tel Aviv University, Tel Aviv, Israel, March 1999.
 
Poo97
Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
Vit85
Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985  [doi>10.1145/3147.3165]
 
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]

CITED BY  47
Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Processing complex aggregate queries over data streams, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Phillip B. Gibbons , Srikanta Tirthapura, Estimating simple functions on the union of data streams, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.281-291, July 2001, Crete Island, Greece
Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
Minos Garofalakis , Amit Kumar, Correlating XML data streams using tree-edit distance embeddings, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.143-154, June 09-11, 2003, San Diego, California
Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California
Tamraparni Dasu , Theodore Johnson , S. Muthukrishnan , Vladislav Shkapenyuk, Mining database structure; or, how to build a data quality browser, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
Yabo Xu , Ke Wang , Ada Wai-Chee Fu , Rong She , Jian Pei, Classification spanning correlated data streams, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
Wei Wang , Haifeng Jiang , Hongjun Lu , Jeffrey Xu Yu, Containment join size estimation: models and methods, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Venkatesh Ganti , Johannes Gehrke , Raghu Ramakrishnan, Mining data streams under block evolution, ACM SIGKDD Explorations Newsletter, v.3 n.2, January 2002
Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Processing set expressions over continuous update streams, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
Raghav Kaushik , Jeffrey F. Naughton , Raghu Ramakrishnan , Venkatesan T. Chakravarthy, Synopses for query optimization: A space-complexity perspective, ACM Transactions on Database Systems (TODS), v.30 n.4, p.1102-1127, December 2005
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
Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France
Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
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
Alin Dobra, Histograms revisited: when are histograms the best approximation method for aggregates over joins?, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003
Minos Garofalakis , Amit Kumar, XML stream processing using tree-edit distance embeddings, ACM Transactions on Database Systems (TODS), v.30 n.1, p.279-332, March 2005
A. R. Calderbank , A. Gilbert , K. Levchenko , S. Muthukrishnan , M. Strauss, Improved range-summable random variable construction algorithms, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005
Cheng Luo , Zhewei Jiang , Wen-Chi Hou, Applying cosine series to join size estimation, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005
Sumit Ganguly , Minos Garofalakis , Amit Kumar , Rajeev Rastogi, Join-distinct aggregate estimation over update streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
Graham Cormode , S. Muthukrishnan, What's new: finding significant differences in network data streams, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1219-1232, December 2005
Raghav Kaushik , Raghu Ramakrishnan , Venkatesan T. Chakaravarthy, Synopses for query optimization: a space-complexity perspective, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
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
S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
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
Utkarsh Srivastava , Jennifer Widom, Memory-limited execution of windowed stream joins, Proceedings of the Thirtieth international conference on Very large data bases, p.324-335, August 31-September 03, 2004, Toronto, Canada
Graham Cormode , Minos Garofalakis, Streaming in a connected world: querying and tracking distributed data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Graham Cormode , Minos Garofalakis, Sketching probabilistic data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China
Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, 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
Sumit Ganguly , Minos Garofalakis , Rajeev Rastogi, Tracking set-expression cardinalities over continuous update streams, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.354-369, December 2004
Xenofontas Dimitropoulos , Paul Hurley , Andreas Kind, Probabilistic lossy counting: an efficient algorithm for finding heavy hitters, ACM SIGCOMM Computer Communication Review, v.38 n.1, January 2008
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
Graham Cormode , Minos Garofalakis, Approximate continuous querying over distributed streams, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-39, June 2008
J. Aguilar-Saborit , P. Trancoso , V. Muntes-Mulero , J. L. Larriba-Pey, Dynamic adaptive data structures for monitoring data streams, Data & Knowledge Engineering, v.66 n.1, p.92-115, July, 2008
Feng Yan , Wen-Chi Hou , Zhewei Jiang , Cheng Luo , Qiang Zhu, Selectivity estimation of range queries based on data density approximation via cosine series, Data & Knowledge Engineering, v.63 n.3, p.855-878, December, 2007
Yufei Tao , Xiang Lian , Dimitris Papadias , Marios Hadjieleftheriou, Random Sampling for Continuous Streams with Arbitrary Updates, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.96-110, January 2007
Xenofontas Dimitropoulos , Marc Stoecklin , Paul Hurley , Andreas Kind, The eternal sunshine of the sketch data structure, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.17, p.3248-3257, December, 2008
Cheng Luo , Zhewei Jiang , Wen-Chi Hou , Feng Yan , Qiang Zhu, A relational model for XML structural joins and their size estimations, Knowledge and Information Systems, v.16 n.1, p.97-127, July 2008
Alin Dobra , Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Multi-query optimization for sketch-based estimation, Information Systems, v.34 n.2, p.209-230, April, 2009
N. Ntarmos , P. Triantafillou , G. Weikum, Distributed hash sketches: Scalable, efficient, and accurate cardinality estimation for distributed multisets, ACM Transactions on Computer Systems (TOCS), v.27 n.1, p.1-53, February 2009
Karl Schnaitter , Joshua Spiegel , Neoklis Polyzotis, Depth estimation for ranking query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.2, p.521-542, April 2009

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases


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

Collaborative Colleagues:
Noga Alon: colleagues
Phillip B. Gibbons: colleagues
Yossi Matias: colleagues
Mario Szegedy: colleagues

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