Parallel spatial join index

Details Parallel spatial join index Parallel spatial join index

2001-06-11

2004-06-01

Amsbury, Wayne (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

Reexamination Certificate

active

06745198

ABSTRACT:

BACKGROUND
Databases are ubiquitous. As information is accumulated, a database inevitably emerges, both to maintain and to access the information. The vast stores of information upon which many organizations depend have, in many instances, grown unwieldy. Tools for accessing the data continue to be developed at a rapid rate.
With such demands driving the industry, the optimization of query operations is an ongoing feature of database software development. Take, for example, the plethora of types of indexing methods. Indices provide a mechanism for finding a row (also known as a tuple) of a table (also known as a relation) from possibly millions of rows. Hash indices and B-trees are two common indexing types. More recently, with the availability of spatial objects in databases, R-trees and R*-trees, are used for efficient access to the objects.
Another index, known as a join index, is a type of “precomputed” join operation between two or more tables of data. A join index is a data structure that tries to store enough information to accelerate join operations between tables of data. In practice, a join index is a distinct table including record identifiers from two or more existing tables. To compute a join, the record identifiers in the join index are sorted for efficient fetching of tuples from the tables.
Increasingly, spatial data types form part of the database data. Spatial join indices have been proposed to aid efficient spatial join formation. For example, these spatial join indices may employ a grid file, which is a point data index structure, to index the spatial join attributes. Unfortunately, the grid file limits the spatial join index to only point data rather than polygon data. Furthermore, the original spatial join index may only be used in a uni-processor environment. Thus, the known spatial join indices are unsuitable for applications such as data warehousing where parallelism is crucial for optimal performance.
SUMMARY
In accordance with the embodiments described herein, a method is disclosed in which a portion of a join index is received into a memory. The join index comprises first record identifiers from a first table and second record identifiers from a second table. In memory, the join index is sorted according to first record identifiers from the first table. The portion of the join index is resorted according to second record identifiers from the second table. Join operations are performed between first and second spatial join attributes using the resorted portion of the join index.
Other features and embodiments will become apparent from the following description, from the drawings, and from the claims.


REFERENCES:
patent: 5239663 (1993-08-01), Faudemay et al.
patent: 5666525 (1997-09-01), Ross
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5978794 (1999-11-01), Agrawal et al.
patent: 5987468 (1999-11-01), Singh et al.
patent: 6014614 (2000-01-01), Herring et al.
patent: 6032144 (2000-02-01), Srivastava et al.
patent: 6141655 (2000-10-01), Johnson et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6278994 (2001-08-01), Fuh et al.
patent: 6353826 (2002-03-01), Seputis
patent: 6496819 (2002-12-01), Bello et al.
patent: 6618720 (2003-09-01), On Au et al.
L. Arge et al., “Scalable Sweeping-Based Spatial Join”, VLDB 1998: 570-581.
N. Beckmann et al., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles”, SIGMOD Conf. 1990, pp.. 322-331.
T. Brinkhoff et al., “Efficient Processing of Spatial Joins Using R-trees”, SIGMOD Conf. 1993, pp. 237-246.
V. Gaede et al., “Multidimensional Access Methods”, Computing Surveys 30(2), 1998, pp. 170-231.
G. Graefe, “Query Evaluation Techniques for Large Databases”, ACM Comput. Surveys, 25(2):73-170, Jun. 1993.
A. Guttman, “R-Trees: A Dynamic Index Structure for Spatial Searching”, SIGMOD Conf. 1984, pp. 47-57.
P. Haas et al., “Join Algorithms for Online Aggregation”, IBM Research Report RJ10126, 1998.
P. Haas, “Techniques for Online Exploration of Large Object-Relational Datasets”, Proc. 11thIntl. Conf. Scientific and Statistical Database Management, 1999, pp. 4-12.
P. Haas et al., “Ripple Joins for Online Aggregation”, SIGMOD Conf. 1999, pp. 287-298.
I. Kamel et al., “Parallel R-trees”, SIGMOD Conf. 1992, pp. 195-204.
J. Nievergelt et al., “The Grid File: An Adaptable, Symmetric Multikey File Structure”, TODS 9(1): 38-71, 1984.
J. Patel et al., “Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation”, SIGMOD Conf. 1997, pp. 336-347.
J. Patel et al., “Clone Join and Shadow Join: Two Parallel Algorithms for Executing Spatial Join Operations”, Technical Report, University of Wisconsin, CS-TR-99-1403, Aug. 1999.
J. Patel et al., “Partition Based Spatial-Merge Join”, SIGMOD Conf. 1996, 259-270.
D. Rotem, “Spatial Join Indices”, ICDE 1991,, pp. 500-509.
M. Stonebraker et al., “The Sequoia 2000 Storage Benchmark”, SIGMOD Conf. 1993, pp. 632-645.
P. Valduriez, “Join Indices”, TODS 12(2): 218-246, 1987.

Affiliated with

Also associated with

Rating

Parallel spatial join index does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Parallel spatial join index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel spatial join index will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3334823