Skip to content

Read-only version: For security reasons, the Research Information System (FIS) has been temporarily replaced by this read-only version. All public content and full texts remain available; login, editing, submission and statistics are not available. Questions: fis@uni-bamberg.de

Home › Publications › Improving the performance of multi-dimensional access structures based on k-d-Trees

Publication

Improving the performance of multi-dimensional access structures based on k-d-Trees

Henrich, Andreas (2025): Improving the performance of multi-dimensional access structures based on k-d-Trees, in: Bamberg: Otto-Friedrich-Universität, S. 68–75.

Details

Faculty/Chair
Faculty/Professorship
Author
Publisher Information
Otto-Friedrich-Universität : Bamberg
Year of publication
2025
Source/Other editions
Y . Stanley (Hrsg.), Proceedings of the Twelfth International Conference on Data Engineering : February 26 - March 1, 1996, New Orleans, Louisiana (ICDE ’96), Los Alamitos, Calif. u.a.: IEEE, 1996, S. 68–75
Year of first publication
1996
Language
English
Licence
URN
Abstract

In recent years, various k-d-tree based multidimensional access structures have been proposed. All these structures share an average bucket utilization of at most ln 2/spl ap/69.3%. We present two algorithms which perform local redistributions of objects to improve the storage utilization of these access structures. We show that under fair conditions a good improvement algorithm can save up to 20% of space and up to 15% of query processing time. On the other hand we also show that a local redistribution scheme designed without care, can improve the storage utilization and at the same time worsen the performance of range queries drastically. Furthermore we show the dependencies between split strategies and local redistribution schemes and the general limitations which can be derived from these dependencies.

Keywords
k-d-Trees
Type
Conferenceobject
URI
Activation date
2025-11-10

Permalink: https://fis.uni-bamberg.de/handle/uniba/106879 · Data as JSON · Cite: BibTeX · RIS

Data as of: 2026-11-15

Restricted read-only access: login, editing and submission are temporarily disabled.