Find k nearest restaurants to customers

Posted on 2014-09-09
Medium Priority
Last Modified: 2014-09-18
Please help me out with following problem -
 Given a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.

<<This question (but not the answer) may be found at http://www.geeksforgeeks.org/directi-interview-set-3/ It may also be available elsewhere on the internet, >>    Edited by byundt 12 September 2014 so thread complies with site rules on proper attribution, as well as the Creative Commons rules followed by the geeksforgeeks.org web site.

Question by:Rohit Bajaj
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
  • 2
  • +4
LVL 21

Expert Comment

by:Randy Poole
ID: 40312829
First what is nearest?  I assume you mean a specified distance?  Also you want this done per customer? which would make the only sense..
LVL 27

Expert Comment

ID: 40312854
Is this an academic assignment?  
The sort of help you can get depends on the answer.

You might want to break you map in regions (states or grid squares for example), and then keep track of adjacent/nearby states or sqares.
Then when you get a request, you would only have to calculate accurate distances for a subset of the restaurants.
LVL 84

Expert Comment

ID: 40312881
You might build a Voronoi diagram.
Percona Live Europe 2017 | Sep 25 - 27, 2017

The Percona Live Open Source Database Conference Europe 2017 is the premier event for the diverse and active European open source database community, as well as businesses that develop and use open source database software.


Author Comment

by:Rohit Bajaj
ID: 40312882
No its a algorithm question i found one some site.
The locations are coordinates on 2D plane. So by nearest i mean the mathematical distance between two coordinates.
So a naive approach will be to find the distance between each customer and restaurant
But this is a brute force approach , i want a better way to do it.
LVL 21

Expert Comment

by:Randy Poole
ID: 40312905
Normally you would have a max distance to do your calculations to narrow your search, otherwise you will be calculating every restaurant.  
Grab your customer x,y (normally lat/long)
Lets say the distance is 10 miles (dtr)
Just calculate what 10 miles is for xMin and xMax as well yMin and yMax
Lets say 1 mile=5 steps (ms)

Now just return any restaurants where their x is between xMin and xMax and y is between yMin and yMax
LVL 27

Expert Comment

ID: 40312962
What is the value for k?    Is it known and constant?  Does the order of the k restaurants matter?

With significant preprocessing, you could make a map (like ozo's Voroni diagram) so that each region of the map is associated with the same k restaurants.  This would reduce a customer request to a look-up table.
LVL 84

Expert Comment

ID: 40312979
in 2-d, you can build a k-nearest neighbor Voronoi diagram in O(k^2 N log N) time, and search it in O(k+log N) time

Expert Comment

ID: 40312984
You can exclude the longitude and latitude based on distance so say you are at x and you only want items within x+50 yards.  You can add that distance to your longitude and latitude in all directions and exclude all others that fall out of the range.

So it would be anywhere where x+50 and x-50, same for y.  Then I'm not sure how your data is laid out, but you would search any items that falls within x first then y or both, depending if it is a sql server.

Something like that?

Author Comment

by:Rohit Bajaj
ID: 40313724
HI ozo
in 2-d, you can build a k-nearest neighbor Voronoi diagram in O(k^2 N log N) time, and search it in O(k+log N) time ?

Can you give me a reference where its explained to build a k-nearest neighbor voronoi diagram ?
I am not familiar with voronoi diagrams.
LVL 35

Expert Comment

ID: 40318739
No its a algorithm question i found one some site.
I would say, by that the author has contradicted that the question is of academic type.

if I am right, I would like to post the description of an algorithm based on a suggestion d-glitch has made.

LVL 81

Expert Comment

ID: 40318789
I added a link to the question so it is properly attributed in compliance with site rules.

I did so somewhat selfishly, because I think this is an interesting problem, and am looking forward to a good discussion. This kind of problem comes up very frequently on web pages, because a customer always wants to know where are the closest places to buy a product. Since I am frequently asked to choose the state or territory I live in, I have concluded that most web developers are not using a very good way of solving the problem.

That said, I looked up Voronoi diagrams as mentioned by ozo and find them to be an interesting approach. I don't know how to create one, but if one were available it would definitively answer the question of where the closest restaurant is located. You would also want to have available a list of Voronoi territories that are contiguous with each one of the restaurants.

After doing some more thinking about Voronoi diagrams, I realized that the kth closest restaurant must be in a Voronoi territory contiguous with one or more of the k-1 Voronoi territories previously found. This realization greatly reduces the solution space, as each new solution will lie on a spiral of Voronoi territories surrounding the first one. The proof for my assertion involves drawing a line from the customer to a restaurant in a Voronoi territory that is not contiguous with previous solutions. It can be shown that such a line will always pass through a Voronoi territory that is contiguous with previous solutions--and that the restaurant in the Voronoi territory so traversed will always be closer to the customer than the one in the non-contiguous territory.

When you find the k-1 th closest Voronoi territory, you add its contiguous Voronoi territories to the solutions space. Since there are only a handful of such territories, you can calculate the distance between each newly added restaurant and the customer. These distances will likely sort as more distant from the customer than the previously identified contiguous Voronoi territories, so it will be pretty easy to identify the kth closest one in a previously sorted list.

The diameter of the solution cloud is proportional to the square root of the number of previously identified solutions. The solution space for a new territory is proportional to the circumference of that cloud, so the solution space increases in size as the square root of the number of previous solutions.

All that said, I am now going to be quiet in hopes of learning something from ozo, d-glitch, sarabande and others, who clearly are approaching the problem from a higher level.
LVL 35

Assisted Solution

sarabande earned 800 total points
ID: 40318946
unfortunately I don't have experiences with voronoi diagrams. I am also not sure whether those territories could help to find the exact solution as the territories are different in size and shape.

but, using a grid instead of Voronoi as suggested by d-glitch easily could be calculated and most of your thoughts can be applied with a grid as well:

- find out min and max horizontal and vertical coordinates of the restaurants.
- divide the rectangle spanned by (xmin,ymin), (xmin,ymax), (xmax,ymax), (xmax,ymin) into a nxm grid (like it is on a chessboard with cells labeled A1, ..., H8 or on a map). the number of rows and columns might depend on the number of restaurants, but you also could start with 8x8 to make it simple). if the distribution of the restaurants on the map is not evenly distributed you may increase the number of cells such that the maximum number of restaurants per cell is below a given threshold (for example less than 2k).

