I ran into this problem while looking at Google API distance matrix service.

Say you have a collection of a few million (origins, destinations) unique pairs/2 column table like (address, zip) for example. Note that an address and a zip can show up multiple times in their respective columns. In other words, same origin can have multiple destinations and same destination can have multiple origins - a many to many relation.

Google restricts requests to a maximum of 25 origins or 25 destinations per request and at most 100 elements (origins times destinations) per request. I know I can organize my data in groups of 25 and not bother, but I want to take advantage of the 100 elements (rows) per request so that I can minimize the number of requests I have to make by at least four times (I guess...).

I know this can be optimized but cannot figure it out.

Clarification: (Thank you "hardmath" for taking the time to consider my problem) A bipartite graph with millions of connections is an accurate representation of my problem - Wikipedia. Now imagine you have to store/represent the graph in a table as pairs (u,v) with u in column U and v in column V. For example a $u_{930}$ mapping to $v_{3021}$, $v_{23}$, $v_{12345}$ would sit in that table as three rows: (930,3021), (930,23) and (930,12345) It can be thought as a finite subset UxV $\subset$ $\mathbb N$x$\mathbb N$ (natural numbers). It doesn't matter weather U and V sets are disjoint or not but the u-s and the v-s can repeat multiple times in their respective columns. Now think that you have to make draws of up to 100 records (in any order) until you exhaust the table. You are not allowed to have more than 25 distinct u-s or v-s in one draw. It doesn't matter if some u-s equal some v-s. The "25" restriction applies within "source" and "destination" - not within "source" $\cup$ "destination".

  • $\begingroup$ Please restate you question as precisely as possible. It is not at all clear what you are asking about. $\endgroup$ – Carl Christian Jun 2 '16 at 19:48
  • $\begingroup$ I too was puzzled by what the goal was, so I started by breaking up the block of text into manageable paragraphs. If I've caught on to what you want to do, it can be formulated in terms of bipartite graphs, specifically taking the origin/destination pairs as edges of a bipartite graph and trying to cover that with a collection of restricted complete bipartite graphs (restricted to no more than $100$ edges and no more than $25$ nodes in each part). Strangely I think I saw another problem in the last day or so that was similarly reducible (but with different application in mind). $\endgroup$ – hardmath Jun 2 '16 at 22:43

Let's think of the collection of origin and destination "request" pairs as a bipartite graph $G$. The same location might appear in both roles, as an origin and as a destination. From the perspective of defining a bipartite graph this doesn't cause a problem. We simply "label" the location together with its role as origin or destination in the collection of requests, whenever it appears in one part or the other of the graph.

Each query to the Google API may contain some origins and some destinations, so ideally we would work out the minimum number of such queries necessary to "cover" all the request pairs in $G$. Determining the exact minimum (or even appproximations) is likely to be very difficult, based on what is known about computational complexity of similar set cover problems.

Let $m_q$ be the number of origins and $n_q$ the number of destinations in a query $q$, satisfying the restrictions:

$$ m_q \le 25 \; , \; n_q \le 25 \; , \; m_q n_q \le 100 $$

Such a Cartesian product of origins and destinations amounts to a complete bipartite graph on the respective labelled locations, or a biclique as it is often termed in this context.

We will allow queries that returns some distance results which are not included in the collection $G$ of request pairs. This distinguishes our problem from what is commonly called the biclique cover problem, because we allow those extraneous edges in the potential product sets used to cover the essential edges of $G$. To force the data into a mold of a strict set cover problem, we can imagine that the distance pairs returned by a query are intersected with the collection that defines $G$, ridding ourselves of the extraneous edges but hiding the biclique structure behind our queries.

We also allow the same distance result to appear in more than one query, though of course we only need each edge of $G$ to appear at least once. That makes this an edge covering problem, rather than an edge partitioning problem.

A pertinent term of art here is "community detection" particularly as applied to bipartite graphs or "networks" as much of the literature phrases it. The goal of algorithms in this literature is to find sets of nodes in one part of the bipartite graph $G$ which largely share the same neighbors. Thus an example would be four origin locations which all have twenty-five destination locations in common. Such a "cluster" or community would make an ideal candidate for an efficient query since with one query we would get one hundred of the desired distance results.

Given that you have a few million request pairs in your collection $G$, it might well reduce the total time for queries to do some optimization of this kind. I'll give some references to the recent literature, and if there is interest in either pursuing some of their ideas or in formulating a Quick-and-Dirty alternative, I'd be happy to follow through.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.