HOPI: An Efficient Connection Index for Complex XML Document Collections
Identifieur interne : 001910 ( Istex/Corpus ); précédent : 001909; suivant : 001911HOPI: An Efficient Connection Index for Complex XML Document Collections
Auteurs : Ralf Schenkel ; Anja Theobald ; Gerhard WeikumSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2004.
English descriptors
- Teeft :
- Algorithm, Ancestor queries, Arbitrary graphs, Center graph, Center graphs, Center node, Closure, Complete dblp, Compression factor, Compression ratio, Connection index, Cout, Data collections, Database, Dblp, Densest, Densest subgraph, Densest subgraphs, Descendants, Document, Document graph, Entire graph, Experiments show, Graph, Hopi, Hopi index, Index structure, Index structures, Large graphs, Lout, Megabyte, Node, Partitioning, Path expressions, Path queries, Query, Query performance, Schenkel, Search engine, Sigmod, Single document, Span documents, Subgraph, Subgraphs, Theobald, Transitive, Transitive closure, Tree signatures, Vout, Weikum, Wildcards.
Abstract
Abstract: In this paper we present HOPI, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.
Url:
DOI: 10.1007/978-3-540-24741-8_15
Links to Exploration step
ISTEX:EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">HOPI: An Efficient Connection Index for Complex XML Document Collections</title><author><name sortKey="Schenkel, Ralf" sort="Schenkel, Ralf" uniqKey="Schenkel R" first="Ralf" last="Schenkel">Ralf Schenkel</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: schenkel@mpi-sb.mpg.de</mods:affiliation></affiliation></author><author><name sortKey="Theobald, Anja" sort="Theobald, Anja" uniqKey="Theobald A" first="Anja" last="Theobald">Anja Theobald</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: anja.theobald@mpi-sb.mpg.de</mods:affiliation></affiliation></author><author><name sortKey="Weikum, Gerhard" sort="Weikum, Gerhard" uniqKey="Weikum G" first="Gerhard" last="Weikum">Gerhard Weikum</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: weikum@mpi-sb.mpg.de</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-24741-8_15</idno><idno type="url">https://api.istex.fr/document/EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001910</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001910</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">HOPI: An Efficient Connection Index for Complex XML Document Collections</title><author><name sortKey="Schenkel, Ralf" sort="Schenkel, Ralf" uniqKey="Schenkel R" first="Ralf" last="Schenkel">Ralf Schenkel</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: schenkel@mpi-sb.mpg.de</mods:affiliation></affiliation></author><author><name sortKey="Theobald, Anja" sort="Theobald, Anja" uniqKey="Theobald A" first="Anja" last="Theobald">Anja Theobald</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: anja.theobald@mpi-sb.mpg.de</mods:affiliation></affiliation></author><author><name sortKey="Weikum, Gerhard" sort="Weikum, Gerhard" uniqKey="Weikum G" first="Gerhard" last="Weikum">Gerhard Weikum</name><affiliation><mods:affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: weikum@mpi-sb.mpg.de</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2004</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Ancestor queries</term><term>Arbitrary graphs</term><term>Center graph</term><term>Center graphs</term><term>Center node</term><term>Closure</term><term>Complete dblp</term><term>Compression factor</term><term>Compression ratio</term><term>Connection index</term><term>Cout</term><term>Data collections</term><term>Database</term><term>Dblp</term><term>Densest</term><term>Densest subgraph</term><term>Densest subgraphs</term><term>Descendants</term><term>Document</term><term>Document graph</term><term>Entire graph</term><term>Experiments show</term><term>Graph</term><term>Hopi</term><term>Hopi index</term><term>Index structure</term><term>Index structures</term><term>Large graphs</term><term>Lout</term><term>Megabyte</term><term>Node</term><term>Partitioning</term><term>Path expressions</term><term>Path queries</term><term>Query</term><term>Query performance</term><term>Schenkel</term><term>Search engine</term><term>Sigmod</term><term>Single document</term><term>Span documents</term><term>Subgraph</term><term>Subgraphs</term><term>Theobald</term><term>Transitive</term><term>Transitive closure</term><term>Tree signatures</term><term>Vout</term><term>Weikum</term><term>Wildcards</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we present HOPI, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.</div></front></TEI><istex><corpusName>springer</corpusName><keywords><teeft><json:string>node</json:string><json:string>hopi</json:string><json:string>lout</json:string><json:string>transitive</json:string><json:string>query</json:string><json:string>transitive closure</json:string><json:string>subgraph</json:string><json:string>vout</json:string><json:string>algorithm</json:string><json:string>partitioning</json:string><json:string>cout</json:string><json:string>connection index</json:string><json:string>database</json:string><json:string>weikum</json:string><json:string>center graph</json:string><json:string>densest subgraph</json:string><json:string>theobald</json:string><json:string>closure</json:string><json:string>schenkel</json:string><json:string>dblp</json:string><json:string>megabyte</json:string><json:string>densest</json:string><json:string>wildcards</json:string><json:string>subgraphs</json:string><json:string>densest subgraphs</json:string><json:string>sigmod</json:string><json:string>arbitrary graphs</json:string><json:string>search engine</json:string><json:string>path queries</json:string><json:string>large graphs</json:string><json:string>query performance</json:string><json:string>ancestor queries</json:string><json:string>index structure</json:string><json:string>compression ratio</json:string><json:string>complete dblp</json:string><json:string>experiments show</json:string><json:string>center graphs</json:string><json:string>document graph</json:string><json:string>index structures</json:string><json:string>entire graph</json:string><json:string>hopi index</json:string><json:string>compression factor</json:string><json:string>data collections</json:string><json:string>tree signatures</json:string><json:string>single document</json:string><json:string>span documents</json:string><json:string>path expressions</json:string><json:string>center node</json:string><json:string>graph</json:string><json:string>descendants</json:string><json:string>document</json:string></teeft></keywords><author><json:item><name>Ralf Schenkel</name><affiliations><json:string>Max Planck Institut für Informatik, Saarbrücken, Germany</json:string><json:string>E-mail: schenkel@mpi-sb.mpg.de</json:string></affiliations></json:item><json:item><name>Anja Theobald</name><affiliations><json:string>Max Planck Institut für Informatik, Saarbrücken, Germany</json:string><json:string>E-mail: anja.theobald@mpi-sb.mpg.de</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max Planck Institut für Informatik, Saarbrücken, Germany</json:string><json:string>E-mail: weikum@mpi-sb.mpg.de</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: In this paper we present HOPI, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.</abstract><qualityIndicators><score>6.596</score><pdfWordCount>8097</pdfWordCount><pdfCharCount>42263</pdfCharCount><pdfVersion>1.3</pdfVersion><pdfPageCount>19</pdfPageCount><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><abstractWordCount>133</abstractWordCount><abstractCharCount>832</abstractCharCount><keywordCount>0</keywordCount></qualityIndicators><title>HOPI: An Efficient Connection Index for Complex XML Document Collections</title><chapterId><json:string>15</json:string><json:string>Chap15</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><title>Lecture Notes in Computer Science</title><language><json:string>unknown</json:string></language><copyrightDate>2004</copyrightDate><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><editor><json:item><name>Gerhard Goos</name><affiliations><json:string>Karlsruhe University, Germany</json:string></affiliations></json:item><json:item><name>Juris Hartmanis</name><affiliations><json:string>Cornell University, NY, USA</json:string></affiliations></json:item><json:item><name>Jan van Leeuwen</name><affiliations><json:string>Utrecht University, The Netherlands</json:string></affiliations></json:item></editor></serie><host><title>Advances in Database Technology - EDBT 2004</title><language><json:string>unknown</json:string></language><copyrightDate>2004</copyrightDate><doi><json:string>10.1007/b95855</json:string></doi><issn><json:string>0302-9743</json:string></issn><eissn><json:string>1611-3349</json:string></eissn><eisbn><json:string>978-3-540-24741-8</json:string></eisbn><bookId><json:string>978-3-540-24741-8</json:string></bookId><isbn><json:string>978-3-540-21200-3</json:string></isbn><volume>2992</volume><pages><first>237</first><last>255</last></pages><genre><json:string>book-series</json:string></genre><editor><json:item><name>Elisa Bertino</name><affiliations><json:string>Purdue University,</json:string><json:string>E-mail: bertino@cs.purdue.edu</json:string></affiliations></json:item><json:item><name>Stavros Christodoulakis</name><affiliations><json:string>Laboratory of Distributed Multimedia Information Systems and Applications, Technical University of Crete (MUSIC/TUC) Chania, 73100, Crete, Greece</json:string><json:string>E-mail: stavros@ced.tuc.gr</json:string></affiliations></json:item><json:item><name>Dimitris Plexousakis</name><affiliations><json:string>Institute of Computer Science, FO.R.T.H., Vassilika Vouton, P.O. Box 1385, GR 71110, Heraklion, Greece</json:string><json:string>E-mail: dp@ics.forth.gr</json:string></affiliations></json:item><json:item><name>Vassilis Christophides</name><affiliations><json:string>Department of Computer Science, University of Crete, P.O.Box 2208, GR 71409, Heraklion, Greece</json:string><json:string>E-mail: christop@ics.forth.gr</json:string></affiliations></json:item><json:item><name>Manolis Koubarakis</name><affiliations><json:string>National and Kapodistrian University of Athens, Greece</json:string><json:string>E-mail: koubarak@di.uoa.gr</json:string></affiliations></json:item><json:item><name>Klemens Böhm</name><affiliations><json:string>IPD, Universität Karlsruhe, Am Fasanengarten 5, 76131, Karlsruhe,</json:string><json:string>E-mail: boehm@ipd.uka.de</json:string></affiliations></json:item><json:item><name>Elena Ferrari</name><affiliations><json:string>Department of Computer Science and Communication, University of Insubria, 22100, Varese, Italy</json:string><json:string>E-mail: elena.ferrari@uninsubria.it</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Database Management</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Information Storage and Retrieval</value></json:item><json:item><value>Information Systems Applications (incl.Internet)</value></json:item><json:item><value>Computers and Society</value></json:item><json:item><value>Business Information Systems</value></json:item></subject></host><categories><inist><json:string>sciences appliquees, technologies et medecines</json:string><json:string>sciences exactes et technologie</json:string><json:string>terre, ocean, espace</json:string><json:string>sciences de la terre</json:string></inist></categories><publicationDate>2004</publicationDate><copyrightDate>2004</copyrightDate><doi><json:string>10.1007/978-3-540-24741-8_15</json:string></doi><id>EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9</id><score>1</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">HOPI: An Efficient Connection Index for Complex XML Document Collections</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2004</p></availability><date>2004</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">HOPI: An Efficient Connection Index for Complex XML Document Collections</title><author xml:id="author-0000"><persName><forename type="first">Ralf</forename><surname>Schenkel</surname></persName><email>schenkel@mpi-sb.mpg.de</email><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation></author><author xml:id="author-0001"><persName><forename type="first">Anja</forename><surname>Theobald</surname></persName><email>anja.theobald@mpi-sb.mpg.de</email><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation></author><author xml:id="author-0002"><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><email>weikum@mpi-sb.mpg.de</email><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation></author><idno type="istex">EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9</idno><idno type="DOI">10.1007/978-3-540-24741-8_15</idno><idno type="ChapterID">15</idno><idno type="ChapterID">Chap15</idno></analytic><monogr><title level="m">Advances in Database Technology - EDBT 2004</title><title level="m" type="sub">9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004</title><idno type="DOI">10.1007/b95855</idno><idno type="pISBN">978-3-540-21200-3</idno><idno type="eISBN">978-3-540-24741-8</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="book-title-ID">81801</idno><idno type="book-ID">978-3-540-24741-8</idno><idno type="book-chapter-count">62</idno><idno type="book-volume-number">2992</idno><idno type="book-sequence-number">2992</idno><idno type="PartChapterCount">3</idno><editor xml:id="book-author-0000"><persName><forename type="first">Elisa</forename><surname>Bertino</surname></persName><email>bertino@cs.purdue.edu</email><affiliation>Purdue University</affiliation></editor><editor xml:id="book-author-0001"><persName><forename type="first">Stavros</forename><surname>Christodoulakis</surname></persName><email>stavros@ced.tuc.gr</email><affiliation>Laboratory of Distributed Multimedia Information Systems and Applications, Technical University of Crete (MUSIC/TUC) Chania, 73100, Crete, Greece</affiliation></editor><editor xml:id="book-author-0002"><persName><forename type="first">Dimitris</forename><surname>Plexousakis</surname></persName><email>dp@ics.forth.gr</email><affiliation>Institute of Computer Science, FO.R.T.H., Vassilika Vouton, P.O. Box 1385, GR 71110, Heraklion, Greece</affiliation></editor><editor xml:id="book-author-0003"><persName><forename type="first">Vassilis</forename><surname>Christophides</surname></persName><email>christop@ics.forth.gr</email><affiliation>Department of Computer Science, University of Crete, P.O.Box 2208, GR 71409, Heraklion, Greece</affiliation></editor><editor xml:id="book-author-0004"><persName><forename type="first">Manolis</forename><surname>Koubarakis</surname></persName><email>koubarak@di.uoa.gr</email><affiliation>National and Kapodistrian University of Athens, Greece</affiliation></editor><editor xml:id="book-author-0005"><persName><forename type="first">Klemens</forename><surname>Böhm</surname></persName><email>boehm@ipd.uka.de</email><affiliation>IPD, Universität Karlsruhe, Am Fasanengarten 5, 76131, Karlsruhe</affiliation></editor><editor xml:id="book-author-0006"><persName><forename type="first">Elena</forename><surname>Ferrari</surname></persName><email>elena.ferrari@uninsubria.it</email><affiliation>Department of Computer Science and Communication, University of Insubria, 22100, Varese, Italy</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2004"></date><biblScope unit="volume">2992</biblScope><biblScope unit="page" from="237">237</biblScope><biblScope unit="page" to="255">255</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor xml:id="serie-author-0000"><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName><affiliation>Karlsruhe University, Germany</affiliation></editor><editor xml:id="serie-author-0001"><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName><affiliation>Cornell University, NY, USA</affiliation></editor><editor xml:id="serie-author-0002"><persName><forename type="first">Jan</forename><surname>van Leeuwen</surname></persName><affiliation>Utrecht University, The Netherlands</affiliation></editor><biblScope><date>2004</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2004</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: In this paper we present HOPI, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><item><term>Computer Science</term></item><label>I18024</label><item><term>Database Management</term></item><label>I13022</label><item><term>Computer Communication Networks</term></item><label>I18032</label><item><term>Information Storage and Retrieval</term></item><label>I18040</label><item><term>Information Systems Applications (incl.Internet)</term></item><label>I24040</label><item><term>Computers and Society</term></item><label>W26007</label><item><term>Business Information Systems</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2004">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Jan</GivenName><Particle>van</Particle><FamilyName>Leeuwen</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Karlsruhe University</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Cornell University</OrgName><OrgAddress><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>Utrecht University</OrgName><OrgAddress><Country>The Netherlands</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-24741-8</BookID><BookTitle>Advances in Database Technology - EDBT 2004</BookTitle><BookSubTitle>9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004</BookSubTitle><BookVolumeNumber>2992</BookVolumeNumber><BookSequenceNumber>2992</BookSequenceNumber><BookDOI>10.1007/b95855</BookDOI><BookTitleID>81801</BookTitleID><BookPrintISBN>978-3-540-21200-3</BookPrintISBN><BookElectronicISBN>978-3-540-24741-8</BookElectronicISBN><BookChapterCount>62</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2004</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I18024" Priority="1" Type="Secondary">Database Management</BookSubject><BookSubject Code="I13022" Priority="2" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I18032" Priority="3" Type="Secondary">Information Storage and Retrieval</BookSubject><BookSubject Code="I18040" Priority="4" Type="Secondary">Information Systems Applications (incl.Internet)</BookSubject><BookSubject Code="I24040" Priority="5" Type="Secondary">Computers and Society</BookSubject><BookSubject Code="W26007" Priority="6" Type="Secondary">Business Information Systems</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Elisa</GivenName><FamilyName>Bertino</FamilyName></EditorName><Contact><Email>bertino@cs.purdue.edu</Email></Contact></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Stavros</GivenName><FamilyName>Christodoulakis</FamilyName></EditorName><Contact><Email>stavros@ced.tuc.gr</Email></Contact></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>Dimitris</GivenName><FamilyName>Plexousakis</FamilyName></EditorName><Contact><Email>dp@ics.forth.gr</Email></Contact></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Vassilis</GivenName><FamilyName>Christophides</FamilyName></EditorName><Contact><Email>christop@ics.forth.gr</Email></Contact></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Manolis</GivenName><FamilyName>Koubarakis</FamilyName></EditorName><Contact><Email>koubarak@di.uoa.gr</Email></Contact></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>Klemens</GivenName><FamilyName>Böhm</FamilyName></EditorName><Contact><Email>boehm@ipd.uka.de</Email></Contact></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Elena</GivenName><FamilyName>Ferrari</FamilyName></EditorName><Contact><Email>elena.ferrari@uninsubria.it</Email></Contact></Editor><Affiliation ID="Aff4"><OrgName>Purdue University</OrgName><OrgAddress><Country> </Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgDivision>Laboratory of Distributed Multimedia Information Systems and Applications</OrgDivision><OrgName>Technical University of Crete (MUSIC/TUC) Chania</OrgName><OrgAddress><Postcode>73100</Postcode><City>Crete</City><Country>Greece</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgDivision>Institute of Computer Science</OrgDivision><OrgName>FO.R.T.H., Vassilika Vouton</OrgName><OrgAddress><Postbox>P.O. Box 1385</Postbox><Postcode>GR 71110</Postcode><City>Heraklion</City><Country>Greece</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>University of Crete</OrgName><OrgAddress><Postbox>P.O.Box 2208</Postbox><Postcode>GR 71409</Postcode><City>Heraklion</City><Country>Greece</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>National and Kapodistrian University of Athens</OrgName><OrgAddress><Country>Greece</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>IPD, Universität Karlsruhe</OrgName><OrgAddress><Street>Am Fasanengarten 5</Street><Postcode>76131</Postcode><City>Karlsruhe</City><Country> </Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgDivision>Department of Computer Science and Communication</OrgDivision><OrgName>University of Insubria</OrgName><OrgAddress><Postcode>22100</Postcode><City>Varese</City><Country>Italy</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part5"><PartInfo TocLevels="0"><PartID>5</PartID><PartSequenceNumber>5</PartSequenceNumber><PartTitle>Innovative Query Processing Techniques for XML Data</PartTitle><PartChapterCount>3</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Advances in Database Technology - EDBT 2004</BookTitle></PartContext></PartInfo><Chapter ID="Chap15" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>15</ChapterID><ChapterDOI>10.1007/978-3-540-24741-8_15</ChapterDOI><ChapterSequenceNumber>15</ChapterSequenceNumber><ChapterTitle Language="En">HOPI: An Efficient Connection Index for Complex XML Document Collections</ChapterTitle><ChapterFirstPage>237</ChapterFirstPage><ChapterLastPage>255</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2004</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>5</PartID><BookID>978-3-540-24741-8</BookID><BookTitle>Advances in Database Technology - EDBT 2004</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff11"><AuthorName DisplayOrder="Western"><GivenName>Ralf</GivenName><FamilyName>Schenkel</FamilyName></AuthorName><Contact><Email>schenkel@mpi-sb.mpg.de</Email><URL>http://www.mpi-sb.mpg.de/units/ag5/</URL></Contact></Author><Author AffiliationIDS="Aff11"><AuthorName DisplayOrder="Western"><GivenName>Anja</GivenName><FamilyName>Theobald</FamilyName></AuthorName><Contact><Email>anja.theobald@mpi-sb.mpg.de</Email><URL>http://www.mpi-sb.mpg.de/units/ag5/</URL></Contact></Author><Author AffiliationIDS="Aff11"><AuthorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></AuthorName><Contact><Email>weikum@mpi-sb.mpg.de</Email><URL>http://www.mpi-sb.mpg.de/units/ag5/</URL></Contact></Author><Affiliation ID="Aff11"><OrgName>Max Planck Institut für Informatik</OrgName><OrgAddress><City>Saarbrücken</City><Country>Germany</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>In this paper we present <Emphasis Type="Italic">HOPI</Emphasis>, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>HOPI: An Efficient Connection Index for Complex XML Document Collections</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>HOPI: An Efficient Connection Index for Complex XML Document Collections</title></titleInfo><name type="personal"><namePart type="given">Ralf</namePart><namePart type="family">Schenkel</namePart><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation><affiliation>E-mail: schenkel@mpi-sb.mpg.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Anja</namePart><namePart type="family">Theobald</namePart><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation><affiliation>E-mail: anja.theobald@mpi-sb.mpg.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max Planck Institut für Informatik, Saarbrücken, Germany</affiliation><affiliation>E-mail: weikum@mpi-sb.mpg.de</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2004</dateIssued><copyrightDate encoding="w3cdtf">2004</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: In this paper we present HOPI, a new connection index for XML documents based on the concept of the 2–hop cover of a directed graph introduced by Cohen et al. In contrast to most of the prior work on XML indexing we consider not only paths with child or parent relationships between the nodes, but also provide space– and time–efficient reachability tests along the ancestor, descendant, and link axes to support path expressions with wildcards in our XXL search engine. We improve the theoretical concept of a 2–hop cover by developing scalable methods for index creation on very large XML data collections with long paths and extensive cross–linkage. Our experiments show substantial savings in the query performance of the HOPI index over previously proposed index structures in combination with low space requirements.</abstract><relatedItem type="host"><titleInfo><title>Advances in Database Technology - EDBT 2004</title><subTitle>9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004</subTitle></titleInfo><name type="personal"><namePart type="given">Elisa</namePart><namePart type="family">Bertino</namePart><affiliation>Purdue University</affiliation><affiliation>E-mail: bertino@cs.purdue.edu</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Stavros</namePart><namePart type="family">Christodoulakis</namePart><affiliation>Laboratory of Distributed Multimedia Information Systems and Applications, Technical University of Crete (MUSIC/TUC) Chania, 73100, Crete, Greece</affiliation><affiliation>E-mail: stavros@ced.tuc.gr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dimitris</namePart><namePart type="family">Plexousakis</namePart><affiliation>Institute of Computer Science, FO.R.T.H., Vassilika Vouton, P.O. Box 1385, GR 71110, Heraklion, Greece</affiliation><affiliation>E-mail: dp@ics.forth.gr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Vassilis</namePart><namePart type="family">Christophides</namePart><affiliation>Department of Computer Science, University of Crete, P.O.Box 2208, GR 71409, Heraklion, Greece</affiliation><affiliation>E-mail: christop@ics.forth.gr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Manolis</namePart><namePart type="family">Koubarakis</namePart><affiliation>National and Kapodistrian University of Athens, Greece</affiliation><affiliation>E-mail: koubarak@di.uoa.gr</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Klemens</namePart><namePart type="family">Böhm</namePart><affiliation>IPD, Universität Karlsruhe, Am Fasanengarten 5, 76131, Karlsruhe</affiliation><affiliation>E-mail: boehm@ipd.uka.de</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Elena</namePart><namePart type="family">Ferrari</namePart><affiliation>Department of Computer Science and Communication, University of Insubria, 22100, Varese, Italy</affiliation><affiliation>E-mail: elena.ferrari@uninsubria.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2004</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I18024">Database Management</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I18032">Information Storage and Retrieval</topic><topic authority="SpringerSubjectCodes" authorityURI="I18040">Information Systems Applications (incl.Internet)</topic><topic authority="SpringerSubjectCodes" authorityURI="I24040">Computers and Society</topic><topic authority="SpringerSubjectCodes" authorityURI="W26007">Business Information Systems</topic></subject><identifier type="DOI">10.1007/b95855</identifier><identifier type="ISBN">978-3-540-21200-3</identifier><identifier type="eISBN">978-3-540-24741-8</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">81801</identifier><identifier type="BookID">978-3-540-24741-8</identifier><identifier type="BookChapterCount">62</identifier><identifier type="BookVolumeNumber">2992</identifier><identifier type="BookSequenceNumber">2992</identifier><identifier type="PartChapterCount">3</identifier><part><date>2004</date><detail type="part"><title>Innovative Query Processing Techniques for XML Data</title></detail><detail type="volume"><number>2992</number><caption>vol.</caption></detail><extent unit="pages"><start>237</start><end>255</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2004</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><affiliation>Karlsruhe University, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><affiliation>Cornell University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jan</namePart><namePart type="family">van Leeuwen</namePart><affiliation>Utrecht University, The Netherlands</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2004</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2004</recordOrigin></recordInfo></relatedItem><identifier type="istex">EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9</identifier><identifier type="DOI">10.1007/978-3-540-24741-8_15</identifier><identifier type="ChapterID">15</identifier><identifier type="ChapterID">Chap15</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2004</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2004</recordOrigin></recordInfo></mods></metadata></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Sarre/explor/MusicSarreV3/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001910 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001910 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Sarre
|area= MusicSarreV3
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:EF8BDDE90350CC3E6406E65AC136E9959B0FA3E9
|texte= HOPI: An Efficient Connection Index for Complex XML Document Collections
}}
| This area was generated with Dilib version V0.6.33. |  |