{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T18:08:39Z","timestamp":1743098919596,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642043284"},{"type":"electronic","value":"9783642043291"}],"license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-04329-1_14","type":"book-chapter","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T19:06:21Z","timestamp":1259607981000},"page":"309-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Labeling RDF Graphs for Linear Time and\u00a0Space Querying"],"prefix":"10.1007","author":[{"given":"Tim","family":"Furche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonius","family":"Weinzierl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Bry","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,1]]},"reference":[{"key":"14_CR1","first-page":"253","volume-title":"Proc. ACM Symp. on Management of Data (SIGMOD)","author":"R. Agrawal","year":"1989","unstructured":"Agrawal, R., Borgida, A., Jagadish, H.V.: Efficient management of transitive relationships in large data and knowledge bases. In: Proc. ACM Symp. on Management of Data (SIGMOD), pp. 253\u2013262. ACM, New York (1989)"},{"key":"14_CR2","first-page":"141","volume-title":"Proc. Int. Conf. on Data Engineering","author":"S. Al-Khalifa","year":"2002","unstructured":"Al-Khalifa, S., Jagadish, H.V., Koudas, N., Patel, J.M., Srivastava, D., Wu, Y.: Structural joins: a primitive for efficient XML query pattern matching. In: Proc. Int. Conf. on Data Engineering, p. 141. IEEE Computer Society, Los Alamitos (2002)"},{"key":"14_CR3","unstructured":"Backett, D.: Turtle\u2014Terse RDF Triple Language. Technical Report, Institute for Learning and Research Technology, University of Bristol (2007)"},{"key":"14_CR4","unstructured":"Beckett, D., McBride, B.: RDF\/XML Syntax Specification (Revised). Recommendation, W3C (2004)"},{"key":"14_CR5","unstructured":"Bolzer, O.: Towards Data-Integration on the Semantic Web: Querying RDF with Xcerpt. Diplomarbeit\/diploma Thesis, University of Munich (2005)"},{"key":"14_CR6","first-page":"479","volume-title":"Proc. ACM Symp. on Management of Data (SIGMOD)","author":"P. Boncz","year":"2006","unstructured":"Boncz, P., Grust, T., van Keulen, M., Manegold, S., Rittinger, J., Teubner, J.: MonetDB\/XQuery: a fast XQuery processor powered by a relational engine. In: Proc. ACM Symp. on Management of Data (SIGMOD), pp. 479\u2013490. ACM, New York (2006)"},{"key":"14_CR7","first-page":"255","volume-title":"Proc. of ACM Symposium on Theory of Computing","author":"K.S. Booth","year":"1975","unstructured":"Booth, K.S., Lueker, G.S.: Linear algorithms to recognize interval graphs and test for the consecutive ones property. In: Proc. of ACM Symposium on Theory of Computing, pp. 255\u2013265. ACM, New York (1975)"},{"key":"14_CR8","first-page":"310","volume-title":"Proc. ACM SIGMOD Int. Conf. on Management of Data","author":"N. Bruno","year":"2002","unstructured":"Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: optimal XML pattern matching. In: Proc. ACM SIGMOD Int. Conf. on Management of Data, pp. 310\u2013321. ACM, New York (2002)"},{"key":"14_CR9","unstructured":"Bry, F., Furche, T., Linse, B., Pohl, A.: Xcerpt\n                  rdf\n                : A pattern-based answer to the versatile web challenge. In: Proc. Workshop on (Constraint) Logic Programming (WLP) (2008)"},{"key":"14_CR10","unstructured":"Chen, L., Gupta, A., Kurul, M.E.: Stack-based algorithms for pattern matching on dags. In: Proc. Int\u2019l. Conf. on Very Large Data Bases (VLDB), pp. 493\u2013504. VLDB Endowment (2005)"},{"key":"14_CR11","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/1066157.1066209","volume-title":"Proc. ACM SIGMOD Int. Conf. on Management of Data","author":"T. Chen","year":"2005","unstructured":"Chen, T., Lu, J., Ling, T.W.: On boosting holism in XML twig pattern matching using structural indexing techniques. In: Proc. ACM SIGMOD Int. Conf. on Management of Data, pp.\u00a0455\u2013466. ACM, New York (2005)"},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.datak.2006.03.003","volume":"60","author":"Z. Chen","year":"2007","unstructured":"Chen, Z., Gehrke, J., Korn, F., Koudas, N., Shanmugasundaram, J., Srivastava, D.: Index structures for matching XML twigs using relational query processors. Data Knowl. Eng. (DKE) 60(2), 283\u2013302 (2007)","journal-title":"Data Knowl. Eng. (DKE)"},{"key":"14_CR13","first-page":"544","volume-title":"Proc. Int\u2019l. World Wide Web Conf. (WWW)","author":"V. Christophides","year":"2003","unstructured":"Christophides, V., Plexousakis, D., Scholl, M., Tourtounis, S.: On labeling schemes for the semantic web. In: Proc. Int\u2019l. World Wide Web Conf. (WWW), pp. 544\u2013555. ACM, New York (2003)"},{"key":"14_CR14","first-page":"937","volume-title":"Proc. ACM Symposium on Discrete Algorithms","author":"E. Cohen","year":"2002","unstructured":"Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. In: Proc. ACM Symposium on Discrete Algorithms, pp. 937\u2013946. Society for Industrial and Applied Mathematics, Philadelphia (2002)"},{"key":"14_CR15","first-page":"122","volume-title":"Proc. ACM Symp. on Theory of Computing (STOC)","author":"P.F. Dietz","year":"1982","unstructured":"Dietz, P.F.: Maintaining order in a linked list. In: Proc. ACM Symp. on Theory of Computing (STOC), pp. 122\u2013127. ACM, New York (1982)"},{"issue":"3","key":"14_CR16","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D.R. Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Gross, O.A.: Incidence matrices and interval graphs. Pac. J. Math. 15(3), 835\u2013855 (1965)","journal-title":"Pac. J. Math."},{"key":"14_CR17","unstructured":"Furche, T.: Implementation of web query language reconsidered: beyond tree and single-language algebras at (almost) no cost. Dissertation\/doctoral Thesis, Ludwig-Maxmilians University Munich (2008)"},{"key":"14_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"1","key":"14_CR19","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1089\/cmb.1995.2.139","volume":"2","author":"P.W. Goldberg","year":"1995","unstructured":"Goldberg, P.W., Golumbic, M.C., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139\u2013152 (1995)","journal-title":"J. Comput. Biol."},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM Trans. Database Syst. (2005)","DOI":"10.1145\/1071610.1071614"},{"issue":"3","key":"14_CR21","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1145\/382780.382783","volume":"48","author":"G. Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. J. ACM 48(3), 431\u2013498 (2001)","journal-title":"J. ACM"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Grust, T.: Accelerating XPath location steps. In: Proc. ACM Symp. on Management of Data (SIGMOD) (2002)","DOI":"10.1145\/564691.564705"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Grust, T., van Keulen, M., Teubner, J.: Staircase join: teach a relational DBMS to watch its (axis) steps. In: Proc. Int. Conf. on Very Large Databases (2003)","DOI":"10.1016\/B978-012722442-8\/50053-7"},{"issue":"1\u20132","key":"14_CR24","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/S0304-3975(97)00241-7","volume":"234","author":"M. Habib","year":"2000","unstructured":"Habib, M., McConnell, R., Paul, C., Viennot, L.: Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci. 234(1\u20132), 59\u201384 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"14_CR25","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.ipl.2008.04.009","volume":"108","author":"S. Haddadi","year":"2008","unstructured":"Haddadi, S., Layouni, Z.: Consecutive block minimization is 1.5-approximable. Inf. Process. Lett. 108(3), 132\u2013135 (2008)","journal-title":"Inf. Process. Lett."},{"key":"14_CR26","series-title":"LNCS","volume-title":"Proc. Int\u2019l. Conf. on Computing and Combinatorics","author":"W.L. Hsu","year":"2001","unstructured":"Hsu, W.L.: PC-trees vs. PQ-trees. In: Proc. Int\u2019l. Conf. on Computing and Combinatorics. LNCS, vol.\u00a02108. Springer, Berlin (2001)"},{"issue":"1","key":"14_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jagm.2001.1205","volume":"43","author":"W.L. Hsu","year":"2002","unstructured":"Hsu, W.L.: A simple test for the consecutive ones property. J. Algorithms 43(1), 1\u201316 (2002)","journal-title":"J. Algorithms"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Jiang, H., Wang, W., Lu, H., Yu, J.X.: Holistic twig joins on indexed XML documents. In: Proc. Int\u2019l. Conf. on Very Large Data Bases (VLDB), pp. 273\u2013284. VLDB Endowment (2003)","DOI":"10.1016\/B978-012722442-8\/50032-X"},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/0206004","volume":"6","author":"L.T. Kou","year":"1977","unstructured":"Kou, L.T.: Polynomial complete consecutive information retrieval problems. SIAM J. Comput. 6(1), 67\u201375 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"14_CR30","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1145\/382979.383042","volume":"19","author":"H. Meuss","year":"2001","unstructured":"Meuss, H., Schulz, K.U.: Complete answer aggregates for treelike databases: a novel approach to combine querying and navigation. ACM Trans. Inf. Syst. 19(2), 161\u2013215 (2001)","journal-title":"ACM Trans. Inf. Syst."},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Olteanu, D.: SPEX: streamed and progressive evaluation of XPath. IEEE Trans. Knowl. Data Eng. (2007)","DOI":"10.1109\/TKDE.2007.1063"},{"key":"14_CR32","doi-asserted-by":"crossref","unstructured":"Olteanu, D., Furche, T., Bry, F.: Evaluating complex queries against XML streams with polynomial combined complexity. In: Proc. British National Conf. on Databases (BNCOD), pp.\u00a031\u201344 (2003)","DOI":"10.1007\/978-3-540-27811-5_4"},{"key":"14_CR33","doi-asserted-by":"crossref","unstructured":"Olteanu, D., Furche, T., Bry, F.: An efficient single-pass query evaluator for XML data streams. In: Data Streams Track, Proc. ACM Symp. on Applied Computing (SAC) pp. 627\u2013631 (2004)","DOI":"10.1145\/967900.968032"},{"key":"14_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36128-6_7","volume-title":"Proc. EDBT Workshop on XML-Based Data Management","author":"D. Olteanu","year":"2002","unstructured":"Olteanu, D., Meuss, H., Furche, T., Bry, F.: XPath: looking forward. In: Proc. EDBT Workshop on XML-Based Data Management. Lecture Notes in Computer Science, vol. 2490. Springer, Berlin (2002)"},{"key":"14_CR35","first-page":"903","volume-title":"Proc. ACM Symp. on Management of Data (SIGMOD)","author":"P. O\u2019Neil","year":"2004","unstructured":"O\u2019Neil, P., O\u2019Neil, E., Pal, S., Cseri, I., Schaller, G., Westbury, N.: ORDPATHs: insert-friendly XML node labels. In: Proc. ACM Symp. on Management of Data (SIGMOD), pp. 903\u2013908. ACM, New York (2004)"},{"issue":"6","key":"14_CR36","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"Perez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. In: Proc. Int\u2019l. Semantic Web Conf. (ISWC) (2006)","DOI":"10.1007\/11926078_3"},{"key":"14_CR38","doi-asserted-by":"crossref","unstructured":"P\u00e9rez, J., Arenas, M., Gutierrez, C.: nSPARQL: A navigational language for rdf. In: Proc. Int\u2019l. Semantic Web Conf. (ISWC), pp. 66\u201381 (2008)","DOI":"10.1007\/978-3-540-88564-1_5"},{"key":"14_CR39","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/1242572.1242679","volume-title":"Proc. Int\u2019l. World Wide Web Conf. (WWW)","author":"A. Polleres","year":"2007","unstructured":"Polleres, A.: From SPARQL to rules (and back). In: Proc. Int\u2019l. World Wide Web Conf. (WWW), pp. 787\u2013796. ACM, New York (2007)"},{"key":"14_CR40","unstructured":"Prud\u2019hommeaux, E., Seaborne, A.: SPARQL Query Language for RDF. Proposed Recommendation, W3C (2007)"},{"key":"14_CR41","doi-asserted-by":"crossref","unstructured":"Schenkel, R., Theobald, A., Weikum, G.: HOPI: an efficient connection index for complex XML document collections. In: Proc. Extending Database Technology (2004)","DOI":"10.1007\/978-3-540-24741-8_15"},{"issue":"2","key":"14_CR42","doi-asserted-by":"publisher","first-page":"88","DOI":"10.4103\/0256-4602.49086","volume":"26","author":"H. Su-Cheng","year":"2009","unstructured":"Su-Cheng, H., Chien-Sing, L.: Node labeling schemes in XML query optimization: A survey and trends. IETE Tech. Rev. 26(2), 88\u2013100 (2009)","journal-title":"IETE Tech. Rev."},{"key":"14_CR43","first-page":"845","volume-title":"Proc. ACM Symp. on Management of Data (SIGMOD)","author":"S. Tri\u00dfl","year":"2007","unstructured":"Tri\u00dfl, S., Leser, U.: Fast and practical indexing and querying of very large graphs. In: Proc. ACM Symp. on Management of Data (SIGMOD), pp. 845\u2013856. ACM, New York (2007)"},{"key":"14_CR44","first-page":"75","volume-title":"Proc. Int\u2019l. Conf. on Data Engineering (ICDE)","author":"H. Wang","year":"2006","unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., Yu, J.X.: Dual labeling: Answering graph reachability queries in constant time. In: Proc. Int\u2019l. Conf. on Data Engineering (ICDE), p. 75. IEEE Computer Society, Los Alamitos (2006)"},{"key":"14_CR45","series-title":"LNCS","first-page":"49","volume-title":"Proc. Int\u2019l. XML Database Symposium (XSym)","author":"F. Weigel","year":"2005","unstructured":"Weigel, F., Schulz, K.U., Meuss, H.: The BIRD numbering scheme for XML and tree databases\u2014deciding and reconstructing tree relations using efficient arithmetic operations. In: Proc. Int\u2019l. XML Database Symposium (XSym). LNCS, vol. 3671, pp. 49\u201367. Springer, Berlin (2005)"},{"key":"14_CR46","unstructured":"Weinzierl, A.: Interval-based graph representations for efficient web querying. Diplomarbeit\/diploma Thesis, Ludwig-Maxmilians University Munich (2009)"}],"container-title":["Semantic Web Information Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04329-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T20:49:37Z","timestamp":1676062177000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-04329-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,1]]},"ISBN":["9783642043284","9783642043291"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04329-1_14","relation":{},"subject":[],"published":{"date-parts":[[2009,12,1]]},"assertion":[{"value":"1 December 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}