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 › A hybrid split strategy for k-d-tree based access structures

Publication

A hybrid split strategy for k-d-tree based access structures

Henrich, Andreas (2025): A hybrid split strategy for k-d-tree based access structures, in: Bamberg: Otto-Friedrich-Universität, S. 1–8.

Details

Faculty/Chair
Faculty/Professorship
Author
Publisher Information
Otto-Friedrich-Universität : Bamberg
Year of publication
2025
Source/Other editions
Shashi Shekhar und Patrick Bergougnoux (Hrsg.), GIS ’96 : Proceedings of the 4th ACM international workshop on Advances in geographic information systems, New York: ACM, 1996, S. 1–8, ISBN: 978-0-89791-874-9
Year of first publication
1996
Language
English
Licence
URN
Abstract

With spatial access structures the split strategy determining how the objects stored in an overflowing bucket are distributed over two buckets. is crucial for the performance and robustness. Two categories of split strategies can be distinguished: Data dependent split strategies depend only on the objects stored in the bucket to be split. Distribution dependent split strategies choose the split dimension and the split position independently of the objects actually stored in the bucket to be split based on an hypothesis about the object distribution. Unfortunately both types of split strategies have specific drawbacks. For a distribution dependent split strategy a sound hypothesis for the spatial distribution of the objects is needed in advance and with data dependent split strategies the directory tree becomes extremely unbalanced for insertions in a geometrically presorted order. In this paper we present a hybrid split strategy which tries to combine the advantages of both types of split strategies. Normally it adapts the behavior of a data dependent split strategy, but when the risk of a degeneration of the access structure is detected, it mutates to a distribution dependent split strategy. We will show that this hybrid split strategy is robust with respect to skew distributions and with respect to insertions in presorted order.

Keywords
hybrid split strategy
Type
Conferenceobject
URI
Activation date
2025-11-10

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

Data as of: 2026-11-15

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