Optimizing the link importance detection method in the link database and its application in the architecture of search engines

Computer-Software Engineering Master Thesis (M.Sc)

Abstract

In the information age, the web has become one of the most powerful and fastest means of communication and interaction between people. Search engines as web applications automatically navigate the web and receive a set of available documents. The process of receiving, storing, classifying and indexing is done automatically based on semi-intelligent algorithms. Although many facts about the structure of these applications remain hidden as trade secrets, the research literature in the field of search engines and information retrieval tools is trying to find the best solutions for the optimal performance of each module in the structure of search engines. Due to the limited time of today's web users, providing them with the most relevant and up-to-date documents is often the most important challenge for search engines. To do this, every module in the search engine architecture should be intelligently designed to not only provide relevant documents but also respond as quickly as possible. Among these modules, there is a sensitive and vital part called crawler. One of the debatable issues in search engine performance optimization is to reconfigure the crawling policy in such a way that relevant external links that link to content related to the source pages are followed. The crawler module is responsible for fetching pages for the ranking module. If higher quality pages with less subject deviation are indexed by the crawler, the ranking will be done faster.

Considering the structure of the web as a graph, the way to navigate the web is in the form of graph search methods. In this research, by experimentally applying different graph search methods and their various combinations, and by issuing queries to Google search engine to measure the quality of received pages and by keeping the navigation depth factor constant, the best method with reasonable temporal and spatial complexity will be identified to be used in the crawler section of the search engine architecture.

Key words: web crawler, graph navigation, search engines, topic deviation.

Introduction

Without search engines, the World Wide Web is almost useless. But the question is how search engines find the information we need among all these websites. The internet is very vast and the web users are estimated to be around two billion. Among them, there are at least 250 million Internet websites, which contain a total of about 30 billion web pages. Searching the web[1] when it was very small and there were very few websites was usually reserved for researchers and university professors and it can be said that it was considered a difficult task [9]. Meanwhile, it was in the early nineties that the first search engines called Archi[2] appeared. In the first step, a search engine must collect and classify information before displaying results to the user. Therefore, search engines should crawl as many websites as possible and store and classify page addresses with a summary of the page's contents. This task is very heavy and is performed by web crawlers[3][53].

These programs automatically search the web and save the contents of web pages for later analysis. Since the number of pages and their volume is very high, this work is done on a very large scale and requires high bandwidth and time. Popular search engines have created a huge repository of web pages, but newer crawlers have to start from scratch. To begin with, crawlers usually go to famous directories, because through them they can access a large list of related sites, and by browsing these websites, the web crawler dives deeper into the internal space of the websites and obtains more information. All this information is stored in the repository to be analyzed later[44].

A well-designed crawler can browse the content of web pages at high speed, while all crawlers search the web with the help of a coordinating program.

A well-designed crawler can crawl the content of web pages at a high speed, while all crawlers search the web with the help of a coordinating program so that this process does not repeat itself. This coordinator causes the freshness factor of the pages to be maintained so that their latest version is included in the search engine database[46].

After the crawlers collect the information on the web pages, this information must be stored on the searcher's site servers. Storing and indexing the countless pages on the web is a big challenge, but even more important is that the search engine knows what its users are looking for. The more information displayed by a search engine matches the phrase searched by the user, the better the performance and popularity of the search engine.

But what makes a website rank higher in the search results of a search engine is actually the type of search engine algorithm found in the page ranking. This algorithm is a complex set of various rules and considerations, which, of course, is constantly being optimized to show better results to users. The better the algorithm of a search engine works, the better results the website will provide to users, and therefore the success of a search engine is guaranteed by its architecture and the type of search algorithm. Search engines all evaluate entire pages based on the words they contain. The importance of a website has an important effect on its ranking, and if many sites link to a certain page, the search engine will realize that that page is important and pay more attention to that page. The more links from other sites to a site, the more important and authoritative that website is.

Now if a website that has a high ranking links to another website, that link will be more valuable than multiple links[35].

1-2 Statement of the problem

A web crawler is a program that downloads web pages, generally for a web search engine. Crawlers of major search engines such as Google, Altavista and . A significant portion of text web pages are used to build content indexes. Other crawlers may also view many pages and only use certain types of information, such as email addresses. At the other end of the spectrum, there are personalized crawlers that crawl a particular user's favorite pages to build a quick-access cache. Designing a good crawler presents many challenges due to the vastness of the web and must be constantly updated. According to various studies there are more than one million pages available on the web and this growth rate is expected to continue. Besides, newly created pages are constantly being updated [5]. The difficulty of implementing an efficient web crawler clearly states that the bandwidth for crawling is neither infinite nor free. Therefore, it is necessary to crawl the web not only at a scale, but also in an efficient way so that an acceptable level of quality or freshness of the web pages is maintained, so the administrator of a web crawler must define its behavior. Therefore, the crawler must determine what algorithm it uses to download pages with higher quality and how the pages are selected to update and avoid creating overhead in websites.

According to the current size of the web, it is necessary for the crawler to perform crawling on a fraction of the web that has higher content quality. Even today's major search engines crawl only a fraction of the pages on the web, but the crawler must crawl a fraction of the pages that are relevant to the topic, not just random pages, i.e. pages must be selected based on their importance. The importance of a web page depends on the number of links or their visits [23]. In order to be able to visit pages according to their importance, the web crawler must be able to use a good and strong strategy to detect the quality of the pages. In this research, to choose a suitable strategy, all strategies of graph navigation and crawling were tested. This research, while examining the various methods available in recognizing the importance of links, has provided a solution and an algorithm in order to optimize the methods of recognizing the importance of links.