A Faster Algorithm for Truth Discovery via Range Cover View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2019-03-25

AUTHORS

Ziyun Huang, Hu Ding, Jinhui Xu

ABSTRACT

Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a (1+ϵ)-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking down them into a small number of parametrized cases. More... »

PAGES

1-16

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-019-00562-z

DOI

http://dx.doi.org/10.1007/s00453-019-00562-z

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Penn State Behrend", 
          "id": "https://www.grid.ac/institutes/grid.447418.a", 
          "name": [
            "Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College, Erie, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Huang", 
        "givenName": "Ziyun", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Science and Technology of China", 
          "id": "https://www.grid.ac/institutes/grid.59053.3a", 
          "name": [
            "School of Computer Science and Technology, University of Science and Technology of China, Hefei, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ding", 
        "givenName": "Hu", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University at Buffalo, State University of New York", 
          "id": "https://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Jinhui", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/1281192.1281309", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001415013"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2566486.2568033", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005964066"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2897350.2897352", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011559054"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2588555.2610509", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027118395"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/070699007", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062851449"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.14778/1687627.1687690", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1067367588"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.14778/2735496.2735505", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1067368630"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019-03-25", 
    "datePublishedReg": "2019-03-25", 
    "description": "Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a (1+\u03f5)-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking down them into a small number of parametrized cases.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00453-019-00562-z", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isFundedItemOf": [
      {
        "id": "sg:grant.3582796", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.6624425", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.3659070", 
        "type": "MonetaryGrant"
      }, 
      {
        "id": "sg:grant.4314562", 
        "type": "MonetaryGrant"
      }
    ], 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }
    ], 
    "name": "A Faster Algorithm for Truth Discovery via Range Cover", 
    "pagination": "1-16", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "862d195e3356e79dd4e7fd5e5b59498c7c9c02876f92e9d244de505c9bc7dae2"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-019-00562-z"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1112987262"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-019-00562-z", 
      "https://app.dimensions.ai/details/publication/pub.1112987262"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000366_0000000366/records_112069_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00453-019-00562-z"
  }
]
 

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/s00453-019-00562-z'

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/s00453-019-00562-z'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00562-z'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-019-00562-z'


 

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

