[
    {
        "id": "osp-18471",
        "type": "article-journal",
        "title": "BetweenCut: Private Heavy-Node Classification with Doubly Logarithmic Error in Tree Height",
        "author": [
            {
                "family": "Bao",
                "given": "Ergute"
            },
            {
                "family": "Cormode",
                "given": "Graham"
            },
            {
                "family": "Xiao",
                "given": "Xiaokui"
            },
            {
                "family": "Yu",
                "given": "Ting"
            }
        ],
        "URL": "https://omanscience.com/ar/articles/betweencut-private-heavy-node-classification-with-doubly-logarithmic-error-in-tree-height",
        "language": "en",
        "issued": {
            "date-parts": [
                [
                    2026
                ]
            ]
        },
        "abstract": "Finding heavy nodes in a tree---those whose counts exceed a given threshold---is a building block for analysis and learning over structured data. Achieving record-level differential privacy (DP) without sacrificing accuracy is challenging because each record contributes to counts along an entire root-to-leaf path, allowing privacy costs to accumulate across levels. Existing methods account for the multiple threshold comparisons for each record incur additive error margins of $Ω_{\\varepsilon,δ}(\\log h)$ or $Ω_{\\varepsilon,δ}(\\sqrt{\\log h})$ for tree height $h$. We introduce \\textsc{BetweenCut}, an $(\\varepsilon,δ)$-DP algorithm with an additive error margin of $O_{\\varepsilon,δ}(\\log\\log h)$, improving the existing bounds for deep trees. This error holds simultaneously for all nodes and is independent of the input database size."
    }
]