Evaluation of Jensen-Shannon distance over sparse data

Richard Connor; Franco Alberto Cardillo; Robert Moss; Fausto Rabitti

doi:10.1007/978-3-642-41062-8_16

Evaluation of Jensen-Shannon distance over sparse data

Richard Connor, Franco Alberto Cardillo, Robert Moss, Fausto Rabitti

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

11 Citations (Scopus)

463 Downloads (Pure)

Abstract

Jensen-Shannon divergence is a symmetrised, smoothed version of Küllback-Leibler. It has been shown to be the square of a proper distance metric, and has other properties which make it an excellent choice for many high-dimensional spaces in R*.
The metric as defined is however expensive to evaluate. In sparse spaces over many dimensions the Intrinsic Dimensionality of the metric space is typically very high, making similarity-based indexing ineffectual. Exhaustive searching over large data collections may be infeasible.
Using a property that allows the distance to be evaluated from only those dimensions which are non-zero in both arguments, and through the identification of a threshold function, we show that the cost of the function can be dramatically reduced.

Original language	English
Title of host publication	Similarity Search and Applications
Subtitle of host publication	6th International Conference, SISAP 2013, A Coruña, Spain, October 2-4, 2013, Proceedings
Editors	Nieves Brisaboa, Oscar Pedreira, Pavel Zezula
Place of Publication	Berlin
Publisher	Springer
Pages	163-168
Number of pages	6
Volume	8199
ISBN (Print)	9783642410611
DOIs	https://doi.org/10.1007/978-3-642-41062-8_16
Publication status	Published - 13 Sept 2013
Event	6th International Conference on Similarity Search and Applications, SISAP 2013 - Hotel Riazor, A Coruña, Spain Duration: 2 Oct 2013 → 4 Oct 2013

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8199
ISSN (Print)	0302-9743

Conference

Conference	6th International Conference on Similarity Search and Applications, SISAP 2013
Country/Territory	Spain
City	A Coruña
Period	2/10/13 → 4/10/13

Keywords

distance metrics
exhaustive searching
high dimensional spaces
instrinsic dimensionalitites
Jensen-Shannon divergence
metric spaces
other properties
threshold functions
artificial intelligence
computer science

Access to Document

10.1007/978-3-642-41062-8_16

Connor-etal-LNCS2013-Evaluation-Jensen-Shannon-distance-over-sparse-dataAccepted author manuscript, 244 KB

Cite this

Connor, R., Cardillo, F. A., Moss, R., & Rabitti, F. (2013). Evaluation of Jensen-Shannon distance over sparse data. 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 (Vol. 8199, pp. 163-168). (Lecture Notes in Computer Science; Vol. 8199). Springer. https://doi.org/10.1007/978-3-642-41062-8_16

Connor, Richard ; Cardillo, Franco Alberto ; Moss, Robert et al. / Evaluation of Jensen-Shannon distance over sparse data. 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. Vol. 8199 Berlin : Springer, 2013. pp. 163-168 (Lecture Notes in Computer Science).

@inproceedings{8ddc1fc480a346c48c9d9d12e1262f9c,

title = "Evaluation of Jensen-Shannon distance over sparse data",

abstract = "Jensen-Shannon divergence is a symmetrised, smoothed version of K{\"u}llback-Leibler. It has been shown to be the square of a proper distance metric, and has other properties which make it an excellent choice for many high-dimensional spaces in R*.The metric as defined is however expensive to evaluate. In sparse spaces over many dimensions the Intrinsic Dimensionality of the metric space is typically very high, making similarity-based indexing ineffectual. Exhaustive searching over large data collections may be infeasible.Using a property that allows the distance to be evaluated from only those dimensions which are non-zero in both arguments, and through the identification of a threshold function, we show that the cost of the function can be dramatically reduced.",

keywords = "distance metrics, exhaustive searching, high dimensional spaces, instrinsic dimensionalitites, Jensen-Shannon divergence, metric spaces, other properties, threshold functions, artificial intelligence, computer science",

author = "Richard Connor and Cardillo, {Franco Alberto} and Robert Moss and Fausto Rabitti",

year = "2013",

month = sep,

day = "13",

doi = "10.1007/978-3-642-41062-8_16",

language = "English",

isbn = "9783642410611",

volume = "8199",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "163--168",

editor = "Brisaboa, {Nieves } and Oscar Pedreira and Zezula, {Pavel }",

booktitle = "Similarity Search and Applications",

note = "6th International Conference on Similarity Search and Applications, SISAP 2013 ; Conference date: 02-10-2013 Through 04-10-2013",

}

Connor, R, Cardillo, FA, Moss, R & Rabitti, F 2013, Evaluation of Jensen-Shannon distance over sparse data. 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. vol. 8199, Lecture Notes in Computer Science, vol. 8199, Springer, Berlin, pp. 163-168, 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_16

Evaluation of Jensen-Shannon distance over sparse data. / Connor, Richard; Cardillo, Franco Alberto; Moss, Robert et al.
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. Vol. 8199 Berlin: Springer, 2013. p. 163-168 (Lecture Notes in Computer Science; Vol. 8199).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

TY - GEN

T1 - Evaluation of Jensen-Shannon distance over sparse data

AU - Connor, Richard

AU - Cardillo, Franco Alberto

AU - Moss, Robert

AU - Rabitti, Fausto

PY - 2013/9/13

Y1 - 2013/9/13

N2 - Jensen-Shannon divergence is a symmetrised, smoothed version of Küllback-Leibler. It has been shown to be the square of a proper distance metric, and has other properties which make it an excellent choice for many high-dimensional spaces in R*.The metric as defined is however expensive to evaluate. In sparse spaces over many dimensions the Intrinsic Dimensionality of the metric space is typically very high, making similarity-based indexing ineffectual. Exhaustive searching over large data collections may be infeasible.Using a property that allows the distance to be evaluated from only those dimensions which are non-zero in both arguments, and through the identification of a threshold function, we show that the cost of the function can be dramatically reduced.

AB - Jensen-Shannon divergence is a symmetrised, smoothed version of Küllback-Leibler. It has been shown to be the square of a proper distance metric, and has other properties which make it an excellent choice for many high-dimensional spaces in R*.The metric as defined is however expensive to evaluate. In sparse spaces over many dimensions the Intrinsic Dimensionality of the metric space is typically very high, making similarity-based indexing ineffectual. Exhaustive searching over large data collections may be infeasible.Using a property that allows the distance to be evaluated from only those dimensions which are non-zero in both arguments, and through the identification of a threshold function, we show that the cost of the function can be dramatically reduced.

KW - distance metrics

KW - exhaustive searching

KW - high dimensional spaces

KW - instrinsic dimensionalitites

KW - Jensen-Shannon divergence

KW - metric spaces

KW - other properties

KW - threshold functions

KW - artificial intelligence

KW - computer science

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

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

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

M3 - Conference contribution book

SN - 9783642410611

VL - 8199

T3 - Lecture Notes in Computer Science

SP - 163

EP - 168

BT - Similarity Search and Applications

A2 - Brisaboa, Nieves

A2 - Pedreira, Oscar

A2 - Zezula, Pavel

PB - Springer

CY - Berlin

T2 - 6th International Conference on Similarity Search and Applications, SISAP 2013

Y2 - 2 October 2013 through 4 October 2013

ER -

Connor R, Cardillo FA, Moss R, Rabitti F. Evaluation of Jensen-Shannon distance over sparse data. 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. Vol. 8199. Berlin: Springer. 2013. p. 163-168. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-41062-8_16

Evaluation of Jensen-Shannon distance over sparse data

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this