{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,11]],"date-time":"2025-12-11T20:36:01Z","timestamp":1765485361011,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>This article introduces the Tuple Graph (TuG) synopses, a new class of data summaries that enable accurate approximate answers for complex relational queries. The proposed summarization framework adopts a \u201csemi-structured\u201d view of the relational database, modeling a relational data set as a graph of tuples and join queries as graph traversals, respectively. The key idea is to approximate the structure of the induced data graph in a concise synopsis, and to approximate the answer to a query by performing the corresponding traversal over the summarized graph. We detail the (TuG) synopsis model that is based on this novel approach, and we describe an efficient and scalable construction algorithm for building accurate (TuG) within a specific storage budget. We validate the performance of (TuG) with an extensive experimental study on real-life and synthetic datasets. Our results verify the effectiveness of (TuG) in generating accurate approximate answers for complex join queries, and demonstrate their benefits over existing summarization techniques.<\/jats:p>","DOI":"10.1145\/1508857.1508860","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:14:44Z","timestamp":1240323284000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["TuG synopses for approximate query answering"],"prefix":"10.1145","volume":"34","author":[{"given":"Joshua","family":"Spiegel","sequence":"first","affiliation":[{"name":"BEA Systems, Redwood Shores, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neoklis","family":"Polyzotis","sequence":"additional","affiliation":[{"name":"University of California at Santa Cruz, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304198"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304207"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276314"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_5_1","unstructured":"Anonymous. Details removed due to double-blind reviewing.  Anonymous. Details removed due to double-blind reviewing."},{"volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases, 111--122","author":"Chakrabarti K.","key":"e_1_2_1_6_1","unstructured":"Chakrabarti , K. , Garofalakis , M. , Rastogi , R. , and Shim , K . 2000. Approximate query processing using wavelets . In Proceedings of the 26th International Conference on Very Large Data Bases, 111--122 . Chakrabarti, K., Garofalakis, M., Rastogi, R., and Shim, K. 2000. Approximate query processing using wavelets. In Proceedings of the 26th International Conference on Very Large Data Bases, 111--122."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375685"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564699"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103424"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233340"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375727"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the LinkKDD Workshop at the 10th ACM Conference on KDD.","author":"Gilbert A. C.","year":"2004","unstructured":"Gilbert , A. C. 2004 . Compressing network graphs . In Proceedings of the LinkKDD Workshop at the 10th ACM Conference on KDD. Gilbert, A. C. 2004. Compressing network graphs. In Proceedings of the LinkKDD Workshop at the 10th ACM Conference on KDD."},{"volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99)","author":"Ioannidis Y. E.","key":"e_1_2_1_15_1","unstructured":"Ioannidis , Y. E. and Poosala , V . 1999. Histogram-Based approximation of set-valued query answers . In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99) , 174--185. Ioannidis, Y. E. and Poosala, V. 1999. Histogram-Based approximation of set-valued query answers. In Proceedings of the 25th International Conference on Very Large Data Bases (VLDB'99), 174--185."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90224-H"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007599"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.175"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142497"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.178"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233324"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508860","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1508857.1508860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:42Z","timestamp":1750253382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1508857.1508860"],"URL":"https:\/\/doi.org\/10.1145\/1508857.1508860","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}