Skip to content

web search done right

16.7 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2023 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

use std::{
    collections::{BTreeMap, BTreeSet},
    sync::atomic::AtomicBool,
};

use std::sync::atomic::Ordering;

use bloom::U64BloomFilter;
use tracing::info;

use crate::{
    hyperloglog::HyperLogLog,
    kahan_sum::KahanSum,
    webgraph::{query, EdgeLimit, NodeID, Webgraph},
    webpage::html::links::RelFlags,
};

const HYPERLOGLOG_COUNTERS: usize = 64;

pub static SKIPPED_REL: std::sync::LazyLock<RelFlags> = std::sync::LazyLock::new(|| {
    RelFlags::TAG
        | RelFlags::NOFOLLOW
        | RelFlags::SPONSORED
        | RelFlags::IS_IN_FOOTER
        | RelFlags::IS_IN_NAVIGATION
        | RelFlags::PRIVACY_POLICY
        | RelFlags::TERMS_OF_SERVICE
        | RelFlags::SEARCH
        | RelFlags::LINK_TAG
        | RelFlags::SCRIPT_TAG
        | RelFlags::SAME_ICANN_DOMAIN
        | RelFlags::UGC
});

type Counter = BTreeMap<NodeID, HyperLogLog<HYPERLOGLOG_COUNTERS>>;

fn initialize(
    graph: &Webgraph,
    counters: &mut Counters,
    centralities: &mut BTreeMap<NodeID, KahanSum>,
) -> u64 {
    let mut num_nodes = 0;

    for node in graph.host_nodes() {
        let mut counter = HyperLogLog::default();
        counter.add_u128(node.as_u128());

        counters.old.insert(node, counter);
        centralities.insert(node, KahanSum::default());

        num_nodes += 1;
    }

    counters.new = counters.old.clone();

    num_nodes
}

fn update_changed_counters(
    graph: &Webgraph,
    exact_changed_nodes: &mut BTreeSet<NodeID>,
    counters: &mut Counters,
    new_changed_nodes: &mut U64BloomFilter,
) -> bool {
    let mut new_exact_changed_nodes = BTreeSet::default();
    let has_changes = AtomicBool::new(false);

    exact_changed_nodes.iter().for_each(|changed_node| {
        for edge in graph
            .search(&query::ForwardlinksQuery::new(*changed_node).with_limit(EdgeLimit::Unlimited))
            .unwrap_or_default()
            .into_iter()
            .filter(|e| !e.rel_flags.intersects(*SKIPPED_REL))
        {
            if let (Some(counter_to), Some(counter_from)) =
                (counters.new.get_mut(&edge.to), counters.old.get(&edge.from))
            {
                if counter_to
                    .registers()
                    .iter()
                    .zip(counter_from.registers().iter())
                    .any(|(to, from)| *from > *to)
                {
                    counter_to.merge(counter_from);
                    new_changed_nodes.insert_u128(edge.to.as_u128());

                    new_exact_changed_nodes.insert(edge.to);

                    has_changes.store(true, Ordering::Relaxed);
                }
            }
        }
    });

    *exact_changed_nodes = new_exact_changed_nodes;

    has_changes.load(Ordering::Relaxed)
}

fn update_all_counters(
    graph: &Webgraph,
    mut exact_changed_nodes: Option<&mut BTreeSet<NodeID>>,
    counters: &mut Counters,
    changed_nodes: &U64BloomFilter,
    new_changed_nodes: &mut U64BloomFilter,
) -> bool {
    let has_changes = AtomicBool::new(false);

    if let Some(exact_changed_nodes) = &mut exact_changed_nodes {
        **exact_changed_nodes = BTreeSet::default();
    }

    graph
        .host_edges()
        .filter(|e| !e.rel_flags.intersects(*SKIPPED_REL))
        .for_each(|edge| {
            if changed_nodes.contains_u128(edge.from.as_u128()) {
                if let (Some(counter_to), Some(counter_from)) =
                    (counters.new.get_mut(&edge.to), counters.old.get(&edge.from))
                {
                    if counter_to
                        .registers()
                        .iter()
                        .zip(counter_from.registers().iter())
                        .any(|(to, from)| *from > *to)
                    {
                        counter_to.merge(counter_from);
                        new_changed_nodes.insert_u128(edge.to.as_u128());

                        if let Some(exact_changed_nodes) = &mut exact_changed_nodes {
                            exact_changed_nodes.insert(edge.to);
                        }

                        has_changes.store(true, Ordering::Relaxed);
                    }
                }
            }
        });

    has_changes.load(Ordering::Relaxed)
}

