{'fraction_non_alphanumeric': 0.03305426770287849, 'fraction_numerical': 0.008538741202761749, 'mean_word_length': 4.64101599247413, 'pattern_counts': {'":': 0, '<': 1, '<?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': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Efficient Search for Data with Numerical and Categorical Attributes Based on Dual Locality-Sensitive Hashing

Similarity search problems are prevalent across a number of domains, including information retrieval, contentbased image retrieval, computer vision, bioinformatics, and computational linguistics1. Similarity computation between a data object and a query is usually simple, but it becomes burdensome when the volume of data is large. Several indexing and hashing techniques have been proposed in response to computation time concerns1-4. The indexing techniques organize the data set into a structure, usually tree-based, in order to minimize the number of computations for locating specific data. They are efficient for relatively low-dimensional spaces, but they usually deteriorate to almost an exhaustive search for high-dimensional spaces. Hashing is a technique to determine the location of data with a simple computation, although there are chances to have collisions which require extra computations5. When the data set is large and its dimension is high, the traditional indexing and hashing techniques lose their effectiveness6-9. Moreover, when similarity-based or approximate search is needed, indexing or hashing techniques that support nearest neighbor search are required. Similarity search is difficult for data having both numerical and categorical attributes because there are no widely accepted similarity or distance measures for them as yet1. We may encounter large volumes of such data in many application domains. To address the similarity search problem for such data sets, we propose a localitysensitive hashing-based search method. The proposed method expresses a query with a fuzzy Abstract


Introduction
Similarity search problems are prevalent across a number of domains, including information retrieval, contentbased image retrieval, computer vision, bioinformatics, and computational linguistics 1 . Similarity computation between a data object and a query is usually simple, but it becomes burdensome when the volume of data is large. Several indexing and hashing techniques have been proposed in response to computation time concerns [1][2][3][4] . The indexing techniques organize the data set into a structure, usually tree-based, in order to minimize the number of computations for locating specific data. They are efficient for relatively low-dimensional spaces, but they usually deteriorate to almost an exhaustive search for high-dimensional spaces. Hashing is a technique to determine the location of data with a simple computation, although there are chances to have collisions which require extra computations 5 . When the data set is large and its dimension is high, the traditional indexing and hashing techniques lose their effectiveness [6][7][8][9] . Moreover, when similarity-based or approximate search is needed, indexing or hashing techniques that support nearest neighbor search are required.
Similarity search is difficult for data having both numerical and categorical attributes because there are no widely accepted similarity or distance measures for them as yet 1 . We may encounter large volumes of such data in many application domains. To address the similarity search problem for such data sets, we propose a localitysensitive hashing-based search method.
The proposed method expresses a query with a fuzzy ball for numerical space and a conjunction of ground or general terms for categorical domains. It exploits a dual locality-sensitive hashing technique that constructs separate locality-sensitive hashing tables for the numerical and categorical spaces. It determines the buckets for a query by considering the relative distances of the numerical part of the query to the subspace boundaries and using concept hierarchies for the categorical attributes. When the number of data objects to be considered is large, it may use a Bloom filter 10 to select the candidate data set to be examined from among the buckets. The remainder of the paper is organized as follows: Section 2 presents related work, and Section 3 introduces the proposed search method for large volumes of data in high-dimensional data space. Section 4 shows some experimental results of the proposed method, and, finally, Section 5 draws conclusions.

Similarity Search
The similarity search problem is closely related to the nearest neighbor search problem, which seeks the data point closest to a query. In the database literature, a point query P(q) is used to find the data point x that meets its conditions from the data set X 1 . P(q) = {x | d(q,x) = 0 for x ∈ X}, (1) where d(q,x) indicates the distance between q and x. A range query RQ(q,r) specifies the data objects that are located within a distance r from a query point q: RQ(q,r) = {x | d(q,x) ≤ r for x ∈ X }.
(2) As another alternative, the nearest neighbor NN(q) search for a query point q seeks the data point closest to the query without requiring an exact match or specifying an exact distance: (3) In the k-nearest neighbor search problem, the top k nearest data points kNN(q,k) are searched with respect to a query point q: kNN(q,k) = {x ∈ A | A ⊆ X, |A| = k, d(q,x) ≤ d(q,y), for all y ∈ X -A}.
(4) While the range query finds all data points located within the given distance r from the query point, the k-nearest neighbor search is concerned with finding only the top k nearest ones.
Fuzzy queries are specified using membership functions 5 , which express qualitative or linguistic terms in a quantitative manner. One form of fuzzy query is shown by Eq. (5), in which μ q (x) denotes a membership function to measure the extent to which data point x satisfies the constraint imposed by query q and the minimum satisfaction degree m.
Various indexing structures have been developed to support similarity and nearest neighbor search 1,[11][12][13][14][15][16][17][18] . Most of them are based on the partitioning principle, according to which the search space is divided into subspaces and a search is performed for a similar or nearest point starting from the subspace in which the query point is located. Several tree-indexing structures have been developed, in which the space is partitioned using either spherical balls or hyperplanes. Ball partitioning methods include vantage point tree, fixed-queries tree, multi-vantage point tree, and m-tree methods, among others 1,3,4 . Some examples of generalized hyperplane partitioning methods are kdtree, generalized hyperplane tree, spatial tree, Principal Component Analysis (PCA) tree, and random projection tree 1,3,4 .
When we enter a high-dimensional space, we suffer from the curse of dimensionality [19][20][21] . This implies that as the dimensionality of data space increases, the distances among all data objects become more similar. While treestructured indexing techniques work quite well in lowerdimensional space, in high-dimensional space they do not always do better than a brute-force linear search. To deal with high-dimensional data spaces in similarity searches, hash-based techniques called locality-sensitive hashing have been developed 9,11 .

Locality-Sensitive Hashing
Hash-based indexing techniques usually focus on mapping an even distribution of keys over the buckets, and the major concern is to quickly locate data given their keys 5 . A new class of hash techniques called Locality-Sensitive Hashing (LSH) has been developed for approximate searches. Locality-sensitive hash techniques implement hash functions that map similar keys to the same bucket and different keys to different buckets with high probability.
The notion of locality-sensitive hashing was first proposed by Indyk and Motwani 9 and is defined as follows. For any two data objects p, q ∈ S, a set U of buckets, functions h ∈ H, a distance function d(p,q), probability function P H , and non-negative constants r 1 , r 2 ∈ [0,∞) (r 1 < r 2 ) and P 1 , P 2 ∈ (0,1] such that P 1 > P 2 , an LSH family H = {h | S→U} is a family of functions such that the following conditions are satisfied: If d(p,q) ≤ r 1 , then P H (h(p) = h(q)) ≥ P 1 , and if d(p,q) ≥ r 2 , then P H (h(p) = h(q)) ≤ P 2 .
(6) The functions satisfying the above properties are called (r 1 , r 2 , P 1 , P 2 )-sensitive 13 . Most LSH methods encode data into short binary strings for hash codes; data objects with the same hash code have a high probability of being similar to each other. Various LSH methods have been developed for approximate similarity search 9,11,12,[17][18][19] . Most of them use multiple functions to construct hash codes, each function producing a single bit that is later concatenated with other bits to form a binary string.
A wide array of LSH methods have been developed for numerical data sets [16][17][18] . The projection-based method is an LSH method that uses several randomly selected projection vectors that define hyperplanes 9 , each of which takes the role of a hash function, producing a binary value. The boost similarity-sensitive hashing method uses a machine learning-based LSH technique that applies AdaBoost 20 to both the sampled similar pairs and the dissimilar pairs of data 15 . The Restricted Boltzmann Machine (RBM)-based LSH method trains a stacked RBM with multiple layers, the upper layers gradually having smaller numbers of nodes 16 . The density-sensitive hashing method chooses the separating hyperplanes by first finding the clusters using the k-means algorithm 21 and then searching for the median planes to separate adjacent groups in such a way as to produce the highest entropy score 17 . These numerical LHS methods have been proved to be practical and successful in various similarity search applications such as image retrieval 18 .
Although many data sets have categorical attributes, these do not usually provide any natural information regarding distances between values. Lee and Lee 22 proposed an LSH method for categorical data that uses data-driven distance measures to create a similarity matrix for the attribute values and then groups the categorical values into disjoint groups using hierarchical clustering based on the similarity matrix 23,24 . After that, mapping functions are defined to project the attribute values into disjoint group identifiers; these are combined to build an LSH function that encompasses all the categorical attributes. Although the categorical LSH method is a meaningful approach, it is restrictive in that the hash codes can be rather long when there are many categorical attributes each of which produces its own hash bits.
Many data sets contain both numerical and categorical attributes simultaneously. To deal with such data in an LSH manner, the dual hash technique was proposed, which uses both numerical LSH and categorical LSH techniques for the corresponding attributes 21 . It maintains two sets of hash tables, one for numerical attributes and the other for categorical ones.

Bloom Filter
The Bloom filter is a technique to filter streaming data so that elements belonging to a particular key set S pass through and others are ignored 9 . It consists of an array B of n bits, initially set to 0, and a set of hash functions h 1 , h 2 , …, h k . The range of each hash function is from 1 to n, corresponding to the bit position of the array. To add a key K to S, the filter applies it to k hash functions to get k array positions and sets the bits at all these positions to 1.
To check whether a key K is in S, the algorithm determines the array positions by applying the key to the hash functions, and it judges that the key is in S only when all bits at the corresponding positions are 1.
A Bloom filter never fails to detect data having keys that belongs to the key set S; however, there is a chance that incorrect data will also be passed. The probability of a false positive is , where the size of the key set S is m, the array has n bits, and k hash functions are used.

Fuzzy Theory
Fuzzy sets and their degrees of membership provide a useful tool for expressing vague or uncertain collections and quantities in numeric form 25 . In particular, they allow us to convert qualitative linguistic terms such as "small" or "about 12" into quantitative values.
When membership functions are defined on numerical domains, they are usually specified using special unimodal forms like triangular, trapezoidal, or Gaussian fuzzy numbers 5 . While these fuzzy numbers are easily defined on a single numerical domain, we are concerned with multi-or high-dimensional numerical domains. To help deal with fuzzily quantified numerical subspaces, we define the notion of a fuzzy ball as follows: A fuzzy ball FB(c, μ) is a ball-shaped membership function centered at point c, at which point the membership degree is the largest and gradually decreases as it goes away from c. Figure 1 shows a fuzzy ball and its membership function defined with respect to the distance from its center. Concept hierarchies are sometimes defined for categorical attributes to describe the conceptual hierarchy among the categorical terms, where parent nodes indicate terms of greater generality than that of their children. When the terms represent categories, some terms may have partial membership with multiple general terms. Such concept hierarchies can be extended to fuzzy conceptual hierarchies, in which the edges are weighted with the membership degree with which the child term belongs to its parent term. Figure 2 shows a fuzzy concept hierarchy regarding software.

The Proposed Method
The overall architecture of the proposed method is shown in Figure 3. The data set to be searched is assumed to contain both numerical and categorical attributes. For flexible query representation, the method supports fuzzy queries by incorporating fuzzy balls and generalized categorical terms along with the threshold for the degree of matching. For the efficient handling of large volumes of numerical and categorical data, a dual LSH technique is employed, with both numerical LSH and categorical LSH modules. The numerical LSH module hashes data into its own buckets based on the numerical part of the data, and the categorical LHS module likewise maintains its own buckets with respect to the categorical part of the data.
To support fuzzy query and efficient bucket management, the proposed method develops an improved bucket selection strategy for numerical buckets and introduces a new categorical LSH technique. For a given fuzzy query, the LSH functions determine the buckets from both the numerical and categorical bucket sets in which similar data are to be searched. The intersection of the data in the selected numerical buckets with those in the selected categorical buckets comprises the candidate data set to be examined. To reduce execution time when the volume of data is large, a Bloom filter can optionally be used to perform the intersection. The candidate set is now examined to compute the degree to which each data object satisfies the fuzzy query. Only those data objects having a degree of satisfaction greater than the threshold are returned as the query result.

Fuzzy Query Expression
To deal with high-dimensional numerical attributes, fuzzy balls are allowed as fuzzy constraints, which are defined as a unimodal membership function centered at a point in the numerical attribute space. The constraints on categorical attributes are selectively enforced; hence, the user might not care about the values some attributes have. A Fuzzy Query FQ for similarity search is described by specifying a fuzzy ball on the numerical attribute space and fuzzy constraints on some categorical attributes, as follows: Here (l 1 , …, l p ) denotes the center of the fuzzy ball, LT is a linguistic term expressing the proximity, θ is the threshold for the degree of satisfaction necessary for a match, and C jk = t k represents the condition that categorical attribute C jk should be comparable with term t k , which can be either a ground term or a general term. The ground terms refer to the categorical values that appear in the data set. In a query, not all categorical attributes need to have a condition statement.

Locality-Sensitive Hashing for Categorical Attributes with Selective Query Support
Categorical hashing for categorical attributes is conducted using the following strategy: If a (fuzzy) concept hierarchy is given for an attribute, it is used to determine its constituent code for the hash function. Otherwise, the hierarchical tree for the attribute is constructed using a data-driven distance matrix as in the method of Lee and Lee 26 . To balance the bucket size, a randomly sampled subset of the data set is used. For the samples, we count the occurrences of distinct categorical values for each attribute. In the concept hierarchies, a concept node may have multiple parent nodes. Once the value occurrence counts are obtained, the leaf nodes are tagged with the corresponding counts. The occurrence count of each internal node is the sum of the occurrence counts of the internal node's child nodes. The categorical LSH method partitions the value set of categorical attributes into the number of partitions given by its pre-assigned resolution.
For this purpose, we sort the nodes in increasing order of their occurrence count and compute the expected average count by dividing the number of samples by the attribute resolution. Choosing partitions in a greedy manner, we start with the node having the count closest to the expected average and continue choosing nodes one by one so that the set of the chosen partitions covers the whole set of leaf nodes in a balanced manner.
The following procedure, Partition-Cat-Space(S, C, r, TR), partitions the categorical value set of a categorical attribute C into the set P of r subsets using sample data set S and concept hierarchy TR: procedure Partition-Cat-Space(S, C, r, TR) input: sample data set S, attribute C, resolution r, concept hierarchy for pnd ∈ an(nd) In the above procedure, Count-Occurrence(C, e, S) is the procedure to count the occurrences of value e for attribute C in data set S. Propagate-Occurrence-Count(TR) propagates occurrence counts upward from leaf nodes in a concept hierarchy whose leaf nodes are tagged with their occurrence counts.
procedure Propagate-Occurrence-Count(TR) input: concept hierarchy TR with leaf nodes having their occurrence counts output: concept hierarchy TR with all nodes having their occurrence counts begin for nd ∈ IN(TR) oc(nd) = 0 Split-Even(R, TR) splits the set R into two subsets R 1 and R 2 for which the sums of their occurrence counts are approximately balanced. procedure Split-Even(R, TR) input: a set R of nodes, concept hierarchy TR output: two subsets R 1 , R 2 such that R = R 1 ∪ R 2 begin

ad = Least-Common-Ancestor(R, TR) STR(SV,SE) = Get-Sub-Hierarchy(TR, ad, R) bc = Σ nd∈R oc(nd)/2 nd = argmin nd∈SV {|oc(nd) -
Least-Common-Ancestor(R, TR) is the procedure that finds a least common ancestor of nodes in R of the concept hierarchy TR.  Find(HM, nd) retrieves the pair of the node and its value that has nd as a key from the hash map HM.
Get-Sub-Hierarchy(TR, ad, R) produces a subgraph STR(SV,SE) of TR, which contains all the nodes and edges from node ad to leaf nodes in R as follows: SV = ad ∪ de(ad) SE = {(na,nb) | na,nb ∈ SV, (na,nb) ∈ E} Once a categorical space is partitioned by Partition-Cat-Space, a binary code is assigned to each partition using Assign-Binary-Codes. Assign-Binary-Codes(P, r) takes as input r sets of nodes, each of which is a partition, and assigns a unique binary code of length log 2 r to each partition; hence, terms belonging to the same partition have the same binary code. procedure Assign-Binary-Codes(P, r) input: a partition set P of nodes, resolution r output: a code table CT = {(v, code)} begin len = log 2 r CT = ∅ code = binary string for value 0 of length len for vS ∈ P for nd ∈ vS CT = CT ∪ {(lb(nd), code)} code = code + 1 end. Figure 4 shows how categorical attribute values are partitioned and how unique binary codes are assigned to ground terms. In the figure, the sample size is 48 and the resolution is set to 4; hence, the average count in a partition is 12. The partitions are therefore formed by Partition-Cat-Space to have about 12 counts. The partitions thus determined are {g 1 , g 2 }, {g 6 , g 7 }, {g 5 , g 7 }, and {g 3 }. Each partition is then assigned a unique binary code of length 2 by the procedure Assign-Binary-Codes.
In the above procedure, Get-Code(CT i , v k (C i )) is a procedure to return the binary code for attribute C i in data D k using the code table for C i , and "||" denotes the concatenation of the binary strings on either side.
The categorical attribute part of a query is not always expressed in ground terms; it may contain general terms of internal nodes in the concept hierarchies. To generate query codes, the nodes of concept hierarchies are labeled with binary string(s) by propagating the leaf node labels upward and keeping the newly arrived labels in the nodes. For the categorical part of the query (C j1 = t 1 , …, C jr = t r ), its code can be obtained by finding the categorical codes of the attributes and combining them. Generate-Cat-Query-Code(CTS, C) does this by producing a set of binary codes for the categorical part C of the query by using the code table set CTS, which contains the associations of terms and component codes. procedure Generate-Cat-Query-Code(CTS, C) input: code table set CTS = {CT 1 , …, CT q }, categorical query part C = (C j1 = t 1 , …, C jr = t r ) output: a set CCD of binary codes begin Cat-Code-Combination(CD) generates all possible binary codes using the allowed code segments for each categorical attribute. procedure Cat-Code-Combination(CD) input: a set CD = {CD 1 , CD 2 , …, CD q } of binary codes for attributes output: a set CCD of binary codes begin The codes generated from Code-for-Categorical-Domain and Generate-Cat-Query-Code could be too long to be used as hash codes when the number of categorical attributes and their values are large. To deal with this situation, a hash function h c (x) can optionally be used, which maps binary strings to shorter hash codes. Suppose that there are three concept hierarchies and they are assigned component codes for the three categorical attributes C 1 , C 2 , and C 3 , as shown in Figure 5. When the categorical part of a query is given as (C 1 = g 3 , C 2 = i 2 , C 3 = i 5 ), the procedure Generate-Cat-Query-Code generates the following query codes: 100110, 100111, 101010, and 101011.

Locality-Sensitive Hashing for Numerical Attributes Using Fuzzy Ball Queries
A fuzzy ball indicates a cluster on a numerical data space, centered at a point, for which membership to the cluster decreases as distance from the center increases. To locate data points within a fuzzy ball, a locality-sensitive hashing technique is used, employing the approach proposed by Lee 22 in which the extended boundary LSH allows the fuzzy balls centered near a space partitioning boundary to retrieve the data points within their influence by enforcing extension bounds.

Code-for-Numerical-Domain
In the above procedure, ds(h i , NV(D)) is a function to compute the distance from point NV(D), corresponding to the numerical part of data object D, to hyperplane h i . It results in either positive or negative distance depending on which side of the hyperplane the data object is located.  Figure 6 shows a code assignment for three data points D 1 , D 2 , and D 3 with respect to two partitioning hyperplanes h 1 and h 2 . A hyperplane partitions the space into two separate subspaces, and assigns 1 to one side and 0 to the other. The hyperplanes have extension bounds that cover the narrow band of width 2δ. A data point within an extension bound is treated as being on both sides of its hyperplane. The two hyperplanes map the data points into binary codes of length 2 as follows: D 1 is mapped into 10, D 2 into 10 and 11, and D 3 into 11. Hash

Categorical Bucket Selection for Queries
When a query Q is given, its categorical part CV(Q) is extracted. Then, its binary map is determined using Codefor-Categorical-Domain (CTS, CV(Q)). When the system uses a rehash function h c , the hash function is applied to the codes thus obtained, to get the identifiers of the buckets.

Numerical Bucket Selection for Queries
A fuzzy ball for the numerical part is described with a center for the ball and a membership function. The LHS for the numerical domain is constructed with a set H of hyperplanes. From the membership function and the minimum degree of satisfaction specified in the query, we can determine the maximum allowed distance d m from the center of the ball to the data. In order to determine the buckets to be examined, we compute the distances ds(c i , h j ) of the center c i to each hyperplane h j . When the distance is farther than the maximum allowed distance d m plus the extension bound δ, i.e., ds(c i , h j ) > d m + δ, the neighboring bucket to the hyperplane should be simultaneously examined.
In the above procedure, max-allowed-distance(LT, θ ) computes the distance at which the membership degree for LT is θ. Toggle-position(cs1, i) copies cs1 and flips its i-th position from 1 to 0 or vice versa.
Query-Code-for-cDomain(NV(D), H) computes the binary code for the bucket(s) to which the numerical attribute part of data object D is mapped.

Candidate Data Set Selection
When a query is initiated, the candidate data sets to be examined are efficiently determined by selecting proper LSH buckets. The numerical part of the query is used to determine the target bucket(s) NB of the numerical LSH; the categorical part is used to determine the target bucket(s) CB of the categorical LSH. The data set belonging to their intersection NB ∩ CB becomes the candidate data set for thorough examination. For an efficient intersection operation, the Bloom filter can be used, which never fails to miss the true candidate.

Similarity Examination between Query and Candidates
The similarity is computed for the numerical and categorical parts separately. For the numerical part, the distance between the data point and the center of the fuzzy ball is computed, and its membership degree to the fuzzy ball is then determined. When the membership degree is less than the threshold specified in the query, the data point is ignored. For a data point that meets the constraints for the numerical part, the satisfaction degree for the categorical part of the query is evaluated. When a fuzzy concept hierarchy is given, the degree of satisfaction for a categorical value to a general term is set to be the minimum of the weights on the path from the general term to the categorical value.

Experimental Results
To show the effectiveness of the proposed method, we performed some experiments using synthetic data.
Two locality-sensitive hashing settings were implemented: The first setting (Set I) used 10 hyperplanes to realize a hyperplane-based LSH for the numerical space and a 10-bit categorical LSH, and the second setting (Set II) used 15 hyperplanes for the numerical space LHS and a 15-bit categorical LSH. The hyperplanes for LSH were also randomly generated, and the extension bound was set to 0.3. The rehash functions of the categorical LSH were defined as a mapping function that performs a permutation of the bit string and then applies the modulo to the output bit size.
In the experiments, we evaluated the performance characteristics using the following measures: the portions of the data set to be examined as the candidate when only the numerical LSH was used, when only the categorical LSH was used, and when both LSHs were used (Tables 1  and 2); and the average number of numerical buckets to be examined in each experimental setting (Table 3).    Table 1 implies that as the more the number of buckets increase, the smaller portion of the data set is examined at the expense of storage overhead for bucket management. The results shown in Table 2 indicate that the dual LSH method is more efficient than either numerical LSH or categorical LSH method in the perspective to the number of examined data at the final stage. Table 3 shows that additional numerical buckets are examined depending on the threshold of the degree of satisfaction, and as the hash code length increases, the bucket size decreases and hence more additional buckets are examined.

Conclusions
Similarity search and nearest neighbor search are wellknown fundamental operations in various data processing tasks. Large volumes of high-dimensional data spaces having both numerical and categorical attributes are now available in many application domains. To support approximate but fast search for such data, we have proposed a new LSH technique based on the dual LSH approach.
We believe this work presents the following contributions: First, it introduces a flexible query scheme for data having both numerical and categorical attributes by defining the notion of fuzzy balls and incorporating fuzzy concept hierarchies in categorical attributes to support the queries with general categorical terms. Second, a new categorical LSH technique is introduced that incorporates concept hierarchies and generates reduced-length hash codes by applying an additional rehash. Third, the proposed method optionally employs the Bloom filter to reduce the time to compute the intersection of buckets from both numerical and categorical LSHs for large volumes of data.
From the experimental studies, we observe that the proposed method shows the desired and expected behaviors: The proposed dual LSH outperforms both the numerical LSH and the categorical LSH in the perspective of the number of examined data objects for finding similar data. This study considers only the fuzzy balls for the entire numerical space, and there yet remains to develop an LSH method to handle fuzzy balls defined on a numerical subspace.