Paper accepted by IEEE Transactions on Knowledge and Data Engineering