101 TRIPLES      21 PREDICATES      31 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-019-00562-z schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N997a8fd72b4144d98fb603b7377ac96e
4 schema:citation https://doi.org/10.1137/070699007
5 https://doi.org/10.1145/1281192.1281309
6 https://doi.org/10.1145/2566486.2568033
7 https://doi.org/10.1145/2588555.2610509
8 https://doi.org/10.1145/2897350.2897352
9 https://doi.org/10.14778/1687627.1687690
10 https://doi.org/10.14778/2735496.2735505
11 schema:datePublished 2019-03-25
12 schema:datePublishedReg 2019-03-25
13 schema:description Truth discovery is a key problem in data analytics which has received a great deal of attention in recent years. In this problem, we seek to obtain trustworthy information from data aggregated from multiple (possibly) unreliable sources. Most of the existing approaches for this problem are of heuristic nature and do not provide any quality guarantee. Very recently, the first quality-guaranteed algorithm has been discovered. However, the running time of the algorithm depends on the spread ratio of the input points and is fully polynomial only when the spread ratio is relatively small. This could restrict the applicability of the algorithm. To resolve this issue, we propose in this paper a new algorithm which yields a (1+ϵ)-approximation in near quadratic time for any dataset with constant probability. Our algorithm relies on a data structure called range cover, which is interesting in its own right. The data structure provides a general approach for solving some high dimensional optimization problems by breaking down them into a small number of parametrized cases.
14 schema:genre research_article
15 schema:inLanguage en
16 schema:isAccessibleForFree false
17 schema:isPartOf sg:journal.1047644
18 schema:name A Faster Algorithm for Truth Discovery via Range Cover
19 schema:pagination 1-16
20 schema:productId N2e3f12cc37134d4ea47d5d62f8ab9e6c
21 Na00b267c068849f2aebb6eaa144b7a45
22 Nebe1f94f5dc04c368fccace64fba88a3
23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1112987262
24 https://doi.org/10.1007/s00453-019-00562-z
25 schema:sdDatePublished 2019-04-11T13:05
26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
27 schema:sdPublisher N318fcda7ec9546d3869375154fd31da6
28 schema:url https://link.springer.com/10.1007%2Fs00453-019-00562-z
29 sgo:license sg:explorer/license/
30 sgo:sdDataset articles
31 rdf:type schema:ScholarlyArticle
32 N2c4b60408ea9454983d437c1aa2da3b4 schema:affiliation https://www.grid.ac/institutes/grid.447418.a
33 schema:familyName Huang
34 schema:givenName Ziyun
35 rdf:type schema:Person
36 N2e3f12cc37134d4ea47d5d62f8ab9e6c schema:name doi
37 schema:value 10.1007/s00453-019-00562-z
38 rdf:type schema:PropertyValue
39 N318fcda7ec9546d3869375154fd31da6 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N50cc831af93241309f6e1ead91ced426 rdf:first N70c778881f7a4da9961e644db1a0e19f
42 rdf:rest rdf:nil
43 N70c778881f7a4da9961e644db1a0e19f schema:affiliation https://www.grid.ac/institutes/grid.273335.3
44 schema:familyName Xu
45 schema:givenName Jinhui
46 rdf:type schema:Person
47 N876140b0ef0447ca96808210dc774830 schema:affiliation https://www.grid.ac/institutes/grid.59053.3a
48 schema:familyName Ding
49 schema:givenName Hu
50 rdf:type schema:Person
51 N997a8fd72b4144d98fb603b7377ac96e rdf:first N2c4b60408ea9454983d437c1aa2da3b4
52 rdf:rest Nff641206a08247a09c6c339b23dfb729
53 Na00b267c068849f2aebb6eaa144b7a45 schema:name dimensions_id
54 schema:value pub.1112987262
55 rdf:type schema:PropertyValue
56 Nebe1f94f5dc04c368fccace64fba88a3 schema:name readcube_id
57 schema:value 862d195e3356e79dd4e7fd5e5b59498c7c9c02876f92e9d244de505c9bc7dae2
58 rdf:type schema:PropertyValue
59 Nff641206a08247a09c6c339b23dfb729 rdf:first N876140b0ef0447ca96808210dc774830
60 rdf:rest N50cc831af93241309f6e1ead91ced426
61 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
62 schema:name Mathematical Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
65 schema:name Numerical and Computational Mathematics
66 rdf:type schema:DefinedTerm
67 sg:grant.3582796 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-019-00562-z
68 rdf:type schema:MonetaryGrant
69 sg:grant.3659070 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-019-00562-z
70 rdf:type schema:MonetaryGrant
71 sg:grant.4314562 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-019-00562-z
72 rdf:type schema:MonetaryGrant
73 sg:grant.6624425 http://pending.schema.org/fundedItem sg:pub.10.1007/s00453-019-00562-z
74 rdf:type schema:MonetaryGrant
75 sg:journal.1047644 schema:issn 0178-4617
76 1432-0541
77 schema:name Algorithmica
78 rdf:type schema:Periodical
79 https://doi.org/10.1137/070699007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062851449
80 rdf:type schema:CreativeWork
81 https://doi.org/10.1145/1281192.1281309 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001415013
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1145/2566486.2568033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005964066
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1145/2588555.2610509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027118395
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1145/2897350.2897352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011559054
88 rdf:type schema:CreativeWork
89 https://doi.org/10.14778/1687627.1687690 schema:sameAs https://app.dimensions.ai/details/publication/pub.1067367588
90 rdf:type schema:CreativeWork
91 https://doi.org/10.14778/2735496.2735505 schema:sameAs https://app.dimensions.ai/details/publication/pub.1067368630
92 rdf:type schema:CreativeWork
93 https://www.grid.ac/institutes/grid.273335.3 schema:alternateName University at Buffalo, State University of New York
94 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, Buffalo, USA
95 rdf:type schema:Organization
96 https://www.grid.ac/institutes/grid.447418.a schema:alternateName Penn State Behrend
97 schema:name Department of Computer Science and Software Engineering, Penn State Erie, The Behrend College, Erie, USA
98 rdf:type schema:Organization
99 https://www.grid.ac/institutes/grid.59053.3a schema:alternateName University of Science and Technology of China
100 schema:name School of Computer Science and Technology, University of Science and Technology of China, Hefei, China
101 rdf:type schema:Organization
 




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


...