News for hackers. Stuff that matters.
Re:Show HN: PageFish search algorithm by sonofgod on Tuesday July 17, 2018 @09:13AM (#17549468)
Instead of addition, why not use an actual hashing algorithm, truncated to a certain number of bits? That'll give you better binning and give you flexibility about filesize / number of file tradeoffs.

I like the idea of using unicode characters -- have you performance tested it to see if it gives superior performance to an ASCII filename of the same number of bytes?

Re:Show HN: PageFish search algorithm by peterburkimsher on Tuesday July 17, 2018 @09:36AM (#17549610)
Binning! That's the word, not "hash distribution" like I wrote. Yes, I'd like to experiment more with different hashing algorithms. It needs to run fast on the query side.

Unicode seems great, but I noticed that filenames are restricted on various platforms, including Github. Uppercase and lowercase URLs are equivalent. So perhaps I should consider a different subset of characters instead of the first 65536 Unicode characters.

Performance is much faster than grep, because it only reads a fraction of the file. I couldn't find a good benchmark for ElasticSearch/Lucene/Sphinx, and apparently there isn't an easy way to compare.

https://stackoverflow.com/questions/44846271/performance-com...

Re:Show HN: PageFish search algorithm by sonofgod on Tuesday July 17, 2018 @10:48AM (#17550050)
Whilst there's a few hashing algorithms explicitly designed to be memory and time-intensive to make password retrieval impractical, most are really fast, even in Javascript. (Given there's g and so should be fine but isn't particularly lightweight. oing to be network access, I expect it to be entirely negligible)

In terms of performance I was more wondering whether or not "£" (one code point, two bytes) was much less expensive than "Ao" (two code points, two bytes). Just restricting yourself to ASCII might also have advantages for ensuring portability.

https://qntm.org/safe might also be of interest: discusses potential issues with using unicode as a high-density encoding -- base-2048 is Twitter-safe.

Re:Show HN: PageFish search algorithm by nine_k on Tuesday July 17, 2018 @09:50AM (#17549704)
Making a longer hash than 2 bytes would help selectivity, and filesystems are usually very good at finding files by name.

Also, apparently the files are not sorted by name (or I failed to see it). Searching in a sorted file using binary search is logarithmic, much faster than grepping which is linear.

Sorting can be done once, when the files are formed. BTW inserting into a sorted file should also be pretty fast (cheaper than appending and re-sorting).

Re:Show HN: PageFish search algorithm by peterburkimsher on Tuesday July 17, 2018 @10:08AM (#17549814)
The data is in the order it came in from OSMNames.

http://osmnames.org/download/

When there's two elements with the same name (e.g. Geneva), the first result is the most common (the city I was born, not the town in the US).

Re:Show HN: PageFish search algorithm by netgusto on Tuesday July 17, 2018 @02:35PM (#17551967)
I proposed to use a simple polynomial hash https://github.com/peterburk/pagefish/issues/1