sujayakar · HackerTrans

6 bulan yang laludiscuss

I'd absolutely love to play with this. one idea I had is to train another model to create bitmaps of sidewalks and roads and add a simulation for pedestrians and cars. day/night cycle would also be so cool!

sujayakar

tahun laludiscuss

switch to auto mode and it should still work!

sujayakar

tahun laludiscuss

Here's an interesting negative result.

After watching this video, my first thought was whether recent results from columnar compression (e.g. https://docs.vortex.dev/references#id1) applied "naively" like QOI would have good results.

I started with a 1.79MiB sprite file for a 2D game I've been hacking on, and here are the results:

  PNG: 1.79 MiB
  QOI: 2.18 MiB
  BtrBlocks: 3.69 MiB

(Source: https://gist.github.com/sujayakar/aab7b4e9df01f365868ec7ca60...)

So, there's magic to being Quite OK that is more than just applying compression techniques than elsewhere :)

sujayakar

tahun laludiscuss

Deepseek is already using SSDs for their KV cache: https://github.com/deepseek-ai/3FS

sujayakar

tahun laludiscuss

I really love this space: Navarro's book is an excellent survey.

Erik Demaine has a few great lectures on succinct data structures too: L17 and L18 on https://courses.csail.mit.edu/6.851/spring12/lectures/

sujayakar

2 tahun yang laludiscuss

that's roughly what the wasm component model is aiming for!

https://hacks.mozilla.org/2019/11/announcing-the-bytecode-al...

sujayakar

2 tahun yang laludiscuss

can you specify the algorithm in more detail?

this looks to be solving a different problem than A*, which operates over discrete graphs. this looks to be operating in 2D continuous space instead.

so, what is the algorithm for finding the optimal point on the obstacle's outline for bypass (4)? is it finding the point on the outline nearest the destination?

then, how do you subsequently "backtrack" to a different bypass point on the obstacle if the first choice of bypass point doesn't work out?

there's something interesting here for trying to directly operate on 2D space rather than discretizing it into a graph, but I'm curious how the details shake out.

sujayakar

2 tahun yang laludiscuss

this is unbelievably cool. ~27ns overhead for searching for a u32 in a 4GB set in memory is unreal.

it's interesting that the wins for batching start diminishing at 8. I'm curious then how the subsequent optimizations fare with batch size 8 (rather than 128).

smaller batch sizes are nice since it determines how much request throughput we'd need to saturate this system. at batch size 8, we need 1s / ~30ns * 8 = 266M searches per second to fully utilize this algorithm.

the multithreading results are also interesting -- going from 1 to 6 threads only improves overhead by 4x. curious how this fares on a much higher core count machine.

sujayakar

2 tahun yang laludiscuss

I love playing with it at UltraHigh quality and 1 solver iterations. It reminds me of gradually incorporating one ingredient into another when cooking: like incorporating flour into eggs when making pasta.

sujayakar

2 tahun yang laludiscuss

+1. I'd be curious how much of a pessimization to uncontended workloads it'd be to just use `tokio::sync::RwLock`.

and, if we want to keep it as a spinlock, I'm curious how much the immediate wakeup compares to using `tokio::task::yield_now`: https://docs.rs/tokio/latest/tokio/task/fn.yield_now.html

sujayakar

2 tahun yang laludiscuss

looking forward to it!

I'd be curious if y'all end up supporting adding filter attributes to the inverted index that can then be pushed down into the posting list traversal.

for example, a restaurant search app may have (1) an embedding for each restaurant but also (2) a cuisine. then, if a restaurant has `cuisine = Italian`, we'd also store its ghost ID in a `cuisine:Italian` posting list.

at query time, the query planner could take a query like `SELECT * FROM t1 WHERE cuisine = 'Italian' ORDER BY DISTANCE(..)` and emit a plan that efficiently intersects the `cuisine:Italian` posting list with the union of the partitions' posting lists.

this feels to me like a potential strength of the inverted indexing approach compared to graph-based approaches, which struggle with general filtering (e.g. the Filtered-DiskANN paper).

sujayakar

2 tahun yang laludiscuss

very cool stuff! I just read the SPFresh paper a few days ago and was wondering if it's been implemented in industry (e.g. Turbopuffer's implementation of SPANN).

I'd be curious how y'all represent the posting lists for each partition in InnoDB:

- what IDs are you storing in the posting lists?

- how are the posting lists represented on disk? are they using compression and/or some form of skip indexing? the paper seemed to use a pretty simple block-based representation, but I'm curious what works well in practice.

- how do the posting list data structures themselves handle incremental updates and MVCC?

comments