Article

Free access

Synopsis data structures for massive data sets

Authors:

Phillip B. Gibbons,

Yossi MatiasAuthors Info & Claims

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

Pages 909 - 910

Published: 01 January 1999 Publication History

PDF eReader

Abstract

No abstract available.

References

[1]

N. Alon, Y. Matins, and M. Szegedy, The space comple.zity of approzimating the frequency moments, in Proc. 28th ACM Syrup. on the Theory of Computing, May 1996, pp. 20-29. Full version to appear in JCSS special issue for STOC'96.

Digital Library

Google Scholar

[2]

D. Barbar~ et al., The New Jersey data reduction repor#, Bulletin of the Technical Committee on Data Engineering, 20 (1997), pp. 3-45.

Google Scholar

[3]

S. Chaudhuri, R. Motwani, and V. Narasayya, Random sampling for histogram construction: How much is enough?, in Proc. ACM SIGMOD Int'l Conf. on Management of Data, June 1998, pp. 436-447.

Digital Library

Google Scholar

[4]

C. Faloutsos, Y. Matias, and A. Silberschatz, Modeling skewed distribution using multifractals and the '80-20' law, in Proc. 22rd Int'l Conf. on Very Large Data Bases, Sept. 1996, pp. 307-317.

Digital Library

Google Scholar

[5]

M. Fang, N. Shivakumar, H. Garcia-Molina, R. Motwani, and J. D. Ullman, Computing iceberg queries efficiently, in Proc. 24th Int'l Conf. on Very Large Data Bases, Aug. 1998, pp. 299-310.

Digital Library

Google Scholar

[6]

P. Flajolet and G. N. Martin, Probabilistic counting algorithms for data base applications, J. Computer and System Sciences, 31 (1985), pp. 182-209.

Digital Library

Google Scholar

[7]

P.B. Gibbons and Y. Matins, New sampling-based summary statistics for improving approximate query answers, in Proc. ACM SIGMOD Iat'l Conf. on Management of Data, June 1998, pp. 331-342.

Digital Library

Google Scholar

[8]

--#--, Synopsis data structures for massive data sets, DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, (1998). To appear. Available as Bell Labs tech. rep., Sept. 1998, and at http://www, bell-1 abs.com/" pbgibbons/.

Google Scholar

[9]

P.B. Gibbons, Y. Matins, and V. Poosala, Aqua project white paper, tech. rep., Bell Laboratories, Murray Hill, New Jersey, Dec. 1997.

Google Scholar

[10]

--#---, Fast incremental maintenance of approximate histograms, in Proc. 23rd Int'l Conf. on Very Large Data Bases, Aug. 1997, pp. 466-475.

Digital Library

Google Scholar

[11]

P. B. Gibbons, V. Poosala, S. Acharya, Y. Bartal, Y. Matins, S. Muthukristman, S. Ramaswamy, and T. Suel, A QUA: Syst#n and techniques for approximate query answering, teeh. rep., Bell Laboratories, Murray Hill, New Jersey, Feb. 1998.

Google Scholar

[12]

G. S. Manku, S. Rajagopalan, and B. G. Lindsley, Approximate medians and other quantiles in one pass and with limited memory, in Proc. ACM SIGMOD #t'l Conf. on Management of Data, June 1998, pp. 426-435.

Digital Library

Google Scholar

[13]

Y. Matins, 3. S. Vitter, and M. Wang, Wavelet-based histograms for selectivity estimation, in Proc. ACM SIGMOD Imt'l Conf. on Management of Data, June 1998, pp. 448-459.

Digital Library

Google Scholar

[14]

V. Poosala, Y. E. Ioannidis, P. J. Haas, and E. J. c range predicates, fix Proc. ACM SIGMOD Int'l Cc:af. on Management of Data, June 1996, pp. 294- 305.

Digital Library

Google Scholar

[15]

J. S. Vitter and E. A. M. Shriver, Algorithms .for parallel memory I: Two-level memories, Algorithmica, 12 (1994), pp. 110-147.

Google Scholar

Cited By

View all

