News for hackers. Stuff that matters.
Re:Writing a full-text search engine using Bloom filters (2013) by kragen on Wednesday June 10, 2020 @02:52AM (#23474629)
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.

In 2006 I built the regular kind of posting-list inverted index for my web pages at http://canonical.org/~kragen/inverted-index.html. I just used regular HTML <table>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't think I ever implemented the actual client-side JS search engine.

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 https://www.mail-archive.com/[email protected]/msg0... and the algorithm is outlined in https://www.mail-archive.com/[email protected]/msg001....

Three weeks ago, I wrote https://gitlab.com/kragen/derctuo/-/blob/master/recursive-bl... 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't thought about combining that with my 2006 client-side inverted-index search approach, but it's designed to have reasonable locality of reference, so it might work.

Related comment thread: https://news.ycombinator.com/item?id=23473303

— ⁂ —

Bloom filters are a reasonable thing to try when looking for the "frequency-domain representation of thinking", but I've long thought Pentti Kanerva'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.

You can recover the value of an attribute from an aggregate by XORing the aggregate with the attribute'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.

Re:Writing a full-text search engine using Bloom filters (2013) by memexy on Wednesday June 10, 2020 @03:27AM (#23474798)
Sounds interesting. Any links and references for "Fully Distributed Representation"? This is what I found when I Googled the quoted phrase: http://www.cap-lore.com/RWC97-kanerva.pdf.

Skimming the paper this reminds me of word2vec and similar techniques for embedding words into vector spaces but instead of using XOR the embedding is accomplished with another neural network. Here's a link to a good description of the embedding process: https://towardsdatascience.com/neural-network-embeddings-exp....

Re:Writing a full-text search engine using Bloom filters (2013) by kragen on Wednesday June 10, 2020 @03:54AM (#23474919)
Yup, that's the paper — I probably read it at the time from Norm's site, QEPD. More recently Pentti's been working on sparse distributed representations, which as I understand it greatly simplify the matching problem.

I think the latent-spaces approach of ANNs is pretty interesting but I don't feel like I understand it well enough. It's a bit lower dimensional than Kanerva's proposal, though.

Re:Writing a full-text search engine using Bloom filters (2013) by breuderink on Thursday June 11, 2020 @03:07AM (#23485976)
Here is a more recent paper [1] from Pentti Kanerva that gives a great introduction: http://www.rctn.org/vs265/kanerva09-hyperdimensional.pdf. More papers can be found with the query "vector symbolic architecture". I find it utterly fascinating.

[1] Kanerva, Pentti. “Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors.” Cognitive Computation 1 (2009): 139-159.

Re:Writing a full-text search engine using Bloom filters (2013) by bergstromm466 on Wednesday June 10, 2020 @02:26PM (#23480407)
> I like the idea of just downloading a summary file of the whole website and searching it on the client side.

I can't wait for this to exist. The Holographic chain by ceptr.org (Arthur Brock + Eric Harris-Braun) is the closest to an agent centric web [also called Protocol Cooperativism] that I've come across so far, it's truly distributed [1]. Have you come across them?

[1] https://medium.com/holochain/holochain-reinventing-applicati...

Re:Writing a full-text search engine using Bloom filters (2013) by 6510 on Thursday June 11, 2020 @01:51PM (#23491437)
Nice project. My gut says an agent based system is the right approach but this implementation doesn't go far enough. The agent is reduced to a world view while it should imho involve a willingness to do favors for other agents. It would be far less complicated (and dare I say less toxic) without a market. The list of systems all try to establish reliability/trust in their own way but we know who to trust irl. The service should just slow down if to few people in your circles are willing to contribute resources.
Re:Writing a full-text search engine using Bloom filters (2013) by bergstromm466 on Thursday June 11, 2020 @02:42PM (#23492011)
> it should imho involve a willingness to do favors for other agents.

Absolutely. Because it is agent centric it can do this completely transparently. Since the individual agent is only the starting point, what you describe will definitely be developed on top of it, as I would agree that this is a common use case.

The real groundbreaking breakthrough with this project is that they are putting the individual user back in the middle, enabling peer-to-peer networks organized into a beautiful symphony sometimes referred to as Protocol Cooperativism. It is in contrast to Platform Capitalism - what we have today, and which takes humongous rents through corporate middlemen and third parties.

Building out from the individual agent allows, for example, cooperative Open Value Networks to be built (Sensorica is working on this), where users have complete agency/autonomy over the protocols and agreements they use, as well as users being able to temporarily hand off decision-making to others if they trust them, to act on their behalf, reflecting how they work together in the real world.

Basically this project is allowing everybody to carry a copy of the rules. This allows the protocols to rapidly evolve and change to meet the shifting needs of individuals and their communities.

There is a project building on the work of Ceptr called Holo-REA (developed out of http://valueflo.ws), which is doing exactly what you describe above.

Here is a story to quickly explain their work:

http://mikorizal.org/ValueFlows-Story.pdf

If you read my comment, I'd be grateful to know if it helped clarify some things. Does it help you see how what you described above is possible?

Re:Writing a full-text search engine using Bloom filters (2013) by nwmcsween on Wednesday June 10, 2020 @03:02AM (#23474685)
So why not just use minhashing like google does? There is hyperminhash and a newer algo on GitHub (I forget the name) with even better properties.
Re:Writing a full-text search engine using Bloom filters (2013) by kragen on Wednesday June 10, 2020 @03:11AM (#23474730)
Because I didn't know about MinHash, even though it dates from 1997! Thank you!