Systems and methods for using tiled data

Patent metadata

Field	Value
Publication number	US-10895946-B2
Application number	US-201715666368-A
Country	US
Kind code	B2
Filing date	Aug 1, 2017
Priority date	May 30, 2017
Publication date	Jan 19, 2021
Grant date	Jan 19, 2021

Abstract

Systems, methods, and non-transitory computer readable media are provided for using tiled data. An information request for an area may be received. Information for the area may be accessed. The information for the area may be stored in a tree structure such that the information is subdivided into one or more levels of tiles. Individual tiles may correspond to a portion of the area. One or more tiles may include precomputed information for the corresponding portion(s) of the area. A response to the information request may be determined based on the precomputed information.

First claim

The invention claimed is:

1. A system comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the system to perform:
receiving an information request for a geographical area, the information request being associated with a particular type of analysis;
accessing information for the area, the information stored in a tree structure such that the information is subdivided into one or more levels of tiles, wherein one or more of the tiles include precomputed information for one or more portions of the area corresponding to the one or more of the tiles;
determining a response to the information request, the determining the response to the information request including:
determining that a first tile does not include first precomputed information for a first portion of the area corresponding to the first tile;
recursively determining the first precomputed information based on the information subdivided in sub-tiles of the first tile in response to determining that the first tile does not include the first precomputed information;
merging at least a portion of the precomputed information of the one or more tiles with the recursively determined first precomputed information, thereby updating the precomputed information for the one or more portions of the area corresponding to the one or more of the tiles;
caching the recursively determined first precomputed information based at least in part on a frequency of receipt of the information request;
determining that a particular sub-tile of the sub-tiles of the first tile includes null data for a portion of the area corresponding to the particular sub-tile;
associating a pointer with the particular sub-tile wherein the pointer points to a null data set that is shared with one or more other tiles or sub-tiles;
generating, in response to the merging at least a portion of the precomputed information of the one or more tiles with the recursively determined first precomputed information and based on the type of the analysis, a histogram for the area, the histogram presenting statistical information regarding one or more objects within the area; and
displaying, based on the recursively determined first precomputed information, an interface including at least one tile of the levels of tiles and the histogram.

2. The system of claim 1 , wherein the information is subdivided based on a quadtree structure.

3. The system of claim 1 , wherein the information request for the area is received through a user interface, the user interface enabling a user selection of at least one tile of the one or more tiles.

4. The system of claim 3 , wherein the user interface further enables changes in zoom levels, individual zoom levels of the zoom levels corresponding to individual levels of tiles.

5. The system of claim 3 , wherein a level of the one or more tiles used to determine the precomputed information responsive to the information request is different from a level of the one or more tiles corresponding to the user selection of one or more of the tiles corresponding to the area.

6. The system of claim 1 , wherein the one or more tiles is a plurality of tiles, and wherein the system is further caused to perform:
determining that information within a second tile of the plurality of tiles has changed since the precomputed information was computed;
marking the second tile as a dirty tile; and
recursively rebuilding the plurality of tiles responsive at least in part to receiving the information request.

7. The system of claim 6 , wherein the system is further caused to perform:
automatically rebuilding the second tile marked as the dirty tile based at least in part on a historical frequency of the information request.

8. The system of claim 1 , wherein determining the response to the information request further comprises:
determining that the precomputed information of the one or more tiles is overlapping precomputed information that is not directly responsive to the information request; and
performing a logical analysis of the overlapping precomputed information to determine information that is directly responsive to the information request.

9. A method implemented by a computing system including one or more processors and storage media storing machine-readable instructions, wherein the method is performed using the one or more processors, the method comprising:
receiving an information request for a geographical area, the information request being associated with a particular type of analysis;
accessing information for the area, the information stored in a tree structure such that the information is subdivided into one or more levels of tiles, wherein one or more of the tiles include precomputed information for one or more portions of the area corresponding to the one or more of the tiles;
determining a response to the information request, the determining the response to the information request including:
determining that a first tile does not include first precomputed information for a first portion of the area corresponding to the first tile;
recursively determining the first precomputed information based on the information subdivided in sub-tiles of the first tile in response to determining that the first tile does not include the first precomputed information;
merging at least a portion of the precomputed information of the one or more tiles with the recursively determined first precomputed information, thereby updating the precomputed information for the one or more portions of the area corresponding to the one or more of the tiles;
caching the recursively determined first precomputed information based at least in part on a frequency of receipt of the information request;
determining that a particular sub-tile of the sub-tiles of the first tile includes null data for a portion of the area corresponding to the particular sub-tile;
associating a pointer with the particular sub-tile wherein the pointer points to a null data set that is shared with one or more other tiles or sub-tiles;
generating, in response to the merging at least a portion of the precomputed information of the one or more tiles with the recursively determined first precomputed information and based on the type of the analysis, a histogram for the area, the histogram presenting statistical information regarding one or more objects within the area; and
displaying, based on the recursively determined first precomputed information, an interface including at least one tile of the levels of tiles and the histogram.

10. The method of claim 9 , wherein the information is subdivided based on a quadtree structure.

11. The method of claim 9 , wherein the information request for the area is received through a user interface, the user interface enabling a user selection of at least one tile of the one or more tiles.

12. The method of claim 11 , wherein the user interface further enables changes in zoom levels, individual zoom levels of the zoom levels corresponding to individual levels of tiles.

13. The method of claim 9 , wherein the one or more tiles is a plurality of tiles, and wherein determining the response to the information request further comprises:
determining that information within a second tile of the plurality of tiles has changed since the precomputed information was computed;
marking the second tile as a dirty tile; and
recursively rebuilding the plurality of tiles responsive at least in part to receiving the information request.

14. The method of claim 13 , further comprising automatically rebuilding the second tile marked as the dirty ti

Assignees

• Palantir Technologies Inc

Inventors

• Wilczynski Peter
• Cervelli Daniel
• Freiberg Stephen

Classifications

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/322

  Trees · CPC title

• G06F2203/04806

  Zoom, i.e. interaction techniques or interactors for controlling the zooming operation · CPC title

• G06F3/0481 Primary

  based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance · CPC title

• G06F3/04842

  Selection of displayed objects or displayed text elements (G06F3/0482 takes precedence) · CPC title