# Disentangling Online Chats with DAG-Structured LSTMs

Duccio Pappadopulo∗1, Lisa Bauer∗2, Marco Farina1, Ozan İrsoy1, Mohit Bansal2
1Bloomberg 2UNC Chapel Hill
{dpappadopulo, mfarina19<EMAIL_ADDRESS>
{lbauer6<EMAIL_ADDRESS>
###### Abstract

Many modern messaging systems allow fast and synchronous textual communication
among many users. The resulting sequence of messages hides a more complicated
structure in which independent sub-conversations are interwoven with one
another. This poses a challenge for any task aiming to understand the content
of the chat logs or gather information from them. The ability to disentangle
these conversations is then tantamount to the success of many downstream tasks
such as summarization and question answering. Structured information
accompanying the text such as user turn, user mentions, timestamps, is used as
a cue by the participants themselves who need to follow the conversation and
has been shown to be important for disentanglement. DAG-LSTMs, a
generalization of Tree-LSTMs that can handle directed acyclic dependencies,
are a natural way to incorporate such information and its non-sequential
nature. In this paper, we apply DAG-LSTMs to the conversation disentanglement
task. We perform our experiments on the Ubuntu IRC dataset. We show that the
novel model we propose achieves state of the art status on the task of
recovering _reply-to_ relations and it is competitive on other disentanglement
metrics.

##  1 Introduction

††$*$ Equal contribution

Online chat and text messaging systems like Facebook Messenger, Slack, WeChat,
WhatsApp, are common tools used by people to communicate in groups and in real
time. In these venues multiple independent conversations often occur
simultaneously with their individual utterances interspersed.

Figure 1:  Excerpt from the IRC dataset (_left_) and our reply-to classifier
architecture (_right_). Blue dots represent a unidirectional DAG-LSTM unit
processing the states coming from the children of the current node. Red dots
represent the GRU units performing thread encoding. At this point in time, we
are computing the score (log-odds) of fifth utterance replying to the third.

It is reasonable to assume the existence of an underlying _thread_ structure
partitioning the full conversation into disjoint sets of utterances, which
ideally represent independent sub-conversations. The task of identifying these
sub-units, _disentanglement_ , is a prerequisite for further downstream tasks
among which question answering, summarization, and topic modeling Traum et al.
(2004); Shen et al. (2006); Adams and Martell (2008); Elsner and Charniak
(2010). Additional structure can generally be found in these logs, as a
particular utterance could be a response or a continuation of a previous one.
Such _reply-to_ relationships implicitly define threads as the connected
components of the resulting graph topology, and can then be used for
disentanglement Mehri and Carenini (2017); Dulceanu (2016); Wang et al.
(2008); Gaoyang Guo et al. (2018).

Modeling work on conversation disentanglement spans more than a decade. Elsner
and Charniak (2008, 2010) use feature based linear models to find pairs of
utterances belonging to the same thread and heuristic global algorithms to
assign posts to threads. Mehri and Carenini (2017) and Jiang et al. (2018),
while also adopting similar heuristics, use features extracted through neural
models, LSTMSs Hochreiter and Schmidhuber (1997) and siamese CNNs Bromley et
al. (1993) respectively. Wang et al. (2011) follow a different approach by
modeling the interactions between the predicted reply-to relations as a
conditional random field.

One challenge in building automatic systems that perform disentanglement is
the scarcity of large annotated datasets to be used to train expressive
models. A remarkable effort in this direction is the work of Kummerfeld et al.
(2019a) and the release of a dataset containing more that $77k$ utterances
from the IRC #Ubuntu channel with annotated reply-to structure. In the same
paper, it is shown how a set of simple handcrafted features, pooling of
utterances GloVe embeddings Pennington et al. (2014), and a feed-forward
classifier can achieve good performances on the disentanglement task. Most of
the follow-up work on the dataset relies on BERT Devlin et al. (2019)
embeddings to generate utterance representations Zhu et al. (2020); Gu et al.
(2020); Li et al. (2020). Zhu et al. (2020) use an additional transformer
module to contextualize these representations, while Gu et al. (2020); Li et
al. (2020) use an LSTM. Two exceptions are Liu et al. (2020), which models
thread membership in an online fashion and discards reply-to relationships,
and the recent Yu and Joty (2020a) which uses pointer networks Vinyals et al.
(2015).

In this short paper, we use DAG-structured LSTMs İrsoy et al. (2019) to study
disentanglement. As a generalization of Tree-LSTMs Tai et al. (2015a), DAG-
LSTMs allow to faithfully represent the structure of a conversation, which is
more properly described as a directed acyclic graph (DAG) than a sequence.
Furthermore, DAG-LSTMs allow for the systematic inclusion of structured
information like user turn and mentions in the learned representation of the
conversation context. We enrich the representation learned by the DAG-LSTM by
concatenating to it a representation of the thread to which the utterance
belongs. This _thread encoding_ is obtained by means of a GRU unit Cho et al.
(2014) and captures thread specific features like style, topic, or persona.
Finally we manually construct new features to improve username matching, which
is crucial for detecting user mentions, one of the most important features for
disentanglement.

Our results are summarized in Table 1. The DAG-LSTM significantly outperforms
the BiLSTM baseline. Ablation studies show the importance of the new features
we introduce. When augmented by thread encoding and a careful handling of
posts predicted to be thread starters, the DAG-LSTM architecture achieves
state of the art performances on _reply-to_ relation extraction on the IRC
Ubuntu dataset and it is competitive on the other metrics which are relevant
to disentanglement.

##  2 Methodology

###  2.1 Problem Statement

A multi-party chat $C$ is a sequence of posts $(c_{i})_{i}$, $i=1,\ldots,|C|$.
For each _query_ post $c_{i}$ we look for the set of _link_ posts
$\mathcal{R}(c_{i})$ such that $c_{i}$ replies to, or _links to_ , $c_{j}$ for
$c_{j}\in\mathcal{R}(c_{i})$. When a post $c$ is a conversation starter we
define, consistently with Kummerfeld et al. (2019a), $\mathcal{R}(c)=\\{c\\}$,
that is $c$ replies to itself, it is a _self-link_. This reply-to binary
relation defines a DAG over $C$. By taking the union of the reply-to relation
with its converse and by calculating its transitive closure, we obtain an
equivalence relation on $C$ whose equivalence classes are threads, thus
solving the disentanglement problem.

We frame the problem as a sequence classification task. For each query post
$c_{i}$ we consider its $L$ preceding posts
$\mathcal{O}_{c_{i}}\equiv\\{c_{i-L-1},\ldots,c_{i}\\}$ and predict one of
them as its link. In the IRC Ubuntu dataset, predicting a single link per
query post is a good approximation, holding true for more than 95% of the
annotated utterances. We use $L=50$ in the following. As described in Sections
2.2 and 2.3, for each query utterance $c_{i}$, we construct a contextualized
representation, $\phi_{i}\equiv\phi(c_{i},C)$. We do the same for each of the
links $c_{j}\in\mathcal{O}_{c_{i}}$, using a representation $\psi$ that can in
principle differ from $\phi$. We then calculate $p(c_{i}\,{\textrm{replies-
to}}\,c_{j})\equiv p(c_{j}|c_{i})$ as

$p(c_{j}|c_{i})\equiv\frac{\exp(s_{ij})}{\sum_{c_{k}\in\mathcal{O}_{c_{i}}}\exp(s_{ik})},$
(1)

where $s_{ij}\equiv s(\phi_{i},\psi_{j},f_{ij})$ is a real-valued scoring
function described in Section 2.4 and $f_{ij}$ are additional features. The
parameters of the resulting model are learned by maximizing the likelihood
associated to Eq. 1. At inference time we predict
$\hat{j}=\textrm{argmax}_{c_{j}\in\mathcal{O}_{c_{i}}}p(c_{j}|c_{i})$.

###  2.2 Contextual Post Representation

The construction of the $\phi$ and $\psi$ representations closely follows
İrsoy et al. (2019). Every post $c_{i}$ is represented as a sequence of tokens
$(t_{n}^{i})_{n}$. An embedding layer maps the tokens to a sequence of
$d_{I}$-dimensional real vectors $(\omega_{n}^{i})_{n}$. We use the tokenizer
and the word embeddings from Kummerfeld et al. (2019a), $d_{I}=50$. We
generate a representation $\chi_{i}$ of $c_{i}$ by means of a single BiLSTM
layer unrolled over the sequence of the token embeddings
$(\upsilon^{i}_{n})_{n}\equiv\textrm{BiLSTM}[(\omega_{n}^{i})_{n}]$ followed
by elementwise max-affine pooling
$\chi_{i}=\max_{n}{\textrm{Affine}}[(\upsilon^{i}_{n})_{n}]$.

To obtain the contextualized representations $\phi$, we use a DAG-LSTM layer.
This is an N-ary Tree-LSTM Tai et al. (2015a) in which the sum over children
in the recursive definition of the memory cell is replaced with an elementwise
max operation (see Appendix). This allows the existence of multiple paths
between two nodes (as it is the case if a node has multiple children) without
the associated state explosion İrsoy et al. (2019). This is crucial to handle
long sequences, as in our case.

At each time step the DAG-LSTM unit receives the utterance representation
$\chi_{i}$ of the current post $c_{i}$ as the input and all the hidden and
cell states coming from a labeled set of children, $\mathcal{C}(c_{i})$, see
Figure 1. In our case $\mathcal{C}(c_{i})$ contains three elements: the
previous post in the conversation ($c_{i-1}$), the previous post by the same
user of $c_{i}$, the previous post by the user mentioned in $c_{i}$ if any.
More dependencies can be easily added making this architecture well suited to
handle structured information. The DAG-LSTM is unrolled over the sequence
$(\\{\chi_{i},\mathcal{C}(c_{i})\\})_{i}$, providing a sequence of
contextualized post representations $(\phi_{i})_{i}$. We also consider a
bidirectional DAG-LSTM defined by a second unit processing the reversed
sequence $\tilde{c}_{i}\equiv c_{|C|-i+1}$. Forward and backward DAG-LSTM
representations are then concatenated to obtain $\phi$.

###  2.3 Thread Encoding

The link post representation $\psi$ can coincide with the query one,
$\psi_{j}\equiv\phi_{j}$. One potential issue with this approach is that
$\psi$ does not depend on past thread assignments. Furthermore, thread-
specific features such as topic and persona, cannot be easily captured by the
hierarchical but sequential model described in the previous section. Thus we
augment the link representations by means of _thread encoding_ Liu et al.
(2020). Given a query, $c_{i}$, and a link $c_{j}$ posts pair, we consider the
thread $\mathcal{T}(c_{j})=(c_{t_{i}})$, $t_{i}<t_{i+1}$,
$t_{|\mathcal{T}(c_{j})|}=j$, to which $c_{j}$ has been assigned. We construct
a representation $\tau_{j}$ of such thread by means of a GRU cell,
$\tau_{j}={\textrm{GRU}}[(\chi(c))_{c\in\mathcal{T}(c_{j})}]$. $\psi_{j}$ is
then obtained by concatenating $\phi_{j}$ and $\tau_{j}$. At training time we
use the gold threads to generate the $\tau$ representations, while at
evaluation time we use the predicted ones.

###  2.4 Scoring Function

Once query and link representations are constructed we use the scoring
function in Eq. 1 to score each link against the query utterance, with $s$ a
three-layer feed-forward neural network. The input of the network is the
concatenation $[\phi_{i};\psi_{j};f_{ij}]$, where $f_{ij}$ are the 77 features
introduced by Kummerfeld et al. (2019a). We augment them by 42 additional
features based on Levenshtein distance and longest common prefix between
query’s username and words in the link utterance (and viceversa). These are
introduced to improve mention detection by being more lenient on spelling
mistakes (see 2.5 for precise definitions).

###  2.5 User Features

While IRC chats allow systematically tagging other participants (a single
mention per post), users can address each other explicitly by typing
usernames. This allows for abbreviations and typos to be introduced, which are
not efficiently captured by the set of features used by Kummerfeld et al.
(2019b). To ameliorate this problem we construct additional features. Given a
pair of utterances $c_{1}$ and $c_{2}$ we define the following:

  * •

Smallest Levenshtein distance ($D_{L}$) between $c_{1}(c_{2})$’s username and
each of the word in $c_{2}(c_{1})$; 5 bins, $D_{L}=i$ for $i=0,\ldots,4$ or
$D_{L}>4$ .

  * •

Largest length of common prefix ($\ell$) between $c_{1}(c_{2})$’s username and
each of the word in $c_{2}(c_{1})$; 5 bins, $\ell=i$ for $i=3,\ldots,6$ or
$\ell>6$.

  * •

Binary variable indicating whether $c_{1}(c_{2})$’s username is a prefix of
any of the words in $c_{2}(c_{1})$.

These amount to a total of 42 additional features for each pair of posts.

##  3 Results

Model | Graph | Cluster
---|---|---
| ${\rm P}$ | ${\rm R}$ | ${\rm F}$ | ${\rm P}$ | ${\rm R}$ | ${\rm F}$
Kummerfeld et al. | $73.7$ | $71.0$ | $72.3$ | $34.6$ | $38.0$ | $36.2$
Zhu et al.⋆ | $73.2$ | $69.2$ | $70.6$ | $35.8$ | $32.7$ | $34.2$
Li et al.⋆ |  |  |  | $42.3$ | $\underline{46.2}$ | $44.1$
Yu and Joty | $74.7$ | $72.7$ | $73.7$ | $33.0$ | $38.9$ | $36.0$
$+$ self. | $\underline{74.8}$ | $\underline{72.7}$ | $\underline{73.7}$ | $42.2$ | $40.9$ | $41.5$
$+$ joint train, self. | $74.5$ | $71.7$ | $73.1$ | $\underline{44.9}$ | $44.2$ | $\underline{44.5}$
BiLSTM ($\downarrow$) | $73.9$ | $71.2$ | $72.5$ | $31.3$ | $37.5$ | $34.1$
DAG-LSTM | $74.9$ | $72.2$ | $73.6$ | $37.3$ | $42.3$ | $39.6$
$-$ user features ($\downarrow$) | $74.0$ | $71.3$ | $72.6$ | $33.6$ | $39.7$ | $36.4$
$-$ mention link | $74.5$ | $71.8$ | $73.1$ | $33.5$ | $38.3$ | $35.7$
$+$ self. ($\uparrow$) | $74.9$ | $72.6$ | $73.8$ | $41.1$ | $41.1$ | $41.1$
$+$ thread enc. | $75.0$ | $72.3$ | $73.7$ | $37.3$ | $\mathbf{42.5}$ | $39.7$
$+$ thread enc., self. | $\mathbf{75.2}$ | $\mathbf{72.7}$ | $\mathbf{73.9}$ | $\mathbf{42.4}$ | $41.7$ | $\mathbf{42.0}$
Table 1:  Results of our experiments (_bottom_ , best in bold) and literature
(_top_ , best underlined). The $\uparrow$($\downarrow$) sign indicates the
model being significantly better (worse) ($\textrm{p}<0.05$) than the DAG-LSTM
entry based on a McNemar test McNemar (1947) conducted on the _test_ set. User
features and mention links are included in this baseline model, thread
encoding and self-link threshold tuning are not. Starred entries use
contextual embeddings.

###  3.1 Evaluation

We conduct our experiments on the Ubuntu IRC dataset for disentanglement
Kummerfeld et al. (2019a); Kim et al. (2019). We focus on two evaluation
metrics defined in Kummerfeld et al. (2019a): _graph_ F1, the F-score
calculated using the number of correctly predicted reply-to pairs; _cluster_
F1, the F-score calculated using the number of matching threads of length
greater than 1.

###  3.2 Experiments

As a baseline, we use a BiLSTM model in which $\phi_{i}(=\psi_{i})$ is
obtained as the hidden states of a bidirectional LSTM unrolled over the
sequence $(\chi_{i})_{i}$. The base DAG-LSTM model uses both username and
mentions to define the children set $\mathcal{C}$ of an utterance.
Bidirectionality is left as a hyperparameter. All our experiments use the same
architecture from section 2 to construct the utterance representation $\chi$.
We train each model by minimizing the negative log-likelihood for Eq. 1 using
Adam optimizer Kingma and Ba (2019). We tune the hyperparameters of each
architecture through random search.111We refer to the Appendix for details.
Table 1 shows the test set performances of the models which achieve the best
graph ${\textrm{F}}_{1}$ score over the dev set. Optimizing graph over cluster
score is motivated by an observation: dev set cluster ${\textrm{F}}_{1}$ score
displays a much larger variance than graph ${\textrm{F}}_{1}$ score, which is
roughly four-fold after subtracting the score rolling average. By picking the
iteration with the best cluster ${\textrm{F}}_{1}$ score we would be more
exposed to fluctuation and to worse generalization, which we observe.

###  3.3 Self-Links Threshold Tuning

As noted by Yu and Joty (2020b), the ability of the model to detect self-links
is crucial for its final performances. In line with their findings, we also
report that all our models are skewed towards high recall for self-link
detection (Table 2).

Model | Self-links
---|---
| ${\rm P}$ | ${\rm R}$ | ${\rm F}$
BiLSTM | $79.6$ | $94.6$ | $86.5$
DAG-LSTM | $82.8$ | $93.8$ | $88.0$
$+$ self-links threshold | $87.7$ | $92.4$ | $90.0$
DAG-LSTM + thread enc. | $81.4$ | $93.8$ | $87.2$
$+$ self-links threshold | $89.8$ | $90.6$ | $90.2$
Table 2:  Thread starters (_self-links_) performances for our models in Table
1, before and after thresholding.

To help with this, we introduce two thresholds $\theta$ and $\delta$, which we
compare with $\hat{p}$, the argmax probability Eq. 1, and $\Delta p$, the
difference between the top-2 predicted probabilities. Whenever the argmax is a
self-link: if $p<\theta$, we predict the next-to-argmax link, otherwise we
predict both the top-2 links if also $\Delta\hat{p}<\delta$. On the dev set,
we first fine-tune $\theta$ to maximize the self-link F1 score and the fine-
tune $\delta$ to maximize the cluster F1 score.

###  3.4 Results Discussion

Table 1 shows our main results. Our DAG-LSTM model significantly outperforms
the BiLSTM baseline. We perform ablation studies on our best DAG-LSTM model
showing that while both user features and mention link provide a performance
improvement for both cluster and graph score, only user features ablation
results in a significant change. Self-links threshold tuning improves
performances, particularly on cluster score for both models, highlighting the
importance of correctly identifying thread starters.

The DAG-LSTM model with thread encoding achieves state of the art performances
in predicting reply-to relations. This is particularly interesting especially
when we compare with models employing contextual embeddings like Zhu et al.
(2020). For the cluster scores, the best model is the pointer network model of
Yu and Joty (2020a), which is anyway within less than 0.5% of the best
contextual model, and within 2.5% of our model. The difference mainly arises
from a difference in recall and corresponds to an absolute difference of less
than 10 true positive clusters on the test set. Further comparisons with
existing literature are limited by code not being available at the moment.

##  4 Conclusions

In this paper we apply, for the first time, DAG-LSTMs to the disentanglement
task; they provide a flexible architecture that allows to incorporate into the
learned neural representations the structured information which comes
alongside multi-turn dialogue. We propose thread encoding and a new set of
features to aid identification of user mentions.

There are possible directions left to explore. We modeled the reply-to
relationships in a conversation by making an assumption of conditional
independence of reply-to assignments. This is possibly a poor approximation
and it would be interesting to lift it. A challenge with this approach is the
computational complexity resulting from the large dimension of the output
space of the reply-to classifier. We notice that thread encoding allows a non-
greedy decoding strategy through beam search which would be interesting to
further explore.

## Acknowledgments

We thank the reviewers for their useful feedback. We thank Andy Liu, Camilo
Ortiz, Huayan Zhong, Philipp Meerkamp, Rakesh Gosangi, Raymond (Haimin) Zhang
for their initial collaboration. We thank Jonathan Kummerfeld for discussions.
This work was performed while Lisa interned at Bloomberg, and was later
supported by DARPA MCS Grant N66001-19-2-4031, NSF-CAREER Award 1846185, and a
NSF PhD Fellowship. The views are those of the authors and not of the funding
agencies.

## References

  * Adams and Martell (2008) P. H. Adams and C. H. Martell. 2008.  Topic Detection and Extraction in Chat.  In _2008 IEEE International Conference on Semantic Computing_ , pages 581–588.
  * Bromley et al. (1993) Jane Bromley, James W Bentz, Léon Bottou, Isabelle Guyon, Yann LeCun, Cliff Moore, Eduard Säckinger, and Roopak Shah. 1993.  Signature Verification Using a “Siamese” Time Delay Neural Network.  _International Journal of Pattern Recognition and Artificial Intelligence_ , 7(04):669–688.
  * Cho et al. (2014) Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014\.  On the Properties of Neural Machine Translation: Encoder–Decoder Approaches.  In _Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation_ , pages 103–111.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Dulceanu (2016) Andrei Dulceanu. 2016.  Recovering Implicit Thread Structure in Chat Conversations.  _Romanian Journal of Human-Computer Interaction_ , 9(3).
  * Elsner and Charniak (2008) Micha Elsner and Eugene Charniak. 2008.  You Talking to Me? a Corpus and Algorithm for Conversation Disentanglement.  _ACL-08: HLT_ , page 834.
  * Elsner and Charniak (2010) Micha Elsner and Eugene Charniak. 2010.  Disentangling Chat.  _Computational Linguistics_ , 36(3):389–409.
  * Gaoyang Guo et al. (2018) Gaoyang Guo, Chaokun Wang, Jun Chen, Pengcheng Ge, and Weijun Chen. 2018.  Who is Answering Whom? finding “Reply-To” Relations in Group Chats with Deep Bidirectional LSTM Networks.  _Cluster Computing_ , pages 1–12.
  * Gu et al. (2020) Jia-Chen Gu, Tianda Li, Quan Liu, Xiaodan Zhu, Zhen-Hua Ling, and Yu-Ping Ruan. 2020\.  Pre-Trained and Attention-Based Neural Networks for Building Noetic Task-Oriented Dialogue Systems.  In _AAAI 2020 Workshop on The Eighth Dialog System Technology Challenge_.
  * Hochreiter and Schmidhuber (1997) Sepp Hochreiter and Jürgen Schmidhuber. 1997.  Long Short-Term Memory.  _Neural computation_ , 9(8):1735–1780.
  * Jiang et al. (2018) Jyun-Yu Jiang, Francine Chen, Yan-Ying Chen, and Wei Wang. 2018.  Learning to Disentangle Interleaved Conversational Threads with a Siamese Hierarchical Network and Similarity Ranking.  In _Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)_ , pages 1812–1822.
  * Kim et al. (2019) Seokhwan Kim, Michel Galley, Chulaka Gunasekara, Sungjin Lee, Adam Atkinson, Baolin Peng, Hannes Schulz, Jianfeng Gao, Jinchao Li, Mahmoud Adada, et al. 2019\.  The Eighth Dialog System Technology Challenge.  _arXiv preprint arXiv:1911.06394_.
  * Kingma and Ba (2019) Diederik P Kingma and J Adam Ba. 2019.  A Method for Stochastic Optimization. arxiv 2014.  _arXiv preprint arXiv:1412.6980_ , 434.
  * Kummerfeld et al. (2019a) Jonathan K Kummerfeld, Sai R Gouravajhala, Joseph J Peper, Vignesh Athreya, Chulaka Gunasekara, Jatin Ganhotra, Siva Sankalp Patel, Lazaros C Polymenakos, and Walter Lasecki. 2019a.  A Large-Scale Corpus for Conversation Disentanglement.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3846–3856.
  * Kummerfeld et al. (2019b) Jonathan K. Kummerfeld, Sai R. Gouravajhala, Joseph J. Peper, Vignesh Athreya, Chulaka Gunasekara, Jatin Ganhotra, Siva Sankalp Patel, Lazaros C Polymenakos, and Walter Lasecki. 2019b.  A large-scale corpus for conversation disentanglement.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3846–3856, Florence, Italy. Association for Computational Linguistics.
  * Li et al. (2020) Tianda Li, Jia-Chen Gu, Xiaodan Zhu, Quan Liu, Zhen-Hua Ling, Zhiming Su, and Si Wei. 2020.  Dialbert: A Hierarchical Pre-Trained Model for Conversation Disentanglement.  _CoRR_ , abs/2004.03760.
  * Liu et al. (2020) Hui Liu, Zhan Shi, Jia-Chen Gu, Quan Liu, Si Wei, and Xiaodan Zhu. 2020.  End-to-End Transition-Based Online Dialogue Disentanglement.  In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20_ , pages 3868–3874. International Joint Conferences on Artificial Intelligence Organization.  Main track.
  * McNemar (1947) Quinn McNemar. 1947.  Note on the Sampling Error of the Difference between Correlated Proportions or Percentages.  _Psychometrika_ , 12(2):153–157.
  * Mehri and Carenini (2017) Shikib Mehri and Giuseppe Carenini. 2017.  Chat Disentanglement: Identifying Semantic Reply Relationships with Random Forests and Recurrent Neural Networks.  In _Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 615–623.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  Glove: Global Vectors for Word Representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Shen et al. (2006) Dou Shen, Qiang Yang, Jian-Tao Sun, and Zheng Chen. 2006.  Thread Detection in Dynamic Text Message Streams.  In _Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’06, page 35–42, New York, NY, USA. Association for Computing Machinery.
  * Tai et al. (2015a) Kai Sheng Tai, Richard Socher, and Christopher D Manning. 2015a.  Improved Semantic Representations from Tree-Structured Long Short-Term Memory Networks.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1556–1566.
  * Tai et al. (2015b) Kai Sheng Tai, Richard Socher, and Christopher D. Manning. 2015b.  Improved semantic representations from tree-structured long short-term memory networks.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 1556–1566, Beijing, China. Association for Computational Linguistics.
  * Traum et al. (2004) David R. Traum, Susan Robinson, and Jens Stephan. 2004.  Evaluation of multi-party virtual reality dialogue interaction.  In _Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC’04)_ , Lisbon, Portugal. European Language Resources Association (ELRA).
  * Vinyals et al. (2015) Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015.  Pointer Networks.  In _Advances in Neural Information Processing Systems_ , pages 2692–2700.
  * Wang et al. (2011) Hongning Wang, Chi Wang, ChengXiang Zhai, and Jiawei Han. 2011.  Learning Online Discussion Structures by Conditional Random Fields.  In _Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’11, page 435–444, New York, NY, USA. Association for Computing Machinery.
  * Wang et al. (2008) Yi-Chia Wang, Mahesh Joshi, William Cohen, and Carolyn Rosé. 2008.  Recovering Implicit Thread Structure in Newsgroup Style Conversations.  In _AAAI_.
  * Yu and Joty (2020a) Tao Yu and Shafiq Joty. 2020a.  Online Conversation Disentanglement with Pointer Networks.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6321–6330.
  * Yu and Joty (2020b) Tao Yu and Shafiq Joty. 2020b.  Online conversation disentanglement with pointer networks.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 6321–6330, Online. Association for Computational Linguistics.
  * Zhu et al. (2020) Henghui Zhu, Feng Nan, Zhiguo Wang, Ramesh Nallapati, and Bing Xiang. 2020.  Who Did They Respond To? Conversation Structure Modeling Using Masked Hierarchical Transformer.  In _Proceedings of the AAAI Conference on Artificial Intelligence_.
  * İrsoy et al. (2019) Ozan İrsoy, Rakesh Gosangi, Haimin Zhang, Mu-Hsin Wei, Peter Lund, Duccio Pappadopulo, Brendan Fahy, Neophytos Neophytou, and Camilo Ortiz. 2019.  Dialogue Act Classification in Group Chats with DAG-LSTMs.  In _SIGIR 2019 Workshop on Conversational Interaction Systems_.

