Using Ant Colony Optimization for Results Merging in Federated Search

doi:10.21203/rs.3.rs-3115769/v1

Download PDF

Article

Using Ant Colony Optimization for Results Merging in Federated Search

https://doi.org/10.21203/rs.3.rs-3115769/v1

This work is licensed under a CC BY 4.0 License

Version 1

posted

You are reading this latest preprint version

Federated search routes the user's search query to multiple component collections and presents a merged results list in ranked order by comparing the relevance score of each returned result. However, the heterogeneity of the component collections makes it challenging for the central broker to compare these relevance scores while fusing the results in ranked order. To address this issue, most existing approaches merged the returned results by changing the document ranks to their ranking scores or downloading the documents and computing their relevance score at query time. However, these approaches are less efficient as the former suffer from limited efficiency of results merging due to negligible overlapping documents among the component collections, and the latter is resource intensive. This research addresses this problem by proposing a new method that extracts features of both the documents and component collections from the available information provided by the collections at querying time. Next, each document and its collection features are exploited together to establish the document relevance score. The ant colony optimization is then used for information foraging to create a merged results list. The empirical results on a real-world dataset demonstrate significant improvements by the proposed approach over baseline approaches.

Physical sciences/Mathematics and computing

Physical sciences/Mathematics and computing/Computational science

Physical sciences/Mathematics and computing/Computer science

Information retrieval

federated search

relevance ranking

results merging

ant colony optimization

Users rely on traditional search engines like Google, Bing, and Yahoo to find information due to the massive size of the Web. However, some information sources are not fully accessible through these traditional search engines for commercial or security reasons [1]. As such, users relying on search engines miss valuable collections of information sources that may be relevant but not fully accessible where they posed their query. Federated search, or distributed information retrieval (DIR) [2], connects users directly to those information sources through a unified search interface. This interface can perform multiple searches across distributed collections and combine their results into a single list [3]. However, with multiple collections involved, users cannot know beforehand which collections will most likely be relevant to their query. This is where the central broker acts as an intermediary between the component collections and users [2]. This way, as illustrated in Fig.1, a user uses the user interface to submit search query, which is transmitted directly to the broker. The broker picks a few collections that may hold relevant documents and routes the query toward them. Each collection processes the received query, returns a ranked results list, which the broker merges into a single ranked list before presenting to the user.

The literature divides the domain of federated search into three separate research areas: resource description, collection selection, and results merging [2]. The resource description [4], also called collection representation [2], is to obtain information concerning each collection's content and size. The collection selection [5, 6] uses the sampled information to select a few collections that may contain relevant documents against a searc query. Finally, the results merging [7, 8] combines the results from the component collections into an ordered list.

This paper studies results merging as it plays a key role in meeting users' information needs. This is because user satisfaction is compromised if the most relevant collections are selected, and their results lists are merged poorly, where the most relevant documents may not make it to the top of the merged result list. In addition, merging multiple results lists is a challenging task, especially in non-cooperative environments [2] due to the differences in the collections corpus statistics, the use of varying indexing schemes, retrieval models, and the non-availability of the documents' full-text at the merging time. Moreover, some collections may have non-text content, such as images, videos, etc.

Learning to rank (L2R) techniques have been considered an alternative to traditional document-ranking approaches in recent years. Several research works [7, 9-13] have used L2R for various retrieval tasks. In these techniques, a set of queries, each associated with the ranked list of documents and their relevance judgments, is exploited as training data [14]. This training data is used to extract query-document relevance features and then to learn a ranking function that predicts the documents' relevance for each given query. For example, in federated search, Ghansah et al. [13] considered the results merging problem a classification problem. They extracted some features from the returned documents by the collections and learned a ranking function that merged the multiple results list. This method's drawback is the need for a huge amount of training data in learning the ranking function.

Swarm intelligence and genetic programming are widely used in various domains to solve optimization problems. In applying these techniques, multiple rounds of iterative processes of selections, variations, and mutation are performed on the extracted features to obtain the optimum solution. These techniques have been reported [15] to provide better solutions than the algorithms defined by experts. A recent study [7] used genetic programming to solve the result merging problem in which returned documents by the collections are downloaded, some likely relevance features are extracted from the documents at each iterative process, and then the documents are re-ranked based on their relevance scores. However, the drawbacks of this approach are increases in bandwidth usage, computational resources, and latency time.

