# Identifying overlapping time intervals with two more criteria in R?

I have to check birds observations made over a longer period for duplicate/overlapping entries.

Observers from different points (A,B,C) made observations and marked them on paper maps. Those lines where brought into a line feature with additional data for the species, the observation point and the time intervals they were seen.

Normally, the observers communicate with each others via phone while observing, but sometimes they forget, so I get those duplicate lines.

I already reduced the data to those lines which touch the circle, so I do not have to make a spatial analysis, but only compare the time intervals for each species and can be quite sure that it is the same individual that is found by the comparison.

I'm now looking for a way in R to identify those entries which:

• are made on the same day with an overlapping interval
• and where it is the same species
• and which were made from different observation points (A or B or C or ...))

In this example, I manually found possibly duplicated entries of the same individual. Observation point is different (A <-> B), species is the same (Sst) and the interval of the start and end times overlaps.

I would now create a new field "duplicate" in my data.frame, giving both rows a common id to be able to export them and later decide on what to do.

I searched around a lot for already available solutions, but didn't find any concerning the fact that I have to subset the process for the species (preferably without a loop) and have to compare the rows for 2 + x observation points.

Some data to play around with:

``````testdata <- structure(list(bird_id = c("20150712_0810_1410_A_1", "20150712_0810_1410_A_2",
"20150712_0810_1410_A_4", "20150712_0810_1410_A_7", "20150727_1115_1430_C_1",
"20150727_1120_1430_B_1", "20150727_1120_1430_B_2", "20150727_1120_1430_B_3",
"20150727_1120_1430_B_4", "20150727_1120_1430_B_5", "20150727_1130_1430_A_2",
"20150727_1130_1430_A_4", "20150727_1130_1430_A_5", "20150812_0900_1225_B_3",
"20150812_0900_1225_B_6", "20150812_0900_1225_B_7", "20150812_0907_1208_A_2",
"20150812_0907_1208_A_3", "20150812_0907_1208_A_5", "20150812_0907_1208_A_6"
), obsPoint = c("A", "A", "A", "A", "C", "B", "B", "B", "B",
"B", "A", "A", "A", "B", "B", "B", "A", "A", "A", "A"), species = structure(c(11L,
11L, 11L, 11L, 10L, 11L, 10L, 11L, 11L, 11L, 11L, 10L, 11L, 11L,
11L, 11L, 11L, 11L, 11L, 11L), .Label = c("Bf", "Fia", "Grr",
"Kch", "Ko", "Lm", "Rm", "Row", "Sea", "Sst", "Wsb"), class = "factor"),
from = structure(c(1436687150, 1436689710, 1436691420, 1436694850,
1437992160, 1437991500, 1437995580, 1437992360, 1437995960,
1437998360, 1437992100, 1437994000, 1437995340, 1439366410,
1439369600, 1439374980, 1439367240, 1439367540, 1439369760,
1439370720), class = c("POSIXct", "POSIXt"), tzone = ""),
to = structure(c(1436687690, 1436690230, 1436691690, 1436694970,
1437992320, 1437992200, 1437995600, 1437992400, 1437996070,
1437998750, 1437992230, 1437994220, 1437996780, 1439366570,
1439370070, 1439375070, 1439367410, 1439367820, 1439369930,
1439370830), class = c("POSIXct", "POSIXt"), tzone = "")), .Names = c("bird_id",
"obsPoint", "species", "from", "to"), row.names = c("20150712_0810_1410_A_1",
"20150712_0810_1410_A_2", "20150712_0810_1410_A_4", "20150712_0810_1410_A_7",
"20150727_1115_1430_C_1", "20150727_1120_1430_B_1", "20150727_1120_1430_B_2",
"20150727_1120_1430_B_3", "20150727_1120_1430_B_4", "20150727_1120_1430_B_5",
"20150727_1130_1430_A_2", "20150727_1130_1430_A_4", "20150727_1130_1430_A_5",
"20150812_0900_1225_B_3", "20150812_0900_1225_B_6", "20150812_0900_1225_B_7",
"20150812_0907_1208_A_2", "20150812_0907_1208_A_3", "20150812_0907_1208_A_5",
"20150812_0907_1208_A_6"), class = "data.frame")
``````

I found a partial solution with the data.table function foverlaps mentioned e.g. here https://stackoverflow.com/q/25815032

``````library(data.table)
#Subsetting the data for each observation point and converting them into data.tables
A <- setDT(testdata[testdata\$obsPoint=="A",])
B <- setDT(testdata[testdata\$obsPoint=="B",])
C <- setDT(testdata[testdata\$obsPoint=="C",])

#Set a key for these subsets (whatever key exactly means. Don't care as long as it works ;) )
setkey(A,species,from,to)
setkey(B,species,from,to)
setkey(C,species,from,to)

