Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest (or most similar) to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values. Formally, the nearest neighbor (NN) search problem is defined as follows: given a set S of points in a space M and a query point q ∈ M {\displaystyle q\in M} , find the closest point in S to q. Donald Knuth in volume 3 of The Art of Computer Programming (1973) called it the post-office problem, referring to an application of assigning to a residence the nearest post office. A direct generalization of this problem is a k-NN search, where we need to find the k closest points. Most commonly M is a metric space and dissimilarity is expressed as a distance metric, which is symmetric and satisfies the triangle inequality. Even more common, M is taken to be the d-dimensional vector space where dissimilarity is measured using the Euclidean distance, Manhattan distance or other distance metric. However, the dissimilarity function can be arbitrary. One example is asymmetric Bregman divergence, for which the triangle inequality does not hold. == Applications == The nearest neighbor search problem arises in numerous fields of application, including: Pattern recognition – in particular for optical character recognition Statistical classification – see k-nearest neighbor algorithm Computer vision – for point cloud registration Computational geometry – see Closest pair of points problem Cryptanalysis – for lattice problem Databases – e.g. content-based image retrieval Coding theory – see maximum likelihood decoding Semantic search Vector databases, where nearest-neighbor lookup over embeddings is used to retrieve semantically similar records Retrieval-augmented generation systems, where nearest-neighbor retrieval over embeddings is used to fetch candidate passages or documents before generation Data compression – see MPEG-2 standard Robotic sensing Recommendation systems, e.g. see Collaborative filtering Internet marketing – see contextual advertising and behavioral targeting DNA sequencing Spell checking – suggesting correct spelling Plagiarism detection Similarity scores for predicting career paths of professional athletes. Cluster analysis – assignment of a set of observations into subsets (called clusters) so that observations in the same cluster are similar in some sense, usually based on Euclidean distance Chemical similarity Sampling-based motion planning == Methods == Various solutions to the NNS problem have been proposed. The quality and usefulness of the algorithms are determined by the time complexity of queries as well as the space complexity of any search data structures that must be maintained. The informal observation usually referred to as the curse of dimensionality states that there is no general-purpose exact solution for NNS in high-dimensional Euclidean space using polynomial preprocessing and polylogarithmic search time. === Exact methods === ==== Linear search ==== The simplest solution to the NNS problem is to compute the distance from the query point to every other point in the database, keeping track of the "best so far". This algorithm, sometimes referred to as the naive approach, has a running time of O(dN), where N is the cardinality of S and d is the dimensionality of S. There are no search data structures to maintain, so the linear search has no space complexity beyond the storage of the database. Naive search can, on average, outperform space partitioning approaches on higher dimensional spaces. The absolute distance is not required for distance comparison, only the relative distance. In geometric coordinate systems the distance calculation can be sped up considerably by omitting the square root calculation from the distance calculation between two coordinates. The distance comparison will still yield identical results. ==== Space partitioning ==== Since the 1970s, the branch and bound methodology has been applied to the problem. In the case of Euclidean space, this approach encompasses spatial index or spatial access methods. Several space-partitioning methods have been developed for solving the NNS problem. Perhaps the simplest is the k-d tree, which iteratively bisects the search space into two regions containing half of the points of the parent region. Queries are performed via traversal of the tree from the root to a leaf by evaluating the query point at each split. Depending on the distance specified in the query, neighboring branches that might contain hits may also need to be evaluated. For constant dimension query time, average complexity is O(log N) in the case of randomly distributed points, worst case complexity is O(kN^(1-1/k)) Alternatively the R-tree data structure was designed to support nearest neighbor search in dynamic context, as it has efficient algorithms for insertions and deletions such as the R tree. R-trees can yield nearest neighbors not only for Euclidean distance, but can also be used with other distances. In the case of general metric space, the branch-and-bound approach is known as the metric tree approach. Particular examples include vp-tree and BK-tree methods. Using a set of points taken from a 3-dimensional space and put into a BSP tree, and given a query point taken from the same space, a possible solution to the problem of finding the nearest point-cloud point to the query point is given in the following description of an algorithm. (Strictly speaking, no such point may exist, because it may not be unique. But in practice, usually we only care about finding any one of the subset of all point-cloud points that exist at the shortest distance to a given query point.) The idea is, for each branching of the tree, guess that the closest point in the cloud resides in the half-space containing the query point. This may not be the case, but it is a good heuristic. After having recursively gone through all the trouble of solving the problem for the guessed half-space, now compare the distance returned by this result with the shortest distance from the query point to the partitioning plane. This latter distance is that between the query point and the closest possible point that could exist in the half-space not searched. If this distance is greater than that returned in the earlier result, then clearly there is no need to search the other half-space. If there is such a need, then you must go through the trouble of solving the problem for the other half space, and then compare its result to the former result, and then return the proper result. The performance of this algorithm is nearer to logarithmic time than linear time when the query point is near the cloud, because as the distance between the query point and the closest point-cloud point nears zero, the algorithm needs only perform a look-up using the query point as a key to get the correct result. === Approximation methods === An approximate nearest neighbor search algorithm is allowed to return points whose distance from the query is at most c {\displaystyle c} times the distance from the query to its nearest points. The appeal of this approach is that, in many cases, an approximate nearest neighbor is almost as good as the exact one. In particular, if the distance measure accurately captures the notion of user quality, then small differences in the distance should not matter. ==== Greedy search in proximity neighborhood graphs ==== Proximity graph methods (such as navigable small world graphs and HNSW) are considered the current state-of-the-art for the approximate nearest neighbors search. The methods are based on greedy traversing in proximity neighborhood graphs G ( V , E ) {\displaystyle G(V,E)} in which every point x i ∈ S {\displaystyle x_{i}\in S} is uniquely associated with vertex v i ∈ V {\displaystyle v_{i}\in V} . The search for the nearest neighbors to a query q in the set S takes the form of searching for the vertex in the graph G ( V , E ) {\displaystyle G(V,E)} . The basic algorithm – greedy search – works as follows: search starts from an enter-point vertex v i ∈ V {\displaystyle v_{i}\in V} by computing the distances from the query q to each vertex of its neighborhood { v j : ( v i , v j ) ∈ E } {\displaystyle \{v_{j}:(v_{i},v_{j})\in E\}} , and then finds a vertex with the minimal distance value. If the distance value between the query and the selected vertex is smaller than the one between the query and the current element, then the algorithm moves to the selected vertex, and it becomes new enter-point. The algorithm stops when it reaches a local minimum: a vertex whose neighborhood does not contain a vertex that is closer to the query than the vertex itself. The idea of proximity neighborhood graphs was exploited in multiple publications, including the seminal paper by Arya and Mount, in the VoroNet syst
Thermal attack
A thermal attack (aka thermal imaging attack) is an approach that exploits heat traces to uncover the entered credentials. These attacks rely on the phenomenon of heat transfer from one object to another. During authentication, heat transfers from the users' hands to the surface they are interacting with, leaving heat traces behind that can be analyzed using thermal cameras that operate in the far-infrared spectrum. These traces can be recovered and used to reconstruct the passwords. In some cases, the attack can be successful even 30 seconds after the user has authenticated. Thermal attacks can be performed after the victim had authenticated, alleviating the need for in-situ observation attacks (e.g., shoulder surfing attacks) that can be affected by hand occlusions. While smudge attacks can reveal the order of entries of graphical passwords, such as the Android Lock Patterns, thermal attacks can reveal the order of entries even in the case of PINs or alphanumeric passwords. The reason thermal attacks leak information about the order of entry is because keys and buttons that the user touches first lose heat over time, while recently touched ones maintain the heat signature for a longer time. This results in distinguishable heat patterns that can tell the attacker which entry was entered first. Thermal attacks were shown to be effective against plastic keypads, such as the ones used to enter credit card's PINs in supermarkets and restaurants, and on handheld mobile devices such as smartphones and tablets. In their paper published at the Conference on Human Factors in Computing Systems (CHI 2017), Abdelrahman et al. showed that the attack is feasible on today's smartphones. They also proposed some ways to mitigate the attack, such as swiping randomly on the screen to distort the heat traces, or forcing maximum CPU usage for a few seconds. Thermal attacks can also infer passwords from heat traces on keyboards. Researchers at the University of Glasgow showed that attackers who use AI methods can be more effective in performing thermal attacks. Their study presents a new tool called ThermoSecure and evaluates it in two user studies. The results show that ThermoSecure can successfully attack passwords with an average accuracy of 92% to 55%, depending on the length of the password. The effectiveness of thermal attacks also depends on typing behavior and the material of the keycaps. ABS keycaps, which retain heat traces longer, are more vulnerable to thermal attacks. The study also discusses ways to protect against thermal attacks and presents seven potential mitigation approaches. Dr Khamis, who led the development of the technology with Norah Alotaibi and John Williamson, said with thermal imaging cameras more affordable than ever and machine learning becoming more accessible, it was "very likely that people around the world are developing systems along similar lines to ThermoSecure in order to steal passwords". == Thermal Attack Mitigation == === Simple and Practical Measures === One basic and effective way to mitigate thermal attacks is to deliberately create heat noise over the input interface, such as a keypad or keyboard, after entering a password. For instance, placing one's palm over the entire interface for a few seconds after use can obscure the thermal pattern left by the fingers, making it much more difficult for an unauthorized user to interpret the heat traces. === Range of Proposed Strategies === In addition to simple methods, researchers have developed a spectrum of mitigation strategies to counter thermal attacks. These strategies encompass 15 different approaches including: Use of Biometrics: Replacing traditional pin codes or passwords with biometric authentication, such as fingerprint recognition or facial recognition, eliminates the issue of residual heat on keypads. Heating the Interface: Implementing technology to slightly warm up the keypad can effectively neutralize the heat traces left by fingers, preventing thermal cameras from capturing the pattern. Randomizing Key Layouts: Employing dynamic key layouts that change positions every time the interface is used, making it impossible to correlate heat patterns with static input positions. === Technological Intervention on Thermal Cameras === Another avenue for mitigation is to address the issue at the source by modifying thermal cameras. Proposals have been made to develop thermal cameras that can automatically detect vulnerable interfaces such as keyboards or keypads. When these interfaces are detected within the camera's field of view, the camera would be programmed to prevent the user from recording images of them. This solution, however, would require widespread adoption by thermal camera manufacturers. Additionally, the approach is particularly viable for thermal cameras connected to a computing device, such as a smartphone, which can process the images in real time. Many affordable thermal cameras are standalone and do not have connectivity or processing capabilities. However, thermal cameras designed for connection to mobile devices can utilize the smartphone's processing power, making this mitigation approach feasible for such devices.
Event condition action
Event condition action (ECA) is a short-cut for referring to the structure of active rules in event-driven architecture and active database systems. Such a rule traditionally consisted of three parts: The event part specifies the signal that triggers the invocation of the rule The condition part is a logical test that, if satisfied or evaluates to true, causes the action to be carried out The action part consists of updates or invocations on the local data This structure was used by the early research in active databases which started to use the term ECA. Current state of the art ECA rule engines use many variations on rule structure. Also other features not considered by the early research is introduced, such as strategies for event selection into the event part. In a memory-based rule engine, the condition could be some tests on local data and actions could be updates to object attributes. In a database system, the condition could simply be a query to the database, with the result set (if not null) being passed to the action part for changes to the database. In either case, actions could also be calls to external programs or remote procedures. Note that for database usage, updates to the database are regarded as internal events. As a consequence, the execution of the action part of an active rule can match the event part of the same or another active rule, thus triggering it. The equivalent in a memory-based rule engine would be to invoke an external method that caused an external event to trigger another ECA rule. ECA rules can also be used in rule engines that use variants of the Rete algorithm for rule processing. == ECA rule engines == Rulecore Concurrent Rules Apart Database Detect Invocation Rules ConceptBase ECArules
Whitelist
A whitelist or allowlist is a list or register of entities that are being provided a particular privilege, service, mobility, access or recognition. Entities on the list will be accepted, approved and/or recognized. Whitelisting is the reverse of blacklisting, the practice of identifying entities that are denied, unrecognized, or ostracized. == Email whitelists == Spam filters often include the ability to "whitelist" certain sender IP addresses, email addresses or domain names to protect their email from being rejected or sent to a junk mail folder. These can be manually maintained by the user or system administrator - but can also refer to externally maintained whitelist services. === Non-commercial whitelists === Non-commercial whitelists are operated by various non-profit organizations, ISPs, and others interested in blocking spam. Rather than paying fees, the sender must pass a series of tests; for example, their email server must not be an open relay and have a static IP address. The operator of the whitelist may remove a server from the list if complaints are received. === Commercial whitelists === Commercial whitelists are a system by which an Internet service provider allows someone to bypass spam filters when sending email messages to its subscribers, in return for a pre-paid fee, either an annual or a per-message fee. A sender can then be more confident that their messages have reached recipients without being blocked, or having links or images stripped out of them, by spam filters. The purpose of commercial whitelists is to allow companies to reliably reach their customers by email. == Advertising whitelist == Many websites rely on ads as a source of revenue, but the use of ad blockers is increasingly common. Websites that detect an adblocker in use often ask for it to be disabled - or their site to be "added to the whitelist" - a standard feature of most adblockers. == Network whitelists == === LAN whitelists === A use for whitelists is in local area network (LAN) security. Many network admins set up MAC address whitelists, or a MAC address filter, to control who is allowed on their networks. This is used when encryption is not a practical solution or in tandem with encryption. However, it's sometimes ineffective because a MAC address can be faked. === IP whitelist === Firewalls can usually be configured to only allow data-traffic from/to certain (ranges of) IP-addresses. === Application whitelists === One approach in combating viruses and malware is to whitelist software which is considered safe to run, blocking all others. This is particularly attractive in a corporate environment, where there are typically already restrictions on what software is approved. Leading providers of application whitelisting technology include Bit9, Velox, McAfee, Lumension, ThreatLocker, Airlock Digital and SMAC. On Microsoft Windows, recent versions include AppLocker, which allows administrators to control which executable files are denied or allowed to execute. With AppLocker, administrators are able to create rules based on file names, publishers or file location that will allow certain files to execute. Rules can apply to individuals or groups. Policies are used to group users into different enforcement levels. For example, some users can be added to a report-only policy that will allow administrators to understand the impact before moving that user to a higher enforcement level. Linux systems typically have AppArmor and SE Linux features available which can be used to effectively block all applications which are not explicitly whitelisted, and commercial products are also available. On HP-UX introduced a feature called "HP-UX Whitelisting" on 11iv3 version. == Controversy regarding name == In 2018, a journal commentary on a report on predatory publishing was released making claims that "white" and "black" are racially charged terms that need to be avoided in instances such as "whitelist" and "blacklist". The premise of the journal is that "black" and "white" have negative and positive connotations respectively. It states that since "blacklisting" was first referred to during "the time of mass enslavement and forced deportation of Africans to work in European-held colonies in the Americas," the word is therefore related to race. There is no mention of "whitelist" and its origin or relation to race. This issue is most widely disputed in computing industries where "whitelist" and "blacklist" are prevalent (e.g. IP whitelisting). Despite the commentary nature of the journal, some companies and individuals in others have taken to replacing "whitelist" and "blacklist" with new alternatives such as "allow list" and "deny list". Those adopting this change consider using the "whitelist"/"blacklist" names as a code smell. Those that oppose these changes question its attribution to race, citing the same etymology quote that the 2018 journal uses. According to the remark, the term "blacklist" evolved from the term "black book" about a century ago. The term "black book" does not appear to have any etymology or sources that support racial associations, instead originating in the 1400s as a reference to "a list of people who had committed crimes or fallen out of favor with leaders", and popularized by King Henry VIII's literal use of a black book. Others also note the prevalence of positive and negative connotations to "white" and "black" in the Bible, predating attributions to skin tone and slavery. It wasn't until the 1960s Black Power movement that "Black" became a widespread word to refer to one's race as a person of color in America (alternate to African-American) lending itself to the argument that the negative connotation behind "black" and "blacklist" both predate attribution to race.
Hierarchical RBF
In computer graphics, hierarchical RBF is an interpolation method based on radial basis functions (RBFs). Hierarchical RBF interpolation has applications in treatment of results from a 3D scanner, terrain reconstruction, and the construction of shape models in 3D computer graphics (such as the Stanford bunny, a popular 3D model). This problem is informally named as "large scattered data point set interpolation." == Method == The steps of the interpolation method (in three dimensions) are as follows: Let the scattered points be presented as set P = { c i = ( x i , y i , z i ) | i = 1 N ⊂ R 3 } {\displaystyle \mathbf {P} =\{\mathbf {c} _{i}=(\mathbf {x} _{i},\mathbf {y} _{i},\mathbf {z} _{i})\vert _{i=1}^{N}\subset \mathbb {R} ^{3}\}} Let there exist a set of values of some function in scattered points H = { h i | i = 1 N ⊂ R } {\displaystyle \mathbf {H} =\{\mathbf {h} _{i}\vert _{i=1}^{N}\subset \mathbb {R} \}} Find a function f ( x ) {\displaystyle \mathbf {f} (\mathbf {x} )} that will meet the condition f ( x ) = 1 {\displaystyle \mathbf {f} (\mathbf {x} )=1} for points lying on the shape and f ( x ) ≠ 1 {\displaystyle \mathbf {f} (\mathbf {x} )\neq 1} for points not lying on the shape As J. C. Carr et al. showed, this function takes the form f ( x ) = ∑ i = 1 N λ i φ ( x , c i ) {\displaystyle \mathbf {f} (\mathbf {x} )=\sum _{i=1}^{N}\lambda _{i}\varphi (\mathbf {x} ,\mathbf {c} _{i})} where φ {\displaystyle \varphi } is a radial basis function and λ {\displaystyle \lambda } are the coefficients that are the solution of the following linear system of equations: [ φ ( c 1 , c 1 ) φ ( c 1 , c 2 ) . . . φ ( c 1 , c N ) φ ( c 2 , c 1 ) φ ( c 2 , c 2 ) . . . φ ( c 2 , c N ) . . . . . . . . . . . . φ ( c N , c 1 ) φ ( c N , c 2 ) . . . φ ( c N , c N ) ] ∗ [ λ 1 λ 2 . . . λ N ] = [ h 1 h 2 . . . h N ] {\displaystyle {\begin{bmatrix}\varphi (c_{1},c_{1})&\varphi (c_{1},c_{2})&...&\varphi (c_{1},c_{N})\\\varphi (c_{2},c_{1})&\varphi (c_{2},c_{2})&...&\varphi (c_{2},c_{N})\\...&...&...&...\\\varphi (c_{N},c_{1})&\varphi (c_{N},c_{2})&...&\varphi (c_{N},c_{N})\end{bmatrix}}{\begin{bmatrix}\lambda _{1}\\\lambda _{2}\\...\\\lambda _{N}\end{bmatrix}}={\begin{bmatrix}h_{1}\\h_{2}\\...\\h_{N}\end{bmatrix}}} For determination of surface, it is necessary to estimate the value of function f ( x ) {\displaystyle \mathbf {f} (\mathbf {x} )} in specific points x. A lack of such method is a considerable complication on the order of O ( n 2 ) {\displaystyle \mathbf {O} (\mathbf {n} ^{2})} to calculate RBF, solve system, and determine surface. == Other methods == Reduce interpolation centers ( O ( n 2 ) {\displaystyle \mathbf {O} (\mathbf {n} ^{2})} to calculate RBF and solve system, O ( m n ) {\displaystyle \mathbf {O} (\mathbf {m} \mathbf {n} )} to determine surface) Compactly support RBF ( O ( n log n ) {\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })} to calculate RBF, O ( n 1.2..1.5 ) {\displaystyle \mathbf {O} (\mathbf {n} ^{1.2..1.5})} to solve system, O ( m log n ) {\displaystyle \mathbf {O} (\mathbf {m} \log {\mathbf {n} })} to determine surface) FMM ( O ( n 2 ) {\displaystyle \mathbf {O} (\mathbf {n} ^{2})} to calculate RBF, O ( n log n ) {\displaystyle \mathbf {O} (\mathbf {n} \log {\mathbf {n} })} to solve system, O ( m + n log n ) {\displaystyle \mathbf {O} (\mathbf {m} +\mathbf {n} \log {\mathbf {n} })} to determine surface) == Hierarchical algorithm == A hierarchical algorithm allows for an acceleration of calculations due to decomposition of intricate problems on the great number of simple (see picture). In this case, hierarchical division of space contains points on elementary parts, and the system of small dimension solves for each. The calculation of surface in this case is taken to the hierarchical (on the basis of tree-structure) calculation of interpolant. A method for a 2D case is offered by Pouderoux J. et al. For a 3D case, a method is used in the tasks of 3D graphics by W. Qiang et al. and modified by Babkov V.
IEEE Transactions on Visualization and Computer Graphics
IEEE Transactions on Visualization and Computer Graphics is a peer-reviewed scientific journal published by the IEEE Computer Society. It covers subjects related to computer graphics and visualization techniques, systems, software, hardware, and user interface issues. TVCG has been considered the top journal in the field of visualization. Since 2011, TVCG has allowed authors to present recently accepted papers at partner conferences. These include: IEEE Visualization (VIS), including VAST, InfoVis, and SciVis. IEEE Virtual Reality Conference (IEEE VR) IEEE International Symposium on Mixed and Augmented Reality (ISMAR) ACM Symposium on Interactive 3D Graphics and Games (I3D) IEEE Pacific Visualization Conference (IEEE PacificVis) ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA) Eurographics Symposium on Geometry Processing (SGP) Pacific Graphics Conference (PG) Eurovis - The EG and VGTC Conference on Visualization Graphics Interfaces (GI)
Distinguishable interfaces
Distinguishable interfaces use computer graphic principles to automatically generate easily distinguishable appearance for computer data. Although the desktop metaphor revolutionized user interfaces, there is evidence that a spatial layout alone does little to help in locating files and other data; distinguishable appearance is also required. Studies have shown that average users have considerable difficulty finding files on their personal computers, even ones that they created the same day. Search engines do not always help, since it has been found that users often know of the existence of a file without being able to specify relevant search terms. On the contrary, people appear to incrementally search for files using some form of context. Recently researchers and web developers have argued that the problem is the lack of distinguishable appearance: in the traditional computer interface most objects and locations appear identical. This problem rarely occurs in the real world, where both objects and locations generally have easily distinguishable appearance. Discriminability was one of the recommendations in the ISO 9241-12 recommendation on presentation of information on visual displays (part of the overall report on Ergonomics of Human System Interaction), however it was assumed in that report that this would be achieved by manual design of graphical symbols. == VisualIDs, semanticons, and identicons == The mass availability of computer graphics supported the introduction of approaches that make better use of the brain's "visual hardware", by providing individual files and other abstract data with distinguishable appearance. This idea initially appeared in strictly academic VisualIDs and Semanticons works, but the web community has explored and rapidly adopted similar ideas, such as the Identicon. The VisualIDs project automatically generated icons for files or other data based on a hash of the data identifier, so the icons had no relation to the content or meaning of the data. It was argued not only that generating meaningful icons is unnecessary (their user study showed rapid learning of the arbitrary icons), but also that basing icons on content is actually incorrect ("contrasting visualization with visual identifiers"). The Semanticons project developed by Setlur et al. demonstrated an algorithm to create icons that reflect the content of files. In this work the name, location and content of a file are parsed and used to retrieve related image(s) from an image database. These are then processed using a Non-photorealistic rendering technique in order to generate graphical icons. Developer Don Park introduced the identicon library for making a visual icon from a hash of a data identifier. This initial public implementation has spawned a large number of implementations for various environments. In particular, identicons are now being used as default visual user identifiers (avatars) for several widely used systems. They are also used as a complement to Gravatars, which are pre-existing avatar images created or chosen by users, instead of automatically generated images. (see #External links). == Current research == While current web practice has followed the semantics-free approach of VisualIDs, recent research has followed the semantics-based approach of Semanticons. Examples include using data mining principles to automatically create "intelligent icons" that reflect the contents of files and creating icons for music files that reflect audio characteristics or affective content.