Geek Answers Handbook

Data structures and search algorithm for multiple predicate

Does anyone know a good data structure and an algorithm for searching using multiple predicates.

eg. Suppose I have a tcp header dataset (excluding duplicates). If I were looking for the tcp header of the src ip list, I could sort it by src IP and do a binary search.

What data structure / algorithm should I use if I want to find the tcp header from a set that matches all src / dst ip / port? (except for iterating over the entire set).

+4
source share
4 answers

These are exactly the things that database vendors have dealt with for years. If you are going to search sequentially by src / dst IP / port, you can use this as a criterion for sorting and look for it more or less directly.

Otherwise, a typical approach is to sort the data by one field and construct indexes for other fields. You can then perform a binary search in each index to find a set of records that match the criteria for this field. The intersection of these sets will be the records you are looking for.

Of course, if you prefer, you can also reduce the number of indexes, so (for example) you can use indexes to get a set of records with the correct source and destination IP addresses, and then just scan it (maybe quite small) to get numbers with The correct port number.

+3
source

I would suggest indexing individually by common fields, and then use the merge combining strategy to satisfy queries for multiple fields.

You can also use the index for (a, b, c) to query (a, b) or just (a), so a reasonable choice of indexes can allow you to avoid having to join the join.

+1
source

Perhaps you could use kd-trees as a means to get an efficient multi-quark search? I can’t say that I know a lot about the specific problem you are trying to solve, but asking about searching in terms of several keys seems like this could be applicable.

0
source

C ++ Boost provides something called a container with multiple indices. This is essentially a group of hash tables, one for each key, with some code to maintain consistency.

0
source

More articles:


All Articles