fn update_centralities(centralities: &mut BTreeMap<NodeID, KahanSum>, counters: &Counters, t: u64) {
    centralities.iter_mut().for_each(|(node, score)| {
        *score += counters
            .new
            .get(node)
            .map(|counter| counter.size())
            .unwrap_or(1)
            .checked_sub(
                counters
                    .old
                    .get(node)
                    .map(|counter| counter.size())
                    .unwrap_or(1),
            )
            .unwrap_or_default() as f64
            / (t + 1) as f64;
    });
}

fn normalize_centralities(
    centralities: BTreeMap<NodeID, KahanSum>,
    norm_factor: f64,
) -> BTreeMap<NodeID, f64> {
    centralities
        .into_iter()
        .map(|(node_id, sum)| (node_id, f64::from(sum)))
        .filter(|(_, centrality)| *centrality > 0.0)
        .map(|(node_id, centrality)| (node_id, centrality / norm_factor))
        .map(|(node_id, centrality)| {
            if !centrality.is_finite() {
                (node_id, 0.0)
            } else {
                (node_id, centrality)
            }
        })
        .collect()
}

struct Counters {
    old: Counter,
    new: Counter,
}

impl Counters {
    fn new() -> Self {
        Self {
            old: BTreeMap::default(),
            new: BTreeMap::default(),
        }
    }

    fn step(&mut self) {
        self.old = self.new.clone();
    }
}

fn calculate_centrality(graph: &Webgraph) -> BTreeMap<NodeID, f64> {
    let mut counters = Counters::new();
    let mut centralities: BTreeMap<NodeID, KahanSum> = BTreeMap::new();

    let num_nodes = initialize(graph, &mut counters, &mut centralities);

    let mut changed_nodes = U64BloomFilter::new(num_nodes, 0.05);

    for node in graph.host_nodes() {
        changed_nodes.insert_u128(node.as_u128());
    }

    info!("Found {} nodes in the graph", num_nodes);
    let exact_counting_threshold = (num_nodes as f64).sqrt().max(0.0).round() as u64;
    let norm_factor = (num_nodes - 1) as f64;

    let mut exact_counting = false;
    let mut has_changes = true;
    let mut t = 0;

    let mut exact_changed_nodes: BTreeSet<NodeID> = BTreeSet::default();

    loop {
        if !has_changes {
            break;
        }

        let mut new_changed_nodes = U64BloomFilter::new(num_nodes, 0.05);

        if !exact_changed_nodes.is_empty()
            && exact_changed_nodes.len() as u64 <= exact_counting_threshold
        {
            has_changes = update_changed_counters(
                graph,
                &mut exact_changed_nodes,
                &mut counters,
                &mut new_changed_nodes,
            );
        } else if exact_counting {
            has_changes = update_all_counters(
                graph,
                Some(&mut exact_changed_nodes),
                &mut counters,
                &changed_nodes,
                &mut new_changed_nodes,
            );
        } else {
            has_changes = update_all_counters(
                graph,
                None,
                &mut counters,
                &changed_nodes,
                &mut new_changed_nodes,
            );
        }

        update_centralities(&mut centralities, &counters, t);

        counters.step();
        changed_nodes = new_changed_nodes;
        t += 1;

        if changed_nodes.estimate_card() <= exact_counting_threshold {
            exact_counting = true;
        }
    }

    let res = normalize_centralities(centralities, norm_factor);

    info!("Harmonic centrality calculated");

    res
}

pub struct HarmonicCentrality(BTreeMap<NodeID, f64>);

impl HarmonicCentrality {
    pub fn calculate(graph: &Webgraph) -> Self {
        Self(calculate_centrality(graph))
    }

    pub fn get(&self, node: &NodeID) -> Option<f64> {
        self.0.get(node).copied()
    }

    pub fn iter(&self) -> impl Iterator<Item = (&NodeID, f64)> {
        self.0.iter().map(|(node, centrality)| (node, *centrality))
    }

    pub fn len(&self) -> usize {
        self.0.len()
    }

    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

#[cfg(test)]
mod tests {
    use file_store::temp::TempDir;

    use super::*;
    use crate::{
        webgraph::{Edge, Node, Webgraph},
        webpage::html::links::RelFlags,
    };

