Afaik, a list of transactions is like a doubly linked list. You can get the parent and child from a transaction. The pointer just points to the latest mode in the linked list.
So, if you’re passed a transaction, it should be easy to discover its ancestry.
Unless I’m missing detail. A diagram would help! 
“Easy” like traverse millions of records on the network?
Easy, yes. Fast, maybe not. Obviously, it would depend on the number of transactions.
Iirc, blockchain validators do exactly that though.
If we essentially have a doubly linked list with a pointer to the head (latest), it is a well known data structure though. I’m sure we don’t need to reinvent wheels to find a solution.
I suspect starting with a standard data structure also gives good scope for composition with other data structures to get what we need.
This of course is done by searching the database (blockchain) residing on local disk. In the case of Autonomi this is across the network with the lag time between accesses. Say average of 50mS for request/response, this would be fast, to follow the chain. To trace back 100 transactions/records in the chain is more than 5 seconds. To trace back 100 records on a blockchain is still milli seconds since its local disk.
But they have to download the blockchain first, right? They also need to download the blocks for all transactions and not just a single transaction chain.
I’m sure there are ways to optimise this though. I remember discussing storing snapshots of the blockchain to autonomi to allow faster bootstrapping of blockchain clients, for example. Instead of reading blocks from the start, they just trust the snapshot and validate subsequent blocks.
Maybe some sort of snapshotting can be done for autonomi lists/chains? We could have validator nodes/apps which store these snapshots. Trust could become a sensitive area here too, but if folks don’t want to do a full chain scan every time, or at all, it would need summarising another way.
I would think anyone searching the blockchain would have already downloaded. But yes first time it requires it to be downloaded. That is done once.
Yes, the chain could be made into chunks so that thousands of chain elements are in one chunk.
But is it trustworthy? Could it be forged to make out new transactions are legit, but in fact are scams?
Not an easy task to simplify, but there is surely a way. One suggestion is large chains could have markers for every 100 or 1000th record. Like a pointer (yep another) that allows one to skip back 100 or 1000 records at a time.
But as you say trust is a problem.