5 ms·

Why send each URL to a server to be checked, instead of doing a periodic download of the (very small) list of HN links and comment counts, to be checked offline

• diggan 9y ago
  What makes you think it's a very small list? HN has been around since 2007, with a lot of submissions. Any guesses on the size of that? I think it's bigger than
  • xiphias 9y ago
    Another option is using a bloom filter (just like how Chrome does it for malware URL detection)
  • vijayp 9y ago
    You can sort HN by date, and few URLs are updated every day. So you can push a new bloom filter every day and a different list of updates every 5m. Then just check your URL against both of them.
  • tbirrell 9y ago
    Well... including comments it looks like we are pushing 16.3 million posts. The id in the url is sequential. If you are saving url, HN id, and comment count, that's probably no more than a couple megs, if even that.
    • Ajedi32 9y ago
      ~391 MB if we store SHA-1 hashes of the URLs (160 bits each) and HN ids and assume 16.3 million posts[1]. (Probably less, since, as you said, some posts are just comments.) If we're okay submitting one out of every hundred URLs as a SHA-1 hashed value to an external server, we can reduce that further to ~18 MB with a bloom filter[2]. [1]: https://www.google.com/search?q=(160+bits+%2B+32+bits)+*+16.3+million&oq=(160+bits+%2B+32+bits)+*+16.3+million https://www.google.com/search?q=(160+bits+%2B+32+bits)+*+16.... [2]: https://hur.st/bloomfilter?n=16300000&p=0.01 https://hur.st/bloomfilter?n=16300000&p=0.01
      • tzs 9y ago
        I don't think we need either a strong hash or to submit hashed URLs to a server. We can use an ordinary hash and the only URLs we need to submit to a server are story requests to HN, if we do this thing like this: Include in the extension a hash table construction as follows: foreach ID of an HN story submission URL = the URL of the submitted story URL = normalize(URL) insert_into_hash_table(URL, ID) insert_into_hash_table(key, val) is a function that inserts val into a hash table with key key. The hashing function does not need to be cryptographically secure. normalize(URL) is a function that takes a URL and normalizes it. What normalize means in this context is a little fuzzy, but the basic idea is that if URL_1 and URL_2 are different URLs to the same article, normalize(URL_1) == normalize(URL_2). NOTE: what you include with the extension is the hash table itself. Conceptually it is probably just a sparse array containing HN IDs, with maybe a little more depending on how collisions are handled. In the extension, do this: URL = normalize(URL_of_current_page) ID_list = lookup_URL_in_hash(URL) foreach ID in ID_list story = get_HN_story(ID) if (normalize(URL_of_story(story)) == URL show_story_comments(story) The hash is only used for data retrieval from a local hash table, so does not need to be cryptographically secure. After the hash lookup we have a list of candidate stories on HN that might match the browser story. It's a list because due to collisions there might be more than one HN story with matching hash. Note that all that is ever fetched from the server during operation of this are HN stories, so there is minimal information leakage.
        • Ajedi32 9y ago
          Don't hash tables typically store the key itself in the table though? Wouldn't that take up _more_ space per entry than a 160-bit hash? Using a sufficiently collision-resistant hash function allows you to eliminate the need to store URLs entirely, which in theory should reduce the size of the hash table significantly.
          • tzs 9y ago
            Whether or not you need to store keys depends on how you handle collisions. For instance, if we had a hash table whose keys were names, and whose values were telephone numbers, we'd probably have to store keys with the phone numbers so that in the case of a collision we could figure out which phone number matches the search key. If, on the other hand, we had a hash table that stored record numbers of employee records from our employee database, keyed by employee name, then we probably would not need to store keys with the hash table values. If there is a collision, we can just retrieve all of the colliding records from the database. Those records will contain the employee name, and we can use that to figure out which is the right one. For the HN comment extension we are closer to the second case. The HN story contains the URL, so in the case of a collision we can fetch all the colliding HN stories and see which one is the right one.
• jdormit 9y ago
  Mostly because it is a free extension and I don't want to pay for a server :)