In combinatorics and computational learning theory, a witness set is a set of elements that distinguishes a given Boolean function from a given class of other Boolean functions. Let C {\displaystyle C} be a concept class over a domain X {\displaystyle X} (that is, a family of Boolean functions over X {\displaystyle X} ) and c {\displaystyle c} be a concept in X {\displaystyle X} (a single Boolean function). A subset S {\displaystyle S} of X {\displaystyle X} is a witness set for c {\displaystyle c} in X {\displaystyle X} if S {\displaystyle S} distinguishes c {\displaystyle c} from all the other functions in C {\displaystyle C} , in the sense that no other function in C {\displaystyle C} has the same values on S {\displaystyle S} . For a concept class with | C | {\displaystyle |C|} concepts, there exists a concept that has a witness of size at most log 2 | C | {\displaystyle \log _{2}|C|} ; this bound is tight when C {\displaystyle C} consists of all Boolean functions over X {\displaystyle X} . By a result of Bondy (1972) there exists a single witness set of size at most | C | − 1 {\displaystyle |C|-1} that is valid for all concepts in C {\displaystyle C} ; this bound is tight when C {\displaystyle C} consists of the indicator functions of the empty set and some singleton sets. One way to construct this set is to interpret the concepts as bitstrings, and the domain elements as positions in these bitstrings. Then the set of positions at which a trie of the bitstrings branches forms the desired witness set. This construction is central to the operation of the fusion tree data structure. The minimum size of a witness set for c {\displaystyle c} is called the witness size or specification number and is denoted by w C ( c ) {\displaystyle w_{C}(c)} . The value max { w C ( c ) : c ∈ C } {\displaystyle \max\{w_{C}(c):c\in C\}} is called the teaching dimension of C {\displaystyle C} . It represents the number of examples of a concept that need to be presented by a teacher to a learner, in the worst case, to enable the learner to determine which concept is being presented. Witness sets have also been called teaching sets, keys, specifying sets, or discriminants. The "witness set" terminology is from Kushilevitz et al. (1996), who trace the concept of witness sets to work by Cover (1965).
Dominant resource fairness
Dominant resource fairness (DRF) is a rule for fair division. It is particularly useful for dividing computing resources in among users in cloud computing environments, where each user may require a different combination of resources. DRF was presented by Ali Ghodsi, Matei Zaharia, Benjamin Hindman, Andy Konwinski, Scott Shenker and Ion Stoica in 2011. == Motivation == In an environment with a single resource, a widely used criterion is max-min fairness, which aims to maximize the minimum amount of resource given to a user. But in cloud computing, it is required to share different types of resource, such as: memory, CPU, bandwidth and disk-space. Previous fair schedulers, such as in Apache Hadoop, reduced the multi-resource setting to a single-resource setting by defining nodes with a fixed amount of each resource (e.g. 4 CPU, 32 MB memory, etc.), and dividing slots which are fractions of nodes. But this method is inefficient, since not all users need the same ratio of resources. For example, some users need more CPU whereas other users need more memory. As a result, most tasks either under-utilize or over-utilize their resources. DRF solves the problem by maximizing the minimum amount of the dominant resource given to a user (then the second-minimum etc., in a leximin order). The dominant resource may be different for different users. For example, if user A runs CPU-heavy tasks and user B runs memory-heavy tasks, DRF will try to equalize the CPU share given to user A and the memory share given to user B. == Definition == There are m resources. The total capacities of the resources are r1,...,rm. There are n users. Each users runs individual tasks. Each task has a demand-vector (d1,..,dm), representing the amount it needs of each resource. It is implicitly assumed that the utility of a user equals the number of tasks he can perform. For example, if user A runs tasks with demand-vector [1 CPU, 4 GB RAM], and receives 3 CPU and 8 GB RAM, then his utility is 2, since he can perform only 2 tasks. More generally, the utility of a user receiving x1,...,xm resources is minj(xj/dj), that is, the users have Leontief utilities. The demand-vectors are normalized to fractions of the capacities. For example, if the system has 9 CPUs and 18 GB RAM, then the above demand-vector is normalized to [1/9 CPU, 2/9 GB]. For each user, the resource with the highest demand-fraction is called the dominant resource. In the above example, the dominant resource is memory, as 2/9 is the largest fraction. If user B runs a task with demand-vector [3 CPU, 1 GB], which is normalized to [1/3 CPU, 1/18 GB], then his dominant resource is CPU. DRF aims to find the maximum x such that all agents can receive at least x of their dominant resource. In the above example, this maximum x is 2/3: User A gets 3 tasks, which require 3/9 CPU and 2/3 GB. User B gets 2 tasks, which require 2/3 CPU and 1/9 GB. The maximum x can be found by solving a linear program; see Lexicographic max-min optimization. Alternatively, the DRF can be computed sequentially. The algorithm tracks the amount of dominant resource used by each user. At each round, it finds a user with the smallest allocated dominant resource so far, and allocates the next task of this user. Note that this procedure allows the same user to run tasks with different demand vectors. == Properties == DRF has several advantages over other policies for resource allocation. Proportionality: each user receives at least as much resources as they could get in a system in which all resources are partitioned equally among users (the authors call this condition "sharing incentive"). Strategyproofness: a user cannot get a larger allocation by lying about his needs. Strategyproofness is important, as evidence from cloud operators show that users try to manipulate the servers in order to get better allocations. Envy-freeness: no user would prefer the allocation of another user. Pareto efficiency: no other allocation is better for some users and not worse for anyone. Population monotonicity: when a user leaves the system, the allocations of remaining users do not decrease. When there is a single resource that is a bottleneck resource (highly demanded by all users), DRF reduces to max-min fairness. However, DRF violates resource monotonicity: when resources are added to the system, some allocations might decrease. == Extensions == Weighted DRF is an extension of DRF to settings in which different users have different weights (representing their different entitlements). Parkes, Procaccia and Shah formally extend weighted DRF to a setting in which some users do not need all resources (that is, they may have demand 0 to some resource). They prove that the extended version still satisfies proportionality, Pareto-efficiency, envy-freeness, strategyproofness, and even Group strategyproofness. On the other hand, they show that DRF may yield poor utilitarian social welfare, that is, the sum of utilities may be only 1/m of the optimum. However, they prove that any mechanism satisfying one of proportionality, envy-freeness or strategyproofness may suffers from the same low utilitarian welfare. They also extend DRF to the setting in which the users' demands are indivisible (as in fair item allocation). For the indivisible setting, they relax envy-freeness to EF1. They show that strategyproofness is incompatible with PO+EF1 or with PO+proportionality. However, a mechanism called SequentialMinMax satisfies efficiency, proportionality and EF1. Wang, Li and Liang present DRFH - an extension of DRF to a system with several heterogeneous servers. == Implementation == DRF was first implemented in Apache Mesos - a cluster resource manager, and it led to better throughput and fairness than previously used fair-sharing schemes.
Ordered key–value store
An ordered key–value store (OKVS) is a type of data storage paradigm that can support multi-model databases. An OKVS is an ordered mapping of bytes to bytes. An OKVS will keep the key–value pairs sorted by the key lexicographic order. OKVS systems provides different set of features and performance trade-offs. Most of them are shipped as a library without network interfaces, in order to be embedded in another process. Most OKVS support ACID guarantees. Some OKVS are distributed databases. Ordered key–value stores found their way into many modern database systems including NewSQL database systems. == History == The origin of ordered key–value store stems from the work of Ken Thompson on dbm in 1979. Later in 1991, Berkeley DB was released that featured a B-Tree backend that allowed the keys to stay sorted. Berkeley DB was said to be very fast and made its way into various commercial product. It was included in Python standard library until 2.7. In 2009, Tokyo Cabinet was released that was superseded by Kyoto Cabinet that support both transaction and ordered keys. In 2011, LMDB was created to replace Berkeley DB in OpenLDAP. There is also Google's LevelDB that was forked by Facebook in 2012 as RocksDB. In 2014, WiredTiger, successor of Berkeley DB was acquired by MongoDB and is since 2019 the primary backend of MongoDB database. Other notable implementation of the OKVS paradigm are Sophia and SQLite3 LSM extension. Another notable use of OKVS paradigm is the multi-model database system called ArangoDB based on RocksDB. Some NewSQL databases are supported by ordered key–value stores. JanusGraph, a property graph database, has both a Berkeley DB backend and FoundationDB backend. == Key concepts == === Lexicographic encoding === There are algorithms that encode basic data types (boolean, string, number) and composition of those data types inside sorted containers (tuple, list, vector) that preserve their natural ordering. It is possible to work with an ordered key–value store without having to work directly with bytes. In FoundationDB, it is called the tuple layer. === Range query === Inside an OKVS, keys are ordered, and because of that it is possible to do range queries. A range query retrieves all keys between two specified keys, ensuring that the fetched keys are returned in a sorted order. === Subspaces === === Key composition === One can construct key spaces to build higher level abstractions. The idea is to construct keys, that takes advantage of the ordered nature of the top level key space. When taking advantage of the ordered nature of the key space, one can query ranges of keys that have particular pattern. === Denormalization === Denormalization, as in, repeating the same piece of data in multiple subspace is common practice. It allows to create secondary representation, also called indices, that will allow to speed up queries. == Higher level abstractions == The following abstraction or databases were built on top ordered key–value stores: Timeseries database, Record Database, also known as Row store databases, they behave similarly to what is dubbed RDBMS, Tuple Stores, also known as Triple Store or Quad Store but also Generic Tuple Store, Document database, that mimics MongoDB API, Full-text search Geographic Information Systems Property Graph Versioned Data Vector space database for Approximate Nearest Neighbor All those abstraction can co-exist with the same OKVS database and when ACID is supported, the operations happens with the guarantees offered by the transaction system. == Feature matrix == == Use-cases == OKVS are useful to implement two strategies: optimize a small feature e.g. to make a 10% improvement in read or write latency; the second strategy is to take advantage of the distributed nature of FoundationDB, and TiKV, for which there is no equivalent at very large scale in resilience. Both users need to re-implement the needed high level abstractions, because there are no portable ready-to-use libraries of high-level abstraction. There is still a complex balance, of complexity, maintainability, fine-tuning, and readily available features that makes it still a choice of experts. Sometime more specialized data-structures can be faster than a high-level abstraction on top of an OKVS. Another interest of OKVS paradigm stems from it simple, and versatile interface, that makes it an interesting target for experimental storage algorithms, and data structures.
Terminology extraction
Terminology extraction (also known as term extraction, glossary extraction, term recognition, or terminology mining) is a subtask of information extraction. The goal of terminology extraction is to automatically extract relevant terms from a given corpus. In the semantic web era, a growing number of communities and networked enterprises started to access and interoperate through the internet. Modeling these communities and their information needs is important for several web applications, like topic-driven web crawlers, web services, recommender systems, etc. The development of terminology extraction is also essential to the language industry. One of the first steps to model a knowledge domain is to collect a vocabulary of domain-relevant terms, constituting the linguistic surface manifestation of domain concepts. Several methods to automatically extract technical terms from domain-specific document warehouses have been described in the literature. Typically, approaches to automatic term extraction make use of linguistic processors (part of speech tagging, phrase chunking) to extract terminological candidates, i.e. syntactically plausible terminological noun phrases. Noun phrases include compounds (e.g. "credit card"), adjective noun phrases (e.g. "local tourist information office"), and prepositional noun phrases (e.g. "board of directors"). In English, the first two (compounds and adjective noun phrases) are the most frequent. Terminological entries are then filtered from the candidate list using statistical and machine learning methods. Once filtered, because of their low ambiguity and high specificity, these terms are particularly useful for conceptualizing a knowledge domain or for supporting the creation of a domain ontology or a terminology base. Furthermore, terminology extraction is a very useful starting point for semantic similarity, knowledge management, human translation and machine translation, etc. == Bilingual terminology extraction == The methods for terminology extraction can be applied to parallel corpora. Combined with e.g. co-occurrence statistics, candidates for term translations can be obtained. Bilingual terminology can be extracted also from comparable corpora (corpora containing texts within the same text type, domain but not translations of documents between each other).
Data quality
Data quality refers to the state of qualitative or quantitative pieces of information. There are many definitions of data quality, but data is generally considered high quality if it is "fit for [its] intended uses in operations, decision making and planning". Data is deemed of high quality if it correctly represents the real-world construct to which it refers. Apart from these definitions, as the number of data sources increases, the question of internal data consistency becomes significant, regardless of fitness for use for any particular external purpose. People's views on data quality can often be in disagreement, even when discussing the same set of data used for the same purpose. When this is the case, businesses may adopt recognised international standards for data quality (See #International Standards for Data Quality below). Data governance can also be used to form agreed upon definitions and standards, including international standards, for data quality. In such cases, data cleansing, including standardization, may be required in order to ensure data quality. == Definitions == Defining data quality is difficult due to the many contexts data are used in, as well as the varying perspectives among end users, producers, and custodians of data. From a consumer perspective, data quality is: "data that are fit for use by data consumers" data "meeting or exceeding consumer expectations" data that "satisfies the requirements of its intended use" From a business perspective, data quality is: data that are "'fit for use' in their intended operational, decision-making and other roles" or that exhibits "'conformance to standards' that have been set, so that fitness for use is achieved" data that "are fit for their intended uses in operations, decision making and planning" "the capability of data to satisfy the stated business, system, and technical requirements of an enterprise" From a standards-based perspective, data quality is: the "degree to which a set of inherent characteristics (quality dimensions) of an object (data) fulfills requirements" "the usefulness, accuracy, and correctness of data for its application" Arguably, in all these cases, "data quality" is a comparison of the actual state of a particular set of data to a desired state, with the desired state being typically referred to as "fit for use," "to specification," "meeting consumer expectations," "free of defect," or "meeting requirements." These expectations, specifications, and requirements are usually defined by one or more individuals or groups, standards organizations, laws and regulations, business policies, or software development policies. == Dimensions of data quality == Drilling down further, those expectations, specifications, and requirements are stated in terms of characteristics or dimensions of the data, such as: accessibility or availability accuracy or correctness comparability completeness or comprehensiveness consistency, coherence, or clarity credibility, reliability, or reputation flexibility plausibility relevance, pertinence, or usefulness timeliness or latency uniqueness validity or reasonableness A systematic scoping review of the literature suggests that data quality dimensions and methods with real world data are not consistent in the literature, and as a result quality assessments are challenging due to the complex and heterogeneous nature of these data. == International standards for data quality == ISO 8000 is an international standard for data quality. Managed by the International Organization for Standardization, the ISO 8000 standards address and describe general aspects of data quality including principles, vocabulary and measurement data governance data quality management data quality assessment quality of master data, including exchange of characteristic data and identifiers quality of industrial data == History == Before the rise of the inexpensive computer data storage, massive mainframe computers were used to maintain name and address data for delivery services. This was so that mail could be properly routed to its destination. The mainframes used business rules to correct common misspellings and typographical errors in name and address data, as well as to track customers who had moved, died, gone to prison, married, divorced, or experienced other life-changing events. Government agencies began to make postal data available to a few service companies to cross-reference customer data with the National Change of Address registry (NCOA). This technology saved large companies millions of dollars in comparison to manual correction of customer data. Large companies saved on postage, as bills and direct marketing materials made their way to the intended customer more accurately. Initially sold as a service, data quality moved inside the walls of corporations, as low-cost and powerful server technology became available. Companies with an emphasis on marketing often focused their quality efforts on name and address information, but data quality is recognized as an important property of all types of data. Principles of data quality can be applied to supply chain data, transactional data, and nearly every other category of data found. For example, making supply chain data conform to a certain standard has value to an organization by: 1) avoiding overstocking of similar but slightly different stock; 2) avoiding false stock-out; 3) improving the understanding of vendor purchases to negotiate volume discounts; and 4) avoiding logistics costs in stocking and shipping parts across a large organization. For companies with significant research efforts, data quality can include developing protocols for research methods, reducing measurement error, bounds checking of data, cross tabulation, modeling and outlier detection, verifying data integrity, etc. == Overview == There are a number of theoretical frameworks for understanding data quality. A systems-theoretical approach influenced by American pragmatism expands the definition of data quality to include information quality, and emphasizes the inclusiveness of the fundamental dimensions of accuracy and precision on the basis of the theory of science (Ivanov, 1972). One framework, dubbed "Zero Defect Data" (Hansen, 1991) adapts the principles of statistical process control to data quality. Another framework seeks to integrate the product perspective (conformance to specifications) and the service perspective (meeting consumers' expectations) (Kahn et al. 2002). Another framework is based in semiotics to evaluate the quality of the form, meaning and use of the data (Price and Shanks, 2004). One highly theoretical approach analyzes the ontological nature of information systems to define data quality rigorously (Wand and Wang, 1996). A considerable amount of data quality research involves investigating and describing various categories of desirable attributes (or dimensions) of data. Nearly 200 such terms have been identified and there is little agreement in their nature (are these concepts, goals or criteria?), their definitions or measures (Wang et al., 1993). Software engineers may recognize this as a similar problem to "ilities". MIT has an Information Quality (MITIQ) Program, led by Professor Richard Wang, which produces a large number of publications and hosts a significant international conference in this field (International Conference on Information Quality, ICIQ). This program grew out of the work done by Hansen on the "Zero Defect Data" framework (Hansen, 1991). In practice, data quality is a concern for professionals involved with a wide range of information systems, ranging from data warehousing and business intelligence to customer relationship management and supply chain management. One industry study estimated the total cost to the U.S. economy of data quality problems at over U.S. $600 billion per annum (Eckerson, 2002). Incorrect data – which includes invalid and outdated information – can originate from different data sources – through data entry, or data migration and conversion projects. In 2002, the USPS and PricewaterhouseCoopers released a report stating that 23.6 percent of all U.S. mail sent is incorrectly addressed. One reason contact data becomes stale very quickly in the average database – more than 45 million Americans change their address every year. In fact, the problem is such a concern that companies are beginning to set up a data governance team whose sole role in the corporation is to be responsible for data quality. In some organizations, this data governance function has been established as part of a larger Regulatory Compliance function - a recognition of the importance of Data/Information Quality to organizations. Problems with data quality don't only arise from incorrect data; inconsistent data is a problem as well. Eliminating data shadow systems and centralizing data in a warehouse is one of the initiatives a company can take to ensure data consistency. En
Frameserver
A frameserver is any program that acts as a media source in the process called frameserving, which transfers digital video data from one computer program to another without intermediate files. The program that receives the data – the frameclient – could be any type of video application. The process is controlled by the frameclient: the frameclient requests audio/video frames and the frameserver serves them. The client can request frames in any order, allowing it to pause or jump to an arbitrary frame, just as a media player does with a file on disk. The client is most commonly a media encoder, a non-linear editing system, or a media player. == Frameservers == AviSynth VirtualDub VapourSynth Debugmode FrameServer
Sikidy
Sikidy is a form of algebraic geomancy practiced by Malagasy peoples in Madagascar. It involves algorithmic operations performed on random data generated from tree seeds, which are ritually arranged in a tableau called a toetry and divinely interpreted after being mathematically operated on. Columns of seeds, designated "slaves" or "princes" belonging to respective "lands" for each, interact symbolically to express vintana ('fate') in the interpretation of the diviner. The diviner also prescribes solutions to problems and ways to avoid fated misfortune, often involving a sacrifice. The centuries-old practice derives from Islamic influence brought to the island by medieval Arab traders. The sikidy is consulted for a range of divinatory questions pertaining to fate and the future, including identifying sources of and rectifying misfortune, reading the fate of newborns, and planning annual migrations. The mathematics of sikidy involves Boolean algebra, symbolic logic and parity. == History == The practice is several centuries old, and is influenced by Arab geomantic traditions of Arab Muslim traders on the island. Most writers link the origins of sikidy to the "sea-going trade involving the southwest coast of India, the Persian Gulf, and the east coast of Africa in the 9th or 10th century C.E." Stephen Ellis and Solofo Randrianja describe sikidy as "probably one of the oldest components of Malagasy culture", writing that it most likely the product of an indigenous divinatory art later influenced by Islamic practice. Umar H. D. Danfulani writes that the integration of Arabic divination into indigenous divination is "clearly demonstrated" in Madagascar, where the Arabic astrological system was adapted to the indigenous agricultural system and meshed with Malagasy lunar months by "adapting indigenous months, volana, to the astrological months, vintana". Danfulani also describes the concepts in sikidy of "houses" (lands) and "kings in their houses" as retained from medieval Arabic astrology. Chemillier et al. say the practice's spread across Madagascar likely originated with the southeastern Antemoro people, among whom Arab influence was the strongest. Though the etymology of sikidy is unknown, it has been posited that the word derives from the Arabic sichr ('incantation' or 'charm'). Sikidy was of central importance to pre-Christian Malagasy religion, with one practitioner quoted in 1892 as calling sikidy "the Bible of our ancestors". A missionary report from 1616 describes one form of sikidy using tamarind seeds, and another using fingered markings in the sand. The early colonial French governor of Madagascar Étienne de Flacourt documented sikidy in the mid-17th century: Matatane country in southeastern Madagascar [...] where the Antemoro [...] live was a center of astrological study as early as the fourteenth century [...]. This area was also the site of early Arab settlements, although strict Islamic observances were lost centuries ago [...]. Historical evidence shows that Antemoro diviners, bearers of the astrological system, infiltrated nearly all the ancient kingdoms of Madagascar beginning in the sixteenth century. [...] Today, although many persons claim to be ombiasy [diviners], only the Antemoro diviners are considered true professionals. The area is still a famous place of learning where specialists go for training and then return to their home communities with a certain body of knowledge. Now we can better understand the degree of similarity of divination forms found throughout Madagascar. For centuries Matitanana has remained a training center for diviners who have migrated widely, usually attaining important positions in their home communities and with various royal families. Comparison of contemporary rites with centuries-old texts show that sikidy has been remarkably unchanged throughout its history. The "infiltration" of Malagasy kingdoms by Antemoro diviners, and Matitanana's role as a place for astrological and divinatory learning, help to explain the relatively uniform practicing of sikidy across Madagascar. Chemallier et al. write that the mathematical construction of the arrangement of seeds is procedurally consistent across all of Madagascar, with variations in practice between groups and regions being limited to more minor aspects, such as the alignment of figures according to cardinal directions. One exception is the simplified Merina sikidy joria. === Origin myths === Mythic tradition relating to the origin of sikidy "links [the practice] both to the return by walking on water of Arab ancestors who had intermarried with Malagasy but then left, and to the names of the days of the week" and holds that the art was supernaturally communicated to the ancestors, with Zanahary (the supreme deity of Malagasy religion) giving it to Ranakandriana, who then gave it to a line of diviners (Ranakandriana to Ramanitralanana to Rabibi-andrano to Andriambavi-maitso (who was a woman) to Andriam-bavi-nosy), the last of whom terminated the monopoly by giving it to the people, declaring: "Behold, I give you the sikidy, of which you may inquire what offerings you should present in order to obtain blessings; and what expiation you should make so as to avert evils, when any are ill or under apprehension of some future calamity". A mythic anecdote of Ranakandriana says that two men observed him one day playing in the sand. In fact he was practicing a form of sikidy worked in sand called sikidy alanana. The two men seized him, and Ranakandriana promised that he would teach them something if they released him. They agreed, and Ranakandriana taught them in depth how to work the sikidy. The two men then went to their chief and told him that they could tell him "the past and the future—what was good and what was bad—what increased and what diminished." The chief asked them to tell him how he could obtain plenty of cattle. The two men worked their sikidy and told the chief to kill all of his bulls, and that "great numbers would come to him" on the following Friday. The chieftain, doubting, asked what would happen if their prediction didn't come true, and the two men promised they would pay with their lives. The chief agreed and killed his bulls. On Thursday, thinking he'd been duped, he prematurely killed the first man of the two who'd told him about the divinatory art. On Friday, however, "vast herds" came amidst heavy rain, actually filling an immense plain in their crowd. The chieftain lamented the mpisikidy's wrongful execution and ordered for him a pompous funeral. The chieftain took the second man as his close adviser and friend, and trusted the sikidy forever afterwards. The British missionary William Ellis recorded in 1839 two idiomatic expressions used in Madagascar that come from this story: "Tsy mahandry andro Zoma" (lit. 'He cannot wait 'til Friday') is said of someone extremely impatient, and heavy rainshowers falling in rapid succession are called "sese omby" (lit. 'a crowding together of cattle'). == Rites and arrangement of seeds == The divination is performed by a practitioner called an mpisikidy, ny màsina (lit. 'sacred one'), ombiasy, or ambiàsa (derived from the Arabic anbia, meaning 'prophet') who guides the client through the process and interprets the results in the context of the client's inquiries and desires. As part of an mpisikidy's formal initiation into the art, which includes a long period of apprenticeship, the initiate (called a mianatsy) must gather 124 and 200 fàno (Entada sp.) or kily (tamarind) tree seeds for his subsequent ritual use in sikidy. Raymond Decary writes that, at least among the Sakalava, a man must be 40 years old before learning and practicing sikidy, or he risks death. Before beginning to study, a student practitioner must make incisions at the tips of his index finger, his middle finger, and his tongue, and put within the incisions a paste containing red pepper and crushed wasp. This paste impregnates the fingers that will move the seeds of the sikidy and the tongue that will speak their revelations with the power to decipher the sikidy. Once this is done, he leaves at dawn to search for a fano (Entada chrysostachys) tree. Upon finding it, he throws his spear at its branches, shaking the tree and causing its large seed pods to fall. During this act, some initiates say: "When you were on the steep peak and in the dense forest, on you the crabs climbed, from you the crocodiles made their bed, with their paws the birds trod on you. Whether you are suspended in the trees or buried, you are never dried up nor rotten." In his study (written in 1941 and revised in 1948), Decary reported that the salary paid by a mianatsy to his master is "not very high": up to five francs, plus a red rooster's feather. The mpisikidy ritually arranges his seeds into a sixteen-column table consisting of four columns of randomly-generated data (representing fate) and eight columns of data derived from logical ope