Treffer: A Multi-dimensional Spatial Cache for Decision Support Systems

Data-driven systems can benefit greatly from software caches. When the processed information is spatial, the cache must be aware of the spatial properties of the data. The Framework for Integrated Risk Management (FIRM) and the National Agriculture Decision Support System (NADSS) are data-driven systems that may benefit from a spatial cache. A spatial cache was developed for NADSS, but it had several aspects that could be improved. This thesis describes a new spatial cache designed for FIRM. This cache is designed to ease integration with new calculations as well as reduce duplicate calculations. In attempting to calculate cache misses without calculating previously cached information, a new problem is discovered: Minimal n-Dimensional Orthogonal Partitioning (MNDOP). A discussion on this problem follows, but an algorithm that finds the optimal solution is not found. Instead, a fast algorithm that finds an approximate solution is described. The spatial cache was implemented to fit the design using this fast algorithm as well as incorporating several new features of the Java Enterprise Edition framework and some data structures that reduce complexity of spatial queries. The performance of the spatial cache is dependent on the complexity of the calculation that is cached. The performance gain matches closely to the percent of the request that is cached, largely dependent on the constant overhead of the calculation. The cache achieves a noticeable performance gain when the uncached request spans only a few seconds, even though the cache is designed for more complex calculations. Finally, several improvements and added features are described for future development. i iiTo my parents, who got me this far. Special thanks to