[Data-modeling] Modeling datastructures

[Faye Harris]

Hi Daniel,

For modeling Big O notation, I suggest creating a type and make it the 
expected type for Data Structure properties like "space complexity".  
Then create a topic for each common Big O order. If you add a property 
"algorithmic efficiency" to an Algorithm type, you can use the same Big 
O Order type as the expected type.

The type allows you to have properties and reusability, and support 
reverse links. Having the Big O values as topics buys you an article 
where you can describe what each value means. If you mark the type as 
enumerated, users will be able to see a drop down and select a 
pre-populated value when they need to fill out a Big O property. Since 
there aren't that many common orders, I think it makes sense.

To summarize, this is what we'd have:

Type: Big O Order (or whatever you want to name it)
Display: Enumerated
Properties:
1) Data structures with this space complexity (expected type: Data 
Structure)
2) Algorithms with this runtime efficiency (expected type: Algorithm)
Create a topic for each common order: O(1), O(n), O(log n), O(n log n), 
O(n^2), etc.

For your existing Data Structure type, set:
Property:
Space complexity, expected type Big O Order (make sure it's a reverse 
property of the Big O Order type's #1 property to link them together).

And do something similar with algorithms. Viola!

-- Faye



Daniel Peebles wrote:
> Hi all,
>
> I'm pretty new to all this Freebase stuff, but yesterday I got myself
> extremely involved in setting up a Data Structure type, with related
> information and so on. You can find what I have so far at
> http://www.freebase.com/view/user/pumpkin/computer_science/data_structure
> (and please join my computer science domain if you're interested in
> helping me with this!)
>
> My main question has to do with modeling the operations on a given
> data structure. If you look at what I added to splay tree, you'll see
> I have a list of operations that the splay tree supports, along with
> time complexities for each of them. When the complexity is obvious,
> all is fine, but on the same page you can see my information for a
> Trie. There, the complexity is in terms of the length of the input
> string, rather than the total size of the data structure.
>
> Ideally, my data structure type would have a property called "relevant
> variables", which could map from a name to a description (n -> "Number
> of strings contained", m -> "Size of string being operated on"), and
> then the big-O notation in the "data structure operation profile" CVT
> would require there to be a mathematical expression in terms of only
> the variables in the data structure associated with it.
>
> This seems awfully complex, and I'm not sure I can place a constraint
> on the variable source in the expression to ensure it didn't come from
> another data structure. The other issue is that I don't have a
> "mathematical expression" basic type, and to make my own type would be
> monstrously complicated and ugly.
>
> So it boils down to, does anyone have any ideas on how to implement
> the time complexities better? It looks really ugly to me to write
> O(size of inserted string) as a machine-readable string, but I can't
> see any better way to do it. The end-goal is obviously to have a
> structured database of datastructures, the operations they support,
> and the time complexity of that operation, so that people can quickly
> find the best tool for the job (and just for the sake of good data
> modeling). Is this too specific an application of the extremely
> general data modeling features of freebase?
>
> Thanks,
> Daniel Peebles
> _______________________________________________
> Data-modeling mailing list
> Data-modeling at freebase.com
> http://lists.freebase.com/mailman/listinfo/data-modeling
>
>