Ontology type: schema:ScholarlyArticle Open Access: True
1997-02
AUTHORSK. Mehlhorn, R. Sundar, C. Uhrig
ABSTRACTWe present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests inO(1) time. The randomized version supports new sequence creations inO(log2n) expected time wheren is the length of the sequence created. The deterministic solution supports sequence creations inO(logn(logmlog*m+logn)) time for themth operation. More... »
PAGES183-198
http://scigraph.springernature.com/pub.10.1007/bf02522825
DOIhttp://dx.doi.org/10.1007/bf02522825
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1007699916
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, D-66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, D-66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Mehlhorn",
"givenName": "K.",
"id": "sg:person.011757371347.43",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India",
"id": "http://www.grid.ac/institutes/grid.34980.36",
"name": [
"Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India"
],
"type": "Organization"
},
"familyName": "Sundar",
"givenName": "R.",
"id": "sg:person.014126753701.71",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014126753701.71"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, D-66123, Saarbr\u00fccken, Germany",
"id": "http://www.grid.ac/institutes/grid.419528.3",
"name": [
"Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, D-66123, Saarbr\u00fccken, Germany"
],
"type": "Organization"
},
"familyName": "Uhrig",
"givenName": "C.",
"id": "sg:person.013360611545.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013360611545.48"
],
"type": "Person"
}
],
"datePublished": "1997-02",
"datePublishedReg": "1997-02-01",
"description": "We present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests inO(1) time. The randomized version supports new sequence creations inO(log2n) expected time wheren is the length of the sequence created. The deterministic solution supports sequence creations inO(logn(logmlog*m+logn)) time for themth operation.",
"genre": "article",
"id": "sg:pub.10.1007/bf02522825",
"inLanguage": "en",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "2",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "17"
}
],
"keywords": [
"data structure",
"equality test",
"deterministic data structure",
"sequence creation",
"polylogarithmic time",
"dynamic sequence",
"creation",
"deterministic solution",
"new sequences",
"sequence",
"time",
"version",
"wheren",
"solution",
"operation",
"structure",
"pairs",
"dynamic family",
"test",
"splitting",
"length",
"family"
],
"name": "Maintaining dynamic sequences under equality tests in polylogarithmic time",
"pagination": "183-198",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1007699916"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf02522825"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf02522825",
"https://app.dimensions.ai/details/publication/pub.1007699916"
],
"sdDataset": "articles",
"sdDatePublished": "2022-06-01T22:03",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_290.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/bf02522825"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02522825'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02522825'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02522825'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02522825'
This table displays all metadata directly associated to this object as RDF triples.
97 TRIPLES
21 PREDICATES
48 URIs
40 LITERALS
6 BLANK NODES