Backing Up on Witness Points of Input Vectors

Let be a set of vectors on which we are going to perform point-based DP update. As mentioned earlier, we can assume that we know a witness point for each vector in . Denote the witness point for a vector by . Point-based DP update first backs up on these points and thereby obtains a new set of vectors. To be more specific, it begins with the following subroutine:

 
 		    :

		 1. 		   .

		 2.  		 for each   

		 3. 		  		   .

		4.   		    		if   

 		5.  		  		  		               .

		6.   		   		 		    .

		7. 		 return   .

In this subroutine, line 4 makes sure that the resulting set contains no duplicates and line 5 takes note of the fact that is also a witness point for (w.r.t ).