# US 9,519,680 B2 · Methods for query processing of topological relationships among complex spatial objects

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,519,680 B2
- Document ID: US9519680B2
- Status: Granted
- Kind: B2
- Application number: 14/754,210
- Filed: 2015-06-29
- Published: 2015-11-05
- Granted: 2016-12-13
- Earliest claimed: 2013-02-28
- Assignees: Oracle International Corporation
- Applicants: Oracle International Corporation
- Inventors: Ying Hu; Siva Ravada; Richard J. Anderson; Bhuvan Bamba
- Web page: https://patentgrep.com/patent/US9519680B2

## CPC

- G06F 16/245: Query processing
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/284: {Relational databases}
- G06F 16/9537: Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
- G06V 10/457: {by analysing connectivity, e.g. edge linking, connected component analysis or slices}
- G06V 30/1983: {Syntactic or structural pattern recognition, e.g. symbolic string recognition}
- G06F 16/322: {Trees}
- G06F 16/7335: {Graphical querying, e.g. query-by-region, query-by-sketch, query-by-trajectory, GUIs for designating a person/face/object as a query predicate (end-user interface involving hot spots associated with the video H04N21/4725; end-user interface for selecting a Region of Interest H04N21/4728)}
- G06F 16/9027: {Trees}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

An optimized method of processing queries requesting a description of a spatial relationship between a test geometry and a query geometry, such as points, lines, polygons, and collections thereof, is disclosed. A first part of the method finds a first spatial relationship between a minimum bounding rectangle (MBR) of the test geometry and an In-Memory R-tree (IMR-tree) built to describe the query geometry. If the first relationship does not specify the requested description, then a second part of the method uses the IMR-tree of the query geometry to find a second spatial relationship between the test geometry itself and the query geometry. Optimizations are applied to the first part and to the second part. Optimizations in the second part depend on the test geometry.

## Claims

### Claim 1

A method comprising:
receiving a query requesting a spatial relationship between a query object and at least one test object, the query object comprising a plurality of line segments;
obtaining a minimum bounding box containing the at least one test object;
obtaining an In-Memory R-tree (IMR-tree) for accessing one or more bounding boxes of the query object, wherein each bounding box of said one or more bounding boxes contains one or more of the plurality of line segments of the query object;
determining at least one first value in a set of spatial relationship values for the at least one test object by searching the IMR-tree with the minimum bounding box of the at least one test object;
wherein the set of spatial relationship values includes one or more values that describe whether a boundary, an interior or an exterior of the at least one test object intersects a boundary, an interior, or an exterior of the query object;
determining if the spatial relationship can be resolved based on the at least one first value;
if the spatial relationship cannot be resolved based on the at least one first value:
obtaining the at least one test object;
determining at least one second value in the set of spatial relationship values for the at least one test object by searching the IMR-tree using the at least one test object;
wherein the spatial relationship can be resolved based on the set of spatial relationship values after determining the at least one second value;
wherein the method is performed by one or more computing devices.

### Claim 2 (depends on 1)

The method of claim 1, wherein the query object comprises a query line formed from one or more line segments of the plurality of line segments.

### Claim 3 (depends on 1)

The method of claim 1, wherein the query object comprises a geodetic polygon.

### Claim 4 (depends on 1)

The method of claim 1,
wherein the query object comprises a query collection comprising two or more spatial objects;
wherein a test object feature selected from the boundary, the interior, and the exterior of the at least one test object intersects the boundary of the query object if the test object feature intersects a boundary of any of the two or more spatial objects;
wherein the test object feature intersects the interior of the query object if the test object feature intersects an interior of any of the two or more spatial objects;
wherein the test object feature intersects the exterior of the query object if the test object feature intersects an exterior of each of the two or more spatial objects.

### Claim 5 (depends on 1)

The method of claim 1, wherein the at least one test object comprises a plurality of test objects arranged in an R-tree.

### Claim 6 (depends on 5)

The method of claim 5,
wherein the minimum bounding box of the at least one test object is a non-leaf minimum bounding box having one or more descendant minimum bounding boxes for one or more descendant test objects of the at least one test object; and
wherein determining the at least one first value includes recursively determining at least one first value in a set of spatial relationship values for the one or more descendant test objects by searching the IMR-tree with the one or more descendant minimum bounding boxes.

### Claim 7 (depends on 5)

The method of claim 5,
wherein the minimum bounding box of the at least one test object is a leaf minimum bounding box having four boundary edges; and
wherein determining the at least one first value in the set of spatial relationship values includes determining whether any of the four boundary edges of the leaf minimum bounding box intersects the query object.

### Claim 8 (depends on 5)

