Re: Feature freeze imminent

On Tue, Feb 27, 2007 at 07:30:32AM +0000, Tuomo Valkonen wrote:
> On 2007-02-26, Sam Mason <[email protected]> wrote:
> > File lookups would have to stop while tags were being modified though.
> > But yes, it's much less of an issue for file systems than for databases.
> 
> Actually, with suitable structures for the bitmaps, it might only be
> necessary to lock suitable ranges of the bitmaps containing the ID of 
> the object to be added/removed, so that other threads could continue 
> working on searches on the remaining parts, until they reach a locked
> part. 

Definitly possible, but you'd have to be very careful about
deadlocking.  Think about the case when you're extending the bitmap
somewhere in the middle.

> But it's not really that important on my toy file system. 

I agree, it's also way outside any real programming experience I've ever
had.

> I primarily 
> want to test the concept in an application where efficiencies should 
> not be a big issue: riot. Of course, if it works out, I'd like to
> store other random data as well that way... I hate trying to remember 
> the exact paths for random Web saves and stuff. But saving by metadata
> pre-entered by others isn't going to work either: the unusefulness of
> ID3 tags in MP3s is evidence of that. Non-hierarchical tags should 
> work better. (Now, if you could still combine this with that: 
> <http://iki.fi/tuomov/b/archives/2006/06/16/T18_23_18/>).

I tend to get annoyed when things fit into several categories and having
to choose between one.  For example I have a "projects" directory
containing the projects I'm working on at the moment and a "people"
directory for stuff that doesn't fit into a specific project.  But
really I'd like to be able to say that a file is from this person and
also belongs to this project.

> > Why not [bar,baz,quk,zum]? all of these tags appear in files once you've
> > filtered out the ones that don't have foo in.  But yes, I see why
> > pruning could be problematic.  I'll have to think about it more!
> 
> Because that would not be much of a pruning, would it? 

I thought that was because as the filesystem grew there would be many
more files relative to tags.  If this was the case then it would help;
but maybe there would always be a similar number of tags to files.
You'll probably have a few files called "index.html" on your computer
but most other files are going to have unique names (the basename in a
hierachial system).

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.  After all, the latest Firefox browser just tends to dump
downloaded files into your home directory with just the name taken from
the URL.

> It would make
> for more predictable results, however, when the pruning would otherwise
> resort to tag frequencies. 

Yes, and, as you noted, reconstructing a hierachy dynamically is not an
easy thing to do.  Additionally there are potentially lots of ways of
doing it which /could/ lead to confusion when the defaults change.

> (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?

> Whereas in the worst case, the computational complexity of even the
> frequency-based pruning operation can be quite high(*) (let alone the
> optimal Minimum Hitting Set, which is NP-complete), I doubt it is 
> a big problem in practise. What I do find problematic, is storing all 
> the search results in memory for pruning: there can be quite a few 
> results for the top-level empty search.  However, it is possible to 
> do even more sub-optimal pruning by working on smaller (fixed-length)
> blocks of results at a time, and thus also providing a O(log n_tags)
> average time bound for producing a single result (a tag).

> (*) The number of tags per object can probably have a fixed upper limit,
> so the number of tags an object has plays no role in the complexities,
> as does not the length of the query. A very conservative estimate for 
> inserting all the tags in the found objects in a frequency-counting 
> search tree, and also inserting the objects in a search tree, is 
> O(n_objects * log n_tags). Likewise, a _very_ conservative estimate 
> for working through all the tags, removing objects listed after the tag
> from an object search tree, and removing the tags no longer referenced 
> to by any object from the tag search tree, is
> O(n_tags * n_objects * max(log n_objects, log n_tags)).
> The n_objects term is the estimate for number objects for each tag
> and is, of course, a serious over-estimation in practise. Also, if one
> tag (not in the search set) has all the objects, there's nothing to be
> done after that. The n_tags factor also a heavy over-estimation in 
> practise, as the tags  get removed along the way.

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


  Sam