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 N5fed706a573741e683307e38e0800419
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 N71e866a84efa4f058d4fc2e347a2dc5b
11 Ne6c520bcce2e4ff085f6637457ebf0e1
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 Na299e426ff75427db8521953ce27d0b9
38 Ne1105e2529dd47119098bc90a75fc69a
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 N9dbebba6b67c43ccb9c073d702674d85
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 N395c3d3000b94deb9dd8b3f5eca4f14c rdf:first sg:person.014126753701.71
49 rdf:rest Ne96bfa2eecbd490799d0675e52aad42d
50 N5fed706a573741e683307e38e0800419 rdf:first sg:person.011757371347.43
51 rdf:rest N395c3d3000b94deb9dd8b3f5eca4f14c
52 N71e866a84efa4f058d4fc2e347a2dc5b schema:volumeNumber 17
53 rdf:type schema:PublicationVolume
54 N9dbebba6b67c43ccb9c073d702674d85 schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 Na299e426ff75427db8521953ce27d0b9 schema:name dimensions_id
57 schema:value pub.1007699916
58 rdf:type schema:PropertyValue
59 Ne1105e2529dd47119098bc90a75fc69a schema:name doi
60 schema:value 10.1007/bf02522825
61 rdf:type schema:PropertyValue
62 Ne6c520bcce2e4ff085f6637457ebf0e1 schema:issueNumber 2
63 rdf:type schema:PublicationIssue
64 Ne96bfa2eecbd490799d0675e52aad42d rdf:first sg:person.013360611545.48
65 rdf:rest rdf:nil
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)


...