A multi-way divergence metric for vector spaces

Robert Moss, Richard Connor

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

Abstract

The majority of work in similarity search focuses on the efficiency of threshold and nearest-neighbour queries. Similarity join has been less well studied, although efficient indexing algorithms have been shown. The multi-way similarity join, extending similarity join to multiple spaces, has received relatively little treatment.
Here we present a novel metric designed to assess some concept of a mutual similarity over multiple vectors, thus extending pairwise distance to a more general notion taken over a set of values. In outline, when considering a set of values X, our function gives a single numeric outcome D(X) rather than calculating some compound function over all of d(x, y) where x,y are elements of X. D(X) is strongly correlated with various compound functions, but costs only a little more than a single distance to evaluate. It is derived from an information-theoretic distance metric; it correlates strongly with this metric, and also with other metrics, in high-dimensional spaces. Although we are at an early stage in its investigation, we believe it could potentially be used to help construct more efficient indexes, or to construct indexes more efficiently.
The contribution of this short paper is simply to identify the function, to show that it has useful semantic properties, and to show also that it is surprisingly cheap to evaluate. We expect uses of the function in the domain of similarity search to follow.
LanguageEnglish
Title of host publicationSimilarity Search and Applications
Subtitle of host publication6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings
EditorsNieves Brisaboa, Oscar Pedreira, Pavel Zezula
Pages169-174
Number of pages6
DOIs
Publication statusPublished - 2 Oct 2013
Event6th International Conference on Similarity Search and Applications, SISAP 2013 - Hotel Riazor, A Coruña, Spain
Duration: 2 Oct 20134 Oct 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume8199
ISSN (Print)0302-9743

Conference

Conference6th International Conference on Similarity Search and Applications, SISAP 2013
CountrySpain
CityA Coruña
Period2/10/134/10/13

Fingerprint

Vector spaces
Cost functions
Semantics

Keywords

  • distance metric
  • multi-way divergence
  • similarity join
  • mutual similarity
  • multiple vectors
  • indexing algorithms

Cite this

Moss, R., & Connor, R. (2013). A multi-way divergence metric for vector spaces. In N. Brisaboa, O. Pedreira, & P. Zezula (Eds.), Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings (pp. 169-174). (Lecture Notes in Computer Science; Vol. 8199). https://doi.org/10.1007/978-3-642-41062-8_17
Moss, Robert ; Connor, Richard. / A multi-way divergence metric for vector spaces. Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings. editor / Nieves Brisaboa ; Oscar Pedreira ; Pavel Zezula. 2013. pp. 169-174 (Lecture Notes in Computer Science).
@inproceedings{1b63265f67274a47bf26cec4ad25f1c4,
title = "A multi-way divergence metric for vector spaces",
abstract = "The majority of work in similarity search focuses on the efficiency of threshold and nearest-neighbour queries. Similarity join has been less well studied, although efficient indexing algorithms have been shown. The multi-way similarity join, extending similarity join to multiple spaces, has received relatively little treatment.Here we present a novel metric designed to assess some concept of a mutual similarity over multiple vectors, thus extending pairwise distance to a more general notion taken over a set of values. In outline, when considering a set of values X, our function gives a single numeric outcome D(X) rather than calculating some compound function over all of d(x, y) where x,y are elements of X. D(X) is strongly correlated with various compound functions, but costs only a little more than a single distance to evaluate. It is derived from an information-theoretic distance metric; it correlates strongly with this metric, and also with other metrics, in high-dimensional spaces. Although we are at an early stage in its investigation, we believe it could potentially be used to help construct more efficient indexes, or to construct indexes more efficiently.The contribution of this short paper is simply to identify the function, to show that it has useful semantic properties, and to show also that it is surprisingly cheap to evaluate. We expect uses of the function in the domain of similarity search to follow.",
keywords = "distance metric, multi-way divergence, similarity join, mutual similarity, multiple vectors, indexing algorithms",
author = "Robert Moss and Richard Connor",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-41062-8_17",
year = "2013",
month = "10",
day = "2",
doi = "10.1007/978-3-642-41062-8_17",
language = "English",
isbn = "9783642410611",
series = "Lecture Notes in Computer Science",
publisher = "Springer Berlin Heidelberg",
pages = "169--174",
editor = "Nieves Brisaboa and Oscar Pedreira and Pavel Zezula",
booktitle = "Similarity Search and Applications",

}

