Options
A hybrid split strategy for k-d-tree based access structures
Henrich, Andreas (1996): A hybrid split strategy for k-d-tree based access structures, in: Shashi Shekhar, Patrick Bergougnoux, Shashi Shekhar, u. a. (Hrsg.), GIS ’96 : Proceedings of the 4th ACM international workshop on Advances in geographic information systems, New York: ACM, S. 1–8, doi: 10.1145/258319.258323.
Author:
Title of the compilation:
GIS '96 : Proceedings of the 4th ACM international workshop on Advances in geographic information systems
Editors:
Shekhar, Shashi
Bergougnoux, Patrick
Conference:
4th ACM international workshop on Advances in geographic information systems (GIS '96), November 15-16, 1996 ; Rockville, Maryland, USA
Publisher Information:
Year of publication:
1996
Pages:
ISBN:
978-0-89791-874-9
Language:
English
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
Activation date:
July 13, 2015
Versioning
Question on publication
Permalink
https://fis.uni-bamberg.de/handle/uniba/36069