The story of a robot that has to remember everything 一个关于"机器人如何记住一切"的故事

One tree.
Space, time & meaning, jointly. 一棵树，同时索引
空间、时间与语义。

By the end of one eight-hour shift, a warehouse robot has seen about 300,000 things. Then someone asks: 一台仓库机器人跑完八小时的班，大约看过三十万个东西。这时有人问它：

“the yellow pole near the loading dock, the last time you saw it?” “装卸口附近那根黄色立柱，最后一次见到是什么时候？”

One sentence, three kinds of clue: what, where, when. No existing index can read all three at once. TriDex is the one we built that can, and it provably never misses the right answer. 一句话，三种线索：是什么、在哪里、什么时候。现有的索引没有一个能同时读懂三种。TriDex 就是我们造的那个能读懂的。而且可以证明，它绝不漏掉正确答案。

never misses an answer, provably绝不漏答，数学上可证明 builds itself while the robot works机器人边工作，索引边生长 a week of memories fits in pocket-size RAM一周的记忆，内存只占口袋大小
position x ∈ ℝ³位置 x ∈ ℝ³ timestamp t时间戳 t embedding e ∈ 𝕊ᵈ⁻¹嵌入 e ∈ 𝕊ᵈ⁻¹
The cameras never stop. Every frame becomes records, each carrying a position, a timestamp and a semantic vector. TriDex indexes all three into one tree, live. 相机从不停转。每一帧都变成记录，各带一个位置、一个时间戳和一个语义向量。TriDex 把三者实时索引进同一棵树。
§1 · The problem§1 · 问题

Spatial indexes know where. Vector indexes know what. Nothing knows both. 空间索引懂“在哪”，向量索引懂“是什么”，没有索引两者都懂。

Databases have great indexes for each coordinate separately, and none for the combination. That’s the gap this work fills. 数据库领域为每种坐标都有出色的索引，唯独没有为“组合”造过。这项工作填的就是这个空。

SPATIAL INDEXES空间索引

R-trees, kd-treesR 树 · kd 树

Nested rectangles answer “what was in this area?” instantly[1]. But “yellow pole” can’t be written as a rectangle condition. 嵌套矩形能瞬间回答“这片区域有什么”[1]。但“黄色立柱”写不成一个矩形条件。

blind tosemantics e语义轴 e
VECTOR INDEXES向量索引

HNSW, DiskANNHNSW · DiskANN

A graph over the embeddings, searched by hopping toward the query[6],[7]. But the edges encode only similarity: “near the dock, an hour ago” can’t steer a single hop. 在语义向量上连一张近邻图，一跳一跳逼近查询[6],[7]。但边只编码相似度：“装卸口附近、一小时前”指挥不了任何一跳。

blind togeometry x, t几何轴 x, t
BOLT-TOGETHER拼接方案

One index per axis + join逐轴索引 + 求交

One index per coordinate, then intersect? Each index over-returns, blind to the other conditions. We prove the intersection converges to a full scan. 每种坐标各建一个索引再求交？每个索引都看不见其他条件，只能多返回。我们证明了求交最终退化成全库扫描。

forfeitscross-axis pruning跨轴剪枝
why bolting indexes together breaks · animated拼接方案为何失效 · 动画演示
Same query, two architectures. Left: conditions meet only at the final intersection, after most of the work is wasted. Right: TriDex applies all three conditions during the search, pruning (✂) any subtree that any one condition rules out. 同一条查询，两种架构。左边：三个条件直到最后求交才会合，大部分工作已经白费。右边：TriDex 在检索过程中同时施加三个条件，任何一个条件说“不可能”，整棵子树当场剪掉（✂）。
§2 · The structure§2 · 数据结构

One tree, two summaries per node: a bounding box and a spherical cap. 一棵树，每个节点两份摘要：一个包围盒，一顶球面帽。

Every node summarizes its subtree twice: a box around the positions and times, a cap around the embeddings. Together they answer one cheap question: what’s the best score down there? Not enough → skip the whole subtree. 每个节点用两份摘要概括子树：盒包住位置与时间，帽包住语义向量。它们回答一个便宜的问题：下面最高能得几分？不够高就整棵跳过。

node anatomy · drag the query节点解剖 · 拖动查询点试试 interactive可交互
Drag q and eQ: box and cap each yield an upper bound, and the bounds add into one number, which is why a single traversal can prune on any mix of conditions. 拖动 q 与 eQ：盒与帽各给一个上界，上界相加成一个总数，这正是一次遍历能在任意条件组合上剪枝的原因。

Mixed-axis splitting is what makes it one index混合轴切分，才让它成为“一个”索引

Different nodes split on different coordinates: time here, position there, semantics below. One tree is therefore a spatial, temporal and vector index at once; that’s the structural difference from three indexes glued together. 不同节点在不同坐标上切分：这里按时间，那里按位置，再往下按语义。一棵树因此同时是空间索引、时间索引和向量索引；这就是它与“三个索引粘在一起”的结构性区别。

§3 · Construction§3 · 构建

The data streams past once. The tree still comes out balanced. 数据只流过一遍，树照样平衡。

The stream can’t be replayed, so there’s no “collect everything, then sort”. The trick: building a balanced tree only needs three lightweight running statistics, each a classic one-pass estimator. 数据流不可重放，不存在“先攒齐、再排序”。诀窍在于：建平衡树其实只需要三个轻量的流式统计量，每个都是经典的单遍估计器。

Welford · 1962

Which axis first?先切哪根轴？

A running variance per axis[8], O(1) per record. The most spread-out axis gets split first. 逐轴的滑动方差[8]，每条记录 O(1)。哪根轴最分散，就先切哪根。

Oja · 1982

Which direction to cut?沿哪个方向切？

Positions and embeddings have no sort order, so Oja’s rule[9] learns the data’s main direction and every cut goes straight across it. 位置和语义没有天然排序，Oja 迭代[9]学出数据的主方向，每一刀都横切过去。

Bădoiu–Clarkson · 2003

How tight a cap?帽能收多紧？

A few fixed iterations[12] shrink each leaf’s cap; an imperfect fit only leaves it slightly loose, no record ever escapes. 固定几轮迭代[12]收紧每个叶子的帽；收得不完美也只是稍松，记录绝不会漏出去。

StreamBulkLoad · conditional-median splits, animatedStreamBulkLoad · 条件中位数切分动画
Each cut lands at the region’s own median, so it halves exactly and balance is guaranteed; on the right, parents merge their children’s summaries as the recursion returns. 每一刀都落在区域自己的中位数上，恰好对半，平衡有保证；右侧的父节点在递归返回时合并孩子的摘要。
§4 · Query processing§4 · 查询处理

One best-first traversal answers every shape of question, exactly. 一次 best-first 遍历，精确回答所有形态的问题。

Conditions come in two kinds: preferences (“near the dock”: closer scores higher) and hard filters (“last half hour”: outside is out). The search itself is one rule: always expand the subtree with the highest possible score, stop once k records are out. At that point nothing unexplored can beat them: the answer is provably exact. 条件分两种：偏好（“靠近装卸口”：越近分越高）和硬过滤（“最近半小时”：出界即出局）。检索只有一条规则：永远展开可能得分最高的子树，取满 k 条即停。此刻剩下的都不可能反超：答案可证明精确。

best-first traversal · pick a query shape abovebest-first 遍历 · 点上方切换查询形态
Grey ✂ branches were cut by a glance at the box, no vector math. The fourth query above finishes with zero vector computations. 灰色 ✂ 支路只看一眼盒子就被剪掉，不动向量。上面第四个查询全程零次向量计算。

How the plan gets picked执行计划怎么选

hard walks the tree and may stop early; collect scores every filtered record, the exact-method floor. adapt prices both and takes the cheaper; a wrong guess costs speed, never the answer. hard 走树、可提前停；collect 给每条过滤后的记录打分，即精确方法的成本下限。adapt 比价择廉；估错只损失速度，不损失答案。

One tricky case: cross-modal queries一个棘手情况：跨模态查询

Object → keyframe queries can never score high (the modalities sit in different clusters), so early stopping won’t fire. adapt probes a few samples first; weak scores, so it takes collect, staying within 2–7% of the floor. 拿物体找关键帧天生出不了高分（两种模态各聚一簇），提前停止失灵。adapt 先抽查几条样本，见分数都低，便改走 collect，代价只比下限高 2–7%。

§5 · How the others move§5 · 竞品是如何运作的

Now hand the opening question to the baselines, and watch. 现在，把开头那个问题交给各个基线系统，看看会发生什么。

