US 2015/0317358 A1Published application

Methods For Query Processing Of Topological Relationships Among Complex Spatial Objects

AssigneeOracle International Corporation

InventorsYing Hu, Siva Ravada, Richard J. Anderson, Bhuvan Bamba

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

A method comprising:

receiving a query requesting a spatial relationship between a query object formed from a plurality of line segments and at least one test object;
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 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.

8 more elements

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 causes the one or more processors to perform:

receiving a query requesting a spatial relationship between a query object formed from a plurality of line segments and at least one test object;
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 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.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/754,210Filed 29 Jun 2015
Priority: 28 Feb 2013
Published: 5 Nov 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

G06F 16/245
Querying: query processing
G06F 16/2246
Indexing structures: trees, e.g. B+trees
G06F 16/284
Databases characterised by their database models, e.g. relational or object models: relational databases
G06F 16/9537
Querying, e.g. by the use of web search engines: spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Family

Application13/780,990Continuation · filed 28 Feb 2013
Application14/754,210Continuation
US 2014/0244635 A1Published application
US 9,104,770 B2Related patent
US 9,519,680 B2Related patent
US 2015/0317358 A1This patent

From the US filing history. Foreign family members aren’t listed.