Range join data.frames - specific date column with date ranges/intervals in R

Question

Although the details of this are, of course, app specific, in the SO spirit I'm trying to keep this as general as possible! The basic problem is how to merge data.frames by date when one data.frame has specific dates and the other has a date-range. Secondly, the question asks how to deal with multiple observations of a given variable, and how to include these in a final output data.frame. I'm sure some of this is standard, but an pretty full search has revealed little.

The mre objects I'm trying to merge are below.

# 'Speeches' data.frame
structure(list(Name = structure(c(2L, 2L, 2L, 2L, 2L, 2L, 2L, 
2L, 2L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), .Label = c("BBB", 
"AAA"), class = "factor"), Date = structure(c(12543, 12404, 12404, 
12404, 12373, 12362, 12345, 12320, 12207, 15450, 15449, 15449, 
15449, 15449, 15449, 15449, 15449, 15448, 15448, 15448), class = "Date")), .Names =     c("Name", 
"Date"), row.names = c("1", "1.1", "1.2", "1.3", "1.4", "1.5", 
"1.6", "1.7", "1.8", "2", "2.1", "2.2", "2.3", "2.4", "2.5", 
"2.6", "2.7", "2.8", "2.9", "2.10"), class = "data.frame")

# 'History' data.frame
structure(list(Name = structure(c(2L, 2L, 2L, 2L, 2L, 2L, 1L, 
1L, 1L, 1L, 1L, 1L, 1L), .Label = c("BBB", "AAA"), class = "factor"), 
    Role = structure(c(1L, 2L, 3L, 3L, 3L, 4L, 1L, 2L, 3L, 3L, 
3L, 3L, 4L), .Label = c("Political groups", "National parties", 
"Member", "Substitute", "Vice-Chair", "Chair", "Vice-President", 
"Quaestor", "President", "Co-President"), class = "factor"), 
Value = structure(c(10L, 12L, 6L, 3L, 8L, 4L, 9L, 11L, 1L, 
7L, 1L, 2L, 5L), .Label = c("a", "b", "c", "d", "e", "f", 
"g", "h", "i", "j", "k", "l", "m", "n", "o"), class = "factor"), 
Role.Start = structure(c(12149, 12149, 12150, 12150, 12152, 
12150, 14439, 14439, 14441, 14503, 15358, 15411, 14441), class = "Date"), 
Role.End = structure(c(12618, 12618, 12618, 12618, 12538, 
12618, 15507, 15507, 15357, 15507, 15410, 15507, 15357), class = "Date")), .Names = c("Name", 
"Role", "Value", "Role.Start", "Role.End"), row.names = c(NA, 
13L), class = "data.frame")

There are a number of difficulties that I'm facing.

1) Although there is date information in both the speeches and history data, in the first I have specific dates for each entry, and in the second there is a date-range. Ideally, I would like to be able to merge so that each speech entry is matched with both the speaker ('Name') and the history entry into which the speech date falls.

2) The desired output is to have a data.frame or data.table with rows equal to the observations in the speeches data.frame, and columns for Name, Date, and each of the Roles (which will be populated by value). However, some Roles appear multiple times for a given speaker, on a given date, and thus I need to be able to create multiple columns for these instances.

The object below gives this output, but was constructed using a horribly fragile and very slow for-loop:

structure(list(Name = structure(c(2L, 2L, 2L, 2L, 2L, 2L, 2L, 
2L, 2L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), .Label = c("BBB", 
"AAA"), class = "factor"), Date = structure(c(12543, 12404, 12404, 
12404, 12373, 12362, 12345, 12320, 12207, 15450, 15449, 15449, 
15449, 15449, 15449, 15449, 15449, 15448, 15448, 15448), class = "Date"), 
`Political groups` = structure(c(2L, 2L, 2L, 2L, 2L, 2L, 
2L, 2L, 2L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L), .Label = c("i", 
"j"), class = "factor"), `National parties` = structure(c(2L, 
2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L, 1L, 1L), .Label = c("k", "l"), class = "factor"), 
Member.1 = structure(c(1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L, 2L), .Label = c("f", 
"g"), class = "factor"), Member.2 = structure(c(2L, 2L, 2L, 
2L, 2L, 2L, 2L, 2L, 2L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, 
1L, 1L), .Label = c("b", "c"), class = "factor"), Member.3 = structure(c(NA, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, NA, NA, NA, NA, NA, NA, NA, 
NA, NA, NA, NA), .Label = "h", class = "factor"), Substitute = structure(c(1L, 
1L, 1L, 1L, 1L, 1L, 1L, 1L, 1L, NA, NA, NA, NA, NA, NA, NA, 
NA, NA, NA, NA), .Label = "d", class = "factor")), .Names = c("Name", 
"Date", "Political groups", "National parties", "Member.1", "Member.2", 
"Member.3", "Substitute"), row.names = c("1", "1.1", "1.2", "1.3", 
"1.4", "1.5", "1.6", "1.7", "1.8", "2", "2.1", "2.2", "2.3", 
"2.4", "2.5", "2.6", "2.7", "2.8", "2.9", "2.10"), class = "data.frame")

Any help and/or comments on how to improve this question would be welcome!

Answer 1

Update: In v1.9.3+, now overlap joins are implemented. This is a special case where start and end Date are identical in Speeches. We can accomplish this using foverlaps() as follows:

require(data.table) ## 1.9.3+
setDT(Speeches)
setDT(History)

Speeches[, `:=`(Date2 = Date, id = .I)]
setkey(History, Name, Role.Start, Role.End)

ans = foverlaps(Speeches, History, by.x=c("Name", "Date", "Date2"))[, Date2 := NULL]
ans = ans[order(id, Value)][, N := 1:.N, by=list(Name, Date, Role, id)]
ans = dcast.data.table(ans, id+Name+Date ~ Role+N, value.var="Value")

---

This is a case for range/interval join.

Here's the data.table way. It uses two rolling joins.

require(data.table) ## 1.9.2+
dt1 = as.data.table(Speeches)
dt2 = as.data.table(History)

# first rolling join - to get end indices
setkey(dt2, Name, Role.Start)
tmp1 = dt2[dt1, roll=Inf, which=TRUE]

# second rolling join - to get start indices
setkey(dt2, Name, Role.End)
tmp2 = dt2[dt1, roll=-Inf, which=TRUE]

# generate dt1's and dt2's corresponding row indices
idx = tmp1-tmp2+1L
idx1 = rep(seq_len(nrow(dt1)), idx)
idx2 = data.table:::vecseq(tmp2, idx, sum(idx))

dt1[, id := 1:.N] ## needed for casting later

# subset using idx1 and idx2 and bind them colwise
ans = cbind(dt1[idx1], dt2[idx2, -1L, with=FALSE])

# a little reordering to get the output correctly (factors are a pain!)
ans = ans[order(id,Value)][, N := 1:.N, by=list(Name, Date, Role, id)]

# finally cast them.
f_ans = dcast.data.table(ans, id+Name+Date ~ Role+N, value.var="Value")

Here's the output:

    id Name       Date Political groups_1 National parties_1 Member_1 Member_2 Member_3 Substitute_1
 1:  1  AAA 2004-05-05                  j                  l        c        f       NA            d
 2:  2  AAA 2003-12-18                  j                  l        c        f        h            d
 3:  3  AAA 2003-12-18                  j                  l        c        f        h            d
 4:  4  AAA 2003-12-18                  j                  l        c        f        h            d
 5:  5  AAA 2003-11-17                  j                  l        c        f        h            d
 6:  6  AAA 2003-11-06                  j                  l        c        f        h            d
 7:  7  AAA 2003-10-20                  j                  l        c        f        h            d
 8:  8  AAA 2003-09-25                  j                  l        c        f        h            d
 9:  9  AAA 2003-06-04                  j                  l        c        f        h            d
