AI Data Jobs

AI Data Jobs — independent reviews, comparisons, pricing and step-by-step guides on Aizhi.

• 

  Verbot

  The Verbot (short for Verbal-Robot) was a chatbot program and artificial intelligence software development kit (SDK) designed for Windows and web platforms. == Early beginning == The origin of verbot traces back to Michael Mauldin's research during his time as a graduate student and post-doctoral fellow at Carnegie Mellon University. The creative foundation also stems from Peter Plantec's work in personality psychology and art direction. === Historic outline === In 1994, Michael Loren Mauldin, founder of Lycos, Inc., developed a prototype chatbot, Julia, which competed in the internationally known Turing test, for the coveted Loebner Prize. The Turing test matches computer scientist judges against machines to see if they can distinguish a computer from a real human. Julia was refined and developed, and in 1997, Dr. Mauldin and Peter Plantec, a clinical psychologist and animator, formed Virtual Personalities, Inc. (now Conversive, Inc.) in order to create a virtual human interface that would incorporate real-time animation as well as speech and natural language processing. The initial release, a stand-alone virtual person called Sylvie, was beta-tested to the public. This release was well received, and finally, after several versions, the production release (deemed version 3) of the Verbally Enhanced Software Robot, or Verbot, was deployed in fall 2000. The grandfather of all Verbots is Rog-O-Matic, which, although it could not talk, could and did explore a virtual world. Julia has been active on the internet in one form or another since 1989. A close cousin of Julia is Lycos, a robot that explores the World Wide Web and answers questions about it. Sylvie was the first Verbot with a face and a voice. Sylvie was the first Virtual Human with advanced, flexible interfacing capability. === Beginnings === The Virtual Personalities story goes back to 1978, where Mauldin was attending Rice University. Fascinated by the idea of ELIZA, he proceeded to write a program called "PET" for his 8 kilobyte Commodore PET Computer. PET included simple induction as a way to post new information, for example: Subject: I like my friend (later) Subject: I like food. PET: I have heard that food is your friend. Meanwhile, Plantec was separately designing a personality for "Entity", a theoretical virtual human that would interact comfortably with humans without pretending to be one. At that time the technology was not advanced enough to realize Entity. Mauldin got so involved with this that he majored in Computer Science and minored in Linguistics. === Rogue === In the late seventies and early eighties, a popular computer game at universities was Rogue, an implementation of Dungeons and Dragons where the player would descend 26 levels in a randomly created dungeon, fighting monsters, gathering treasure, and searching for the elusive "Amulet of Yendor". Mauldin was one of four grad students who devoted a large amount of time to building a program called "Rog-O-Matic" capable of retrieving the amulet and emerging victorious from the dungeon. === TinyMUD === In 1989, when James Aspnes at Carnegie Mellon created the first TinyMUD (a descendant of MUD and AberMUD), Mauldin was one of the first to create a computer player that would explore the text-based world of TinyMUD. But his first robot, Gloria, gradually accreted more and more linguistic ability, to the point that it could pass the "unsuspecting" Turing test. In this version of the test, the human has no reason to suspect that one of the other occupants of the room is controlled by a computer, and so is more polite and asks fewer probing questions. The second generation of Mauldin's TinyMUD robots was Julia, created on Jan. 8, 1990. Julia slowly developed into a more and more capable conversational agent, and assumed useful duties in the TinyMUD world, including tour guide, information assistant, note-taker, and message-relayer. She could even play the card game hearts along with the other human players. In 1991, Julia attended the first Loebner Prize contest in Boston, Massachusetts. Although she only finished third, she was ranked by one judge as more human than one of the human confederates, winning a coveted certificate of humanness in the world's first restricted Turing test. Julia continued to log in to various TinyMUD's and TinyMucks for the next seven years, and chatted with hundreds of people a month over the internet. === Lycos === Julia's job was to explore a virtual world consisting of pages of textual descriptions, with links between them, and to construct an internal map of that world and answer questions about it (including path information such as the shortest route from one room to another, and matching information, such as which rooms contained a certain kind of object or textual description). It was therefore only a very short cognitive leap from Julia to Lycos, another robotic agent that explores a virtual world made of hyperlinked pages of text, and which answers questions about those pages. Sylvie was born and her abilities were expanded greatly to include interfacing with computers and control systems via her serial ports. === Sylvie === Sylvie was the first intelligent animated virtual human. She was designed both as a conversation agent and as a virtual human interface that would form a bridge between the two. She became more popular as a conversation agent, but her designers believe she serves as a prototype for future virtual human interface design that will help us all cope with the increasing complexity of technology. As an aside, Plantec noticed that a large number of Sylvies have been sold in Southeast Asia. Upon investigation, he found out that students had discovered a "test" mode that would allow them to type in English sentences that Sylvie would pronounce in her somewhat stylized English. == Ownership == In 1997, Dr. Mauldin and Peter Plantec formed Virtual Personalities, Inc. to create Natural Language Processing solutions for companies. In 2001 Virtual Personalities, Inc. became Conversive, Inc. to reflect the focus on providing Customer Service and Marketing to the Enterprise Market. In late 2012 Avaya, Inc. acquired Conversive's assets including Verbots. == Verbot versions == The Verbot 4 version was created and released in 2004. In 2005 Version 4.1 of the Verbot Software was released with many feature enhancements and bug fixes, including built-in support for embedding C# code in outputs and conditionals. In early 2006 Conversive launched Verbots Online allowing Verbot 4 users to upload their knowledge and show off their bots to the world. In 2009 Version 5 was released, completely free and fully featured. In early 2012 the last version of Verbot, 5.0.1.2, was released to the general public with support for Windows 7. Later in 2012 Verbots Online completely shut down. == Verbots today == Verbots.com, its community of users, and its forums no longer exist, but the software and users can still be found. There has been no active development since the early 2012 release of Verbot 5.0.1.2.

  Read more →
• 

  Block swap algorithms

  In computer algorithms, block swap algorithms swap two regions of elements of an array. It is simple to swap two non-overlapping regions of an array of equal size. However, it is not as simple to swap two contiguous regions of an array of unequal sizes (algorithms that perform such swapping are called rotation algorithms). A few well-known algorithms can accomplish this: Bentley's juggling (also known as the dolphin algorithm), Gries-Mills rotation, triple reversal algorithm, conjoined triple reversal algorithm (also known as the trinity rotation) and Successive rotation. == Triple reversal algorithm == The triple reversal algorithm is the simplest to explain, using rotations. A rotation is an in-place reversal of array elements. This method swaps two elements of an array from outside in within a range. The rotation works for an even or odd number of array elements. The reversal algorithm uses three in-place rotations to accomplish an in-place block swap: Rotate region A Rotate region B Rotate region AB Where A and B are adjacent regions of an array that together form the region AB. Gries-Mills and reversal algorithms perform better than Bentley's juggling, because of their cache-friendly memory access pattern behavior. The triple reversal algorithm parallelizes well, because rotations can be split into sub-regions, which can be rotated independently of others.

  Read more →
• 

  Single customer view

  A single customer view is an aggregated, consistent and holistic representation of the data held by an organisation about its customers that can be viewed in one place, such as a single page. The advantage to an organisation of attaining this unified view comes from the ability it gives to analyse past behaviour in order to better target and personalise future customer interactions. A single customer view is also considered especially relevant where organisations engage with customers through multichannel marketing, since customers expect those interactions to reflect a consistent understanding of their history and preferences. However, some commentators have challenged the idea that a single view of customers across an entire organisation is either natural or meaningful, proposing that the priority should instead be consistency between the multiple views that arise in different contexts. Where representations of a customer are held in more than one data set, achieving a single customer view can be difficult: firstly because customer identity must be traceable between the records held in those systems, and secondly because anomalies or discrepancies in the customer data must be data cleansed for data quality. As such, the acquisition by an organisation of a single customer view is one potential outcome of successful master data management. Since 31 December, 2010, maintaining a single customer view, and submitting it within 72 hours, has become mandatory for financial institutions in the United Kingdom due to new rules introduced by the Financial Services Compensation Scheme.

  Read more →