The proposed work addresses this issue by extracting similar features, like in [13] but with a few modifications: First, the mentioned studies consider only the document's features in obtaining their relevance score, whereas we consider the quality of the collection as an important factor in addition to these features. Second, we depart from learning a ranking function because it requires colossal training data. Instead, we use the ant colony optimization (ACO), a swarm intelligence algorithm, in generating the merged results list. The novelty of the proposed method lies in the use of the only available information in a way that neither overwhelms the broker nor increases its computational resources or response time. To summarize, we make the following contributions to the body of knowledge.

We propose a method that uses only the information provided by the component collections at query time.
The proposed method uses the ACO algorithm and considers collection quality and document features to compute the results merging scores of documents.
We test the efficacy of the proposed approach by conducting experiments with the TREC 2013 FedWeb dataset. The experimental results demonstrate its robustness. It outperforms both the learning and non-learning models used as the baselines.

The remaining paper has five sections. Section 2 presents the related works. Section 3 presents research methdology. Section 4 presents experimental and evaluation setup. Section 5 presents and discusses the experimental results. Section 6 presents conclusions, followed by references.

Results merging combines results from multiple collections into a unified list before serving to the search user. Many factors make results merging challenging; the prominent among them is the incomplete information about collections' corpus statistics and the use of different retrieval models in retrieving the documents [2]. The simple scenario to assume is that the component collections return their documents' relevance score or run the same retrieval model. Even with this assumption, the document's returned relevance score cannot be compared directly due to the differences in their documents index and processing method [8]. For these reasons, few models have been proposed for the results merging problem.

The early models proposed in the literature assumed the component collections share their documents' index information with the broker [16] or they should return their results with their index terms statistics [17]. Neither of these assumptions is achievable in a realistic web environment because most component collections are uncooperative and treat the broker as an ordinary search user. As such, the only response to the broker request for each query received is by returning a ranked results list without sharing information about the documents index [18].

Due to the uncooperative nature of the component collections, several studies [8, 19, 20] used query-based sampling to sample representative documents from each component collection. They built a centralized sample index (CSI) at the broker site. When the broker receives a user query, it forwards it to the most relevant collections and runs it on the CSI. The final merging score of the documents is estimated by mapping the documents' ranks returned in the collections result lists to their corresponding relevance scores obtained from the CSI. The drawback of these models is that their effectiveness hinges on the high number of overlap documents between the collections result lists and the CSI list [2].

Various approaches [4, 21] were proposed in the TREC FedWeb search track for the results merging task. Buccio et al. [22] applied a round-robin approach in merging results, where the first document of each highly relevant selected collection is picked and kept in a ranked order. The models proposed in [23, 24] estimated the document merging scores by converting their ranks into a ranking score. Specifically, Mourão et al. [23] converted the ranks of the documents into a ranking score by modifying the reciprocal rank fusion [25]. They estimated the merging score for each document by taking the log of the reciprocal of the document rank and multiplying it with the relevance score of the collection that returned it [20]. Similarly, the ICTNET [26] computes each document merging score by computing the BM25 score of the document parts (i.e., title, URL, heading, etc.) and combines them using a linear weighting method.

The L2R approaches have shown competitiveness in generating effective document ranking compared to non-learning methods. Recently, some research works [12, 13, 27, 28] have used L2R for results merging. Ghansah et al. [13] used the information in the collections' results list to extract some likely relevant features, which include the occurrences of query terms in the titles, the order of occurrences of the terms, and the presence or absence of URLs for a document. These features were fed to the boosting algorithm [29] to learn the ranking function. Ponnuswami et al. [23] used a gradient boost algorithm to learn the composition of the final merged results list when different verticals returned the results list. However, the downside of machine learning algorithms is the need for huge training data and their computational expense.

The meta-heuristic approach has recently gained much attention due to its efficacy in solving hard combinatorial optimization problems [30]. Most meta-heuristic algorithms study the behavior of social insects and design algorithms that mimic their behavior to solve real-world problems. A recent study [31] focused on the ACO algorithm to see how the ants use the foraging behavior to communicate and perform complex tasks. Interestingly, ants can identify the shortest path from their next to the food sources with the foraging behavior by depositing the pheromone chemical on the ground. One of the characteristics of pheromone is that it evaporates with time. Because of this evaporating nature, the pheromone deposit of the path followed by most ants is continuously updated, and their trail is sustained as the shortest path. On the other hand, the pheromone deposit of the path followed by a few ants is quickly evaporated, their trail is lost, and the ants abandon the path.

