kdb+ is a column-based relational time series database (TSDB) with in-memory (IMDB) abilities, developed and marketed by KX Systems. The database is commonly used in high-frequency trading (HFT) to store, analyze, process, and retrieve large data sets at high speed. kdb+ has the ability to handle billions of records and analyzes data within a database. The database is available in 32-bit and 64-bit versions for several operating systems. Financial institutions use kdb+ to analyze time series data such as stock or commodity exchange data. The database has also been used for other time-sensitive data applications including commodity markets such as energy trading, telecommunications, sensor data, log data, machine and computer network usage monitoring along with real time analytics in Formula One racing. == Overview == kdb+ is a high-performance column-store database that was designed to process and store large amounts of data. Commonly accessed data is pushed into random-access memory (RAM), which is faster to access than data in disk storage. Created with financial institutions in mind, the database was developed as a central repository to store time series data that supports real-time analysis of billions of records. kdb+ has the ability to analyze data over time and responds to queries similar to Structured Query Language (SQL). Columnar databases return answers to some queries in a more efficient way than row-based database management systems. kdb+ dictionaries, tables and nanosecond time stamps are native data types and are used to store time series data. At the core of kdb+ is the built-in programming language, q, a concise, expressive query array language, and dialect of the language APL. Q can manipulate streaming, real-time, and historical data. kdb+ uses q to aggregate and analyze data, perform statistical functions, and join data sets and supports SQL queries The vector language q was built for speed and expressiveness and eliminates most need for looping structures. kdb+ includes interfaces in C, C++, Java, C#, and Python. == History == In 1998, KX released kdb, a database built on the language K written by Arthur Whitney. In 2003, kdb+ was released as a 64-bit version of kdb. In 2004, the kdb+ tick market database framework was released along with kdb+ taq, a loader for the New York Stock Exchange (NYSE) taq data. kdb+ was created by Arthur Whitney, building on his prior work with array languages. In April 2007, KX announced that it was releasing a version of kdb+ for Mac OS X. Then, kdb+ was also available on the operating systems Linux, Windows, and Solaris. In September 2012, version 3.0 was released. It was optimized for Intel's upgraded processors with support for WebSockets, and universally unique identifiers (UUIDs, termed globally unique identifiers (GUID)s in Microsoft software). Intel's Advanced Vector Extensions (AVX) and Streaming SIMD Extensions 4 (SSE4) 4.2 on the Sandy Bridge processors of the time allowed for enhanced support of the kdb+ system. In June 2013, version 3.1 was released, with benchmarks up to 8 times faster than older versions. In March 2020, version 4.0 was released. New features included Multithreaded primitives, Intel Optane DC persistent memory support and Data at Rest Encryption.
Patent visualisation
Patent visualisation is an application of information visualisation. The number of patents has been increasing, encouraging companies to consider intellectual property as a part of their strategy. Patent visualisation, like patent mapping, is used to quickly view a patent portfolio. Software dedicated to patent visualisation began to appear in 2000, for example Aureka from Aurigin (now owned by Thomson Reuters). Many patent and portfolio analytics platforms, such as Questel, Patent Forecast, PatSnap, Patentcloud, Relecura, and Patent iNSIGHT Pro, offer options to visualise specific data within patent documents by creating topic maps, priority maps, IP Landscape reports, etc. Software converts patents into infographics or maps, to allow the analyst to "get insight into the data" and draw conclusions. Also called patinformatics, it is the "science of analysing patent information to discover relationships and trends that would be difficult to see when working with patent documents on a one-and-one basis". Patents contain structured data (like publication numbers) and unstructured text (like title, abstract, claims and visual info). Structured data are processed by data-mining and unstructured data are processed with text-mining. == Data mining == The main step in processing structured information is data-mining, which emerged in the late 1980s. Data mining involves statistics, artificial intelligence, and machine learning. Patent data mining extracts information from the structured data of the patent document. These structured data are bibliographic fields such as location, date or status. === Structured fields === === Advantages === Data mining allows study of filing patterns of competitors and locates main patent filers within a specific area of technology. This approach can be helpful to monitor competitors' environments, moves and innovation trends and gives a macro view of a technology status. == Text-mining == === Principle === Text mining is used to search through unstructured text documents. This technique is widely used on the Internet, it has had success in bioinformatics and now in the intellectual property environment. Text mining is based on a statistical analysis of word recurrence in a corpus. An algorithm extracts words and expressions from title, summary and claims and gathers them by declension. "And" and "if" are labeled as non-information bearing words and are stored in the stopword list. Stoplists can be specialised in order to create an accurate analysis. Next, the algorithm ranks the words by weight, according to their frequency in the patent's corpus and the document frequency containing this word. The score for each word is calculated using a formula such as: W e i g h t = T e r m F r e q u e n c y D o c u m e n t F r e q u e n c y = F r e q u e n c y o f t h e w o r d o r e x p r e s s i o n i n t h e T e x t S e a N u m b e r o f d o c u m e n t s c o n t a i n i n g t h e e x p r e s s i o n o r w o r d {\displaystyle Weight={\frac {Term\ Frequency}{Document\ Frequency}}={\frac {Frequency\ of\ the\ word\ or\ expression\ in\ the\ Text\ Sea}{Number\ of\ documents\ containing\ the\ expression\ or\ word}}} A frequently used word in several documents has less weight than a word used frequently in a few patents. Words under a minimum weight are eliminated, leaving a list of pertinent words or descriptors. Each patent is associated to the descriptors found in the selected document. Further, in the process of clusterisation, these descriptors are used as subsets, in which the patent are regrouped or as tags to place the patents in predetermined categories, for example keywords from International Patent Classifications. Four text parts can be processed with text-mining : Title Abstract Claim Patent Full-Text Software offer different combinations but title, abstract and claim are generally the most used, providing a good balance between interferences and relevancy. === Advantages === Text-mining can be used to narrow a search or quickly evaluate a patent corpus. For instance, if a query produces irrelevant documents, a multi-level clustering hierarchy identifies them in order to delete them and refine the search. Text-mining can also be used to create internal taxonomies specific to a corpus for possible mapping. == Visualisations == Allying patent analysis and informatic tools offers an overview of the environment through value-added visualisations. As patents contain structured and unstructured information, visualisations fall in two categories. Structured data can be rendered with data mining in macrothematic maps and statistical analysis. Unstructured information can be shown in like clouds, cluster maps and 2D keyword maps. === Data mining visualisation === === Text mining visualisation === === Visualisation for both data-mining and text-mining === Mapping visualisations can be used for both text-mining and data-mining results. == Uses == What patent visualisation can highlight: Competitors Partners New innovations Technologic environment description Networks Field application: R&D strategy management Competitive intelligence Licensing Strategy
Paper data storage
Paper data storage refers to the use of paper as a data storage device. This includes writing, illustrating, and the use of data that can be interpreted by a machine or is the result of the functioning of a machine. A defining feature of paper data storage is the ability of humans to produce it with only simple tools and interpret it visually. Though now mostly obsolete, paper was once an important form of computer data storage as both paper tape and punch cards were a common staple of working with computers before the 1980s. == History == Before paper was used for storing data, it had been used in several applications for storing instructions to specify a machine's operation. The earliest use of paper to store instructions for a machine was the work of Basile Bouchon who, in 1725, used punched paper rolls to control textile looms. This technology was later developed into the wildly successful Jacquard loom. The 19th century saw several other uses of paper for controlling machines. In 1846, telegrams could be prerecorded on punched tape and rapidly transmitted using Alexander Bain's automatic telegraph. Several inventors took the concept of a mechanical organ and used paper to represent the music. In the late 1880s Herman Hollerith invented the recording of data on a medium that could then be read by a machine. Prior uses of machine readable media, above, had been for control (automatons, piano rolls, looms, ...), not data. "After some initial trials with paper tape, he settled on punched cards..." Hollerith's method was used in the 1890 census. Hollerith's company eventually became the core of IBM. Other technologies were also developed that allowed machines to work with marks on paper instead of punched holes. This technology was widely used for tabulating votes and grading standardized tests. Banks used magnetic ink on checks, supporting MICR scanning. In an early electronic computing device, the Atanasoff–Berry Computer, electric sparks were used to singe small holes in paper cards to represent binary data. The altered dielectric constant of the paper at the location of the holes could then be used to read the binary data back into the machine by means of electric sparks of lower voltage than the sparks used to create the holes. This form of paper data storage was never made reliable and was not used in any subsequent machine. == Modern techniques == === 1D barcodes === Barcodes make it possible for any object that was to be sold or transported to have some computer readable information securely attached to it. Universal Product Code barcodes, first used in 1974, are ubiquitous today. Some people recommend a width of at least 3 pixels for each minimum-width gap and each minimum-width bar for 1D barcodes. The density is about 50 bits per linear inch (about 2 bit/mm). === 2D barcodes === 2D barcodes allow to store much more data on paper, up to 2.9 kbyte per barcode. It is recommended to have a width of at least 4 pixels—e.g., a 4 × 4 pixel = 16 pixel module. == Limits == The limits of data storage depend on the technology to write and read such data. The theoretical limits assume a scanner that can perfectly reproduce the printed image at its printing resolution, and a program which can accurately interpret such an image. For example, an 8 in × 10 in (200 mm × 250 mm) 600 dpi black-and-white image contains 3.43 MiB of data, as does a 300 dpi CMYK printed image. A 2,400 ppi True color (24-bit) image contains about 1.29 GiB of information; printing an image maintaining this data would require a printing resolution of about 120,000 dpi in black and white, or 60,000 dpi with CMYK dots.
List of algorithm general topics
This is a list of algorithm general topics. Analysis of algorithms Ant colony algorithm Approximation algorithm Best and worst cases Big O notation Combinatorial search Competitive analysis Computability theory Computational complexity theory Embarrassingly parallel problem Emergent algorithm Evolutionary algorithm Fast Fourier transform Genetic algorithm Graph exploration algorithm Heuristic Hill climbing Implementation Las Vegas algorithm Lock-free and wait-free algorithms Monte Carlo algorithm Numerical analysis Online algorithm Polynomial time approximation scheme Problem size Pseudorandom number generator Quantum algorithm Random-restart hill climbing Randomized algorithm Running time Sorting algorithm Search algorithm Stable algorithm (disambiguation) Super-recursive algorithm Tree search algorithm
Information access
Information access is the freedom or ability to identify, obtain and make use of database or information effectively. There are various research efforts in information access for which the objective is to simplify and make it more effective for human users to access and further process large and unwieldy amounts of data and information. == Technology == Several technologies applicable to the general area are Information Retrieval, Text Mining, Machine Translation, and Text Categorisation. During discussions on free access to information as well as on information policy, information access is understood as concerning the insurance of free and closed access to information. Information access covers many issues including copyright, open source, privacy, and security. == Groups == Groups such as the American Library Association, the American Association of Law Libraries, Ralph Nader's Taxpayers Assets Project have advocated for free access to legal information. The vendor neutral citation movement in the legal field is working to ensure that courts will accept citations from cases on the web which do not have the traditional (copyrighted) page numbers from the West Publishing company. There is a worldwide Free Access to Law Movement which advocates free access to legal information. The Wired article "Who Owns The Law" is an introduction to the access to legal information issue. Postsecondary organizations such as K-12 work to share information. They feel it is a legal and moral obligation to provide access (including to people with disabilities or impairments) to information through the services and programs they offer. Some effects of charging for information access, such as literature searches for physicians, is studied in the article "Fee or Free: The Effect of Charging on Information Demand". In this study, a $5 charge resulted in a 77% decrease in searches.
Shape table
Shape tables are a feature of the Apple II ROMs which allows for manipulation of small images encoded as a series of vectors. An image (or shape) can be drawn in the high-resolution graphics mode—with scaling and rotation—via software routines in the ROM. Shape tables are supported via Applesoft BASIC and from machine code in the "Programmer's Aid" package that was bundled with the original Integer BASIC ROMs for that computer. Applesoft's high-resolution graphics routines were not optimized for speed, so shape tables were not typically used for performance-critical software such as games, which were typically written in assembly language and used pre-shifted bitmap shapes. Shape tables were used primarily for static shapes and sometimes for fancy text; Beagle Bros offered a number of fonts in Font Mechanic as Applesoft shape tables. == Technical details == The vectors of a two-dimensional graphic, each encoding a direction from the previous pixel along with a flag indicating whether the new pixel should be illuminated or not, were encoded up to three in a byte. These were stored in a table via the Monitor or the POKE command. From there, the graphic could be referenced by number (a table could contain up to 255 shapes), and built-in Applesoft routines permitted scaling, rotating, and drawing or erasing the shape. An XOR mode was also available to allow the shape to be visible on any color background; this had the advantage, also, of allowing the shape to be easily erased by redrawing it. Apple did not provide any utilities for creating shape tables; they had to be created by hand, usually by plotting on graph paper, then calculating the hexadecimal values and entering them into the computer. Beagle Bros created a shape table editing program, which eliminated the "number crunching", called Apple Mechanic, and a related program, Font Mechanic.
Bisection (software engineering)
Bisection is a method used in software development to identify change sets that result in a specific behavior change. It is mostly employed for finding the patch that introduced a bug. Another application area is finding the patch that indirectly fixed a bug. == Overview == The process of locating the changeset that introduced a specific regression was described as "source change isolation" in 1997 by Brian Ness and Viet Ngo of Cray Research. Regression testing was performed on Cray's compilers in editions comprising one or more changesets. Editions with known regressions could not be validated until developers addressed the problem. Source change isolation narrowed the cause to a single changeset that could then be excluded from editions, unblocking them with respect to this problem, while the author of the change worked on a fix. Ness and Ngo outlined linear search and binary search methods of performing this isolation. Code bisection has the goal of minimizing the effort to find a specific change set. It employs a divide and conquer algorithm that depends on having access to the code history which is usually preserved by revision control in a code repository. == Bisection method == === Code bisection algorithm === Code history has the structure of a directed acyclic graph which can be topologically sorted. This makes it possible to use a divide and conquer search algorithm which: splits up the search space of candidate revisions tests for the behavior in question reduces the search space depending on the test result re-iterates the steps above until a range with at most one bisectable patch candidate remains === Algorithmic complexity === Bisection is in LSPACE having an algorithmic complexity of O ( log N ) {\displaystyle O(\log N)} with N {\displaystyle N} denoting the number of revisions in the search space, and is similar to a binary search. === Desirable repository properties === For code bisection it is desirable that each revision in the search space can be built and tested independently. === Monotonicity === For the bisection algorithm to identify a single changeset which caused the behavior being tested to change, the behavior must change monotonically across the search space. For a Boolean function such as a pass/fail test, this means that it only changes once across all changesets between the start and end of the search space. If there are multiple changesets across the search space where the behavior being tested changes between false and true, then the bisection algorithm will find one of them, but it will not necessarily be the root cause of the change in behavior between the start and the end of the search space. The root cause could be a different changeset, or a combination of two or more changesets across the search space. To help deal with this problem, automated tools allow specific changesets to be ignored during a bisection search. == Automation support == Although the bisection method can be completed manually, one of its main advantages is that it can be easily automated. It can thus fit into existing test automation processes: failures in exhaustive automated regression tests can trigger automated bisection to localize faults. Ness and Ngo focused on its potential in Cray's continuous delivery-style environment in which the automatically isolated bad changeset could be automatically excluded from builds. The revision control systems Fossil, Git and Mercurial have built-in functionality for code bisection. The user can start a bisection session with a specified range of revisions from which the revision control system proposes a revision to test, the user tells the system whether the revision tested as "good" or "bad", and the process repeats until the specific "bad" revision has been identified. Other revision control systems, such as Bazaar or Subversion, support bisection through plugins or external scripts. Phoronix Test Suite can do bisection automatically to find performance regressions.