×

Indexing for summary queries, theory and practice. (English) Zbl 1321.68259


MSC:

68P20 Information storage and retrieval of data
68P15 Database theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Afshani, G. S. Brodal, and N. Zeh. 2011. Ordered and unordered top-k range reporting in large data sets. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. · Zbl 1373.68182 · doi:10.1137/1.9781611973082.31
[2] P. K. Agarwal, G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi. 2012. Mergeable summaries. In Proceedings of the ACM Symposium on Principles of Database Systems. · Zbl 1321.68238 · doi:10.1145/2213556.2213562
[3] P. K. Agarwal and J. Erickson. 1999. Geometric range searching and its relatives. In Advances in Discrete and Computational Geometry. American Mathematical Society, 1–56. · Zbl 0916.68031 · doi:10.1090/conm/223/03131
[4] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. 2002. Tracking join and self-join sizes in limited storage. J. Comput. Syst. Sci. 64, 3, 719–747. · Zbl 1051.68136 · doi:10.1006/jcss.2001.1813
[5] N. Alon, Y. Matias, and M. Szegedy. 1999. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58, 1, 137–147. · Zbl 0938.68153 · doi:10.1006/jcss.1997.1545
[6] A. Arasu and G. Manku. 2004. Approximate counts and quantiles over sliding windows. In Proceedings of the ACM Symposium on Principles of Database Systems. · doi:10.1145/1055558.1055598
[7] L. Arge and J. S. Vitter. 2003. Optimal external memory interval management. SIAM J. Comput. 32, 6, 1488–1508. · Zbl 1030.68027 · doi:10.1137/S009753970240481X
[8] R. A. Baeza-Yates and G. H. Gonnet. 1991. Handbook of Algorithms and Data Structures. Addison-Wesley. · Zbl 0719.68001
[9] Z. Bar-Yossef. 2002. The complexity of massive data set computations. Ph.D. Dissertation, University of California at Berkeley.
[10] K. Beyer, P. J. Haas, B. Reinwald, Y. Sismanis, and R. Gemulla. 2007. On synopses for distinct-value estimation under multiset operations. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/1247480.1247504
[11] G. S. Brodal, B. Gfeller, A. G. Jørgensen, and P. Sanders. 2011. Towards optimal range medians. Theor. Comput. Sci. 412, 1, 2588–2601. · Zbl 1220.68052
[12] F. Buccafurri, G. Lax, D. Sacca, L. Pontieri, and D. Rosaci. 2008. Enhancing histograms by tree-like bucket indices. VLDB J. 17, 5, 1041–1061. · doi:10.1007/s00778-007-0050-5
[13] S. Chaudhuri, G. Das, and U. Srivastava. 2004. Effective use of block-level sampling in statistics estimation. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/1007568.1007602
[14] S. Chaudhuri, R. Motwani, and V. Narasayya. 1998. Random sampling for histogram construction: How much is enough? In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/276304.276343
[15] G. Cormode and M. Hadjieleftheriou. 2008. Finding frequent items in data streams. In Proceedings of the International Conference on Very Large Data Bases. · doi:10.14778/1454159.1454225
[16] G. Cormode and S. Muthukrishnan. 2005. An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55, 1, 58–75. · Zbl 1068.68048 · doi:10.1016/j.jalgor.2003.12.001
[17] M. Datar, A. Gionis, P. Indyk, and R. Motwani. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. · Zbl 1008.68039 · doi:10.1137/S0097539701398363
[18] J. Gehrke, F. Korn, and D. Srivastava. 2001. On computing correlated aggregates over continual data streams. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/375663.375665
[19] A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss. 2002. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the International Conference on Very Large Data Bases. · doi:10.1016/B978-155860869-6/50047-0
[20] J. Gray, S. Chaudhuri, A. Bosworth, A. Layman, D. Reichart, M. Venkatrao, F. Pellow, and H. Pirahesh. 1997. Data cube: A relational aggregation operator generalizing group-by, cross-tab, and sub-totals. Data Mining Knowl. Discov. 1, 1, 29–53. · doi:10.1023/A:1009726021843
[21] M. Greenwald and S. Khanna. 2001. Space-efficient online computation of quantile summaries. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/375663.375670
[22] J. Hellerstein, P. Haas, and H. Wang. 1997. Online aggregation. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/253260.253291
[23] Z. Huang, L. Wang, K. Yi, and Y. Liu. 2011. Sampling based algorithms for quantile computation in sensor networks. In Proceedings of the ACM SIGMOD International Conference on Management of Data. · doi:10.1145/1989323.1989401
[24] C. Jermaine, S. Arumugam, A. Pol, and A. Dobra. 2008. Scalable approximate query processing with the dbo engine. ACM Trans. Datab. Syst. 33, 4. · doi:10.1145/1412331.1412335
[25] A. Jørgensen and K. Larsen. 2011. Range selection and median: Tight cell probe lower bounds and adaptive data structures. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. · Zbl 1373.68196
[26] X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. 2007. Selecting stars: The k most representative skyline operator. In Proceedings of the IEEE International Conference on Data Engineering. · doi:10.1109/ICDE.2007.367854
[27] A. McGregor, A. Pavan, S. Tirthapura, and D. P. Woodruff. 2012. Space-efficient estimation of statistics over sub-sampled streams. In Proceedings of the ACM Symposium on Principles of Database Systems. · Zbl 1351.62026 · doi:10.1145/2213556.2213594
[28] A. Metwally, D. Agrawal, and A. Abbadi. 2006. An integrated efficient solution for computing frequent and top-k elements in data streams. ACM Trans. Datab. Syst. 31, 3, 1095–1133. · doi:10.1145/1166074.1166084
[29] J. Misra and D. Gries. 1982. Finding repeated elements. Sci. Comput. Program. 2, 2, 143–152. · Zbl 0497.68041 · doi:10.1016/0167-6423(82)90012-0
[30] J. I. Munro and M. S. Paterson. 1980. Selection and sorting with limited storage. Theor. Comput. Sci. 12, 3, 315–323. · Zbl 0441.68067 · doi:10.1016/0304-3975(80)90061-4
[31] S. Muthukrishnan. 2005. Data Streams: Algorithms and Applications. Foundations and Trends in Theoretical Computer Science. Now Publishers.
[32] H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. · Zbl 1139.68022
[33] N. Shrivastava, C. Buragohain, D. Agrawal, and S. Suri. 2004. Medians and beyond: New aggregation techniques for sensor networks. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04). ACM.
[34] Y. Tao, L. Ding, X. Lin, and J. Pei. 2009. Distance-based representative skyline. In Proceedings of the IEEE International Conference on Data Engineering. · doi:10.1109/ICDE.2009.84
[35] Y. Tao, G. Kollios, J. Considine, F. Li, and Papadias. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the IEEE International Conference on Data Engineering.
[36] V. N. Vapnik and A. Y. Chervonenkis. 1971. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16, 2, 264–280. · Zbl 0247.60005 · doi:10.1137/1116025
[37] J. S. Vitter. 2008. Algorithms and Data Structures for External Memory. Now Publishers. · Zbl 1244.68007
[38] Z. Wei and K. Yi. 2011. Beyond simple aggregates: Indexing for summary queries. In Proceedings of the ACM Symposium on Principles of Database Systems. · doi:10.1145/1989284.1989299
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.