{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T02:54:43Z","timestamp":1792032883032,"version":"4.4.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>\n            Effective support for XML query languages is becoming increasingly important with the emergence of new applications that access large volumes of XML data. All existing proposals for querying XML (e.g., XQuery) rely on a pattern-specification language that allows (1)\n            <jats:italic>path navigation and branching through the label structure<\/jats:italic>\n            of the XML data graph, and (2)\n            <jats:italic>predicates on the values<\/jats:italic>\n            of specific path\/branch nodes, in order to reach the desired data elements. Clearly, optimizing such queries requires approximating the result cardinality of the referenced paths and hence hinges on the existence of concise synopsis structures that enable accurate compile-time selectivity estimates for complex path expressions over the base XML data. In this article, we introduce a novel approach to building and using statistical summaries of large XML data graphs for effective path-expression selectivity estimation. Our proposed graph-synopsis model (termed XSketch) exploits\n            <jats:italic>localized graph stability<\/jats:italic>\n            and\n            <jats:italic>value-distribution summaries<\/jats:italic>\n            (e.g., histograms) to accurately approximate (in limited space) the path and branching distribution, as well as the complex correlation patterns that can exist between and across path structure and element values in the data graph. To the best of our knowledge, ours is the first work to address this timely problem in the most general setting of graph-structured XML data with values, and complex (branching) path expressions.\n          <\/jats:p>","DOI":"10.1145\/1166074.1166082","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"1014-1063","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["XSKETCH synopses for XML data graphs"],"prefix":"10.1145","volume":"31","author":[{"given":"Neoklis","family":"Polyzotis","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minos","family":"Garofalakis","sequence":"additional","affiliation":[{"name":"Intel Research Berkeley, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases.]]","author":"Aboulnaga A.","unstructured":"Aboulnaga , A. , Alameldeen , A. R. , and Naughton , J. F . 2001. Estimating the Selectivity of XML Path Expressions for Internet Scale Applications . In Proceedings of the 27th International Conference on Very Large Data Bases.]] Aboulnaga, A., Alameldeen, A. R., and Naughton, J. F. 2001. Estimating the Selectivity of XML Path Expressions for Internet Scale Applications. In Proceedings of the 27th International Conference on Very Large Data Bases.]]"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956930"},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the 26th International Conference on Very Large Data Bases. 53--64","author":"Altinel M.","unstructured":"Altinel , M. and Franklin , M. J . 2000. Efficient filtering of XML documents for selective dissemination of information . In Proceedings of the 26th International Conference on Very Large Data Bases. 53--64 .]] Altinel, M. and Franklin, M. J. 2000. Efficient filtering of XML documents for selective dissemination of information. In Proceedings of the 26th International Conference on Very Large Data Bases. 53--64.]]"},{"key":"e_1_2_2_4_1","unstructured":"Boag S. Chamberlin D. Fernndez M. F. Florescu D. Robie J. and Simon J. 2005. XQuery 1.0: An XML query language. W3C Candidate Recommendation. Go online to www.w3.org.]]  Boag S. Chamberlin D. Fernndez M. F. Florescu D. Robie J. and Simon J. 2005. XQuery 1.0: An XML query language. W3C Candidate Recommendation. Go online to www.w3.org.]]"},{"key":"e_1_2_2_5_1","unstructured":"Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible Markup Language (XML) 1.0 (second edition). W3C Recommendation. Go online to www.w3.org\/.]]  Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible Markup Language (XML) 1.0 (second edition). W3C Recommendation. Go online to www.w3.org\/.]]"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233368"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_2_8_1","volume-title":"Proceedings of the 17th International Conference on Data Engineering. 595--604","author":"Chen Z.","unstructured":"Chen , Z. , Jagadish , H. V. , Korn , F. , Koudas , N. , Muthukrishnan , S. , Ng , R. , and Srivastava , D . 2001. Counting twig matches in a tree . In Proceedings of the 17th International Conference on Data Engineering. 595--604 .]] Chen, Z., Jagadish, H. V., Korn, F., Koudas, N., Muthukrishnan, S., Ng, R., and Srivastava, D. 2001. Counting twig matches in a tree. In Proceedings of the 17th International Conference on Data Engineering. 595--604.]]"},{"key":"e_1_2_2_9_1","unstructured":"Clark J. 1999. XSL Transformations (XSLT) Version 1.0. W3C Recommendation. Go online to www.w3.org.]]  Clark J. 1999. XSL Transformations (XSLT) Version 1.0. W3C Recommendation. Go online to www.w3.org.]]"},{"key":"e_1_2_2_10_1","unstructured":"Clark J. and DeRose S. 1999. XML path language (XPath) version 1.0. W3C Recommendation. Go online to www.w3.org.]]  Clark J. and DeRose S. 1999. XML path language (XPath) version 1.0. W3C Recommendation. Go online to www.w3.org.]]"},{"key":"e_1_2_2_11_1","unstructured":"DeRose S. Maler E. and Orchard D. 2001. XML linking language (XLink) version 1.0. W3C Recommendation. Go online to www.w3.org.]]  DeRose S. Maler E. and Orchard D. 2001. XML linking language (XLink) version 1.0. W3C Recommendation. Go online to www.w3.org.]]"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375685"},{"key":"e_1_2_2_13_1","volume-title":"An Introduction to Probability Theory and its Applications---Volume I","author":"Feller W.","unstructured":"Feller , W. 1968. An Introduction to Probability Theory and its Applications---Volume I , John Wiley & Sons , New York, NY .]] Feller, W. 1968. An Introduction to Probability Theory and its Applications---Volume I, John Wiley & Sons, New York, NY.]]"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_2_15_1","first-page":"211","article-title":"Discrete Optimization Via Marginal Analysis. Manage","volume":"13","author":"Fox B.","year":"1966","unstructured":"Fox , B. 1966 . Discrete Optimization Via Marginal Analysis. Manage . Sci. 13 , 3, 211 -- 216 .]] Fox, B. 1966. Discrete Optimization Via Marginal Analysis. Manage. Sci. 13, 3, 211--216.]]","journal-title":"Sci."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564713"},{"key":"e_1_2_2_17_1","volume-title":"Proceedings of the 27th International Conference on Very Large Data Bases.]]","author":"Garofalakis M. N.","unstructured":"Garofalakis , M. N. and Gibbons , P . 2001. Approximate Query processing: Taming the terabytes . In Proceedings of the 27th International Conference on Very Large Data Bases.]] Garofalakis, M. N. and Gibbons, P. 2001. Approximate Query processing: Taming the terabytes. In Proceedings of the 27th International Conference on Very Large Data Bases.]]"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672351"},{"key":"e_1_2_2_19_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases.]]","author":"Goldman R.","unstructured":"Goldman , R. and Widom , J . 1997. DataGuides: Enabling query formulation and optimization in semistructured databases . In Proceedings of the 23rd International Conference on Very Large Data Bases.]] Goldman, R. and Widom, J. 1997. DataGuides: Enabling query formulation and optimization in semistructured databases. In Proceedings of the 23rd International Conference on Very Large Data Bases.]]"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases.]]","author":"Jagadish H.","unstructured":"Jagadish , H. , Koudas , N. , Muthukrishnan , S. , Poosala , V. , Sevcik , K. C. , and Suel , T . 1998. Optimal histograms with quality guarantees . In Proceedings of the 24th International Conference on Very Large Data Bases.]] Jagadish, H., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K. C., and Suel, T. 1998. Optimal histograms with quality guarantees. In Proceedings of the 24th International Conference on Very Large Data Bases.]]"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-002-0081-x"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564707"},{"key":"e_1_2_2_24_1","volume-title":"Proceedings of the 18th International Conference on Data Engineering. 129--140","author":"Kaushik R.","unstructured":"Kaushik , R. , Shenoy , P. , Bohannon , P. , and Gudes , E . 2002b. Exploiting local similarity for efficient indexing of paths in graph structured data . In Proceedings of the 18th International Conference on Data Engineering. 129--140 .]] Kaushik, R., Shenoy, P., Bohannon, P., and Gudes, E. 2002b. Exploiting local similarity for efficient indexing of paths in graph structured data. In Proceedings of the 18th International Conference on Data Engineering. 129--140.]]"},{"key":"e_1_2_2_25_1","volume-title":"Proceedings of the 28th International Conference on Very Large Data Bases. 442--453","author":"Lim L.","unstructured":"Lim , L. , Wang , M. , Padmanabhan , S. , Vitter , J. , and Parr , R . 2002. XPathLearner: An on-line self-tuning markov histogram for XML path selectivity estimation . In Proceedings of the 28th International Conference on Very Large Data Bases. 442--453 .]] Lim, L., Wang, M., Padmanabhan, S., Vitter, J., and Parr, R. 2002. XPathLearner: An on-line self-tuning markov histogram for XML path selectivity estimation. In Proceedings of the 28th International Conference on Very Large Data Bases. 442--453.]]"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of the 7th International Conference on Database Theory (ICDT'99)","author":"Milo T.","unstructured":"Milo , T. and Suciu , D . 1999. Index structures for path expressions . In Proceedings of the 7th International Conference on Database Theory (ICDT'99) . 277--295.]] Milo, T. and Suciu, D. 1999. Index structures for path expressions. In Proceedings of the 7th International Conference on Database Theory (ICDT'99). 277--295.]]"},{"key":"e_1_2_2_28_1","first-page":"2","article-title":"The niagara internet query system","volume":"24","author":"Naughton J. F.","year":"2001","unstructured":"Naughton , J. F. , DeWitt , D. J. , and 2001 . The niagara internet query system . IEEE Data Eng. Bull. 24 , 2 .]] Naughton, J. F., DeWitt, D. J., and et al 2001. The niagara internet query system. IEEE Data Eng. Bull. 24, 2.]]","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216062"},{"key":"e_1_2_2_30_1","volume-title":"Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann","author":"Pearl J.","unstructured":"Pearl , J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann , San Francisco, CA .]] Pearl, J. 1988. Probabilistic reasoning in intelligent systems: Networks of plausible inference. Morgan Kaufmann, San Francisco, CA.]]"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.175"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007599"},{"key":"e_1_2_2_33_1","volume-title":"Proceedings of the 20th International Conference on Data Engineering. 264--275","author":"Polyzotis N.","unstructured":"Polyzotis , N. , Garofalakis , M. , and Ioannidis , Y . 2004b. Selectivity estimation for XML twigs . In Proceedings of the 20th International Conference on Data Engineering. 264--275 .]] Polyzotis, N., Garofalakis, M., and Ioannidis, Y. 2004b. Selectivity estimation for XML twigs. In Proceedings of the 20th International Conference on Data Engineering. 264--275.]]"},{"key":"e_1_2_2_34_1","volume-title":"Proceedings of the 23rd International Conference on Very Large Data Bases. 486--495","author":"Poosala V.","unstructured":"Poosala , V. and Ioannidis , Y. E . 1997. Selectivity estimation without the attribute value independence assumption . In Proceedings of the 23rd International Conference on Very Large Data Bases. 486--495 .]] Poosala, V. and Ioannidis, Y. E. 1997. Selectivity estimation without the attribute value independence assumption. In Proceedings of the 23rd International Conference on Very Large Data Bases. 486--495.]]"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233342"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.75"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304199"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872777"},{"key":"e_1_2_2_39_1","volume-title":"Proceedings of the 30th International Conference on Very Large Data Bases. 240--251","author":"Wang W.","unstructured":"Wang , W. , Jiang , H. , Lu , H. , and Yu , J. X . 2004. Bloom histogram: Path selectivity estimation for XML data with updates . In Proceedings of the 30th International Conference on Very Large Data Bases. 240--251 .]] Wang, W., Jiang, H., Lu, H., and Yu, J. X. 2004. Bloom histogram: Path selectivity estimation for XML data with updates. In Proceedings of the 30th International Conference on Very Large Data Bases. 240--251.]]"},{"key":"e_1_2_2_40_1","volume-title":"Proceedings of the 8th International Conference on Extending Database Technology (EDBT '02)","author":"Wu Y.","unstructured":"Wu , Y. , Patel , J. M. , and Jagadish , H . 2002. Estimating answer sizes for XML queries . In Proceedings of the 8th International Conference on Extending Database Technology (EDBT '02) . 590--608.]] Wu, Y., Patel, J. M., and Jagadish, H. 2002. Estimating answer sizes for XML queries. In Proceedings of the 8th International Conference on Extending Database Technology (EDBT '02). 590--608.]]"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the 19th International Conference on Data Engineering. 443--454","author":"Wu Y.","unstructured":"Wu , Y. , Patel , J. M. , and Jagadish , H . 2003. Structural join order selection for XML query optimization . In Proceedings of the 19th International Conference on Data Engineering. 443--454 .]] Wu, Y., Patel, J. M., and Jagadish, H. 2003. Structural join order selection for XML query optimization. In Proceedings of the 19th International Conference on Data Engineering. 443--454.]]"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.178"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1166074.1166082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:20:20Z","timestamp":1672262420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1166074.1166082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1166074.1166082"],"URL":"https:\/\/doi.org\/10.1145\/1166074.1166082","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}