Hi! Hammad here - Chroma’s CTO. First off, I have an immense amount of respect for the Turbopuffer team, they’ve build a solid product.
I understand your point. Chroma Cloud has been quietly live in production for a year, and we have been discussing this architecture publicly for almost two years now. You can see this talk I gave at the CMU databases group - https://youtu.be/E4ot5d79jdA?si=i64ouoyFMevEgm3U. Some details have changed since then. But the core ideas remain the same.
The business model similarities mostly fall out of our architecture being similar, which mostly falls out of our constraints with respect to the workload being the same. There are only so many ways you can deliver a usage based billing model that is fair, understandable, and predictable. We aimed for a billing model that was all three, and this is what we arrived at.
On aesthetics, that’s always been our aesthetic, I think a lot of developer tools are leaning into the nostalgia of the early PC boom during this AI boom (fun fact, all the icons on our homepage are done by hand!).
On differences, we support optimized regexes vs full-scans, lending better performance. We also support trigram based full-text search which can often be useful for scenarios which need substring matches. We also support forking, which allows for cheap copy-on-write clones of your data, great for dataset versioning and tracking git repos with minimal cost. We've been building with support for generic sparse vectors (in beta) which enables techniques like SPLADE to be used, rather than just BM25. You can also run Chroma locally, enabling low-latency local workflows. This is great for AI apps where you need to iterate on a dataset until it passes evals, and then push it up to the cloud.
Chroma is Apache 2.0 open source - https://github.com/chroma-core/chroma and has a massive developer community behind it. Customers can run embedded, single-node and distributed Chroma themselves. We've suffered from depending on closed-source database startups and wanted to give developers using Chroma confidence in the longevity of their choice.
Lastly, we are building with AI workloads front and center and this changes what you build, how you build it and who you build for in the long term. We think search is changing and that the primary consumer of the search API for AI applications is shifting from human engineers, to language models. We are building some exciting things in this direction, more on that soon.
"The obstacle is that until now, off-the-shelf vector databases could not index a dataset larger than memory, because both the full-resolution vectors and the index (edge list) needed to be kept in memory during index construction. Larger datasets could be split into segments, but this means that at query time they need to search each segment separately, then combine the results, turning an O(log N) search per segment into O(N) overall."
I was trying to make the point that the dominant factor becomes linear instead of logarithmic, but more accurately it's O(S log N) = O(N log N) because S is proportional to N.
Sure, I see. I think this is an area where complexity analysis doesn’t lead to useful information.
To be more correct it’s O(N/C log C) where C is the capacity of a segment. In this case you can ignore 1/C and log C as constant. So now sure, you actually just have O(N). But this is not super useful as it says that a segmented hnsw approach and brute force approach are the same - when this is really not the case in practice.
Also O(N log N) > O(N) so I’m not sure why we would ever do anything with segmentation according to that analysis if it were correct.