• 

  Chandy–Misra–Haas algorithm resource model

  The Chandy–Misra–Haas algorithm resource model checks for deadlock in a distributed system. It was developed by K. Mani Chandy, Jayadev Misra and Laura M. Haas. == Locally dependent == Consider the n processes P1, P2, P3, P4, P5,, ... ,Pn which are performed in a single system (controller). P1 is locally dependent on Pn, if P1 depends on P2, P2 on P3, so on and Pn−1 on Pn. That is, if P 1 → P 2 → P 3 → … → P n {\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}} , then P 1 {\displaystyle P_{1}} is locally dependent on P n {\displaystyle P_{n}} . If P1 is said to be locally dependent to itself if it is locally dependent on Pn and Pn depends on P1: i.e. if P 1 → P 2 → P 3 → … → P n → P 1 {\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}\rightarrow P_{1}} , then P 1 {\displaystyle P_{1}} is locally dependent on itself. == Description == The algorithm uses a message called probe(i,j,k) to transfer a message from controller of process Pj to controller of process Pk. It specifies a message started by process Pi to find whether a deadlock has occurred or not. Every process Pj maintains a boolean array dependent which contains the information about the processes that depend on it. Initially the values of each array are all "false". === Controller sending a probe === Before sending, the probe checks whether Pj is locally dependent on itself. If so, a deadlock occurs. Otherwise it checks whether Pj, and Pk are in different controllers, are locally dependent and Pj is waiting for the resource that is locked by Pk. Once all the conditions are satisfied it sends the probe. === Controller receiving a probe === On the receiving side, the controller checks whether Pk is performing a task. If so, it neglects the probe. Otherwise, it checks the responses given Pk to Pj and dependentk(i) is false. Once it is verified, it assigns true to dependentk(i). Then it checks whether k is equal to i. If both are equal, a deadlock occurs, otherwise it sends the probe to next dependent process. == Algorithm == In pseudocode, the algorithm works as follows: === Controller sending a probe === if Pj is locally dependent on itself then declare deadlock else for all Pj,Pk such that (i) Pi is locally dependent on Pj, (ii) Pj is waiting for 'Pk and (iii) Pj, Pk are on different controllers. send probe(i, j, k). to home site of Pk === Controller receiving a probe === if (i)Pk is idle / blocked (ii) dependentk(i) = false, and (iii) Pk has not replied to all requests of to Pj then begin "dependents""k"(i) = true; if k == i then declare that Pi is deadlocked else for all Pa,Pb such that (i) Pk is locally dependent on Pa, (ii) Pa is waiting for 'Pb and (iii) Pa, Pb are on different controllers. send probe(i, a, b). to home site of Pb end == Example == P1 initiates deadlock detection. C1 sends the probe saying P2 depends on P3. Once the message is received by C2, it checks whether P3 is idle. P3 is idle because it is locally dependent on P4 and updates dependent3(2) to True. As above, C2 sends probe to C3 and C3 sends probe to C1. At C1, P1 is idle so it update dependent1(1) to True. Therefore, deadlock can be declared. == Complexity == Suppose there are n {\displaystyle n} controllers and m {\displaystyle m} processes, at most m ( n − 1 ) / 2 {\displaystyle m(n-1)/2} messages need to be exchanged to detect a deadlock, with a delay of O ( n ) {\displaystyle O(n)} messages.

  Read more →
• 

  Amazon Elastic Compute Cloud

  Amazon Elastic Compute Cloud (EC2) is a part of Amazon's cloud-computing platform, Amazon Web Services (AWS), that allows users to rent virtual computers on which to run their own computer applications. EC2 encourages scalable deployment of applications by providing a web service through which a user can boot an Amazon Machine Image (AMI) to configure a virtual machine, which Amazon calls an "instance", containing any software desired. A user can create, launch, and terminate server-instances as needed, paying by the second for active servers – hence the term "elastic". EC2 provides users with control over the geographical location of instances that allows for latency optimization and high levels of redundancy. In November 2010, Amazon switched its own retail website platform to EC2 and AWS. == History == Amazon announced a limited public beta test of EC2 on August 25, 2006, offering access on a first-come, first-served basis. Amazon added two new instance types (Large and Extra-Large) on October 16, 2007. On May 29, 2008, two more types were added, High-CPU Medium and High-CPU Extra Large. There were twelve types of instances available. Amazon added three new features on March 27, 2008: static IP addresses, availability zones, and user-selectable kernels. On August 20, 2008, Amazon added Elastic Block Store (EBS). This provides persistent storage, a feature that had been lacking since the service was introduced. Amazon EC2 went into full production when it dropped the beta label on October 23, 2008. On the same day, Amazon announced the following features: a service level agreement for EC2, Microsoft Windows in beta form on EC2, Microsoft SQL Server in beta form on EC2, plans for an AWS management console, and plans for load balancing, autoscaling, and cloud monitoring services. These features were subsequently added on May 18, 2009. Amazon EC2 was developed mostly by a team in Cape Town, South Africa led by Chris Pinkham. Pinkham provided the initial architecture guidance for EC2 and then built the team and led the development of the project along with Willem van Biljon. == Instance types == Initially, EC2 used Xen virtualization exclusively. However, on November 6, 2017, Amazon announced the new C5 family of instances that were based on a custom architecture around the KVM hypervisor, called Nitro. Each virtual machine, called an "instance", functions as a virtual private server. Amazon sizes instances based on "Elastic Compute Units". The performance of otherwise identical virtual machines may vary. On November 28, 2017, AWS announced a bare-metal instance, a departure from exclusively offering virtualized instance types. As of January 2019, the following instance types were offered: General Purpose: A1, T3, T2, M5, M5a, M4, T3a Compute Optimized: C5, C5n, C4 Memory Optimized: R5, R5a, R4, X1e, X1, High Memory, z1d Accelerated Computing: P3, P2, G3, F1 Storage Optimized: H1, I3, D2 As of April 2018, the following payment methods by instance were offered: On-demand: pay by the hour without commitment. Reserved: rent instances with one-time payment receiving discounts on the hourly charge. Spot: bid-based service: runs the jobs only if the spot price is below the bid specified by bidder. The spot price is claimed to be supply-demand based, however a 2011 study concluded that the price was generally not set to clear the market, but was dominated by an undisclosed reserve price. In 2025, AWS expanded EC2 with the compute-optimized C8gn family, powered by Graviton4 and offering up to 600 Gbit/s network bandwidth (about 30% higher compute performance than C7gn), and introduced G6f fractional-GPU instances that let customers provision one-eighth, one-quarter, or one-half of an NVIDIA L4 GPU for right-sized graphics/ML workloads. === Cost === As of April 2018, Amazon charged about $0.0058 per hour ($4.176 per month) for the smallest "Nano Instance" (t2.nano) virtual machine running Linux or Windows. Storage-optimized instances cost as much as $4.992 per hour (i3.16xlarge). "Reserved" instances can go as low as $2.50 per month for a three-year prepaid plan. The data transfer charge ranges from free to $0.12 per gigabyte, depending on the direction and monthly volume (inbound data transfer is free on all AWS services). EC2 costs can be analyzed using the Amazon Cost and Usage Report. There are many different cost categories for EC2 including: hourly Instance Charges, Data Transfer, EBS Volumes, EBS Volume Snapshots, and Nat Gateway. === Free tier === As of December 2010 Amazon offered a bundle of free resource credits to new account holders. The credits are designed to run a "micro" sized server, storage (EBS), and bandwidth for one year. Unused credits cannot be carried over from one month to the next. === Reserved instances === Reserved instances enable EC2 or RDS service users to reserve an instance for one or three years. The corresponding hourly rate charged by Amazon to operate the instance is 35 to 75% lower than the rate charged for on-demand instances. Reserved instances can be purchased with three different payment options: All Upfront, Partial Upfront and No Upfront. The different purchase options allow for different structuring of payment models, with a larger discount given to customers that pay their reservation upfront. Reserved Instances are purchased based on a resource commitment. These reservations are made based on an instance type and a count of that instance type. For example, you could reserve 100 i3.large instances for a 3-year term. In September 2016, AWS announced several enhancements to Reserved instances, introducing a new feature called scope and a new reservation type called a Convertible. In October 2017, AWS announced the allowance to subdivide the instances purchased for more flexibility. === Spot instances === Cloud providers maintain large amounts of excess capacity they have to sell or risk incurring losses. Amazon EC2 Spot instances are spare compute capacity in the AWS cloud available at up to 90% discount compared to On-Demand prices. As a trade-off, AWS offers no SLA on these instances and customers take the risk that it can be interrupted with only two minutes of notification when Amazon needs the capacity back. Researchers from the Israeli Institute of Technology found that "they (Spot instances) are typically generated at random from within a tight price interval via a dynamic hidden reserve price". Some companies, like Spotinst, are using machine learning to predict spot interruptions up to 15 minutes in advance. === Savings Plans === In November 2019, Amazon announced Savings Plans. Savings Plans are an alternative to Reserved Instances that come in two different plan types: Compute Savings Plans and EC2 Instances Savings Plans. Compute Savings Plans allow an organization to commit to EC2 and Fargate usage with the freedom to change region, family, size, availability zone, OS and tenancy inside the lifespan of the commitment. EC2 Instance Savings plans provide a larger discount than Compute Savings Plans but are less flexible meaning a user must commit to individual instance families within a region to take advantage, but with the freedom to change instances within the family in that region. AWS uses the Cost Explorer to automatically calculate recommendations for the commitments you should make how that commitment will look like as a monthly charge on your AWS bill. AWS Savings Plans are purchased based on hourly spend commitment. This hourly commitment is made using the discounted pricing of the savings plan you are purchasing. For example, you could commit to spending $5 per hour, on a Compute Savings Plan, for a 3-year term. == Features == === Operating systems === When it launched in August 2006, the EC2 service offered Linux and later Sun Microsystems' OpenSolaris and Solaris Express Community Edition. In October 2008, EC2 added the Windows Server 2003 and Windows Server 2008 operating systems to the list of available operating systems. In March 2011, NetBSD AMIs became available. In November 2012, Windows Server 2012 support was added. Since 2006, Colin Percival, a FreeBSD developer and Security Officer, solicited Amazon to add FreeBSD. In November 2012, Amazon officially supported running FreeBSD in EC2. The FreeBSD/EC2 platform is maintained by Percival who also developed the secure deduplicating Amazon S3-cloud based backup service Tarsnap. Amazon has their own Linux distribution based on Fedora and Red Hat Enterprise Linux as a low cost offering known as the Amazon Linux AMI. Version 2013.03 included: Linux kernel, Java OpenJDK Runtime Environment and GNU Compiler Collection. On November 30, 2020, Amazon announced that it would be adding macOS to the EC2 service. Initial support was announced for macOS Mojave and macOS Catalina running on Mac Mini. === Managed Container and Kubernetes Services === Amazon Elastic Container Registry (ECR) is a Docker registry service for Amazon EC2

  Read more →