ssss

##  Appendix A Appendix

###  A.1 DAG-LSTM Equations

A DAG-LSTM is a variation on the Tree-LSTM Tai et al. (2015b) architecture,
that is defined over DAGs. Given a DAG, $G$, we assume that for every vertex
$v$ of $G$, the edges $e(v,v^{\prime})$ connecting the children
$v^{\prime}\in\mathcal{C}(v)$ to $v$ can be assigned a unique label
$\ell_{v,v^{\prime}}$ from a fixed set of labels.

A pair of states vectors $(h_{v},c_{v})$ and an input $x_{v}$ are associated
to every vertex $v$. The DAG-LSTM equations define the states $(h_{v},c_{v})$,
as a function of the input $x_{v}$ and the states of its children:

$(h_{v},c_{v})={\textrm{DAG-
LSTM}}(x_{v};\\{(h_{w},c_{w})|w\in\mathcal{C}(v)\\}).$ (2)

The equations defining such functions are the following:

$\displaystyle i_{v}$ $\displaystyle=$
$\displaystyle\sigma\bigg{(}W_{ix}x_{v}+\sum_{v^{\prime}\in\mathcal{C}(v)}W^{\ell_{v,v^{\prime}}}_{ih}h_{v^{\prime}}\bigg{)}$
(3) $\displaystyle f_{vv^{\prime}}$ $\displaystyle=$
$\displaystyle\sigma\bigg{(}W_{fx}x_{v}+\sum_{v^{\prime\prime}\in\mathcal{C}(v)}W^{\ell_{v,v^{\prime}}\ell_{v,v^{\prime\prime}}}_{fh}h_{v^{\prime\prime}}\bigg{)}\phantom{xxx}$
(4) $\displaystyle c_{v}$ $\displaystyle=$ $\displaystyle i_{v}\odot
u_{v}+\max_{v^{\prime}\in\mathcal{C}(v)}f_{vv^{\prime}}\odot c_{v^{\prime}}$
(5) $\displaystyle h_{v}$ $\displaystyle=$ $\displaystyle
o_{v}\odot\tanh(c_{v})$ (6)

