A join is a set of manuscript fragments identified as originally emanating from the same manuscript. We study manuscript join retrieval: Given a query image of a fragment, retrieve other fragments originating from the same physical manuscript. We propose Bag of Bags (BoB), an image-level representation that replaces the global-level visual codebook of classical Bag of Words (BoW) with a fragment-specific vocabulary of local visual words. Our pipeline trains a sparse convolutional autoencoder on binarized fragment patches, encodes connected components from each page, clusters the resulting embeddings with per image $k$-means, and compares images using set to set distances between their local vocabularies. Evaluated on fragments from the Cairo Genizah, the best BoB variant (viz.\@ Chamfer) achieves Hit@1 of 0.78 and MRR of 0.84, compared to 0.74 and 0.80, respectively, for the strongest BoW baseline (BoW-RawPatches-$χ^2$), a 6.1\% relative improvement in top-1 accuracy. We furthermore study a mass-weighted BoB-OT variant that incorporates cluster population into prototype matching and present a formal approximation guarantee bounding its deviation from full component-level optimal transport. A two-stage pipeline using a BoW shortlist followed by BoB-OT reranking provides a practical compromise between retrieval strength and computational cost, supporting applicability to larger manuscript collections.
Alex: Welcome to another episode of ResearchPod.
Sam: Today, we're looking at a paper called "Bag of Bags: Adaptive Visual Vocabularies for Genizah Join Image Retrieval" from researchers at Tel Aviv University.
Alex: So this is about piecing together old manuscript fragments?
Sam: Exactly. The core puzzle is how to automatically match damaged pieces from the same ancient book when standard methods overlook subtle handwriting differences.
Alex: Right—and these fragments come from somewhere specific?
Sam: Yes, the Cairo Genizah—a massive collection of medieval manuscript scraps found in an old synagogue in Cairo, now scattered across libraries worldwide. Scholars want to group fragments that originally came from the same physical book, called "joins," to better study history and culture. But manually comparing stained, torn pieces across institutions takes forever and doesn't scale to the whole collection.
Alex: Okay, so what's the main roadblock for computers doing this?
Sam: The usual approach uses something like a shared dictionary of visual patterns for all images. It counts how often common shapes or textures appear in a picture, much like tallying words in a text using one big word list. Researchers call this a Bag of Words model—but it averages everything into a global summary, washing out unique handwriting styles from each page, especially when damage makes backgrounds look alike.
Alex: Huh—so the computer misses what makes one writer's scribble different from another's?
Sam: That's right. Fragments from the same manuscript share only faint style cues, like how letters slant or connect, while unrelated ones might match in stains or aging. The paper introduces Bag of Bags, which builds a custom set of visual patterns just for each fragment, preserving those page-specific traits for better matching.
Alex: So instead of one dictionary for everything...
Sam: Precisely—each page gets its own tailored vocabulary of local shapes, clustered from its own character patches. They compare these custom sets directly.
Alex: So each fragment gets its own set of visual patterns clustered from its character shapes... How exactly do they turn that into a way to compare two pages?
Sam: They group similar character embeddings from one page into a small collection of average shapes—say, 20 main types—representing the most common ways letters look on that specific fragment. Each group also notes how often that shape appears, like the population size of that letter style. This creates a custom "bag" for the page: a handful of prototype shapes with their frequencies.
Alex: Okay, so it's like sorting your own drawings into piles of similar ones, instead of forcing everything into someone else's categories.
Sam: Right. To compare two pages, they measure the distance between these bags of prototypes. One straightforward way is to let each prototype from the first page find its closest match in the second, add up those shortest gaps both ways, and average them. This symmetric nearest-neighbor check handles cases where damage hides some shapes, since it doesn't require every prototype to match perfectly. Researchers call this the Chamfer distance.
Alex: That sounds useful for torn edges... But what if some shapes are more common on one page than the other?
Sam: They account for frequency with a refined version that treats the cluster sizes as amounts of "mass" to shift between the two sets of prototypes, finding the cheapest way to reassign them while respecting those counts. It's like optimally pairing supplies from two warehouses, weighted by how much each has, to minimize transport cost. The paper calls this BoB-OT, using an efficient approximation called Sinkhorn to solve it quickly. This mass-aware matching better captures handwriting styles where certain letter forms dominate a page.
Alex: Huh... So the frequencies help spot if two pages use the same slants or connections more often.
Sam: Exactly—and on the Genizah benchmark of hundreds of fragments across 100 known joins, this approach finds correct matches about 6% more often at the top rank than the global Bag of Words method. It preserves those subtle, page-specific traits that get lost otherwise. The paper suggests this makes a meaningful step for scaling joins in large collections.
Alex: So Chamfer pulls ahead in practice... What makes it handle the damage better than the other matching options they tested?
Sam: One alternative forces a strict one-to-one pairing between every prototype on the first page and one on the second, like assigning each student to a unique seat in a classroom no matter the sizes. It finds the overall cheapest way to match them up completely, using a method called the Hungarian algorithm. The paper labels this BoB-Hungarian, and while it's mathematically clean as a true distance measure, it demands full coverage—which hurts when fragments are torn and miss entire character types.
Alex: Right, so no room for partial matches... And the mass-weighted one you mentioned earlier?
Sam: BoB-OT builds on that by letting common shapes carry more weight in the pairing, proportional to how often they appear on each page—like prioritizing bulk shipments over rare items when calculating delivery costs between stores. It solves for the minimum-cost way to move those weighted amounts using an efficient tool called Sinkhorn. Still, Chamfer outperforms both because it lets each shape pick its best partner independently, rewarding any overlap without punishing gaps from damage.
Alex: Huh—that fits the torn edges perfectly. How does this stack up against the usual global approach?
Sam: The baseline pools all prototypes across the dataset into one shared dictionary, then tallies how often each page uses them. BoB avoids averaging away page quirks this way, and Chamfer on BoB bags finds the right join about 78% of the time at the top spot on the Genizah set—roughly 6% better relatively—because it keeps local styles sharp for degraded matches.
Alex: Okay, so the custom bags plus flexible matching make the difference... The paper notes Chamfer lacks some math properties, though?
Sam: Yes—unlike Hungarian or OT, Chamfer doesn't always satisfy the triangle inequality, meaning distances don't behave perfectly for sorting large groups. But in this damaged domain, its leniency on partial overlaps wins empirically across metrics. The authors position it as a practical choice, with OT offering guarantees if needed for other tasks.
Alex: The paper mentions distance separation between matching and non-matching pairs... Does that show the custom bags actually create clearer groupings?
Sam: They checked how far apart the distances are for true joins versus unrelated fragments. The average gap between those two types of distances is larger with the custom bags than with the global approach—suggesting the page-specific prototypes pull real matches closer together while pushing mismatches farther.
Alex: Okay, that diagnostic makes sense... How about the computing side? Does building these custom sets slow things down too much?
Sam: Comparing two custom bags with Chamfer takes time proportional to the square of the number of prototypes. Fancier mass-weighted pairing jumps higher, but precomputing all distances for hundreds of images finishes in seconds. For bigger collections, they suggest a two-stage setup where a quick global filter grabs top candidates first, then precise bag matching reranks only those, keeping query times low regardless of scale.
Alex: Right, and they tested tweaks to the setup... Like how many prototypes per page?
Sam: They varied the cluster count from 8 to 64 and found performance climbing to around 32 prototypes before dipping—meaning too few lose detail, too many add noise from rare outliers. A middle ground like 20 balances expressiveness and speed well for these scripts.
Alex: So design choices matter a lot...
Sam: Exactly. Sparsity in the embeddings—favoring a few strong features per character—boosted top matches by focusing on distinctive traits over fuzzy ones. Keeping original letter shapes during prep, without stretching, also helped by preserving width clues key to handwriting.
Alex: Yeah, tuning those details seems key... How solid is the testing overall? They mention the dataset size.
Sam: The evaluation uses a manually checked subset of 287 images forming 100 known joins, which reflects how hard it is to get expert-verified ground truth. The full Genizah has over 250,000 fragments, so this hasn't been run end-to-end there yet. They designed the pipeline to scale, though, expecting per-fragment adaptation to shine more as stylistic differences grow in a huge mix.
Alex: Right—so promising at scale, but needs bigger proof... Any other limits they flag?
Sam: They stuck to Bag-of-Words baselines with the same encoder to spotlight the adaptive vocabularies' edge, leaving comparisons to newer learned models for later. It also focuses on their benchmark scripts, so tweaks like handling tinier or more degraded pieces remain open. Optimal cluster counts may shift by text complexity, too.
Alex: Huh—that keeps it honest. Still, for piecing together history...
Sam: Exactly. Overall, BoB-Chamfer makes a clear improvement—about 6% relative gain at top matches—by keeping page-specific shapes crisp where globals blur them. The two-stage setup lets it handle full collections practically, aiding scholars in reconstructing lost texts without endless manual work.
Alex: That's a grounded step forward. Appreciate the breakdown, Sam—shows how small tweaks in representation can matter a lot.
Sam: My pleasure, Alex. This work underscores modeling local structure over global stats for these challenges.
Alex: That's it for this look at Bag of Bags for Genizah joins. Thanks for listening to ResearchPod.