Optimal weight assignment for signature generation.
Previous work on superimposed coding has been characterized by two aspects. First, it is generally assumed that signatures are generated from logical text blocks of the same size; that is, each block contains the same number of unique terms after stopword and duplicate removal. We call this approach the fixed-size block (FSB) method, since each text block has the same size, as measured by the number of unique terms contained in it. Second, with only a few exceptions [6,7,8,9,17], most previous work has assumed that each term in the text contributes the same number of ones to the signature (i.e., the weight of the term signatures is fixed). The main objective of this paper is to derive an optimal weight assignment that assigns weights to document terms according to  their occurrence and query frequencies in order to minimize the false-drop probability. The optimal scheme can account for both uniform and nonuniform occurence and query frequencies, and the signature generation method is still based on hashing rather than on table lookup. Furthermore, a new way of generating signatures, the fixed-weight block (FWB) method, is introduced. FWB controls the weight of every signature to a constant, whereas in FSB, only the expected signature weight is constant. We have shown that FWB has a lower false-drop probability than that of the FSB method, but its storage overhead is slightly  higher. Other advantages of FWB are that the optimal weight assignment can be obtained analytically without making unrealistic assumptions and that the formula for computing the term signature weights is simple and efficient.
Introduction
Many applications such as library systems and office automation systems must access to a
large amount of textual data. Since traditional database management systems are mainly
for handling formatted records, they have limited facilities for retrieving textual data. One
approach which has been widely studied as an efficient access method for text retrieval is
the signature file method [6,9,12]. A signature file has a storage overhead much smaller
than that of an inverted file. Its simple file structure facilitates database maintenance (e.g.,
fast insertion and deletion) as well as parallel search on special hardware [10] and general-purpose
parallel computers [19]. Also, it can support both text retrieval and multiattribute
retrieval in relational databases. However, signature files suffer from two drawbacks: (1)
They are slow compared to inverted files, and (2) they produce false drops; that is, the
signature file may identify a block as one satisfying the query but in fact it is not.
The first problem stems from the fact that the size of the signature file is proportional
to the size of the database. Thus, a straightforward, exhaustive, search algorithm on the
signature file will have a linear time complexity with respect to the database size, and the
performance will become a problem for large databases.
Many techniques have been proposed to improve the search performance of the signature
file. Storing the file as a transposed file [10,15] allows the system to retrieve only the bit slices
which are necessary to evaluate the query. Sophisticated file structures such as the two-level
and multi-level superimposed coding methods [2,3,11,16,17], the indexed descriptor
file method [14], and the partitioned signature file methods [12,13] have been proposed to
further improve the search speed. The general idea of these methods is to avoid searching
the whole signature file by using a nonsequential file structure, typically using tree search
or hashing techniques.
False drops introduced by the signature file also seriously degrade the system perfor-
mance. The problem is particularly acute for large databases, since the number of false
drops produced by a query is proportional to the number of unqualified documents. Thus,
when the size of the database is large and the query is highly selective (in the extreme case,
an unsuccessful search), the number of false drops will be very large even though the false
drop probability is small. Therefore, a substantial amount of efforts has been devoted to the
study of optimal algorithms for generating signatures from the text and to the estimation
of false drop probability [5,6].
In previous work on superimposed coding, it has generally been assumed that signatures
are generated from logical text blocks of the same size. That is, every logical text block
contains the same number of distinct terms after stopword removal. We call this approach
the fixed size block (FSB) method. Also, with only a few exceptions [7,8,9,16], most previous
work assumed that every term signature has the same weight (i.e., containing the same
number of 1's). In previous work, the condition that every signature is generated from the
same number of distinct terms is necessary for obtaining design parameters and evaluating
the false drop probabilities. The uniform weight assumption is clearly a simplification, and
there have been investigations on weight assignment methods that assign weights to terms
based on occurrence and query frequencies [8].
The main objective of this paper is to derive an optimal way of assigning weights to
document terms based on their occurrence and query frequencies to minimize the false drop
probability. Our optimal scheme can account for both uniform and nonuniform occurrence
and query frequencies. The signature generation method is still based on hashing rather
than table lookup [7]. We evaluate the performance of the optimal weight assignment
against the uniform weight assignment as well as two other assignment schemes.
Further, we introduce a new way of generating signatures, namely, the fixed weight
block method, in which the weight of every signature is controlled to a constant. In
the FSB method, only the expected signature weight is constant. Thus, the FWB method
is intuitively better than the FSB method, since there is a nonzero probability in the FSB
method for signatures with a large number of ones to be generated, thus increasing the
number of false drops. The FWB method completely eliminates this situation. We have
shown by analysis and simulation that the false drop probability of the FWB method is
indeed smaller than that of the FSB method, although its storage overhead is slightly higher.
Another advantage of the FWB method is that it allows an optimal weight assignment to
be obtained analytically without making unrealistic assumptions, mainly because of the
condition that every signature in FWB has the same weight.
In Section 2, we review the traditional signature file method and the term weight assignment
methods proposed in the literature. Then, a new blocking approach, the Fixed
Weight Block (FWB) method, is introduced. In Section 3, we obtain the optimal term
weight assignment based on the FWB method. The false drop probability and the storage
overhead of the optimal method is evaluated and compared to three other weight assignment
strategies. In Section 4, the performances of the FWB and FSB methods are evaluated and
compared. Both analytical and simulation results are presented in Section 3 and 4.

Overview

A signature file is basically a compressed version of a text. Thus, searching the signature file
is substantially faster than searching the text itself. However, the signature file approach
is different from traditional compression techniques (e.g., Huffman coding) in two major
aspects. First, the signature file typically allows information loss (i.e., the compression is
non-reversible) in order to achieve a good compression rate. Second, search on the signature
file must be efficient. In particular, a search must be able to start at any point in the
signature file. Traditional compression techniques, however, are reversible and emphasize
on compression rate rather than search time. Thus, the signature file method has in itself
many interesting research issues involving the organization and search techniques of the
signature file and the tradeoff between storage overhead and information loss.
There are many signature file techniques proposed in the literature [4,5]. In this section,
we provide an overview of the superimposed coding method, which is pertinent to the
understanding of this paper. A summary of important symbols frequently used in this
paper can be found in Table 1.
The typical steps involved in generating a signature is illustrated in Figure 1. The first
step is to hash each noncommon term (word) in the text into a fixed length bit string called
a term signature. Then, a number of term signatures are superimposed together to form
a block signature S i [20,21]. When a query is received, a query signature SQ is generated
in the same way and compared to every signature in the signature file. Figure 1 depicts
the three possible outcomes of a comparison: (1) a (true) match in which the text indeed
contains the query term; (2) a no-match indicating the text does not contain the query
match in which the block is identified as containing the query term
but in fact it is not. It can be observed that there are three steps involved in signature
generation: (1) to determine the number of 1's to set in a term signature; (2) to determine
the positions to be set; and (3) to determine the number of term signatures to superimpose
into a block signature. All these factors have influence on the false drop probability of the
signature file. Previous work typically assume that the weight (i.e., the number of 1's) of
every term signature is the same. Second, the bit positions are chosen randomly once the
term signature weight is determined. Finally, the number of unique terms in a block is fixed,
ith block in FWB approach
ith block in FSB approach
m length of a signature
number of blocks containing term i
number of blocks which do not contain term i
selected as a query
SQ query signature
T no. of distinct terms in a block
V the vocabulary size
number of ones (weight) of ith FWB block signature
summation of terms' weights in the ith FWB block
wBavg average weight of all the FWB blocks in database
Bavg average value of all the w
in database
wQ weight of query signature

Table

1: List of Symbols.
thus determining the number of term signatures to be superimposed into a block signature.
Methods in which block signatures are generated from logical text blocks containing the
same number of distinct terms are called fixed size block (FSB) methods.
Since false drops can seriously degrade the performance of a signature file, a lot of the
recent work has focused on reducing the false drop probability. Signature schemes which
have lower false drop probabilities than superimposed coding have been proposed [5,6].
000 010 101 001 signatures
{ { }
{
{
block signature

Figure

1: Generating signatures from a text block.
Using information theory, Faloutsos and Christodoulakis have established the relationship
between the information loss when signature extraction is performed and the false drop
probability of the signature file [7]. They also attempted to find an optimal signature
extraction method for assigning term signatures to document terms. For uniform occurrence
and query frequencies, they demonstrated that the optimal way was to assign the same
number of distinct terms to each signature. However, there are a few problems with their
results:
1. The optimal solution is based on a lookup table which maps terms in the vocabulary
to a pool of term signatures. An algorithm based on hashing is preferable.
2. For nonuniform occurrence and query frequencies, they only obtained a suboptimal
algorithm for mapping terms to term signatures.
3. They assumed that each text block contains only one term. Thus, they avoided
tackling the problem of false drops introduced when term signatures were combined
into block signatures (e.g., using superimposition). In other words, they only consider
the step of term signature assignment without considering the effect of combining
term signatures into block signatures.
Thus, although their study forms a very important first step toward a theoretical investigation
of term signature assignment method, much still needs to be done. In a different
report, Faloutsos and Christodoulakis proposed another assignment strategy which accounts
for nonuniform occurrence and query frequencies [8]. In their method, the set S of all possible
terms in the text file is partitioned into n classes S 1 , S 2 , \Delta \Delta \Delta, S n , such that S i 's are
disjoint and . Terms with occurrence frequencies falling into the same
range are assigned to the same class and to the same weight. The expected number of terms
in a block that are assigned to class j, D j , is assumed given. Thus, are known
and the expected number of distinct terms in a block is
. Given the query
frequencies, the length of the signatures, and , an optimal weight assignment
strategy for minimizing the false drop probability is obtained. However, a careful study of
their analysis reveals several undesirable assumptions:
1. The optimal weight assignment is obtained based on the expected value of D j 's without
considering the distribution of the D j values. Thus, the result is optimal only for "well-
behaved" distributions (e.g., when the value of D j for a specific class j is the same for
all block i). For real databases, in which the distribution may not be well-behaved,
the assignment strategy may deviate from the optimal point. It is necessary to include
the effect of the distribution in the analysis. Further, if D j 's are only expected values,
the sizes of the text blocks may be different from each other. This is contradictory to
the general condition that every block has a fixed size.
2. Their analysis requires the assumption that the weight for each block signature is
constant but in fact only the expected weight is fixed.
We can see that the problem mainly stems from the fact that the analysis is based on
expected values. When the input parameters are only expected values, there is no guarantee
that the result of the analysis can predict the general behaviors of a real system.
In this paper, we obtain an optimal weight assignment based on a new signature generation
technique in which the weights of the block signatures are controlled to a constant.
We call our method the fixed weight block method. The FWB method can be implemented
by generating term signatures from the text incrementally and superimposing them
into the block signature as they are generated until the block signature weight reaches the
pre-defined value. The terms used in generating the signature then form a logical block of
the document. An informal algorithm is given below:
1. Initialize count to zero and set the block signature to zeros;
2. Repeat the following steps until count - the pre-defined constant:
(a) Get next term from the document;
(b) Generate term signature and superimpose it into the block signature;
(c) Increment count by the number of new bit positions set in the block signature;
3. Output the block signature and logical text block; goto (1).
Observe that the final weight of the block signature may exceed the pre-defined constant,
but the deviation should not be large. Also duplicates are automatically eliminated. Note
that both the FSB and FWB methods yield variable-length physical text blocks. For the
FSB method, since only the number of unique terms in a block is fixed, the actual block
length is almost guaranteed to vary since a block may contain multiple occurrences of the
same term and common terms removed by a stop-word list. Hence, the FWB method is
not inferior than the FSB method in this aspect.
As discussed before, the FWB method intuitively produces fewer false drops than the
FSB method. This is because the FSB method may produce signatures with large weights
although the expected weight of all signatures remains fixed. The heavy signatures have
a higher chance to be retrieved as false drops, and thus increasing the overall false drop
probability. This can be easily observed by considering two signatures, one containing all
zeros and the other all ones. The false drop probability of these two signatures will be
much higher than that of two signatures with exactly one-half of the bits set. In the FWB
method, this situation is completely eliminated. Further, since the block signature weights
are constant in the FWB method, the analysis for obtaining the optimal weight assignment
for term signatures can be simplified, and the analysis is not dependent on expect values of
the parameters.
3 Optimal Weight Assignment
A good weight assignment scheme must satisfy the following three criteria:
ffl Since the occurrence frequencies in the database is nonuniform (e.g., natural-language
text follows the Zipf's law [18]), the assignment should take into account the occurrence
and query frequencies. It must be able to handle both uniform and nonuniform
occurrences and query frequencies, in such a way that the uniform case can be treated
as a special case in the formulation.
ffl The scheme must be optimal in minimizing the false drop probability.
ffl Lookup tables for direct mapping of terms into their signatures should be avoided.
For the last criterion, it must be noted that lookup tables are unavoidable for finding
the occurrence and query frequencies of a term (unless an approximation based on some
distribution function such as the Zipf's law must be used). If lookup tables are used to
directly obtain optimal signature assignments for the terms (as in [7]), the storage overhead
would be tremendous for any realistic environment, and lookup tables are inflexible for
changes. Thus, it is desirable to obtain signatures algorithmically once the occurrence and
query frequencies are known.
The problem of signature generation can be separated into two parts: (1) to determine
the weight of each term; and (2) to choose the positions to set in a signature after its weight
has been decided. In this section, we address the problem of weight assignment. Once the
weight is determined, the bit positions are chosen randomly. This avoids the use of lookup
table, and the optimal weight assignment can still be determined.
3.1 False Drop Probability
Our optimal solution is essentially different from the optimal solutions reported by Roberts
[15] and Faloutsos and Christodoulakis [8]. Their optimal solutions are based on the condition
that each block contains a fixed number of unique terms. For databases containing
the same number of unique terms, the size of the signature files (thus the overheads) are
the same. The optimization problem is to determine the term weight to minimize the false
drop probability. An optimal point exists since when the weight of a term signature in-
creases, there are two conflicting effects on the false drop probability. First, the weights of
the block signatures to which this term belongs will increase and thus increasing the false
drop probability; second, the false drop probability will decrease when the term is selected
as a query since more bits are set in the query signature. Hence, an optimal point can be
obtained at which the false drop probability is minimized. It turns out that the optimal
point is when the expected numbers of ones and zeros in the block signatures are the same.
Based on this condition, the term weight (assuming the same for every term) can be found
easily.
In our optimization method, we first determine what parameters must be fixed. To this
end, we define a parameter as monotone if and only if the false drop probability increases
or decreases monotonously with respect to this parameter. For example, the average term
weight is not monotone in the FSB approach since, as mentioned before, the false drop
probability could be increasing or decreasing with respect to it when the block size is
fixed. However, it is monotone in the FWB approach, because when the average term
weight increases the average query weight also increases, resulting in a smaller false drop
probability. However, increasing the average term signature weight would not increase the
block signature weight in FWB by definition. It only means fewer terms are included in
a signature. This will, of course, increase the storage overhead, which is a trade-off to be
determined at design time. Another monotone parameter is the signature length m. It is
monotone in both the FSB and FWB methods, since in both cases the false drop probability
decreases monotonously when m increases. It is obvious that all monotone parameters must
be fixed since there is no bounded optimal values for these parameters.
In this section, we obtain the optimal weight assignment based on the FWB approach.
The first theorem introduces a weight assignment to achieve an optimal false drop probability
when the monotone parameters are fixed. Moreover, our new optimal assignment
is more accurate than Faloutsos and Christodoulakis' method [8] in that it assigns each
individual term with a specific weight depending on its occurrence frequency and the query
probability, instead of assigning every term in a class with the same weight.
Let the query probability of term j be denoted by P (Q j ), then the expected false drop
probability is a product of the number of false drops under query Q j and the value P (Q j ).
Consequently, the overall performance, measured by the expected false drop probability
Ex, with respect to all the possible query terms can be expressed as
where fB i;j is the set of blocks which don't contain Q j , and V is the vocabulary
size. It may be argued that the value V should have been replaced with
where x is the number of terms that are too common to be used in a query. We use this
formulation later in Theorem 1. The equation can be simplified further to:
Since wB 1;j
We have observed that both m and wBavg are pre-defined constants for every i in the
FWB approach, since they are monotone parameters. Thus if we assume that the vocabulary
size is a constant, then the only parameters which could affect Ex are the query term weight
, 2 the query probability P (Q j ), and the number of blocks not containing Q j . That is,
the problem becomes one of deciding the value of wQ j
, in terms of P
that Ex is optimal. Of course, it is obvious that Ex becomes better when wQ j
increases.
However, a larger
will also imply a larger term weight and in turn a larger storage
overhead in the FWB method. Hence, the optimal solution should take into consideration
the fact that the storage overhead should be fixed (or the storage overhead is a pre-defined
constant) when comparing it with other weight assignment methods.
In the next theorem, an optimal solution is introduced under two restrictions. The
first restriction fixes the storage overhead of a weight assignment method and the second
restriction forces the sum of P (Q j ) to be 1. We represent these two restrictions with two
mathematical equations,
1.
2.
C is in fact the total number of ones produced by all of the terms (multiple occurrences
of a term are counted in the formula). It will be shown in Theorem 2 that the summation
of the first equation is the storage overhead of a weight assignment method; that is, the
storage overhead of a weight assignment method is fixed if its C value is fixed. Like other
signature methods, the storage overhead is always a design parameter in the sense that the
number of false drops will decrease if a larger storage overhead can be afforded. Thus, C is
a design parameter to be supplied by the designer.
Theorem 1 In the FWB method, if the storage overhead is fixed, then the optimal false drop
probability can be obtained when the weight of each term is related to the query probability,
the term frequency, and the number of blocks not containing the query as follows:
log d
log d
otherwise
2 The set of query terms are the same as the set of document terms (except for some common terms for
which P (Q j ) is zero). Since the weight of a term is the same as its query weight, we will obtain the term
weights by finding the query weights.
is the vocabulary size excluding terms with P
, and
Proof: In the FWB method,
is a constant for all i and is strictly less than m,
or
First, we consider the first two cases. That P will never be used in
a query. Further, when a term belongs to every block (i.e., blocks will qualify if
the term is used in the query. In either case, the term is useless and should not be encoded
in the signature file in order not to increase the false drop probability and the storage
overhead. Thus, terms in this class are assigned with zero weight. A term having f
means it is not contained in any block. Since it won't have any effect on the signature file, it
should be assigned a weight as large as possible (i.e., m) to reduce the false drop probability
when it is used in a query.
In order to find the optimal solution of Equation (1) under the following restrictions:
1.
2.
we use the Lagrange's method [1] to solve the optimization problem. First, we consider
variables formulated in a new function, \Phi, composed of Equation (1)
and the above two restrictions:
It is obvious that the function \Phi is first-order differentiable with respect to each of the t
variables. Our goal is to construct t +2 equations to obtain the values of the t +2 variables,
well as the relationship between wQ j
Using the Lagrange's method, there are t partial derivatives D j with respect to
the t variables wQ j
and the two restrictions:
The first t equations yield:
log d
log d
Substituting wQ j in the first restriction, we can obtain the value of log d (\Gamma- 1
log d (\Gamma- 1
log d (lnd)
Combining Equation (2) and (3), the proof can be obtained:
log d
log d
(4)Note that the second restriction (or - 2 ) is not used in the proof because it does not
contain any variable wQ j
. Since p j and f j depend on the occurrence frequency, the formula
accounts for both occurrence and query frequencies. The frequencies are usually obtained
from real databases or estimated from empirical laws. In particular, the Zipf's law can be
used to estimate the occurrence frequencies.
Theorem 1 not only develops a weight assignment that accounts for both uniform and
nonuniform occurrence and query frequencies but also proves that it is an optimal solution.
In addition, the term weights are computed from the occurrence and query frequencies
rather than lookup from a static table, and the computation is efficient since the first and
second terms in the formula can be pre-computed. Therefore, the weight assignment satisfies
the three criteria described at the beginning of this section.
Simulation. The false drop probability of the optimal weight assignment is compared with
the three methods below:
1. Linear Weight: All of the distinct terms are listed in descending order according to
their occurrence frequencies, and are equally partitioned into groups. The group containing
terms with highest occurrence frequencies is assigned with the largest weight,
the group with the second highest occurrence frequencies is assigned with the second
largest weight, and so on. The term weights are chosen to generate the desire
signature weight.
2. Uniform Weight: Each term is assigned with the same weight. This strategy typically
has been assumed in previous work on superimposed coding.
3. Inverse Linear Weight: This strategy is the same as the linear weight assignment,
except that the least frequent group is assigned with the largest weight while the
most frequent group is assigned with the smallest weight.
In the comparison, the value of
is set to the same value for all four methods.
Also, the query frequencies are assumed uniform in the simulation. The signature length m
is 1024 and the block signature weight is set to 312, 412, 512 612, and 712. Figure 2 shows
the results of the simulation. It is clear from the figure that the linear weight assignment
method is the worst and that our optimal method is almost an order of magnitude better
than the uniform weight assignment method.
Consider Equation (4) again. Intuitively, the first term, C
can be considered as the
weighted average term weight and is constant for every term. A frequent term, Q j , will have
a large number of blocks containing it (i.e., small p j and large f j ). When P (Q j ) is uniform
for all j, the last term in (4) yields negative values for frequent terms and positive values
for infrequent terms. Therefore, the optimal weight assignment is an inverse function of the
occurrence frequency. However, since the last term is a logarithm term, the inverse function
is not linear and should be closer to the uniform function than the inverse linear function.
When the query frequencies are nonuniform, the optimal weight assignment would deviate
further towards the inverse linear function when frequent terms are queried less frequently,
and move towards the uniform function when frequent terms are queried more frequently.
3.2 Storage Overhead
The primary result of Theorem 1 is that the optimal weight assignment is the best in terms
of false drop probability. However, false drop probabilities cannot be compared without
False Drop Rate in FWB
False Drop Rate0:01
0:03
0:04
0:06
0:07
2p Uniform
\Phip Linear
Optimal
Average Block Weight

Figure

2: False drop probability of the FWB approach.
reference to the storage overhead. Therefore, it is necessary to study the storage overhead
of this new method. In this section, we evaluate the storage overheads of the three different
weight assignments: (1) high occurrence terms are assigned with large weights, (2) uniform
weight assignment, and (3) low occurrence terms are assigned with large weights. These
three methods are similar to those in Section 3.1, but the first and third methods are not
necessarily linear.
Before introducing the theorem, some important notations are reviewed.
is the weight (number of 1's) of block signature S j which is superimposed from
the term signatures in the block.
ffl wBavg is defined as the average weight of all of the block signatures in the database.
is the weight of the ith term in the block B j , and T
stands for the block size (number of distinct terms).
Bavg represents the average value of w
for all of the B j .
For the example in Figure 1, the weight of block B i , which contains two terms free and text,
is 7 while the value of w
is 4+4=8. Consequently, we need to study the relationship of
two quantities, wB j
, to explore the distribution of 1's in each block. The problem
can be stated in the following lemma.
Given a block B j , the ratio of w
to wB j , denoted by -, depends only on wB j ,
when the following conditions are true:
1. bit positions to be set are chosen randomly;
2. the length of the block signature is fixed, namely, m;
3. the size of the text block B j is T , which is the same as the number of distinct words
in the block; and
4. w i;j , which represents the ith term's weight in block B j , is given for all
Proof: It is obvious that 1 \Gamma w i;j =m is the probability for a bit to be '0' in term i's
signature. Thus,
represents the probability of a bit to be '1' within the block signature as long as m AE w i;j .
Consequently, the expected weight for the block signature can be formulated as:
Finally, we may simplify the previous equation into:
Therefore, the ratio - is a constant as long as the block signature weight and the length
of the signature are fixed (i.e., FWB approach). More precisely, the ratio - can be formulated
as a function of wB j
, denoted by -(wB j
In particular, this ratio is independent of
the number of unique terms in a block, and the ratio approaches 1 when the length of a
signature is much greater than the expected weight of the block signature. 2
The main purpose for this lemma is to show that each FWB block signature contains
the same number of 1's (the same w
value), since wB j
is pre-defined and fixed for each
block. That is, the value of w
is a function of wB j ; it is fixed as long as wB j is fixed.
Therefore, the storage overhead can be evaluated based on this condition.
Theorem 2 In the FWB method, each text block signature has the same weight. Let wt (1)
and wt (2)
i be two weight assignments for a term i where . Then the storage
overhead for both weight assignments will be the same if and only if the following equation
holds:
Proof: During the proof of this theorem, an important assumption that each physical
block contains a term at most once must be observed (alternatively, multiple occurrences
of the same term are counted as one occurrence). Consequently, the term frequency f i can
be defined as the number of blocks in which the term appears:
Then the number of ones that a term contributes to the database will be the product of
term frequency f i and its weight. Hence, the total number of ones in the database will be
According to Lemma 1, each block B i requires the same number of individual ones, w
to yield the specific weight wB i
for all i. For the FWB approach, every wB i
Bavg . Therefore, the number of blocks can be obtained by dividing the total
number of ones in the database by w
Bavg . That is,
Number of
Bavg
Storage Overhead in FWB
Size of
Signature File8001200160020002400
qp
\Pip Inverse
2p Uniform
\Phip Linear
Optimal
Average Block Weight

Figure

3: Storage overhead of the FWB approach.
Then the storage overhead in the FWB method of two different weight assignments will
be the same, if

Figure

3 illustrates the storage overheads of the four methods in our simulation, obtained
with the same set of parameters as in Figure 2. The simulation results demonstrate that the
optimal weight assignment has much better performance in false drop probability than the
other three strategies when their storage overheads in the signature file are all the same.
4 Performance of the FWB and the FSB Methods
In this section, we analyze the FWB and FSB approaches in terms of their false drop probabilities
and storage overheads. We will demonstrate that the optimal weight assignment
developed for the FWB environment still maintains the lowest false drop probability compared
to other weight assignment methods in the FSB approach. The main idea of the
FWB approach is to fix the weight of each block signature instead of fixing the number
of unique terms in a block as in the FSB method. The rationale behind this is that the
weight of each block may vary when it is superimposed from a fixed number of different
term signatures, especially when the term signatures have non-uniform weights. A widely
dispersed distribution of the block signature weight results in a higher false drop probability
but lower storage overhead than a narrow distribution.
We first introduce two lemmas to aid in the proof of our main theorem in this section.
a k
a
Proof: Since a j - a k and b j - b k for every j - k, then it is obvious that
After expanding and rearranging the left-hand side of the inequality, we obtain:
a
a
a k
a
In addition, the term
to
replaced
with k. Hence, the inequality can be expressed as:
a k
a
and after simplification:
a
a k
!The next lemma introduces another inequality that also involves two monotone sequences
of integers.
be positive integers and a 1 - a In addition, if
are also integers with
Proof: Two cases should be considered:
case 1: If b then it is obvious that
case 2: If b 1
there exists an integer j 2 [1; p) such
that
a new inequality can be obtained by introducing a decreasing sequence a i into the latter
equality,
since each a i is positive and a i - a j - a j+1 - a k for every
a 0Theorem 3 The false drop probability for the FWB method is smaller than that of the FSB
method when the average block signature weights of the signatures in the two approaches are
the same.
Proof: Consider a set of blocks fB i j1 - i - pg in the FWB method and a set of blocks
in the FSB method. Given a query Q not contained in any B i or -
the average number of false drops for FWB is the summation of the probabilities
is the probability that a query signature SQ is qualified for block signature SB i
. That
is, the average number of false drops can be expressed as:
and this is the same for the FSB approach.
However, each block in FWB has the same weight i.e., wB 1
then the theorem can be proved by proving the following inequality:
wBavg
=p and w -
=p are the average block weights for FWB
and FSB approaches, respectively. Since m and wQ are fixed, (6), which we try to prove,
can be simplified as:
wBavg
or
(w -
(7) can be proved by induction. Considered 2, the proof makes use of Lemma 2
and the assumption that the average weights of the signatures in the two methods are the
same (i.e.
loss of generality, it is assumed that
Bp to satisfy the condition in Lemma 2. Hence, by Lemma 2,
and then we may obtain a new inequality when using
(w -
Thus, (7) is valid for 2. Next, if is valid, that is,
(w -
then
(w -
(w -
(w -
According to our assumption, w -
Bp . Therefore,
and
Using a sequence of decreasing positive integers fw -
(w -
every i from 1 to p g as the sequence fa i g in Lemma 3, we may obtain another
inequality by Lemma 3
(w -
From Equation (9) and (10), we can verify that it is also valid when
(w -
By the principle of mathematical induction, the theorem is proved. 2
The primary result of Theorem 3 is that the traditional FSB technique is worse than the
FWB method in terms of false drop probability. Furthermore, Theorem 3 can be generalized
to show that a widely dispersed distribution in block signature weights results in a higher
false drop probability.
Next, we consider the storage overhead of the two methods. We have observed that the
in Lemma 1 can be treated as a function of the block signature weight wB j
when the signature length m is a constant. Hence, the value w
can also be defined as a
function of wB j .
In order to know how the value w
is growing, the first and second derivatives of the
with respect to wB j are obtained as follows.
Both derivatives are positive, when wB j
m), since the value of \Gamma1=ln(1 \Gamma 1=m) is
always positive with a positive m. Then the value w
is not only an increasing function
but also a function growing more rapidly than any linear function. It means that, for
instance, the total term weight added to a block in order to increase the block signature
weight from 200 to 300 is smaller than what is necessary to increase the block signature
weight from weight 700 to 800. Therefore, the following theorem can be easily proved.
Theorem 4 The storage overhead for the FWB method is larger than that of the FSB
method when the average block signature weights of the signatures in the two approaches are
the same.
Proof: The main idea of this proof is to try to verify that, given two sets of the same
size, representing FWB and FSB blocks respectively, the total number of ones superimposed
in the blocks of the FWB set is less than that of the FSB set (i.e., blocks in FSB set will
absorb more ones than those in FWB). Therefore, for a given database, it is obviously that
the storage overhead of FWB will be greater than that of FSB.
be two sets of FWB blocks and FSB blocks
respectively. From Equation (5), it can be generalized to satisfy both approaches.
Number of
Bavg
Number of
Bavg
Hence the storage overhead in Equation (14) is larger than that in Equation (15), if and
only if w
Bavg is less than w
Bavg
. Alternatively,
According to the definitions of the two approaches and the assumption in this theorem,
we observe that P p
Without loss of generality, the sequence of blocks in the FSB set can be ordered into
Bp , and then there exists an index j 2 [1; p] such that
and
Then Equation (16) and, hence, the theorem can be proved when the inequality expressed
in Equation (18) is valid.
(w
(w
Bavg
The detail proof for Equation (18) will be described in Appendix A. 2
Simulation results of both theorems are illustrated in Figure 4 and 5. The text generated
for the simulations follows the Zipf's Law. The database contains 90,000 terms, and the
number of distinct terms V is 10,000. Two weight assignments were used, namely, the
inverse linear and the uniform assignments, to generate two distinct distributions of the
block signature weights for the FSB and FWB approaches; the optimal assignment method
cannot be used since an optimal assignment is not available for the FSB method. Figure
6 compares the distributions of the block signature weights in the FSB and FWB methods
when the two weight assignments are used.
According to Figure 4(a) and 5(a), FWB is 13% to 45% better than FSB in false drop
probability while incurring only 6% to 8% more storage overhead when the inverse linear
weight assignment method is employed. For the uniform weight assignment, however, both
the false drop probabilities and the storage overheads are the same in both method, since
the distributions of the block signature weights in the two methods are about the same. It
can be concluded from the analytical and simulation results that the FWB approach is at
least as good as the FSB method in false drop probability at the expense of a slightly higher
storage overhead. The difference depends on how flat the distribution in FSB is. It must
be pointed out that for a large block size and a "well-behaved" distribution (such as a Zipf
distribution), the signatures generated from the FSB and FWB methods are practically
identical under the uniform weight assignment. The FWB method excels when there are
"ill-behaved" text blocks and under non-uniform weight assignment strategies. Since the
optimal weight assignment has been shown to be better than the inverse linear method, its
performance gain over the FSB method should be even better.

Figure

4: False drop probabilities of FSB and FWB: (a) Inverse proportional; (b) Uniform

Figure

5: Storage overheads of FSB and FWB: (a) Inverse proportional; (b) Uniform weight

Figure

Distribution of block signature weights in FSB and FWB: (a) Inverse proportional;
5 Conclusion
The objective of this paper is to obtain the optimal weight assignment for a term as a
function of the occurrence and query frequencies of the term. Once the weight is obtained,
the term signature can be generated by setting the specified number of bits randomly. Thus,
the optimal signature can be generated algorithmically. This is in contrast with previous
methods where a lookup table is used to map a word directly to the word signature [7].
Further, unlike the traditional blocking scheme, the fixed size block (FSB) method, which
includes a fixed number of distinct terms in each block, we propose a new way, the fixed
weight block (FWB) method, to force each block signature to have a constant weight.
The FWB method provides two important advantages over the FSB approach. First, the
FSB method, with a constant block signature weight, simplifies the process of obtaining
the optimal weight assignment, since the block signature weight is directly involved in
the expression for determining the false drop probability. This allows us to obtain the
optimal weight assignment without making unrealistic assumptions and, more importantly,
the expression for computing the term signature weight is simple and efficient. The second
advantage is that the FWB approach has a lower false drop probability than the traditional
FSB method due to its constant block weight. This eliminates the situation where some
signatures are generated with abnormally high weights, which is possible (though with a
small probability) in the FSB method.
From the simulation results, the false drop probability of the optimal weight assignment
is close to 10 times better than that of the commonly used uniform weight assignment.
The comparison is done at the same storage overhead and under the FWB method. When
comparing the FWB method with the FSB method, it has been shown that FWB has a
better false drop probability than that of the FSB method, but the storage overhead is
slightly higher. The differences depend on the degree of dispersion in the distribution of
the signature weights.
From an implementation point of view, the optimal solution can be used directly for
computing the term weights. Statistics about the document terms and query terms can be
kept in a hash table, which can be updated periodically, if necessary, to reflect updates to
the document base and changes in usage pattern. Given the size of main memory typically
available on computers, the hash table can easily fit into main memory. Thus, the terms
weights can be computed efficiently. This is impossible if a lookup table is used to map
terms into word signatures, since the table would be too large. Of course, the system
designer also has the option of further simplifying the formula (e.g., set query frequencies
to a constant value) or using an expression (e.g., Zipf distribution) to approximate the
occurrence frequencies. However, the optimal solution remains the best, and feasible, choice
if minimizing false drops is the primary concern.
The combination of the new blocking scheme and the optimal weight assignment definitely
outperforms the traditional method in terms of false drop probability and storage
overhead. The technique developed here can work with other signature file structures, such
as the multi-level signature file [11,16] and the partition signature file [12]. Since many of
these search techniques have a better search performance when more 1's are specified in
the query signature (see, for example, Lee and Leng [12]), our optimal weight assignment,
which assigns higher weight to frequently queried terms, not only reduces the false drop
probability, but also improves the search performance of these search methods.

Acknowledgment

The authors would like to thank the Applied Information Technology Research Center,
a Thomas Edison program funded by the State of Ohio, for their financial support, and
to the anonymous referees whose comments have helped us to improve the contents and
presentation of this paper.


Appendix

I
We have shown in Equation (11) that the value of w
is a function of wB i
. Additionally,
in Equation (12) and (13), both the first and the second derivatives of w
with respect to
are positive when wB m). In order to make w
more expressive, a function f is
defined as:
Then the inequality expression in Equation (18), which Theorem 4 attempts to prove,
becomes:
when Equation (17) is valid. For every i 2 [1; j],
Then, according to the Mean-Value Theorem, we can translate the above summation into
is positive within [0; m), f 0
must be
increasing with respect to the value w -
. Therefore,
(wBavg
or
(wBavg
is satisfied for every i 2 [1; j]. That is, we can reach the inequality:
(wBavg
By the same arguments, we may obtain another similar inequality:
(w -
Combining Equations (17), (20) and (21), we can verify Equation (19):
and also Equation (18):



--R

Mathematical Analysis.
"A signature access method for the Starburst database system,"
"S-Tree: A dynamic balanced signature index for office retrieval,"
"Signature-based text retrieval methods: A survey,"
"Signature files: an access method for documents and its analytical performance evaluation,"
"Description and performance analysis of signature file methods for office filing,"
"Optimal signature extraction and information loss,"
"Design of a signature file method that accounts for non-uniform occurrence and query frequencies,"
"A signature file scheme based on multiple organizations for indexing very large databases,"
"A word-parallel, bit-serial signature processor for superimposed coding,"
"Efficient signature file methods for text retrieval.,"
"Partitioned signature files: Design issues and performance evaluation,"
"A partitioned signature file structure for multiattribute and text retrieval,"
"Partial match retrieval using indexed descriptor files,"
"Partial-match retrieval via method of superimposed codes,"
"Multikey access methods based on superimposed coding techniques,"
"A two level superimposed coding scheme for partial match retrieval,"
Introduction to Modern Information Retrieval.
"Parallel free-text search on the connection machine system,"
"Mathematical analysis of various superimposed coding methods,"
"Message files,"
--TR
Parallel free-text search on the connection machine system
Description and performance analysis of signature file methods for office filing
Multikey access methods based on superimposed coding techniques
Partitioned signature files: design issues and performance evaluation
Signature-based text retrieval methods: a survey
A signature access method for the Starburst database system
Optimal signature extraction and information loss
S-tree
Signature files
Message files
Partial-match retrieval using indexed descriptor files
Introduction to Modern Information Retrieval
A Partitioned Signature File Structure for Multiattribute and Text Retrieval
A Word-Parallel, Bit-Serial Signature Processor for Superimposed Coding

--CTR
P. Drew , B. Hamidzadeh , K. Karlapalem , A. Kean , D. Lee , Q. Li , F. Lochovsky , C. D. Shum , B. Wuthrich, Data and knowledge base research at Hong Kong University of Science and Technology, ACM SIGMOD Record, v.24 n.4, p.84-89, Dec. 1995
Deniz Aktug , Fazli Can, Analysis of multiterm queries in a dynamic signature file organization, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.96-105, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States
Pavel Zezula , Paolo Ciaccia , Paolo Tiberio, Hamming Filters: A Dynamic Signature File Organization for Parallel Stores, Proceedings of the 19th International Conference on Very Large Data Bases, p.314-327, August 24-27, 1993
Dik Lun Lee , Young Man Kim , Gaurav Patel, Efficient Signature File Methods for Text Retrieval, IEEE Transactions on Knowledge and Data Engineering, v.7 n.3, p.423-435, June 1995
signature file;optimization;access method;coding methods;text retrieval;information retrieval;document retrieval;superimposed coding