WO2011025162A2 - Method for searching for a list of entities belonging to a specific class - Google Patents

Abstract

The present invention relates to an information searching and ranking model. An aim of the present invention is to provide a method which provides a result suitable for the intention of an information search inquirer when the inquirer seeks to obtain list information on entities belonging to a specific class. For example, for an inquiry on "Web server list", the intention of the inquiry is the desire to know an existing list of Web server entities such as Apache belonging to a class called "Web server". However, existing search engines cannot provide a ranking of the results suitable for this intention. To solve this problem, the method of the present invention involves extracting a class, entity information belonging to the class, and significance information of the entity, from a collected document and establishes a database. Next, when a search engine receives an inquiry for the intention, it finds a class in the intention from the database, aligns information on entities belonging to the class according to significance, and transfers the information to a subsequent user. Thus, the user can obtain a good search result.

Description

[Correction by rule 26.08.09.2010] 리스트 List search method of entity belonging to specific class

The present invention relates to information retrieval and data mining using a computer or an information communication network. More particularly, the present invention relates to a method for producing a suitable ranking result in accordance with the intention of a search query, and data (primarily non-structured). In the literature).

 As the Internet has become popular, many users are getting information through Internet search services. One of the important abilities a search engine should have is to identify the user's search intent and produce ranking results that match that intent. However, existing search engines are based on simple keyword-based search, and there is no satisfactory technology. In particular, when a search query wants to know a list (or list) of entities belonging to a particular class, it does not show a suitable result corresponding to the query.

 An entity is here a broad term that refers to any one being (including both tangible / intangible, abstract / specific, or material / immaterial beings). A class is a term used to refer to a group of entities with common characteristics, similar to the concept of classes used in object-oriented programming theory. This term is synonymous with kind, type, or category, and can be thought of as an abstract entity. For example, Socrates and Plato are each an entity, and man is the class of those entities.

 As an example of the query of intention described above, if a query called "cosmetic store list" is thrown, the intention of this query is to obtain a list of instances belonging to the class "cosmetic store" as a search result. In this context, an instance is a term that refers to an existing entity, and is similar to an instance used in object-oriented programming theory. Thus, an instance of the class "cosmetic store" is the actual store operator. However, when queried as such, existing search engines often display high rank web page information that is simply co-occurrence terms. In fact, if you've experimented with a well-known search engine, the search 1 ranking result is a web that consists of a text with the phrase "cosmetics store" and a menu with the phrase "playlist" that has nothing to do with it. Page. That is, the search engine simply displays a web page where the queryed word appears.

Now think about the query "List of hospitals in Bundang." The intent of this query is to know a list of instances of a particular class called "Bundang Hospital" (here, the actual operators that run Bundang Hospital). Such a query to another well-known keyword-based search engine would inadvertently rank a link to a web page that contains results that match the query's intent. But when you look at the list on the web page, you're sorting in a meaningless order so you don't know which hospital has a better reputation and is more authoritative. In other words, it is shown as a ranking irrespective of the importance of the object to find. And the addresses and phone numbers of the hospitals were good because they were listed on a web page, but there was no hyperlink to the hospital's website URL or directions page showing the location of the hospital. In other words, even if you browse a web page with a list you want, there is no organized and convenient information.

The present invention seeks to automatically and reliably determine the objective ranking of entities belonging to a particular class using a computer. The ranking results are applied to information processing such as information retrieval, classification, clustering, and prioritizing. In particular, by grasping the pattern of a query of a search engine user, it is determined whether the intention of the query is to obtain list information of instances belonging to a specific class, and if so, the ranking result obtained in the present invention is provided as a search result. To improve the quality of service.

 List search method of the entities belonging to the specific class of the present invention,

It is divided into how to rank the entities belonging to a specific class and how to produce the result suitable for the user's query.

 First, the method of ranking the entities belonging to a specific class is

 Acquiring a database storing a collection of classes and information of instances belonging to each class, or extracting relevant information from data that is a source of information (101) to build a database (102);

 Extracting sequence ranking information of an instance (exactly, the term for instance) appearing in each document of the collected document collection (103);

 A process of extracting term frequency or / and Boolean term frequency information of an instance (exactly, an term meaning an instance) appearing in collected documents together with the above-described extracting ranking order information of instances. (103),

 Calculating a ranking score of the instances in the collection of instances belonging to a particular class according to the order of ranking of the instances, the term frequency, and / or the term term frequency (104);

 In step 105, the calculated ranking score of each instance is stored in a database.

 The best way to get the right results for your query is

 Receiving a search query from a client 201;

 Determining a pattern of the query and determining whether the intention of the query is to obtain list information of instances belonging to a specific class (202);

 Extracting a word representing an entity from the query if the intention of the query requires list information (203);

 Finding a class item in the collection (or dictionary) of classes in the database that match the word for that entity (204);

 If there is a matching class item, the process of finding a collection (or list) of instances associated with (associated with) the item for that class (205);

 Reading the data items for the instances in the found collection of instances and writing the answer (206);

 And providing the answer (search results) to the client (207). While writing the answer content, the method may further include sorting the data (search results) of the instance according to the ranking score of the instance.

 According to the present invention as described above, when a search queryer requests a list of entities belonging to a specific class, it is possible to provide high quality results corresponding to the intention.

In addition, the importance ranking of the entities belonging to a specific class can be determined objectively and at a low cost.

 1 is a flowchart illustrating a process of determining a ranking of entities belonging to a specific class in the method for searching a list of the entities belonging to the specific class of the present invention.

 2 is a flowchart illustrating a method of providing a result suitable for a user's query in a method for searching a list of entities belonging to a specific class of the present invention.

 3 is a view showing an example of a literature collection in the present invention.

 4 is a diagram of a database of an abstract structure consisting of a collection of classes and a collection of instances associated with each class (which is an item within that collection), in accordance with the present invention.

 5 is a diagram showing an example of an index embodying an abstract database in the present invention.

 6 is a view showing an example of the provided search results in the present invention.

 FIG. 7 illustrates an example of a relational database for an entity named enterprise in the present invention. FIG.

8 is a diagram illustrating a system for searching a list of entities belonging to a specific class in the present invention.

 In order to implement the present invention, a new ranking model is proposed. The description of the model is largely divided into how to rank entities belonging to a specific class and how to produce a result suitable for a user's query.

 The ranking method of the present invention is based on the following two empirical rules.

 First, people write things that are usually considered important when referring to instances belonging to a particular class.

 Second, people list things that are usually considered important when listing multiple instances belonging to a particular class.

 Let's explain the first rule of thumb. We often see patterns in the pattern "A, B, C, and D Business Groups" when we read articles that list the names of Korean business groups published by the media. Of the many instances of a class called "corporate groups" (here, "corporate group businesses") in the media, only four of these instances are often mentioned because their sales, assets, and social influence are more likely than other firms in Korea. It is considerably more important. As we see above, we often experience the application of the first rule of thumb in everyday information exchange.

 Let's explain the second rule of thumb this time. When we read articles that list university names in the media, we often see sentences with patterns like "Admissions Guidelines for Colleges A, B, and C". When most media refer to universities in Korea, they are listed in the above order because they are considered to be A, B, and C in order. As mentioned above, we often experience the application of the second rule of thumb in everyday information exchange. Therefore, we can implicitly include the author's intelligent judgment of which instance is important to that data and which instance is more important.

 Thus, data or data (mainly unstructured textual documents) to which the above two empirical rules apply can extract information about which instances belong to a particular class and which of those instances are important or their importance sequences.

Of course, such judgment information of an individual cannot be completely trusted. Thus, the present invention introduces the concept of collective intelligence used when describing web 2.0. Collective intelligence refers to the intelligence (or intelligence) of a group of individuals when they collaborate in groups. The term is used in the theory that judgment results are better when multiple individuals come together and cooperate than individual judgments. According to this theory, if an individual makes such a judgment, it is not entirely reliable, but the average (or summation) of the multiple judgments is believed to be reliable.

 Hereinafter, the present invention is to disclose a ranking method based on the two empirical rules and the concept of collective intelligence. Once the ranking method is outlined, the computer extracts a particular class, its instance information, and the importance of the instance from the data (usually unstructured textual literature) and then ranks them based on them. This method is described step by step with reference to FIG. 1.

 First, a database storing a collection of classes and information of instances belonging to each class is obtained (101 and 102). If a well-organized database is difficult to obtain, the database can be constructed by extracting the relevant information from the data that is the source of the information (101).

 If the data that would be the source of such information extraction is a document collection of text written in natural language, in order to obtain a particular class and its associated instance information, the search server may use an is-a relationship in that document. In operation 101, information about a class and an instance (in other words, class / instance pair) having the information is found and extracted. Here, an relationship is a relationship in which an entity is an instance of a particular class. For example, in the English sentence “Socrates is a man.”, We can see that an entity called Socrates is an instance of a class called man. In natural language, such a relationship is called an Iz-word relationship because it is expressed in the following pattern.

