HIERARCHICAL GRID FOR SPATIAL QUERYING
First Claim
1. A method comprising:
- applying a grid to a domain space to divide the domain space into cells using gridlines;
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 first query window based on the location criteria;
expanding the first query window to produce an expanded query window whose boundaries coincide with gridlines of the grid;
based on the first 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;
wherein the method is performed by one or more computing devices.
1 Assignment
0 Petitions
Accused Products
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.
10 Citations
20 Claims
-
1. A method comprising:
-
applying a grid to a domain space to divide the domain space into cells using gridlines; 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 first query window based on the location criteria; expanding the first query window to produce an expanded query window whose boundaries coincide with gridlines of the grid; based on the first 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; wherein the method is performed by one or more computing devices. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause performance of a method comprising the step of:
-
applying a grid to a domain space to divide the domain space into cells using gridlines; 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 first query window based on the location criteria; expanding the first query window to produce an expanded query window whose boundaries coincide with gridlines of the grid; based on the first 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; wherein the method is performed by one or more computing devices. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
Specification