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
