Cover Image

The Kinetic Hourglass Data Structure for Computing the Bottleneck Distance of Dynamic Data

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Munch, Elizabeth, Wang, Elena Xinyi, Wenk, Carola
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance
by: Chambers, Erin Wolf, et al.
Published: (2024)

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck
by: Kuszmaul, William, et al.
Published: (2025)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Data Structures for Approximate Discrete Fréchet Distance
by: van der Hoog, Ivor, et al.
Published: (2022)

Zip-Tries: Simple Dynamic Data Structures for Strings
by: Eppstein, David, et al.
Published: (2025)

Kd-tree Based Wasserstein Distance Approximation for High-Dimensional Data
by: Teshigawara, Kanata, et al.
Published: (2026)

Succinct Data Structures for Segments
by: Bille, Philip, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

Fully Dynamic Algorithms for Chamfer Distance
by: Goranci, Gramoz, et al.
Published: (2025)

Hardness of Dynamic Tree Edit Distance and Friends
by: Hu, Bingbing, et al.
Published: (2025)

On Competitiveness of Dynamic Replication for Distributed Data Access
by: Zuo, Tianyu, et al.
Published: (2025)

Succinct Data Structures for Baxter Permutation and Related Families
by: Chakraborty, Sankardeep, et al.
Published: (2024)

Succinct Data Structure for Graphs with $d$-Dimensional $t$-Representation
by: Balakrishnan, Girish, et al.
Published: (2023)

Nearly Optimal Bounds for Computing Decision Tree Splits in Data Streams
by: Ta, Hoang, et al.
Published: (2026)

Vantage Point Selection Algorithms for Bottleneck Capacity Estimation
by: Ashvinkumar, Vikrant, et al.
Published: (2025)

Contiguous Graph Partitioning For Optimal Total Or Bottleneck Communication
by: Ahrens, Willow
Published: (2020)

A Framework for Building Data Structures from Communication Protocols
by: Andoni, Alexandr, et al.
Published: (2025)

Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
by: Ferragina, Paolo, et al.
Published: (2025)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
by: Balakrishnan, Girish, et al.
Published: (2024)

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

Towards Efficient Data Structures for Approximate Search with Range Queries
by: Kian, Ladan, et al.
Published: (2026)

Engineering Rank/Select Data Structures for Large-Alphabet Strings
by: Arroyuelo, Diego, et al.
Published: (2023)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
by: Moretti, Simone, et al.
Published: (2022)

GTA -- An ATSP Method: Shifting the Bottleneck from Algorithm to RAM
by: Nakhle, Wissam
Published: (2025)

Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
by: Chen, Lin, et al.
Published: (2026)

Structured Downsampling for Fast, Memory-efficient Curation of Online Data Streams
by: Moreno, Matthew Andres, et al.
Published: (2024)

A Modern Approach to Electoral Delimitation using the Quadtree Data Structure
by: Kale, Sahil, et al.
Published: (2024)

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations
by: Charikar, Moses, et al.
Published: (2024)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
by: Gorbachev, Egor, et al.
Published: (2024)

Computing Data Distribution from Query Selectivities
by: Agarwal, Pankaj K., et al.
Published: (2024)

Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
by: Jo, Seungbum, et al.
Published: (2022)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

Stable Tree Labelling for Accelerating Distance Queries on Dynamic Road Networks
by: Koehler, Henning, et al.
Published: (2025)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

CuckooGraph: A Scalable and Space-Time Efficient Data Structure for Large-Scale Dynamic Graphs
by: Fan, Zhuochen, et al.
Published: (2024)

An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
by: Sanaullah, Ahsan, et al.
Published: (2025)

Dual-Hierarchy Labelling: Scaling Up Distance Queries on Dynamic Road Networks
by: Farhan, Muhammad, et al.
Published: (2025)

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

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
by: Kociumaka, Tomasz, et al.
Published: (2025)