5.11 Network Analysis Using Load on Demand

Load on demand means that during network analysis, a network partition is not loaded into memory until the analysis has reached this partition while exploring the network.

With load on demand, Oracle Spatial performs most partitioning and loading operations automatically, and this usually results in more efficient memory utilization with very large networks.

Load on demand analysis involves the following major steps: network creation, network partition, partition cache configuration, and network analysis.

1. Create the network, using one of the approaches described in Main Steps in Using the Network Data Model.

2. Partition the network using the SDO_NET.SPATIAL_PARTITION procedure, as explained in Partitioning a Network.

3. Optionally, generate partition BLOBs, as explained in Generating Partition BLOBs.

4. Configure the load on demand environment, including the partition cache, as explained in Configuring the Partition Cache.

5. Analyze the network, as explained in Analyzing the Network.

Note:

Load on demand analysis also works with nonpartitioned networks by treating the entire network as one partition. For a small network, there may be no performance benefit in partitioning it, in which case you can skip the partitioning but still use load on demand APIs.

For examples of performing load on demand network analysis and configuring the partition cache, see Partitioning and Load on Demand Analysis Examples (PL/SQL_ XML_ and Java).

Additional examples of partitioning and load on demand analysis are included on the Oracle Database Examples media (see Oracle Database Examples Installation Guide). For more information about Network Data Model example and demo files, see Network Data Model Tutorial and Other Resources.

• Partitioning a Network
  
• Generating Partition BLOBs
  
• Configuring the Partition Cache
  
• Analyzing the Network
  
• Using Link Levels for Priority Modeling
  
• Precomputed Analysis Results
  

5.11.1 Partitioning a Network

You can partition a network using the SDO_NET.SPATIAL_PARTITION procedure, specifying the maximum number of nodes in each partition. The partition result is stored in a partition table, which is automatically generated, and partition metadata information is inserted into the network metadata. (As an alternative to using the procedure, you can partition a network by creating and populating a partition table.) You can use other SDO_NET subprograms to query the partitioning metadata.

A good partition strategy is to minimize the number of links between partitions, which reduces the number of partitions that need to be loaded and the probable number of times that the same partitions need to be reloaded. Moreover, partitions that are too small require excessive loading and unloading of partitions during analysis.

The recommended maximum number of nodes per partition, assuming 1 GB of memory, is between 5,000 and 10,000. You can tune the number and see what is best for your applications, considering the available memory, type of analysis, and network size. You should also consider configuring the partition caching size.

5.11.2 Generating Partition BLOBs

To enhance the performance of network loading, you can optionally store partitions as BLOBs in a network partition BLOB table. This information needs to be stored in the network metadata view in order to take advantage of faster partition loading time. Note that if a network or partition information is updated, the partition BLOBs need to be regenerated as well.

A partition BLOB is a binary stream of data containing the network partition information, such as number of nodes, number of links, properties of each node, properties of each link, and so on. If a partition BLOB exists, Spatial uses it to read information during the load operation, rather than performing time-consuming database queries.

To generate partition BLOBs, use the SDO_NET.GENERATE_PARTITION_BLOBS procedure. The partition BLOBs and their metadata are stored in the Partition BLOB Table.

5.11.3 Configuring the Partition Cache

Before you perform network analysis, you can configure the network partition cache to optimize performance, by modifying an XML configuration file to override the default configuration. You can specify the following:

• Cache size: the maximum number of nodes in partition cache

• Partitions source: from network tables or partition BLOBs

• Resident partitions: IDs of partitions that will not be flushed out of the cache, but will stay in memory once they are loaded

• Cache flushing policy: class name of the CachingHandler implementation

  The default caching policy is LeastRecentlyUsed, which flushes out the oldest partition out of memory when the cache is full. You can specify other caching policies by implementing the CachingHandler interface.

A copy of the default load on demand configuration file is included in the supplementary documentation, described in Network Data Model Tutorial and Other Resources.

5.11.4 Analyzing the Network

After you have created and partitioned the network, and optionally configured the partition cache, you can issue analysis queries. Analysis results are returned in Java representation or XML responses, depending on whether you used the Java or XML API. For details, see the load on demand (LOD) Javadoc and XML schemas (the latter described in Network Data Model Tutorial and Other Resources).

You can write the analysis results to the database using the load on demand Java API.

5.11.5 Using Link Levels for Priority Modeling

Although the load on demand approach reduces the effect of memory limitations in analyzing large networks, analysis operations still can sometimes be very slow. For example, shortest path analysis of two nodes diagonally across the entire network is likely to require traversing almost every link in the network, and this will take a significant amount of time for a network with more than, for example, two million nodes.

To further reduce network analysis time, you can perform analysis on different link levels. Link level is a positive integer assigned to a link indicating the level of preference of this link. The higher the link level, the higher the preference. For example, a road network may consist of two link levels, level 1 for local roads and level 2 for highways. During network analysis, highways are preferred to local roads, and the minimum link level is 1. (If no link level is assigned to a link, the default link level of 1 is used for the link.)

Link levels have an implicit inheritance property, which means that a network at higher link levels must be a subnetwork of a network at a lower link level. That is, link level 2 is a subnetwork of link level 1, link level 3 is a subnetwork of link level 2, and so on.

You can specify a link level when you load a network or a partition, which causes links at that level and higher levels to be loaded. Using the road network example, with link level 1 for local roads and link level 2 for highways, specifying link level 1 on a load operation loads links at link levels 1 and 2 (that is, local roads and highways), but specifying link level 2 on a load operation loads only the highways links. If you wanted to perform analysis using only highways links, you could optimize the performance by specifying link level 2 for the load operation.

5.11.6 Precomputed Analysis Results

Some analysis operations, such as connected component analysis, can be time consuming. To improve runtime performance, you can call the SDO_NET.FIND_CONNECTED_COMPONENTS procedure, which computes the connected components in the network and stores the results in the Connected Component Table.

At runtime, before calling shortest path analysis or reachability analysis, you can check whether the nodes of interest belong to the same connected component by querying the connected component table. If precomputed component information does not exist, it may take a long time for shortest path and reachability analysis to discover that two nodes are, in fact, not connected.