In solving optimization problems, artificial ants are created to mimic natural ones with additional capabilities. The number of ants created equals the number of data points for solving the problem. Each ant is placed on a data point with some pheromone value. The selection bias is avoided by initializing the same pheromone value to all the data points. The ants select the next data point based on its importance in solving the problem. The pheromone value is updated after the first iteration (i.e., the ants transverse the data points). The update is performed by increasing the pheromone values of the data points the ants selected while the pheromone value of the data points the ants did not select remains unchanged. This pheromone update is performed multiple times until the algorithm converges. The data points with the highest frequency after the convergence are considered the optimal solution to the problem.

In the literature on federated search, Vo [4] employed a genetic algorithm to fuse multiple results lists into a single list. This approach extracts the BM25 and language modeling scores of features like titles and URLs from the downloaded collection to rank the merged results. A better alternative is using document features only, as the authors did in [4]. However, how the component collections are created from the dataset used for their experiment is not explicitly explained. The problem with this and the abovementioned studies is that they consider document features but cannot consider collection-level features. Therefore, one possible solution could be to not only consider the document and collection features in estimating the document merging scores but to use the foraging behavior of ants to make it possible to iterate at query execution time quickly. In addition, the method should be designed to require no training data and rely only on the click-through data or relevance judgments of the documents. The following section explains how this approach can be materialized.

This section presents the proposed approach and its methodology by discussing the experimental setup, dataset, evaluation metrics, and baselines. We start with some preliminaries that will help understand this section. The proposed approach and the experimental and evaluation methodology follow this.

3.1 Preliminaries

To explain our proposed method, we must create a CSI, an accumulation of sample documents from all the collections involved. The sample documents are obtained using the most widely used query-based sampling (QBS) method [4]. In QBS, a random query is issued to all component collections and the top five documents are downloaded to CSI. Querying and downloading documents to CSI continues until 300 documents are sampled from each collection. In this paper, the CSI is used only for collection selection purposes.

For the experiment purpose, suppose broker receives a search query q, and it selects ${C}_{i}$ collections for $1<i\le m$ as probably highly relevant to q in the collection selection phase. The broker routes q to those collections, and each one processes the query and responds by returning a ranked results list ${C}_{i}=\{{c}_{i1},{c}_{i2},\dots ,{c}_{in}\}$ to the broker. Our goal in this paper is to fuse these results lists into a single ranked list $C=\{{c}_{1}, {c}_{2}, \dots , {c}_{n}\}$ similar to what is obtained, the query is issued to a centralized search system.

3.2 The Proposed Approach

Unlike most existing approaches, the proposed method uses only the available information that the collection returned to the broker at query time in merging the result lists. The detailed description of the processes involved in the proposed method is as follows:

Step 1

Assume that for a query issued to the broker, the broker runs the query on the CSI and selects the most relevant collection to search.

Step 2

The query is routed to the collections selected in Step 1. Each collection processes the query and returns a ranked results list. This results list is expected to contain snippets of documents similar to those obtained in real-world search systems.

Step 3

For each snippet returned in Step 2, its query-dependent features are extracted, as shown in Table 1.

Step 4

For each collection that returns a results list, its quality concerning query is represented by the features shown in Table 2.

Step 5

Initialize the number of ants equal to the number of features in Tables 1 and 2. The pheromone value is also initialized to a unit value and assigned to all features. Each ant receives a random feature for the first iteration to begin its search. From the second iteration to convergence, the ants select a feature by looking at its importance in determining the document's relevance, which is obtained using the probability, given in Eq. 1.

$${f}_{i}= {\alpha }_{k}{{\Delta }\alpha }_{k}$$

where ${\alpha }_{k}$ is the pheromone value, which is initiated at a unit value, ${{\Delta }\alpha }_{k}$ is the proportion of the ants that select that particular feature. Eq. 2 updates the pheromone value when an ant selects a feature.

$${\alpha }_{k+1}=({\alpha }_{k}+ {exp}^{r})$$

where ${{\alpha }}_{\text{k}+1}$ is the next iteration pheromone value, and r is the relevance label of the document ${d}_{i}$ provided in the relevance judgment file.

Step 6

