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.07527745 = sum of:
     0.07527745 = product of:
       0.47048408 = sum of:
         0.049480237 = weight(abstract_txt:scheme in 2280) [ClassicSimilarity], result of:
           0.049480237 = score(doc=2280,freq=1.0), product of:
             0.11552623 = queryWeight, product of:
               1.5163312 = boost
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.013897138 = queryNorm
             0.42830306 = fieldWeight in 2280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.078125 = fieldNorm(doc=2280)
         0.07569703 = weight(abstract_txt:namely in 2280) [ClassicSimilarity], result of:
           0.07569703 = score(doc=2280,freq=1.0), product of:
             0.1533835 = queryWeight, product of:
               1.7472018 = boost
               6.31699 = idf(docFreq=216, maxDocs=44218)
               0.013897138 = queryNorm
             0.49351484 = fieldWeight in 2280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.31699 = idf(docFreq=216, maxDocs=44218)
               0.078125 = fieldNorm(doc=2280)
         0.21810158 = weight(abstract_txt:subsumption in 2280) [ClassicSimilarity], result of:
           0.21810158 = score(doc=2280,freq=1.0), product of:
             0.3105741 = queryWeight, product of:
               2.486202 = boost
               8.988837 = idf(docFreq=14, maxDocs=44218)
               0.013897138 = queryNorm
             0.7022529 = fieldWeight in 2280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.988837 = idf(docFreq=14, maxDocs=44218)
               0.078125 = fieldNorm(doc=2280)
         0.12720527 = weight(abstract_txt:schemes in 2280) [ClassicSimilarity], result of:
           0.12720527 = score(doc=2280,freq=1.0), product of:
             0.29424524 = queryWeight, product of:
               3.8262954 = boost
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.013897138 = queryNorm
             0.43231034 = fieldWeight in 2280, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.078125 = fieldNorm(doc=2280)
       0.16 = coord(4/25)
   

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

   0.04894575 = sum of:
     0.04894575 = product of:
       0.6118219 = sum of:
         0.24675377 = weight(abstract_txt:subsumption in 1099) [ClassicSimilarity], result of:
           0.24675377 = score(doc=1099,freq=2.0), product of:
             0.3105741 = queryWeight, product of:
               2.486202 = boost
               8.988837 = idf(docFreq=14, maxDocs=44218)
               0.013897138 = queryNorm
             0.79450846 = fieldWeight in 1099, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               8.988837 = idf(docFreq=14, maxDocs=44218)
               0.0625 = fieldNorm(doc=1099)
         0.3650681 = weight(abstract_txt:hierarchies in 1099) [ClassicSimilarity], result of:
           0.3650681 = score(doc=1099,freq=8.0), product of:
             0.290792 = queryWeight, product of:
               2.9463925 = boost
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.013897138 = queryNorm
             1.255427 = fieldWeight in 1099, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.0625 = fieldNorm(doc=1099)
       0.08 = coord(2/25)
   

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

   0.04466204 = sum of:
     0.04466204 = product of:
       0.37218368 = sum of:
         0.03958419 = weight(abstract_txt:scheme in 4795) [ClassicSimilarity], result of:
           0.03958419 = score(doc=4795,freq=1.0), product of:
             0.11552623 = queryWeight, product of:
               1.5163312 = boost
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.013897138 = queryNorm
             0.34264246 = fieldWeight in 4795, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.0625 = fieldNorm(doc=4795)
         0.12907107 = weight(abstract_txt:hierarchies in 4795) [ClassicSimilarity], result of:
           0.12907107 = score(doc=4795,freq=1.0), product of:
             0.290792 = queryWeight, product of:
               2.9463925 = boost
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.013897138 = queryNorm
             0.44386047 = fieldWeight in 4795, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.0625 = fieldNorm(doc=4795)
         0.20352842 = weight(abstract_txt:schemes in 4795) [ClassicSimilarity], result of:
           0.20352842 = score(doc=4795,freq=4.0), product of:
             0.29424524 = queryWeight, product of:
               3.8262954 = boost
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.013897138 = queryNorm
             0.6916965 = fieldWeight in 4795, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.0625 = fieldNorm(doc=4795)
       0.12 = coord(3/25)
   

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

   0.040025398 = sum of:
     0.040025398 = product of:
       0.333545 = sum of:
         0.060557622 = weight(abstract_txt:namely in 84) [ClassicSimilarity], result of:
           0.060557622 = score(doc=84,freq=1.0), product of:
             0.1533835 = queryWeight, product of:
               1.7472018 = boost
               6.31699 = idf(docFreq=216, maxDocs=44218)
               0.013897138 = queryNorm
             0.39481187 = fieldWeight in 84, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.31699 = idf(docFreq=216, maxDocs=44218)
               0.0625 = fieldNorm(doc=84)
         0.12907107 = weight(abstract_txt:hierarchies in 84) [ClassicSimilarity], result of:
           0.12907107 = score(doc=84,freq=1.0), product of:
             0.290792 = queryWeight, product of:
               2.9463925 = boost
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.013897138 = queryNorm
             0.44386047 = fieldWeight in 84, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.1017675 = idf(docFreq=98, maxDocs=44218)
               0.0625 = fieldNorm(doc=84)
         0.14391631 = weight(abstract_txt:schemes in 84) [ClassicSimilarity], result of:
           0.14391631 = score(doc=84,freq=2.0), product of:
             0.29424524 = queryWeight, product of:
               3.8262954 = boost
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.013897138 = queryNorm
             0.4891033 = fieldWeight in 84, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.533572 = idf(docFreq=474, maxDocs=44218)
               0.0625 = fieldNorm(doc=84)
       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.039081853 = sum of:
     0.039081853 = product of:
       0.4885232 = sum of:
         0.056768782 = weight(abstract_txt:label in 660) [ClassicSimilarity], result of:
           0.056768782 = score(doc=660,freq=1.0), product of:
             0.10048991 = queryWeight, product of:
               7.230979 = idf(docFreq=86, maxDocs=44218)
               0.013897138 = queryNorm
             0.56492025 = fieldWeight in 660, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.230979 = idf(docFreq=86, maxDocs=44218)
               0.078125 = fieldNorm(doc=660)
         0.4317544 = weight(abstract_txt:labeling in 660) [ClassicSimilarity], result of:
           0.4317544 = score(doc=660,freq=4.0), product of:
             0.35309726 = queryWeight, product of:
               3.246733 = boost
               7.825686 = idf(docFreq=47, maxDocs=44218)
               0.013897138 = queryNorm
             1.2227634 = fieldWeight in 660, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.825686 = idf(docFreq=47, maxDocs=44218)
               0.078125 = fieldNorm(doc=660)
       0.08 = coord(2/25)