Re: Feature freeze imminent

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. 

But it's not really that important on my toy file system. 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/>).

> 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? It would make
for more predictable results, however, when the pruning would otherwise
resort to tag frequencies. (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.)

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.

> If you're still exploring the problem they can be very good at providing
> a flexible data store.  

I don't know about that.. The thing is, I like writing algorithms and
data structures more than learning others' APIs, and the help provided
by a DB isn't _that_ big...

-- 
Tuomo