Efficient point-in-polygon indexing technique for processing queries over geographic data sets

• US 10,026,204 B2
• Filed: 01/27/2015
• Issued: 07/17/2018
• Est. Priority Date: 01/27/2015
• Status: Active Grant

• Current Assignee: Splunk Inc.
• Original Assignee: Splunk Inc.
• Inventors: Hendrey, Geoffrey R.
• Primary Examiner(s): Demeter, Hilina K
• Application Number:
  US14/606,396
• Publication Number:
  US 20160217597A1
• Time in Patent Office: 1,267 Days
• Field of Search: None
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A system that displays geographic data is disclosed. During operation, the system receives a query to be processed, wherein the query is associated with a set of geographic regions. Next, the system uses a late-binding schema generated from the query to retrieve a set of data points from a set of events containing previously gathered data. Then, for each data point in a set of data points, the system identifies zero or more geographic regions in the set of geographic regions that the data point falls into. Finally, the system displays the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon.

Claims

1. A computer-implemented method for displaying geographic data, comprising:

receiving a query to be processed, wherein the query is associated with a set of geographic regions;

using a late-binding schema generated from the query to retrieve a set of data points from a set of events containing previously gathered raw machine data and corresponding timestamps, the late-binding schema including an extraction rule to apply to the set of events to extract the set of data points;

for each data point in the set of data points, identifying zero or more geographic regions in the set of geographic regions that the data point falls into using an index of open line segments that correspond to the set of geographic regions and that project onto a reference line that is separate from any borders of the geographic regions; and

causing display of the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon.

2. The computer-implemented method of claim 1, wherein prior to receiving the query, the method further comprises:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;

projecting rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index; and

for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval in the index.

3. The computer-implemented method of claim 1, wherein prior to receiving the query, the method further comprises, obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment, projecting rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index;

and

for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval in the index; and

wherein for each data point in the set of data points, identifying the zero or more polygons that define geographic regions that the data point falls into includes,

identifying a relevant interval on the reference line that the data point projects onto,

performing a crossing number (CN) operation by counting a number of intersections between a ray projected from the data point and open line segments, the number of intersections being determined using the open line segments stored in the index and associated with the relevant intervals, to identify zero or more polygons that the data point falls into; and

incrementing a count for each polygon that the data point falls into.

4. The computer-implemented method of claim 2, wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line.

5. The computer-implemented method of claim 3,

wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line;

and

wherein identifying a relevant interval for a data point includes obtaining a list of open intervals for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

6. The computer-implemented method of claim 1, wherein causing display of the set of geographic regions includes causing display of a choropleth map wherein each geographic region is shaded, patterned or colored in proportion to a number of data points that fall into the geographic region.

7. The computer-implemented method of claim 1, wherein the reference line is an X coordinate axis.

8. The computer-implemented method of claim 1, wherein the reference line is a Y coordinate axis.

9. The computer-implemented method of claim 1, wherein the query is received from a user through a user interface.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for displaying geographic data, the method comprising:

receiving a query to be processed, wherein the query is associated with a set of geographic regions;

using a late-binding schema generated from the query to retrieve a set of data points from a set of events containing previously gathered raw machine data and corresponding timestamps, the late-binding schema including an extraction rule to apply to the set of events to extract the set of data points;

for each data point in the set of data points, identifying zero or more geographic regions in the set of geographic regions that the data point falls into using an index of open line segments that correspond to the set of geographic regions and that project onto a reference line that is separate from any borders of the geographic regions; and

causing display of the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon.

11. The non-transitory computer-readable storage medium of claim 10, wherein prior to receiving the query, the method further comprises:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;

projecting rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index; and

for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval in the index.

12. The non-transitory computer-readable storage medium of claim 10, wherein prior to receiving the query, the method further comprises:

obtaining a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;

projecting rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and storing the intersection points in the index; and

for each interval between pairs of consecutive intersection points on the reference line, keeping track of open line segments that project onto the interval in the index; and

wherein for each data point in the set of data points, the method further comprises identifying the zero or more polygons that define geographic regions that the data point falls into by;

identifying a relevant interval on the reference line that the data point projects onto;

performing a crossing number (CN) operation by counting a number of intersections between a ray projected from the data point and open line segments the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval to identify zero or more polygons that the data point falls into, and incrementing a count for each polygon that the data point falls into.

