Re: Feature freeze imminent

On 2007-02-27, Sam Mason <[email protected]> wrote:
> I tend to get annoyed when things fit into several categories and having
> to choose between one.  

Yeah, and I hate also deciding between "todo/ion" and "ion/todo", 
and such cases.

> I thought that was because as the filesystem grew there would be many
> more files relative to tags.  

It depends on the use I guess. If, say, you would be saving email in
the SetFS, each with its MessageID as one tag, and other information
as other tags (say, 'ion/list/[email protected]/msg.123098asdfasdf234'),
there would be more tags than files. But in many other use cases the
situation might be the opposite.

> If these names were treated the same as the rest of the tags thos
> would kill my naive pruning attempts.  One possible fix would be to
> diffrentiate between the filename and it's tags.  This is very different
> from what you wanted to do, but I'm not sure if it would be bad in
> practice.  

I've thought about a lot of extensions to the basic scheme, because,
well it is not perfect, and there are still many situations where
it is difficult to decide how one should tag things. (Even that
example above, 'ion/list/[email protected]/msg.123098asdfasdf234' could
be rendered in various different ways.) However, I've decided against
most of these, because they would unnecessarily complicate the system,
without really solving anything. One of these things is a distinguished
file name component. KISS. 

>> (If there are objects with immediate successor
>> tag sets to the search set, the extra tags _must_ be included in the
>> result, and therefore creating even such dummy "directories" will let
>> one control the results.)
>
> I'm not sure how you would identify these by looking at the frequency
> of occurance, wouldn't you just get two tags occuring with the same
> frequency?

Suppose you search by 'foo/bar', and get 'foo/bar/baz' among the 
(fully qualified) results. The you absolutely have to list 'baz'
in the output, because there's no other route to it, there being
no additional tags. However, if you get the result 'foo/bar/baz/quk',
but do _not_ get 'foo/bar/baz', you do not have to list 'baz', as
'quk' provides a path to the result 'foo/bar/baz/quk'. 

You see, if you have a file with the set A of tags, and a file with
the set B of tags, superset of A, you do not have to have the files
with the sets of tags C_i, where C_i is between A and B. However, 
if you want to, you can create such dummy files ("directories"), and
thus direct the pruner.

The pruning operation would be unnecessary/automatic if we, instead 
of tag bitmaps, stored the partial order of the tag sets in the FS. 
Such a partial order would also immediately provide the structure to
use for search for a file with exactly the given set of tags. However,
the partial order structure seems intractable to maintain. (Consider 
the number of subsets of a set.) Not that I've given it careful 
thought yet...

> That all sounds like quite a hard problem for any reasonable number of
> objects and tags.

Yes, the optimal pruning (at least without bounds on the number of
tags per file) is (NP-) hard. However, sub-optimal should suffice.
Of course, the pruning method can be user-tunable, and perhaps even
some simple greedy lexicographical pruning would suffice sometimes
(i.e. if an object is not covered by one of the tags seen yet, take
the first of its tags in, say, lexicographical order, not part of the
search set). Or maybe one could use the total occurence frequencies 
of the tags (which can be stored on the fs) when there are many 
results, and use the frequency within the results, when there aren't
that many. Infact, if some program one wants particular kind of
results, this could be configured in some path element:
foo/#created:year=2006/#prune:alltags/ (demonstrating also the
additional filters).

-- 
Tuomo