• 

  Vocabulary-based transformation

  In metadata, a vocabulary-based transformation (VBT) is a transformation aided by the use of a semantic equivalence statements within a controlled vocabulary. Many organizations today require communication between two or more computers. Although many standards exist to exchange data between computers such as HTML or email, there is still much structured information that needs to be exchanged between computers that is not standardized. The process of mapping one source of data into another is often a slow and labor-intensive process. VBT is a possible way to avoid much of the time and cost of manual data mapping using traditional extract, transform, load technologies. == History == The term vocabulary-based transformation was first defined by Roy Shulte of the Gartner Group around May 2003 and appeared in annual "hype-cycle" for integration. == Application == VBT allows computer systems integrators to more automatically "look up" the definitions of data elements in a centralized data dictionary and use that definition and the equivalent mappings to transform that data element into a foreign namespace. The Web Ontology Language (OWL) language also support three semantic equivalence statements. == Companies or products == IONA Technologies Contivo and Delta by Liaison Technologies enLeague Systems ItemField Unicorn Solutions Vitria Technology Zonar

  Read more →
• 

  Information behavior

  Information behavior is a field of information science research that seeks to understand the way people search for and use information in various contexts. It can include information seeking and information retrieval, but it also aims to understand why people seek information and how they use it. The term 'information behavior' was coined by Thomas D. Wilson in 1982 and sparked controversy upon its introduction. The term has now been adopted and Wilson's model of information behavior is widely cited in information behavior literature. In 2000, Wilson defined information behavior as "the totality of human behavior in relation to sources and channels of information". A variety of theories of information behavior seek to understand the processes that surround information seeking. An analysis of the most cited publications on information behavior during the early 21st century shows its theoretical nature. Information behavior research can employ various research methodologies grounded in broader research paradigms from psychology, sociology and education. In 2003, a framework for information-seeking studies was introduced that aims to guide the production of clear, structured descriptions of research objects and positions information-seeking as a concept within information behavior. == Concepts of information behavior == === Information need === Information need is a concept introduced by Wilson. Understanding the information need of an individual involved three elements: Why the individual decides to look for information, What purpose the information they find will serve, and How the information is used once it is retrieved === Information-seeking behavior === Information-seeking behavior is a more specific concept of information behavior. It specifically focuses on searching, finding, and retrieving information. Information-seeking behavior research can focus on improving information systems or, if it includes information need, can also focus on why the user behaves the way they do. A review study on information search behavior of users highlighted that behavioral factors, personal factors, product/service factors and situational factors affect information search behavior. Information-seeking behavior can be more or less explicit on the part of users: users might seek to solve some task or to establish some piece of knowledge which can be found in the data in question, or alternatively the search process itself is part of the objective of the user, in use cases for exploring visual content or for familiarising oneself with the content of an information service. In the general case, information-seeking needs to be understood and analysed as a session rather than as a one-off transaction with a search engine, and in a broader context which includes user high-level intentions in addition to the immediate information need. === Information use === An information need is the recognition that a gap exists in one’s knowledge, prompting a desire to seek information to fill that gap. It often arises when a person encounters a problem or question they cannot resolve with their current understanding. === Information poverty and barriers === Introduced by Elfreda Chatman in 1987, information poverty is informed by the understanding that information is not equally accessible to all people. Information poverty does not describe a lack of information, but rather a worldview in which one's own experiences inside their own small world may create a distrust in the information provided by those outside their own lived experiences. == Metatheories == In Library and Information Science (LIS), a metatheory is described "a set of assumptions that orient and direct theorizing about a given phenomenon". Library and information science researchers have adopted a number of different metatheories in their research. A common concern among LIS researchers, and a prominent discussion in the field, is the broad spectrum of theories that inform the study of information behavior, information users, or information use. This variation has been noted as a cause of concern because it makes individual studies difficult to compare or synthesize if they are not guided by the same theory. This sentiment has been expressed in studies of information behavior literature from the early 1980s and more recent literature reviews have declared it necessary to refine their reviews to specific contexts or situations due to the sheer breadth of information behavior research available. Below are descriptions of some, but not all, metatheories that have guided LIS research. === Cognitivist approach === A cognitive approach to understanding information behavior is grounded in psychology. It holds the assumption that a person's thinking influences how they seek, retrieve, and use information. Researchers that approach information behavior with the assumption that it is influenced by cognition, seek to understand what someone is thinking while they engage in information behavior and how those thoughts influence their behavior. Wilson's attempt to understand information-seeking behavior by defining information need includes a cognitive approach. Wilson theorizes that information behavior is influenced by the cognitive need of an individual. By understanding the cognitive information need of an individual, we may gain insight into their information behavior. Nigel Ford takes a cognitive approach to information-seeking, focusing on the intellectual processes of information-seeking. In 2004, Ford proposed an information-seeking model using a cognitive approach that focuses on how to improve information retrieval systems and serves to establish information-seeking and information behavior as concepts in and of themselves, rather than synonymous terms. === Constructionist approach === The constructionist approach to information behavior has roots in the humanities and social sciences. It relies on social constructionism, which assumes that a person's information behavior is influenced by their experiences in society. In order to understand information behavior, constructionist researchers must first understand the social discourse that surrounds the behavior. The most popular thinker referenced in constructionist information behavior research is Michel Foucault, who famously rejected the concept of a universal human nature. The constructionist approach to information behavior research creates space for contextualizing the behavior based on the social experiences of the individual. One study that approaches information behavior research through the social constructionist approach is a study of the information behavior of a public library knitting group. The authors use a collectivist theory to frame their research, which denies the universality of information behavior and focuses on "understanding the ways that discourse communities collectively construct information needs, seeking, sources, and uses". === Constructivist approach === The constructivist approach is born out of education and sociology in which, "individuals are seen as actively constructing an understanding of their worlds, heavily influenced by the social world(s) in which they are operating". Constructivist approaches to information behavior research generally treat the individual's reality as constructed within their own mind rather than built by the society in which they live. The constructivist metatheory makes space for the influence of society and culture with social constructivism, "which argues that, while the mind constructs reality in its relationship to the world, this mental process is significantly informed by influences received from societal conventions, history and interaction with significant others". == Theories == A common concern among LIS researchers, and a prominent discussion in the field, is the broad spectrum of theories that inform LIS research. This variation has been noted as a cause of concern because it makes individual studies difficult to compare if they are not guided by the same theory. Recent studies have shown that the impact of these theories and theoretical models is very limited. LIS researchers have applied concepts and theories from many disciplines, including sociology, psychology, communication, organizational behavior, and computer science. === Wilson's theory of information behavior (1981) === The term was coined by Thomas D. Wilson in his 1981 paper, on the grounds that the current term, 'information needs' was unhelpful since 'need' could not be directly observed, while how people behaved in seeking information could be observed and investigated. However, there is increasing work in the information-searching field that is relating behaviors to underlying needs. In 2000, Wilson described information behavior as the totality of human behavior in relation to sources and channels of information, including both active and passive information-seeking, and information use. He described info

  Read more →
