Let's look into pf_sample_set_t type.

```
typedef struct _pf_sample_set_t {
// The samples
int sample_count;
pf_sample_t *samples;
// A kdtree encoding the histogram
pf_kdtree_t *kdtree;
// Clusters
int cluster_count, cluster_max_count;
pf_cluster_t *clusters;
// Filter statistics
pf_vector_t mean;
pf_matrix_t cov;
int converged;
} pf_sample_set_t;
```

Sample particles are stored as an array hold by the pointer, `samples`

, instead of `kdtree`

.
The kdtree is for constructing weight histogram of particles.
The purposes of this histogram are to provide the number of non-empty bins for KLD-sampling and to calculate mean and covariance values from each cluster. This clustering algorithm for the kdtree histogram seems like a type of density-based clustering algorithms. Nodes connected to each other are labeled as a same cluster where connectivity is determined based on neighbor nodes. In pf_kdtree.c of amcl package, the neighbor node, `nnode`

, of a node is

```
nkey[0] = node->key[0] + (i / 9) - 1;
nkey[1] = node->key[1] + ((i % 9) / 3) - 1;
nkey[2] = node->key[2] + ((i % 9) % 3) - 1;
nnode = pf_kdtree_find_node(self, self->root, nkey);
```

where `key`

is the spatial information of a node.