Maintaining dynamic sequences under equality tests in polylogarithmic time View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1997-02

AUTHORS

K. Mehlhorn, R. Sundar, C. Uhrig

ABSTRACT

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. More... »

PAGES

183-198

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02522825

DOI

http://dx.doi.org/10.1007/bf02522825

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1007699916


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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

Subject Predicate Object
1 sg:pub.10.1007/bf02522825 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7aea6f9ca0334ed1a791b33fd82cfab6
4 schema:datePublished 1997-02
5 schema:datePublishedReg 1997-02-01
6 schema: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.
7 schema:genre article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N4482f2389f724e2896a70b22885b6f4c
11 N966db64347c849678d5763d42c9e0e30
12 sg:journal.1047644
13 schema:keywords creation
14 data structure
15 deterministic data structure
16 deterministic solution
17 dynamic family
18 dynamic sequence
19 equality test
20 family
21 length
22 new sequences
23 operation
24 pairs
25 polylogarithmic time
26 sequence
27 sequence creation
28 solution
29 splitting
30 structure
31 test
32 time
33 version
34 wheren
35 schema:name Maintaining dynamic sequences under equality tests in polylogarithmic time
36 schema:pagination 183-198
37 schema:productId N466c05a059424d8cb22b330d1b5c59f6
38 Nc464b8077ef245c2b20e51c3ca689996
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007699916
40 https://doi.org/10.1007/bf02522825
41 schema:sdDatePublished 2022-06-01T22:03
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N517b3d9293f14c52b39b7303dd9c8837
44 schema:url https://doi.org/10.1007/bf02522825
45 sgo:license sg:explorer/license/
46 sgo:sdDataset articles
47 rdf:type schema:ScholarlyArticle
48 N3adca67aaf2e421cbcc5221bee0f25b8 rdf:first sg:person.013360611545.48
49 rdf:rest rdf:nil
50 N4482f2389f724e2896a70b22885b6f4c schema:issueNumber 2
51 rdf:type schema:PublicationIssue
52 N466c05a059424d8cb22b330d1b5c59f6 schema:name dimensions_id
53 schema:value pub.1007699916
54 rdf:type schema:PropertyValue
55 N517b3d9293f14c52b39b7303dd9c8837 schema:name Springer Nature - SN SciGraph project
56 rdf:type schema:Organization
57 N5ba42cb4a4a04f12be82ee9375a9a25f rdf:first sg:person.014126753701.71
58 rdf:rest N3adca67aaf2e421cbcc5221bee0f25b8
59 N7aea6f9ca0334ed1a791b33fd82cfab6 rdf:first sg:person.011757371347.43
60 rdf:rest N5ba42cb4a4a04f12be82ee9375a9a25f
61 N966db64347c849678d5763d42c9e0e30 schema:volumeNumber 17
62 rdf:type schema:PublicationVolume
63 Nc464b8077ef245c2b20e51c3ca689996 schema:name doi
64 schema:value 10.1007/bf02522825
65 rdf:type schema:PropertyValue
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
70 schema:name Computation Theory and Mathematics
71 rdf:type schema:DefinedTerm
72 sg:journal.1047644 schema:issn 0178-4617
73 1432-0541
74 schema:name Algorithmica
75 schema:publisher Springer Nature
76 rdf:type schema:Periodical
77 sg:person.011757371347.43 schema:affiliation grid-institutes:grid.419528.3
78 schema:familyName Mehlhorn
79 schema:givenName K.
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011757371347.43
81 rdf:type schema:Person
82 sg:person.013360611545.48 schema:affiliation grid-institutes:grid.419528.3
83 schema:familyName Uhrig
84 schema:givenName C.
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013360611545.48
86 rdf:type schema:Person
87 sg:person.014126753701.71 schema:affiliation grid-institutes:grid.34980.36
88 schema:familyName Sundar
89 schema:givenName R.
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014126753701.71
91 rdf:type schema:Person
92 grid-institutes:grid.34980.36 schema:alternateName Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India
93 schema:name Department of Computer Science and Automation, Indian Institute of Science, 560012, Bangalore, India
94 rdf:type schema:Organization
95 grid-institutes:grid.419528.3 schema:alternateName Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany
96 schema:name Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany
97 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...