An approximate oracle for distance in metric spaces

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

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


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 languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 9th Annual Symposium, CPM 1998, Proceedings
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3540647392, 9783540647393
StatePublished - 1998
Event9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998 - Piscataway, NJ, United States
Duration: Jul 20 1998Jul 22 1998

Publication series

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


Other9th Annual Symposium on Combinatorial Pattern Matching, CPM 1998
Country/TerritoryUnited States
CityPiscataway, NJ

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'An approximate oracle for distance in metric spaces'. Together they form a unique fingerprint.

Cite this