September
2005
Variable KD-Tree Algorithms for Efficient Spatial Pattern Search
Authors:
Abstract:
In this paper we consider the problem of finding sets of points that conform to a given underlying model from within a dense, noisy set of observations. This problem is motivated by the task of efficiently linking faint asteroid detections, but is applicable to a range of spatial queries. We survey current tree-based approaches, showing a trade-off exists between single tree and multiple tree algorithms. To this end, we present a new type of multiple tree algorithm that uses a variable number of trees to exploit the advantages of both approaches. We empirically show that this algorithm performs well using both simulated and astronomical data.
copied = false, 2000);
">
@techreport{Kubica-2005-9294,
author = {Jeremy Martin Kubica And Joseph Masiero And Andrew Moore And Robert Jedicke And Andrew J. Connolly},
title = {Variable KD-Tree Algorithms for Efficient Spatial Pattern Search},
year = {2005},
month = {September},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-05-43},
}
author = {Jeremy Martin Kubica And Joseph Masiero And Andrew Moore And Robert Jedicke And Andrew J. Connolly},
title = {Variable KD-Tree Algorithms for Efficient Spatial Pattern Search},
year = {2005},
month = {September},
institute = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-05-43},
}