The Rank-Biased Centroids (RBC) rank fusion method to combine multiple-rankings of objects.

Overview

Rank-Biased Centroids (RBC) Crates.io Docs.rs MIT licensed

The Rank-Biased Centroids (RBC) rank fusion method to combine multiple-rankings of objects.

This code implements the RBC rank fusion method, as described in:

@inproceedings{DBLP:conf/sigir/BaileyMST17,
  author    = {Peter Bailey and
               Alistair Moffat and
               Falk Scholer and
               Paul Thomas},
  title     = {Retrieval Consistency in the 
               Presence of Query Variations},
  booktitle = {Proc of {ACM} {SIGIR} Conference on
               Research and Development in Information Retrieval,
  pages     = {395--404},
  publisher = {{ACM}},
  year      = {2017},
  url       = {https://doi.org/10.1145/3077136.3080839},
  doi       = {10.1145/3077136.3080839},
  timestamp = {Wed, 25 Sep 2019 16:43:14 +0200},
  biburl    = {https://dblp.org/rec/conf/sigir/BaileyMST17.bib},
}

The fundamental step in the working of RBC is the usage a persistence parameter (p or phi) to to fusion multiple ranked lists based only on rank information. Larger values of p give higher importance to elements at the top of each ranking. From the paper:

As extreme values, consider p = 0 and p = 1. When p = 0, the agents only ever examine the first item in each of the input rankings, and the fused output is by decreasing score of firstrst preference; this is somewhat akin to a first-past-the-post election regime. When p = 1, each agent examines the whole of every list, and the fused ordering is determined by the number of lists that contain each item – a kind of "popularity count" of each item across the input sets. In between these extremes, the expected depth reached by the agents viewing the rankings is given by 1/(1 − p). For example, when p = 0.9, on average the first 10 items in each ranking are being used to contribute to the fused ordering; of course, in aggregate, across the whole universe of agents, all of the items in every ranking contribute to the overall outcome.

More from the paper:

Each item at rank 1 <= x <= n when the rankings are over n items, we suggest that a geometrically decaying weight function be employed, with the distribution of d over depths x given by (1 − p) p^{x-1} for some value 0 <= p <= 1 determined by considering the purpose for which the fused ranking is being constructed.

Example fusion

For example (also taken from the paper) for diffent rank orderings (R1-R4) of items A-G:

Rank R1 R2 R3 R4
1 A B A G
2 D D B D
3 B E D E
4 C C C A
5 G - G F
6 F - F C
7 - - E -

Depending on the persistence parameter p will result in different output orderings based on each items accumulated weights:

Rank p=0.6 p=0.8 p=0.9
1 A(0.89) D(0.61) D(0.35)
2 D(0.86) A(0.50) C(0.28)
3 B(0.78) B(0.49) A(0.27)
4 G(0.50) C(0.37) B(0.27)
5 E(0.31) G(0.37) G(0.23)
6 C(0.29) E(0.31) E(0.22)
7 F(0.11) F(0.21) F(0.18)

Code Example:

Non weighted runs:

use rank_biased_centroids::rbc;
let r1 = vec!['A', 'D', 'B', 'C', 'G', 'F'];
let r2 = vec!['B', 'D', 'E', 'C'];
let r3 = vec!['A', 'B', 'D', 'C', 'G', 'F', 'E'];
let r4 = vec!['G', 'D', 'E', 'A', 'F', 'C'];
let p = 0.9;
let res = rbc(vec![r1, r2, r3, r4], p).unwrap();
let exp = vec![
    ('D', 0.35),
    ('C', 0.28),
    ('A', 0.27),
    ('B', 0.27),
    ('G', 0.23),
    ('E', 0.22),
    ('F', 0.18),
];
for ((c, s), (ec, es)) in res.into_ranked_list_with_scores().into_iter().zip(exp.into_iter()) {
    assert_eq!(c, ec);
    approx::assert_abs_diff_eq!(s, es, epsilon = 0.005);
}

Weighted runs:

use rank_biased_centroids::rbc_with_weights;
let r1 = vec!['A', 'D', 'B', 'C', 'G', 'F'];
let r2 = vec!['B', 'D', 'E', 'C'];
let r3 = vec!['A', 'B', 'D', 'C', 'G', 'F', 'E'];
let r4 = vec!['G', 'D', 'E', 'A', 'F', 'C'];
let p = 0.9;
let run_weights = vec![0.3, 1.3, 0.4, 1.4];
let res = rbc_with_weights(vec![r1, r2, r3, r4],run_weights, p).unwrap();
let exp = vec![
    ('D', 0.30),
    ('E', 0.24),
    ('C', 0.23),
    ('B', 0.19),
    ('G', 0.19),
    ('A', 0.17),
    ('F', 0.13),
];
for ((c, s), (ec, es)) in res.into_ranked_list_with_scores().into_iter().zip(exp.into_iter()) {
    assert_eq!(c, ec);
    approx::assert_abs_diff_eq!(s, es, epsilon = 0.005);
}

License

MIT

You might also like...
Drop ownership from "method position"

disown Drop ownership from "method position". Motivation Normally, unowned data is automatically dropped at the end of its residing block. We can also

Simulation tools for animating interacting soft objects

Softy Simulation tools and libraries for animating rigid and soft objects (including cloth) subject to frictional contacts against smooth implicit sur

A stack-allocated box that stores trait objects.

This crate allows saving DST objects in the provided buffer. It allows users to create global dynamic objects on a no_std environment without a global allocator.

Vue, React, Solid, Angular, Svelte, and Liquid From JS Objects.

Vue, React, Solid, Angular, Svelte, and Liquid From JS Objects.

Vue, React, Solid, Angular, Svelte, and Liquid From JS Objects.

Vue, React, Solid, Angular, Svelte, and Liquid From JS Objects.

Remoc 🦑 — Remote multiplexed objects and channels for Rust
Remoc 🦑 — Remote multiplexed objects and channels for Rust

Remoc 🦑 — remote multiplexed objects and channels Remoc makes remote interaction between Rust programs seamless and smooth. Over a single underlying

beaver is a library for setting up Rust objects inspired by factory_bot.
beaver is a library for setting up Rust objects inspired by factory_bot.

beaver is a library for setting up Rust objects inspired by factory_bot. Usage | Examples | Docs Dependencies [dependenci

Parser for Object files define the geometry and other properties for objects in Wavefront's Advanced Visualizer.

format of the Rust library load locad blender obj file to Rust NDArray. cargo run test\t10k-images.idx3-ubyte A png file will be generated for the fi

A stack for rust trait objects that minimizes allocations

dynstack A stack for trait objects that minimizes allocations COMPATIBILITY NOTE: dynstack relies on an underspecified fat pointer representation. Tho

Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism" written in OCaml

bidi-higher-rank-poly Didactic implementation of the type checker described in "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorph

Implementation of "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism"

Implementation of "Complete and Easy Bidirectional Typechecking for Higher-Rank Polymorphism" See arXiv:1306.6032 This implementation focusses on read

The goal of this challenge is to create an isometric, decorated scene in which the character can move around the objects in the room.

The goal of this challenge is to create an isometric, decorated scene in which the character can move around the objects in the room.

A lightweight Rust library for BitVector Rank&Select operations, coupled with a generic Sparse Array implementation

A lightweight Rust library for BitVector Rank&Select operations, coupled with a generic Sparse Array implementation

Multiple USB File Flasher
Multiple USB File Flasher

Popsicle Popsicle is a Linux utility for flashing multiple USB devices in parallel, written in Rust. Build Dependencies If building the GTK front end,

👩‍❤️‍💋‍👩 Synchronize installed packages on multiple machines
👩‍❤️‍💋‍👩 Synchronize installed packages on multiple machines

emplace Command-line tool to mirror installed software on multiple machines. Features Outputs a human-readable (RON) file to sync between machines: .e

Single-reader, multi-writer & single-reader, multi-verifier; broadcasts reads to multiple writeable destinations in parallel

Bus Writer This Rust crate provides a generic single-reader, multi-writer, with support for callbacks for monitoring progress. It also provides a gene

Truly cross platform, truly native. multiple backend GUI for rust
Truly cross platform, truly native. multiple backend GUI for rust

WIP: Sauron-native a rust UI library that conquers all platforms ranging from desktop to mobile devices. An attempt to create a truly native, truly cr

Splits test files into multiple groups to run tests in parallel nodes

split-test split-test splits tests into multiple groups based on timing data to run tests in parallel. Installation Download binary from GitHub releas

Hitbox is an asynchronous caching framework supporting multiple backends and suitable for distributed and for single-machine applications.

Hitbox is an asynchronous caching framework supporting multiple backends and suitable for distributed and for single-machine applications.

Owner
Matthias Petri
Matthias Petri
A fusion of OTP lib/dialyzer + lib/compiler for regular Erlang with type inference

Typed ERLC The Problem I have a dream, that one day there will be an Erlang compiler, which will generate high quality type-correct code from deduced

Dmytro Lytovchenko 35 Sep 5, 2022
Fusion Reactor for Rust - Atom Rust IDE

токамак Fusion Reactor for Rust - Syntax highlighting Creating Cargo project Support for Cargo projects Code Completion with Racer Managing Rust toolc

Theo M. Bulut 405 Apr 15, 2022
Combine simple building blocks to create smooth cameras: first-person, chase, orbit, look-at, you name it!

?? dolly Combine simple building blocks to create smooth cameras: first-person, chase, orbit, look-at, you name it! Camera rigs made with dolly are en

Tomasz Stachowiak 260 Sep 22, 2022
Combine internet connections, increase your download speed

dispatch A SOCKS proxy that balances traffic between network interfaces. Should work on macOS, Windows, and Linux. Only tested on macOS for now. This

Alexandre Kirszenberg 65 Sep 24, 2022
Let's combine wasi-nn and witx-bindgen and see how it goes!

WASI-NN Experiment (API Docs) Experiments with wasmtime, the wasi-nn proposal, and tract. Getting Started To use this experiment, you will first need

Hammer of the Gods 4 Aug 30, 2022
Help Skelly to find bones, combine them to build his body back

Bones Collector Help Skelly to find bones, combine them to build his body back! Game made for the bevy Jam#2. Play it here in your browser: itch.io! R

Thomas 3 Aug 30, 2022
🍋: A General Lock following paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method"

Optimistic Lock Coupling from paper "Optimistic Lock Coupling: A Scalable and Efficient General-Purpose Synchronization Method" In actual projects, th

LemonHX 21 Jul 25, 2022
An efficient method of heaplessly converting numbers into their string representations, storing the representation within a reusable byte array.

NumToA #![no_std] Compatible with Zero Heap Allocations The standard library provides a convenient method of converting numbers into strings, but thes

Michael Murphy 42 Sep 6, 2022
This crate implements an array_chunks method for iterators

This crate implements an array_chunks method for iterators. It behaves like [slice::array_chunks] but works with any [Iterator] type. Several nightly

kangalioo 1 Jan 24, 2022
A flexible, stateless implementation of the bisection method

Flexibility is achieved by giving the user of this crate control over the input and output types

Martijn Gribnau 1 May 13, 2022