Searching a database for objects that are most similar to a query object is a fundamental task in many database application domains, for example data mining, knowledge discovery, information extraction, and machine learning [1].
In [2] we described BitPart as a mechanism suitable for performing exact metric search in "high(er)" dimensions. While we did not define "high(er)", the evidence in the paper shows that it gives its best relative performance for spaces with dimensionality of between 10 and 30. BitPart's space cost is linear with respect to the size of the data, but the actual space required for each object may be small as log 2 𝑛 bits, which allows representations of very large data sets to fit in main memory. Potentially the time cost still scales with 𝑂(log 𝑛) time. Together these attributes give exact search which outperforms indexing structures as dimensionality increases within a certain range 1 . The BitPart mechanism uses a set of binary partitions defined over the finite data set, where each partition is represented by a bitmap. If the total set of bitmaps is perfectly balanced and perfectly orthogonal, then the probability of a selection of 𝑘 bitmaps being able to exclude an arbitrary element of the data is 1− 1 2 𝑘 , and the expected number of non-excluded values becomes very small if 𝑘 ≈ log 2 𝑛. While we can come close to achieving this for low-dimensional data, this becomes increasingly challenging as dimensionality increases.
In [2] two issues are noted as requiring further investigation. The first is how to select appropriate pivots in order to find orthogonal exclusion partitions. The second is the interaction between partition balance and the efficacy of exclusion; this is the subject of this article.
To do this we introduce the notion of exclusion power, and show its application to some generated data sets across different dimensions. Exclusion power provides the ability to: fundamentally understand the exclusions that are possible in different datasets, to understand when one approach will outperform another and, to tune the BitPart algorithm to optimally accommodate data sets of different dimensions.
The novel contribution of this article is the quantification of exclusion power, which can be measured for a given binary partition structure with respect to a balancing factor 𝜏 . We observe that, in low dimensions, partitions are best balanced evenly, approximately splitting the search space into two equal parts. In higher dimensions however such balanced partitions perform very badly, and highly skewed partitions have much greater power. We are not aware of any previous work which attempts to quantify this effect, although it is well known within the "folklore" of metric search researchers.
Formally we are interested in searching a (large) finite set of objects 𝑆 which is a subset of an infinite set 𝑈 , where (𝑈, 𝑑) is a metric space [1]. The general requirement is to efficiently find members of 𝑆 which are similar to an arbitrary member of 𝑈 given as a query, where the distance function 𝑑 gives the only way by which any two objects may be compared. The simplest type of similarity query is the range search query: for some threshold 𝑡, based on a query 𝑞 ∈ 𝑈 , the solution set is 𝒬(𝑞, 𝑡) = {𝑠 ∈ 𝑆| 𝑑(𝑞, 𝑠) ≤ 𝑡}.
The essence of metric search is to spend time pre-processing the finite set 𝑆 (i.e., indexing it) so that solutions to queries can be efficiently calculated. In all cases distances between members of 𝑆 and selected reference objects (pivot) are calculated during pre-processing. At query time the relative distances between the query and the same pivot objects can be used to make deductions about which data values may, or may not, be candidate solutions to the query.
Many metric indexes employ binary partitions of the space 𝑈 , i.e., partitions of the form 𝒫 = {𝒫 0 , 𝒫 1 } where 𝒫 0 ∪ 𝒫 1 = 𝑈 and 𝒫 0 ∩ 𝒫 1 = ∅. In the context of metric search, binary partitions are defined by partition rules that typically rely on computing the distance 𝑑 of the data objects to a set of pivots. Notable examples include ball and sheet partitioning (see, e.g., Figure 1). A ball partition is defined by a pivot 𝑝 ∈ 𝑈 and a covering radius 𝜏 ∈ R + , so that
A sheet partition is defined by two pivots 𝑝 1 , 𝑝 0 ∈ 𝑈 so that the boundary of the partition regions is the hyperplane equidistant from the two reference objects:
Informally we refer to 𝒫 0 as "outside" and 𝒫 1 as "inside". Under certain circumstances it is possible to deduce that, for a given query, one of the subsets of the partition cannot (or conversely must) contain solutions to the query. Typically, the triangle inequality and the distances to the pivots are exploited to determine bounds on distances between data objects (distance constraints), which are used at query time for excluding certain regions from the searching process.
The exclusion of a region of a partition occurs when the query ball does not intersect the partition boundary. For a ball region, the condition for non-intersection of the query ball and the boundary is
For a sheet region, the non-intersection condition is
If the respective non-intersection condition occurs, the implication is that any possible solution to the query lies on one or other side of the partition boundary, and therefore either 𝒫 0 or 𝒫 1 may be excluded from the search for solutions.
The core of the technique is to define a large set of binary partitions over the original space; the data is stored as a set of bitmaps according to containment with these regions. At query time, the query is assessed against this containment information, but without reference to the original data representation.
For each region, one of three possible conditions may be determined: (a) the solution set 𝒬(𝑞, 𝑡) must be fully contained in the region, or (b) there is no intersection between the region and the solution set, or (c) neither of these is the case. In either case (a) or (b), the containment information stored may be useful with respect to solving the query, and is used as part of the query computation. In case (c) however the containment information is of no value, and is not accessed as a part of the computation. This approach maximises the effectiveness of memory used for calculation against the original data representation: the amount of memory required depends on the cardinality of the original data, but not on the size of its individual objects.
An Example. Figure 2 shows a simple example within the 2D plane, comprising four reference objects 𝑝 1 to 𝑝 4 and a set of six regions defined by them. The regions are respectively: 𝒜 1 , the area to the left of the line between 𝑝 1 and 𝑝 2 ; ℬ 1 , the area above the line between 𝑝 1 and 𝑝 3 ; and the areas within the variously sized circles drawn around each 𝑝 1 to 𝑝 4 , labeled 𝒞 1 , 𝒟 1 , ℰ 1 and ℱ 1 respectively. Note that each regional boundary defines a binary partition of the total space of the form 𝒫 = {𝒫 1 , 𝒫 0 }, where 𝒫 0 = 𝑈 ∖ 𝒫 1 . Thus in Figure 2, six binary partitions
For each partition 𝒫 we generate a bitmap of 𝑛 bits, where 𝑛 is the number of data points, which stores the logical containment information of each data object 𝑠 𝑖 , that is 1 if 𝑠 𝑖 ∈ 𝒫 1 and 0 if 𝑠 𝑖 / ∈ 𝒫 1 (Figure 2c). Thus a bit being set (to 1) corresponds to that object being in the region and a member of 𝑃 1 .
Figure 2a also shows a range query 𝑞 drawn with a threshold 𝑡. It can be seen that all solutions to this query must lie within the area highlighted in Figure 2b. The circle around the query intersects with two regional boundaries (𝒜 1 and ℰ 1 ), and so no information is available with respect to these; however it is completely contained within two of the defined regions (ℬ 1 and 𝒟 1 ), and fails to intersect with the final two (𝒞 1 and ℱ 1 ). Such containment and intersection is derivable only from the measurement of distances between the query and the reference objects, the definition of the regions, and the search radius. Here for example the possible solution area shown is determined using only the four distance calculations 𝑑(𝑞, 𝑝 1 ).. 𝑑(𝑞, 𝑝 4 ). It can be seen that the only possible solutions to the query are those which match on all non-intersecting fields; in this case, the objects 𝑠 1 , 𝑠 5 and 𝑠 6 depicted in Figure 2. This is equivalent to the Conjunctive Normal Form (CNF) expression ℬ ∧ ¬𝒞 ∧ 𝒟 ∧ ¬ℱ. This expression covers the set of all possible solutions to the query and hints at how the data can be stored using bit vectors.
Before describing the query algorithm, we describe the data structures used and how they are initialised. A set of enumerated pivots 𝑝 1 to 𝑝 𝑚 is selected from 𝑆. We define a set of binary partitions within 𝑈 , each of the form 𝒫 = {𝒫 0 , 𝒫 1 }, defined using the distance function 𝑑. There may be many more regions than reference objects; for example a set of 𝑚 reference objects defines at least (︀ 𝑚
)︀ sheet regions, plus 𝑚 ball regions. We now define the notion of an exclusion zone (EZ) as a containment map of 𝑆 based on a given partition; this is the information we will use at query time to perform exclusions and derive a candidate set of solutions. We impose an ordering on 𝑆, then for each 𝑠 𝑖 map whether it is a member of the region 𝒫 1 or otherwise. This logical containment information is best stored in a bitmap of 𝑛 bits, where 𝑛 = |𝑆|. One such exclusion zone is generated per partition.
The query process comprises three distinct phases:
Phase 1 in which the query is checked against the regional definitions, and the two types of regions with non-intersecting boundaries are identified. Initially, the distance from the query 𝑞 to each pivot 𝑝 𝑖 is measured. For each partition, it can be established if the query ball intersects with the boundary of the partition. If there is no intersection, any solution to the query must lie on one or other side of the partition's boundary, so the exclusion zone is brought into the query calculation in one of two sets depending on whether the query solutions are fully contained within 𝒫 1 or 𝒫 0 . We name these sets of bitmaps 𝐵 1 and 𝐵 0 , which are carried forwards to the computation in Phase 2.
Phase 2 in which the regions identified are used to conduct a series of logical operations, thus identifying a set of candidate solutions for the query.
The second phase comprises the manipulation of the bitmaps deriving from the first phase to identify a set of candidate solutions. This may be efficiently achieved by a series of bitwise operations over these bitmaps 2 . It can be seen now that any solution is guaranteed to be identifiable from the bitmap deriving from the bitwise calculation:
Phase 3 in which the candidate solutions are checked against the original data set to identify the exact solution to the query. This requires a sequential scan of the single bitmap resulting from Phase 2 and checking the data corresponding to any remaining set bits using the original space and distance metric in order to produce an exact solution to the query.
To unify our treatment of different kinds of binary partitions with their associated distance constraints, we introduce the concept of a binary partition characterised by a single partition function 𝑓 : 𝑈 → R and a balancing factor 𝜏 ∈ R with the following properties: • if 𝑓 (𝑞) ≤ 𝜏 − 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫 1 and 𝒫 0 can be excluded • if 𝑓 (𝑞) > 𝜏 + 𝑡 then 𝒬(𝑞, 𝑡) ⊂ 𝒫 0 and 𝒫 1 can be excluded Note that different functions 𝑓 may be used to determine the same regions 𝒫 0 , 𝒫 1 but with different distance lower-bounds, and thus different exclusion rules. For example, let's consider the Euclidean space (R 𝑛 , ℓ 2 ), 𝜏 = 0, 𝑓 1 (𝑠) = 𝑑(𝑠,𝑝 1 )−𝑑(𝑠,𝑝 0 ) 2 and 𝑓 2 (𝑠) = 𝑑(𝑠,𝑝 1 ) 2 −𝑑(𝑠,𝑝 0 ) 2 2𝑑(𝑝 1 ,𝑝 0 ) for two fixed pivot 𝑝 1 and 𝑝 0 . Both the functions 𝑓 1 and 𝑓 2 produce the same sheet partitioning, i.e., 𝒫 1 = {𝑠 ∈ R 𝑛 |𝑑(𝑠, 𝑝 1 ) ≤ 𝑑(𝑠, 𝑝 0 )} and 𝒫 0 = {𝑠 ∈ R 𝑛 |𝑑(𝑠, 𝑝 1 ) > 𝑑(𝑠, 𝑝 0 )}. However, in [7] we proved that the exclusion rule determined by 𝑓 1 (Hyperbolic exclusion) is weaker than the one determined by 𝑓 2 (Hilbert Exclusion), and the latter is valid only on the large class of Supermetric Spaces [8].
In the following we show how general ball partitioning and sheet partitioning can be described within this formalism. Sheet Partitions Sheet partitions are defined with respect to two reference points 𝑝 1 and 𝑝 0 . Usually, a simple binary partition is defined according to whichever of 𝑝 1 and 𝑝 0 is the nearer value with respect to the metric 𝑑. However it has been noted [9,10] that such partitions may also be subject to a balancing factor 𝛼, so that
In this case, we can use 𝑓 (𝑠) = (𝑑(𝑠, 𝑝 1 ) − 𝑑(𝑠, 𝑝 0 ))/2 which gives property 1 above for the constant 𝜏 = 𝛼/2. Moreover from the triangle inequality of the space we have that 𝑑(𝑠, 𝑝 1 ) ≤ 𝑑(𝑠, 𝑠 ′ ) + 𝑑(𝑠 ′ , 𝑝 1 ) and 𝑑(𝑠 ′ , 𝑝 0 ) ≤ 𝑑(𝑠, 𝑠 ′ ) + 𝑑(𝑠, 𝑝 0 ) for any 𝑠, 𝑠 ′ ∈ 𝑈 , which gives 𝑑(𝑠, 𝑠 ′ ) ≥ 𝑑(𝑠,𝑝 1 )−𝑑(𝑠,𝑝 0 )−𝑑(𝑠 ′ ,𝑝 1 )+𝑑(𝑠 ′ ,𝑝 0 ) 2 = 𝑓 (𝑠) − 𝑓 (𝑠 ′ ). By symmetry, we also have 𝑑(𝑠, 𝑠 ′ ) > 𝑓 (𝑠 ′ ) − 𝑓 (𝑠), therefore 𝑑(𝑠, 𝑠 ′ ) > |𝑓 (𝑠) − 𝑓 (𝑠 ′ )|.
Like ball partitions, the balance of the partition is affected by selecting different values for 𝜏 .
The exclusion power of a partition gives a quantification of the effectiveness of that partition with respect to a given metric search task. It is clear that this is likely to be quite different depending on the partition type, the selection of reference objects, and the chosen value 𝜏 . The meaning of exclusion power is based on the probability, for arbitrarily selected objects 𝑞 and 𝑠, and a distance 𝑡, of being able to demonstrate that 𝑑(𝑞, 𝑠) > 𝑡. As we will show, for low dimensional spaces the maximum exclusion power of any partition structure is likely to coincide with a value of 𝜏 which causes the partition to bisect the finite search space 𝑆, i.e. |𝒫 0 | ≈ |𝒫 1 |. However as we will see, in higher dimensional spaces this may be a very bad choice.
For a range query 𝒬(𝑞, 𝑡) we define the exclusion power of the partition 𝒫 = {𝒫 0 , 𝒫 1 } as the probability of excluding one generic element 𝑠 on the basis only of the data partition to which it belongs:
The exact calculation of the probabilities 𝑃 (𝒬(𝑞, 𝑡) ⊂ 𝒫 𝑖 ), for 𝑖 = 0 or 1, is not straightforward for a general binary partition in a metric space, however, if we know that the partition can be characterised by a function 𝑓 and a balancing factor 𝜏 , we can estimate a lower-bound of these probabilities 3 and thus obtain an approximation of the exclusion power as
Let CDF(𝑥) be the cumulative distribution function of 𝑓 (𝑠) for 𝑠 ∈ 𝑆 then the exclusion power can be expressed as
where 𝜏 is the partition balancing factor and 𝑡 in the query distance threshold Estimates of exclusion power can be made with respect to a representative sample of the data set, and indeed of the query set if that is different 4 . A large enough sample will give a good estimate of the probability of an individual datum falling within each of the subsets.
To understand the effect of different values of 𝜏 an exclusion power graph may be constructed which is plotted across the range of 𝜏 for a fixed value of 𝑡. This allows the optimum value of 𝜏 to be deduced for a range query with threshold 𝑡.
We illustrate the construction of power graphs for 5 dimensional data in Section 5.1 and for 20 dimensional data in 5.2. Figure 3 shows histograms of two sets of sampled distances from a randomly generated five-dimensional Euclidean space. The left-hand side of the figure shows the distribution of 5,000 witness points in terms of distance from a randomly selected pivot point, 𝑝. The right-hand side shows the distribution of the 5NN (fifth nearest-neighbour) distances for a set of 1,000 queries; this distance representing a query threshold necessary to return a small proportion of the data, and thus useful values for 𝑡.
Based on this information, we will pick example values of 𝜏 ^= 0.89 and 𝑡 ^= 0.19, being the median values in the distributions of 𝜏 and 𝑡 values, respectively. We can now consider the exclusion power of these values applied to the partition thus formed, centered around 𝑝.
The left-hand side of Figure 4 shows the Cumulative Probability Density function (CDF) with the X-axis values of 𝜏 ^, 𝜏 ^− 𝑡 ^, and 𝜏 ^+ 𝑡 ^highlighted. Given that 𝜏 ^has been selected as the median distance from 𝑝, the value of the CDF at 𝜏 ^is 0.5. Therefore if an exclusion occurs, half of the data set will be excluded and its exclusion power is:
The more general form of this equation (i.e., Equation 7) hints how the exclusion power can be displayed for a single partition, as shown on the right-hand side of Figure 4. Here, for a fixed value of 𝑡 (again 0.19), the power of the partition is calculated over the whole range of distances that have been measured between the witness points and the point 𝑝. As can be seen, the maximum power is achieved when the partition is split at the median distance, i.e. 𝜏 ^= 0.89 in this example. With this partition, and this value of 𝜏 , the probability of excluding an arbitrary datum for an arbitrary query is around 0.21. left-hand side of Figure 5 shows a histogram of 5,000 distances measured with respect to randomly selected element 𝑝 of a 20-dimensional uniformly generated Euclidean space. The right-hand side shows a histogram (for 1,000 queries selected from the same set) of the distances to the 5th-nearest neighbour with respect to this same set of 5,000 values. Figure 6 shows the same information in the form of cumulative probability density functions. The left-hand side of Figure 6 shows the CDF function superimposed with a line corresponding to the medium value for 𝜏 . The value of t for this data is 1.07.
Finally, although we have no space here to provide in-depth analysis, Figure 7 shows exclusion power graphs using sheet partitions over both 5D and 20D spaces. It can be seen that the graph patterns are quite similar. As can be seen in Figure 6 such a value is unlikely to result in any successful exclusions. These diagrams explain behaviour observed by many researchers into metric search that choosing unbalanced indexing structures often works better for higher dimensional data. The establishment of a unified partition interface using 𝑓 and 𝜏 allows similar graphs to be produced for sheet partitions (e.g., Figure 7). The mechanistic value of these graphs is that the value or values of 𝜏 corresponding to the maxiumum power can be automatically extracted on a per-partition basis, and used in an implementation of BitPart. In the case of low dimensional data a single offset can be used for each ball where as for high(er) dimensional data two offsets can be used. Furthermore, as described earlier a particular implementation can use as few or as many exclusion zones that as necessary, as may be predicted by the power value at the optimum value.
In Section 6 these offsets are applied to a BitPart implementation to demonstrate their effect. In order to validate the above results we ran experiments against a BitPart implementation5 using uniformly generated data in 5 and 20 dimensions with Euclidean distance. Each contained one million data points, and 1000 queries were executed. In all experiments fixed threshold distances 𝑡 were used and set to values which correspond to one-millionth of the data volume. In order to measure exclusion power, the 1000 queries were run 25 times for differing values of 𝜏 for both sheet and ball partitions. The 5D data uses 20 pivot points and the 20D data 100.
In [2] we described how a selection of 𝑚 reference points allows for (︀ 𝑚
)︀ sheet and 𝑚 ball partitions to be produced. After the above analysis, we used this number for the 5D space, but in the 20D space we generated twice that number, corresponding to the twin peaks in the power graphs. Note that this does not require any extra distance calculations at query time, as the number of reference points is not increased. Furthermore there is not necessarily any increase in memory usage, as partitions are typically stored in secondary memory and only fetched when the query ball does not intersect with the partition, which requires only the evaluation of the 𝑓 function to determine. For each experiment a suitable range is calculated for 𝜏 for both balls and sheets, ensuring that for all partitions both 𝒫 0 and 𝒫 1 are non-empty, and the whole calculation was executed with different values of 𝜏 across this range.
Results are shown in Figure 8. In order to visualize these results, the number of residual (i.e. Phase 3) distance calculations per query was measured, this number giving a good proxy for the value of the exclusion mechanism. The plots show the inverse of these counts. Peaks similar to those shown in the power graphs in Figures 4 and 6 can be seen in these experimental results.
In this paper, we have reiterated the design of the BitPart indexing and query mechanisms. The novel contribution of this paper is an exposition of how dimensionality effects the efficacy of this and other metric search mechanisms. We have demonstrated how the distribution of distances changes with the dimensionality of the data and how in turn this affects the ability to perform effective exclusions and thus efficient queries. In particular we have explored the notion of balance and how that affects exclusion. To do this we have introduced the notion of exclusion power, and shown its application to some Euclidean data sets in different dimensions.
This analysis gives fundamental insights into what data can be queried effectively and what cannot. Furthermore it demonstrates how index and search algorithms can be tuned to compensate for data sets of arbitrary dimensions.
We have demonstrated that the phenomena explored in mathematical terms are manifested in synthetically generated data sets and queries over them using an implementation of BitPart. We believe that the results in this paper may be applied to other metric search and indexing mechanisms. Our future plans include investigating these phenomena in real life data sets and exploring the outstanding issue of partition orthogonality.