[Data-modeling] Modeling datastructures

[Jeff Prucher]

This is waaay outside my areas of expertise, but if I understand the problem
correctly, your suggestion of a property stating the variables used would
seem to work fine.  It really just moves the textual information like
"length of string" to another property, so people will have to look in two
places to understand the time complexity (that is, in the time complexity
property itself and in the variables used property). So if your goal is for
the notation to be standardized, that's probably the best solution. If you
just want to be able to quickly read down a list of time complexities, the
way you have it now might be best.

Jeff

> -----Original Message-----
> From: data-modeling-bounces at freebase.com 
> [mailto:data-modeling-bounces at freebase.com] On Behalf Of 
> Daniel Peebles
> Sent: Thursday, October 23, 2008 9:54 AM
> To: data-modeling at freebase.com
> Subject: [Data-modeling] Modeling datastructures
> 
> 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/dat
> a_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
>