- determine for each restaurant which cell it belongs to and create a list of restaurants for each cell (for example by using an array of lists).
- determine a circle around the customer. you may start with a radius that is 1.5 times as long as the diagonal of a cell.
- determine which cells would intersect with the circle.
- calculate the total number r of restaurants of these cells which are included in the circle as well.
- check whether r is between k and 2k. if it is less, you would increase the radius of the customer's circle  (for example by 1/4) until r is within the range (k, 2k), if it is greater, you would decrease the radius accordingly.
the restaurants of these cells would be a superset of the restaurants you look for.

- you may now order the restaurants of the found cells by their absolute distance to the customer's location to determine the final solution.

if the map is small or the number of restaurants is small (say less than 100), the time needed for the "brute force" approach would be not measurable on modern hardware.

some more considerations:

the linear distance between customer and restaurant rarely will the best measure for a customer who looks for the nearest places for restaurants. travel times probably would be much better. however it surely is not easy to get reliable travel times between two arbitrary points on the map at runtime. a possible method for a known map is to using a fixed number of nodal points like junctions where you have a complete table of the travel distances between each pair. the problem then could be modified to find first the nearest nodes to the customer (using linear distance), then find other near nodes by using the travel time table, and finally check the restaurants near to any of these nodes (using linear distance to the node which it is nearest to). from a programmer's point of view I would say the best method to solve the problem is to using a tree of (node) points and (leaf) points where the customer is the root node and restaurants are the leafs and the nodes are chosen such that the distance from root to leaf is minimal.

LVL 84

Accepted Solution

ozo earned 1200 total points
ID: 40319104
There are many grid methods that can be used for k-nearest problems,
such as quad-trees, R-trees, cover trees, etc...
and for each of them there are various ways to pre-process the tree to optimize searching it.
Any of which could make an interesting discussion, but with such an overwhelming number of possibilities
it seems difficult to recommend one over another.
So I'd be inclined to favor a method that solves the problem directly, with a well defined optimal structure,
which is why I suggested Voronoi diagrams.

I'd suggest looking up
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
Mohammad Kolahdouzan and Cyrus Shahabi, 2004
On k-Nearest Neighbor Voronoi Diagrams in the Plane
Der-Tsai Lee, 1982

These can also be used with different distance metrics other than Pythagorean distance.
It could get complicated to try to account for local road travel times under different traffic conditions,
but you did say we are allowed to do an significant amount of pre-processing.

Featured Post

Get proactive database performance tuning online

At Percona’s web store you can order full Percona Database Performance Audit in minutes. Find out the health of your database, and how to improve it. Pay online with a credit card. Improve your database performance now!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …
Starting up a Project
Suggested Courses

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question