Writing a full-text search engine using Bloom filters (2013)
I like the idea of just downloading a summary file of the whole website and searching it on the client side.  It seems like it can only scale up to some limited extent — it should be feasible for 1000 or 10000 pages, but maybe once you have 100 000 pages it will start to be a bit top-heavy.<p>In 2006 I built the regular kind of posting-list inverted index for my web pages at <a href="http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;inverted-index.html" rel="nofollow">http:&#x2F;&#x2F;canonical.org&#x2F;~kragen&#x2F;inverted-index.html</a>.  I just used regular HTML &lt;table&gt;s for the representation, trusting to Content-Encoding: gzip to squeeze out the resulting redundancy, and the index is split into many different files so that the client can snarf just the part of the index that interests it.  Building the index (over my smallish set of pages) was surprisingly easy, although I don&#x27;t think I ever implemented the actual client-side JS search engine.<p>The same year, I also wrote a search engine using a kind of structure similar to a Bloom filter per post, similar to the one Stavros describes, but transposed and encoded for better locality of reference; source code is in <a href="https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-hacks@canonical.org&#x2F;msg00134.html" rel="nofollow">https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-hacks@canonical.org&#x2F;msg0...</a> and the algorithm is outlined in <a href="https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-tol@canonical.org&#x2F;msg00155.html" rel="nofollow">https:&#x2F;&#x2F;www.mail-archive.com&#x2F;kragen-tol@canonical.org&#x2F;msg001...</a>.<p>Three weeks ago, I wrote <a href="https:&#x2F;&#x2F;gitlab.com&#x2F;kragen&#x2F;derctuo&#x2F;-&#x2F;blob&#x2F;master&#x2F;recursive-bloom-filters.md" rel="nofollow">https:&#x2F;&#x2F;gitlab.com&#x2F;kragen&#x2F;derctuo&#x2F;-&#x2F;blob&#x2F;master&#x2F;recursive-bl...</a> describing a data structure, not yet tested, for using a bunch of Bloom filters for indexing large data sets.  This structure seems like it might be capable of competing with traditional database sorted-column indexes for ad-hoc query evaluation, perhaps even exceeding their performance on some queries, though at a larger space cost.  I hadn&#x27;t thought about combining that with my 2006 client-side inverted-index search approach, but it&#x27;s designed to have reasonable locality of reference, so it might work.<p>Related comment thread: <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=23473303" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=23473303</a><p>— ⁂ —<p>Bloom filters are a reasonable thing to try when looking for the &quot;frequency-domain representation of thinking&quot;, but I&#x27;ve long thought Pentti Kanerva&#x27;s Fully Distributed Representation was interesting, in which each atom is encoded by a large random bitvector, attribute-value pairs are encoded by XORs of the atomic bitvectors, and aggregates of multiple attributes are encoded as the bitwise majority rule (with ties broken at random) of all their attribute-value pairs.<p>You can recover the value of an attribute from an aggregate by XORing the aggregate with the attribute&#x27;s atom and examining its Hamming distance from all the candidate atoms, a process which Kanerva originally suggested you could train a neural network to be able to do in better than linear time.  The atoms actually stored for that attribute will have a Hamming distance many, many standard deviations from 50%, while the false matches will all be within, say, six standard deviations.