"<entity> (a main noun) is a <class> (a noun).

(In this case, compound nouns are seen as one noun.)

The term is-a word relationship is a term commonly used in object-oriented programming theory. The search server analyzes documents written in natural language and tokenizes them and finds out whether they are Iz-related.

"A is a B." The statement in the pattern is an explicit Iz-word relationship, but the following sentences (or paragraphs) can also find class / instance pairs in the Iz-word relationship.

I'm from A elementary school.

I want to join B Corporation and C Corporation. Such a public company is stable.

Company D belongs to a large company.

He tried to be a scientist like E.

From the above sentences, the following Iz-e relationship information can be extracted.

A elementary school is elementary school.

Corporation B and Corporation C are public companies.

Company D is a large company.

E is a scientist.

That is, from the above sentences, class / instance pair information such as (elementary school / A elementary school), (public corporation / B corporation), (public corporation / C corporation), (large company / D corporation), and (scientist / E) is obtained. Therefore, if the text document is analyzed by the above-described method, the class and instance information thereof can be extracted.

 In the process of finding and extracting class and instance information (101), the data that is the source of information extraction is not a structured text document as described above, but a structured database, and the database has an Is-Ear column. If includes, class / instance pair information can be extracted. For example, in the relational database 805 for an entity called enterprise as shown in FIG. 7, the second column is a "company classification" column with a value such as "large company / small business / venture company", and the first column is the "company name". "to be. The fields in the second column are then classes, and the fields in the first column are instances of that class. That is, the second column and the first column have an Iz-er relationship. In the database as shown in FIG. 7, the pair information of SMEs and the "Venture Company" class and a list of company names (eg, A, D, E and F companies) belonging to the class may be extracted.

 The data source of information extraction in step 101 is not only unstructured text documents and relational databases but also semantic web, microformat HTML documents, and entity-relationship model data. It can also be obtained from WordNet.

 An embodiment of the process of finding and extracting class and instance information 101 is as follows. 3 is an example of a literature collection 301. The search server finds and extracts a class / instance pair having an idea-ear relationship from each document of FIG. 3.

(a) Analyzing the document 311, the sentence "D, E, F companies ..." as a video portal company can be found in the sentence "D, E, F companies are video portal companies."

Therefore, in the document 311, a class called "video portal company" and information that the companies D, E, and F belong to it are extracted (101).

(b) Analyzing document 312 finds the I-E relationship information "G and H are enterprise groups" in the phrases "G company groups" and "H company groups".

Accordingly, the document 312 extracts information that the class "enterprise group" and the instances G and H belong to it (101).

Thereafter, the extracted class and the instance information belonging to the extracted class are put into the database.

4 illustrates a database of abstract structures consisting of a collection of classes 401 and a collection 402 of instances 410 associated with each class (which is an item in that collection). Here, a collection refers to a group of data items of the same type. Types of collections include lists, sets, multisets / bags, trees, and graphs. Usually tables and arrays are not treated as collections, but for the sake of convenience in the present invention, they are considered to be a kind of collection.

 In more detail, the process of storing the extracted class and the instance information belonging to the database 102 in the database, the search server puts the extracted class in the collection 401 and the instance belonging to the class (410) associated with the class ( 402). If there is no collection 402, of course, it creates a collection, then associates it with a class (410) and puts an instance into it.

 A database having a structure as shown in FIG. 4 may be embodied as an index as shown in FIG. 5. The collection 401 of the class of FIG. 4 is embodied as a list 501 (commonly referred to as a dictionary) and the collection 402 of instances is embodied as a list 510. Like the connection 410 in FIG. 4, each item in the list 501 is connected to the other list 510 (520).

 An embodiment of the process 102 of storing the extracted class and instance information belonging thereto is as follows.

 (a) As described above, in the process of extracting class and instance information from the search server 801, in the document 311, a class called "video portal company" and an instance of companies D, E, and F are used. Extraction of information called a fish relationship (101).

