Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software Development SDKs and Libraries
- Intel® Integrated Performance Primitives
- How to compute pairwise Euclidean distances using IPP?

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

minne

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

01-25-2008
02:31 PM

84 Views

How to compute pairwise Euclidean distances using IPP?

for(int i = 0; i smaller than n; i++) {

for(int j = i + 1; j smaller than n; j++) {

double val = 0.0;

for(int k = 0; k

val += pow((float) *(data + (i * (data_step / sizeof(Ipp32f))) + k) - (float) *(data + (j * (data_step / sizeof(Ipp32f))) + k), (float) 2.0);

}

*(P + (i * (P_step / sizeof(Ipp32f))) + j) = *(P + (j * (P_step / sizeof(Ipp32f))) + i) = (Ipp32f) val;

}

}

Herein, the data is my NxD matrix with stride data_step, and P is the NxN matrix in which I store the squared Euclidean distances.

I've been trying to think about a smart way to do this with IPP (e.g., by using d(A,B) = sum(A.^2) + sum(B.^2) - 2*sum(A.*B)), but they all involve the implementation of loops. Does anyone have a suggestion how I can do this computation efficiently using IPP?

Link Copied

3 Replies

Intel_C_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

02-01-2008
12:04 AM

84 Views

Hi,

It is possible to apply one of ippsLogGauss_IdVar_* function (ippsr library). The formula slightly differs (for val==0 you get the negative Euclidean square distance.

32f, 16s to 32s and 16s to 32f data types are supported.

Data step in these functions is in data elements, not in bytes

Alexander

minne

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

02-01-2008
12:46 PM

84 Views

minne

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

02-02-2008
06:37 PM

84 Views

=========================

Ipp64f* dataSqr = ippsMalloc_64f (n * d);

Ipp64f* dataSqrSums = ippsMalloc_64f (n);

ippsSqr_64f (data, dataSqr, n * d);

ippsSumRow_64f_D2 (dataSqr, d, d, dataSqrSums, n);

ippmMul_mt_64f (data, d * sizeof(Ipp64f), sizeof(Ipp64f), d, n, data, d * sizeof(Ipp64f), sizeof(Ipp64f), d, n, P, n * sizeof(Ipp64f), sizeof(Ipp64f));

ippsMulC_64f_I ((Ipp64f) -2.0, P, n * n);

for(int i = 0; i smaller than n; i++) {

for(int j = 0; j smaller than n; j++) {

*(P + i * n + j) += *(dataSqrSums + i) + *(dataSqrSums + j);

}

}

ippsFree(dataSqr);

ippsFree(dataSqrSums);

==========================

However, it has three disadvantages:

* It uses ippm, which I think is mainly optimized for small matrices (in my case, N=5000 and D=[1,10])

* I still need a loop to add the L2-norms of the data vectors

* I don't exploit the fact that the pairwise distance matrix is symmetric (I compute everything twice)

Any ideas anyone?

For more complete information about compiler optimizations, see our Optimization Notice.