Document (#23706)

Author

Cannane, A.
Williams, H.E.

Title

General-purpose compression for efficient retrieval

Source

Journal of the American Society for Information Science and technology. 52(2001) no.5, S.430-437

Year

2001

Abstract

Compression of databases not only reduces space requirements but can also reduce overall retrieval times. In text databases, compression of documents based on semistatic modeling with words has been shown to be both practical and fast. Similarly, for specific applications -such as databases of integers or scientific databases-specially designed semistatic compression schemes work well. We propose a scheme for general-purpose compression that can be applied to all types of data stored in large collections. We describe our approach -which we call RAY-in detail, and show experimentally the compression available, compression and decompression costs, and performance as a stream and random-access technique. We show that, in many cases, RAY achieves better compression than an efficient Huffman scheme and popular adaptive compression techniques, and that it can be used as an efficient general-purpose compression scheme

Theme

Retrievalalgorithmen

Similar documents (author)

1. Williams, R.M.: ISI search network research front specialties (1983) 4.51

   4.512219 = sum of:
     4.512219 = weight(author_txt:williams in 1474) [ClassicSimilarity], result of:
       4.512219 = fieldWeight in 1474, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         7.2195506 = idf(docFreq=87, maxDocs=44218)
         0.625 = fieldNorm(doc=1474)
   

2. Williams, J.W.: Serials cataloging, 1985-1990 : an overview of a half-decade (1992) 4.51

   4.512219 = sum of:
     4.512219 = weight(author_txt:williams in 4207) [ClassicSimilarity], result of:
       4.512219 = fieldWeight in 4207, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         7.2195506 = idf(docFreq=87, maxDocs=44218)
         0.625 = fieldNorm(doc=4207)
   

3. Williams, D.A.: Information skills in the school curriculum (1991) 4.51

   4.512219 = sum of:
     4.512219 = weight(author_txt:williams in 4835) [ClassicSimilarity], result of:
       4.512219 = fieldWeight in 4835, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         7.2195506 = idf(docFreq=87, maxDocs=44218)
         0.625 = fieldNorm(doc=4835)
   

4. Williams, M.: Transparent information systems through gateways, front ends, intermediaries, and interfaces (1986) 4.51

   4.512219 = sum of:
     4.512219 = weight(author_txt:williams in 5135) [ClassicSimilarity], result of:
       4.512219 = fieldWeight in 5135, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         7.2195506 = idf(docFreq=87, maxDocs=44218)
         0.625 = fieldNorm(doc=5135)
   

5. Williams, F.: Appraisal and evaluation of software products (1992) 4.51

   4.512219 = sum of:
     4.512219 = weight(author_txt:williams in 5307) [ClassicSimilarity], result of:
       4.512219 = fieldWeight in 5307, product of:
         1.0 = tf(freq=1.0), with freq of:
           1.0 = termFreq=1.0
         7.2195506 = idf(docFreq=87, maxDocs=44218)
         0.625 = fieldNorm(doc=5307)
   

Similar documents (content)

1. Bell, T.C.; Moffat, A.; Nevill-Manning, C.G.; Witten, I.H.; Zobel, J.: Data compression in full-text retrieval system (1993) 0.30

   0.30088556 = sum of:
     0.30088556 = product of:
       1.2536899 = sum of:
         0.03776021 = weight(abstract_txt:stored in 5643) [ClassicSimilarity], result of:
           0.03776021 = score(doc=5643,freq=1.0), product of:
             0.06338378 = queryWeight, product of:
               1.0763363 = boost
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.009267128 = queryNorm
             0.5957393 = fieldWeight in 5643, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.3545527 = idf(docFreq=208, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
         0.0123516815 = weight(abstract_txt:retrieval in 5643) [ClassicSimilarity], result of:
           0.0123516815 = score(doc=5643,freq=1.0), product of:
             0.037912514 = queryWeight, product of:
               1.1772405 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.009267128 = queryNorm
             0.3257943 = fieldWeight in 5643, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
         0.008305621 = weight(abstract_txt:that in 5643) [ClassicSimilarity], result of:
           0.008305621 = score(doc=5643,freq=2.0), product of:
             0.026438309 = queryWeight, product of:
               1.2040274 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.009267128 = queryNorm
             0.314151 = fieldWeight in 5643, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
         0.025171956 = weight(abstract_txt:show in 5643) [ClassicSimilarity], result of:
           0.025171956 = score(doc=5643,freq=1.0), product of:
             0.060941037 = queryWeight, product of:
               1.4925498 = boost
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.009267128 = queryNorm
             0.4130543 = fieldWeight in 5643, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
         0.07152916 = weight(abstract_txt:databases in 5643) [ClassicSimilarity], result of:
           0.07152916 = score(doc=5643,freq=2.0), product of:
             0.12226081 = queryWeight, product of:
               2.989734 = boost
               4.4127526 = idf(docFreq=1456, maxDocs=44218)
               0.009267128 = queryNorm
             0.58505386 = fieldWeight in 5643, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.4127526 = idf(docFreq=1456, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
         1.0985713 = weight(abstract_txt:compression in 5643) [ClassicSimilarity], result of:
           1.0985713 = score(doc=5643,freq=3.0), product of:
             0.89564025 = queryWeight, product of:
               12.79457 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.009267128 = queryNorm
             1.2265766 = fieldWeight in 5643, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.09375 = fieldNorm(doc=5643)
       0.24 = coord(6/25)
   

2. Cheng, K.-S.; Young, G.H.; Wong, K.-F.: ¬A study on word-based and integral-bit Chinese text compression algorithms (1999) 0.23

   0.23051864 = sum of:
     0.23051864 = product of:
       1.4407415 = sum of:
         0.009689891 = weight(abstract_txt:that in 3056) [ClassicSimilarity], result of:
           0.009689891 = score(doc=3056,freq=2.0), product of:
             0.026438309 = queryWeight, product of:
               1.2040274 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.009267128 = queryNorm
             0.36650947 = fieldWeight in 3056, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.109375 = fieldNorm(doc=3056)
         0.029367283 = weight(abstract_txt:show in 3056) [ClassicSimilarity], result of:
           0.029367283 = score(doc=3056,freq=1.0), product of:
             0.060941037 = queryWeight, product of:
               1.4925498 = boost
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.009267128 = queryNorm
             0.48189667 = fieldWeight in 3056, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.109375 = fieldNorm(doc=3056)
         0.12001788 = weight(abstract_txt:scheme in 3056) [ClassicSimilarity], result of:
           0.12001788 = score(doc=3056,freq=2.0), product of:
             0.14153105 = queryWeight, product of:
               2.785771 = boost
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.009267128 = queryNorm
             0.84799683 = fieldWeight in 3056, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               5.4822793 = idf(docFreq=499, maxDocs=44218)
               0.109375 = fieldNorm(doc=3056)
         1.2816665 = weight(abstract_txt:compression in 3056) [ClassicSimilarity], result of:
           1.2816665 = score(doc=3056,freq=3.0), product of:
             0.89564025 = queryWeight, product of:
               12.79457 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.009267128 = queryNorm
             1.431006 = fieldWeight in 3056, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.109375 = fieldNorm(doc=3056)
       0.16 = coord(4/25)
   

3. Moffat, A.; Isal, R.Y.K.: Word-based text compression using the Burrows-Wheeler transform (2005) 0.20

   0.19943522 = sum of:
     0.19943522 = product of:
       0.99717605 = sum of:
         0.026664805 = weight(abstract_txt:modeling in 1044) [ClassicSimilarity], result of:
           0.026664805 = score(doc=1044,freq=1.0), product of:
             0.05675903 = queryWeight, product of:
               1.018536 = boost
               6.0133076 = idf(docFreq=293, maxDocs=44218)
               0.009267128 = queryNorm
             0.46978965 = fieldWeight in 1044, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.0133076 = idf(docFreq=293, maxDocs=44218)
               0.078125 = fieldNorm(doc=1044)
         0.02916449 = weight(abstract_txt:costs in 1044) [ClassicSimilarity], result of:
           0.02916449 = score(doc=1044,freq=1.0), product of:
             0.060253035 = queryWeight, product of:
               1.0494176 = boost
               6.195629 = idf(docFreq=244, maxDocs=44218)
               0.009267128 = queryNorm
             0.48403352 = fieldWeight in 1044, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.195629 = idf(docFreq=244, maxDocs=44218)
               0.078125 = fieldNorm(doc=1044)
         0.004894134 = weight(abstract_txt:that in 1044) [ClassicSimilarity], result of:
           0.004894134 = score(doc=1044,freq=1.0), product of:
             0.026438309 = queryWeight, product of:
               1.2040274 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.009267128 = queryNorm
             0.18511525 = fieldWeight in 1044, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.078125 = fieldNorm(doc=1044)
         0.020976631 = weight(abstract_txt:show in 1044) [ClassicSimilarity], result of:
           0.020976631 = score(doc=1044,freq=1.0), product of:
             0.060941037 = queryWeight, product of:
               1.4925498 = boost
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.009267128 = queryNorm
             0.3442119 = fieldWeight in 1044, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4059124 = idf(docFreq=1466, maxDocs=44218)
               0.078125 = fieldNorm(doc=1044)
         0.915476 = weight(abstract_txt:compression in 1044) [ClassicSimilarity], result of:
           0.915476 = score(doc=1044,freq=3.0), product of:
             0.89564025 = queryWeight, product of:
               12.79457 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.009267128 = queryNorm
             1.022147 = fieldWeight in 1044, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.078125 = fieldNorm(doc=1044)
       0.2 = coord(5/25)
   

4. Adiego, J.; Navarro, G.; Fuente, P. de la: Lempel-Ziv compression of highly structured documents (2007) 0.18

   0.1762568 = sum of:
     0.1762568 = product of:
       0.881284 = sum of:
         0.0386689 = weight(abstract_txt:random in 4993) [ClassicSimilarity], result of:
           0.0386689 = score(doc=4993,freq=2.0), product of:
             0.066975184 = queryWeight, product of:
               1.1064094 = boost
               6.532101 = idf(docFreq=174, maxDocs=44218)
               0.009267128 = queryNorm
             0.57736164 = fieldWeight in 4993, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.532101 = idf(docFreq=174, maxDocs=44218)
               0.0625 = fieldNorm(doc=4993)
         0.046440866 = weight(abstract_txt:adaptive in 4993) [ClassicSimilarity], result of:
           0.046440866 = score(doc=4993,freq=2.0), product of:
             0.07567276 = queryWeight, product of:
               1.1760579 = boost
               6.943297 = idf(docFreq=115, maxDocs=44218)
               0.009267128 = queryNorm
             0.6137065 = fieldWeight in 4993, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.943297 = idf(docFreq=115, maxDocs=44218)
               0.0625 = fieldNorm(doc=4993)
         0.0067815105 = weight(abstract_txt:that in 4993) [ClassicSimilarity], result of:
           0.0067815105 = score(doc=4993,freq=3.0), product of:
             0.026438309 = queryWeight, product of:
               1.2040274 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.009267128 = queryNorm
             0.2565032 = fieldWeight in 4993, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0625 = fieldNorm(doc=4993)
         0.057011835 = weight(abstract_txt:efficient in 4993) [ClassicSimilarity], result of:
           0.057011835 = score(doc=4993,freq=1.0), product of:
             0.15765211 = queryWeight, product of:
               2.9401495 = boost
               5.7860904 = idf(docFreq=368, maxDocs=44218)
               0.009267128 = queryNorm
             0.36163065 = fieldWeight in 4993, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               5.7860904 = idf(docFreq=368, maxDocs=44218)
               0.0625 = fieldNorm(doc=4993)
         0.73238087 = weight(abstract_txt:compression in 4993) [ClassicSimilarity], result of:
           0.73238087 = score(doc=4993,freq=3.0), product of:
             0.89564025 = queryWeight, product of:
               12.79457 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.009267128 = queryNorm
             0.8177177 = fieldWeight in 4993, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.0625 = fieldNorm(doc=4993)
       0.2 = coord(5/25)
   

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

   0.16434664 = sum of:
     0.16434664 = product of:
       0.58695227 = sum of:
         0.023331592 = weight(abstract_txt:costs in 9) [ClassicSimilarity], result of:
           0.023331592 = score(doc=9,freq=1.0), product of:
             0.060253035 = queryWeight, product of:
               1.0494176 = boost
               6.195629 = idf(docFreq=244, maxDocs=44218)
               0.009267128 = queryNorm
             0.38722682 = fieldWeight in 9, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.195629 = idf(docFreq=244, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.024410749 = weight(abstract_txt:reduce in 9) [ClassicSimilarity], result of:
           0.024410749 = score(doc=9,freq=1.0), product of:
             0.062096924 = queryWeight, product of:
               1.065354 = boost
               6.2897153 = idf(docFreq=222, maxDocs=44218)
               0.009267128 = queryNorm
             0.3931072 = fieldWeight in 9, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.2897153 = idf(docFreq=222, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.014262493 = weight(abstract_txt:retrieval in 9) [ClassicSimilarity], result of:
           0.014262493 = score(doc=9,freq=3.0), product of:
             0.037912514 = queryWeight, product of:
               1.1772405 = boost
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.009267128 = queryNorm
             0.37619486 = fieldWeight in 9, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               3.4751394 = idf(docFreq=3720, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.003915307 = weight(abstract_txt:that in 9) [ClassicSimilarity], result of:
           0.003915307 = score(doc=9,freq=1.0), product of:
             0.026438309 = queryWeight, product of:
               1.2040274 = boost
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.009267128 = queryNorm
             0.1480922 = fieldWeight in 9, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.3694751 = idf(docFreq=11241, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.064472675 = weight(abstract_txt:similarly in 9) [ClassicSimilarity], result of:
           0.064472675 = score(doc=9,freq=2.0), product of:
             0.0941723 = queryWeight, product of:
               1.3119596 = boost
               7.7456436 = idf(docFreq=51, maxDocs=44218)
               0.009267128 = queryNorm
             0.6846246 = fieldWeight in 9, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               7.7456436 = idf(docFreq=51, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.03371917 = weight(abstract_txt:databases in 9) [ClassicSimilarity], result of:
           0.03371917 = score(doc=9,freq=1.0), product of:
             0.12226081 = queryWeight, product of:
               2.989734 = boost
               4.4127526 = idf(docFreq=1456, maxDocs=44218)
               0.009267128 = queryNorm
             0.27579704 = fieldWeight in 9, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.4127526 = idf(docFreq=1456, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
         0.4228403 = weight(abstract_txt:compression in 9) [ClassicSimilarity], result of:
           0.4228403 = score(doc=9,freq=1.0), product of:
             0.89564025 = queryWeight, product of:
               12.79457 = boost
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.009267128 = queryNorm
             0.47210953 = fieldWeight in 9, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.5537524 = idf(docFreq=62, maxDocs=44218)
               0.0625 = fieldNorm(doc=9)
       0.28 = coord(7/25)