As a small comment, this seems closely related to another recent paper: History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures (PODS 2024, Best Paper).
I'm not sure how they compare, since neither paper seems to know about the other. And I'm also not sure which paper came first, since the geometric search paper does not seem to post a publication date.
Whoah, cool. I'm one of the authors of the geometric search tree paper, and we totally hadn't see that paper, but will for sure dig in! Thanks for mentioning it.
I don't think the claim is true in quite as much generality as the author claims. Some deterministic data structures use much more space than time, for example, the deterministic implementation of a Van Emde Boas tree.
I think you're missing out on the time it takes to build the tree in the first place, which is O(M), equal the space complexity. People usually ignore this cost as a "preprocessing" factor, but it's a cost that's really there.
After this initial O(M) time and space cost, you do additional operations which only take up time, not space, so the claim Time >= Space holds here as well.
IcebergHT isn't just for persistent memory (although I can see why you might think it is based on the paper's title). The paper also gives experiments showing that the hash table performs very well in standard RAM, much better than other concurrent implementations.
I think you may have a backwards. Libcuckoo, CLHT, and TBB are widely used high performance C/C++ DRAM hash tables. I think TBB is the hash table Intel maintains, if I remember right.
So the DRAM experiments are apples to apples. It's actually the PMEM experiments, I think, that are comparing a new hash table on a new technology to previous hash tables that weren't designed specifically for that technology.
As a super minor grammar point for the author, "ubiquitous" is a rare example of a word that starts with a vowel but should be proceeded by "a" instead of "an".
I think that's got to be a great test for foreign spies!
"ubiquitous" starts with the sound of "you-biquitous" and so the suffix -n is a duplicated non-vowel. ("y" is probably a vocalic glide, but still not in {a,e,i,o,u}.)
I bet the real rule is some reality about feasibility of pronunciation, even though native english speakers see the rules explained in terms of spellings.
> I bet the real rule is some reality about feasibility of pronunciation, even though native english speakers see the rules explained in terms of spellings.
The rule as often given in English classes is to use "an" if a word starts with a "vowel sound", rather than starting with a vowel. So, it's "an herb" (since the 'h' is silent in (American) English), but "a ubiquitous".
Relatedly, you can infer whether someone likely pronounces "URL" by spelling it out (like "you are ell") or as a word (like "earl") based on whether they write "a URL" or "an URL".
As someone who uses a dialect/accent of English that means I often pronounce these "silent" letters (e.g. I would pronounce the "h" in herb), I've often wondered if selection of "a" vs "an" is supposed to be accent specific.
I think so, yes; if you say "herb" with a non-silent 'h', you'd write "a herb".
By way of example, the name Herb is commonly pronounced with a non-silent H, so even in a dialect where "herb" is pronounced "erb", you'd write "A Herb picked up an herb.".
> I bet the real rule is some reality about feasibility of pronunciation
YUP! Sorry I don't have a good citation handy, but lots of English grammar happens as a result of misaligned word boundaries. "napron" (from the French naperon) became "an apron". Orange (from the Arabic naranj)... "an ewt" became "a newt". etc.
Consider the imaginary world that the author describes, in which people's estimate of their score is independent of their actual score. Wouldn't it be fair to say that, in this imaginary world, the DK effect is real?
The point of the effect is that people who score low tend to overestimate their score and people who score high tend to underestimate. Of course there are lots of rational reasons why this could occur (including the toy example the author gave, where nobody has any good sense of what their score will be), but the phenomenon appears to me to be correct.
The author's example with random points is bad because you might reasonably expect people to behave differently than uniform random points.
It'd be reasonable to expect that people who are good at a thing estimate that they are good at it, and that people who are bad at a thing, estimate that they're bad at it. I mean, my kids love math and always estimate themselves to do well on math tests (and they usually do). They have classmates loudly detest math, estimate they'll do badly, and often do (at least somewhat). Similarly I'm a bad cook and I have no doubt that if I join a cooking contest, I'll get few jury points. The expected data is correlated.
So if a study finds that, well actually, the data is not at all that correlated! Lots of people who estimate that they'll do fine actually don't, and equally many people who estimate that they'll do badly, actually do fine (ie it looks like uniform random data), then that's surprising, and that's the D-K effect.
Right? I'm no statistician at all so I might be missing something.
If it's a statistical illusion, the correlation is still true, it just has no business being studied by psychologists.
If I roll a die, and then roll a second die, I might study the behaviour of the second die and wonder why it wants to add up to 7 with the first die. Since they're dice, I can dismiss that as a stupid idea, but if they were people, I could certainly be led astray by psychological theories about them.
The randomized version of this algorithm is also fun: repeatedly find an edge that is not yet covered, select one of the two end points at random, and add it to S.
It's a nice exercise to show that the randomized algorithm is also a 2-approximate algorithm, i.e., the size of S is at most twice the size of S_{OPT}, in expectation.
This is a classic example of price discrimination. Slowly but surely, companies such as Toyota will converge to a state where every consumer individually pays the maximum amount that the consumer is willing to pay for the product.
$8 a month may not seem like much compared to the cost of a car, but that's the point. Toyota will be able to get free extra money from a large population of people (many of whom will later barely even remember that they are incurring this regular cost).
As a small comment, this seems closely related to another recent paper: History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures (PODS 2024, Best Paper).
I'm not sure how they compare, since neither paper seems to know about the other. And I'm also not sure which paper came first, since the geometric search paper does not seem to post a publication date.
reply