Re: Feature freeze imminent

On Tue, Feb 27, 2007 at 04:39:27PM +0000, Tuomo Valkonen wrote:
> On 2007-02-27, Sam Mason <[email protected]> wrote:
> > 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 you can think up any cases where you're not going to have a similar
number of tags to files then I'd be interested to know, I'm failing.
The only one I can think of would be if you treated the tags like
the digits of a binary number, I can't see anyone doing that in
practise---the number tags would grow to the log of the files though!

> > 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. 

It's up to the users to find the optimal way to use the tools isn't it?

> 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'. 

OK

> 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.

Wouldn't there be the same number of occurrences for each tag? If so,
how does the pruner know which one to pick?

> 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...

I thought the point was to remove the hierarchy!

More usefully, if you're sold on having a pruner then it sounds like
the only way to get sensible answers out is to have some order in there
somewhere.

> > 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).

:) you said you wanted to keep it simple earlier and now you're
proposing some ad-hock language to "fix" the pruning process?


You mentioned earlier that you'd come up with lots of ideas and
discarded them because they didn't really solve anything.  I'm not
really sure what problems you're trying to solve!  I would be personally
interested to see if we could turn this into something that would be
usable as a file system that could be mounted to look after most of the
files in a user's home directory.

I think that hierarchical file systems are going to exist for a
while---they are very good ways of organising code.  But unless you're
doing something that naturally breaks down into a hierarchy, like code,
(i.e. most things) then the tag concept is probably more useful.

How far apart are our goals?


  Sam

p.s. I hope this is somewhat interesting to you, I tend to get carried
away with these sorts of discussions!