{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:04:54Z","timestamp":1754157894751,"version":"3.41.2"},"reference-count":27,"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 Extensible Markup Language (XML) data partitioning schemes that can cope with static and dynamic allocation for parallel holistic twig joins: grid metadata model for XML (GMX) and streams\u2010based partitioning method for XML (SPX).<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>GMX exploits the relationships between XML documents and query patterns to perform workload\u2010aware partitioning of XML data. Specifically, the paper constructs a two\u2010dimensional model with a document dimension and a query dimension in which each object in a dimension is composed from XML metadata related to the dimension. GMX provides a set of XML data partitioning methods that include document clustering, query clustering, document\u2010based refinement, query\u2010based refinement, and query\u2010path refinement, thereby enabling XML data partitioning based on the static information of XML metadata. In contrast, SPX explores the structural relationships of query elements and a range\u2010containment property of XML streams to generate partitions and allocate them to cluster nodes on\u2010the\u2010fly.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>GMX provides several salient features: a set of partition granularities that balance workloads of query processing costs among cluster nodes statically; inter\u2010query parallelism as well as intra\u2010query parallelism at multiple extents; and better parallel query performance when all estimated queries are executed simultaneously to meet their probability of query occurrences in the system. SPX also offers the following features: minimal computation time to generate partitions; balancing skewed workloads dynamically on the system; producing higher intra\u2010query parallelism; and gaining better parallel query performance.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Research limitations\/implications<\/jats:title><jats:p>The current status of the proposed XML data partitioning schemes does not take into account XML data updates, e.g. new XML documents and query pattern changes submitted by users on the system.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Practical implications<\/jats:title><jats:p>Note that effectiveness of the XML data partitioning schemes mainly relies on the accuracy of the cost model to estimate query processing costs. The cost model must be adjusted to reflect characteristics of a system platform used in the implementation.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>This paper proposes novel schemes of conducting XML data partitioning to achieve both static and dynamic workload balance.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17440080910968445","type":"journal-article","created":{"date-parts":[[2009,6,6]],"date-time":"2009-06-06T07:08:39Z","timestamp":1244272119000},"page":"151-194","source":"Crossref","is-referenced-by-count":3,"title":["XML data partitioning schemes for parallel holistic twig joins"],"prefix":"10.1108","volume":"5","author":[{"given":"Imam","family":"Machdi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiyuki","family":"Amagasa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroyuki","family":"Kitagawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","reference":[{"key":"key2022012720021080400_b1","unstructured":"Al\u2010Khalifa, S., Jagadish, H.V., Patel, J.M., Wu, Y., Koudas, N. and Srivastava, D. (2002), \u201cStructural joins: a primitive for efficient XML query pattern matching\u201d, Proceedings of the 18th International Conference on Data Engineering (ICDE), San Jose, CA, February 26\u2010March 1, IEEE Computer Society, Washington, DC, pp. 141\u201052."},{"key":"key2022012720021080400_b2","doi-asserted-by":"crossref","unstructured":"Amagasa, T., Kido, K. and Kitagawa, H. (2007), \u201cQuerying XML data using PC cluster system\u201d, Proceedings of the 18th International Conference on Database and Expert Systems Applications (DEXA), Regensburg, September 3\u20107, IEEE Computer Society, Washington, DC, pp. 5\u20109.","DOI":"10.1109\/DEXA.2007.108"},{"key":"key2022012720021080400_b3","doi-asserted-by":"crossref","unstructured":"Bonifati, A. and Cuzzocrea, A. (2007), \u201cEfficient fragmentation of large XML documents\u201d, Proceedings of the 18th International Conference on Database and Expert Systems Applications (DEXA), Regensburg, September 3\u20107, IEEE Computer Society, Washington, DC, pp. 539\u201050.","DOI":"10.1007\/978-3-540-74469-6_53"},{"key":"key2022012720021080400_b4","unstructured":"Bremer, J.\u2010M. and Gertz, M. (2003), \u201cOn distributing XML repositories\u201d, Proceedings of the International Workshop on Web and Databases, San Diego, CA, June 12\u201013, pp. 73\u20108."},{"key":"key2022012720021080400_b5","doi-asserted-by":"crossref","unstructured":"Bruno, N., Koudas, N. and Srivastava, D. (2002), \u201cHolistic twig joins: optimal XML pattern matching\u201d, Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, WI, June 3\u20106, ACM, New York, NY, pp. 310\u201021.","DOI":"10.1145\/564691.564727"},{"key":"key2022012720021080400_b6","unstructured":"Chen, S., Li, H\u2010G., Tatemura, J., Agrawal, D. and Candan, K.S. (2006), \u201cTwig2Stack: bottom\u2010up processing of generalized\u2010tree\u2010pattern queries over XML documents\u201d, Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), Seoul, September 12\u201015, VLDB Endowment, Berlin, pp. 283\u201094."},{"key":"key2022012720021080400_b7","doi-asserted-by":"crossref","unstructured":"Chen, T., Lu, J. and Ling, T.W. (2005), \u201cOn boosting holism in XML twig pattern matching using structural indexing techniques\u201d, Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, MD, June 14\u201016, ACM, New York, NY, pp. 455\u201066.","DOI":"10.1145\/1066157.1066209"},{"key":"key2022012720021080400_b8","unstructured":"Goldman, R. and Widom, J. (1997), \u201cDataguides: enabling query formulation and optimization in semistructured databases\u201d, Proceedings of 23rd International Conference on Very Large Data Bases (VLDB), Athens, August 25\u201029, Morgan Kaufmann, San Francisco, CA, pp. 436\u201045."},{"key":"key2022012720021080400_b9","doi-asserted-by":"crossref","unstructured":"Gou, G. and Chirkova, R. (2007), \u201cEfficiently querying large XML data repositories: a survey\u201d, IEEE Transactions on Knowledge and Data Engineering, Vol. 19 No. 10, pp. 1381\u2010403.","DOI":"10.1109\/TKDE.2007.1060"},{"key":"key2022012720021080400_b10","unstructured":"Hockney, R. and Berry, M. (1994), \u201cPublic international benchmarks for parallel computers: PARKBENCH committee\u201d, Technical Report Report\u20101, PARKBENCH Committee, available at: www.netlib.org\/parkbench\/parkbench.ps (accessed June 2008)."},{"key":"key2022012720021080400_b11","doi-asserted-by":"crossref","unstructured":"Kaushik, R., Krishnamurthy, R., Naughton, J.F. and Ramakrishnan, R. (2004), \u201cOn the integration of structure indexes and inverted lists\u201d, Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, June 13\u201018, ACM, New York, NY, pp. 779\u201090.","DOI":"10.1145\/1007568.1007656"},{"key":"key2022012720021080400_b12","doi-asserted-by":"crossref","unstructured":"Kido, K., Amagasa, T. and Kitagawa, H. (2006), \u201cProcessing XPath queries in PC\u2010clusters using XML data partitioning\u201d, Proceedings of the 22nd International Conference on Data Engineering Workshops, Atlanta, GA, April 3\u20107, IEEE Computer Society, Washington, DC, pp. 114\u20109.","DOI":"10.1109\/ICDEW.2006.120"},{"key":"key2022012720021080400_b13","doi-asserted-by":"crossref","unstructured":"Kurita, H., Hatano, K., Miyazaki, J. and Uemura, S. (2007), \u201cEfficient query processing for large XML data in distributed environments\u201d, Proceedings of the 21st International Conference on Advanced Networking and Applications (AINA), Niagara Falls, May 21\u201023, IEEE Computer Society, Washington, DC, pp. 317\u201022.","DOI":"10.1109\/AINA.2007.64"},{"key":"key2022012720021080400_b14","doi-asserted-by":"crossref","unstructured":"Lin, F. and Keller, R. (1987), \u201cThe gradient model load balancing method\u201d, IEEE Transactions on Software Engineering, Vol. 13 No. 1, pp. 32\u20108.","DOI":"10.1109\/TSE.1987.232563"},{"key":"key2022012720021080400_b15","unstructured":"Lu, J., Ling, T.W., Chan, C.\u2010Y. and Chen, T. (2005), \u201cFrom region encoding to extended Dewey: on efficient processing of XML twig pattern matching\u201d, Proceedings of the 31st International Conference on Very Large Data Bases (VLDB), Trondheim, August 30\u2010September 2, VLDB Endowment, Berlin, pp. 193\u2010204."},{"key":"key2022012720021080400_b16","unstructured":"L\u00fc, K., Zhu, Y., Sun, W., Lin, S. and Fan, J. (2002), \u201cParallel processing XML documents\u201d, Proceedings of the 2002 International Database Engineering and Applications Symposium (IDEAS), Edmonton, July 17\u201019, IEEE Computer Society, Washington, DC, pp. 96\u2010105."},{"key":"key2022012720021080400_b19","unstructured":"McHugh, J. and Widom, J. (1999), \u201cQuery optimization for XML\u201d, Proceedings of the 25th International Conference on Very Large Data Bases (VLDB), Athens, September 7\u201010, Morgan Kaufmann, San Francisco, CA, pp. 315\u201026."},{"key":"key2022012720021080400_b17","doi-asserted-by":"crossref","unstructured":"Machdi, I., Amagasa, T. and Kitagawa, H. (2008), \u201cGMX: an XML data partitioning scheme for holistic twig joins\u201d, Proceedings of the 10th International Conference on Information Integration and Web\u2010based Applications and Services (iiWAS), Linz, November 24\u201026, ACM, New York, NY, pp. 137\u201046.","DOI":"10.1145\/1497308.1497338"},{"key":"key2022012720021080400_b18","doi-asserted-by":"crossref","unstructured":"Machdi, I., Amagasa, T. and Kitagawa, H. (2009), \u201cXML data partitioning strategies to improve parallelism in parallel holistic twig joins\u201d, Proceedings of the 3rd International Conference on Ubiquitous Information Management and Communication (ICUIMC), Suwon, January 15\u201016, ACM, New York, NY, pp. 471\u201080.","DOI":"10.1145\/1516241.1516322"},{"key":"key2022012720021080400_b20","doi-asserted-by":"crossref","unstructured":"Muniz, F. and Zaluska, E. (1995), \u201cParallel load\u2010balancing: an extension to the gradient model\u201d, Parallel Computing, Vol. 21 No. 2, pp. 287\u2010301.","DOI":"10.1016\/0167-8191(94)00067-K"},{"key":"key2022012720021080400_b21","doi-asserted-by":"crossref","unstructured":"Qin, L., Yu, J.X. and Ding, B. (2007), \u201cTwigList: make twig pattern matching fast\u201d, Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA), Bangkok, April 9\u201012, Springer, Berlin, pp. 850\u201062.","DOI":"10.1007\/978-3-540-71703-4_70"},{"key":"key2022012720021080400_b22","doi-asserted-by":"crossref","unstructured":"Sakellariou, R. and Gurd, J.R. (1997), \u201cCompile\u2010time minimisation of load imbalance in loop nests\u201d, Proceedings of the 11th International Conference on Supercomputing, Vienna, July 7\u201011, ACM, New York, NY, pp. 277\u201084.","DOI":"10.1145\/263580.263811"},{"key":"key2022012720021080400_b23","unstructured":"Tan, P.\u2010N., Steinbach, M. and Kumar, V. (2006), Introduction to Data Mining, Addison Wesley, Boston, MA."},{"key":"key2022012720021080400_b24","unstructured":"Tang, N., Wang, G., Yu, J.X., Wong, K.\u2010F. and Yu, G. (2005), \u201cWIN: an efficient data placement strategy for parallel XML databases\u201d, Proceedings of the 11th International Conference on Parallel and Distributed System (ICPADS), Fukuoka, July 20\u201022, IEEE Computer Society, Washington, DC, pp. 249\u2010355."},{"key":"key2022012720021080400_b25","doi-asserted-by":"crossref","unstructured":"Wang, H., Park, S., Fan, W. and Yu, P.S. (2003), \u201cViST: a dynamic index method for querying XML data by tree structures\u201d, Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, June 9\u201012, ACM, New York, NY, pp. 110\u201021.","DOI":"10.1145\/872757.872774"},{"key":"key2022012720021080400_b26","doi-asserted-by":"crossref","unstructured":"Watts, J. and Taylor, S. (1998), \u201cA practical approach to dynamic load balancing\u201d, IEEE Transactions on Parallel and Distributed Systems, Vol. 9 No. 3, pp. 235\u201048.","DOI":"10.1109\/71.674316"},{"key":"key2022012720021080400_b27","doi-asserted-by":"crossref","unstructured":"Zhang, C., Naughton, J.F., DeWitt, D.J., Luo, Q. and Lohman, G.M. (2001), \u201cOn supporting containment queries in relational database management systems\u201d, Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, CA, May 21\u201024, ACM, New York, NY, pp. 425\u201036.","DOI":"10.1145\/376284.375722"}],"container-title":["International Journal of Web Information Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/17440080910968445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080910968445\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440080910968445\/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\/151-194\/166621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6,19]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6,19]]}},"alternative-id":["10.1108\/17440080910968445"],"URL":"https:\/\/doi.org\/10.1108\/17440080910968445","relation":{},"ISSN":["1744-0084"],"issn-type":[{"type":"print","value":"1744-0084"}],"subject":[],"published":{"date-parts":[[2009,6,19]]}}}