Jump to content

Talk:K-D-B-tree

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Splitting

[edit]

"First, a region page is split along some plane to ..."

Well, how do you decide on which plane to use? — Preceding unsigned comment added by 188.60.245.15 (talk) 10:26, 21 November 2017 (UTC)[reply]

"It is important to take care in the domain and element chosen to split page by, since it is desirable to try to balance the number of points on either side of the splitting plane. In some cases, a poor choice of splitting domain can result in undesirable splits. It is also possible that a page cannot be split by a certain domain."

Algorithm (split part) doesn't specify actually how this is done, making this really a pseudo-algorithm. The splitting (and deciding where to split) is crucial and actually most important part of the algorithm, and other parts of algorithm are actually trivial. Are there some standard strategies for the KDB-trees? Histograms, or maybe having additional metadata in region pages like counts of points (at the expense of needing to update it on every insert, even if otherwise region pages and root would not require to be updated) or counters of queries (if one wants to optimize for query speed instead of storage balance)? — Preceding unsigned comment added by 188.60.245.15 (talk) 10:25, 21 November 2017 (UTC)[reply]