Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking

Track materialization converts raw videos into reusable object tracks that downstream queries can run against without rerunning tracking, but extracting those tracks efficiently and with high fidelity remains expensive. Prior systems reduce track materialization cost through temporal frame sampling, but aggressive sampling spaces each track's detection points too far apart to faithfully capture the object's actual trajectory. In stationary video, however, large portions of each frame contain no objects of interest, and different sampling rates can be used to extract tracks from the remaining regions. Leveraging this idea, we present Tetris, a track-extraction system that decomposes videos into a tile-based polyomino data model, enabling fine-grained spatiotemporal pruning that reduces detector calls with minimal fidelity loss. Tetris implements track materialization in three steps: first, a classifier identifies relevant tiles and groups them into polyominoes. Then, we use an integer linear program (ILP) to prune redundant polyominoes under a user-specified accuracy constraint, before packing the remaining polyominoes into canvases to minimize detector calls. Across 7 stationary-video datasets, Tetris stays within a 5% tracking accuracy loss as compared to a reference pipeline that processes every frame in its entirety, while prior systems exceed this bound on 3 of the 7 datasets. Moreover, with this 5% bound, Tetris achieves up to 17.4x higher throughput than prior systems, and up to 68.8x higher than the reference pipeline. Conversely, Tetris delivers up to 0.42 higher HOTA tracking accuracy than the best prior system at matched throughput. The project page is at https://tetris-db.github.io .