Static index pruning methods have been proposed to reduce size of the inverted index of information retrieval systems. The goal is to increase efficiency (in terms of query response time) while preserving effectiveness (in terms of ranking quality). Current state-of-the-art approaches include the term-centric pruning approach and the document-centric pruning approach. While the term-centric pruning considers each inverted list independently and removes less important postings from each inverted list, the document-centric approach considers each document independently and removes less important terms from each document. In other words, the term-centric approach does not consider the relative importance of a posting in comparison with others in the same document, and the document-centric approach does not consider the relative importance of a posting in comparison with others in the same inverted list. The consequence is less important postings are not pruned in some situations, and important postings are pruned in some other situations. We propose a posting-based pruning approach, which is a generalization of both the term-centric and document-centric approaches. This approach ranks all postings and keeps only a subset of top ranked ones. The rank of a posting depends on several factors, such as its rank in its inverted list, its rank in its document, its weighting score, the term weight and the document weight. The effectiveness of our approach is verified by experiments using TREC queries and TREC datasets.
Copyright © 2009 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. Re-publication of material from this volume requires permission by the copyright owners. This volume is published by its editors.
LSDS-IR Workshop. July 2009. Boston, USA.
Text information retrieval systems are based on an inverted index to efficiently process queries. The most important part of an inverted index is its inverted file, a file that contains posting list for each term in the text collection [1]. In general, a posting list of a term contains its posting entries (or index pointers), each in the form of <docID, freq>, where docID is the ID of a document that contains the term, and freq is its frequency in the document. For a multi-keyword query, all posting lists of query terms are retrieved from the inverted file, and document scores are accumulated for each document in the union of the posting lists, based on a specified weighting scheme. A list of documents in descending order of rank scores is presented to the user.
For a large text corpus, the inverted file is too large to fit into memory of the search server. Thus, query processing involves a lot of disk access, which increases query response time. For a text information retrieval system that has to process thousands of queries per second, it is critical to improve query processing performance.
Beside the parallel query processing approach that uses a cluster
of servers to process queries, the index compression approach is
widely used. The lossless compression approach uses data
compression techniques to compress index data, thereby reducing
the volume of data transferred from disk. The compressed index
data is then decompressed in memory, and queries are processed
based on the original index information. Common data
compression technique used in information retrieval systems is
variable length data coding [2]. In contrast, lossy compression
approach opts for keeping only important information in the
index, discarding other less important information [4][
In this work, we concentrate on lossy index compression. Current
state-of-the-art approaches include term-centric pruning [
We propose a posting-based pruning approach, which is a generalization of both the term-centric and document-centric approaches. Our approach ranks all postings and keeps only a subset of the top ranked ones, removing the others. We consider a couple of factors when ranking a posting, such as its rank in its posting list, its rank in its document, its weighting score, the normalized weight of the term, and the normalized weight of the document. Our experiments based on TREC queries and TREC datasets [22] show that posting-based pruning method outperforms both the term-centric and document-centric methods.
Lossless index compression techniques are well studied, for example, see Witten et al. [2][3]. Those techniques are mainly based on the fact that the frequencies of terms in documents, which are stored in the inverted index, follow a skewed distribution. In that case, variable length coding technique can be used to encode index information, consuming only a few bits for most of term frequency values. In general, this helps to reduce index size by about one-tenth. However, for large scale information retrieval systems, the compressed index is still too big to fit into memory. In addition, using a compressed index reduces time to access index data from disk, but does not reduce time to process the posting lists. Thus, using lossless index compression alone cannot significantly improve efficiency.
Lossy index compression techniques opt for discarding postings that are not informative. By removing a large number of postings from the inverted index, lossy index compression techniques not only significantly reduce index size, but also significantly reduce length of posting lists. Therefore, lossy index compression techniques can reduce both time to access index data from disk and time to process posting lists. However, as some index information is lost, lossy index compression techniques may lead to a drop in query ranking quality.
In [
Buttcher and Clarke introduce a document-centric pruning
technique [
Other index pruning techniques (some are for distributed,
peer-topeer information retrieval systems) belong to either the
termcentric approach or document-centric approach. Blanco et al. [
Looking at other aspect of static index pruning, Skobeltsyn et al.
[
Term-centric pruning fits very well with the inverted index
structure of information retrieval systems. As queries are
processed based on inverted lists, it is natural to truncate inverted
lists in order to reduce index size. Based on the inverted index
structure, the “idealized, term-based” pruning technique proposed
by Carmel et al. is well-formed and mathematically provable. This
clearly shows that a pruned index, even though not containing all
information, still can guarantee the ranking quality to some extent
[
There are several properties that are specific to term-centric
pruning. It preserves the collection vocabulary. For every term,
there are always some entries in its inverted list in the pruned
index. (The works of Blanco et al. [
Document-centric pruning does not make any assumption about the index structure and how queries are processed. Precisely, document-centric pruning should be considered as a “data” pruning technique instead of an index pruning technique, as what it actually does is to prune the documents, not an index structure. In contrast to term-centric pruning, document-centric pruning preserves the set of documents, not the set of terms. While any document in the collection is represented by a subset of its terms (i.e., its set of representative terms), there is no guarantee that every term will be indexed. It is likely that there are terms that are always ranked low in any document and are removed by document-centric pruning.
The first assumption implied by document-centric pruning is that every document can be ranked first by some queries (one such query might be the query that contains all its representative terms). Due to this assumption, document-centric pruning opts for including every document in the pruned index. The second implied assumption is that terms are not equally important, and some terms can be totally removed from the pruned index.
As pointed out above, term-centric pruning prunes index elements, which are posting lists; while document-centric pruning prunes data elements, which are documents. Both approaches assume that all elements are equally important, and thus the pruned index should keep some information about every element, either they are posting lists or documents.
We first find that the decision to keep some amount of information for each posting list or document to be reasonable. Without any information about the user queries, we must assume any term can be used by users. Thus no term can be totally removed. Similarly, without any information about what users will search for, we also have to assume any document can be an answer (to some queries). Therefore, no document can be totally removed.
However, given the requirement of significantly reducing index size, it is not affordable to keep information for all posting lists and all documents. We believe that the pruned index should contain neither all terms, nor all documents, but only the most important postings, given the desired pruning level.
We suspect that non-informative terms are common in any large
text collection. Non-informative terms are those terms that do not
help to discriminate documents. One example of non-informative
terms is a term that appears in every document, such as the term
“abstract” in a collection of scientific papers. Those terms are
expected to have similar weighting scores to every document.
Therefore, eliminating those terms will not hurt ranking quality.
Unfortunately, term-centric pruning tends not to prune any entries
from the posting lists of those terms. The reason is, as entry scores
are almost similar, all scores are likely to be greater than the
threshold value computed by the term-based method proposed in
[
We also suspect that there are many “rarely asked for” documents
in any large text collection. A document is called “rarely asked
for” if it does not appear in the top-ranked results of any real
world query. In practice, users normally look at only the top 20
results, so any document that does not appear in the top-20 results
of a large number of queries can be removed. Puppin et al. [
When building a pruned index, terms should not be treated
equally. Non-informative terms appear in a large number of
documents, results in long posting lists. However,
noninformative terms do not help much in ranking documents. Thus,
the pruned index should significantly prune the posting lists of
non-informative terms and reserve places for other informative
terms. Our posting-based pruning method assigns a weight to each
term as its informativeness value. Blanco and Barreiro [
Documents in a large text collection are not equally important and
therefore, in the pruned index, more terms should be kept for
important documents. As for term weighting, we also assign a
weight to each document in the collection to reflect how
important it is. For a Web collection, the PageRank [
KLD(d || C ) = ∑t∈d t|fd(t|) log t|fd(t|) × T|FC(t|) (2) where tf(t) is the term frequency of term t, TF(t) is the collection term frequency of term t, |d| is the length of document d (i.e., the number of terms in d), and |C| is the length of the collection (i.e., the sum of document lengths).
Our static pruning method evaluates postings and assigns each a usefulness value. We then build the pruned index based on these values. Given a desired level of pruning, posting entries are selected based on their usefulness values and added into the pruned index until the pruned index size reaches its limit. According to term-centric pruning, we should assign a high usefulness value to a posting entry which appears at the top of its posting list. According to document-centric pruning, we should not assign a high usefulness value to a posting whose term does not belong to the set of top-ranked terms of the document. In addition, as discussed above, we should assign low values to noninformative terms and “rarely asked for” documents, and vice versa. Also, we obviously want to assign high usefulness value to posting entries with high scores.
To rank postings, for each posting <t, d>, we compute the following quantities: • • • • •
S(t, d) = the score term t contributes to the rank score of document d.
RIDF(t) = the informativeness value of term t.
KLD(d || C) = the important value of document d.
Rank(t) = the rank of term t relatively with other terms in document d.
Rank(d) = the rank of document d relatively with other documents in the posting list of term t.
Among the quantities above, S(t, d) is computed using a
weighting scheme, such as the classic TFIDF weighting scheme,
or the state-of-the-art BM25 weighting scheme; RIDF(t) is
calculated as specified in (1); KLD(d || C) is calculated according
to (2); Rank(d) is the position of document d in the posting list of
term t, where posting entries are sorted in descending order of its
scores S(t,di); and Rank(t) is the position of term t in document d,
where terms are sorted in descending order of its “feedback” score
[
ScoreDCP (t) = | tdf | log | tdf | × |TCF|
In this work, we use the BM25 weighting scheme [
S BM 25 (t, d ) = log N - df + 0.5 × df + 0.5
tf (k1 + 1) tf + k1 (1 - b) + b a|vdgd| l where avgdl is the average length of documents, k1 is set to its “standard” value of 1.2 and b is set to its “standard” value of 0.75.
In combination, our posting entry ranking function takes as parameters all the above quantities and returns a usefulness value. Note that we apply normalization and transformation to parameter values. First, RIDF(t) values are normalized so that they sum up to one. Similar normalization is applied to KLD(d || C) values. Normalization step is necessary, as the range of RIDF(t) and KLD(d || C) are different. Second, we use a sigmoid function to (3) (4) 1 transform the term rank values and document rank values. This transformation is necessary, too. Using the term rank values makes it appears that the 10th term is ten time less important than the top ranked term, which does not seem right. Therefore, we use a non-linear function specified below (5) as a transform function. The parameter x0 is used to shift the “transition” point, where the sigmoid function switches from high value state to low value state, and the parameter a is used to control the slope of the transition period of the function.
sigmoid (x) = 1 - 1 + e(-1x+x0) a (5) The sigmoid function above returns a value between zero and one. Rank value close to zero (i.e., top ranked element) will be transformed to a value close to one, while other rank values will be transformed depend on two parameters x0 and a. In Figure 1, we show the shape of the sigmoid function for several combinations of parameters.
1 16 31 61 76
91 46
Rank
We show that our posting entry ranking function generalizes document-centric index pruning method and term-centric pruning method.
If we set the value of α to zero, replace the document weighting
function KLD(d||C) with the unity function u(d) = 1, and set the
parameter a of the sigmoid function to 1 so that the sigmoid
function in (5) becomes a threshold function at x0, then for each
document d, our ranking function f() assigns a non-zero value to
the posting entry <t, d> if t is ranked in the top-x0 among all
unique terms in d, otherwise f() returns a zero value. In this case,
our posting-based pruning technique is equivalent to the
“constant” document-centric pruning technique proposed by
Buttcher and Clarke in [
Similarly, if we set the value of α to one, replace the term
weighting function RIDF(t) with the unity function u(t) = 1, set
the parameter a of the sigmoid function to 1, and set the parameter
x0 to the rank of the i-th posting entry in the posting list of term t
such that S(t, di) > τ (t) and S(t, di+1) ≤ τ (t), where τ (t) is the
cutoff threshold proposed by Carmel et al. in [
Our posting-based pruning technique is different from termcentric and document-centric pruning techniques in several aspects. By using term weighting function and document weighting function other than the unity function, we allow the pruned index to include more information for informative terms and outstanding documents. By using a sigmoid function instead of a threshold function to transform the term and document ranks, we open the possibility that a posting entry which is ranked low in a posting list could be selected, if it is ranked high in the document, and vice versa.
We use the WT10G collection as our data set. This collection
contains 1,692,096 Web documents crawled from the Web. We
use the Terrier platform [
We use the BM25 weighting scheme for both calculating termdocument scores and query ranking. Potter stemming algorithm [23] and a standard list of stop-words are used for preprocessing documents. After stemming and stop-word removal, the vocabulary contains 3,161,488 unique terms. The un-pruned index contains 280,632,807 posting entries.
We use TREC [22] topics 451–500 as our query set. Precision is
measured for each pruned index using the set of relevance
judgment provided by TREC for topics 451–500. From TREC
topics 451–500, we build two sets of queries: one set of long
queries, wherein each query includes the title and the description
fields from the TREC topic, and one set of short queries, wherein
each query includes only the title field from the TREC topic.
We also implement term-centric index pruning and
documentcentric index pruning exactly as specified in their original works
[
We conduct experiments to compare the effectiveness of our
proposed posting-based pruning technique with the term-based,
“score shifting” pruning technique proposed in [
In Figure 2, we show the effectiveness of pruned indices for the set of short TREC queries; and in Figure 3, we show the effectiveness of pruned indices for the set of long TREC queries. Posting-centric pruned index is marked as “pXX_YY_ZZ”, where XX is the value of parameter α (percentage), YY is the value of parameter a, and ZZ is the value of parameter x0. Figure 2 and Figure 3 show experiment results for a posting-centric pruned index with α = 50%, a = 15, and x0 = 50. With the pruning level less than 70%, posting-centric pruning has similar performance as compare with document-centric pruning and term-centric pruning. However, for pruning level of 70% or more, posting-centric pruning is outperformed by document-centric pruning. We turn our parameters for posting-centric index pruning technique. Table 1, Table 2, and Table 3 show experiment results for short queries of document-centric pruning technique and posting-centric pruning techniques with various combinations of parameter values. Experiments with long queries have similar trend and therefore are omitted.
In Table 1, Table 2, and Table 3, the values in bold are the highest performance for a specific pruning level. The first observation is that posting-centric pruning is better at low and moderate pruning level, while document-centric pruning is better at higher pruning level. The second observation is that, even though posting-centric pruning is better than document-centric pruning at low and moderate pruning level, the differences are small. In contrast, at higher pruning level, the differences between the performance of posting-centric pruning and document-centric pruning are larger. In addition, none of the posting-centric pruning techniques outperforms document-centric pruning technique at high pruning level.
In all previous experiments of posting-centric pruning technique, parameters of the posting entry ranking function (6) are fixed for all posting entries. We consider the possibility of adaptively setting parameters for each posting entry, by adapting the slope of the sigmoid function as follows. For a posting entry <t, d>, we use two sigmoid functions, one for the rank of term t in the document d, the other for the rank of document d in the posting list of term t. We call the former document-oriented sigmoid function, and the later term-oriented sigmoid function. For the term-oriented sigmoid function, its x0 parameter is set according to the pruning level (i.e., if the pruning level is 90%, x0 is equal to 10% of the length of the term posting list). Similarly, for the document-oriented sigmoid function, if the pruning level is 90%, its x0 parameter is set to 10% of the number of unique terms in the document. For both sigmoid functions, the parameter a, which control the slope of the function, is set so that the function returns a value close to 1 for input value which is less than 0.9 × x0 and returns a value close to 0 for input value which is greater than 1.1 × x0. We also explore the performance of several alternatives, which may or may not use term-weighting and/or documentweighting (refer to the ranking function (6) in Section 4.3). In Table 4, we report the performance of different alternatives at the approximately 90% pruning level. Document-centric pruning performance is included for reference. For each column, the best value is in bold. From the results reported in Table 4, we can see that: (i) (ii) (iii)
Term-document scores should be used in the posting entry ranking function (6), which is revealed by the significant differences between the performance of AP1 and AP2.
Term-weighting is useful, which is confirmed by the differences between the performance of AP1 and AP3. Document weighting seems to be harmful, which hurt the performance of AP4, compare to the performance of AP3 and AP1.
Among all alternatives, AP3 is the best, which is only slightly outperformed by document-centric pruning for long queries according to MAP. We therefore consider it as the best among our alternatives. Below, we report its performance in comparison with document-centric pruning and term-centric pruning at various level of pruning in Figure 4 and Figure 5.
By adapting the sigmoid functions to posting entries, the performance of our posting-centric pruning technique is much better, as good as the performance of document-centric pruning technique (posting-centric pruning is better than document-centric pruning at some pruning level, while the inverse is true at other pruning levels).
We evaluate document-centric and term-centric static index pruning based on the WT10G corpus and TREC query sets. Based on our experimental results, term-centric index pruning is better than document-centric index pruning at low and moderate pruning level (i.e., less than 70% pruning, according to our results), while document-centric index pruning is better at higher pruning level. We propose posting-centric index pruning technique, which ranks each posting entry (i.e., a term-document pair) based on a set of features such as the rank of the term in the document and the rank of the document in the inverted list of the term. We show that posting-centric index pruning generalizes both document-centric and term-centric pruning, and therefore, the solution space of term-centric pruning covers the solution spaces of both documentcentric and term-centric index pruning. This implies that, by exploring this larger solution space, better solution can be found. We explore the solution space of posting-centric pruning by studying a family of posting entry ranking functions. We discover that term weighting based on RIDF is useful, while document weighting based on KL-divergence is harmful. We also notice that parameters of the sigmoid function, which we use to transform the rank of a term/document to its score, should be adapted to each posting entry. Fixing these parameters makes posting-centric pruning less effective than document-centric pruning. Other term weighting and document weighting methods are possible. We are evaluating a method of weighting terms and documents based on user queries and the PageRank algorithm applying on the graph of terms and documents. Our goal is to discover important terms and documents by analyzing the relationship among terms and documents given the context of user queries. Once the important terms and the important documents are discovered, their information is kept in the pruned index, while information about others, less important terms and documents, can be partially removed or totally discarded.
[22] TREC (WT10G, TREC-9)