The equations for the $o$ and $u$ gates are the same as those for the $i$ gate
by replacing everywhere $i\to o,u$. Bias vectors are left implicit in the
definition of $i$, $f$, $o$, and $u$. $\odot$ represents Hadamard product and
max in Eq. 5 represent elementwise max operation.

A bidirectional DAG-LSTM, is just a pair of independent DAG-LSTM, one of which
is unrolled over the time reversed sequence of utterances. The output of a
bidirectional DAG-LSTM is the concatenation of the $h$ states of the forward
and backward unit for a given utterance.

###  A.2 Training and Hyperparameter Tuning

We use adjudicated training, development, and test sets from Kummerfeld et al.
(2019b). Each of these dataset is composed a set of conversation (153 in the
training set and 10 in both development and test set) each representing a
chunk of contiguous posts from the IRC #Ubuntu channel. Each of these
conversation contains strictly more than 1000 posts (exactly 1250 and 1500 for
dev and test set respectively). Annotations are available for all but the
first 1000 posts in every conversation. We apply some preprocessing to these
conversations. We chunk the annotated section of every training conversation
in contiguous chunks of 50 posts each, starting from the first annotated post.
222This may result in the last chunk to have less than 50 posts. This happens
for 45 conversations. To each of these chunks we attach a past context of 100
posts and a future context of 50, resulting in 200 utterances long chunks. For
each of these chunks we keep only those annotated links for which the response
utterance lies in the central 50 posts. We do not chunk development and test
set, but drop the first 900 post in every conversation.

