Data processing: database and file management or data structures – Database design – Data structure types
Patent
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.
Agrawal Rakesh
Shafer John Christopher
Black Thomas G.
Ho Ruay Lian
International Business Machines - Corporation
Tran Khanh Q.
LandOfFree
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.
Profile ID: LFUS-PAI-O-827745