Spatial embedding is one of feature learning techniques used in spatial analysis where points, lines, polygons or other spatial data types. representing geographic locations are mapped to vectors of real numbers. Conceptually it involves a mathematical embedding from a space with many dimensions per geographic object to a continuous vector space with a much lower dimension. Such embedding methods allow complex spatial data to be used in neural networks and have been shown to improve performance in spatial analysis tasks == Embedded data types == Geographic data can take many forms: text, images, graphs, trajectories, polygons. Depending on the task, there may be a need to combine multimodal data from different sources. The next section describes examples of different types of data and their uses. === Text === Geolocated posts on social media can be used to acquire a library of documents bound to a given place that can be later transformed to embedded vectors using word embedding techniques. === Image === Satellites and aircraft collect digital spatial data acquired from remotely sensed images which can be used in machine learning. They are sometimes hard to analyse using basic image analysis methods and convolutional neural networks can be used to acquire an embedding of images bound to a given geographical object or a region. === Point === A single point of interest (POI) can be assigned multiple features that can be used in machine learning. These could be demographic, transportation, meteorological, or economic data, for example. When embedding single points, it is common to consider the entire set of available points as nodes in a graph. === Line / multiline === Among other things, motion trajectories are represented as lines (multilines). Individual trajectories are embedded taking into account travel time, distances and also features of points visited along the way. Embedding of trajectories allows to improve performance of such tasks as clustering and also categorization. === Polygon === The geographic areas analyzed in machine learning are defined by both administrative boundaries and top-down division into grids of regular shapes such as rectangles, for example. Both types are represented as polygons and, like points, can be assigned different demographic, transportation, or economic features. A polygon can also have features related to the size of the area or shape it represents. === Graph === An example domain where graph representation is used is the street layout in a city, where vertices can be intersections and edges can be roads. The vertices can also be destination points like public transport stops or important points in the city, and the edges represent the flow between them. Embedding graphs or single vertices allows to improve accuracy of analysis methods in which the treated geographical domain can be represented as a network. == Usage == POI recommendation - generating personalized point of interest recommendations based on user preferences. Next/future location prediction - prediction of the next location a person will go to based on their historical trajectory. Zone functions classification - based on different mobility of people or POI distribution a function of a given area in a city can be predicted. Crime prediction - estimation of crime rate in different regions of a city. Local event detection - studying spatio-temporal changes in embeddings can provide valuable information in detection of local event occurring in specific location. Regional mobility popularity prediction - analysis of mobility can show patterns in popularity of different regions in a city. Shape matching - finding a similar shape of given polygon, for example finding building with the same shape as input building. Travel time estimation - predicting estimated travel time given current traffic conditions and special occurring events. Time estimation for on-demand food delivery - estimation of delivery time when placing an order through the website. == Temporal aspect == Some of the data analyzed has a timestamp associated with it. In some cases of data analysis this information is omitted and in others it is used to divide the set into groups. The most common division is the separation of weekdays from weekends or division into hours of the day. This is particularly important in the analysis of mobility data, because the characteristics of mobility during the week and at different times of the day are very different from each other. Another area in which time division into, for example, individual months can be used is in the analysis of tourism of a given region. In order to take such a split into account, embedding methods treat the time stamp specifically or separate versions of the model are developed for different subgroups of the analyzed set.
Protocol engineering
Protocol engineering is the application of systematic methods to the development of communication protocols. It uses many of the principles of software engineering, but it is specific to the development of distributed systems. == History == When the first experimental and commercial computer networks were developed in the 1970s, the concept of protocols was not yet well developed. These were the first distributed systems. In the context of the newly adopted layered protocol architecture (see OSI model), the definition of the protocol of a specific layer should be such that any entity implementing that specification in one computer would be compatible with any other computer containing an entity implementing the same specification, and their interactions should be such that the desired communication service would be obtained. On the other hand, the protocol specification should be abstract enough to allow different choices for the implementation on different computers. It was recognized that a precise specification of the expected service provided by the given layer was important. It is important for the verification of the protocol, which should demonstrate that the communication service is provided if both protocol entities implement the protocol specification correctly. This principle was later followed during the standardization of the OSI protocol stack, in particular for the transport layer. It was also recognized that some kind of formalized protocol specification would be useful for the verification of the protocol and for developing implementations, as well as test cases for checking the conformance of an implementation against the specification. While initially mainly finite-state machine were used as (simplified) models of a protocol entity, in the 1980s three formal specification languages were standardized, two by ISO and one by ITU. The latter, called SDL, was later used in industry and has been merged with UML state machines. == Principles == The following are the most important principles for the development of protocols: Layered architecture: A protocol layer at the level n consists of two (or more) entities that have a service interface through which the service of the layer is provided to the users of the protocol, and which uses the service provided by a local entity of level (n-1). The service specification of a layer describes, in an abstract and global view, the behavior of the layer as visible at the service interfaces of the layer. The protocol specification defines the requirements that should be satisfied by each entity implementation. Protocol verification consists of showing that two (or more) entities satisfying the protocol specification will provide at their service interfaces the specified service of that layer. The (verified) protocol specification is used mainly for the following two activities: The development of an entity implementation. Note that the abstract properties of the service interface are defined by the service specification (and also used by the protocol specification), but the detailed nature of the interface can be chosen during the implementation process, separately for each entity. Test suite development for conformance testing. Protocol conformance testing checks that a given entity implementation conforms to the protocol specification. The conformance test cases are developed based on the protocol specification and are applicable to all entity implementations. Therefore standard conformance test suites have been developed for certain protocol standards. == Methods and tools == Tools for the activities of protocol verification, entity implementation and test suite development can be developed when the protocol specification is written in a formalized language which can be understood by the tool. As mentioned, formal specification languages have been proposed for protocol specification, and the first methods and tools where based on finite-state machine models. Reachability analysis was proposed to understand all possible behaviors of a distributed system, which is essential for protocol verification. This was later complemented with model checking. However, finite-state descriptions are not powerful enough to describe constraints between message parameters and the local variables in the entities. Such constraints can be described by the standardized formal specification languages mentioned above, for which powerful tools have been developed. It is in the field of protocol engineering that model-based development was used very early. These methods and tools have later been used for software engineering as well as hardware design, especially for distributed and real-time systems. On the other hand, many methods and tools developed in the more general context of software engineering can also be used of the development of protocols, for instance model checking for protocol verification, and agile methods for entity implementations. == Constructive methods for protocol design == Most protocols are designed by human intuition and discussions during the standardization process. However, some methods have been proposed for using constructive methods possibly supported by tools to automatically derive protocols that satisfy certain properties. The following are a few examples: Semi-automatic protocol synthesis: The user defines all message sending actions of the entities, and the tool derives all necessary reception actions (even if several messages are in transit). Synchronizing protocol: The state transitions of one protocol entity are given by the user, and the method derives the behavior of the other entity such that it remains in states that correspond to the former entity. Protocol derived from service specification: The service specification is given by the user and the method derives a suitable protocol for all entities. Protocol for control applications: The specification of one entity (called the plant - which must be controlled) is given, and the method derives a specification of the other entity such that certain fail states of the plant are never reached and certain given properties of the plant's service interactions are satisfied. This is a case of supervisory control. == Books == Ming T. Liu, Protocol Engineering, Advances in Computers, Volume 29, 1989, Pages 79–195. G.J. Holzmann, Design and Validation of Computer Protocols, Prentice Hall, 1991. H. König, Protocol Engineering, Springer, 2012. M. Popovic, Communication Protocol Engineering, CRC Press, 2nd Ed. 2018. P. Venkataram, S.S. Manvi, B.S. Babu, Communication Protocol Engineering, 2014.
Xulvi-Brunet–Sokolov algorithm
Xulvi-Brunet and Sokolov's algorithm generates networks with chosen degree correlations. This method is based on link rewiring, in which the desired degree is governed by parameter ρ. By varying this single parameter it is possible to generate networks from random (when ρ = 0) to perfectly assortative or disassortative (when ρ = 1). This algorithm allows to keep network's degree distribution unchanged when changing the value of ρ. == Assortative model == In assortative networks, well-connected nodes are likely to be connected to other highly connected nodes. Social networks are examples of assortative networks. This means that an assortative network has the property that almost all nodes with the same degree are linked only between themselves. The Xulvi-Brunet–Sokolov algorithm for this type of networks is the following. In a given network, two links connecting four different nodes are chosen randomly. These nodes are ordered by their degrees. Then, with probability ρ, the links are randomly rewired in such a way that one link connects the two nodes with the smaller degrees and the other connects the two nodes with the larger degrees. If one or both of these links already existed in the network, the step is discarded and is repeated again. Thus, there will be no self-connected nodes or multiple links connecting the same two nodes. Different degrees of assortativity of a network can be achieved by changing the parameter ρ. Assortative networks are characterized by highly connected groups of nodes with similar degree. As assortativity grows, the average path length and clustering coefficient increase. == Disassortative model == In disassortative networks, highly connected nodes tend to connect to less-well-connected nodes with larger probability than in uncorrelated networks. Examples of such networks include biological networks. The Xulvi-Brunet and Sokolov's algorithm for this type of networks is similar to the one for assortative networks with one minor change. As before, two links of four nodes are randomly chosen and the nodes are ordered with respect to their degrees. However, in this case, the links are rewired (with probability p) such that one link connects the highest connected node with the node with the lowest degree and the other link connects the two remaining nodes randomly with probability 1 − ρ. Similarly, if the new links already existed, the previous step is repeated. This algorithm does not change the degree of nodes and thus the degree distribution of the network.
Knowledge spillover
Knowledge spillover is an exchange of ideas among individuals. Knowledge spillover is usually replaced by terminations of technology spillover, R&D spillover and/or spillover (economics) when the concept is specific to technology management and innovation economics. In knowledge management economics, knowledge spillovers are non-rival knowledge market costs incurred by a party not agreeing to assume the costs that has a spillover effect of stimulating technological improvements in a neighbor through one's own innovation. Such innovations often come from specialization within an industry. There are two kinds of knowledge spillovers: internal and external. Internal knowledge spillover occurs if there is a positive impact of knowledge between individuals within an organization that produces goods and/or services. An external knowledge spillover occurs when the positive impact of knowledge is between individuals outside of a production organization. Marshall–Arrow–Romer (MAR) spillovers, Porter spillovers and Jacobs spillovers are three types of spillovers. == Conceptualizations == === Marshall–Arrow–Romer === Marshall–Arrow–Romer (MAR) spillover has its origins in 1890, where the English economist Alfred Marshall developed a theory of knowledge spillovers. Knowledge spillovers later were extended by economists Kenneth Arrow (1962) and Paul Romer (1986). In 1992, Edward Glaeser, Hedi Kallal, José Scheinkman, and Andrei Shleifer pulled together the Marshall–Arrow–Romer views on knowledge spillovers and accordingly named the view MAR spillover in 1992. Under the Marshall–Arrow–Romer (MAR) spillover view, the proximity of firms within a common industry often affects how well knowledge travels among firms to facilitate innovation and growth. The closer the firms are to one another, the greater the MAR spillover. The exchange of ideas is largely from employee to employee, in that employees from different firms in an industry exchange ideas about new products and new ways to produce goods. The opportunity to exchange ideas that lead to innovations key to new products and improved production methods. Research on the Cambridge IT Cluster (UK) suggests that technological knowledge spillovers might only happen rarely and are less important than other cluster benefits such as labour market pooling. === Porter === Porter (1990), like MAR, argues that knowledge spillovers in specialized, geographically concentrated industries stimulate growth. He insists, however, that local competition, as opposed to local monopoly, fosters the pursuit and rapid adoption of innovation. He gives examples of Italian ceramics and gold jewellery industries, in which hundreds of firms are located together and fiercely compete to innovate since the alternative to innovation is demise. Porter's externalities are maximized in cities with geographically specialized, competitive industries. === Jacobs === Under the Jacobs spillover view, the proximity of firms from different industries affect how well knowledge travels among firms to facilitate innovation and growth. This is in contrast to MAR spillovers, which focus on firms in a common industry. The diverse proximity of a Jacobs spillover brings together ideas among individuals with different perspectives to encourage an exchange of ideas and foster innovation in an industrially diverse environment. Developed in 1969 by urbanist Jane Jacobs and John Jackson the concept that Detroit’s shipbuilding industry from the 1830s was the critical antecedent leading to the 1890s development of the auto industry in Detroit since the gasoline engine firms easily transitioned from building gasoline engines for ships to building them for automobiles. == Incoming and outgoing spillovers == Knowledge spillover has asymmetric directions. The focal entity and receives or outflows know-how to others, creating incoming and outgoing spillovers. Cassiman and Veugelers (2002) use survey data and estimate incoming and outgoing spillover and study the economic impacts. Incoming spillover increases growth opportunity and productivity improvements of receivers, while outgoing spillover leads to free rider problem in the technology competition. Chen et al. (2013) use econometric method to gauge incoming spillover, a way that applies for all companies without survey. They find that incoming spillover explains R&D profits of industrial firms. == Policy implications == As information is largely non-rival in nature, certain measures must be taken to ensure that, for the originator, the information remains a private asset. As the market cannot do this efficiently, public regulations have been implemented to facilitate a more appropriate equilibrium. As a result, the concept of intellectual property rights have developed and ensure the ability of entrepreneurs to temporarily hold on to the profitability of their ideas through patents, copyrights, trade secrets, and other governmental safeguards. Conversely, such barriers to entry prevent the exploitation of informational developments by rival firms within an industry. For example, Wang (2023) indicates that technology spillovers are reduced by 27% to 51% when trade secrets laws are implemented by the Uniform Trade Secrets Act in the US. On the other hand, when the research and development of a private firm results in a social benefit, unaccounted for within the market price, often greater than the private return of the firm's research, then a subsidy to offset the underproduction of that benefit might be offered to the firm in return for its continued output of that benefit. Government subsidies are often controversial, and while they might often result in a more appropriate social equilibrium, they could also lead to undesirable political repercussions as such a subsidy must come from taxpayers, some of whom may not directly benefit from the researching firm's subsidized knowledge spillover. The concept of knowledge spillover is also used to justify subsidies to foreign direct investment, as foreign investors help diffuse technology among local firms. == Examples == Business parks are a good specific example of concentrated businesses that may benefit from MAR spillover. Many semiconductor firms intentionally located their research and development facilities in Silicon Valley to take advantage of MAR spillover. In addition, the film industry in Los Angeles, California, and elsewhere relies on a geographic concentration of specialists (directors, producers, scriptwriters, and set designers) to bring together narrow aspects of movie-making into a final product. A general example of a knowledge spillover could be the collective growth associated with the research and development of online social networking tools like Facebook, YouTube, and Twitter. Such tools have not only created a positive feedback loop, and a host of originally unintended benefits for their users, but have also created an explosion of new software, programming platforms, and conceptual breakthroughs that have perpetuated the development of the industry as a whole. The advent of online marketplaces, the utilization of user profiles, the widespread democratization of information, and the interconnectivity between tools within the industry have all been products of each tool's individual developments. These developments have since spread outside the industry into the mainstream media as news and entertainment firms have developed their own market feedback applications within the tools themselves, and their own versions of online networking tools (e.g. CNN’s iReport).
Semantic heterogeneity
Semantic heterogeneity is when database schema or datasets for the same domain are developed by independent parties, resulting in differences in meaning and interpretation of data values. Beyond structured data, the problem of semantic heterogeneity is compounded due to the flexibility of semi-structured data and various tagging methods applied to documents or unstructured data. Semantic heterogeneity is one of the more important sources of differences in heterogeneous datasets. Yet, for multiple data sources to interoperate with one another, it is essential to reconcile these semantic differences. Decomposing the various sources of semantic heterogeneities provides a basis for understanding how to map and transform data to overcome these differences. == Classification == One of the first known classification schemes applied to data semantics is from William Kent in the late 80s. Kent's approach dealt more with structural mapping issues than differences in meaning, which he pointed to data dictionaries as potentially solving. One of the most comprehensive classifications is from Pluempitiwiriyawej and Hammer, "Classification Scheme for Semantic and Schematic Heterogeneities in XML Data Sources". They classify heterogeneities into three broad classes: Structural conflicts arise when the schema of the sources representing related or overlapping data exhibit discrepancies. Structural conflicts can be detected when comparing the underlying schema. The class of structural conflicts includes generalization conflicts, aggregation conflicts, internal path discrepancy, missing items, element ordering, constraint and type mismatch, and naming conflicts between the element types and attribute names. Domain conflicts arise when the semantics of the data sources that will be integrated exhibit discrepancies. Domain conflicts can be detected by looking at the information contained in the schema and using knowledge about the underlying data domains. The class of domain conflicts includes schematic discrepancy, scale or unit, precision, and data representation conflicts. Data conflicts refer to discrepancies among similar or related data values across multiple sources. Data conflicts can only be detected by comparing the underlying sources. The class of data conflicts includes ID-value, missing data, incorrect spelling, and naming conflicts between the element contents and the attribute values. Moreover, mismatches or conflicts can occur between set elements (a "population" mismatch) or attributes (a "description" mismatch). Michael Bergman expanded upon this schema by adding a fourth major explicit category of language, and also added some examples of each kind of semantic heterogeneity, resulting in about 40 distinct potential categories . This table shows the combined 40 possible sources of semantic heterogeneities across sources: A different approach toward classifying semantics and integration approaches is taken by Sheth et al. Under their concept, they split semantics into three forms: implicit, formal and powerful. Implicit semantics are what is either largely present or can easily be extracted; formal languages, though relatively scarce, occur in the form of ontologies or other description logics; and powerful (soft) semantics are fuzzy and not limited to rigid set-based assignments. Sheth et al.'s main point is that first-order logic (FOL) or description logic is inadequate alone to properly capture the needed semantics. == Relevant applications == Besides data interoperability, relevant areas in information technology that depend on reconciling semantic heterogeneities include data mapping, semantic integration, and enterprise information integration, among many others. From the conceptual to actual data, there are differences in perspective, vocabularies, measures and conventions once any two data sources are brought together. Explicit attention to these semantic heterogeneities is one means to get the information to integrate or interoperate. A mere twenty years ago, information technology systems expressed and stored data in a multitude of formats and systems. The Internet and Web protocols have done much to overcome these sources of differences. While there is a large number of categories of semantic heterogeneity, these categories are also patterned and can be anticipated and corrected. These patterned sources inform what kind of work must be done to overcome semantic differences where they still reside.
Grammar checker
A grammar checker, in computing terms, is a program, or part of a program, that attempts to verify written text for grammatical correctness. Grammar checkers are most often implemented as a feature of a larger program, such as a word processor, but are also available as a stand-alone application that can be activated from within programs that work with editable text. The implementation of a grammar checker makes use of natural language processing. == History == The earliest "grammar checkers" were programs that checked for punctuation and style inconsistencies, rather than a complete range of possible grammatical errors. The first system was called Writer's Workbench, and was a set of writing tools included with Unix systems as far back as the 1970s. The whole Writer's Workbench package included several separate tools to check for various writing problems. The "diction" tool checked for wordy, trite, clichéd or misused phrases in a text. The tool would output a list of questionable phrases and provide suggestions for improving the writing. The "style" tool analyzed the writing style of a given text. It performed a number of readability tests on the text and output the results, and gave some statistical information about the sentences of the text. Aspen Software of Albuquerque, New Mexico released the earliest version of a diction and style checker for personal computers, Grammatik, in 1981. Grammatik was first available for a Radio Shack - TRS-80, and soon had versions for CP/M and the IBM PC. Reference Software International of San Francisco, California, acquired Grammatik in 1985. Development of Grammatik continued, and it became an actual grammar checker that could detect writing errors beyond simple style checking. Other early diction and style checking programs included Punctuation & Style, Correct Grammar, RightWriter and PowerEdit. While all the earliest programs started as simple diction and style checkers, all eventually added various levels of language processing, and developed some level of true grammar checking capability. Until 1992, grammar checkers were sold as add-on programs. There were a large number of different word processing programs available at that time, with WordPerfect and Microsoft Word the top two in market share. In 1992, Microsoft decided to add grammar checking as a feature of Word, and licensed CorrecText, a grammar checker from Houghton Mifflin that had not yet been marketed as a standalone product. WordPerfect answered Microsoft's move by acquiring Reference Software, and the direct descendant of Grammatik is still included with WordPerfect. As of 2019, grammar checkers are built into systems like Google Docs, browser extensions like Grammarly and Qordoba, desktop applications like Ginger, free and open-source software like LanguageTool, and text editor plugins like those available from WebSpellChecker Software. == Technical issues == The earliest writing style programs checked for wordy, trite, clichéd, or misused phrases in a text. This process was based on simple pattern matching. The heart of the program was a list of many hundreds or thousands of phrases that are considered poor writing by many experts. The list of questionable phrases included alternative wording for each phrase. The checking program would simply break text into sentences, check for any matches in the phrase dictionary, flag suspect phrases and show an alternative. These programs could also perform some mechanical checks. For example, they would typically flag doubled words, doubled punctuation, some capitalization errors, and other simple mechanical mistakes. True grammar checking is more complex. While a programming language has a very specific syntax and grammar, this is not so for natural languages. One can write a somewhat complete formal grammar for a natural language, but there are usually so many exceptions in real usage that a formal grammar is of minimal help in writing a grammar checker. One of the most important parts of a natural language grammar checker is a dictionary of all the words in the language, along with the part of speech of each word. The fact that a natural word may be used as any one of several parts of speech (such as "free" being used as an adjective, adverb, noun, or verb) greatly increases the complexity of any grammar checker. A grammar checker will find each sentence in a text, look up each word in the dictionary, and then attempt to parse the sentence into a form that matches a grammar. Using various rules, the program can then detect various errors, such as agreement in tense, number, word order, and so on. It is also possible to detect some stylistic problems with the text. For example, some popular style guides such as The Elements of Style deprecate excessive use of the passive voice. Grammar checkers may attempt to identify passive sentences and suggest an active-voice alternative. The software elements required for grammar checking are closely related to some of the development issues that need to be addressed for speech recognition software. In voice recognition, parsing can be used to help predict which word is most likely intended, based on part of speech and position in the sentence. In grammar checking, the parsing is used to detect words that fail to follow accepted grammar usage. Recently, research has focused on developing algorithms which can recognize grammar errors based on the context of the surrounding words. == Criticism == Grammar checkers are considered a type of foreign language writing aid which non-native speakers can use to proofread their writings as such programs endeavor to identify syntactical errors. However, as with other computerized writing aids such as spell checkers, popular grammar checkers are often criticized when they fail to spot errors and incorrectly flag correct text as erroneous. The linguist Geoffrey K. Pullum argued in 2007 that they were generally so inaccurate as to do more harm than good: "for the most part, accepting the advice of a computer grammar checker on your prose will make it much worse, sometimes hilariously incoherent."
Irish logarithm
The Irish logarithm was a system of number manipulation invented by Percy Ludgate for machine multiplication. The system used a combination of mechanical cams as lookup tables and mechanical addition to sum pseudo-logarithmic indices to produce partial products, which were then added to produce results. The technique is similar to Zech logarithms (also known as Jacobi logarithms), but uses a system of indices original to Ludgate. == Concept == Ludgate's algorithm compresses the multiplication of two single decimal numbers into two table lookups (to convert the digits into indices), the addition of the two indices to create a new index which is input to a second lookup table that generates the output product. Because both lookup tables are one-dimensional, and the addition of linear movements is simple to implement mechanically, this allows a less complex mechanism than would be needed to implement a two-dimensional 10×10 multiplication lookup table. Ludgate stated that he deliberately chose the values in his tables to be as small as he could make them; given this, Ludgate's tables can be simply constructed from first principles, either via pen-and-paper methods, or a systematic search using only a few tens of lines of program code. They do not correspond to either Zech logarithms, Remak indexes or Korn indexes. == Pseudocode == The following is an implementation of Ludgate's Irish logarithm algorithm in the Python programming language: Table 1 is taken from Ludgate's original paper; given the first table, the contents of Table 2 can be trivially derived from Table 1 and the definition of the algorithm. Note since that the last third of the second table is entirely zeros, this could be exploited to further simplify a mechanical implementation of the algorithm.