    fn test_edges() -> Vec<(Node, Node)> {
        //     ┌────┐
        //     │    │
        // ┌───A◄─┐ │
        // │      │ │
        // ▼      │ │
        // B─────►C◄┘
        //        ▲
        //        │
        //        │
        //        D
        vec![
            (Node::from("A"), Node::from("B")),
            (Node::from("B"), Node::from("C")),
            (Node::from("A"), Node::from("C")),
            (Node::from("C"), Node::from("A")),
            (Node::from("D"), Node::from("C")),
        ]
    }

    fn test_graph() -> (Webgraph, TempDir) {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(temp_dir.as_ref().join("test"), 0u64.into())
            .open()
            .unwrap();

        for (from, to) in test_edges() {
            graph.insert(Edge::new_test(from, to)).unwrap();
        }

        graph.commit().unwrap();

        (graph, temp_dir)
    }

    #[test]
    fn host_harmonic_centrality() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(temp_dir.as_ref().join("test"), 0u64.into())
            .open()
            .unwrap();

        graph
            .insert(Edge::new_test(
                Node::from("A.com/1").into_host(),
                Node::from("A.com/2").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/1").into_host(),
                Node::from("A.com/3").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/1").into_host(),
                Node::from("A.com/4").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/2").into_host(),
                Node::from("A.com/1").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/2").into_host(),
                Node::from("A.com/3").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/2").into_host(),
                Node::from("A.com/4").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/3").into_host(),
                Node::from("A.com/1").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/3").into_host(),
                Node::from("A.com/2").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/3").into_host(),
                Node::from("A.com/4").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/4").into_host(),
                Node::from("A.com/1").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/4").into_host(),
                Node::from("A.com/2").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("A.com/4").into_host(),
                Node::from("A.com/3").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("C.com").into_host(),
                Node::from("B.com").into_host(),
            ))
            .unwrap();
        graph
            .insert(Edge::new_test(
                Node::from("D.com").into_host(),
                Node::from("B.com").into_host(),
            ))
            .unwrap();

        graph.commit().unwrap();

        let centrality = HarmonicCentrality::calculate(&graph);

        assert!(
            centrality.get(&Node::from("B.com").id()).unwrap()
                > centrality.get(&Node::from("A.com").id()).unwrap_or(0.0)
        );
    }

    #[test]
    fn harmonic_centrality() {
        let (graph, _temp_dir) = test_graph();
        let centrality = HarmonicCentrality::calculate(&graph);

        assert!(
            centrality.get(&Node::from("C").id()).unwrap()
                > centrality.get(&Node::from("A").id()).unwrap()
        );
        assert!(
            centrality.get(&Node::from("A").id()).unwrap()
                > centrality.get(&Node::from("B").id()).unwrap()
        );
        assert_eq!(centrality.get(&Node::from("D").id()), None);
    }

    #[test]
    fn additional_edges_ignored() {
        let (graph, _temp_dir) = test_graph();
        let centrality = HarmonicCentrality::calculate(&graph);

        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(temp_dir.as_ref().join("test"), 0u64.into())
            .open()
            .unwrap();

        for (from, to) in test_edges() {
            graph.insert(Edge::new_test(from, to)).unwrap();
        }

        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();
        graph
            .insert(Edge::new_test(Node::from("A"), Node::from("B")))
            .unwrap();
        graph.commit().unwrap();

        graph.optimize_read().unwrap();

        let centrality_extra = HarmonicCentrality::calculate(&graph);

        assert_eq!(centrality.0, centrality_extra.0);
    }

    #[test]
    fn test_rel_flag_ignored() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(temp_dir.as_ref().join("test"), 0u64.into())
            .open()
            .unwrap();

        for (from, to) in test_edges() {
            graph
                .insert(Edge {
                    from,
                    to,
                    rel_flags: RelFlags::TAG,
                    ..Edge::empty()
                })
                .unwrap();
        }

        graph.commit().unwrap();

        let centrality = HarmonicCentrality::calculate(&graph);

        assert!(centrality.0.values().all(|&v| v == 0.0));
    }

    #[test]
    fn test_same_icann_domain_ignored() {
        let temp_dir = crate::gen_temp_dir().unwrap();
        let mut graph = Webgraph::builder(temp_dir.as_ref().join("test"), 0u64.into())
            .open()
            .unwrap();

        for (from, to) in test_edges() {
            graph
                .insert(Edge {
                    from,
                    to,
                    rel_flags: RelFlags::SAME_ICANN_DOMAIN,
                    ..Edge::empty()
                })
                .unwrap();
        }

        graph.commit().unwrap();

        let centrality = HarmonicCentrality::calculate(&graph);

        assert!(centrality.0.values().all(|&v| v == 0.0));
    }
}