KR100511164B1 - Method for caching index data for and operations based on real-time analysis of user's queries in a web search engine - Google Patents

Abstract

The caching method of index data for AND query processing in the web search engine according to the present invention includes not only the memory area to be cached but also the I / O buffering area of an operating system (OS) kernel. Also, in order to more accurately determine the data to be cached among the index data stored in the disk, the importance of the search target words included in the input AND query is analyzed in real time to determine the index data to be cached. In addition, the index data caching method according to the present invention, in order to maximize the memory space available to the OS kernel and the application program, so that data not to be cached is not stored in the buffering space of the OS kernel. According to the present invention, by frequently indexing the index data corresponding to the words most likely to be used in the future based on the frequency of use of the words included in the AND query of the user using the web search engine, frequent disks of the web search engine Performance degradation due to input / output operations (I / O) can be prevented. In addition, according to the present invention, by using not only the internal memory area of the AOP but also the I / O buffering area of the OS as a cache memory area, caching of index data can be efficiently performed.

Description

METHOD FOR CACHING INDEX DATA FOR AND OPERATIONS BASED ON REAL-TIME ANALYSIS OF USER'S QUERIES IN A WEB SEARCH ENGINE}

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a web search service on the Internet. In particular, in implementing a web search engine for a web search service, an AND query process that can improve performance degradation due to a bottleneck caused when reading data from a disk is provided. It relates to a method of caching index data.

Web search engines collect and store huge amounts of web pages accessible on the Internet, such as, for example, EMPAS, NAVER, and GOOGLE, and store these web pages Indexing is based on key words, and is used for services that search and display web pages that are highly related to the query of users who use the web search engine. Means application.

The user of the web search service enters a query consisting of several words (eg, "patent office location") into this web search engine. As such, a user query that includes two or more words is called an "AND query", and processing such AND queries in a web search engine is called "AND query processing." When the user enters an AND query, the web search engine searches for a web document containing both words (eg, "Patent Office" and "Location") to generate a web search result. That is, for an entered query, the web search engine searches for web pages (or web documents) that have two or more words included in the query as indexed words, and ranks the retrieved web documents. The web documents sorted in order of high importance are output as the web search results. In the present invention, an application program that processes a user query consisting of two or more words in this manner is referred to as an "AND-Operation Processor (AOP)".

1 is a flowchart illustrating the operation of a web search engine according to the prior art. First, a user enters an AND query including _n words (w ₁ , w ₂ , ..., w _n ) in an input window of a web search engine (step 101). Here, n is a positive integer, and these n words are assumed to have a logical AND relationship with each other. The AOP receiving the AND query of the user reads index data corresponding to _n words (w ₁ , w ₂ ,..., W _n ) from the storage medium (eg, a hard disk) (step 102). The AOP retrieves a web document containing all _n words (w ₁ , w ₂ ,..., W _n ) based on the index data read (step 103). The AOP then executes a predetermined ranking algorithm for the retrieved web documents, assigning each web document a rank according to its importance (step 104). As such, when the importance of each of the retrieved web documents is determined, the AOP sorts the web documents according to the ranking determined according to the importance, and transmits the IDs of the sorted web documents to the web screen generator (step 105).

The web screen generator uses information about the web document corresponding to each of the IDs of the web documents received from the AOP, and summarizes the contents of the web document and the URL (universal resource locator) indicating the location of the web document on the Internet. Generate information (step 106). The generated URL and the summary information are then displayed on the user's computer screen (step 107).

In general, AOP processes user queries that are input several tens per second, and AOP reads the index data generated for each word from disk to process an AND query that includes various words. You have to search the web documents. In this case, the index data that AOP needs to read from disk typically has a size of more than a few hundred gigabytes, so AOP requires a lot of disk input / output operation (I / O) time to process the AND query. Therefore, an I / O bottleneck is likely to occur during the AND query processing of the AOP. Therefore, in order for AOP to efficiently process AND queries, AOP needs a method of efficiently reading such large sized index data from the hard disk into memory. It is very important to minimize the size and the number of times of data access.

In order to reduce the number of I / Os from the disk to the memory of the index data, it is preferable to read in advance into the memory area of the server where the AOP is executed a high probability that the index data stored in the disk will be used repeatedly in the future. Conventionally, the least recently used (LRU) method is used as a caching method of index data. When the new index data is read from the disk into the memory, the LRU method is used to store the most recently used index data in the memory area. Use the way to store the new index data. The LRU scheme is generally based on the temporal locality that data that has not been used for the longest time is most likely not to be used in the future.

However, in an Internet environment, a large number of users use a web search engine at the same time, and generally, in such an environment, the number of words that can be included in a user query to be processed by the web search engine is usually 10 million or more. In addition, the user query includes a wide variety of words, which makes it very difficult to determine the most usable index data in the future. In addition, since the distribution of words included in a query that a user enters frequently changes over time, the data to be cached corresponding to that word must also change accordingly, but the prior art caching technique is based on the distribution of these searched words. There is a problem that does not reflect frequent changes.

Meanwhile, the conventional caching technique uses the internal memory space used by AOP to cache index data. However, if the size of the index data that AOP needs to retrieve exceeds its internal memory space, you must run separate disk I / O to retrieve the portion of the index data that is not stored in the internal memory space. The problem of deterioration arises. Therefore, a technique for more efficiently utilizing the memory space of the server on which AOP is executed is needed.

The present invention is to solve the problems of the prior art as described above, to provide an index data caching method and structure of the index data that can minimize the number and time of disk I / O required for AND query processing in the web search engine do. In addition, the present invention provides a method of caching index data and a structure of index data that can more efficiently utilize a memory space of a server running a web search engine.

In order to achieve the above object, the present invention provides a method of caching index data for an AND query based on real-time user query analysis in a web search engine, wherein (a) a word included in the AND query is a first word list and Determining whether the second word list is included in the second word list, wherein the first word list is generated based on a frequency of use of words included in an AND query input to the search engine by a user for a predetermined period of time; Is a subset of the first word list, (b) if the word included in the AND query in step (a) is included in the first word list and the second word list, an index corresponding to the word Reading data from a first caching memory area into a memory area of the web search engine, (c) in step (a) the word is included in the first word list Is, but provides a method comprising a step to read the memory area of the web search engine to the indexed data is not included in the second word list, corresponding to the word in the second memory area caching.

In the present invention, the LRU (Least Recently Used) method, which is a caching algorithm mainly used in the prior art, is not used. In addition, the memory area to be cached is extended to the I / O buffering area of an operating system (OS) kernel without being limited to the memory space of an application program as in the prior art. Also, in order to more accurately determine the data to be cached among the index data stored in the disk, the importance of the words included in the input query is analyzed in real time to determine the index data to be cached.

In addition, in the index data caching method according to the present invention, in order to maximize the memory space available to the OS kernel and the application program, the index data not to be cached is read directly from the disk so as not to pass through the OS kernel buffering space. . In this manner, the caching method of the index data according to the present invention can prevent the data cached in the memory from being swapped out from the memory to the disk by the paging operation of the OS. That is, the size of the entire index data to be cached can be kept smaller than the available memory size in the server, thereby preventing data once cached from memory from being deleted from the memory without requiring an AOP.

Hereinafter, the structure of the index data and the caching method of the index data according to the present invention will be described in detail with reference to the accompanying drawings.

Structure of Index Data Used in the Invention

