Re: consistant failures on a new kind of spam

> No, sorry I didn't explain that more clearly.  SP uses a fixed size
> array for its hash table.  A term (word or phrase) is hashed into a 32
> bit hash code.  Then that code is mod'd down into an index in the
> array.   If the slot at that index is full SP tries the next index until
> it finds an empty slot (wraps around at end).  That's what I meant about
> a hash table degenerating into a list if the file is nearly full.  SP
> would try all of the slots in the file one after another looking for an
> empty one.  Same thing on look ups.  So an O(1) data structure can
> degenerate into an O(N) one.
> 
> It's always best to keep the table about half empty to make collisions
> unlikely.  A few collisions here and there don't hurt but a nearly full
> file would be a Bad Thing indeed.

Thanks for the explanation, I understand now. I'm embarassed to say, I 
wasn't cleaning my database in cron. The accuracy rate was fantastic which 
is why I didn't touch the configuration. Doing spamprobe dump | wc -l, I 
saw that my db was full. After a cleanup it is now approx 40% free.

I must say, this cleaning issue bothers me because it seems so sensitive to 
selecting the right parameters. In the past I cleaned too much, and it hurt 
filter accuracy. Perhaps some users aren't enjoying the full benefit of 
spamprobe because of a simple mistake like too aggressive cleaning? In 
other words we're asking users to make a very difficult adjustment, which 
has huge effects.

It would be nice to have a way to automatically clean somehow. We already 
have a probabilistic process which could be leveraged to our benefit. Here 
is an idea, what do you think?

Combine the idea of cleanup [junk_count] with the hash collision. Do not 
manually clean the database by removing terms. Let the collision (a rare 
event) guide us to the opportunity, then proceed to replace the existing 
entry if it has a low junk_count. Iterate if not possible on the first 
collision.

Here is the effect I think this would have - you would not be arbitrarily 
removing potentially useful tokens from the hash db (as you do with a 
regular cron cleanup). Instead, you would only be removing a 'useless' term 
if forced to by collision. I can't see how there would be a big performance 
hit, since you will quickly encounter unused terms that need cleaning. If 
you don't encounter any such (worst case) and have to iterate a lot, then 
the hash db is obviously too small to accommodate all the useful tokens 
encountered.

Any thoughts?


-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys - and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV