SAAP: Spatial awareness and Association based Prefetching of Virtual Objects in Augmented Reality at the Edge

Figure 2 shows two example application scenarios for AR. In a grocery store scenario[32], users interact with virtual objects of the store items to receive information about their ingredients, manufacturing details, price variations, recipes, and so on. The items are typically placed on racks in aisles based on their categories, and there is a well defined order of placement. The Field of View (FoV) of a user will have multiple items at their location in the store, from which the user might be interested in a few.

In the case of a tourist scenario, [33], attractions are typically scattered across a region (such as a city block, campus, or neighborhood). The virtual objects may contain historical facts, 3D representations of buildings, informative audio/video, and so on. A tourist would visit the attractions based on multiple factors like user interests, transportation availability, accessibility, guide recommendations, and so on. The FoV of the user in this case would likely consist of only a few items in their vinicity, and the user will have to explore the region more to find the next attraction.

Such MAR scenarios face the following challenges:

Edge infrastructure is well placed to meet these challenges by expanding on the limited on-device storage capacity, while reducing the user latency. The use of the edge in an MAR context necessitates novel data management policies that consider both AR-specific data characteristics and edge/cloud parameters.

Recent research on MAR architecture and applications [38, 18, 20, 21, 39] partitions data and tasks across mobile devices and edge servers to leverage resources at both locations and facilitate data sharing. Caching is crucial for improving AR application performance, and partitioning the cache across devices and edge servers has shown potential for increasing hit rates and reducing latency [18, 20].

However, existing approaches often neglect critical AR-specific factors: (1) Increasing Object Sizes: Caching strategies must adapt to the growing size and complexity of virtual objects. (2) Occlusion and User Proximity: Virtual objects can be occluded by physical objects in AR environments. Additionally, users are more likely to interact with nearby objects. These spatial considerations, along with object access patterns, can inform more effective caching strategies. (3) Object Relevance and User Associations: User interactions with virtual objects often exhibit predictable patterns (e.g., a user interacting with a milk carton may subsequently interact with nearby eggs or bread). However, caching strategies must assess the relevance of potential interactions to avoid unnecessary cache pollution.

Association rule mining (ARM) [40], a technique widely used in recommender systems to predict user-item interactions, offers a promising approach for AR prefetching. ARM has proven successful in various domains, including e-commerce [32], tourism [33], fraud detection [41], and social network analysis[42]. For example, in online grocery shopping, purchasing milk and eggs often triggers recommendations for bread and jam. However, the direct application of ARM for prefetching in AR remains an underexplored area. The rule generation process, particularly with frequent updates, can be computationally expensive, posing a challenge for latency-sensitive AR applications. This work explores adapting ARM to the specific needs of AR, aiming to achieve efficient prefetching while minimizing computational overhead. While ARM effectively identifies related virtual objects, it may not prioritize those most relevant to the user’s current location. Prefetching objects far from the user’s field of view (FoV) provides limited value in AR. Therefore, this work emphasizes incorporating spatial awareness into the prefetching process. By prioritizing objects near the user’s FoV, we aim to optimize cache utilization and enhance the user experience.

Figure 3 illustrates the MAR pipeline incorporating SAAP into the edge cache. Sensor data from the user’s device is transmitted to the nearest edge server, where video frames are pre-processed and object detection is performed. Extracted features are then used for object recognition. If a corresponding virtual object exists, the system attempts to retrieve it from the edge cache. Upon a cache miss, the SAAP algorithm is invoked to identify all necessary objects for prefetching and request them from the cloud, along with the object that caused the cache miss. After receiving the virtual objects, template matching is performed to estimate their pose. This pose information, along with the virtual objects, is sent to the object tracking module on the user’s device. The tracking module identifies objects across frames, and this information, combined with data from the edge server, is used by the rendering module to overlay virtual content onto the user’s display.

We next discuss the two main SAAP techniques that drive its prefetching: association and proximity.

Intuitively, if a user accesses a virtual object in an MAR scenario, they are likely to soon access related objects (e.g., milk and eggs in the grocery scenario), which should be prefetched to the edge cache for faster access. SAAP’s Association technique generates association rules using Association rule mining (ARM) [43, 40] to predict frequently co-accessed virtual objects based on user interaction history.

