Hardness of Embedding Metric Spaces of Equal Size.
Subhash KhotRishi SaketPublished in: APPROX-RANDOM (2007)
Keyphrases
- metric space
- similarity search
- vector space
- similarity queries
- distance function
- range queries
- multidimensional index
- low dimensional spaces
- nearest neighbor queries
- high dimensional
- searching in metric spaces
- partially ordered sets
- probability measures
- similarity searching
- point sets
- data management
- access methods
- multimedia databases
- closed form
- algebraic structures
- range query processing
- np hard
- viewpoint
- lower bound