FICA: A Novel Crawling algorithm based on reinforcement learning

Ali Mohammad Zareh Bidoki, Nasser Yazdani, Pedram Ghodsnia

Abstract – Web is a huge and highly dynamic environment which is growing exponentially in the content and structure. Also no search engine can cover whole of the web, thus it has to focus on the most valuable pages for crawling. So an efficient crawling algorithm for retrieving the most important pages has remained still as a challenging issue. Several algorithms like PageRank and OPIC have been proposed. Unfortunately, they have high time complexity. In this paper, an intelligent crawling algorithm based on reinforcement learning, called FICA is proposed that models a real surfing user. The priority for crawling pages is based on a concept which we name it as logarithmic distance. FICA is easy to implement and its time complexity is O(E*logV) where V and E are the number of nodes and edges in the web graph respectively. Comparison of the FICA with other proposed algorithms shows that FICA outperforms them in discovering highly important pages. Furthermore, FICA computes the importance (ranking) of each page during the crawling process. Thus, we can also use FICA as a ranking method for computation of page importance. An adaptive version of FICA is also proposed that adjusts dynamically with changes in the web graph. We have used UK’s web graph for our experiments.

International Journal of Web Intelligence and Agent Systems, Vol 7, No. 4, pp. 363-373, September 2009.

COCA Filters: Co-Occurrence Aware Bloom Filters

Kamran Tirdad, Pedram Ghodsnia, J. Ian Munro, and Alejandro Lopez-Ortiz

Abstract – We propose an indexing data structure based on a novel variation of Bloom Filters. Signature Files have been proposed in the past as a method to index large text databases though they suver from a high false positive error problem. In this paper we introduce COCA Filters, a new type of Bloom Filters which exploits the co-occurrence probability of words in documents to reduce the false positive error. We show experimentally that by using this technique we can reduce the false positive error by up to 21 times for the same index size. Furthermore Bloom Filters can be replaced by COCA Filters wherever the co-occurrence of any two members of the universe is identifiable.

In Proceedings of the SPIRE'11, October 17-21, 2011, Pisa, Italy.
(This paper won the best student paper award)

Dynamic Data Allocation with Replication in Distributed Systems

Shahin Kamali, Pedram Ghodsnia, Khuzaima Daudjee

Abstract Fragment allocation is an important problem in modern distributed database systems. The goal of fragment allocation is to allocate data fragments to a network of sites so as to minimize the overall data transmission cost incurred to satisfy queries. We consider the problem of fragment allocation and address both placement and replication issues in an integrated approach. While replication can improve system performance via increased locality, excessive replication can incur extra transmission cost to maintain consistency. A comprehensive model that takes into account network topology, fragment correlation and data access patterns is presented. Based on this model, two algorithms are proposed to find near-optimal dynamic allocation solutions. Experimental results show the efficacy of the proposed solutions.

In Proceedings of the IPCCC'11 , November 17-19, 2011, Orlando, USA.

Statistical Evaluation of effect of Some Persian Language Characteristics in Recall Factor of Search Engine Results

Pedram Ghodsnia, Ali Mohammad Zareh Bidoki, Naser Yazdani

Abstract – With growth of Farsi web content in recent years, Farsi language has been turned into the primar language of Iranians in communication, learning and interchange of ideas and thoughts in Internet. In spite of recent studies about challenges and restrictions of Farsi language in quality of search results in search engines, there is no exact statistical analysis about the role of each problem in decreasing the quality of search results. In this paper, using a real collection of Farsi web pages, we present some experimental results about the role of some of the most important problems and restrictions of Farsi language in decreasing the recall factor of search results in search engines.

In Proceedings of the 13th National CSI Computer Conference, March 9-11, 2008, Kish Island, Persian Gulf, Iran.

FICA: A Fast Intelligent Crawling Algorithm

Ali Mohammad Zareh Bidoki, Nasser Yazdani, Pedram Ghodsnia

Abstract – Due to the proliferation and highly dynamic nature of the web, an efficient crawling and ranking algorithm for retrieving the most important pages has remained as a challenging issue. Several algorithms like PageRank and OPIC have been proposed. Unfortunately, they have high time complexity. In this paper, an intelligent crawling algorithm based on reinforcement learning, called FICA is proposed that models a real surfing user. The priority for crawling pages is based on a concept which we name as logarithmic distance. FICA is easy to implement and its time complexity is O(E*logV) where V and E are the number of nodes and edges in the web graph respectively. Comparison of the FICA with other proposed algorithms shows that FICA outperforms them in discovering highly important pages. Furthermore, FICA computes the importance (ranking) of each page during the crawling process. Thus, we can also use FICA as a ranking method for computation of page importance. We have used UK’s web graph for our experiments.

In Proceedings of the IEEE/WIC/ACM International Conference on Web Intelligence, November 2-5, 2007, Silicon Valley, USA.

A Punishment/Reward Based Approach to Ranking

Pedram Ghodsnia, Ali Mohammad Zareh Bidoki, Nasser Yazdani

Abstract – One of the important challenges in current search engines is dealing with the "rich get richer" problem. In popularity-based ranking algorithms like PageRank, due to considering the structure of the web as the measure for ranking the pages, newly-created but highly-qualified pages are effectively disregarded shoot out, and can take a very long time before becoming popular. In this paper we present a new punishment/reward based approach that adds a new dimension to the PageRank model for reducing the effect of the rich get richer problem using implicit feedback of visitors. In this approach, in addition to considering the structure of links as a page-creator's point of view, we use the page-visitor's view as an important parameter to improve the accuracy of the PageRank algorithm.

In Proceedings of the ACM Second International Conference on Scalable Information Systems(INFOSCALE 2007), June 6-8, 2007, Suzhou, China.

Novel Way of Determining the Optimal Location of a Fragment in a DDBS: BGBR

Ashkan Bayati, Pedram Ghodsnia, Masood Rahgozar, Reza Baseda

Abstract – This paper addresses the problem of determining the optimal location to place a fragment (object) in a distributed non-replicated database. The algorithm defined takes into consideration a changing environment with changing access patterns. This paper contributes by allocating data fragments to their optimal location, in a distributed network, based on the access patterns for that fragment. The mechanism for achieving this optimality relies on knowing the costs involved in moving data fragments from one site to the other. Embedded into the algorithm is a mechanism to prioritize fragments so that if there is a limited space on a specific node where many fragments are chosen to be allocated the ones with higher priority are placed before the lower priority fragments.

In Proceedings of the IEEE ICSNC06, Tahiti, French Polynesia, 2006.