At each iteration of features selection, each document’s relevance score is obtained by aggregating its features and that of the collection that returned it, as shown in Eq. (3)

$${\text{S}(\text{d}}_{i})= \sum _{i=1}^{m}{f}_{i}*\sum _{j=1}^{n}\left({f}_{j}\right)$$

where ${\text{f}}_{i}$ and ${\text{f}}_{j}$ represent the document and collection quality features, respectively. The feature selection, pheromone update, and relevance score estimation continue until its convergence.

Table 1

The list of extracted features of the document
ID	Feature (${{f}}_{{i}})$	Description
1.	Document rank	Convert each document's rank in a collection result list into a ranking score: $\mathcal{R}\left(s\right)=exp-\left(\frac{r}{n}\right)$ where, r is the document ranking position in a particular collection's returned results list, and n represents documents in the results list.
2.	Query terms in the URL	Count the occurrences of query terms of each document URL: ${\sum }_{i=1}^{\left\|q\right\|}C({q}_{i}, U)$
3.	Query terms in the title	Counts the number of query terms in the title: ${\sum }_{i=1}^{\left\|q\right\|}C({q}_{i}, T)$
4.	Query terms in the description	Counts the number of query terms in the description: ${\sum }_{i=1}^{\left\|q\right\|}C({q}_{i}, D)$
5.	BM25 of the title	Relevance score of the title using BM25 as a retrieval model
6.	BM25 of the description	Relevance score of the description using BM25 as a retrieval model
7.	LM of the title	Relevance score of the title using language model (LM) as a retrieval model with Dirichlet prior
8.	LM of the description	Relevance score of the description using language model (LM) as a retrieval model with Dirichlet prior
9.	Average query terms in the description	The average number of query terms in the description: $avg\left(q, D\right)=\frac{{\sum }_{i=1}^{\left\|q\right\|}C({q}_{i}, D)}{\left\|D\right\|}$ where $\left\|D\right\|$ is the length of the description.

Table 2

The list of extracted features of the collection quality
ID	Feature (${{f}}_{{j}})$	Description
1	Relevance score	The relevance score of the collection, obtained in the collection selection phase.
2	No. of query terms	Count the number of query terms in the results list of the collection $TF\left(t, {C}_{i}\right)= \sum _{{t}_{q}\in {C}_{i}}TF({t}_{q},{C}_{i})$
3	No. of documents	The number of documents a collection returned in its result list.
4	Average query terms	The average number of query terms in a collection

Algorithm 1: Result Merging using ACO
Input:	Initial pheromone value ${{\alpha }}_{\text{k}}$, number of ants, number of features, and number of iterations.
Output:	A merged results list of documents$\text{C}=\{{\text{c}}_{1}, {\text{c}}_{2}, \dots , {\text{c}}_{\text{n}}\}$
Steps:
	1. Repeat
		a. Create the number of ants equal to the number of features extracted in Tables 1 and 2.
		b. Initialize the pheromone values ${\alpha }_{k}$ to 1
		c. Allow ants to select the features based on their pheromone value using Eq. (1).
		d. Perform pheromone update using Eq. (2).
		e. For each iteration, rank the documents based on their score computed using Eq. (3).
		f. Check if the number of iterations is not reached, then repeat steps 3 to 5
	2. Return the final merged results list

3.3 Experiments and Evaluation

We used the sampled search engine snippets provided in the TREC 2013 FedWeb dataset¹ as the collections. This is the first standard dataset created to promote federated search research simultaneously to discourage the artificial creation of collections using TREC web track datasets [32]. The dataset has 24 vertical categories (i.e., academics, blogs, entertainment, jobs, kids, etc.) holding results from 157 search engines. This dataset is more suitable for our work because each search engine uses its proprietary retrieval method to retrieve its result, and each result is separated in the dataset [33]. We use 50 queries released with the dataset to represent the user information needs. The queries are judged using the five levels of graded relevance judgment, that is, not relevant (NRel), relevant (Rel), highs relevant (HRel), top relevant (Key), and navigational (Nav) by the team of experts.

Regarding the collection selection, it was observed that routing a query to all the relevant and non-relevant collections would waste resources. Therefore, using a modified version of the collection selection algorithm proposed in [34], only the top five most relevant collections were used for each query. In the model, a collection is considered relevant based on the number of relevant documents in the top N-ranked list and the documents ranking positions.

