On approaches to accelerate object search in information processing tasks

The paper provides a detailed examination of the concept of the enumeration process. It is performed with objects x, which are elements of a certain set Х. The purpose of enumeration is to execute a certain active operation y = f(x) on the elements being processed. This operation can, of course, be applied to every element, but in the vast majority of practical tasks, the operation is applied only to those elements that satisfy a specific enumeration condition P(x). The simplest method of enumeration is exhaustive search or "brute-force". In this approach, every single element of the set Х is checked against the condition P(x), and depending on the result, the operation y = f(x) is executed. It is evident that exhaustive search serves as a benchmark process in the sense that it is convenient to evaluate the efficiency of various fast enumeration algorithms in comparison to it. Fast (or restricted) enumeration algorithms are advisable to use in most practical cases, provided that exhaustive search does not take an insignificant amount of time, such as fractions of a second. However, in some cases, it is reasonable to optimize (limit) the enumeration process even when execution times are very short, particularly if such short enumeration processes are repeated multiple times per unit of time, ultimately accumulating into a significantly large total runtime. The branch and bound method is the most well-known algorithm for restricted enumeration, allowing the process to progressively advance from one variant to another while discarding entire sets of elements that are known in advance not to satisfy the condition P(x). However, this method does not allow for reliable preliminary estimates of the efficiency of traversing the entire tree of corresponding elements, and its applicability to a particular problem only becomes evident during the enumeration process. This paper proposes a restriction method based on representing the enumeration condition P(x) in conjunctive or disjunctive normal form, followed by verifying this condition using a scheme of reduced logical computations that utilize only one of the conditions. Additionally, it is proposed to precompute certain supplementary information that allows obtaining the final result more quickly during enumeration. Such information may include the classification (clustering) of all objects being enumerated and performing the enumeration only within clusters, thereby reducing the total number of elements to be processed. The proposed approach is explained in detail through an example of solving a relevant problem in the field of computer graphics, specifically the search for all regular n-angles (demonstrated using equilateral triangles) within a set of N points in three-dimensional space, where each point is defined by its coordinates. A verbal description of the exhaustive search necessary for solving this problem is provided, along with a detailed explanation of the restricted enumeration algorithm constructed according to the proposed scheme (reduced computations using conjunctive normal form and preliminary clustering of all objects being enumerated, or more precisely, clustering of the associated information – distances between all pairs of points). The paper presents numerical calculations that allow for a theoretical assessment of the efficiency of the proposed solution. It has been established that, under the assumption of a perfectly uniform distribution of all enumerated objects across K classes, a significant reduction in the number of distance comparison operations occurs when searching for equilateral triangles. Specifically, for K = 50, the theoretical speedup reaches up to three times. This acceleration has been practically examined using a model software implementation written in C#, demonstrating that the actual speedup is quite close to the theoretical maximum, confirming that the proposed approach is indeed effective.