Usually, you'll need to make a trade-off between inserting items into your data structure and just accessing items. Based on how often you are going to change your graph and how often you just read from it different data structures are more efficient. There is no one-size-fits-all solution to your problem. Without deep knowledge of your problem it is impossible to give the right answer.

10000 elements is not a large number of items for today's computers. Almost every algorithm might be fast enough for you. Only if you need very high performance does it make sense to use the kind of hacks that Jochen has suggested. Otherwise a regular data structure will be sufficient (and a lot easier to maintain). Sometimes it is not worth it to spend a lot of time tweaking a data structure that nobody is able to maintain. So, ask yourself the following: Will the project stay for many years (10 years+)? Will this be a data structure that is only written once and never touched again? If the answer is "yes" to both questions you can consider looking for the optimal solution, but you don't have to. Don't spend to much time for complicated code that nobody else will ever want to touch, but they might have to. Be kind to your future self ;-)

Dear Mayur Narkhede,

there exists most certainly not "the best" data structure. It all depends on how you want/have to access the data. One very general, but also very important point regarding performance is this: In todays computer systems, memory access is by far the slowest operation compared to, e.g., arithmetic operations. So, if you have only 10000 nodes to store, you should choose a compact representation (if possible) and store this representation directly in an array on the stack. For instance, lets say you need an integer ID-value per node, another integer to store a cluster ID, and 17 words for the first 17 edges + a 64 bit pointer to a memory location on the heap that is set if you have more than 17 edges. In this case you would need 50 bytes per node or 500KB for your 10000 nodes. On a modern CPU this amount fits well into the 2nd or 3rd level cache and will make the access on the data very fast. In contrast, if you store your graph as a complex structure in the heap memory, access performance can drop by two orders of magnitude.

Cheers,

Jochen

I agree with Jochen.  My tame(?) Computer Scientist comments, "It could be a case for k-d-trees. 10K entities for K-d-trees if trivial. It is not clear, however, the sort of info (s)he needs to recover when (s)he searches the index. 

STINGER was designed with the goal of supporting dynamic graphs with millions of vertices and billions edges:

http://www.stingergraph.com/ 

There are several publications that discuss performance and scaling, I will gladly refer you to these.

@Oded Green : does It STINGER supports clustered graph?

Usually, you'll need to make a trade-off between inserting items into your data structure and just accessing items. Based on how often you are going to change your graph and how often you just read from it different data structures are more efficient. There is no one-size-fits-all solution to your problem. Without deep knowledge of your problem it is impossible to give the right answer.

10000 elements is not a large number of items for today's computers. Almost every algorithm might be fast enough for you. Only if you need very high performance does it make sense to use the kind of hacks that Jochen has suggested. Otherwise a regular data structure will be sufficient (and a lot easier to maintain). Sometimes it is not worth it to spend a lot of time tweaking a data structure that nobody is able to maintain. So, ask yourself the following: Will the project stay for many years (10 years+)? Will this be a data structure that is only written once and never touched again? If the answer is "yes" to both questions you can consider looking for the optimal solution, but you don't have to. Don't spend to much time for complicated code that nobody else will ever want to touch, but they might have to. Be kind to your future self ;-)

Though in your case the size is not huge, still, you might want to check bloom-filters which is space-efficient and provides very fast access for large amounts of data with a slight possibility of false positives.

I will add just a few facts and conclusions to the above, well-elaborated, answers.  Really, there’s no unique data structure that is “proven” to be the best choice in all cases. For the best time-space performance, the structures and algorithms should be “tailored” according to the particular need. The static array assures the fastest performance, and thus the best time complexity of the algorithm, but only within a constant—which does not appear as an important contributor in the big O notation. But if that constant is much smaller than for other solutions, it can be significant in practice (as suggested by the first answer). Furthermore, this solution effectively makes the space complexity of the algorithms to be a constant equal to the size of the array, and independent of the size of the problem. The drawback is that this solution requires a predetermination of the space needed for the implementation of the structure. Thus, the strict, assumably low, upper space limit of the problem is set. Because of the low demand on the number of nodes in this case, this is a possible choice. However, for a flexible solution, which allows a big range of available nodes, dynamic allocation of memory is a better choice. An example of this for the binary trees, together with the analysis of the time-space complexities of several algorithms on such trees, can be found in my  paper “Algorithms and data structures for the modelling of dynamical systems by means of stochastic finite automata.” These algorithms and structures are implemented in my DSA program (Dynamical Systems Automata). Here the number of nodes can grow up to the values that are allowed by the maximal heap memory that can be allocated to the process. For a Win32 application, such as the DSA program, this is slightly less than 2GiB, and this allows the creation of up to 32Mi nodes of the particular trees used in the program. It is interesting to note that as the memory used approaches its maximal possible value for the process, the algorithms tend to work slower! Also, the memory calculated from the number of nodes and other used data is significantly less than that shown by the task manager, which is another interesting thing to explore [I will gladly distribute the program accompanied by an instructions manual to all interested colleagues.]

There is also another aspect to take into consideration: are you expecting to access mostly directly related nodes or are you going to deeply traverse the graph? If you are planning on doing inference, then you need a data structure that is tailored more in traversing the graph than selecting specific elements at random. I use Neo4j (http://www.neo4j.org) which is a very good graph database. Unless you developing an embedded application, it is usually easier to use general purpose databases such as that one.

Milko is right - the node structure should be (carefully) tailored to the type and needs of the algorithms used on the tree structure. E.g. an indicator (pointer) of the node parent is needed to enable the nonrecursive algorithms, but, of course, it will increase the size of additional data in the tree node. Also, sometimes the level of the node comes as very useful. It is needed when the concept of subtree is introduced. (All this tradeoffs are discussed in my paper “Recursive and Nonrecursive Traversal Algorithms for Dynamically Created Binary Trees”).

Perhaps Milko can discuss the versatility of the Neo4j database regarding these (additional) features, and help Mayur to choose between a ready-made or custom-tailored solution.