The collection selection experiments were performed using Apache Solr version 8.2 with Python 3.6 on an Intel core i7-based system running Linux and 8GB memory. The default vector space model of the Apache Solr was used for indexing and retrieval of the results snippets. The title and description of each indexed snippet was queried and their scores were summed up to be its relevance score. The required parameters for the ACO algorithm were set as the number of ants = 40, the number of iterations = 20, ${{\alpha }}_{\text{k}}=1.0$, ${\beta }=0.45$, and ${\gamma }$ is 0.55.

Regarding the evaluation of the proposed approach, the selected baselines can be categorized into learning [4][10] and non-learning [20][23] methods. The standard evaluation metric for federated search is nDCG@k [35]. The nDCG metric measures the goodness of the retrieved result list compared to the best/ideal ordering of the result list. We report the results at the top $k$ cutoff ranks, where the value of $k$ is 1, 3, 5, and 10, respectively.

Table 3 reports on the experimental results. For each cutoff rank, the best-performing method is boldfaced. We represent our approach as ACO-RM. From the result, we can observe that our approach has the highest performance compared to the baselines across all the cutoff ranks. The highest performance of over 94.75% on nDCG@1 was achieved compared to the baselines, and the lowest was 61.97% on nDCG@10. We can further observe from the results that except for TF-RF, which achieved its highest performance on nDCG@3, all the other methods achieved their highest performance on nDCG@1. Among the baseline methods, nsRRF has shown a strong performance than all the baselines, followed by TF-RF, which has the second-best performance. The poor performance of the BTM method can be attributed to insufficient training data. That is, for fairness, we only use the result of the top five selected collections for the model's training and testing. This result has once again proved that without enough training data, the non-learning methods, in some cases, can outperform machine learning models. The following two subsections further elaborate on these findings.

Table 3

Performance comparison of the proposed methods against the baselines
Works	nDCG@1	nDCG@3	nDCG@5	nDCG@10
nsRRF	0.5075	0.4515	0.4294	0.4253
ICTNET	0.3790	0.3579	0.3401	0.3397
BTM	0.3499	0.3556	0.3499	0.3452
TF-RF	0.3353	0.3892	0.3852	0.3559
ACO-RM	0.9475	0.8037	0.7411	0.6197

4.1.1 Ranking Construction at Each Iteration

Figures 2 and 3 are the sample of the first iteration generated ranking and the relevance label of the top 5 documents extracted from the TREC relevance judgment file, respectively. Looking at the top 5 documents highlighted in red in Fig. 2 and their corresponding relevance label in Fig. 3, we can observe that only the top document is marginally relevant while all the remaining are non-relevant. At this stage, the ants explore features by selecting them based on the initialized pheromone value. However, as the iteration progresses, the pheromone update increases the merging score of highly relevant documents while decreasing the ones of non-relevant documents. This can be observed in the fifth iteration generated ranking shown in Fig. 4. Comparing the first and fifth iterations generated ranking as shown in Figs. 2 and 4, we can see that the top rank document of Fig. 2 is now on ranking position 3 in Fig. 4 and the document on position 3 is now on ranking position 5, while, the remaining three documents have lost their ranking spot. Finally, Figs. 5 and 6 show the top 5 documents of our model after its convergences and their corresponding extracted relevance label. The extracted relevance label shown in Fig. 6 shows that our model could rank most of the highly relevant documents at top-ranking positions, as shown in Fig. 5.

4.1.1 The Contribution of Collection Quality to Relevance

We attributed the superior performance achieved by our approach to including collection quality features in computing the merging score of the documents. However, to provide more insight into how much collection quality features contribute to identifying the most relevant documents, a further experiment was performed by removing the collection quality features in calculating the merging score and comparing the results with ACO-RM. Table 4 shows the experimental results in which we denoted the result of merging scores without collection quality features as ACO-RMN.

Table 4

Contribution of Collection Quality in Identifying Relevant Documents
Works	nDCG@1	nDCG@3	nDCG@5	nDCG@10
ACO-RM	0.9475	0.8037	0.7411	0.6197
ACO-RMN	0.7755	0.7354	0.6835	0.5969

From the results, we can see that by removing the collection quality features in calculating the merging score, the efficacy of the merged results list has decreased by 18.2% on nDCG@1 and 3.67% on nDCG@10. These findings enable us to conclude that considering the features of collection in calculating the merging scores of documents increase the effectiveness of the merged results list in a federated search environment.