Moss, R & Connor, R 2013, A multi-way divergence metric for vector spaces. in N Brisaboa, O Pedreira & P Zezula (eds), Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings. Lecture Notes in Computer Science, vol. 8199, pp. 169-174, 6th International Conference on Similarity Search and Applications, SISAP 2013, A Coruña, Spain, 2/10/13. https://doi.org/10.1007/978-3-642-41062-8_17

A multi-way divergence metric for vector spaces. / Moss, Robert; Connor, Richard.

Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings. ed. / Nieves Brisaboa; Oscar Pedreira; Pavel Zezula. 2013. p. 169-174 (Lecture Notes in Computer Science; Vol. 8199).

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

TY - GEN

T1 - A multi-way divergence metric for vector spaces

AU - Moss, Robert

AU - Connor, Richard

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-642-41062-8_17

PY - 2013/10/2

Y1 - 2013/10/2

N2 - The majority of work in similarity search focuses on the efficiency of threshold and nearest-neighbour queries. Similarity join has been less well studied, although efficient indexing algorithms have been shown. The multi-way similarity join, extending similarity join to multiple spaces, has received relatively little treatment.Here we present a novel metric designed to assess some concept of a mutual similarity over multiple vectors, thus extending pairwise distance to a more general notion taken over a set of values. In outline, when considering a set of values X, our function gives a single numeric outcome D(X) rather than calculating some compound function over all of d(x, y) where x,y are elements of X. D(X) is strongly correlated with various compound functions, but costs only a little more than a single distance to evaluate. It is derived from an information-theoretic distance metric; it correlates strongly with this metric, and also with other metrics, in high-dimensional spaces. Although we are at an early stage in its investigation, we believe it could potentially be used to help construct more efficient indexes, or to construct indexes more efficiently.The contribution of this short paper is simply to identify the function, to show that it has useful semantic properties, and to show also that it is surprisingly cheap to evaluate. We expect uses of the function in the domain of similarity search to follow.

AB - The majority of work in similarity search focuses on the efficiency of threshold and nearest-neighbour queries. Similarity join has been less well studied, although efficient indexing algorithms have been shown. The multi-way similarity join, extending similarity join to multiple spaces, has received relatively little treatment.Here we present a novel metric designed to assess some concept of a mutual similarity over multiple vectors, thus extending pairwise distance to a more general notion taken over a set of values. In outline, when considering a set of values X, our function gives a single numeric outcome D(X) rather than calculating some compound function over all of d(x, y) where x,y are elements of X. D(X) is strongly correlated with various compound functions, but costs only a little more than a single distance to evaluate. It is derived from an information-theoretic distance metric; it correlates strongly with this metric, and also with other metrics, in high-dimensional spaces. Although we are at an early stage in its investigation, we believe it could potentially be used to help construct more efficient indexes, or to construct indexes more efficiently.The contribution of this short paper is simply to identify the function, to show that it has useful semantic properties, and to show also that it is surprisingly cheap to evaluate. We expect uses of the function in the domain of similarity search to follow.

KW - distance metric

KW - multi-way divergence

KW - similarity join

KW - mutual similarity

KW - multiple vectors

KW - indexing algorithms

UR - http://www.sisap.org/2013/cfp.html

U2 - 10.1007/978-3-642-41062-8_17

DO - 10.1007/978-3-642-41062-8_17

M3 - Conference contribution book

SN - 9783642410611

T3 - Lecture Notes in Computer Science

SP - 169

EP - 174

BT - Similarity Search and Applications

A2 - Brisaboa, Nieves

A2 - Pedreira, Oscar

A2 - Zezula, Pavel

ER -

Moss R, Connor R. A multi-way divergence metric for vector spaces. In Brisaboa N, Pedreira O, Zezula P, editors, Similarity Search and Applications: 6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings. 2013. p. 169-174. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-41062-8_17