Method and mechanism for performing spatial joins

Data processing: measuring – calibrating – or testing – Measurement system – Measured signal processing

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

382176, 382180, 382203, G06K 934

Patent

active

060146141

ABSTRACT:
A method and mechanism for performing a spatial join between two sets of objects employs a two-pass primary filter. The objects are decomposed into variable-sized cells no larger than a predetermined cell size and stored in respective spatial indexes. The spatial indexes include a code for the variable-size cells of the object and a code for the fixed-size supercell of the variable-size cells. The first pass can be implemented as an equijoin filtering operation using the fixed-size cell codes corresponding to the predetermined cell size, and the second pass as a join operation using the variable-size cell codes at smaller cell sizes.

REFERENCES:
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5652882 (1997-07-01), Doktor
patent: 5751852 (1998-05-01), Marimont et al.
patent: 5774579 (1998-06-01), Wang et al.
patent: 5818962 (1998-10-01), Mizukami
patent: 5884320 (1999-03-01), Agrawal et al.
H. Samet et al., "Recent Developments in Linear Quadtree-Based Geographic Information Systems", Image and Vision Computing, vol. 5, No. 3, Aug. 1987, pp. 187-197.
Michael A. Bauer, "Note: Set Operations on Linear Quadtrees", Computer Vision, Graphics, and Image Processing, vol. 29, No. 2, Feb. 1985, pp. 248-258.
Shu-Xiang Li et al., "The Quadcode and Its Arithmetic", Communications of the ACM, vol. 30, No. 7, Jul. 1987, pp. 621-626.
Marloes L. P. van Lierop, "Geometrical Transformations on Pictures Represented by Leafcodes", Computer Vision, Graphics, and Image Processing, vol. 33, No. 1, Jan. 1986, pp. 81-98.
S. K. Bhaskar, "Parallel Processing of Regions Represented by Linear Quadtrees", Computer Vision, Graphics, and Image Processing, vol. 42, No. 3, Jun. 1988, pp. 371-380.
Peng Gao et al., "Space Efficient Hierarchical Structures: Relatively Addressed Compact Quadtress for GISs", Image and Vision Computing, vol. 7, No. 3, Aug. 1989, pp. 173-177.
F.C. Holroyd et al., "Efficient Linear Quadtree Construction Algorithm", Image and Vision Computing, vol. 8, Aug. 1990, pp. 218-224.
Sotirios G. Ziavras et al., "Improved Algorithms for Translation of Pictures Represented by Leaf Codes", Image and Vision Computing, vol. 6, No. 1, Feb. 1998, pp. 13-20.
Shu-Xiang Li et al., "Adjacency Detection Using Quadcodes", Communications of the ACM, Jul. 1987, vol. 30, No. 7, pp. 627-631.
Hanan Samet, "Region Representation: Quadtrees from Boundary Codes", Communications of the ACM, vol. 23, No. 3, Mar. 1980, pp. 163-170.
Hanan Samet, "Note Region Representation: Quadtrees from Binary Arrays", Computer Graphics and Image Processing, vol. 13, No. 1, May 1980, pp. 88-93.
S.B.M. Bell et al., "Spatially Referenced Methods of Processing Raster and Vector Data", Image and Vision Computing, vol. 1, No. 4, Nov. 1983, pp. 211-220.
S. B. M. Bell et al., "Tesseral Amalgamators and Hierarchical Tessellations", Image and Vision Computing, vol. 9, No. 5, Oct. 1991, pp. 313-328.
Takashi Matsuyama et al., "A File Organization for Geographic Information Systems Based on Spatial Proximity", Computer Vision, Graphics, and Image Processing, vol. 26, No. 3, Jun. 1984, pp. 303-318.
Randal C. Nelson et al., "A Consistent Hierarchical Representation for Vector Data", Compute Graphics, vol. 20, No. 4, Aug. 1986, pp. 197-206.
D. J. Abel et al., A B(+) Tree Structure for Large Quadtrees, Computer Vision, Graphics, and Image Processing, vol. 37, No. 1, Jul. 1984, pp. 19-31.
D. J. Abel et al., "A Data Structure and Algorithm Based on a Linear Key for a Rectangle Retrieval Problem", Computer Vision, Graphics, and Image Processing, vol. 24, No. 1, Oct. 1983, pp. 1-13.
Fangju Wang, "Relational-Linear Quadtree Approach for Two-Dimensional Spatial Representation and Manipulation", IEEE Transactions on Knowledge and Data Engineering, vol. 3, No. 1, Mar. 1991, pp. 118-122.
Esen A. Ozkarahan et al., "Join Strategies Using Data Space Partitioning", New Generation Computing, vol. 6, No. 1, 1988, pp. 19-39.
Thomas Brinkhoff et al., "Approximations for a Multi-Step Processing of Spatial Joins", IGIS, 1994, pp. 25-34.
Ming-Ling Lo et al., "Spatial Joins Using Seeded Trees", SIGMOD Conferences 1994, pp. 209-220.
Ming-Ling Lo et al., "Generating Seeded Trees from Data Sets", SSD 1995, pp. 328-347.
Jignesh M. Patel et al., "Partition Based Spatial-Merge Join", SIGMOD Conference 1996, pp. 259-270.
Ming-Ling Lo et al., "Spatial Hash-Joins", SIGMOD Conference 1996, pp. 247-258.
Nick Koudas et al., "Size Separation Spatial Join", SIGMOD Conference 1997, pp. 324-335.
Xiaofang Zhou et al., "Data Partitioning for Parallel Spatial Join Processing", Advances in Spatial Databases (SSD) 1997, pp. 178-196.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

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

Rate now

     

Profile ID: LFUS-PAI-O-1469499

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.