Paper Accepted at ACM TOIS