An effective method for approximating the euclidean distance in high-dimensional space

Seungdo Jeong, Sang Wook Kim, Kidong Kim, Byung Uk Choi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

Abstract

It is crucial to compute the Euclidean distance between two vectors efficiently in high-dimensional space for multimedia information retrieval. We propose an effective method for approximating the Euclidean distance between two high-dimensional vectors. For this approximation, a previous method, which simply employs norms of two vectors, has been proposed. This method, however, ignores the angle between two vectors in approximation, and thus suffers from large approximation errors. Our method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method. Also, we formally prove that the value approximated by our method is always smaller than the actual Euclidean distance. This implies that our method does not incur any false dismissal in multimedia information retrieval. Finally, we verify the superiority of the proposed method via performance evaluation with extensive experiments.

Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings
PublisherSpringer Verlag
Pages863-872
Number of pages10
ISBN (Print)3540378715, 9783540378716
StatePublished - 2006 Jan 1
Event17th International Conference on Database and Expert Systems Applications, DEXA 2006 - Krakow, Poland
Duration: 2006 Sep 42006 Sep 8

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4080 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Database and Expert Systems Applications, DEXA 2006
CountryPoland
CityKrakow
Period06/09/406/09/8

Fingerprint

Euclidean Distance
High-dimensional
Information retrieval
Approximation Error
Angle
Information Retrieval
Multimedia
Approximation
Performance Evaluation
Verify
Norm
Imply
Experiment
Experiments

Cite this

Jeong, S., Kim, S. W., Kim, K., & Choi, B. U. (2006). An effective method for approximating the euclidean distance in high-dimensional space. In Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings (pp. 863-872). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4080 LNCS). Springer Verlag.
Jeong, Seungdo ; Kim, Sang Wook ; Kim, Kidong ; Choi, Byung Uk. / An effective method for approximating the euclidean distance in high-dimensional space. Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Springer Verlag, 2006. pp. 863-872 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{dc09868c9390435a9e3dd5b464889616,
title = "An effective method for approximating the euclidean distance in high-dimensional space",
abstract = "It is crucial to compute the Euclidean distance between two vectors efficiently in high-dimensional space for multimedia information retrieval. We propose an effective method for approximating the Euclidean distance between two high-dimensional vectors. For this approximation, a previous method, which simply employs norms of two vectors, has been proposed. This method, however, ignores the angle between two vectors in approximation, and thus suffers from large approximation errors. Our method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method. Also, we formally prove that the value approximated by our method is always smaller than the actual Euclidean distance. This implies that our method does not incur any false dismissal in multimedia information retrieval. Finally, we verify the superiority of the proposed method via performance evaluation with extensive experiments.",
author = "Seungdo Jeong and Kim, {Sang Wook} and Kidong Kim and Choi, {Byung Uk}",
year = "2006",
month = "1",
day = "1",
language = "English",
isbn = "3540378715",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "863--872",
booktitle = "Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings",

}

Jeong, S, Kim, SW, Kim, K & Choi, BU 2006, An effective method for approximating the euclidean distance in high-dimensional space. in Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4080 LNCS, Springer Verlag, pp. 863-872, 17th International Conference on Database and Expert Systems Applications, DEXA 2006, Krakow, Poland, 06/09/4.

An effective method for approximating the euclidean distance in high-dimensional space. / Jeong, Seungdo; Kim, Sang Wook; Kim, Kidong; Choi, Byung Uk.

Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Springer Verlag, 2006. p. 863-872 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4080 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - An effective method for approximating the euclidean distance in high-dimensional space

AU - Jeong, Seungdo

AU - Kim, Sang Wook

AU - Kim, Kidong

AU - Choi, Byung Uk

PY - 2006/1/1

Y1 - 2006/1/1

N2 - It is crucial to compute the Euclidean distance between two vectors efficiently in high-dimensional space for multimedia information retrieval. We propose an effective method for approximating the Euclidean distance between two high-dimensional vectors. For this approximation, a previous method, which simply employs norms of two vectors, has been proposed. This method, however, ignores the angle between two vectors in approximation, and thus suffers from large approximation errors. Our method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method. Also, we formally prove that the value approximated by our method is always smaller than the actual Euclidean distance. This implies that our method does not incur any false dismissal in multimedia information retrieval. Finally, we verify the superiority of the proposed method via performance evaluation with extensive experiments.

AB - It is crucial to compute the Euclidean distance between two vectors efficiently in high-dimensional space for multimedia information retrieval. We propose an effective method for approximating the Euclidean distance between two high-dimensional vectors. For this approximation, a previous method, which simply employs norms of two vectors, has been proposed. This method, however, ignores the angle between two vectors in approximation, and thus suffers from large approximation errors. Our method introduces an additional vector called a reference vector for estimating the angle between the two vectors, and approximates the Euclidean distance accurately by using the estimated angle. This makes the approximation errors reduced significantly compared with the previous method. Also, we formally prove that the value approximated by our method is always smaller than the actual Euclidean distance. This implies that our method does not incur any false dismissal in multimedia information retrieval. Finally, we verify the superiority of the proposed method via performance evaluation with extensive experiments.

UR - http://www.scopus.com/inward/record.url?scp=33749409766&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:33749409766

SN - 3540378715

SN - 9783540378716

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 863

EP - 872

BT - Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings

PB - Springer Verlag

ER -

Jeong S, Kim SW, Kim K, Choi BU. An effective method for approximating the euclidean distance in high-dimensional space. In Database and Expert Systems Applications - 17th International Conference, DEXA 2006, Proceedings. Springer Verlag. 2006. p. 863-872. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).