• 

  Environmental informatics

  Environmental informatics is the science of information applied to environmental science. As such, it provides the information processing and communication infrastructure to the interdisciplinary field of environmental sciences aiming at data, information and knowledge integration, the application of computational intelligence to environmental data as well as the identification of environmental impacts of information technology. Environmental informatics thus acts as a bridge, providing an interdisciplinary means of analysing, describing and understanding the complex interactions between humans, nature and technology. Since each field of applied computer science has its own subject matter, terminology and methods, specialised disciplines, such as environmental, bio- and geoinformatics have emerged, each of which combines computer science with a specific field of application such as environmental, bio- or geosciences. Environmental informatics, bioinformatics and geoinformatics all deal with computer-based processing of environmental phenomena. However, environmental informatics is the only field that pursues normative goals (e.g., political goals of environmental protection, environmental planning, and sustainability). This also influences the choice of methods. This also distinguishes it from application areas such as numerical weather prediction, which is considered an early and important example of computer simulation of environmental phenomena. The UK Natural Environment Research Council defines environmental informatics as the "research and system development focusing on the environmental sciences relating to the creation, collection, storage, processing, modelling, interpretation, display and dissemination of data and information." Kostas Karatzas defined environmental informatics as the "creation of a new 'knowledge-paradigm' towards serving environmental management needs." Karatzas argued further that environmental informatics "is an integrator of science, methods and techniques and not just the result of using information and software technology methods and tools for serving environmental engineering needs." Environmental informatics emerged in early 1990 in Central Europe. Current initiatives to effectively manage, share, and reuse environmental and ecological data are indicative of the increasing importance of fields like environmental informatics and ecoinformatics to develop the foundations for effectively managing ecological information. Examples of these initiatives are National Science Foundation Datanet projects, DataONE and Data Conservancy. == Subject matter and objectives == The subject of environmental informatics are environmental information systems (EIS). An EIS 'is a computer-based system that integrates and stores data collected about the natural environment and provides powerful methods for accessing and evaluating it.' This allows environmental data to be processed by computers for environmental protection, planning, research and technology. According to Jaeschke and Bossel, environmental informatics has three interrelated objectives: Environmental informatics serves to procure data and information for describing the state and development of the environment. Of particular importance is information that is needed to prevent or limit undesirable changes and to support desirable changes. Based on the evaluation and analysis of data, environmental informatics improves our understanding of the environment and the interactions between nature, technology and society. It thus supports environmentally relevant decisions. This enables the influence of development (system correction), the assessment of the effects and side effects of potential measures, and the creation of tools for the routine planning, implementation and monitoring of measures. == History == The simulation model World3, which formed the basis of the highly acclaimed study The Limits to Growth, is considered the starting point of environmental informatics. It incorporated environmental information, among other things, to calculate scenarios for global development. In the mid-1980s, interest grew in structuring environmental protection as an area of application for computer science. One of the first publications in German was the book Informatik im Umweltschutz. Anwendungen und Perspektiven (Computer science in environmental protection. Applications and perspectives) from 1986. The term 'environmental informatics' did not appear until around 1993, which is why the development of environmental informatics is usually referred to as having taken place in the 1990s. In 1993, the first university chair for environmental informatics was established in Cottbus. In 1994, the anthology Umweltinformatik. Informatikmethoden für Umweltschutz und Umweltforschung (Environmental Informatics: Informatics Methods for Environmental Protection and Environmental Research) was published. The development of environmental informatics was 'primarily initiated by German computer science.' In the English-speaking world, the volume Environmental Informatics was published in 1995, mainly based on the German anthology of 1994. An article in the conference proceedings of the World Computer Congress of the International Federation for Information Processing (IFIP) in Hamburg in 1994 describes the initial situation of environmental informatics as follows: 'On the one hand, we suffer from the huge amount of available data – people sometimes speak of data graveyards – on the other hand, the really relevant data may still be missing.' This statement indicates the need that led to the emergence of environmental informatics as a specialised discipline of applied computer science. Furthermore, the specific characteristics and processing requirements of environmental data necessitated the emergence of environmental informatics. The special features of environmental data include: The data structures required are highly heterogeneous due to specific processes and differing perspectives on environmental aspects (e.g., water protection, emission control, hazardous substances). In addition to the heterogeneity of the data, heterogeneous databases also play a role, as environmental data is often obtained and presented in an interdisciplinary manner. Obligations change frequently as a result of new legislation, whether regional (e.g. state regulations on water protection), national (e.g. federal emission control regulations) or international (e.g. Registration, Evaluation, Authorisation and Restriction of Chemicals|REACH). The objects represented are often multidimensional and, therefore, require complex geometric representation using curves or polygons. It is often necessary to process uncertain, imprecise or incomplete data, which is, for example, the result of extrapolations or forecasts. A new "knowledge paradigm" has emerged to meet the requirements of environmental management. Environmental informatics produces its own concepts, methods and techniques and is not merely the result of using information and communication technology methods and tools to meet environmental requirements. The development of environmental informatics since the 1990s has been significantly influenced by the newly established conferences EnviroInfo, ISESS and ITEE and is documented in the respective proceedings. Aspects of sustainability and sustainable development were increasingly integrated into environmental informatics after 2000, thereby expanding the field. In 2004, the Working Group on Sustainable Information Society of the Gesellschaft für Informatik e. V. (German Informatics Society, GI) published the Memorandum on a Sustainable Information Society, which formulates recommendations for an information society that is compatible with human, social and natural needs. Since 2007, environmental informatics has often been described in more detail as informatics for environmental protection, sustainable development and risk management. The increased focus on sustainability has also contributed to the formation of the research focus Information and Communications Technology for Sustainability (ICT4S) and to the emergence of the international conference ICT4S in 2013. ICT-ENSURE, the European Commission's funding measure for the establishment of a European research area on "ICT for Environmental Sustainability Research" (2008–2010), has also contributed to the structuring of environmental informatics. == Environmental informatics and sustainable development == Efforts to place environmental informatics within the context of sustainable development have been growing since 2000 and were significantly influenced by the Memorandum on a Sustainable Information Society. According to this Memorandum, the information society offers great but unevenly distributed opportunities for education, participation and intercultural understanding. In addition, the Memorandum highlighted the material and energy consumption of inf

  Read more →
• 

  Control-flow integrity

  Control-flow integrity (CFI) is a general term for computer security techniques that prevent a wide variety of malware attacks from redirecting the flow of execution (the control flow) of a program. == Background == A computer program commonly changes its control flow to make decisions and use different parts of the code. Such transfers may be direct, in that the target address is written in the code itself, or indirect, in that the target address itself is a variable in memory or a CPU register. In a typical function call, the program performs a direct call, but returns to the caller function using the stack – an indirect backward-edge transfer. When a function pointer is called, such as from a virtual table, we say there is an indirect forward-edge transfer. Attackers seek to inject code into a program to make use of its privileges or to extract data from its memory space. Before executable code was commonly made read-only, an attacker could arbitrarily change the code as it is run, targeting direct transfers or even do with no transfers at all. After W^X became widespread, an attacker wants to instead redirect execution to a separate, unprotected area containing the code to be run, making use of indirect transfers: one could overwrite the virtual table for a forward-edge attack or change the call stack for a backward-edge attack (return-oriented programming). CFI is designed to protect indirect transfers from going to unintended locations. == Techniques == Associated techniques include code-pointer separation (CPS), code-pointer integrity (CPI), stack canaries, shadow stacks (SS), and vtable pointer verification. These protections can be classified into either coarse-grained or fine-grained based on the number of targets restricted. A coarse-grained forward-edge CFI implementation, could, for example, restrict the set of indirect call targets to any function that may be indirectly called in the program, while a fine-grained one would restrict each indirect call site to functions that have the same type as the function to be called. Similarly, for a backward edge scheme protecting returns, a coarse-grained implementation would only allow the procedure to return to a function of the same type (of which there could be many, especially for common prototypes), while a fine-grained one would enforce precise return matching (so it can return only to the function that called it). == Implementations == Related implementations are available in Clang (LLVM front-end),, GNU Compiler Collection, Microsoft's Control Flow Guard and Return Flow Guard, Google's Indirect Function-Call Checks and Reuse Attack Protector (RAP). === LLVM/Clang === The LLVM compiler's C/C++ front-end Clang provides a number of "CFI" schemes that works on the forward edge by checking for errors in virtual tables and type casts. Not all of the schemes are supported on all platforms and most of them, the exception being two "kcfi" schemes intended for low-level kernel software, depends on link-time optimization (LTO) to know what functions are supposed to be called in normal cases. Also provided is a separate "shadow call stack" (SCS) instrumentation pass that defends on the backward edge by checking for call stack modifications, available only for the aarch64 and RISC-V ISAs. And due to use of a shared processor register SCS is only enforceable on certain ABIs or if in other ways it is ensured that any other software using the register set (thread/processor) does not interfere with this use. Google has shipped Android with the Linux kernel compiled by Clang with link-time optimization (LTO) and CFI enabled since 2018. Even though SCS is available for the Linux kernel as an option, and support is also available for Android's system components it is recommended only to enable it for components for which it can be ensured that no third party code is loaded. === GCC === The GNU Compiler Collection implemented a "shadow call stack" compatible with Clang for aarch64 in v12 released in 2022. This feature is primarily intended for building the Linux kernel as support is missing from GCC user space libraries. === Intel Control-flow Enforcement Technology === Intel Control-flow Enforcement Technology (CET) detects compromises to control flow integrity with a shadow stack (SS) and indirect branch tracking (IBT). The kernel must map a region of memory for the shadow stack not writable to user space programs except by special instructions. The shadow stack stores a copy of the return address of each CALL. On a RET, the processor checks if the return address stored in the normal stack and shadow stack are equal. If the addresses are not equal, the processor generates an INT #21 (Control Flow Protection Fault). Indirect branch tracking detects indirect JMP or CALL instructions to unauthorized targets. It is implemented by adding a new internal state machine in the processor. The behavior of indirect JMP and CALL instructions is changed so that they switch the state machine from IDLE to WAIT_FOR_ENDBRANCH. In the WAIT_FOR_ENDBRANCH state, the next instruction to be executed is required to be the new ENDBRANCH instruction (ENDBR32 in 32-bit mode or ENDBR64 in 64-bit mode), which changes the internal state machine from WAIT_FOR_ENDBRANCH back to IDLE. Thus every authorized target of an indirect JMP or CALL must begin with ENDBRANCH. If the processor is in a WAIT_FOR_ENDBRANCH state (meaning, the previous instruction was an indirect JMP or CALL), and the next instruction is not an ENDBRANCH instruction, the processor generates an INT #21 (Control Flow Protection Fault). On processors not supporting CET indirect branch tracking, ENDBRANCH instructions are interpreted as NOPs and have no effect. === Microsoft Control Flow Guard === Control Flow Guard (CFG) was first released for Windows 8.1 Update 3 (KB3000850) in November 2014. Developers can add CFG to their programs by adding the /guard:cf linker flag before program linking in Visual Studio 2015 or newer. As of Windows 10 Creators Update (Windows 10 version 1703), the Windows kernel is compiled with CFG. The Windows kernel uses Hyper-V to prevent malicious kernel code from overwriting the CFG bitmap. CFG operates by creating a per-process bitmap, where a set bit indicates that the address is a valid destination. Before performing each indirect function call, the application checks if the destination address is in the bitmap. If the destination address is not in the bitmap, the program terminates. This makes it more difficult for an attacker to exploit a use-after-free by replacing an object's contents and then using an indirect function call to execute a payload. ==== Implementation details ==== For all protected indirect function calls, the _guard_check_icall function is called, which performs the following steps: Convert the target address to an offset and bit number in the bitmap. The highest 3 bytes are the byte offset in the bitmap The bit offset is a 5-bit value. The first four bits are the 4th through 8th low-order bits of the address. The 5th bit of the bit offset is set to 0 if the destination address is aligned with 0x10 (last four bits are 0), and 1 if it is not. Examine the target's address value in the bitmap If the target address is in the bitmap, return without an error. If the target address is not in the bitmap, terminate the program. ==== Bypass techniques ==== There are several generic techniques for bypassing CFG: Set the destination to code located in a non-CFG module loaded in the same process. Find an indirect call that was not protected by CFG (either CALL or JMP). Use a function call with a different number of arguments than the call is designed for, causing a stack misalignment, and code execution after the function returns (patched in Windows 10). Use a function call with the same number of arguments, but one of pointers passed is treated as an object and writes to a pointer-based offset, allowing overwriting a return address. Overwrite the function call used by the CFG to validate the address (patched in March 2015) Set the CFG bitmap to all 1's, allowing all indirect function calls Use a controlled-write primitive to overwrite an address on the stack (since the stack is not protected by CFG) === Microsoft eXtended Flow Guard === eXtended Flow Guard (XFG) has not been officially released yet, but is available in the Windows Insider preview and was publicly presented at Bluehat Shanghai in 2019. XFG extends CFG by validating function call signatures to ensure that indirect function calls are only to the subset of functions with the same signature. Function call signature validation is implemented by adding instructions to store the target function's hash in register r10 immediately prior to the indirect call and storing the calculated function hash in the memory immediately preceding the target address's code. When the indirect call is made, the XFG validation function compares the value in r10 to the target

  Read more →
