1
$\begingroup$

I have a dataset about wireless devices describing when they were connected to a network access point $p$. Any given device can connect to $p$ for some duration, disconnect, and then later reconnect for some other duration. Basically each device in my dataset has a set of intervals belonging to it, where a single device's intervals do not overlap (i.e. a single device will never commence a new session before disconnecting from an old connection).

$p$ can of course support multiple devices connecting to it concurrently. Part of the analysis I am doing on the data is to infer where two devices encounter each other by looking for overlapping intervals in time where those two devices were concurrently connected to $p$. I am having some difficulty coming up with the appropriate notation to succinctly articulate how the set of overlapping intervals between two devices represents the periods during which they encountered.

I've started with the following:

  • Any given device $d$ has a set of intervals describing the periods during which it was connected to $p$. I believe this essentially makes this a "set of sets", if we treat an interval in time (e.g. [513, 936]) as a set. Let's call this set of sets $I_d$.
  • To find overlaps in $d$ and another device $e$'s sessions, we can take the "cross intersection"(?) (like cross product but instead of pair-wise multiplication pair-wise intersection of $d$ and $e$'s intervals). This leaves us with a set of sets where each set describes an overlapping period in time during which $d$ and $e$ where concurrently connected to $p$.

My first question:

  • Is there any notation for the "cross intersection" I describe?

Here's my stab at describing how encounters are inferred from the dataset:

If $d$ and $e$ are two devices connected to AP $p$ for interval sets $S \in [{d_p}^{i}, {d'_p}^{i}] \forall i$ and $T \in [{e_p}^{j}, > {e'_p}^{j}] \forall j$, then $d$ and $e$ encounter at $p$ during intervals $u \in S \,crossIntersect\, T$ where $u \ne \emptyset$.

My second question:

  • Aside from the almost certain technical wrongness of the notation above, could you please provide suggestions on how the notation could be improved, whether this be choice of letters, symbols or other notational conventions?

As you will have gathered I'm pretty amateur at this and this is probably one of the easier questions on this site, so I'm hoping this is still an appropriate venue.

$\endgroup$
2
$\begingroup$

One way is to let $U_{d, p}$ be a union of the intervals of the times that device $d$ accesses point $p$. For example, $$U_{d, p} = [2,5]\cup [19,30] \cup [42, 100].$$

Then, if you want the times that devices $d$ and $e$ are both accessing $p$, then you just want $$U_{d,p} \cap U_{e, p}$$ which will be another union of intervals.

Small example: \begin{align*} U_{d,p} &= [1,5] \cup [8,10]\\ U_{e,p} &= [4,6] \cup [9,12]\\ U_{d,p} \cap U_{e,p} &= [4,5] \cup [9,10] \end{align*}


If you prefer to have things as "sets of intervals" rather than a union (which is what I think you prefer, seeing from your attempt), you could instead define $U_{d,p}$ to be a set, like this: $$U_{d, p} = \left\{[2,5], [19,30],[42, 100]\right\}.$$

Then the set of intervals when $d$ and $e$ are both accessing $p$ is $$\{I_d \cap I_e \mid I_d \in U_{d,p}, I_e \in U_{e,p}, I_d \cap I_e \ne \emptyset \}$$ If you are not familiar with this notation, it reads "the set of all $I_d \cap I_e$ for all $I_d \in U_{d,p}$, $I_e \cap U_{e,p}$, such that $I_d \cap I_e \ne \emptyset$."

$\endgroup$
  • $\begingroup$ Potential correction: in your last sentence, should that be $I_e \in U_{e,p}$ rather than $I_e \cap I_{e,p}$? Or have I misinterpreted? $\endgroup$ – Bryce Thomas Jan 11 '14 at 8:01
  • $\begingroup$ Also, in terms of notation for defining the union of all intervals for a single device $d$ at access point $p$, does $U_{d,p} = \left\{U_{i} \cup U_{j} \mid U_{i} \in U_{d,p}, U_{j} \in U_{d,p}, U_{i} \neq U_{j}\right\}$ look correct? $\endgroup$ – Bryce Thomas Jan 11 '14 at 8:04
  • 1
    $\begingroup$ @BryceThomas Thanks for catching the typo; you're right. The problem with using $U_i \ne U_j$ is that it is not equivalent to $U_i \cap U_j \ne \emptyset$. For example, $U_{d,p} = \{[0,1],[4,6]\}$ and $U_{e,p} = \{[2,3], [5,7]\}$ would have "cross intersection" $\{[5,6]\}$ by my notation, and $\{[5,6], \emptyset, \emptyset, \emptyset\}$ by yours. I don't know if this is a problem or not. Also, I wouldn't use the letter $U$ in $U_i$ because it suggests that $U_i$ and $U_{d,p}$ are the same type of objects when they are not: $U_i$ is an interval, and $U_{d,p}$ is a set of intervals. $\endgroup$ – angryavian Jan 11 '14 at 13:43

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.