Self-Adjusting Partially Ordered Lists

We introduce self-adjusting partially ordered lists, a generalization of self-adjusting lists where additionally there may be constraints for the relative order of some nodes in the list. The lists self-adjust to improve performance while serving input sequences exhibiting favorable properties, such as locality of reference, but the constraints must be respected.

We design a deterministic adjusting algorithm that operates without any assumptions about the input distribution and without maintaining frequency statistics or timestamps. Despite the more general model, we show that our deterministic algorithm performs closely to optimum (it is 4-competitive). In addition, we design a family of randomized algorithms with improved competitive ratios, handling also a more general rearrangement cost model, scaled by an arbitrary constant d ≥ 1. Moreover, we observe that different constraints influence the competitiveness of online algorithms, and we shed light on this aspect with a lower bound.

We investigate the applicability of our self-adjusting lists in the context of network packet classification. Our evaluations show that our classifier performs similarly to a static list for lowlocality traffic, but significantly outperforms Efficuts (by factor 7x), CutSplit (3.6x) and the static list (14x) for high locality and small rulesets.