• 

  TurboQuant

  TurboQuant is an online vector quantization algorithm for compressing high-dimensional Euclidean vectors while preserving their geometric structure. It was proposed in 2025 by Amir Zandieh, Majid Daliri, Majid Hadian, and Vahab Mirrokni in the paper TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate. The paper lists Zandieh and Mirrokni as affiliated with Google Research, Daliri with New York University, and Hadian with Google DeepMind. The method was developed for applications including large language model (LLM) inference, key–value (KV) cache compression, vector databases, and nearest neighbor search. TurboQuant consists of two related algorithms: TurboQuantmse, which is optimized for mean squared error (MSE), and TurboQuantprod, which is optimized for unbiased inner product estimation. The algorithm uses a random rotation of input vectors, applies scalar quantizers to the rotated coordinates, and, for inner-product estimation, applies a one-bit Quantized Johnson–Lindenstrauss (QJL) transform to the residual error. == Background == Vector quantization is a compression method that maps high-dimensional vectors to a finite set of codewords. The problem has roots in Shannon's source coding theory and rate–distortion theory. In machine learning and information retrieval, vector quantization is used to reduce the memory required to store embeddings, activation vectors, and other numerical representations. In Transformer-based large language models, the KV cache stores key and value vectors from previous tokens during autoregressive decoding. The size of this cache grows with context length, the number of attention heads, and the number of concurrent requests, making it a major memory bottleneck in LLM serving. Similar compression problems appear in vector search, where large collections of embedding vectors must be stored and searched efficiently. Earlier approaches to vector quantization include product quantization, scalar quantization, and data-dependent k-means codebook construction. The TurboQuant paper argues that many existing methods either require offline preprocessing and calibration or suffer from suboptimal distortion guarantees in online settings. == Algorithm == === TurboQuantmse === TurboQuantmse is the version of the algorithm optimized for mean-squared error. For a unit vector x ∈ S d − 1 {\displaystyle x\in S^{d-1}} , the algorithm first applies a random rotation matrix Π ∈ R d × d {\displaystyle \Pi \in \mathbb {R} ^{d\times d}} and sets z = Π x {\displaystyle z=\Pi x} . Each coordinate of the rotated vector follows a shifted and scaled beta distribution, which converges to a normal distribution in high dimensions. In high dimensions, distinct coordinates also become nearly independent, allowing the algorithm to apply scalar quantizers independently to each coordinate. The scalar quantizer is constructed by solving a one-dimensional continuous k-means or Lloyd–Max quantization problem. If the centroids are c 1 , c 2 , … , c 2 b {\displaystyle c_{1},c_{2},\ldots ,c_{2^{b}}} , the quantization step stores, for each coordinate, i d x j = ⁡ a r g m i n k ∈ [ 2 b ] | z j − c k | . {\displaystyle \mathrm {idx} _{j}=\operatorname {} {arg\,min}_{k\in [2^{b}]}|z_{j}-c_{k}|.} During dequantization, the stored index for each coordinate is replaced by the corresponding centroid, giving a reconstructed rotated vector z ~ {\displaystyle {\tilde {z}}} . The algorithm then rotates back: x ~ = Π ⊤ z ~ . {\displaystyle {\tilde {x}}=\Pi ^{\top }{\tilde {z}}.} The paper gives the following bound for TurboQuantmse: D m s e ≤ 3 π 2 ⋅ 1 4 b . {\displaystyle D_{\mathrm {mse} }\leq {\frac {\sqrt {3\pi }}{2}}\cdot {\frac {1}{4^{b}}}.} It also reports finer-grained MSE values of approximately 0.36, 0.117, 0.03, and 0.009 for bit-widths b = 1 , 2 , 3 , 4 {\displaystyle b=1,2,3,4} , respectively. === TurboQuantprod === TurboQuantprod is optimized for unbiased inner-product estimation. The authors note that an MSE-optimized quantizer may introduce bias when used to estimate inner products. To address this, TurboQuantprod first applies TurboQuantmse with bit-width b − 1 {\displaystyle b-1} , then applies a one-bit Quantized Johnson–Lindenstrauss transform to the remaining residual vector. Let r = x − Q m s e − 1 ( Q m s e ( x ) ) {\displaystyle r=x-Q_{\mathrm {mse} }^{-1}(Q_{\mathrm {mse} }(x))} be the residual after MSE quantization, and let γ = ‖ r ‖ 2 {\displaystyle \gamma =\|r\|_{2}} . The QJL step stores a sign vector for the residual. For γ ≠ 0 {\displaystyle \gamma \neq 0} , this can be written using the normalized residual u = r / γ {\displaystyle u=r/\gamma } : q j l = sign ⁡ ( S u ) , {\displaystyle qjl=\operatorname {sign} (Su),} where S ∈ R d × d {\displaystyle S\in \mathbb {R} ^{d\times d}} is a random projection matrix. Since the sign function is invariant under positive rescaling, this is equivalent to sign ⁡ ( S r ) {\displaystyle \operatorname {sign} (Sr)} when r ≠ 0 {\displaystyle r\neq 0} . If γ = 0 {\displaystyle \gamma =0} , the residual correction is zero. TurboQuantprod stores the MSE quantization, the QJL sign vector, and the residual norm: Q p r o d ( x ) = [ Q m s e ( x ) , q j l , γ ] . {\displaystyle Q_{\mathrm {prod} }(x)=\left[Q_{\mathrm {mse} }(x),qjl,\gamma \right].} The dequantized vector is reconstructed as x ~ = x ~ m s e + π / 2 d γ S ⊤ q j l . {\displaystyle {\tilde {x}}={\tilde {x}}_{\mathrm {mse} }+{\frac {\sqrt {\pi /2}}{d}}\,\gamma S^{\top }qjl.} The paper proves that TurboQuantprod is unbiased for inner-product estimation: E x ~ [ ⟨ y , x ~ ⟩ ] = ⟨ y , x ⟩ . {\displaystyle \mathbb {E} _{\tilde {x}}\left[\langle y,{\tilde {x}}\rangle \right]=\langle y,x\rangle .} It also gives the distortion bound D p r o d ≤ 3 π 2 ⋅ ‖ y ‖ 2 2 d ⋅ 1 4 b . {\displaystyle D_{\mathrm {prod} }\leq {\frac {\sqrt {3\pi }}{2}}\cdot {\frac {\|y\|_{2}^{2}}{d}}\cdot {\frac {1}{4^{b}}}.} == Performance and applications == The TurboQuant paper reports that the algorithm achieves near-optimal distortion rates within a small constant factor of information-theoretic lower bounds. The authors report that, for KV cache quantization, TurboQuant achieved quality neutrality at 3.5 bits per channel and marginal degradation at 2.5 bits per channel. In long-context LLM experiments using Llama 3.1 8B Instruct, the paper evaluated the method on a "needle-in-a-haystack" retrieval task with document lengths from 4,000 to 104,000 tokens. It reported that TurboQuant matched the uncompressed full-precision baseline while using more than 4× compression, and compared the method against PolarQuant, SnapKV, PyramidKV, and KIVI. Google Research stated that TurboQuant was evaluated on long-context benchmarks including LongBench, Needle in a Haystack, ZeroSCROLLS, RULER, and L-Eval using open-source models including Gemma and Mistral. According to a report in Tom's Hardware, Google described the method as reducing KV-cache memory by at least six times and achieving up to an eightfold improvement in attention-logit computation on Nvidia H100 GPUs compared with unquantized 32-bit keys. TurboQuant has also been applied to nearest-neighbor vector search. The original paper reports experiments on DBpedia entity embeddings and GloVe embeddings, comparing TurboQuant with product quantization and other vector-search quantization baselines. == Relationship to other methods == TurboQuant is related to several methods for efficient large language model inference and high-dimensional search: Product quantization – a vector quantization technique widely used for approximate nearest-neighbor search Quantization (machine learning) – reducing the numerical precision of weights, activations, or cached tensors in machine learning models PagedAttention – a memory-management algorithm for LLM serving that reduces fragmentation in the KV cache Johnson–Lindenstrauss lemma – a result in high-dimensional geometry used in random projection methods Lloyd's algorithm – an algorithm for scalar and vector quantization, including k-means-style codebook construction Unlike PagedAttention, which focuses on memory allocation and cache layout, TurboQuant reduces the numerical storage cost of the vectors themselves. Unlike many product-quantization methods, TurboQuant is designed to be data-oblivious and online, avoiding dataset-specific codebook training. == Limitations == The strongest performance claims for TurboQuant come from the original paper and Google Research's own publication. Coverage in technology media has noted that the broader impact of the method will depend on real-world implementation details, workloads, and hardware architectures.

  Read more →
