A display list, also called a command list in Direct3D 12 and a command buffer in Vulkan, is a series of graphics commands or instructions that are run when the list is executed. Systems that make use of display list functionality are called retained mode systems, while systems that do not are as opposed to immediate mode systems. In OpenGL, display lists are useful to redraw the same geometry or apply a set of state changes multiple times. This benefit is also used with Direct3D 12's bundle command lists. In Direct3D 12 and Vulkan, display lists are regularly used for per-frame recording and execution. == Origins in vector displays == The vector monitors or calligraphic displays of the 1960s and 1970s used electron beam deflection to draw line segments, points, and sometimes curves directly on a CRT screen. Because the image would immediately fade, it needed to be redrawn many times a second (storage tube CRTs retained the image until blanked, but they were unsuitable for interactive graphics). To refresh the display, a dedicated CPU called a Display Processor or Display Processing Unit (DPU) was used, which had a memory buffer for a "display list", "display file", or "display program" containing line segment coordinates and other information. Advanced Display Processors also supported control flow instructions, which were useful for drawing repetitive graphics such as text, and some could perform coordinate transformations such as 3D projection. == Home computer display list functionality == One of the earliest systems with a true display list was the Atari 8-bit computers. The display list (actually called so in Atari terminology) is a series of instructions for ANTIC, the video co-processor used in these machines. This program, stored in the computer's memory and executed by ANTIC in real-time, can specify blank lines, any of six text modes and eight graphics modes, which sections of the screen can be horizontally or vertically fine-scrolled, and trigger Display List Interrupts (called raster interrupts or HBI on other systems). The Amstrad PCW family contains a Display List function called the 'Roller RAM'. This is a 512-byte RAM area consisting of 256 16-bit pointers in RAM, one for each line of the 720 × 256 pixel display. Each pointer identifies the location of 90 bytes of monochrome pixels that hold the line's 720 pixel states. The 90 bytes of 8 pixel states are spaced at 8-byte intervals, so there are 7 unused bytes between each byte of pixel data. This suits how the text-orientated PCW constructs a typical screen buffer in RAM, where the first character's 8 rows are stored in the first 8 bytes, the second character's rows in the next 8 bytes, and so on. The Roller RAM was implemented to speed up display scrolling as it would have been unacceptably slow for its 3.4 MHz Z80 to move up the 23 KB display buffer 'by hand' i.e. in software. The Roller RAM starting entry used at the beginning of a screen refresh is controlled by a Z80-writable I/O register. Therefore, the screen can be scrolled simply by changing this I/O register. Another system using a Display List-like feature in hardware is the Amiga, which, not coincidentally, was also designed by some of the same people who developed the custom hardware for the Atari 8-bit computers. Once directed to produce a display mode, it would continue to do so automatically for every following scan line. The computer also included a dedicated co-processor, called "Copper", which ran a simple program or 'Copper List' intended for modifying hardware registers in sync with the display. The Copper List instructions could direct the Copper to wait for the display to reach a specific position on the screen, and then change the contents of hardware registers. In effect, it was a processor dedicated to servicing raster interrupts. The Copper was used by Workbench to mix multiple display modes (multiple resolutions and color palettes on the monitor at the same time), and by numerous programs to create rainbow and gradient effects on the screen. The Amiga Copper was also capable of reconfiguring the sprite engine mid-frame, with only one scanline of delay. This allowed the Amiga to draw more than its 8 hardware sprites, so long as the additional sprites did not share scanlines (or the one scanline gap) with more than 7 other sprites. i.e., so long as at least one sprite had finished drawing, another sprite could be added below it on the screen. Additionally, the later 32-bit AGA chipset allowed the drawing of bigger sprites (more pixels per row) while retaining the same multiplexing. The Amiga also had dedicated block-shifter ("blitter") hardware, which could draw larger objects into a framebuffer. This was often used in place of, or in addition to, sprites. In more primitive systems, the results of a display list can be simulated, though at the cost of CPU-intensive writes to certain display modes, color control, or other visual effect registers in the video device, rather than a series of rendering commands executed by the device. Thus, one must create the displayed image using some other rendering process, either before or while the CPU-driven display generation executes. In many cases, the image is also modified or re-rendered between frames. The image is then displayed in various ways, depending on the exact way in which the CPU-driven display code is implemented. Examples of the results possible on these older machines requiring CPU-driven video include effects such as Commodore 64/128's FLI mode, or Rainbow Processing on the ZX Spectrum. == Usage in OpenGL == To delimit a display list, the glNewList and glEndList functions are used, and to execute the list, the glCallList function is used. Almost all rendering commands that occur between the function calls are stored in the display list. Commands that affect the client state are not stored in display lists. Display lists are named with an integer value, and creating a display list with the same name as one already created overrides the first. The glNewList function expects two arguments: an integer representing the name of the list, and an enumeration for the compilation mode. The two modes include GL_COMPILE_AND_EXECUTE, which compiles and immediately executes, and GL_COMPILE, which only compiles the list. Display lists enable the use of the retained mode rendering pattern, which is a system in which graphics commands are recorded (retained) to execute in succession at a later time. This is contrary to immediate mode, where graphics commands are immediately executed on client calls. == Usage in Direct3D 12 == Command lists are created using the ID3D12Device::CreateCommandList function. Command lists may be created in several types: direct, bundle, compute, copy, video decode, video process, and video encoding. Direct command lists specify that a command list the GPU can execute, and doesn't inherit any GPU state. Bundles, are best used for storing and executing small sets of commands any number of times. This is used differently than regular command lists, where commands stored in a command list are typically executed only once. Compute command lists are used for general computations, with a common use being calculating mipmaps. A copy command list is strictly for copying and the video decode and video process command lists are for video decoding and processing respectively. Upon creation, command lists are in the recording state. Command lists may be re-used by calling the ID3D12GraphicsCommandList::Reset function. After recording commands, the command list must be transitioned out of the recording state by calling ID3D12GraphicsCommandList::Close. The command list is then executed by calling ID3D12CommandQueue::ExecuteCommandLists.
Image registration
Image registration is the process of transforming different sets of data into one coordinate system. Data may be multiple photographs, data from different sensors, times, depths, or viewpoints. It is used in computer vision, medical imaging, military automatic target recognition, and compiling and analyzing images and data from satellites. Registration is necessary in order to be able to compare or integrate the data obtained from these different measurements. == Algorithm classification == === Intensity-based vs feature-based === Image registration or image alignment algorithms can be classified into intensity-based and feature-based. One of the images is referred to as the target, fixed or sensed image and the others are referred to as the moving or source images. Image registration involves spatially transforming the source/moving image(s) to align with the target image. The reference frame in the target image is stationary, while the other datasets are transformed to match to the target. Intensity-based methods compare intensity patterns in images via correlation metrics, while feature-based methods find correspondence between image features such as points, lines, and contours. Intensity-based methods register entire images or sub-images. If sub-images are registered, centers of corresponding sub images are treated as corresponding feature points. Feature-based methods establish a correspondence between a number of especially distinct points in images. Knowing the correspondence between a number of points in images, a geometrical transformation is then determined to map the target image to the reference images, thereby establishing point-by-point correspondence between the reference and target images. Methods combining intensity-based and feature-based information have also been developed. === Transformation models === Image registration algorithms can also be classified according to the transformation models they use to relate the target image space to the reference image space. The first broad category of transformation models includes affine transformations, which include rotation, scaling, translation and shearing. Affine transformations are global in nature, thus, they cannot model local geometric differences between images. The second category of transformations allow 'elastic' or 'nonrigid' transformations. These transformations are capable of locally warping the target image to align with the reference image. Nonrigid transformations include radial basis functions (thin-plate or surface splines, multiquadrics, and compactly-supported transformations), physical continuum models (viscous fluids), and large deformation models (diffeomorphisms). Transformations are commonly described by a parametrization, where the model dictates the number of parameters. For instance, the translation of a full image can be described by a translation vector parameter. These models are called parametric models. Non-parametric models on the other hand, do not follow any parameterization, allowing each image element to be displaced arbitrarily. There are a number of programs that implement both estimation and application of a warp-field. It is a part of the SPM and AIR programs. === Transformations of coordinates via the law of function composition rather than addition === Alternatively, many advanced methods for spatial normalization are building on structure preserving transformations homeomorphisms and diffeomorphisms since they carry smooth submanifolds smoothly during transformation. Diffeomorphisms are generated in the modern field of Computational Anatomy based on flows since diffeomorphisms are not additive although they form a group, but a group under the law of function composition. For this reason, flows which generalize the ideas of additive groups allow for generating large deformations that preserve topology, providing 1-1 and onto transformations. Computational methods for generating such transformation are often called LDDMM which provide flows of diffeomorphisms as the main computational tool for connecting coordinate systems corresponding to the geodesic flows of Computational Anatomy. There are a number of programs which generate diffeomorphic transformations of coordinates via diffeomorphic mapping including MRI Studio and MRI Cloud.org === Spatial vs frequency domain methods === Spatial methods operate in the image domain, matching intensity patterns or features in images. Some of the feature matching algorithms are outgrowths of traditional techniques for performing manual image registration, in which an operator chooses corresponding control points (CP) in images. When the number of control points exceeds the minimum required to define the appropriate transformation model, iterative algorithms like RANSAC can be used to robustly estimate the parameters of a particular transformation type (e.g. affine) for registration of the images. Frequency-domain methods find the transformation parameters for registration of the images while working in the transform domain. Such methods work for simple transformations, such as translation, rotation, and scaling. Applying the phase correlation method to a pair of images produces a third image which contains a single peak. The location of this peak corresponds to the relative translation between the images. Unlike many spatial-domain algorithms, the phase correlation method is resilient to noise, occlusions, and other defects typical of medical or satellite images. Additionally, the phase correlation uses the fast Fourier transform to compute the cross-correlation between the two images, generally resulting in large performance gains. The method can be extended to determine rotation and scaling differences between two images by first converting the images to log-polar coordinates. Due to properties of the Fourier transform, the rotation and scaling parameters can be determined in a manner invariant to translation. === Single- vs multi-modality methods === Another classification can be made between single-modality and multi-modality methods. Single-modality methods tend to register images in the same modality acquired by the same scanner/sensor type, while multi-modality registration methods tended to register images acquired by different scanner/sensor types. Multi-modality registration methods are often used in medical imaging as images of a subject are frequently obtained from different scanners. Examples include registration of brain CT/MRI images or whole body PET/CT images for tumor localization, registration of contrast-enhanced CT images against non-contrast-enhanced CT images for segmentation of specific parts of the anatomy, and registration of ultrasound and CT images for prostate localization in radiotherapy. === Automatic vs interactive methods === Registration methods may be classified based on the level of automation they provide. Manual, interactive, semi-automatic, and automatic methods have been developed. Manual methods provide tools to align the images manually. Interactive methods reduce user bias by performing certain key operations automatically while still relying on the user to guide the registration. Semi-automatic methods perform more of the registration steps automatically but depend on the user to verify the correctness of a registration. Automatic methods do not allow any user interaction and perform all registration steps automatically. === Similarity measures for image registration === Image similarities are broadly used in medical imaging. An image similarity measure quantifies the degree of similarity between intensity patterns in two images. The choice of an image similarity measure depends on the modality of the images to be registered. Common examples of image similarity measures include cross-correlation, mutual information, sum of squared intensity differences, and ratio image uniformity. Mutual information and normalized mutual information are the most popular image similarity measures for registration of multimodality images. Cross-correlation, sum of squared intensity differences and ratio image uniformity are commonly used for registration of images in the same modality. Many new features have been derived for cost functions based on matching methods via large deformations have emerged in the field Computational Anatomy including Measure matching which are pointsets or landmarks without correspondence, Curve matching and Surface matching via mathematical currents and varifolds. == Uncertainty == There is a level of uncertainty associated with registering images that have any spatio-temporal differences. A confident registration with a measure of uncertainty is critical for many change detection applications such as medical diagnostics. In remote sensing applications where a digital image pixel may represent several kilometers of spatial distance (such as NASA's LANDSAT imagery), an uncertain image registration can mean that a solution could b
Multistage interconnection networks
Multistage interconnection networks (MINs) are a class of high-speed computer networks usually composed of processing elements (PEs) on one end of the network and memory elements (MEs) on the other end, connected by switching elements (SEs). The switching elements themselves are usually connected to each other in stages, hence the name. MINs are typically used in high-performance or parallel computing as a low-latency interconnection (as opposed to traditional packet switching networks), though they could be implemented on top of a packet switching network. Though the network is typically used for routing purposes, it could also be used as a co-processor to the actual processors for such uses as sorting; cyclic shifting, as in a perfect shuffle network; and bitonic sorting. == Background == Interconnection network are used to connect nodes, where nodes can be a single processor or group of processors, to other nodes. Interconnection networks can be categorized on the basis of their topology. Topology is the pattern in which one node is connected to other nodes. There are two main types of topology: static and dynamic. Static interconnect networks are hard-wired and cannot change their configurations. A regular static interconnect is mainly used in small networks made up of loosely couple nodes. The regular structure signifies that the nodes are arranged in specific shape and the shape is maintained throughout the networks. Some examples of static regular interconnections are: Completely connected network In a mesh network, multiple nodes are connected with each other. Each node in the network is connected to every other node in the network. This arrangement allows proper communication of the data between the nodes. But, there are a lot of communication overheads due to the increased number of node connections. Shared busThis network topology involves connection of the nodes with each other over a bus. Every node communicates with every other node using the bus. The bus utility ensures that no data is sent to the wrong node. But, the bus traffic is an important parameter which can affect the system. RingThis is one of the simplest ways of connecting nodes with each other. The nodes are connected with each other to form a ring. For a node to communicate with some other node, it has to send the messages to its neighbor. Therefore, the data message passes through a series of other nodes before reaching the destination. This involves increased latency in the system. TreeThis topology involves connection of the nodes to form a tree. The nodes are connected to form clusters and the clusters are in-turn connected to form the tree. This methodology causes increased complexity in the network. Hypercube This topology consists of connections of the nodes to form cubes. The nodes are also connected to the nodes on the other cubes. ButterflyThis is one of the most complex connections of the nodes. As the figure suggests, there are nodes which are connected and arranged in terms of their ranks. They are arranged in the form of a matrix. In dynamic interconnect networks, the nodes are interconnected via an array of simple switching elements. This interconnection can then be changed by use of routing algorithms, such that the path from one node to other nodes can be varied. Dynamic interconnections can be classified as: Single stage Interconnect Network Multistage interconnect Network Crossbar switch connections == Crossbar Switch Connections == In crossbar switch, there is a dedicated path from one processor to other processors. Thus, if there are n inputs and m outputs, we will need nm switches to realize a crossbar. As the number of outputs increases, the number of switches increases by factor of n. For large network this will be a problem. An alternative to this scheme is staged switching. == Single Stage Interconnect Network == In a single stage interconnect network, the input nodes are connected to output via a single stage of switches. The figure shows 88 single stage switch using shuffle exchange. As one can see, from a single shuffle, not all input can reach all output. Multiple shuffles are required for all inputs to be connected to all the outputs. == Multistage Interconnect Network == A multistage interconnect network is formed by cascading multiple single stage switches. The switches can then use their own routing algorithm, or be controlled by a centralized router, to form a completely interconnected network. Multistage Interconnect Network can be classified into three types: Non-blocking: A non-blocking network can connect any idle input to any idle output, regardless of the connections already established across the network. Crossbar is an example of this type of network. Rearrangeable non-blocking: This type of network can establish all possible connections between inputs and outputs by rearranging its existing connections. Blocking: This type of network cannot realize all possible connections between inputs and outputs. This is because a connection between one free input to another free output is blocked by an existing connection in the network. The number of switching elements required to realize a non-blocking network in highest, followed by rearrangeable non-blocking. Blocking network uses least switching elements. == Examples == Multiple types of multistage interconnection networks exist. === Omega network === An Omega network consists of multiple stages of 22 switching elements. Each input has a dedicated connection to an output. An NN omega network has log2(N) stages and N/2 switching elements in each stage for a perfect shuffle between stages. Thus the network has complexity of 0(N log(N)). Each switching element can employ its own switching algorithm. Consider an 88 omega network. There are 8! = 40320 1-to-1 mappings from input to output. There are 12 switching element for a total permutation of 2^12 = 4096. Thus, it is a blocking network. === Clos network === A Clos network uses 3 stages to switch from N inputs to N outputs. In the first stage, there are r= N/n crossbar switches and each switch is of size nm. In the second stage there are m switches of size rr and finally the last stage is a mirror of the first stage with r switches of size mn. A clos network will be completely non-blocking if m >= 2n-1. The number of connections, though more than omega network is much less than that of a crossbar network. === Beneš network === A Beneš network is a rearrangeably non-blocking network derived from the clos network by initializing n = m = 2. There are (2log2(N) - 1) stages, with each stage containing N/2 22 crossbar switches. An 88 Beneš network has 5 stages of switching elements, and each stage has 4 switching elements. The center three stages has two 44 benes network. The 44 Beneš network, can connect any input to any output recursively.
Data lineage
Data lineage refers to the process of tracking how data is generated, transformed, transmitted and used across systems over time. It documents data's origins, transformations and movements, providing detailed visibility into its life cycle. This process simplifies the identification of errors in data analytics workflows, by enabling users to trace issues back to their root causes. Data lineage facilitates the ability to replay specific segments or inputs of the dataflow. This can be used in debugging or regenerating lost outputs. In database systems, this concept is closely related to data provenance, which involves maintaining records of inputs, entities, systems and processes that influence data. Data provenance provides a historical record of data origins and transformations. It supports forensic activities such as data-dependency analysis, error/compromise detection, recovery, auditing and compliance analysis: "Lineage is a simple type of why provenance." Data governance plays a critical role in managing metadata by establishing guidelines, strategies and policies. Enhancing data lineage with data quality measures and master data management adds business value. Although data lineage is typically represented through a graphical user interface (GUI), the methods for gathering and exposing metadata to this interface can vary. Based on the metadata collection approach, data lineage can be categorized into three types: Those involving software packages for structured data, programming languages and Big data systems. Data lineage information includes technical metadata about data transformations. Enriched data lineage may include additional elements such as data quality test results, reference data, data models, business terminology, data stewardship information, program management details and enterprise systems associated with data points and transformations. Data lineage visualization tools often include masking features that allow users to focus on information relevant to specific use cases. To unify representations across disparate systems, metadata normalization or standardization may be required. == Representation of data lineage == Representation broadly depends on the scope of the metadata management and reference point of interest. Data lineage provides sources of the data and intermediate data flow hops from the reference point with backward data lineage, leading to the final destination's data points and its intermediate data flows with forward data lineage. These views can be combined with end-to-end lineage for a reference point that provides a complete audit trail of that data point of interest from sources to their final destinations. As the data points or hops increase, the complexity of such representation becomes incomprehensible. Thus, the best feature of the data lineage view is the ability to simplify the view by temporarily masking unwanted peripheral data points. Tools with the masking feature enable scalability of the view and enhance analysis with the best user experience for both technical and business users. Data lineage also enables companies to trace sources of specific business data to track errors, implement changes in processes and implementing system migrations to save significant amounts of time and resources. Data lineage can improve efficiency in business intelligence BI processes. Data lineage can be represented visually to discover the data flow and movement from its source to destination via various changes and hops on its way in the enterprise environment. This includes how the data is transformed along the way, how the representation and parameters change and how the data splits or converges after each hop. A simple representation of the Data Lineage can be shown with dots and lines, where dots represent data containers for data points, and lines connecting them represent transformations the data undergoes between the data containers. Data lineage can be visualized at various levels based on the granularity of the view. At a very high-level, data lineage is visualized as systems that the data interacts with before it reaches its destination. At its most granular, visualizations at the data point level can provide the details of the data point and its historical behavior, attribute properties and trends and data quality of the data passed through that specific data point in the data lineage. The scope of the data lineage determines the volume of metadata required to represent its data lineage. Usually, data governance and data management of an organization determine the scope of the data lineage based on their regulations, enterprise data management strategy, data impact, reporting attributes and critical data elements of the organization. == Rationale == Distributed systems like Google Map Reduce, Microsoft Dryad, Apache Hadoop (an open-source project) and Google Pregel provide such platforms for businesses and users. However, even with these systems, Big Data analytics can take several hours, days or weeks to run, simply due to the data volumes involved. For example, a ratings prediction algorithm for the Netflix Prize challenge took nearly 20 hours to execute on 50 cores, and a large-scale image processing task to estimate geographic information took 3 days to complete using 400 cores. "The Large Synoptic Survey Telescope is expected to generate terabytes of data every night and eventually store more than 50 petabytes, while in the bioinformatics sector, the 12 largest genome sequencing houses in the world now store petabytes of data apiece. It is very difficult for a data scientist to trace an unknown or an unanticipated result. === Big data debugging === Big data analytics is the process of examining large data sets to uncover hidden patterns, unknown correlations, market trends, customer preferences and other useful business information. Machine learning, among other algorithms, is used to transform and analyze the data. Due to the large size of the data, there could be unknown features in the data. The massive scale and unstructured nature of data, the complexity of these analytics pipelines, and long runtimes pose significant manageability and debugging challenges. Even a single error in these analytics can be extremely difficult to identify and remove. While one may debug them by re-running the entire analytics through a debugger for stepwise debugging, this can be expensive due to the amount of time and resources needed. Auditing and data validation are other major problems due to the growing ease of access to relevant data sources for use in experiments, the sharing of data between scientific communities and use of third-party data in business enterprises. As such, more cost-efficient ways of analyzing data intensive scale-able computing (DISC) are crucial to their continued effective use. === Challenges in Big Data debugging === ==== Massive scale ==== According to an EMC/IDC study, 2.8 ZB of data were created and replicated in 2012. Furthermore, the same study states that the digital universe will double every two years between now and 2020, and that there will be approximately 5.2 TB of data for every person in 2020. Based on current technology, the storage of this much data will mean greater energy usage by data centers. ==== Unstructured data ==== Unstructured data usually refers to information that doesn't reside in a traditional row-column database. Unstructured data files often include text and multimedia content, such as e-mail messages, word processing documents, videos, photos, audio files, presentations, web pages and many other kinds of business documents. While these types of files may have an internal structure, they are still considered "unstructured" because the data they contain doesn't fit neatly into a database. The amount of unstructured data in enterprises is growing many times faster than structured databases are growing. Big data can include both structured and unstructured data, but IDC estimates that 90 percent of Big Data is unstructured data. The fundamental challenge of unstructured data sources is that they are difficult for non-technical business users and data analysts alike to unbox, understand and prepare for analytic use. Beyond issues of structure, the sheer volume of this type of data contributes to such difficulty. Because of this, current data mining techniques often leave out valuable information and make analyzing unstructured data laborious and expensive. In today's competitive business environment, companies have to find and analyze the relevant data they need quickly. The challenge is going through the volumes of data and accessing the level of detail needed, all at a high speed. The challenge only grows as the degree of granularity increases. One possible solution is hardware. Some vendors are using increased memory and parallel processing to crunch large volumes of data quickly. Another method is putting data in-memory but using a grid
Social bot
A social bot, refers to fully or partially automated social media accounts designed to perform most regular users’ actions, such as liking, posting content, and chatting with other users. Although their levels of autonomy vary, and often include a human-in-the-loop, social bots can use artificial intelligence to perform social media actions and can use large language models to mimic human dialogue. Social bots can operate alone or in groups that coordinate messaging as part of a network of coordinated inauthentic behavior. Social bots are often used to perform ad fraud by artificially boosting viewership and engagement metrics and to spread disinformation on social media. == Uses == Social bots are used for a large number of purposes on a variety of social media platforms, including Twitter, Instagram, Facebook, and YouTube. One common use of social bots is to inflate a social media user's apparent popularity, usually by artificially manipulating their engagement metrics with large volumes of fake likes, reposts, or replies. Social bots can similarly be used to artificially inflate a user's follower count with fake followers, creating a false perception of a larger and more influential online following than is the case. The use of social bots to create the impression of a large social media influence allows individuals, brands, and organizations to attract a higher number of human followers and boost their online presence. Fake engagement can be bought and sold in the black market of social media engagement. Corporations typically use automated customer service agents on social media to affordably manage high levels of support requests. Social bots are used to send automated responses to users’ questions, sometimes prompting the user to private message the support account with additional information. The increased use of automated support bots and virtual assistants has led to some companies laying off customer-service staff. Social bots are also often used to influence public opinion. Autonomous bot accounts can flood social media with large numbers of posts expressing support for certain products, companies, or political campaigns, creating the impression of organic grassroots support. This can create a false perception of the number of people who support a certain position, which may also have effects on the direction of stock prices or on elections. Messages with similar content can also influence fads or trends. Many social bots are also used to amplify phishing attacks. These malicious bots are used to trick a social media user into giving up their passwords or other personal data. This is usually accomplished by posting links claiming to direct users to news articles that would in actuality direct to malicious websites containing malware. Scammers often use URL shortening services such as TinyURL and bit.ly to disguise a link's domain address, increasing the likelihood of a user clicking the malicious link. The presence of fake social media followers and high levels of engagement help convince the victim that the scammer is in fact a trusted user. Social bots can be a tool for computational propaganda. Bots can also be used for algorithmic curation, algorithmic radicalization, and/or influence-for-hire, a term that refers to the selling of an account on social media platforms. == History == Bots have coexisted with computer technology since the earliest days of computing. Social bots have their roots in the 1950s with Alan Turing, whose work focused on machine intelligence with the development of the Turing Test. The following decades saw further progress made towards the goal of creating programs capable of mimicking human behavior, notably with Joseph Weizenbaum’s creation of ELIZA. Considered to be one of the first Chatbots, ELIZA could simulate natural conversations with human users through pattern matching. Its most famous script was DOCTOR, a simulation of a Rogerian psychotherapist that was programmed to chat with patients and respond to questions. With the growth of social media platforms in the early 2000s, these bots could be used to interact with much larger user groups in an inconspicuous manner. Early instances of autonomous agents on social media could be found on sites like MySpace, with social bots being used by marketing firms to inflate activity on a user’s page in an effort to make them appear more popular. Social bots have been observed on a large variety of social media websites, with Twitter being one of the most widely observed examples. The creation of Twitter bots is generally against the site’s terms of service when used to post spam or to automatically like and follow other users, but some degree of automation using Twitter’s API may be permitted if used for “entertainment, informational, or novelty purposes.” Other platforms such as Reddit and Discord also allow for the use of social bots as long as they are not used to violate policies regarding harmful content and abusive behavior. Social media platforms have developed their own automated tools to filter out messages that come from bots, although they cannot detect all bot messages. == Legal regulation == Due to the difficulty of recognizing social bots and separating them from "eligible" automation via social media APIs, it is unclear how legal regulation can be enforced. Social bots are expected to play a role in shaping public opinion by autonomously acting as influencers. Some social bots have been used to rapidly spread misinformation, manipulate stock markets, influence opinion on companies and brands, promote political campaigns, and engage in malicious phishing campaigns. In the United States, some states have started to implement legislation in an attempt to regulate the use of social bots. In 2019, California passed the Bolstering Online Transparency Act (the B.O.T. Act) to make it unlawful to use automated software to appear indistinguishable from humans for the purpose of influencing a social media user's purchasing and voting decisions. Other states such as Utah and Colorado have passed similar bills to restrict the use of social bots. The Artificial Intelligence Act (AI Act) in the European Union is the first comprehensive law governing the use of Artificial Intelligence. The law requires transparency in AI to prevent users from being tricked into believing they are communicating with another human. AI-generated content on social media must be clearly marked as such, preventing social bots from using AI in a manner that mimics human behavior. == Detection == The first generation of bots could sometimes be distinguished from real users by their often superhuman capacities to post messages. Later developments have succeeded in imprinting more "human" activity and behavioral patterns in the agent. With enough bots, it might be even possible to achieve artificial social proof. To unambiguously detect social bots as what they are, a variety of criteria must be applied together using pattern detection techniques, some of which are: cartoon figures as user pictures sometimes also random real user pictures are captured (identity fraud) reposting rate temporal patterns sentiment expression followers-to-friends ratio length of user names variability in (re)posted messages engagement rate (like/followers rate) analysis of the time series of social media posts Social bots are always becoming increasingly difficult to detect and understand. The bots' human-like behavior, ever-changing behavior of the bots, and the sheer volume of bots covering every platform may have been a factor in the challenges of removing them. Social media sites, like Twitter, are among the most affected, with CNBC reporting up to 48 million of the 319 million users (roughly 15%) were bots in 2017. Botometer (formerly BotOrNot) is a public Web service that checks the activity of a Twitter account and gives it a score based on how likely the account is to be a bot. The system leverages over a thousand features. An active method for detecting early spam bots was to set up honeypot accounts that post nonsensical content, which may get reposted (retweeted) by the bots. However, bots evolve quickly, and detection methods have to be updated constantly, because otherwise they may get useless after a few years. One method is the use of Benford's Law for predicting the frequency distribution of significant leading digits to detect malicious bots online. This study was first introduced at the University of Pretoria in 2020. Another method is artificial-intelligence-driven detection. Some of the sub-categories of this type of detection would be active learning loop flow, feature engineering, unsupervised learning, supervised learning, and correlation discovery. Some operations of bots work together in a synchronized way. For example, ISIS used Twitter to amplify its Islamic content by numerous orchestrated accounts which further pushed an item to the Hot List news, thus further a
Termcap
Termcap (terminal capability) is a legacy software library and database used on Unix-like computers that enables programs to use display computer terminals in a terminal-independent manner, which greatly simplifies the process of writing portable text mode applications. It was superseded by the terminfo database used by ncurses, tput, and other programs. A termcap database can describe the capabilities of hundreds of different display terminals. This allows programs to have character-based display output, independent of the type of terminal. On-screen text editors such as vi and Emacs are examples of programs that may use termcap. Other programs are listed in the Termcap category. Access to the termcap database was usually provided by separate libraries, e.g. GNU Termcap. Examples of what the database describes: how many columns wide the display is what string to send to move the cursor to an arbitrary position (including how to encode the row and column numbers) how to scroll the screen up one or several lines how much padding is needed for such a scrolling operation. == History == Bill Joy wrote the first termcap library in 1978 for the Berkeley Unix operating system; it has since been ported to most Unix and Unix-like environments, even OS-9. Joy's design was reportedly influenced by the design of the terminal data store in the earlier Incompatible Timesharing System. == Data model == Termcap databases consist of one or more descriptions of terminals. === Indices === Each description must contain the canonical name of the terminal. It may also contain one or more aliases for the name of the terminal. The canonical name or aliases are the keys by which the library searches the termcap database. === Data values === The description contains one or more capabilities, which have conventional names. The capabilities are typed: boolean, numeric and string. The termcap library has no predetermined type for each capability name. It determines the types of each capability by the syntax: string capabilities have an "=" between the capability name and its value, numeric capabilities have a "#" between the capability name and its value, and boolean capabilities have no associated value (they are always true if specified). Applications which use termcap do expect specific types for the commonly used capabilities, and obtain the values of capabilities from the termcap database using library calls that return successfully only when the database contents matches the assumed type. === Hierarchy === Termcap descriptions can be constructed by including the contents of one description in another, suppressing capabilities from the included description or overriding or adding capabilities. No matter what storage model is used, the termcap library constructs the terminal description from the requested description, including, suppressing or overriding at the time of the request. == Storage model == Termcap data is stored as text, making it simple to modify. The text can be retrieved by the termcap library from files or environment variables. === Environment variables === The TERM environment variable contains the terminal type name. The TERMCAP environment variable may contain a termcap database. It is most often used to store a single termcap description, set by a terminal emulator to provide the terminal's characteristics to the shell and dependent programs. The TERMPATH environment variable is supported by newer termcap implementations and defines a search path for termcap files. === Flat file === The original (and most common) implementation of the termcap library retrieves data from a flat text file. Searching a large termcap file, e.g., 500 kB, can be slow. To aid performance, a utility such as reorder is used to put the most frequently used entries near the beginning of the file. === Hashed database === 4.4BSD based implementations of termcap store the terminal description in a hashed database (e.g., something like Berkeley DB version 1.85). These store two types of records: aliases which point to the canonical entry, and the canonical entry itself. The text of the termcap entry is stored literally. == Limitations and extensions == The original termcap implementation was designed to use little memory: the first name is two characters, to fit in 16 bits capability names are two characters descriptions are limited to 1023 characters. only one termcap entry with its definitions can be included, and must be at the end. Newer implementations of the termcap interface generally do not require the two-character name at the beginning of the entry. Capability names are still two characters in all implementations. The tgetent function used to read the terminal description uses a buffer whose size must be large enough for the data, and is assumed to be 1024 characters. Newer implementations of the termcap interface may relax this constraint by allowing a null pointer in place of the fixed buffer, or by hiding the data which would not fit, e.g., via the ZZ capability in NetBSD termcap. The terminfo library interface also emulates the termcap interface, and does not actually use the fixed-size buffer. The terminfo library's emulation of termcap allows multiple other entries to be included without restricting the position. A few other newer implementations of the termcap library may also provide this ability, though it is not well documented. == Obsolete features == A special capability, the "hz" capability, was defined specifically to support the Hazeltine 1500 terminal, which had the unfortunate characteristic of using the ASCII tilde character ('~') as a control sequence introducer. In order to support that terminal, not only did code that used the database have to know about using the tilde to introduce certain control sequences, but it also had to know to substitute another printable character for any tildes in the displayed text, since a tilde in the text would be interpreted by the terminal as the start of a control sequence, resulting in missing text and screen garbling. Additionally, attribute markers (such as start and end of underlining) themselves took up space on the screen. Comments in the database source code often referred to this as "Hazeltine braindamage". Since the Hazeltine 1500 was a widely used terminal in the late 1970s, it was important for applications to be able to deal with its limitations.
Tropical cryptography
In tropical analysis, tropical cryptography refers to the study of a class of cryptographic protocols built upon tropical algebras. In many cases, tropical cryptographic schemes have arisen from adapting classical (non-tropical) schemes to instead rely on tropical algebras. The case for the use of tropical algebras in cryptography rests on at least two key features of tropical mathematics: in the tropical world, there is no classical multiplication (a computationally expensive operation), and the problem of solving systems of tropical polynomial equations has been shown to be NP-hard. == Basic Definitions == The key mathematical object at the heart of tropical cryptography is the tropical semiring ( R ∪ { ∞ } , ⊕ , ⊗ ) {\displaystyle (\mathbb {R} \cup \{\infty \},\oplus ,\otimes )} (also known as the min-plus algebra), or a generalization thereof. The operations are defined as follows for x , y ∈ R ∪ { ∞ } {\displaystyle x,y\in \mathbb {R} \cup \{\infty \}} : x ⊕ y = min { x , y } {\displaystyle x\oplus y=\min\{x,y\}} x ⊗ y = x + y {\displaystyle x\otimes y=x+y} It is easily verified that with ∞ {\displaystyle \infty } as the additive identity, these binary operations on R ∪ { ∞ } {\displaystyle \mathbb {R} \cup \{\infty \}} form a semiring.