Query expansion using Haar wavelet transform

Abstract

Novice users are unable to express their information needs properly, due to this it is difficult to retrieve all the desired relevant documents from the test collection. The problem of word mismatch is fundamental to information retrieval. Query expansion is a technique in which additional terms are added to retrieve relevant documents. In this article, we have expanded the query using pseudo-relevance feedback and Haar wavelet transform. The performance of the proposed technique is evaluated on FIRE 2011 ad hoc English test Collection and Robust dataset. The mean average precision of the proposed model on the FIRE dataset and Robust Track dataset is 0.3334 and 0.2724, respectively.

Keywords

Haar wavelet Hilbert space information retrieval query expansion term signal wavelet transform

1. Introduction

In information retrieval (IR), the user poses a query to search engines and it retrieves documents that are relevant to the user query. The problem of word mismatch is fundamental in IR. The words of query might not appear in a document despite it being relevant to the query. In such cases, a non-retrieved document might contain relevant information. Query Expansion is a technique to overcome the problem of word mismatch. In this technique, after retrieving an initial set of documents the original query is expanded by appending additional words that are obtained by applying some or other technique on top k retrieved documents. It reformulates the original query to improve retrieval performance. The expansion words may be synonyms of words, semantically related words (like antonyms, hyponyms, etc.), or various morphological forms of words. Global and local methods are two major classes of query expansion. Pseudo-relevance feedback also known as blind relevance feedback is one of the local methods. Local methods adjust the query relative to the document that initially appears to match the query [1]. It retrieves an initial set of relevant documents, then assumes that top ‘k’ rank documents are relevant, and from these top ‘k’ documents expansion terms are automatically selected. In Global methods, expansion terms are selected from large corpora. Global methods use semantically similar terms to the original query terms. It uses thesaurus-based query expansion. Global methods are broadly classified into four categories: (a) linguistic-based, (b) corpus-based, (c) search log-based and (d) web-based.

Vector space [2,3] and probabilistic [4] methods are based on the hypothesis that the document is relevant to query if it contains more occurrences of the query terms in the document. Generally, these are similarity-based methods. In vector space, query and documents are represented as a vector in which each term represents a dimension in that space. Some IR methods are based on term proximity and are known as proximity-based methods. Clarke and Cormack [5] proposed a hypothesis that the document is more relevant to the query if query terms are found in smaller proximity to each other. In this positional information is used to achieve higher precision.

Spectral-based document retrieval is a mix of vector and proximity model. It finds relevant documents by considering the query term occurrence pattern in the documents. The documents that follow similar positional patterns are considered more relevant than those documents in which query term does not follow a similar pattern. Spectral-based retrieval compares query terms in spectral domain rather than the spatial domain. Wavelet transform is used for spectral-based document retrieval. Wavelet transform is a mathematical tool which allows us to break the given signal into a wavelet of different scale and position. It allows us to analyse the signal at different frequencies and its positions.

The proposed work is motivated by the work of Park et al. [6]. They proposed document retrieval using discrete wavelet transform. Alnofaie et al. [7] used wavelet transform for document ranking and then query is expanded using Kullback–Leibler (KL) divergence. KL divergence is applied on top ‘k’ retrieved documents.

Our proposed query expansion method uses pseudo-relevance feedback and Haar wavelet transform for query expansion. The spectral concept is applied on documents that are obtained after the initial round of retrieval for selecting expansion terms. It analyzes query term frequency and its position in the initial retrieved documents. The partition (component) of a document, in which query terms are close to each other is selected as expansion region and from it, all terms are selected for query expansion. The novelty in the proposed method is that we have applied Haar wavelet transform for query expansion instead of document retrieval and ranking [6]. The architecture of proposed model is shown in Figure 1. The proposed method is also compared with the existing query expansion methods. The article is organised as follows: Section 2 discusses related work. Sections 3 and 4 discuss multi-resolution and wavelet transform. Section 5 discusses query expansion and discrete Haar wavelet and the proposed algorithm is also presented in this section. Section 6 presents experimental results. Section 7 analyses the result. Section 8 presents the conclusion and future work.

Figure 1.

Process of query expansion using Haar wavelet transform.

2. Related work

A number of document ranking and expansion models are proposed over the years to improve the performance of the retrieval system. Query Expansion is a technique to improve the performance of the retrieval system by appending few terms in the initial query [8]. Salton and Buckley [9] proposed relevance feedback using vector space model. Rocchio Algorithm is one of the oldest algorithms based on the vector space model [10]. Singhal et al. [11] showed that better results are obtained by using only documents that are close to the query. Koenemann and Belkin [12] did user study for the effectiveness of relevance feedback. Riezler et al. [13] used statistical Natural Language Processing (NLP) approach for Relevance Feedback. Qiu and Frei [14] and Schütze [15] used automatic thesaurus generation for query expansion. Miller [16] proposed thesaurus (WordNet)-based query expansion technique. It uses synonyms words of the query words for expansion. The approach faces a query drifting problem. To avoid query drifting, Leung et al. [17] proposed a context-aware personalised query suggestion clustering-based technique. In this technique, instead of suggesting a similar query to every user, they suggested clustered user click-through data to anticipate user intention. Session-based [18] query term suggestion is another important query expansion technique that asserts that every search query on the same session is related to one or another in a way or two. Ganguly et al. [19] proposed query expansion technique based on sentence similarity. They used sentences instead of adding terms, and they concluded that their method outperforms the previous state-of-the-art methods. Latiri-Cherif et al. [20] used fuzzy-based query expansion technique to improve the performance of the retrieval system. Bhogal et al. [21] proposed ontology heredity concept to find the expansion terms by calculating the similarity between ontology and query words. Previous studies [22 –24] proposed latent semantic indexing, probabilistic latent semantic indexing and latent Dirichlet allocation method. They tried to reduce the query mismatch problem by finding semantically related terms for query expansion. ALMasri et al. [25] make a comparison among deep learning–based technique, pseudo-relevance feedback technique and mutual information–based technique. Xu and Croft [26] proposed query expansion using global and local document analysis and showed that both global and local analysis technique is more effective than simple local feedback. Zingla et al. [27] proposed hybrid query expansion technique for text and microblog IR. El Mahdaouy et al. [28] proposed word-embedding-based pseudo-relevance feedback-based query expansion technique for Arbic IR.

Wavelet transform plays a very important role in text analysis and text retrieval [29]. Miller et al. [30] used wavelet transform in text document at a different portion of the document, containing the main topic related to the query for ranking the document. The literature reveals that the performance of the IR system degrades due to word mismatch and query drift problems.

3. Term signal of document

A wavelet function is defined by $ψ$ , which is the subset of $L^{2} (R)$ , that is, wavelet functions lie on Hilbert Space [31]. In the context of the document, wavelet transform analyses the document at different resolution. In this approach, each document is divided into $2^{i}$ components (in this case i = 3), where $i = 1, 2, 3, . . .$ and in each component frequency of query terms are counted. Let d be the document and t is the query term, then term signal for document d is represented by

f_{d, t} = [f_{d, t, 0}, f_{d, t, 1}, \dots, f_{d, t, B - 1}]

where $f_{d, t, b}$ is the value of term signal in the $b th$ component of document d. If there are B components and the total number of terms in the document is D, then value of $b th$ component for term signal t in the document d is computed by counting the occurrence of term t between $\frac{bD}{B} th$ word in the document and $(\frac{(b + 1) D}{B} - 1) th$ word in the document. In wavelet transform, document retrieval is a generalisation of the vector space model. In terms of signal representation of document d, if B = 1, then there is only one component for each query term and thus it behaves like a vector space model. The score, in this case, is computed by the following formula

s_{d, 0} = \sum_{t \in q} w_{q, t} w_{d, t, 0}

where $s_{d, 0}$ is score of the first component in the eight-component document d, $w_{q, t}$ is weight of term t in query q and $w_{d, t, 0}$ is weight of term t in the first component of document d. Using $l_{1}$ norms we have

s_{d} = \sum_{t \in q} w_{q, t} w_{d, t, 0}

$s_{d}$ is combined component score of document d, which is same as vector space model.

4. Multi-resolution and wavelet transform

Fourier transform [32] and family of unitary transform [33] provide information about the frequency component that exists in the signal. The transformation is useful for a stationary signal where frequency exists as a whole. In-text retrieval Fourier transform gives the frequency of query terms for the whole document. It does not provide frequency information at different positions of the document. Discrete Fourier transform of term signal $f (t)$ with frequency $ω$ is given by

f [ω] = \sum_{t = 0}^{T - 1} f [t] \exp [- 2 π i ω t / T]

where $i = \sqrt{- 1}$ and T is the length of the signal. The transform score is higher if it has a cyclic positional pattern for query terms. The transform examines the signal as a whole. It does not examine different frequencies at different positions of the document.

Short-time Fourier transform (STFT) [34] is another transform which transforms term signal into frequency domain. The STFT of term signal f(t) with frequency $ω$ is given by

S f [υ, ω] = \sum_{t = 0}^{T - 1} f [t] g [t - υ] \exp [- 2 π i ω t / T]

where g[t−v] is the window function centred at v.

The resolution must be set in order to extract certain time-frequency information from a signal in STFT. By using the STFT, we could tell where in time the impulses occurred, but we would only be able to notice high-frequency changes. Any slow changes to the signal are not noticeable in the frequency analysis due to windowing.

Multi-resolution analysis (MRA) is required to examine a signal across different time-frequency resolution scales. To achieve this, wavelet transform [35] is applied.

A wavelet is a small wave of finite length. A wavelet is scaled and translated with parameters b and a, respectively

ψ_{a, b} (t) = \frac{1}{\sqrt{b}} ψ (\frac{t - a}{b})

Scaling factor keeps the norm equal to one. The wavelet transform of f(t) $\in L^{2} (R)$ is given by

W (a, b) = \int_{- \infty}^{\infty} f (t) \frac{1}{\sqrt{b}} ψ^{☆} (\frac{t - a}{b}) dt

where $ψ^{☆}$ represents complex conjugate of $ψ$ . For a given wavelet function, scaling function $ϕ_{a, b} (t) \in V_{n}$ must satisfy the following condition

{0} \subset . . \subset V_{n + 2} \subset V_{n + 1} \subset V_{n} \subset V_{n - 1} \subset V_{n - 2} \subset . . . \subset L^{2} (R)

where set of $ϕ_{a, b} (t)$ for all a is basis of $V_{n}$ , $b = 2^{n}$ and $⋃_{n \in Z} V_{n} = L^{2} (R)$ . $V_{n}$ is the subspace spanned by scaling function and n is the set of integers. The relation of $V_{n}$ and $W_{n}$ is shown in Figure 2.

Figure 2.

Enclosing scaling function $(ϕ_{a, b} (t) \in V_{n})$ space as oval and the wavelet function space $(ψ_{a, b} (t) \in W_{n})$ as annuli [6].

From Figure 2, the following holds

V_{n - 1} = V_{n} ⋃_{} W_{n - 1}, V_{n} ⊥ W_{n - 1}

also

⋃_{n \in Z} W_{n} = L^{2} (R), ⋂_{n \in Z} W_{n} = \emptyset

Wavelet transform is applied to the word signal, and it gives the position of the word in the desired resolution.

A wavelet must satisfy the following properties

(1) It has zero mean, that is

\int_{- \infty}^{\infty} ψ (t) dt = 0

(2) Unit norm, that is

\int_{- \infty}^{\infty} | ψ (t {) |}^{2} dt = 1

(3)It has vanishing moment, that is, $ψ$ should be continuous function with a higher number M of vanishing moment, for all $m < M$

\int_{- \infty}^{\infty} t^{m} ψ (t) dt = 0

(4) The Fourier transform of $ψ (t)$ must satisfy the admissibility condition given by

C_{ψ} = \int_{- \infty}^{\infty} \frac{| ψ (ω {) |}^{2}}{ω} d ω < \infty

For a continuous wavelet, scaling function can be set at any scale while in case of discrete wavelet scaling is allowed only dyadic scale, that is, for a discrete wavelet if scaling function $ϕ_{a, b} (t) \in V_{n}$ then $ϕ_{a, b} (2 t) \in V_{n + 1}$ , $ϕ_{a, b} (4 t) \in V_{n + 2}$ and so on.

5. Query expansion and discrete Haar wavelet transform

The family of N Haar functions $h_{k} (t)$ [36,37] (k = 0, 1, 2, …, N−1) are defined on the interval $0 \leq t \leq 1$ . The shape of specific function $h_{k} (t)$ of a given index depends on p and q. The value of k is determined by

k = 2^{p} + q - 1

for any values of $k \geq 0$ , p and q are uniquely determined so that $2^{p} \leq k$ and $q - 1 = k - 2^{p}$ . For example, when N = 8, index k with corresponding p and q are shown in Table 1.

Table 1.

Determining value of k, p and q for Haar transform.

k	0	1	2	3	4	5	6	7
p	0	0	1	1	2	2	2	2
q	0	1	1	2	1	2	3	4

Now Haar function can be defined as

when $k = 0$

h_{0} (t) = \frac{1}{\sqrt{N}}

when $k > 0$

h_{k} (t) = \frac{1}{\sqrt{N}} {\begin{matrix} 2^{p / 2}, & for \frac{(q - 1)}{2^{p}} \leq t < \frac{(q - \frac{1}{2})}{2^{p}} \\ - 2^{p / 2}, & for \frac{(q - \frac{1}{2})}{2^{p}} \leq t < \frac{(q)}{2^{p}} \\ 0, & otherwise \end{matrix}}

where p specifies the magnitude and width (or scale) of the shape and q specifies the position of the shape (shift). The Haar transform is real and orthogonal, that is

H = H^{*}, H^{- 1} = H^{T}

The value of t is computed as $t = (\frac{m}{N})$ , where m = 0, 1, 2, …, N−1 to form an N×N matrix. So for N = 8, $c = \frac{1}{\sqrt{8}}$

H_{8} = c [\begin{matrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & - 1 & - 1 & - 1 & - 1 \\ \sqrt{2} & \sqrt{2} & - \sqrt{2} & - \sqrt{2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & \sqrt{2} & \sqrt{2} & - \sqrt{2} & - \sqrt{2} \\ 2 & - 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & - 2 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 & - 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 2 & - 2 \end{matrix}]

Haar transform for word signal gives the location of the word at different wavelet components. In the proposed method, initially, the user issues a query, and in response to it, the system returns an initial set of ‘k’ documents. The proposed method does an automatic local analysis using Haar wavelet on these top ‘k’ retrieved documents. The Haar wavelet helps in automatically searching the expansion region in the top k retrieved documents. The expansion terms are then selected from the spectral domain rather than the spatial domain. Finally, the expansion terms are appended in the initial query for the final round of retrieval. Figure 1 describes the Haar wavelet-based query expansion method. The proposed algorithm is shown in algorithm 1.

Algorithm 1.

Wavelet Query Expansion HWQE(Q[],D[]).

1: Retrieve top k documents from D and store them in

D_{k}

.
2: for

d \in D_{k}

do
3: for

t \in Q

do
4: calculate

f_{d, t} \leftarrow [f_{d, t, 0}, f_{d, t, 1}, f_{d, t, 2}, \dots, f_{d, t, 7}]

5: end for
6: end for
7:

exptf \leftarrow []

8: for

d \in D_{k}

do
9: for

t \in Q

do
10: calculate

W_{d, t} \leftarrow H_{8} . transpose (f_{d, t})

11: end for
12: end for
13: for

t \in Q

do
14:

ex p_{t} \leftarrow []

15: end for
16: for

d \in D_{k}

do
17: for

t \in Q

do
18: if

W_{d, t, 1} \geq 0

then
19: if

W_{d, t, 2} \geq 0

then
20: if

W_{d, t, 4} \geq 0

then
21:

ex p_{t} \leftarrow

First component of d
22: else
23:

ex p_{t} \leftarrow

Second component of d
24: end if
25: else
26: if

W_{d, t, 5} \geq 0

then
27:

ex p_{t} \leftarrow

Third component of d
28: else
29:

ex p_{t} \leftarrow

Fourth component of d
30: end if
31: end if
32: else
33: if

W_{d, t, 3} \geq 0

then
34: if

W_{d, t, 6} \geq 0

then
35:

ex p_{t} \leftarrow

Fifth component of d
36: else
37:

ex p_{t} \leftarrow

Sixth component of d
38: end if
39: else
40: if

W_{d, t, 6} \geq 0

then
41:

ex p_{t} \leftarrow

Seventh component of d
42: else
43:

ex p_{t} \leftarrow

last component of d
44: end if
45: end if
46: end if
47: end for
48:

exptf [] \leftarrow ex p_{t}

49: end for
50:

\exp \leftarrow exptf [0]

51: for

t \in Q

and $ex p_{t} \in exptf$ do
52:

\exp \leftarrow \exp \cap ex p_{t}

53: end for
54: if

Length (\exp) < 15

then
55: Append all terms to original query and store in qexp.
56: else
57: Calculate

P (t / Q)

, where

t \in \exp

58: Retrieve top 15 terms from exp with

maxP (t / Q)

59: Append 15 terms along with original query in qexp .
60: end if
61: return qexp

For example, if the term signal of query term ‘cosmic’ in a document d is computed as [3,1,0,0,2,1,1,1] where 3, 1, 0, 0, 2, 1, 1, 1 is the occurrences of term ‘cosmic’ in the first, second, third, fourth, fifth, sixth, seventh and eighth component of document d, respectively, then spectral vector for query term ‘cosmic’ is computed as $[\frac{9}{\sqrt{8}}, \frac{- 1}{\sqrt{8}}, 2, \frac{1}{2}, \frac{4}{\sqrt{8}}, 0, \frac{2}{\sqrt{8}}, 0]$ . The second component of the spectral vector contains a negative value; therefore, the second half of the term signal ‘cosmic’ [2,1,1,1] (2 + 1 + 1 + 1 = 5) has more number of occurrences than the first half [3,1,0,0] (3 + 1 + 0 + 0 = 4) in the term signal vector. Therefore, method directly enters the second half of the term signal vector, and there is no need to check the third component of the spectral vector as it contains the information about the number of occurrences of the term ‘cosmic’ in the first fourth [3,1] and second fourth [0,0] in the first half of the term signal. Similarly, the fourth component of the spectral contains a positive value which suggests to the system that the third fourth [2,1] of the signal vector has more occurrences than the last fourth [1,1]. Therefore, method directly enters the third fourth of the term signal vector. Again we have to skip the fifth and sixth components of the spectral vector because it contains the number of occurrences of first eighth [3], second eighth [1] and third eighth [0], fourth eighth [0], respectively, but we are present in the third-fourth component [2,1] of term signal. Now the seventh component of the spectral vector contains a positive value; therefore, fifth eighth [2] of the signal vector has more occurrences than the sixth eight [1]. Thus, the fifth component is selected as the desired component because the term ‘cosmic’ is well localised in the fifth component of the document. Although the number of occurrences of the term ‘cosmic’ has more in the first eighth component [3] of the term signal, it has given small importance compared to the fifth eighth [2]. This process is repeated for each query term in each top k document. Finally, we find the intersection of terms within the selected components for each query term. In this example, the wavelet component or spectral vector component plays a key role in selecting the desired component of a document. In the proposed method, if expansion terms are greater than some threshold value m, then it is further filtered by applying conditional probability on these terms; otherwise, all terms are appended to the original query. The length of expansion terms varies query by query and is not a fixed value. However, in this experiment, we have fixed the threshold value m to 15. From Table 7, it is clear that for query number Q127 the length of expansion terms is 11; however, for Q140, Q151, Q169 and Q174, it is 15.

6. Experimental result

The experiment is performed on the FIRE 2011 ad hoc English test collection and Robust Track dataset. The size of test collection is 1.1 GB and it contains 392,577 documents. The size of the Robust dataset is 2.1 GB and it contains 528,155 documents. The test collection is indexed using Terrier3.5 search engine [38]. We have used the InL2c1.0 model to index the test collection. The Stopwords are removed and PorterStemmer is used to stem the words. In this experiment, we have evaluated 50 queries, and query expansion is done using the top ‘k’ (k = 30) documents. The sample query of the ad hoc test collection is shown in Figure 3. The mean average precision (MAP) comparison of the proposed method with the other methods is shown in Table 2.

Figure 3.

Example of topic file.

Table 2.

Comparison of mean average precision of proposed method with other methods.

Type of query	MAP
Original query	0.2979
Bo1 model-based query expansion	0.3302
Bo2 model-based query expansion	0.3301
CS model-based query expansion	0.2912
KLD model-based query expansion	0.3317
Word-embedding-based query expansion	0.3176
Haar wavelet-based query expansion	0.3334

MAP: mean average precision; CS: chi-square divergence; KLD: Kullback–Leibler divergence.

The performance of the original query (Title only), BM25 model, query expansion using word-embedding-based semantic model, query expansion using Bo1 model [39], query expansion using Bo2 model, query expansion using chi-square divergence (CS) model, query expansion using Kullback–Leibler divergence (KLD) model and query expansion with Wavelet are shown in Table 3. Comparative improvement of proposed model with other models is shown in Table 4. The performance of proposed model with other models for long query is shown in Table 5. Figure 4 shows the performance of the original query with respect to the Wavelet-based query expansion technique. The Wavelet technique performs well on some of the queries but could not perform well on other queries. Out of 50 queries, the Wavelet technique performs well on 24 queries and 19 queries with respect to the original query and Bo1 model, respectively. For this experiment, the MAP value is 0.3334. An improvement of 0.9691%, 4.97% and 11.91% is observed with respect to the Bo1 model, word-embedding-based query expansion model [40] and original query, respectively. A Z statistics is defined as

Table 3.

Comparison of proposed model with other models.

	Numberofqueries	Retrieved	Relevant	Relevant retrieved	Average precision	R Precision	P@5	P@10	P@20	P@50
Original query	50	50,000	2761	2322	0.2979	0.3188	0.4480	0.40	0.3900	0.3152
BM25 Model	50	50,000	2761	2325	0.2970	0.3230	0.4400	0.4240	0.3860	0.3168
Word-embedding-based model	50	50,000	2761	2406	0.3176	0.3457	0.5160	0.4640	0.4190	0.3424
Bo1 Model	50	50,000	2761	2424	0.3302	0.3500	0.4640	0.4580	0.3880	0.3420
Bo2 Model	50	50,000	2761	2464	0.3301	0.3514	0.4880	0.4500	0.3970	0.3560
Chi-square model	50	50,000	2761	2381	0.2912	0.3083	0.4160	0.3880	0.3650	0.3096
KL Divergencemodel	50	50,000	2761	2427	0.3317	0.3504	0.4560	0.4700	0.3920	0.3452
Haar waveletmodel	50	50,000	2761	2439	0.3334	0.3555	0.5240	0.4820	0.4280	0.3580

KL: Kullback–Leibler.

Table 4.

Comparative improvement of proposed model with other models.

	MAP	R Precision	P@5	P@10	P@20	P@50
Word-embedding-based model	4.97%	2.83%	1.55%	3.87%	2.14%	4.55%
Bo1 Model	0.9691%	1.6%	12.93%	5.24%	10.30%	4.67%
Bo2 Model	0.9996%	1.16%	7.37%	7.11%	7.80%	8.14%
Chi-square model	14.49%	15.30%	25.96%	24.22%	17.26%	15.63%
KL Divergence model	0.5125%	1.45%	14.91%	2.55%	9.18%	3.70%

MAP: mean average precision; KL: Kullback–Leibler.

Bold values indicate the best result.

Table 5.

Comparison of proposed model with other models for long query.

	Numberof queries	Relevant	Relevantretrieved	Averageprecision	R Precision	P@5	P@10	P@20	P@50
Bo1 Model	50	2761	2620	0.4070	0.4165	0.5320	0.5160	0.4880	0.4044
Bo2 Model	50	2761	2614	0.4118	0.4284	0.5280	0.5100	0.4890	0.4132
Chi-square model	50	2761	2402	0.3722	0.3831	0.5160	0.5040	0.4450	0.3652
Word-embedding-based model	50	2761	2578	0.3622	0.3770	0.5840	0.5060	0.4580	0.3876
KL Divergence model	50	2761	2624	0.4088	0.4176	0.5520	0.5220	0.4920	0.4056
Haar wavelet model	50	2761	2566	0.3973	0.4094	0.6240	0.5800	0.5030	0.4004

KL: Kullback–Leibler.

Z = \frac{\bar{X} - μ}{σ / \sqrt{n}}

Figure 4.

Performance of Bo1-based query expansion versus original query.

The provided sample mean is $\bar{X} = 0.3334$ , the known population standard deviation is $σ = 0.234967682$ and the sample size is n = 50. At significance level $α = 0.05$ , the critical value for a two-tailed test is $z_{c} = 1.96$ . The rejection region for this two-tailed test is $R = z : | z | > 0.96012$ . The Z statistics for our sample is 0.237. Since it is observed that $| z | = 0.04668 \leq z_{c} = 0.96012$ , the null hypothesis is not rejected. Hence, there is not enough evidence to claim that the population mean $μ$ is different than 0.3334, at the 0.05 significance level. From the above computation, it is concluded that improvement is not significant. The proposed model has also been evaluated on the Robust Track dataset containing 249 queries. The MAP value of the proposed model on the Robust dataset is 0.2724. The comparison of the proposed model with other models on the Robust Track dataset is shown in Table 6. The proposed model performs better on MAP, R Precision, P@5, P@10, P@20 and P@50 parameters with respect to the original query and chi-square-based query expansion model. The proposed model also performs well on P@5, P@10, P@20 and P@50 parameters with respect to Bo1-based query expansion model and KL divergence-based query expansion model. The proposed model performs well on P@5, P@10 and P@20 parameters with respect to Bo2-based query expansion model.

Table 6.

Comparison of proposed model with other models on Robust Track dataset.

	Numberof queries	Relevant	Relevantretrieved	Average precision	R precision	P@5	P@10	P@20	P@50
Original query	249	17,412	10,234	0.2460	0.2887	0.4707	0.4333	0.3536	0.2518
Bo1 Model	249	17,412	11,017	0.2735	0.3040	0.4956	0.4398	0.3713	0.2677
Bo2 Model	249	17,412	11,108	0.2792	0.3119	0.5028	0.4446	0.3785	0.2708
Chi-square model	249	17,412	10,474	0.2495	0.2749	0.4635	0.4032	0.3428	0.2460
KL Divergence model	249	17,412	10,981	0.2756	0.3057	0.4972	0.4422	0.3743	0.2655
Haar wavelet model	249	17,412	10,304	0.2724	0.2984	0.5229	0.4598	0.3795	0.2697

KL: Kullback–Leibler.

7. Discussion

It is clear from Figures 4 –7 that the proposed model performs well. The MAP has an improvement of 0.9691% in comparison to the Bo1 model, 4.97% improvement in comparison to the word-embedding-based query expansion model and 11.91% improvement in comparison to the original query. Query-by-query analysis reveals that out of 50 queries proposed model performs well on 24 queries and 19 queries in comparison to the original query and Bo1 model, respectively. The proposed model performs well on some queries but not on all queries. It is observed that the Bo1 model also not performs well on all queries with respect to the original query. Bo1 model performs well on 37 queries with respect to the original query. It is observed that proposed method outperforms the Bo1 model with respect to MAP, R Precision, P@5, P@10, P@20 and P@50. The proposed model also retrieves 117, 33 and 15 more relevant documents with respect to the original query, word-embedding-based query expansion model and Bo1 model, respectively. The proposed model performs well on query number Q127, Q131, Q132, Q133, Q135, Q136, Q139, Q140, Q144, Q146, Q151, Q153, Q156, Q157, Q160, Q169, Q171, Q173 and Q174 with respect to Bo1 model because query terms of these queries are close to each other in the initially retrieved top 30 documents. On other queries, the Bo1 model performs well, because the Bo1 model selects expansion terms according to their term distribution in the document. Bo1 model uses Divergence from Randomness (DFR)-based term weighting model to extract the most informative terms. So if terms are properly distributed in the documents, there is a higher probability to select good terms. It is clear that whenever the query terms are close to each other in the document, then the wavelet-based query expansion method retrieves good expansion terms from the components; otherwise, expansion terms may drift the query. Overall performance of the proposed method is better than both original query and Bo1 model query expansion. The performance of the proposed model with respect to other models on the Robust Track dataset is presented in Table 6. The proposed model performs better on all parameters with respect to the original query and chi-square-based query expansion model. The proposed model performs better with respect to other models on P@5, P@10 and P@20 parameters. Sample query from topic file with expansion terms using Haar wavelet is shown in Table 7.

Figure 5.

Performance of wavelet-based query expansion versus original query.

Figure 6.

Performance of query expansion using wavelet versus Bo1 model.

Figure 7.

Performance of QE using wavelet versus QE using Bo1 model versus original query.

Table 7.

Sample query from topic file and expansion terms using Haar wavelet.

Query no.	Query	Expansion terms using Haar wavelet	Length of expansionterms
Q127	Rare cosmic events	sun, mars, three, sky, eclipse, astronomy, seen, time, event, solar, darkness	11
Q140	Search for life and water in space	soil, mission, found, scientists, earth, phoenix, spacecraft, nasa, lander, planet, mars, planets, new, one, ice	15
Q151	An Indian wins the Nobel Prize for Chemistry	swedish, india, us, scientists, thought, prizes, two, research, cambridge, must, sciences, laboratory, world, obama, ramakrishnan	15
Q169	Naxalite attacks	naxalites, government, jharkhand, state, security, orissa, rebels, two, police, attack, killed, district, policemen, personnel, force	15
Q174	International economic slump	market, crisis, global, world, percent, year, financial, growth, recession, us, new, bank, economy, billion, sectors	15

8. Conclusion

In this article, a query expansion method using wavelet transform is proposed. Proximity and term frequency are considered for selecting expansion terms from the initially retrieved top 30 documents. The region where terms are close to each other are considered as expansion regions and terms belonging to this region are used as expansion terms. The proposed method performs better in comparison to the Bo1 model on FIRE 2011 ad hoc English test collection. The experimental result shows that there is an improvement of 0.9691%, 4.97% and 11.91% in comparison to the Bo1 model, word-embedding-based query expansion model and original query, respectively. The proposed model has also been compared with other models on the Robust dataset. The MAP value of the proposed model on the Robust Track dataset is 0.2724. The proposed model has an improvement in MAP, R precision, P@5, P@10, P@20 and P@50 parameters with respect to the original query and chi-square-based query expansion model. The proposed model also has an improvement on P@5, P@10, P@20 and P@50 parameters with respect to the Bo1 model and KL divergence-based query expansion model, respectively. The proposed model also performs better on P@5, P@10 and P@20 parameters with respect to the Bo2-based query expansion model. The proposed method also faces query drifting problem like other query expansion methods. In the future, we will try to further improve the proposed method using machine learning techniques.

Footnotes

Acknowledgements

One of the authors is pursuing doctoral programme from Department of Mathematics and Computer Applications, Maulana Azad National Institute of Technology, Bhopal, India, as full time research scholar. He expresses his sincere gratitude towards the institute for giving opportunity and required facility to pursue his doctoral programme from the institute. The authors have used Terrier search engine for performing their experiments and we are thankful for that. The authors are thankful to FIRE for providing the dataset. The authors are also thankful to TREC NIST for providing the Robust Track dataset for performing the experiment.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

ORCID iD

Abhishek Kumar Shukla

References

Schütze

Manning

Raghavan

. Introduction to information retrieval, vol. 39. Cambridge: Cambridge University Press, 2008.

Zobel

Moffat

. Exploring the similarity space. ACM SIGIR Forum 1998; 32(1): 18–34.

Fuhrmann

Torres

. The genus of curves over finite fields with many rational points. Manuscripta Math 1996; 89(1): 103–106.

Robertson

Walker

. Okapi/keenbow at TREC-8. TREC 1999; 8: 151–162.

Clarke

Cormack

. Shortest-substring retrieval and ranking. ACM T Inform Syst 2000; 18(1): 44–78.

Park

Ramamohanarao

Palaniswami

. A novel document retrieval method using the discrete wavelet transform. ACM T Inform Syst 2005; 23(3): 267–298.

Alnofaie

Dahab

Kamal

. A novel information retrieval approach using query expansion and spectral-based. Inform Retrieval 2016; 7(9): 364–373.

Robertson

Jones

. Relevance weighting of search terms. J Am Soc Inform Sci 1976; 27(3): 129–146.

Salton

Buckley

. Improving retrieval performance by relevance feedback. J Am Soc Inform Sci 1990; 41(4): 288–297.

10.

Rocchio

. Relevance feedback in information retrieval. In: Salton

. (ed.) The smart retrieval system-experiments in automatic document processing. Englewood Cliffs, NJ: Prentice-Hall, 1971, pp. 313–323.

11.

Singhal

Mitra

Buckley

. Learning routing queries in a query zone. In: Proceedings of the 20th annual international ACM SIGIR conference on research and development in information retrieval, Philadelphia, PA, 1 July 1997, pp. 25–32. New York: ACM.

12.

Koenemann

Belkin

. A case for interaction: a study of interactive information retrieval behavior and effectiveness. In: Proceedings of the SIGCHI conference on human factors in computing systems, Vancouver, BC, Canada, 13–18 April 1996, pp. 205–212. New York: ACM.

13.

Riezler

Vasserman

Tsochantaridis

et al. Statistical machine translation for query expansion in answer retrieval. In: Proceedings of the 45th annual meeting of the Association of Computational Linguistics, Prague, June 2007, pp. 464–471. New York: Association for Computational Linguistics.

14.

Qiu

Frei

HP.

Concept based query expansion. In: Proceedings of the 16th annual international ACM SIGIR conference on research and development in information retrieval, Pittsburgh, PA, 1 July 1993, pp. 160–169. New York: ACM.

15.

Schütze

. Automatic word sense discrimination. Comput Linguist 1998; 24(1): 97–123.

16.

Miller

. WordNet: an electronic lexical database. Cambridge, MA: MIT Press, 1998.

17.

Leung

KWT

Lee

DL.

Personalized concept-based clustering of search engine queries. IEEE T Knowl Data En 2008; 20(11): 1505–1518.

18.

Jiang

Liao

et al. Web query recommendation via sequential query prediction. In: 2009 IEEE 25th international conference on data engineering, Shanghai, China, 29 March 2009, pp. 1443–1454. New York: IEEE.

19.

Ganguly

Leveling

Jones

. Query expansion for language modeling using sentence similarities. In: Information retrieval facility conference, Vienna, 6 June 2011, pp. 62–77. Berlin: Springer.

20.

Latiri-Cherif

Chevallet

Elloumi

Galois connection based information retrieval model. In: EUROFUSE workshop on information systems, Varenna, 23–25 September 2002.

21.

Bhogal

MacFarlane

Smith

. A review of ontology based query expansion. Inform Process Manag 2007; 43(4): 866–886.

22.

Deerwester

Dumais

Furnas

et al. Indexing by latent semantic analysis. J Am Soc Inform Sci 1990; 41(6): 391–407.

23.

Hong

A tutorial on probabilistic latent semantic analysis. arXiv preprint arXiv. https://arxiv.org/abs/1212.3900

24.

Blei

Jordan

. Latent Dirichlet allocation. J Mach Learn Res 2003; 3: 993–1022.

25.

ALMasri

Berrut

Chevallet

. A comparison of deep learning based query expansion with pseudo-relevance feedback and mutual information. In: European conference on information retrieval, Padoue, 20 March 2016, pp. 709–715. Cham: Springer.

26.

Croft

. Query expansion using local and global document analysis. ACM SIGIR Forum 2017; 51(2): 168–175.

27.

Zingla

Latiri

Mulhem

et al. Hybrid query expansion model for text and microblog information retrieval. Inform Retrieval J 2018; 21(4): 337–367.

28.

El Mahdaouy

El Alaoui

Gaussier

. Word-embedding-based pseudo-relevance feedback for Arabic information retrieval. J Inform Sci 2019; 45(4): 429–442.

29.

Pierce

. Wavelets: time-frequency methods and phase space. J Acoust Soc Am 1991; 89: 2477.

30.

Miller

Wong

Brewster

et al. TOPIC ISLANDS/sup TM/-a wavelet-based text visualization system. In: Proceedings visualization ’98, Research Triangle Park NC 18–23 October 1998, Cat. No.98CB36276, pp. 189–196. New York: IEEE.

31.

Aerts

Gabora

. A theory of concepts and their combinations II: a Hilbert space representation. Kybernetes 2005; 34(1–2): 192–221.

32.

Bracewell

. The Fourier transform and its applications, vol. 31999. New York: McGraw-Hill, 1986.

33.

Jain

. A sinusoidal family of unitary transforms. IEEE T Pattern Anal 1979; PAMI-1(4): 356–365.

34.

Griffin

Lim

. Signal estimation from modified short-time Fourier transform. IEEE T Acoust Speech 1984; 32(2): 236–243.

35.

Alpert

Beylkin

Coifman

et al. Wavelet-like bases for the fast solution of second-kind integral equations. SIAM J Sci Comput 1993; 14(1): 159–184.

36.

Porwik

Lisowska

. The Haar-wavelet transform in digital image processing: its status and achievements. Mach Graph Vision 2004; 13(1–2): 79–98.

37.

Hamming

Trefethen

. Haar wavelets, 1999, http://dsp-book.narod.ru/PWSA/8276_01.pdf

38.

Macdonald

McCreadie

Santos

et al. From puppy to maturity: experiences in developing terrier. In: SIGIR 2012 workshop on open source information retrieval, Portland, OR, 16 August 2012, pp. 60–63. New York: ACM.

39.

Amati

. Probabilistic models for information retrieval based on divergence from randomness. PhD Thesis, University of Glasgow, Glasgow, 2003.

40.

Shukla

Das

. Deep neural network and pseudo relevance feedback based query expansion. Comput Mater Con 2022; 71(2): 3557–3570.