1. Please edit your question to incorporate all relevant information into the question, so we don't need to read the comments to understand the full context, and then flag the comments as obsolete. Thank you! 2. I'm not sure whether "help fine-tuning your memory allocation strategy" is going to be on-topic here. If it's about implementation details, it's probably not suitable here.

@D.W. 1. All of the comments are obsolete now. 2. I'm not too worried about the implementation details, but I do remember from CS classes that there are some analytical approaches we can apply that help for both the hash maps and determining partition sizes.

I don't see that any of them have been incorporated into the question, and the question has not been edited since I made my comment. For instance, I don't see a precise description of the search problem you want to solve; I don't see a precise description of your algorithm (I'm not sure how to answer a question about managing memory in your algorithm if we don't know what your memory is). You don't state what the constraints on partition sizes are, what counts as optimal, how partition sizes affect optimality. I don't understand why you've rejected nearest neighbor data structures.

@D.W. 1) The comments are obsolete because the question was edited on SE before it was migrated here. 2) Give me a little bit to mathematically formalize the problem, I tend to work more in a CS&E space so some of my notation is a bit rusty. 3) Other nearest neighbor approaches were rejected because the data set as a whole updates every time step (i.e., everything is moving).

I still don't get it - why do you need a 3D matrix $h_l$? Why don't you simply make $h_l$ a standard hash table indexed by the integer point (round(x/r),round(y/r),round(z/r)), with values = a bucket of entities? Then the search for an entity near to (x,y,z) can be done by looking into the 27 neighbours (including itself) of (round(x/r),round(y/r),round(z/r)).

... that will reduce your capacity problem to one dimension, instead of 3. That makes your question much simpler: if you expect m entities at maximum, a good hash table capacity is typically 2m.

@DocBrown Also, in the context of my specific problem, I'm not even sure I could determine an $r_{max}$ since there is some stochasticity involved with it as well. However, I'm trying to keep the question fairly generic since I've seen similar problems pop up elsewhere.

@rjzii: well, above you linked to the fixed-radius near-neighbours problem, and a fixed radius is exactly the opposite of a variable radius, that's why I asked you twice why you don't follow the algo given in that Wikipedia article. Variable radius - where, when and how often is the radius changed? A new one for every search?

@rjzii I find it highly unlikely that there's a real world requirement that says you need to do something in constant time. Typically, it would be something like search in X (clock) time with up to N elements. It's often the case that algorithms with poor O time are the fastest within a given context. For example iterating through an usorted array will often beat searching a hashtable for small N.

@DocBrown D'oh! That link isn't in the question any more though, the text of the question should be fairly on point and I updated the psudo-code. In my case though there are multiple entity types, each of which can have their own $r$ value. The $r$ should be stable for the duration of the for loop though.

@JimmyJames Not sure if you caught the updates to the question, but the starting conditions are 10M entities and that can double or triple during execution. Sure for small $N$ I'll whip up a bubble sort knowing that quick sort is better, but my time is more valuable in those cases and the time difference is minuscule. In this case though, the model already take around 30 minutes to converge, I'd rather not do anything to make it take longer. The whole point of this exercise is to speed things up.

@rjzii "The whole point of this exercise is to speed things up." And my point is that O(1) doesn't necessarily speed things up. By insisting that it must be O(1), you exclude a huge number of possible solution paths. The log of 10M is not a very large number. Say each step takes around 10,000 clock cycles; we'll call that 10 microseconds. That's 200 microseconds for a search. If this is an academic exercise then have fun but if you actually have an engineering problem to solve, you should put some real numbers on this.

I once coded up a k-tree type structure for finding distances between points in an unlimited number of dimensions. The approach I went with was semi recursive such that if a point was close enough to another cell, that cell would be searched on a different thread. This could be designed to be done in parallel. If there is no algorithm that meets the requirements you have given, are you going to just give up?

@JimmyJames It's actually a real modeling problem - I work within the CS&E domain - and in terms of real numbers, for 1M entities it takes about 30 minutes to converge and that is without any searching being done. The radial search is a new feature and the existing data structures didn't even support it. It doesn't have to be $O(1)$ for CURD operations, but that $O$ needs to be as low as possible since typically each iteration of the for loop will have either an update or multiple deletes and inserts.