The various architectures we consider share the same set of parameters to
fine-tune. One parameter $d_{h}$ controls the dimension of the hidden state of
the LSTMs and one parameter $d_{FF}$ controls the dimension of the hidden
layers of the feed-forward scorer. We use word dropout, apply dropout after
the max-affine layer, and apply dropout after activation at every layer of the
feed-forward scorer. We clip all gradient entries at 5. We use a single layer
of LSTMs and DAG-LSTMs to build the $\chi$ and $\phi,\psi$ representations and
we do not dropout any of their units. Similarly we use a single layer GRU for
the thread encoder. We list all the hyperparameters in Table 3 together with
their range and distribution used for the random search.

Hyperparameter optimization is performed by running 100 training jobs for the
base BiLSTM architecture, DAG-LSTM, and DAG-LSTM with thread encoding. Our
published results are from the best among these runs. The best sets of
parameters we find for each of these architectures are:

  * •

BiLSTM: $d_{h}=256$, $d_{FF}=128$, no word and max-affine dropout, a feed
forward-dropout equal to 0.3, and a learning rate of $2.4\times 10^{-4}$.

  * •

DAG-LSTM: $d_{h}=64$, $d_{FF}=256$, no word and max-affine dropout, a feed
forward-dropout equal to 0.3, and a learning rate of $7.3\times 10^{-4}$.

  * •

DAG-LSTM with thread encoding: $d_{h}=d_{FF}=256$, word and max-affine dropout
equal to 0.3, a feed forward-dropout equal to 0.5, and a learning rate of
$7.9\times 10^{-4}$.

User feature and mention link ablations are obtained by fixing all parameters
of the best DAG-LSTM run (removing the feature we are experimenting with) and
running 10 jobs by only changing the random seed.

Each training job is performed on a single GPU and, depending on the
architectures, takes from 6 to 12 hours.

Parameter | Domain | Distribution
---|---|---
$d_{h}$ | $\\{64,128,256\\}$ | categorical
$d_{FF}$ | $\\{64,128,256\\}$ | categorical
word dropout | $\\{0,0.3,0.5\\}$ | categorical
max-affine dropout | $\\{0,0.3,0.5\\}$ | categorical
feed-forward dropout | $\\{0,0.3,0.5\\}$ | categorical
learning rate | $[10^{-5},10^{-3}]$ | log-uniform
BiDAG-LSTM | $\\{{\textrm{true},\textrm{false}}\\}$ | categorical
Table 3:  Hyperparameters of the model architectures. During hyperparameter
optimization, we perform a random search according to the distributions
described above. Categorical distributions have uniform probability mass
function.

###  A.3 Significance Estimates

We use McNemar test McNemar (1947) to evaluate the significance of performance
differences between model. Given two models $M_{A}$ and $M_{B}$, we define
$n_{A\overline{B}}$ as the number of links correctly predicted by $A$ but not
by $B$. Under the null hypothesis both
$n_{A\overline{B}}\sim{\textrm{Bin}}(n_{A\overline{B}},n,1/2)$, where $n\equiv
n_{A\overline{B}}+n_{B\overline{A}}$. We define a model $A$ to be
_significantly_ better than a model $B$ if the null hypothesis is excluded at
95% confidence level.


# An Optimal Algorithm for Range Search on Multidimensional Points

T.Hema and K.S. Easwarakumar
Department of Computer Science & Engineering
Anna University, Chennai 600 025, INDIA Email:
<EMAIL_ADDRESS>Author.Email<EMAIL_ADDRESS>
###### Abstract

This paper proposes an efficient and novel method to address range search on
multidimensional points in $\theta(t)$ time, where $t$ is the number of points
reported in $\Re^{k}$ space. This is accomplished by introducing a new data
structure, called BITS kd-tree. This structure also supports fast updation
that takes $\theta(1)$ time for insertion and $O(\log n)$ time for deletion.
The earlier best known algorithm for this problem is $O(\log^{k}n+t)$ time [5,
15] in the pointer machine model.

Keywords: BITS kd-tree, Threaded Trie, Range Search.

##  1 Introduction

kd-trees introduced by J.L.Bentley [4, 6] are multidimensional binary search
trees commonly used for storing $k$ dimensional points. They are also used to
perform search operations such as exact match, partial match and range
queries. Range queries are mostly used in $GIS$ applications to locate cities
within a certain region in a map. Similarly, in the geometrical view of a
database, one can use orthogonal range search to perform a query. Generally,
kd-trees with $n$ nodes have a height $n$ and hence the complexity for
insertion and search are high. Although many multi-dimensional search
structures are found in the literature [2, 8, 20, 22, 23] they differ from the
standard kd-trees mainly in the space-partitioning methods used. Recall that a
$2$-d tree stores two-dimensional point data of the form $(x,y)$. A $2$-d tree
splits primarily on the $x$ coordinate of a point at even level and then on
the corresponding $y$ coordinate at the odd level, and so on. Hence, the trees
are unbalanced and are not efficient for search operations. Also, the worst
case time complexity for range search on a $2$-$d$ tree is $O(\sqrt{n}+t)$,
where $t$ is the number of points reported and for $k$ dimensions it is
$O(n^{1-1/k}+t)$[4, 16]. In general, most of the kd-tree variants get
unbalanced when the data is clustered thereby affecting query operations.

$PR$ k-d tree, Bucket $PR$ k-d tree [19], $PMR$ k-d trees [21] and Path level
compressed $PR$ k-d trees[18] are some of the trie-based kd trees used to
store point data. However, these trees are not always balanced, especially
when the data is clustered. One of the dynamic versions of k-d tree is the
divided k-d trees [25] for which the range query time is
$O(n^{1-1/k}\log^{1/k}n+t)$.

