Query pruning using interior rectangles in an R-tree index

Details Query pruning using interior rectangles in an R-tree index Query pruning using interior rectangles in an R-tree index

2006-07-18

2006-07-18

Le, Uyen (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

07080065

ABSTRACT:
To determine relationships among objects represented in a database at least one interior rectangle lying entirely within a first geometric shape is define. A minimum bounding area for the first geometry and a minimum bounding area for a second geometry are defined and compared with one another to determine if the second geometry fulfills a primary filter condition of an interaction between the first and second geometries. Based on the fulfillment of the primary condition by the second geometry, it is determined whether an intermediate filter condition of interaction between the first and second geometries is fulfilled by analyzing the distribution of the second geometry with respect to at least one interior rectangle within the first geometry. It is determined whether the second geometry fulfills a secondary filter condition by comparing the second geometry with the first geometry if the second geometry fulfills the primary filter condition.

REFERENCES:
patent: 5428744 (1995-06-01), Webb et al.
patent: 5710916 (1998-01-01), Barbara et al.
patent: 5963956 (1999-10-01), Smartt
patent: 5988853 (1999-11-01), Kim et al.
patent: 6084595 (2000-07-01), Bach et al.
patent: 6115717 (2000-09-01), Mehrotra et al.
patent: 6148295 (2000-11-01), Megiddo et al.
patent: 6154746 (2000-11-01), Berchtold et al.
patent: 6252605 (2001-06-01), Beesley et al.
patent: 6263334 (2001-07-01), Fayyad et al.
patent: 6308177 (2001-10-01), Israni et al.
patent: 6438269 (2002-08-01), Kim et al.
Kim et al “Development of multi-step filtering processor”, IEEE 1999 pp. 169-176.
Silva et al “An exact interactive time visibility ordering algorithm for polyhedral cell complexes”, IEEE 1998, pp. 87-94.
P. Fischer et al., Computing a Maximum Axis-Aligned Rectangle in a Convex Polygon, Information Processing Letters 51 (1994) 189-193.
R. Kothuri et al, Efficient Processing of Large Spatial Queries Using Interior Approximations, Advances in Spacial and Temporal Databases, Lecture Notes in Computer Science, 2121, pp. 404-424, Redondo Beach CA, Jul. 2001.
H. Alt et al., Computing the Largest Inscribed Isothetic Rectangle, pp. 1-8, Proc. 7thCanadian Conference Computational Geometry, Universit's Laval, Qu'ebec, Aug. 1995.
K. Kanth et al., Indexing Medium-Dimensionality Data in Oracle, Proc. of ACM SIGMOND Intl. Conference on Management of Data, pp. 521-522, Jun. 1999.

Affiliated with

Also associated with

Rating

Query pruning using interior rectangles in an R-tree 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 Query pruning using interior rectangles in an R-tree index, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Query pruning using interior rectangles in an R-tree index will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3560188