The method of claim 5,
wherein the minimum bounding box of the at least one test object is a leaf minimum bounding box having six boundary faces; and
wherein determining the at least one first value in the set of spatial relationship values includes determining whether any of the six boundary faces of the leaf minimum bounding box intersects the query object.

### Claim 9 (depends on 1)

The method of claim 1,
wherein the at least one test object comprises a single point; and
wherein determining the at least one second value in the set of spatial relationship values includes:
determining whether the single point is inside the query object,
determining whether the single point is on a line segment of the query object, and
determining whether the single point is disjoint from the query object.

### Claim 10 (depends on 1)

The method of claim 1,
wherein the at least one test object comprises is a line segment having endpoints,
wherein determining the at least one second value in the set of spatial relationship values includes:
determining whether the endpoints of the line segment are inside the query object;
determining whether the endpoints of the line segment are on a line segment of the query object, and
determining whether the line segment intersects the query object.

### Claim 11

A non-transitory computer readable medium carrying one or more sequences of instructions for processing queries of spatial objects, wherein execution of the one or more sequences of instructions by one or more processors cause:
receiving a query requesting a spatial relationship between a query object and at least one test object, the query object comprising a plurality of line segments;
obtaining a minimum bounding box containing the at least one test object; obtaining an In-Memory R-tree (IMR-tree) for accessing one or more bounding boxes of the query object, wherein each bounding box of said one or more bounding boxes contains one or more of the plurality of line segments of the query object;
determining at least one first value in a set of spatial relationship values for the at least one test object by searching the IMR-tree with the minimum bounding box of the at least one test object;
wherein the set of spatial relationship values includes one or more values that describe whether a boundary, an interior or an exterior of the at least one test object intersects a boundary, an interior, or an exterior of the query object;
determining if the spatial relationship can be resolved based on the at least one first value;
if the spatial relationship cannot be resolved based on the at least one first value:
obtaining the at least one test object;
determining at least one second value in the set of spatial relationship values for the at least one test object by searching the IMR-tree using the at least one test object;
wherein the spatial relationship can be resolved based on the set of spatial relationship values after determining the at least one second value.

### Claim 12 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the query object comprises a query line formed from one or more line segments of the plurality of line segments.

### Claim 13 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the query object comprises a geodetic polygon.

### Claim 14 (depends on 11)

The non-transitory computer readable medium of claim 11,
wherein the query object comprises a query collection comprising two or more spatial objects;
wherein a test object feature selected from the boundary, the interior, and the exterior of the at least one test object intersects the boundary of the query object if the test object feature intersects a boundary of any of the two or more spatial objects;
wherein the test object feature intersects the interior of the query object if the test object feature intersects an interior of any of the two or more spatial objects;
wherein the test object feature intersects the exterior of the query object if the test object feature intersects an exterior of each of the two or more spatial objects.

### Claim 15 (depends on 11)

The non-transitory computer readable medium of claim 11, wherein the at least one test object comprises a plurality of test objects arranged in an R-tree.

### Claim 16 (depends on 15)

The non-transitory computer readable medium of claim 15,
wherein the minimum bounding box of the at least one test object is a non-leaf minimum bounding box having one or more descendant minimum bounding boxes for one or more descendant test objects of the at least one test object; and
wherein determining the at least one first value includes recursively determining at least one first value in a set of spatial relationship values for the one or more descendant test objects by searching the IMR-tree with the one or more descendant minimum bounding boxes.

### Claim 17 (depends on 15)

The non-transitory computer readable medium of claim 15,
wherein the minimum bounding box of the at least one test object is a leaf minimum bounding box having four boundary edges; and
wherein determining the at least one first value in the set of spatial relationship values includes determining whether any of the four boundary edges of the leaf minimum bounding box intersects the query object.

### Claim 18 (depends on 15)

The non-transitory computer readable medium of claim 15,
wherein the minimum bounding box of the at least one test object is a leaf minimum bounding box having six boundary faces; and
wherein determining the at least one first value in the set of spatial relationship values includes determining whether any of the six boundary faces of the leaf minimum bounding box intersects the query object.

### Claim 19 (depends on 11)

The non-transitory computer readable medium of claim 11,
wherein the at least one test object comprises a single point; and
wherein determining the at least one second value in the set of spatial relationship values includes:
determining whether the single point is inside the query object,
determining whether the single point is on a line segment of the query object, and
determining whether the single point is disjoint from the query object.

### Claim 20 (depends on 11)

The non-transitory computer readable medium of claim 11,
wherein the at least one test object comprises is a line segment having endpoints,
wherein determining the at least one second value in the set of spatial relationship values includes:
determining whether the endpoints of the line segment are inside the query object;
determining whether the endpoints of the line segment are on a line segment of the query object, and
determining whether the line segment intersects the query object.