US-20260127233-A1 - OPTIMIZED GEOSPATIAL DATA PROCESSES VIA A DATABASE SYSTEM

US20260127233A1US 20260127233 A1US20260127233 A1US 20260127233A1US-20260127233-A1

Abstract

A method executable by a processing module of a database system includes identifying a query that includes a geospatial buffer expression for a geospatial object, obtaining the geospatial object based on the geospatial buffer expression, executing a geospatial object simplification function on the geospatial object to produce a simplified geospatial object, executing an offset curve function on the simplified geospatial object to produce one or more offset curves, executing an offset curve segment loop elimination function on the one or more offset curves to produce one or more simplified offset curves, and executing a depth analysis function on the one or more simplified offset curves to produce a geospatial object buffer geography of the geospatial object, wherein the depth analysis function identifies and eliminates portions of the simplified offset curves that are located inside the geospatial object buffer geography.

Inventors

Daniel Joseph Zollers

Assignees

Ocient Holdings LLC

Dates

Publication Date: 20260507
Application Date: 20241106

Claims (20)

1 . A method comprising; identifying, by a processing module of a database system, a query that includes a geospatial buffer expression for a geospatial object; obtaining, by the processing module, the geospatial object based on the geospatial buffer expression; executing, by the processing module, a geospatial object simplification function on the geospatial object to produce a simplified geospatial object; executing, by the processing module, an offset curve function on the simplified geospatial object to produce one or more offset curves; executing, by the processing module, an offset curve segment loop elimination function on the one or more offset curves to produce one or more simplified offset curves; and executing, by the processing module, a depth analysis function on the one or more simplified offset curves to produce a geospatial object buffer geography of the geospatial object, wherein the depth analysis function identifies and eliminates portions of the one or more simplified offset curves that are located inside the geospatial object buffer geography.
2 . The method of claim 1 , wherein the executing the offset curve function comprises: identifying, by the processing module, geospatial object segments of the simplified geospatial object; traversing, by the processing module, the geospatial object segments in a first direction, wherein for each geospatial object segment of the geospatial object segments, a first geospatial object offset curve segment is generated to produce first geospatial object offset curve segments; joining, by the processing module, the first geospatial object offset curve segments to produce a first offset curve; determining, by the processing module, whether to produce a full buffer on the geospatial object; when the processing module determines to produce the full buffer: determining, by the processing module, whether the geospatial object is an open geography; and when the geospatial object is the open geography: generating, by the processing module, endpoint offsets for the geospatial object; and joining, by the processing module, the first offset curve and the endpoint offsets to produce the one or more offset curves; and when the geospatial object is not an open geography: interpreting, by the processing module, the first offset curve as the one or more offset curves; and when the processing module determines to not produce the full buffer: traversing, by the processing module, the geospatial object segments in a second direction, wherein for each geospatial object segment of the geospatial object segments, a second geospatial object offset curve segment is generated to produce second geospatial object offset curve segments; joining, by the processing module, the second geospatial object offset curve segments to produce a second offset curve; determining, by the processing module, whether the geospatial object is the open geography; and when the geospatial object is the open geography: generating, the processing module, the endpoint offsets for the geospatial object; and joining, the processing module, the first offset curve, the second offset curve, and the endpoint offsets to produce the one or more offset curves; and when the geospatial object is not the open geography: interpreting, by the processing module, the first and second offset curves as the one or more offset curves.
3 . The method of claim 2 further comprises: when a geospatial object segment of the geospatial object segments is longer than a tolerance threshold, adding, by the processing module, one or more points to the geospatial object segment to break the geospatial object segment into two or more geospatial object segments.
4 . The method of claim 1 , wherein the executing the offset curve segment loop elimination function comprises: analyzing, by the processing module, the one or more offset curves to identify one or more simplification features, wherein the one or more simplification features include one or more consecutive right turns present in the one or more offset curves; when the one or more simplification features are identified: analyzing, by the processing module, the one or more offset curves to identify one or more loop conditions; and when the one or more loop conditions are identified: eliminating, by the processing module, one or more loops indicated by the one or more loop conditions from the one or more offset curves to produce the one or more simplified offset curves; and when the one or more loop conditions are not identified: using, by the processing module, the one or more offset curves as the one or more simplified offset curves; and when the one or more simplification features are not identified: using, by the processing module, the one or more offset curves as the one or more simplified offset curves.
5 . The method of claim 4 , wherein the analyzing the one or more offset curves to identify the one or more loop conditions comprises: grouping, by the processing module, a plurality of offset curve segments and a plurality of offset curve joins of the one or more offset curves into right turn groups and no right turn groups, wherein the right turn groups include offset curve segments and offset curve joins of the plurality of offset curve segments and the plurality of offset curve joins that form right turns and the no right turn groups include offset curve segments and offset curve joins of the plurality of offset curve segments and the plurality of offset curve joins that do not form right turns; for each right turn group of the right turn groups, concatenating, by the processing module, a proceeding no right turn group of the no right turn groups and a following no right turn group of the no right turn groups with the right turn group to form one or more offset curve segment groups of the one or more offset curves; for each offset curve segment group of the one or more offset curve segment groups: identifying, by the processing module, intersection points to produce one or more offset curve segment groups with ordered intersection points; when an ordered intersection point appears both first and last in the offset curve segment group with ordered intersection points: identifying, by the processing module, the ordered intersection point as a loop condition of the one or more loop conditions; and identifying, by the processing module, the offset curve segments and offset curve joins of the offset curve segment group with ordered intersection points between the ordered intersection point as a loop of the one or more loops.
6 . The method of claim 1 , wherein the executing the depth analysis function comprises: determining, by the processing module, that the one or more simplified offset curves include one or more intersections; splitting, by the processing module, the one or more simplified offset curves into a plurality of simplified offset curve segments based on the one or more intersections; assigning, by the processing module, a current depth value to a current simplified offset curve segment of the plurality of simplified offset curve segments; analyzing, by the processing module, a next simplified offset curve segment of the plurality of simplified offset curve segments for a depth change condition between the current simplified offset curve segment and the next simplified offset curve segment; and when the depth change condition is detected: determining, by the processing module, whether the depth change condition indicates a depth increase between the current simplified offset curve segment and the next simplified offset curve segment or a depth decrease between the current simplified offset curve segment and the next simplified offset curve segment; when the depth change condition indicates the depth increase: assigning, by the processing module, an increased depth value to the next simplified offset curve segment; and when the depth change condition indicates the depth decrease: assigning, by the processing module, a decreased depth value to the next simplified offset curve segment; and when the depth change condition is not detected: maintaining, by the processing module, a current depth value for the next simplified offset curve segment; and traversing, by the processing module, the plurality of simplified offset curve segment to assign depth values to each next simplified offset curve segments of the plurality of simplified offset curve segments until each simplified offset curve segment of the plurality of simplified offset curve segments is assigned a corresponding depth value; and generating, by the processing module, the geospatial object buffer geography of the geospatial object by eliminating simplified offset curve segments of the plurality of simplified offset curve segments assigned a depth value above a depth threshold.
7 . The method of claim 6 , wherein the analyzing the next simplified offset curve segment for the depth change condition comprises: determining, by the processing module, that the current simplified offset curve segment ends with an intersection point of the one or more intersection points.
8 . The method of claim 6 further comprises: when the plurality of simplified offset curve segments are traversed in a first direction, and a next simplified offset curve segment is selected left of the current simplified offset curve: when the current offset curve segment is oriented away from the first direction from a perspective of an intersection point and the next simplified offset curve segment is oriented toward the first direction from the perspective of the intersection point, determining, by the processing module, that the depth change condition indicates the depth increase; and when the current offset curve segment is oriented toward the first direction from the perspective of the intersection point and the next offset simplified curve segment is oriented away from the first direction from the perspective of the intersection point, determining, by the processing module, that the depth change condition indicates the depth decrease.
9 . The method of claim 6 , wherein the generating the geospatial object buffer geography further comprises: selecting, by the processing module, a simplified offset curve segment assigned the depth value below the depth threshold as an initial simplified offset curve segment; starting from the initial simplified offset curve segment, traversing, by the processing module, the one or more simplified offset curves; and when an intersection point of the one or more intersections is encountered, proceeding, by the processing module, to the next simplified offset curve segment that is assigned the depth value below the threshold, such that simplified offset curve segments of the plurality of simplified offset curve segments assigned the depth value above the depth threshold are eliminated from the geospatial object buffer geography.
10 . The method of claim 1 further comprises one or more of: outputting, by the processing module, the geospatial object buffer geography to at least one node of a plurality of nodes of the database system for use in the query on a data set; storing, by the processing module, the geospatial object buffer geography to memory of the database system; and providing, by the processing module, the geospatial object buffer geography to a requester of the query.
11 . A non-transitory computer readable storage medium comprises: a first memory section that stores operational instructions that, when executed by a processing module of a database system, causes the processing module to: identify a query that includes a geospatial buffer expression for a geospatial object; and obtain the geospatial object based on the geospatial buffer expression; and a second memory section that stores operational instructions that, when executed by the processing module, causes the processing module to: execute a geospatial object simplification function on the geospatial object to produce a simplified geospatial object; execute an offset curve function on the simplified geospatial object to produce one or more offset curves; execute an offset curve segment loop elimination function on the one or more offset curves to produce one or more simplified offset curves; and execute a depth analysis function on the one or more simplified offset curves to produce a geospatial object buffer geography of the geospatial object, wherein the depth analysis function identifies and eliminates portions of the one or more simplified offset curves that are located inside the geospatial object buffer geography.
12 . The non-transitory computer readable storage medium of claim 11 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to execute the offset curve function by: identifying geospatial object segments of the simplified geospatial object; traversing the geospatial object segments in a first direction, wherein for each geospatial object segment of the geospatial object segments, a first geospatial object offset curve segment is generated to produce first geospatial object offset curve segments; joining the first geospatial object offset curve segments to produce a first offset curve; determining whether to produce a full buffer on the geospatial object; when the full buffer is determined to be produced: determine whether the geospatial object is an open geography; and when the geospatial object is the open geography: generate endpoint offsets for the geospatial object; and join the first offset curve and the endpoint offsets to produce the one or more offset curves; and when the geospatial object is not an open geography: interpret the first offset curve as the one or more offset curves; and when the full buffer is not determined to be produced: traverse the geospatial object segments in a second direction, wherein for each geospatial object segment of the geospatial object segments, a second geospatial object offset curve segment is generated to produce second geospatial object offset curve segments; join the second geospatial object offset curve segments to produce a second offset curve; determine whether the geospatial object is the open geography; and when the geospatial object is the open geography: generate the endpoint offsets for the geospatial object; and join the first offset curve, the second offset curve, and the endpoint offsets to produce the one or more offset curves; and when the geospatial object is not the open geography: interpret the first and second offset curves as the one or more offset curves.
13 . The non-transitory computer readable storage medium of claim 12 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to: when a geospatial object segment of the geospatial object segments is longer than a tolerance threshold, add one or more points to the geospatial object segment to break the geospatial object segment into two or more geospatial object segments.
14 . The non-transitory computer readable storage medium of claim 11 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to execute the offset curve segment loop elimination function by: analyzing the one or more offset curves to identify one or more simplification features, wherein the one or more simplification features include one or more consecutive right turns present in the one or more offset curves; and when the one or more simplification features are identified: analyzing the one or more offset curves to identify one or more loop conditions; and when the one or more loop conditions are identified: eliminating one or more loops indicated by the one or more loop conditions from the one or more offset curves to produce the one or more simplified offset curves; and when the one or more loop conditions are not identified: using the one or more offset curves as the one or more simplified offset curves; and when the one or more simplification features are not identified: using the one or more offset curves as the one or more simplified offset curves.
15 . The non-transitory computer readable storage medium of claim 14 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to analyze the one or more offset curves to identify the one or more loop conditions by: grouping a plurality of offset curve segments and a plurality of offset curve joins of the one or more offset curves into right turn groups and no right turn groups, wherein the right turn groups include offset curve segments and offset curve joins of the plurality of offset curve segments and the plurality of offset curve joins that form right turns and the no right turn groups include offset curve segments and offset curve joins of the plurality of offset curve segments and the plurality of offset curve joins that do not form right turns; for each right turn group of the right turn groups, concatenating a proceeding no right turn group of the no right turn groups and a following no right turn group of the no right turn groups with the right turn group to form one or more offset curve segment groups of the one or more offset curves; for each offset curve segment group of the one or more offset curve segment groups: identifying intersection points to produce one or more offset curve segment groups with ordered intersection points; when an ordered intersection point appears both first and last in the offset curve segment group with ordered intersection points: identifying the ordered intersection point as a loop condition of the one or more loop conditions; and identifying the offset curve segments and offset curve joins of the offset curve segment group with ordered intersection points between the ordered intersection point as a loop of the one or more loops.
16 . The non-transitory computer readable storage medium of claim 11 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to execute the depth analysis function by: determining that the one or more simplified offset curves include one or more intersections; splitting the one or more simplified offset curves into a plurality of simplified offset curve segments based on the one or more intersections; assigning a current depth value to a current simplified offset curve segment of the plurality of simplified offset curve segments; analyzing a next simplified offset curve segment of the plurality of simplified offset curve segments for a depth change condition between the current simplified offset curve segment and the next simplified offset curve segment; and when the depth change condition is detected: determining whether the depth change condition indicates a depth increase between the current simplified offset curve segment and the next simplified offset curve segment or a depth decrease between the current simplified offset curve segment and the next simplified offset curve segment; when the depth change condition indicates the depth increase: assigning an increased depth value to the next simplified offset curve segment; and when the depth change condition indicates the depth decrease: assigning a decreased depth value to the next simplified offset curve segment; and when the depth change condition is not detected: maintaining a current depth value for the next simplified offset curve segment; and traversing the plurality of simplified offset curve segment to assign depth values to each next simplified offset curve segments of the plurality of simplified offset curve segments until each simplified offset curve segment of the plurality of simplified offset curve segments is assigned a corresponding depth value; and generating the geospatial object buffer geography of the geospatial object by eliminating simplified offset curve segments of the plurality of simplified offset curve segments assigned a depth value above a depth threshold.
17 . The non-transitory computer readable storage medium of claim 16 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to analyze a next simplified offset curve segment for the depth change condition by: determining that the current simplified offset curve segment ends with an intersection point of the one or more intersection points.
18 . The non-transitory computer readable storage medium of claim 16 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to: when the plurality of simplified offset curve segments are traversed in a first direction, and next simplified offset curve segment is selected to left of the current simplified offset curve: when the current offset curve segment is oriented away from the first direction from a perspective of an intersection point and the next simplified offset curve segment is oriented toward the first direction from the perspective of the intersection point, determine that the depth change condition indicates the depth increase; and when the current offset curve segment is oriented toward the first direction from the perspective of the intersection point and the next simplified offset curve segment is oriented away from the first direction from the perspective of the intersection point, determine that the depth change condition indicates the depth decrease.
19 . The non-transitory computer readable storage medium of claim 16 , wherein the second memory section further stores operational instructions that, when executed by the processing module, causes the processing module to generate the geospatial object buffer geography further by: selecting a simplified offset curve segment assigned the depth value below the depth threshold as an initial simplified offset curve segment; starting from the initial simplified offset curve segment, traversing the one or more simplified offset curves; and when an intersection point of the one or more intersections is encountered, proceeding to the next simplified offset curve segment that is assigned the depth value below the threshold, such that simplified offset curve segments of the plurality of simplified offset curve segments assigned the depth value above the depth threshold are eliminated from the geospatial object buffer geography.
20 . The non-transitory computer readable storage medium of claim 11 , wherein a third memory section that stores operational instructions that, when executed by the processing module, causes the processing module to execute one or more of: outputting the geospatial object buffer geography to at least one node of a plurality of nodes of the database system for use in the query on a data set; storing the geospatial object buffer geography to memory of the database system; and providing the geospatial object buffer geography to a requester of the query.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS Not Applicable. STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT Not Applicable. INCORPORATION-BY-REFERENCE OF MATERIAL SUBMITTED ON A COMPACT DISC Not Applicable. BACKGROUND OF THE INVENTION Technical Field of the Invention The disclosed subject matter relates generally to computer networking and more particularly to a database system and operation. Description of Related Art Computing devices are known to communicate data, process data, and/or store data. Such computing devices range from wireless smart phones, laptops, tablets, personal computers (PC), work stations, and video game devices, to data centers that support millions of web searches, stock trades, or on-line purchases every day. In general, a computing device includes a central processing unit (CPU), a memory system, user input/output interfaces, peripheral device interfaces, and an interconnecting bus structure. As is further known, a computer may effectively extend its CPU by using “cloud computing” to perform one or more computing functions (e.g., a service, an application, an algorithm, an arithmetic logic function, etc.) on behalf of the computer. Further, for large services, applications, and/or functions, cloud computing may be performed by multiple cloud computing resources in a distributed manner to improve the response time for completion of the service, application, and/or function. The issuing bank validates that the card has not been reported stolen or lost, confirms whether funds/credit is available, and sends a response code back through the payment processing network to the acquiring bank as to whether the transaction is approved. Of the many applications a computer can perform, a database system is one of the largest and most complex applications. In general, a database system stores a large amount of data in a particular way for subsequent processing. In some situations, the hardware of the computer is a limiting factor regarding the speed at which a database system can process a particular function. In some other instances, the way in which the data is stored is a limiting factor regarding the speed of execution. In yet some other instances, restricted co-process options are a limiting factor regarding the speed of execution. BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING(S) FIG. 1 is a schematic block diagram of an embodiment of a large scale data processing network that includes a database system; FIG. 1A is a schematic block diagram of an embodiment of a database system; FIG. 2 is a schematic block diagram of an embodiment of an administrative sub-system; FIG. 3 is a schematic block diagram of an embodiment of a configuration sub-system; FIG. 4 is a schematic block diagram of an embodiment of a parallelized data input sub-system; FIG. 5 is a schematic block diagram of an embodiment of a parallelized query and response (Q&R) sub-system; FIG. 6 is a schematic block diagram of an embodiment of a parallelized data store, retrieve, and/or process (IO& P) sub-system; FIG. 7 is a schematic block diagram of an embodiment of a computing device; FIG. 8 is a schematic block diagram of another embodiment of a computing device; FIG. 9 is a schematic block diagram of another embodiment of a computing device; FIG. 10 is a schematic block diagram of an embodiment of a node of a computing device; FIG. 11 is a schematic block diagram of an embodiment of a node of a computing device; FIG. 12 is a schematic block diagram of an embodiment of a node of a computing device; FIG. 13 is a schematic block diagram of an embodiment of a node of a computing device; FIG. 14 is a schematic block diagram of an embodiment of operating systems of a computing device; FIGS. 15-23 are schematic block diagrams of an example of processing a table or data set for storage in the database system; FIG. 24A is a schematic block diagram of a query execution plan implemented via a plurality of nodes; FIGS. 24B-24D are schematic block diagrams of embodiments of a node that implements a query processing module; FIG. 24E is a schematic block diagram of an embodiment of a plurality of nodes that communicate via shuffle networks; FIG. 24F is a schematic block diagram of a database system communicating with an external requesting entity; FIG. 24G is a schematic block diagram of an embodiment of a query processing system; FIG. 24H is a schematic block diagram of an embodiment of a query operator execution flow, FIG. 24I is a schematic block diagram of an embodiment of a plurality of nodes that utilize query operator execution flows; FIG. 24J is a schematic block diagram of an embodiment of a query execution module that executes a query operator execution flow via a plurality of corresponding operator execution modules; FIG. 24K is a schematic block diagram of an embodiment of a plurality of database tables stored in database storage; FIG. 24L is a schematic block diagram of a query execution module that implements