A paperless society is a society in which paper communication (written documents, email, letters, etc.) is replaced by electronic communication and storage. The concept was first introduced by Frederick Wilfrid Lancaster in 1978. Furthermore, libraries would no longer be needed to handle printed documents. "Librarians will, in time, become information specialists in a deinstitutionalized setting". Lancaster also stated that both computers and libraries will not always give us the information that other people and living life will. == Literature == Brodman, E. (1979). Review of Toward Paperless Information Systems. Bulletin of the Medical Library Association, 67(4), 437–439. Buckland, M. K. (1980). Review of Toward Paperless Information Systems. Journal of Academic Librarianship, 5(6), 349. Grosch, A. (1979). Review of Toward Paperless Information Systems. College & Research Libraries, 40(1), 88–89. Kohl, D. F. (2004). From the editor . . . The paperless society . . . Not quite yet. Journal of Academic Librarianship, 30(3), 177–178. Lancaster, F. W. (1978a). Toward paperless information systems. New York: Academic Press. Lancaster, F. W. (1980b). The future of the librarian lies outside of the library. Catholic Library World, 51, 388–391. Lancaster, F. W. (1982a). Libraries and librarians in an age of electronics. Arlington, VA: Information Resources Press. Lancaster, F. W. (1982b). The evolving paperless society and its implications for libraries. International Forum on Information and Documentation, 7(4), 3–10. Lancaster, F. W. (1983). Future librarianship: Preparing for an unconventional career. Wilson Library Bulletin, 57, 747–753. Lancaster, F. W. (1985). The paperless society revisited. American Libraries, 16, 553–555. Lancaster, F. W. (1993). Libraries and the future: Essays on the library in the twenty-first century. New York: Haworth Press. Lancaster, F. W. (1999). Second thoughts on the paperless society. Library Journal, 124(15), 48– 50. Lancaster, F. W., & Smith, L. C. (1980c). On-Line systems in the communication process: Projections. Journal of the American Society for Information Science, 31(3), 193–200. Miall, D. S. (2001). The library versus the Internet: Literary studies under siege? Proceedings of the Modern Language Association, 116(5), 1405–1414. Salton, G. (1979). Review of Toward Paperless Information Systems. Journal of Documentation, 35(3), 250–252. Sellen, A. J., & Harper, R. H. R. (2003). The myth of the paperless office. Cambridge, MA: MIT Press. Stevens, N. D. (2006). The fully electronic academic library. College & Research Libraries, 67(1),5–14. Young, Arthur P. (2008).Aftermath of a Prediction: F. W. Lancaster and the Paperless Society LIBRARY TRENDS, 56(4),(“The Evaluation and Transformation of Information Systems: Essays Honoring the Legacy of F. W. Lancaster,” edited by Lorraine J. Haricombe and Keith Russell), pp. 843–858.
Reasoning model
A reasoning model, also known as a reasoning language model (RLM) or large reasoning model (LRM), is a type of large language model (LLM) that has been specifically trained to solve complex tasks requiring multiple steps of logical reasoning. These models demonstrate superior performance on logic, mathematics, and programming tasks compared to standard LLMs. They possess the ability to revisit and revise earlier reasoning steps and utilize additional computation during inference as a method to scale performance, complementing traditional scaling approaches based on training data size, model parameters, and training compute. == Overview == Unlike traditional language models that generate responses immediately, reasoning models allocate additional compute, or thinking, time before producing an answer to solve multi-step problems. OpenAI introduced this terminology in September 2024 when it released the o1 series, describing the models as designed to "spend more time thinking" before responding. The company framed o1 as a reset in model naming that targets complex tasks in science, coding, and mathematics, and it contrasted o1's performance with GPT-4o on benchmarks such as AIME and Codeforces. Independent reporting the same week summarized the launch and highlighted OpenAI's claim that o1 automates chain-of-thought style reasoning to achieve large gains on difficult exams. In operation, reasoning models generate internal chains of intermediate steps, then select and refine a final answer. OpenAI reported that o1's accuracy improves as the model is given more reinforcement learning during training and more test-time compute at inference. The company initially chose to hide raw chains and instead return a model-written summary, stating that it "decided not to show" the underlying thoughts so researchers could monitor them without exposing unaligned content to end users. Commercial deployments document separate "reasoning tokens" that meter hidden thinking and a control for "reasoning effort" that tunes how much compute the model uses. These features make the models slower than ordinary chat systems while enabling stronger performance on difficult problems. == History == The research trajectory toward reasoning models combined advances in supervision, prompting, and search-style inference. Early alignment work on reinforcement learning from human feedback showed that models can be fine-tuned to follow instructions with "human feedback" and preference-based rewards. In 2022, Google Research scientists Jason Wei and Denny Zhou showed that chain-of-thought prompting "significantly improves the ability" of large models on complex reasoning tasks. Input → Step 1 → Step 2 → ⋯ → Step n ⏟ Reasoning chain → Answer {\displaystyle {\text{Input}}\rightarrow \underbrace {{\text{Step}}_{1}\rightarrow {\text{Step}}_{2}\rightarrow \cdots \rightarrow {\text{Step}}_{n}} _{\text{Reasoning chain}}\rightarrow {\text{Answer}}} A companion result demonstrated that the simple instruction "Let's think step by step" can elicit zero-shot reasoning. Follow-up work introduced self-consistency decoding, which "boosts the performance" of chain-of-thought by sampling diverse solution paths and choosing the consensus, and tool-augmented methods such as ReAct, a portmanteau of Reason and Act, that prompt models to "generate both reasoning traces" and actions. Research then generalized chain-of-thought into search over multiple candidate plans. The Tree-of-Thoughts framework from Princeton computer scientist Shunyu Yao proposes that models "perform deliberate decision making" by exploring and backtracking over a tree of intermediate thoughts. OpenAI's reported breakthrough focused on supervising reasoning processes rather than only outcomes, with Lightman et al.'s "Let's Verify Step by Step" reporting that rewarding each correct step "significantly outperforms outcome supervision" on challenging math problems and improves interpretability by aligning the chain-of-thought with human judgment. OpenAI's o1 announcement ties these strands together with a large-scale reinforcement learning algorithm that trains the model to refine its own chain of thought, and it reports that accuracy rises with more training compute and more time spent thinking at inference. Together, these developments define the core of reasoning models. They use supervision signals that evaluate the quality of intermediate steps, they exploit inference-time exploration such as consensus or tree search, and they expose controls for how much internal thinking compute to allocate. OpenAI's o1 family made this approach available at scale in September 2024 and popularized the label "reasoning model" for LLMs that deliberately think before they answer. The development of reasoning models illustrates Richard S. Sutton's "bitter lesson" that scaling compute typically outperforms methods based on human-designed insights. This principle was demonstrated by researchers at the Generative AI Research Lab (GAIR), who initially attempted to replicate o1's capabilities using sophisticated methods including tree search and reinforcement learning in late 2024. Their findings, published in the "o1 Replication Journey" series, revealed that knowledge distillation, a comparatively straightforward technique that trains a smaller model to mimic o1's outputs, produced unexpectedly strong performance. This outcome illustrated how direct scaling approaches can, at times, outperform more complex engineering solutions. === Drawbacks === Reasoning models require significantly more computational resources during inference compared to non-reasoning models. Research on the American Invitational Mathematics Examination (AIME) benchmark found that reasoning models were 10 to 74 times more expensive to operate than their non-reasoning counterparts. The extended inference time is attributed to the detailed, step-by-step reasoning outputs that these models generate, which are typically much longer than responses from standard large language models that provide direct answers without showing their reasoning process. One researcher in early 2025 argued that these models may face potential additional denial-of-service concerns with "overthinking attacks." === Releases === ==== 2024 ==== In September 2024, OpenAI released o1-preview, a large language model with enhanced reasoning capabilities. The full version, o1, was released in December 2024. OpenAI initially shared preliminary results on its successor model, o3, in December 2024, with the full o3 model becoming available in 2025. Alibaba released reasoning versions of its Qwen large language models in November 2024. In December 2024, the company introduced QvQ-72B-Preview, an experimental visual reasoning model. In December 2024, Google introduced Deep Research in Gemini, a feature designed to conduct multi-step research tasks. On December 16, 2024, researchers demonstrated that by scaling test-time compute, a relatively small Llama 3B model could outperform a much larger Llama 70B model on challenging reasoning tasks. This experiment suggested that improved inference strategies can unlock reasoning capabilities even in smaller models. ==== 2025 ==== In January 2025, DeepSeek released R1, a reasoning model that achieved performance comparable to OpenAI's o1 at significantly lower computational cost. The release demonstrated the effectiveness of Group Relative Policy Optimization (GRPO), a reinforcement learning technique used to train the model. On January 25, 2025, DeepSeek enhanced R1 with web search capabilities, allowing the model to retrieve information from the internet while performing reasoning tasks. Research during this period further validated the effectiveness of knowledge distillation for creating reasoning models. The s1-32B model achieved strong performance through budget forcing and scaling methods, reinforcing findings that simpler training approaches can be highly effective for reasoning capabilities. On February 2, 2025, OpenAI released Deep Research, a feature powered by their o3 model that enables users to conduct comprehensive research tasks. The system generates detailed reports by automatically gathering and synthesizing information from multiple web sources. OpenAI called GPT-4.5 its "last non-chain-of-thought model", and implemented with GPT-5 a router model that selects a model based on the difficulty of the task. ==== 2026 ==== In January 2026, Moonshot AI released Kimi K2.5, an open-source 1 trillion parameter MoE model with 32 billion active parameters. It uses an “Agent Swarm” system that dynamically decomposes tasks into sub-agents for reasoning and execution, enabling more scalable multi-step problem solving than a single sequential reasoning chain. == Training == Reasoning models follow the familiar large-scale pretraining used for frontier language models, then diverge in the post-training and optimization. OpenAI reports that o1 is trained with a large-
Social media stock bubble
The social media bubble is a hypothesis stating that there was a speculative boom and bust phenomenon in the field of social media in the 2010s, particularly in the United States. The Wall Street Journal defined a bubble as stocks "priced above a level that can be justified by economic fundamentals," but this bubble includes social media. Social networking services (SNS) have seen huge growth since 2006, but some investors believed around 2014-2015, that the "bubble" was similar to the dot-com bubble of the late 1990s and early 2000s. In 2015, Mark Cuban, owner of the Dallas Mavericks NBA team and star of the TV show, Shark Tank, sounded an alarm on his personal blog over the social media bubble, calling it worse than the tech bubble in 2000 due to the lack of liquidity in social media stocks. A year prior, however, Cuban told CNBC that he did not believe social media stocks were on the verge of a bubble. In a letter to investors in 2014, David Einhorn, who runs the hedge-fund Greenlight Capital, wrote that "we are witnessing our second tech bubble in 15 years." He went on to write, "What is uncertain is how much further the bubble can expand, and what might pop it." Einhorn cited several factors supporting the existence an over-exuberance including "rejection of conventional valuation methods" and "huge first day IPO pops for companies that have done little more than use the right buzzwords and attract the right venture capital." Since those claims, services like Facebook, Twitter, Instagram, and Snapchat have grown to become multi-billion-dollar corporations generating enormous revenues, though some continue to lose money. == History of social networking services == Social networking services have grown and evolved with time since the launch of SixDegrees.com in 1997. Cutting edge at its time, SixDegrees.com allowed users to create a profile, invite friends, and connect within its platform. At its peak, SixDegrees.com had more than 3.5 million users. Between 1997 and 2001 more social sites aimed at allowing users to connect with others for personal, professional, or dating reasons. Friendster and MySpace were next to enter the social SNS arena, followed by Facebook in 2004. Even though MySpace had a following of more than 300 million users, it could not compete with Facebook, which now has overtaken the social networking world. However, as development of SNS started to emerge, a market saturation began to take effect. Some classrooms have begun to incorporate technology in daily learning as well as social channels specific to student's course work. Traditional social media sites are used, as are educational oriented sites such as ShowMe and Educreations Interactive Whiteboard. == Controversies == While SNS continue to play an influential role in helping people form real-world connections via the Internet, renewed concerns over the social media bubble have surfaced due to recent controversies. These threats include growing concerns about breaches in data, the rise of bot accounts, and the sharing of fake news on SNS platforms. There are also concerns that big data figures associated with these SNS are inflated or fake, as well as worries about the role the platforms played in national elections (see Russian interference in the 2016 United States elections). These issues have resulted in a lack of trust among the sites' users.
Software token
A software token (a.k.a. soft token) is a piece of a two-factor authentication security device that may be used to authorize the use of computer services. Software tokens are stored on a general-purpose electronic device such as a desktop computer, laptop, PDA, or mobile phone and can be duplicated. (Contrast hardware tokens, where the credentials are stored on a dedicated hardware device and therefore cannot be duplicated — absent physical invasion of the device) Because software tokens are something one does not physically possess, they are exposed to unique threats based on duplication of the underlying cryptographic material - for example, computer viruses and software attacks. Both hardware and software tokens are vulnerable to bot-based man-in-the-middle attacks, or to simple phishing attacks in which the one-time password provided by the token is solicited, and then supplied to the genuine website in a timely manner. Software tokens do have benefits: there is no physical token to carry, they do not contain batteries that will run out, and they are cheaper than hardware tokens. == Security architecture == There are two primary architectures for software tokens: shared secret and public-key cryptography. For a shared secret, an administrator will typically generate a configuration file for each end-user. The file will contain a username, a personal identification number, and the secret. This configuration file is given to the user. The shared secret architecture is potentially vulnerable in a number of areas. The configuration file can be compromised if it is stolen and the token is copied. With time-based software tokens, it is possible to borrow an individual's PDA or laptop, set the clock forward, and generate codes that will be valid in the future. Any software token that uses shared secrets and stores the PIN alongside the shared secret in a software client can be stolen and subjected to offline attacks. Shared secret tokens can be difficult to distribute, since each token is essentially a different piece of software. Each user must receive a copy of the secret, which can create time constraints. Some newer software tokens rely on public-key cryptography, or asymmetric cryptography. This architecture eliminates some of the traditional weaknesses of software tokens, but does not affect their primary weakness (ability to duplicate). A PIN can be stored on a remote authentication server instead of with the token client, making a stolen software token no good unless the PIN is known as well. However, in the case of a virus infection, the cryptographic material can be duplicated and then the PIN can be captured (via keylogging or similar) the next time the user authenticates. If there are attempts made to guess the PIN, it can be detected and logged on the authentication server, which can disable the token. Using asymmetric cryptography also simplifies implementation, since the token client can generate its own key pair and exchange public keys with the server.
Social media use in health awareness
Social media is being increasingly used for health awareness. It is not only used to promote health and wellness but also to motivate and guide public for various disease and ailments. Use of social media was proven to be cornerstone for awareness during COVID-19 management. In recent times, it is one of the most cost effective tool for cardiovascular health awareness since it can be used to motivate people for adoption of healthy lifestyle practices. Over the span of a decade, and Doctor Mike utilized social media to significantly impact the public about cardiovascular health awareness. == Background == Social media is proven to be useful for various chronic and incurable diseases where patients form groups and connect for sharing of knowledge. Similarly, health professionals, health institutions, and various other individuals and organizations have their own social media accounts for health information, awareness, guidance, or motivation for their patients. The utilization of social media for health awareness campaigns has become increasingly prevalent in recent years. The history of utilizing social media in health campaigns can be traced back to the early 2000s with the rise of platforms such as Facebook, Twitter, and YouTube. == Health campaigns == Health campaigns especially for chronic diseases like cancer and heart diseases are increasingly common on different social media platforms because social media serves as a cost-effective medium for launching and promoting health campaigns. Many organizations and governmental bodies use platforms like Twitter and Instagram to reach a wide audience. This wide outreach gives health campaigns more attention and support while raising awareness of their specific cause. Recently, there have been increasing calls for health organizations to involve the public and consumer groups in their social media health campaigns to ensure their acceptability with the target audience, encouraging use of collaborations and co-design of messages. == Research == When incorporating social media into health research recruitment, there is potential for a greater number of individuals to participate. Social media allows researchers to reach a wide range of participants while also allowing for recruitment 24 hours a day. There are many health organizations with large social media followings to allow them to reach a large amount of individuals. If these organizations pair with researchers and post flyers or make posts about a study they may be able to find the population that they are looking for. Although there are positives to using social media for health research recruitment, looking at the issues is important. Using this method in recruitment may cause competition between companies for the attention of the users. Another important point is that this is dependent on the type of health condition that is being researched. For chronic conditions, there are many organizations and platforms for support while for acute illnesses, there are not as many organizations that would be able to promote these studies and post for outreach. == Patient education == Patients increasingly turn to social media for health communication and health-related information. Online health communities, forums and blogs enable individuals to share their experiences, offer support, and seek advice from peers. Healthcare professionals also use social media to provide valuable insights and address common health concerns. The use of social media for patient education allows individuals to gain more information for their illness or disease along with gaining support from individuals who may be experiencing the same. Many health organizations such as cancer organizations or organizations for chronic health conditions often have social media platforms that allow individuals to connect and even share their own stories. Peer support is beneficial to patients emotionally and even for them to understand their condition and how to cope. Another way that social media allows individuals to gain more information is the improvement of health literacy. Medical jargon can be confusing for individuals especially when they are newly diagnosed with an illness or disease. Social media has been able to create platforms that explain the information that individuals may need when they are newly diagnosed or if they just want to learn more about their illness. Medical conditions can be confusing but using social media may allow for individuals to develop a better understanding in a manner that they understand. When patients have a better understanding of their health there will be a result of better health outcomes. == Misinformation == While social media is a powerful tool for health awareness, it comes with challenges. Misinformation can spread rapidly, potentially leading to incorrect or harmful health practices. Ensuring the accuracy of health-related information on social media is an ongoing concern. Health misinformation can be easily spread through social media to large amounts of individuals which can make this dangerous. Often, critics will question whether health-related information that is shared online is credible. Social media does not require the amount of regulation that could prevent false medical information from being disseminated online. According to The Influencer Effect: Exploring the persuasive communication tactics of social media influencers in the health and wellness industry by Deborah Deutsch, "the information shared is often lacking accepted scientific evidence or is contrary to industry standards, and, at times, deceptive, unethical, and misleading." One example of this was in 2020, when President Donald Trump said in speeches and on Twitter that hydroxychloroquine and chloroquine could be used to treat COVID-19. While these drugs are antimalaria, it was being spread that they could be used for COVID-19. This resulted in increased deaths and individuals falling ill from taking this drug and the misinformation that was spread about this drug. Spreading misinformation regarding health is one of the biggest concerns when using social media for health awareness. When spreading misinformation about health there is an increase in confusion about what is true and what is false regardless of who is saying this information. Along with the confusion of the public, there is a sense of mistrust that is a consequence of misinformation. Individuals are seeing different opinions which leads people to a situation where they do not know who to trust. While health misinformation is one of the largest issues, there are ways to help prevent it. As individuals, it is important to know where you are getting your information from and learn how to identify what is misinformation and avoid the spread of it. == Privacy and ethical issues == The sharing of personal health information on social media raises privacy and ethical concerns. Striking a balance between raising awareness and respecting individuals' privacy remains a delicate issue.
Database index
A database index is a data structure that improves the speed of data retrieval operations on a database table at the cost of additional writes and storage space to maintain the index data structure. Indexes are used to quickly locate data without having to search every row in a database table every time said table is accessed. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records. An index is a copy of selected columns of data, from a table, that is designed to enable very efficient search. An index normally includes a "key" or direct link to the original row of data from which it was copied, to allow the complete row to be retrieved efficiently. Some databases extend the power of indexing by letting developers create indexes on column values that have been transformed by functions or expressions. For example, an index could be created on upper(last_name), which would only store the upper-case versions of the last_name field in the index. Another option sometimes supported is the use of partial index, where index entries are created only for those records that satisfy some conditional expression. A further aspect of flexibility is to permit indexing on user-defined functions, as well as expressions formed from an assortment of built-in functions. == Usage == === Support for fast lookup === Most database software includes indexing technology that enables sub-linear time lookup to improve performance, as linear search is inefficient for large databases. Suppose a database contains N data items and one must be retrieved based on the value of one of the fields. A simple implementation retrieves and examines each item according to the test. If there is only one matching item, this can stop when it finds that single item, but if there are multiple matches, it must test everything. This means that the number of operations in the average case is O(N) or linear time. Since databases may contain many objects, and since lookup is a common operation, it is often desirable to improve performance. An index is any data structure that improves the performance of lookup. There are many different data structures used for this purpose. There are complex design trade-offs involving lookup performance, index size, and index-update performance. Many index designs exhibit logarithmic (O(log(N))) lookup performance and in some applications it is possible to achieve flat (O(1)) performance. === Policing the database constraints === Indexes are used to police database constraints, such as UNIQUE, EXCLUSION, PRIMARY KEY and FOREIGN KEY. An index may be declared as UNIQUE, which creates an implicit constraint on the underlying table. Database systems usually implicitly create an index on a set of columns declared PRIMARY KEY, and some are capable of using an already-existing index to police this constraint. Many database systems require that both referencing and referenced sets of columns in a FOREIGN KEY constraint are indexed, thus improving performance of inserts, updates and deletes to the tables participating in the constraint. Some database systems support an EXCLUSION constraint that ensures that, for a newly inserted or updated record, a certain predicate holds for no other record. This can be used to implement a UNIQUE constraint (with equality predicate) or more complex constraints, like ensuring that no overlapping time ranges or no intersecting geometry objects would be stored in the table. An index supporting fast searching for records satisfying the predicate is required to police such a constraint. == Index architecture and indexing methods == === Non-clustered === The data is present in arbitrary order, but the logical ordering is specified by the index. The data rows may be spread throughout the table regardless of the value of the indexed column or expression. The non-clustered index tree contains the index keys in sorted order, with the leaf level of the index containing the pointer to the record (page and the row number in the data page in page-organized engines; row offset in file-organized engines). In a non-clustered index, The physical order of the rows is not the same as the index order. The indexed columns are typically non-primary key columns used in JOIN, WHERE, and ORDER BY clauses. There can be more than one non-clustered index on a database table. === Clustered === Clustering alters the data block into a certain distinct order to match the index, resulting in the row data being stored in order. Therefore, only one clustered index can be created on a given database table. Clustered indexes can greatly increase overall speed of retrieval, but usually only where the data is accessed sequentially in the same or reverse order of the clustered index, or when a range of items is selected. Since the physical records are in this sort order on disk, the next row item in the sequence is immediately before or after the last one, and so fewer data block reads are required. The primary feature of a clustered index is therefore the ordering of the physical data rows in accordance with the index blocks that point to them. Some databases separate the data and index blocks into separate files, others put two completely different data blocks within the same physical file(s). === Cluster === When multiple databases and multiple tables are joined, it is called a cluster (not to be confused with clustered index described previously). The records for the tables sharing the value of a cluster key shall be stored together in the same or nearby data blocks. This may improve the joins of these tables on the cluster key, since the matching records are stored together and less I/O is required to locate them. The cluster configuration defines the data layout in the tables that are parts of the cluster. A cluster can be keyed with a B-tree index or a hash table. The data block where the table record is stored is defined by the value of the cluster key. == Column order == The order that the index definition defines the columns in is important. It is possible to retrieve a set of row identifiers using only the first indexed column. However, it is not possible or efficient (on most databases) to retrieve the set of row identifiers using only the second or greater indexed column. For example, in a phone book organized by city first, then by last name, and then by first name, in a particular city, one can easily extract the list of all phone numbers. However, it would be very tedious to find all the phone numbers for a particular last name. One would have to look within each city's section for the entries with that last name. Some databases can do this, others just won't use the index. In the phone book example with a composite index created on the columns (city, last_name, first_name), if we search by giving exact values for all the three fields, search time is minimal—but if we provide the values for city and first_name only, the search uses only the city field to retrieve all matched records. Then a sequential lookup checks the matching with first_name. So, to improve the performance, one must ensure that the index is created on the order of search columns. == Applications and limitations == Indexes are useful for many applications but come with some limitations. Consider the following SQL statement: SELECT first_name FROM people WHERE last_name = 'Smith';. To process this statement without an index the database software must look at the last_name column on every row in the table (this is known as a full table scan). With an index the database simply follows the index data structure (typically a B-tree) until the Smith entry has been found; this is much less computationally expensive than a full table scan. Consider this SQL statement: SELECT email_address FROM customers WHERE email_address LIKE '%@wikipedia.org';. This query would yield an email address for every customer whose email address ends with "@wikipedia.org", but even if the email_address column has been indexed the database must perform a full index scan. This is because the index is built with the assumption that words go from left to right. With a wildcard at the beginning of the search-term, the database software is unable to use the underlying index data structure (in other words, the WHERE-clause is not sargable). This problem can be solved through the addition of another index created on reverse(email_address) and a SQL query like this: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@wikipedia.org');. This puts the wild-card at the right-most part of the query (now gro.aidepikiw@%), which the index on reverse(email_address) can satisfy. When the wildcard characters are used on both sides of the search word as %wikipedia.org%, the index available on this field is not used. Rather only a sequential search is performed, which takes O ( N ) {\displaystyle
BitFunnel
BitFunnel is the search engine indexing algorithm and a set of components used in the Bing search engine, which were made open source in 2016. BitFunnel uses bit-sliced signatures instead of an inverted index in an attempt to reduce operations cost. == History == Progress on the implementation of BitFunnel was made public in early 2016, with the expectation that there would be a usable implementation later that year. In September 2016, the source code was made available via GitHub. A paper discussing the BitFunnel algorithm and implementation was released as through the Special Interest Group on Information Retrieval of the Association for Computing Machinery in 2017 and won the Best Paper Award. == Components == BitFunnel consists of three major components: BitFunnel – the text search/retrieval system itself WorkBench – a tool for preparing text for use in BitFunnel NativeJIT – a software component that takes expressions that use C data structures and transforms them into highly optimized assembly code == Algorithm == === Initial problem and solution overview === The BitFunnel paper describes the "matching problem", which occurs when an algorithm must identify documents through the usage of keywords. The goal of the problem is to identify a set of matches given a corpus to search and a query of keyword terms to match against. This problem is commonly solved through inverted indexes, where each searchable item is maintained with a map of keywords. In contrast, BitFunnel represents each searchable item through a signature. A signature is a sequence of bits which describe a Bloom filter of the searchable terms in a given searchable item. The bloom filter is constructed through hashing through several bit positions. === Theoretical implementation of bit-string signatures === The signature of a document (D) can be described as the logical-or of its term signatures: S D → = ⋃ t ∈ D S t → {\displaystyle {\overrightarrow {S_{D}}}=\bigcup _{t\in D}{\overrightarrow {S_{t}}}} Similarly, a query for a document (Q) can be defined as a union: S Q → = ⋃ t ∈ Q S t → {\displaystyle {\overrightarrow {S_{Q}}}=\bigcup _{t\in Q}{\overrightarrow {S_{t}}}} Additionally, a document D is a member of the set M' when the following condition is satisfied: S Q → ∩ S D → = S Q → {\displaystyle {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}} This knowledge is then combined to produce a formula where M' is identified by documents which match the query signature: M ′ = { D ∈ C ∣ S Q → ∩ S D → = S Q → } {\displaystyle M'=\left\{D\in C\mid {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}\right\}} These steps and their proofs are discussed in the 2017 paper. === Pseudocode for bit-string signatures === This algorithm is described in the 2017 paper. M ′ = ∅ foreach D ∈ C do if S D → ∩ S Q → = S Q → then M ′ = M ′ ∪ { D } endif endfor {\displaystyle {\begin{array}{l}M'=\emptyset \\{\texttt {foreach}}\ D\in C\ {\texttt {do}}\\\qquad {\texttt {if}}\ {\overrightarrow {S_{D}}}\cap {\overrightarrow {S_{Q}}}={\overrightarrow {S_{Q}}}\ {\texttt {then}}\\\qquad \qquad M'=M'\cup \{D\}\\\qquad {\texttt {endif}}\\{\texttt {endfor}}\end{array}}}