Document (#18496)

Author

Nelson, M.J.

Title

¬A prefix trie index for inverted files

Source

Information processing and management. 33(1997) no.6, S.739-744

Year

1997

Abstract

A prefix trie index is applied to the problem of providing fast search times, fast load times and fast update properties in a bibliographic or full text retrieval system. For all but the largest dictionaries a single key search in the dictionary under trie hashing takes exactly 1 disk read. Front compression of search keys is used to enhance performance. Analyzes partial combining of the postings into the dictionary as a method to give both faster retrieval and improved update properties for the trie hashing inverted file. Gives statistics for a test database consisting of an online catalogue at the Graduate School of Library and Information Science Library of the University of Western Ontario, Canada. Tests the effect of changing various parameters of prefix tries in this application

Similar documents (author)

1. Nelson, M.J.: Correlation of term usage and term indexing frequencies (1988) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 650) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 650, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=650)
   

2. Nelson, M.G.: Catalogers as librarians (1986) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 2879) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 2879, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=2879)
   

3. Nelson, T.H.: ¬A file structure for the complex, the changing, and the indeterminate (1965) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 4467) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 4467, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=4467)
   

4. Nelson, M.J.: ¬The design of a hypertext interface for information retrieval (1991) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 4804) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 4804, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=4804)
   

5. Nelson, S.J.: From meaning to term : semantic locality in the UMLS metathesaurus (1992) 5.02

   5.023691 = sum of:
     5.023691 = weight(author_txt:nelson in 5610) [ClassicSimilarity], result of:
       5.023691 = fieldWeight in 5610, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         8.037906 = idf(docFreq=38, maxDocs=44421)
         0.625 = fieldNorm(doc=5610)
   

Similar documents (content)

1. Wartik, S.; Fox, E.; Heath, L.; Chen, Q.-F.: Hashing algorithms (1992) 0.12

   0.12246547 = sum of:
     0.12246547 = product of:
       1.0205456 = sum of:
         0.031293966 = weight(abstract_txt:retrieval in 4510) [ClassicSimilarity], result of:
           0.031293966 = score(doc=4510,freq=2.0), product of:
             0.050920583 = queryWeight, product of:
               1.0162746 = boost
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.014412524 = queryNorm
             0.6145642 = fieldWeight in 4510, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.125 = fieldNorm(doc=4510)
         0.14234465 = weight(abstract_txt:keys in 4510) [ClassicSimilarity], result of:
           0.14234465 = score(doc=4510,freq=1.0), product of:
             0.13979138 = queryWeight, product of:
               1.190665 = boost
               8.146119 = idf(docFreq=34, maxDocs=44421)
               0.014412524 = queryNorm
             1.0182649 = fieldWeight in 4510, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.146119 = idf(docFreq=34, maxDocs=44421)
               0.125 = fieldNorm(doc=4510)
         0.84690696 = weight(abstract_txt:hashing in 4510) [ClassicSimilarity], result of:
           0.84690696 = score(doc=4510,freq=3.0), product of:
             0.40097106 = queryWeight, product of:
               2.851812 = boost
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.014412524 = queryNorm
             2.11214 = fieldWeight in 4510, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.125 = fieldNorm(doc=4510)
       0.12 = coord(3/25)
   

2. MacFarlane, A.; McCann, J.A.; Robertson, S.E.: Parallel methods for the update of partitioned inverted files (2007) 0.12

   0.116834916 = sum of:
     0.116834916 = product of:
       0.5841746 = sum of:
         0.015646983 = weight(abstract_txt:retrieval in 1819) [ClassicSimilarity], result of:
           0.015646983 = score(doc=1819,freq=2.0), product of:
             0.050920583 = queryWeight, product of:
               1.0162746 = boost
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.014412524 = queryNorm
             0.3072821 = fieldWeight in 1819, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.0625 = fieldNorm(doc=1819)
         0.028215393 = weight(abstract_txt:index in 1819) [ClassicSimilarity], result of:
           0.028215393 = score(doc=1819,freq=1.0), product of:
             0.09504742 = queryWeight, product of:
               1.3884637 = boost
               4.7496953 = idf(docFreq=1044, maxDocs=44421)
               0.014412524 = queryNorm
             0.29685596 = fieldWeight in 1819, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.7496953 = idf(docFreq=1044, maxDocs=44421)
               0.0625 = fieldNorm(doc=1819)
         0.17220311 = weight(abstract_txt:update in 1819) [ClassicSimilarity], result of:
           0.17220311 = score(doc=1819,freq=4.0), product of:
             0.19996636 = queryWeight, product of:
               2.013923 = boost
               6.889283 = idf(docFreq=122, maxDocs=44421)
               0.014412524 = queryNorm
             0.8611604 = fieldWeight in 1819, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               6.889283 = idf(docFreq=122, maxDocs=44421)
               0.0625 = fieldNorm(doc=1819)
         0.2917354 = weight(abstract_txt:inverted in 1819) [ClassicSimilarity], result of:
           0.2917354 = score(doc=1819,freq=6.0), product of:
             0.24825153 = queryWeight, product of:
               2.2439353 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014412524 = queryNorm
             1.1751605 = fieldWeight in 1819, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.0625 = fieldNorm(doc=1819)
         0.076373674 = weight(abstract_txt:fast in 1819) [ClassicSimilarity], result of:
           0.076373674 = score(doc=1819,freq=1.0), product of:
             0.21132092 = queryWeight, product of:
               2.535603 = boost
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.014412524 = queryNorm
             0.36141086 = fieldWeight in 1819, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.0625 = fieldNorm(doc=1819)
       0.2 = coord(5/25)
   

3. Ford, D.A.; Christodoukalis, S.: File organizations for optical disks (1992) 0.10

   0.10204567 = sum of:
     0.10204567 = product of:
       0.63778543 = sum of:
         0.023470474 = weight(abstract_txt:retrieval in 4501) [ClassicSimilarity], result of:
           0.023470474 = score(doc=4501,freq=2.0), product of:
             0.050920583 = queryWeight, product of:
               1.0162746 = boost
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.014412524 = queryNorm
             0.46092314 = fieldWeight in 4501, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.09375 = fieldNorm(doc=4501)
         0.13303298 = weight(abstract_txt:disk in 4501) [ClassicSimilarity], result of:
           0.13303298 = score(doc=4501,freq=2.0), product of:
             0.1284818 = queryWeight, product of:
               1.141485 = boost
               7.809647 = idf(docFreq=48, maxDocs=44421)
               0.014412524 = queryNorm
             1.0354227 = fieldWeight in 4501, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.809647 = idf(docFreq=48, maxDocs=44421)
               0.09375 = fieldNorm(doc=4501)
         0.114560515 = weight(abstract_txt:fast in 4501) [ClassicSimilarity], result of:
           0.114560515 = score(doc=4501,freq=1.0), product of:
             0.21132092 = queryWeight, product of:
               2.535603 = boost
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.014412524 = queryNorm
             0.5421163 = fieldWeight in 4501, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.09375 = fieldNorm(doc=4501)
         0.36672148 = weight(abstract_txt:hashing in 4501) [ClassicSimilarity], result of:
           0.36672148 = score(doc=4501,freq=1.0), product of:
             0.40097106 = queryWeight, product of:
               2.851812 = boost
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.014412524 = queryNorm
             0.91458344 = fieldWeight in 4501, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.755557 = idf(docFreq=6, maxDocs=44421)
               0.09375 = fieldNorm(doc=4501)
       0.16 = coord(4/25)
   

