tradeoff – VIBE: Vector Index Benchmark for Embeddings

To inspect the tradeoffs between recall and throughput, select a dataset and a value of \(k\). Then, using the legend below, select the algorithms you are interested in.

db = DuckDBClient.of({
    summary: FileAttachment("results/summary.parquet"),
  algorithm_basics: {file: FileAttachment("algorithms_basics.csv"), header: true}
});
alldata = db.sql`select * from summary;`
algorithms = db.sql`
    select distinct algorithm
    from summary natural join algorithm_basics
    where is_gpu = ${gpu_algorithms}
    order by all;
`
datasets = db.sql`
    select distinct dataset
    from summary
    where dataset not like '%-id-%'
    order by dataset;
`

palette = Array.from(d3["schemeTableau10"]);
ncolors = palette.length;

mutable_non_gpu_color_map = new Mutable(new Map([
    ["lorann", palette[0]],
    ["glass", palette[1]],
    ["symphonyqg", palette[2]],
]));
non_gpu_color_map = mutable_non_gpu_color_map.generator

mutable_gpu_color_map = new Mutable(new Map([
    ["cuvs-cagra", palette[0]],
    ["faiss-gpu-ivf", palette[1]],
    ["ggnn", palette[2]],
]));
gpu_color_map = mutable_gpu_color_map.generator

color_map = gpu_algorithms ? gpu_color_map : non_gpu_color_map

viewof selected_dataset = Inputs.select(
    datasets.map(d => d.dataset),
    {value: "landmark-nomic-768-normalized", label: "select dataset"}
);
k_values = db.sql`select distinct k from summary;`
viewof k_value = Inputs.select(k_values.map(d => d.k), {value: 10, label: "value of k"});

d3.select("#legend")
    .selectAll("div")
    .data(algorithms)
    .join("div")
    .style("border-bottom", d => `solid 6px ${(color_map.has(d.algorithm))? color_map.get(d.algorithm) : "lightgray"}`)
    .style("border-top", "solid 1px lightgray")
    .style("border-left", "solid 1px lightgray")
    .style("border-right", "solid 1px lightgray")
    .style("border-radius", "4px")
    .style("padding-right", "5pt")
    .style("padding-left", "5pt")
    .on("click", (event, d)=> {
        const key = d.algorithm;
        let cm = new Map(color_map);
        console.log("Algorithm " + key);
        if (cm.has(key)) {
            cm.delete(key);
        } else {
            const usedColors = new Set(cm.values());
            const color = palette.find(color => !usedColors.has(color));
            if (color !== undefined) {
                cm.set(key, color);
            }
        }
        if (gpu_algorithms) {
            mutable_gpu_color_map.value = cm;
        } else {
            mutable_non_gpu_color_map.value = cm;
        }
        console.log(color_map);
        console.log(event.target);
    })
    .text(d => d.algorithm);

Algorithm type

viewof gpu_algorithms = {
    const control = html`
        <div class="form-check form-switch d-flex align-items-center gap-2">
            <input class="form-check-input mt-0" type="checkbox" role="switch" id="gpu-algorithms-toggle">
            <label class="form-check-label" for="gpu-algorithms-toggle">GPU algorithms</label>
        </div>
    `;
    const toggle = control.querySelector("input");
    Object.defineProperty(control, "value", {get: () => toggle.checked});
    return control;
}

Algorithms

html`
<div class="algorithm-list-content">
    <p>Select up to ${ncolors} algorithms to highlight them in the plot.</p>
    <div id="legend" style="display: flex; flex-direction: row; flex-wrap: wrap; gap: 4pt;">
    </div>
</div>
`

pareto = db.sql`WITH
filtered_summary AS (
    SELECT *
    FROM summary natural left join algorithm_basics
    WHERE is_gpu = ${gpu_algorithms}
),
ranked_points AS (
    SELECT
        algorithm, dataset, params, qps, recall,
        ROW_NUMBER() OVER (PARTITION BY algorithm, dataset ORDER BY qps) AS rank_qps,
        ROW_NUMBER() OVER (PARTITION BY algorithm, dataset ORDER BY recall) AS rank_recall
    FROM filtered_summary
    where dataset = ${selected_dataset} and k = ${k_value}
),
non_dominated AS (
    SELECT
        r1.algorithm, r1.dataset, r1.params, r1.qps, r1.recall
    FROM ranked_points r1
    LEFT JOIN ranked_points r2
    ON r1.algorithm = r2.algorithm
    AND r1.dataset = r2.dataset
    AND ((r1.rank_qps < r2.rank_qps AND r1.rank_recall <= r2.rank_recall) OR
         (r1.rank_qps <= r2.rank_qps AND r1.rank_recall < r2.rank_recall))
    WHERE r2.recall IS NULL -- no dominating point
)
SELECT * FROM non_dominated;
`
highlighted = pareto.filter(d => color_map.has(d.algorithm));
background = pareto.filter(d => !color_map.has(d.algorithm));

Tradeoff between quality (recall) and efficiency (queries per second)

viewof paretoplot = Plot.plot({
    style: {fontSize: "10pt"},
  x: {domain: [0, 1], grid: true},
  y: {type: "log", grid: true},
  marks: [
        Plot.ruleY([1]),
        Plot.ruleX([0]),
        Plot.line(background, {
              x: "recall",
              y: "qps",
              stroke: "lightgray",
              z: "algorithm",
              marker: "circle-stroke",
              tip: false
        }),
        Plot.line(highlighted, {
              x: "recall",
              y: "qps",
              stroke: (d) => color_map.get(d.algorithm),
              z: "algorithm",
              marker: "circle-stroke",
              tip: false
        }),
      Plot.ruleX(background, Plot.pointerX({x: "recall", py: "qps", stroke: "red"}))
  ]
})

dynamic_recall_threshold = (paretoplot)? paretoplot.recall : null;
rankdata = db.sql`
    SELECT dataset, algorithm, k, max(qps) as qps
    FROM summary natural left join algorithm_basics
    WHERE recall > ${dynamic_recall_threshold}
    AND dataset = ${selected_dataset}
    AND is_gpu = ${gpu_algorithms}
    GROUP BY dataset, algorithm, k
`
half = d3.max(rankdata, d => d.qps) / 2
console.log(half)

Ranking of algorithms at recall higher than the selected threshold

Plot.plot({
    style: {fontSize: "12pt"},
    marginLeft: 180,
    marks: [
        Plot.ruleY([0]),
        Plot.barX(rankdata, {
            y: "algorithm",
            x: "qps",
            fill: d => color_map.has(d.algorithm)? color_map.get(d.algorithm) : "gray",
            sort: {y: "-x"}
        }),
        Plot.text(rankdata.filter(d => d.qps < half), {
            y: "algorithm",
            x: "qps",
            text: d => d3.format(".0f")(d.qps) + " qps",
            dx: 10,
            textAnchor: "start",
            fill: "black"
        }),
        Plot.text(rankdata.filter(d => d.qps >= half), {
            y: "algorithm",
            x: "qps",
            text: d => d3.format(".0f")(d.qps) + " qps",
            dx: -10,
            textAnchor: "end",
            fill: "white"
        })
    ]
})