Re: Feature freeze imminent

On Mon, 26 Feb 2007 15:38:57 +0000 (UTC) Tuomo Valkonen <[email protected]> wrote: 

TV> My present plan is that each tag has a sparse bitmap associated 
TV> with it, with the bit for each object ID that has that tag set, set
TV> to one. Then you just 'and' these bitmaps when you search for the
TV> subset of files having the given tags set. This should be quite
TV> efficient given a suitable sparse structure for the bitmaps. 

You probably want inversion lists for this.  They are very efficient
for sparse membership, and extend to N members easily since they are
just linked lists internally.

TV> There's, however, another structure needed for looking up a particular
TV> file with exactly given set of tags. One approach would be to use a 
TV> binary self-balancing tree (red-black, AVL), but I'm afraid that could
TV> be too inefficient on a file system, as multiple 'inodes' all around the
TV> disk would have to be accessed on each lookup. An alternative, possibly
TV> more efficient, approach would be to order the identifier sets by tag ID,
TV> and use a nested B-tree for looking up the files as if they were on a 
TV> normal hierachical file system. In fact, you could store the files on 
TV> a normal underlying file system in that hierarchy. I do not plan to do
TV> so, however, although I do intend to use (at least initially) a normal
TV> FS for storing the files, with an additional file for the indices.

Have you considered SQLite or something similar?  Even if you don't
use on a DB backend eventually, I think using it at first would make
your life easier because the prototype will be easier to produce.

I also think the tag ideas would apply nicely to Ion3 elements.  Right
now, "goto window," for example, has just the tab-completion interface
by name.  It could use tags by window class, workspace type and
number, etc.  Just a thought for Ion3plus.

Ted