ARM identifies relationships between items in a transaction database by discovering frequent itemsets: groups of items that frequently co-occur in transactions. The support $(S)$ of an itemset indicates the proportion of transactions containing that itemset, with frequent itemsets exceeding a predefined minimum support threshold. Based on these frequent itemsets, ARM generates association rules of the form $A\implies B$, where $A$ (antecedent) and $B$ (consequent) are disjoint itemsets. The confidence $(C)$ of a rule represents the conditional probability of observing the consequent in transactions containing the antecedent, controlled by a minimum confidence threshold. The lift $(L)$ of a rule measures the strength of the association between the antecedent and consequent, quantifying how much more likely they are to co-occur than if they were statistically independent. Support of an itemset $X$ ($S(X)$), confidence of a rule $A\implies B$ ($C(A\implies B)$) and lift of the rule ($L(A\implies B)$) are formally represented as follows:

where $T(X)$ and $T$ are the number of transactions containing $X$ and the total number of transactions respectively. We use ARM algorithms to either generate rules a priori from history user interactions or dynamically during the process.

SAAP uses an ARM algorithm to generate a set of associated objects for prefetching whenever there is a cache miss. However, all such associated objects are not equally relevant for prefetching. Objects that have been accessed more frequently and more recently are more likely to be more useful for caching. Thus, SAAP prioritizes relevant objects within an association set using an association factor value for each object. This factor reflects the combined influence of frequency and recency of association with the missing object. Objects with higher association factors are prioritized for caching due to their increased likelihood of subsequent user interaction.

We calculate the association factor ($A$) of a virtual object $vo$ as follows:

where $\alpha=\frac{2}{1+window}$, $window$ is the window frame of previous object interactions which are relevant, $F(vo)$ is the number of times the virtual object $vo$ is reference in the window frame. The value of $window$ could be tuned according to the recency requirement. A larger window implies longer trend and a smaller one for shorter trend. If the access patterns are not changing frequently, a larger window size would suffice. Association factor threshold value should be set such that low association objects are filtered. The higher the threshold value, higher the chance that the selected objects are accessed in the near future.

Since relevant AR objects are based on the field of view of the user, the system only needs to prefetch objects that are in the user’s physical vicinity. SAAP incorporates spatial proximity to refine the prefetching list generated by the Association component. Proximity refers to the distance of virtual objects $(Prox(vo))$ from the user’s location. For instance, in the grocery store scenario (Figure 2), an association rule might suggest prefetching “milk” alongside “apples” and “bananas”. However, if the user is not yet in the aisle containing milk, immediate prefetching of the “milk” virtual object is unnecessary. SAAP prioritizes contextual relevance by employing a lazy prefetching strategy, deferring the prefetching of “milk” until the user is in closer proximity. This ensures that prefetched objects are highly relevant to the user’s immediate surroundings. A proximity threshold $(Prox(threshold))$ is used to identify objects within a specific distance from the user. This threshold is domain-specific and depends on the application use case and physical environment.

Figure 4 illustrates the workflow of the SAAP framework. Upon encountering a cache miss for virtual object $vo$ , SAAP’s Association module utilizes the ARM-generated rules to identify potentially associated objects based on the user’s access history and the missing object . To refine this selection and prioritize relevant objects, it uses the association factor for each object. Objects with association factors higher than the Association factor threshold are prioritized for caching due to their increased likelihood of subsequent user interaction . Next, the Proximity module filters the selected objects further to those within the Proximity threshold of the user . The filtered out relevant objects are set aside for lazy fetch later when the user moves closer to them . Once all the virtual objects to be fetched are identified, the request is send to the cloud . On retrieval, the objects are stored in cache and the missed virtual object is returned. Note that SAAP works in a complementary manner to the cache that continues to use its caching algorithms, e.g., for evicting any objects needed to make space in the cache.

In ARM, selecting the minimum support and minimum confidence thresholds is often domain-dependent, requiring expert knowledge. To automate SAAP, we focus on tuning the minimum support parameter. Minimum support is prioritized as it directly influences the generation of frequent itemsets, which are fundamental to the subsequent steps in the process. Other parameters can be tuned in a similar manner.

The TuneMinSup function dynamically adjusts the minimum support based on cache hit rate degradation. It determines whether to generate new association rule sets, select from existing ones, or continue with the current/next set, depending on the degree of hit rate degradation relative to a predefined threshold.

The GenARules function identifies the bounds for minimum support and generates $N$ new association rule sets, ranging from low to high support values, based on the last $n$ transactions. The value of $n$ can be adjusted to meet the application’s association recency requirements.

The SetARules function selects the appropriate rule set to use. Whenever new $N$ rulesets are generated in the increasing order of minimum support, the function selects the middle ruleset. Otherwise, it goes in the increasing or decreasing minimum support direction, depending on the hit rate degradation. This dynamic adjustment allows the system to adapt to changing access patterns and maintain optimal performance.

