An approximate oracle for distance in metric spaces

Yanling Yang; Kaizhong Zhang; Xiong Wang; Jason T.L. Wang; Dennis Shasha

doi:10.1007/bfb0030784

An approximate oracle for distance in metric spaces

Yanling Yang, Kaizhong Zhang, Xiong Wang, Jason T.L. Wang, Dennis Shasha

Computer Science

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

2 Scopus citations

Abstract

In this paper we present a new data structure for estimating distances in a pseudo-metric space. Given are a database of objects and a distance function for the objects, which is a pseudo-metric. We map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such a data structure can be used as an approximate oracle to process a broad class of pattern-matching based queries. Experimental results on both synthetic and real data show the good performance of the oracle in distance estimation.

Original language	English (US)
Title of host publication	Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings
Publisher	Springer Verlag
Pages	104-117
Number of pages	14
ISBN (Print)	3540647392, 9783540647393
DOIs	https://doi.org/10.1007/bfb0030784
State	Published - 1998
Event	9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998 - Piscataway, NJ, United States Duration: Jul 20 1998 → Jul 22 1998

Publication series

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

Other

Other	9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998
Country/Territory	United States
City	Piscataway, NJ
Period	7/20/98 → 7/22/98

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0030784

Cite this

Yang, Y., Zhang, K., Wang, X., Wang, J. T. L., & Shasha, D. (1998). An approximate oracle for distance in metric spaces. In Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings (pp. 104-117). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1448 LNCS). Springer Verlag. https://doi.org/10.1007/bfb0030784

@inproceedings{de566a0f15054460bdf47fe4320476c1,

title = "An approximate oracle for distance in metric spaces",

abstract = "In this paper we present a new data structure for estimating distances in a pseudo-metric space. Given are a database of objects and a distance function for the objects, which is a pseudo-metric. We map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such a data structure can be used as an approximate oracle to process a broad class of pattern-matching based queries. Experimental results on both synthetic and real data show the good performance of the oracle in distance estimation.",

author = "Yanling Yang and Kaizhong Zhang and Xiong Wang and Wang, {Jason T.L.} and Dennis Shasha",

year = "1998",

doi = "10.1007/bfb0030784",

language = "English (US)",

isbn = "3540647392",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "104--117",

booktitle = "Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings",

address = "Germany",

}

Yang, Y, Zhang, K, Wang, X, Wang, JTL & Shasha, D 1998, An approximate oracle for distance in metric spaces. in Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1448 LNCS, Springer Verlag, pp. 104-117, 9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998, Piscataway, NJ, United States, 7/20/98. https://doi.org/10.1007/bfb0030784

An approximate oracle for distance in metric spaces. / Yang, Yanling; Zhang, Kaizhong; Wang, Xiong et al.
Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings. Springer Verlag, 1998. p. 104-117 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1448 LNCS).

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

TY - GEN

T1 - An approximate oracle for distance in metric spaces

AU - Yang, Yanling

AU - Zhang, Kaizhong

AU - Wang, Xiong

AU - Wang, Jason T.L.

AU - Shasha, Dennis

PY - 1998

Y1 - 1998

N2 - In this paper we present a new data structure for estimating distances in a pseudo-metric space. Given are a database of objects and a distance function for the objects, which is a pseudo-metric. We map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such a data structure can be used as an approximate oracle to process a broad class of pattern-matching based queries. Experimental results on both synthetic and real data show the good performance of the oracle in distance estimation.

AB - In this paper we present a new data structure for estimating distances in a pseudo-metric space. Given are a database of objects and a distance function for the objects, which is a pseudo-metric. We map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such a data structure can be used as an approximate oracle to process a broad class of pattern-matching based queries. Experimental results on both synthetic and real data show the good performance of the oracle in distance estimation.

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

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

U2 - 10.1007/bfb0030784

DO - 10.1007/bfb0030784

M3 - Conference contribution

AN - SCOPUS:84877330430

SN - 3540647392

SN - 9783540647393

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

SP - 104

EP - 117

BT - Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings

PB - Springer Verlag

T2 - 9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998

Y2 - 20 July 1998 through 22 July 1998

ER -

Yang Y, Zhang K, Wang X, Wang JTL, Shasha D. An approximate oracle for distance in metric spaces. In Combinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings. Springer Verlag. 1998. p. 104-117. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0030784

An approximate oracle for distance in metric spaces

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this