Cleaning timestamps with temporal constraints View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2021-02-23

AUTHORS

Shaoxu Song, Ruihong Huang, Yue Cao, Jianmin Wang

ABSTRACT

Timestamps are often found to be dirty in various scenarios, e.g., in distributed systems with clock synchronization problems or unreliable RFID readers. Without cleaning the imprecise timestamps, temporal-related applications such as provenance analysis or pattern queries are not reliable. To evaluate the correctness of timestamps, temporal constraints could be employed, which declare the distance restrictions between timestamps. Guided by such constraints on timestamps, in this paper, we study a novel problem of repairing inconsistent timestamps that do not conform to the required temporal constraints. Following the same line of data repairing, the timestamp repairing problem is to minimally modify the timestamps towards satisfaction of temporal constraints. This problem is practically challenging, given the huge space of possible timestamps. We tackle the problem by identifying a concise set of promising candidates, where an optimal repair solution can always be found. Repair algorithms with efficient pruning are then devised over the identified candidates. Approximate solutions are also presented including simple heuristic and linear programming (LP) relaxation. Experiments on real datasets demonstrate the superiority of our proposal compared to the state-of-the-art approaches. More... »

PAGES

425-446

References to SciGraph publications

  • 2013. Improving Documentation by Repairing Event Logs in THE PRACTICE OF ENTERPRISE MODELING
  • 2018-12-07. Constraint-Driven Database Repair in ENCYCLOPEDIA OF DATABASE SYSTEMS
  • 2018-03-15. Bus-OLAP: A Data Management Model for Non-on-Time Events Query Over Bus Journey Data in DATA SCIENCE AND ENGINEERING
  • 2005. On the Computational Complexity of Minimal-Change Integrity Maintenance in Relational Databases in INCONSISTENCY TOLERANCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00778-020-00641-6

    DOI

    http://dx.doi.org/10.1007/s00778-020-00641-6

    DIMENSIONS

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


    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"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Tsinghua University, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Song", 
            "givenName": "Shaoxu", 
            "id": "sg:person.012451307613.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012451307613.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Huang", 
            "givenName": "Ruihong", 
            "id": "sg:person.012132305225.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012132305225.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cao", 
            "givenName": "Yue", 
            "id": "sg:person.012712534041.97", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012712534041.97"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Tsinghua University, Beijing, China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Tsinghua University, Beijing, China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "Jianmin", 
            "id": "sg:person.012303351315.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012303351315.43"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4614-8265-9_599", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1110419482", 
              "https://doi.org/10.1007/978-1-4614-8265-9_599"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-41641-5_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043765167", 
              "https://doi.org/10.1007/978-3-642-41641-5_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30597-2_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017425845", 
              "https://doi.org/10.1007/978-3-540-30597-2_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s41019-018-0061-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1101542182", 
              "https://doi.org/10.1007/s41019-018-0061-9"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2021-02-23", 
        "datePublishedReg": "2021-02-23", 
        "description": "Timestamps are often found to be dirty in various scenarios, e.g., in distributed systems with clock synchronization problems or unreliable RFID readers. Without cleaning the imprecise timestamps, temporal-related applications such as provenance analysis or pattern queries are not reliable. To evaluate the correctness of timestamps, temporal constraints could be employed, which declare the distance restrictions between timestamps. Guided by such constraints on timestamps, in this paper, we study a novel problem of repairing inconsistent timestamps that do not conform to the required temporal constraints. Following the same line of data repairing, the timestamp repairing problem is to minimally modify the timestamps towards satisfaction of temporal constraints. This problem is practically challenging, given the huge space of possible timestamps. We tackle the problem by identifying a concise set of promising candidates, where an optimal repair solution can always be found. Repair algorithms with efficient pruning are then devised over the identified candidates. Approximate solutions are also presented including simple heuristic and linear programming (LP) relaxation. Experiments on real datasets demonstrate the superiority of our proposal compared to the state-of-the-art approaches.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00778-020-00641-6", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.8325325", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.8302034", 
            "type": "MonetaryGrant"
          }, 
          {
            "id": "sg:grant.7003954", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1044889", 
            "issn": [
              "1066-8888", 
              "0949-877X"
            ], 
            "name": "The VLDB Journal", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "30"
          }
        ], 
        "keywords": [
          "temporal constraints", 
          "optimal repair solution", 
          "clock synchronization problem", 
          "imprecise timestamps", 
          "pattern queries", 
          "data repairing", 
          "efficient pruning", 
          "art approaches", 
          "linear programming relaxation", 
          "real datasets", 
          "timestamps", 
          "RFID reader", 
          "repair algorithm", 
          "huge space", 
          "novel problem", 
          "distance restrictions", 
          "concise set", 
          "programming relaxation", 
          "synchronization problem", 
          "such constraints", 
          "constraints", 
          "queries", 
          "algorithm", 
          "correctness", 
          "dataset", 
          "pruning", 
          "repair solution", 
          "scenarios", 
          "approximate solution", 
          "solution", 
          "set", 
          "superiority", 
          "proposal", 
          "applications", 
          "system", 
          "space", 
          "repairing", 
          "same line", 
          "experiments", 
          "provenance analysis", 
          "readers", 
          "satisfaction", 
          "candidates", 
          "state", 
          "restriction", 
          "analysis", 
          "lines", 
          "promising candidate", 
          "relaxation", 
          "problem", 
          "paper", 
          "approach", 
          "unreliable RFID readers", 
          "temporal-related applications", 
          "correctness of timestamps", 
          "inconsistent timestamps", 
          "possible timestamps"
        ], 
        "name": "Cleaning timestamps with temporal constraints", 
        "pagination": "425-446", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1135647453"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00778-020-00641-6"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00778-020-00641-6", 
          "https://app.dimensions.ai/details/publication/pub.1135647453"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T19:00", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_915.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00778-020-00641-6"
      }
    ]
     

    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/s00778-020-00641-6'

    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/s00778-020-00641-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00778-020-00641-6'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00778-020-00641-6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    162 TRIPLES      22 PREDICATES      87 URIs      74 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00778-020-00641-6 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0806
    4 schema:author Ne4636cbdb3c544f5ab4a1aa2167f0d6b
    5 schema:citation sg:pub.10.1007/978-1-4614-8265-9_599
    6 sg:pub.10.1007/978-3-540-30597-2_5
    7 sg:pub.10.1007/978-3-642-41641-5_10
    8 sg:pub.10.1007/s41019-018-0061-9
    9 schema:datePublished 2021-02-23
    10 schema:datePublishedReg 2021-02-23
    11 schema:description Timestamps are often found to be dirty in various scenarios, e.g., in distributed systems with clock synchronization problems or unreliable RFID readers. Without cleaning the imprecise timestamps, temporal-related applications such as provenance analysis or pattern queries are not reliable. To evaluate the correctness of timestamps, temporal constraints could be employed, which declare the distance restrictions between timestamps. Guided by such constraints on timestamps, in this paper, we study a novel problem of repairing inconsistent timestamps that do not conform to the required temporal constraints. Following the same line of data repairing, the timestamp repairing problem is to minimally modify the timestamps towards satisfaction of temporal constraints. This problem is practically challenging, given the huge space of possible timestamps. We tackle the problem by identifying a concise set of promising candidates, where an optimal repair solution can always be found. Repair algorithms with efficient pruning are then devised over the identified candidates. Approximate solutions are also presented including simple heuristic and linear programming (LP) relaxation. Experiments on real datasets demonstrate the superiority of our proposal compared to the state-of-the-art approaches.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N09612e197b8f4169a975cd7a7186d4c0
    16 Nc4620e6a44df481ab27144f8531738b4
    17 sg:journal.1044889
    18 schema:keywords RFID reader
    19 algorithm
    20 analysis
    21 applications
    22 approach
    23 approximate solution
    24 art approaches
    25 candidates
    26 clock synchronization problem
    27 concise set
    28 constraints
    29 correctness
    30 correctness of timestamps
    31 data repairing
    32 dataset
    33 distance restrictions
    34 efficient pruning
    35 experiments
    36 huge space
    37 imprecise timestamps
    38 inconsistent timestamps
    39 linear programming relaxation
    40 lines
    41 novel problem
    42 optimal repair solution
    43 paper
    44 pattern queries
    45 possible timestamps
    46 problem
    47 programming relaxation
    48 promising candidate
    49 proposal
    50 provenance analysis
    51 pruning
    52 queries
    53 readers
    54 real datasets
    55 relaxation
    56 repair algorithm
    57 repair solution
    58 repairing
    59 restriction
    60 same line
    61 satisfaction
    62 scenarios
    63 set
    64 solution
    65 space
    66 state
    67 such constraints
    68 superiority
    69 synchronization problem
    70 system
    71 temporal constraints
    72 temporal-related applications
    73 timestamps
    74 unreliable RFID readers
    75 schema:name Cleaning timestamps with temporal constraints
    76 schema:pagination 425-446
    77 schema:productId N2d48336bc22a4c0f9bfa9633999b4c82
    78 Nc0888a43740e4881b30344144b96a22b
    79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1135647453
    80 https://doi.org/10.1007/s00778-020-00641-6
    81 schema:sdDatePublished 2022-01-01T19:00
    82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    83 schema:sdPublisher N9555319865bf4e5cb2edd0a141552f3d
    84 schema:url https://doi.org/10.1007/s00778-020-00641-6
    85 sgo:license sg:explorer/license/
    86 sgo:sdDataset articles
    87 rdf:type schema:ScholarlyArticle
    88 N004b945fd32e4a7f89eb0c7b4b530ee7 rdf:first sg:person.012303351315.43
    89 rdf:rest rdf:nil
    90 N09612e197b8f4169a975cd7a7186d4c0 schema:volumeNumber 30
    91 rdf:type schema:PublicationVolume
    92 N2d48336bc22a4c0f9bfa9633999b4c82 schema:name dimensions_id
    93 schema:value pub.1135647453
    94 rdf:type schema:PropertyValue
    95 N7b7d31ba15f4489ca258c0150c474892 rdf:first sg:person.012132305225.22
    96 rdf:rest Nfa442c71aa514b3f8bade7c6dc18cdc4
    97 N9555319865bf4e5cb2edd0a141552f3d schema:name Springer Nature - SN SciGraph project
    98 rdf:type schema:Organization
    99 Nc0888a43740e4881b30344144b96a22b schema:name doi
    100 schema:value 10.1007/s00778-020-00641-6
    101 rdf:type schema:PropertyValue
    102 Nc4620e6a44df481ab27144f8531738b4 schema:issueNumber 3
    103 rdf:type schema:PublicationIssue
    104 Ne4636cbdb3c544f5ab4a1aa2167f0d6b rdf:first sg:person.012451307613.22
    105 rdf:rest N7b7d31ba15f4489ca258c0150c474892
    106 Nfa442c71aa514b3f8bade7c6dc18cdc4 rdf:first sg:person.012712534041.97
    107 rdf:rest N004b945fd32e4a7f89eb0c7b4b530ee7
    108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    109 schema:name Information and Computing Sciences
    110 rdf:type schema:DefinedTerm
    111 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    112 schema:name Computation Theory and Mathematics
    113 rdf:type schema:DefinedTerm
    114 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    115 schema:name Information Systems
    116 rdf:type schema:DefinedTerm
    117 sg:grant.7003954 http://pending.schema.org/fundedItem sg:pub.10.1007/s00778-020-00641-6
    118 rdf:type schema:MonetaryGrant
    119 sg:grant.8302034 http://pending.schema.org/fundedItem sg:pub.10.1007/s00778-020-00641-6
    120 rdf:type schema:MonetaryGrant
    121 sg:grant.8325325 http://pending.schema.org/fundedItem sg:pub.10.1007/s00778-020-00641-6
    122 rdf:type schema:MonetaryGrant
    123 sg:journal.1044889 schema:issn 0949-877X
    124 1066-8888
    125 schema:name The VLDB Journal
    126 schema:publisher Springer Nature
    127 rdf:type schema:Periodical
    128 sg:person.012132305225.22 schema:affiliation grid-institutes:grid.12527.33
    129 schema:familyName Huang
    130 schema:givenName Ruihong
    131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012132305225.22
    132 rdf:type schema:Person
    133 sg:person.012303351315.43 schema:affiliation grid-institutes:grid.12527.33
    134 schema:familyName Wang
    135 schema:givenName Jianmin
    136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012303351315.43
    137 rdf:type schema:Person
    138 sg:person.012451307613.22 schema:affiliation grid-institutes:grid.12527.33
    139 schema:familyName Song
    140 schema:givenName Shaoxu
    141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012451307613.22
    142 rdf:type schema:Person
    143 sg:person.012712534041.97 schema:affiliation grid-institutes:grid.12527.33
    144 schema:familyName Cao
    145 schema:givenName Yue
    146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012712534041.97
    147 rdf:type schema:Person
    148 sg:pub.10.1007/978-1-4614-8265-9_599 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110419482
    149 https://doi.org/10.1007/978-1-4614-8265-9_599
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-540-30597-2_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017425845
    152 https://doi.org/10.1007/978-3-540-30597-2_5
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/978-3-642-41641-5_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043765167
    155 https://doi.org/10.1007/978-3-642-41641-5_10
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/s41019-018-0061-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101542182
    158 https://doi.org/10.1007/s41019-018-0061-9
    159 rdf:type schema:CreativeWork
    160 grid-institutes:grid.12527.33 schema:alternateName Tsinghua University, Beijing, China
    161 schema:name Tsinghua University, Beijing, China
    162 rdf:type schema:Organization
     




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


    ...