NO20013308L - Device for searching the Internet - Google Patents

Description

Detailed description

The invention relates to publishing and searching on the World Wide Web, also simply called the web. The web contains a large number of web pages, made available by content providers and stored on web servers linked together on the internet. End users often use search engines to find information. Typical examples of search engines are Fast, AltaVista, Google and Yahoo.

A description of a search engine can be found in "Anatomy of a Large-Scale Hypertextual Web Search Engine" by Sergey Brin and Lawrence Page, 1997.

Today's search engines are typically based on submission or crawling, or a combination of these two principles, to obtain data for a search index. This search index then forms the basis for serving search requests from end users.

For submission-based search engines, URLs are submitted by end users

or content providers or obtained from directory services such as Open Directory. The websites corresponding to these URLs are then downloaded and used as bases for a search index.

Crawl-based search engines are based on a crawler that starts from selected web pages, downloads them, finds web pages referenced from the downloaded pages and downloads them again, and so on. The downloaded pages form the basis for a search index. The start pages can be submitted pages.

When web pages are added, changed or deleted, this should be reflected in the search index. Crawling is typically used to detect additions, changes or deletions. This means that the crawling must be repeated regularly, which leads to a heavy load on transmission lines, on the web servers of content providers and on the computers of the search engine. Because of these costs, the crawling of the supposedly interesting part of the web is often limited to being done at a rate equivalent to an average revisit time of a few weeks to a few months. Therefore, news can be available for a certain time on web servers before they are found by the search engines. New pages to which there are no links may remain undetected.

There are several search engines that try to crawl a significant part of the web.

It is an object of this invention to provide search engines with a new way to update their indexes based on what is available on the internet.

It is a further object of this invention to improve the quality of search engine indexes by reducing the time from when a web page is made available until it is included in the indexes.

It is a further object of this invention to reduce the costs associated with keeping indexes up to date.

It is a further object of this invention to provide content providers with an opportunity to publish news and changes in their web pages to potential information users.

It is a further object of this invention to reduce the amount of data traffic required to keep indexes up to date.

It is a further purpose of this invention to provide portals with improved possibilities for delivering news on their web pages.

It is a further object of this invention to reduce caused by crawling.

It is a further purpose of this invention to provide better control over which web pages are to be included by the search engines.

It is a further object of this invention to improve the categorization of web pages.

It is a further object of this invention to reduce the misuse of categorization.

It is a further object of this invention to enable dynamically generated web pages to be indexed.

It is a further purpose of this invention to provide an overview of which web pages are available on the Internet.

Fig. 1 a illustrates a search engine based on the state of the art.

Fig. 1 b illustrates a search engine based on the present invention.

Fig. 2 shows a detailed example of information that can flow from web servers to a central change server and on to search engines.

Fig. 3 shows some details of the internal structure of an agent.

Fig. 4 a and b illustrate ways to balance the communication load for an exchange.

Fig. 5 shows an example of a configuration file for the agent.

Fig. 6 illustrates a way of connecting search engines and cache servers based on the present invention. Fig. 7 shows a flexible, fault-tolerant, scalable architecture for data flow in a web change server. Fig. 8 a and b illustrate two possible arrangements for building a list of documents that exist on the web.

The basic principle of the invention is that local agents are installed on or near web servers or groups of web servers, and these agents detect and forward changes to a central web change server. Web changes are then sent to search engines, giving search engines a basis for downloading only pages that are new or modified, and giving them an opportunity to remove parts of the index corresponding to deleted web pages.

The basic principle is illustrated both for use within a search engine and for providing an independent change catalog as an independent service that can be offered to several search engines.

Several methods of detecting changes are shown.

The basic principle of search engines according to the prior art is illustrated in fig. 1 a. Web pages 12 14 are stored on a web server 10. A search engine 20 has a crawler 22. The crawler 22 reads through the web pages it finds and produces an index

24. A user on an end-user machine 30 searches the index 24 with a local

browser 32. The desired documents 14 are downloaded from the web server 10.

Fig. 1 b shows a search engine based on the present invention. Web pages 52 are stored on a web server 50. An agent 54 crawls the web pages 52. For each crawl, a log file 56 is generated. This log file 56 is used for change detection. Information about modifications, covering new, changed and deleted pages, is sent from the agent 54 to a loader 62 in a search engine 60. The search engine 60 updates an index 64 based on the results of crawling new and changed pages, and deletes index content based on deleted pages . The index 64 can then be queried and the results presented in a browser 72 on an end user machine 70 in the traditional manner.

The amount of modified web pages on a web server will usually be significantly less than the total amount of web pages on the server. Therefore, much less data will be transferred, and the total load for the search engine will be much less when using the present invention.

In addition, the agent can transmit the modification list to the search engine quickly after the modifications have been made, instead of having to wait for the search engine to find the modifications while crawling at some point.

There are several ways to start execution of the agent. One way is to implement a service or daemon that executes regularly according to a time interval and an initial start time, or some other scheme. Another way is to let administrators start the agent manually. Yet another method is to implement the agent so that it can be started from a script, possibly synchronized with other processes that are executed on the web servers.

The web change server may be a component of a search engine.

Alternatively, the web change server can be used as a stand alone service that serves several search engines. The latter option has the advantage of allowing data to be published on multiple search engines by simply installing and maintaining an agent.

Fig. 2 shows an example of information that can be transferred. Two agents, each installed on a web server, send two modification lists 10 20 containing URLs referring to modified web pages to a central server, where the lists 10 20 are combined into one aggregated modification list 30. Various extracts 40 50 can then be made from this aggregated list 30 and can be sent to various search engines.

In the figure, new web pages are marked with '+', changed web pages are marked with '!' and deleted web pages are marked with

The aggregated list can be created by concatenating incoming modification lists in order of arrival.

Fig. 3 shows a preferred embodiment method for detecting modifications. An agent 10 is installed on a web server 5. A crawler 15 crawls the web pages 25 on the web server 5. A log 35 is created based on the crawling. After the crawl is complete, a change detector 40 compares the log 35 from the most recent crawl with the log 45 from the previous crawl. The difference between these logs is summarized in a modification list and transferred.

A preferred implementation method for the log is to create it as a table with a row for each web page, a column with the URL for each web page, and a column with the checksum for each web page. The change detector 40 can then compare the most recent log 35 with the previous log 45 and report changes as follows: A URL present only in the most recent log is reported as a new page, a URL present only in the previous log is reported as a deleted page, and a URL that is present in both lists but with different checksums is reported as a changed page. URLs present in both logs 35 45 are not reported.

In one preferred embodiment, the checksum is generated based on Exclusive OR (XOR) of groups of characters on the web page. If, for example, 32 bit checksums are desired, the web page can be divided into groups of 4 and 4 bytes, and the checksum is generated by XORing the groups.

Other methods for generating checksums can be used. The method should preferably generate a relatively short checksum, for example from 16 to 128 bits, and at the same time there should be a relatively low probability of two web pages with different content being assigned the same checksum.

In many cases, the same content can be represented by different URLs. These web pages are called duplicates. One such case is when aliases are used.

When aliases are used, the content provider often has a preference as to which URL to report for the duplicates.

This can be solved by using checksums. The crawl log can be sorted or accessed in checksum order. In cases where two or more pages have the same checksum, one of the URLs can be dropped.

In general, any method of generating checksums, where the checksum is shorter than the non-redundant part of the original data, can accidentally produce the same checksum as for two different web pages. In the event of a checksum collision, the pages themselves must therefore be compared to ensure that duplicates are correctly detected.

Selection of which web page to report in case of duplicates can be done with a set rule. For example, the shortest URL can be used, and in case two or more URLs have the same length, the first one in alphabetical order can be used.

Some web pages have predominantly static content but also have a smaller part that changes automatically, for example a clock or a hit counter. Such pages should not be reported as always changed, because this would cause a search engine to download and reindex all such pages each time "changes" are reported, resulting in unnecessary load on servers and networks.

This problem can be solved in several different ways. One way is to exclude certain elements of the pages from the checksum calculation. For example, all strings of the form "99:99:99" or "99/99-9999" can be replaced with blank characters before or during checksum generation. It should be possible to control this using a configuration tool, including controlling exactly which strings are to be extracted. An administrator can be presented with examples of strings to extract. Alternatively, the administrator may be given the option to specify such strings, e.g. by using regular expressions as used in the grep command in UNIX.

A special case of web pages that are generated dynamically are error message pages that correspond to missing pages, also called dead links. The HTTP protocol allows reporting missing pages with a 404 error message, with no content beyond this. A crawler can detect this and stop further processing. However, some web servers are programmed to respond with an error message containing an element such as "Sorry, the page AAAA.htm was not found". In such a case, every URL pointing to the web server but not to a valid web page on that server will result in a unique web page, which in unfortunate cases can lead to an infinite number of web pages that can choke the agent and/or search engines. Such cases can be solved by removing self-references from the web pages before or during checksum generation. For example for the URL

http://linkloader.com/nonexisting.page.htm which could result in an error message page containing the string "Sorry, the page http://linkloader.com/nonexistingpage.htm does not exist", the agent can modify the string to "Sorry , the page does not exist", which will be caught through duplicate detection.

On some sites where web pages are dynamically generated or change detection is difficult for other reasons, it may be more efficient to report only new and deleted pages. This should be configurable.

On some websites, some pages may be dynamically generated. For such cases, it should be possible to implement the agent so that for some pages both new, changed and deleted pages are reported, while for other pages only new and deleted pages are reported. One possibility is to differentiate based on file types, for example so that URLs with the extension ".html" are checked for all types of modifications, while URLs with the extension ".asp" are only checked for new or deleted URLs. Another solution for separation is to base this on folders.

In some cases, some publishing tool is used to create websites. In these cases, it may be more efficient to base the list of modifications directly on results from the publishing tool instead of crawling, or possibly to combine these two methods. This can be taken into the system by defining an interface file, so that at a defined time for crawling or transfer, all URLs in the interface file are picked up by the agent and reported to the central office. This can be a list of existing URLs so that the agent can perform change detection and transfer afterwards. Alternatively, it can be a list of modifications, ready for direct transfer.

The URLs reported by the agent should be the same as the URLs as seen by a search engine and an end user. This is an important reason for using the HTTP protocol for crawling, rather than the FILE protocol. Therefore, the HTTP protocol is a natural choice in most cases. However, advantages of the FILE protocol may be important in some cases, such as faster execution or web server independence. When the FILE protocol is used, the agent should have a mechanism to convert FILE-based URLs to HTTP-based URLs that can be used from the outside.

The agent must transfer the list of modifications back to the central office. Possible protocols that can be used include FTP (File Transfer Protocol), mail (e.g. SMTP) and HTTP (Hypertext Transfer Protocol). In a preferred embodiment, the agent initiates communication by either starting an FTP session, sending an email or by sending an HTTP request. This results in efficient use of available communication channels, in that communication is only initiated when the agent has something to transfer.

Alternatively, the exchange can initiate the communication. An advantage of this is that the central site can achieve a better distribution of the load over time.

The agent should be authenticated both in case FTP, email and HTTP are used. The authentication can be divided into two phases: authentication of the administrator and associated agent during registration, and later authentication of submissions assumed to come from the given agent.

The authentication during registration can be done manually. Alternatively, automatic support for this process can be added. Correspondence between the crawl area and the name and e-mail address of the administrator can be ensured by making a lookup in a Whois database. The validity of the e-mail address can be ensured by sending an e-mail to the registered e-mail address and demanding a reply.

Later authentication of transfers can be done using Public Key Encryption, using key pairs generated during registration.

In addition to search engines, others can also use data from a web change server. One example is caching services.

One way to build a caching service on the Internet is to have a mechanism that copies web pages from content providers, stores these pages in one or more intermediate locations, and delivers them on demand.

Such a caching service needs a mechanism to ensure cache coherence, i.e. to ensure that the copy delivered to users is functionally identical to the original web page located on the web server. A traditional way to solve this is based on HTTP headers: Every time a web page is requested, the caching server will retrieve the corresponding header from the original website. If the header is identical to the header stored on the caching server, the rest of the web page will be displayed from the caching server. This method relies on correctly generated HTTP headers, which cannot always be guaranteed. Furthermore, the method also depends on communication with the content provider for each individual web page to be delivered, which in turn leads to unwanted network traffic. By using the methods shown in the present patent application, both problems can be reduced. The modification list can be used to indicate which web pages can be served from the caching server, and which must be re-fetched from the original web server.