Each animation first shows a system at its best, then hands it the mixed question: “yellow pole near the dock, last hour”. Brilliant at home; outside, they collapse. 每个动画先展示对手最擅长的一面，再递给它那道混合题：装卸口附近的黄色立柱，最近一小时”。主场出色，出了主场就崩塌。

DiskANN / Vamana[7],[17],[18] · greedy graph search, then the same search under filters贪心图搜索，然后给同样的搜索加上过滤条件
Act 1: pure semantic search: a few hops, recall 0.98. Genuinely excellent. Act 2: add the region + time filter, and the qualifying records (green) scatter across a graph whose edges only know similarity: even with the strongest published fix[18], recall falls to 0.08, and cross-modal queries return 0.00. 第一幕：纯语义检索：几跳收敛，recall 0.98，确实出色。第二幕：加上区域+时间过滤，满足条件的记录（绿色）散落在一张只认相似度的图上：即便用上已发表的最强补救[18]，recall 仍跌到 0.08，跨模态查询更是 0.00。
HNSW[6]

Hierarchical graph layers层级图

The in-memory standard for vector search. But the graph must stay resident, and it grows with the data: 26 → 69 MB over our stream, versus TriDex’s flat 9–15 MB. 内存内向量检索的事实标准。但整张图必须常驻内存，且随数据一起增长，我们的数据流上从 26 涨到 69 MB，而 TriDex 恒定 9–15 MB。

streamΘ(n) resident memoryΘ(n) 常驻内存
R-TREER 树[1],[3]

Nested bounding rectangles嵌套包围矩形

On a pure region query it beats us 7–42× in node visits, reported as measured. Add “last ten minutes” and TriDex draws level, then ahead; and the R-tree has no semantic axis and needs rebuilds to absorb a stream. 纯区域查询它以 7–42× 的节点访问赢我们，如实记录。但加上“最近十分钟”，TriDex 追平反超；而且 R 树没有语义轴，吸收数据流还得靠重建。

semanticno embedding axis无语义轴

The honest scorecard诚实的记分牌

We lose the two pure extremes by a bounded constant, and win everything in between, which is where most real questions live. 两个纯粹极端我们以有界常数落败；中间的一切归我们，而大多数真实问题都住在中间。

pure semantic纯语义 pure spatial纯空间 mixed conditions · most real questions混合条件 · 大多数真实问题 graph wins图索引赢 (we pay ~11×)（我们多付 ~11×） R-tree winsR 树赢 (7–42× visits)（7–42× 访问） TriDex: exact everywhereTriDex：全程精确 specialists collapse: 0.08 · 0.11 · 0.00专门结构崩塌：0.08 · 0.11 · 0.00 TriDex recall 1.00 across the whole spectrumTriDex 在整条谱系上 recall 1.00 graph recall ↓图索引 recall ↓
§6 · Online maintenance§6 · 在线维护

The stream never stops, so the index grows in segments. 数据流不停，索引就按“段”生长。

Rather than restructure one big tree mid-operation, TriDex works LSM-style[4]: records land in a crash-safe buffer, each hour freezes into an immutable segment, and segments merge upward into day- and week-level ones, so a time-windowed query skips irrelevant history whole segments at a time. 与其在运行中反复重构一棵大树，TriDex 采用 LSM 方式[4]：记录先进掉电不丢的缓冲区，每小时冻结成一个不可变段，段再逐级合并成天级、周级，带时间窗的查询因此整段整段地跳过无关历史。

the time-tiered forest · buffer → L0 → L1 → L2时间分层森林 · 缓冲区 → L0 → L1 → L2
A record is queryable the instant it hits the log, and deleting history just drops whole segments: 55,908 records retired in 39 ms, zero bytes rewritten. 记录一落日志即可查询；删除历史只是摘掉整段：55,908 条记录 39 毫秒退役，零字节重写。
§7 · Secondary storage§7 · 二级存储

Only the navigation skeleton stays in RAM. 常驻内存的，只有导航骨架。

Embeddings dominate storage (~4 KB per record). So each segment splits into three layers: the navigation skeleton (~3 MB/week) stays in RAM, cap vectors load from disk on demand, and raw embeddings are read last, only for the answers. 存储大头是语义向量（每条约 4 KB）。所以每个段拆成三层：导航骨架（每周约 3 MB）常驻内存，帽心向量按需从磁盘载入，原始向量最后才读，只为答案而读。

