Re: [9fans] text database Kirara

["Peter A. Cejchan" <tyapca7@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 6007 bytes --]

Sounds great!
Thank you, Kenji !!
++pac


On Tue, Aug 6, 2013 at 3:14 AM, arisawa <arisawa@ar.aichi-u.ac.jp> wrote:

> Hello 9fans,
>
> I have written a text database named Kirara.
> The following is a brief introduction to Kirara.
> If you are interested in, get Kirara from:
>   http://plan9.aichi-u.ac.jp/netlib/kirara/
>
> Kenji Arisawa
>
> -------------
>
> Kirara
>
> -------------
>
> Kirara is a text indexing/retrieval tool for Plan 9.
>
> Personal use: index/retrieve local files.
>
> Kirara is based on the idea similar to Glimpse.
>
> (1) indexing + grep
> (2) multi-level indexing
>
> (a) small space for indexing
> (b) small update time
> (c) quick search
>
> Note that:
> small indexing   <->    quick search
> Kirara makes more index -> quick search
> Glimpse is single-level indexing.
>
> -------------
>
> Query
>
> Kirara does not support phrase search.
> The database is index of words,
>
> supporting:
> QE mode (query expression mode)
>         '&', '|', '*'
> The example:
>         'snoopy&html'
>         'snoop*&htm*'
>
> RE mode (regular expression mode)
>         '&', RE
> where RE denotes regular expression.
> The example:
>         'sn.*y&h.+l'
>
> RE mode is a bit slow. (a few second.)
>
> -------------
>
> Words
>
> Two or more runes.
> All words are converted to lower case.
> In English, words is composed of alphabets.
> The number of runes is configurable
>
> Assumption:
> Text is composed of space-separated words
> popular in English and many European Languages,
> but not in Japanese.
>
> -------------
>
> The user's interface
>
> Best match with Rio
>         term% kfind snoop
>         G snoop /sys/src/9/ip/
>         G snoop /sys/src/cmd/spell/
>         G snoop /sys/src/9/kw/
>         ...
>         term% G snoop /sys/src/9/ip
>         devip.c:34:     Qsnoop,
>         devip.c:95:     case Qsnoop:
>         devip.c:98:             devdir(c, q, "snoop", qlen(cv->sq),
> cv->owner, 0400, dp);
>         ...
> Note that: two steps
> 1. find directories
> 2. find files and the contents
> Step 2 is actually 'grep'. we can use RE.
>
> Two-steps search is not a weekness, but a desirable feature.
> Because we have so many files that are hit by the query.
>
> -------------
>
> The organization
>
> My example
>
> /n/other/kirara/sysdb
> target: (/lib /sys/lib /sys/src /sys/man /sys/include /sys/doc /rc)
>
> /n/other/kirara/usrdb
> target: $home/^(bin/rc lib netlib doc adm issues srclib src sources)
>
> Indexing target is fully configurable.
>
> -------------
>
> Multi-Level Indexing
>
> (1) Indexing (top level)
> word to directory mapping
>
> sysdb/index             # main index                                    #
> used for RE mode
> sysdb/mindex    # meta index (alphabetic index) # used for QE mode
> sysdb/dind/*    # rough index of each directory
> sysdb/QTDir             # map table (QID, mtime, path-to-dir)
>
> index           # word to dir QID
>         aa      0000000000014f0a
>         aa      000000000001a1e0
>         aa      000000000001a26e
>
> mindex  # word to range in index
>         aa 0 126669
>         ab 126669 491569
>         ac 491569 1258566
>         ad 1258566 1852467
>         ...
> dind/*                          # `*' is a directory QID
>         0000000000014f05
>         0000000000014f0a
>         000000000001a1ce
>
> usrdb is same.
>
> (2) Indexing (directory level)  # optional
> word to file mapping
>
> sysdb/find/*/ind.gz     # fine index of the directory (gzipped)
> sysdb/find/*/qtn        # map table (QID, mtime, name)
> where `*' is a directory QID
>
> usrdb is same as sysdb.
>
> -------------
>
> Experiment
>
> (a) hardware
> GA-H61M-USB3-B3
> Intel Pentium G860 (3GHz)
> DDR3 PC3 4GB
>
> (b) software
> 9front
> cwfs64x
>
> -------------
>
> The performance (compression ratio)
>
> target   target  num_of_dirs      indexing
> sysdb:   556 MB    1790 dirs             49 MB
> usrdb:  6620 MB    8948 dirs            150 MB
>
> compression ratio: 49/556 (sysdb)
> note: usrdb includes many non-text file.
>
> -------------
>
> The performance (retrieval time)
> system dependent
>
> RQ search       # kfind foo
>
> 0.1 seconds.
>
> It is not important to make this time smaller.
> (sufficiently small)
>
> RE search       # kfind -r foo
>
> a few seconds
>
>
> -------------
>
> The performance (construction/update)
>
> (a) Construction time
> system dependent
>
> Initial construction
> need
>         10 minutes for sysdb
>         30 minutes for usrdb
>
> (b) Updating time
> two commands for update
>
> mkdb
>         20 seconds to a few minutes for usrdb
>         depends largely on state of cache
>
> mkdb1 (currently only for usrdb)
>         5 to 15 seconds for usrdb
>         mkdb1 needs event log
>
> -------------
>
> Scalability
>
> Main factors
>
> (a) retrieval time
> QE search: proportional to number of dirs that include the query
> RE search: proportional to size of index
>
> (b) initial construction time
> proportional to total data
>
> (c) update time
> mkdb:   proportional to number of dirs and the changes
> mkdb1:  proportional to changes and size of index
>
> -------------
>
> Used Tools
>
> (1) rc
>
> (2) grep, sed, awk, sort, diff, gzip, ...
>
> (3) some new tools written in C
>
> -------------
>
> What Kirara means?
>
> Kirara is name of a girl that appeared in a Japanese comic book.
> (But I have never read the book.)
> The name is seldom used in real world.
> From the name we Japanese imagine something glittering.
> I like the name.
>
> -------------
>
> References
>
> [1] GLIMPSE: A Tool to Search Through Entire File Systems
> Udi Manber and Sun Wu (1993)
> http://webglimpse.net/pubs/glimpse.pdf
> [2] Glimpse Documentation
> http://webglimpse.net/gdocs/glimpsehelp.html
>
>
>

[-- Attachment #2: Type: text/html, Size: 7504 bytes --]