wpi.associations.arminerSequence
Class HashTree

java.lang.Object
  extended bywpi.associations.arminerSequence.HashTree

public class HashTree
extends java.lang.Object

A special data structure that is used to index a Vector of ARMinerItemset objects for more efficient processing.

Author:
Dana Cristofor, Laurentiu Cristofor, Keith A. Pray (kap@wpi.edu)

Nested Class Summary
private  class HashTree.HashNode
           
private static class HashTree.HashTreeOverflowException
           
private  class HashTree.ListNode
           
private static class HashTree.MyHashtable
           
private static class HashTree.Node
           
 
Field Summary
private  int counter
          used for some computations
private static int DEFAULT_HASH_SIZE
           
private static int DEFAULT_LIST_SIZE
           
private static int HASH_NODE
           
private  int HASH_SIZE
           
private  java.util.Vector itemsets
          from the getCandidate method:
private  java.util.Vector leaves
          keeps all leaves of the HashTree
private static int LIST_NODE
           
private  int LIST_SIZE
           
private  HashTree.Node theRoot
          the root of the HashTree
 
Constructor Summary
HashTree(int listSize, int hashSize, java.util.Vector itemsets)
          Create a new HashTree.
HashTree(java.util.Vector itemsets)
          Create a new HashTree.
 
Method Summary
private  HashTree.Node add(HashTree.Node node, int level, int index)
          Adds a node recursively.
 void add(int index)
          This method indexes in the HashTree the ARMinerItemset at index index from Vector itemsets which was passed to the constructor of this HashTree.
 long countSubsets(ARMinerItemset itemset)
          Count how many ARMinerItemsets are included in itemset
private  void countSubsets(HashTree.Node node, ARMinerItemset itemset, int index)
          Count how many ARMinerItemsets are included in itemset recursively.
private  void prepare(HashTree.Node node)
          Prepares the hash tree for desecent recursively.
 void prepareForDescent()
          This method should be called before calling update() to gather all leaves of the HashTree for more efficient processing.
private  void readdAll()
          Reset HashTree and readd all itemsets added previously this method may be called by add()
private  void unvisitLeaves()
          Sets each leaf to unvisited.
 void update(ARMinerItemset row)
          Update the weights of all indexed ARMinerItemsets that are included in row
private  void update(HashTree.Node node, ARMinerItemset row, int index)
          Updates the support of itemsets recursively.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LIST_NODE

private static final int LIST_NODE
See Also:
Constant Field Values

HASH_NODE

private static final int HASH_NODE
See Also:
Constant Field Values

DEFAULT_LIST_SIZE

private static final int DEFAULT_LIST_SIZE
See Also:
Constant Field Values

DEFAULT_HASH_SIZE

private static final int DEFAULT_HASH_SIZE
See Also:
Constant Field Values

LIST_SIZE

private int LIST_SIZE

HASH_SIZE

private int HASH_SIZE

counter

private int counter
used for some computations


leaves

private java.util.Vector leaves
keeps all leaves of the HashTree


itemsets

private java.util.Vector itemsets
from the getCandidate method:


theRoot

private HashTree.Node theRoot
the root of the HashTree

Constructor Detail

HashTree

public HashTree(int listSize,
                int hashSize,
                java.util.Vector itemsets)
Create a new HashTree. The listSize parameter determines after how many inserts in a ListNode we have to change it to a HashNode (i.e. perform a split). The hashSize parameter can be specified to improve the efficiency of the structure.

Parameters:
listSize - the size of the internal lists in the list nodes
hashSize - the size of the internal hashtables in the hash nodes
itemsets - the Vector of ARMinerItemsets that we should index
Throws:
java.lang.IllegalArgumentException - itemsets is null or listSize <= 0 or hashSize <= 0

HashTree

public HashTree(java.util.Vector itemsets)
Create a new HashTree. This initializes the HashTree with default parameters.

Parameters:
itemsets - the Vector of ARMinerItemsets that we should index
Throws:
java.lang.IllegalArgumentException - itemsets is null
Method Detail

unvisitLeaves

private void unvisitLeaves()
Sets each leaf to unvisited.


prepareForDescent

public void prepareForDescent()
This method should be called before calling update() to gather all leaves of the HashTree for more efficient processing.


prepare

private void prepare(HashTree.Node node)
Prepares the hash tree for desecent recursively.


readdAll

private void readdAll()
Reset HashTree and readd all itemsets added previously this method may be called by add()


add

public void add(int index)
This method indexes in the HashTree the ARMinerItemset at index index from Vector itemsets which was passed to the constructor of this HashTree.

Parameters:
index - the index of the ARMinerItemset that we need to index in this HashTree.

add

private HashTree.Node add(HashTree.Node node,
                          int level,
                          int index)
Adds a node recursively.

Parameters:
node -
level -
index -

update

public void update(ARMinerItemset row)
Update the weights of all indexed ARMinerItemsets that are included in row

Parameters:
row - the ARMinerItemset (normally a database row) against which we test for inclusion

update

private void update(HashTree.Node node,
                    ARMinerItemset row,
                    int index)
Updates the support of itemsets recursively.

Parameters:
node -
row - the ARMinerItemset (normally a database row) against which we test for inclusion
index -

countSubsets

public long countSubsets(ARMinerItemset itemset)
Count how many ARMinerItemsets are included in itemset

Parameters:
itemset - the ARMinerItemset for which we count the subsets

countSubsets

private void countSubsets(HashTree.Node node,
                          ARMinerItemset itemset,
                          int index)
Count how many ARMinerItemsets are included in itemset recursively.

Parameters:
node -
itemset - the ARMinerItemset for which we count the subsets
index -