Thereafter, the dictionary 501 of the index 804 having the structure as shown in FIG. 5 checks whether or not a class named "video portal company" exists as an item, and if not, inserts the item and puts the class name in the item ( 102). After creating a list 510 that is linked 520 to the item, the data of the three operators (including name) is put into the item of the list.

 (b) In the document 314, similar to the above, a class named "video portal company" extracts information of an instance of an E, D, A company and an Is-Ear relationship (101). The class item already exists in the dictionary 501, so only the instances need to be added to the index. Since E and D are already present in the list, only A is added (102). Class / instance pairs in documents 312 and 313 are also stored in the database in the same manner as above. In this way, you can build a database or index that knows which instances belong to a particular class.

 Then, sequence ranking information of an instance appearing in each document of the collected document collection (exactly, the term meaning instance) is extracted (103). The rank order of instance i is a term defined in this document and refers to the number of ranks in which instance i appears in the list of instances of the class to which instance i belongs in a document. For example, comparing the instances stored in index 804 by sequentially sequencing tokens in document 311, D, E and F appear in document 311 in the order just described and they are referred to as "video portal vendors". You can see that it belongs to a specific class. If so, D's ranking is first, E's second, and F's third.

 You can also search the ranking information in which these instances are listed in the entire document range, rather than in a single paragraph. For example, analyzing the document 312 using an index reveals that instances stored in the indices G and H (FIG. 5) appear in the document 312, which belong to a particular class called "corporate group." have. In this case, G's group ranks first, H's second.

 Note that the listing rank is the appearance ranking within the listing of instances belonging to a particular class in a document. For example, if a document appears with a middle school name "X Middle School" and two high school names "Y High School" and "Z High School" appear in that order, then the class "Middle School" appears in the document. The list of instances belonging to is "X Middle School", and the list of instances belonging to a class called "High School" is "Y High School" and "Z High School". Therefore, in the document, the rank order of "X middle school" is 1, and the rank order of "Y high school" and "Z high school" are 1 and 2, respectively.

 Then, along with the above-described extracting ranking order information of the instances, term frequency or / and Boolean term frequency information of an instance appearing in the collected documents (exactly, the term meaning an instance) is extracted. It may be done (103). Here, the term frequency refers to the frequency of occurrence of a specific term in a document. And terminology terminology is a variation of terminology, the value of which is 1 if a particular term appears in a document and 0 otherwise. For example, in document 311, the instance D appears twice, so that the term frequency of D in 311 is 2 and the term frequency of boolean is 1.

 The following describes how to rank the instances in an instance collection belonging to a specific class. The ranking score of the instances for the ranking is determined according to the order of ranking of the instances, the term frequency or / and the term term, based on the basic concepts described above (104).

 This ranking score function can be expressed as Equation 1 and Equation 2 below by using a mathematical formula.

Equation 1

Equation (1) gives a ranking score when given the term i for a specific instance belonging to a specific class c in a collection of documents D consisting of N documents, d ₁ , d ₂ , ..., d _N-1 , d _N. Indicates.

Here, S (i, c) is the ranking score of i belonging to c,

w _j is the weight of document d _j ,

