<quote>Exploring the feasibility of a rete-based approach to the continuous compression of dynamic graphs.</quote>

The goal of the project is to create a continuous compression method for dynamic graphs.

In order to implement the compression method a cross-domain apporoach is being adopted. Drawing on specialised knowledge from across domains of expertise is recognized as an important element of innvation ¹⁾ The project will specifically be drawing from three specialised technology domains: Graph Processing, Expert Systems and Relational Databases.

A cross domain collaboration approach called Cross-Domain Topic Learning is being adapted. It is an approach that models topics within a source and target domain simultaneously through . ²⁾

The focus is on a problem the problem of traversing a large graph. This same problem is present in all three domains:

• Graph Processing - Pattern Matching within a Graph
• Expert Sytems - Testing all facts within working memory for activated productions.
• Relational Databases - Joining and reducing data sets to complete a query

Within all three domains the same solution is found: Indexing data sets with hashing functions in order to reduce the iterations required to complete traversal.

Within the domain of expert system only there exists the RETE algorithm. ³⁾ This algorithm represents the indexing function as a network of simple feature regonizers. Processing the changes to working memory through this network entirely removes the need to iterate over and evaluate facts.

Adoptions of the RETE algorithm introduces two important benefits within the Expert System domain. The project involves seeks to investigate how well these benefits can be achieved within the Graph Processing domain.

• Language Alignment. The RETE approach supports the creation of declarative languages that are more closely

aligned to the problem domain than iterative languages.

• Continuous Matching. The RETE has proven itself as effective at continuous pattern matching, evaluating changes in state quickly and efficiently.
• Parallel Execution. By removing the need for traversal the RETE approach removes a barrier to parallel execution.
• Execution Plan. The RETE approach creates a network for evaluating state changes and executing actions when specific conditions occur. This network can be examined and optimized.
• Runtime Optimization. The dynamic nature of the RETE approach supports the adjustment of the generated network at runtime to maintain optimal performance within a changing environment.

For evaluation of the potential benefits of Langauge Alignment and Continous Matching prototypes will be created using the CLIPS rules engine. It is believed that the CLIPS langauge will allow for these benefits to be demonstrated without the need for chaning it's implementation.

This analysis will be applied over the following prototypes:

1. Simple Algorithm. A well understood algorithm for idenitfying elementary cycles is prototyped to assess the value of the RETE approach in the graph processing context.
2. Existing Algorithm. An existing method for graph compression is prototyped to assess the value of the RETE approach in the graph compression context.
3. New Algorithm. A novel compression method for graph compression is prototyped to assess the value of the RETE approach for the development of new graph algorithms.
4. End to End Process. The algorithms developed will be implemented within a pipes and filters framework to assess the composability of the RETE approach.

For evaluating the potential benefits of Parallel Processing, Execution Plan and Runtime Optmisation research will be carried out. It is believed that the CLIPS runtime would need to be updated in order to demonstrate these benefits. Updates to the CLIPS runtime is outside the scope of this project.

The research will identify existing solutions that demonstrate these benefits, and provide an overview of the porgress made. Recommendations will be made for how these benefits might be achieved within a RETE based graph processing solution.

* Forgy, C.L. (1982) “Rete: A fast algorithm for the many pattern/many object pattern match problem,” Artificial Intelligence, 19(1), pp. 17–37. Available at: https://doi.org/10.1016/0004-3702(82)90020-0. * Hille C. H. (2012). “Working Alone Together: Coordination in Collaboration across Domains of Expertise.” Academy of Management Journal. Vol. 56, No. 1. Available online at https://doi.org/10.5465/amj.2010.0756 * Tang, Jie et al. “Cross-Domain Collaboration Recommendation.” Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2012. 1285–1293. Web.