Computing location depth and regression depth in higher dimensions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1998-08

AUTHORS

Peter J. Rousseeuw, Anja Struyf

ABSTRACT

The location depth (Tukey 1975) of a point θ relative to a p-dimensional data set Z of size n is defined as the smallest number of data points in a closed halfspace with boundary through θ. For bivariate data, it can be computed in O(nlogn) time (Rousseeuw and Ruts 1996). In this paper we construct an exact algorithm to compute the location depth in three dimensions in O(n2logn) time. We also give an approximate algorithm to compute the location depth in p dimensions in O(mp3+mpn) time, where m is the number of p-subsets used. Recently, Rousseeuw and Hubert (1996) defined the depth of a regression fit. The depth of a hyperplane with coefficients (θ1,...,θp) is the smallest number of residuals that need to change sign to make (θ1,...,θp) a nonfit. For bivariate data (p=2) this depth can be computed in O(nlogn) time as well. We construct an algorithm to compute the regression depth of a plane relative to a three-dimensional data set in O(n2logn) time, and another that deals with p=4 in O(n3logn) time. For data sets with large n and/or p we propose an approximate algorithm that computes the depth of a regression fit in O(mp3+mpn+mnlogn) time. For all of these algorithms, actual implementations are made available. More... »

PAGES

193-203

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1008945009397

DOI

http://dx.doi.org/10.1023/a:1008945009397

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "Department of Mathematics and Computer Science, U.I.A., Universiteitsplein 1, B-2610, Antwerp, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rousseeuw", 
        "givenName": "Peter J.", 
        "id": "sg:person.0775337371.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0775337371.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Mathematics and Computer Science, U.I.A., Universiteitsplein 1, B-2610, Antwerp, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Struyf", 
        "givenName": "Anja", 
        "id": "sg:person.01057276224.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01057276224.31"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1006/jmva.1994.1002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033615659"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-9473(96)00027-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034778667"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/1467-9868.00088", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040836499"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/02331888808802095", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041204323"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/01621459.1995.10476643", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058304926"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/01621459.1999.10474129", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1058305578"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1214/aos/1176348890", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064408724"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2290720", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069863837"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2291471", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1069864152"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2986073", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101983592"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.2307/2986073", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1101983592"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1998-08", 
    "datePublishedReg": "1998-08-01", 
    "description": "The location depth (Tukey 1975) of a point \u03b8 relative to a p-dimensional data set Z of size n is defined as the smallest number of data points in a closed halfspace with boundary through \u03b8. For bivariate data, it can be computed in O(nlogn) time (Rousseeuw and Ruts 1996). In this paper we construct an exact algorithm to compute the location depth in three dimensions in O(n2logn) time. We also give an approximate algorithm to compute the location depth in p dimensions in O(mp3+mpn) time, where m is the number of p-subsets used. Recently, Rousseeuw and Hubert (1996) defined the depth of a regression fit. The depth of a hyperplane with coefficients (\u03b81,...,\u03b8p) is the smallest number of residuals that need to change sign to make (\u03b81,...,\u03b8p) a nonfit. For bivariate data (p=2) this depth can be computed in O(nlogn) time as well. We construct an algorithm to compute the regression depth of a plane relative to a three-dimensional data set in O(n2logn) time, and another that deals with p=4 in O(n3logn) time. For data sets with large n and/or p we propose an approximate algorithm that computes the depth of a regression fit in O(mp3+mpn+mnlogn) time. For all of these algorithms, actual implementations are made available.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1008945009397", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1327447", 
        "issn": [
          "0960-3174", 
          "1573-1375"
        ], 
        "name": "Statistics and Computing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "8"
      }
    ], 
    "name": "Computing location depth and regression depth in higher dimensions", 
    "pagination": "193-203", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "76798a853d5fa4b3d9612da441dc51c14fb7572595214100ce1a3dcd16f0b2ac"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1008945009397"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1024868624"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1008945009397", 
      "https://app.dimensions.ai/details/publication/pub.1024868624"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T21:31", 
    "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/0000000001_0000000264/records_8687_00000488.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023/A:1008945009397"
  }
]
 

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.1023/a:1008945009397'

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.1023/a:1008945009397'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008945009397'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008945009397'


 

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

