Fully Dynamic Embedding into $\ell_p$ Spaces
Authors: Kiarash Banihashem, Xiang Chen, Mohammadtaghi Hajiaghayi, Sungchul Kim, Kanak Mahadik, Ryan A. Rossi, Tong Yu
ICML 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present the first fully dynamic algorithm for this problem, achieving O(log(n))2q O(log(n W))q 1 expected distortion with O(m1/q+o(1)) update time and O(q log(n) log(n W)) query time, where q 2 is an integer parameter. Our main result is the following theorem. Theorem 1.1. Let G = (V, E) be a weighted undirected graph undergoing edge insertions and deletions. For any q 2, there exists an algorithm A (see Algorithm 1) that randomly maintains an embedding function ρ : V Rℓ with the following properties: Low expected distortion and non-contractivity... In this section, we prove our main result, i.e., Theorem 1.1. |
| Researcher Affiliation | Collaboration | 1University of Maryland, College Park 2Adobe research. Correspondence to: Kiarash Banihashem <EMAIL>. |
| Pseudocode | Yes | Algorithm 1: Dynamic embedding into ℓp metric. 1 Function Init(): 2 Set k = Θ(log n) ; 3 Initialize dynamic forest embeddings T1, . . . , Tk (See Section C) and empty hash tables H1, . . . , Hk; 4 Function Update(u): // Insertion or Deletion 5 for i [k] do 6 (Vadd, Vremove, ) Update(Ti, u) // Forward to Ti and store new and deleted vertices in Ti 7 for each v in Vremove do 8 Remove (v, γv) from Hi; 9 for each v in Vadd do 10 Sample γv uniformly at random from {1, 2}; 11 Add (v, γv) to Hi; 12 Function Query(u): 13 for i [k] do 14 p u, ρi(u) 0; 15 while p / root(Ti) do 16 Retrieve γp from Hi; 17 ρi(u) ρi(u) + w Ti(p, parent Ti(p)) γp; 18 p parent Ti(p); 19 ρi(u) ρi(u) + W γp ; 20 return ρ(u) = (ρ1(u), . . . , ρk(u)) |
| Open Source Code | No | The paper does not provide any statements about code availability or links to repositories for the methodology described. |
| Open Datasets | No | The paper describes a theoretical algorithm for dynamic embedding into ℓp spaces and does not use or reference any specific public datasets for experimental evaluation. |
| Dataset Splits | No | The paper focuses on theoretical algorithm design and analysis, and therefore does not involve empirical evaluation with dataset splits. |
| Hardware Specification | No | The paper presents a theoretical algorithm and its analysis; it does not describe experimental results that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical, focusing on algorithm design and proofs, and does not provide details on software dependencies or specific version numbers. |
| Experiment Setup | No | The paper is a theoretical work presenting an algorithm and its analysis, and therefore does not include details about experimental setup, hyperparameters, or training configurations. |