13. The non-transitory computer-readable storage medium of claim 11, wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line.

14. The non-transitory computer-readable storage medium of claim 12,

wherein keeping track of the open line segments that project onto the intervals includes maintaining a list of open line segments for every nth interval on the reference line;

and

wherein identifying a relevant interval for a data point includes obtaining a list of open intervals for a nearest nth interval on the reference line, and adjusting the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

15. The non-transitory computer-readable storage medium of claim 10, wherein causing display of the set of geographic regions includes causing display of a choropleth map wherein each geographic region is shaded, patterned or colored in proportion to a number of data points that fall into the geographic region.

16. The non-transitory computer-readable storage medium of claim 10, wherein the reference line an X coordinate axis.

17. The non-transitory computer-readable storage medium of claim 10, wherein the reference line is a Y coordinate axis.

18. The non-transitory computer-readable storage medium of claim 10, wherein the query is received from a user through a user interface.

19. A system that displays geographic data, comprising:

at least one processor and at least one associated memory; and

a query-processing mechanism that executes on the at least one processor and is configured to;

receive a query to be processed, wherein the query is associated with a set of geographic regions;

use a late-binding schema generated from the query to retrieve a set of data points from a set of events containing previously gathered raw machine data and corresponding timestamps, the late-binding schema including an extraction rule to apply to the set of events to extract the set of data points;

for each data point in the set of data points, identify zero or more geographic regions in the set of geographic regions that the data point falls into using an index of open line segments that correspond to the set of geographic regions and that project onto a reference line that is separate from any borders of the geographic regions; and

cause display of the set of geographic regions, wherein each polygon that defines a geographic region is marked to indicate a number of data points that fall into the polygon.

20. The system of claim 19, wherein prior to receiving the query, the query-processing mechanism is further configured to:

obtain a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;

project rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and store the intersection points in the index; and

for each interval between pairs of consecutive intersection points on the reference line, keep track of open line segments that project onto the interval in the index.

21. The system of claim 19,

wherein prior to receiving the query, the query-processing mechanism is further configured to,

obtain a set of polygons that define the set of geographic regions, wherein each polygon comprises line segments that define a border of the polygon, and wherein each line segment is defined by coordinates for two endpoints of the line segment;

project rays from the endpoints of the line segments of the set of polygons onto the reference line separate from the line segments of the set of polygons, wherein the rays are projected in a direction orthogonal to the reference line to form intersection points with the reference line, and store the intersection points in the index; and

for each interval between pairs of consecutive intersection points on the reference line, keep track of open line segments that project onto the interval in the index; and

wherein for each data point in the set of data points, while identifying the zero or more polygons that define geographic regions that the data point falls into, the query-processing mechanism is configured to;

identify a relevant interval on the reference line that the data point projects onto;

perform a crossing number (CN) operation by counting a number of intersections between a ray projected from the data point and open line segments, the number of intersections being determined using the open line segments stored in the index and associated with the relevant interval to identify zero or more polygons that the data point falls into; and

increment a count for each polygon that the data point falls into.

22. The system of claim 20, wherein while keeping track of the open line segments that project onto the intervals, the query-processing mechanism is configured to maintain a list of open line segments for every nth interval on the reference line.

23. The system of claim 21,

wherein while keeping track of the open line segments that project onto the intervals, the query-processing mechanism is configured to maintain a list of open line segments for every nth interval on the reference line;

and

wherein while identifying a relevant interval for a data point, the query-processing mechanism is configured to;

obtain a list of open intervals for a nearest nth interval on the reference line; and

adjust the list to account for intervening line segment openings and closings associated with intersection points located between the nearest nth interval and the relevant interval on the reference line to produce a list of open intervals for the relevant interval.

24. The system of claim 19, wherein while causing display of the set of geographic regions, the query-processing mechanism is configured to cause display of a choropleth map wherein each geographic region is shaded, patterned or colored in proportion to a number of data points that fall into the geographic region.

25. The system of claim 19, wherein the reference line is an X coordinate axis.

26. The system of claim 19, wherein the reference line is a Y coordinate axis.

27. The system of claim 19, wherein the query is received from a user through a user interface.