question, the best data structure and algorithm

Question

I have a question about implementing a data structure (with algorithm) that has these features:

1. There are too many places (like stores), and each place can store too many items, I want to store items in the places. The point is we need to have optimized insertion (or deletion) and optimized search feature.

2. Search can be done based on places (return items in the place) or base on items (return places that have the item)

I thought to use a hashmap for this, and use places ID as the key and store items as a collection (again a hashmap with item id for both key and value).

So based on this, the insertion of each item or place would be O(1) but get or remove of place will be O(n) and for item it will be O(n*k)! (assume we have "n" places and "k" items - I hope this is the correct calculation).

Is there any better data structure or algorithm for this problem?

Answer 1

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];
    }
}

Answer 2

Why not use a real DB for that? I think VistaDB, SQLite etc. would be perfect for the job?

Answer 3

The best algorithm/structure depends on how it will be used.

BTW this is a "grand truth". It applies to everything else in life. Picking the best car, bank, wife, etc.