Boolean Similarity Measures for Resource Discovery.
AbstractAs the number of Internet servers increases rapidly, it becomes difficult to determine the relevant servers when searching for information. We develop a new method to rank Internet servers for Boolean queries. Our method reduces time and space complexity from exponential to polynomial in the number of Boolean terms. We contrast it with other known methods and describe its implementation.
Introduction
Searching for information in the Internet is a considerable
task. Thousands of servers provide different information
over the networks. Determining appropriate servers
for searching is a common problem. For novice users, they
have no idea where to send requests, and experienced users
may miss new servers having relevant information.
A user query can be described using natural language,
keywords, or a database query language. We assume each
query is transformed to a standard format, such as a
Boolean expression, by an associated query engine. Because
each user requests different information, it is inappropriate
to broadcast requests to all servers. That overwhelms
the underlying networks and overloads irrelevant
servers.
To solve this problem, we propose the client-directory-
server model [1]. Our goal is to give users a list of relevant
servers ranked according to their relevance to the query.
In this model, a "directory of services" records a description
of each information server, called a server description.
A user sends his query to the directory of services which
determines and ranks the servers relevant to the user's re-
quest. The user employs the rankings when selecting the
servers to query directly. Fig. 1 shows the details.
A server description can be automatically generated by
clustering algorithms [1], by information extraction tools
[2], or can be manually assigned by administrators [3], [4].
In either case, it can represent a summary of the underlying
database contents or function as a filter to collect
information satisfying certain conditions. In this research,
we focus on Boolean environments, where both user queries
and server descriptions are written in Boolean expressions.
We believe that Boolean expressions can precisely describe
a server's contents as well as a user's information need. Using
the above methods [1], [2], server descriptions can eas-
This work was supported in part by the Advanced Research
Projects Agency under contract number DABT63-93-C-0052, HBP
NIH grant 1-P20-MH/DA52194-01A1, National Science Foundation
Institutional Infrastructure grant number CDA-9216321, and NSF
NYI grant number NCR-9457518.
The authors are with the Computer Science Department, University
of Southern California, Los Angeles, California, 90089.
Directory of
Services
User
Server A
(1) (2)
query result
relevant list
query
Server A
query Document 1
Document 2
Fig. 1. Resource discovery process: (1) A user sends a query to
the directory of services. (2) The directory of services returns a
ranked list of relevant servers. (3) The user sends his query to
one or more of the relevant servers which (4) return matching
documents.
ily be formulated as Boolean expressions. For user queries,
existing tools or algorithms can help users generate or re-construct
complicated Boolean queries to express their information
needs [5], [6], [7].
Example 1: Consider the following Boolean expression,
where keyword and author are predefined attribute names,
and network, UNIX, and Smith are their corresponding val-
ues. In the discussion, we would represent this expression
as are called descrip-
tors, - is the logical or operator, and - is the logical and
operator. 2
In this paper, we develop an efficient algorithm to rank
servers based on their similarities with respect to a query.
We describe two existing similarity measures for Boolean
expressions, introduce our new measure, and experimentally
contrast it with the well known Jaccard's coefficient.
We review related work on Internet resource discovery
in Section II. Section III describes existing and our new
Boolean similarity measures. We show experimental results
of both measures in Section IV and analyze their time and
space complexity in Section V. Section VI discusses the implementation
of our method and Section VII presents our
conclusions.
II. Related Work
Internet resource discovery services [8], such as Archie
[9], WAIS [3], CRS [10], GlOSS [11], and Indie [4], all provide
services similar to the client-directory-server model.
They determine relevant servers for users to submit queries.
In Archie [9], a centralized server collects file and directory
names from anonymous Internet FTP servers. Users
G
send queries containing the requested file name to the centralized
server, get back a list of matching hosts, and retrieve
the file manually. This system only searches documents
by their file names and does not support complicated
Boolean queries.
WAIS [3] has a special server called the directory of
servers, which contains the description of each WAIS server
and compares them with user queries to determine relevant
servers. The WAIS directory of servers is similar to the directory
of services in our model. It ranks servers based on
a word-weighting algorithm, but it is maintained manually.
In Content Routing System (CRS) [10], each server is
characterized by a content label, which is a Boolean combination
of attribute-value pairs and is manually constructed
by administrators or automatically derived from frequently
occurring terms in the database. A server is relevant to a
query if its content label satisfies the query. Users can refine
queries when browsing the content labels of selected
servers. In addition, this system automatically forwards
queries to relevant servers and merges their results. Cur-
rently, nesting of Boolean operations is not supported.
The GlOSS [11] system uses a probabilistic scheme to
find relevant servers for user queries. In GlOSS, each server
extracts a "histogram" of term occurrences in its database.
The histograms are used to estimate the query result size
(defined as the number of documents in the database times
the probability that a document contains all the query
terms) and to determine relevant servers. This method
is built upon the assumption that terms appear in different
documents of a database following independent and
uniform probability distributions. GlOSS only considers
Boolean and queries and does not rank servers.
Indie [4] is designed and implemented based on the client-
directory-server model. Each Indie resource is managed by
a server called an Indie broker, which maintains a generator
that describes the objects stored in its database. The
generator, a nested Boolean expression, is used as a filter to
collect data from information providers. The logically centralized
but replicated server, called directory of services, is
a specialized broker that contains only the generators of every
Indie broker in the system. Users send a Boolean query
to the directory of services, which compares the query with
each generator in its database, finds the similarity between
them, then sends a ranked list of relevant Indie brokers to
the user.
Depending on the type and format of the user query and
server description, each system employs a different similarity
measure to determine relevant servers. Most systems
only support a simple query type, such as keywords or
simple Boolean combinations. They do not solve nested
Boolean queries and rank servers accordingly. The method
presented in this paper is to measure the similarity between
Boolean expressions, which can be directly applied to In-
die. It can also be used for full text data or keyword queries
by combining them with all and or or Boolean operators.
III. Similarity Measure
Well-known similarity measures, such as Dice's coeffi-
cient, Jaccard's coefficient, Cosine coefficient, and Overlap
coefficient, have been used to compute the similarities
of one document to another document, and documents to
queries for automatic classification, clustering, and indexing
[12]. For these measures, documents and queries are
represented as sets of keywords or vectors.
In the "cluster-based retrieval" system, documents with
high similarities are grouped into a cluster. User queries
are first compared with cluster representatives, then compared
with documents in the clusters that have high similarities
with the queries [12]. In the client-directory-server
model, the function of directory of services is similar to
cluster-based retrieval, where servers are clusters described
by cluster representatives (i.e. server descriptions). For
user queries and cluster representatives both described as
Boolean expressions, the above similarity measures can not
be applied directly. The degree of similarity between user
queries and server descriptions is determined by how much
these Boolean expressions overlap. Consider the example
below.
Example 2: Suppose RA and RB are the server descriptions
of two retrieval systems stored in the directory
of services, and Q 1 and Q 2 are two user queries:
Both RA and RB overlap with Q 1 , but RA contains two
overlapped terms (t 1 and t 3 ) while RB contains only one
Thus, RA is more relevant to query Q 1 than RB ,
assuming all terms are weighted equally. However, for an
and-or-combined query Q 2 , it becomes more complicated
to determine which server description is more relevant. 2
We need a systematic method to measure the overlap between
user queries and server descriptions. Furthermore,
this method must perform efficiently even when the number
of server descriptions increase. Radecki employed several
measures to rank similarity between Boolean expressions
[13], [14]. In the following sections, we review Radecki's
measures and present our modified measure. We demonstrate
our improvements in space and time complexity and
compare the two measures on a synthetic benchmark.
A. Background
Radecki proposed two similarity measures, S and S   ,
based on Jaccard's coefficient. He defined the similarity
value S between queries Q 1 and Q 2 as the ratio of the
number of common documents to the total number of documents
returned in response to both queries. This ratio,
commonly known as Jaccard's coefficient, can be described
as
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 3
" denotes set intersection, [ denotes set union, and
are the response sets to Q 1 and Q 2 , re-
spectively. To apply S in our environment, we denote -(R)
and /R (Q) as the sets of documents in the cluster represented
by R and in R's response to query Q. The similarity
value S between Q and R is then defined as the ratio of
the number of common documents to the total number of
documents in /R (Q) and -(R),
Because all the documents satisfying query Q belong to
cluster R (i.e. /R (Q) ' -(R)), (1) can be simplified as
Example 3: Using the definitions from Example 2, we
assume system A (represented by RA ) contains documents
(represented by RB ) contains
documents g. Thus,
Assume for query Q 1 , the system responses are
are the responses to Q 1 in systems
A and B respectively. The similarity measures between
against RA and RB are then
0:667:In the case of a directory of services, however, the similarity
measure is used to estimate the importance of entire
information systems and decide the order in which users
should search them. If the similarity is calculated based
on the query results from every information system, the
searching order is no longer needed because you have already
searched them all.
Radecki proposed a similarity measure S   that is independent
of the responses to the queries [14]. In S   , Boolean
expression Q is transformed into its reduced disjunctive
normal form (RDNF), denoted as ~
Q, which is the disjunction
of a list of reduced atomic descriptors. If set T is
the union of all the descriptors that appear in the to-be-
compared Boolean expression pair, then a reduced atomic
descriptor is defined as a conjunction of all the elements in
T in either their original or negated forms. Let Q and R
be two Boolean expressions and TQ and TR be the sets of
descriptors that appear in Q and R respectively. Suppose
is the set size of TQ[TR .
Then the RDNFs of Q and R are
~
~
r i;j );
where m and n are the number of reduced atomic descriptors
in ( ~
Q) TQ[TR and ( ~
R) TQ[TR . Each reduced atomic descriptor
q i;j and
in the two RDNFs consists
of the same number of descriptors (k), which is the
set size of TQ [TR . Each ~ q i;j and ~ r i;j in the RDNFs represents
the corresponding descriptor t j or its negation :t j (:
is the logical not operator). For example, ~
q 2;1 denotes the
first descriptor in the second reduced atomic descriptor of
q 2;1 is either t 1 or :t 1 depending
on how Q is transformed. The following example illustrates
the transformation from Boolean expressions to RDNFs.
Example 4: From Example 2,
where set TX is the union of all the descriptors in Boolean
or RB ). To transform Q 2 to
its RDNF, we can apply the distributive law
and expand the two conjunctions,
their associated reduced atomic descriptors. The expansion
process is based on the equation
where t a and t b are descriptors. Consider Q 2 and RA first.
each reduced atomic descriptor
in ( ~
and ( ~
must contain all the
negated forms. Thus, the conjunctions
in Q 2 are expanded to
The RDNFs of Q 2 and RA are
Similarly, because TQ2 [ g, the RDNFs
of Q 2 and RB are
-t 4 ):Radecki defines the similarity value S   between two
Boolean expressions (Q and R) as the ratio of the number
of common reduced atomic descriptors in ~
Q and ~
R to
the total number of reduced atomic descriptors in them,
Example 5: Continuing with Example 4,
Therefore, RA is more relevant to query Q 2 than RB . 2
From Example 4, we can see that Q 2 is transformed
to different RDNFs, ( ~
and ( ~
, when
computing with RA and RB . This means whenever a new
user query is compared against N server descriptions, it
needs 2N RDNF transformations to calculate the similarity
between them. This method suffers when the number
of server descriptions is large and users query frequently.
The system will spend significant amounts of time recomputing
RDNFs, and consequently will perform badly. To
solve this problem, we modify Radecki's method so that
it need not recompute RDNFs of server descriptions while
still providing results of equivalent or better quality.
B. New Similarity Measure
We propose a new measure based on Radecki's similarity
measure S   , that is independent of the underlying information
systems and requires less computation. We transform
a Boolean expression to its compact disjunctive normal
form (CDNF) using the distributive law described in
the previous section. The CDNF is a disjunction of compact
atomic descriptors, each being a conjunction of subsets
of descriptors in the original Boolean expression. The descriptors
in each compact atomic descriptor are determined
while performing the distributive law.
Let Q and R be two Boolean expressions, and TQ and
TR be their sets of descriptors. We denote -
R as the
CDNFs of Q and R, and express them as
r j;v );
where each conjunction (
q i;u and
r j;v ) is a compact
atomic descriptor, and m and n are their number
in -
R. The x i is the number of descriptors in the
th (1 - i - m) compact atomic descriptor of -
Q, and y j is
the number of descriptors in the j th (1 - j - n) compact
atomic descriptor of -
R. Each -
q i;u and - r j;v in the CDNFs
represents a descriptor in TQ and TR respectively.
Example The CDNFs of Q 2 , RA , and RB in Example
are
Each compact atomic descriptor in -
consists of only
the descriptors in TQ2 without introducing new descriptors
from TRA and TRB . In other words, the descriptors in
are independent of those in other Boolean expressions,
such as RA and RB . 2
We denote our similarity measure S \Phi and define the similarity
of two Boolean expressions as the summation of the
individual similarity measures (s \Phi ) between each compact
atomic descriptor. The individual similarity measure s \Phi is
defined as
and
indicates the i th compact atomic descriptor of
Q, and -
R j indicates the j th compact atomic descriptor
of CDNF -
R.
R are the sets of descriptors
in -
is the number of descriptors that
appear in T j
R but not in T i
R j is the number of
descriptors that appear in T i
Q but not in T j
R . The similarity
measure S \Phi is the sum of the individual s \Phi given by
Qj
Qj and j -
Rj are the number of compact atomic descriptors
in -
R respectively.
Example 7: Using the above definitions, we compute S \Phi
for and RB of Example 6. We find
A
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 5
RA , and T 1
RB , are the sets of descriptors
in the compact atomic descriptors -
A , and -
respectively. The individual similarity measures are therefor

R A
R A
R A
R A
which yields
Similarly for Q 2 and RB , we get
which leads to
Therefore, RA is more relevant to query Q 2 than RB . 2
Notice that the similarity values calculated using S \Phi (in
Example 7) are different from those calculated using S
(in Example 5). It is meaningless to compare these values
directly because both are measured on a relative scale.
However, they can be used to rank a list of Boolean expressions
measured by the same method.
IV. Experiments
To compare the rankings estimated by similarity measures
S   and S \Phi , we conduct experiments on two
databases. One is the standard CISI dataset. The other is
the Homer database at the University of Southern Califor-
nia. We use the result of S as the criterion, and compare
it to that of S   and S \Phi . Each experiment consists of the
following steps.
1. Create individual server databases by using queries as
filters.
2. Calculate S based on the number of hit documents on
each server.
3. Calculate S   and S \Phi for each filter-query pair.
4. Rank servers based on S, S   and S \Phi .
5. Compare their rankings using Spearman rank-order
correlation coefficient (r s ) [15].
using confidence interval
for the proportion [16].
We describe the details as follows.
During the experiment, all queries play two roles. First,
each query is used as the filter of a server to collect specific
documents from the testing database. Thus, we can create
N servers by running N queries on the database, where
each server description is represented by the associated fil-
ter. Second, each query is submitted to all the N servers.
The number of hit documents is used to calculate S using
(2). Based on the S values from the N servers, we can rank
them for each query and use that as the standard ranking
to evaluate S   and S \Phi .
To calculate the rankings estimated by S   and S \Phi , we
apply (3) and (4) to each filter-query pair (i.e. query pair)
and sort them in descending order. To compare which
method generates a ranking closer to the standard, we compute
the degree of association between (S   , S) and between
(S \Phi , S) by applying the Spearman rank-order correlation
coefficient (r s ) [15]. The r s ranges between \Gamma1 and 1. If
two rankings are identical, r s = 1. If one ranking is the
reverse of the other, r \Gamma1. The larger the r s , the closer
the rankings.
denote the N queries as well as the
filters. For each query Q
according to the similarity values
separately. For
tied values, each Q j is assigned the average of the ranks
that would have been assigned had no ties happened. Let
an and b be two rankings for Q i generated
by various similarity measures, where n is the number of
elements in the ranking (N in our case). The tied ranks in
each ranking form a group. Assume there are g u different
groups in a an , each group has u k (1 - k - g u ) tied
elements. Similarly, ranking b groups, each
has tied elements. The r s coefficient can
be obtained by [15]:
where
gu
(v 3
For each query, we can determine which method performs
better by their r s values with respect to S. Among
the N observations, we measure the confidence that S \Phi is
superior to S   by calculating the confidence interval for the
proportion, defined as follows [16]:
Confidence interval
r
where z 1\Gamma ffis the
2 )-quantile of a unit normal variate
confidence level), n is the total
number of samples (N in our case), and n 1 is the number
of times S \Phi is superior to S   (i.e. r s (S \Phi
6 IEEE TRANSACTIONS ON KNOWLEDGE AND
By definition [16], if and the confidence interval
does not include 0.5, we can say with 95% confidence that
S \Phi is superior to S   .
A. CISI Experiment
The CISI dataset consists of 1460 information science
documents and 35 Boolean queries. All documents are indexed
with terms occurring in the title and abstract but
not on a stop list of 429 common words. All indexed terms
are stored in their original forms without stemming. A
Boolean query is a nested structure of terms with logical
and, or, and not operators in between. Documents are hit
by a query if they satisfy all the conditions in the query.
Following the six steps described previously, we calculate
r s (S \Phi ; S) and r s (S   ; S) for the 35 queries. Fig. 2 shows the
value of r s (S \Phi ; S) minus r s (S   ; S) for each query. Among
them, r s (S \Phi ; S) is greater than r s (S   ; S) for 24 times (the
\Theta's above zero) and less than r s (S   ; S) for 11 times (the
\Theta's below zero). This indicates S \Phi generates a ranking
closer to that of S for 24 out of 35 times, whereas S   only
has closer order for 11 out of 35 times. The mean Spearman
coefficient of r s (S \Phi ; S) and r s (S   ; S) are 0.331 and
respectively. This shows S \Phi has a better average
estimation than S   on the CISI database.
-0.4
query sample
Spearman
coefficient
difference
Fig. 2. The difference between rs (S \Phi ; S) and rs (S   ; S) for
Boolean queries on the CISI database. The \Theta's above zero indicate
S \Phi generates a ranking closer to that of S than S   for the
associated query.
From the results of r s (S \Phi ; S) and r s (S   ; S), the sample
proportion of "r s (S \Phi
Because 35), we can calculate the "confidence
interval for the proportion" for
95% confidence interval
r
The confidence interval does not include 0.5. Therefore, we
can say with 95% confidence that S \Phi is superior to S   in
the CISI experiment.
B. USC Homer Experiment
In this experiment, we manually create
samples, each averaging 3.6 descriptors picked up from 24
terms in diverse fields. We submit these queries to the USC
Homer database and compute the results. Fig. 3 shows the
values of r s (S \Phi ; S) minus r s (S   ; S) for the queries.
-0.4
query sample
Spearman
coefficient
difference
Fig. 3. The difference between rs (S \Phi ; S) and rs (S   ; S) for
Boolean queries on the USC Homer database. The \Theta's above
zero indicate S \Phi generates a ranking closer to that of S than S
for the associated query.
In Fig. 3, r s (S \Phi ; S) is greater than r s (S   ; S) for 22 times
(the \Theta's above zero) and less than r s (S   ;
(the \Theta's below zero). This indicates S \Phi generates a ranking
closer to that of S for 22 out of 32 times, whereas S
only has closer order for 10 out of 32 times. The mean
Spearman coefficients of r s (S \Phi ; S) and r s (S   ; S) are 0.595
and 0.494 respectively. This shows S \Phi has a better average
estimation than S   on the USC Homer database.
From the results of r s (S \Phi ; S) and r s (S   ; S), the sample
proportion of "r s (S \Phi
Because calculate the "confidence
interval for the proportion" for
95% confidence interval
r
The confidence interval does not include 0.5. Therefore, we
can say with 95% confidence that S \Phi is superior to S   in
this experiment.
C. Discussion
The queries associated with each dataset are designed to
hit a number of documents in the collection. Therefore, the
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 7
servers generated by using queries as the filters contain different
portions of the collection. The CISI database is a collection
of documents in library science and related areas. It
is an experimental database commonly used by researchers
working on information retrieval. The USC Homer is an
on-line library catalog system that covers a board range
of collections, such as business, law, literature, medicine,
science, and engineering. So, for example, each server in
the first experiment is a subset of documents focusing on
a specific topic in information science, while the servers
in the second experiment contain documents in widely different
fields. Table I gives the additional characteristics
of the two experiments. We obtained similar results from
the two databases even though they have different size and
cover different fields of documents. In the two experiments,
both the average Spearman coefficient and the confidence
interval for proportion show that S \Phi is superior to S   .


I
Characteristics of the CISI and USC Homer experiments.
CISI USC Homer
Number of documents 1460 - 800,000
Number of queries
Number of servers
Mean number of terms per query 7.14 3.6
Mean number of documents per server 91.7 5492
V. Analysis and Comparison
Space and time are two of the important factors in designing
a real-time system. In an on-line information retrieval
system, the system response time is highly dependent
on the underlying data structures and associated indexing
and searching techniques. In this section we analyze
the space and time complexities of the two searching techniques
- similarity measures S   and S \Phi .
As mentioned eariler, to calculate S \Phi , we need to apply
the distributive law such as
to obtain CDNFs, where t 1 , t 2 , and t 3 are descriptors. To
calculate Radecki's S   , we need to transform Boolean expressions
to RDNFs. Two steps are required in the trans-
where the distributive law is
used to produce the corresponding disjunctive normal form;
and 2) "expansion", where we use t
so that each reduced atomic descriptor contains all the
descriptors (original or negated) in the to-be-compared
Boolean expressions. The order of these two steps affects
the complexity, but not the result, of transforming
a Boolean expression to a RDNF. If the distribution is performed
before the expansion, it is equivalent to transforming
the Boolean expression to its CDNF and then expanding
the CDNF to a RDNF. If the expansion is performed
before the distribution, it needs more space and computation
because extra negated descriptors, such as :t 2 , will
be generated in the expansion step. The following example
will clarify this idea.
Case 1: We transform Boolean expression Q to CDNF
Q, then expand it to RDNF ~
Q.
Case 2: We expand Q first, then distribute it.
oe
oe
oe
In Case 1, the expansion is performed after the distri-
bution. Therefore each compact atomic descriptor is expanded
(from (5) to (6)) instead of each descriptor (from
(7) to (8)), as in Case 2. A compact atomic descriptor usually
contains more than one descriptor after applying the
distributive law to its original Boolean expression. In the
above example, each of the two compact atomic descriptors
in -
contains two descriptors.
Eight additional descriptors are added from (5) to (6) after
the expansion. On the other hand, each individual descriptor
in the original Boolean expression is expanded in
Case 2. Thirty-three additional descriptors are added from
(7) to (8). The second approach needs more space than the
first one for storing those intermediate descriptors, which
consequently cause it to spend more time checking the duplicates
before obtaining the final ~
Q.
In our example, the original Boolean expression contains
only 3 descriptors. It is the simplest transformation case.
For more complicated Boolean expressions, the difference
between Case 1 and Case 2 is bigger. Therefore we use the
first approach (i.e. Boolean expression
in our complexity analysis. Based on this, the time complexities
of S \Phi and S   are equal to the transformation time
from Boolean expression to CDNF or RDNF plus the time
to compute the similarity measures. For a single Boolean
expression,
Time S \Phi (computation);
where
Time S \Phi (transformation)
Similarly, the space complexities of S \Phi and S   are determined
by the storage requirements for the CDNF and
RDNF respectively. For a single Boolean expression,
Space
Space S
In the following sections, we discuss the complexity of each
individual step.
A. From Boolean Expression To CDNF
To simplify the analysis, we use binary trees [17] to represent
the Boolean expressions. Each external node or "leaf"
represents a descriptor. All the internal nodes, including
the root, are logical operators. The negation not can be
stored with the associated descriptor, therefore we do not
denote it separately. The height of a tree is the longest
path from any leaf to the root.
The binary trees are transformed to their equivalent
CDNF binary trees using the distributive law. The technique
is to transform an and-rooted subtree to an equivalent
or-rooted subtree one at a time in a top-down ap-
proach. An example is shown in Fig. 4, where A, B, and C
are the subtrees of associated nodes.
and
or
A A
and
and or
Fig. 4. Compact disjunctive normalization. We use the distributive
law C), on the subtrees A, B, and
C.
We first change the current root node from and to or, and
change its or-rooted child node to be and-rooted. Then we
demote the other child (C) by one level, and add one and
node at its original position to be its new parent. Finally,
we replicate the demoted child (C) and exchange it with
one of the children (B) on the other subtree. The same
procedure is repeated until reaching the leaves.
The space complexity of transforming the Boolean expression
to a CDNF varies from O(n) to O(n 2 ) depending
on how the Boolean expression is constructed, where n is
the sum of the total number of descriptors and logical operators
in the Boolean expression. For example, a linear
binary tree (Fig. 5(a)) generates an O(n) CDNF, while a
complete binary tree (Fig. 5(b)) generates an O(n 2 ) CDNF.
Notice that n is equal to the total number of nodes if the
Boolean expression is represented as a binary tree. Intu-
itively, the O(n 2 ) CDNF can be derived by starting with
a tree of height h. It will have nodes for a
complete binary tree. The distributive law no more than
doubles the height. Thus, the new tree is bounded by size
The time complexity is primarily determined by the
number of times the distributive law is invoked and the
size of the subtree to be duplicated. Basically it is the
same order as the space complexity - O(n) for a linear
binary tree and O(n 2 ) for a complete binary tree.
or
and
or
and
or and
and
or and
and
or
(a) (b)
Fig. 5. Various binary trees: (a) a linear binary tree, and (b) a
complete binary tree, where and and or are logical operators,
are descriptors.
The linear and complete binary trees are used as the
lower and upper bounds for complexity analysis. Below,
we discuss only the worst case - a complete binary tree
with and node at the root and or nodes elsewhere. In this
case, the distributive law is applied to all the subtrees at
each level. The case of linear binary tree is described in
[18].
Fig. 6 shows an n-node complete binary tree where each
internal node contains two children (i.e. a complete binary
tree). Every time the topmost and node is distributed, an
additional and node and a copy of one of its subtrees will
be created. Fig. 6(a) is transformed to 6(b) by creating
an and node and a duplicate C. Similarly, A and B are
duplicated from Fig. 6(b) to 6(c). The time complexity
T (n) consists of the time for adding additional and nodes
and for duplicating subtrees. Since there is no need for
distribution for n - 3 , T these cases. Otherwise,
Therefore,
Let h be the height of the original binary tree, then
1. We can derive
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 9
and [n]
or
or
or
n-3[ ] or
or
or
(a)
and
or
and
or
or
or
or
or
or
or
or
A
(b)
or [2n+1]
or
or
and
or
or
and
or
or
or
and
or
A C2
or
and
or
A C1
(c)
Fig. 6. The CDNF transformation of an n-node complete binary tree. Originally, only the root is the and operator, the other internal nodes
are all or operators. A; B; C 1
, and C 2
are subtrees. The number in the brackets means the number of nodes in this subtree. (a) The
original binary tree. (b) The binary tree after distribution on the first level node (i.e. the root), where the subtree C is duplicated. (c)
The binary tree after distributions on the second level nodes, where the subtrees A and B are duplicated.
Similarly, the space complexity M(n) consists of the
space to store the root and its two to-be-distributed sub-
trees. For n - 3, the space is not changed because there is
no need for distribution. Otherwise,
Therefore,
ae n if n - 3;
which can be derived as
the n+1
descriptors (i.e.
leaves) in the original n-node full binary tree. We divide t i
into four groups (A, B, C 1 , C 2 ) of equal size, each group
having n+1
descriptors. Let
Therefore, Fig. 6 can be presented as
A
A
are subtrees, and (9), (10), and
Figs. 6(a), 6(b), and 6(c) respectively. Equation
(12) represents the resulting CDNF -
Q, which consists
of ( n+1
descriptors with 2 descriptors
in each of them. We can therefore show that the characteristics
of the CDNF of an n-node complete binary tree
are:
8 descriptors,
ffl each compact atomic descriptor contains 2 descriptors,
ffl Time complete (Boolean expression
ffl Space complete
B. From CDNF To RDNF
Assume are two Boolean expressions, which
have n 1 and n 2 total nodes and p 1 and p 2 distinct descriptors
respectively. Let p be the size of the union of these two
distinct descriptor sets, c 1 and c 2 the number of compact
atomic descriptors of -
the number
of reduced atomic descriptors of ~
We observe
that the resulting RDNFs of Boolean expressions Q 1 and
contain the following characteristics:
ffl each reduced atomic descriptor contains p descriptors,
Q 1 has (r 1 \Theta p) descriptors,
descriptors.
In ~
each compact atomic descriptor containing
2 descriptors is expanded to 2 p\Gamma2 reduced atomic descriptors
containing p descriptors. However, some of these
reduced atomic descriptors are duplicates. Therefore the
total number should not exceed 2 p , which is the number
of all possible combinations of reduced atomic descriptors
containing p descriptors. The space complexity of ~
be derived as
ae
where (r 1 \Theta p) is the number of descriptors in ~
is the number of logical operators in ~
The time for transforming CDNF to RDNF consists of
expanding each compact descriptor, and 2) checking and
removing duplicate reduced atomic descriptors. Because 2)
can be done as 1) is being executed, it is omitted in our
analysis. Thus, the time complexity for an n-node binary
tree is
C. Computation
To calculate the similarity measure S \Phi between two CD-
NFs, we need to compare their compact atomic descriptors.
Using the notation given above, we further define that the
th
descriptors
and the j th (1 - j - c 2 ) atomic descriptor of
To speed up the computation time, all the descriptors
within the compact atomic descriptors or reduced
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 11
atomic descriptors are sorted before calculating their sim-
ilarities. Therefore it takes
To compare these two CD-
NFs term-by-term, it takes
Hence,
Time S \Phi (computation)
Similarly, we transform the same two Boolean expressions
to RDNFs ~
each reduced atomic descriptors
contains exact p descriptors. Using the same optimal
sorting method, it takes
time to
time to compare them.
Thus,
Because RDNF is obtained by expanding its CDNF,
we are certain that c 1 - r 1 and c 2 - r 2 . There-
fore, Time S \Phi (computation) is always less than or equal to
are both n-node binary
trees as described above, then k
Time S \Phi (computation)
D. Remarks
Below, we summarize the previous time and space analysis

Time S \Phi (computation)
Time S \Phi (computation)
Space
Space S
The above comparisons are analyzed based on a pair of
Boolean expressions only. For (N +1) Boolean expressions,
consisting of one incoming query and N server descriptions,
their time and space complexities are in proportion to N
[18]. As discussed previously, an n-node binary tree consists
of n+1
leaves (or descriptors in the Boolean expres-
sion). The number of distinct descriptors p must be no
larger than n+1
O(n). Thus, the complexities
of the two measures S \Phi and S   can be simplified as
shown in Table II.


II
Time and space complexities of S \Phi and S   for one user query
against N server descriptions. Both the user query and the
server descriptions are n-node binary trees.
time complexity O(Nn 4 ) O(N2 2n n)
space complexity O(Nn 2 ) O(N2 n n)
Apparently, S \Phi outperfroms S   in both time and space
complexities. The above analysis shows that our similarity
measure based on CDNFs consumes up to exponentially
less time and space than Radecki's method. The following
example further illustrates the performance difference
between the two measures.
Example 8: Consider a directory of services containing
100 server descriptions, each consisting of 5 descriptors.
The time and space used to calculate the similarities S
and S \Phi for a 5-descriptor user query are:
Time S \Phi (1 query, 100 server descriptions)
Space S   (1 query, 100 server descriptions)
Space S \Phi (1 query, 100 server descriptions)
When using S \Phi , the directory of service is eight times faster
in searching the relevant servers, and takes only one-sixth
the space of S   . 2
VI. Implementation
In the client-directory-server model, the directory of services
ranks the servers by comparing their descriptions with
the query. Both the query and the server descriptions need
to be normalized before the comparison. In our method,
the normalization of a Boolean expression is independent
of other Boolean expressions in the comparison. There-
fore, we can pre-normalize the server descriptions and store
them in the directory of services. Below, we describe the
implementation of our Boolean similarity measure.
We use the UNIX tools flex and bison to parse the nested
Boolean expressions and build the associated binary parse
trees. Each attribute-value pair in the user query and the
server description is presented as a three-element subtree in
the binary parse tree. The three-element subtree consists
of one parent node and two child nodes. The left and right
child nodes, i.e. the leaves, are the attribute name and its
value respectively. The leaves are joined by the parent
node, which is a relational operator ("=" or "6="). These
subtrees are merged by the logical operators (and and or)
to form the binary parse tree.
The binary parse trees are transformed to their equivalent
CDNF binary trees based on the distributive law. Notice
that while replicating the subtree (such as C in Fig. 4),
we only copy the logical operator nodes in order to save
space. For relational operator nodes, only their associated
pointers are copied. All the nodes in the binary tree whose
parents are or are linked together after the distributive
normalization. Consider the following example.
Example 9: Let Q 1 be an incoming user query and
be three server descriptions stored as CDNFs
RC ) in the directory of services,
and
The Q 1 is normalized to -
or
The similarity values between the user query and the three
server descriptions are
:Figs. 7 and 8 show the binary parse tree of the user query
Example 9 before and after normalization. Fig. 9
shows the server description RC after normalization. The
link generated in each normalized binary tree is pointed at
by head.
network keyword
or
and
author
Smith
Fig. 7. User query Q 1 before normalization.
and
network keyword
and
or
head
author
Smith author
Smith
Fig. 8. Normalized user query -
. The head links all the nodes whose
parents are or. The dashed subtree is a replicated subtree. The
iis one of the compact atomic descriptors in -
Q1 .
database McLeod
author
and
and
or
head
author
Smith
R C
Fig. 9. Normalized server description -
RC . The head links all the
nodes whose parents are or. The -
is one of the compact atomic
descriptors in -
RC .
After the normalization process, we compare each component
in the links of the two binary trees. Each element in
the server description link represents a compact atomic descriptor
C in the server description -
RC . Each element in
the user query link represents a compact atomic descriptor
in the user query -
To calculate s \Phi ( -
we compare all the nodes under -
1 with all the nodes
under -
C and find out the number of uncommon nodes
between them. Then we sum up all the s \Phi ( -
C ) to
Similarly, we calculate S \Phi
in descending order of
their similarity values with Q 1 , and return the result to the
user.
VII. Conclusions
We have developed a new method using compact disjunctive
normal form (CDNF) to rank the similarity between
Boolean expressions. We compared our method with
LI AND DANZIG: BOOLEAN SIMILARITY MEASURES FOR RESOURCE DISCOVERY 13
Radecki's measure on two databases and used the Spearman
rank coefficients and the confidence intervals to show
that our method can get a closer ranking order to that
generated by Jaccard's coefficient. The theoretical analysis
proves that this new measure outperforms the one proposed
by Radecki significantly in terms of time and space
complexity. These results demonstrate that our similarity
measure can greatly improve the searching process in
today's world of overwhelming information.
In addition to ranking results, similarity estimates can
be used to help identify similar but autonomously managed
retrieval systems. For example, the similarity measure can
be used to cluster servers with similar descriptions in a single
directory entry. When the similarity measures of two
servers exceed a certain value, they can be merged to remove
redundancy. Moreover, the administrator can create
new servers by using the most frequently asked queries as
the filter and select other relevant servers as its information
sources. Thus, most user queries can be satisfied by
a small number of servers which reduces search time. For
people using Boolean expressions to represent their inter-
ests, such as collaborative filtering [19] or user profile [20],
[21], similarity measure can help find other individuals having
common interests, so that they may share their collec-
tions. Our method can also benefit systems that support
automatic query formulations by relevance-feedback [22],
[23], where the reformed queries could be in complex
Boolean forms.



--R

"Vocabulary problem in Internet resource discovery"
"Essence: A resource discovery system based on semantic file indexing"
"An information system for corporate users: Wide Area Information Servers"
"Distributed indexing of autonomous Internet services"
"A direct manipulation interface for Boolean information retrieval via natural language query"
"A graphical filter/flow representation of Boolean queries: A prototype implementation and evaluation"
"Algorithms for automatic construction of query formulations in Boolean form"
"Internet resource discovery services"
"Archie: An electronic directory service for the Internet"
"A content routing system for distributed information servers"
"The efficacy of GlOSS for the text database discovery problem"
Information Retrieval
"A model of a document-clustering-based information retrieval system with a Boolean search request formu- lation"
"Similarity measures for Boolean search request formulations"
Rank Correlation Meth- ods
The Art of Computer Systems Performance Analysis

"Boolean similarity measures for resource discovery"
"Using collaborative filtering to weave an information tapestry"
"Modeling of user preferences and needs in Boolean retrieval systems"
"Index structures for selective dissemination of information under the Boolean model"
"The use of automatic relevance feedback in Boolean retrieval systems"
"Ad- vanced feedback methods in information retrieval"
--TR

--CTR
Rashid Ali , M. M. Sufyan Beg, A comprehensive model for web search evaluation, Proceedings of the 5th WSEAS International Conference on Circuits, Systems, Electronics, Control & Signal Processing, p.159-164, November 01-03, 2006, Dallas, Texas
Katia Sycara , Seth Widoff , Matthias Klusch , Jianguo Lu, Larks: Dynamic Matchmaking Among Heterogeneous Software Agents in Cyberspace, Autonomous Agents and Multi-Agent Systems, v.5 n.2, p.173-203, June 2002
Charles L. A. Clarke , Gordon V. Cormack, Shortest-substring retrieval and ranking, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.44-78, Jan. 2000
Weiyi Meng , Clement Yu , King-Lup Liu, Building efficient and effective metasearch engines, ACM Computing Surveys (CSUR), v.34 n.1, p.48-89, March 2002
resource discovery;ranking;boolean query;information retrieval;similarity measure