Stories
Slash Boxes
Comments

SoylentNews is people

posted by martyb on Wednesday August 15 2018, @01:02PM   Printer-friendly
from the won't-you-be-my-neighbor? dept.

The nearest neighbor problem asks where a new point fits in to an existing data set. A few researchers set out to prove that there was no universal way to solve it. Instead, they found such a way.

If you were opening a coffee shop, there's a question you'd want answered: Where's the next closest cafe? This information would help you understand your competition.

This scenario is an example of a type of problem widely studied in computer science called "nearest neighbor" search. It asks, given a data set and a new data point, which point in your existing data is closest to your new point? It's a question that comes up in many everyday situations in areas such as genomics research, image searches and Spotify recommendations.

And unlike the coffee shop example, nearest neighbor questions are often very hard to answer. Over the past few decades, top minds in computer science have applied themselves to finding a better way to solve the problem. In particular, they've tried to address complications that arise because different data sets can use very different definitions of what it means for two points to be "close" to one another.

Now, a team of computer scientists has come up with a radically new way of solving nearest neighbor problems. In a pair of papers, five computer scientists have elaborated the first general-purpose method of solving nearest neighbor questions for complex data.


Original Submission

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 1, Interesting) by Anonymous Coward on Wednesday August 15 2018, @02:12PM (5 children)

    by Anonymous Coward on Wednesday August 15 2018, @02:12PM (#721779)

    and if not, why not

    Starting Score:    0  points
    Moderation   +1  
       Interesting=1, Total=1
    Extra 'Interesting' Modifier   0  

    Total Score:   1  
  • (Score: 2) by takyon on Wednesday August 15 2018, @02:18PM (3 children)

    by takyon (881) <reversethis-{gro ... s} {ta} {noykat}> on Wednesday August 15 2018, @02:18PM (#721781) Journal

    Why solve when you can buy?

    --
    [SIG] 10/28/2017: Soylent Upgrade v14 [soylentnews.org]
    • (Score: 0) by Anonymous Coward on Wednesday August 15 2018, @06:06PM (2 children)

      by Anonymous Coward on Wednesday August 15 2018, @06:06PM (#721868)

      Why buy when you can steal?

      • (Score: 0) by Anonymous Coward on Wednesday August 15 2018, @07:03PM (1 child)

        by Anonymous Coward on Wednesday August 15 2018, @07:03PM (#721889)

        Why steal when you can control?

  • (Score: 4, Informative) by Non Sequor on Wednesday August 15 2018, @02:40PM

    by Non Sequor (1005) on Wednesday August 15 2018, @02:40PM (#721789) Journal

    Well, the graph theory version of the problem actually has intractable cases, so-called expander graphs that are both highly connected (you have to remove a lot of vertices or edges to split the graph in two pieces) and with low average degree (most vertices aren’t connected to many others).

    --
    Write your congressman. Tell him he sucks.