4. Carterette, B.; Can, F.: Comparing inverted files and signature files for searching a large lexicon (2005) 0.08

   0.07623407 = sum of:
     0.07623407 = product of:
       0.47646296 = sum of:
         0.062047694 = weight(abstract_txt:faster in 2029) [ClassicSimilarity], result of:
           0.062047694 = score(doc=2029,freq=1.0), product of:
             0.10993856 = queryWeight, product of:
               1.0559039 = boost
               7.2241306 = idf(docFreq=87, maxDocs=44421)
               0.014412524 = queryNorm
             0.5643852 = fieldWeight in 2029, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.2241306 = idf(docFreq=87, maxDocs=44421)
               0.078125 = fieldNorm(doc=2029)
         0.06108812 = weight(abstract_txt:index in 2029) [ClassicSimilarity], result of:
           0.06108812 = score(doc=2029,freq=3.0), product of:
             0.09504742 = queryWeight, product of:
               1.3884637 = boost
               4.7496953 = idf(docFreq=1044, maxDocs=44421)
               0.014412524 = queryNorm
             0.642712 = fieldWeight in 2029, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.7496953 = idf(docFreq=1044, maxDocs=44421)
               0.078125 = fieldNorm(doc=2029)
         0.25786006 = weight(abstract_txt:inverted in 2029) [ClassicSimilarity], result of:
           0.25786006 = score(doc=2029,freq=3.0), product of:
             0.24825153 = queryWeight, product of:
               2.2439353 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014412524 = queryNorm
             1.0387049 = fieldWeight in 2029, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.078125 = fieldNorm(doc=2029)
         0.09546709 = weight(abstract_txt:fast in 2029) [ClassicSimilarity], result of:
           0.09546709 = score(doc=2029,freq=1.0), product of:
             0.21132092 = queryWeight, product of:
               2.535603 = boost
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.014412524 = queryNorm
             0.45176357 = fieldWeight in 2029, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7825737 = idf(docFreq=371, maxDocs=44421)
               0.078125 = fieldNorm(doc=2029)
       0.16 = coord(4/25)
   

5. Robertson, A.M.; Willett, P.: Applications of n-grams in textual information systems (1998) 0.07

   0.07393827 = sum of:
     0.07393827 = product of:
       0.4621142 = sum of:
         0.019362155 = weight(abstract_txt:retrieval in 5715) [ClassicSimilarity], result of:
           0.019362155 = score(doc=5715,freq=1.0), product of:
             0.050920583 = queryWeight, product of:
               1.0162746 = boost
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.014412524 = queryNorm
             0.3802422 = fieldWeight in 5715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.4765 = idf(docFreq=3732, maxDocs=44421)
               0.109375 = fieldNorm(doc=5715)
         0.09948898 = weight(abstract_txt:compression in 5715) [ClassicSimilarity], result of:
           0.09948898 = score(doc=5715,freq=1.0), product of:
             0.12034579 = queryWeight, product of:
               1.1047521 = boost
               7.558333 = idf(docFreq=62, maxDocs=44421)
               0.014412524 = queryNorm
             0.82669264 = fieldWeight in 5715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.558333 = idf(docFreq=62, maxDocs=44421)
               0.109375 = fieldNorm(doc=5715)
         0.13483725 = weight(abstract_txt:dictionary in 5715) [ClassicSimilarity], result of:
           0.13483725 = score(doc=5715,freq=1.0), product of:
             0.18569385 = queryWeight, product of:
               1.9407212 = boost
               6.6388726 = idf(docFreq=157, maxDocs=44421)
               0.014412524 = queryNorm
             0.7261267 = fieldWeight in 5715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.6388726 = idf(docFreq=157, maxDocs=44421)
               0.109375 = fieldNorm(doc=5715)
         0.20842582 = weight(abstract_txt:inverted in 5715) [ClassicSimilarity], result of:
           0.20842582 = score(doc=5715,freq=1.0), product of:
             0.24825153 = queryWeight, product of:
               2.2439353 = boost
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.014412524 = queryNorm
             0.8395752 = fieldWeight in 5715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.676116 = idf(docFreq=55, maxDocs=44421)
               0.109375 = fieldNorm(doc=5715)
       0.16 = coord(4/25)