Algorithm to quickly find a row in a table

1
votes

I have a document with the following fields:

  • field1
  • field2
  • field3
  • field4

I have the following table structure:

field1  |  field2  |  field3  |  field4  || result
--------------------------------------------------
foo                   bar                   MC
foo        test1                            MR
           test2                 test3      OM
foo        test1      bar                   CM

When a document comes in with field1 is foo, field2 (null value), field3 is bar, the result MC should be selected. When a document comes in with field1 is foo, field2 is test1, field3 is bar, the result CM should be selected.

Of course, you can check each column and leave the matching rows open until you looped each row. But, this table structure can become very large, and I'm looking for some kind of algorithm which solves the above issue, on a performant and good way.

Any idea's?

2
javaalgorithmdesign-patterns
What do you mean by 'document'? Is this a text/plain file? Is the content of such a file always structured like your example? - user647772
are the values of field1, etc. limited? - vainolo
This problem has been worked on for the last 50 years and the result are today's RDBMSs. If you want to implement your own, just copy those solutions. - Marko Topolnik
@Tichodroma: a document is Java object with a list of fields List<Field> - Jochen Hebbrecht
@vainolo: values of field1 are not limited, they can take whatever value - Jochen Hebbrecht

2 Answers

1
votes

As @MarkoTopolnik wrote, RDBMSs do what you wish to do. But if you still want to implement your own algorithm, one option is to create a tree: level 1 is field1, level 2 is field2, etc. Each branch is one row of your table. If you only had two fields, this would look something like this:

root----field1.valueA----field2.valueC---result1
    \                \
     \                \--field2.valueD---result2
      \
       \field1.valueB----field2.valueC---result3
                     \
                      \--field2.valueD---result4

You can implement this tree using hashtables at each level. First you have a hashtable with field1 values as keys and hastables as values. These hashtables have field2 as keys and result as value. Since you allow null as a value, you must use HashMap and not Hashtable.

0
votes

For any string search like this the fastest option is a radix tree. Create 4 radix trees, one for each field where the leaf of the tree is the sorted list of records the value participates in. For example, for Field 1, if you search on Foo, it should return a list like { 1, 2, 4 } indicating that Foo is in records 1, 2 and 4 in Field 1. The result is you will have 4 sets of numbers, the intersection of which is the answer.

To get the intersection can be done in linear time because they are maintained in sorted order. Here is a simple sorted set intersection algorithm to do this in C:

#define int32 unsigned int

// A, B - operands, sorted arrays
// s_a, s_b - sizes of A and B
// C - result buffer
// return size of the result C
size_t intersect_sorted_list(int32 *A, int32 *B, size_t s_a, size_t s_b, int32 *C) {
    size_t i_a = 0, i_b = 0;
    size_t counter = 0;

    while(i_a < s_a && i_b < s_b) {
        if(A[i_a] < B[i_b]) {
            i_a++;
        } else if(B[i_b] < A[i_a]) {
            i_b++;
        } else {
            C[counter++] = A[i_a];
            i_a++; i_b++;
        }
    }
    return counter;
}