#Generate the match results for each obsPoint/species combination with an overlapping interval
matchesAB <- foverlaps(A,B,type="within",nomatch=0L) #nomatch=0L -> remove NA
matchesAC <- foverlaps(A,C,type="within",nomatch=0L)
matchesBC <- foverlaps(B,C,type="within",nomatch=0L)
``````

Of course, this somehow "works", but is really not what I like to achieve in the end.

First, I have to hard code the observation points. I would prefer to find a solution taking an arbitrary number of points.

Second, the outcome is not in a format that I can really can resume working with easily. The matching rows are actually put INTO the same row, while my goal is to have the rows be put underneath, and in a new column, they would have a common identifier.

Third, I have to check manually again, if an interval overlaps from all three points (which isn't the case with my data, but generally could)

In the end, I would just like to receive a new data.frame with all candidates identifiable by a group id that I can join back to the lines and export the result as a layer for further examination.

So anyone more ideas how to do this?

• I am not sure I understand fully, but it seems like a task that is fairly straight forward in PostgreSQL. There is functions for time ranges. As I have understood it should be easy to share data between PostgreSQL and R. Oct 16, 2015 at 18:11
• I have to admit that I have no to zero knowledge of Postgres, but actually, when drinking a beer this evening, I also had the idea that some sql stuff might be available for this. For the rest of my operations I have to do with the dataset, R is THE tool though, but I know that sql functions can be also performed within R through some packages. Investigating .... Oct 16, 2015 at 23:18
• How big is the dataset - hundreds, thousands, millions of rows? For SQL functions did you find sqldf? Feb 24, 2016 at 19:13
• In the meanwhile, I found a working solution. Shame on me I didn't post it so far. Will have to make it more general to be of use for others, and then I will post it asap. Feb 24, 2016 at 23:10
• Will +1 it if it's all vectorised and doesn't use `for` loops! Feb 25, 2016 at 9:09

As some commenters alluded, SQL is a good option for expressing rather complicated sets of constraints. The sqldf package makes it easy to use SQL's power in R without needing to set up a relational database yourself.

Here's a solution using SQL. Before running, I had to rename your data's interval columns to `startTime` and `endTime` because the name `from` is reserved in SQL.

``````library(reshape2)
library(sqldf)

dupes_wide <- sqldf("SELECT hex(randomblob(16)) dupe_id, x.bird_id x_bird_id, y.bird_id y_bird_id
FROM testdata x JOIN testdata y
ON (x.startTime <= y.endTime)
AND (x.endTime >= y.startTime)
AND (x.species = y.species)
AND (x.obsPoint < y.obsPoint)")
dupes_long <- melt(dupes_wide, id.vars='dupe_id', value.name='bird_id')
merge(testdata, dupes_long[, c('dupe_id', 'bird_id')], by='bird_id', all.x=TRUE)
``````

To aid understanding, the SQL response `dupes_wide` ends up looking like this:

```                         dupe_id              x_bird_id              y_bird_id
253FCC7A58FD8401960FC5D95153356C 20150727_1130_1430_A_2 20150727_1120_1430_B_1
9C1C1A13306ECC2DF78004D421F70CE6 20150727_1130_1430_A_5 20150727_1120_1430_B_4
1E8316DBF631BBF6D2CCBD15A85E6EF3 20150812_0907_1208_A_5 20150812_0900_1225_B_6```

Self-join `FROM testdata x JOIN testdata y` : Finding pairs of rows from a single dataset is a self-join. We need to compare every row with every other one. The `ON` expression lists the constraints for keeping pairs.

Overlapping interval: I'm pretty sure the definition of overlap I used in this SQL (source) differs from what `foverlaps` was doing for you. You used the "within" type, which requires the observation at the earlier `obsPoint` to be entirely within the observation at the later `obsPoint` (but it misses the converse, e.g. if C's observation is entirely within B's). Luckily it's easy in SQL if you need to encode a different definition of overlap.

Different points: Your constraint that duplicates were made from different observation points would really be expressed `(x.obsPoint <> y.obsPoint)`. If I'd typed that, SQL would return every duplicated pair twice, just with the birds switched order in each row. Instead I used a `<` to keep only the unique half of the rows. (This is not the only way to do this)

Unique duplicate ID: As with your previous solution, the SQL itself list the duplicates in the same row. `hex(randomblob(16))` is a hacky (yet recommended) way in SQLite to generate unique IDs for each pair.

Output format: You didn't like the duplicates in the same row, so `melt` splits them out, and `merge` assigns the duplicate IDs back to your initial data frame.

Limitations: My solution doesn't handle the case where the same bird is captured in more than two tracks. It's trickier and somewhat ill-defined. For example, if their time ranges look like

```    |-- Bird1 --|
|-- Bird2 --|
|-- Bird3 --|```

then Bird1 is a duplicate of Bird2, which is a duplicate of Bird3, but are Bird1 and Bird3 duplicates?