SEARCH APPARATUS, SEARCH METHOD, AND RECORDING MEDIUM STORING PROGRAM

• US 20110219000A1
• Filed: 11/06/2009
• Published: 09/08/2011
• Est. Priority Date: 11/26/2008
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Kusumura, Yukitaka
• Granted Patent: US 8,892,574 B2
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 16/3346 using probabilistic model

Abstract

Provided is a search apparatus, a search method, and a program that can improve search speed for a document set even when an object to be searched is a large-scale document set. A search apparatus is used which includes an abstract matrix storage unit 1 that, when information which is created from a plurality of regions of a matrix representing a co-occurrence relationship between a word set and a document set and which represents a subset of the document set is provided, stores abstract information which enables calculation of a frequency of a word in each region, a word frequency calculation unit 2 that, in response to an input of the information representing the subset, examines a relationship between this and each region, refers to the abstract information of each region, and calculates an upper limit of the frequency for the subset of the word by each region, a word frequency calculation unit 3 that adds the upper limit of the frequency for each word region, and specifies the added value as the upper limit of the frequency of the word for each word region, and a document frequency reference unit 4 that obtains a region to be searched from the upper limit of the frequency of the word for each word region, and specifies the specified number of words in order of higher frequency according to this region.

Claims

1. A search apparatus comprising:

an abstract matrix storage unit that, when information which is created from a plurality of regions obtained by dividing a matrix representing a co-occurrence relationship between a word set and a document set and which also represents a subset included in the document set is provided, stores information which enables calculation or estimation of a frequency of a word in each of the to plurality of regions as abstract information;

a region upper limit calculation unit that, when the information representing the subset is input, examines a relationship between the information representing the subset and the plurality of regions, refers to the abstract information for each of the plurality of regions from the obtained result, and calculates, for each of the plurality of regions, an upper limit of the frequency of the word included in each of the plurality of regions for the subset;

a word frequency calculation unit that adds the upper limit of the frequency for each of the plurality of regions by each region with a common word, and specifies the obtained added value as the upper limit of the frequency of the word for each region with the common word; and

a document frequency reference unit that obtains a region to be searched according to the upper limit of the frequency of the word for each region with the common word, further specifies a specified number of words in order of higher frequency according to the obtained region to be searched, and outputs the specified word as a word characteristic to the subset.

2. The search apparatus according to claim 1, further comprising:

a cluster creation unit that inputs the matrix specifying the co-occurrence relationship between the word set and the document set, performs a clustering process to the word and a document, thereby divides the word set and the subset composing the matrix into a plurality of subsets to generate the plurality of region; and

a region abstract creation unit that creates the abstract information stored by the abstract matrix storage unit from the plurality of regions generated by the division of the clustering process.

3. The search apparatus according to claim 2, wherein

the region abstract creation unit, for each of the plurality of regions created by the division in the clustering process, obtains at least the frequency in the region of the word included in each region, further specifies a maximum value of the obtained frequency, and sets the specified maximum value as the abstract information, and

the region upper limit calculation unit, for each of the plurality of regions, obtains a number of the documents composing the subset included in the region as the relationship between the information representing the subset and the plurality of regions, compares the obtained number of documents and the maximum value of the frequency for the region, and calculates the upper limit of the frequency according to a comparison result.

4. The search apparatus according to claim 2, wherein

the region abstract creation unit, for each of the plurality of regions created by the division of the clustering process, obtains at least a bitstream indicating whether the word in the region is included in the document of each region, and sets the obtained bitstream as the abstract information, and

the region upper limit calculation unit, for each of the plurality of regions, obtains a bitstream indicating whether the document composing the subset is included in the region as the relationship between the information representing the subset and the plurality of regions, executes an AND operation between the bitstream obtained by the region upper limit calculation unit and the bitstream obtained by the region abstract creation unit, and calculates the upper limit of the frequency according to an operation result.

5. The search apparatus according to claim 2, further comprising:

