Method for computing near neighbors of a query point in a databa

Details Method for computing near neighbors of a query point in a databa Method for computing near neighbors of a query point in a databa

1997-12-30

2000-11-14

Kulik, Paul V.

Data processing: database and file management or data structures

Database design

Data structure types

707 4, 707 5, G06F 1730

Patent

active

061482951

ABSTRACT:
A method for determining k nearest-neighbors to a query point in a database in which an ordering is defined for a data set P of a database, the ordering being based on l one-dimensional codes C.sub.1, . . . , C.sub.1. A single relation R is created in which R has the attributes of index-id, point-id and value. An entry (j,i,C.sub..epsilon.j (p.sub.i)) is included in relation R for each data point p.sub.i .EPSILON.P, where index-id equals j, point-id equals i, and value equals C.sub..epsilon.j (p.sub.i). A B-tree index is created based on a combination of the index-id attribute and the value attribute. A query point is received and a relation Q is created for the query point having the attributes of index-id and value. One tuple is generated in the relation Q for each j, j=1, . . . , l, where index-id equals j and value equals C.sub..epsilon.j (q). A distance d is selected. The index-id attribute for the relation R of each data point p.sub.i is compared to the index-id attribute for the relation Q of the query point. A candidate data point p.sub.i is selected when the comparison of the relation R of a data point p.sub.i to the index-id attribute for the relation Q of the query point is less than the distance d. Lower bounds are calculated for each cube of the plurality of cubes that represent a minimum distance between any point in a cube and the query point. Lastly, k candidate data points p.sub.i are selected as k nearest-neighbors to the query point.

REFERENCES:
patent: 4907276 (1990-03-01), Aldersberg
patent: 5440742 (1995-08-01), Schwanke
patent: 5579471 (1996-11-01), Barber et al.
patent: 5598559 (1997-01-01), Chaudhuri
patent: 5630121 (1997-05-01), Braden-Harder et al.
patent: 5799301 (1998-08-01), Castelli et al.
patent: 5857169 (1999-01-01), Seite
patent: 5884320 (1999-03-01), Agrawal et al.
N. Beckman et al., The R*-tree: An Efficient and Robust Access Method for Points and Rectangles, ACM 089791-365-5/90/0005/0322, pp. 322-330, 1990.
T. Brinkhoff et al., Parallel Processing of Spatial Joins Using R-trees, Institute for Computer Science, niversity of Munich, Leopoldstr. 11 B, D-80802, Munchen, Germany, date unknown.
A. Butz, Alternative Algorithm For Hilbert's Space-Filling Curve, IEEE Transactions on Computers, Apr. 1971, pp. 424-426.
A. Butz, Convergence with Hilbert's Space Filling Curve, Journal of Computer and System Sciences, 3, pp. 128-146, 1969.
A. Butz, Space Filling Curves and Mathematical Programming, Information and Control, 12, pp. 314-330, 1968.
A. Guttman, R-trees: A Dynamic Index Structure For Spatial Searching, ACM 0-89791-128-8/84/006/0047, pp. 42-57, 1984.
A. Irahim et al., Indexing and retrieving point and region objects, SPIE vol. 2670, 1996, pp. 321-336.
H.V. Jagadish, A Retrieval Technique for Similar Shapes, ACM 0-89791-425-2/91/005/0208, pp. 208-246, 1991.
K.-I. Lin et al., The TV-Tree: An Index Structure for High-Dimensional Data, VLDB Journal, 3, pp. 517-542, 1994.
D. Lomet et al., The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance, ACM Transactions on Database Systems, vol. 15, No. 4, Dec. 1990, pp. 625-658.
P. Prusinkiewicz et al., Synthesis of Space-Filling Curves On The Square Grid, Fractals in the Fundamental and Applied Sciences, H.-O. Peitgen et al. editors, Elsevier Science Publishers B.V. pp. 341-367, 1991.
H. Ralambondrainy, A conceptual version of the K-means algorithm, Pattern Recognition Letters 16, pp. 1147-1157, 1995.
J.T. Robinson, The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes, ACM-SIGMOD Conference Proceedings, Apr. 1981, pp. 10-18.
H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley Publishing Co., Inc., pp. 43-80, 1990.
H. Sagen, Space-Filling Curves, Universitext, Springer-Verlag, 1994, pp. 1-30.
T. Sellis et al., The R.sup.+ -tree: A Dynamic Index for Mult-Dimensional Objects, UMIACS-TR-87-3, CS-TR-1795, Feb. 1987.
A.P. Sistla et al., Similarity based Retrieval of Pictures Using Indices on Spatial Relationships, Proceedings of the 21st VLDB conference Zurich, Switzerland, pp. 619-629, 1995.
R.J. Stevens et al., Manipulation and presentation of Multidimensional Image Data Using the Peano Scan, IEEE Transactions on pattern Analysis and Maching Intelligence, vol. PAMI-5, No. 5, Sep. 1983, pp., 520-526.

Affiliated with

Also associated with

Rating

Method for computing near neighbors of a query point in a databa does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method for computing near neighbors of a query point in a databa, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for computing near neighbors of a query point in a databa will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2075011