Path: Xl.tags.giganews.com!local-2.nntp.ord.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 28 Mar 2024 04:05:43 +0000
Subject: Re: Meta: a usenet server just for sci.math
Newsgroups: sci.math,news.software.nntp
References: <8f7c0783-39dd-4f48-99bf-f1cf53b17dd9@googlegroups.com>
 <1b50e6d3-2e7c-41eb-9324-e91925024f90o@googlegroups.com>
 <31663ae2-a6a2-44b8-9aa3-9f0d16d24d79o@googlegroups.com>
 <6eedc16b-2c82-4aaf-a338-92aba2360ba2n@googlegroups.com>
 <51605ff6-f18f-48c5-8e83-0397632556aen@googlegroups.com>
 <b0c4589a-f222-457e-95b3-437c0721c2a2n@googlegroups.com>
 <5a48e832-3573-4c33-b9cb-d112f01b733bn@googlegroups.com>
 <8wWdnVqZk54j3Fj4nZ2dnZfqnPGdnZ2d@giganews.com>
 <MY-cnRuWkPoIhFr4nZ2dnZfqnPSdnZ2d@giganews.com>
 <NqqdnbEz-KTJTlr4nZ2dnZfqnPudnZ2d@giganews.com>
 <FqOcnYWdRfEI2lT4nZ2dnZfqn_SdnZ2d@giganews.com>
 <NVudnVAqkJ0Sk1D4nZ2dnZfqn_idnZ2d@giganews.com>
 <RuKdnfj4NM2rlkz4nZ2dnZfqn_qdnZ2d@giganews.com>
 <HfCdnROSvfir-E_4nZ2dnZfqnPWdnZ2d@giganews.com>
 <FLicnRkOg7SrWU_4nZ2dnZfqnPadnZ2d@giganews.com>
 <v7ecnUsYY7bW40j4nZ2dnZfqnPudnZ2d@giganews.com>
 <q7-dnR2O9OsAAH74nZ2dnZfqnPhg4p2d@giganews.com>
 <Hp-cnUAirtFtx2P4nZ2dnZfqnPednZ2d@giganews.com>
 <MDKdnRJpQ_Q87Z77nZ2dnZfqn_idnZ2d@giganews.com>
From: Ross Finlayson <ross.a.finlayson@gmail.com>
Date: Wed, 27 Mar 2024 21:05:44 -0700
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.6.0
MIME-Version: 1.0
In-Reply-To: <MDKdnRJpQ_Q87Z77nZ2dnZfqn_idnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <-bOdnWSSIMUKcZn7nZ2dnZfqnPednZ2d@giganews.com>
Lines: 384
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-pAKAd5/5Rre6kRuAb5zLHpn22eNfdiEfLPGMAo+642n0DnvTUWpVz5FHwaOgi2Xa7r6vtm991ivLpHH!3n43tmkD1ujVgTcHbatTi4nyiuy/xApgFln8lyB/jt7Jk+fTaR0EC0FZlgNbHSZbSC9UvEFPJ7GM
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
Bytes: 18998