O _{i, c, j} is the number of ranks (starting at 1) where i appears in the list of instances belonging to class c appearing in document d _j , and its value is assumed to be infinity (∞).

 Description of Equation 1 is as follows. It is the sum of the product of terms called the inverse of the weight of the document and the number of ranks of the instances. The score of instance i in one document is proportional to the inverse of the number of ranks in which instance i appears in the list of instances belonging to class c to which instance i belongs. That is, if an instance appears first in the sequence, its multiplier is (1/1), and if it appears second, the multiplier is (1/2). If an instance does not appear in the document, the multiplier is 0 because it appears to be an infinite equality.

 Another multiplier is the weight of the document. This weight may be arbitrarily determined by the calculator in accordance with the characteristics of the document collection. For example, if the document is a web document, its weight can be determined by a static ranking model such as PageRank.

 Analyzing Equation 1, it can be seen that the score obtained through the product of the inverse of the rank rank of instance i and the document weight in one document is compatible with the empirical rule. And it can be seen that the ranking score in the document collection of a particular instance is the sum of the scores in each document. This corresponds to the spirit of collective intelligence mentioned above.

 Calculating the ranking score through the above formula through the embodiment as follows. The w value of document tag 321 in FIG. 3 is a weight that is metadata for each document. Let's obtain the ranking score obtained by the company D, which is an instance of the video portal company appearing in FIG. Company D, belonging to the class "Video Portal Company", appears first in the listing of the class in document 311, does not appear in documents 312 and 313, and lists the class in document 314. Appears second in. Therefore, D's ranking score is as follows. The mathematical symbol "*" below means a product symbol.

(Ranking score of D company)

= 0.3 * (1/1) + 0.4 * (1 / infinity) + 0.1 * (1 / infinity) + 0.2 * (1/2)

= 0.4

Similarly, the ranking score of E, an instance of a video portal company, is as follows.

(Ranking score of E company)

= 0.3 * (1/2) + 0.4 * (1 / infinity) + 0.1 * (1 / infinity) + 0.2 * (1/1)

= 0.35

Therefore, Company D has a higher ranking score than Company E. Therefore, D ranks higher than E when ranking each instance in the collection of instances belonging to the "Video Portal Vendor" class.

The ranking score of an instance belonging to a specific class may also be calculated by the formula of Equation 2 below (104). Equation 2 is a ranking score when given the term i for a specific instance belonging to a specific class c in the document collection D consisting of N documents, d ₁ , d ₂ , ..., d _N-1 , d _N Indicates.

Equation 2

Here, S (i) is the ranking score of i,

w _j is the weight of document d _j ,

tf _{i, j} is the term frequency or Boolean term frequency of i in document d _j (1 if it appears, or 0 otherwise).

 Explanation of Equation 2 is as follows. The formula is, as you can see, the sum of the weight of the document and the term term frequency (or term term boolean) of the instance. Equation 2, like Equation 1, also meets the above empirical rules and the concept of collective intelligence. Equations 1 and 2 may be combined, or the equations may be modified and used within a range reflecting the basic concept of the present invention. Since the modification formula of the term frequency in Equation 2 can be easily identified in the information search textbook, the description is omitted here. And the use of Equation 2 will be described in detail in the following specific embodiments.

 In the last step, the calculated ranking score of each instance is stored in the database (105). For example, the ranking score of Company D calculated as described above is stored in the ranking score storage area (the area indicated by parentheses, ie, 512) of the item 511. For reference, the ranking score in FIG. 5 is a score obtained in the following specific examples. This completes the construction of the database (or index).

 Although omitted from the figure, when storing the index, additional data other than the instance name and the ranking score may be included as data for each instance. For example, if an instance is a company, data such as contact numbers, addresses, employee numbers, sales, stock prices, etc. can be obtained from the company's mutual telephone number database and the corporate disclosure website. You can take each business-specific data from this database and put it in an item for an instance in the index. This performance will be described in the following specific embodiments.

 Hereinafter, referring to FIG. 2, when a search engine user wants to obtain list information of instances belonging to a specific class, the search server grasps the intention and uses the database constructed as described above to obtain a search result corresponding to the query. Explain how to pay.

 In a first step, search server 801 receives a search query from client 810 (201).

 In operation 202, it is determined whether the intention of the given query is to obtain list information of instances belonging to a specific class. Specifically, when the query pattern is as follows, it may be determined that the list information is desired.

"List (or list): <entity>",

"<Entity> list (or list)",

"Compare <entities>".

An example of the pattern is as follows.

"List: web servers",

"List of Navigator Manufacturers",

"Comparison of Domestic Cars".

The above intention may also be determined when a list or the word list does not exist explicitly in a query, but a noun or a pronoun is followed by a suffix indicating "s". Even if this is not the case, the query intent is that you want the list information. If the query is in English, it can be determined that the following are queries of the intention.

"list: <entity or entities>"

"a list of <entity or entities>"

"<entity> list"

"<entiti> es

"comparison of <entity or entities>"

If it is determined that the intention of the query has been described above, the next step, the search server 801 extracts a word for the entity from the query (203).

 Then, a class item matching the word representing the entity is found in the collection 401 of the class in the database as shown in FIG. 4 (204). If the abstract database is implemented with an index as shown in Figure 5, it is found in a dictionary 501. For example, if the query is a "video portal company list", the word "or video portal company" (or phrase) is extracted from the query (203) and the dictionary class class item 502 matching the word representing the entity is dictionary. Look up (501) (204).

 When a matching class item is found, a list of instances of (520) instances associated with (item) an item for that class is found (205).

 When the list of instances is found through the process 205, the data items for the instances in the list are read, the answers are written, and the data (search results) of the instances are sorted according to the ranking score of the instances. (206).

 Of course you can omit this sort if you don't want to. Also, if the instance items in the list are sorted in order of ranking score in advance, the sorting operation is unnecessary. In addition, instance items may be re-ranked by another ranking algorithm before and after the alignment.

 Finally, the answer (search results) is forwarded to the client 810 (207).

 The above-described processes 205, 206, and 207 are described by way of example, where a class name matching the word "video portal company" is found in the index (Fig. 5). If a matching item 502 is found in the dictionary 501 of the index, a list 510 associated with the item is found (520) (205). The list contains items that contain data about D, E, F, and A. Sort according to the ranking score in parenthesis 512 in each item. If you sort in descending order, the result is D, E, F, and A. In addition, the contents of the answer are written with attributes such as an address and a phone number of each instance (206). The response is then sent to the client 810 (207).

 In addition, the ranking method described above can be applied not only in the field of information retrieval but also in other information processing fields such as classification, clustering, and prioritizing. An example of classifying, clustering, and prioritizing instances belonging to a specific class using the above-described ranking method is as follows. (a) A ranking score may be scored for instances belonging to a class called a smartphone vendor, and classified into major smartphone vendors and minor smartphone vendors according to a reference score. (b) A ranking score may be assigned to an instance belonging to a class of US universities, and groups of universities with similar scores may be grouped into 1st and 2nd grade schools. (c) Ranking rankings for instances belonging to a class called blog websites, and determine the priority and frequency of visits for the blogs of the web crawler according to the scores.

 The following items are supplementary descriptions of the present invention.

 a) Formulas 1 and 2 are compared with the tf-idf weighting formula. Notably, the formula 1 and formula 2 do not have an inverse document frequency (idf) term, unlike the tf-idf weighting formula. The basic concept of the tf-idf weighting formula is that the term is meaningful only when it appears only in certain literature. In contrast, Equations 1 and 2 are based on the idea that instances that are often mentioned are important, so there is no inverse document frequency term. Therefore, there is no inverse frequency term.

 b) When extracting the ranking information of an instance belonging to a specific class in a document, we can see the case where an instance appeared several times in the listing. In that case, you can count the number of instances each time they appear, but it's better to count only the number of ranks that appear first. For the first instance appears to be the subject sentence (or preface) of the paragraph describing the instance, and the next instance is likely to be the sentence to describe the subject.

 c) Classes and instances may have an Eze-Eye relationship, but classes and subclasses may also have an Eze-Eye relationship. In the present invention, subclasses are considered to be instances for the sake of simplicity.

 d) In order to simplify the formulas of Equations 1 and 2, the weight of the document may be fixed to a constant equal to one. This can be useful when you can't or don't need to weight documents.

 e) When calculating a ranking score of a term having a plurality of meanings, the weight of the document may be adjusted according to the relevance of the document to the class. For example, the term apple can be an instance of a fruit but an instance of an IT enterprise. When calculating the ranking score for Apple, the IT company, if the document is related to IT, the weight is increased. If the document is related to fruit, the weight is decreased.

 Hereinafter, with reference to the embodiments shown in the accompanying drawings will be described in detail. This embodiment is constructed in the first and second embodiments of the above-described method of extracting information of entities belonging to a specific class in document collection FIG. 3 and determining the importance ranking of the entities using the formula (2). The second embodiment describes a method of producing a search result that matches a user's intention by using the index.

 First, the first embodiment is illustrated. First, as shown in FIG. 8, the search server 801 collects computer readable documents from web servers 803 on the Internet via the information communication network 802. Then, the collected document collection 301 finds and extracts class and instance pair information having an Ez-E relationship (101). The results are shown through the example of FIG. 3 as follows.

