Distributed k-d trees§
Enrico Nardelli · 2003
In this paper we present a generalization of the k-d tree data structure suitable for an efficient management and querying in a distributed framework. We present optimal searching algorithm for exact, partial, and range search queries. Optimality is in the sense that (1) only servers that could have k-dimensional points related to a query reply to it and that (2) the client issuing the query can deterministically know when the search is complete. The set of k-d points is managed in a scalable way, i.e. it can be dynamically enlarged with insertion of new points. We consider distributed environments where multicast (i.e. restricted broadcast) is allowed but show how to use it only when necessary. Key words and phrases: distributed data structure, multi-dimensional data, k-d-tree, multicast. 1.