\begin{algorithm}[!ht]\caption{Dynamic KDE, query part}\label{alg:dynamic_KDE_query}
\begin{algorithmic}[1]
\State {\bf data structure} \textsc{DynamicKDE} \Comment{Theorem~\ref{thm:main_result}}
\State
 
\Procedure{\textsc{Query}}{$q\in \mathbb{R}^d, \epsilon \in (0,1),f_{\mathsf{KDE}} \in [0,1]$} 
 
    \For{$a=1,2,\cdots,K_1$}\label{lin:first_loop}
        \For{$r=1,2,\cdots,R$}\label{lin:second_loop}
            \State $\mathcal{H}_{a,r}.\textsc{Recover}(q)$\label{lin:evaluate_recover}
            \State $\mathcal{S} \leftarrow \mathcal{S} \cup (\mathcal{H}_{a,r}.\mathcal{R}\cap L_r) $\label{lin:choose_L_j_point}
        \EndFor\label{lin:end_second_loop}
        \State $\mathcal{R}_{R+1}\leftarrow$ recover points in $L_{R+1}\cap\tilde{P}_{a}$\label{lin:recover_point_J+1} \Comment{Recover by calculating $w$ directly.}
        \State $\mathcal{S} \leftarrow \mathcal{S}\cup\mathcal{R}_{R+1}$\label{lin:add_point_to_S}
        \For{$x_{i}\in \mathcal{S}$} \label{lin:third_loop} 
            \State $w_{i}\leftarrow f(x_{i},q)$
            \If{$x_{i}\in L_{r}$ for some $r\in[R]$}
                \State $p_{i}\leftarrow\min\{ \frac{1}{2^{r} n f_{\mathsf{KDE}} },1\}$
            \ElsIf{$x_{i} \in X \setminus \bigcup_{ r \in [R] } L_{r}$}
                \State $p_{i}\leftarrow\frac{1}{n}$
            \EndIf
        \EndFor\label{lin:end_third_loop}
        \State $T_{a}\leftarrow\sum_{x_{i}\in\mathcal{S}}\frac{w_i}{p_i}$ \label{lin:output_Z_a}
    \EndFor
    \State \Return $\mathrm{Median}\{T_{a}\}$
