Search Results

Documents authored by Stordalen, Tord

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.SWAT.2022.18
Predecessor on the Ultra-Wide Word RAM

Authors: Philip Bille, Inge Li Gørtz, and Tord Stordalen

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w² bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures. Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.
Cite as

Philip Bille, Inge Li Gørtz, and Tord Stordalen. Predecessor on the Ultra-Wide Word RAM. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bille_et_al:LIPIcs.SWAT.2022.18,
  author =	{Bille, Philip and G{\o}rtz, Inge Li and Stordalen, Tord},
  title =	{{Predecessor on the Ultra-Wide Word RAM}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{18:1--18:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.18},
  URN =		{urn:nbn:de:0030-drops-161786},
  doi =		{10.4230/LIPIcs.SWAT.2022.18},
  annote =	{Keywords: Ultra-wide word RAM model, predecessor, word-level parallelism}
}
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