Comment by joshstrange | Hacker News Reader

Comment by joshstrange | Hacker News Reader

Love the idea, I have thought about this before and the main issue is training my self to click an extension to check. If an icon flashed when there was a HN submission (ideally only if I didn't come directly from HN since I already know) it would be way more useful.

That said we all know the big issue with that is privacy. I don't want an extension sending every url I visit to any service (directly to the API or through some third-party). I've mulled over this issue before and I'm not sure how much space it would take up to store a list of urls that have been submitted to HN (Maybe keep 1 month plus all submissions that got over 100 upvotes or something) and check against that local list.

Then, and only then, when you get a match you can call out to the Algolia API to get the HN url (or store that as well depending on size).

I have no idea, off the top of my head, what the storage requirements for this look like but I don't think they would be huge. The other issue (which I want to look into the source to see how this handles it) is the stupid social/ads tracking params that are added to URLs. Maybe there is a good list of these that you can remove (from both the current URL and the HN submission) so you can see if it's the same base URL.

Every day there are at most around a hundred articles that generate any meaningful discussion at all (see past). Let’s say each article takes up <=200 bytes (URL + title + some stats, a very generous limit actually), then one year worth of data is at most ~7 MB. That might be a bit too much but not by far. If you gate submissions by votes/comments threshold as a function of time, it’s conceivable to store metadata of all the good discussions on HN within 20 MB or even 10 MB.

Chrome and Firefox extensions can request the unlimitedStorage permission, btw. (Chrome has a 5MB default limit, Firefox doesn’t seem to have one.)

You could allow for errors and use a bloom filter to avoid the space issue:

https://en.wikipedia.org/wiki/Bloom_filter

Or you could use a privacy-preserving lookup API, but that might be too much traffic. A Bloom filter could be downloaded locally and is probably a better solution.

Bloom filter as first pass and then privacy-preserving lookup API if it returns "probably a match"?

If it returns "probably a match", you can just look up with HN directly, like it does now.

> I'm not sure how much space it would take up to store a list of urls that have been submitted to HN

I recently was wondering how much space this would take up myself. After a lot of searching, I found this reddit post, which links to an archive of Hackernews. It contains data from HN from late 2006 until mid 2018 and totals just over 2 gigabytes. These dumps contain all comments, job postings, polls, poll options, and stories.

I did some super quick analysis of the 2018-05 archive (the latest provided by this source). I found that there were 237,646 total items, and only 32,473 of those are stories. That's only ~14%. Assuming the ratio of stories to non-stories has been constant for the entire dataset, that's only 280 megabytes for the entire 2006 to 2018 set.

That data can further be shrunk by removing extraneous information from each story in the data. Mirroring the HN api, it has the following pieces of data for each item: author username, id, date retrieved, score, time posted, title, type, url, and whether its dead, how many descendants it has, and what items are its kids. I didn't attempt to reduce the data to only contain links, but I imagine it would be significantly reduce the size.

Once you've reduced the data down to a list of urls, I imagine it can be reduced even more by removing duplicate links.

Depending on the average size of the urls, it's not unreasonable to think that taking a hash of each of the urls would result in a smaller set of data.

On top of that, there's wonderful text compression, but I don't have the numbers on how much that would reduce the size of data.

If you can find that thread, I'd love to mirror that content!

I was curious so I downloaded a list of id-url pairs from here [0]. It's CSV formatted and contains 1_960_207 entries (last update being 22 feb 2019). It is 134MiB uncompressed and 35MiB compressed using xz, so definitely storable in a web extension.

IDs being integers smaller than 10_000_000, they can be stored in 3 bytes and using a 64 bits hash function is enough (using this approximation [1] with k=2_000_000 and N=2^64 gives p=1,08e-7) which accounts for 22MB for 2 million entries. Stats on duplicates would be needed to know the impact of bundling identical hashes together. Definitely doable!

Keeping up-to-date would be harder, having a server querying the API to collect and distribute the day-by-day data to every extension-user is probably the best option.

[0]: https://console.cloud.google.com/marketplace/product/y-combi... [1]: https://preshing.com/20110504/hash-collision-probabilities/

Comparing hashes would help a bit on both anonymity and size concerns.

I also think, in a majority of cases, one could remove all of the query parameters from a URL and still have the same page. I'm not 100% confident about this though

Yeah, I thought about that but there are still a number of blogs that use something like

    https://mysite.com/post.php?id=123

But it would work for a lot of sites to strip the query.

> params that are added to URLs. Maybe there is a good list of these that you can remove

Although not every page offers it, for those that do, comparing the canonical link [0] should be pretty robust.

[0] https://en.wikipedia.org/wiki/Canonical_link_element

That's a really good idea! Thanks for mentioning that, it's something I've used before (coded support for) but it completely slipped my mind when thinking about this.

Reply on news.ycombinator.com