In the GenARules function, the initial lower and upper bounds for minimum support are first determined. Since popular items typically represent a small percentage of the total unique items in most datasets [44], the lower bound is set to the average support of all items [45]. From this initial range, $D$ evenly spaced minimum support values are selected. For each value, association rules are generated with a fixed minimum confidence. During rule generation, the process terminates if the rule count ratio exceeds a predefined threshold $(\eta)$, indicating the potential inclusion of irrelevant rules. Otherwise, the kurtosis value is recorded. If the difference in kurtosis between the current and previous rule sets exceeds another threshold $(\theta)$, the process terminates, signaling the generation of a large number of rules with relatively low lift values. This step helps to prevent overfitting and ensures the selection of meaningful rules. If neither termination condition is met, the current minimum support range is updated. Finally, $N$ rule sets are generated from the identified minimum support bounds and utilized accordingly. This adaptive approach allows for efficient and effective rule generation tailored to the specific characteristics of the workload.

We use a combination of simulations and real testbed experiments. Our experimental testbed utilizes a 64GB Intel Xeon E5-2620 with 24 cores (end-users), a 16GB AWS Local Zone EC2 t3.xlarge (edge server), and a 16GB AWS EC2 t2.xlarge (cloud server). Evaluation is performed using four synthetic datasets and a real-world dataset [44].

We designed an AR workload simulator that replicates key aspects of user behavior and object placement: (1) Environment: Constructs a geographical region with obstacles using collider data [46], mimicking real-world scenarios with varying object placement densities . The distance between objects is within the range of [10, 15] unit distance. (2) User Behavior: Models user movement, gaze direction, and interaction time with virtual objects. (3) User Traffic: Simulates user arrivals using a Poisson process and interaction time with each object using a normal distribution, capturing both regular and peak usage scenarios.

We utilize both synthetic and real world datasets (Table II) for our experiments.

Since SAAP is complementary to the underlying cache algorithm, we consider four native cache eviction policies in our evaluation: FIFO, LRU, LFU and Popularity (POP). Comparison is carried out with and without SAAP integration with the cache. Unless specified, we are not tuning SAAP in the experiments in this section. The results of auto-tuning algorithm are presented separately.

This experiment evaluates SAAP’s effectiveness when integrated with cache eviction algorithms (baselines). We varied both minimum support and minimum confidence from 30% to 75% while keeping other parameters constant (association factor at 1, and proximity threshold at 15). As shown in Figure 5 and Table III, SAAP significantly improves hit rates compared to baselines by 3.27% to 40.6% across all datasets.

SAAP demonstrates the highest relative improvement over the FIFO baseline, particularly with the DS30 dataset. This highlights SAAP’s ability to mitigate FIFO’s limitation of potentially evicting frequently accessed items by proactively caching those likely to be accessed in the near future. Similar improvements are observed for LRU and POP. However, LFU exhibits lower hit rates due to its tendency to evict recently added, associated items.

Furthermore, hit rates generally increase from DS30 to DS75, indicating that both baseline algorithms and SAAP benefit from a greater number of relevant associations. Subsequent results provide a detailed analysis of each parameter’s impact within specific configurations¹¹1For space reasons, we present results with a subset of the datasets and baseline algorithms. The trends hold for the omitted results..

This experiment investigates the impact of minimum support on SAAP’s performance. We varied the minimum support threshold from 30% to 75% while keeping other parameters constant (minimum confidence at 45%, association factor at 1, and proximity threshold at 15). Figure 6 shows the hit rate variation for DS30 and DS75, with similar trends observed for DS45 and DS60. This behavior is consistent across different minimum confidence values. As a critical parameter in association rule mining, higher minimum support thresholds result in fewer frequent itemsets and consequently, fewer association rules, potentially leading to lower hit rates.

This experiment analyzes the influence of minimum confidence on SAAP’s performance. We varied the minimum support threshold from 30% to 75% while keeping other parameters constant (minimum confidence at 45%, association factor at 1, and proximity threshold at 15). Figure 7 shows this effect on DS30 and DS75, with similar trends observed for DS45 and DS60 across different minimum support values. As a key parameter in ARM, increasing the minimum confidence threshold initially improves or maintains hit rates before causing a decline. This trend reflects the trade-off between rule quality and quantity. Higher thresholds reduce the number of rules, improving quality but potentially excluding relevant associations.

