Questions tagged [metrics]
The metrics tag has no usage guidance.
26
questions
2
votes
0answers
57 views
Complexity of computing Earth Mover's Distance when the costs satisfy the triangle inequality
Let p and q by two categorical probability distributions over $\{1,2,...,k\}$. Given a set of costs $c_{ij} \ge 0, i,j \in \{1,2,...,k\}$ that satisfy the triangle inequality, that is $c_{ij} \le c_{...
0
votes
0answers
42 views
Approximate nearest neighbor search for $(\ell_p)^p$ metric, $0 < p < 1$
It is well known that approximate bichromatic nearest-neighbor search can be solved in sub-quadratic time for the $\ell_1$ and $\ell_2$ norms, as well as some other metrics. Are there any such results ...
1
vote
0answers
38 views
BK-Tree intersection
I'm looking to calculate the approximate intersection (proximity under a certain distance) of two sets of points in a discrete metric space. In other words, given a metric space $(M, d)$, subsets $A, ...
2
votes
0answers
175 views
Quicksort optimal partition
Has the question been studied, how to find the shortest sequence of partition choices so that a quick-sort algorithm can sort a set?
To be clear, I'm not interested in quick sort per se, but in ...
5
votes
2answers
1k views
Min Hamming distance of a given string from substrings of another string
Let $U$ be a small finite set.
Consider the following problem:
Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$.
Output: a (contiguous) substring of $v$ of length $k$
with the minimum ...
3
votes
2answers
176 views
Are there Similar Distance Binary Error Correcting Codes?
I'm trying to find a low distortion embedding of the trivial metric space into hamming space.
It seems this should be doable by using a large set of low dimensional vectors, with approximately equal ...
5
votes
2answers
157 views
L1 - embeddability of metrics supported on the Hypercube
I am quite new to the area of metric embeddings so this question might turn out to be extremely easy.
Consider a metric supported on the edges of a boolean hypercube. By supported I mean every edge ...
0
votes
1answer
67 views
Define metric for systems of set of points
Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $...
1
vote
0answers
45 views
Fixed orientation metrics
I am currently working on some computational geometry problems with non-euclidean metrics, and have some trouble on a fact that sounds easy enough, at least intuitively.
The fact is as follows:
...
2
votes
0answers
125 views
Quality measure for clusters of a metric space embedding of a graph?
When evaluating clustering algorithms for networks, we have well-established metrics like Modularity and Surprise for evaluating the quality of the resulting partition.
If we then embed our graph (...
4
votes
1answer
219 views
Is “normalized distance” (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?
In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the ...
19
votes
2answers
804 views
Axioms for Shortest Paths
Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences ...
19
votes
2answers
1k views
A data structure for minimum dot product queries
Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
3
votes
1answer
173 views
Combinatorial algorithm for optimization over semimetric polytope
This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.
Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More ...
1
vote
1answer
208 views
Weighted Metric Graph: ratio of sum of wts of edges to the wt of MST
I am working on complete metric graph (V,d) where shortest distance is used as metric. The question is how large can be the ratio of the sum of weights of all edges to the weight of the MST (minimum ...
27
votes
1answer
2k views
Isometric embedding of L2 into L1
It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$.
Is ...
2
votes
0answers
104 views
Does kd-tree search look at more leaves in L1 than in Lmax ?
Dear theorists and experimenters,
I find that kd-tree search looks at many more leaves in $L_1$ than in
$L_{max}$ ($L_\infty$).
Does anyone else see this ? If so,
why ?
(An $L_1$ simplex of volume 1 ...
5
votes
2answers
346 views
How to calculate this string-dissimilarity function efficiently?
Migrated from stackoverflow.
Hello,
I was looking for a string metric that have the property that moving around large blocks in a string won't affect the distance so much. So "helloworld" is close ...
17
votes
4answers
737 views
Applications of metric structures on posets/lattices in theoryCS
Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper ...
10
votes
1answer
917 views
$\epsilon$-nets with respect to the cut norm
The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\...
7
votes
2answers
224 views
Counting Metrics
Say that I have a set of $n$ points $N$, and am interested in metrics $d:N\times N \rightarrow \mathbb{R}$ over $N$. Let $M$ denote the set of all metrics over $N$.
Now let me define the distance ...
7
votes
4answers
1k views
Deciding whether a metric is a tree metric
An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, ...
4
votes
1answer
311 views
Extracting Independent Information About Sequences
Related to this question, but asked in a different way.
For the purposes of a text-based implementation of a fuzzy vault, what metrics can we take on Sequences that are isolated such that the set of ...
11
votes
1answer
413 views
In domain theory, what can the extra structure present in metric spaces be used for?
Smyth's chapter in the handbook of logic in computer science and other references describe how metric spaces can be used as domains. I do understand that complete metric spaces give unique fixed ...
11
votes
4answers
482 views
Dimensionality reduction with slack?
The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ ...
20
votes
3answers
407 views
Property testing in other metrics?
There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases:
$f$ is a ...
