Document (#26680)

Author

Heinz, S.
Zobel, J.

Title

Efficient single-pass index construction for text databases

Source

Journal of the American Society for Information Science and technology. 54(2003) no.8, S.713-729

Year

2003

Abstract

Efficient construction of inverted indexes is essential to provision of search over large collections of text data. In this article, we review the principal approaches to inversion, analyze their theoretical cost, and present experimental results. We identify the drawbacks of existing inversion approaches and propose a single-pass inversion method that, in contrast to previous approaches, does not require the complete vocabulary of the indexed collection in main memory, can operate within limited resources, and does not sacrifice speed with high temporary storage requirements. We show that the performance of the single-pass approach can be improved by constructing inverted files in segments, reducing the cost of disk accesses during inversion of large volumes of data.

Theme

Retrievalalgorithmen

Similar documents (author)

1. Heinz, S.: Realisierung und Evaluierung eines virtuellen Bibliotheksregals für die Informationswissenschaft an der Universitätsbibliothek Hildesheim (2003) 2.07

   2.0709965 = sum of:
     2.0709965 = product of:
       4.141993 = sum of:
         4.141993 = weight(author_txt:heinz in 983) [ClassicSimilarity], result of:
           4.141993 = score(doc=983,freq=1.0), product of:
             0.7071068 = queryWeight, product of:
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.07544678 = queryNorm
             5.8576627 = fieldWeight in 983, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.625 = fieldNorm(doc=983)
       0.5 = coord(1/2)
   

2. Heinz, M.: Bemerkungen zur Entwicklung der Internationalität der Forschung : Bibliometrische Untersuchungen am SCI (2006) 2.07

   2.0709965 = sum of:
     2.0709965 = product of:
       4.141993 = sum of:
         4.141993 = weight(author_txt:heinz in 1111) [ClassicSimilarity], result of:
           4.141993 = score(doc=1111,freq=1.0), product of:
             0.7071068 = queryWeight, product of:
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.07544678 = queryNorm
             5.8576627 = fieldWeight in 1111, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.625 = fieldNorm(doc=1111)
       0.5 = coord(1/2)
   

3. Heinz, A.: ¬Diie Lösung des Leib-Seele-Problems bei John R. Searle (2002) 2.07

   2.0709965 = sum of:
     2.0709965 = product of:
       4.141993 = sum of:
         4.141993 = weight(author_txt:heinz in 300) [ClassicSimilarity], result of:
           4.141993 = score(doc=300,freq=1.0), product of:
             0.7071068 = queryWeight, product of:
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.07544678 = queryNorm
             5.8576627 = fieldWeight in 300, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.625 = fieldNorm(doc=300)
       0.5 = coord(1/2)
   

4. Großmann. R.; Heinz, M.: RAK-WB als Hypertext (1994) 1.66

   1.6567973 = sum of:
     1.6567973 = product of:
       3.3135946 = sum of:
         3.3135946 = weight(author_txt:heinz in 775) [ClassicSimilarity], result of:
           3.3135946 = score(doc=775,freq=1.0), product of:
             0.7071068 = queryWeight, product of:
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.07544678 = queryNorm
             4.68613 = fieldWeight in 775, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.5 = fieldNorm(doc=775)
       0.5 = coord(1/2)
   

5. Heinz, M.; Voigt, H.: Inhaltliche und formale Unzulänglichkeiten bei CD-ROMs : eine Gewichtung (1993) 1.66

   1.6567973 = sum of:
     1.6567973 = product of:
       3.3135946 = sum of:
         3.3135946 = weight(author_txt:heinz in 1422) [ClassicSimilarity], result of:
           3.3135946 = score(doc=1422,freq=1.0), product of:
             0.7071068 = queryWeight, product of:
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.07544678 = queryNorm
             4.68613 = fieldWeight in 1422, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.37226 = idf(docFreq=9, maxDocs=43254)
               0.5 = fieldNorm(doc=1422)
       0.5 = coord(1/2)
   

Similar documents (content)

1. Moffat, A.; Bell, T.A.H.: In situ generation of compressed inverted files (1995) 0.20

   0.19822644 = sum of:
     0.19822644 = product of:
       0.70795155 = sum of:
         0.06246671 = weight(abstract_txt:memory in 3717) [ClassicSimilarity], result of:
           0.06246671 = score(doc=3717,freq=1.0), product of:
             0.120923124 = queryWeight, product of:
               1.0821438 = boost
               6.61225 = idf(docFreq=157, maxDocs=43254)
               0.01689955 = queryNorm
             0.516582 = fieldWeight in 3717, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.61225 = idf(docFreq=157, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.016378498 = weight(abstract_txt:data in 3717) [ClassicSimilarity], result of:
           0.016378498 = score(doc=3717,freq=1.0), product of:
             0.06241222 = queryWeight, product of:
               1.0994617 = boost
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.01689955 = queryNorm
             0.26242453 = fieldWeight in 3717, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.028701968 = weight(abstract_txt:text in 3717) [ClassicSimilarity], result of:
           0.028701968 = score(doc=3717,freq=1.0), product of:
             0.09071826 = queryWeight, product of:
               1.3255395 = boost
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.01689955 = queryNorm
             0.31638578 = fieldWeight in 3717, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.18475918 = weight(abstract_txt:temporary in 3717) [ClassicSimilarity], result of:
           0.18475918 = score(doc=3717,freq=2.0), product of:
             0.19775963 = queryWeight, product of:
               1.3838822 = boost
               8.455969 = idf(docFreq=24, maxDocs=43254)
               0.01689955 = queryNorm
             0.9342614 = fieldWeight in 3717, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               8.455969 = idf(docFreq=24, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.06671678 = weight(abstract_txt:large in 3717) [ClassicSimilarity], result of:
           0.06671678 = score(doc=3717,freq=3.0), product of:
             0.11037479 = queryWeight, product of:
               1.4621106 = boost
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.01689955 = queryNorm
             0.60445666 = fieldWeight in 3717, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.07145363 = weight(abstract_txt:construction in 3717) [ClassicSimilarity], result of:
           0.07145363 = score(doc=3717,freq=1.0), product of:
             0.16663638 = queryWeight, product of:
               1.7965124 = boost
               5.4886365 = idf(docFreq=485, maxDocs=43254)
               0.01689955 = queryNorm
             0.42879972 = fieldWeight in 3717, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.4886365 = idf(docFreq=485, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
         0.27747476 = weight(abstract_txt:inverted in 3717) [ClassicSimilarity], result of:
           0.27747476 = score(doc=3717,freq=2.0), product of:
             0.3267578 = queryWeight, product of:
               2.5156965 = boost
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.01689955 = queryNorm
             0.8491757 = fieldWeight in 3717, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.078125 = fieldNorm(doc=3717)
       0.28 = coord(7/25)
   

2. Mukhopadhyay, S.; Peng, S.; Raje, R.; Mostafa, J.; Palakal, M.: Distributed multi-agent information filtering : a comparative study (2005) 0.16

   0.15692629 = sum of:
     0.15692629 = product of:
       0.56045103 = sum of:
         0.06158789 = weight(abstract_txt:speed in 5560) [ClassicSimilarity], result of:
           0.06158789 = score(doc=5560,freq=1.0), product of:
             0.11978631 = queryWeight, product of:
               1.0770451 = boost
               6.5810947 = idf(docFreq=162, maxDocs=43254)
               0.01689955 = queryNorm
             0.514148 = fieldWeight in 5560, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.5810947 = idf(docFreq=162, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.016378498 = weight(abstract_txt:data in 5560) [ClassicSimilarity], result of:
           0.016378498 = score(doc=5560,freq=1.0), product of:
             0.06241222 = queryWeight, product of:
               1.0994617 = boost
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.01689955 = queryNorm
             0.26242453 = fieldWeight in 5560, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.09881965 = weight(abstract_txt:drawbacks in 5560) [ClassicSimilarity], result of:
           0.09881965 = score(doc=5560,freq=1.0), product of:
             0.16417454 = queryWeight, product of:
               1.2609074 = boost
               7.704553 = idf(docFreq=52, maxDocs=43254)
               0.01689955 = queryNorm
             0.6019182 = fieldWeight in 5560, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.704553 = idf(docFreq=52, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.0770379 = weight(abstract_txt:large in 5560) [ClassicSimilarity], result of:
           0.0770379 = score(doc=5560,freq=4.0), product of:
             0.11037479 = queryWeight, product of:
               1.4621106 = boost
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.01689955 = queryNorm
             0.69796646 = fieldWeight in 5560, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.083706416 = weight(abstract_txt:efficient in 5560) [ClassicSimilarity], result of:
           0.083706416 = score(doc=5560,freq=1.0), product of:
             0.18517944 = queryWeight, product of:
               1.8938329 = boost
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.01689955 = queryNorm
             0.45202866 = fieldWeight in 5560, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.09160506 = weight(abstract_txt:approaches in 5560) [ClassicSimilarity], result of:
           0.09160506 = score(doc=5560,freq=2.0), product of:
             0.17867082 = queryWeight, product of:
               2.2783358 = boost
               4.640457 = idf(docFreq=1134, maxDocs=43254)
               0.01689955 = queryNorm
             0.51270294 = fieldWeight in 5560, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.640457 = idf(docFreq=1134, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
         0.1313156 = weight(abstract_txt:single in 5560) [ClassicSimilarity], result of:
           0.1313156 = score(doc=5560,freq=2.0), product of:
             0.22715288 = queryWeight, product of:
               2.5689168 = boost
               5.232305 = idf(docFreq=627, maxDocs=43254)
               0.01689955 = queryNorm
             0.57809347 = fieldWeight in 5560, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.232305 = idf(docFreq=627, maxDocs=43254)
               0.078125 = fieldNorm(doc=5560)
       0.28 = coord(7/25)
   

3. MacFarlane, A.; McCann, J.A.; Robertson, S.E.: Parallel methods for the generation of partitioned inverted files (2005) 0.12

   0.12119164 = sum of:
     0.12119164 = product of:
       0.5049652 = sum of:
         0.069678746 = weight(abstract_txt:speed in 1777) [ClassicSimilarity], result of:
           0.069678746 = score(doc=1777,freq=2.0), product of:
             0.11978631 = queryWeight, product of:
               1.0770451 = boost
               6.5810947 = idf(docFreq=162, maxDocs=43254)
               0.01689955 = queryNorm
             0.5816921 = fieldWeight in 1777, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.5810947 = idf(docFreq=162, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
         0.013102798 = weight(abstract_txt:data in 1777) [ClassicSimilarity], result of:
           0.013102798 = score(doc=1777,freq=1.0), product of:
             0.06241222 = queryWeight, product of:
               1.0994617 = boost
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.01689955 = queryNorm
             0.20993961 = fieldWeight in 1777, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.3590338 = idf(docFreq=4087, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
         0.039770614 = weight(abstract_txt:text in 1777) [ClassicSimilarity], result of:
           0.039770614 = score(doc=1777,freq=3.0), product of:
             0.09071826 = queryWeight, product of:
               1.3255395 = boost
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.01689955 = queryNorm
             0.438397 = fieldWeight in 1777, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
         0.043579217 = weight(abstract_txt:large in 1777) [ClassicSimilarity], result of:
           0.043579217 = score(doc=1777,freq=2.0), product of:
             0.11037479 = queryWeight, product of:
               1.4621106 = boost
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.01689955 = queryNorm
             0.39482942 = fieldWeight in 1777, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
         0.06696513 = weight(abstract_txt:efficient in 1777) [ClassicSimilarity], result of:
           0.06696513 = score(doc=1777,freq=1.0), product of:
             0.18517944 = queryWeight, product of:
               1.8938329 = boost
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.01689955 = queryNorm
             0.36162293 = fieldWeight in 1777, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
         0.27186865 = weight(abstract_txt:inverted in 1777) [ClassicSimilarity], result of:
           0.27186865 = score(doc=1777,freq=3.0), product of:
             0.3267578 = queryWeight, product of:
               2.5156965 = boost
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.01689955 = queryNorm
             0.83201885 = fieldWeight in 1777, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.0625 = fieldNorm(doc=1777)
       0.24 = coord(6/25)
   

4. Uratani, N.; Takeda, M.: ¬A fast string-searching algorithm for multiple patterns (1993) 0.11

   0.11395906 = sum of:
     0.11395906 = product of:
       0.71224415 = sum of:
         0.048708856 = weight(abstract_txt:text in 6275) [ClassicSimilarity], result of:
           0.048708856 = score(doc=6275,freq=2.0), product of:
             0.09071826 = queryWeight, product of:
               1.3255395 = boost
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.01689955 = queryNorm
             0.5369245 = fieldWeight in 6275, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.09375 = fieldNorm(doc=6275)
         0.1004477 = weight(abstract_txt:efficient in 6275) [ClassicSimilarity], result of:
           0.1004477 = score(doc=6275,freq=1.0), product of:
             0.18517944 = queryWeight, product of:
               1.8938329 = boost
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.01689955 = queryNorm
             0.5424344 = fieldWeight in 6275, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.785967 = idf(docFreq=360, maxDocs=43254)
               0.09375 = fieldNorm(doc=6275)
         0.11142498 = weight(abstract_txt:single in 6275) [ClassicSimilarity], result of:
           0.11142498 = score(doc=6275,freq=1.0), product of:
             0.22715288 = queryWeight, product of:
               2.5689168 = boost
               5.232305 = idf(docFreq=627, maxDocs=43254)
               0.01689955 = queryNorm
             0.49052858 = fieldWeight in 6275, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.232305 = idf(docFreq=627, maxDocs=43254)
               0.09375 = fieldNorm(doc=6275)
         0.45166257 = weight(abstract_txt:pass in 6275) [ClassicSimilarity], result of:
           0.45166257 = score(doc=6275,freq=1.0), product of:
             0.57748306 = queryWeight, product of:
               4.096006 = boost
               8.342641 = idf(docFreq=27, maxDocs=43254)
               0.01689955 = queryNorm
             0.7821226 = fieldWeight in 6275, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.342641 = idf(docFreq=27, maxDocs=43254)
               0.09375 = fieldNorm(doc=6275)
       0.16 = coord(4/25)
   

5. Moffat, A.; Zobel, J.: Self-indexing inverted files for fast text retrieval (1996) 0.10

   0.10184785 = sum of:
     0.10184785 = product of:
       0.50923926 = sum of:
         0.039435167 = weight(abstract_txt:indexed in 2010) [ClassicSimilarity], result of:
           0.039435167 = score(doc=2010,freq=1.0), product of:
             0.10326173 = queryWeight, product of:
               6.1103244 = idf(docFreq=260, maxDocs=43254)
               0.01689955 = queryNorm
             0.38189527 = fieldWeight in 2010, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.1103244 = idf(docFreq=260, maxDocs=43254)
               0.0625 = fieldNorm(doc=2010)
         0.03247257 = weight(abstract_txt:text in 2010) [ClassicSimilarity], result of:
           0.03247257 = score(doc=2010,freq=2.0), product of:
             0.09071826 = queryWeight, product of:
               1.3255395 = boost
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.01689955 = queryNorm
             0.35794964 = fieldWeight in 2010, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.049738 = idf(docFreq=2048, maxDocs=43254)
               0.0625 = fieldNorm(doc=2010)
         0.03081516 = weight(abstract_txt:large in 2010) [ClassicSimilarity], result of:
           0.03081516 = score(doc=2010,freq=1.0), product of:
             0.11037479 = queryWeight, product of:
               1.4621106 = boost
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.01689955 = queryNorm
             0.27918658 = fieldWeight in 2010, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.466985 = idf(docFreq=1349, maxDocs=43254)
               0.0625 = fieldNorm(doc=2010)
         0.09258947 = weight(abstract_txt:cost in 2010) [ClassicSimilarity], result of:
           0.09258947 = score(doc=2010,freq=2.0), product of:
             0.18241394 = queryWeight, product of:
               1.8796383 = boost
               5.7426 = idf(docFreq=376, maxDocs=43254)
               0.01689955 = queryNorm
             0.5075789 = fieldWeight in 2010, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.7426 = idf(docFreq=376, maxDocs=43254)
               0.0625 = fieldNorm(doc=2010)
         0.31392688 = weight(abstract_txt:inverted in 2010) [ClassicSimilarity], result of:
           0.31392688 = score(doc=2010,freq=4.0), product of:
             0.3267578 = queryWeight, product of:
               2.5156965 = boost
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.01689955 = queryNorm
             0.96073264 = fieldWeight in 2010, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               7.685861 = idf(docFreq=53, maxDocs=43254)
               0.0625 = fieldNorm(doc=2010)
       0.2 = coord(5/25)