A temporal kd-tree is a data-structure for storing a set of space-time points such that spatial nearest-neighbor queries can be answered efficiently for varying time-intervals. A temporal kd-tree is an instance of a temporal space-partitioning tree, a general technique for converting a space-partitioning tree to its temporal version by fractional cascading.