Search Results

Documents authored by Kempf, Tobias

Artifact
Software
DOI: 10.4230/artifacts.27686
wembed-pdf/sprk

Authors: Tobias Kempf and Dennis Kobert

Abstract
Cite as

Tobias Kempf, Dennis Kobert. wembed-pdf/sprk (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27686,
   title = {{wembed-pdf/sprk}}, 
   author = {Kempf, Tobias and Kobert, Dennis},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:293dee235b22ac27188619ae7c1b50797096641e;origin=https://github.com/wembed-pdf/sprk;visit=swh:1:snp:997317f4ee3eacd190017da43f195aed7bb5a0b6;anchor=swh:1:rev:1e195eab1119aa5cf420bfb322788d53b95bf1ad}{\texttt{swh:1:dir:293dee235b22ac27188619ae7c1b50797096641e}} (visited on 2026-08-25)},
   url = {https://github.com/wembed-pdf/sprk},
   doi = {10.4230/artifacts.27686},
}
Artifact
Software
DOI: 10.4230/artifacts.27687
wembed-pdf/rembed

Authors: Tobias Kempf and Dennis Kobert

Abstract
Cite as

Tobias Kempf, Dennis Kobert. wembed-pdf/rembed (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27687,
   title = {{wembed-pdf/rembed}}, 
   author = {Kempf, Tobias and Kobert, Dennis},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:48b2e0e7921e86d574d2f7d019c422dddf8186dd;origin=https://github.com/wembed-pdf/rembed;visit=swh:1:snp:ed9f5c4277ce9a8b313691c0dec40a259ac117ea;anchor=swh:1:rev:a81b216a2a63bde3d4447e4053b4ca31081fe286}{\texttt{swh:1:dir:48b2e0e7921e86d574d2f7d019c422dddf8186dd}} (visited on 2026-08-25)},
   url = {https://github.com/wembed-pdf/rembed},
   doi = {10.4230/artifacts.27687},
}
Document
DOI: 10.4230/LIPIcs.ESA.2026.22
Benchmarking and Engineering Data Structures for Spherical Range Queries

Authors: Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf, Dennis Kobert, and Nikolai Maas

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract
Spherical range queries are a fundamental primitive for working with spatial data. Many spatial data structures have been developed to answer these queries, but choosing the optimal one for a specific application is a difficult task. This is because theoretical worst-case bounds are often overly pessimistic, and existing average-case analyses are rather restricted and hard to compare. We address this problem with two main contributions. First, we present a comprehensive evaluation of state-of-the-art spatial indices across a diverse set of benchmarks. This includes a new benchmark based on graph embeddings alongside multiple real-world datasets from the literature. Our benchmark covers instances scaling up to 10M points and ranging between 2 and 960 dimensions. Second, we introduce the Sorted-Projection Radius KD-tree (SPRK-tree), a high-performance KD-tree variant. The SPRK-tree combines aggressive subtree pruning via radius reduction, sorted projection-based leaf nodes, and careful implementation optimizations. It consistently achieves the fastest query times in almost all benchmarks, and ranks second in the few remaining cases.
Cite as

Thomas Bläsius, Jean-Pierre von der Heydt, Tobias Kempf, Dennis Kobert, and Nikolai Maas. Benchmarking and Engineering Data Structures for Spherical Range Queries. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2026.22,
  author =	{Bl\"{a}sius, Thomas and von der Heydt, Jean-Pierre and Kempf, Tobias and Kobert, Dennis and Maas, Nikolai},
  title =	{{Benchmarking and Engineering Data Structures for Spherical Range Queries}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.22},
  URN =		{urn:nbn:de:0030-drops-271585},
  doi =		{10.4230/LIPIcs.ESA.2026.22},
  annote =	{Keywords: Spherical Range Queries, Fixed-Radius Nearest Neighbor Search, Spatial Indexing, KD-tree, Benchmarking, Graph Embedding, SPRK-Tree}
}
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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact