The most versatile newsreader with respect to threading is tin. It was written by Iain Lea and is loosely modeled on an older newsreader named tass (written by Rich Skrenta). It does its threading when the user enters the newsgroup, and it is pretty fast unless you're getting posts via NNTP.
On a 486DX50, it takes roughly 30 seconds to thread 1,000 articles when reading directly from disk. It would take more than 5 minutes over NNTP to reach a loaded news server. You may improve this time by regularly updating your index file by invoking tin with the –u option, so that when you next start tin to read news the threads already exist. Alternatively, you can invoke tin with the –U option to read news. When invoked this way, tin forks a background process to build the index files while you are reading news.
Usually, tin dumps its threading databases in the user's home directory below .tin/index. This may be costly in terms of resources, however, so you should keep a single copy of them in a central location. This may be achieved by making tin setuid to news, for example. tin will then keep all thread databases below /var/spool/news/.index. For any file access or shell escape, it will reset its effective uid to the real uid of the user who invoked it.
The version of tin included in some Linux distributions is compiled without NNTP support, but most do have it now. When invoked as rtin or with the –r option, tin tries to connect to the NNTP server specified in the file /etc/nntpserver or in the NNTPSERVER environment variable. The nntpserver file simply contains the server's name on a single line.
Things improve drastically if the NNTP server does the threading itself and lets the client retrieve the threads databases; INN does this, for instance.
This is the reason why you will get ugly error messages when invoking tin as superuser. But you shouldn't do routine work as root, anyway.