{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T13:41:56Z","timestamp":1760708516595},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T00:00:00Z","timestamp":1362096000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00453-012-9692-9","type":"journal-article","created":{"date-parts":[[2013,3,1]],"date-time":"2013-03-01T10:12:36Z","timestamp":1362132756000},"page":"741-757","source":"Crossref","is-referenced-by-count":8,"title":["Better Size Estimation for Sparse Matrix Products"],"prefix":"10.1007","volume":"69","author":[{"given":"Rasmus Resen","family":"Amossen","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Campagna","sequence":"additional","affiliation":[]},{"given":"Rasmus","family":"Pagh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,1]]},"reference":[{"key":"9692_CR1","volume-title":"Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data","author":"S. Acharya","year":"1999","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V., Ramaswamy, S.: Join synopses for approximate query answering. In: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. ACM, New York (1999). SIGMOD Rec. 28(2), 275\u2013286"},{"key":"9692_CR2","first-page":"487","volume-title":"Proceedings of 20th International Conference on Very Large Data Bases (VLDB \u201994)","author":"R. Agrawal","year":"1994","unstructured":"Agrawal, R., Srikant, R.: Fast algorithms for mining association rules. In: Proceedings of 20th International Conference on Very Large Data Bases (VLDB \u201994), pp.\u00a0487\u2013499. Morgan Kaufmann, San Mateo (1994)"},{"key":"9692_CR3","isbn-type":"print","volume-title":"The Probabilistic Method","author":"N. Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992). ISBN 0-471-53588-5","ISBN":"http:\/\/id.crossref.org\/isbn\/0471535885"},{"key":"9692_CR4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/1514894.1514909","volume-title":"Proceedings of the 12th International Conference on Database Theory (ICDT\u00a0\u201909)","author":"R.R. Amossen","year":"2009","unstructured":"Amossen, R.R., Pagh, R.: Faster join-projects and sparse matrix multiplications. In: Proceedings of the 12th International Conference on Database Theory (ICDT\u00a0\u201909), pp.\u00a0121\u2013126. ACM, New York (2009)"},{"key":"9692_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-45726-7_1","volume-title":"Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM \u201902)","author":"Z. Bar-Yossef","year":"2002","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kumar, R., Sivakumar, D., Trevisan, L.: Counting distinct elements in a data stream. In: Proceedings of the 6th International Workshop on Randomization and Approximation Techniques (RANDOM \u201902), pp.\u00a01\u201310. Springer, Berlin (2002)"},{"key":"9692_CR6","first-page":"268","volume-title":"Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS \u201900)","author":"M. Charikar","year":"2000","unstructured":"Charikar, M., Chaudhuri, S., Motwani, R., Narasayya, V.R.: Towards estimation error guarantees for distinct values. In: Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS \u201900), pp.\u00a0268\u2013279. ACM, New York (2000)"},{"issue":"3","key":"9692_CR7","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1006\/jcss.1997.1534","volume":"55","author":"E. Cohen","year":"1997","unstructured":"Cohen, E.: Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3), 441\u2013453 (1997)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9692_CR8","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1009716300509","volume":"2","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Structure prediction and computation of sparse matrix products. J. Comb. Optim. 2(4), 307\u2013332 (1998)","journal-title":"J. Comb. Optim."},{"issue":"5","key":"9692_CR9","doi-asserted-by":"crossref","first-page":"1722","DOI":"10.1137\/S0097539795288611","volume":"28","author":"D. Dor","year":"1999","unstructured":"Dor, D., Zwick, U.: Selecting the median. SIAM J. Comput. 28(5), 1722\u20131758 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9692_CR10","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach. 31(3), 538\u2013544 (1984)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9692_CR11","first-page":"259","volume-title":"Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS\u00a0\u201905)","author":"S. Ganguly","year":"2005","unstructured":"Ganguly, S., Garofalakis, M., Kumar, A., Rastogi, R.: Join-distinct aggregate estimation over update streams. In: Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS\u00a0\u201905), pp.\u00a0259\u2013270. ACM, New York (2005)"},{"key":"9692_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/11940128_18","volume-title":"Proceedings of 17th International Symposium on Algorithms and Computation (ISAAC \u201906)","author":"S. Ganguly","year":"2006","unstructured":"Ganguly, S., Saha, B.: On estimating path aggregates over streaming graphs. In: Proceedings of 17th International Symposium on Algorithms and Computation (ISAAC \u201906). Lecture Notes in Computer Science, vol.\u00a04288, pp.\u00a0163\u2013172. Springer, Berlin (2006)"},{"key":"9692_CR13","first-page":"541","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases (VLDB \u201901)","author":"P.B. Gibbons","year":"2001","unstructured":"Gibbons, P.B.: Distinct sampling for highly-accurate answers to distinct values queries and event reports. In: Proceedings of the 27th International Conference on Very Large Data Bases (VLDB \u201901), pp.\u00a0541\u2013550. Morgan Kaufmann, San Mateo (2001). http:\/\/www.vldb.org\/conf\/2001\/P541.pdf"},{"issue":"7","key":"9692_CR14","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1145\/366622.366644","volume":"4","author":"C.A.R. Hoare","year":"1961","unstructured":"Hoare, C.A.R.: Algorithm 65: find. Commun. ACM 4(7), 321\u2013322 (1961)","journal-title":"Commun. ACM"},{"issue":"1","key":"9692_CR15","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1007\/s00453-010-9441-x","volume":"61","author":"A. Lingas","year":"2011","unstructured":"Lingas, A.: A fast output-sensitive algorithm for boolean matrix multiplication. Algorithmica 61(1), 36\u201350 (2011)","journal-title":"Algorithmica"},{"key":"9692_CR16","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995). ISBN 0-521-47465-5","ISBN":"http:\/\/id.crossref.org\/isbn\/0521474655"},{"issue":"1","key":"9692_CR17","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/1077464.1077466","volume":"1","author":"R. Yuster","year":"2005","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms 1(1), 2\u201313 (2005). doi: 10.1145\/1077464.1077466","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9692-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9692-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9692-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:10Z","timestamp":1559137510000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9692-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,1]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["9692"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9692-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,1]]}}}