Computer executable dimension reduction and retrieval engine

• US 20050027678A1
• Filed: 07/21/2004
• Published: 02/03/2005
• Est. Priority Date: 07/30/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aono, Masaki, Kobayashi, Mei, Houle, Michael Edward
• Application Number:
  US10/896,191
• Publication Number:
  US 20050027678A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/328 Management therefor

Abstract

Provides a computer executable dimension reduction method, a program for causing a computer to execute the dimension reduction method, a dimension reduction device and a retrieval engine using the dimension reduction device. A dimension reduction device for reducing the dimension of a numerical matrix with a computer to provide a dimension reduction matrix and the information comprises a processing part for generating a dimension reduction matrix or the index data for dimension reduction using a random average matrix RAV to store the dimension reduction matrix or the index data. The processing part further comprises a shuffle vector generating part for generating a shuffle vector useful as the shuffle information, and a non-normalized basis vector generating part for generating the non-normalized basis vectors from the numerical elements of the data vector specified by the shuffle vector to store the non-normalized basis vectors.

Claims

1. ) A dimension reduction method for reducing the dimension of a numerical matrix with a computer to provide information, the method comprising:

a step of generating the shuffle information by selecting randomly a data vector stored in a database and storing said shuffle information in a memory; and

a step of reducing the dimension of said numerical matrix by the basis vectors that are made orthogonal using said shuffle information.

2. ) The dimension reduction method according to claim 1, wherein the step of generating said shuffle information comprises a step of storing an identification value of said data vector selected randomly in a memory in the selected order and a step of generating a shuffle vector, and the step of reducing said dimension comprises a step of reading the numerical elements of said data vector specified by said shuffle vector from said database, and calculating an average value for every allocated chunk to generate the non-normalized basis vectors that are stored in a memory, a step of making said non-normalized basis vectors orthogonal to generate the normalized basis vectors that are stored as a random average matrix in a memory, and a step of multiplying said random average matrix by said data vector to generate a dimension reduction matrix with reduced dimension or the index data for dimension reduction that is stored in a storing part.

3. ) The dimension reduction method according to claim 1, wherein the number of said chunks corresponds to the number of basis vectors.

4. ) The dimension reduction method according to claim 2, wherein the step of calculating said average value comprises a step of averaging the elements of said data vector for every floor (M/k) with the number of data vectors (M) and the number of basis vectors (k).

16. ) An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing dimension reduction, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect the steps of claim 1.

17. ) A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for dimension reduction, said method steps comprising the steps of claim 1.

5. ) A computer executable program for performing a dimension reduction method for reducing the dimension of a numerical matrix with a computer to provide a dimension reduction matrix or the index data for dimension reduction, said method comprising:

a step of generating the shuffle information by selecting randomly a data vector stored in a database and storing said shuffle information in a memory; and

a step of reducing the dimension of said numerical matrix by the basis vectors that are made orthogonal using said shuffle information.

6. ) The computer executable program according to claim 5, wherein the step of generating said shuffle information comprises a step of storing an identification value of said data vector selected randomly in a memory in the selected order, and the step of reducing said dimension comprises a step of reading the numerical elements of said data vector specified by said shuffle vector from said database, and calculating an average value for every allocated chunk to generate the non-normalized basis vectors that are stored in a memory, a step of making said non-normalized basis vectors orthogonal to generate the normalized basis vectors that are stored as a random average matrix in a memory, and a step of multiplying said random average matrix by said data vector to generate a dimension reduction matrix with reduced dimension or the index data for dimension reduction that is stored in a storing part.

7. ) The computer executable program according to claim 6, wherein the number of said chunks corresponds to the number of basis vectors.

8. ) The computer executable program according to claim 6, wherein the step of calculating said average value comprises a step of averaging the elements of said data vector for every floor (M/k) with the number of data vectors (M) and the number of basis vectors (k).

9. ) A dimension reduction device for reducing the dimension of a numerical matrix with a computer to provide a dimension reduction matrix or the index data for dimension reduction, said device comprising:

a processing part for generating the shuffle information by selecting randomly a data vector stored in a database to store said shuffle information in a memory; and

a processing part for generating a random average matrix with the basis vectors that are made orthogonal using said shuffle information, and generating a dimension reduction matrix or the index data for dimension reduction using said random average matrix to store said dimension reduction matrix or said index data.

10. ) The dimension reduction device according to claim 9, wherein said processing parts comprise a shuffle vector generating part for generating the shuffle information as a shuffle vector by storing an identification value of said data vector selected randomly in a memory in the selected order and a non-normalized basis vector generating part for generating the non-normalized basis vectors that are stored in a memory by reading the numerical elements of said data vector specified by said shuffle vector from said database, and calculating an average value for every allocated chunk.

11. ) The dimension reduction device according to claim 10, wherein said processing parts comprise a random average matrix generating part for generating a random average matrix with the normalized basis vectors obtained by making the non-normalized basis vectors orthogonal, and a dimension reduction data storing part for generating a dimension reduction matrix with reduced dimension or the index data for dimension reduction that is stored in a storing part by reading said random average matrix, and multiplying said random average matrix by said data vector.

12. ) A retrieval engine for enabling a computer to provide information, comprising:

a processing part for generating the shuffle information by selecting randomly a data vector stored in a database to store said shuffle information in a memory;

a processing part for generating a random average matrix with the basis vectors that are made orthogonal using said shuffle information, and generating a dimension reduction matrix using said random average matrix to store said dimension reduction matrix;

a query vector storing part for generating and storing a query vector;

an inner product calculating part for calculating an inner product between said dimension reduction matrix and said query vector; and

a retrieval result storing part for storing a score of said calculated inner product.

13. ) The retrieval engine according to claim 12, wherein said

processing parts comprise a shuffle vector generating part for generating the shuffle information as a shuffle vector by storing an identification value of said data vector selected randomly in a memory in the selected order and a non-normalized basis vector generating part for generating the non-normalized basis vectors that are stored in a memory by reading the numerical elements of said data vector specified by said shuffle vector from said database, and calculating an average value for every allocated chunk.

14. ) The retrieval engine according to claim 13, wherein said processing parts comprise a random average matrix generating part for generating a random average matrix with the normalized basis vectors obtained by making the non-normalized basis vectors orthogonal, and a dimension reduction data storing part for generating a dimension reduction matrix with reduced dimension or the index data for dimension reduction that is stored in a storing part by reading said random average matrix, and multiplying said random average matrix by said data vector.

15. ) The retrieval engine according to claim 12, wherein said data vector comprises a number vector in which a document is digitized using a keyword.

18. ) A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing functions of a dimension reduction device for reducing the dimension of a numerical matrix with a computer to provide a dimension reduction matrix or the index data for dimension reduction, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of:

a processing part for generating the shuffle information by selecting randomly a data vector stored in a database to store said shuffle information in a memory; and

a processing part for generating a random average matrix with the basis vectors that are made orthogonal using said shuffle information, and generating a dimension reduction matrix or the index data for dimension reduction using said random average matrix to store said dimension reduction matrix or said index data.

19. ) A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing functions of a retrieval engine for enabling a computer to provide information, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect the functions of:

a processing part for generating the shuffle information by selecting randomly a data vector stored in a database to store said shuffle information in a memory;

a processing part for generating a random average matrix with the basis vectors that are made orthogonal using said shuffle information, and generating a dimension reduction matrix using said random average matrix to store said dimension reduction matrix;

a query vector storing part for generating and storing a query vector;

an inner product calculating part for calculating an inner product between said dimension reduction matrix and said query vector; and

a retrieval result storing part for storing a score of said. calculated inner product.