A caching service may be able to report the number of hits for each web page. This can be reported back to the web change server and distributed further to search engines and other interested parties. Hit reports can be valuable to search engines in selecting web pages for downloading and indexing, and also for ranking results to present to end users.

This is illustrated in fig. 6. An agent 10 on a web server 15 reports modifications to a web change server 20. The web change server 20 then sends the URLs to a caching server 25 and a search engine 30. Both will download the modified web pages from the web server 15, allowing them to deliver web pages and search results respectively. The caching server 25 will maintain page view statistics, which are reported back to the web change server 20 and further to the search engine 30. Thus, the search engine 30 can deliver a better search result ranking.

Commercially, several different business models are possible.

Content providers may be asked to pay for a more efficient way to

publish their content than would otherwise be possible. Payment can be calculated, for example, based on the number of URLs transferred, or on the total size of the monitored website.

Infrastructure players such as communication, hosting or caching companies may be asked to pay for a reduced load on their infrastructure or to offer new functionality to their customers. Payment can be based on estimated or measured reduced load on infrastructure, or by sharing profits such providers can receive from their customers for the new functionality.

Search engines may be asked to pay for improving the quality of their indexes or for reducing their communication costs. Payment may be based on the number of URLs received used.

Some search engines are specialized with respect to category. For such search engines, it is relevant to subscribe to data only within selected categories.

A category may be assigned to the site upon registration. A user can select category from a list or from a tree structure. OpenDirectory is one example of a category tree that can be used.

In addition to categorization at website level, there may be a need for categorization at URL level, where each URL is assigned one or more categories. A data format that works well for URL-level categorization is to add a category column to the modifier list. This column can then be filled with category codes according to a given list or tree structure.

The category column can be based on configuration data provided by the administrator of a web server. For example, all content within a given folder can be assigned to a given category.

Categorization can also be based on data or metadata. The agent can search for given keywords in the header or body part of web pages.

Just as some search engines specialize in certain categories or otherwise use category information to serve search queries, search engines can do the same with language. This can be handled in a similar way to categories. A language can be registered at the website level. Alternatively, a language code can be entered into the modification list. This language code can be configured, data-based, meta-data-based, or otherwise provided by an administrator.

For maximum speed, the agent can be allowed to run without limitations regarding processor load or network traffic.

In cases where the agent competes with other processes, it may be beneficial to limit the use of resources. For example if the agent is run on the same computer as a web server application, the web server's performance may be reduced while the agent is running. In such cases, the agent should be restricted with regard to resource use. One way to do this is to limit the number of HTTP requests to a given number of pages or kilobytes per second or minute. Another way is to set a limit on percentage CPU usage. Another way is to set a limit on how much RAM the application can use. Yet another way is to limit the amount of disk space used. It should be possible to set such restrictions during configuration.

Fig. 7 shows a scalable and fault-tolerant architecture for a back-end system that handles modification lists.

The FTP servers 00 05 accept incoming FTP sessions from agents transferring modification lists. The modification lists are stored on disk 10 15. As long as there is at least one FTP server running, the agents will be able to transfer their modification lists. Each FTP server is largely independent of the rest of the architecture, which makes the FTP servers very robust against errors in the rest of the system.

The aggregation servers 20 25 read modification lists and store them in aggregate modification lists 30 35. The aggregation servers can also authenticate the modification lists against websites registered in a database 70.

Each aggregation server 20 25 can read modification lists from disks 10 15 on several different FTP servers 00 05. Therefore, the overall system will still function even if one or more aggregation servers are down or out of order, as long as at least one aggregation server is still functioning.

Extraction servers 40 45 extract data from the aggregated modification lists, based on extraction profiles stored in the database 70, and in this case also store the result on disk 50 55.

The distribution servers 60 65 distribute extracted data to the respective subscribers. The distribution servers 60 65 can be FTP servers, email clients, HTTP servers or other means for communicating with subscribers.

The disks at each stage act as buffers. If a stage should stop or start working very slowly, the disks will buffer the results from the previous stage until the stage is operational again.

