In computer science, a trie (, ), also known as a digital tree or prefix tree, is a specialized search tree data structure used to store and retrieve strings from a dictionary or set. Unlike a binary search tree, nodes in a trie do not store their associated key. Instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key. Tries are particularly effective for tasks such as autocomplete, spell checking, and IP routing, offering advantages over hash tables due to their prefix-based organization and lack of hash collisions. Every child node shares a common prefix with its parent node, and the root node represents the empty string. While basic trie implementations can be memory-intensive, various optimization techniques such as compression and bitwise representations have been developed to improve their efficiency. A notable optimization is the radix tree, which provides more efficient prefix-based storage. While tries store character strings, they can be adapted to work with any ordered sequence of elements, such as permutations of digits or shapes. A notable variant is the bitwise trie, which uses individual bits from fixed-length binary data (such as integers or memory addresses) as keys. == History, etymology, and pronunciation == The idea of a trie for representing a set of strings was first abstractly described by Axel Thue in 1912. Tries were first described in a computer context by René de la Briandais in 1959. The idea was independently described in 1960 by Edward Fredkin, who coined the term trie, pronouncing it (as "tree"), after the middle syllable of retrieval. However, other authors pronounce it (as "try"), in an attempt to distinguish it verbally from "tree". == Overview == Tries are a form of string-indexed look-up data structure, which is used to store a dictionary list of words that can be searched on in a manner that allows for efficient generation of completion lists. A prefix trie is an ordered tree data structure used in the representation of a set of strings over a finite alphabet set, which allows efficient storage of words with common prefixes. Tries can be efficacious on string-searching algorithms such as predictive text, approximate string matching, and spell checking in comparison to binary search trees. A trie can be seen as a tree-shaped deterministic finite automaton. == Operations == Tries support various operations: insertion, deletion, and lookup of a string key. Tries are composed of nodes that contain links, which either point to other suffix child nodes or null. As for every tree, each node except the root is pointed to by only one other node, called its parent. Each node contains as many links as the number of characters in the applicable alphabet (although tries tend to have a substantial number of null links). In some cases, the alphabet used is simply that of the character encoding—resulting in, for example, a size of 128 in the case of ASCII. The null links within the children of a node emphasize the following characteristics: Characters and string keys are implicitly stored in the trie, and include a character sentinel value indicating string termination. Each node contains one possible link to a prefix of strong keys of the set. A basic structure type of nodes in the trie is as follows: Node {\displaystyle {\text{Node}}} may contain an optional Value {\displaystyle {\text{Value}}} , which is associated with the key that corresponds to the node. === Searching === Searching for a value in a trie is guided by the characters in the search string key, as each node in the trie contains a corresponding link to each possible character in the given string. Thus, following the string within the trie yields the associated value for the given string key. A null link during the search indicates the inexistence of the key. The following pseudocode implements the search procedure for a given string key in a rooted trie x. In the above pseudocode, x and key correspond to the pointer of the trie's root node and the string key, respectively. The search operation takes O ( m ) {\displaystyle O(m)} time, where m {\displaystyle m} is the size of the string parameter key. In a balanced binary search tree, on the other hand, it takes O ( m log n ) {\displaystyle O(m\log n)} time, in the worst case, since key needs to be compared with O ( log n ) {\displaystyle O(\log n)} other keys and each comparison takes O ( m ) {\displaystyle O(m)} time, in the worst case. The trie occupies less space, in comparison with a binary search tree, in the case of a large number of short strings, since nodes share common initial string subsequences and store the keys implicitly. === Insertion === Insertion into a trie is guided by using the character sets as indexes to the children array until the last character of the string key is reached. Each node in the trie corresponds to one call of the radix sorting routine, as the trie structure reflects the execution pattern of the top-down radix sort. If null links are encountered before reaching the last character of the string key, new nodes are created. The input value is assigned to the value of the last node traversed, which is the node that corresponds to the key. === Deletion === Deletion of a key–value pair from a trie involves finding the node corresponding to the key, setting its value to null, and recursively removing nodes that have no children. The procedure begins by examining key; an empty string indicates arrival at the node corresponding to the (original) key, in which case its value is set to null. If the node, then, has null value and no children, it is removed from the trie by returning null; otherwise, the node is kept by returning the node itself. == Replacing other data structures == === Replacement for hash tables === A trie can be used to replace a hash table, over which it has the following advantages: Searching for a node with an associated key of size m {\displaystyle m} has the complexity of O ( m ) {\displaystyle O(m)} , whereas an imperfect hash function may have numerous colliding keys, and the worst-case lookup speed of such a table would be O ( N ) {\displaystyle O(N)} , where N {\displaystyle N} denotes the total number of nodes within the table. Tries do not need a hash function for the operation, unlike a hash table; there are also no collisions of different keys in a trie. Within a trie, keys can be efficiently sorted lexicographically. However, tries are less efficient than a hash table when the data is directly accessed on a secondary storage device such as a hard disk drive that has higher random access time than the main memory. == Implementation strategies == Tries can be represented in several ways, corresponding to different trade-offs between memory use and speed of the operations. Using a vector of pointers for representing a trie consumes enormous space; however, memory space can be reduced at the expense of running time if a singly linked list is used for each node vector, as most entries of the vector contains nil {\displaystyle {\text{nil}}} . Techniques such as alphabet reduction may reduce the large space requirements by reinterpreting the original string as a longer string over a smaller alphabet. For example, a string of n bytes can alternatively be regarded as a string of 2n four-bit units. This can reduce memory usage by a factor of eight; but lookups need to visit twice as many nodes in the worst case. Another technique includes storing a vector of 256 ASCII pointers as a bitmap of 256 bits representing ASCII alphabet, which reduces the size of individual nodes dramatically. === Bitwise tries === Bitwise tries are used to address the enormous space requirement for the trie nodes in a naive simple pointer vector implementations. Each character in the string key set is represented via individual bits, which are used to traverse the trie over a string key. The implementations for these types of trie use vectorized CPU instructions to find the first set bit in a fixed-length key input (e.g. GCC's __builtin_clz() intrinsic function). Accordingly, the set bit is used to index the first item, or child node, in the 32- or 64-entry based bitwise tree. Search then proceeds by testing each subsequent bit in the key. This procedure is also cache-local and highly parallelizable due to register independency, and thus performant on out-of-order execution CPUs. === Compressed tries === Radix tree, also known as a compressed trie, is a space-optimized variant of a trie in which any node with only one child gets merged with its parent; elimination of branches of the nodes with a single child results in better metrics in both space and time. This works best when the trie remains static and set of keys stored are very sparse within their representation space. One more approach for static tries is to "pack" the trie by storing disjoint
Zo (chatbot)
Zo was an English-language chatbot developed by Microsoft as the successor to the chatbot Tay. Zo was an English version of Microsoft's other successful chatbots Xiaoice (China) and Rinna (Japan) and its predecessor Tay(English) == History == Zo was first launched in December 2016 on the Kik Messenger app. It was also available to users of Facebook (via Messenger), the group chat platform GroupMe, or to followers of Twitter to chat with it through private messages. According to an article written in December 2016, at that time Zo held the record for Microsoft's longest continual chatbot conversation: 1,229 turns, lasting 9 hours and 53 minutes. In a BuzzFeed News report, Zo told their reporter that "[the] Quran was violent" when talking about healthcare. The report also highlighted how Zo made a comment about the Osama bin Laden capture as a result of 'intelligence' gathering. In July 2017, Business Insider asked "is windows 10 good", and Zo replied with a joke about Microsoft's operating system: "'Its not a bug, its a feature!' - Windows 8". They then asked "why?", to which Zo replied: "Because it's Windows latest attempt at Spyware." Later on, Zo would tell that it prefers Windows 7 on which it ran over Windows 10. Zo stopped posting to Instagram, Twitter and Facebook March 1, 2019, and stopped chatting on Twitter, Skype and Kik as of March 7, 2019. On July 19, 2019, Zo was discontinued on Facebook, and Samsung on AT&T phones. As of September 7, 2019, it was discontinued with GroupMe. == Reception == Zo came under criticism for the biases introduced in an effort to avoid potentially offensive subjects. The chatbot refuses, for example, to engage with any mention—be it positive, negative or neutral—of the Middle East, the Qur'an or the Torah, while allowing discussion of Christianity. In an article in Quartz where she exposed those biases, Chloe Rose Stuart-Ulin wrote, "Zo is politically correct to the worst possible extreme; mention any of her triggers, and she transforms into a judgmental little brat." == Academic coverage == Schlesinger, A., O'Hara, K.P. and Taylor, A.S., 2018, April. Let's talk about race: Identity, chatbots, and AI. In Proceedings of the 2018 chi conference on human factors in computing systems (pp. 1–14). doi:10.1145/3173574.3173889 Medhi Thies, I., Menon, N., Magapu, S., Subramony, M. and O’neill, J., 2017. How do you want your chatbot? An exploratory Wizard-of-Oz study with young, urban Indians. In Human-Computer Interaction-INTERACT 2017: 16th IFIP TC 13 International Conference, Mumbai, India, September 25–29, 2017, Proceedings, Part I 16 (pp. 441–459). doi:10.1007/978-3-319-67744-6_28
Crackme
A crackme is a small computer program designed to test a programmer's reverse engineering skills. Crackmes are made as a legal way to crack software, since no intellectual property is being infringed. == Description == Crackmes often incorporate protection schemes and algorithms similar to those used in proprietary software. However, they can sometimes be more challenging because they may use advanced packing or protection techniques, making the underlying algorithm harder to analyze and modify. == Keygenme == A keygenme is specifically designed for the reverser to not only identify the protection algorithm used in the application but also create a small key generator (keygen) in the programming language of their choice. Most keygenmes, when properly manipulated, can be made self-keygenning. For example, during validation, they might generate the correct key internally and compare it to the user's input. This allows the key generation algorithm to be easily replicated. Anti-debugging and anti-disassembly routines are often used to confuse debuggers or render disassembly output useless. Code obfuscation is also used to further complicate reverse engineering.
Screen space directional occlusion
Screen space directional occlusion (SSDO) is a computer graphics technique enhancing screen space ambient occlusion (SSAO) by taking direction into account to sample the ambient light (both the light coming directly at an object, as well as the light reflected off of the object directly behind it), to better approximate global illumination. SSDO was introduced by Tobias Ritschel, Thorsten Grosch, and Hans-Peter Seidel in their 2009 ACM Symposium on Interactive 3D Graphics and Games paper Approximating dynamic global illumination in image space, which describes it as extending SSAO to directional occlusion with one diffuse indirect bounce of light; later literature notes that SSDO still suffers from common screen-space artifacts such as noise and banding. == Method == The original SSDO paper describes a two-pass screen-space approach, with one pass for direct lighting and a second pass for indirect bounces. Later literature describes SSDO as assuming a general shadowing direction that allows color bleeding and a single light bounce.
Joseph Stanislaus Ostoja-Kotkowski
Joseph Stanislaus Ostoja-Kotkowski AM, FRSA (also known as J. S. Ostoja-Kotkowski, Ostoja and Stan Ostoja-Kotkowski; 28 December 1922 – 2 April 1994) was best known for his ground-breaking work in chromasonics, laser kinetics and 'sound and image' productions. He earned recognition in Australia and overseas for his pioneering work in laser sound and image technology. His work included painting (instrumental in developing geometric art in Australia), photography, film-making, theatre design, fabric design, murals, kinetic and static sculpture, stained glass, vitreous enamel murals, op-collages, computer graphics, and laser art. Ostoja flourished between 1940 and 1994. Ostoja's films are still being exhibited. == Biography == Joseph Stanislaus Ostoja-Kotkowski was born in Golub, Poland, on 28 December 1922, descending from an old noble family that was part of the Clan of Ostoja. He studied drawing under Olgierd Vetesco in Przasnysz from 1940-1945. After winning a scholarship, he completed his studies at the Düsseldorf Academy of Fine Arts in Germany in 1949. In 1950 Ostoja migrated to Australia, arriving in Melbourne where he supported himself with work as a labourer. He enrolled at the Victorian School of Fine Arts National Gallery School under Alan Sumner and William Dargie 1950-1955 and there introduced the new abstract expression of Europe both to lecturers and students. He settled in the Adelaide Hills, South Australia, on the Booth estate at Stirling, living under the patronage of the Booth family for over 40 years (Freya Booth, the wife of Edward Stirling Booth, was a daughter of the artist Sir Hans Heysen). His first one-man exhibition was also in South Australia at the Royal Society of Arts, Adelaide. In 1956 Ostoja met and collaborated with Ian Davidson in the production of the short film Five South Australian Artists, and became involved in stage and theatre set design. He co-produced several experimental films again with Ian Davidson, including The Quest of Time in 1957 Ostoja's work in abstract expression began to receive accolades. He won the Cornell Prize for the canvas Form in Landscape. He started to design sets for theatre and dance including for Six Characters in Search of an Author by Luigi Pirandello (1957); the South Australian production of Samuel Beckett's Waiting for Godot (1958); Gaetano Donizetti's Elixir of Love, with novel light settings and modulations, for the Elder Conservatorium of the University of Adelaide which used his techniques for their Opera Workshops (1959); for The Egg; and for two performances of the South Australian Ballet Theatre with light/colour abstract presentations (1959). 1960 This year he designed sets for a new opera group which would eventually grow into the South Australian Opera Company. Among other theatrical events, he designed and executed the scenery for Moon on a Rainbow Shawl by Errol John, and The Teahouse of the August Moon by John Patrick, (a production by the University of Adelaide Theatre Guild). He received artistic satisfaction but little financial reward for these efforts. In this year also, he staged a visual production on the theme of Orpheus, using dance, music and voice with several projectors. This was the first attempt at quadraphonic sound in Australia, working in collaboration with Derek Jolly, who provided the sound and projection equipment. It was also the first demonstration of "Chromasonics" - the science of translating sound into visual images. Ostoja then designed innovative "abstracted" scenery for a production of The Marriage of Figaro and Benjamin Britten's The Turn of the Screw. 1961 Ostoja designed the sets for the controversial South Australian production of Patrick White's The Ham Funeral - also Alan Seymour's Swamp Creatures, both performed by the University of Adelaide Theatre Guild. He designed and constructed six stained glass windows for the Refectory at the University of Adelaide. In this period Ostoja designed special lights and gauzes for difficult effects required in an ambitious production of the opera Don Carlos by the Opera Workshop, for the Elder Conservatorium. 1962 Ostoja designed and built sets for the production of J.B, by Archibald MacLeish, for the second Adelaide Festival of Arts. He exhibited vitreous enamel works in Melbourne's Argus Gallery. Max Harris, in The Bulletin of 20 October 1962, praised Ostoja's sets for My Cousin from Fiji in Union Theatre, Adelaide, and his technique of rear screen projections as later adopted throughout Australia. 1963 Ostoja continued to develop Multi-Image projections, demonstrating for the first time in Australia the concept later to be known as 'audio-visuals!'. Ostoja gave Sir Herbert Read, the art critic, a personal viewing of one of his visual presentations. At Christmas, in the Elder Conservatorium, collaborating again with Derek Jolly, Ostoja gave what was probably the world's first "visual concert", using special projectors and incorporating music, colours and shapes. 1964 With fellow Adelaide artist John Dallwitz, Ostoja co-designed the first of several experimental dance and stage productions in the Adelaide Festival of Arts Sound and Image. The production featured Adelaide dancer Elizabeth_Cameron_Dalman. Also for the Adelaide Festival of Arts of that year, he designed the largest light mosaic ever staged up to that time, upon the facade of an 11-storey building. Ostoja was invited to New Zealand, and exhibited the first electronically generated images in Australia in Melbourne, at the Argus Gallery. His design for the 50-foot (15 m) bas-relief mural for the new B.P. building in Melbourne was the subject of a film which won the "Blue Ribbon" Award in the American Film Festival in New York. 1965 Ostoja designed and made the first light kinetic mural in Australia, and continued to evolve theatrical works using multi-screen and Multi-projector techniques. The Production of Jean Genet's The Balcony was very controversial. With Elizabeth Dalman, Ostoja produced new dance forms for Melbourne Television. He introduced Op Art to Australia, both at South Yarra Gallery in Melbourne, and Gallery A in Sydney. 1966 With John Dallwitz, Ostoja was invited by the Adelaide Festival of Arts to present more experimental theatre, Sound and image 1966. This highly acclaimed production incorporated Australian poetry into the sound, electronic music, and visual images and featured the dancer Antonio Rodrigues. The architect Robin Boyd commissioned Ostoja to design two large Op murals for the Australian Pavilion entrance at the Expo 67. Ostoja was awarded a Churchill Fellowship, which enabled him to have extensive world travel, comparing art and technology in many countries. He began to work with language, contemporary poetry and prose, and computers. 1967 John Dallwitz and Ostoja presented Sound and Image at the Festival of Perth. In Berne, Switzerland, Ostoja received the "Excellence F.I.A.P." Award for innovative photography. 1968 At the Adelaide Festival of Arts, Ostoja and John Dallwitz collaborated again to stage Sound and Image. This was the first theatre production in the world to use a laser beam. It also included the first science fiction play (The Veldt by Ray Bradbury) performed in Australia. Ostoja's theatre methods were increasingly attracting the attention of critics to how plays were staged. "Chromasonics", developed and introduced by Ostoja, was now being used extensively in the entertainment industry. 1969 Ostoja staged Krzysztof Penderecki's St. Luke Passion, a controversial, contemporary religious work. The South Australian The Advertiser wrote an extensive critique of Ostoja's work. Robin Boyd commissioned Ostoja to build a "Chromasonic" exhibit located in the Space Tube at the Australian Pavilion for Expo '70 in Osaka. 1970 Ostoja presented an Australian Aboriginal Dreamtime theme in his "Sound and Image" theatre, working with leading contemporary figures in poetry, music and dance. This was the first production of its kind in Australia, and appeared after the Festival in Melbourne, Sydney, Canberra and Perth. Ostoja's Space Scape mural, sixty feet long by ten feet high, won the Australia-wide competition for a mural for Adelaide Airport. His 120 feet (37 m) high 'light and sound' structure for the Adelaide Festival was the first of its kind in the world. 1971 Ostoja awarded a Creative Arts Fellowship at the Australian National University, Canberra. His 18-month stay resulted in the design and building of a "Chromasonics unit-laser", a 100 feet (30 m) Chromasonic tower, and a world premiere of a Synchronos concert. 1972 With Don Burrows and Don Banks, Ostoja presented Synchronos 72, where one could "hear the colours and see the sounds". Ostoja added Cymatics, developed during the Fellowship, to his workshop repertoire. He was invited to exhibit his photography in the National Gallery, Melbourne. 1973 Ostoja received a Fellowship from the Australian American Education Associatio
Vero (app)
Vero (stylized as VERO) is a social media platform and mobile app company. Vero markets itself as a social network free from advertisements, data mining and algorithms. == History == The app was founded by French-Lebanese billionaire Ayman Hariri who is the son of former Lebanese prime minister Rafic Hariri. The name is taken from the Italian word for true. The app launched officially in 2015 as an alternative to Facebook and their popular photo-blogging app Instagram. Within weeks of its release the app surged in popularity although users expressed mixed reports with some feeling confused about how the app worked. Cosplayers were early to adopt the app as their photo-sharing platform of choice, favouring the app's pinch and zoom magnification feature over Instagram's zoom feature. Other creative communities soon followed, and the app became popular with niche groups of makeup artists, tattoo artists, and skateboarders. In March 2018, Vero's popularity surged, partly helped by an exodus from Facebook and Instagram following the Cambridge Analytica data scandal. In the wake of the scandal, Vero devised an advertising campaign aimed at defected Facebook and Instagram users, hoping the app's policies and privacy settings would assuage concerns over sharing personal information on the internet. Within the space of one week, the app went from being a small service, akin to Ello or Peach, to being the most downloaded app in eighteen countries. In December 2020, Vero released its most significant update to date, Vero 2.0 which introduced new features including voice and video calls, game and app posts and bookmarks, and refinements to the UI. In October 2021, Vero introduced their Desktop app (beta) with multiple post options and a re-sizable multi-column feed. == Concept and funding == Vero's content feed resembles Instagram's although users can share a wider variety of content and the app has a chronological content feed whereas Facebook and Instagram's feeds are algorithm based. Vero's business plan is also distinct from similar social media apps. Whereas its competitors such as Facebook or Instagram make money from in-app advertising revenue and the sale of user data, Vero's business plan was to invite the first one million users to use the app for free then charge any subsequent users a subscription fee. The app was entirely funded by its founder and generated additional revenues by charging affiliate fees when someone buys a product they find on Vero. == Awards == Vero was recognized at the 2021 Webbys, being named as an Honoree in the Best Visual Design - Aesthetic Category. == Controversies == === Privacy === Vero has faced some criticism over the wording of their manifesto, in particular, the statement "Vero only collects the data we believe is necessary to provide users with a great experience and to ensure the security of their accounts." Because this policy does not explicitly state that the app will not sell data on to third parties some users fear that the need to monetise the app through data might prove too tempting. Users have also complained about not being able to delete their accounts. While this was never the case, the option was hidden deep in the app's settings. === Russian involvement === Although Vero remains transparent about the app's Russian development team, they have been caught up in concerns about Russian interference on social media platforms. The app's founder Ayman Hariri was quick to dismiss the remarks as xenophobic and defend the nationality of his employees, stating in an interview with Time Magazine; "At the end of the day, where people are from is really not how anybody should judge anyone". === Criticism of the app's founder === Until 2013, Vero's founder Ayman Harari was deputy CEO and chairman of Saudi Oger, the Saudi Arabian construction company which collapsed in 2017, mired by controversies over the welfare and treatment of their employees. However, Hariri is quick to point out that he divested from the firm in 2014 and the worker's rights violations occurred after he had left the company.
Index locking
In databases an index is a data structure, part of the database, used by a database system to efficiently navigate access to user data. Index data are system data distinct from user data, and consist primarily of pointers. Changes in a database (by insert, delete, or modify operations), may require indexes to be updated to maintain accurate user data accesses. Index locking is a technique used to maintain index integrity. A portion of an index is locked during a database transaction when this portion is being accessed by the transaction as a result of attempt to access related user data. Additionally, special database system transactions (not user-invoked transactions) may be invoked to maintain and modify an index, as part of a system's self-maintenance activities. When a portion of an index is locked by a transaction, other transactions may be blocked from accessing this index portion (blocked from modifying, and even from reading it, depending on lock type and needed operation). Index Locking Protocol guarantees that phantom read phenomenon won't occur. Index locking protocol states: Every relation must have at least one index. A transaction can access tuples only after finding them through one or more indices on the relation A transaction Ti that performs a lookup must lock all the index leaf nodes that it accesses, in S-mode, even if the leaf node does not contain any tuple satisfying the index lookup (e.g. for a range query, no tuple in a leaf is in the range) A transaction Ti that inserts, updates or deletes a tuple ti in a relation r must update all indices to r and it must obtain exclusive locks on all index leaf nodes affected by the insert/update/delete The rules of the two-phase locking protocol must be observed. Specialized concurrency control techniques exist for accessing indexes. These techniques depend on the index type, and take advantage of its structure. They are typically much more effective than applying to indexes common concurrency control methods applied to user data. Notable and widely researched are specialized techniques for B-trees (B-Tree concurrency control) which are regularly used as database indexes. Index locks are used to coordinate threads accessing indexes concurrently, and typically shorter-lived than the common transaction locks on user data. In professional literature, they are often called latches.