AMV:Algorithm Metadata Vocabulary
type: Ontology
version IRI: https://w3id.org/amv/1.0
creator: Biswanath Dutta (https://sites.google.com/view/bdutta)
creator: Jyotima Patel (https://www.linkedin.com/in/jyotima-patel-61220411b)
description: AMV v1.0 was first published on June 16, 2021. This is the revised version dated on February 6, 2023.
description: Metadata vocabularies are used in various domains of study. It provides an in-depth description of the resources. In this work, we develop Algorithm Metadata Vocabulary (AMV), a vocabulary for capturing and storing the metadata about the algorithms (a procedure or a set of rules that is followed step-by-step to solve a problem, especially by a computer). The snag faced by the researchers in the current time is the failure of getting relevant results when searching for algorithms in any search engine. AMV is represented as a semantic model and produced OWL file, which can be directly used by anyone interested to create and publish algorithm metadata as a knowledge graph, or to provide metadata service through SPARQL endpoint. To design the vocabulary, we propose a well-defined methodology, which considers real issues faced by the algorithm users and the practitioners. The evaluation shows a promising result.
issued: 2021-06-16
modified: 2023-02-06
publisher: Indian Statistical Institute (https://www.isibang.ac.in/)
rights: https://creativecommons.org/publicdomain/zero/1.0/
preferred namespace prefix: amv
version info: V1.0
competency question: Example competency questions. CQ1: What characteristics or properties are common across all algorithms? CQ2: List all algorithms that compute the solution to problem X along with their types and input. CQ3: Retrieve an algorithm that solves problem X with its details like best case space complexity, best case time complexity, and the problems related to it. CQ4: Retrieve all the algorithms X which are expressed in the form of a flowchart. CQ5: Which Sorting algorithms are derived from the already existing sorting algorithms?
vocabulary used: http://xmlns.com/foaf/0.1/
vocabulary used: http://purl.org/dc/terms/
vocabulary used: http://purl.org/ontology/bibo/
vocabulary used: http://www.w3.org/2004/02/skos/core#
vocabulary used: http://www.w3.org/ns/dcat#
vocabulary used: http://www.wikidata.org/entity/
vocabulary used: https://schema.org/

access rights
type: ObjectProperty
sub property of: rights
inverse of: access rights of
domain: Thing
range: Rights Statement
comment: Information about who access the resource or an indication of its security status. Access Rights may include information regarding access or restrictions based on privacy, security, or other policies. Examples of access rights are: Public, Internal, Department (source: https://www.dublincore.org/groups/government/accessRights/)

contributor
type: ObjectProperty
inverse of: contributor of
domain: Thing
range: Agent
comment: An agent who contributes towards the algorithm.

creator
type: ObjectProperty
inverse of: creator of
domain: Thing
range: Agent
comment: The person who created the algorithm.
alt label: author

has Part
type: ObjectProperty
sub property of: relation
inverse of: is Part Of
type: TransitiveProperty
domain: Thing
range: Thing
comment: A related resource that is included either physically or logically in the described resource.(https://www.dublincore.org/specifications/dublin-core/dcmi-terms/#http://purl.org/dc/terms/isPartOf)

has Version
type: ObjectProperty
sub property of: relation
inverse of: is Version Of
type: TransitiveProperty
domain: Thing
range: Thing
comment: A related resource (e.g., algorithm, program) that is a version, edition, or adaptation of the described resource.

is Part Of
type: ObjectProperty
sub property of: relation
type: TransitiveProperty
domain: Thing
range: Thing
comment: A related resource in which the described resource is physically or logically included.(https://www.dublincore.org/specifications/dublin-core/dcmi-terms/#http://purl.org/dc/terms/isPartOf)

is Version Of
type: ObjectProperty
sub property of: relation
type: TransitiveProperty
domain: Thing
range: Thing
comment: A related resource (e.g., algorithm, program) of which the described resource is a version, edition, or adaptation.

license
type: ObjectProperty
sub property of: rights
inverse of: license of
domain: Thing
range: LicenseDocument
comment: The licence under which the algorithm is published.

publisher
type: ObjectProperty
inverse of: publisher of
domain: Class
  union of: Algorithm
  union of: Implementation
  union of: Information Resource
range: Agent
comment: An entity responsible for making the resource available.

relation
type: ObjectProperty
type: SymmetricProperty
domain: Thing
range: Thing
comment: A related resource. For example, a Sorting problem is related to a problem Convex Hull.

rights
type: ObjectProperty
inverse of: rights of
domain: Thing
range: Rights Statement
comment: Information about rights held in and over the resource.

subject
type: ObjectProperty
sub property of: topObjectProperty
inverse of: subject of
domain: Thing
range: Academic discipline
comment: A topic of the resource.

comment
type: ObjectProperty
inverse of: comment of
domain: Class
  union of: Algorithm
  union of: Implementation
  union of: Information Resource
range: Comment
comment: Comments, typically from users.

generalization of
type: ObjectProperty
sub property of: relation
inverse of: specialization of
type: TransitiveProperty
domain: Thing
range: Thing
comment: An entity that is a generalization of another. E.g., Distribution sort algorithm is a generalization of Bucket sort.

had derivation
type: ObjectProperty
inverse of: was Derived From
type: TransitiveProperty
domain: Thing
range: Thing

had primary source
type: ObjectProperty
sub property of: was Derived From
inverse of: was primary source of
type: TransitiveProperty
domain: Thing
range: Thing
comment: A primary source for a topic refers to something produced by some agent with direct experience and knowledge about the topic, at the time of the topic's study, without benefit from hindsight. Because of the directness of primary sources, they 'speak for themselves' in ways that cannot be captured through the filter of secondary sources. As such, it is important for secondary sources to reference those primary sources from which they were derived, so that their reliability can be investigated. A primary source relation is a particular case of derivation of secondary materials from their primary sources. It is recognized that the determination of primary sources can be up to interpretation, and should be done according to conventions accepted within the application's domain.

had revision
type: ObjectProperty
sub property of: had derivation
inverse of: was revision of
type: TransitiveProperty
domain: Thing
range: Thing

specialization of
type: ObjectProperty
sub property of: relation
type: TransitiveProperty
domain: Thing
range: Thing
comment: An entity that is specialization of (... is a kind of) another entity and shares all aspects of the later including its own specific aspects. E.g., Bucket sort algorithm is a specialization of (a kind of) Distribution sort.

was Derived From
type: ObjectProperty
type: TransitiveProperty
domain: Thing
range: Thing
comment: A derivation is a transformation of an entity into another, an update of an entity resulting in a new one, or the construction of a new entity based on a pre-existing entity.

was primary source of
type: ObjectProperty
sub property of: had derivation
type: TransitiveProperty
domain: Thing
range: Thing

was revision of
type: ObjectProperty
sub property of: was Derived From
type: TransitiveProperty
domain: Thing
range: Thing
comment: A revision is a derivation for which the resulting entity is a revised version of some original. The implication here is that the resulting entity contains substantial content from the original. Revision is a particular case of derivation.

depiction
type: ObjectProperty
inverse of: depicts
domain: Thing
range: Image
comment: A depiction of some thing.

depicts
type: ObjectProperty
domain: Image
range: Thing
comment: The depiction property is a relationship between a thing and an Image that depicts it. As such it is an inverse of the depicts relationship.

affiliation of
type: ObjectProperty
inverse of: affliation
domain: Organization
range: Person

affliation
type: ObjectProperty
domain: Person
range: Organization
comment: An organization that the person is affiliated with. For example, a school/university.

algorithm type for
type: ObjectProperty
inverse of: is a type of
domain: Algorithmic Type
range: Algorithm
comment: Is an algorithm type for an algorithm.

analysis function type
type: ObjectProperty
sub property of: topObjectProperty
inverse of: analysis function type of
domain: Algorithm
range: AlgorithmAnalysisFunction
comment: The various function types for analysis of algorithms like logarithmic functions, exponential functions etc.

analysis function type of
type: ObjectProperty
domain: AlgorithmAnalysisFunction
range: Algorithm

available algorithm
type: ObjectProperty
inverse of: computes solution to
domain: Problem
range: Algorithm
comment: An algorithm for a given problem.

comment of
type: ObjectProperty
domain: Comment
range: Class
  union of: Algorithm
  union of: Implementation
  union of: Information Resource

computes solution to
type: ObjectProperty
domain: Algorithm
range: Problem
comment: The type of problem the algorithm solves.
comment: Problem that this algorithm or method solves.(https://www.wikidata.org/wiki/Property:P2159)

data Structure Used
type: ObjectProperty
inverse of: data Structure Used In
domain: Algorithm
range: Data Structure
comment: The data structure used in an algorithm.

data Structure Used In
type: ObjectProperty
domain: Data Structure
range: Algorithm

form of expression
type: ObjectProperty
inverse of: form Of expression of
domain: Algorithm
range: Form of expression
comment: The form of expression of an Algorithm.

form Of expression of
type: ObjectProperty
domain: Form of expression
range: Algorithm
comment: The form of expression of an Algorithm.

has implementation
type: ObjectProperty
inverse of: implementation of
domain: Thing
range: Implementation
comment: The various applications of the algorithm.

has message complexity
type: ObjectProperty
sub property of: has metric
inverse of: message complexity of
domain: Algorithm
range: Message complexity

has metric
type: ObjectProperty
inverse of: metric of
domain: Algorithm
range: Metric

has performance metric
type: ObjectProperty
sub property of: has metric
inverse of: performance metric of
domain: Algorithm
range: Performance metric

has space complexity
type: ObjectProperty
sub property of: has metric
inverse of: space complexity of
domain: Algorithm
range: Space complexity

has subalgorithm
type: ObjectProperty
sub property of: has Part
inverse of: subalgorithm of
type: TransitiveProperty
domain: Algorithm
range: Algorithm

has subproblem
type: ObjectProperty
sub property of: has Part
inverse of: subproblem of
type: TransitiveProperty
domain: Problem
range: Problem
comment: a problem that is contingent on or forms a part of another more inclusive problem.

has time complexity
type: ObjectProperty
sub property of: has metric
inverse of: time complexity of
domain: Algorithm
range: Time complexity

implementation of
type: ObjectProperty
domain: Implementation
range: Thing
comment: The various applications of the algorithm.

output image
type: ObjectProperty
sub property of: depiction
inverse of: is output image of
domain: Thing
range: Image

is a type of
type: ObjectProperty
domain: Algorithm
range: Algorithmic Type
comment: The different type of algorithmic techniques that are used to solve the various existing problems in the most optimized manner.This classification is neither exhaustive nor disjoint but highlights the various ways in which a problem can be addressed.
comment: The nature or genre of an algorithm.

is input image of
type: ObjectProperty
sub property of: topObjectProperty
inverse of: input image
domain: Image
range: Thing

is output image of
type: ObjectProperty
sub property of: topObjectProperty
domain: Image
range: Thing

is similar to
type: ObjectProperty
sub property of: relation
type: SymmetricProperty
domain: Thing
range: Thing
comment: A pointer to another, functionally similar thing (or multiple things), for example, an algorithm is similar to another algorithm or algorithms, a problem is similar to another problem or problems, etc.

loop construct
type: ObjectProperty
inverse of: loop construct of
domain: Algorithm
range: Loop construct
comment: The loop best suited for the algorithm.

loop construct of
type: ObjectProperty
domain: Loop construct
range: Algorithm

mathematical property
type: ObjectProperty
inverse of: mathematicalPropertyUsed
domain: Algorithm
range: Mathematical property
comment: The mathematical concept used to solve the problem.

mathematicalPropertyUsed
type: ObjectProperty
domain: Mathematical property
range: Algorithm

message complexity of
type: ObjectProperty
sub property of: metric of
domain: Message complexity
range: Algorithm

metric of
type: ObjectProperty
domain: Metric
range: Algorithm

operatingSystemFor
type: ObjectProperty
inverse of: runs on Operating System
domain: Operating system
range: Implementation

input image
type: ObjectProperty
sub property of: depiction
domain: Thing
range: Image

performance metric of
type: ObjectProperty
sub property of: metric of
domain: Performance metric
range: Algorithm

programming language
type: ObjectProperty
inverse of: programming language used in
domain: Implementation
range: Programming language
comment: In which all language the implementation of the algorithm/ problem is available.

access rights of
type: ObjectProperty
sub property of: rights of
domain: Rights Statement
range: Thing

appeared In
type: ObjectProperty
inverse of: contains
domain: Algorithm
range: Information Resource
comment: An algorithm appeared in a publication.

branch Of
type: ObjectProperty
inverse of: has branch
type: TransitiveProperty
domain: Academic discipline
range: Academic discipline

contains
type: ObjectProperty
domain: Information Resource
range: Algorithm

contributor of
type: ObjectProperty
domain: Agent
range: Thing

creator of
type: ObjectProperty
domain: Agent
range: Thing
alt label: author of

hasArticle
type: ObjectProperty
inverse of: published in
domain: Periodical
range: Article

has branch
type: ObjectProperty
type: TransitiveProperty
domain: Academic discipline
range: Academic discipline
comment: Branch of the academic discipline.

license of
type: ObjectProperty
sub property of: rights of
domain: LicenseDocument
range: Thing

published in
type: ObjectProperty
domain: Article
range: Periodical

publisher of
type: ObjectProperty
domain: Agent
range: Class
  union of: Algorithm
  union of: Implementation
  union of: Information Resource

rights of
type: ObjectProperty
domain: Rights Statement
range: Thing

subject of
type: ObjectProperty
domain: Academic discipline
range: Thing
comment: A topic of the resource for.

runs on Operating System
type: ObjectProperty
domain: Implementation
range: Operating system

space complexity of
type: ObjectProperty
sub property of: metric of
domain: Space complexity
range: Algorithm

subalgorithm of
type: ObjectProperty
sub property of: is Part Of
type: TransitiveProperty
domain: Algorithm
range: Algorithm

subproblem of
type: ObjectProperty
sub property of: is Part Of
type: TransitiveProperty
domain: Problem
range: Problem

time complexity of
type: ObjectProperty
sub property of: metric of
domain: Time complexity
range: Algorithm

programming language used in
type: ObjectProperty
domain: Programming language
range: Implementation

available
type: DatatypeProperty
sub property of: date
domain: Thing
range: Literal
comment: Date (often a range) that the resource became or will become available.

bibliographic citation
type: DatatypeProperty
domain: Thing
range: Literal
comment: A bibliographic reference for the resource.

created
type: DatatypeProperty
sub property of: date
domain: Thing
range: Literal
comment: The date of creation of the algorithm.

date
type: DatatypeProperty
sub property of: topDataProperty
domain: Thing
range: Literal
comment: A point or period of time associated with an event in the lifecycle of the resource.

dateSubmitted
type: DatatypeProperty
sub property of: date
domain: Thing
range: Literal
comment: Date of submission of the resource.

description
type: DatatypeProperty
domain: Thing
range: string
comment: A statement that represents something in words. It is the act of describing something. The description can include, for instance, the purpose of a thing, the scope, the area of applications of a thing, the history, etc.
comment: An account of the resource.

identifier
type: DatatypeProperty
domain: Thing
range: Literal
comment: An unambiguous reference to the resource within a given context.

modified
type: DatatypeProperty
sub property of: date
domain: Thing
range: Literal
comment: Date on which the resource was changed.

title
type: DatatypeProperty
domain: Thing
range: string
comment: A name given to the resource (e.g., book, algorithm, research software).

byte size
type: DatatypeProperty
domain: Implementation
range: decimal
comment: The size of a distribution in bytes.

landingPage
type: DatatypeProperty
sub property of: page
domain: Thing
range: string
comment: A Web page that can be navigated to in a Web browser to gain access to the catalog, a dataset, its distributions and/or additional information.

version
type: DatatypeProperty
domain: Class
  union of: Algorithm
  union of: Implementation
range: Literal
comment: The version number of a resource.

first name
type: DatatypeProperty
domain: Person
range: string
comment: The first name of a person.

homepage
type: DatatypeProperty
domain: Thing
range: anyURI
comment: A homepage for some thing.

last name
type: DatatypeProperty
domain: Person
range: string
comment: The last name of a person.

personal mailbox
type: DatatypeProperty
domain: Agent
range: string
comment: A personal mailbox, ie. an Internet mailbox associated with exactly one owner, the first owner of this mailbox. This is a 'static inverse functional property', in that there is (across time and change) at most one individual that ever has any particular value for foaf:mbox.

name
type: DatatypeProperty
domain: Thing
range: string
comment: The name for some thing.

page
type: DatatypeProperty
domain: Thing
range: string
comment: A page or document about this thing.

accessibility
type: DatatypeProperty
domain: Algorithm
range: string
comment: The information on access (i.e modify, read, download) to the algorithm.

accuracy
type: DatatypeProperty
domain: Performance metric
range: decimal
comment: How close the output will be to a set point.
comment: It is the measure of the degree of closeness of a measured or calculated value to its actual value.

acronym
type: DatatypeProperty
domain: Thing
range: string

alternative title
type: DatatypeProperty
domain: Thing
range: string
comment: An alternative title of a resource.

average message complexity
type: DatatypeProperty
domain: Message complexity
range: string

average space complexity
type: DatatypeProperty
domain: Space complexity
range: string
comment: Space complexity of an algorithm on average.(https://www.wikidata.org/wiki/Property:P3757)

average time complexity
type: DatatypeProperty
domain: Time complexity
range: string
comment: Time complexity of an algorithm on average. (https://www.wikidata.org/wiki/Property:P3754)

best case message complexity
type: DatatypeProperty
domain: Message complexity
range: string

best case space complexity
type: DatatypeProperty
domain: Space complexity
range: string
comment: Space complexity of an algorithm at least.(https://www.wikidata.org/wiki/Property:P3756)

best case time complexity
type: DatatypeProperty
domain: Time complexity
range: string
comment: Time complexity of an algorithm at least. (https://www.wikidata.org/wiki/Property:P3753)

constraint
type: DatatypeProperty
domain: Algorithm
range: string
comment: Limitations that an algorithm posses.

cpu time limit
type: DatatypeProperty
domain: Implementation
range: integer
comment: Time taken by CPU while executing the program.(In seconds)

defining formula
type: DatatypeProperty
domain: Mathematical property
range: string
comment: The mathematical formula used for solving the problem. Mathematical formula representing a theorem or law.

definiton
type: DatatypeProperty
domain: Thing
range: string

edge Case
type: DatatypeProperty
domain: Algorithm
range: string
comment: Input values that require special handling in an algorithm. When using the algorithm at an extreme(maximum or minimum) operating parameters.

excerpt
type: DatatypeProperty
domain: Thing
range: string
comment: An excerpt is a contiguous or discontiguous portion, or a passage selected from a larger work or document.

time of earliest written record
type: DatatypeProperty
domain: Algorithm
range: dateTime
comment: First time a subject was mentioned in writing.(https://www.wikidata.org/wiki/Property:P1249)

flexible
type: DatatypeProperty
domain: Algorithm
range: boolean
comment: The algorithm written in such a way that it allows to add new features without changing the existing module.

formal definition
type: DatatypeProperty
domain: Thing
range: string

input
type: DatatypeProperty
domain: Class
  union of: Algorithm
  union of: Implementation
range: string
comment: Something that is operated on by any process or system. An algorithm can have zero or more inputs.

input description
type: DatatypeProperty
sub property of: description
domain: Algorithm
range: string
comment: Input description of an algorithm.

library URI
type: DatatypeProperty
domain: Class
  union of: Algorithm
  union of: Implementation
range: anyURI
comment: Unique identifier of the central place where the algorithm is stored.

number Of Nested Loops
type: DatatypeProperty
domain: Algorithm
range: nonNegativeInteger
comment: The number of nested loops in an algorithm.

number Of Steps
type: DatatypeProperty
domain: Algorithm
range: nonNegativeInteger
comment: Total number of steps that the algorithm takes to solve a certain problem.

offline algorithm
type: DatatypeProperty
domain: Algorithm
range: boolean
comment: The complete dataset is required to start processing.

online algorithm
type: DatatypeProperty
domain: Algorithm
range: boolean
comment: The data can be feed while processing.

optimal
type: DatatypeProperty
domain: Algorithm
range: boolean
comment: An algorithm is optimal means the time complexity in the worst case is a lower bound of the function that describes the time complexity in the worst case of a problem that the algorithm in question solves.

output
type: DatatypeProperty
domain: Class
  union of: Algorithm
  union of: Implementation
range: string
comment: Output after processing the input.

precision
type: DatatypeProperty
domain: Performance metric
range: float
comment: It is a measure of quality, higher precision means algorithm returns more relevant results than irrelevant ones.

problem description
type: DatatypeProperty
sub property of: description
domain: Problem
range: string
comment: A description providing the problem statement.

download link
type: DatatypeProperty
domain: Class
  union of: Algorithm
  union of: Implementation
range: anyURI
comment: URL which can be used to download a work.

rating
type: DatatypeProperty
domain: Thing
range: integer
comment: Rating given on the basis of usefulness of a thing.

read me
type: DatatypeProperty
domain: Thing
range: string
comment: Provide a description or Link to algorithm, or similar resource "Readme page".

readable
type: DatatypeProperty
domain: Algorithm
range: boolean
comment: Is the algorithm readable/understandable to the user.

recall
type: DatatypeProperty
domain: Performance metric
range: float
comment: percentage of total relevent result correctly classified by the algorithm.

worst case message complexity
type: DatatypeProperty
domain: Message complexity
range: string

worst case space complexity
type: DatatypeProperty
domain: Space complexity
range: string
comment: Space complexity of an algorithm at most.(https://www.wikidata.org/wiki/Property:P3755)

worst case time complexity
type: DatatypeProperty
domain: Time complexity
range: string
comment: Time complexity of an algorithm at most. (https://www.wikidata.org/wiki/Property:P3752)

LicenseDocument
type: Class
subclass of: Rights Statement
comment: A legal document giving official permission to do something with a Resource.

Rights Statement
type: Class
comment: A statement about the intellectual property rights (IPR) held in or over a Resource, a legal document giving official permission to do something with a resource, or a statement about access rights.

Academic article
type: Class
subclass of: Article
comment: A scholarly academic article, typically published in a journal.

Article
type: Class
subclass of: Document
comment: A written composition in prose, usually nonfiction, on a specific topic, forming an independent part of a book or other publication, as a newspaper or magazine.

Book
type: Class
subclass of: Document
comment: A written or printed work of fiction or nonfiction, usually on sheets of paper fastened or bound together within covers.

Book Section
type: Class
subclass of: Document Part
comment: A section of a book.

Chapter
type: Class
subclass of: Book Section
comment: A chapter of a book.
alt label: Book chapter

Collected Document
type: Class
subclass of: Document
comment: A document that simultaneously contains other documents.

Collection
type: Class
subclass of: Information Resource
comment: A collection of Documents or Collections.

Document
type: Class
equivalent class: Document
subclass of: Information Resource
comment: A document (noun) is a bounded physical representation of body of information designed with the capacity (and usually intent) to communicate. A document may manifest symbolic, diagrammatic or sensory-representational information.
comment: The algorithm was published in what kind of literature.

Document Part
type: Class
subclass of: Document
comment: a distinct part of a larger document or collected document.

Edited Book
type: Class
subclass of: Collected Document
comment: An edited book.

Excerpt
type: Class
subclass of: Document Part
comment: A passage selected from a larger work.

Issue
type: Class
subclass of: Collected Document
comment: something that is printed or published and distributed, esp. a given number of a periodical.

Journal
type: Class
subclass of: Periodical
disjoint with: Magazine
comment: A periodical of scholarly journal Articles.
comment: a periodical dedicated to a particular subject; "he reads the medical journals."

Magazine
type: Class
subclass of: Periodical
comment: A periodical of magazine Articles. A magazine is a publication that is issued periodically, usually bound in a paper cover, and typically contains essays, stories, poems, etc., by many writers, and often photographs and drawings, frequently specializing in a particular subject or area, as hobbies, news, or sports.
comment: A periodical publication containing articles and illustrations, often on a particular subject or aimed at a particular readership.

Manuscript
type: Class
subclass of: Document
comment: An unpublished Document, which may also be submitted to a publisher for publication.

Patent
type: Class
subclass of: Document
comment: A document describing the exclusive right granted by a government to an inventor to manufacture, use, or sell an invention for a certain number of years.

Periodical
type: Class
subclass of: Collection
disjoint with: Series
disjoint with: Website
comment: A group of related documents issued at regular intervals.

Proceedings
type: Class
subclass of: Book
comment: A compilation of documents published from an event, such as a conference.

Reference Source
type: Class
subclass of: Document
comment: A document that presents authoritative reference information, such as a dictionary or encylopedia.

Report
type: Class
subclass of: Document
comment: A document describing an account or statement describing in detail an event, situation, or the like, usually as the result of observation, inquiry, etc..

Series
type: Class
subclass of: Collection
comment: A loose, thematic, collection of Documents, often Books.

Slide
type: Class
subclass of: Document Part
comment: A slide in a slideshow.

Thesis
type: Class
subclass of: Document
comment: A document created to summarize research findings associated with the completion of an academic degree.

Webpage
type: Class
subclass of: Document
comment: A web page is an online document available (at least initially) on the world wide web. A web page is written first and foremost to appear on the web, as distinct from other online resources such as books, manuscripts or audio documents which use the web primarily as a distribution mechanism alongside other more traditional methods such as print.

Website
type: Class
subclass of: Collection
comment: A group of Webpages accessible on the Web.

Comment
type: Class
comment: A comment on an item - for example, a comment on a blog post. The comment's content is expressed via the text property, and its topic via about, properties shared with all CreativeWorks.

Academic discipline
type: Class
equivalent class: Academic discipline
comment: Academic field of study or profession.

Algorithm
type: Class
equivalent class: Algorithm
comment: Unambiguous specification of how to solve a class of problems.(https://www.wikidata.org/wiki/Q8366)

Programming language
type: Class
equivalent class: Programming language
comment: language designed to communicate instructions to a machine.
alt label: Computer language

Agent
type: Class
comment: A resource that acts or has the power to act. Example of Agents include person and organization.

Document
type: Class
subclass of: Information Resource
comment: The Document class represents those things which are, broadly conceived, 'documents'.

Image
type: Class
subclass of: Document
comment: The class Image is a sub-class of Document corresponding to those documents which are images.

Organization
type: Class
subclass of: Agent
disjoint with: Person
comment: An agent belonging to some social institutions such as companies, associations etc, that has a collective goal.

Person
type: Class
subclass of: Agent
comment: A human.

Operating system
type: Class
comment: An Operating System (OS) is an interface between a computer user and computer hardware. An operating system is a software which performs all the basic tasks like file management, memory management, process management, handling input and output, and controlling peripheral devices such as disk drives and printers.

Algorithm
type: Class
subclass of: Restriction
  some values from: Problem
  on property: computes solution to
subclass of: Restriction
  some values from: Algorithmic Type
  on property: is a type of
subclass of: Restriction
  some values from: Information Resource
  on property: appeared In
subclass of: Restriction
  some values from: string
  on property: input
subclass of: Restriction
  some values from: nonNegativeInteger
  on property: number Of Steps
subclass of: Restriction
  some values from: string
  on property: output
subclass of: Restriction
  all values from: string
  on property: title
subclass of: Restriction
  on data range: string
  min qualified cardinality: 1
  on property: title
comment: It is a finite and unambiguous sequence of computer implementable instructions to perform a certain task. This can be a simple process, such as adding two numbers together, or a complex function, such as adding effects to an image. It can be expressed within a finite amount of space and time and in a well-defined formal language.

AlgorithmAnalysisFunction
type: Class
comment: Time complexity corresponds to the amount of time required for an algorithm to run over the provided input in order to generate the required output. Analysis of this helps to predict the resources that an algorithm will take to finish execution.

Algorithmic Type
type: Class
comment: The different type of algorithmic techniques that are used to solve the various existing problems in the most optimized manner. This classification is neither exhaustive nor disjoint.

Combinatorial optimization problem
type: Class
subclass of: Optimization problem

Combinatorial Problem
type: Class
subclass of: Problem
comment: Combinatorial algorithms are computational procedures which are designed to help solve combinatorial problems. Combinatorial problems are problems involving arrangements of elements from a finite set and selections from a finite set.

Computational Geometry Problem
type: Class
subclass of: Problem
comment: Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry.

Data Structure
type: Class
comment: A data structure is a named location that can be used to store and organize data.

Data Structures Problem
type: Class
subclass of: Problem
comment: Solving problems related to data structure i.e a particular way of organizing data in a computer so that it can be used effectively.

Form of expression
type: Class
comment: The available form of expression/ notation of an algorithm. For example, Flowcharts, pseudocode, control tables, etc. (source: https://en.wikipedia.org/wiki/Algorithm)

Graph Problem
type: Class
subclass of: Problem
comment: A Graph is a non-linear data structure consisting of nodes and edges. The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.

Hard Problem
type: Class
subclass of: Graph Problem
comment: Any graph problem, which is NP-hard in general graphs, becomes polynomial-time solvable when restricted to graphs in special classes.

Implementation
type: Class
subclass of: Restriction
  some values from: Algorithm
  on property: implementation of
subclass of: Restriction
  some values from: Programming language
  on property: programming language
subclass of: Restriction
  some values from: Operating system
  on property: runs on Operating System
comment: A manifestation of a technical specification or algorithm as a program, software component, or other computer system through computer programming and deployment (source: https://en.wikipedia.org/wiki/Implementation).

Loop construct
type: Class
comment: The type of loop best suited when an algorithm is implemented in any desired programming language. The loop types are for loop, while loop, do-while loop.

Mathematical property
type: Class
comment: The mathematical concept used in the algorithm to tackle the problem. This includes set theoty, linear algebra, graph theory etc.

Message complexity
type: Class
subclass of: Metric
comment: The number of messages passed. This is an important measure, primarily applicable in case of distributed algorithms.

Metric
type: Class

Numerical Problem
type: Class
subclass of: Problem
comment: Numerical algorithms are behind designing shapes (e.g. shapes for cars, planes, fonts), computing intensities for displaying graphics, animating moving objects, studying the spread of diseases, modelling the orbit of planets and satellites, supporting search engines such as google, and many more practical problems.

Optimization problem
type: Class
subclass of: Problem
comment: An optimization problem is the problem of finding the best solution from all feasible solutions.

Performance metric
type: Class
subclass of: Metric
comment: Performance metrics (e.g., accuracy, precision, recall) are used to evaluate different algorithms.

Polynomial Time Problem
type: Class
subclass of: Graph Problem
comment: Polynomial time problem means that an algorithm exists for its solution such that the number of steps in the algorithm is bounded by a polynomial function of n, where n corresponds to the length of the input for the problem.

Problem
type: Class
comment: The various problems for which an algorithm is written.

Programming language
type: Class
comment: Language designed to communicate instructions to a machine Programming languages are used in computer programming to implement algorithms.

Set Problem
type: Class
subclass of: Problem
comment: Sets are collections of symbols whose order is assumed to carry no significance.

Space complexity
type: Class
subclass of: Metric
comment: Space complexity of an algorithm quantifies the amount of space or memory taken by an algorithm to run as a function of the length of the input.

String problem
type: Class
subclass of: Problem
comment: Strings are defined by the sequence or arrangement of symbols

Time complexity
type: Class
subclass of: Metric
comment: It represents the number of times a statement is executed.
comment: Time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the input. It measures only the executing time of the algorithm in a way that depends only on the algorithm itself and its input.

Academic discipline
type: Class
comment: A branch of knowledge.
comment: Academic field of study or profession.
alt label: Academic field
alt label: Subject area

Information Resource
type: Class
comment: An information resource.

Manual
type: Class
subclass of: Document
comment: A small reference book, especially one giving instructions.

A Formal Basis for the Heuristic Determination of Minimum Cost Paths
type: NamedIndividual
creator: Bertram Raphael
creator: NIls Nilson
creator: Peter Hart
created: 01-01-1968T00:00:00

Algorithm 232 - HeapSort
type: NamedIndividual
creator: J.W.J Williams

Arne Kutzner
type: NamedIndividual

Array
type: NamedIndividual
type: Data Structure

BacktrackingAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: Backtracking algorithms are based on a depth-first recursive search.

Bead Sort
type: NamedIndividual
type: Algorithm
creator: Cristian S. Calude
creator: Joshua J. Arulanandham
creator: Michael Dinneen
computes solution to: Sorting
has implementation: Bead Sort In Python
has space complexity: BeadSortSpaceComplexity
has time complexity: BeadSortTimeComplexity
output image: Bead Sort -R
input image: Bead Sort-L
appeared In: Bead–Sort: A Natural Sorting Algorithm
created: 2002-01-01T00:00:00
description: A natural sorting algorithm.
input: A set of positive integers.

Bead Sort-L
type: NamedIndividual

Bead Sort -R
type: NamedIndividual

Bead Sort In Python
type: NamedIndividual
programming language: Python

BeadSortSpaceComplexity
type: NamedIndividual
worst case time complexity: O(n^2)

BeadSortTimeComplexity
type: NamedIndividual
average time complexity: O(S)
best case time complexity: O(n)
worst case time complexity: O(S)

Bellman-Ford Algorithm
type: NamedIndividual
type: Algorithm
relation: Dijkstra's Algorithm
computes solution to: Shortest path problem
data Structure Used: GraphDataStructure
has space complexity: BellmanFordSpaceComplexity
has time complexity: BellmanFordTimeComplexity
is a type of: DynamicProgrammingAlgorithm
loop construct: For
appeared In: Network Flow Theory.
appeared In: On a Routing Problem
created: 1958
description: The Bellman-Ford algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.
description: The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is capable of handling graphs in which some of the edge weights are negative numbers.
input: Graph and a source vertex src.
input description: Works on negative or positive vertex, in a directed weighted graph.
output: Shortest distance to all vertices from src. If there is a negative weight cycle, then shortest distances are not calculated, negative weight cycle is reported.

BellmanFordSpaceComplexity
type: NamedIndividual
type: Space complexity
best case space complexity: O(N)
worst case space complexity: θ(|V|)

BellmanFordTimeComplexity
type: NamedIndividual
type: Time complexity
best case time complexity: θ(|E|)
worst case time complexity: θ(|V||E|)

Bertram Raphael
type: NamedIndividual

Best bin first
type: NamedIndividual
type: Algorithm
description: Best bin first is a search algorithm that is designed to efficiently find an approximate solution to the nearest neighbor search problem in very-high-dimensional spaces.

Block Sort
type: NamedIndividual
type: Algorithm
creator: Arne Kutzner
creator: Pok Son Kim
computes solution to: Sorting
has space complexity: BlockSortSpaceComplexity
has time complexity: BlockSortTimeComplexity
appeared In: Ratio based stable in-place merging
created: 2008-01-01T00:00:00
description: Efficient sorting algorithm that combines insert and merge operations.

BlockSortSpaceComplexity
type: NamedIndividual
worst case space complexity: O(1)

BlockSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(n)
worst case time complexity: O(nlog n)

BranchAndBoundAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: Branch and bound algorithms are generally used for optimization problems. As the algorithm progresses, a tree of subproblems is formed. The original problem is considered the “root problem”. A method is used to construct an upper and lower bound for a given problem. At each node, apply the bounding methods.

BruteForceAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: A brute force algorithm simply tries all possibilities until a satisfactory solution is found.

Bubble sort
type: NamedIndividual
type: Algorithm
computes solution to: Sorting
data Structure Used: Array
has implementation: Bubble Sort Pseudocode Implementation
has space complexity: BubbleSortSpaceComplexity
has time complexity: BubbleSortTimeComplexity
description: Simple sorting algorithm that works by repeatedly swapping the adjacent elements.

Bubble Sort Pseudocode Implementation
type: NamedIndividual

BubbleSortSpaceComplexity
type: NamedIndividual
worst case space complexity: O(1)

BubbleSortTimeComplexity
type: NamedIndividual
average time complexity: O(n^2)
best case time complexity: O(n)
worst case time complexity: O(n^2)

C. A. R. Hoare
type: NamedIndividual

Code for Dijkstra's algorithm
type: NamedIndividual

Cristian S. Calude
type: NamedIndividual

Data Extraction From Sbr
type: NamedIndividual
type: Algorithm
data Structure Used: Dictionary
data Structure Used: List
form of expression: Pseudocode
has implementation: Data Extraction Implementation
loop construct: For
created: 2022-01-01T00:00:00
description: Extract the data of 75 algorithmic problems from Stony Brooks Algorithm Repository in tabular form.
input: https://algorist.com/algorist.html
number Of Steps: 9
output: https://github.com/jyotimapatel/Algorithmic_Knowledge_Graph/blob/main/Problem(75).csv

Data Extraction Implementation
type: NamedIndividual
programming language: Python

DijkastrasAlgorithmTimeComplexity
type: NamedIndividual
worst case time complexity: O(|E|+|V| log |V|)

Dijkstra's Algorithm
type: NamedIndividual
type: Algorithm
creator: Edsger W. Dijkstra
relation: Bellman-Ford Algorithm
computes solution to: Shortest path problem
form of expression: Pseudocode
has implementation: Code for Dijkstra's algorithm
has time complexity: DijkastrasAlgorithmTimeComplexity
is a type of: GreedyAlgorithm
description: An algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks.
description: Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.
input: a directed and weighted graph consisting of 2 or more nodes.
input description: Works on only positive- weight edges in a directed, acyclic graph. The input generally represented by an adjacency matrix or list, and a start node.
output: a set of edges depicting the shortest path to each destination node.

DivideAndConquerAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: A divide and conquer algorithm consists of two parts: (i) Divide the problem into smaller subproblems of the same type, and solve these subproblems recursively; (ii) Combine the solutions to the subproblems into a solution to the original proble.

DynamicProgrammingAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: A dynamic programming algorithm remembers past results and uses them to find new results. Dynamic programming is generally used for optimization problems, where multiple solutions exist but need to find the “best” one.

Edsger W. Dijkstra
type: NamedIndividual

EncoRNNTimeCom1
type: NamedIndividual
type: Time complexity
best case time complexity: O(N)

EncoderDecoderTimeComplexity
type: NamedIndividual
best case time complexity: O(N)

Encoding Recurrent Neural Network
type: NamedIndividual
creator: Ilya Sutskever
creator: Oriol Vinyals
creator: Quoc V. Le
computes solution to: EncodingSourceLanguage
has time complexity: EncoRNNTimeCom1
appeared In: SequenceToSequenceLearningWithNeuralNetworks
created: 2014-01-01T00:00:00
description: It uses deep neural network layers and converts the input words to corresponding hidden vectors. Each vector represents the current word and the context of the word.
input description: Series of symbols in some language that need to be translated.

Fast multipole method
type: NamedIndividual
type: Algorithm
computes solution to: n-body problem
description: The fast multipole method (FMM) is a numerical technique that was developed to speed up the calculation of long-ranged forces in the n-body problem.

Graph
type: NamedIndividual
definiton: A set of items connected by edges. Each item is called a vertex or node. Formally, a graph is a set of vertices and a binary relation between vertices, adjacency.

Heap Sort
type: NamedIndividual
type: Algorithm
creator: J.W.J Williams
computes solution to: Sorting
data Structure Used: Array
has space complexity: HeapSortSpaceComplexity
has time complexity: HeapSortTimeComplexity
appeared In: Algorithm 232 - HeapSort
description: Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

HeapSortSpaceComplexity
type: NamedIndividual
best case space complexity: O(n)

HeapSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(n)
worst case time complexity: O(nlog n)

Hypergraph
type: NamedIndividual
type: Data Structure
specialization of: Graph
definiton: A graph whose hyperedges connect two or more vertices.
formal definition: A hypergraph G can be defined as a pair (V, E), where V is a set of vertices, and E is a set of hyperedges between the vertices. Each hyperedge is a set of vertices: E ⊆ {{u, v, …} ∈ 2V}. (Hyperedges are undirected.)

Ilya Sutskever
type: NamedIndividual

Insertion Sort
type: NamedIndividual
type: Algorithm
computes solution to: Sorting
data Structure Used: Array
has space complexity: InsertionSortSpaceComplexity
has time complexity: InsertionSortTimeComplexity
description: Sorting algorithm that, at each iteration, inserts the current input element into the suitable position between the already sorted elements.
online algorithm: false

InsertionSortSpaceComplexity
type: NamedIndividual
worst case space complexity: O(1)

InsertionSortTimeComplexity
type: NamedIndividual
average time complexity: O(n^2)
best case time complexity: O(n)
worst case time complexity: O(n^2)

J.W.J Williams
type: NamedIndividual

John Von Neumann
type: NamedIndividual

Joshua J. Arulanandham
type: NamedIndividual

L.R Ford
type: NamedIndividual

Merge Sort
type: NamedIndividual
type: Algorithm
creator: John Von Neumann
computes solution to: Sorting
data Structure Used: Array
has space complexity: MergeSortSpaceComplexity
has time complexity: MergeSortTimeComplexity
is a type of: DivideAndConquerAlgorithm
created: 1945-01-01T00:00:00
description: Merge sort is an efficient, general-purpose, and comparison-based sorting algorithm.

MergeSortSpaceComplexity
type: NamedIndividual
best case space complexity: O(1)
worst case space complexity: O(n)

MergeSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(nlog n)
worst case time complexity: O(nlog n)

Michael Dinneen
type: NamedIndividual

Network Flow Theory.
type: NamedIndividual
type: Academic article
creator: L.R Ford
created: 01-01-1956T00:00:00

NIls Nilson
type: NamedIndividual

On a Routing Problem
type: NamedIndividual
type: Academic article
creator: Richard E. Bellman
published in: Quarterly Applied Mathematics
created: 01-01-1958T00:00:00

Oriol Vinyals
type: NamedIndividual

Peter Hart
type: NamedIndividual

Pok Son Kim
type: NamedIndividual

Quarterly Applied Mathematics
type: NamedIndividual
type: Journal

Quick Sort
type: NamedIndividual
type: Algorithm
creator: C. A. R. Hoare
computes solution to: Sorting
has space complexity: QuickSortSpaceComplexity
has time complexity: QuickSortTimeComplexity
is a type of: DivideAndConquerAlgorithm
appeared In: Algorithm 64: Quicksort
created: 1961-01-01T00:00:00
description: Average-case optimal divide and conquer comparison sorting algorithm.
description: Quicksort is a type of divide and conquer algorithm for sorting an array, based on a partitioning routine.
time of earliest written record: 1959-01-01T00:00:00

QuickSortSpaceComplexity
type: NamedIndividual
average space complexity: O(log n)
worst case space complexity: O(n)

QuickSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(nlog n)
worst case time complexity: O(n^^2)

Quoc V. Le
type: NamedIndividual

RandomizedAlgorithm
type: NamedIndividual
type: Algorithmic Type
comment: A randomized algorithm uses a random number at least once during the computation to make a decision.

Ratio based stable in-place merging
type: NamedIndividual
creator: Arne Kutzner
creator: Pok Son Kim
created: 2008-01-01T00:00:00

Recursive algorithm
type: NamedIndividual
type: Algorithmic Type
comment: A simple recursive algorithm: (i) Solves the base cases directly; (ii) Recurs with a simpler subproblem; (iii) Does some extra work to convert the solution to the simpler subproblem into a solution to the given problem. It is called “simple” because several of the other algorithm types are inherently recursive. (source: https://www.cis.upenn.edu/~matuszek/cit594-2003/Lectures/35-algorithm-types.ppt)
alt label: Simple recursive algorithm

Richard E. Bellman
type: NamedIndividual

Selection Sort
type: NamedIndividual
type: Algorithm
computes solution to: Sorting
data Structure Used: Array
has implementation: Selection Sort Implementation In C
has space complexity: SelectionSortSpaceComplexity
has time complexity: SelectionSortTimeComplexity
description: Sorting Algorithm

Selection Sort Implementation In C
type: NamedIndividual

SelectionSortSpaceComplexity
type: NamedIndividual
worst case space complexity: O(1)

SelectionSortTimeComplexity
type: NamedIndividual
average time complexity: O(n^^2)
best case time complexity: O(n^^2)
worst case time complexity: O(n^^2)

Shortest path problem
type: NamedIndividual
type: Polynomial Time Problem

Smooth Sort
type: NamedIndividual
type: Algorithm
creator: Edsger W. Dijkstra
computes solution to: Sorting
data Structure Used: Array
has space complexity: SmoothSortSpaceComplexity
has time complexity: SmoothSortTimeComplexity
appeared In: Smooth Sort: An Alternative For Sorting In Situ
created: 1981-01-01T00:00:00
description: A comparison-based sorting algorithm.

Smooth Sort: An Alternative For Sorting In Situ
type: NamedIndividual
creator: Edsger W. Dijkstra
created: 1981-01-01T00:00:00

SmoothSortSpaceComplexity
type: NamedIndividual
best case space complexity: O(1)
worst case space complexity: O(n)

SmoothSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(n)

Sorting
type: NamedIndividual
type: Combinatorial Problem

Tim Peters
type: NamedIndividual

Tim Sort
type: NamedIndividual
type: Algorithm
creator: Tim Peters
computes solution to: Sorting
data Structure Used: Array
has implementation: Tim Sort Implemented In Python
has space complexity: TimSortSpaceComplexity
has time complexity: TimSortTimeComplexity
created: 2002-01-01T00:00:00
description: Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

Tim Sort Implemented In Python
type: NamedIndividual
programming language: Python

TimSortSpaceComplexity
type: NamedIndividual
worst case space complexity: O(n)

TimSortTimeComplexity
type: NamedIndividual
average time complexity: O(nlog n)
best case time complexity: O(nlog n)
worst case time complexity: O(n)

n-body problem
type: NamedIndividual
type: Problem
comment: The n-body problem is the problem of predicting the individual motions of a group of celestial objects interacting with each other gravitationally.

A* Algorithm
type: NamedIndividual
type: Algorithm
has Version: Dijkstra's Algorithm
relation: Bellman-Ford Algorithm
computes solution to: Shortest path problem
data Structure Used: GraphDataStructure
has space complexity: A*SpaceComplexity
has time complexity: A*TimeComplexity
appeared In: A Formal Basis for the Heuristic Determination of Minimum Cost Paths
description: A* Algorithm is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.

A*SpaceComplexity
type: NamedIndividual
worst case space complexity: O(|V|)

A*TimeComplexity
type: NamedIndividual
worst case time complexity: O(|E|)

Algorithm 64: Quicksort
type: NamedIndividual
creator: C. A. R. Hoare
created: 1961-01-01T00:00:00

Bead–Sort: A Natural Sorting Algorithm
type: NamedIndividual
creator: Cristian S. Calude
creator: Joshua J. Arulanandham
creator: Michael Dinneen
created: 2002-01-01T00:00:00