Paper Accepted by ACM TOIS