Method and system for performing proximity joins on high-dimensi

Details Method and system for performing proximity joins on high-dimensi Method and system for performing proximity joins on high-dimensi

1997-08-20

1999-03-16

Black, Thomas G.

Data processing: database and file management or data structures

Database design

Data structure types

707 2, 707100, G06F 1730

Patent

active

058843205

ABSTRACT:
A method and system for performing spatial proximity joins on high-dimensional points representing data objects of a database in parallel in a multiprocessor system. The method comprises the steps of: partitioning the data points among the processors; creating index structures for the data points of the processors in parallel; assigning the join operations to the processors using the index structures; and simultaneously redistributing and joining the data points in the processors in parallel based on a predetermined joining condition. An efficient data structure, .epsilon.-K-D-B tree, is used to provide fast access to the high-dimensional points and to minimize system storage requirements. The invention achieves fast response time and requires minimum storage space by having structurally identical indices among the processors, assigning workload based on the join costs, and redistributing the data points among the processors while joining the data whenever possible.

REFERENCES:
patent: 5121494 (1992-06-01), Dias et al.
patent: 5345585 (1994-09-01), Iyer et al.
patent: 5404510 (1995-04-01), Smith et al.
patent: 5412806 (1995-05-01), Du et al.
patent: 5423035 (1995-06-01), DePrez
patent: 5542073 (1996-07-01), Schiefer et al.
T. Brinkoff et al., "Parallel Processing of Spatial Joins Using R-Trees", In Proc. of 12th Int'l Conference on Data Engineering, New Orleans, USA, Feb. 1996.
T. Brinkoff et al., "Efficient Processing of Spatial Joins Using R-trees", In Proc. of the ACM-SIGMOD Conference on Management of Data, Washington, D.C., May 1993.
E. Hoel et al., "Algorithms for Data-Parallel Spatial Operations", Technical Report CS-TR-3230, University of Maryland, Feb. 1994.
R. Agrawal et al., "Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases", Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995, pp. 490-501.
N. Beckmann et al., "The R*-tree: An Efficient and Robust Access method for Points and Rectangles", ACM, 1990, p.. 322-331.
D.J. Dewitt et al., "The Gamma Database Machine Project", IEEE Transactions on Data and Knowledge Engineering, vol. 2, No. 1, Mar. 1990, pp. 44-63.
O. Gunther, "Efficient Computation of Spatial Joins", Proceedings of the 9th International Conference on Data Engineering, Vienna, Austria, 1993, pp.1-27.
A. Guttman, "R-trees: A Dynamic Index Structure for Spatial Searching", ACM, 1984, pp. 47-57.
H.V. Jagadish, "A Retrieval Technique for Similar Shapes", ACM, 1991, pp. 208-217.
M. L. Lo et al., "Spatial Joins Using Seeded Trees", Presented at SIGMOD 94, Minneapolis, MN, may 1994, ACM, 1994, pp. 209-220.
"MPI: A Message-passing Interface Standard", Chapter 1, Unversity of Tennessee, Knoxville, Tennessee, May 5, 1994, pp. 1-14.
J. Nievergelt et al., "The Grid File: An Adaptable, Symmetric Multikey File Structure", ACM, 1984, pp. 108-124.
J.M. Patel et al., "Partition Based Spatial-Merge Join", SIGMOD 1996, pp. 1-12.
J.T. Robinson, "The K-D-B*-Tree: A Search Structure for Large Multidimessional Dynamic Indexes", ACM, 1981, pp. 10-18.
T. Sellis et al., "The R*-Tree: A Dynamic Index for Multi-dimensional Objects", Technical Report UMIACS-TR-87-3, CS-TR-1795, University of Maryland, Feb. 1987, pp. 1-24.

Affiliated with

Also associated with

Rating

Method and system for performing proximity joins on high-dimensi 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 and system for performing proximity joins on high-dimensi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing proximity joins on high-dimensi will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-827745