10: 10  BBB 2012-04-20                  i                  k        b        g       NA           NA
11: 11  BBB 2012-04-19                  i                  k        b        g       NA           NA
12: 12  BBB 2012-04-19                  i                  k        b        g       NA           NA
13: 13  BBB 2012-04-19                  i                  k        b        g       NA           NA
14: 14  BBB 2012-04-19                  i                  k        b        g       NA           NA
15: 15  BBB 2012-04-19                  i                  k        b        g       NA           NA
16: 16  BBB 2012-04-19                  i                  k        b        g       NA           NA
17: 17  BBB 2012-04-19                  i                  k        b        g       NA           NA
18: 18  BBB 2012-04-18                  i                  k        b        g       NA           NA
19: 19  BBB 2012-04-18                  i                  k        b        g       NA           NA
20: 20  BBB 2012-04-18                  i                  k        b        g       NA           NA

---

Alternatively you can also accomplish this using GenomicRanges package from bioconductor, which deals with Ranges quite nicely, especially when you require an additional column to join by (Name) in addition to the ranges. You can install it from here.

require(GenomicRanges)
require(data.table)
dt1 <- as.data.table(Speeches)
dt2 <- as.data.table(History)
gr1 = GRanges(Rle(dt1$Name), IRanges(as.numeric(dt1$Date), as.numeric(dt1$Date)))
gr2 = GRanges(Rle(dt2$Name), IRanges(as.numeric(dt2$Role.Start), as.numeric(dt2$Role.End)))

olaps = findOverlaps(gr1, gr2, type="within")
idx1 = queryHits(olaps)
idx2 = subjectHits(olaps)

# from here, you can do exactly as above
dt1[, id := 1:.N]
...
...
dcast.data.table(ans, id+Name+Date ~ Role+N, value.var="Value")

Gives the same result as above.

Answer 2

Here's an approach using sqldf(...) from the sqldf package. This produces your result, with the following exceptions:

1. The Member.n columns contain values in alphabetical order, rather than the order in which they appear in the History data frame. So Member.1 would contain c and Member.2 would contain f, rather than the other way around.
2. Your result set has all the role-related columns as factors, whereas this result set has them as character. If it's important that can easily be changed.

Note that Speeches and History are used for the input data frames, and I use your Output dataframe to get the columns' order only.

library(sqldf)    # for sqldf(...)
library(reshape2) # for dcast(...)

colnames(History)[4:5] <- c("Start","End")   # sqldf doesn't like "." in colnames
Speeches$id <- rownames(Speeches)            # need unique id column
result <- sqldf("select a.id, a.Name, a.Date, b.Role, b.Value 
                from Speeches a, History b 
                where a.Name=b.Name and a.Date between b.Start and b.End")
Roles <- aggregate(Role~Name+Date+id,result,function(x)
  ifelse(x=="Member",paste(x,1:length(x),sep="."),as.character(x)))$Role
result$Roles <- unlist(Roles)
result <- dcast(result,Name+Date+id~Roles,value.var="Value")
result <- result[order(result$id),]   # re-order the rows
result <- result[,colnames(Output)]   # re-order the columns

Explanation

• First, we need an id column in Speeches to differentiate between the replicated columns in the result. So we use the row names for that.
• Second, we use sqldf(...) to merge the Speeches and History tables based on your criteria. Because you want dates to match based on a range, this may be the best approach.
• Third, we have to convert multiple instances of "Member" into "Member.1", "Member.2", etc. We do this using aggregate(...) and paste(...).
• Fourth, we have to convert the result of the sql, which is in "long" format (all Values in one column, distinguished by a second column Roles), into "wide" format, values for each Role in different columns. We do this using dcast(...).
• Finally, we reorder the rows and columns to be consistent with your result.