A (possibly) fast, novel search technique

0.Introduction

“The general idea is that we record for each item (of the same length) a byte position where that item differs from some other item. When we insert a new item we check each recorded byte position to see the current item matches at that position. When it is established that there is no conflict between the current item and some existing item then and only then do we do a full comparison.”

The uniqueness sequence (or some variant of it) is useful for a variety of elementary operations, e.g., uniq and diff, as well as building symbol tables.

Now suppose we have a simple function f(p,e) on a parameter space P (character position in the original context) and E such that

(1)  f(p,ei) .ne. f(p,ej) => ei .ne. ej.

For example, if the data elements are character arrays then f(p,e_i) could be the p’th character in element e_i. Thus, if e₁ = “abcd” then f(3,e₁) = “c”. The important things about f are:

• It is O(1).
• It may distinguish between unequal elements but is not guaranteed to do so.
• It makes different distinctions for different values of p.

Suppose we also have a function g(e_i,e_j) such that g returns a value p such that if e_i .ne. e_j then f(p,e_i) .ne. f(p,e_j). Again, as an example, g could be the first character position at which e_i and e_j differ. Unlike function f which is O(1), the cost of function g is data dependent. When the two elements are the same, the cost of g is the common length; otherwise it depends on the data. Commonly, however, it will also be O(1).

2. The discrimination set tree structure

A node S_i has two principal components, a parameter value p_i, and a set of records. (In an implementation the set might be implemented as an array, a linked list, a binary tree, or even a trie as might be convenient. Formally, however it is a set.) A record has three components:

• A reference (pointer) to a data element e_j.
• The value of f(p_i,e_j)
• A reference (pointer) to a sub node, if any.

A sub node has the properties that:

• Its parameter value is distinct from that of any of its ancestral nodes.
• It’s set of records includes the data element from its parent record.
• It ordinarily has at least two records in its set of records. However deletions can created single element sets.

The root node of an H-tree looks like sub nodes except that it may contain less than two records as a special case; if there are less than two the parameter value is not set.

There are at least two things that make an H-tree unusual. The first is that in effect we have an alternation of generations, i.e., nodes pointing to sets pointing to nodes, etc. The second is that references to elements can appear more than once in a tree; in effect every parent is its own child.

3. Building an discrimination set tree

For people who think in terms of lists we create a list that looks something like this:

    (p1, (ei, f(p1,e1)), (e2, f(p1,e2)))

    p1:  1 -- 2

    p1:  1 -- 2 -- 3

    p1:  1 -- 2
              |
    p2:       2 -- 3

    p1:  1 -- 2 -- 5
         |    |
    p2:  |    2 -- 3
         |         |
    p3:  1 -- 4    |
                   |
    p4:            3 -- 6

In summary: A failed search is very fast; a successful search is slightly slower because of the need for verification.

Adding an element uses the same logic as a search; however the terminal actions are different. If no match is found, i.e., the value of f(node parameter, element) does not match any value in a nodes set of records a new entry is created in the set is created. If a leaf node is reached and a potential match is found we enter the verification step. If there is a match the add routine reports that a duplicate has been found. On the other hand is a mismatch is found a new sub-node is created going down from the candidate element. The new sub node contains the candidate and the element being added.

Summary: Finding a duplicate has the same cost as a failed search; a successful search has the same cost as a successful search plus the cost of creating a new node.

Deleting elements is the most complicated operation because an element can appear more than once in the tree. The general plan is to replace each instance of the deleted element by a sibling and promote the sibling up in place of the deleted element. The details of this process will be described later. Most element deletions (at least half) are simple deletions, i.e., the only occurrence of the element is in the set of a leaf node. In the worst case the cost is proportional to the height of the tree.

The complexity of the deletion process depends upon whether an element can easily be identified as an element in the tree. In many applications in which elements are deleted this will be the case. For example, a data element may well have the structure:

        struct data_element {
                int length;
                char * data;
                struct usage_record *rec;
        };

In summary: Deletion can be complicated; however most deletions will cost about the same as a failed search.

5. A forest of trees

If we hash the data elements we need M reads per element, a cost r per read and a hashing cost h per read. The cost per element for the hashing is (r+h)*M. The amortized cost of checking duplicates is r*(D/N)*M which is small compared to the cost of hashing. The hash table cost should also be small compared to the cost of hashing.

Determining the costs of a discrimination set tree based algorithm is not so simple because it is data dependent. In the worst case every entry requires a call to g(e,e) with a cost 2*r*M. This is better than hashing but not by much. However the average case is much better, the number of reads per element being log2(N)/log2(L) where L is the average length of the lists. Therefore the ratio of access costs (not counting hashing) is

(2) K*log2(L)

A major factor in the cost of implementations is the cost of storage management. There are three potential problem points; these are getting new nodes, getting initial set space for each new node, and increasing the set space as sets increase in size. If a naive storage allocation strategy used allocation/deallocation costs will dominate the algorithm costs; however there are standard techniques for minimizing such costs so that most allocations cost no more than removing an item from a free list.

I have implemented an initial implementation; the preliminary results are quite promising; H tree searches are faster than hash table searches for the test data sets. However there is much work to do be done before the empirical results are satisfactory.