{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T22:32:54Z","timestamp":1743028374330,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":29,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819723027"},{"type":"electronic","value":"9789819723034"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-981-97-2303-4_29","type":"book-chapter","created":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T08:02:03Z","timestamp":1716883323000},"page":"437-451","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["BoundEst: Estimating Join Cardinalities with\u00a0Tight Upper Bounds"],"prefix":"10.1007","author":[{"given":"Jia","family":"Yang","sequence":"first","affiliation":[]},{"given":"Yujie","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Bin","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Xiaochun","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,29]]},"reference":[{"key":"29_CR1","doi-asserted-by":"crossref","unstructured":"Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 739\u2013748. IEEE (2008)","DOI":"10.1109\/FOCS.2008.43"},{"issue":"1","key":"29_CR2","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.datak.2006.01.013","volume":"60","author":"D Birant","year":"2007","unstructured":"Birant, D., Kut, A.: St-DBScan: an algorithm for clustering spatial-temporal data. Data Knowl. Eng. 60(1), 208\u2013221 (2007)","journal-title":"Data Knowl. Eng."},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Bruno, N., Chaudhuri, S., Gravano, L.: Stholes: a multidimensional workload-aware histogram. In: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, pp. 211\u2013222 (2001)","DOI":"10.1145\/375663.375686"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"Cai, W., Balazinska, M., Suciu, D.: Pessimistic cardinality estimation: tighter upper bounds for intermediate join cardinalities. In: Proceedings of the 2019 International Conference on Management of Data, pp. 18\u201335 (2019)","DOI":"10.1145\/3299869.3319894"},{"issue":"2","key":"29_CR5","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1145\/376284.375685","volume":"30","author":"A Deshpande","year":"2001","unstructured":"Deshpande, A., Garofalakis, M., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. ACM SIGMOD Rec. 30(2), 199\u2013210 (2001)","journal-title":"ACM SIGMOD Rec."},{"issue":"9","key":"29_CR6","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.14778\/3329772.3329780","volume":"12","author":"A Dutt","year":"2019","unstructured":"Dutt, A., Wang, C., Nazi, A., Kandula, S., Narasayya, V., Chaudhuri, S.: Selectivity estimation for range predicates using lightweight models. Proc. VLDB Endow. 12(9), 1044\u20131057 (2019)","journal-title":"Proc. VLDB Endow."},{"key":"29_CR7","unstructured":"Gens, R., Pedro, D.: Learning the structure of sum-product networks. In: International Conference on Machine Learning, pp. 873\u2013880. PMLR (2013)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Gunopulos, D., Kollios, G., Tsotras, V.J., Domeniconi, C.: Selectivity estimators for multidimensional range queries over real attributes. VLDB J. 14, 137\u2013154 (2005)","DOI":"10.1007\/s00778-003-0090-4"},{"key":"29_CR9","unstructured":"Han, Y., et\u00a0al.: Cardinality estimation in DBMS: a comprehensive benchmark evaluation. arXiv preprint arXiv:2109.05877 (2021)"},{"key":"29_CR10","doi-asserted-by":"crossref","unstructured":"Hasan, S., Thirumuruganathan, S., Augustine, J., Koudas, N., Das, G.: Deep learning models for selectivity estimation of multi-attribute queries. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, pp. 1035\u20131050 (2020)","DOI":"10.1145\/3318464.3389741"},{"key":"29_CR11","unstructured":"Hertzschuch, A., Hartmann, C., Habich, D., Lehner, W.: Simplicity done right for join ordering. In: CIDR (2021)"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Hilprecht, B., Schmidt, A., Kulessa, M., Molina, A., Kersting, K., Binnig, C.: DeepDB: learn from data, not from queries! arXiv preprint arXiv:1909.00607 (2019)","DOI":"10.14778\/3384345.3384349"},{"key":"29_CR13","unstructured":"Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned cardinalities: estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 (2018)"},{"issue":"6","key":"29_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.066138","volume":"69","author":"A Kraskov","year":"2004","unstructured":"Kraskov, A., St\u00f6gbauer, H., Grassberger, P.: Estimating mutual information. Phys. Rev. E 69(6), 066138 (2004)","journal-title":"Phys. Rev. E"},{"issue":"3","key":"29_CR15","doi-asserted-by":"publisher","first-page":"204","DOI":"10.14778\/2850583.2850594","volume":"9","author":"V Leis","year":"2015","unstructured":"Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proc. VLDB Endow. 9(3), 204\u2013215 (2015)","journal-title":"Proc. VLDB Endow."},{"key":"29_CR16","unstructured":"Leis, V., Radke, B., Gubichev, A., Kemper, A., Neumann, T.: Cardinality estimation done right: index-based join sampling. In: CIDR (2017)"},{"key":"29_CR17","doi-asserted-by":"crossref","unstructured":"Li, F., Wu, B., Yi, K., Zhao, Z.: Wander join: online aggregation via random walks. In: Proceedings of the 2016 International Conference on Management of Data, pp. 615\u2013629 (2016)","DOI":"10.1145\/2882903.2915235"},{"key":"29_CR18","doi-asserted-by":"crossref","unstructured":"Muralikrishna, M., DeWitt, D.J.: Equi-depth multidimensional histograms. In: Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, pp. 28\u201336 (1988)","DOI":"10.1145\/971701.50205"},{"issue":"11","key":"29_CR19","doi-asserted-by":"publisher","first-page":"852","DOI":"10.14778\/3402707.3402724","volume":"4","author":"K Tzoumas","year":"2011","unstructured":"Tzoumas, K., Deshpande, A., Jensen, C.S.: Lightweight graphical models for selectivity estimation without independence assumptions. Proc. VLDB Endow. 4(11), 852\u2013863 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Wu, P., Cong, G.: A unified deep model of learning from both data and queries for cardinality estimation. In: Proceedings of the 2021 International Conference on Management of Data, pp. 2009\u20132022 (2021)","DOI":"10.1145\/3448016.3452830"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Wu, Z., Negi, P., Alizadeh, M., Kraska, T., Madden, S.: FactorJoin: a new cardinality estimation framework for join queries (2023)","DOI":"10.1145\/3588721"},{"key":"29_CR22","unstructured":"Wu, Z., Shaikhha, A., Zhu, R., Zeng, K., Han, Y., Zhou, J.: Bayescard: revitilizing Bayesian frameworks for cardinality estimation. arXiv preprint arXiv:2012.14743 (2020)"},{"key":"29_CR23","unstructured":"Wu, Z., et al.: FSPN: a new class of probabilistic graphical model. arXiv preprint arXiv:2011.09020 (2020)"},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"Yang, Z., et al.: Neurocard: one cardinality estimator for all tables. arXiv preprint arXiv:2006.08109 (2020)","DOI":"10.14778\/3421424.3421432"},{"issue":"2","key":"29_CR25","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/s41019-022-00182-8","volume":"7","author":"P Yi","year":"2022","unstructured":"Yi, P., Li, J., Choi, B., Bhowmick, S.S., Xu, J.: Flag: towards graph query autocompletion for large graphs. Data Sci. Eng. 7(2), 175\u2013191 (2022)","journal-title":"Data Sci. Eng."},{"issue":"3","key":"29_CR26","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1007\/s11280-022-01038-x","volume":"25","author":"H Yin","year":"2022","unstructured":"Yin, H., Gao, H., Wang, B., Li, S., Li, J.: Efficient trajectory compression and range query processing. World Wide Web 25(3), 1259\u20131285 (2022)","journal-title":"World Wide Web"},{"issue":"3","key":"29_CR27","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1007\/s11280-022-01061-y","volume":"26","author":"T Yu","year":"2023","unstructured":"Yu, T., et al.: Zebra: a novel method for optimizing text classification query in overload scenario. World Wide Web 26(3), 905\u2013931 (2023)","journal-title":"World Wide Web"},{"key":"29_CR28","doi-asserted-by":"crossref","unstructured":"Zhao, Z., Christensen, R., Li, F., Hu, X., Yi, K.: Random sampling over joins revisited. In: Proceedings of the 2018 International Conference on Management of Data, pp. 1525\u20131539 (2018)","DOI":"10.1145\/3183713.3183739"},{"key":"29_CR29","unstructured":"Zhu, R., et al.: Flat: fast, lightweight and accurate method for cardinality estimation. arXiv preprint arXiv:2011.09022 (2020)"}],"container-title":["Lecture Notes in Computer Science","Web and Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-2303-4_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T08:07:52Z","timestamp":1716883672000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-2303-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819723027","9789819723034"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-2303-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"29 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"APWeb-WAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Wuhan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 October 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 October 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"apwebwaim2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.apweb-waim2023.com\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}