an out-of-core query, layer by layer一条 out-of-core 查询的逐层触达
This query faulted in one cap chunk and read two payload blocks, nothing more. The theorem: a query’s I/O depends on its answer, not on how much history sits on disk. Bonus: the same column files answer SQL analytics directly, no second copy of the data. 这条查询只载入了一块帽心、读了两个载荷块，仅此而已。背后的定理：查询的 I/O 只取决于答案，与磁盘上的历史总量无关。额外收益：同一批列文件可直接跑 SQL 统计，无需第二份数据。
§8 · Evaluation§8 · 实验评估

What the experiments show. 实验结果。

111,731 records from a real perception pipeline over 1,513 indoor scenes[19],[20], streamed in live, queried from disk, no sampling, nothing built offline. Recall = the fraction of true answers actually returned; 1.00 is perfect. 111,731 条真实感知管线在 1,513 个室内场景中产出的记录[19],[20]，实时流入、从磁盘查询，不抽样、不离线预构建。recall = 实际找回的正确答案比例，1.00 为满分。

0
recall across all 396 filtered test conditions, not one correct answer missed, anywhere396 组带过滤条件的测试全部 recall 1.00，没有漏过任何一个正确答案
0×
average cost of filtered queries; the exactness floor (scoring all survivors) is 1.0×带过滤查询的平均代价；精确成本下限（打分全部幸存记录）记为 1.0×
0 MB
resident memory, flat across the whole stream (9–15 MB); the graph grows 26→69 MB常驻内存全程恒定（9–15 MB）；图索引则从 26 涨到 69 MB
0 ms
to retire 55,908 records: a catalog edit, zero bytes rewritten删除 55,908 条历史记录：纯目录操作，零字节重写

Recall across query shapes (full corpus)各查询形态的 recall（全量语料）

recall@10 vs. exact ground truth · hardest cell per batteryrecall@10 对照精确真值 · 每组实验的最难单元
TriDexDiskANN

The filtered-query collapse deepens with scale过滤查询的崩塌随规模加深

semantic search under the tightest region + time filter · recall as the stream grows最紧“区域 + 时间窗”过滤下的语义检索 · recall 随数据流增长的变化
TriDex (exact)DiskANN

Resident memory on the live stream实时流上的常驻内存

MB resident vs. records ingested常驻 MB 数 vs. 已摄取记录数
TriDexDiskANN

Cost against the exact floor对照精确下限的查询代价

embedding evaluations, normalized to collect = |F| = 1.0嵌入计算次数，按 collect = |F| = 1.0 归一化
TriDex adaptexact floor |F|精确下限 |F|
References参考文献

Cited in this page本页引用

  1. A. Guttman. R-trees: A Dynamic Index Structure for Spatial Searching. SIGMOD, 1984.
  2. S. Leutenegger, M. Lopez, J. Edgington. STR: A Simple and Efficient Algorithm for R-tree Packing. ICDE, 1997.
  3. P. O’Neil, E. Cheng, D. Gawlick, E. O’Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica, 1996.
  4. Y. Malkov, D. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search using HNSW Graphs. IEEE TPAMI, 2018.
  5. S. J. Subramanya et al. DiskANN: Fast Accurate Billion-point Nearest Neighbor Search on a Single Node. NeurIPS, 2019.
  6. B. P. Welford. Note on a Method for Calculating Corrected Sums of Squares and Products. Technometrics, 1962.
  7. E. Oja. Simplified Neuron Model as a Principal Component Analyzer. J. Math. Biology, 1982.
  8. M. Bădoiu, K. Clarkson. Smaller Core-Sets for Balls. SODA, 2003.
  9. A. Singh, S. J. Subramanya, R. Krishnaswamy, H. V. Simhadri. FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search. arXiv:2105.09613, 2021.
  10. L. Patel, P. Kraft, C. Guestrin, M. Zaharia. ACORN: Performant and Predicate-Agnostic Search over Vector Embeddings and Structured Data. SIGMOD, 2024.
  11. A. Koukounas et al. jina-clip-v2: Multilingual Multimodal Embeddings for Text and Images. arXiv:2412.08802, 2024.
  12. A. Dai, A. X. Chang, M. Savva, M. Halber, T. Funkhouser, M. Nießner. ScanNet: Richly-Annotated 3D Reconstructions of Indoor Scenes. CVPR, 2017.