Document (#28394)

Author

Christophides, V.
Plexousakis, D.
Scholl, M.
Tourtounis, S.

Title

On labeling schemes for the Semantic Web

Source

http://www2003.org/cdrom/papers/refereed/p361/p361-christophides/p361-christophides.html

Year

2003

Abstract

This paper focuses on the optimization of the navigation through voluminous subsumption hierarchies of topics employed by Portal Catalogs like Netscape Open Directory (ODP). We advocate for the use of labeling schemes for modeling these hierarchies in order to efficiently answer queries such as subsumption check, descendants, ancestors or nearest common ancestor, which usually require costly transitive closure computations. We first give a qualitative comparison of three main families of schemes, namely bit vector, prefix and interval based schemes. We then show that two labeling schemes are good candidates for an efficient implementation of label querying using standard relational DBMS, namely, the Dewey Prefix scheme [6] and an Interval scheme by Agrawal, Borgida and Jagadish [1]. We compare their storage and query evaluation performance for the 16 ODP hierarchies using the PostgreSQL engine.

Footnote

Beitrag für: WWW2003, May 20--24, 2003, Budapest, Hungary.

Theme

Semantic Web
Auszeichnungssprachen

Object

RDF
DDC

Similar documents (content)

1. Tzitzikas, Y.; Spyratos, N.; Constantopoulos, P.; Analyti, A.: Extended faceted ontologies (2002) 0.08

   0.075314485 = sum of:
     0.075314485 = product of:
       0.47071552 = sum of:
         0.04959514 = weight(abstract_txt:scheme in 3280) [ClassicSimilarity], result of:
           0.04959514 = score(doc=3280,freq=1.0), product of:
             0.115697846 = queryWeight, product of:
               1.5166372 = boost
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.013903359 = queryNorm
             0.42866087 = fieldWeight in 3280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.078125 = fieldNorm(doc=3280)
         0.07551798 = weight(abstract_txt:namely in 3280) [ClassicSimilarity], result of:
           0.07551798 = score(doc=3280,freq=1.0), product of:
             0.15313205 = queryWeight, product of:
               1.744826 = boost
               6.312396 = idf(docFreq=218, maxDocs=44421)
               0.013903359 = queryNorm
             0.49315596 = fieldWeight in 3280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.312396 = idf(docFreq=218, maxDocs=44421)
               0.078125 = fieldNorm(doc=3280)
         0.21839462 = weight(abstract_txt:subsumption in 3280) [ClassicSimilarity], result of:
           0.21839462 = score(doc=3280,freq=1.0), product of:
             0.31083304 = queryWeight, product of:
               2.4858942 = boost
               8.993418 = idf(docFreq=14, maxDocs=44421)
               0.013903359 = queryNorm
             0.70261073 = fieldWeight in 3280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.993418 = idf(docFreq=14, maxDocs=44421)
               0.078125 = fieldNorm(doc=3280)
         0.12720777 = weight(abstract_txt:schemes in 3280) [ClassicSimilarity], result of:
           0.12720777 = score(doc=3280,freq=1.0), product of:
             0.2942309 = queryWeight, product of:
               3.824135 = boost
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.013903359 = queryNorm
             0.43233994 = fieldWeight in 3280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.078125 = fieldNorm(doc=3280)
       0.16 = coord(4/25)
   

2. Bergman, M.K..: Hierarchy in knowledge systems (2022) 0.05

   0.04902338 = sum of:
     0.04902338 = product of:
       0.61279225 = sum of:
         0.24708532 = weight(abstract_txt:subsumption in 2101) [ClassicSimilarity], result of:
           0.24708532 = score(doc=2101,freq=2.0), product of:
             0.31083304 = queryWeight, product of:
               2.4858942 = boost
               8.993418 = idf(docFreq=14, maxDocs=44421)
               0.013903359 = queryNorm
             0.7949133 = fieldWeight in 2101, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               8.993418 = idf(docFreq=14, maxDocs=44421)
               0.0625 = fieldNorm(doc=2101)
         0.36570692 = weight(abstract_txt:hierarchies in 2101) [ClassicSimilarity], result of:
           0.36570692 = score(doc=2101,freq=8.0), product of:
             0.29111308 = queryWeight, product of:
               2.9464262 = boost
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.013903359 = queryNorm
             1.2562367 = fieldWeight in 2101, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.0625 = fieldNorm(doc=2101)
       0.08 = coord(2/25)
   

3. SKOS Simple Knowledge Organization System Primer (2009) 0.04

   0.044700656 = sum of:
     0.044700656 = product of:
       0.3725055 = sum of:
         0.03967611 = weight(abstract_txt:scheme in 795) [ClassicSimilarity], result of:
           0.03967611 = score(doc=795,freq=1.0), product of:
             0.115697846 = queryWeight, product of:
               1.5166372 = boost
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.013903359 = queryNorm
             0.3429287 = fieldWeight in 795, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.4868593 = idf(docFreq=499, maxDocs=44421)
               0.0625 = fieldNorm(doc=795)
         0.12929691 = weight(abstract_txt:hierarchies in 795) [ClassicSimilarity], result of:
           0.12929691 = score(doc=795,freq=1.0), product of:
             0.29111308 = queryWeight, product of:
               2.9464262 = boost
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.013903359 = queryNorm
             0.44414672 = fieldWeight in 795, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.0625 = fieldNorm(doc=795)
         0.20353244 = weight(abstract_txt:schemes in 795) [ClassicSimilarity], result of:
           0.20353244 = score(doc=795,freq=4.0), product of:
             0.2942309 = queryWeight, product of:
               3.824135 = boost
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.013903359 = queryNorm
             0.6917439 = fieldWeight in 795, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.0625 = fieldNorm(doc=795)
       0.12 = coord(3/25)
   

4. Van der Walt, M.: ¬The structure of classification schemes used in Internet search engines (1998) 0.04

   0.040035658 = sum of:
     0.040035658 = product of:
       0.33363047 = sum of:
         0.060414385 = weight(abstract_txt:namely in 1084) [ClassicSimilarity], result of:
           0.060414385 = score(doc=1084,freq=1.0), product of:
             0.15313205 = queryWeight, product of:
               1.744826 = boost
               6.312396 = idf(docFreq=218, maxDocs=44421)
               0.013903359 = queryNorm
             0.39452475 = fieldWeight in 1084, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.312396 = idf(docFreq=218, maxDocs=44421)
               0.0625 = fieldNorm(doc=1084)
         0.12929691 = weight(abstract_txt:hierarchies in 1084) [ClassicSimilarity], result of:
           0.12929691 = score(doc=1084,freq=1.0), product of:
             0.29111308 = queryWeight, product of:
               2.9464262 = boost
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.013903359 = queryNorm
             0.44414672 = fieldWeight in 1084, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1063476 = idf(docFreq=98, maxDocs=44421)
               0.0625 = fieldNorm(doc=1084)
         0.14391917 = weight(abstract_txt:schemes in 1084) [ClassicSimilarity], result of:
           0.14391917 = score(doc=1084,freq=2.0), product of:
             0.2942309 = queryWeight, product of:
               3.824135 = boost
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.013903359 = queryNorm
             0.48913682 = fieldWeight in 1084, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.5339513 = idf(docFreq=476, maxDocs=44421)
               0.0625 = fieldNorm(doc=1084)
       0.12 = coord(3/25)
   

5. Morrow, G.; Swire-Thompson, B.; Montgomery Polny, J.; Kopec, M.; Wihbey, J.P.: ¬The emerging science of content labeling : contextualizing social media content moderation (2022) 0.04

   0.039143912 = sum of:
     0.039143912 = product of:
       0.4892989 = sum of:
         0.05686617 = weight(abstract_txt:label in 1661) [ClassicSimilarity], result of:
           0.05686617 = score(doc=1661,freq=1.0), product of:
             0.10059858 = queryWeight, product of:
               7.2355595 = idf(docFreq=86, maxDocs=44421)
               0.013903359 = queryNorm
             0.56527805 = fieldWeight in 1661, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.2355595 = idf(docFreq=86, maxDocs=44421)
               0.078125 = fieldNorm(doc=1661)
         0.43243274 = weight(abstract_txt:labeling in 1661) [ClassicSimilarity], result of:
           0.43243274 = score(doc=1661,freq=4.0), product of:
             0.3534451 = queryWeight, product of:
               3.2465768 = boost
               7.8302665 = idf(docFreq=47, maxDocs=44421)
               0.013903359 = queryNorm
             1.2234792 = fieldWeight in 1661, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.8302665 = idf(docFreq=47, maxDocs=44421)
               0.078125 = fieldNorm(doc=1661)
       0.08 = coord(2/25)