This experiment examines the impact of the association factor on SAAP’s cache hit rates. With minimum support and minimum confidence fixed at 30% and 45% respectively, the association factor was varied from 0.1 to 4. Figure 8 illustrates the results. As dataset support increases (i.e., associated objects are accessed more frequently), the influence of the association factor on identifying relevant objects diminishes. For DS30, the highest hit rate is achieved with an association factor of 0.1, demonstrating a clear impact. However, for DS75, where frequent itemsets have higher support, the association factor has a less pronounced effect. This suggests that the association factor plays a more critical role in scenarios with lower object access frequencies.

Figure 9 illustrates the influence of the proximity threshold on cache hit rates for SAAP-integrated baselines. We varied the proximity threshold from 5 to 20 unit distance while fixing the minimum support at 30%, minimum confidence at 45%, and association factor threshold at 1. The proximity threshold has a significant impact on hit rates. A very low threshold might neglect relevant objects located slightly further away, potentially missing prefetching opportunities. Conversely, an excessively high threshold could lead to prefetching irrelevant objects that are not close enough for immediate user interaction, wasting cache resources. Therefore, selecting an appropriate proximity threshold is crucial for optimizing SAAP’s effectiveness. Similar results are observed for DS45 and DS60.

Figure 10 shows the relative performance and overhead of using association only and association+proximity (SAAP) on top of the baseline caching algorithm, using the DS30 dataset with fixed parameters. The left graph shows that the hit rate improvement associated with association and SAAP are 3- 20% and 8- 36% respectively. The right graph measures the overhead of using SAAP by comparing on-demand fetches and prefetches across the baseline, baseline with association-based prefetching, and baselines with SAAP. It shows that both association-based prefetching and SAAP reduce on-demand fetches compared to the baseline by 2-17% and 23-31% respectively, as prefetching caches relevant objects. However, this introduces a prefetch overhead. Notably, association-based prefetching alone has a significantly higher overhead (0.51-2.12X) than SAAP (0.12-0.70X) due to its lack of irrelevant object filtering. Overall, the reduced on-demand fetches lead to improved hit rate and lower latency. While the prefetching occurs in the background without degrading user experience, it still leads to additional bandwidth consumption which we plan to address through parameter tuning and encoding in future work.

This experiment evaluates the impact of user count on SAAP’s performance by varying the number of users from 100 to 1000 for FIFO cache policy. Figure 11(a) shows the best hit rates achieved for DS30 across all minimum support and minimum confidence values. SAAP-FIFO improves hit rates by 5-40% when compared to FIFO. Importantly, SAAP maintains consistent hit rate improvements across the varying user counts in each dataset. This suggests that SAAP’s performance is robust to changes in user count.

This experiment examines the impact of virtual object count on SAAP’s effectiveness, a crucial factor varying significantly across application domains. We varied the number of virtual objects from 20 to 100 for DS30 workload for 500 users on FIFO. Figure 11(b) presents the best achievable hit rates for SAAP-FIFO compared to FIFO.

Results show a decreasing trend in hit rate improvement as object count increases within the same region. For instance, it is 96% for 20 objects, 40% for 50 objects, and 15% for 100 objects. Similar trends are observed in other datasets and cache policies. This can be attributed to increased object density, leading to more objects falling within the user’s field of view (FoV). Consequently, baseline caching policies are more likely to cache relevant objects by chance, reducing the relative advantage of SAAP’s targeted prefetching strategy.

In this experiment, we focus on tuning minimum support value with a fixed minimum confidence of 10%, cache capacity of 10%, hit rate degradation threshold of 5%, initial transaction count for generating association rules of 100 and DS30 workload of 1000 users. Figure 12 shows the hit rate associated with FIFO baseline, FIFO with SAAP (no tuning) and FIFO with tunable SAAP. It can be seen than dynamic tuning of SAAP leads to higher hit rates. SAAP-Tune achieves 10% and 22% better hit rate compared to SAAP and FIFO baseline. The hit rates are recorded every 10 views (1 viewpoint) and checked for degradation. If it is above a threshold, the association rule sets are generated. During the generation of association rules, incoming requests are served in parallel. Once the association rule set is selected, it is used for identify associated objects.

We use a real world dataset from SPMF [44] that consist of 169 items and 1000 transactions. We use Amazon Local zone for the edge server and AWS EC2 for the cloud server. The cache capacity is set to 10%, hit rate degradation to 5% and initial transaction count to 100 for rule generation. Figure 13 shows the hit rate performance. The hit rates are recorded every 100 views (1 viewpoint) and checked for degradation. It could be seen that SAAP with dynamic tuning is able to perform better than SAAP and FIFO as time passes by. Initially, it takes time to warm-up and then the hit rate starts increasing. SAAP-Tune achieves 6% and 11% better hit rate compared to SAAP and FIFO baseline.