J. Andrew Rogers, founder of SpaceCurve, writes about geospatial databases, spatial indexing and fast hash functions like MetroHash and AquaHash.
Commenters find his geospatial database posts influential and tantalizing, though one calls his claims overblown. HN links him for spatial indexing and hashing.
Andrew, everything you reveal publicly has been tantalizing! (See https://www.jandrewrogers.com/ for those who haven't stumbled upon his posts yet)
"There is virtually no literature on practical representations of topological spaces, never mind parallel algorithms using those representations. A thorough exposition of both the theory and practice is on the order of a few hundred pages of dense technical literature that no one has had time to write, despite multiple implementations. Watch this space." - October 2015, J. Andrew Rogers.
I emailed you back in 2016 to inquire about your work and wondered what had become of SpaceCurve. (Thank you for replying!) You mentioned recent work then on a "modality architecture." Is that related to the work you mentioned in your post above?
Obviously, you're a busy man with a desire and the potential to change the world with your creations. But perhaps also a drive to withhold your creations from public display until only after you have them distilled to their purest elegance?
If it is your intention to eventually share, I encourage you to do the world a great favor and just share what you've got so far (with a "no guarantees; no support" reminder in your README), even if some corners are unpolished, inscrutable, or built on shifting ideas. With an appropriate license, you'll at least get the benefit of easily taking bits of your implementations with you between projects, even without supporting anyone else who consumes it.
Do you have…
This guy talks a lot of crap. See his website for examples, and don't waste your time with him
<<<There is one significant drawback that should not be understated. Algorithm design using topology manipulation can be enormously challenging to reason about. You are often taking a conceptually simple algorithm, like a nested loop or hash join, and replacing it with a much more efficient algorithm involving the non-trivial manipulation of complex high-dimensionality constraint spaces that effect the same result. Routinely reasoning about complex object relationships in greater than three dimensions, and constructing correct parallel algorithms that exploit them, becomes easier but never easy.>>>
http://www.jandrewrogers.com/2015/10/08/spacecurve/
It's great to see you (jandrewrogers) of SpaceCurve reply to correctly to the question! Your blog post on why Geospatial Databases are Hard has long influenced me and a handful of others I've run into thinking about all of this.
Geohashed (X+Y) points in Redis is only peripherally related to actual geospatial database concerns, particularly big-data or ("NoSQL") spatial database concerns - how do you efficiently index anything other than point data (polygons, multi_polygons), or ask spatial queries (e.g., nearest neighbors) is not even close to being addressed.
Blog post here for reference: http://www.jandrewrogers.com/2015/03/02/geospatial-databases-are-hard/
Hi Shen - The state-of-the-art spatiotemporal database systems are based on topological embedding and geometric interval computation (hyper-rectangle cell/simplicial complex https://en.wikipedia.org/wiki/Simplicial_complex).
And while I don't know of any open-source systems based on this design, SpaceCurve is publicly available (http://www.spacecurve.com http://www.jandrewrogers.com/2015/10/08/spacecurve/) , and I've heard systems like this exist within IBM and Google.
Have you looked into this approach?
Could you elaborate on your comment about modern spatial databases not sequentializing storage along the curve? I would imagine parallel access across the curve, but wouldn't you want some reasonable sequential access at each cluster node to maximize IO speeds?
I've read your blog entries on SpaceCurve (http://www.jandrewrogers.com/2015/10/08/spacecurve/), found them very interesting but also just whetting the appetite. Are there no public reviews or papers covering discrete topology/sharding?
For example, running the sequence generator through AES rounds. This is keyed, very fast if the hardware supports it, and permutations of types smaller than the block size are collision-free and non-reversible[0] if the AES block is setup suitably.
In other cases, a 128-bit key is simply encrypted (conveniently being the same block size as AES), which allows you to put arbitrary structure inside the exported key.
[0] http://www.jandrewrogers.com/2019/02/12/fast-perfect-hashing/