Fast query search in large dimension database

Details Fast query search in large dimension database Fast query search in large dimension database

1997-03-24

1998-12-08

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 5, 707 6, 707100, 707101, G06F 1730

Patent

active

058484043

ABSTRACT:
A computer-implemented database search method includes arranging data points in a tree structure, with upper nodes being labeled by respective randomly selected representative data point and with the distance between each data point which is related to a first node and the label of the first node being less than the distance between the data point and the label of nodes in other branches. When a query is received, the distance between the query and the label of each node in the upper-most level is determined, and the nodes arranged in sequence, shortest distance first. Then, the process is repeated for the first "f" nodes in the sequence, and so on, until a sequence of leaves (i.e., data points having no dependent nodes or leaves) is obtained. The first "k" leaves are returned as the "k" closest database matches to the query. Alternatively, geometric information pertaining to the data points is recorded when the database is populated, and then, for query execution, nodes of data are ranked according to the geometric information as it relates to the query, with the node rankings terminated when a high bound for the geometric relationship between the query and a node is reached.

REFERENCES:
patent: 4135147 (1979-01-01), Riganati et al.
patent: 4667550 (1987-05-01), Ferguson
patent: 4799270 (1989-01-01), Kim et al.
patent: 5276895 (1994-01-01), Grondalski
patent: 5289567 (1994-02-01), Roth
patent: 5329596 (1994-07-01), Hiroshi et al.
patent: 5331554 (1994-07-01), Graham
patent: 5350303 (1994-09-01), Fox et al.
patent: 5404512 (1995-04-01), Powers
patent: 5485612 (1996-01-01), Ota et al.
patent: 5497485 (1996-03-01), Ferguson et al.
patent: 5521910 (1996-05-01), Mattews
patent: 5664174 (1997-09-01), Agrawal et al.
patent: 5701467 (1997-12-01), Freeston
patent: 5710916 (1998-01-01), Barbara
Bozkaya et al., "Distance-based indexing for high dimensional metric spaces", Sigmod Record, vol.26, No.2, p.357-368, Jun. 1997.
Berchtold, et al., "Fast nearest neighbor search in high-dimensional space", IEEE, p.209-218, Feb. 1998.
"Architecture and User Interface of Intelligent Multimedia Database System Trademark", Electrotechnical Laboratory, vol. 52, No. 7, 1988, pp. 1-20.
"Trademark: Multimedia Image Database System with Intelligent Human Interface", Toshikazu Kato, Koreaki Fujimura & Hiroyuiki Shimogaki, Systems and Computers in Japan, vol. 21, No. 11, 1990, pp. 33-46.

Affiliated with

Also associated with

Rating

Fast query search in large dimension database does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast query search in large dimension database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast query search in large dimension database will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-190405