Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2005-07-26
2005-07-26
Robinson, Greta (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06922700
ABSTRACT:
A system and method for providing similarity indexing and searching in multi-dimensional databases. In one aspect, given a set of data points in a multidimensional space, the values of the data points on each dimension are partitioned into a plurality of grids, wherein each grid is assigned a grid value. Given a target data point, similarity candidates (i.e., data points that are similar to the target data point) are identified based on matching grid values. An inverted grid index comprising an index on the data points falling into each grid of each dimension is utilized to identify similarity candidates. A similarity selection process is employed to select the closest identified similarity candidates for output, which utilizes a similarity function to measure the closeness of each identified similarity candidate to the target data point. A preferred similarity function is one that considers a subset of the dimensions in which a point falls within a similar grid of the target point. In addition, a correlation effect among the grids in different dimensions may be a factor captured in the similarity function.
REFERENCES:
patent: 4615496 (1986-10-01), Pinson
patent: 5396418 (1995-03-01), Heuscher
patent: 5675819 (1997-10-01), Schuetze
patent: 5689585 (1997-11-01), Bloomberg et al.
patent: 5754939 (1998-05-01), Herz et al.
patent: 5870752 (1999-02-01), Gibbons et al.
patent: 5905769 (1999-05-01), Lee et al.
patent: 5963739 (1999-10-01), Homeier
patent: 5966131 (1999-10-01), Marks
patent: 5990871 (1999-11-01), Adams et al.
patent: 6081269 (2000-06-01), Quarendon
patent: 6085095 (2000-07-01), Collmann
patent: 6161105 (2000-12-01), Keighan et al.
patent: 6236982 (2001-05-01), Mahajan et al.
patent: 6337692 (2002-01-01), Rai et al.
patent: 6424967 (2002-07-01), Johnson et al.
Aggarwal Charu Chandra
Yu Philip Shi-lung
DeRosa Frank V.
Dodds, Jr. Harold E.
F. Chau & Associates LLC
International Business Machines - Corporation
Robinson Greta
LandOfFree
System and method for similarity indexing and searching in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for similarity indexing and searching in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for similarity indexing and searching in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3396534