• 

  Tuple

  In mathematics, a tuple is a finite sequence (or ordered list) of numbers. More generally, it is a sequence of mathematical objects, called the elements of the tuple. An n-tuple is a tuple of n elements, where n is a non-negative integer. There is only one 0-tuple, called the empty tuple. A 1-tuple and a 2-tuple are commonly called a singleton and an ordered pair, respectively. The term "infinite tuple" is occasionally used for "infinite sequences". Tuples are usually written by listing the elements within parentheses "( )" and separated by commas; for example, (2, 7, 4, 1, 7) denotes a 5-tuple. Other types of brackets are sometimes used, although they may have a different meaning. An n-tuple can be formally defined as the image of a function that has the set of the first n natural numbers as its domain (1, 2, ..., n). Tuples may be also defined from ordered pairs by a recurrence starting from an ordered pair; indeed, an n-tuple can be identified with the ordered pair of its (n − 1) first elements and its nth element, for example, ( ( ( 1 , 2 ) , 3 ) , 4 ) = ( 1 , 2 , 3 , 4 ) {\displaystyle \left(\left(\left(1,2\right),3\right),4\right)=\left(1,2,3,4\right)} . In computer science, tuples come in many forms. Most typed functional programming languages implement tuples directly as product types, tightly associated with algebraic data types, pattern matching, and destructuring assignment. Many programming languages offer an alternative to tuples, known as record types, featuring unordered elements accessed by label. A few programming languages combine ordered tuple product types and unordered record types into a single construct, as in C structs and Haskell records. Relational databases may formally identify their rows (records) as tuples. Tuples also occur in relational algebra; when programming the semantic web with the Resource Description Framework (RDF); in linguistics; and in philosophy. == Etymology == The term originated as an abstraction of the sequence: single, couple/double, triple, quadruple, quintuple, sextuple, septuple, octuple, ..., n‑tuple, ..., where the prefixes are taken from the Latin names of the numerals. The unique 0-tuple is called the null tuple or empty tuple. A 1‑tuple is called a single (or singleton), a 2‑tuple is called an ordered pair or couple, and a 3‑tuple is called a triple (or triplet). The number n can be any nonnegative integer. For example, a complex number can be represented as a 2‑tuple of reals, a quaternion can be represented as a 4‑tuple, an octonion can be represented as an 8‑tuple, and a sedenion can be represented as a 16‑tuple. Although these uses treat ‑tuple as the suffix, the original suffix was ‑ple as in "triple" (three-fold) or "decuple" (ten‑fold). This originates from medieval Latin plus (meaning "more") related to Greek ‑πλοῦς, which replaced the classical and late antique ‑plex (meaning "folded"), as in "duplex". == Properties == The general rule for the identity of two n-tuples is ( a 1 , a 2 , … , a n ) = ( b 1 , b 2 , … , b n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})=(b_{1},b_{2},\ldots ,b_{n})} if and only if a 1 = b 1 , a 2 = b 2 , … , a n = b n {\displaystyle a_{1}=b_{1},{\text{ }}a_{2}=b_{2},{\text{ }}\ldots ,{\text{ }}a_{n}=b_{n}} . Thus a tuple has properties that distinguish it from a set: A tuple may contain multiple instances of the same element, so tuple ( 1 , 2 , 2 , 3 ) ≠ ( 1 , 2 , 3 ) {\displaystyle (1,2,2,3)\neq (1,2,3)} ; but set { 1 , 2 , 2 , 3 } = { 1 , 2 , 3 } {\displaystyle \{1,2,2,3\}=\{1,2,3\}} . Tuple elements are ordered: tuple ( 1 , 2 , 3 ) ≠ ( 3 , 2 , 1 ) {\displaystyle (1,2,3)\neq (3,2,1)} , but set { 1 , 2 , 3 } = { 3 , 2 , 1 } {\displaystyle \{1,2,3\}=\{3,2,1\}} . A tuple has a finite number of elements, while a set or a multiset may have an infinite number of elements. == Definitions == There are several definitions of tuples that give them the properties described in the previous section. === Tuples as functions === The 0 {\displaystyle 0} -tuple may be identified as the empty function. For n ≥ 1 , {\displaystyle n\geq 1,} the n {\displaystyle n} -tuple ( a 1 , … , a n ) {\displaystyle \left(a_{1},\ldots ,a_{n}\right)} may be identified with the surjective function F : { 1 , … , n } → { a 1 , … , a n } {\displaystyle F~:~\left\{1,\ldots ,n\right\}~\to ~\left\{a_{1},\ldots ,a_{n}\right\}} with domain domain ⁡ F = { 1 , … , n } = { i ∈ N : 1 ≤ i ≤ n } {\displaystyle \operatorname {domain} F=\left\{1,\ldots ,n\right\}=\left\{i\in \mathbb {N} :1\leq i\leq n\right\}} and with codomain codomain ⁡ F = { a 1 , … , a n } , {\displaystyle \operatorname {codomain} F=\left\{a_{1},\ldots ,a_{n}\right\},} that is defined at i ∈ domain ⁡ F = { 1 , … , n } {\displaystyle i\in \operatorname {domain} F=\left\{1,\ldots ,n\right\}} by F ( i ) := a i . {\displaystyle F(i):=a_{i}.} That is, F {\displaystyle F} is the function defined by 1 ↦ a 1 ⋮ n ↦ a n {\displaystyle {\begin{alignedat}{3}1\;&\mapsto &&\;a_{1}\\\;&\;\;\vdots &&\;\\n\;&\mapsto &&\;a_{n}\\\end{alignedat}}} in which case the equality ( a 1 , a 2 , … , a n ) = ( F ( 1 ) , F ( 2 ) , … , F ( n ) ) {\displaystyle \left(a_{1},a_{2},\dots ,a_{n}\right)=\left(F(1),F(2),\dots ,F(n)\right)} necessarily holds. Tuples as sets of ordered pairs Functions are commonly identified with their graphs, which is a certain set of ordered pairs. Indeed, many authors use graphs as the definition of a function. Using this definition of "function", the above function F {\displaystyle F} can be defined as: F := { ( 1 , a 1 ) , … , ( n , a n ) } . {\displaystyle F~:=~\left\{\left(1,a_{1}\right),\ldots ,\left(n,a_{n}\right)\right\}.} === Tuples as nested ordered pairs === Another way of modeling tuples in set theory is as nested ordered pairs. This approach assumes that the notion of ordered pair has already been defined. The 0-tuple (i.e. the empty tuple) is represented by the empty set ∅ {\displaystyle \emptyset } . An n-tuple, with n > 0, can be defined as an ordered pair of its first entry and an (n − 1)-tuple (which contains the remaining entries when n > 1): ( a 1 , a 2 , a 3 , … , a n ) = ( a 1 , ( a 2 , a 3 , … , a n ) ) {\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},a_{3},\ldots ,a_{n}))} This definition can be applied recursively to the (n − 1)-tuple: ( a 1 , a 2 , a 3 , … , a n ) = ( a 1 , ( a 2 , ( a 3 , ( … , ( a n , ∅ ) … ) ) ) ) {\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=(a_{1},(a_{2},(a_{3},(\ldots ,(a_{n},\emptyset )\ldots ))))} Thus, for example: ( 1 , 2 , 3 ) = ( 1 , ( 2 , ( 3 , ∅ ) ) ) ( 1 , 2 , 3 , 4 ) = ( 1 , ( 2 , ( 3 , ( 4 , ∅ ) ) ) ) {\displaystyle {\begin{aligned}(1,2,3)&=(1,(2,(3,\emptyset )))\\(1,2,3,4)&=(1,(2,(3,(4,\emptyset ))))\\\end{aligned}}} A variant of this definition starts "peeling off" elements from the other end: The 0-tuple is the empty set ∅ {\displaystyle \emptyset } . For n > 0: ( a 1 , a 2 , a 3 , … , a n ) = ( ( a 1 , a 2 , a 3 , … , a n − 1 ) , a n ) {\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=((a_{1},a_{2},a_{3},\ldots ,a_{n-1}),a_{n})} This definition can be applied recursively: ( a 1 , a 2 , a 3 , … , a n ) = ( ( … ( ( ( ∅ , a 1 ) , a 2 ) , a 3 ) , … ) , a n ) {\displaystyle (a_{1},a_{2},a_{3},\ldots ,a_{n})=((\ldots (((\emptyset ,a_{1}),a_{2}),a_{3}),\ldots ),a_{n})} Thus, for example: ( 1 , 2 , 3 ) = ( ( ( ∅ , 1 ) , 2 ) , 3 ) ( 1 , 2 , 3 , 4 ) = ( ( ( ( ∅ , 1 ) , 2 ) , 3 ) , 4 ) {\displaystyle {\begin{aligned}(1,2,3)&=(((\emptyset ,1),2),3)\\(1,2,3,4)&=((((\emptyset ,1),2),3),4)\\\end{aligned}}} === Tuples as nested sets === Using Kuratowski's representation for an ordered pair, the second definition above can be reformulated in terms of pure set theory: The 0-tuple (i.e. the empty tuple) is represented by the empty set ∅ {\displaystyle \emptyset } ; Let x {\displaystyle x} be an n-tuple ( a 1 , a 2 , … , a n ) {\displaystyle (a_{1},a_{2},\ldots ,a_{n})} , and let x → b ≡ ( a 1 , a 2 , … , a n , b ) {\displaystyle x\rightarrow b\equiv (a_{1},a_{2},\ldots ,a_{n},b)} . Then, x → b ≡ { { x } , { x , b } } {\displaystyle x\rightarrow b\equiv \{\{x\},\{x,b\}\}} . (The right arrow, → {\displaystyle \rightarrow } , could be read as "adjoined with".) In this formulation: ( ) = ∅ ( 1 ) = ( ) → 1 = { { ( ) } , { ( ) , 1 } } = { { ∅ } , { ∅ , 1 } } ( 1 , 2 ) = ( 1 ) → 2 = { { ( 1 ) } , { ( 1 ) , 2 } } = { { { { ∅ } , { ∅ , 1 } } } , { { { ∅ } , { ∅ , 1 } } , 2 } } ( 1 , 2 , 3 ) = ( 1 , 2 ) → 3 = { { ( 1 , 2 ) } , { ( 1 , 2 ) , 3 } } = { { { { { { ∅ } , { ∅ , 1 } } } , { { { ∅ } , { ∅ , 1 } } , 2 } } } , { { { { { ∅ } , { ∅ , 1 } } } , { { { ∅ } , { ∅ , 1 } } , 2 } } , 3 } } {\displaystyle {\begin{array}{lclcl}()&&&=&\emptyset \\&&&&\\(1)&=&()\rightarrow 1&=&\{\{()\},\{(),1\}\}\\&&&=&\{\{\emptyset \},\{\emptyset ,1\}\}\\&&&&\\(1,2)&=&(1)\rightarrow 2&=&\{\{(1)\},\{(1),2\}\}\\&&&=&\{\{\{\{\emptyset \},\{\emptyset ,1\}\}\},\\&&&&\{\{\{\emptyset \},\{\emptyset ,1\}\},2\}\}\\&&&&\\(1,2,3)&=&(1,2)\rightarrow 3&=&\{\{(1,2)\},\{(1,2),3\}\}\\&&&=&\{\{\{\{\{\{\empty

  Read more →
