A survey on tree matching and XML retrieval. (English) Zbl 1295.68109

The paper provides a useful survey of techniques for XML retrieval. The value of the paper is twofold. First, it is time to seriously summarize results achieved in XML retrieval during the more than 15 years of the existence of the XML data model. Second, the authors analyze these results from the point of view of graph theory that provides a theoretical umbrella for both XML query languages and algorithms used for query evaluation. The paper is divided into six sections. Section 2 presents some important concepts and background concerning the XML data model and two categories of XML retrieval: querying semi-structured data and structured text retrieval. The former includes basic XML query languages (XPath, XQuery), the latter uses a method known from information retrieval. Section 2 also introduces some XML query languages belonging to both retrieval categories. A possibility to integrate the functionalities of both these categories is offered by the language XQuery Full-text, which extends the XQuery language to full-text search. Section 3 lists the best known algorithms for exact and approximate tree matching. The latter is of special importance for practical querying of XML data. The authors discuss three main groups of algorithms for tree matching: tree edit distance approaches, tree inclusion and the tree alignment distance. Section 3 summarizes the most important approximate ordered tree matching algorithms and their complexities in a table. The authors emphasize that a lot of these algorithms assume the data to be processed in main memory which is not often possible in real XML databases. Approaches for XML retrieval using the tree matching algorithms described in Section 3 are presented in Section 4, which represents the core of the paper. Its first part covers the exact algorithms for finding all twig patterns in an XML database. The second part describes and illustrates in detail the approximate algorithms including their variants and improvements. All XML approaches are classified into different categories and summarized in tables. Evaluation methods of these approaches are exposed in the rather confusing Section 5. Finally, a discussion about future research directions is presented in Section 6.
The approaches described in the paper use the tree representation of documents and queries, but do not use state-of-the art algorithms for tree matching. It seems that a deeper collaboration between the IR community and researchers developing new XML query languages would be beneficial. Although the development of new XML query languages was not so intensive in the last years, the paper offers a challenge for their further development.


68P20 Information storage and retrieval of data
68P05 Data structures
68P15 Database theory
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI HAL


[1] W3C, EXtensible Markup Language (XML) 1.0, Tech. Rep., World Wide Web Consortium (W3C), Recommendation, February 1998.
[2] W3C XML Web page. http://www.w3.org/XML/.
[3] M. Lalmas, R. Baeza-Yates, In: R. Baeza-Yates, B. Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Professional, 2 edition (February 10, 2011), Ch. Structured Text Retrieval.
[4] W3C, DOM level 1 (Document Object Model), Tech. Rep., World Wide Web Consortium (W3C), Recommendation, October 1998.
[5] Lalmas, M., XML retrieval, synthesis lectures on information concepts, retrieval, and services, (2009), Morgan & Claypool Publishers
[6] Tekli, J.; Chbeir, R.; Yétongnon, K., An overview on XML similarity: background, current trends and future directions, Comput. Sci. Rev., 3, 3, 151-173, (2009) · Zbl 1300.68024
[7] (Liu, L.; Özsu, M. T., Encyclopedia of Database Systems, (2009), Springer US) · Zbl 1183.68252
[8] Lalmas, M.; Baeza-Yates, R., Structured document retrieval, (Encyclopedia of Database Systems, (2009), Springer), 2867-2868
[9] Kazai, G.; Govert, N.; Lalmas, M.; Fuhr, N., The INEX evaluation initiative, (Intelligent Search on XML data, Applications, Languages, Models, Implementations and Benchmarks, (2003), Springer), 279-293
[10] Trotman, A., Processing structural constraints, (Encyclopedia of Database Systems, (2009), Springer), 2191-2195
[11] Amer-Yahia, S.; Lalmas, M., XML search: languages, INEX and scoring, ACM SIGMOD Rec., 35, 4, 16-23, (2006)
[12] W3C, XML Path Language (XPath) 2.0, Tech. Rep., World Wide Web Consortium (W3C), Recommendation, January 2007.
[13] Trotman, A.; Sigurbjornsson, B., Narrowed extended xpath I (NEXI), (Proceedings of the 3rd Workshop of the Initiative for the Evaluation of XML retrieval (INEX), (2004)), 16-40
[14] Campi, A.; Damiani, E.; Guinea, S.; Marrara, S.; Pasi, G.; Spoletini, P., A fuzzy extension of the xpath query language, Journal of Intelligent Information Systems, 33, 3, 285-305, (2009)
[15] W3C, XQuery 1.0 : An XML query language, Tech. Rep., World Wide Web Consortium (W3C), Recommendation, January 2007.
[16] W3C, XQuery 1.0 and XPath 2.0 Full-Text 1.0, Tech. Rep., World Wide Web Consortium (W3C), Note, January 2011.
[17] Zhang, C.; Naughton, J.; Dewitt, D.; Luo, Q.; Lohman, G., On supporting containment queries in relational database management systems, (Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, (2001), Santa Barbara California, USA), 425-426
[18] Al-Khalifa, S.; Jagadish, H.; Koudas, N.; Patel, J.; Srivastava, D.; Wu, Y., Structural joins: a primitive for efficient XML query pattern matching, (Proceedings of the 18th International Conference on Data Engineering, (2002), San Jose CA, USA), 141-152
[19] Bruno, N.; Koudas, N.; Srivastava, D., Holistic twig joins: optimal XML pattern matching, (Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, (2002)), 310-321
[20] J. Lu, T. Chen, T.W. Ling, Efficient processing of XML twig patterns with parent child edges: a look-ahead approach, in: Proceedings of the 13th ACM International Conference on Information and Knowledge Management, CIKM, Washington D.C., USA, 2004, pp. 533-542.
[21] Lu, J.; Ling, T. W.; Chan, C. Y.; Chen, T., From region encoding to extended Dewey: on efficient processing of XML twig pattern matching, (Proceedings of the 31st International Conference on Very Large Data Bases, VLDB, (2005), Trondheim Norway), 193-204
[22] Chen, S.; Li, H. G.; Tatemura, J.; Hsiung, W. P.; Agrawal, D.; Candan, K. S., Twig2stack: bottom-up processing of generalized-tree-pattern queries over XML documents, (Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB’06, (2006)), 283-294
[23] Qin, L.; Yu, J. X.; Ding, B., Twiglist: make twig pattern matching fast, (Proceedings of the 12th International Conference on Database Systems for Advanced Applications, DASFAA, DASFAA’07, (2007), Springer-Verlag Berlin, Heidelberg), 850-862
[24] Haw, S. C.; Lee, C. S., Twigx-guide: an efficient twig pattern matching system extending dataguide indexing and region encoding labeling, J. Inf. Sci. Eng., 25, 2, 603-617, (2009)
[25] Shasha, D.; Wang, J. T.-L.; Shan, H.; Zhang, K., Atreegrep: approximate searching in unordered trees, (Proceedings of the 14th International Conference on Scientific and Statistical Database Management, SSDBM, (2002), Edinburgh Scotland, UK), 89-98
[26] Zezula, P.; Mandreoli, F.; Martoglia, R., Tree signatures and unordered XML pattern matching, (SOFSEM: Theory and Practice of Computer Science, 30th Conference on Current Trends in Theory and Practice of Computer Science, (2004), Merin Czech Republic), 122-139 · Zbl 1202.68125
[27] Wu, X.; Liu, G., XML twig pattern matching using version tree, Data Knowledge Eng., 64, 580-599, (2008)
[28] J. Yao, M.Z. II, A fast tree pattern matching algorithm for XML query, in: 2004 IEEE/WIC/ACM International Conference on Web Intelligence, WI 2004, Beijing, China, 2004, pp. 235-241.
[29] Ogilvie, P., Retrieval using structure for question answering, (Proceedings of the First Twente Data Management Workshop; XML databases and Information retrieval, (2004)), 15-23
[30] Trotman, A.; Sigurbjornsson, B., NEXI, now and next, (Proceedings of the 3rd Workshop of the Initiative for the Evaluation of XML retrieval, INEX, (2004)), 41-53
[31] Buneman, P.; Davidson, S.; Hillebrand, G.; Suciu, D., A query language and optimization techniques for unstructured data, (Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, SIGMOD’96, (1996), ACM New York, NY, USA), 505-516
[32] Levy, A.; Fernandez, M.; Suciu, D.; Florescu, D.; Deutsch, A., XMLQL: a query language for XML, tech. rep., world wide web consortium technical report, number NOTE- XML-ql-19980819, (1998)
[33] Robie, J.; Lapp, J.; Schach, D., XML query language (XQL), (Proceedings of W3C QL98 (Query Languages 98), (1998), Massachussets USA)
[34] Chamberlin, D.; Robie, J.; Florescu, D., Quilt: an XML query language for heterogeneous data sources, (The World Wide Web and Databases, Lecture Notes in Computer Science, vol. 1997, (2001)), 1-25
[35] D. Chamberlin, P. Fankhauser, et al. XML Query Use Cases, Tech. Rep., World Wide Web Consortium (W3C) Group Note, March 2007.
[36] Botev, C.; Shanmugasundaram, J., Xquery full-text, (Encyclopedia of Database Systems, (2009), Springer), 3665-3671
[37] W3C, XQuery 1.0 and XPath 2.0 Full-Text 1.0 Use Cases, Tech. Rep., World Wide Web Consortium (W3C) Group Note, January 2011.
[38] R. van Zwol, J. Baas, H. van Oostendorp, F. Wiering, Bricks: the building blocks to tackle query formulation in structured document retrieval, in: 28th European Conference on IR Research, ECIR 2006, London, UK, 2006, pp. 314-325.
[39] Ceri, S.; Comai, S.; Damiani, E.; Fraternali, P.; Paraboschi, S.; Tanca, L., XML-GL: a graphical language for querying and restructuring XML documents, (Proceedings of the Eighth International Conference on World Wide Web, WWW’99, (1999), Elsevier North-Holland, Inc. New York, NY, USA), 1171-1187
[40] Hoffmann, C. M.; O’Donnell, M. J., Pattern matching in trees, J. ACM, 68-95, (1982) · Zbl 0477.68067
[41] Aho, A. V.; Corasick, M. J., Efficient string matching: an aid to bibliographic search, Commun. ACM, 333-340, (1975) · Zbl 0301.68048
[42] Chase, D. R., An improvement to bottom-up tree pattern matching, (POPL’87, (1987)), 168-177
[43] Cai, J.; Paige, R.; Tarjan, R. E., More efficient bottom-up tree pattern matching, (CAAP’90, (1990)), 72-86 · Zbl 0759.68030
[44] Burghardt, J., A tree pattern matching algorithm with reasonable space requirements, (CAAP’88, (1988)), 1-15 · Zbl 0645.68077
[45] Kosaraju, S. R., Efficient tree pattern matching, (Proceedings of the 30th Annual Symposium on Foundations of Computer Science, (1989), IEEE Computer Society Washington, DC, USA), 178-183
[46] Dubiner, M.; Galil, Z.; Magen, E., Faster tree pattern matching, J. ACM, 41, 205-213, (1994) · Zbl 0806.68055
[47] Cole, R.; Hariharan, R., Tree pattern matching and subset matching in randomized \(o(n \log^3 m)\) time, (Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, (1997), ACM New York, NY, USA), 66-75 · Zbl 0962.68041
[48] Cole, R.; Hariharan, R., Tree pattern matching to subset matching in linear time, SIAM J. on Computing, 32, 1056-1066, (2003) · Zbl 1029.68153
[49] Bille, P., A survey on tree edit distance and related problems, Theoret. Comput. Sci., 217-239, (2005) · Zbl 1078.68152
[50] Schlieder, T.; Meuss, H., Querying and ranking XML documents, JASIST, 53, 6, 489-503, (2002)
[51] Yang, L. H.; Lee, M. L.; Hsu, W., Finding hot query patterns over an xquery stream, VLDB J, 318-332, (2004)
[52] T. Schlieder, Approximate tree embedding for querying XML data, Proceedings of ACM SIGIR workshop on XML and information retrieval, Athens, Greece, 2000.
[53] Tai, K. C., The tree-to-tree correction problem, J. ACM, 26, 422-433, (1979) · Zbl 0409.68040
[54] Zhang, K.; Shasha, D., Simple fast algorithms for the editing distance between trees and related problems, SIAM J. Comput, 1245-1262, (1989) · Zbl 0692.68047
[55] Klein, P. N., Computing the edit-distance between unrooted ordered trees, (Proceedings of the 6th Annual European Symposium on Algorithms, ESA’98, (1998), Springer-Verlag London, UK), 91-102 · Zbl 0932.68066
[56] Chen, W., New algorithm for ordered tree-to-tree correction problem, J. Algorithms, 40, 135-158, (2001) · Zbl 0980.68142
[57] Dulucq, S.; Touzet, H., Decomposition algorithms for the tree edit distance problem, J. Discrete Algorithms, 448-471, (2005) · Zbl 1129.68099
[58] Demaine, E. D.; Mozes, S.; Rossman, B.; Weimann, O., An optimal decomposition algorithm for tree edit distance, (ICALP’07, (2007)), 146-157 · Zbl 1171.68843
[59] Knuth, D. E., The art of computer programming, volume i: fundamental algorithms, (1997), Addison-Wesley
[60] Kilpelainen, P.; Mannila, H., Ordered and unordered tree inclusion, SIAM J. Comput., 340-356, (1995) · Zbl 0827.68050
[61] Richter, T., A new algorithm for the ordered tree inclusion problem, (Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, CPM’97, (1997)), 150-166
[62] Chen, W., More efficient algorithm for ordered tree inclusion, J. Algorithms, 26, 370-385, (1998) · Zbl 0894.68109
[63] Bille, P.; Gortz, I. L., The tree inclusion problem: in optimal space and faster, (32nd International Colloquium on Automata, Languages and Programming, ICALP, (2005)), 66-77 · Zbl 1085.68566
[64] Chen, Y.; Chen, Y., A new tree inclusion algorithm, Inf. Process. Lett., 98, 253-262, (2006) · Zbl 1178.05091
[65] Cheng, H. L.; Wang, B. F., On Chen and chen’s new tree inclusion algorithm, Inf. Process. Lett., 14-18, (2007) · Zbl 1187.68678
[66] Chen, Y.; Chen, Y., A new top-down algorithm for tree inclusion, (Proceedings of the 2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery, (2010)), 293-300
[67] Wagner, R. A.; Fischer, M. J., The string-to-string correction problem, J. ACM, 21, 168-173, (1974) · Zbl 0278.68032
[68] Jiang, T.; Wang, L.; Zhang, K., Alignment of trees—an alternative to tree edit, Theoret. Comput. Sci., 137-148, (1995) · Zbl 0873.68150
[69] Kuboyama, T.; Shin, K.; Miyahara, T.; Yasuda, H., A theoretical analysis of alignment and edit problems for trees, (ICTCS’05, (2005)), 323-337 · Zbl 1171.68437
[70] Jansson, J.; Lingas, A., A fast algorithm for optimal alignment between similar ordered trees, (Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, CPM’01, (2001)), 232-240 · Zbl 0990.68638
[71] Wang, L.; Zhao, J., Parametric alignment of ordered trees, Bioinformatics, 2237-2245, (2003)
[72] Chen, T.; Lu, J.; Ling, T. W., On boosting holism in XML twig pattern matching using structural indexing techniques, (SIGMOD 05, (2005)), 455-466
[73] Jiang, H.; Wang, W.; Lu, H.; Yu, J. X., Holistic twig joins on indexed XML documents, (Proceedings of VLDB, (2003)), 273-284
[74] G. Li, J.F.Y. Zhang, L. Zhou, Efficient holistic twig joins in leaf-to-root combining with root-to-leaf way, DASFAA, Bangkok, Thailand, 2007, pp. 834-849.
[75] Li, J.; Wang, J., Twigbuffer: avoiding useless intermediate solutions completely in twig joins, (Proceedings of the 13th International Conference on Database Systems for Advanced Applications, DASFAA’08, (2008)), 554-561
[76] Zezula, P.; Amato, G.; Debole, F.; Rabitti, F., Tree signatures for XML querying and navigation, (Xsym’03, (2003)), 149-163
[77] Wang, H.; Park, S.; Fan, W.; Yu, P. S., Vist: a dynamic index method for querying XML data by tree structures, (SIGMOD Conference’03, (2003)), 110-121
[78] Jiang, Z.; Luo, C.; Hou, W. C.; Zhu, Q.; Che, D., Efficient processing of XML twig pattern: a novel one-phase holistic solution, (DEXA 07, (2007)), 87-97
[79] Li, J.; Wang, J., Fast matching of twig patterns, (Proceedings of the 19th International Conference on Database and Expert Systems Applications, DEXA’08, (2008)), 523-536
[80] Popovici, E.; Ménier, G.; Marteau, P.-F., SIRIUS: a lightweight XML indexing and approximate search system at INEX 2005, (INEX, (2005)), 321-335
[81] Le, M. D.; Pinel-Sauvagnat, K., Utilisation de la distance d’édition pour l’appariement sémantique de documents XML, (Atelier GAOC, Conférence EGC 2010, Tunisia, (2010))
[82] Laitang, C.; Boughanem, M.; Pinel-Sauvagnat, K., XML information retrieval through tree edit distance and structural summaries, (Asia Information Retrieval Society Conference, AIRS, (2011), Springer Dubai, United Atab Emirates), 73-83
[83] Damiani, E.; Oliboni, B.; Tanca, L., Fuzzy techniques for XML data smushing, (Reusch, B., Fuzzy Days, Lecture Notes in Computer Science, vol. 2206, (2001), Springer), 637-652 · Zbl 1043.68549
[84] C. Laitang, K. Pinel-Sauvagnat, M. Boughanem, Utilisation de la théorie des graphes et de la distance d’édition pour la recherche d’information sur documents XML, in: Proceedings of the 8th Annual Conférence en Recherche d’Information et Applications, CORIA, Avignon, France, 2011.
[85] A. Alilaouar, Interrogation flexible de documents semi-structurés, Ph.D. thesis, Université Paul Sabatier, Toulouse, France, October 2007.
[86] Zhou, J.; Xie, M.; Meng, X., Twigstack+: holistic twig join pruning using extended solution extension, Wuhan Univ. J. Natural Sci., 12, 5, 855-860, (2007)
[87] Dao, D. B.; Cao, J., A glance on current XML twig pattern matching algorithms, (ICCSA (2)’08, (2008)), 307-321
[88] Lu, J.; Meng, X.; Ling, T. W., Indexing and querying XML using extended Dewey labeling scheme, Data Knowl. Eng., 70, 35-59, (2011)
[89] Rao, P.; Moon, B., Prix: indexing and querying XML using prufer sequences, (ICDE’04, (2004)), 288-300
[90] Wang, H.; Meng, X., On the sequencing of tree structures for XML indexing, (Proceeding of ICDE, (2005)), 372-383
[91] Haw, S. C.; Lee, C. S., Node labeling schemes in XML query optimization: a survey and trends, IETE Tech. Rev., 26, 2, 88-100, (2009)
[92] Izadi, S. K.; Harder, T.; Haghjoo, M. S., \(\operatorname{S}^3\): evaluation of tree-pattern XML queries supported by structural summaries, (Proceedings of Data and Knowledge Engineering, (2009)), 126-145
[93] Mass, Y.; Mandelbrod, M., Using the INEX environment as a test bed for various user models for XML retrieval, (INEX, (2005)), 187-195
[94] Mihajlovic, V.; Ramirez, G.; Westerveld, T.; Hiemstra, D.; Blok, H.; de Vries, A. P., TIJAH scratches INEX 2005: vague element selection, image search, overlap, and relevance feedback, (INEX, (2005)), 72-87
[95] van Zwol, R., B3-sdr and effective use of structural hints, (INEX, (2005)), 146-160
[96] Theobald, M.; Schenkel, R.; Weikum, G., Topx and XXL at INEX 2005, (INEX, (2005)), 282-295
[97] Hubert, G., XML retrieval based on direct contribution of query components, (INEX, (2005)), 172-186
[98] Pinel-Sauvagnat, K.; Boughanem, M.; Chrisment, C., Answering content-and-structure-based queries on XML documents using relevance propagation, (Information Systems, (2006), Elsevier), 172-186, Special Issue SPIRE 2004 31
[99] Aouicha, M. B.; Tmar, M.; Boughanem, M.; Abid, M., XML information retrieval based on tree matching, (IEEE International Conference on Engineering of Computer Based Systems, (2008), ECBS Belfast, Ireland), 499-500
[100] M.B. Aouicha, Une approche algébrique pour la recherche d’information structurée, Ph.D. thesis, Université Paul Sabatier, Toulouse, France, 2009.
[101] Alilaouar, A.; Sédes, F., Fuzzy querying of XML documents, (IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology, (2005), IEEE/WIC/ACM Compiègne, France), 11-14
[102] T.L. Saito, S. Morishita, Amoeba join: overcoming structural fluctuations in XML data, in: Ninth International Workshop on the Web and Databases, WebDB 2006, Chicago, Illinois, USA, 2006, pp. 38-43.
[103] Damiani, E.; Tanca, L.; Fontana, F. A., Fuzzy XML queries via context-based choice of aggregations, Kybernetika, 36, 6, 635-655, (2000) · Zbl 1249.68059
[104] (Fuhr, N.; Lalmas, M.; Malik, S.; Kazai, G., Advances in XML Information Retrieval and Evaluation, 4th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2005, Dagstuhl Castle, Germany, Lecture Notes in Computer Science, vol. 3977, (2006), Springer)
[105] Comparative evaluation of XML information retrieval systems, (Fuhr, N.; Lalmas, M.; Trotman, A., 5th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2006, Dagstuhl Castle, Germany, Lecture Notes in Computer Science, vol. 4518, (2007), Springer)
[106] Focused access to XML documents, (Fuhr, N.; Kamps, J.; Lalmas, M.; Trotman, A., 6th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2007, Dagstuhl Castle, Germany, Lecture Notes in Computer Science, vol. 4862, (2008), Springer)
[107] Advances in focused retrieval, (Geva, S.; Kamps, J.; Trotman, A., 7th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2008, Dagstuhl Castle, Germany, Lecture Notes in Computer Science, vol. 5631, (2009), Springer)
[108] Focused retrieval and evaluation, (Geva, S.; Kamps, J.; Trotman, A., 8th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2009, Brisbane, Australia, Lecture Notes in Computer Science, vol. 6203, (2010), Springer)
[109] Comparative evaluation of focused retrieval, (Geva, S.; Kamps, J.; Schenkel, R.; Trotman, A., 9th International Workshop of the Inititative for the Evaluation of XML Retrieval, INEX 2010, Vugh, The Netherlands, December 13-15, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6932, (2011), Springer)
[110] S. Amer-Yahia, S. Cho, D. Srivastava, Tree pattern relaxation, in: EDBT02, Prague, Czech Republic, 2002, pp. 496-513. · Zbl 1054.68762
[111] Dalamagas, T.; Cheng, T.; Winkel, K. J.; Sellis, T. K., Clustering XML documents using structural summaries, (EDBT Workshops, (2004)), 547-556
[112] Dalamagas, T.; Cheng, T.; Winkel, K. J.; Sellis, T. K., A methodology for clustering XML documents by structure, Inf. Syst., 31, 3, 187-228, (2006)
[113] Levenshtein, V. I., Binary codes capable of correcting deletions, insertions, and reversals, Soviet Phys. Dokl., 10, 8, 707-710, (1966)
[114] S. Dulucq, H. Touzet, Analysis of tree edit distance algorithms, in: Proceedings of Combinatorial Pattern Matching, 14th Annual Symposium, CPM 2003, Morelia, Michocán, Mexico, 2003, pp. 83-95. · Zbl 1279.68067
[115] S. Al-Khalifa, XML query evaluation, Ph.D. thesis, University of Michigan, Ann Arbor, USA, 2005.
[116] A. Schmidt, F. Waas, M.L. Kersten, M.J. Carey, I. Manolescu, R. Busse, XMark: a benchmark for XML data management, in: Proceedings of 28th International Conference on Very Large Data Bases, VLDB, Hong Kong, China, Morgan Kaufmann, 2002, pp. 974-985. · Zbl 1021.68797
[117] Yao, B. B.; Özsu, M. T.; Khandelwal, N., Xbench benchmark and performance testing of XML dbmss, (Proceedings of the 20th International Conference on Data Engineering, ICDE 2004, (2004), IEEE Computer Society Boston, MA, USA), 621-633
[118] Runapongsa, K.; Patel, J. M.; Jagadish, H. V.; Chen, Y.; Al-Khalifa, S., The michigan benchmark: towards XML query performance diagnostics, Inf. Syst., 31, 2, 73-97, (2006)
[119] R.S. Shlomo Geva, Jaap Kamps, Inex’12 workshop pre-proceedings, 2012.
[120] Denoyer, L.; Gallinari, P., The wikipedia XML corpus, SIGIR Forum, 40, 1, 64-69, (2006)
[121] Schenkel, R.; Suchanek, F.; Kasneci, G., YAWN: a semantically annotated wikipedia XML corpus, (12. GI-Fachtagung für Datenbanksysteme in Business, Technologie und Web, BTW 2007, Vol. 103, (2007)), 277-291
[122] G. Kazai, M. Lalmas, A.P. de Vries, The overlap problem in content-oriented XML retrieval evaluation, in: Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2004, Sheffield, UK, 2004, pp. 72-79.
[123] Kazai, G.; Lalmas, M., Extended cumulated gain measures for the evaluation of content-oriented XML retrieval, ACM Trans. Inf. Syst., 24, 4, 503-542, (2006)
[124] Kamps, J.; Pehcevski, J.; Kazai, G.; Lalmas, M.; Robertson, S., INEX 2007 evaluation measures, (INEX, (2007)), 24-33
[125] de Vries, A. P.; Kazai, G.; Lalmas, M., Tolerance to irrelevance: a user-effort evaluation of retrieval systems without predefined retrieval unit, (Proceedings of RIAO 2004, (2004), Avignon France), 463-473
[126] Piwowarski, B.; Gallinari, P.; Dupret, G., Precision recall with user modeling (prum): application to structured information retrieval, ACM Trans. Inf. Syst., 25, 1, (2007)
[127] Pehcevski, J.; Thom, J. A., Hixeval: highlighting XML retrieval evaluation, (INEX, (2005)), 43-57
[128] Pehcevski, J.; Piwowarski, B., Evaluation metrics for structured text retrieval, (Encyclopedia of Database Systems, (2009)), 1015-1024
[129] Trotman, A.; Wang, Q., Overview of the INEX 2010 data centric track, (INEX 2010 pre-proceedings, (2010)), 128-137
[130] Ayala, D. V.; Pinto, D.; Balderas, C.; Tovar, M., BUAP: a first approach to the data-centric track of INEX 2010, (INEX 2010 pre-proceedings, (2010)), 159-168
[131] Hummel, F.; da Silva, A.; Moro, M.; Laender, A., Automatically generating structured queries in XML keyword search, (INEX 2010 pre-proceedings, (2010)), 138-149
[132] Li, Q.; Wang, Q.; Wang, S., Inferring query pattern for XML keyword retrieval, (INEX 2010 pre-proceedings, (2010)), 150-158
[133] Wang, Q.; Ramírez, G.; Marx, M. M.; Theobald, M.; Kamps, J., Overview of the inex 2011 data-centric track, (Focused Retrieval and Evaluation: 10th International Workshop of the Initiative for the Evaluation of XML Retrieval, INEX 2011, Lecture Notes in Computer Science, vol. 7424, (2012), Springer Hofgut Imsbach, Theley, Germany)
[134] Schenkel, R.; Theobald, M., Overview of the INEX 2009 efficiency track, (INEX, (2009)), 200-212
[135] Trotman, A.; Lalmas, M., Why structural hints in queries do not help XML-retrieval, (Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2006, (2006), Seattle Washington, USA), 711-712
[136] K. Sauvagnat, M. Boughanem, C. Chrisment, Why using structural hints in XML retrieval? in: Flexible Query Answering Systems, 7th International Conference, FQAS 2006, Milan, Italy, 2006, pp. 197-209.
[137] C. Laitang, K. Pinel-Sauvagnat, M. Boughanem, DTD based costs for TreeEdit distance in Structured Information Retrieval, in: European Conference on Information Retrieval (ECIR), Moscou, Russie, 25-27 March 2013.
[138] Stahl, S., The embeddings of a graph-a survey, J. Graph Theory, 2, 275-298, (1978) · Zbl 0406.05027
[139] Dürr, C.; Heiligman, M.; Hoyer, P.; Mhalla, M., Quantum query complexity of some graph problems, (Proceedings of ICALP’04, (2004)), 481-493 · Zbl 1099.68640
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.