reqsketch 0.1.2

Relative Error Quantiles sketch
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#[cfg(test)]
mod tests {
    use crate::*;

    #[test]
    fn test_rank_method_specific_values() -> Result<()> {
        let mut sketch = ReqSketch::new();
        let n = 50_000;

        // Build the same sketch as our failing case
        for i in 0..n {
            sketch.update(i as f64);
        }

        // Test the specific failing case
        let rank = 0.95;
        let true_quantile = rank * (n - 1) as f64; // 47499.0

        let estimated_rank = sketch.rank(&true_quantile, SearchCriteria::Inclusive)?;

        // Test bounds compliance
        let lower = sketch.get_rank_lower_bound(rank, 3);
        let upper = sketch.get_rank_upper_bound(rank, 3);
        let within_bounds = estimated_rank >= lower && estimated_rank <= upper;

        // Test multiple problematic values
        let problem_cases = [
            (0.6, 0.6 * (n - 1) as f64),
            (0.75, 0.75 * (n - 1) as f64),
            (0.8, 0.8 * (n - 1) as f64),
            (0.95, 0.95 * (n - 1) as f64),
            (0.99, 0.99 * (n - 1) as f64),
        ];

        for (target_rank, quantile_value) in problem_cases {
            let estimated = sketch.rank(&quantile_value, SearchCriteria::Inclusive)?;
            let error_pct = (estimated - target_rank).abs() / target_rank * 100.0;

            // Allow reasonable error for REQ sketches
            assert!(error_pct < 50.0);
        }

        // Basic sanity check that some bounds work
        assert!(within_bounds || estimated_rank >= 0.0 && estimated_rank <= 1.0);

        Ok(())
    }

    #[test]
    fn test_rank_edge_cases() -> Result<()> {
        let mut sketch = ReqSketch::new();
        for i in 0..1000 {
            sketch.update(i as f64);
        }

        // Test boundary values
        let min_value = 0.0;
        let max_value = 999.0;
        let mid_value = 499.5;

        let rank_min = sketch.rank(&min_value, SearchCriteria::Inclusive)?;
        let rank_max = sketch.rank(&max_value, SearchCriteria::Inclusive)?;
        let rank_mid = sketch.rank(&mid_value, SearchCriteria::Inclusive)?;

        // Basic sanity checks
        assert!(rank_min <= rank_mid);
        assert!(rank_mid <= rank_max);
        assert!(rank_min >= 0.0 && rank_min <= 1.0);
        assert!(rank_max >= 0.0 && rank_max <= 1.0);

        Ok(())
    }

    #[test]
    fn test_rank_search_criteria() -> Result<()> {
        let mut sketch = ReqSketch::new();
        for i in 0..1000 {
            sketch.update(i as f64);
        }

        let test_values = [100.0, 250.0, 500.0, 750.0];

        for &val in &test_values {
            let inclusive_rank = sketch.rank(&val, SearchCriteria::Inclusive)?;
            let exclusive_rank = sketch.rank(&val, SearchCriteria::Exclusive)?;

            // Exclusive should be <= Inclusive
            assert!(exclusive_rank <= inclusive_rank);

            // Both should be in [0, 1]
            assert!(inclusive_rank >= 0.0 && inclusive_rank <= 1.0);
            assert!(exclusive_rank >= 0.0 && exclusive_rank <= 1.0);
        }

        Ok(())
    }

    #[test]
    fn test_rank_consistency() -> Result<()> {
        // Test that rank calculation is internally consistent
        let mut sketch = ReqSketch::new();
        for i in 0..10_000 {
            sketch.update(i as f64);
        }

        // Test that higher values get higher ranks
        let values = [1000.0, 3000.0, 5000.0, 7000.0, 9000.0];
        let mut prev_rank = 0.0;

        for value in values {
            let rank = sketch.rank(&value, SearchCriteria::Inclusive)?;

            assert!(rank >= prev_rank);
            prev_rank = rank;
        }

        // Test round-trip consistency (rank -> quantile -> rank)
        let test_ranks = [0.1, 0.25, 0.5, 0.75, 0.9];
        for target_rank in test_ranks {
            let quantile = sketch.quantile(target_rank, SearchCriteria::Inclusive)?;
            let recovered_rank = sketch.rank(&quantile, SearchCriteria::Inclusive)?;

            let error = (recovered_rank - target_rank).abs() / target_rank;

            // Allow some error due to discretization, but should be reasonable
            assert!(error < 0.2);
        }

        Ok(())
    }
}