Eugene Kirpichov (antilamer) wrote in algorithms,
Eugene Kirpichov
antilamer
algorithms

Here's a rather curious problem I've been thinking on for a while but didn't succeed.

Formal statement: Suppose R is a symmetric and reflexive, but not necessarily transitive, binary relation: R :: T -> T -> bool. What properties must R posess so that there would exist an integer n and a function norm :: T -> Rn so that forall a, b in T : R(a,b) <=> |norm(a)-norm(b)|<1? And how to built such a norm function?

Informal statement: R is a 'similarity function' that is computed very slowly and we need to compute it really many times. We are trying to speed it up by substituting objects from T with their vector 'normal forms' so that similarity becomes proximity in the vector space.

An example: suppose T is the domain of strings over a finite alphabet A of size k, and R states 'are anagrams of each other, +-m letters'. Then we can take norm(a) = vector of letter frequencies (of dimension k) in a, and compare frequency vectors. However, in this case a substantial speedup for computing similarity does not occur, but see below.

A reformulation: For what undirected graphs does there exist a layout such that an edge connects those and only those pairs of vertices that are on a distance of less than 1?

If we invent such a 'norm' function, we will be able to efficiently find similar objects in non-vector domains, such as texts etc. by substituting the original problem with the k-nearest problem. I suppose there are many other problems that will largely benefit from the solution of this one.
Subscribe

  • 15 though early morning of 16 April

    I began a reading of "Artemis Fowl". RS said it reminds her of the strangely non-sexual, intense relationship between Lucky and Nrsc. I…

  • Divide a circle

    Hi! I've been member of this community for quite time, and now I need some advise. Question is how do I devide given circle with radius R into N…

  • Contributing without even knowing

    Flash animations on webpages consume a surprisingly large amount of CPU time, especially if you keep many pages open at once. When you think about…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 17 comments

  • 15 though early morning of 16 April

    I began a reading of "Artemis Fowl". RS said it reminds her of the strangely non-sexual, intense relationship between Lucky and Nrsc. I…

  • Divide a circle

    Hi! I've been member of this community for quite time, and now I need some advise. Question is how do I devide given circle with radius R into N…

  • Contributing without even knowing

    Flash animations on webpages consume a surprisingly large amount of CPU time, especially if you keep many pages open at once. When you think about…