In this article, we presented a results merging method for federated search that employed the foraging behavior of ACO in merging the multiple result lists. Unlike existing methods, the proposed method uses document and component collection features to compute the results merging score. The features are first extracted and then summed as the relevance score of the documents. Then a pheromone value is assigned to each relevance score and iterate by updating the pheromone value at each iteration of the result until it converges. We experimented with the TREC 2013 FedWeb dataset and found the effectiveness of the proposed method, which significantly outperformed both the learning and non-learning methods used as the baselines.

Even though the proposed approach shows remarkable performance compared to the baselines, its limitation lies in not fully automating the learning process, as the model parameters are selected based on trial and error instead of learning them. A possible direction for future work should be to use a learning method in selecting the parameters.

Authors Contributions:

AG conceived and designed the study, collected and analyzed the data, performed the experiment and wrote the first draft of the manuscript. SK contributed to the design of the study, assisted with the approach, and critically reviewed and revised the structure and content of the manuscript. HS provided expert input into the design of the approach, contributed to the literature search, and critically proofread the manuscript. All authors have read and approved the final manuscript. IU proofread the paper and provided technical expertise, and critically reviewed the manuscript. NMT and DM provided expert input into the design and experimentation of the approach, and critically proofread the article. All authors have read and approved the final manuscript.

Acknowledgment Statement:

The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through Large Groups RGP.2/412/44.

Conflict of Interest:

The authors of this manuscript have no potential conflicts of interest to disclose

Consent to Publish:

The manuscript was read and approved for submission by all authors

Availability of Data and Materials:

The datasets generated and/or analysed during the current study are available in the FedWeb Greatest Hits repository, https://fedwebgh.intec.ugent.be/. An application form on the FedWeb Greatest Hits site should be filled and submitted to [email protected].

Garba, A. and S. Wu, Snippet-based result merging in federated search. Journal of Information Science, 2023: p. 01655515221144864.
Shokouhi, M. and L. Si, Federated Search. Foundations and Trends® in Information Retrieval, 2011. 5(1): p. 1-102.
Stamatis, V., M. Salampasis, and K. Diamantaras, Machine learning methods for results merging in patent retrieval. Data Technologies and Applications, 2023.
Callan, J. and M. Connell, Query-based sampling of text databases. ACM Transactions on Information Systems (TOIS), 2001. 19(2): p. 97-130.
Garba, A., et al., Embedding based learning for collection selection in federated search. Data Technologies and Applications, 2020.
Li, L., Z. Zhang, and S. Wu. LDA-Based Resource Selection for Results Diversification in Federated Search. in International Conference on Web Information Systems and Applications. 2018. Springer.
Vo, H.T., New re-ranking approach in merging search results. Informatica, 2019. 43(2).
Hong, D. and L. Si. Mixture model with multiple centralized retrieval algorithms for result merging in federated search. in Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval. 2012.
Wu, T., X. Liu, and S. Dong. LTRRS: A Learning to Rank Based Algorithm for Resource Selection in Distributed Information Retrieval. in China Conference on Information Retrieval. 2019. Springer.
Ibrahim, M. and M. Carman, Comparing pointwise and listwise objective functions for random-forest-based learning-to-rank. ACM Transactions on Information Systems (TOIS), 2016. 34(4): p. 1-38.
Mohapatra, P., et al. Efficient optimization for rank-based loss functions. in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2018.
Tjin-Kam-Jet, K. and D. Hiemstra, Learning to merge search results for efficient distributed information retrieval. 2010.
Ghansah, B., S. Wu, and N. Ghansah. Rankboost-Based Result Merging. in 2015 IEEE International Conference on Computer and Information Technology; Ubiquitous Computing and Communications; Dependable, Autonomic and Secure Computing; Pervasive Intelligence and Computing. 2015. IEEE.
Li, H., A short introduction to learning to rank. IEICE TRANSACTIONS on Information and Systems, 2011. 94(10): p. 1854-1862.
Angeline, P.J., Genetic programming: On the programming of computers by means of natural selection: John R. Koza, A Bradford Book, MIT Press, Cambridge MA, 1992, ISBN 0-262-11170-5, xiv+ 819pp., US $55.00. 1994, Elsevier.
Rasolofo, Y., D. Hawking, and J. Savoy, Result merging strategies for a current news metasearcher. Information Processing & Management, 2003. 39(4): p. 581-609.
Kirsch, S.T., Document retrieval over networks wherein ranking and relevance scores are computed at the client for multiple database documents. 1997, Google Patents.
Ogilvie, P. and J. Callan. The effectiveness of query expansion for distributed information retrieval. in Proceedings of the tenth international conference on Information and knowledge management. 2001.
Shokouhi, M. and J. Zobel, Robust result merging using sample-based score estimates. ACM Transactions on Information Systems (TOIS), 2009. 27(3): p. 1-29.
He, C., D. Hong, and L. Si. A weighted curve fitting method for result merging in federated search. in Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. 2011.
Demeester, T., et al., Overview of the TREC 2014 federated Web search track. 2014, GHENT UNIV (BELGIUM).
Di Buccio, E. and M. Melucci, University of Padua at TREC 2014: Federated Web Search Track. 2014, PADUA UNIV (ITALY).
Mourao, A., F. Martins, and J. Magalhaes. NovaSearch at TREC 2013 Federated Web Search Track: Experiments with rank fusion. in TREC. 2013.
Pal, D. and M. Mitra. ISI at the TREC 2013 Federated task. in TREC. 2013.
Cormack, G.V., C.L. Clarke, and S. Buettcher. Reciprocal rank fusion outperforms condorcet and individual rank learning methods. in Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. 2009.
Guan, F., et al. ICTNET at Federated Web Search Track 2013. in TREC. 2014.
Ponnuswami, A.K., et al. On composition of a federated web search result page: using online users to provide pairwise preference for heterogeneous verticals. in Proceedings of the fourth ACM international conference on Web search and data mining. 2011.
Takanobu, R., et al. Aggregating e-commerce search results from heterogeneous sources via hierarchical reinforcement learning. in The World Wide Web Conference. 2019.
Freund, Y., et al., An efficient boosting algorithm for combining preferences. Journal of machine learning research, 2003. 4(Nov): p. 933-969.
Shunmugapriya, P. and S. Kanmani, A hybrid algorithm using ant and bee colony optimization for feature selection and classification (AC-ABC Hybrid). Swarm and Evolutionary Computation, 2017. 36: p. 27-36.
Dorigo, M. and G. Di Caro. Ant colony optimization: a new meta-heuristic. in Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406). 1999. IEEE.
Demeester, T., et al. Overview of the TREC 2013 federated web search track. in Text Retrieval Conference (TREC-2013). 2013.
Lee, C.-J., et al. An optimization framework for merging multiple result lists. in Proceedings of the 24th ACM international on conference on information and knowledge management. 2015.
Shokouhi, M. Central-rank-based collection selection in uncooperative distributed information retrieval. in European Conference on Information Retrieval. 2007. Springer.
Clarke, C.L., et al. Novelty and diversity in information retrieval evaluation. in Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval. 2008.

https//fedwebgh.intec.ugent.be

No competing interests reported.

Download PDF

Version 1

posted

You are reading this latest preprint version

Using Ant Colony Optimization for Results Merging in Federated Search

Status:

Version 1

Abstract

Figures

1. Introduction

2. Background and Related Work

3. Materials and Methods

3.1 Preliminaries

3.2 The Proposed Approach

3.3 Experiments and Evaluation

4. Results and Discussion

4.1.1 Ranking Construction at Each Iteration

4.1.1 The Contribution of Collection Quality to Relevance

5. Conclusions and Future Work

Declarations

References

Footnotes

Additional Declarations

Status:

Version 1

Algorithm 1: Result Merging using ACO
Input:	Initial pheromone value \({{\alpha }}_{\text{k}}\), number of ants, number of features, and number of iterations.
Output:	A merged results list of documents\(\text{C}=\{{\text{c}}_{1}, {\text{c}}_{2}, \dots , {\text{c}}_{\text{n}}\}\)
Steps:
	1. Repeat
		a. Create the number of ants equal to the number of features extracted in Tables 1 and 2.
		b. Initialize the pheromone values \({\alpha }_{k}\) to 1
		c. Allow ants to select the features based on their pheromone value using Eq. (1).
		d. Perform pheromone update using Eq. (2).
		e. For each iteration, rank the documents based on their score computed using Eq. (3).
		f. Check if the number of iterations is not reached, then repeat steps 3 to 5
	2. Return the final merged results list