On 03/26/2024 06:04 PM, Ross Finlayson wrote:
> arithmetic hash searches
>
> take a hashcode, split it up
>
> invert each arithmetically, find intersection in 64 bits
>
> fill in those
>
> detect misses when the bits don't intersect the search
>
> when all hits, then "refine", next double range,
>
> compose those naturally by union
>
> when definite misses excluded then go find matching partition
>
> arithmetic partition hash
>
> So, the idea is, that, each message ID, has applied a uniform
> hash, then that it fills a range, of so many bits.
>
> Then, its hash is split into smaller chunks the same 1/2/3/4
> of the paths, then those are considered a fixed-point fraction,
> of the bits set of the word width, plus one.
>
> Then, sort of pyramidally, is that in increasing words, or doubling,
> is that a bunch of those together, mark those words,
> uniformly in the range.
>
> For example 0b00001111, would mark 0b00001000, then
> 0b0000000010000000, and so on, for detecting whether
> the hash code's integer value, is in the range 15/16 - 16/16.
>
> The idea is that the ranges this way compose with binary OR,
> then that a given integer, then that the integer, can be
> detected to be out of the range, if its bit is zero, and then
> otherwise that it may or may not be in the range.
>
> 0b00001111 number N1
> 0b00001000 range R1
> 0b00000111 number N2
> 0b00000100 range R2
>
> 0b00001100 union range UR = R1 | R2 | ....
>
>
> missing(N) {
> return (UR & RN == 0);
> }
>
>
> This sort of helps where, in a usual hash map, determining
> that an item doesn't exist, is worst case, while the usual
> finding the item that exists is log 2, then that usually its value
> is associated with that, besides.
>
> Then, when there are lots of partitions, and they're about
> uniform, it's expected the message ID to be found in only
> one of the partitions, is that the partitions can be organized
> according to their axes of partitions, composing the ranges
> together, then that search walks down those, until it's either
> a definite miss, or an ambiguous hit, then to search among
> those.
>
> It seems then for each partition (group x date), then those
> can be composed together (group x month, group x year,
> groups x year, all), so that looking to find the group x date
> where a message ID is, results that it's a constant-time
> operation to check each of those, and the data structure
> is not very large, with regards to computing the integers'
> offset in each larger range, either giving up when it's
> an unambiguous miss or fully searching when it's an
> ambiguous hit.
>
> This is where, the binary-tree that searches in log 2 n,
> worst-case, where it's balanced and uniform, though
> it's not to be excluded that a usual hashmap implementation
> is linear in hash collisions, is for excluding partitions,
> in about constant time and space given that it's just a
> function of the number of partitions and the eventual
> size of the pyramidal range, that instead of having a
> binary tree with space n^2, the front of it has size L r
> for L the levels of the partition pyramid and r the size
> of the range stamp.
>
> Then, searching in the partitions, seems it essentially
> results, that there's an ordering of the message IDs,
> so there's the "message IDs" file, either fixed-length-records
> or with an index file with fixed-length-records or otherwise
> for reading out the groups' messages, then another one
> with the message ID's sorted, figuring there's a natural
> enough binary search of those with value identity, or bsearch
> after qsort, as it were.
>
> So, the idea is that there's a big grid of group X date archives,
> each one of those a zip file, with being sort of contrived the
> zip files, so that each entry is self-contained, and it sort of
> results that concatenating them results another. So
> anyways, the idea then is for each of those, for each of
> their message IDs, to compute its four integers, W_i,
> then allocate a range, and zero it, then saturate each
> bit, in each range for each integer. So, that's like, say,
> for fitting the range into 4K, for each partition, with
> there being 2^8 of those in a megabyte, or that many
> partitions (512), or about a megabyte in space for each
> partition, but really where these are just variables,
> because it's opportunistic, and the ranges can start
> with just 32 or 64 bits figuring that most partitions
> are sparse, also, in this case, though usually it would
> be expected they are half-full.
>
> There are as many of these ranges as the hash is split
> into numbers, is the idea.
>
> Then the idea is that these ranges are pyramidal in the
> sense, that when doing lookup for the ID, is starting
> from the top of the pyramid, projecting the hash number
> into the range bit string, with one bit for each sub-range,
> so it's branchless, and'ing the number bits and the partition
> range together, and if any of the hash splits isn't in the
> range, a branch, dropping the partition pyramid, else,
> descending into the partition pyramid.
>
> (Code without branches can go a lot faster than
> code with lots of branches, if/then.)
>
> At each level of the pyramid, it's figured that only one
> of the partitions will not be excluded, except for hash
> collisions, then if it's a base level to commence bsearch,
> else to drop the other partition pyramids, and continue
> with the reduced set of ranges in RAM, and the projected
> bits of the ID's hash integer.
>
> The ranges don't even really have to be constant if it's
> so that there's a limit so they're under a constant, then
> according to uniformity they only have so many, eg,
> just projecting out their 1's, so the partition pyramid
> digging sort of always finds one or more partitions
> with possible matches, those being hash collisions or
> messages duplicated across groups, and mostly finds
> those with exclusions, so that it results reducing, for
> example that empty groups are dropped right off
> though not being skipped, while full groups then
> get into needing more than constant space and
> constant time to search.
>
> Of course if all the partitions miss then it's
> also a fast exit that none have the ID.
>
> So, this, "partition pyramid hash filter", with basically,
> "constant and configurable space and time", basically
> has that because Message Id's will only exist in one or
> a few partitions, and for a single group and not across
> about all groups, exactly one, and the hash is uniform, so
> that hash collisions are low, and the partitions aren't
> overfilled, so that hash collisions are low, then it sort
> of results all the un-used partitions at rest, don't fill
========== REMAINDER OF ARTICLE TRUNCATED ==========