Federated Learning (FL) is a distributed machine learning approach to learn models on decentralized heterogeneous data, without the need for clients to share their data. We introduce a framework to model the natural, inherent prioritization of some clients in federated learning, in subscriber settings or recommender systems. Our novel algorithm FedALIGN, is a communication efficient client selection scheme, that has theoretical convergence guarantees and state of the art performance over baselines.

Pairwise sequence alignment in the context of gene sequencing is a heavy computational burden. This issue is commonly addressed by approximately estimating sequence similarities using a hash-based method such as MinHash. In MinHash, all k-mers in a read are hashed and the minimum hash value, the min-hash, is stored. We introduce a new similarity estimation method called LexicHash, which is effectively independent of the choice of k and attains the high precision of large-k and the high sensitivity of small-k MinHash. In our experiments the area under the Precision-Recall Curves obtained by LexicHash had an average improvement of 20.9% over MinHash. As an added benefit, the LexicHash framework lends itself naturally to an efficient search of the top-T best alignments out of all pairs, yielding an O(n) time algorithm for finding the top-T pairwise similarities, circumventing the seemingly fundamental O(n²) scaling associated with pairwise similarity search.