99 TRIPLES      21 PREDICATES      37 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1008945009397 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author Na593af747a1445adbadd91e577b10ace
4 schema:citation https://doi.org/10.1006/jmva.1994.1002
5 https://doi.org/10.1016/s0167-9473(96)00027-8
6 https://doi.org/10.1080/01621459.1995.10476643
7 https://doi.org/10.1080/01621459.1999.10474129
8 https://doi.org/10.1080/02331888808802095
9 https://doi.org/10.1111/1467-9868.00088
10 https://doi.org/10.1214/aos/1176348890
11 https://doi.org/10.2307/2290720
12 https://doi.org/10.2307/2291471
13 https://doi.org/10.2307/2986073
14 schema:datePublished 1998-08
15 schema:datePublishedReg 1998-08-01
16 schema:description The location depth (Tukey 1975) of a point θ relative to a p-dimensional data set Z of size n is defined as the smallest number of data points in a closed halfspace with boundary through θ. For bivariate data, it can be computed in O(nlogn) time (Rousseeuw and Ruts 1996). In this paper we construct an exact algorithm to compute the location depth in three dimensions in O(n2logn) time. We also give an approximate algorithm to compute the location depth in p dimensions in O(mp3+mpn) time, where m is the number of p-subsets used. Recently, Rousseeuw and Hubert (1996) defined the depth of a regression fit. The depth of a hyperplane with coefficients (θ1,...,θp) is the smallest number of residuals that need to change sign to make (θ1,...,θp) a nonfit. For bivariate data (p=2) this depth can be computed in O(nlogn) time as well. We construct an algorithm to compute the regression depth of a plane relative to a three-dimensional data set in O(n2logn) time, and another that deals with p=4 in O(n3logn) time. For data sets with large n and/or p we propose an approximate algorithm that computes the depth of a regression fit in O(mp3+mpn+mnlogn) time. For all of these algorithms, actual implementations are made available.
17 schema:genre research_article
18 schema:inLanguage en
19 schema:isAccessibleForFree false
20 schema:isPartOf N1d36908e58ae42249d61ea9c60dce4cd
21 N9a95efcd851a48aeb0a1be58ba0eb423
22 sg:journal.1327447
23 schema:name Computing location depth and regression depth in higher dimensions
24 schema:pagination 193-203
25 schema:productId N3e7ced32b99d4581916d108fa8617e91
26 N557c29c513304c3b937ee73115db0c0a
27 Nd0cd1c247b8a4b4b8fc82cc7d50d35df
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024868624
29 https://doi.org/10.1023/a:1008945009397
30 schema:sdDatePublished 2019-04-10T21:31
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N2bf420a2ece84fe58277971757d1061b
33 schema:url http://link.springer.com/10.1023/A:1008945009397
34 sgo:license sg:explorer/license/
35 sgo:sdDataset articles
36 rdf:type schema:ScholarlyArticle
37 N1540bb5915f6469284741c53e705bc92 rdf:first sg:person.01057276224.31
38 rdf:rest rdf:nil
39 N1a271ce6f80741fba9de2b973d5581c4 schema:name Department of Mathematics and Computer Science, U.I.A., Universiteitsplein 1, B-2610, Antwerp, Belgium
40 rdf:type schema:Organization
41 N1d36908e58ae42249d61ea9c60dce4cd schema:volumeNumber 8
42 rdf:type schema:PublicationVolume
43 N2bf420a2ece84fe58277971757d1061b schema:name Springer Nature - SN SciGraph project
44 rdf:type schema:Organization
45 N3e7ced32b99d4581916d108fa8617e91 schema:name readcube_id
46 schema:value 76798a853d5fa4b3d9612da441dc51c14fb7572595214100ce1a3dcd16f0b2ac
47 rdf:type schema:PropertyValue
48 N3fff3c1d423c4aa1ae75a3e5828981bd schema:name Department of Mathematics and Computer Science, U.I.A., Universiteitsplein 1, B-2610, Antwerp, Belgium
49 rdf:type schema:Organization
50 N557c29c513304c3b937ee73115db0c0a schema:name dimensions_id
51 schema:value pub.1024868624
52 rdf:type schema:PropertyValue
53 N9a95efcd851a48aeb0a1be58ba0eb423 schema:issueNumber 3
54 rdf:type schema:PublicationIssue
55 Na593af747a1445adbadd91e577b10ace rdf:first sg:person.0775337371.63
56 rdf:rest N1540bb5915f6469284741c53e705bc92
57 Nd0cd1c247b8a4b4b8fc82cc7d50d35df schema:name doi
58 schema:value 10.1023/a:1008945009397
59 rdf:type schema:PropertyValue
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
64 schema:name Artificial Intelligence and Image Processing
65 rdf:type schema:DefinedTerm
66 sg:journal.1327447 schema:issn 0960-3174
67 1573-1375
68 schema:name Statistics and Computing
69 rdf:type schema:Periodical
70 sg:person.01057276224.31 schema:affiliation N3fff3c1d423c4aa1ae75a3e5828981bd
71 schema:familyName Struyf
72 schema:givenName Anja
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01057276224.31
74 rdf:type schema:Person
75 sg:person.0775337371.63 schema:affiliation N1a271ce6f80741fba9de2b973d5581c4
76 schema:familyName Rousseeuw
77 schema:givenName Peter J.
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0775337371.63
79 rdf:type schema:Person
80 https://doi.org/10.1006/jmva.1994.1002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033615659
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1016/s0167-9473(96)00027-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034778667
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1080/01621459.1995.10476643 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058304926
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1080/01621459.1999.10474129 schema:sameAs https://app.dimensions.ai/details/publication/pub.1058305578
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1080/02331888808802095 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041204323
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1111/1467-9868.00088 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040836499
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1214/aos/1176348890 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064408724
93 rdf:type schema:CreativeWork
94 https://doi.org/10.2307/2290720 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069863837
95 rdf:type schema:CreativeWork
96 https://doi.org/10.2307/2291471 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069864152
97 rdf:type schema:CreativeWork
98 https://doi.org/10.2307/2986073 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101983592
99 rdf:type schema:CreativeWork
 




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


...