MCPrioQ: A lock-free algorithm for online sparse markov-chains
This addresses the need for efficient, concurrent data structures in recommender systems, though it appears incremental as it builds on existing lock-free and read-copy-update techniques.
The paper tackles the problem of building large, efficient graphs for high-performance systems by proposing MCPrioQ, a lock-free sparse Markov-chain data structure that achieves O(1) updates and O(CDF^{-1}(t)) inference, enabling online learning with approximately correct results during concurrent updates.
In high performance systems it is sometimes hard to build very large graphs that are efficient both with respect to memory and compute. This paper proposes a data structure called Markov-chain-priority-queue (MCPrioQ), which is a lock-free sparse markov-chain that enables online and continuous learning with time-complexity of $O(1)$ for updates and $O(CDF^{-1}(t))$ inference. MCPrioQ is especially suitable for recommender-systems for lookups of $n$-items in descending probability order. The concurrent updates are achieved using hash-tables and atomic instructions and the lookups are achieved through a novel priority-queue which allows for approximately correct results even during concurrent updates. The approximatly correct and lock-free property is maintained by a read-copy-update scheme, but where the semantics have been slightly updated to allow for swap of elements rather than the traditional pop-insert scheme.