{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:05:02Z","timestamp":1754157902788,"version":"3.41.2"},"reference-count":34,"publisher":"Emerald","issue":"2","license":[{"start":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T00:00:00Z","timestamp":1277164800000},"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":[[2010,6,22]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>The purpose of this paper is to propose general parallelism techniques for holistic twig join algorithms to process queries against Extensible Markup Language (XML) databases on a multi\u2010core system.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>The parallelism techniques comprised data and task parallelism. As for data parallelism, the paper adopted the stream\u2010based partitioning for XML to partition XML data as the basis of parallelism on multiple CPU cores. The XML data partitioning was performed in two levels. The first level was to create buckets for creating data independence and balancing loads among CPU cores; each bucket was assigned onto a CPU core. Within each bucket, the second level of XML data partitioning was performed to create finer partitions for providing finer parallelism. Each CPU core performed the holistic twig join algorithm on each finer partition of its own in parallel with other CPU cores. In task parallelism, the holistic twig join algorithm was decomposed into two main tasks, which were pipelined to create parallelism. The first task adopted the data parallelism technique and their outputs were transferred to the second task periodically. Since data transfers incurred overheads, the size of each data transfer needed to be estimated cautiously for achieving optimal performance.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>The data and task parallelism techniques contribute to good performance especially for queries having complex structures and\/or higher values of query selectivity. The performance of data parallelism can be further improved by task parallelism. Significant performance improvement is attained by queries having higher selectivity because more outputs computed by the second task is performed in parallel with the first task.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Research limitations\/implications<\/jats:title><jats:p>The proposed parallelism techniques primarily deals with executing a single long\u2010running query for intra\u2010query parallelism, partitioning XML data on\u2010the\u2010fly, and allocating partitions on CPU cores statically. During the parallel execution, presumably there are no such dynamic XML data updates.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Practical implications<\/jats:title><jats:p>The effectiveness of the proposed parallel holistic twig joins relies fundamentally on some system parameter values that can be obtained from a benchmark of the system platform.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>The paper proposes novel techniques to increase parallelism by combining techniques of data and task parallelism for achieving high performance. To the best of the author's knowledge, this is the first paper of parallelizing the holistic twig join algorithms on a multi\u2010core system.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17440081011053131","type":"journal-article","created":{"date-parts":[[2010,6,26]],"date-time":"2010-06-26T07:30:02Z","timestamp":1277537402000},"page":"149-177","source":"Crossref","is-referenced-by-count":6,"title":["Parallel holistic twig joins on a multi\u2010core system"],"prefix":"10.1108","volume":"6","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":[{"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 '02), IEEE Computer Society, Washington, DC, pp. 141\u201052.","key":"key2022012220074821500_b1"},{"doi-asserted-by":"crossref","unstructured":"Bordawekar, R., Lim, L. and Shmueli, O. (2009), \u201cParallelization of XPath queries using multi\u2010core processors: challenges and experiences\u201d, Proceedings of the International Conference on Extending Database and Technology (EDBT '09), Saint Petersburg, Russia, pp. 180\u201091.","key":"key2022012220074821500_b2","DOI":"10.1145\/1516360.1516382"},{"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, ACM, New York, NY, pp. 310\u201021.","key":"key2022012220074821500_b3","DOI":"10.1145\/564691.564727"},{"unstructured":"Che, D. (2006), \u201cMytwigstack: a holistic twig join algorithm with effective path merging support\u201d, SNPD\u2010SAWN '06: Proceedings of the Seventh ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel\/Distributed Computing, Southern Illinois University, Carbondale, IL.","key":"key2022012220074821500_b4"},{"unstructured":"Chen, S., Ailamaki, A., Gibbons, P.B. and Mowry, T.C. (2004), \u201cImproving hash join performance through prefetching\u201d, Proceedings of the 20th International Conference on Data Engineering (ICDE 2004'), Boston, MA, USA.","key":"key2022012220074821500_b5"},{"unstructured":"Chen, S., Li, H.\u2010G., Tatemura, J., Hsiung, W.\u2010P., Agrawal, D. and Candan, K.S. (2006), \u201cTwig2stack: bottom\u2010up processing of generalized\u2010tree\u2010pattern queries over XML documents\u201d, VLDB '06: Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, September 12\u201015, pp. 283\u201094.","key":"key2022012220074821500_b6"},{"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, SIGMOD '05: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, June 14\u201016, Baltimore, MD.","key":"key2022012220074821500_b7","DOI":"10.1145\/1066157.1066209"},{"doi-asserted-by":"crossref","unstructured":"Ding, J.J., Waheed, A., Yao, J. and Bhuyan, L.N. (2009), \u201cPerformance characterization of multi\u2010thread and multi\u2010core processors based XML application oriented networking systems\u201d, Journal of Parallel and Distributed Computing, Vol. 70 No. 5, pp. 584\u201097.","key":"key2022012220074821500_b8","DOI":"10.1016\/j.jpdc.2009.10.009"},{"doi-asserted-by":"crossref","unstructured":"Gorder, P.F. (2007), \u201cMulticore processors for science and engineering\u201d, Computing in Science and Engineering, Vol. 9 No. 2, pp. 3\u20107.","key":"key2022012220074821500_b9","DOI":"10.1109\/MCSE.2007.35"},{"doi-asserted-by":"crossref","unstructured":"He, B. and Luo, Q. (2006), \u201cCache\u2010oblivious nested\u2010loop joins\u201d, Proceedings of the 2006 ACM Conference on Information and Knowledge Management (CIKM 2006), Arlington, VA, USA, pp. 718\u201027.","key":"key2022012220074821500_b10","DOI":"10.1145\/1183614.1183717"},{"doi-asserted-by":"crossref","unstructured":"Head, M.R. and Govindaraju, M. (2009), \u201cPerformance enhancement with speculative execution based parallelism for processing large\u2010scale XML\u2010based application data\u201d, HPDC '09: Proceedings of the 18th ACM International Symposium on High Performance Distributed Computing, ACM, New York, NY, pp. 21\u201030.","key":"key2022012220074821500_b11","DOI":"10.1145\/1551609.1551615"},{"doi-asserted-by":"crossref","unstructured":"Jiang, Z., Luo, C., Hou, W.\u2010C., Zhu, Q. and Che, D. (2007), \u201cEfficient processing of XML twig pattern: a novel one\u2010phase holistic solution\u201d, Proceedings of the 18th International Conference on Database and Expert Systems Applications, DEXA 2007, Regensburg, September 3\u20107, pp. 87\u201097.","key":"key2022012220074821500_b13","DOI":"10.1007\/978-3-540-74469-6_10"},{"doi-asserted-by":"crossref","unstructured":"Kim, S.M. and Yoo, S.I. (2009), \u201cDom tree browsing of a very large XML document: design and implementation\u201d, Journal of Systems and Software, Vol. 82 No. 11, pp. 1843\u201058.","key":"key2022012220074821500_b14","DOI":"10.1016\/j.jss.2009.05.043"},{"doi-asserted-by":"crossref","unstructured":"Kuntraruk, J., Pottenger, W.M. and Ross, A.M. (2005), \u201cApplication resource requirement estimation in a parallel\u2010pipeline model of execution\u201d, IEEE Transactions on Parallel and Distributed Systems, Vol. 16 No. 12.","key":"key2022012220074821500_b15","DOI":"10.1109\/TPDS.2005.143"},{"doi-asserted-by":"crossref","unstructured":"Li, J. and Wang, J. (2008), \u201cFast matching of twig patterns\u201d, Proceedings of the 19th International Conference on Database and Expert Systems Applications \u2013 DEXA '08), Springer, Berlin, pp. 523\u201036.","key":"key2022012220074821500_b16","DOI":"10.1007\/978-3-540-85654-2_45"},{"doi-asserted-by":"crossref","unstructured":"Li, X., Wang, H., Liu, T. and Li, W. (2009), \u201cKey elements tracing method for parallel XML parsing in multi\u2010core system\u201d, Proceedings of the 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, IEEE Computer Society, Washington, DC, pp. 439\u201044.","key":"key2022012220074821500_b17","DOI":"10.1109\/PDCAT.2009.64"},{"doi-asserted-by":"crossref","unstructured":"Liu, L., Feng, J., 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, Zhangjiajie, pp. 70\u20107.","key":"key2022012220074821500_b18","DOI":"10.1109\/WAIM.2008.11"},{"doi-asserted-by":"crossref","unstructured":"Lu, J., Chen, T. and Ling, T.W. (2004), \u201cEfficient processing of XML twig patterns with parent child edges: a look\u2010ahead approach\u201d, Proceedings of the Thirteenth ACM International Conference on Information and Knowledge Management (CIKM '04), November 8\u201013, Washington, DC, pp. 533\u201042.","key":"key2022012220074821500_b19","DOI":"10.1145\/1031171.1031272"},{"doi-asserted-by":"crossref","unstructured":"Lu, J., Chen, T. and Ling, T.W. (2005), \u201cTJFast: effective processing of XML twig pattern matching\u201d, WWW '05: Special Interest Tracks and Posters of the 14th International Conference on World Wide Web, ACM, New York, NY, pp. 1118\u201019.","key":"key2022012220074821500_b20","DOI":"10.1145\/1062745.1062897"},{"doi-asserted-by":"crossref","unstructured":"Lu, W. and Gannon, D. (2007), \u201cParallel XML processing by work stealing\u201d, Proceedings of the 2007 Workshop on Service\u2010oriented Computing Performance: Aspects, Issues, and Approaches, ACM, New York, NY, pp. 31\u20108.","key":"key2022012220074821500_b22","DOI":"10.1145\/1272457.1272462"},{"doi-asserted-by":"crossref","unstructured":"Lu, W., Chiu, K. and Pan, Y. (2006), \u201cA parallel approach to XML parsing\u201d, GRID '06: Proceedings of the 7th IEEE\/ACM International Conference on Grid Computing, Barcelona, September, pp. 223\u201030.","key":"key2022012220074821500_b21","DOI":"10.1109\/ICGRID.2006.311019"},{"doi-asserted-by":"crossref","unstructured":"Machdi, I., Amagasa, T. and Kitagawa, H. (2009a), \u201cExecuting parallel twigstack algorithm on a multi\u2010core system\u201d, Proceedings of the 11th International Conference on Information Integration and Web\u2010based Applications and Services (iiWAS 2009), Kuala Lumpur, Malaysia, pp. 174\u201082.","key":"key2022012220074821500_b23","DOI":"10.1145\/1806338.1806376"},{"doi-asserted-by":"crossref","unstructured":"Machdi, I., Amagasa, T. and Kitagawa, H. (2009b), \u201cXML data partitioning schemes for parallel holistic twig joins\u201d, International Journal of Web Information Systems, Vol. 5 No. 2, pp. 151\u201094.","key":"key2022012220074821500_b24","DOI":"10.1108\/17440080910968445"},{"doi-asserted-by":"crossref","unstructured":"Machdi, I., Amagasa, T. and Kitagawa, H. (2009c), \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 '09), ACM, New York, NY, pp. 501\u201010.","key":"key2022012220074821500_b25","DOI":"10.1145\/1516241.1516322"},{"doi-asserted-by":"crossref","unstructured":"Mathis, C., Harder, T. and Haustein, M. (2006), \u201cLocking\u2010aware structural join operators for XML query processing\u201d, Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, ACM, New York, NY, pp. 467\u201078.","key":"key2022012220074821500_b26","DOI":"10.1145\/1142473.1142526"},{"doi-asserted-by":"crossref","unstructured":"Pan, Y., Lu, W., Zhang, Y. and Chiu, K. (2007a), \u201cA static load\u2010balancing scheme for parallel XML parsing on multicore CPUs\u201d, Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid (CCGrid '07), IEEE Computer Society, Washington, DC, pp. 351\u201062.","key":"key2022012220074821500_b27","DOI":"10.1109\/CCGRID.2007.14"},{"doi-asserted-by":"crossref","unstructured":"Pan, Y., Zhang, Y., Chiu, K. and Lu, W. (2007b), \u201cParallel XML parsing using meta\u2010DFAs\u201d, E\u2010SCIENCE '07: Proceedings of the Third IEEE International Conference on e\u2010Science and Grid Computing, IEEE Computer Society, Washington, DC, pp. 237\u201044.","key":"key2022012220074821500_b28","DOI":"10.1109\/E-SCIENCE.2007.55"},{"doi-asserted-by":"crossref","unstructured":"Qin, L., Yu, J. and Ding, B. (2007), \u201cTwiglist: make twig pattern matching fast\u201d, Proceedings of the 12th International Conference on Database Systems for Advanced Applications (DASFAA 2007), Springer, Berlin, pp. 850\u201062.","key":"key2022012220074821500_b29","DOI":"10.1007\/978-3-540-71703-4_70"},{"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, Austria, pp. 277\u201084.","key":"key2022012220074821500_b30","DOI":"10.1145\/263580.263811"},{"doi-asserted-by":"crossref","unstructured":"Shah, B., Rao, P.R., Moon, B. and Rajagopalan, M. (2009), \u201cA data parallel algorithm for XML DOM parsing\u201d, XSym '09: Proceedings of the 6th International XML Database Symposium on Database and XML Technologies, Springer\u2010Verlag, Berlin, pp. 75\u201090.","key":"key2022012220074821500_b31","DOI":"10.1007\/978-3-642-03555-5_7"},{"doi-asserted-by":"crossref","unstructured":"Taniar, D., Leung, C.H., Rahayu, W. and Goel, S. (2008), High\u2010Performance Parallel Database Processing and Grid Databases, Wiley, Hoboken, NJ.","key":"key2022012220074821500_b32","DOI":"10.1002\/9780470391365"},{"unstructured":"Waldvogel, M., Kramis, M. and Graf, S. (2008), \u201cDistributing XML with focus on parallel evaluation\u201d, Proceedings Databases, Information Systems and Peer\u2010to\u2010Peer Computing (DBISP2P 2008), Auckland, New Zealand, pp. 55\u201067.","key":"key2022012220074821500_b33"},{"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, ACM, New York, NY, pp. 110\u201021.","key":"key2022012220074821500_b34","DOI":"10.1145\/872757.872774"},{"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, pp. 425\u201036.","key":"key2022012220074821500_b36","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\/17440081011053131","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440081011053131\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17440081011053131\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,25]],"date-time":"2025-07-25T00:25:01Z","timestamp":1753403101000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/ijwis\/article\/6\/2\/149-177\/166457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,22]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,6,22]]}},"alternative-id":["10.1108\/17440081011053131"],"URL":"https:\/\/doi.org\/10.1108\/17440081011053131","relation":{},"ISSN":["1744-0084"],"issn-type":[{"type":"print","value":"1744-0084"}],"subject":[],"published":{"date-parts":[[2010,6,22]]}}}