• 

  Birkhoff algorithm

  Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations. == Terminology == A bistochastic matrix (also called: doubly-stochastic) is a matrix in which all elements are greater than or equal to 0 and the sum of the elements in each row and column equals 1. An example is the following 3-by-3 matrix: ( 0.2 0.3 0.5 0.6 0.2 0.2 0.2 0.5 0.3 ) {\displaystyle {\begin{pmatrix}0.2&0.3&0.5\\0.6&0.2&0.2\\0.2&0.5&0.3\end{pmatrix}}} A permutation matrix is a special case of a bistochastic matrix, in which each element is either 0 or 1 (so there is exactly one "1" in each row and each column). An example is the following 3-by-3 matrix: ( 0 1 0 0 0 1 1 0 0 ) {\displaystyle {\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}} A Birkhoff decomposition (also called: Birkhoff-von-Neumann decomposition) of a bistochastic matrix is a presentation of it as a sum of permutation matrices with non-negative weights. For example, the above matrix can be presented as the following sum: 0.2 ( 0 1 0 0 0 1 1 0 0 ) + 0.2 ( 1 0 0 0 1 0 0 0 1 ) + 0.1 ( 0 1 0 1 0 0 0 0 1 ) + 0.5 ( 0 0 1 1 0 0 0 1 0 ) {\displaystyle 0.2{\begin{pmatrix}0&1&0\\0&0&1\\1&0&0\end{pmatrix}}+0.2{\begin{pmatrix}1&0&0\\0&1&0\\0&0&1\end{pmatrix}}+0.1{\begin{pmatrix}0&1&0\\1&0&0\\0&0&1\end{pmatrix}}+0.5{\begin{pmatrix}0&0&1\\1&0&0\\0&1&0\end{pmatrix}}} Birkhoff's algorithm receives as input a bistochastic matrix and returns as output a Birkhoff decomposition. == Tools == A permutation set of an n-by-n matrix X is a set of n entries of X containing exactly one entry from each row and from each column. A theorem by Dénes Kőnig says that: Every bistochastic matrix has a permutation-set in which all entries are positive.The positivity graph of an n-by-n matrix X is a bipartite graph with 2n vertices, in which the vertices on one side are n rows and the vertices on the other side are the n columns, and there is an edge between a row and a column if the entry at that row and column is positive. A permutation set with positive entries is equivalent to a perfect matching in the positivity graph. A perfect matching in a bipartite graph can be found in polynomial time, e.g. using any algorithm for maximum cardinality matching. Kőnig's theorem is equivalent to the following:The positivity graph of any bistochastic matrix admits a perfect matching.A matrix is called scaled-bistochastic if all elements are non-negative, and the sum of each row and column equals c, where c is some positive constant. In other words, it is c times a bistochastic matrix. Since the positivity graph is not affected by scaling:The positivity graph of any scaled-bistochastic matrix admits a perfect matching. == Algorithm == Birkhoff's algorithm is a greedy algorithm: it greedily finds perfect matchings and removes them from the fractional matching. It works as follows. Let i = 1. Construct the positivity graph GX of X. Find a perfect matching in GX, corresponding to a positive permutation set in X. Let z[i] > 0 be the smallest entry in the permutation set. Let P[i] be a permutation matrix with 1 in the positive permutation set. Let X := X − z[i] P[i]. If X contains nonzero elements, Let i = i + 1 and go back to step 2. Otherwise, return the sum: z[1] P[1] + ... + z[2] P[2] + ... + z[i] P[i]. The algorithm is correct because, after step 6, the sum in each row and each column drops by z[i]. Therefore, the matrix X remains scaled-bistochastic. Therefore, in step 3, a perfect matching always exists. == Run-time complexity == By the selection of z[i] in step 4, in each iteration at least one element of X becomes 0. Therefore, the algorithm must end after at most n2 steps. However, the last step must simultaneously make n elements 0, so the algorithm ends after at most n2 − n + 1 steps, which implies O ( n 2 ) {\displaystyle O(n^{2})} . In 1960, Joshnson, Dulmage and Mendelsohn showed that Birkhoff's algorithm actually ends after at most n2 − 2n + 2 steps, which is tight in general (that is, in some cases n2 − 2n + 2 permutation matrices may be required). == Application in fair division == In the fair random assignment problem, there are n objects and n people with different preferences over the objects. It is required to give an object to each person. To attain fairness, the allocation is randomized: for each (person, object) pair, a probability is calculated, such that the sum of probabilities for each person and for each object is 1. The probabilistic-serial procedure can compute the probabilities such that each agent, looking at the matrix of probabilities, prefers his row of probabilities over the rows of all other people (this property is called envy-freeness). This raises the question of how to implement this randomized allocation in practice? One cannot just randomize for each object separately, since this may result in allocations in which some people get many objects while other people get no objects. Here, Birkhoff's algorithm is useful. The matrix of probabilities, calculated by the probabilistic-serial algorithm, is bistochastic. Birkhoff's algorithm can decompose it into a convex combination of permutation matrices. Each permutation matrix represents a deterministic assignment, in which every agent receives exactly one object. The coefficient of each such matrix is interpreted as a probability; based on the calculated probabilities, it is possible to pick one assignment at random and implement it. == Extensions == The problem of computing the Birkhoff decomposition with the minimum number of terms has been shown to be NP-hard, but some heuristics for computing it are known. This theorem can be extended for the general stochastic matrix with deterministic transition matrices. Budish, Che, Kojima and Milgrom generalize Birkhoff's algorithm to non-square matrices, with some constraints on the feasible assignments. They also present a decomposition algorithm that minimizes the variance in the expected values. Vazirani generalizes Birkhoff's algorithm to non-bipartite graphs. Valls et al. showed that it is possible to obtain an ϵ {\displaystyle \epsilon } -approximate decomposition with O ( log ⁡ ( 1 / ϵ 2 ) ) {\displaystyle O(\log(1/\epsilon ^{2}))} permutations.

  Read more →
• 

  AI-complete

  In the field of artificial intelligence (AI), tasks that are hypothesized to require artificial general intelligence to solve are informally known as AI-complete or AI-hard. Calling a problem AI-complete reflects the belief that it cannot be solved by a simple specific algorithm. Prior to 2013, problems supposed to be AI-complete included computer vision, natural language understanding, and dealing with unexpected circumstances while solving any real-world problem. AI-complete tasks were notably considered useful for distinguishing humans from automated agents, as CAPTCHAs aim to do. == History == The term was coined by Fanya Montalvo by analogy with NP-complete and NP-hard in complexity theory, which formally describes the most famous class of difficult problems. Early uses of the term are in Erik Mueller's 1987 PhD dissertation and in Eric Raymond's 1991 Jargon File. Expert systems, that were popular in the 1980s, were able to solve very simple and/or restricted versions of AI-complete problems, but never in their full generality. When AI researchers attempted to "scale up" their systems to handle more complicated, real-world situations, the programs tended to become excessively brittle without commonsense knowledge or a rudimentary understanding of the situation: they would fail as unexpected circumstances outside of its original problem context would begin to appear. When human beings are dealing with new situations in the world, they are helped by their awareness of the general context: they know what the things around them are, why they are there, what they are likely to do and so on. They can recognize unusual situations and adjust accordingly. Expert systems lacked this adaptability and were brittle when facing new situations. DeepMind published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named Gato, can "play Atari, caption images, chat, stack blocks with a real robot arm and much more, deciding based on its context whether to output text, joint torques, button presses, or other tokens." Similarly, some tasks once considered to be AI-complete, like machine translation, are among the capabilities of large language models. == AI-complete problems == AI-complete problems have been hypothesized to include: AI peer review (composite natural language understanding, automated reasoning, automated theorem proving, formalized logic expert system) Bongard problems Computer vision (and subproblems such as object recognition) Natural language understanding (and subproblems such as text mining, machine translation, and word-sense disambiguation) Autonomous driving Dealing with unexpected circumstances while solving any real world problem, whether navigation, planning, or even the kind of reasoning done by expert systems. == Formalization == Computational complexity theory deals with the relative computational difficulty of computable functions. By definition, it does not cover problems whose solution is unknown or has not been characterized formally. Since many AI problems have no formalization yet, conventional complexity theory does not enable a formal definition of AI-completeness. == Research == Roman Yampolskiy suggests that a problem C {\displaystyle C} is AI-Complete if it has two properties: It is in the set of AI problems (Human Oracle-solvable). Any AI problem can be converted into C {\displaystyle C} by some polynomial time algorithm. On the other hand, a problem H {\displaystyle H} is AI-Hard if and only if there is an AI-Complete problem C {\displaystyle C} that is polynomial time Turing-reducible to H {\displaystyle H} . This also gives as a consequence the existence of AI-Easy problems, that are solvable in polynomial time by a deterministic Turing machine with an oracle for some problem. Yampolskiy has also hypothesized that the Turing Test is a defining feature of AI-completeness. Groppe and Jain classify problems which require artificial general intelligence to reach human-level machine performance as AI-complete, while only restricted versions of AI-complete problems can be solved by the current AI systems. For Šekrst, getting a polynomial solution to AI-complete problems would not necessarily be equal to solving the issue of artificial general intelligence, while emphasizing the lack of computational complexity research being the limiting factor towards achieving artificial general intelligence. For Kwee-Bintoro and Velez, solving AI-complete problems would have strong repercussions on society.

  Read more →
