Search Results

Documents authored by Gæde, Emil Toftegaard

Artifact
Software
DOI: 10.4230/artifacts.24667
A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees

Authors: Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen

Abstract
Cite as

Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, Tord Stordalen. A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{impl_index,
   title = {{A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees}}, 
   author = {G{\ae}de, Emil Toftegaard and van der Hoog, Ivor and Rotenberg, Eva and Stordalen, Tord},
   note = {Software, Carlsberg Fonden CF21-0302, Villum Fonden VIL37507, Marie Skłodowska-Curie 899987, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:b8763eb0504d33beb81ee89d230a30dca8ab0b66;origin=https://github.com/Sgelet/DynamicLearnedIndex;visit=swh:1:snp:4cb5f98448fd35e1092239476b3dd4b7fa157fa9;anchor=swh:1:rev:e668899dab95046384f68723e53e0aacbad32feb}{\texttt{swh:1:dir:b8763eb0504d33beb81ee89d230a30dca8ab0b66}} (visited on 2025-10-01)},
   url = {https://github.com/Sgelet/DynamicLearnedIndex},
   doi = {10.4230/artifacts.24667},
}
Artifact
Software
DOI: 10.4230/artifacts.24668
Testbed for our learned index repository

Authors: Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen

Abstract
Cite as

Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, Tord Stordalen. Testbed for our learned index repository (Software, Test Bed). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{impl_bench,
   title = {{Testbed for our learned index repository}}, 
   author = {G{\ae}de, Emil Toftegaard and van der Hoog, Ivor and Rotenberg, Eva and Stordalen, Tord},
   note = {Software, Carlsberg Fonden CF21-0302, Villum Fonden VIL37507, Marie Skłodowska-Curie 899987, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:07ea25cfc176438933c1a5507bfdad3ba9461ab6;origin=https://github.com/Sgelet/LearnedIndexBench;visit=swh:1:snp:b64d98b5a181116695f4f7960511292c6601df13;anchor=swh:1:rev:c3ad0ca2e0149fd2be070b37ba57b12a447bbf71}{\texttt{swh:1:dir:07ea25cfc176438933c1a5507bfdad3ba9461ab6}} (visited on 2025-10-01)},
   url = {https://github.com/Sgelet/LearnedIndexBench},
   doi = {10.4230/artifacts.24668},
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.64
A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees

Authors: Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Indexing data is a fundamental problem in computer science. The input is a set S of n distinct integers from a universe 𝒰. Indexing queries take a value q ∈ 𝒰 and return the membership, predecessor or rank of q in S. A range query takes two values q, r ∈ 𝒰 and returns the set S ∩ [q,r]. Recently, various papers study a special case where the the input data behaves in an approximately piece-wise linear way. Given the sorted (rank,value) pairs, and given some constant ε, one wants to maintain a small number of axis-disjoint line-segments such that, for each rank, the value is within ± ε of the corresponding line-segment. Ferragina and Vinciguerra (VLDB 2020) observe that this geometric problem is useful for solving indexing problems, particularly when the number of line-segments is small compared to the size of the dataset. We study the dynamic version of this geometric problem. In the dynamic setting, inserting or deleting just one data point may cause up to three line-segments to be merged, or one line-segment to be split at most three-way. To determine and compute this, we use techniques from dynamic maintenance of convex hulls, and provide new algorithms with worst-case guarantees, including an O(log n) algorithm to compute a separating line between two non-intersecting convex hulls - an operation previously missing from the literature. We then use our fully-dynamic geometry-based subroutine in an indexing data structure, combining it with a natural hashing technique. The resulting indexing data structure has theoretically efficient worst-case guarantees in expectation. We compare its practical performance to the solution of Ferragina and Vinciguerra, which was shown to perform better in certain structured settings [Sun, Zhou, Li VLDB 2023]. Our empirical analysis shows that our solution supports more efficient range queries in the special case where the update sequence contains many deletions.
Cite as

Emil Toftegaard Gæde, Ivor van der Hoog, Eva Rotenberg, and Tord Stordalen. A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gaede_et_al:LIPIcs.ESA.2025.64,
  author =	{G{\ae}de, Emil Toftegaard and van der Hoog, Ivor and Rotenberg, Eva and Stordalen, Tord},
  title =	{{A Dynamic Piecewise-Linear Geometric Index with Worst-Case Guarantees}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.64},
  URN =		{urn:nbn:de:0030-drops-245323},
  doi =		{10.4230/LIPIcs.ESA.2025.64},
  annote =	{Keywords: Algorithms Engineering, Data Structures, Indexing, Convex Hulls}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.13
Multilevel Skeletonization Using Local Separators

Authors: J. Andreas Bærentzen, Rasmus Emil Christensen, Emil Toftegaard Gæde, and Eva Rotenberg

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In this paper we give a new, efficient algorithm for computing curve skeletons, based on local separators. Our efficiency stems from a multilevel approach, where we solve small problems across levels of detail and combine these in order to quickly obtain a skeleton. We do this in a highly modular fashion, ensuring complete flexibility in adapting the algorithm for specific types of input or for otherwise targeting specific applications. Separator based skeletonization was first proposed by Bærentzen and Rotenberg in [ACM Tran. Graphics'21], showing high quality output at the cost of running times which become prohibitive for large inputs. Our new approach retains the high quality output, and applicability to any spatially embedded graph, while being orders of magnitude faster for all practical purposes. We test our skeletonization algorithm for efficiency and quality in practice, comparing it to local separator skeletonization on the University of Groningen Skeletonization Benchmark [Telea'16].
Cite as

J. Andreas Bærentzen, Rasmus Emil Christensen, Emil Toftegaard Gæde, and Eva Rotenberg. Multilevel Skeletonization Using Local Separators. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brentzen_et_al:LIPIcs.SoCG.2023.13,
  author =	{B{\ae}rentzen, J. Andreas and Christensen, Rasmus Emil and G{\ae}de, Emil Toftegaard and Rotenberg, Eva},
  title =	{{Multilevel Skeletonization Using Local Separators}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.13},
  URN =		{urn:nbn:de:0030-drops-178637},
  doi =		{10.4230/LIPIcs.SoCG.2023.13},
  annote =	{Keywords: Algorithm engineering, experimentation and implementation, shape skeletonization, curve skeletons, multilevel algorithm}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact