This paper introduces randomized K-dimensional binary search trees (randomized Kd-trees), a variant of K-dimensional binary trees. This data structure allows the efficient maintenance of multidimensional records for any sequence of insertions and deletions; and thus, is fully dynamic. We show that several types of associative queries are efficiently supported by randomized Kd-trees. In particular, a randomized Kd-tree with n records answers exact match queries in expected O(log n) time. Partial match queries are answered in expected O(n^{1-f(s/K)}) time, when s out of K attributes are specified, with 0 < f(s/K) < 1 a real valued function of s/K. Nearest neighbor queries are answered on-line in expected O(log n) time. Our randomized algorithms guarantee that their expected time bounds hold irrespective of the order and number of insertions and deletions.