StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Okay you have a way of measuring similarity between objects. That means they form a <a href="http://en.wikipedia.org/wiki/Metric_space" rel="nofollow noreferrer">Metric Space</a>. </p> <p>The question is, is your space also a <a href="http://en.wikipedia.org/wiki/Euclidean_space" rel="nofollow noreferrer">Euclidean space</a> like normal three dimensional space, or integers or something like that? If it is, then you could use a <a href="http://en.wikipedia.org/wiki/Binary_space_partitioning" rel="nofollow noreferrer">binary space partition</a> in however many dimensions you've got. </p> <p>(The question is, basically: is there a homomorphism between your objects and an n-dimensional real number vector? If so, then you can use techniques for measuring closeness of points in n-dimensional space.)</p> <p>Now, if it's <i>not</i> a euclidean space then you've got a bigger problem. An example of a non-euclidean space that programers might be most familiar with would be the <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow noreferrer">Levenshtein Distance</a> between to strings. </p> <p>If your problem is similar to seeing how similar a string is to a list of already existing strings then I don't <i>know</i> of any algorithms that would do that without O(n<sup>2</sup>) time. Maybe there are some out there. </p> <hr> <p>But another important question is: how much time do you have? How many objects? If you have time or if your data set is small enough that an O(n<sup>2</sup>) algorithm is practical, then you just have to iterate through your list of objects to see if it's below a certain threshold. If so, reject it. </p> <p>Just overload <a href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/AbstractCollection.html" rel="nofollow noreferrer">AbstractCollection</a> and replace the Add function. Use an ArrayList or whatever. Your code would look kind of like this</p> <pre><code>class SimilarityRejector<T> extends AbstractCollection<T>{ ArrayList<T> base; double threshold; public SimilarityRejector(double threshold){ base = new ArrayList<T>(); this.threshold = threshold; } public void add(T t){ boolean failed = false; for(T compare : base){ if(similarityComparison(t,compare) < threshold) faled = true; } if(!failed) base.add(t); } public Iterator<T> iterator() { return base.iterator(); } public int size() { return base.size(); } } </code></pre> <p>etc. Obviously T would need to be a subclass of some class that you can perform a comparison on. If you have a euclidean metric, then you can use a space partition, rather then going through every other item.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload