CFTree

Inserts a single pattern vector into the CFTree

true if insertion was successful

Insert a pattern vector with a specific associated pattern vector index. This method does not use periodic memory limit checks.

true if insertion was successful

Inserts an entire CFEntry into the tree. Used for tree rebuilding.

true if insertion happened without problems

Every time we split the root, we check whether the memory limit imposed on the tree has been reached. In this case, we automatically increase the distance threshold and rebuild the tree.

It is worth noting that since we only check memory consumption only during root split, and not for all node splits (for performance reasons), we cannot guarantee that the memory limit will not be exceeded. The tree may grow significantly between a root split and the next. Furthermore, the computation of memory consumption using the SizeOf class is only approximate.

Notice also that if the threshold grows to the point that all the entries fall into one entry of the root (i.e., the root is the only node in the tree, and has only one sub-cluster) the automatic rebuild cannot decrease the memory consumption (because increasing the threshold has not effect on reducing the size of the tree), and if Java runs out of memory the program will terminate.

true if rebuilt

Splits the root to accommodate a new entry. The height of the tree grows by one.

Overwrites the structure of this tree (all nodes, entreis, and leaf list) with the structure of newTree.

Computes a new threshold based on the average distance of the closest subclusters in each leaf node

the new threshold

True if CFTree's memory occupation exceeds or is almost equal to the memory limit

true if memory limit has been reached

Computes the memory usage of a CFTree

memory usage in bytes

This implementation of the rebuilding algorithm is different from the one described in Section 4.5 of the paper. However the effect is practically the same. Namely, given a tree t_i build using threshold T_i, if we set a new threshold T_(i+1) and call rebuildTree (assuming maxEntries stays the same) we will obtain a more compact tree.

Since the CFTree is sensitive to the order of the data, there may be cases in which, if we set the T(i+1) so that non of the sub-clusters (i.e., the leaf entries) can be merged (e.g., T(i+1)=-1) we might actually obtain a new tree t_(i+1) containing more nodes than t_i. However, the obtained sub-clusters in t_(i+1) will be identical to the sub-clusters in t_i.

In practice, though, if T(i+1) > T(i), the tree t_(i+1) will usually be smaller than t_i. Although the Reducibility Theorem in Section 4.5 may not hold anymore, in practice this will not be a big problem, since even in those cases in which t_(i+1)>t_i, the growth should be very small.

The advantage is that relaxing the constraint that the size of t_(i+1) must be less than t_i makes the implementation of the rebuilding algorithm much easier.

the new (usually more compact) CFTree

Signals the fact that we finished inserting data. The obtained subclusters will be assigned a positive, unique ID number

Retrieves the subcluster id of the closest leaf entry to e

a positive integer, if the leaf entries were enumerated using finishedInsertingData(), otherwise -1

Computes an estimate of the cost of running an O(n^2) algorithm to split each subcluster in more fine-grained clusters

sqrt(sum_i[(n_i)^2]), where n_i is the number of members of the i-th subcluster

prints the CFTree

Counts the nodes of the tree (including leaves)

the number of nodes in the tree

Counts the number of CFEntries in the tree

the number of entries in the tree

Counts the number of leaf entries (i.e., the number of sub-clusters in the tree)

the number of leaf entries (i.e., the number of sub-clusters)

Prints the index of all the pattern vectors that fall into the leaf nodes. This is only useful for debugging purposes.

Prints the index of the pattern vectors in each leaf entry (i.e., each subcluster)