Data structure: sort and search effectively

data structuressearchsorting

I need to have a data structure with say 4 keys . I can sort on any of these keys. What data structure can I opt for? Sorting time should be very little.

I thought of a tree, but it will be only help searching on one key. For other keys I'll have to remake the tree on that particular key and then find it. Is there any data structure that can take care of all 4 keys at the same time?

these 4 fields [source ip, destination ip, source port, destination] are of total 12 bytes and total size for each record – 40 bytes.. have memory constraints too…

around one lac records

operations are : insertion, deletion, sorting on different keys.

For printing , sorting the records on any of one keys should not take more than 5 seconds.

Best Answer

1. If you rarely add and remove data

What about using the same technique as the one used in RDBMS with indexes?

In other words, you'll have the unordered set containing the data, and four ordered sets containing the keys and the pointers to the items in the data set.

Of course, this may cause performance issues if you need to frequently add and remove lots of data.

2. If data is added or removed frequently

You can slightly modify the algorithm to reduce the performance impact of sorting the four index sets every time you add or remove an item. You may, for example, have four unordered index sets, create from them the sorted sets when needed, and invalidate those sorted sets when an element is added or removed.

3. Profile

Note that profiling is important, since you can't possibly guess where the bottleneck will be. Remember than:

When you remove an item from the data set, removing four keys from four index sets is fast, since those sets are already ordered;
When you add an item, adding four keys to the index sets is not hugely slow: you just have to walk through the sets, and insert the keys at the appropriate position:
Let the list be:
```
 3, 7, 8, 12, 16, 22, 23, 24, 27
```
If you need to add the value 25, position yourself at the middle of the list:
```
 3, 7, 8, 12, 16, 22, 23, 24, 27
              ↑
```
Since 25 is greater then 16, go to the right:
```
 -, -, -, --, --, 22, 23, 24, 27
                         ↑
```
And again to the right:
```
 -, -, -, --, --, --, --, 24, 27
                             ↑
```
Found the position.

Related Solutions

Question, the best data structure and algorithm

Why not use balanced trees? You would need one tree at each store, mapping item ID to some internal information, and one global tree, mapping item ID to the list of the nodes having the given item. Your operations will be O(log n + log k).

Edit:
the operations in this case would look like the following: (I use the fact that std::map and std::set are tree-based in C++)

using namespace std;

typedef int itemid_t;
typedef int storeid_t;

map<itemid_t, set<storeid_t>> itemID2storeList;

class Store
{
    storeid_t Id;

    // insert requires one lookup in the map (O(log k))
    // plus one insert into a set (O(log n)).
    void insert(itemid_t item)
    {
        itemID2storeList[item].insert(Id);
    }

    // the same as for insert
    void delete(itemid_t item)
    {
        itemID2storeList[item].erase(Id);
    }

    // search in a store requires one lookup in a map (O(log k))
    // and one search in a set (O(log n)).
    bool have(itemid_t item)
    {
        const set<storeid_t>& storesForItem = itemID2storeList[item];
        return storesForItem.find(Id) != storesForItem.end();
    }
}

class Central
{
    // getting the list of stores having the given item requires
    // one lookup in a map (O(log k))
    const set<storeid_t>& storesForItem(itemid_t item)
    {
        return itemID2storeList[item];
    }
}

How to Quickly Search Through a Very Large List of Strings/Records in a Database

Instead of putting your data inside the DB, you can keep them as a set of documents (text files) separately and keep the link (path/url etc.) in the DB.

This is essential because, SQL query by design will be very slow both in sub-string search as well as retrieval.

Now, your problem is formulated as, having to search the text files which contains the set of strings. There are two possibilities here.

Sub-string match If your text blobs is a single sting or word (without any white space) and you need to search arbitrary sub-string within it. In such cases you need to parse every file to find best possible files that matches. One uses algorithms like Boyer Moor algorithm. See this and this for details. This is also equivalent to grep - because grep uses similar stuff inside. But you may still make at least 100+ grep (worst case 2 million) before returning.
Indexed search. Here you are assuming that text contains set of words and search is limited to fixed word lengths. In this case, document is indexed over all the possible occurrences of words. This is often called "Full Text search". There are number of algorithms to do this and number of open source projects that can be used directly. Many of them, also support wild card search, approximate search etc. as below :
a. Apache Lucene : http://lucene.apache.org/java/docs/index.html
b. OpenFTS : http://openfts.sourceforge.net/
c. Sphinx http://sphinxsearch.com/

Most likely if you need "fixed words" as queries, the approach two will be very fast and effective.

Best Answer

Related Solutions

Question, the best data structure and algorithm

How to Quickly Search Through a Very Large List of Strings/Records in a Database

Related Topic