Hierarchical grid for spatial querying

• US 9,977,789 B2
• Filed: 11/29/2011
• Issued: 05/22/2018
• Est. Priority Date: 11/29/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Zhu, Jay J., Venkateswaran, Subramanian, Trivedi, Anuj, Verma, Rupesh
• Primary Examiner(s): Herndon, Heather
• Assistant Examiner(s): Vo, Cecile
• Application Number:
  US13/306,820
• Publication Number:
  US 20130138682A1
• Time in Patent Office: 2,366 Days
• Field of Search: 707706, 707743, 707797, 707793, 707723, 707769, 7079991, 707999102, 707E17014, 707E17024, 707E1711, 707724, 370254, 701455, 701461, 701532
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Techniques are provided for improving performance of spatial queries by defining a grid that divides the domain space into cells, and then using a cell-to-item mapping to determine which items do not have to be individually evaluated against the location criteria of the spatial queries. Based on the cell to which an item belongs, the item may automatically qualify as a match, be automatically disqualified, or require item-specific evaluation. To account for items with size, the query window of a spatial query may be expanded. To limit the degree to which the query window is expanded, a plurality of grids may be established for the domain space, where each grid has differently sized cells, and items are assigned to grids based on the size of the items.

Claims

1. A method for performing a spatial query, the method comprising:

dividing a domain space into cells by applying a grid of grid lines to the domain space;

assigning a plurality of items that belong to the domain space to the cells based on the location of the items within the domain space, wherein each item of the plurality of items is assigned to a single cell;

in response to a spatial query that specifies location criteria, performing the steps of;

determining a query window based on the location criteria;

producing an expanded query window whose boundaries coincide with the gridlines of the grid by expanding the query window;

based on the query window, separating cells that fall within the expanded query window into a set of fully-covered cells and a set of partially-covered cells;

automatically adding, to a matching set for said spatial query, items assigned to cells in the set of fully-covered cells;

automatically disqualifying, from the matching set, items assigned to cells outside the expanded query window;

evaluating items assigned to cells in the set of partially-covered cells against the location criteria of the spatial query;

adding, to the matching set, items assigned to cells in the set of partially-covered cells only if the items satisfy the location criteria; and

returning the matching set;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein:

the plurality of items are items of size; and

the method further includes determining an amount by which to expand the query window in a particular dimension based, at least in part, on a maximum number of gridlines that any single item crosses, in the particular dimension, within the grid.

3. The method of claim 2, wherein each of the plurality of items is assigned to a cell based on a reference point associated with the item.

4. The method of claim 3, wherein:

the reference point located on a particular corner of each item;

determining an amount by which to expand the first query window in the particular dimension includes expanding a particular border of the first query window N+1 gridlines;

N is the maximum number of gridlines that any single item crosses in the particular dimension;

the particular border is the left border when the particular dimension is a horizontal dimension and the particular corner is on the left side of each item;

the particular border is the right border when the particular dimension is a horizontal dimension and the particular corner is on the right side of each item;

the particular border is the upper border when the particular dimension is a vertical dimension and the particular corner is on the top side of each item; and

the particular border is the bottom border when the particular dimension is a vertical dimension and the particular corner is on the bottom side of each item.

5. The method of claim 1, wherein:

the grid is a first grid of a plurality of grids that are applied to the domain space;

the plurality of grids includes a second grid that has differently sized cells than the first grid; and

the method further comprises;

assigning a another plurality of items that belong to the domain space to the cells of the second grid based on the location of the items within the domain space, wherein each item of the other plurality of items is assigned to a single cell within the second grid; and

in response to the spatial query, performing the steps of;

determining a another query window based on the location criteria;

producing another expanded query window whose boundaries coincide with gridlines of the second grid by expanding the other query window;

based on the other query window, separating cells that fall within the other expanded query window into another set of fully-covered cells and another set of partially-covered cells;

automatically adding, to the matching set for said spatial query, items assigned to cells in the other set of fully-covered cells;

automatically disqualifying, from the matching set, items assigned to cells in the second grid that are outside the other expanded query window;

evaluating items assigned to cells in the other set of partially-covered cells against the location criteria of the spatial query; and

adding, to the matching set, items assigned to cells in the other set of partially-covered cells only if the items satisfy the location criteria.

6. The method of claim 5, wherein the grid, of the plurality of grids, to which items are assigned is based, at least in part, on the size of the items.

7. The method of claim 5,

wherein cells within the first grid are smaller than cells within the second grid, and items are assigned to the second grid if the size of the items is sufficiently large to cross more than N gridlines in the first grid;

and

wherein N is a maximum grid crossing amount established for the first grid.

8. The method of claim 1, wherein spacing between gridlines within at least one dimension is not uniform.

9. The method of claim 8, wherein spacing between a first set of adjacent gridlines in the at least one dimension is established to be smaller than spacing between a second set of adjacent gridlines in the at least one dimension, based on item density between the first set of adjacent gridlines being greater than item density between the second set of adjacent gridlines.

10. The method of claim 1, wherein plurality of items includes items of a Very Large Scale Integration (VLSI) design of a circuit and the location criteria specifies a particular region within the circuit.

11. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause performance of a method for performing a spatial query, the method comprising the steps of:

dividing a domain space into cells by applying a grid of gridlines to the domain space;

assigning a plurality of items that belong to the domain space to the cells based on the location of the items within the domain space, wherein each item of the plurality of items is assigned to a single cell; and

in response to a spatial query that specifies location criteria, performing the steps of;

determining a query window based on the location criteria;

producing an expanded query window whose boundaries coincide with the gridlines of the grid by expanding the query window;

based on the query window, separating cells that fall within the expanded query window into a set of fully-covered cells and a set of partially-covered cells;

automatically adding, to a matching set for said spatial query, items assigned to cells in the set of fully-covered cells;

automatically disqualifying, from the matching set, items assigned to cells outside the expanded query window;

evaluating items assigned to cells in the set of partially-covered cells against the location criteria of the spatial query;

adding, to the matching set, items assigned to cells in the set of partially-covered cells only if the items satisfy the location criteria; and

returning the matching set;

wherein the method is performed by one or more computing devices.

12. The non-transitory computer-readable medium of claim 11, wherein:

the plurality of items are items of size; and

the method further includes determining an amount by which to expand the query window in a particular dimension based, at least in part, on a maximum number of gridlines that any single item crosses, in the particular dimension, within the grid.

13. The non-transitory computer-readable medium of claim 12, wherein each of the plurality of items is assigned to a cell based on a reference point associated with the item.

14. The non-transitory computer-readable medium of claim 13, wherein:

the reference point located on a particular corner of each item;

determining an amount by which to expand the query window in the particular dimension includes expanding a particular border of the first query window N+11 gridlines;

N is the maximum number of gridlines that any single item crosses in the particular dimension;

the particular border is the left border when the particular dimension is a horizontal dimension and the particular corner is on the left side of each item;

the particular border is the right border when the particular dimension is a horizontal dimension and the particular corner is on the right side of each item;

the particular border is the upper border when the particular dimension is a vertical dimension and the particular corner is on the top side of each item; and

the particular border is the bottom border when the particular dimension is a vertical dimension and the particular corner is on the bottom side of each item.

15. The non-transitory computer-readable medium of claim 11, wherein:

the grid is a first grid of a plurality of grids that are applied to the domain space;

the plurality of grids includes a second grid that has differently sized cells than the first grid; and

the method further comprises;

assigning a second plurality of items that belong to the domain space to the cells of the second grid based on the location of the items within the domain space, wherein each item of the second plurality of items is assigned to a single cell within the second grid; and

in response to the spatial query, performing the further steps of;

determining another query window based on the location criteria;

expanding the other query window to produce another expanded query window whose boundaries coincide with gridlines of the second grid;

based on the other query window, separating cells that fall within the other expanded query window into a second set of fully-covered cells and a second set of partially-covered cells;

automatically adding, to the matching set for said spatial query, items assigned to cells in the second set of fully-covered cells;

automatically disqualifying, from the matching set, items assigned to cells in the second grid that are outside the other expanded query window;

evaluating items assigned to cells in the second set of partially-covered cells against the location criteria of the spatial query; and

adding, to the matching set, items assigned to cells in the second set of partially-covered cells only if the items satisfy the location criteria.

16. The non-transitory computer-readable medium of claim 15, wherein the grid, of the plurality of grids, to which items are assigned is based, at least in part, on the size of the items.

17. The non-transitory computer-readable medium of claim 15,

wherein cells within the first grid are smaller than cells within the second grid, and items are assigned to the second grid if the size of the items is sufficiently large to cross more than N gridlines in the first grid;

and

wherein N is a maximum grid crossing amount established for the first grid.

18. The non-transitory computer-readable medium of claim 11, wherein spacing between gridlines within at least one dimension is not uniform.

19. The non-transitory computer-readable medium of claim 18, wherein spacing between a first set of adjacent gridlines in the at least one dimension is established to be smaller than spacing between a second set of adjacent gridlines in the at least one dimension, based on item density between the first set of adjacent gridlines being greater than item density between the second set of adjacent gridlines.

20. The non-transitory computer-readable medium of claim 11, wherein plurality of items includes items of a Very Large Scale Integration (VLSI) design of a circuit and the location criteria specifies a particular region within the circuit.