\EndProcedure
\State {\bf end data structure}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!ht]
\caption{Dynamic KDE, query part}\begin{algorithmic}
[1]
\State {\bf data structure} \textsc{DynamicKDE} \Comment{Theorem~\ref{thm:main_result}}
\State
\Procedure{\textsc{Query}}{$q\in \mathbb{R}^d, \epsilon \in (0,1),f_{\mathsf{KDE}} \in [0,1]$}
\For{$a=1,2,\cdots,K_1$} \For{$r=1,2,\cdots,R$} \State $\mathcal{H}_{a,r}.\textsc{Recover}(q)$ \State $\mathcal{S} \leftarrow \mathcal{S} \cup (\mathcal{H}_{a,r}.\mathcal{R}\cap L_r) $ \EndFor \State $\mathcal{R}_{R+1}\leftarrow$ recover points in $L_{R+1}\cap\tilde{P}_{a}$\Comment{Recover by calculating $w$ directly.}
\State $\mathcal{S} \leftarrow \mathcal{S}\cup\mathcal{R}_{R+1}$ \For{$x_{i}\in \mathcal{S}$} \State $w_{i}\leftarrow f(x_{i},q)$
\If{$x_{i}\in L_{r}$ for some $r\in[R]$}
\State $p_{i}\leftarrow\min\{ \frac{1}{2^{r} n f_{\mathsf{KDE}} },1\}$
\ElsIf{$x_{i} \in X \setminus \bigcup_{ r \in [R] } L_{r}$}
\State $p_{i}\leftarrow\frac{1}{n}$
\EndIf
\EndFor \State $T_{a}\leftarrow\sum_{x_{i}\in\mathcal{S}}\frac{w_i}{p_i}$ \EndFor
\State \Return $\mathrm{Median}\{T_{a}\}$
\EndProcedure
\State {\bf end data structure}
\end{algorithmic}
\end{algorithm}
{
    "title": "dynamic maintenance of kernel density estimation data structure: from   practice to theory",
    "id": "2208.03915",
    "abstract": "kernel density estimation (kde) stands out as a challenging task in machine learning. the problem is defined in the following way: given a kernel function $f(x,y)$ and a set of points $\\{x_1, x_2, \\cdots, x_n \\} \\subset \\mathbb{r}^d$, we would like to compute $\\frac{1}{n}\\sum_{i=1}^{n} f(x_i,y)$ for any query point $y \\in \\mathbb{r}^d$. recently, there has been a growing trend of using data structures for efficient kde. however, the proposed kde data structures focus on static settings. the robustness of kde data structures over dynamic changing data distributions is not addressed. in this work, we focus on the dynamic maintenance of kde data structures with robustness to adversarial queries. especially, we provide a theoretical framework of kde data structures. in our framework, the kde data structures only require subquadratic spaces. moreover, our data structure supports the dynamic update of the dataset in sublinear time. furthermore, we can perform adaptive queries with the potential adversary in sublinear time.",
    "categories": "cs.lg stat.ml",
    "doi": "",
    "created": "2022-08-08",
    "updated": "2024-02-13",
    "authors": [
        "jiehao liang",
        "zhao song",
        "zhaozhuo xu",
        "junze yin",
        "danyang zhuo"
    ],
    "affiliation": [],
    "url": "https://arxiv.org/abs/2208.03915"
}
{
    "ToxicityFilter": {
        "text_to_toxicity_attributes": {
            "preli.tex": {
                "toxicity_score": 0.00609454,
                "severe_toxicity_score": 0.0007247925,
                "identity_attack_score": 0.0016834025,
                "insult_score": 0.0062493687,
                "profanity_score": 0.012073003,
                "threat_score": 0.0064532873,
                "sexually_explicit_score": 0.009200439,
                "flirtation_score": 0.29065508
            },
            "app_adversary.tex": {
                "toxicity_score": 0.017718147,
                "severe_toxicity_score": 0.001821518,
                "identity_attack_score": 0.003311308,
                "insult_score": 0.00806388,
                "profanity_score": 0.016616182,
                "threat_score": 0.008323951,
                "sexually_explicit_score": 0.016159745,
                "flirtation_score": 0.24439204
            },
            "app_correctness.tex": {
                "toxicity_score": 0.0066600125,
                "severe_toxicity_score": 0.0005531311,
                "identity_attack_score": 0.0016464046,
                "insult_score": 0.00647737,
                "profanity_score": 0.010962827,
                "threat_score": 0.0063238298,
                "sexually_explicit_score": 0.0064285113,
                "flirtation_score": 0.25106943
            },
            "app_data.tex": {
                "toxicity_score": 0.01017851,
                "severe_toxicity_score": 0.0010347366,
                "identity_attack_score": 0.003884775,
                "insult_score": 0.007009373,
                "profanity_score": 0.0138151245,
                "threat_score": 0.007573096,
                "sexually_explicit_score": 0.011441571,
                "flirtation_score": 0.18818803
            },
            "conclusion.tex": {
                "toxicity_score": 0.007979449,
                "severe_toxicity_score": 0.0006580353,
                "identity_attack_score": 0.001655654,
                "insult_score": 0.0067623714,
                "profanity_score": 0.012517073,
                "threat_score": 0.006382086,
                "sexually_explicit_score": 0.008256803,
                "flirtation_score": 0.26385543
            },
            "abstract.tex": {
                "toxicity_score": 0.014450971,
                "severe_toxicity_score": 0.00089645386,
                "identity_attack_score": 0.00414376,
                "insult_score": 0.008367881,
                "profanity_score": 0.013371054,
                "threat_score": 0.0074565844,
                "sexually_explicit_score": 0.008197826,
                "flirtation_score": 0.14363346
            },
            "app_preli.tex": {
                "toxicity_score": 0.009236055,
                "severe_toxicity_score": 0.0010347366,
                "identity_attack_score": 0.0030523231,
                "insult_score": 0.0069048726,
                "profanity_score": 0.014088398,
                "threat_score": 0.007365964,
                "sexually_explicit_score": 0.010792822,
                "flirtation_score": 0.38172203
            },
            "adversary.tex": {
                "toxicity_score": 0.033806015,
                "severe_toxicity_score": 0.0017356873,
                "identity_attack_score": 0.0065856185,
                "insult_score": 0.010476895,
                "profanity_score": 0.018187506,
                "threat_score": 0.011249693,
                "sexually_explicit_score": 0.018164968,
                "flirtation_score": 0.30483255
            },
            "app_lipschitz.tex": {
                "toxicity_score": 0.010429831,
                "severe_toxicity_score": 0.0018596649,
                "identity_attack_score": 0.0013226734,
                "insult_score": 0.007341875,
                "profanity_score": 0.02071529,
                "threat_score": 0.0060325502,
                "sexually_explicit_score": 0.020759964,
                "flirtation_score": 0.67361206
            },
            "main.tex": {
                "toxicity_score": 0.022256956,
                "severe_toxicity_score": 0.0015354156,
                "identity_attack_score": 0.0055496786,
                "insult_score": 0.010172892,
                "profanity_score": 0.01982715,
                "threat_score": 0.008738215,
                "sexually_explicit_score": 0.012621114,
                "flirtation_score": 0.25408843
            },
            "correctness.tex": {
                "toxicity_score": 0.009738698,
                "severe_toxicity_score": 0.0007009506,
                "identity_attack_score": 0.0026083488,
                "insult_score": 0.0072848746,
                "profanity_score": 0.012141321,
                "threat_score": 0.006757513,
                "sexually_explicit_score": 0.007961918,
                "flirtation_score": 0.33721492
            },
            "intro.tex": {
                "toxicity_score": 0.006942749,
                "severe_toxicity_score": 0.0007390976,
                "identity_attack_score": 0.0022753682,
                "insult_score": 0.0064488696,
                "profanity_score": 0.012687869,
                "threat_score": 0.0066798385,
                "sexually_explicit_score": 0.009554301,
                "flirtation_score": 0.2300378
            },
            "main.bbl": {
                "toxicity_score": 0.01646154,
                "severe_toxicity_score": 0.0016784668,
                "identity_attack_score": 0.0030523231,
                "insult_score": 0.00808288,
                "profanity_score": 0.01941724,
                "threat_score": 0.008129764,
                "sexually_explicit_score": 0.01710338,
                "flirtation_score": 0.283342
            },
            "technical.tex": {
                "toxicity_score": 0.0033614214,
                "severe_toxicity_score": 0.0004029274,
                "identity_attack_score": 0.0008786991,
                "insult_score": 0.005726865,
                "profanity_score": 0.00997221,
                "threat_score": 0.0057347976,
                "sexually_explicit_score": 0.005337434,
                "flirtation_score": 0.30908814
            },
            "app_technical.tex": {
                "toxicity_score": 0.009864358,
                "severe_toxicity_score": 0.0012493134,
                "identity_attack_score": 0.0027933381,
                "insult_score": 0.0072658747,
                "profanity_score": 0.014532468,
                "threat_score": 0.0070552654,
                "sexually_explicit_score": 0.0108517995,
                "flirtation_score": 0.22984806
            },
            "ref.bib": {
                "toxicity_score": 0.013445686,
                "severe_toxicity_score": 0.0014781952,
                "identity_attack_score": 0.0024048607,
                "insult_score": 0.0081208795,
                "profanity_score": 0.016616182,
                "threat_score": 0.007068211,
                "sexually_explicit_score": 0.012857023,
                "flirtation_score": 0.40251273
            },
            "data.tex": {
                "toxicity_score": 0.011812098,
                "severe_toxicity_score": 0.0011491776,
                "identity_attack_score": 0.0044582416,
                "insult_score": 0.0074368757,
                "profanity_score": 0.014669105,
                "threat_score": 0.007883795,
                "sexually_explicit_score": 0.012916001,
                "flirtation_score": 0.23941755
            }
        },
        "reason": null
    }
}
{
    "num_done": {
        "figure": 0,
        "algorithm": 3,
        "plot": 0
    }
}
{
    "NonTrivialRenderingFilter": {
        "white_pixels_ratio": 94.26365480793542,
        "hash": "041f8f1f878fbf1f",
        "most_frequent_color_ratio": 94.26365480793542
    }
}