If a large number of agents are installed on different web servers, this can result in large network traffic when many of the agents transfer modification lists at the same time. Fig. 4 a shows a solution for scaling and load distribution. Different crawlers 10 20 each have a list 15 25 of priority addresses of FTP servers 40 50. When a crawler 10 tries to contact an FTP server, it selects a priority address. If contact cannot be achieved, the next address on the list may be tried.

Alternatively, scaling and load distribution can be done using Network Address Translation, abbreviated to NAT. Using this technique, incoming FTP sessions can be distributed to a group of FTP servers based on round robin or load-based methods

In addition to modification lists that describe changes to web pages, search engines may also wish to have a list of available web pages on the internet at a given time. An example is when a new search engine is established. Such a search engine may then need a list of all available web pages to start its index, in order to have a basis for later modifications. A list of web pages available on the internet will hereafter be called a base list. Fig. 8 a shows a way of integrating a base database 15 in the pipeline described in Fig. 7. An FTP server 10 connected to a network 05 receives modification lists. The modification lists are aggregated by an aggregation server 15 which puts URLs into an aggregate modification list 20 and also consolidates into a base list 25. An extraction server 30 and a playout server 35 then forward the data by distributing to subscribers over a network 40.

A method of consolidation can be summarized with the following pseudocode:

For each URL received from the Aggregating server 15:

If the operation is '+', i.e. a new web page:

If the URL already exists in the Basis list:

Give a warning

else

Insert the URL into the Basis list

If the operation is delayed. a deleted webpage:

If the URL exists in the Basis list:

Delete the URL

else

Give a warning

If the operation is '!', i.e. a changed web page:

If the URL exists in the Basis list:

Update the URL

else:

Insert the URL

Give a warning

The method of maintaining a base list as shown in Fig. 8 a is well suited for real-time processing of small or medium-sized amounts of data.

However, the need for Insert, Update and Delete operations means that the method becomes dependent on a database system, for example an SQL-based database.

A file-based version for batch-based execution is illustrated in Fig. 8 b. An FTP server 55 receives modification lists over a network 50. An aggregation server 60 collects data and stores in an aggregated modification list 65. Batches of the modification lists are collected and sorted by a consolidation module 70. The batches are sorted, and the sorted batches and an earlier version of a base list 80 are read in parallel. The result is consolidated in a merge process, and the data is written to a new version 85 of the base database. The extraction 85 and playout 90 servers can then pass the data on for final distribution over a network 95.

Many websites offer a search mechanism to search within the website. This is sometimes achieved by installing and operating a complete search engine running on the website.

By using the present invention, such functionality as mentioned above can be outsourced to an existing search engine.

Fig. 9 illustrates a search mechanism, where indexing, searching and ranking are outsourced. A web server 10 has a number of web pages 15, among these a search page 20. An agent 25 reports modifications to a web change server 30. The results are reported to a search engine 35, which has a module 40 for downloading and indexing, thereby producing an index 45. The search engine has a query engine 50. When an end user uses the search page 20 to perform a search, the query is sent to the query engine 50 of the search engine 35, results are generated based on the index 45, and these are then returned for display on the search page 20.

As described above, the agent can transfer modifications to the exchange. Alternatively, the agent can transmit a complete list of URLs found on the site to the switchboard and allow the modifications to be calculated on the switchboard. This solution results in an agent with less complexity since operations are performed on the web change server rather than by the agent. However, this also results in greater network traffic, since complete URL lists must be transferred instead of just modifications.

Claims (25)

