The traditional thin-client model is replaced by a model where clients continuously cooperate via the cloud, in order to give the user a rich experience. Well-known examples of such cloud applications are Gmail and Google Docs. The client-side of these cloud applications often runs in the browser while the server-side is deployed in the cloud.

Some collaborative cloud applications serve a massive number of participants who generate huge amounts of data. A simple example of such an application is Twitter. Every time a user sends a tweet to the cloud, the cloud immediately processes this information and notifies an (often small) interested subset of its users (those who are subscribed to the one who tweets) of this new tweet. Twitter is however a dull example because users manually indicate in which users and hash tags they are interested. A more involved example is a dating service that allows its users to upload a profile and (arbitrarily complicated) predicates to constrain potential new contacts. Based on these constraints, the cloud decides which user accounts have a match, and should hence exchange information such as location and contact information with other specific users. These constraints and profiles can, however, continuously change (e.g. a mobile client of this application might always send its location to the server) and this new information needs to be processed in near real-time by the cloud in order to find possible new matches.

This is the type of  cloud-applications we envision in this thesis. To handle such a continuous stream of information, production rule systems are often used.  A well-known implementation of production rule systems is the RETE algorithm [1][2]. This algorithm was designed to detect patterns in large amounts of data. RETE performs well under these circumstances because it incrementally keeps track of intermediate (pattern) matches. The RETE-algorithm, however, was developed in the eighties. Since then, the landscape of how computers are used has changed drastically and the amount of data that sits on a device and that is sent over a network (to the cloud) has increased dramatically. Over the past few decades, numerous optimizations for RETE have been developed to cope with the increasing amount of data that needs to be processed [3][4]. Certain optimizations/implementations expose better performance characteristics when a significant amount data is being removed but expose worse performance characteristics when data is being added to the system. Other optimizations/implementations of the RETE-algorithm perform better under yet other circumstances.