Data extracting method, information processing apparatus, and recording medium

• US 20020029220A1
• Filed: 09/06/2001
• Published: 03/07/2002
• Est. Priority Date: 09/07/2000
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Kubota, Kazuto, Nakase, Akihiko, Oyanagi, Shigeru
• Granted Patent: US 6,850,936 B2
• Time in Patent Office: Days
• US Class Current: 707/101
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 2216/03 Data mining
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A data extraction method comprising: storing a plurality of objects to be processed in a memory device, each of the objects including a single set of two data entities which differ in attribute from each other, converting each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix, extracting from the matrix a submatrix which is generated by replacing rows and columns of the matrix and is dense with the objects, the submatrix being configured by a part of the matrix.

Claims

1. A data extraction method comprising:

storing a plurality of objects to be processed in a memory device, each of the objects including a single set of two data entities which differ in attribute from each other;

converting each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

extracting from the matrix a submatrix which is generated by replacing rows and columns of the matrix and is dense with the objects, the submatrix being configured by a part of the matrix.

6. A method according to claim 1, wherein one of the two data entities corresponds to a customer and the other corresponds to an item bought by the customer.

2. A data extraction method comprising:

storing a plurality of objects to be processed in a memory device, each of the objects including a single set of two data entities which differ in attribute from each other;

converting each of the processing objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

selecting one or more columns from all of the columns of the matrix based on the number and positions of the objects located in each of the columns, to obtain one or more selected columns,

selecting one or more rows from all of the rows of the matrix based on the number and positions of the objects located in each of the rows, to obtain one or more selected rows,

extracting from the matrix a submatrix which is configured by the selected columns and the selected rows, and is dense with the objects.

3. A data extraction method comprising:

storing a plurality of objects to be processed in a memory device, each of the objects including a single set of three data entities which differ in attribute from one another;

converting each of the objects stored in the memory device to an element in a 3-dimensional space including a plurality of axes each of which corresponds to the attribute, the three data entities corresponding to x-, y- and z-components in the 3-dimensional space respectively;

extracting a subspace which is generated by replacing data arrays corresponding to each axis and is dense with the objects, from the 3-dimensional space.

7. A method according to claim 3, wherein one of the three data entities corresponds to a customer and one of the other two data entities corresponds to an item bought by the customer.

4. A data extraction method comprising:

(a) storing a plurality of objects to be processed in a memory device, each of the objects including a single set of two data entities which differ in attribute from each other;

(b) converting each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

(c) selecting one row from the matrix to obtain a selected row;

(d) detecting one or more columns which cross the selected row through one of the objects, to obtain one or more detected columns;

(e) increasing one or more first counters corresponding to the one or each of the more detected columns by 1;

(f) selecting one or more columns based on values of the first counters, to obtain one or more selected columns;

(g) detecting one or more rows which cross the one or each of the more selected columns through one of the objects, to obtain one or more detected rows;

(h) increasing one or more second counters corresponding to the one or each of the more detected rows by 1;

(i) selecting one or more rows based on values of the second counters, to obtain one or more selected rows;

(j) detecting one or more columns which are cross the one or each of the more selected rows through one of the object, to obtain one or more detected columns;

(k) repeating steps (e)-(j) until the selected columns and the selected rows satisfy a given convergence condition;

(l) extracting from the matrix a submatrix which is configured by the selected columns and the selected rows when the given convergence condition is satisfied, and is dense with the objects.

8. A method according to claim 4, wherein the step (f) includes setting a first threshold value to the first counters, the first threshold value being used as a criterion when selecting one or more rows, based on at least one of a size of a temporary submatrix which is configured by the selected columns and the selected rows, and a proportion of the number of the objects located in the temporary submatrix to the size of the temporary submatrix.

9. A method according to claim 8, wherein the first threshold value is set at a value for making the size of the temporary submatrix larger than a given size and for making the proportion maximum.

10. A method according to claim 8, wherein the first threshold value is set at a value for making the proportion larger than a given value and for making the size of the temporary submatrix maximum.

11. A method according to claim 8, wherein the first threshold value is set at a value for making both of the number of the rows and the number of the columns of the temporary submatrix larger than a given value and for making the proportion maximum.

12. A method according to claim 4, wherein step (i) includes setting a second threshold value to the second counters, the second threshold value being used as a criterion when selecting one or more columns, based on at least one of a size of a temporary submatrix which is configured by the selected columns and the selected rows, and a proportion of the number of the objects located in the temporary submatrix to the size of the temporary submatrix.

13. A method according to claim 12, wherein the second threshold value is set at a value for making the size of the temporary submatrix larger than a given size and for making the proportion maximum.

