Later, determine the case with minimum Euclidean distance for each test image and note the corresponding index

I = imread('myimage.jpg'); 
I = rgb2gray(I);
h = imhist(I); % this will have default bins 256
% now second image 
J = imread('myimage1.jpg'); 
J = rgb2gray(J);
h1 = imhist(J); % this will have default bins 256 
E_distance = sqrt(sum((h-h1).^2));
You can do it for 1000 images as well. Let say now your 1000 images histogram are concatenated into h1. where each column is one histogram. Then your query image histogram is h. Then distance can be computed as follow.
h_new = repmat(h,1,size(h1,2));
E_distance = sqrt(sum((h_new-h1).^2));

For Sample data:

s1 = 8192; s2 = 200;
img_a = rand(s1, s2);
img_b = rand(s1, s2);
r = 2;

and the calculation itself:

img_diff = img_a - img_b;
kernel = bsxfun(@plus, (-s1:s1).^2.', (-s2:s2).^2);
kernel = 1/(2/pi/r^2) * exp(-kernel/ (2*r*2));
g = conv2(img_diff, kernel, 'same');
res = g(:)' * img_diff(:); 
res = sqrt(res);

The above takes about 25s. To get down to 2s, you need to replace the standard conv2 with a faster, fft based convolution. 

function c = conv2fft(X, Y)
    % ignoring small floating-point differences, this is equivalent
    % to the inbuilt Matlab conv2(X, Y, 'same')
    X1 = [X zeros(size(X,1), size(Y,2)-1);
          zeros(size(Y,1)-1, size(X,2)+size(Y,2)-1)];
    Y1 = zeros(size(X1)); 
    Y1(1:size(Y,1), 1:size(Y,2)) = Y;
    c = ifft2(fft2(X1).*fft2(Y1));
    c = c(size(X,1)+1:size(X,1)+size(X,1), size(X,2)+1:size(X,2)+size(X,2));
end

Incidentally, if you still want it to go faster, you could make use of the fact that exp(-d^2/r^2) gets very close to zero for fairly small d: so you can actually crop your kernel to just a tiny rectangle, rather than the huge thing suggested above. A smaller kernel means conv2fft (or especially conv2) will run faster.

Step-by-step explanation

Generally, The Euclidean distance is the straight-line distance between two pixels. Pixels whose edges touch are 1 unit apart; pixels diagonally touching are 2 units apart. Simply like Chessboard. The chessboard distance metric measures the path between the pixels based on an 8-connected neighborhood. Hope this helps and Goodluck ahead :)