[Data-modeling] Modeling datastructures

[Daniel Peebles]

So it looks decent now:
http://www.freebase.com/view/en/trie?domain=%2Fuser%2Fpumpkin%2Fcomputer_science

The one issue I have is that the complexities listed don't include
their variable explanations in the Data structure overview. Is there
some way I can get that to show up? Currently the information is there
but is more clicks away than ideal.

Thanks,
Dan

On Thu, Oct 23, 2008 at 8:44 PM, Daniel Peebles <pumpkingod at gmail.com> wrote:
> I've started implementing the suggestions I've received from this
> conversation in my domain. It's looking quite good but I'd welcome
> anyone who was interested in helping, as there's a lot of information.
> Modeling it on the STL is nice, but the STL creates many unintuitive
> types due to C++'s rather strict typing system, that I don't think I'd
> put in a knowledge database. That said, people are free to do anything
> they want with this stuff :P kinda the point, I guess :)
>
> Built-in MathML (ugh it's verbose, but there's not much else) support
> would be very nice. I could construct a compound data type for a full
> expression, but it wouldn't be reasonable to expect everyone who
> wanted to type an equation to break it down, so it would eventually be
> necessary to have a simple "input equation" option that might break it
> down internally. Ah well, maybe someday :)
>
> Thanks,
> Dan
>
> On Thu, Oct 23, 2008 at 8:37 PM, Faye Harris <faye at metaweb.com> wrote:
>> Agreed. It depends on how deep and how detailed you want to model this
>> (for example, for search, you would even break it down to best case,
>> average case, and worst case scenarios if you're so inclined). I glossed
>> over modeling details for an Algorithm type since it was not part of the
>> original question.
>>
>> The whole point of modeling algorithm together with data structure is
>> that the complexity of the former depends on the latter, and the two
>> types could both share and benefit from topics belonging to an
>> complexity order *type* as opposed to just text strings for complexity
>> orders that couldn't be reused.
>>
>> -- Faye
>>
>>
>> Tim Kientzle wrote:
>>>> 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.
>>>>
>>>
>>> Actually, there are at least two different complexity measures for
>>> each operation on a data structure.[1]
>>>
>>> So I think you'll need at least a type for operations, another for
>>> data structures, and a CVT which attaches a complexity to each
>>> combination.
>>>
>>> E.g.,
>>>    array <---  O(n) space ---> Merge sort
>>>    array <---  O(n log n) time ---> Merge sort
>>>    linked list <--- O(1) space ---> Merge sort
>>>    linked list <--- O(n log n) time ---> Merge sort
>>>    heap <---  O(n) space ---> inserting n items
>>>    heap <---  O(n log n) time ---> inserting n items
>>>    heap <---  O(n log n) time ---> removing first n items
>>>
>>> Of course, as David pointed out, "n" is a pretty simple case.
>>> Complexity often varies with several features (average link
>>> density, tree height, largest clique).
>>>
>>> Stepanov's STL work at SGI (http://www.sgi.com/tech/stl/)
>>> has resulted in a very nice hierarchy of data structures
>>> and operations that seems like a nice starting point for this.
>>>
>>> Tim
>>>
>>> [1] Of course, this is only if you limit yourself to big-O
>>> asymptotic average complexity.  There are quite a few
>>> other complexity measures that are of interest in various cases.
>>>
>>> _______________________________________________
>>> Data-modeling mailing list
>>> Data-modeling at freebase.com
>>> http://lists.freebase.com/mailman/listinfo/data-modeling
>>>
>>>
>>
>> _______________________________________________
>> Data-modeling mailing list
>> Data-modeling at freebase.com
>> http://lists.freebase.com/mailman/listinfo/data-modeling
>>
>