C-RAN (Cloud-RAN), also referred to as Centralized-RAN, is an architecture for cellular networks. C-RAN is a centralized, cloud computing-based architecture for radio access networks that supports 2G, 3G, 4G, 5G and future wireless communication standards. Its name comes from the four 'C's in the main characteristics of C-RAN system, "Clean, Centralized processing, Collaborative radio, and a real-time Cloud Radio Access Network". == Background == Traditional cellular, or Radio Access Networks (RAN), consist of many stand-alone base stations (BTS). Each BTS covers a small area, whereas a group BTS provides coverage over a continuous area. Each BTS processes and transmits its own signal to and from the mobile terminal, and forwards the data payload to and from the mobile terminal and out to the core network via the backhaul. Each BTS has its own cooling, back haul transportation, backup battery, monitoring system, and so on. Because of limited spectral resources, network operators 'reuse' the frequency among different base stations, which can cause interference between neighboring cells. There are several limitations in the traditional cellular architecture. First, each BTS is costly to build and operate. Moore's law helps reduce the size and power of an electrical system, but the supporting facilities of the BTS are not improved quite as well. Second, when more BTS are added to a system to improve its capacity, interference among BTS is more severe as BTS are closer to each other and more of them are using the same frequency. Third, because users are mobile, the traffic of each BTS fluctuates (called 'tide effect'), and as a result, the average utilization rate of individual BTS is pretty low. However, these processing resources cannot be shared with other BTS. Therefore, all BTS are designed to handle the maximum traffic, not average traffic, resulting in a waste of processing resources and power at idle times. == Evolution of base station architecture == === All-in-one macro base station === In the 1G and 2G cellular networks, base stations had an all-in-one architecture. Analog, digital, and power functions were housed in a single cabinet as large as a refrigerator. Usually the base station cabinet was placed in a dedicated room along with all necessary supporting facilitates such as power, backup battery, air conditioning, environment surveillance, and backhaul transmission equipment. The RF signal is generated by the base station RF unit and propagates through pairs of RF cables up to the antennas on the top of a base station tower or other mounting points. This all-in-one architecture was mostly found in macro cell deployments. === Distributed base station === For 3G, a distributed base station architecture was introduced by Ericsson, Nokia, Huawei, and other leading telecom equipment vendors. In this architecture the radio function unit, also known as the remote radio head (RRH), is separated from the digital function unit, or baseband unit (BBU) by fiber. Digital baseband signals are carried over fiber, using the Open Base Station Architecture Initiative (OBSAI) or Common Public Radio Interface (CPRI) standard. The RRH can be installed on the top of tower close to the antenna, reducing the loss compared to the traditional base station where the RF signal has to travel through a long cable from the base station cabinet to the antenna at the top of the tower. The fiber link between RRH and BBU also allows more flexibility in network planning and deployment as they can be placed a few hundred meters or a few kilometers away. Most modern base stations now use this decoupled architecture. === C-RAN/Cloud-RAN === C-RAN may be viewed as an architectural evolution of the above distributed base station system. It takes advantage of many technological advances in wireless, optical and IT communications systems. For example, it uses the latest CPRI standard, low cost Coarse or Dense Wavelength Division Multiplexing (CWDM/ DWDM) technology, and mmWave to allow transmission of baseband signal over long distance thus achieving large scale centralised base station deployment. It applies recent Data Centre Network technology to allow a low cost, high reliability, low latency and high bandwidth interconnect network in the BBU pool. It utilizes open platforms and real-time virtualization technology rooted in cloud computing to achieve dynamic shared resource allocation and support multi-vendor, multi-technology environments. == Architecture overview == C-RAN architecture has the following characteristics that are distinct from other cellular architectures: Large scale centralized deployment: Allows many RRHs to connect to a centralized BBU pool. The maximum distance can be 20km in fiber link for 4G (LTE/LTE-A) systems, and even longer distances (40~80km) for 3G (WCDMA/TD-SCDMA) and 2G (GSM/CDMA) systems. Native support to Collaborative Radio technologies: Any BBU can talk with any other BBU within the BBU pool with very high bandwidth (10 Gbit/s and above) and low latency (10 μs level). This is enabled by the interconnection of BBUs in the pool. This is one major difference from BBU Hotelling, or base station Hotelling; in the latter case, the BBUs of different base stations are simply stacked together and have no direct link between them to allow physical layer co-ordination. Real-time virtualization capability based on open platform: This is different from traditional base stations built on proprietary hardware, where the software and hardware are close-sourced and provided by single vendors. In contrast, a C-RAN BBU pool is built on open hardware, like x86/ARM CPU based servers, and interface cards that handle fiber links to RRHs and inter-connections in the pool. Real-time virtualization ensures that resources in the pool can be allocated dynamically to base station software stacks, say 4G/3G/2G function modules from different vendors, according to network load. However, to satisfy the strict timing requirements of wireless communication systems, the real-time performance for C-RAN is at the level of tens of microseconds, which is two orders of magnitude better than the millisecond level 'real-time' performance usually seen in Cloud Computing environments. == Similar architecture and systems == KT, a telecom operator in the Republic of Korea, introduced a Cloud Computing Center (CCC) system in their 3G (WCDMA/HSPA) and 4G (LTE/LTE-A) network in 2011 and 2012. The concept of CCC is basically the same as C-RAN. SK Telecom has also deployed Smart Cloud Access Network (SCAN) and Advanced-SCAN in their 4G (LTE/LTE-A) network in Korea no later than 2012. In 2014, Airvana (now CommScope) introduced OneCell, a C-RAN-based small cell system designed for enterprises and public spaces. == Competing architectures in cellular network evolution == === All-in-one BTS === One major alternative solution that is addressing similar challenges of RAN, is the small size, all-in-one outdoor BTS. Thanks to the achievements in the semiconductor industry, all the functionality of a BTS, including RF, baseband processing, MAC processing and package level processing, can now be implemented in a volume of <50 liters. This makes the system small and weatherproof, reduces the difficulty of BTS site choice and construction, eliminates the air conditioning requirement, and thus reduces operational costs. However, because each BTS is still working on its own, it cannot readily make use of the collaboration algorithms to reduce the interference between neighboring BTSs. It is also relatively hard to upgrade or repair because the all-in-one BTS units are usually mounted near the antenna. More processing units in less-protected environments also implies a higher failure rate compared to C-RAN, which only has the RRU deployed outdoors. The advantage of Cloud RAN lies in its ability to implement LTE-Advanced features such as Coordinated MultiPoint (CoMP) with very low latency between multiple radio heads. However, the economic benefit of improvements such as CoMP can be negated by the higher backhaul costs for some operators. === Small cell === The main competition between small cell and C-RAN occurs in two deployment scenarios: outdoor hotspot coverage and indoor coverage. == Academic research and publications == As one of the promising evolution paths for future cellular network architecture, C-RAN has attracted high academic research interest. Meanwhile, because the native support of cooperative radio capability built into the C-RAN architecture, it also enables many advanced algorithms that were hard to implement in cellular networks, including Cooperative Multi-Point Transmission/Receiving, Network Coding, etc. In October 2011, Wireless World Research Forum 27 was hosted in Germany, when China Mobile was invited to give a C-RAN presentation. In August 2012, IEEE C-RAN 2012 workshop was hosted in Kunming, China. CRC Press published a book, "Green Communications: Theore
Direct Graphics Access
Direct Graphics Access is a plug-in for the X display servers that allows client programs direct access to the frame buffer. Graphics hardware communicates via a chunk of memory called a frame buffer. This is an array of values that represent pixel color values on the screen. Writing the appropriate values into the frame buffer therefore allows a program to paint areas of the screen. However, as with any shared resource, problems occur when multiple programs attempt to access the same resource, as they tend to write over each other's work. In the X Window System, this is solved by having a central display server that mediates between programs that want to draw on the screen. The display server also used to perform a lot of the drawing work, allowing programs to say Draw me a circle of this radius filled with this pattern or draw this text in this font. The X server does all this work, freeing programmers from having to write their own drawing code. Another advantage of the X architecture is that it works over a network, allowing programs on one machine to display output on the screen of another. Direct Graphics Access allows direct access to the frame buffer and the X-server hands over control of the frame buffer to the client program and waits for the client to hand it back. This means that the client program has control of the whole screen, and so it is mostly used for full-screen video/games.
Spatial–temporal reasoning
Spatial–temporal reasoning is an area of artificial intelligence that draws from the fields of computer science, cognitive science, and cognitive psychology. The theoretic goal—on the cognitive side—involves representing and reasoning spatial-temporal knowledge in mind. The applied goal—on the computing side—involves developing high-level control systems of automata for navigating and understanding time and space. == Influence from cognitive psychology == A convergent result in cognitive psychology is that the connection relation is the first spatial relation that human babies acquire, followed by understanding orientation relations and distance relations. Internal relations among the three kinds of spatial relations can be computationally and systematically explained within the theory of cognitive prism as follows: the connection relation is primitive; an orientation relation is a distance comparison relation: you being in front of me can be interpreted as you are nearer to my front side than my other sides; a distance relation is a connection relation using a third object: you being one meter away from me can be interpreted as a one-meter-long object connected with you and me simultaneously. == Fragmentary representations of temporal calculi == Without addressing internal relations among spatial relations, AI researchers contributed many fragmentary representations. Examples of temporal calculi include Allen's interval algebra, and Vilain's & Kautz's point algebra. The most prominent spatial calculi are mereotopological calculi, Frank's cardinal direction calculus, Freksa's double cross calculus, Egenhofer and Franzosa's 4- and 9-intersection calculi, Ligozat's flip-flop calculus, various region connection calculi (RCC), and the Oriented Point Relation Algebra. Recently, spatio-temporal calculi have been designed that combine spatial and temporal information. For example, the spatiotemporal constraint calculus (STCC) by Gerevini and Nebel combines Allen's interval algebra with RCC-8. Moreover, the qualitative trajectory calculus (QTC) allows for reasoning about moving objects. == Quantitative abstraction == An emphasis in the literature has been on qualitative spatial-temporal reasoning which is based on qualitative abstractions of temporal and spatial aspects of the common-sense background knowledge on which our human perspective of physical reality is based. Methodologically, qualitative constraint calculi restrict the vocabulary of rich mathematical theories dealing with temporal or spatial entities such that specific aspects of these theories can be treated within decidable fragments with simple qualitative (non-metric) languages. Contrary to mathematical or physical theories about space and time, qualitative constraint calculi allow for rather inexpensive reasoning about entities located in space and time. For this reason, the limited expressiveness of qualitative representation formalism calculi is a benefit if such reasoning tasks need to be integrated in applications. For example, some of these calculi may be implemented for handling spatial GIS queries efficiently and some may be used for navigating, and communicating with, a mobile robot. == Relation algebra == Most of these calculi can be formalized as abstract relation algebras, such that reasoning can be carried out at a symbolic level. For computing solutions of a constraint network, the path-consistency algorithm is an important tool. == Software == GQR, constraint network solver for calculi like RCC-5, RCC-8, Allen's interval algebra, point algebra, cardinal direction calculus, etc. qualreas is a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra, and Allen's algebra integrated with Time Points and situated in either Left- or Right-Branching Time.
Logico-linguistic modeling
Logico-linguistic modeling is a method for building knowledge-based systems with a learning capability using conceptual models from soft systems methodology, modal predicate logic, and logic programming languages such as Prolog. == Overview == Logico-linguistic modeling is a six-stage method developed primarily for building knowledge-based systems (KBS), but it also has application in manual decision support systems and information source analysis. Logico-linguistic models have a superficial similarity to John F. Sowa's conceptual graphs; both use bubble style diagrams, both are concerned with concepts, both can be expressed in logic and both can be used in artificial intelligence. However, logico-linguistic models are very different in both logical form and in their method of construction. Logico-linguistic modeling was developed in order to solve theoretical problems found in the soft systems method for information system design. The main thrust of the research into has been to show how soft systems methodology (SSM), a method of systems analysis, can be extended into artificial intelligence. == Background == SSM employs three modeling devices i.e. rich pictures, root definitions, and conceptual models of human activity systems. The root definitions and conceptual models are built by stakeholders themselves in an iterative debate organized by a facilitator. The strengths of this method lie, firstly, in its flexibility, the fact that it can address any problem situation, and, secondly, in the fact that the solution belongs to the people in the organization and is not imposed by an outside analyst. Information requirements analysis (IRA) took the basic SSM method a stage further and showed how the conceptual models could be developed into a detailed information system design. IRA calls for the addition of two modeling devices: "Information Categories", which show the required information inputs and outputs from the activities identified in an expanded conceptual model; and the "Maltese Cross", a matrix which shows the inputs and outputs from the information categories and shows where new information processing procedures are required. A completed Maltese Cross is sufficient for the detailed design of a transaction processing system. The initial impetus to the development of logico-linguistic modeling was a concern with the theoretical problem of how an information system can have a connection to the physical world. This is a problem in both IRA and more established methods (such as SSADM) because none base their information system design on models of the physical world. IRA designs are based on a notional conceptual model and SSADM is based on models of the movement of documents. The solution to these problems provided a formula that was not limited to the design of transaction processing systems but could be used for the design of KBS with learning capability. == The six stages of logico-linguistic modeling == The logico-linguistic modeling method comprises six stages. === 1. Systems analysis === In the first stage logico-linguistic modeling uses SSM for systems analysis. This stage seeks to structure the problem in the client organization by identifying stakeholders, modelling organizational objectives and discussing possible solutions. At this stage it not assumed that a KBS will be a solution and logico-linguistic modeling often produces solutions that do not require a computerized KBS. Expert systems tend to capture the expertise, of individuals in different organizations, on the same topic. By contrast a KBS, produced by logico-linguistic modeling, seeks to capture the expertise of individuals in the same organization on different topics. The emphasis is on the elicitation of organizational or group knowledge rather than individual experts. In logico-linguistic modeling the stakeholders become the experts. The end point of this stage is an SSM style conceptual models such as figure 1. === 2. Language creation === According to the theory behind logico-linguistic modeling the SSM conceptual model building process is a Wittgensteinian language-game in which the stakeholders build a language to describe the problem situation. The logico-linguistic model expresses this language as a set of definitions, see figure 2. === 3. Knowledge elicitation === After the model of the language has been built putative knowledge about the real world can be added by the stakeholders. Traditional SSM conceptual models contain only one logical connective (a necessary condition). In order to represent causal sequences, "sufficient conditions" and "necessary and sufficient conditions" are also required. In logico-linguistic modeling this deficiency is remedied by two addition types of connective. The outcome of stage three is an empirical model, see figure 3. === 4. Knowledge representation === Modal predicate logic (a combination of modal logic and predicate logic) is used as the formal method of knowledge representation. The connectives from the language model are logically true (indicated by the "L" modal operator) and connective added at the knowledge elicitation stage are possibility true (indicated by the "M" modal operator). Before proceeding to stage 5, the models are expressed in logical formulae. === 5. Computer code === Formulae in predicate logic translate easily into the Prolog artificial intelligence language. The modality is expressed by two different types of Prolog rules. Rules taken from the language creation stage of model building process are treated as incorrigible. While rules from the knowledge elicitation stage are marked as hypothetical rules. The system is not confined to decision support but has a built in learning capability. === 6. Verification === A knowledge based system built using this method verifies itself. Verification takes place when the KBS is used by the clients. It is an ongoing process that continues throughout the life of the system. If the stakeholder beliefs about the real world are mistaken this will be brought out by the addition of Prolog facts that conflict with the hypothetical rules. It operates in accordance to the classic principle of falsifiability found in the philosophy of science == Applications == === Knowledge-based computer systems === Logico-linguistic modeling has been used to produce fully operational computerized knowledge based systems, such as one for the management of diabetes patients in a hospital out-patients department. === Manual decision support === In other projects the need to move into Prolog was considered unnecessary because the printed logico-linguistic models provided an easy-to-use guide to decision making. For example, a system for mortgage loan approval === Information source analysis === In some cases a KBS could not be built because the organization did not have all the knowledge needed to support all their activities. In these cases logico-linguistic modeling showed shortcomings in the supply of information and where more was needed. For example, a planning department in a telecoms company == Criticism == While logico-linguistic modeling overcomes the problems found in SSM's transition from conceptual model to computer code, it does so at the expense of increased stakeholder constructed model complexity. The benefits of this complexity are questionable and this modeling method may be much harder to use than other methods. This contention has been exemplified by subsequent research. An attempt by researchers to model buying decisions across twelve companies using logico-linguistic modeling required simplification of the models and removal of the modal elements.
TRAIGA
TRAIGA, or the Texas Responsible Artificial Intelligence Governance Act, is a state law regulating the development and deployment of artificial intelligence (AI) systems in Texas. Sponsored by Representative Giovanni Capriglione, the Act establishes a framework governing certain uses of AI, outlines prohibited uses, and creates obligations on state government entities, among other provisions. TRAIGA was signed into law in 2025 and took effect on January 1, 2026. The law applies to AI developers and deployers that conduct business in Texas or whose systems are used by Texas residents. It prohibits the intentional development or deployment of AI systems to incite harm, violate constitutional rights, engage in unlawful discrimination, and produce child sexual abuse material or unlawful deepfakes. TRAIGA also establishes the Texas Artificial Intelligence Council and creates a regulatory sandbox program. The Texas Attorney General is charged with enforcement. It has received attention as one of the first comprehensive AI-related laws enacted by a U.S. state. Legal analysts have compared it to the European Union (EU) Artificial Intelligence Act and the Colorado AI Act, noting its intent-based discrimination standard and narrower scope relative to those frameworks. == Background == In June 2023, Texas Governor Greg Abbott signed House Bill 2060, which created an Artificial Intelligence Advisory Council within the Texas Department of Information Resources. The Council was tasked with monitoring the use of AI systems across state government. Its membership included representatives from law enforcement, academia, and the legal profession. After submitting a report to state policymakers, the Council was disbanded in December 2024. Separately, the Texas House Select Committee on Artificial Intelligence and Emerging Technologies was created in 2023 to examine the political and social implications of artificial intelligence. Among its recommendations was the creation of a regulatory sandbox to allow for controlled testing of AI systems. This recommendation informed the regulatory sandbox provision included in TRAIGA. == History == In December 2024, Representative Capriglione introduced House Bill 1709, the Texas Responsible Artificial Intelligence Governance Act. The bill sought to create a statewide framework for artificial intelligence, including transparency requirements for companies deploying AI systems, restrictions on certain uses of AI, and the creation of a regulatory sandbox. Modeled in part on the EU Artificial Intelligence Act and the Colorado AI Act, House Bill 1709 focused on "high-risk" AI systems and included provisions addressing private sector liability. House Bill 1709 did not advance during the legislative session. Industry stakeholders raised concerns that several provisions were overly burdensome. The bill informed the development of a revised proposal, House Bill 149, also titled the Texas Responsible Artificial Intelligence Governance Act. The revised version removed requirements for private companies to notify consumers when they interact with AI systems and to conduct impact assessments, among other provisions. In April 2025, an amended version of House Bill 149 passed the Texas House of Representatives and was referred to the Senate Committee on Business and Commerce. The bill later received approval from both chambers, where the House voted on amendments adopted by the Senate. On May 31, 2025, the state legislature passed House Bill 149, one of several AI-related bills considered during the legislative session. Governor Abbott signed TRAIGA into law on June 22, 2025. During the legislative process, a proposed federal moratorium on state-level AI regulation initially raised questions about the enforceability of state AI laws, including TRAIGA. At the time of signing, Governor Abbott stated that Texas would ensure compliance with applicable federal requirements. In July 2025, the United States Senate voted to remove the proposed moratorium from federal legislation. The Act took effect on January 1, 2026. == Provisions == === Definitions and scope === TRAIGA applies to AI developers and deployers that advertise or conduct business in Texas, develop products used by Texas residents, or develop or deploy AI systems within the state. The Act also applies to Texas state and local government entities. The Act defines a developer as a person who develops an AI system and a deployer as one who deploys an AI system in Texas. Consumers are defined as Texas residents. The Act defines an artificial intelligence system as a machine-based system that "infers from the inputs the system receives how to generate outputs, including content, decisions, predictions, or recommendations, that can influence physical or virtual environments." === Government use === The Act requires government agencies to provide consumers with plain language notices before interacting with AI systems. It also prohibits government agencies from using artificial intelligence systems to assign social scores to consumers. It also restricts the use of AI systems to identify individuals using biometric data without the individual’s consent. === Prohibitions === The Act prohibits the development or deployment of artificial intelligence systems intended to cause harm, self-harm, or criminal activity. It also prohibits the development or deployment of AI systems designed to violate constitutional rights or unlawfully discriminate based on protected classes. In addition, the Act prohibits the development or deployment of AI systems that are intended to produce or distribute child sexual abuse material or unlawful deepfakes. === Enforcement === Enforcement authority under the Act rests with the Texas Attorney General. The Act does not create a private right of action. The Act requires the Texas Attorney General to create an online complaint system where consumers may submit allegations of potential violations. The Attorney General can investigate complaints received through this system and may request information relevant to the operation of an AI system, including information about training data. Before initiating an enforcement action, the Attorney General must provide a written notice to the alleged violator, who is then provided with a 60-day period to cure the alleged violation. === Penalties === If a violation is not cured, the Act authorizes civil penalties. Penalties range from $10,000 to $12,000 per curable violation and from $80,000 to $200,000 per non-curable violation. The Act also authorizes additional penalties of $2,000 to $40,000 for each day the violation continues. If the Attorney General determines that a person certified or licensed by a state agency has violated the Act and recommends enforcement, the relevant agency may impose additional administrative sanctions, including license suspension or further monetary penalties. === Safe harbor === The Act provides an affirmative defense for AI developers and deployers who identify potential violations through internal testing or auditing or who demonstrate compliance with National Institute of Standards and Technology (NIST)'s Artificial Intelligence Risk Management Framework or a comparable risk management framework. The Act also affords protection to developers and deployers when a third party uses their AI systems in a way that violates the Act. === Texas Artificial Intelligence Council === The Act creates the Texas Artificial Intelligence Council to assist the state legislatures in evaluating artificial intelligence policy and oversight. The Council is charged with developing recommendations for state agencies regarding the use of AI systems and with overseeing the regulatory sandbox. TRAIGA gives the Council the ability to organize AI-related training for state entities and issue reports concerning artificial intelligence. The Council does not have binding rulemaking authority. The Council consists of seven members appointed by the governor, the lieutenant governor, and the speaker of the Texas House of Representatives. === Regulatory sandbox === The Act directs the Texas Department of Information Resources to create a regulatory sandbox program that allows participants to test AI systems under state supervision in a modified regulatory setting. To join the program, companies must submit applications that describe their AI systems and intended use. Approved participants may operate within the sandbox for up to 36 months. During that period, the Attorney General is restricted from initiating enforcement actions for certain categories of violations. == Reception == === Support === During legislative testimony, the Texas Public Policy Foundation stated that TRAIGA would benefit Texas businesses by reducing legal ambiguity and creating clearer compliance standards. Representatives of business groups also expressed support, stating that the Act would not impose overly burdensome regulations. The consum
Color quantization
In computer graphics, color quantization or color image quantization is quantization applied to color spaces; it is a process that reduces the number of distinct colors used in an image, usually with the intention that the new image should be as visually similar as possible to the original image. Computer algorithms to perform color quantization on bitmaps have been studied since the 1970s. Color quantization is critical for displaying images with many colors on devices that can only display a limited number of colors, usually due to memory limitations, and enables efficient compression of certain types of images. The name "color quantization" is primarily used in computer graphics research literature; in applications, terms such as optimized palette generation, optimal palette generation, or decreasing color depth are used. Some of these are misleading, as the palettes generated by standard algorithms are not necessarily the best possible. == Algorithms == Most standard techniques treat color quantization as a problem of clustering points in three-dimensional space, where the points represent colors found in the original image and the three axes represent the three color channels. Almost any three-dimensional clustering algorithm can be applied to color quantization, and vice versa. After the clusters are located, typically the points in each cluster are averaged to obtain the representative color that all colors in that cluster are mapped to. The three color channels are usually red, green, and blue, but another popular choice is the Lab color space, in which Euclidean distance is more consistent with perceptual difference. The most popular algorithm by far for color quantization, invented by Paul Heckbert in 1979, is the median cut algorithm. Many variations on this scheme are in use. Before this time, most color quantization was done using the population algorithm or population method, which essentially constructs a histogram of equal-sized ranges and assigns colors to the ranges containing the most points. A more modern popular method is clustering using octrees, first conceived by Gervautz and Purgathofer and improved by Xerox PARC researcher Dan Bloomberg. If the palette is fixed, as is often the case in real-time color quantization systems such as those used in operating systems, color quantization is usually done using the "straight-line distance" or "nearest color" algorithm, which simply takes each color in the original image and finds the closest palette entry, where distance is determined by the distance between the two corresponding points in three-dimensional space. In other words, if the colors are ( r 1 , g 1 , b 1 ) {\displaystyle (r_{1},g_{1},b_{1})} and ( r 2 , g 2 , b 2 ) {\displaystyle (r_{2},g_{2},b_{2})} , we want to minimize the Euclidean distance: ( r 1 − r 2 ) 2 + ( g 1 − g 2 ) 2 + ( b 1 − b 2 ) 2 . {\displaystyle {\sqrt {(r_{1}-r_{2})^{2}+(g_{1}-g_{2})^{2}+(b_{1}-b_{2})^{2}}}.} This effectively decomposes the color cube into a Voronoi diagram, where the palette entries are the points and a cell contains all colors mapping to a single palette entry. There are efficient algorithms from computational geometry for computing Voronoi diagrams and determining which region a given point falls in; in practice, indexed palettes are so small that these are usually overkill. Color quantization is frequently combined with dithering, which can eliminate unpleasant artifacts such as banding that appear when quantizing smooth gradients and give the appearance of a larger number of colors. Some modern schemes for color quantization attempt to combine palette selection with dithering in one stage, rather than perform them independently. A number of other much less frequently used methods have been invented that use entirely different approaches. The Local K-means algorithm, conceived by Oleg Verevka in 1995, is designed for use in windowing systems where a core set of "reserved colors" is fixed for use by the system and many images with different color schemes might be displayed simultaneously. It is a post-clustering scheme that makes an initial guess at the palette and then iteratively refines it. In the early days of color quantization, the k-means clustering algorithm was deemed unsuitable because of its high computational requirements and sensitivity to initialization. In 2011, M. Emre Celebi reinvestigated the performance of k-means as a color quantizer. He demonstrated that an efficient implementation of k-means outperforms a large number of color quantization methods. The high-quality but slow NeuQuant algorithm reduces images to 256 colors by training a Kohonen neural network "which self-organises through learning to match the distribution of colours in an input image. Taking the position in RGB-space of each neuron gives a high-quality colour map in which adjacent colours are similar." It is particularly advantageous for images with gradients. Finally, one of the newer methods is spatial color quantization, conceived by Puzicha, Held, Ketterer, Buhmann, and Fellner of the University of Bonn, which combines dithering with palette generation and a simplified model of human perception to produce visually impressive results even for very small numbers of colors. It does not treat palette selection strictly as a clustering problem, in that the colors of nearby pixels in the original image also affect the color of a pixel. See sample images. == History and applications == In the early days of PCs, it was common for video adapters to support only 2, 4, 16, or (eventually) 256 colors due to video memory limitations; they preferred to dedicate the video memory to having more pixels (higher resolution) rather than more colors. Color quantization helped to justify this tradeoff by making it possible to display many high color images in 16- and 256-color modes with limited visual degradation. Many operating systems automatically perform quantization and dithering when viewing high color images in a 256 color video mode, which was important when video devices limited to 256 color modes were dominant. Modern computers can now display millions of colors at once, far more than can be distinguished by the human eye, limiting this application primarily to mobile devices and legacy hardware. Nowadays, color quantization is mainly used in GIF and PNG images. GIF, for a long time the most popular lossless and animated bitmap format on the World Wide Web, only supports up to 256 colors, necessitating quantization for many images. Some early web browsers constrained images to use a specific palette known as the web colors, leading to severe degradation in quality compared to optimized palettes. PNG images support 24-bit color, but can often be made much smaller in filesize without much visual degradation by application of color quantization, since PNG files use fewer bits per pixel for palettized images. The infinite number of colors available through the lens of a camera is impossible to display on a computer screen; thus converting any photograph to a digital representation necessarily involves some quantization. Practically speaking, 24-bit color is sufficiently rich to represent almost all colors perceivable by humans with sufficiently small error as to be visually identical (if presented faithfully), within the available color space. However, the digitization of color, either in a camera detector or on a screen, necessarily limits the available color space. Consequently there are many colors that may be impossible to reproduce, regardless of how many bits are used to represent the color. For example, it is impossible in typical RGB color spaces (common on computer monitors) to reproduce the full range of green colors that the human eye is capable of perceiving. With the few colors available on early computers, different quantization algorithms produced very different-looking output images. As a result, a lot of time was spent on writing sophisticated algorithms to be more lifelike. === Quantization for image compression === Many image file formats support indexed color. A whole-image palette typically selects 256 "representative" colors for the entire image, where each pixel references any one of the colors in the palette, as in the GIF and PNG file formats. A block palette typically selects 2 or 4 colors for each block of 4x4 pixels, used in BTC, CCC, S2TC, and S3TC. === Editor support === Many bitmap graphics editors contain built-in support for color quantization, and will automatically perform it when converting an image with many colors to an image format with fewer colors. Most of these implementations allow the user to set exactly the number of desired colors. Examples of such support include: Photoshop's Mode→Indexed Color function supplies a number of quantization algorithms ranging from the fixed Windows system and Web palettes to the proprietary Local and Global algorithms for generating palettes suited to a particu
LIFER/LADDER
LIFER/LADDER was one of the first database natural language processing systems. It was designed as a natural language interface to a database of information about US Navy ships. This system, as described in a paper by Hendrix (1978), used a semantic grammar to parse questions and query a distributed database. It was implemented in Interlisp. The LIFER/LADDER system could only support simple one-table queries or multiple table queries with easy join conditions. Some examples of queries it could accept: What are the length, width, and draft of the Kitty Hawk? When will Reeves achieve readiness rating C2? What is the nearest ship to Naples with a doctor on board? What ships are carrying cargo for the United States? Where are they going? Print the American cruisers’ current positions and states of readiness?