{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T11:53:11Z","timestamp":1790941991677,"version":"4.1.0"},"reference-count":17,"publisher":"Emerald","issue":"2","license":[{"start":{"date-parts":[[2009,6,19]],"date-time":"2009-06-19T00:00:00Z","timestamp":1245369600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009,6,19]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>The purpose of this paper is to propose efficient algorithms for structural grouping over Extensible Markup Language (XML) data, called TOPOLOGICAL ROLLUP (T\u2010ROLLUP), which are to compute aggregation functions based on XML data with multiple hierarchical levels. They play important roles in the online analytical processing of XML data, called XML\u2010OLAP, with which complex analysis over XML can be performed to discover valuable information from XML.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>Several variations of algorithms are proposed for efficient T\u2010ROLLUP computation. First, two basic algorithms, top\u2010down algorithm (TDA) and bottom\u2010up algorithm (BUA), are presented in which the well\u2010known structural\u2010join algorithms are used. The paper then proposes more efficient algorithms, called single\u2010scan by preorder number and single\u2010scan by postorder number (SSC\u2010Pre\/Post), which are also based on structural joins, but have been modified from the basic algorithms so that multiple levels of grouping are computed with a single scan over node lists. In addition, the paper attempts to adopt the algorithm for parallel execution in multi\u2010core environments.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>Several experiments are conducted with XMark and synthetic XML data to show the effectiveness of the proposed algorithms. The experiments show that proposed algorithms perform much better than the na\u00efve implementation. In particular, the proposed SSC\u2010Pre and SSC\u2010Post perform better than TDA and BUA for all cases. Beyond that, the experiment using the parallel single scan algorithm also shows better performance than the ordinary basic algorithm.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Research limitations\/implications<\/jats:title><jats:p>This paper focuses on the T\u2010ROLLUP operation for XML data analysis. For this reason, other operations related to XML\u2010OLAP, such as CUBE, WINDOWING, and RANKING should also be investigated.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>The paper presents an extended version of one of the award winning papers at iiWAS2008.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17440080910968436","type":"journal-article","created":{"date-parts":[[2009,6,6]],"date-time":"2009-06-06T07:08:38Z","timestamp":1244272118000},"page":"122-150","source":"Crossref","is-referenced-by-count":5,"title":["Algorithms for structure\u2010based grouping in XML\u2010OLAP"],"prefix":"10.1108","volume":"5","author":[{"given":"Chantola","family":"Kit","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toshiyuki","family":"Amagasa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hiroyuki","family":"Kitagawa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"140","reference":[{"key":"key2022031420265414000_b9","unstructured":"Al\u2010Khalifa, S., Jagadish, H., Koudas, N., Patel, J.M., Srivastava, D. and Wu, Y. (2002), \u201cStructural joins: a primitive for efficient XML query pattern matching\u201d, Proceedings of the 18th International Conference on Data Engineering (ICDE 2002), San Jose, CA, pp. 141\u201052."},{"key":"key2022031420265414000_b3","unstructured":"Boag, S., Chamberlin, D., Fen\u00e1ndez, M.F., Florescu, D., Robie, J. and Sim\u00e9on, J. (2007), \u201cXQuery 1.0: An XML Query Language \u2013 world wide web consortium recommendation\u201d, available at: www.w3.org\/TR\/xquery."},{"key":"key2022031420265414000_b7","doi-asserted-by":"crossref","unstructured":"Bordawekar, R. and Lang, C.A. (2005), \u201cAnalytical processing of XML documents: opportunities and challenges\u201d, ACM SIGMOD Record, Vol. 34 No. 2, pp. 27\u201032.","DOI":"10.1145\/1083784.1083790"},{"key":"key2022031420265414000_b1","unstructured":"Bray, T., Paoli, J., Sperberge\u2010McQueen, C.M., Maler, E. and Yergeau, F. (2008), \u201cExtensible Markup Language (XML) 1.0 (fifth edition) \u2013 world wide web consortium proposed recommendation\u201d, available at: www.w3.org\/TR\/xml."},{"key":"key2022031420265414000_b2","unstructured":"Clark, J. and DeRose, S. (1999), \u201cXML Path Language (XPath) Version 1.0 \u2013 world wide web consortium recommendation\u201d, available at: www.w3.org\/TR\/xpath."},{"key":"key2022031420265414000_b5","unstructured":"Fur, N. (2004), \u201cXML information retrieval \u2013 achievement and challenges\u201d, Proceedings of First Twente Data Management Workshop (TDM 2004) on XML Databases and Information Retrieval, Enschede, p. 1."},{"key":"key2022031420265414000_b13","doi-asserted-by":"crossref","unstructured":"Gokhale, C., Gupta, N., Kumar, P., Lakshmanan, L., Ng, R. and Prakash, B. (2007), \u201cComplex group\u2010by queries for XML\u201d, Proceedings of the 23th International Conference on Data Engineering (ICDE 2007), Istanbul, pp. 646\u201055.","DOI":"10.1109\/ICDE.2007.367910"},{"key":"key2022031420265414000_b10","unstructured":"Jensen, M.R., Moller, T.H. and Pedersen, T.B. (2001), \u201cSpecifying OLAP cubes on XML data\u201d, Journal of Intelligent Information Systems, Vol. 17 Nos 2\/3, pp. 101\u201012."},{"key":"key2022031420265414000_b14","doi-asserted-by":"crossref","unstructured":"Kit, C., Amagasa, T. and Kitagawa, H. (2007), \u201cOLAP query processing for XML data in RDBMS\u201d, Proceedings of IEEE International Workshop on Database for Next Generation Research (SWOD), in Conjunction with the 23th International Conference on Data Engineering (ICDE 2007), Istanbul, pp. 7\u201012.","DOI":"10.1109\/SWOD.2007.353190"},{"key":"key2022031420265414000_b8","doi-asserted-by":"crossref","unstructured":"Kit, C., Amagasa, T. and Kitagawa, H. (2008), \u201cAlgorithms for efficient structure\u2010based grouping in XML\u2010OLAP\u201d, Proceedings of the 10th International Conference on Information Integration and Web\u2010based Application & Services (iiWAS 2008), Linz, pp. 170\u20107.","DOI":"10.1145\/1497308.1497343"},{"key":"key2022031420265414000_b6","doi-asserted-by":"crossref","unstructured":"Kotsaki, E. (2002), \u201cStructured information retrieval in XML documents\u201d, Proceedings of ACM Symposium on Applied Computing (SAC 2002), Madrid, pp. 663\u20107.","DOI":"10.1145\/508791.508919"},{"key":"key2022031420265414000_b16","doi-asserted-by":"crossref","unstructured":"Liu, L., Feng, J., Li, G., Qian, Q. and Li, J. (2008), \u201cParallel structural join algorithm on shared\u2010memory multi\u2010core systems\u201d, Proceedings of the Ninth International Conference on Web\u2010age Information Management (WAIM 2008), Zhangjiajie, pp. 70\u20107.","DOI":"10.1109\/WAIM.2008.11"},{"key":"key2022031420265414000_b11","unstructured":"Pedersen, D., Riss, K. and Pedersen, T.B. (2002), \u201cXML\u2010Extended OLAP querying\u201d, Proceedings of the 14th International Conference on Scientific and Statistical Database Management (SSDBM 2002), Edinburgh, pp. 195\u2010206."},{"key":"key2022031420265414000_b17","unstructured":"Schemidt, A. (2003), \u201cXMark \u2013 an XML benchmark project\u201d, Centrum Wiskunde & Informatica (CWI), available at: www.monetdb.cwi.nl\/xml\/."},{"key":"key2022031420265414000_b4","doi-asserted-by":"crossref","unstructured":"Winter, J. and Drobnik, O. (2007), \u201cAn architecture for XML information retrieval in a peer\u2010to\u2010peer environment\u201d, Proceedings of Conference on Information and Knowledge Management, Proceedings of the ACM First Ph.D. Workshop in CIKM, Lisbon, pp. 17\u201024.","DOI":"10.1145\/1316874.1316878"},{"key":"key2022031420265414000_b12","doi-asserted-by":"crossref","unstructured":"Wiwatwattana, N., Jagadish, H., Lakshmanan, L.V. and Srivastava, D. (2007), \u201cX3: a cube operator for XML OLAP\u201d, Proceedings of the 23th International Conference on Data Engineering (ICDE 2007), Istanbul, pp. 916\u201025.","DOI":"10.1109\/ICDE.2007.367937"},{"key":"key2022031420265414000_b15","doi-asserted-by":"crossref","unstructured":"Yoshikawa, M., Amagasa, T., Shimura, T. and Uemura, S. (2001), \u201cXRel: A path\u2010based approach to storage and retrieval of XML documents using relational databases\u201d, ACM Transaction on Internet Technology (TOIT), Vol. 1 No. 1, pp. 110\u201041.","DOI":"10.1145\/383034.383038"}],"container-title":["International Journal of Web Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/17440080910968436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080910968436\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080910968436\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:24:58Z","timestamp":1753403098000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/ijwis\/article\/5\/2\/122-150\/166618"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,19]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6,19]]}},"alternative-id":["10.1108\/17440080910968436"],"URL":"https:\/\/doi.org\/10.1108\/17440080910968436","relation":{},"ISSN":["1744-0084"],"issn-type":[{"value":"1744-0084","type":"print"}],"subject":[],"published":{"date-parts":[[2009,6,19]]}}}