In Document 311: (Video Portal Vendors / D, E, F); (Classes are paired with each instance in parentheses.)

In document 312: (corporate group / G, H);

In document 313: (corporate group / B);

In Document 314: (Video Portal Vendors / E, D, A).

The ID is assigned to the extracted instance as D / 1, E / 2, F / 3, G / 4, H / 5, B / 6, A / 7.

 Then, the extracted information of the class and the instances belonging to it is stored in the index (102). The procedure is as follows. Let's say the index in Figure 5 is empty before doing this.

 (a) Process the entities that appear in document 311. It checks if the class "Video Portal Company" exists in the dictionary 501 of the index of FIG. 5, and if not, inserts it (in the item at position 502). After insertion, a list 510 is created that is linked 520 to the item 502 of that class. Put instances D, E, and F belonging to the class in the list.

 (b) Process the entities that appear in document 312. Checks if a class named "corporate group" exists in the index, and if not, inserts it (in the item at position 503). After insertion, a list is created that is linked to item 503 of that class. Put the instances G and H belonging to the class in the list.

 (c) process the entities that appear in document 313; Examine whether the class "corporate group" is in the index. Since it already exists, find the list that is linked to item 503 of that class. Check if B is in the list, and if not, put it.

 (d) Process the entities that appear in document 314. Check if the class named "Video Portal Vendor" is in the index. Since it already exists, find the list that is linked to item 502 of that class. Examine the list for E, D and A. There is no A, so put it in the list.

 As such, after storing the extracted information of the class and the instances belonging to it in the index, the term frequency information of the instance is extracted in each document as follows (103). That is, in this embodiment, the term frequency information in each document is extracted instead of the order ranking information.

In Figure 3,

In Document 311: D appears twice, E is 1, F is 1;

In Document 312: G is 1, H is 1;

In Document 313: B is 1;

In Document 314: E is 1, D is 1, A is 1.

 The importance ranking score of the extracted instance is calculated through Equation 2 (104). As the weight of the document, the w value of the tag 321 is used. The weight of each document was obtained through PageRank. In the present embodiment, the term tf of Equation 2 is defined as term frequency, not term term. The ranking score of each instance is as follows.

A: 0.3 * 0 + 0.4 * 0 + 0.1 * 0 + 0.2 * 1 = 0.2

B: 0.3 * 0 + 0.4 * 0 + 0.1 * 1 + 0.2 * 0 = 0.1

D: 0.3 * 2 + 0.4 * 0 + 0.1 * 0 + 0.2 * 1 = 0.8

E: 0.3 * 1 + 0.4 * 0 + 0.1 * 0 + 0.2 * 1 = 0.5

F: 0.3 * 1 + 0.4 * 0 + 0.1 * 0 + 0.2 * 0 = 0.3

G: 0.3 * 0 + 0.4 * 1 + 0.1 * 0 + 0.2 * 0 = 0.4

H: 0.3 * 0 + 0.4 * 1 + 0.1 * 0 + 0.2 * 0 = 0.4

 Finally, the ranking score of each calculated instance is stored in the index (105). The items in each list in that index are then sorted by the ID of the instance, by name (in alphabetical order), or by the ranking score of the instance. The results are as follows when ordered by the ranking score.

Class "Video Portal Vendor": D (0.8)> E (0.5)> F (0.3)> A (0.2) (Ranked Scores in Brackets)

Class "corporate group": G (0.4) = H (0.4)> B (0.1)

