Is there a good way to determine after seeing N unique items in M trials how many items there potentially are? Would tracking the time between seeing new unique items help? Is this an already solved problem?
There are many different statistical estimators for this problem, many from the ecology literature (e.g. Chao1). This paper and a Python library based on it covers many of them:
No, it's not the same as the German tank problem, because that assumes all sampled values are unique (and totally ordered). It's closer to the "species richness" estimation problem, where you estimate the total number of species from a sample (specimens) with many repeated values (species).
https://www.vldb.org/conf/1995/P311.PDF
https://pydistinct.readthedocs.io/en/latest/docs/readme_link...