Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery
by Jeremy Kubica, Joseph Masiero, Andrew Moore, Robert Jedicke and Andrew Connolly
BibTeX:
@inproceedings{kubicaNIPS2005,
title = {Variable KD-Tree Algorithms for Spatial Pattern Search and Discovery},
author = {Jeremy Kubica and Joseph Masiero and Andrew Moore and Robert Jedicke and Andrew Connolly},
booktitle = {Advances in Neural Information Processing Systems 18},
editor = {Y. Weiss and B. Sch\"{o}lkopf and J. Platt},
publisher = {MIT Press},
address = {Cambridge, MA},
pages = {691--698},
year = {2006}
}
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.
- Download PDF