MATCH_GRAPH function
can be called either within a SELECT statement as a table function or within
an EXECUTE FUNCTION call.
Parameters
GRAPH
GRAPH
Name of the graph to match
SAMPLE_POINTS
SAMPLE_POINTS
Sample points used to match an underlying geospatial graph specified using the SQL
INPUT_TABLE or
INPUT_TABLES function. Sample points are specified as identifiers,
which are grouped into combinations.The input can be either the name of a table with appropriately named columns; or a query, to
use specific columns or other SQL features).
SOLVE_METHOD
SOLVE_METHOD
The type of solve method to use for the operation; review Match Identifier Combinations for more
information.
| Solver | Description | CPU Parallel |
|---|---|---|
MARKOV_CHAIN | Matches sample points to the graph using the Hidden Markov Model (HMM)-based method, which conducts a range-tree closest-edge search to find the best combinations of possible road segments for each sample point to create the best route. The route is secured one point at a time, so the prediction is corrected after each point. This solution type is the most accurate, but also the most computationally intensive. | X |
MATCH_BATCH_SOLVES | Matches each provided sample source and destination pair using the shortest path between the points. | X |
MATCH_CHARGING_STATIONS | Matches a given sample source and destination pair to the optimal recharging stations along the route (for EVs). | X |
MATCH_CLUSTERS | Matches the graph nodes with a cluster index using the Louvain clustering algorithm. Parallel running of this solver is experimental and can be invoked with the parallel_clustering option. | X* |
MATCH_LOOPS | Matches closed loops (Eulerian paths) originating and ending at each graph node between min and max hops (levels). | X |
MATCH_OD_PAIRS | Matches sample points to find the most probable path between origin and destination (OD) pairs with given cost constraints. | X |
MATCH_SIMILARITY | Computes the Jaccard similarity between vertex pairs and N-level intersections within M hops. | X |
MATCH_SUPPLY_DEMAND | Matches sample generic supply depots to generic demand points using abstract transportation (referred to as trucks). Each route is determined by a truck’s ability (size) to service demand at each demand point. | X |
SOLUTION_TABLE
SOLUTION_TABLE
Only applicable when using
EXECUTE FUNCTION syntax. Name of the table to store the solution
in [schema_name.]table_name format, using standard
name resolution rules and meeting
table naming criteriaOPTIONS
OPTIONS
Optional indicator that a comma-delimited list of connection option/value assignments will follow.
| Option | Description |
|---|---|
aggregated_output | For the MATCH_SUPPLY_DEMAND solver only. When set to true (default), each record in the output table shows a particular supplier’s scheduled cumulative round-trip path (MULTILINESTRING) and the corresponding aggregated cost. Otherwise, each record shows a single scheduled supplier route (LINESTRING) towards a particular demand site with its corresponding cost. |
batch_tsm_mode | For the MATCH_SUPPLY_DEMAND solver only. If set to true (non-default), each supplier is limited to drop off 1 unit of supply at each demand site visited per trip, in order to model the traveling salesman problem. |
chain_width | For the MARKOV_CHAIN solver only. Length of the sample points lookahead window within the Markov kernel; the larger the number, the more accurate the solution. The default value is 9. |
charging_candidates | For the MATCH_CHARGING_STATIONS solver only. Solver searches for this many stations closest to each base charging location found by capacity. The default value is 10. |
charging_capacity | For the MATCH_CHARGING_STATIONS solver only. The maximum charging capacity of an EV (distance in meters or time in seconds, depending on the unit of the graph weights). The default value is 300000. |
charging_penalty | For the MATCH_CHARGING_STATIONS solver only. The penalty for fully charging. The default value is 30000. |
cluster_quality_metric | For the MATCH_CLUSTERS solver only. The quality metric for Louvain modularity optimization solver. |
destination | Optional WKT ending point from SAMPLE_POINTS for the solver. The default behavior for the endpoint is to use time to determine the destination point. The default value is POINT NULL. |
enable_reuse | For the MATCH_SUPPLY_DEMAND solver only. If set to true (non-default), all suppliers can be scheduled for additional rounds of supply drop-off from their originating depots. |
filter_folding_paths | For the MARKOV_CHAIN solver only. When set to true (non-default), the paths per sequence combination is checked for folding over patterns and can significantly increase the execution time depending on the chain width and the number of GPS samples. |
gps_noise | GPS noise value (in meters) to remove redundant sample points. Use -1 to disable noise reduction. The default value (5.0) accounts for 95% of point variation (±5 meters) |
intersection_penalty | This will add an additional weight over the edges labeled as intersection if the add_turn option was invoked during graph creation. The default value is 0.0. |
inverse_solve | For the MATCH_BATCH_SOLVES solver only. Solves source-destination pairs using inverse shortest path solver. |
left_turn_penalty | This will add an additional weight over the edges labeled as left_turn if the add_turn option was invoked during graph creation. The default value is 0.0. |
max_combinations | For the MATCH_SUPPLY_DEMAND solver only. This is the cutoff for the number of generated combinations for sequencing the demand locations. The maximum number of combinations is 2000000. The default value is 10000. |
max_hops | For the MATCH_SIMILARITY solver only. Solver searches within this many hops for source and target node pairs to compute the Jaccard scores. The default value is 3. |
max_loop_level | For the MATCH_LOOPS solver only. Finds closed loops around each node deducible not more than this maximal hop (level) deep. |
max_num_clusters | For the MATCH_CLUSTERS solver only. If set, processing terminates when the number of clusters after a cycle is at or below this number; thus, the solution will have at most this many clusters in it. |
max_num_threads | For the MARKOV_CHAIN solver only. If specified value is greater than 0 (default), the maximum number of threads will not be greater than the specified value. It can be lower due to the memory and number of cores available. The default value allows the algorithm to set the optimal number of threads within these constraints. |
max_stops | For the MATCH_SUPPLY_DEMAND solver only. If specified (greater than zero), a supplier can at most have this many stops (demand sites) in one round trip; otherwise, it is unlimited. If enable_reuse is on, this condition will be applied separately at each round-trip use of the same supplier. |
max_supply_combinations | For the MATCH_SUPPLY_DEMAND solver only. This is the cutoff for the number of generated combinations for sequencing the supply locations, when permute_supplies is true. The default value is 10000. |
max_trip_cost | For the MATCH_SUPPLY_DEMAND solver only. If this constraint is greater than 0 (default), then the suppliers will skip traveling from one demand site to another if the cost between them is greater than this number (distance or time). The default value means no check is performed. |
min_loop_level | For the MATCH_LOOPS solver only. Finds closed loops around each node deducible not less than this minimal hop (level) deep. |
num_cycles | For the MATCH_CLUSTERS solver only. If this is greater than 0 (default), then at most this many 2-step clustering exchange cycles will be performed; otherwise, processing will continue until quality does not improve across iterations. |
num_loops_per_cycle | For the MATCH_CLUSTERS solver only. If this is greater than 0 (default), then at most this many best-fit calculations for all nodes will be attempted in the first step of each cycle; otherwise, processing will continue until the overall best-fit quality does not improve beyond a pre-defined epsilon threshold value. |
num_output_clusters | For the MATCH_CLUSTERS solver only. If this is greater than 0 (default), then at most this many of the top clusters will be output after sorting them from most dense to least dense; otherwise, all clusters will be output. |
num_segments | Maximum number of potentially matching road segments for each sample point. The default is 3. |
output_batch_size | For the MATCH_LOOPS solver only. Uses this value as the batch size of the number of loops in flushing (inserting) to the output table. |
output_tracks | For the MATCH_SUPPLY_DEMAND solver only. When it is true (non-default), the output will be in tracks format for all the round trips of each supplier in which the timestamps are populated directly from the edge weights starting from their originating depots. |
paired_similarity | For the MATCH_SIMILARITY solver only. When set to true (default), the Jaccard score will be computed between each pair; otherwise, the Jaccard score will be computed from the intersection set between the source and target nodes. |
partial_loading | For the MATCH_SUPPLY_DEMAND solver only. When false (non-default), suppliers do not off-load at the demand site side if the remainder is less than the site’s demand. |
permute_supplies | For the MATCH_SUPPLY_DEMAND solver only. When true (default), suppliers are permuted for the demand site combinations during the optimization phase. This option increases optimization time significantly—use of max_combinations in tandem is recommended to prevent prohibitively long runs. |
restricted_type | For the MATCH_SUPPLY_DEMAND solver only. If specified, this supplier type will be restricted from routes traversing edges with the MSDO_ODDEVEN_RESTRICTED label. This models restrictions that exist, for example, in Jakarta, Indonesia. Possible values:
|
right_turn_penalty | This will add an additional weight over the edges labeled as right_turn if the add_turn option was invoked during graph creation. The default value is 0.0. |
round_trip | For the MATCH_SUPPLY_DEMAND solver only. When set to true (default), each supplier will have to return to the origination site; otherwise, the route is considered terminated at the final demand site. |
search_limit | For the MATCH_LOOPS solver only. Searches within this limit of nodes per vertex to detect loops. The value zero means there is no limit. |
search_radius | Maximum search radius used when snapping sample points onto potentially matching surrounding segments. The default value (0.001) corresponds to approximately 100 meters. |
server_id | Indicates which graph server(s) to send the request to. Default is to send to the server, among those containing the corresponding graph, that has the most computational bandwidth. |
service_limit | For the MATCH_SUPPLY_DEMAND solver only. If specified, any supplier’s total service cost (distance or time) will be limited by the specified value including multiple rounds of drop-off (if set). The default value is 0.0. |
service_radius | For the MATCH_SUPPLY_DEMAND solver only. If specified, it filters the demands outside this radius, centered around the supplier’s originating location (distance or time). The default value is 0.0. |
sharp_turn_penalty | This will add an additional weight over the edges labeled as sharp_turn or u_turn if the add_turn option was invoked during graph creation. The default value is 0.0. |
source | Optional WKT starting point from SAMPLE_POINTS for the solver. The default behavior for the endpoint is to use time to determine the starting point. The default value is POINT NULL. |
traversal_node_limit | For the MATCH_SIMILARITY solver only. Limits the traversal depth if it reaches this many nodes. The default value is 1000. |
unit_unloading_cost | For the MATCH_SUPPLY_DEMAND solver only. The unit cost per load amount to be delivered. If this value is greater than 0 (default) then the additional cost of this unit load multiplied by the total dropped load will be added over to the trip cost to the demand location. |
Examples
Using theEXECUTE FUNCTION syntax necessitates the SOLUTION_TABLE
parameter to store the match results, where using the table function syntax will
return the results directly.