Index data used by the AOP according to the present invention is divided into MCF (Main Catalog File) and RIF (Rank Information File). 2 illustrates a structure of index data according to the present invention, that is, a structure of MCF and RIF. For convenience of description, FIG. 2 illustrates only index data for two words w ₁ and w ₂ , but the structure of the index data according to the present invention may include a data structure for two or more words. As shown in FIG. 2, the MCF 210 includes IDs (Document IDs) (DIDs) 211 and 213 of web documents including the corresponding words for each word (w ₁ or w ₂ ) and the importance of the web documents ( The positions 212 and 214 of the importance information used for the rank calculation are included. In addition, the RIF 220 includes various pieces of information 221 and 222 necessary for calculating the importance of the web document associated with each word w ₁ or w ₂ . The information 221 and 222 necessary for calculating the importance of such a web document may be accessed using the positions 212 and 214 of the importance information included in the MCF 210.

Using the structure of the index data according to the present invention described above, the AND operation on two words (w ₁ , w ₂ ) is performed in the following manner. First, read the the information by using the position information 215 of the index data of the word (w ₁₎ for the word (w ₁₎ in the MCF (210) (211, 212 ) into memory, then the word (w ₂ The information 213 and 214 corresponding to the word w ₂ is read from the MCF 210 into the memory by using the position information 216 of the index data of FIG. In order to find a web document containing two words (w ₁ , w ₂ ) at the same time, the DIDs commonly included in the information (211, 213) including the DIDs corresponding to the two words (w ₁ , w ₂ ) Find. After determining the DIDs corresponding to the web documents including the two words (w ₁ , w ₂ ), two words from the RIF 220 using the positions 212 and 214 of the importance information associated with the determined DIDs. The importance information 221, 222 for (w ₁ , w ₂ ) is read into the memory. Then, the importance of each web document including two words w1 and w2 is calculated from the importance information 221, 222. The method of determining the importance of the web document is not included in the scope of the present invention and thus will not be described in more detail here.

The hatched portions of the RIF 220 shown in FIG. 2 represent RIF data to be read for importance calculation when performing AND query processing of the words w ₁ and w ₂ . As shown in FIG. 2, the RIF data that should be read into memory to calculate the importance of web documents associated with the words w ₁ , w ₂ are distributed scattered on the RIF 220 and distributed on the RIF 220. The position of the RIF data also varies very fluidly with the combination of words w ₁ , w ₂ . In addition, since the size of the RIF is very large compared to the size of the MCF, even if the RIF data used once is cached in the memory, the probability of the data being used again is very low. Because of this nature of RIF data, the caching method according to the present invention preferably does not cache RIF data, but instead RIF data is read from disk into the memory area of the AOP and deleted from memory immediately after it is used in calculating the importance of web documents. do.

Logical Organization of Memory Used to Cache Index Data

Let M _server be the total amount of memory installed in the server running AOP. In addition, when the size of the memory used by the OS and other programs running on the server (that is, other applications except AOP) is M _other , the actual memory size that can be used by the caching method of index data according to the present invention is M _available = M _server -M _other Therefore, the size of data to be cached should be kept smaller than M _available .

Cache memory having a size of M _available or smaller is divided into two memory areas. That is, the cache memory is divided into an internal memory space (MS _process ) of the AOP and a kernel memory space (MS _kernel ) to be used for I / O buffering of the OS. The caching method according to the present invention provides two memory spaces (MS _process , Keep the size of the MS _kernel smaller than M _available and decide whether to place the data to be cached in the MS _process or the MS _kernel , depending on the importance of the data to be cached.

3 illustrates a structure of a memory to be used for caching index data according to the present invention. Among the memory areas shown in FIG. 3, two memory spaces (MS _process , MS _kernels 340 and 350 are cache memory areas to be used by the caching method of index data according to the present invention. One important feature of the method of caching index data according to the present invention is that data that is not to be cached is not stored in the I / O buffering space 350 managed by the OS. In general, when an application reads data from disk to memory via disk I / O, the data is read from disk, once read into the OS's I / O buffering space 350, and then back to the application's memory space (330). Is copied to). That is, although not originally intended, data read from disk by an application is always cached in the OS's I / O buffering space 350.

If such unwanted data is stored in the I / O buffering space 350 of the OS, data already cached in the I / O buffering space 350 of the OS is swapped by the LRU algorithm, which is a general OS buffering management technique. out), and thus, unnecessary disk I / O is frequently generated. In order to solve this problem, the caching method according to the present invention does not read data to be cached using a specially designed system function, without reading from disk and storing it in the I / O buffering space 350 of the OS. In the memory area 330. The data stored in the memory area 330 of the AOP is immediately deleted after the AND query processing of the AOP, and the corresponding memory area is used for the next AND query processing. In other words, the data used for AND query processing never occupies the MS _process and MS _kernel (340, 350) the cache space.

How to Cache Index Data

Caching method of index data in accordance with the present invention performs the caching using the list (LIST _cache) corresponding to the index of data to be caching the word. FIG. 4 is a flowchart illustrating a process of generating a list _{cache of} words corresponding to index data to be cached.

First, web log data in which an AND query input by a user using a web search engine is recorded is recorded (step 410), and words frequently included in an AND query within a recent period (step 410) are extracted. 420). Then, among the words extracted, words having a size larger than or equal to the index data are extracted again (step 430). Here, the index data whose sizes are compared with each other is preferably MCF 210, but may include one or both of MCF 210 and RIF 220. The words extracted in step 430 are sorted in order of the size of the index data and stored in a file (step 440). The saved file is used as a LIST _cache and is used to select index data to be cached when the AND query of AOP starts.

In the caching method of index data according to the present invention, when a user inputs an AND query to a web search engine, it is first determined whether each word included in the AND query is included in the LIST _cache . Once the index data corresponding to the words contained in the LIST _cache are to be cached in the server memory space. As described above, the cache memory structure according to the present invention uses two memory spaces (MS _kernel , MS _process ) 340 and 350 as caching memory for index data. Therefore, when a word included in an AND query is included in a LIST _cache , the AOP must determine which of two memory spaces (MS _kernel , MS _process ) 340 and 350 store the index data corresponding to the word.

The AOP determines the storage location of the index data in the cache memory space (MS _kernel , MS _process ) 340, 350 according to the following criteria. That is, AOP re-extracts the words that are expected to be searched more frequently among the words in the LIST _cache and includes them in the LIST _process . When the word included in the AND query input by the user is included in the LIST _process , index data corresponding to the word is stored in the memory space (MS _process ) 350, and the word is included in the LIST _cache . If it is, but not included in the LIST _process , the index data corresponding to the word is stored in the memory space (MS _kernel ) 340. Here, the LIST _process is a list of the words most frequently used among words included in the AND query input by the user. Therefore, the LIST _process needs to be updated more frequently in the LIST _cache . For example, if the LIST _cache is updated on a monthly basis, the LIST _process can be updated on a daily or hourly basis.

Caching method of index data in accordance with the present invention, in order to manage in the most optimal according to the time variation LIST _process, by analyzing the words in the AND query that the user enters in real time and updates the LIST _process. The update of the LIST _process may be executed at regular time intervals, i.e., periodically, or in real time at the request of the AOP. In addition, the update operation of the LIST _process may be executed by a request of the AOP or by a cache algorithm execution process or a thread executed independently from the AOP. Hereinafter, a process for performing the update operation of the _process LIST "LIST _process update process _{(LIST process updating process: LUP)} " as referred to.

5 is a flowchart illustrating a method of generating a LIST _process according to the present invention. If the AOP requests the LUP to update the LIST _process (step 501), the LUP collects AND queries entered from the time of updating the latest LIST _process to the present (step 502). Although it is described in FIG. 5 that an update operation of a LIST _process is started by a request of an AOP, the LUP may periodically perform an update operation of a LIST _process regardless of an AOP request. Next, the LUP extracts words included in the LIST _cache among the words included in the collected AND query (step 503), and calculates F _i and S _i for each extracted word w _i (step 504). Here, F _i represents the number of times a user requests a search for the word w _i , and S _i represents the size of the index data corresponding to the word w _i . Next, the LUP calculates the importance I _i of the word w _i using the calculated S _i and F _i (step 505). At this time, the importance I _i has a larger value as the values of S _i and F _i are larger. The LUP performs an update operation of the LIST _{process and} an update operation of the cache memory space (MS _process ) 350 using the calculated importance I _i .

That is, the LUP checks whether a word having an importance of less than the importance I _i for the word w _i is included in the LIST _process (step 506). If, if the words having the importance of a value less than the significance (I _i) is not included in LIST _process for the word (w _i), LUP delivers the current LIST _process the AOP and ends the update process of the LIST _process (Step 509). Conversely, if a word with an importance less than the importance (I _i ) for a word (w _i ) is included in the LIST _process , the word is deleted from the LIST _process and the index data corresponding to that word is cached in memory. Delete in space MS _process 350 (step 507). The LUP newly includes the word w _i in the LIST _process , and reads index data corresponding to the word w _i from the disk into the cache memory space MS _process 350 (step 508). Finally, the LUP delivers the updated LIST _process to the AOP and terminates the update operation of the LIST _process (step 509). Here, the index data is preferably MCF 210, but may include one or both of MCF 210 and RIF 220.

Hereinafter, a method of caching index data using the above-described LIST _cache and LIST _process according to the present invention will be described in detail.

6 is a flowchart illustrating a method of caching index data for AND query processing according to the present invention. If the user enters an AND query (w ₁ , w ₂ , ..., w _n ) into the web search engine (step 601), AOP returns each word (w _i , where i = 1, 2) included in the AND query. , ..., n)

That is, the AOP checks if the word w _i is included in the LIST _cache (step 602). If the word w _i is included in the LIST _cache , it is checked whether the word w _i is also included in the LIST _process (step 603). If the word w _i is included in both the LIST _cache and the LIST _process , this means that the index data corresponding to the word w _i is already cached in the cache memory space (MS _process ) 350. Accordingly, the AOP finds index data corresponding to the word w _i stored in the cache memory space (MS _process ) 350 (step 604). At this time, the caching memory space (MS _process) if the index data corresponding to a word (w _i) to (350) is not stored, AOP is caching the caching memory space (MS _process) 350 read the index data from the disk do. The AOP then retrieves the web document using the index data stored in the caching memory space (MS _process ) 350 and returns the corresponding memory area (step 605). Here, the index data is preferably MCF 210, but may include one or both of MCF 210 and RIF 220.

On the other hand, if it is determined in steps 602 and 603 that the word w _i is included in the LIST _cache but not in the LIST _process , the AOP uses an I / O call function using the OS buffering area 340. Index data is retrieved from the OS buffering area 340 (step 606). At this time, if the index data corresponding to the word w _i is not stored in the OS buffering area 340, the AOP reads the index data from the disk and caches the index data in the OS buffering area 340. This operation is performed automatically during the operation of the I / O call function. The AOP then retrieves the web document using the index data stored in OS buffering area 340 and returns the corresponding memory area (step 605).

On the other hand, if it is determined in step 602 that the word w _i is not included in the LIST _cache , the AOP reads the index data directly from the disk into the memory area 330 of the AOP without passing through the OS buffering area 340. (Step 607). The AOP then retrieves the web document using the read index data and returns the corresponding memory area (step 605).

While the invention has been described above by way of specific embodiments, it is not intended that the scope of the invention be limited to the foregoing, and may vary without departing from the scope of the invention as defined in the following claims. Modifications or changes may be possible.

As described above, according to the present invention, a web search engine caches index data corresponding to words most likely to be used in the future, based on the distribution and frequency of use of words included in an AND query, in a memory. This can prevent performance degradation due to frequent disk I / O of the engine. In addition, according to the present invention, by using not only the internal memory area of the AOP but also the I / O buffering area of the OS as a cache memory area, caching of index data can be efficiently performed.

1 is a flowchart illustrating a process of processing a user AND query by a web search engine according to the related art.

2 shows a structure of index data according to the present invention.

3 illustrates a structure of a memory including a caching area according to the present invention.

4 is a flowchart illustrating a method of generating a list of words corresponding to index data to be cached according to the present invention.

5 is a flowchart illustrating a method of generating a list of words that are expected to be frequently used among a list of words corresponding to index data to be cached according to the present invention.

6 is a flowchart illustrating a method of caching index data for AND query processing according to the present invention.

<Description of the code | symbol about the principal part of drawing>

320: native memory area of the operating system

330: Memory area of AOP

340: internal memory area of the AOP (MS _kernel )

350: I / O buffering area (MS _process ) of operating system

Claims (10)

Based on real-time user query analysis in a web search engine performed on a computer including a web search engine memory area storing a first word list and a second word list, a memory including a first memory area and a second memory area, and a disk. In the method of caching index data for an AND query, The first word list is prepared based on a frequency of use of words included in an AND query input by the user to the web search engine for a predetermined period, and the second word list is a subset of the first word list. The caching method, (a) searching whether a word included in the AND query is included in the first word list and the second word list, (b) if the word included in the AND query is included in the first word list and the second word list in step (a), the index data corresponding to the word is read from the first caching memory area. Searching for a web document that contains words, (c) if the word is included in the first word list but not included in the second word list in step (a), the index data corresponding to the word is read from the second cache memory area and the word is read. Retrieving a web document containing Way. In the method of claim 1, (d) If the word is not included in either the first word list or the second word list in step (a), the index data corresponding to the word is inputted from the disk to the input / output (I / O) of the operating system of the computer. Outputting the web document containing the word by reading directly into the web search engine memory region without going through a buffering region. Way. In the method of claim 1, In the step (b), if the index data corresponding to the word is not found in the first cache memory area, the index data corresponding to the word is read from the disk and stored in the first cache memory. Way. In the method of claim 1, The step (c) includes reading index data corresponding to the word from the disk and storing the index data corresponding to the word in the second cache memory when the index data corresponding to the word is not found in the second cache memory area. Way. In the method of claim 1, (e) updating the first word list based on web log data storing usage history of the AND query of the user within a predetermined period of time; Way. The method of claim 5, Step (e) is (e1) analyzing the web log data to extract the most frequently used words within a recent period; (e2) extracting words of the extracted words whose size of index data corresponding thereto is equal to or greater than a predetermined threshold value, (e3) sorting the words extracted in the step (e2) in order of the corresponding index data size; Way. In the method of claim 1, (f) updating the second word list by extracting words of high importance from words included in the first word list, wherein the importance is the number of query requests for each of the words included in the first word list; And calculating using the size of the corresponding index data. Way. In the method of claim 7, Step (f) (f1) collecting AND query terms processed by the web search engine from the time of updating the latest second word list to the present; (f2) extracting words included in the first word list from among words included in the collected AND query word, (f3) calculating importance using the number of query requests for each of the words w _i extracted in the step (f2) and the size of the corresponding index data; (f4) if a word having an importance less than the importance of the word w _i is included in the second word list, the word is deleted from the second word list and the index data corresponding to the deleted word is recalled. the first caching deleted from the memory area, and wherein the insert in the second word list of the word (w _i), and comprising a read, as step index data corresponding to said word (w _i) with the first caching memory area Way. In the method of any one of claims 1 to 8, The second cache memory area is an input / output operation (I / O) buffering area of the operating system. Way. In the method of any one of claims 1 to 8, The index data includes IDs of web documents including words included in the AND query and location information of importance information of the web documents. Way.