×

HIERARCHICAL GRID FOR SPATIAL QUERYING

  • US 20130138682A1
  • Filed: 11/29/2011
  • Published: 05/30/2013
  • Est. Priority Date: 11/29/2011
  • Status: Active Grant
First Claim
Patent Images

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 all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×