If there is an approach that can handle fast searches as well as constant updates to the data structure I'm open to hearing about it. However, based on all of the reading I've been doing so far, partitioning seems to be the best approach to things.

@rjzii: you may consider to update your question to supply a little bit more information about how r is calculated.

This keeps coming back to you needing constant time updates but that can't really be a requirement. If you really need a constant time insert: just put in waits in order to make all inserts as slow as the slowest one.

@rjzii, I don't understand what "partitioned according to s" means. I don't understand what "Project a movement" means. What is a "movement"? What does it mean to project it? How is s defined? You ask us how to determine s but don't define s or what criteria it must satisfy, so I don't know how we're supposed to answer this question.

Also, I think you misunderstood my point about array traversals. I wasn't talking about development time. I'm saying that simply iterating over an array (O(n)) will outperform hashtable lookups (O(1)) for values of N under some threshold. That's why I think a k-tree structure works best here. You figure out that threshold for the platform and then base the size of the cells on that. If you have multiple CPUs, you search the nearest cells in parallel.

To make inserts fast (but not necessary O(1)) you index the cells or create some sort of tree. Let's say you have 1000 points per cell, that's only 10K cells for 10M. Say you create a index binning the cells by dimension. That's maybe 20 something bins per dimension. Find the cell that contains your point in all three indexes (dimensions). It's not constant but it might be fast enough.

@JimmyJames I understand the point about array traversals just fine. However, you haven't done anything to convince me that what you are asserting will apply in this situation. Plus k-d trees are only O(log n) in the average case so I could end up with a model that has a the worse case O(n) insertions often enough to slow everything down. The really insidious part of this model is the fact that everything is always moving and inserts-deletes are happening on a regular basis.

@D.W. Projecting a movement means that the entity calculates a movement to a new position and uses that location to search for matching entities. If a match is found f() is called which will destroy one or more entities and create one or more entities. If a match is not found than the location of the entity is updated to the new location. Realistically it's a bit of a micro-optimization, but it's low hanging fruit to avoid the update if we are unsure if the entity will continue to exist.

The s used to partition the 3D lattice is the really insidious part because I don't know how to explain that better than I already have. However, the link in the question takes you to a slide deck for a presentation that discusses spatial partitioning strategies at a really high level.

It looks like one simple strategy is limit the bin size to the the size of your search radius, but that's only effective when r is fixed.

In this case r is variable, although I might be able to throw some analysis techniques at it to come up with some sort of mean r as a starting condition. There's also some algorithm optimizations I can do, but those might be coding details as opposed to the CS.

However, my google-fu seems to be failing me over on ACM and IEEE Xplore since I'm either getting not hits or too many irrelevant hits. Some of the language overlaps with GIS as well which doesn't seem to help me very much, since there really isn't any way to index the entities.

I don't think it's our job to convince you that k-d trees are better. Instead, I think that's something you should evaluate. You have the data and you know the algorithm; we don't. You're in a position to do that evaluation; we're not. Or, to put it another way, given the requirements that we can understand k-d trees sound like the obvious solution. If you reject them out of hand it makes me wonder if there are some other requirements I don't understand.

If you do try k-d trees and they turn out not to meet your needs, then that'd also be a useful outcome, because it might enable you to identify your requirements and quantify them in a useful way. So, take the feedback not as "you should use k-d trees; I know that is the perfect solution" but rather as "you should try k-d trees and use that to improve your question; if they're not a good enough solution, use that as an opportunity to clarify and quantify your requirements".

As far as the answers to my questions, I wasn't really looking for you to explain it here in the chat room. Instead, I'm looking for you to edit the question to make the question clear, so we can understand everything we need to know from reading the question (without reading comments/chatroom).

@D.W. I agree, but given that @JimmyJames has been pushing them hard, the onus is kind of them to either give me a way to evaluate k-d trees on the back of an envelope, or just my judgement that they aren't appropriate for this particular application. I could just as easily say that R-trees would be better... but without a logical grouping it doesn't make sense to use them.

Plus, I already pointed out in the question that O(c) < O(log n) in this case and since N is only getting bigger I don't see that flipping the other way any time soon. Plus, there's always the chance that we can bump into the O(n) worse case for CRUD operations.

Before I revise the question, does what I said here in chat clarify things for you?