An Efficient Algorithm of XML Twig Pattern Matching Without Merging
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [20]
  • |
  • Related [20]
  • |
  • Cited by [2]
  • | |
  • Comments
    Abstract:

    In an XML database, finding all occurrences of a twig pattern is a core operation for XML query processing. In the past few years, many algorithms, such as Holistic Twig and TJFast, were proposed in theliteratures. However, these algorithms are based on merging, with high computational cost. Recently Twig2Stackalgorithm and TwigList algorithm are proposed to resolve this problem, but they are very complex. Aim at this problem, this paper considers the characteristic that most path expressions have only a few output nodes, and proposes two new algorithms without merging, named TwigNM and TwigNME, which use only a few stacks.Finally, the experimental results show that these algorithms are superior to the previous algorithms, especially for only ancestor-descendant relationship in XPath.

    Reference
    [1] Zhang C, Naughton J, De Witt D, Luo Q, Lohman G. On supporting containment queries in relational database management systems. In: Timos S, ed. Proc. of the 2001 ACM SIGMOD Int’l Conf. on Management of Data. New York: ACM Press, 2001.425?436.
    [2] Li QZ, Moon B. Indexing and querying XML data for regular path expressions. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S,Ramamohanarao K, Snodgrass RT, eds. Proc. of the 27th Int’l Conf. on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 2001. 361?370.
    [3] AI-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu Y. Structural joins: A primitive for efficient XML query pattern matching. In: Agrawal R, Dittrich K, Ngu AHH, eds. Proc. of the 18th Int’l Conf. on Data Engineering. Los Alamitos: IEEE Press,2002. 141?152.
    [4] Wang J, Meng XF, Wang S. Structural join of XML based on range partitioning. Journal of Software, 2004,15(5):720?729 (inChinese with English abstract). http://www.jos.org.cn/1000-9825/15/720.htm
    [5] Bruno N, Koudas N, Srivastava D. Holistic twig joins: Optimal XML pattern matching. In: Franklin MJ, Moon B, Ailamaki A, eds.Proc. of the SIGMOD Int’l Conf. on Management of Data. Madison: ACM Press, 2002. 310?321.
    [6] Jiang H, Lu H, Wang W. XR-Tree: Indexing XML data for efficient structural joins. In: Dayal U, Ramamritham K, eds. Proc. of the 19th Int’l Conf. on Data Engineering (ICDE). Bangalore: IEEE Computer Society, 2003. 253?264.
    [7] Chen T, Lu J, Ling TW. On boosting holism in XML twig pattern matching. In: Ozcan F, ed. Proc. of the 2005 ACM SIGMOD Int’l Conf. on Management of Data. Baltimore: ACM Press, 2005. 455?466.
    [8] Lu J, Chen T, Ling TW. Effcient processing of XML twig patterns with parent child edges: A look-ahead approach. In: Proc. of the ACM Conf. on Information and Knowledge Management (CIKM). Washington: ACM Press, 2004. 533?542.
    [9] Lu J, Ling TW, Chan CY, Chen T. From region encoding to extended dewey: On efficient processing of XML twig patternmatching. In: Bohm KK, Jensen CS, Haas LM, Kersten ML, Larson P, Ooi BC, eds. Proc. of the 31st Int’l Conf. on Very LargeData Bases (VLDB). Trondheim: ACM Press, 2005. 193?204.
    [10] Choi B, Mahoui M, Wood D. On the optimality of holistic algorithms for twig queries. In: Marik V, et al., eds. Proc. of theDatabase and Expext Systems Application (DEXA). LNCS 2736, Berlin: Springer-Verlag, 2003. 28?37.
    [11] Aghili S, Li, HG, Agrawal D, Abbadi AE. Twix: Twig structure and content matching of selective queries using binary labeling. In: Proc. of the first Int’l Conf. on Scalable Information Systems (INFOSCALE). Hong Kong: ACM Press, 2006. 411?420.
    [12] Chen S, Li HG, Tatemura J, Hsiung WP, Agrawal D, Candan KS. Twig2stack: Bottom-Up processing of generalized-tree patternqueries over XML documents. In: Dayal U, Whang KY, Lomet DB, et al., eds. Proc. of the 32nd Int’l Conf. on Very Large Data Bases (VLDB). Seoul: ACM Press, 2006. 283?294.
    [13] Liu Q, Jeffrey XY, Ding BL. TwigList: Make twig pattern matching fast. In: Proc. of the 12th Int’l Conf. on Database Systems for Advances Applications (DASFAA). Bangkok: 2007. 850?862. http://www.se.cuhk.edu.hk/~lqin/files/TwigList.pdf
    [14] Wirth N. Type extensions. ACM Trans. on Programming Languages and Systems, 1988,10(2):204?214.
    [15] Online Computer Library Center. Dewey decimal classification. http://www.oclc.org/dewey/
    [16] Wang W, Jiang HF, Lu HJ, Jeffrey XY. PBiTree coding and efficient processing of containment joins. In: Dayal U, Ramamritham K, Vijayaraman TM, eds. Proc. of the 19th Int’l Conf. on Data Engineering. Los Alamitos: IEEE Press, 2003. 391?402.
    [17]
    [17] Busse R, Carey M, Florescu D, Kersten M, Manolescu I, Schmidt A, Waas F. XMark an XML benchmark project.http://monetdb.cwi.nl/xml/index.html
    [18] University of Washington XML Repository. http://www.cs.washington.edu/research/xmldatasets/ 附中文参考文献:
    [4] 王静,孟小峰,王珊.基于区域划分得XML 结构连接.软件学报,2004,15(5):720?729. http://www.jos.org.cn/1000-9825/15/720.htm
    Comments
    Comments
    分享到微博
    Submit
Get Citation

陶世群,富丽贞.一种高效非归并的XML 小枝模式匹配算法.软件学报,2009,20(4):795-803

Copy
Share
Article Metrics
  • Abstract:4848
  • PDF: 7245
  • HTML: 0
  • Cited by: 0
History
  • Received:July 22,2007
  • Revised:February 04,2008
You are the first2032471Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063