• 

  List of algorithms

  An algorithm is a fundamental set of rules or defined procedures that are typically designed and used to be a simpler way to solve a specific problem or a broad set of problems. Simply speaking, algorithms define different processes, sets of rules and regulations, or methodologies that are to be followed through in calculations, data processing, data mining, pattern recognition, automated reasoning or other problem-solving operations. With the increasing automation of services, more and more decisions are being made by algorithms. Some general examples are risk assessments, anticipatory policing, and pattern recognition technology. The following is a list of well-known algorithms. == Automated planning == == Combinatorial algorithms == === General combinatorial algorithms === Brent's algorithm: finds a cycle in function value iterations using only two iterators Floyd's cycle-finding algorithm: finds a cycle in function value iterations Gale–Shapley algorithm: solves the stable matching problem Pseudorandom number generators (uniformly distributed—see also List of pseudorandom number generators for other PRNGs with varying degrees of convergence and varying statistical quality): ACORN generator Blum Blum Shub Lagged Fibonacci generator Linear congruential generator Mersenne Twister === Graph algorithms === Blossom algorithm: algorithm for constructing maximum-cardinality matching on graphs. Coloring algorithm: algorithms for graph (vertex or edge) coloring (subject to constraints, e.g. proper coloring or list coloring) Hopcroft–Karp algorithm: convert a bipartite graph to a maximum-cardinality matching Hungarian algorithm: algorithm for finding a perfect matching Prüfer coding: conversion between a labeled tree and its Prüfer sequence Tarjan's off-line lowest common ancestors algorithm: computes lowest common ancestors for pairs of nodes in a tree Topological sort: finds linear order of nodes (e.g. jobs) based on their dependencies. ==== Graph drawing ==== Coin graph drawing algorithms for finite connected planar graphs (approximately computing the theoretical circle-packing given by the Koebe-Andreev-Thurston theorem). See also Fáry's theorem on straight-line drawings of planar graphs. Force-based algorithms (also known as force-directed algorithms or spring-based algorithms) Spectral layout ==== Network theory ==== Network analysis Link analysis Girvan–Newman algorithm: detect communities in complex systems Web link analysis Hyperlink-Induced Topic Search (HITS) (also known as Hubs and authorities) PageRank TrustRank Flow networks Dinic's algorithm: is a strongly polynomial algorithm for computing the maximum flow in a flow network. Edmonds–Karp algorithm: implementation of Ford–Fulkerson Ford–Fulkerson algorithm: computes the maximum flow in a graph Karger's algorithm: a Monte Carlo method to compute the minimum cut of a connected graph Push–relabel algorithm: computes a maximum flow in a graph ==== Routing for graphs ==== Edmonds' algorithm (also known as Chu–Liu/Edmonds' algorithm): find maximum or minimum branchings Euclidean minimum spanning tree: algorithms for computing the minimum spanning tree of a set of points in the plane Longest path problem: find a simple path of maximum length in a given graph Minimum spanning tree Borůvka's algorithm Kruskal's algorithm Prim's algorithm Reverse-delete algorithm Nonblocking minimal spanning switch say, for a telephone exchange Shortest path problem Bellman–Ford algorithm: computes shortest paths in a weighted graph (where some of the edge weights may be negative) Dijkstra's algorithm: computes shortest paths in a graph with non-negative edge weights Floyd–Warshall algorithm: solves the all pairs shortest path problem in a weighted, directed graph Johnson's algorithm: all pairs shortest path algorithm in sparse weighted directed graph Transitive closure problem: find the transitive closure of a given binary relation Traveling salesman problem Christofides algorithm Nearest neighbour algorithm Vehicle routing problem Clarke and Wright Saving algorithm Warnsdorff's rule: a heuristic method for solving the Knight's tour problem ==== Graph search ==== A: special case of best-first search that uses heuristics to improve speed B: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals) Backtracking: abandons partial solutions when they are found not to satisfy a complete solution Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement Beam stack search: integrates backtracking with beam search Best-first search: traverses a graph in the order of likely importance using a priority queue Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph Breadth-first search: traverses a graph level by level Brute-force search: an exhaustive and reliable search method, but computationally inefficient in many applications D: an incremental heuristic search algorithm Depth-first search: traverses a graph branch by branch Dijkstra's algorithm: a special case of A for which no heuristic function is used General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine. Iterative deepening depth-first search (IDDFS): a state space search strategy Jump point search: an optimization to A which may reduce computation time by an order of magnitude using further heuristics Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph SSS: state space search traversing a game tree in a best-first fashion similar to that of the A search algorithm Uniform-cost search: a tree search that finds the lowest-cost route where costs vary ==== Subgraphs ==== Cliques Bron–Kerbosch algorithm: a technique for finding maximal cliques in an undirected graph MaxCliqueDyn maximum clique algorithm: find a maximum clique in an undirected graph Strongly connected components Kosaraju's algorithm Path-based strong component algorithm Tarjan's strongly connected components algorithm Subgraph isomorphism problem === Sequence algorithms === ==== Approximate sequence matching ==== Bitap algorithm: fuzzy algorithm that determines if strings are approximately equal. Phonetic algorithms Daitch–Mokotoff Soundex: a Soundex refinement which allows matching of Slavic and Germanic surnames Double Metaphone: an improvement on Metaphone Match rating approach: a phonetic algorithm developed by Western Airlines Metaphone: an algorithm for indexing words by their sound, when pronounced in English NYSIIS: phonetic algorithm, improves on Soundex Soundex: a phonetic algorithm for indexing names by sound, as pronounced in English String metrics: computes a similarity or dissimilarity (distance) score between two pairs of text strings Damerau–Levenshtein distance: computes a distance measure between two strings, improves on Levenshtein distance Dice's coefficient (also known as the Dice coefficient): a similarity measure related to the Jaccard index Hamming distance: sum number of positions which are different Jaro–Winkler distance: is a measure of similarity between two strings Levenshtein edit distance: computes a metric for the amount of difference between two sequences Trigram search: search for text when the exact syntax or spelling of the target object is not precisely known ==== Selection algorithms ==== Introselect Quickselect ==== Sequence search ==== Linear search: locates an item in an unsorted sequence Selection algorithm: finds the kth largest item in a sequence Sorted lists Binary search algorithm: locates an item in a sorted sequence Eytzinger binary search: cache friendly binary search algorithm Fibonacci search technique: search a sorted sequence using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers Jump search (or block search): linear search on a smaller subset of the sequence Predictive search: binary-like search which factors in magnitude of search term versus the high and low values in the search. Sometimes called dictionary search or interpolated search. Uniform binary search: an optimization of the classic binary search algorithm Ternary search: a technique for finding the minimum or maximum of a function that is either strictly increasing and then strictly decreasing or vice versa ==== Sequence merging ==== k-way merge algorithm Simple merge algorithm Union (merge, with elements on the output not repeated) ==== Sequence permutations ==== Fisher–Yates shuffle (also known as the Knuth shuffle): randomly shuffle a finite set Heap's permutation generation algorithm: interchange elements to generate next permutation Schensted algorithm: constructs a pair of Young tableaux from a permutation Steinhaus–Johnson–Trotter algorithm (also known as the Johnson–Trotter algorithm):

  Read more →
• 

  Scriptella

  Scriptella is an open source extract transform load (ETL) and script execution tool written in Java. It allows the use of SQL or another scripting language suitable for the data source to perform required transformations. Scriptella does not offer any graphical user interface. == Typical use == Database migration. Database creation/update scripts. Cross-database ETL operations, import/export. Alternative for Ant task. Automated database schema upgrade. == Features == Simple XML syntax for scripts. Add dynamics to your existing SQL scripts by creating a thin wrapper XML file: Support for multiple datasources (or multiple connections to a single database) in an ETL file. Support for many useful JDBC features, e.g. parameters in SQL including file blobs and JDBC escaping. Performance and low memory usage are one of the primary goals. Support for evaluated expressions and properties (JEXL syntax) Support for cross-database ETL scripts by using elements Transactional execution Error handling via elements Conditional scripts/queries execution (similar to Ant if/unless attributes but more powerful) Easy-to-Use as a standalone tool or Ant task, without deployment or installation. Easy-To-Run ETL files directly from Java code. Built-in adapters for popular databases for a tight integration. Support for any database with JDBC/ODBC compliant driver. Service Provider Interface (SPI) for interoperability with non-JDBC DataSources and integration with scripting languages. Out of the box support for JSR 223 (Scripting for the Java Platform) compatible languages. Built-in CSV, TEXT, XML, LDAP, Lucene, Velocity, JEXL and Janino providers. Integration with Java EE, Spring Framework, JMX and JNDI for enterprise ready scripts.

  Read more →