wesm/pandas — Issue #760: Non-matching join operation
Author: wesm
Created: 2012-02-07 16:37:15+00:00
State: open
Labels: Enhancement

from @yarden on the mailing list

```
Hi,

I have a very common use case which pandas which involve a JOIN operation related to coordinate arithmetic on two dataframes, with queries like: for each entry in dataframe A, return all the entries from dataframe B that have coordinates overlapping with this entry. This join is not just matching on the columns values of A and B, since the column values here are coordinates that require simple arithmetic operations like intersection, overlap, etc.

Following Wes's answer to someone else's question here (http://stackoverflow.com/questions/7837722/), I implemented this in a naive way using iteration. My solution is extremely inefficient however, probably in part since it is non-vectorized and requires iterating through each element of the DataFrame.

Do you know of a more efficient/elegant way to do this? The naive implementation is unfortunately not workable for anything even moderately large (e.g. dataframes with a couple thousand entries.)

Complete example below. The first dataframe, df1, is made up of two datasources, and each entry has a coordinate column "loc1". The second dataframe df2 has an interval (start and end coordinate) for each position. The "join" operation function my_join() simply returns all the entry numbers in df2 that have intervals that contain the loc1 column from df1. The join is not unique, so entries in df1 can be contained in multiple entries in df2 (in which case they are stored as comma-separated strings), or they can be contained in none of the entries in df2, in which case the function stores the value as "-1".

I'd like this to scale to instances where df1 and df2 contain ~50k entries. What is the best way to do this?

Thanks very much.

import pandas as p
import scipy
import numpy
# DataFrames for each data source
source1_data = np.array([0, 7, 2, 5, 0, 5, 4, 3, 9, 0, 4, 2, 5, 8, 0, 4, 0, 3, 3, 6])
source1_size = len(source1_data)
source1 = p.DataFrame({"id": range(source1_size),
"loc1": source1_data})
source1.set_index(["id"])
source2_data = np.array([8, 4, 1, 1, 9, 3, 7, 2, 8, 7])
source2_size = len(source2_data)
source2 = p.DataFrame({"id": range(source2_size),
"loc1": source2_data})
source2.set_index(["id"])
dataframe_dict = {"source1": source1,
"source2": source2}
# Concatenated into one DataFrame
df1 = p.concat(dataframe_dict, keys=["source1", "source2"])

df2_size = 6
# dataframe with intervals
intervals = np.array([[ 5, 6],
[ 3, 6],
[ 6, 13],
[ 7, 10],
[ 8, 9],
[ 9, 12]])
df2 = p.DataFrame({"entry": range(df2_size),
"coord1": intervals[:, 0],
"coord2": intervals[:, 1]})
# JOIN df1 and df2 based on interval containment
def my_join(first_df, second_df):
all_hits = []
for entry, value in first_df.T.iteritems():
# Look for cases where loc1 field of df1 falls within
# (coord1, coord2)
coord = value["loc1"]
hits = second_df.ix[(coord > second_df["coord1"]) & \
(coord < second_df["coord2"])]
num_hits = len(hits)
if num_hits == 0:
hits = [-1]
else:
hits = hits["entry"].values
# If there are any hits, record their entries in a
# column of df1. When none, record them as -1
print "%d falls within %d hits: " %(coord, num_hits)
if num_hits > 0: print hits
# Must convert hits to string to store these
# non-scalars in first_df later on
hits_str = ",".join(map(str, hits))
all_hits.append(hits_str)
# Store hits in first_df
first_df["hits"] = all_hits
print "Revised first_df: "
print first_df

my_join(df1, df2)
```