In addition, the database 805 of an entity called an enterprise is read and the physical address, homepage address, sales, profit, and number of employees of each enterprise are put into the corresponding item as shown in FIG.

 Hereinafter, the second embodiment will be exemplified using the index constructed in the first embodiment. When the client 810 makes a query of "List: Corporate Group", the search server 801 that has received the query 201 determines whether the intention of the query is a list of instances belonging to a specific class (202). The client is a computing device such as a personal computer, a mobile device. If it is determined that you want a list of instances, it proceeds to extract the entity from the next query, and if not intended, terminates the query processing or passes the query to another module.

 Next, a word representing an entity is extracted from the query "List: Enterprise Group" (203). In this case, an entity called "corporate group" is extracted.

 A class name matching the word representing the entity is found in the index as shown in FIG. 5 (204).

 The class name that matches item 503 is shown. A list of instances associated with the found item 503 is found (205).

 Then, with the data of the item in the found list of instances, the answer to the query is made (206). When writing an answer, sort the data (search results) of that instance according to the item's ranking score. In other words, the ranking results. In the second embodiment, the ranking is determined based on the ranking score determined by the first embodiment, and the results are as follows.

G (0.4) = H (0.4)> B (0.1)

In order to systematically display the search results, as shown in FIG. 6, a table is created with data of each company group's name, ranking score, physical address, homepage address, sales, profit and number of employees.

 And finally, the response is sent to the client 810 (207). As can be seen in Figure 6, the search results are sorted according to the ranking score, and the attributes of each corporate group are systematically shown, which is convenient for the user to obtain information.

The ranking scores obtained in the first embodiment can be applied not only to information retrieval fields as in the second embodiment, but also to other information processing fields such as classification, clustering, and prioritizing. . For example, the web crawler may set the ratio of the frequency of visits to the sites of the instances belonging to the "video portal company" class as the ranking score. Accordingly, the web collector visits the sites D, E, F, and A at a ratio of 8: 5: 3: 2. As another example, if the criterion of being labeled with the first grade among the instances of the class "corporate group" is a ranking score of 0.3 or higher, G and H are classified as the first grade.

Claims (7)

 A first step of acquiring a database storing a collection of classes and information of instances belonging to each class, or extracting related information from data that is a source of information;  A second process of extracting at least one of term frequency and enumerated rank information of a term representing each instance in the database appearing in the collected document;  A third step of calculating a ranking score of the instances in the instance collection belonging to a specific class according to at least one of the rank order and term frequency of the extracted instances;  And a fourth step of storing the calculated ranking score of each instance in a database.  The method of claim 1,  In extracting the term frequency information of the term meaning each instance in the database appearing in the document collected in the second step, to extract the information of either the term frequency or the Boolean term frequency or both. How to determine the ranking of the entities belonging to a particular class characterized in that.  The method of claim 1,  The first step is to find and extract information about a class and an instance (class / instance pair) having an is-a relationship in the collected document of the text written in natural language, and the extracted class and The method of determining the ranking of the entities belonging to a specific class, characterized in that it further comprises the step of putting the instance information belonging to the database and knowing which instances belong to a particular class.  The method of claim 1,  In calculating the ranking score of the instances in the third step,  A ranking score when the term i, which represents a specific instance belonging to a specific class c, is collected from a collection of N documents, is determined from the following equation.

 Here, S (i, c) is the ranking score of i belonging to c, w _j is the weight of document d _j , O _{i, c, j} is the number of ranks (starting at 1) where i appears in the list of instances belonging to class c appearing in document d _j , and its value is assumed to be infinity (∞).  The method of claim 1, wherein in calculating the ranking score of the instances in the third process,  A ranking score when the term i, which represents a specific instance belonging to a specific class c, is collected from a collection of N documents, is determined from the following equation.

 Here, S (i) is the ranking score of i, w _j is the weight of document d _j , tf _{i, j} is the term frequency or Boolean term frequency of i that appears in document d _j .  Receiving a search query from a client,  Determining a pattern of the query and determining whether the intention of the query is to obtain list information of instances belonging to a specific class;  If the intention of the query is to request list information, extracting a word representing an entity from the query;  The process of finding a class item in a collection (or dictionary) of classes in the database that matches the word for that entity,  If there is a matching class item, the process of finding a collection (or list) of instances associated with (associated with) the item for that class, Creating a response by reading the data items for an instance in the found collection (or list) of that instance,  A method of retrieving a list of entities belonging to a specific class, characterized by a method for producing a result suitable for a user's query, which is made by providing the client with the answer (search results).  The method of claim 6,  The process of writing the contents of the answer may include a method of producing a result suitable for the user's query, which further includes the step of sorting the data (search results) of the instance according to the ranking score of the instance during the contents of the answer. How to retrieve a list of entities belonging to a specific class.

Images