Suppose that we have a dataset of n elements each element is composed of m sub elements, is there any existing algorithm that we can use to calculate the complexity of this dataset?

I mean by the complexity anything that includes the following elements:

  • Diversity of dataset (number of distinct elements)
  • Distance between each element
  • Correlation between the elements of this dataset
  • Size of the dataset
  • $\begingroup$ You can determine these things fairly easily in your database, and efficiently so if you accept approximations (e.g.,. APPROX COUNT DISTINCT). You can also define a figure that combines multiple metrics, but how is up to you. $\endgroup$
    – Emre
    Mar 9, 2018 at 1:21

1 Answer 1


well ... "if n elements each element is composed of m sub elements" sound like you have a set of sets from discrete objects. If this is the case you can go through Combinatorial Analysis like Graph Theory. You can model it in two ways:

1) Using Hypergraphs: You have your elements as hyper-edges of a Hypergraph. This model lets you compute distances, diversities, sizes, and many more graph theoretical measures e.g. look at this, this and this.

2) Simple Graphs: You can create simple complete graphs from each sub-element and connect them to other complete graph (forming cliques) of other sub-elements. See the example bellow:

element1 = [[a,b,c],[b,c,d],[e,f,g]]  
Graph = [(a,b),(b,c),(a,c),(b,c),(c,d),(b,d),(e,f),(e,g),(f,g)]

using this you will have a huge graph (network) of your object on which you can calculate tones of structural and statistical measures.

I assume my thought were naive as your question is not clear and you need to provide more detailed example to get a more accurate answer.

Good Luck!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.