Abstract
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, without maintaining frequency statistics or timestamps. Although the partial order limits the effectiveness of self-adjustments, the 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 the rearrangement cost 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 lists in the context of network packet classification. Our evaluations show that our classifier performs similarly to a static list for low-locality traffic, but significantly outperforms Efficuts (by factor 7x), CutSplit (3.6x) and the static list (14x) for high locality and small rulesets.
Cite this work
BibTeX entry
@inproceedings{salists,
author = {Addanki, Vamsi and Pacut, Maciej and Pourdamghani, Arash and R{\'{e}}tv{\'{a}}ri, G{\'{a}}bor and Schmid, Stefan and Vanerio, Juan},
title = {Self-Adjusting Partially Ordered Lists},
year = {2023},
booktitle = {Proceedings of the IEEE INFOCOM 2023 Conference}
}