1. An apparatus for searching among web pages on the Internet, the apparatus called a search engine, where each web page is identified by a .Unified Resource Locator, abbreviated URL, and where the web pages are stored on a number of web servers, the apparatus consisting of device for reading web pages, device to create an index based on the web pages, device for removing a part of the index corresponding to removed web pages, and device for receiving search requests and returning results based on the contents of the index, where said devices are located in a central location, characterized by the apparatus further consists of a device called an agent, located on each web server or on a local network together with each web server, where the agent sends a list containing URLs for new web pages and a list containing URLs for deleted web pages, the two pages together called a modification list, to the central site, and the web page reader device chooses which pages to read based on the modification list. 2. An apparatus according to claim 1, where the agent also sends a list containing URLs for modified web pages as part of the modification list. 3. An apparatus according to claim 3, wherein the agent contains a device called a crawler to crawl web pages on each web server, so that a list of web pages is generated for each crawl, and the list of modifications for the time interval between two crawls is formed based on the difference between the lists of web pages corresponding to the two crawls. 4. An apparatus according to claim 3, where the crawler uses the Hyper Text Transfer Protocol, abbreviated HTTP. 5. An apparatus according to claim 3, where the crawler uses the File protocol, and the URLs found thereby are modified so that they appear as valid HTTP-based URLs when used from a browser. 6. An apparatus according to one of claims 3 to 5, which the device further consists of a device to calculate a checksum for each web page found during crawling, where a change in a web page is detected by a change in the corresponding checksum. 7. An apparatus according to claim 6, where the unit to calculate a checksum can overlook parts of the website corresponding to given regular expressions. 8. A device according to claim 6 or 7, where the device for calculating a checksum can ignore references to the current web page. 9. An apparatus according to one of claims 1 to 8, where web pages with identical content but with different URLs, where the URLs are called aliases, are detected and one of these URLs is selected to be reported by the agent to the central location. 10. An apparatus according to claim 9, where a set of rules defines which of the aliases is selected. 11. An apparatus according to one of claims 1 to 10, where the agent further comprises an interface for accepting an externally produced list of modifications. 12. An apparatus according to one of claims 1 to 11, where the File Transfer Protocol, FTP for short, is used to transfer the modification list to the central location. 13. An apparatus according to one of claims 1 to 11, where electronic mail is used to transmit the modification list to the central location. 14. An apparatus according to one of claims 1 to 11, where the Hypertext Transfer Protocol, abbreviated HTTP, is used to send the modification list to the central location. 15. An apparatus according to one of claims 1 to 14, which the device further consists of a device to start the agent or transfer at given times or linked to given events. 16. An apparatus according to one of claims 1 to 15, the apparatus further consisting of device for registering users and corresponding passwords and crawl areas, and device for authenticating data according to passwords, where a crawl area delimits a part of the web by defining a top level domain, a level-2 domain and possibly one or more restrictions within the domain, and the device to authenticate data checks that received URLs are within the corresponding crawl area. 17. An apparatus according to one of claims 1 to 16, where the agent further consists of device to associate each URL with one or more categories, based on data or metadata in the web pages, or configurable rules, or lookups in a registry of web pages, and the association between web pages and categories is transferred to the central location. 18. An apparatus according to one of claims 1 to 17, the apparatus further consisting of a device, located on each web server or on equipment connected to each web server over a local area network, to receive search requests, forward the search requests to the central location, receive results from the central location, and present the results on each web server. 19. An apparatus for producing an overview of changes to web pages on the Internet, the apparatus called a web change server, where each web page is identified with a URL and where the web pages are stored on several web servers, the apparatus consisting of a device for compiling a list of URLs for new, modified, and deleted web pages, the list called total modification list, and a device for transmitting or presenting the total modification list or an excerpt thereof to one set of subscribers; characterized by that the agent is run on each web server or on a device connected to each web server over a local area network, the device for compiling the total modification list is located in a central location, and the device for assembling the total modification list receives modification lists from each agent. 20. An apparatus according to claim 19, modified according to one of claims 2 to 18. 21. An apparatus according to one of claims 19 to 20, where an extract specification is associated with each subscriber, and the extract specification consists of rules that define which URLs from the total modification list should be sent to the subscriber. 22. An apparatus for caching web pages, such that the apparatus creates copies of mage original web pages, where the collection of copies is called a cache, characterized in that the cache is kept coherent with the original web pages using an apparatus according to one of claims 19 until the 21st. 23. A search engine according to one of claims 1 to 18, with the search engine connected to a device for caching web pages, wherein the web page caching apparatus produces web page cache hit statistics, the statistics are transferred to the search engine, pg the search engine uses statistics on cache hits when ranking results. 24. A web change server according to one of claims 19 to 21, with the web change server connected to an apparatus for caching web pages, the apparatus for caching web pages producing statistics of cache hits for web pages, the statistics are transferred to the search engine, and the statistics are presented together with the total modification list or its extract. 25. An apparatus for producing a list of web pages on several web servers connected to the internet, the list called web status, the apparatus called web status server, characterized in that modifications from a web change server according to one of claims 19 to 21 are consolidated into a web statute.