経験的にいうと、まず作成者、タイトル、カテゴリー、人気度、これらを優先順位で複合して表示していると思います。
タグは使わないのですか?
また、
>作成者、タイトル、カテゴリー、人気度
はこの順が適切だと思いますか?
ちなみに、「新規のビデオが追加されない」と仮定すると、関連するビデオのリストは人気度でしか変更はしないということになりますか?
あるビデオを複数回見た人は同じものが関連していた方がいいと思いますか?
ルールとしては同じ方がいいのかもしれませんが、ユーザにとっては違うのが出て関連するものを多く知れた方がいいような気もします。
+ランダムもありですかね?
見る方として便利なのは、同じタイトルのpart1の次にpart2が表示されるとか、同じ作成者のエロビデオがならぶとか。http://end