a plurality of cluster processing unit;

a cluster process expansion unit; and

a cluster process selection unit, wherein

the cluster creation unit, the region abstract creation unit, the abstract matrix storage unit, the region upper limit calculation unit, the word frequency calculation unit, and the document frequency reference unit are included in each of the plurality of cluster processing unit,

each of the cluster creation unit performs a different clustering process from each other in each of the plurality of cluster processing unit,

when the information representing the subset is input, the cluster process expansion unit inputs the input information into each of the region upper limit calculation unit of the plurality of cluster processing unit,

the cluster process selection unit receives the upper limit of the frequency of the word for each region with the common word, which is specified by the word frequency calculation unit in each of the plurality of cluster processing unit, and selects at least one of the plurality of cluster processing unit according to distribution of the upper limit of the frequency of the received each word, and makes only the document frequency reference unit of the selected cluster processing unit perform the process.

6. A search method comprising:

(a) when information which is created from a plurality of regions obtained by dividing a matrix representing a co-occurrence relationship between a word set and a document set and which also represents a subset included in the document set is provided, storing information which enables calculation or estimation of a frequency of a word in each of the plurality of regions as abstract information;

(b) when the information representing the subset is input, examining a relationship between the information representing the subset and the plurality of regions, referring to the abstract information for each of the plurality of regions from the obtained result, and calculating, for each of the plurality of regions, an upper limit of the frequency of the word included in each of the plurality of regions for the subset;

(c) adding the upper limit of the frequency for each of the plurality of regions by each region with the common word, and specifying the obtained added value as the upper limit of the frequency of the word for each region with the common word; and

(d) obtaining a region to be searched according to the upper limit of the frequency of the word for each region with the common word, further specifying a specified number of words in order of higher frequency according to the obtained region to be searched, and outputting the specified word as a word characteristic to the subset.

7. The search method according to claim 6, further comprising:

(e) inputting the matrix specifying the co-occurrence relationship between the word set and the document set, performing a clustering process to the word and a document, and thereby dividing the word set and the subset composing the matrix into a plurality of subsets to generate the plurality of regions; and

(f) creating the abstract information stored in the step (a) from the plurality of regions generated by the division of the clustering process in the (e).

8. The search method according to claim 7, wherein

in the creation of (f), for each of the plurality of regions created by the division in the clustering process, at least the frequency in the region of the word included in each region is obtained, further a maximum value of the obtained frequency is specified, and the specified maximum value is set as the abstract information, and

in the calculating of (b), for each of the plurality of regions, a number of documents is obtained that compose the subset included in the region as a relationship between the information representing the subset and the plurality of regions, the obtained number of documents is compared with the maximum value of the frequency for the region, and the upper limit of the frequency is calculated according to a comparison result.

9. The search method according to claim 7, wherein

in the creation of (f), for each of the plurality of regions created by the division of the clustering process, at least a bitstream is obtained that indicates whether the word in the region is included in the document of each region, and the obtained bitstream is set as the abstract information, and;

and

in the calculating of (b), for each of the plurality of regions, a bitstream is obtained that indicates whether the document composing the subset is included in the region as the relationship between the information representing the subset and the plurality of regions, an AND operation is executed between the obtained bitstream and the bitstream obtained in the creation of (f), and the upper limit of the frequency is calculated according to an operation result.

10. The search method according to claim 7, wherein

the creation of (e) is executed for several times with types of the clustering process being changed,

in a case when the creation of (f) and (a) to (c) are executed every time the creation of (e) is executed,

at least one upper limit of the frequency of the word for each region with the common word is selected from the upper limit of the frequency of the word for each region with the common word, which is specified in (c) corresponding to the creation of each (e) according to distribution of each upper limit, and executes the output of (d) using the selected upper limit.

11. A recording medium storing a program for causing a computer to execute:

