The Riau Islands is a province in Indonesia . Tanjung Pinang is its capital city . Originally part of the Riau Province , the Riau Islands were split off as a separate province in July 2004 , with Tanjung Pinang as its capital , located at south of Bintan island .