Xapian devel - Mar 2014 - apply hash in doclength

Hi,


I'm writing my proposal, besides skip list, fixed width and VSEncoding,
I'd like to apply hash in storing doclength.


Firstly we devise a proper hash function h(). When dealing with a document with
did1, we have a chunk storing did1 and the length of the doc. Let t = h(did1),
then we use t+term as an index to save the chunk in B tree.
When  meeting did2, where h(did2) = h(did1)  = t, we append did2 and the length
of doc did2 to the chunk indexed by t+term. So when we want to get the length of
did2, we can exactly get the chunk containing did2 by querying B tree with
h(did2)+term.


The key is to devise such a h() that we have proper docids be hashed into same
chunk. If too many docids are in same chunk, the efficiency of searching in this
chunk will be too slow. If we have too many chunks, I'm afraid the
efficiency of B tree will be lowered.


Besides, inserting and deleting will be easy in this way.


I think taking modulus with a prime may be a good hash function. Depending on
docids, we can select different prime.


I'm trying to do further research in hashing, would you like to give some
suggestions about the algorithm?


------------------
Shangtong Zhang,Second Year Undergraduate,
School of Computer Science,
Fudan University, China.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.xapian.org/pipermail/xapian-devel/attachments/20140315/b03825fa/attachment-0002.html>

On Sat, Mar 15, 2014 at 02:36:11PM +0800, Hurricane Tong
wrote:
> Firstly we devise a proper hash function h(). When dealing with a
> document with did1, we have a chunk storing did1 and the length of the
> doc. Let t = h(did1), then we use t+term as an index to save the chunk
> in B tree.
I don't follow "t+term" here.  What term are we using?  And why
would
we want to involve a term?  We need to be able to find the doclength
independent of any particular term (and we don't want to save the
doclength once per term in the document - we used to do that and
it wastes a lot of space!)
> When  meeting did2, where h(did2) = h(did1)  = t, we append did2 and
> the length of doc did2 to the chunk indexed by t+term. So when we want
> to get the length of did2, we can exactly get the chunk containing
> did2 by querying B tree with h(did2)+term.
It's an interesting idea, but I don't think this is really going to work
well.

To implement MatchAll efficiently, we need to be able to read the used
document ids in ascending order efficiently, which we currently do by
reading the doclength list.  If you hash it, it's no longer in order,
so we'd need to find another way to do this.

And while matching, we access the doclengths which we access in
ascending order.  By hashing them, you ruin the locality of reference
which we currently have - accesses to the doclengths will jump around
all over the Btree.

Also, when we look up a doclength, we hash the docid, do a Btree lookup
(which is O(log(collection_size)) and then we need to scan through the
chunk to find the docid we want (out of all of those which hash the
same).

Currently looking up the next doclength just involves scanning forward
through the current chunk in many cases, and when it doesn't, the
next chunk we want will be in the same area of the B-tree so is
still cheaper to load than the essentially random block the next hash
key would take us to.

The aim is to make looking up the next doclength cheaper than it
currently is, not more expensive.

And during indexing, in the common case of adding new documents, we
can currently just accrue their document lengths until we have a
full chunk, then write that out and start the next chunk.  With the
hashed scheme, we'd have to load, update, and store each chunk as we add
a document (or else keep all the hashed blocks in memory, which is a lot
of memory for a large database).

Cheers,
    Olly