{'fraction_non_alphanumeric': 0.026947764497565294, 'fraction_numerical': 0.01217352810978309, 'mean_word_length': 4.628464652756151, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Setting lower bounds on Jensen—Shannon divergence and its application to nearest neighbor document search

The Jensen—Shannon divergence provides a mechanism to determine nearest neighbours in a document collection to a speciﬁc query document. This is an eﬀective mechanism however for exhaustive search this can be a time-consuming process. In this paper, we show by setting lower bounds on the Jensen—Shannon divergence search we can reduce by up to a factor of 60% the level of calculation for exhaustive search and 98% for approximate search, based on the nearest neighbour search in a real-world document collection. In these experiments a document corpus that contains 1 854 654 articles published in New York Times from 1987-01-01 till 2007-06-19 (The New York Times Annotated Corpus) was used. As queries, 100 documents from same document corpus were selected randomly. We assess the eﬀect on performance based on the reduction in the number of log function calculations. Approximate nearest neighbour search is based on clustering of documents using Contextual Document Clustering algorithm. We perform an approximated nearest neighbour search by ﬁnding the best matching set of cluster attractors to a query and limiting the search for documents to the attractors’ corresponding clusters.

1. Introduction. Many tasks in information retrieval require searching for the most similar (nearest neighbor (NN)) document in a document corpus given a query document. As a document corpus may contain millions of terms and each document may contain only a relatively small set of terms, this problem poses particular problems in being able to identify nearest neighbor in a manner that is faster than brute-force search. Document can be represented in a number of different forms but a standard approach is based on the bag of words model, where a document can be represented as a multinomial probability distribution over words [1]. Similarity between documents can be evaluated by standard measures for comparing probability distributions such as Kullback-Leibler or Jensen-Shannon (JS) divergence, which we utilize in this case.
A main area of research in retrieving the nearest neighbor has focused on the use hierarchical decomposition of the search space (KD-tree, metric ball tree, bregman ball tree). These approaches utilize geometric properties that enable fast search by pruning out area of the search space via a branch and bound exploration. KD-trees [2] is one example of the latter approach, where the tree defines a hierarchical space partition, where each node defines an axis-aligned rectangle [3]. Metric ball trees extend the basic mechanism behind KD-trees to metric spaces by using metric balls in place of rectangles. Bregman ball trees (BB-trees) [4,5] are similar to metric ball trees however such trees can be constructed for any Bregman divergence, which is a generalized dissimilarity measure and need not support the triangular inequality. Examples of Bregman divergence measures include Kullback-Leibler. Results of experiments show that significant speed up (3 times or more) for exact neighbor search can be achieved with BB-trees, if dimension of search space is not very large (256 or less). But for higher dimensionality, space partitioning technique are still a problem in exact NN search. Such algorithms are exponential in the number of dimensions d and in case of large d the best solution is to use brute-force search [6].
As a consequence, research in this area has concentrated instead on approximate nearest neighbor. In this formulation, the algorithm is allowed to return a point whose distance from the query is at most c times the distance from the query to its nearest points, where c > 1 is called the approximation factor [7]. One of most popular approaches in this area is based on Locality Sensitive Hashing (LSH) [8,9]. The key idea behind this technique is to hash the points using several hash functions to ensure that for each function the probability of collision is much higher for objects that are close to each other than for those that are far apart. Then, one can determine near neighbors by hashing the query point and retrieving elements stored in buckets containing that point. In the case of d-dimensional Euclidean space LSH has polynomial preprocessing time and sub-linear query time [10].
The curse of dimensionality problem can be solved with randomized algorithms. In works [11,12] Dynamic Continuous Indexing (DCI) and Prioritized DCI exact NN algorithms were proposed. Instead of space partitioning, data points are projected on a number of random directions and corresponding indexes are created to store ranks of data points in each direction.
Term or feature clustering is at least as popular theme of research as document clustering in information retrieval community [13][14][15][16][17]. In this article we also use term clustering for contraction of probability distribution of words as a document representation. However our goal is less ambitious at this point -we use very simple word statistics based clustering that is specific to our task of fast NN search.
Rather than focus on alternatives to brute force search, we consider, if there are means to significantly reduce the number of calculations in finding the nearest neighbor, when documents are represented as probability distributions and the dissimilarity measure is based on JS divergence. We consider both exact nearest neighbor using brute-force search and approximate nearest neighbor search based on clustering of documents. In [18] was presented a mechanism of clustering documents based on the concept of identifying of contextual attractors to which documents are assigned to form a simple partitioning of the document space, where a cluster of documents is created for each attractor. The contextual attractors are represented as probability distributions over a maximum 1000 terms over the term space.
As candidates for contextual attractors, considered conditional probability distributions for all context terms z (z ∈ T , where T is the set of all unique terms from the document corpus) except too rare or too common terms (terms with too small or too high document frequency). Here D z stands for set of documents that contain term z and tf(x, y) denotes term frequency (number of occurrences of term y in document x).
To select final set of contextual attractors we select a set of terms Z with relatively low entropies of distributions p(y|z), z ∈ Z. Each attractor is reduced to up to 1000 most probable terms and then each document is assigned to nearest attractor (in terms of JS divergence).
It is possible to perform an approximated nearest neighbour search by finding a best matching set of attractors to a query and limiting the search for documents to the attractors' corresponding clusters. It will be shown that by determining lower bounds on the JS divergence the level of calculation can be reduced in both approaches.
2. Lower bounds on JS. JS divergence was proposed in [19]. Many interesting inequalities related to JS divergence and many other divergences can be found in [20][21][22][23]. Let A be finite alphabet, P and Q be probability distributions over A, be relative entropy. Then the JS divergence is given by where M = P +Q 2 . Let p = (p 1 , p 2 , ..., p n ) and q = (q 1 , q 2 , ..., q n ) be probability distributions. Some probabilities in both p and q can be equal to zero but The formula (1) can be rewritten as Let constants P j , Q j for j ∈ {1, ..., m} be determined by formulas Claim 1: Proof. Consider the optimization task: To take into account these conditions on p ′ i , q ′ i used Lagrange multipliers: Please note that we can use Lagrange multipliers method here because the functions in (3)-(5) are C 1 functions and the gradients of the functions in (4) and (5) and for all i ∈ A j in (6) and (7). We can assume that (8) and (9) hold because any summand in (3), where p ′ i = 0 or q ′ i = 0 is equal to zero so we can ignore such i ∈ A j . So for each i ∈ A j we have π 1 = log 2 This means, that As a consequence We compared our lower bound on JS divergence to the lower bound presented derived in [23]. This bound is one of many results of long standing research of different divergence measures [21,22].
The lower bound is given by where and total variation distance D T V is given by In section 3 we show that (2) is better than (10) in about 80% of cases, when we calculate both bounds on JS divergence calculated on (query, document) pairs, where we used up to 100 documents that are most similar to query (100 queries were randomly selected from dataset).

Applying lower bounds for calculation reduction.
Let q be a probability distribution of terms in a query and P be group of item distributions. P may be a set of document probability distributions of terms or a set of cluster attractor probability distributions of terms. The main goal is the faster selection of item from P that has the smallest distance from q in terms of JS distance. To facilitate this, we utilize lower bounds on JS distance (2) presented in previous section. This approach requires a term clustering -partitioning of all terms presented in q or in distributions from P into ⋃ m j=1 A j . Term clustering allows the contraction of the query and documents or attractors so that the terms probability values occuring in one cluster are summed.
The technique that we apply is based on document frequency (DF) term clustering algorithm that orders terms by their document frequency in the corpus. The first cluster containing the least frequent terms whereas the last cluster contains most frequent terms. The idea of splitting more popular and less popular terms is supported by our goal -to contract query and documents in such manner that this contraction preserve similarity and dissimilarity between them. If we insert popular and non-popular terms in one cluster then in contraction popular terms can hide non-popular term and this results in larger similarity that it should be. So if we cluster non-popular terms separately from popular ones then preserved dissimilarity between query and documents and this should result in a better low bound. Our experiments confirm this idea (compare this clustering approach with random clustering, where popular and non-popular terms may appear in same cluster).
Cluster sizes also depends on term frequency and its real values mostly depends on a decay parameter α and total number of terms under consideration. Based on Zipf's law we can say that approximately the probability to get a term from any of these clusters doesn't depend on cluster index and number of clusters depends on the decay parameter value.

DF based term clustering algorithm. The pseudocode of the clustering algorithm is shown below.
Data: W -set of all terms from q and P , W P -set of all terms that have positive probability in at least one probability distribution from P , W q -set of all terms that have positive probability in query q, α ∈ (0, 1) is decay parameter, β > 0 is minimum size of term cluster. Result: Term clusters W = A 1 ∪ ... ∪ A m . // Partitioning of terms that occur in P :

Algorithm 1: Term clustering
Depending on the nature of the query some of the generated clusters may be empty.

Nearest neighbor algorithm utilising lower bounds on JS divergence.
We consider two variants of nearest neighbor search algorithm: • Brute-force search. In this variant we calculate distance between query and all documents from a corpus and return document that is in shortest distance from the query. • Cluster-based search. In this variant we are seeking an approximate solution. Given a set of document clusters we: -calculate distances between query and attractors of each cluster and select few attractors that are in shortest distance from the query, -return document from clusters correspondent to selected attractors that is in shortest distance from the query. Given a probability distribution q and a set of probability distributions P we wish to find p NN = arg min p∈P JS(q, p).
As a group P , we either use set of probability distributions that represent all documents from a document corpus in brute force search algorithm or set of all documents from a document cluster in cluster-based search algorithm or set of probability distributions that represent all cluster attractors in cluster-based search algorithm. In total this corpus contains 1 142 689 unique terms (stems of non-stop words). Each context is represented by probability distribution over up to 1000 terms. In total all contexts contain 154 010 unique terms.
As queries we selected randomly 100 documents from same document corpus. Queries are run as is -there is no dependency on any pre-compute data structure so the execution of queries is the same as if the query was based on a document outside the corpus. We assess the effect on performance based on the reduction in the number of log function calculations The investigation focused brute force search and utilize these results. We want to compare standard brute force search and brute force search with low bounds and select optimal parameter values for term clustering algorithm to maximize reduction of log function calculations.
Our term clustering algorithm uses two parameters α and β. In all experiments parameter β has fixed value equal to 200, but for α we tested some different values. Table 1 shows how average (over 100 queries) reduction of log function calculation in brute force search with low bounds comparing to brute force search without low bounds depends on α. We considered cluster-based search with and without lower bounds. Maximum reductions is achieved, when α = 0.5 in DF based term clustering algorithm. Also used random term clustering with equal sizes of clusters to compare it with DF based term clustering, to show that mechanism of DF based clustering is more effective. We want to demonstrate that if mix frequent and non-frequent terms in same cluster (random clustering), then reduction of log function calculations will be smaller in comparison to DF based clustering that split frequent and infrequent terms.
In cluster based search need to generate two sets of term clusters. First of all needed to cluster unique terms that occur in cluster attractors (contexts). In total we have 154 010 such terms, which are clustered in 11 clusters by DF based clustering algorithm with α = 0.5. These clusters are used in best clusters selection step. Then in the second step we need to find nearest document in each of the selected best clusters. Here we use clusters of all unique terms that occur in documents (stop words were removed and Porter stemming was used). In total we have 984 341 such terms that were clustered into 14 clusters by DF based term clustering algorithm with α = 0.5. All clusters generated by DF based clustering have different sizes with largest cluster of rare or low frequency terms and smallest cluster of most popular or highest frequency terms. In random clusters experiments generated clusters of equal sizes with terms randomly assigned to clusters. Numbers of clusters were same as in DF term based clustering -11 clusters for terms from attractors and 14 clusters for documents terms. Table 2 shows results (averaged over 100 queries) of cluster-based search (up to 10 best clusters were selected for each query) for 3 variants: -cluster-based search without use of low bounds; -cluster-based search with low bounds, where DF based term clustering was used; -cluster-based search with low bounds, where random term clustering was used. For each variant we show reduction of log function calculations compared to brute force search and the accuracy. Accuracy is the percentage of queries for which most similar document returned by brute force search is also returned by cluster-based search. This result depends on the number of selected best clusters and increases with it. Average reduction of log function calculations is calculated comparing to number of this function calculations in brute force search. Accuracy shows percentage of queries, where clusterbased search returns same result as brute force search. From the presented results we can see that in cluster based search we can achieve 0.83 accuracy, if select up to 10 best clusters. Cluster-based search with lower bounds based on DF based term clustering outperform significantly cluster based search without low bounds. In the case of 10 best clusters selection the number of log function calculations with low bounds on average is times smaller in terms of the number of log function calculations. We compared the lower bound method (2) to lower bound (10). For each of 100 queries (documents randomly selected from NYT dataset) calculated JS divergence, and the respective bounds between the query and all other documents from NYT. Then select top X nearest neighbors (in terms of JS divergence) and calculated percentage of cases, when the bound (2) is closer to the actual JS divergence (larger) than bound (10). In Figure we present results averaged over 100 queries for X in between 1 and 100. Figure. Percentage of cases when bound (2) is better than (10) X-axis shows number of top nearest neighbors used in comparison of two bounds. Y -axis shows percentage of cases, when our bound is better. 4. Conclusions. In this paper, by determining lower bounds on JS divergence, we can significantly reduce the number of calculations to determine the nearest neighbours both in brute force and approximate search. As JS divergence is utilize in a number of different mechanisms such as distributional similarity [20] or bioinformatics [24] our findings may have application to a number of different problem areas. Our low bound on JS divergence depends on query and this means that we need to use effective algorithm for on-line generation of contracted version of large number of probability distributions. In future are planning to develop an efficient data structure for this task.