The best known dynamically balanced tree uses bitwise interlaced data [24]
over kd-trees mapping $k$ dimensions to one dimension. Although their search
time is $O(k(\log~{}n+t))$ for reporting $t$ points, bitwise interlacing leads
to discarded areas during range search. In the case of squarish kd-trees [12],
an $x$, $y$ discriminant is based on the longest side of rectangle enclosing
the problem space instead of alternating the keys. Recently, hybrid versions
of squarish kd-tree, relaxed kd-tree and median kd-trees [11] have overcome
the problem of height balancing. An amortized worst case efficiency of range
search for the hybrid squarish kd-trees, relaxed and median trees for
k-dimensional partial match queries are $1.38628~{}log_{2}n$,
$1.38629~{}log_{2}n$ and $1.25766~{}log_{2}n$ respectively. Their experimental
results match the aforementioned theoretical results, where they show that the
hybrid median trees outperform the other variants. However, as far as query
handling is concerned, these structures perform only partial match queries for
two dimensions efficiently. The most recent work in the pointer machine model
is an orthogonal range reporting data structure with $O(n(\log~{}n/\log
logn)^{d})$ space that address range queries in $O(\log~{}n(\log
n/log~{}log~{}n)$ time, where $d\geq 4$ [1].

Range trees of Bentley and Maurer [6, 5] are yet another class of balanced
binary search trees used for rectangular range search which showed improvement
in the query time of $O(\log^{k}n+t)$ over $O(n^{1-1/k}+t)$ of $k$d-trees,
where $k$ is the dimension for a set of $n$ points and $k$ is the number of
reported points. This was later improved to $O(\log^{k-1}n+t)$ using
fractional cascading in layered range trees[13] but the space requirements are
relatively high of $O(n\log^{k-1}n)$. A kd-Range $DSL$-tree performs
$k$-dimensional range search in $O(\log^{k}n+t)$ time was proposed in [15].

Recently, Chan et.al [10] have proposed two data structures for $2d$
orthogonal range search in the word $RAM$ model. The first structure takes
$O(n~{}lg~{}lg~{}n)$ space and $O(lg~{}lg~{}n)$ query time. They show improved
performance over previous results [3] of which $O(n~{}lg^{\epsilon}~{}n)$
space and $O(lg~{}lg~{}n)$ query time, or with $O(n~{}lg~{}lg~{}n)$ space and
$O(lg^{2}~{}lg~{}n)$ query time. The second data strucure is based on $O(n)$
space and answers queries in $O(lg^{\epsilon}~{}n)$ time that outperforms
previous $O(n)$ space data structure [17], answers queries in
$O(lg~{}n/lg~{}lg~{}n)$ time.

Furthermore, they also propose an efficient data structure for $3$-$d$
orthogonal range reporting with $O(n~{}{lg^{1+\epsilon}}+n)$ space and
$O(lg~{}lg~{}n+k)$ query time for points in rank space where $\epsilon>0$.
This improves their previous results [9] with $O(n~{}lg^{2}~{}n)$ space and
$O(lg~{}lg~{}n+k)$ query time, or with $O(n~{}lg^{1+\epsilon}~{}n)$ space and
$O(lg^{2}~{}lg~{}n+k)$ query time, where $k$ points are reported. Finally they
have extended range search to higher dimensions also.

Since such range queries are common among multi-dimensional queries in
database applications, we have mainly considered an orthogonal range search on
multi-dimensional points.

##  2 Our Contributions

In this work, we make use of the $BITS$-tree [14], a segment tree variant that
performs stabbing and range queries on segments efficiently in logarithmic
time. Most importantly, the distribution of the data points (uniform or
skewed) does not affect the height of the $BITS$-tree and in turn facilitates
faster search time. Here, we actually use the $BITS$-tree structure to store
points related to each dimension and thereby form a multi-level tree, called
$BITS$ kd-tree. In addition, certain nodes of the $BITS$-tree associate to a
variant of the trie data structure, called threaded trie, to facilitate
fetching a required node in constant time. Unlike k-d trees, it does not
associate co-ordinate axis, level wise, for comparison to locate or insert a
point. Instead, the tree at the first level has nodes with a key on only
distinct values of first co-ordinate of the points. Therefore, this tree
corresponds to the one dimensional data. This tree is then augmented with
another tree at second level and there in key values of the nodes associated
with distinct first two co-ordinates of the points. In general, $i^{th}$ tree
corresponds to the distinct first $i$ co-ordinates of the set of points given.
Moreover, in each tree, the inorder sequence provides the sorted sequence.
That is, $BITS$ k-d trees is a multi-level tree, and its construction is
illustrated in the subsequent sections.

###  2.1 $BITS$-Trees

Originally, the $BITS$-tree (Balanced Inorder Threaded Segment Tree) [14] is a
dynamic structure that stores segments, and also answers both stabbing and
range queries efficiently. Unlike segment trees, it also permits insertion of
segment with any interval range.

###### Definition 1

A $BITS$-tree is a height balanced two-way inorder-threaded binary tree $T$
that satisfies the following properties.

  1. 1.

Each node $v$ of $T$ is represented as $v([a,b],L)$, where $[a,b]$ is the
range associated with the node $v$, and $L$ is the list of segments containing
the range $[a,b]$, i.e if $[c,d]\in L$ then $[a,b]\subseteq[c,d]$.

  2. 2.

Given $v_{1}([a_{1},b_{1}],L_{1})\neq v_{2}([a_{2},b_{2}],L_{2})$, then

$\left[a_{1},b_{1}\right]\cap\left[a_{2},b_{2}\right]=\left\\{\begin{array}[]{lcl}\left[b_{1}\right]~{}if~{}a_{2}=b_{1}\\\
\left[b_{2}\right]~{}if~{}a_{1}=b_{2}\\\
\phi~{}~{}otherwise\end{array}\right.$

i.e ranges can either overlap only at end points or do not overlap at all.

  3. 3.

Suppose $v_{1}([a_{1},b_{1}],L_{1})$ appears before
$v_{2}([a_{2},b_{2}],L_{2})$ in the inorder sequence, then $b_{1}\leq a_{2}$.

  4. 4.

It has a special node, called $dummy$ node denoted by $D$, with range and list
as $\phi$(empty).

  5. 5.

Suppose $v_{1}([a_{1},b_{1}],L_{1})$ and $v_{n}([a_{n},b_{n}],L_{n})$ are the
first and last nodes of the inorder sequence respectively, then
$InPred(v_{1})=InSucc(v_{n})=D$, and the range, say $[a,b]$, of any node
contained in $[a_{1},b_{n}]$, i.e $[a,b]\subseteq[a_{1},b_{n}]$.

Here, the functions InPred() and InSucc() respectively returns inorder
predecessor and successor. A sample $BITS$-tree is shown in Figure 1.

Figure 1: (a) Set of segments.(b) $BITS$-Tree for the given segments.

Note that the dangling threads actually point to a dummy node, which is not
shown in the figure.

The $BITS$-tree is originally developed for storing segments, but we use this
for a different purpose of storing points. Thus, we modify this structure to
suit our requirement as described below.

  1. 1.

Each node $v([a,b],L)$ is replaced by $v(p,L^{\prime},T)$, where $p$ is a
point in $\Re^{k}$, $k\geq 1$, and $L^{\prime}$ is a pointer to the list of
collinear points in dimension $k+1$, having $p$ for the first $k$ co-
ordinates. However, this list is maintained in the tree at the next level,
which is described in section 2. Now, $T$ is either null or a pointer to a
threaded trie, which is elaborated in the next section.

  2. 2.

For any two points $p_{1}$ and $p_{2}$ stored in a tree, $p_{1}\neq p_{2}$.

  3. 3.

Suppose $v_{1}(p_{1},L_{1}^{\prime},T_{1})$ appears before
$v_{2}(p_{2},L_{2}^{\prime},T_{2})$ in the inorder sequence, then
$p_{1}<p_{2}$ as per the following definition.

###### Definition 2

Let $p_{1}=(x_{1}^{1},x_{2}^{1},\ldots x_{k}^{1})$ and
$p_{2}=(x_{1}^{2},x_{2}^{2},\ldots x_{k}^{2})$ be two points in a
$k$-dimensional space, then

  1. a.

$p_{1}=p_{2}$ implies $x_{j}^{1}=x_{j}^{2}$ for each $j$=1, 2,…k.

  2. b.

$p_{1}<(or>)p_{2}$ implies $head(p_{1},j)=head(p_{2},j)$ and $x_{j+1}^{1}$ $<$
(or >) $x_{j+1}^{2}$ for some $j$.

In the subsequent sections, for better clarity, we use hyphen($-$) for a
certain parameter of a node to denote that the particular parameter is
irrelevant with respect to the context. For instance, $(p,-,T)$ denotes that
the list contents are irrelevant for that point $p$ at this time.

###  2.2 Threaded Trie

Figure 2: A sample threaded trie

Threaded tries are variants of tries that consists of two types of nodes viz.
trie node and data node. For instance, in Figure 2, $A$, $B$ and $C$ are trie
nodes and the rest are data nodes. Unlike in tries, the trie node here does
not have a field for blank ($\not{b}$). However, each of these trie nodes
contain two segments. One is the index pointer and the other is a tag value,
which is either $0$ or $1$, where $0$ denotes the corresponding index point in
a thread and otherwise it will be $1$. Here, all null pointers are replaced by
threaded pointers, which point to the next valid node, if one exists. For
instance, the thread pointers of $1$, $2$, $3$ of node $A$ points to the node
$C$, as this is the next valid node. Similarly, thread pointers of $0$ and
$1$, in $C$ points to the data node $42$. Note here that ordering on the nodes
provides the sorted sequence. Also, data nodes appear at the same level. This
is accomplished by having uniform width for all data. For instance, the data
$8$ is treated as $08$ in Figure 2.

###  2.3 Construction of Multi-level $BITS$-Tree

Multi-level $BITS$-trees are constructed using a collection of $BITS$-trees
one at each level, and interlinking the trees of two consecutive levels in a
specified manner, which are due to the following definitions. These multi-
level $BITS$-trees are termed here as $BITS$-kd trees.

###### Definition 3

Given a point $p=(x_{1},x_{2},\ldots x_{k})$ and an integer $l\leq k$, the
head of $p$ and tail of $p$ are defined respectively as
$head(p,l)=(x_{1},x_{2},\ldots x_{l})$ and
$tail(p,l)=(x_{k-l+1},x_{k-l+2},\ldots x_{k})$. Also, having
$(head(p,l),y_{1},y_{2},\ldots y_{m})=(x_{1},x_{2},\ldots
x_{l},y_{1},y_{2},\ldots y_{m})$, leads to $(head(p,l),\\\ tail(p,k-l))=p$.

###### Definition 4

Given $S$ as the set of points in $\Re^{k}$ and $\left|S\right|$=n, the set
$S_{1}$ is defined as, $S_{1}=\bigcup_{i=1}^{n}\\{(x)~{}|~{}p\in
S~{}and~{}head(p,1)=(x)\\}$. That is, $S_{1}$ is the set of distinct $x$
values of the points in $S$. In general,
$S_{j}=\bigcup_{i=1}^{n}\left\\{(x_{1},x_{2},\ldots x_{j})~{}|~{}p\in
S\right.$ and $\left.head(p,j)=(x_{1},x_{2},\ldots x_{j})\right\\}$, where
$1\leq j\leq k$.

###### Definition 5

For a point $p=\left(x_{1},x_{2},\ldots x_{j}\right)$ in $S_{j}$, the term
$x_{j}$ is said to be the dimensional value of $p$ as the set of points in
$S_{j}$ is used to construct $j^{th}$ level $BITS$-tree.

Figure 3: A $BITS$ 2d-tree: (a) Spatial representation of points. (b)
$BITS$-2d tree for points shown in (a).

###### Definition 6

A $BITS$ kd-tree is a multi-level tree, which is constructed as follows.

  1. 1.

Create separate $BITS$ trees, $T_{j}$ for each $S_{j}$, $1\leq j\leq k$.

  2. 2.

Let $X_{j}=(x_{1},x_{2},\ldots x_{j})$. Now, for each node, say
$v_{j}=\left(X_{j},L,-\right)$, of $T_{j}$, $1\leq j<k$, the list $L$ points
to the node $v_{j+1}=((X_{j},x^{\prime}_{j+1}),-,-)~{}of~{}T_{j+1}$,
where $x_{j+1}^{\prime}=min\\{x_{j+1}~{}|~{}head(p,j)=X_{j}$ and
$(head(p,j),x_{j+1})\in S_{j+1}\\}$. We term these links as cross links, and
the node $v_{j+1}$ as a cross link node in $T_{j+1}$.

  3. 3.

In $T_{1}$, there is only one cross link node, which is the first node in the
in order sequence, and the tree pointer always points to this node.

  4. 4.

For each node $v=((X_{j-1},x_{j}^{\prime}),-,T)$ in $T_{j}$, $1\leq j\leq k$,
$T$ is pointer to the threaded tree if $v$ is a cross link node, and otherwise
$T$ is set to be null.

  5. 5.

For every cross link node $v_{j}=((X_{j-1},x_{j}^{\prime}),-,T)$ in $T_{j}$,
the data node of $T$ for a key, say $k^{\prime}$, points to the node
$((X_{j-1},k^{\prime}),-,-)$ in $T_{j}$. That is, $T$ provides links to the
nodes in $\left\\{((X_{j-1},x_{j}),-,-)|(X_{j-1},x_{j})\in S_{j}\right\\}$ and
these links are termed as trie links.

A $BITS$ 2d-tree for the sample points in Figure 3(a) is shown in Figure 3(b).
Since, $BITS$ kd-trees are multi-level trees with binary inorder threaded
search trees at each level, the height of the trees at each level is
$O(\log~{}n)$. Also, each node in $T_{i-1}$ has a cross link to a node in
$T_{i}$, which has the least value for the $i^{th}$ co-ordinate with respect
to the head value of the node in $T_{i-1}$. Note here that at least one such
point exists. This link is useful to locate a list of collinear points in the
$i^{th}$ dimension, associated with a point in $T_{i-1}$. Also, the trie links
are useful to locate a point in a given range window in constant time. The
cross link and trie links also make the structure much suitable to address
range queries efficiently.

Normally, kd-trees perform insertion by a simple comparison between the
respective co-ordinates at each level. However, deletion is tedious due to
candidate replacement. This is because, candidate for replacement can be
anywhere in the subtree. Also, it requires a little more work when the right
subtree is empty. Now, to find a candidate for replacement, it is required to
find the smallest element from the left subtree to avoid violation of the
basic rules of kd-trees and then it is required to perform a swap of left and
right subtrees, as many possible candidate keys exist in the left subtree. To
handle such a situation, we make use of a collection of $BITS$-trees, one for
each dimension. Here, deleting a point may or may not require a replacement,
but if so, it is only the inorder successor and that can be located in
$\theta(1)$ time as inorder links exist for each node. Also, the cross links
that exist between two consecutive levels, practically provide a faster search
on next level trees.

Another advantage of this structure is that when a node is pruned out at a
particular level, it need not be considered in the subsequent levels. That is,
nodes that have head values as these will be ignored in the subsequent levels.
To the best of our knowledge, there is no such structure using multi-levels of
balanced binary search trees, with two-way threads introduced in this work,
for storing point data and to perform range search efficiently.

###  2.4 $2d$-Range Search for Window Query

Given a rectangular range in the form of a window, a range query finds all
points lying within this window. Let $[x_{1}:x_{2}]~{}\times~{}[y_{1}:y_{2}]$
be a given query range. First, we use a trie stored in the first node, which
is the only cross link node, in the tree at level $1$ to find the smallest
point larger than or equal to $x_{1}$ in $S_{1}$. The non-existence of such a
point is determined from the trie itself. On the other hand, once such a point
$p$ is located, subsequent points that fall within $[x_{1}:x_{2}]$ can be
determined using the inorder threads as the inorder sequence is in sorted
order. Let us say that the reported set of points as $S^{\prime}$. However, if
the dimensional value of the point $p$ is greater than $x_{2}$, it implies
absence of required candidates.

Now, using cross links of the node in $T_{1}$, that corresponds to each point
in $S^{\prime}$, further search is performed at $T_{2}$ in a similar fashion.
Note that each cross link node in $T_{2}$ has a trie structure that supports
quick access to a node in $T_{2}$, where the dimensional value is in
$[y_{1}:y_{2}]$. In case, the dimensional value of the cross link node is
within $[y_{1}:y_{2}]$, the respective trie structure need not be looked into,
instead the inorder threads are used to find the remaining candidates.

###### Example: 1

For instance, let us consider Figure 3 with search range $[1:8]\times[5:7]$.
First, we use the only cross link node present in $T_{1}$. As its dimension
value, ie. $2$ lies within the range $[1:8]$, we do not use the respective
trie. Instead, we use the inorder threads to identify the candidate points,
which are 2,6 and 8. Now, for each of these candidates, further search is
continued respectively from $(2,2)$,$(6,2)$ and $(8,10)$ in $T_{2}$, as these
are the corresponding cross link nodes. Now, by looking at the tries of these
cross link nodes we find a point whose dimensional value is the smallest one
is $[5:7]$. Thus, tries of $(2,2)$ yields $(2,6)$, $(6,2)$ yields $(6,6)$ and
$(8,10)$ yields nothing. Further, by performing inorder traversal from $(2,6)$
and $(6,6)$, the final reported points for $Q_{1}$ are $E(2,6)$ and $C(6,6)$.
Also, for $Q_{2}$ i.e, $([5:8]\times[12:14])$, no points will be reported.

Notice that one can stop the search at $T_{1}$ without traversing $T_{2}$ if
there is no candidate node in $T_{1}$ within the given range. This is also
applicable in $k$-d trees because if there is no candidate node in the higher
tree, the lower level trees need not be searched. Thus, this structure prunes
the search in some cases and thereby practically reduces the time for
reporting a query.

###  2.5 k-d Range Search

A range search on $k$-dimensional points can be performed by extending the
search on $T_{3},T_{4},\ldots T_{k}$, similar to that of $T_{2}$ as in the
case of 2d range search. However in $T_{1}$ and $T_{2}$, we need to perform
the search as described for 2d range search. That is, when we take the query
range as
$[x_{1}:x_{1}^{\prime}]\times[x_{2}:x_{2}^{\prime}]\times\ldots[x_{k}:x_{k}^{\prime}]$,
the search is performed to find candidates within the range of
$[x_{1}:x_{1}^{\prime}]$ in $T_{1}$, $[x_{2}:x_{2}^{\prime}]$ in $T_{2}$,
$[x_{3}:x_{3}^{\prime}]$ in $T_{3}$, and so on. Finally, the points reported
from $T_{k}$ will be in $Q$. It is important to note that the search requires
comparison of keys within the given range of the particular co-ordinate
dimension in each of $T_{1},T_{2},\ldots T_{k}$. This simplifies subsequent
searches at the next level.

##  3 Implementation Details

###  3.1 Two Dimensions

Given a set of two dimensional points in $\Re^{2}$, a two-level tree
($BITS$2d-tree) is constructed in $O(n)$ time as a point may require at most
two insertions, one at $T_{1}$ and the other at $T_{2}$. But the position at
which insertion is to be made in $T_{1}$ and $T_{2}$ could be determined in
constant time as described in the proof of Lemma 5. Thus, to insert $n$ nodes
requires $O(n)$ time. Also, it may be required to create a cross link for each
node of $T_{1}$ in the case of $BITS$ 2d-tree. Since, $T_{1}$ cannot have more
than $n$ points, the number of cross links created cannot exceed $n$. Also,
the number of trie links created cannot exceed the number of nodes in $T_{1}$
and $T_{2}$, which is $O(n)$. Moreover, construction of a trie requires only
constant time as the height of the trie is constant due to fixed size of the
key. Thus, all these factors lie within $O(\log n)$ for each insertion.

Regarding space requirements in a $BITS$ 2d-tree, it is $O(n)$, as the second
tree is the one that contains all the $n$ points, and fewer or equal number of
points in the first tree. Also, the number of trie nodes is $O(n)$ as the
height of a trie is constant which is due to the size of(number of digits) of
the key. Thus, we obtain the following lemma.

###### Lemma: 1

Construction of $BITS$ 2d-tree for $n$ points requires $O(n)$ time and $O(n)$
space.

Now, searching a candidate node in $T_{1}$ is done through the trie in $T_{1}$
and that requires only constant time as the height of the trie is fixed. Once
such a point is identified, subsequent points are identified through inorder
threads. Thus. for identifying candidate points, it takes only $\theta(t_{1})$
time, if there are $t_{1}$ candidate points in $T_{1}$. Now, using cross links
of each of these nodes, we can locate the required tries in constant time and
further search is to be done in a similar fashion as described earlier. Thus,
it leads to the following lemma.

###### Lemma: 2

Range search for window query using $BITS$ 2d-tree can be addressed in
$\theta(t)$ time, where $t$ stands for the number of points reported.

###  3.2 Higher Dimensions

A straight forward extension of $BITS$ 2d-tree to $k$ dimensions is made easy
by connecting (cross links) to the corresponding nodes in the tree at next
level. Unlike range trees [7] which build another range tree at a given node
from the main tree, we maintain the trees $T_{1},T_{2},\ldots T_{k}$,
dimension-wise such that the inorder traversal provides an ordered sequence of
points stored in the tree. This definitely reduces the overall time taken for
range search across $k$ dimensions. As described in the previous section, the
time required to find a candidate point in any $T_{i}$, $1\leq i\leq k$, is
only a constant. Thus, it leads to the following lemma.

###### Lemma: 3

Let $S$ be a set of points in $k$-dimensional space, $k\geq 1$. A range search
on $BITS$ kd-tree reports all points that lie within the rectangular query
range in $\theta(t)$ time, where $t$ is the number of points reported.

###### Lemma: 4

Given a set of $n$ points, a $BITS$ kd-tree can be constructed in $O(n)$ time
and $O(n)$ space.

Proof: Since we construct $T_{1},T_{2}\ldots T_{k}$, such that $T_{k}$ at
level $k$ has at most $n$ nodes, it follows that $N\left(T_{i}\right)\leq
N\left(T_{i+1}\right)$, $1\leq i<k$ and $N(T_{k})$=$n$, where
$N\left(T_{i}\right)$ is the number of nodes in $T_{i}$. Note that levels
correspond to dimensions and hence may be used interchangeably. Also, the
number of trie nodes is $O(n)$ as its height is constant. Therefore for $k$
levels, a $BITS$ kd-tree uses $O(n)$ storage in the worst case as $k$ is a
constant. Now, construction of $BITS$ kd-tree is considered as a sequence of
insertions. Each insertion, may or may not alter $T_{i}$, $1\leq i\leq k$, a
$BITS$ tree of a particular level. However, if a $BITS$-tree $T_{j}$ is
altered, due to insertion, all trees $T_{j+1},T_{j+2},\ldots T_{k}$ will be
altered. Let $j$ be the least index such that the tree $T_{j}$ is altered.
Thus, for $T_{1},T_{2},\ldots T_{j-1}$, with trie links and cross links, one
can determine that the required values are already stored in those trees
within constant time. Now, from a particular cross link in $T_{j-1}$ followed
by a trie link in $T_{j}$, one can find a position for the new value in
$T_{j}$. This requires only constant time. Then, while inserting the value if
the tree is unbalanced, atmost one rotation is required to balance the tree.
So, for $T_{j}$ too, it requires constant time. Let $n_{j}$ be the new node
inserted in $T_{j}$. Now, by taking cross link of inorder successor of
$n_{j}$, one can determine the position of the new node in $T_{j+1}$, and that
as inorder predecessor of cross link node of inorder successor of $n_{j}$.
This new node in $T_{j+1}$ need to have a trie, which again be created in
constant time. Then, the process is to be continued for $T_{j+2}\ldots T_{k}$.
Here, updation in each $T_{i},1\leq i\leq k$, takes only constant time and
hence each insertion takes $\theta(1)$ time. So, construction of $BITS$ kd-
tree for $n$ points requires $O(n)$ time.

Table 1: Theoretical comparison of kd-trees, divided k-d trees, range trees,
k-d Range DSL-trees, layered range trees and the proposed $BITS$ kd-trees.

Description | Storage | Construction | Update | Range Search
---|---|---|---|---
kd-Trees [4] | $O(n)$ | $O(n\log n)$ | $O(\log^{k}n)$ | $O(n^{1-1/k}+t)$
Divided k-d trees [25] | $O(n)$ | $O(n\log n)$ | $O(\log^{k-1}n)$ | $O(n^{1-1/k}\log^{1/k}n+t)$
Range Trees[7] | $O(n\log^{k-1}n)$ | $O(n\log^{k-1}n)$ | $O(\log^{k}n)$ | $O(\log^{k}n+t)$
kd-Range DSL-Trees [15] | $O(n\log^{k-1}n)$ | $O(n\log^{k}n)$ | $O(n\log^{k-1}n)$ | $O(\log^{k}n+t)$
Layered Range Trees[13] | $O(n\log^{k-1}n)$ | $O(n\log^{k-1}n)$ | $O(\log^{k}n)$ | $O(\log^{k-1}n+t)$
BITS kd-Trees | $O(n)$ | $O(n)$ |  Ins. $\theta(1)$ Del. $O(\log n)$ | $\theta(t)$

$n$-number of points, $k$-dimensions, $t$-number of points reported.
---

###### Lemma: 5

Insertion and Deletion of a point in a $BITS$ kd-tree can be respectively done
in $\theta(1)$ and $O(\log n)$ time.

Proof: As per the description given in the proof of Lemma 4, insertion of a
point in BITS kd-tree takes only $\theta(1)$ time. But for deletion, finding a
node to be removed from a $BITS$-tree requires only constant time. However, if
that node is not a leaf node a cascading replacement with inorder successor is
required until reaching a leaf node to be removed physically. Certainly, the
number of such replacements to be done cannot exceed $O(\log n)$. After that
it may require a sequence of rotations on the path from the physically removed
leaf to the root, and that too in at most $O(\log n)$ rotations. So, deletion
of a point in $BITS$ kd-tree requires $O(\log n)$ time.

##  4 Performance

Table 1 summarizes the performance of kd-trees, divided k-d trees, range
trees, kd-range $DSL$-trees and the $BITS$kd- tree proposed in this work.
Furthermore, our theoretical comparison of the $BITS$ kd-tree is made with kd-
trees adapted for internal memory(pointer machine model) and not with any of
the other bulk loading kd-trees($RAM$ model). The results give an $\theta(t)$
query time using the $BITS$ kd-tree that shows a reduction in time as compared
to the existing bounds. Since we try to capitalize on the efficiency of
balanced search trees at all the levels by using cross links and trie links,
we ensure that the number of nodes visited during a range query is
considerably reduced in $BITS$ kd-tree. Observe that the storage is increased
from $O(n)$ in kd-trees to $O(n\log^{k-1}n)$ in range trees while $BITS$ kd-
tree still maintains an $O(n)$. Notice that the update time for BITSkd-tree
has been reduced considerably. To summarize, although the storage requirements
of $BITS$ kd-tree are comparable to k-d trees, divided k-d trees, the
construction and update time are improved considerably. Moreover, the overall
query time is improved to $\theta(t)$ time where $t$ is the number of points
reported as it prunes points falling outside the query region for each
dimension.

##  5 Conclusion

A $BITS$ kd-tree for storing $k$-dimensional points having update and query
operations efficiently than $kd$-trees is proposed. The main advantage of this
tree is that it effectively handles the collinear points. As a result, number
of nodes visited during search is much less compared to other kd-tree variants
that are either not height balanced or update operation is complex. In the
case of height balanced kd-trees, having better search efficiency, insertion
is tedious. A k-d range $DSL$ tree gives a logarithmic amortized worst case
search time with efficient updates mainly for partial match queries and not
for window queries. In $BITS$ kd-tree, overall insertion time is $\theta(1)$.
Moreover, points can be dynamically updated at each level. Since co-ordinate
dimensions at each level are distributed and using threaded tries, we quickly
find points falling within the query range. Also, points falling above and
below the search range are pruned efficiently using cross links to the next
level and inorder threads similar to the $BITS$-tree. In addition, threaded
tries introduced in this work link the node, having cross link, by means of
trie links to find the points within the given range in constant time.
Therefore, range search for points in a rectangular region using $BITS$ k-d
tree takes $\theta(t)$ time where $t$ is the number of points reported, and
therefore the logarithmic factor in earlier worst case bounds is reduced.
Hence it is definitely a remarkable improvement over $O(n^{1-1/k}+t)$ of kd-
trees and $O(\log^{k}n+t)$ time of k-d range $DSL$ trees.

## References

  * [1] P. Afshani, L. Arge, and K.G. Larsen.  Higher-dimensional orthogonal range reporting and rectangle stabbing in the pointer machine model.  In Proceedings of the twenty-eighth annual symposium on Computational geometry, pages 323–332. ACM, 2012.
  * [2] P. K. Agarwal.  Range searching. In J. E. Goodman and J. O’Rourke, editors, CRC Handbook of Discrete and Computational Geometry.  CRC Press, Inc, 2004.
  * [3] S. Alstrup, G. S. Brodal, and T. Rauhe.  New data structures for orthogonal range searching.  In Foundations of Computer Science, 2000. Proceedings. 41st Annual Symposium on, pages 198–207. IEEE, 2000.
  * [4] J.L. Bentley.  Multidimensional binary search tress used for associative searching.  Communications of ACM, 18(9):509–516, 1975.
  * [5] J.L. Bentley.  Decomposable search problems.  Information Processing Letters, 8(5):5–9, June 1979.
  * [6] J.L. Bentley.  Multidimensional binary search trees in database applications.  IEEE Transactions on Software Engineering, SE-5(4):333–340, 1979\.
  * [7] J.L. Bentley.  Multidimensional divide and conquer.  Communications of the ACM, 23(4):214–229, April 1980.
  * [8] M.D. Berg, O. Cheong, M.V. Kreveld, and M. Overmars.  Computational Geometry: algorithms and applications.  Springer-Verlag, New York,USA, third edition, 2008.
  * [9] T.M. Chan.  Persistent predecessor search and orthogonal point location on the word ram.  In Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’11, pages 1131–1145. SIAM, 2011.
  * [10] T.M. Chan, K.G. Larsen, and M. Pătraşcu.  Orthogonal range searching on the ram, revisited.  In Proceedings of the Twenty-seventh Annual Symposium on Computational Geometry, SoCG ’11, pages 1–10, New York, NY, USA, 2011. ACM.
  * [11] M.M.P. Crespo.  Design, Analysis and Implementation of New Variants of Kd-trees.  Master Thesis, Universitat Politecnica de Catalunya,Departament de Llenguatges i Sistemes Informatics, 2010.
  * [12] L. Devroye, J. Jabbour, and C. Zamora-Cura.  Squarish kd-trees.  SIAM Journal of Computing, 30:1678–1700, 2000.
  * [13] D.Willard.  New data structures for orthogonal queries.  Harvard University, TR:22–78, 1978.
  * [14] K.S. Easwarakumar and T. Hema.  BITS-Tree-An efficient data structure for segment storage and query processing.  International Journal of Computers and Technology, 11(10):3108–3116, December 2013.
  * [15] M.G. Lamoureux and B.G. Nicolson.  Determinisitic skip lists for k-dimensional range search.  Technical Report(TR95-098), pages 1–95, Novemeber 1995.
  * [16] D.T. Lee and C. K. Wong.  Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees.  Acta Informatica, pages 23–29, 1977.
  * [17] Y. Nekrich.  Orthogonal range searching in linear and almost-linear space.  Computational Geometry, 42(4):342–351, 2009.
  * [18] S. Nilsson and M.Tikkanen.  An experimental study of compression methods for dynamic tries.  Algorithmica, 33(1):19–33, 2002.
  * [19] J.A. Orienstein.  Multidimensional tries used for associative searching.  Information Processing Letters, 14(4):150–157, June 1982.
  * [20] F.P. Preparata and M.L. Shamos.  Computational Geometry: An Introduction.  Springer-Verlag, New York, 1985.
  * [21] R.C.Nelson and H.Samet.  A consistent hierarchical representation for vector data.  In Proceedings of the SIGGRAPH’86 Conference, Dallas, volume 20, pages 197–206, August 1986.
  * [22] H. Samet.  Fundamentals of Multi-dimensional and Metric Data Structures.  Academic Press, New York,USA, 1974.
  * [23] H. Samet.  The Design and Analysis of Spatial Data Structures.  Addison Wesley, 1990.
  * [24] H. Tropf and H.Herzog.  Multidimensional range search in dynamically balanced trees.  Applied Informatics, Vieweg Verlag,Germany, 2:71–77, 1981.
  * [25] M.J. van Kreveld and M.H. Overmars.  Divided k-d trees.  Algorithmica, 6:840–858, 1991.