14. A method according to claim 12, wherein the second threshold value is set at a value for making the proportion larger than a given value and for making the size of the temporary submatrix maximum.

15. A method according to claim 12, wherein the second threshold value is set at a value for making both of the number of the rows and the number of the columns of the temporary submatrix larger than a given values and for making the proportion maximum.

5. A data extraction method comprising:

(a) storing a plurality of objects to be processed in a memory device, each of the objects including a single set of two data entities which differ in attribute from each other;

(b) converting each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

(c) selecting one column from the matrix to obtain a selected column;

(d) detecting one or more rows which cross the selected column through one of the objects, to obtain one or more detected rows;

(e) increasing one or more first counters corresponding to the one or each of the more detected rows by 1;

(f) selecting one or more rows based on values of the first counters, to obtain one or more selected rows;

(g) detecting one or more columns which cross the one or each of the more selected rows through one of the objects, to obtain one or more detected columns;

(h) increasing one or more second counters corresponding to the one or each of the more detected columns by 1;

(i) selecting one or more columns based on values of the second counters, to obtain one or more selected columns;

(j) detecting one or more rows which are cross the one or each of the more selected columns through one of the object, to obtain one or more detected rows;

(k) repeating steps (e)-(j) until the selected rows and the selected columns satisfy a given convergence condition;

(l) extracting from the matrix a submatrix which is configured by the selected rows and the selected columns when the given convergence condition is satisfied, and is dense with the objects.

16. An information processing apparatus comprising:

a memory device configured to store a plurality of objects to be processed, each of the objects including a single set of two data entities which differ in attribute from each other;

a converter configured to convert each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

a data extraction device configured to extract from the matrix a submatrix which is generated by replacing rows and columns of the matrix and is dense with the objects, the submatrix being configured by a part of the matrix.

17. An information processing apparatus comprising:

a memory device configured to store a plurality of objects to be processed, each of the objects including a single set of two data entities which differ in attribute from each other;

a converter configured to convert each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

a first selector configured to select one or more columns from all of the columns of the matrix based on the number and positions of the objects located in each of the columns, to obtain one or more selected columns,

a second selector configured to select one or more rows from all of the columns of the matrix based on the number and positions of the objects located in each of the rows, to obtain one or more selected rows,

a data extraction device configured to extract from the matrix a submatrix which is configured by the selected columns and the selected rows, and is dense with the objects.

18. An information processing apparatus comprising:

a memory device configured to store a plurality of objects to be processed, each of the objects including a single set of two data entities which differ in attribute from each other;

a converter configured to convert each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

a plurality of first counters, each of which corresponds to each column,

a plurality of second counters, each of which corresponds to each row,

a first selector configured to select one row from the matrix to obtain a selected row;

a second selector which selects one or more columns and one or more rows beginning at the selected row to obtain one or more selected columns and one or more selected rows, by repeating a first process and a second process alternately, until the selected columns and the selected rows satisfy a given convergence condition, and

an extraction device configured to extract from the matrix a submatrix which is configured by the selected columns and the selected rows when the given convergence condition is satisfied, and is dense with the objects,

the first process detecting one or more columns which cross the selected rows including the selected row through one of the objects, to obtain one or more detected columns, increasing one or more first counters corresponding to the one or each of the more detected columns by 1, and selecting one or more columns based on values of the first counters, and

the second process detecting one or more rows which cross the selected columns through one of the objects, to obtain one or more detected rows, increasing one or more second counters corresponding to one or each of the more detected rows by 1, and selecting one or more rows based on values of the second counters.

19. A computer program stored on a computer readable medium, the computer including a memory device which stores a plurality objects to be processed, each of the objects including a single set of two data entities which differ in attribute from each other, the computer program comprising:

first program instruction means for instructing a computer processor to convert each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

second program instruction means for instructing the computer processor to extract from the matrix a submatrix which is generated by replacing the rows and the columns of the matrix and is dense with the objects.

20. A computer program stored on a computer readable medium, the computer including a memory device which stores a plurality of objects to be processed, each of the objects including a single set of two data entities which differ in attribute from each other, the computer program comprising:

first program instruction means for instructing a computer processor to convert each of the objects stored in the memory device to one of elements arranged in a matrix, by setting one of the two data entities at a row of the matrix and the other at a column of the matrix;

second program instruction means for instructing the computer processor to select one or more columns from all of the columns of the matrix based on the number and positions of the objects located in each of the columns, to obtain one or more selected columns;

third program instruction means for instructing the computer processor to select one or more rows from all of the rows of the matrix based on the number and positions of the objects located in each of the rows, to obtain one or more selected rows;

fourth program instruction means for instructing the computer processor to extract from the matrix a submatrix which is configured by the selected columns and the selected rows, and is dense with the objects.