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.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 651) [ClassicSimilarity], result of:
       5.020828 = score(doc=651,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 651, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=651)
   

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

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 2880) [ClassicSimilarity], result of:
       5.020828 = score(doc=2880,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 2880, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=2880)
   

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

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 4468) [ClassicSimilarity], result of:
       5.020828 = score(doc=4468,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 4468, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=4468)
   

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

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 4805) [ClassicSimilarity], result of:
       5.020828 = score(doc=4805,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 4805, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=4805)
   

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

   5.020828 = sum of:
     5.020828 = weight(author_txt:nelson in 5611) [ClassicSimilarity], result of:
       5.020828 = score(doc=5611,freq=1.0), product of:
         0.99999994 = queryWeight, product of:
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.12448145 = queryNorm
         5.0208282 = fieldWeight in 5611, product of:
           1.0 = tf(freq=1.0), with freq of:
             1.0 = termFreq=1.0
           8.033325 = idf(docFreq=38, maxDocs=44218)
           0.625 = fieldNorm(doc=5611)
   

Similar documents (content)

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

   0.12236951 = sum of:
     0.12236951 = product of:
       1.019746 = sum of:
         0.031277753 = weight(abstract_txt:retrieval in 3510) [ClassicSimilarity], result of:
           0.031277753 = score(doc=3510,freq=2.0), product of:
             0.05091413 = queryWeight, product of:
               1.0165573 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.014412331 = queryNorm
             0.6143236 = fieldWeight in 3510, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.125 = fieldNorm(doc=3510)
         0.14219801 = weight(abstract_txt:keys in 3510) [ClassicSimilarity], result of:
           0.14219801 = score(doc=3510,freq=1.0), product of:
             0.13972592 = queryWeight, product of:
               1.1907928 = boost
               8.14154 = idf(docFreq=34, maxDocs=44218)
               0.014412331 = queryNorm
             1.0176924 = fieldWeight in 3510, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.14154 = idf(docFreq=34, maxDocs=44218)
               0.125 = fieldNorm(doc=3510)
         0.84627014 = weight(abstract_txt:hashing in 3510) [ClassicSimilarity], result of:
           0.84627014 = score(doc=3510,freq=3.0), product of:
             0.4008577 = queryWeight, product of:
               2.852383 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.014412331 = queryNorm
             2.1111486 = fieldWeight in 3510, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.125 = fieldNorm(doc=3510)
       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.11686106 = sum of:
     0.11686106 = product of:
       0.5843053 = sum of:
         0.015638877 = weight(abstract_txt:retrieval in 819) [ClassicSimilarity], result of:
           0.015638877 = score(doc=819,freq=2.0), product of:
             0.05091413 = queryWeight, product of:
               1.0165573 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.014412331 = queryNorm
             0.3071618 = fieldWeight in 819, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.0625 = fieldNorm(doc=819)
         0.028220631 = weight(abstract_txt:index in 819) [ClassicSimilarity], result of:
           0.028220631 = score(doc=819,freq=1.0), product of:
             0.09507999 = queryWeight, product of:
               1.389176 = boost
               4.74895 = idf(docFreq=1040, maxDocs=44218)
               0.014412331 = queryNorm
             0.29680938 = fieldWeight in 819, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.74895 = idf(docFreq=1040, maxDocs=44218)
               0.0625 = fieldNorm(doc=819)
         0.17258516 = weight(abstract_txt:update in 819) [ClassicSimilarity], result of:
           0.17258516 = score(doc=819,freq=4.0), product of:
             0.20030583 = queryWeight, product of:
               2.0163202 = boost
               6.892866 = idf(docFreq=121, maxDocs=44218)
               0.014412331 = queryNorm
             0.86160827 = fieldWeight in 819, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               6.892866 = idf(docFreq=121, maxDocs=44218)
               0.0625 = fieldNorm(doc=819)
         0.29140463 = weight(abstract_txt:inverted in 819) [ClassicSimilarity], result of:
           0.29140463 = score(doc=819,freq=6.0), product of:
             0.24811813 = queryWeight, product of:
               2.2440987 = boost
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.014412331 = queryNorm
             1.1744592 = fieldWeight in 819, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.0625 = fieldNorm(doc=819)
         0.07645596 = weight(abstract_txt:fast in 819) [ClassicSimilarity], result of:
           0.07645596 = score(doc=819,freq=1.0), product of:
             0.21151894 = queryWeight, product of:
               2.5376573 = boost
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.014412331 = queryNorm
             0.36146152 = fieldWeight in 819, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.0625 = fieldNorm(doc=819)
       0.2 = coord(5/25)
   

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

   0.10199588 = sum of:
     0.10199588 = product of:
       0.63747424 = sum of:
         0.023458315 = weight(abstract_txt:retrieval in 3501) [ClassicSimilarity], result of:
           0.023458315 = score(doc=3501,freq=2.0), product of:
             0.05091413 = queryWeight, product of:
               1.0165573 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.014412331 = queryNorm
             0.4607427 = fieldWeight in 3501, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.09375 = fieldNorm(doc=3501)
         0.13288626 = weight(abstract_txt:disk in 3501) [ClassicSimilarity], result of:
           0.13288626 = score(doc=3501,freq=2.0), product of:
             0.12841542 = queryWeight, product of:
               1.1415799 = boost
               7.805067 = idf(docFreq=48, maxDocs=44218)
               0.014412331 = queryNorm
             1.0348154 = fieldWeight in 3501, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.805067 = idf(docFreq=48, maxDocs=44218)
               0.09375 = fieldNorm(doc=3501)
         0.11468394 = weight(abstract_txt:fast in 3501) [ClassicSimilarity], result of:
           0.11468394 = score(doc=3501,freq=1.0), product of:
             0.21151894 = queryWeight, product of:
               2.5376573 = boost
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.014412331 = queryNorm
             0.5421923 = fieldWeight in 3501, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.09375 = fieldNorm(doc=3501)
         0.36644572 = weight(abstract_txt:hashing in 3501) [ClassicSimilarity], result of:
           0.36644572 = score(doc=3501,freq=1.0), product of:
             0.4008577 = queryWeight, product of:
               2.852383 = boost
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.014412331 = queryNorm
             0.9141542 = fieldWeight in 3501, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               9.7509775 = idf(docFreq=6, maxDocs=44218)
               0.09375 = fieldNorm(doc=3501)
       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.076193206 = sum of:
     0.076193206 = product of:
       0.47620755 = sum of:
         0.061970416 = weight(abstract_txt:faster in 1029) [ClassicSimilarity], result of:
           0.061970416 = score(doc=1029,freq=1.0), product of:
             0.10987129 = queryWeight, product of:
               1.0559415 = boost
               7.2195506 = idf(docFreq=87, maxDocs=44218)
               0.014412331 = queryNorm
             0.56402737 = fieldWeight in 1029, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.2195506 = idf(docFreq=87, maxDocs=44218)
               0.078125 = fieldNorm(doc=1029)
         0.06109946 = weight(abstract_txt:index in 1029) [ClassicSimilarity], result of:
           0.06109946 = score(doc=1029,freq=3.0), product of:
             0.09507999 = queryWeight, product of:
               1.389176 = boost
               4.74895 = idf(docFreq=1040, maxDocs=44218)
               0.014412331 = queryNorm
             0.64261115 = fieldWeight in 1029, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               4.74895 = idf(docFreq=1040, maxDocs=44218)
               0.078125 = fieldNorm(doc=1029)
         0.25756773 = weight(abstract_txt:inverted in 1029) [ClassicSimilarity], result of:
           0.25756773 = score(doc=1029,freq=3.0), product of:
             0.24811813 = queryWeight, product of:
               2.2440987 = boost
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.014412331 = queryNorm
             1.0380851 = fieldWeight in 1029, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.078125 = fieldNorm(doc=1029)
         0.095569946 = weight(abstract_txt:fast in 1029) [ClassicSimilarity], result of:
           0.095569946 = score(doc=1029,freq=1.0), product of:
             0.21151894 = queryWeight, product of:
               2.5376573 = boost
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.014412331 = queryNorm
             0.4518269 = fieldWeight in 1029, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7833843 = idf(docFreq=369, maxDocs=44218)
               0.078125 = fieldNorm(doc=1029)
       0.16 = coord(4/25)
   

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

   0.07384988 = sum of:
     0.07384988 = product of:
       0.46156177 = sum of:
         0.019352123 = weight(abstract_txt:retrieval in 4715) [ClassicSimilarity], result of:
           0.019352123 = score(doc=4715,freq=1.0), product of:
             0.05091413 = queryWeight, product of:
               1.0165573 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.014412331 = queryNorm
             0.38009337 = fieldWeight in 4715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.109375 = fieldNorm(doc=4715)
         0.09937342 = weight(abstract_txt:compression in 4715) [ClassicSimilarity], result of:
           0.09937342 = score(doc=4715,freq=1.0), product of:
             0.120278895 = queryWeight, product of:
               1.1048223 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.014412331 = queryNorm
             0.82619166 = fieldWeight in 4715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.109375 = fieldNorm(doc=4715)
         0.1346467 = weight(abstract_txt:dictionary in 4715) [ClassicSimilarity], result of:
           0.1346467 = score(doc=4715,freq=1.0), product of:
             0.18555945 = queryWeight, product of:
               1.9406815 = boost
               6.634292 = idf(docFreq=157, maxDocs=44218)
               0.014412331 = queryNorm
             0.7256257 = fieldWeight in 4715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.634292 = idf(docFreq=157, maxDocs=44218)
               0.109375 = fieldNorm(doc=4715)
         0.20818952 = weight(abstract_txt:inverted in 4715) [ClassicSimilarity], result of:
           0.20818952 = score(doc=4715,freq=1.0), product of:
             0.24811813 = queryWeight, product of:
               2.2440987 = boost
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.014412331 = queryNorm
             0.8390742 = fieldWeight in 4715, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.6715355 = idf(docFreq=55, maxDocs=44218)
               0.109375 = fieldNorm(doc=4715)
       0.16 = coord(4/25)