Buchumschlag

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Teshigawara, Kanata, Oh, Keisho, Kobayashi, Ken, Nakata, Kazuhide
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
von: Beretta, Lorenzo, et al.
Veröffentlicht: (2025)

Distance Estimation for High-Dimensional Discrete Distributions
von: Kumar, Gunjan, et al.
Veröffentlicht: (2023)

Differentially Private High-Dimensional Approximate Range Counting, Revisited
von: Aumüller, Martin, et al.
Veröffentlicht: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
von: Bilò, Davide, et al.
Veröffentlicht: (2023)

New Diameter Approximations via Distance Oracle Techniques
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2026)

Approximate Circular Pattern Matching under Edit Distance
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2024)

Data Structures for Approximate Discrete Fréchet Distance
von: van der Hoog, Ivor, et al.
Veröffentlicht: (2022)

An Approximation Algorithm for 2-Vertex-Connectivity via Cycle-Restricted 2-Edge-Covers
von: Kobayashi, Yusuke, et al.
Veröffentlicht: (2026)

Fault-Tolerant Approximate Distance Oracles with a Source Set
von: Dey, Dipan, et al.
Veröffentlicht: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
von: Kopelowitz, Tsvi, et al.
Veröffentlicht: (2023)

Improved Approximation Algorithms for Three-Dimensional Knapsack
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Additive Approximation Schemes for Low-Dimensional Embeddings
von: Anderson, Prashanti, et al.
Veröffentlicht: (2025)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
von: Mao, Xiao, et al.
Veröffentlicht: (2026)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
von: Horowicz, Noam, et al.
Veröffentlicht: (2025)

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2020)

High-Dimensional Geometric Streaming for Nearly Low Rank Data
von: Esfandiari, Hossein, et al.
Veröffentlicht: (2024)

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
von: Moretti, Simone, et al.
Veröffentlicht: (2022)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
von: Yan, Shuyi
Veröffentlicht: (2025)

Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
von: Siqueira, Gabriel, et al.
Veröffentlicht: (2025)

Forcing a unique minimum spanning tree and a unique shortest path
von: Gima, Tatsuya, et al.
Veröffentlicht: (2025)

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
von: Dinitz, Michael, et al.
Veröffentlicht: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
von: Harada, Kaito, et al.
Veröffentlicht: (2024)

FAMST: Fast Approximate Minimum Spanning Tree Construction for Large-Scale and High-Dimensional Data
von: Almansoori, Mahmood K. M., et al.
Veröffentlicht: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Data-Dependent LSH for the Earth Mover's Distance
von: Jayaram, Rajesh, et al.
Veröffentlicht: (2024)

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data
von: Munch, Elizabeth, et al.
Veröffentlicht: (2025)

Streaming Diameter of High-Dimensional Points
von: Halldórsson, Magnús M., et al.
Veröffentlicht: (2025)

Private Synthetic Graph Generation and Fused Gromov-Wasserstein Distance
von: Wirth, Leoni Carla, et al.
Veröffentlicht: (2025)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
von: Cheng, Siu-Wing, et al.
Veröffentlicht: (2025)

Towards Efficient Data Structures for Approximate Search with Range Queries
von: Kian, Ladan, et al.
Veröffentlicht: (2026)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
von: Balakrishnan, Girish, et al.
Veröffentlicht: (2023)

Faster Approximation Algorithms for k-Center via Data Reduction
von: Filtser, Arnold, et al.
Veröffentlicht: (2025)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
von: Ferragina, Paolo, et al.
Veröffentlicht: (2025)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
von: Kociumaka, Tomasz, et al.
Veröffentlicht: (2025)

Hamming Distance Oracle
von: Boneh, Itai, et al.
Veröffentlicht: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
von: Das, Debarati, et al.
Veröffentlicht: (2025)

Interpreting the Curse of Dimensionality from Distance Concentration and Manifold Effect
von: Peng, Dehua, et al.
Veröffentlicht: (2023)

Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
von: Adar, Tomer, et al.
Veröffentlicht: (2024)

Many Flavors of Edit Distance
von: Bhattacharya, Sudatta, et al.
Veröffentlicht: (2024)