SYSTEM AND METHOD PROVIDING AUTOMATED MARGIN TREE ANALYSIS AND PROCESSING OF SAMPLED DATA
First Claim
1. A computer related database lookup system, comprising:
- a quantizer to form a vector having M components, M being an integer, the M components of the vector having at least one of three values (0, 1, and q); and
a component to perform a lookup in a database in accordance with the values, where q directs a backtrack on the lookup, if encountered.
2 Assignments
0 Petitions
Accused Products
Abstract
The present invention relates to a system and methodology to facilitate database processing in accordance with a plurality of various applications. In one aspect, a large database of objects is processed, wherein the objects can be represented as points in a vector space, and two or more objects are deemed ‘close’ if a Euclidean distance between the points is small. This can apply for substantially any type of object, provided a suitable distance measure can be defined. In another aspect, a ‘test’ object having a vector x, is processed to determine if there exists an object y in the database such that the distance between x and y falls below a threshold t. If several objects in the database satisfy this criteria, a list of objects can be returned, together with their corresponding distances. If no objects were to satisfy the criterion, an indication of this condition can also be provided, but in addition, the condition or information relating to the condition can be provided.
36 Citations
20 Claims
-
1. A computer related database lookup system, comprising:
-
a quantizer to form a vector having M components, M being an integer, the M components of the vector having at least one of three values (0, 1, and q); and
a component to perform a lookup in a database in accordance with the values, where q directs a backtrack on the lookup, if encountered. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A computer related database lookup method, comprising:
-
receiving a test vector x having d components;
creating a quantized vector {circumflex over (x)} that maps the d components to at least one of three values of 0, 1, and q, q denoting a database backtrack operation; and
looking up data in the database via the quantized vector {circumflex over (x)}. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A computer related lookup method to mitigate computational costs when accessing a database, comprising:
-
constructing d binary trees having a depth less than or equal to d;
computing a number of edges for the trees;
selecting the tree having at least a lowest number of edges that must be traversed, for a given x; and
employing the selected tree to mitigate computational costs when accessing the database. - View Dependent Claims (20)
-
Specification