(a) a process that, when information which is created from a plurality of regions obtained by dividing a matrix representing a co-occurrence relationship between a word set and a document set and which also represents a subset included in the document set is provided, stores information which enables calculation or estimation of a frequency of a word in each of the plurality of regions as abstract information;

(b) a process that, when the information representing the subset is input, examines a relationship between the information representing the subset and the plurality of regions, refers to the abstract information for each of the plurality of regions from the obtained result, and calculates, for each of the plurality of regions, an upper limit of the frequency of the word included in each of the plurality of regions for the subset;

(c) a process that adds the upper limit of the frequency for each of the plurality of regions by each region with the common word, and specifies the obtained added value as the upper limit of the frequency of the word by each region with the common word; and

(d) a process that obtains a region to be searched according to the upper limit of the frequency of the word for each region with the common word, further specifies a specified number of words in order of higher frequency according to the obtained region to be searched, and outputs the specified word as a word characteristic to the subset.

12. The recording medium storing the program according to claim 11 for causing the computer to further execute;

(e) a process that inputs the matrix specifying the co-occurrence relationship between the word set and the document set, performs a clustering process to the word and a document, and thereby divides the word set and the subset composing the matrix into a plurality of subsets to generate the plurality of regions; and

(f) a process that creates the abstract information stored in the process of (a) from the plurality of regions generated by the division of the clustering process in the process of (e).

13. The recording medium storing the program according to claim 12, wherein

in the process of (f), for each of the plurality of regions created by the division in the clustering process, at least the frequency in the region of the word included in each region is obtained, further a maximum value of the obtained frequency is specified, and the specified maximum value is set as the abstract information, and

in the process of (b), for each of the plurality of regions, a number of documents is obtained that compose the subset included in the region as a relationship between the information representing the subset and the plurality of regions, the obtained number of documents is compared with the maximum value of the frequency for the region, and the upper limit of the frequency is calculated according to a comparison result.

14. The recording medium storing the program according to claim 13, wherein

in the process of (f), for each of the plurality of regions created by the division of the clustering process, at least a bitstream is obtained that indicates whether the word in the region is included in the document of each region, and the obtained bitstream is set as the abstract information, and;

and

in the process of (b), for each of the plurality of regions, a bitstream is obtained that indicates whether the document composing the subset is included in the region as the relationship between the information representing the subset and the plurality of regions, an AND operation is executed between the obtained bitstream and the bitstream obtained in the process of (f), and the upper limit of the frequency is calculated according to an operation result.

15. The recording medium storing the program according to claim 12, wherein

the process of (e) is executed for several times with types of the clustering process being changed,

in a case when the process of (f) and the processes of (a) to (c) are executed every time the process of (e) is executed,

at least one upper limit of the frequency of the word for each region with the common word is selected from the upper limit of the frequency of the word for each region with the common word, which is specified in the process of (c) corresponding to the process of each (e) according to distribution of each upper limit, and executes the process of (d) using the selected upper limit.

16. A search apparatus comprising:

an abstract matrix storage that, when information which is created from a plurality of regions obtained by dividing a matrix representing a co-occurrence relationship between a word set and a document set and which also represents a subset included in the document set is provided, stores information which enables calculation or estimation of a frequency of a word in each of the plurality of regions as abstract information;

a region upper limit calculation that, when the information representing the subset is input, examines a relationship between the information representing the subset and the plurality of regions, refers to the abstract information for each of the plurality of regions from the obtained result, and calculates, for each of the plurality of regions, an upper limit of the frequency of the word included in each of the plurality of regions for the subset;

a word frequency calculation that adds the upper limit of the frequency for each of the plurality of regions by each region with a common word, and specifies the obtained added value as the upper limit of the frequency of the word for each region with the common word; and

a document frequency reference that obtains a region to be searched according to the upper limit of the frequency of the word for each region with the common word, further specifies a specified number of words in order of higher frequency according to the obtained region to be searched, and outputs the specified word as a word characteristic to the subset.