Questions tagged [metrics]
The metrics tag has no usage guidance.
25
questions
2
votes
0
answers
78
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_{...
- 181
1
vote
0
answers
39
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
0
answers
205
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 ...
- 211
6
votes
2
answers
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 ...
- 113
4
votes
2
answers
192
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 ...
- 778
5
votes
2
answers
188
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 ...
- 656
0
votes
1
answer
81
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 $...
- 305
1
vote
0
answers
58
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:
Given ...
- 11
2
votes
0
answers
140
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 (...
- 161
4
votes
1
answer
236
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 ...
- 1,318
19
votes
2
answers
864
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 ...
- 1,559
19
votes
2
answers
2k
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 ...
- 1,559
3
votes
1
answer
181
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,559
1
vote
1
answer
237
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 ...
- 705
27
votes
1
answer
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 ...
- 4,872
2
votes
0
answers
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 ...
- 325
5
votes
2
answers
369
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 ...
- 163
17
votes
4
answers
786
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 ...
- 31.7k
10
votes
1
answer
1k
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}\...
- 9,800
7
votes
2
answers
261
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 ...
- 9,800
7
votes
4
answers
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, ...
- 73
4
votes
1
answer
313
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 ...
- 179
12
votes
1
answer
442
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 ...
- 791
11
votes
4
answers
487
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)$ ...
- 9,800
20
votes
3
answers
421
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 ...
- 9,800