Shan JLuo JNi GWu ZDuan W(2016)CVSNeurocomputing10.1016/j.neucom.2016.01.072194:C(107-116)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1016/j.neucom.2016.01.072
Kangarlou AShete SStrunk JSchindler JZadok E(2015)ChronicleProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750508(345-358)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750508
Liu WThirumuruganathan SZhang NDas G(2014)Aggregate estimation over dynamic hidden web databasesProceedings of the VLDB Endowment10.14778/2732977.27329857:12(1107-1118)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.14778/2732977.2732985
Show More Cited By

Index Terms

Synopsis data structures for massive data sets

Recommendations

A Spark-Based Big Data Platform for Massive Remote Sensing Data Processing
ICDS 2015: Proceedings of the Second International Conference on Data Science - Volume 9208

With the fast development of remote sensing techniques, the volume of acquired data grows exponentially. This brings a big challenge to process massive remote sensing data. In the paper, an in-memory computing framework is proposed to address this ...
Theoretical analysis of constructing wavelet synopsis on partitioned data sets

Currently, the size of data becomes much larger and the distributed data processing is getting very important to manage the huge size of data. The MapReduce well known as Google's data processing environment is the most popular distributed platform with ...
Mining structures from massive text data: will it help software engineering?
ASE '17: Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering

The real-world big data are largely unstructured, interconnected text data. One of the grand challenges is to turn such massive unstructured text data into structured, actionable knowledge. We propose a text mining approach that requires only distant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '99: Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms

January 1999

992 pages

ISBN:0898714346

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 1999

Check for updates

Qualifiers

Article

Conference

SODA99

Sponsor:

SIGACT
SIAM

SODA99: 1999 10th Conference on Discrete Algorithms

January 17 - 19, 1999

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
142
Total Downloads

Downloads (Last 12 months)58
Downloads (Last 6 weeks)8

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Shan JLuo JNi GWu ZDuan W(2016)CVSNeurocomputing10.1016/j.neucom.2016.01.072194:C(107-116)Online publication date: 19-Jun-2016
https://dl.acm.org/doi/10.1016/j.neucom.2016.01.072
Kangarlou AShete SStrunk JSchindler JZadok E(2015)ChronicleProceedings of the 13th USENIX Conference on File and Storage Technologies10.5555/2750482.2750508(345-358)Online publication date: 16-Feb-2015
https://dl.acm.org/doi/10.5555/2750482.2750508
Liu WThirumuruganathan SZhang NDas G(2014)Aggregate estimation over dynamic hidden web databasesProceedings of the VLDB Endowment10.14778/2732977.27329857:12(1107-1118)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.14778/2732977.2732985
Batu TFortnow LRubinfeld RSmith WWhite P(2013)Testing Closeness of Discrete DistributionsJournal of the ACM10.1145/2432622.243262660:1(1-25)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1145/2432622.2432626
Madani OConnor MGreiner W(2009)Learning When Concepts AboundThe Journal of Machine Learning Research10.5555/1577069.175587210(2571-2613)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.5555/1577069.1755872
George BKang JShekhar S(2009)Spatio-Temporal Sensor Graphs (STSG): A data model for the discovery of spatio-temporal patternsIntelligent Data Analysis10.5555/1551768.155177313:3(457-475)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.5555/1551768.1551773
Karras P(2009)Optimality and scalability in lattice histogram constructionProceedings of the VLDB Endowment10.14778/1687627.16877032:1(670-681)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.14778/1687627.1687703
Woodruff D(2009)The average-case complexity of counting distinct elementsProceedings of the 12th International Conference on Database Theory10.1145/1514894.1514928(284-295)Online publication date: 23-Mar-2009
https://dl.acm.org/doi/10.1145/1514894.1514928
Li HLee S(2009)Mining frequent itemsets over data streams using efficient window sliding techniquesExpert Systems with Applications: An International Journal10.1016/j.eswa.2007.11.06136:2(1466-1477)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.eswa.2007.11.061
Karras PMamoulis N(2008)Hierarchical synopses with optimal error guaranteesACM Transactions on Database Systems10.1145/1386118.138612433:3(1-53)Online publication date: 3-Sep-2008
https://dl.acm.org/doi/10.1145/1386118.1386124
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A Spark-Based Big Data Platform for Massive Remote Sensing Data Processing

Theoretical analysis of constructing wavelet synopsis on partitioned data sets

Mining structures from massive text data: will it help software engineering?