×

Vector index preparing method, similar vector searching method, and apparatuses for the methods

  • US 20020178158A1
  • Filed: 08/21/2001
  • Published: 11/28/2002
  • Est. Priority Date: 12/21/1999
  • Status: Active Grant
First Claim
Patent Images

1. A method of preparing a mechanically searchable index with respect to a vector database in which a finite number of sets each including at least N-dimensional real vector and an identification number of the vector are registered as vector data, said method comprising:

  • a first step of vector index preparation of dividing N components into m sets in a predetermined method with respect to the N-dimensional real vector V of each vector data in said vector database, preparing m partial vectors v1 to vm, subsequently tabulating a distribution of a norm of the partial vector vk (k=1 to m), preparing a norm division table in which a norm range of a predetermined D type norm division is determined, calculating a region number d to which said partial vector vk belongs in accordance with predetermined D region center vectors p1 to pD, tabulating a distribution of a cosine (vk·

    pd)/(|Vk|*|pd|) of an angle formed by said partial vector vk and the region center vector pd as a declination distribution, and preparing a declination division table in which a declination range of the predetermined C type declination division is recorded;

    a second step of the vector index preparation of dividing N components into m sets in the same method as said first step with respect to the N-dimensional real vector V of each vector data in said vector database, preparing m partial vectors v1 to vm, referring to said norm division table to calculate a number r of the norm division to which the norm of said partial vector vb belongs with respect to the partial vector vb (b=1 to m) for the partial space number b, calculating the region number d to which said partial vector vb belongs in accordance with the predetermined D region center vectors pl to pD in the same method as said first step, calculating a declination (vb·

    pd)/(|vb|*|pd|) as a cosine of an angle formed by said partial vector vb and the region center vector pd indicating a center direction of the region of said region number d, referring to said declination division table, calculating a number c of the belonging declination division, and calculating index registration data to be registered in a vector index from said partial space number b, said region number d, said declination division number c, said norm division number r, the component of said partial vector vb, and the identification number i; and

    a third step of the vector index preparation of constituting the vector index such that the identification number and the component of each partial vector can be searched using a set of the partial space number b, the region number d, the declination division number c and a norm division number range [r1, r2] as a key from said norm division table, said declination division table, and said index registration data, and such that the vector component of each vector data can be searched with the identification number of the vector component.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×