Wavelet-Based Cost Estimation for Spatial Queries View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Min Wang , Jeffrey Scott Vitter , Lipyeow Lim , Sriram Padmanabhan

ABSTRACT

Query cost estimation is an important and well-studied problem in relational database systems. In this paper we study the cost estimation problem in the context of spatial database systems. We introduce a new method that provides accurate cost estimation for spatial selections, or window queries, by building wavelet-based histograms for spatial data. Our method is based upon two techniques: (a) A representation transformation in which geometric objects are represented by points in higher-dimensional space and window queries correspond to semi-infinite range-sum queries, and (b) Multiresolution wavelet decomposition that provides a time-efficient and space-efficient approximation of the underlying distribution of the multidimensional point data, especially for semi-infinite range-sum queries. We also show for the first time how a wavelet decomposition of a dense multidimensional array derived from a sparse array through a partial-sum computation can still be computed efficiently using sparse techniques by doing the processing implicitly on the original data. Our method eliminates the drawbacks of the partition-based histogram methods in previous work, and even with very small space allocation it gives excellent cost estimation over a broad range of spatial data distributions and queries. More... »

PAGES

175-193

References to SciGraph publications

Book

TITLE

Advances in Spatial and Temporal Databases

ISBN

978-3-540-42301-0
978-3-540-47724-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-47724-1_10

DOI

http://dx.doi.org/10.1007/3-540-47724-1_10

DIMENSIONS

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


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/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "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": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T J. Watson Research Center, Hawthorne, NY, 10532"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Min", 
        "id": "sg:person.012657435165.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012657435165.75"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Dept. of Computer Science, Duke University, Durham, NC, 27708-0129"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "Jeffrey Scott", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Dept. of Computer Science, Duke University, Durham, NC, 27708-0129"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lim", 
        "givenName": "Lipyeow", 
        "id": "sg:person.015270452377.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015270452377.19"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T J. Watson Research Center, Hawthorne, NY, 10532"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Padmanabhan", 
        "givenName": "Sriram", 
        "id": "sg:person.015175246447.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015175246447.02"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01231357", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022424524", 
          "https://doi.org/10.1007/bf01231357"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01231357", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022424524", 
          "https://doi.org/10.1007/bf01231357"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2001", 
    "datePublishedReg": "2001-01-01", 
    "description": "Query cost estimation is an important and well-studied problem in relational database systems. In this paper we study the cost estimation problem in the context of spatial database systems. We introduce a new method that provides accurate cost estimation for spatial selections, or window queries, by building wavelet-based histograms for spatial data. Our method is based upon two techniques: (a) A representation transformation in which geometric objects are represented by points in higher-dimensional space and window queries correspond to semi-infinite range-sum queries, and (b) Multiresolution wavelet decomposition that provides a time-efficient and space-efficient approximation of the underlying distribution of the multidimensional point data, especially for semi-infinite range-sum queries. We also show for the first time how a wavelet decomposition of a dense multidimensional array derived from a sparse array through a partial-sum computation can still be computed efficiently using sparse techniques by doing the processing implicitly on the original data. Our method eliminates the drawbacks of the partition-based histogram methods in previous work, and even with very small space allocation it gives excellent cost estimation over a broad range of spatial data distributions and queries.", 
    "editor": [
      {
        "familyName": "Jensen", 
        "givenName": "Christian S.", 
        "type": "Person"
      }, 
      {
        "familyName": "Schneider", 
        "givenName": "Markus", 
        "type": "Person"
      }, 
      {
        "familyName": "Seeger", 
        "givenName": "Bernhard", 
        "type": "Person"
      }, 
      {
        "familyName": "Tsotras", 
        "givenName": "Vassilis J.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-47724-1_10", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-42301-0", 
        "978-3-540-47724-2"
      ], 
      "name": "Advances in Spatial and Temporal Databases", 
      "type": "Book"
    }, 
    "name": "Wavelet-Based Cost Estimation for Spatial Queries", 
    "pagination": "175-193", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-47724-1_10"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "07259966d22722ec0fc13f7ddfd8e253acdd94b147b8602edb060e36177fab67"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1001500471"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-47724-1_10", 
      "https://app.dimensions.ai/details/publication/pub.1001500471"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11: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_8660_00000243.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-47724-1_10"
  }
]
 

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/3-540-47724-1_10'

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/3-540-47724-1_10'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-47724-1_10'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-47724-1_10'


 

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

108 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-47724-1_10 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N249291004d5e4114ab68834c975d628f
4 schema:citation sg:pub.10.1007/bf01231357
5 schema:datePublished 2001
6 schema:datePublishedReg 2001-01-01
7 schema:description Query cost estimation is an important and well-studied problem in relational database systems. In this paper we study the cost estimation problem in the context of spatial database systems. We introduce a new method that provides accurate cost estimation for spatial selections, or window queries, by building wavelet-based histograms for spatial data. Our method is based upon two techniques: (a) A representation transformation in which geometric objects are represented by points in higher-dimensional space and window queries correspond to semi-infinite range-sum queries, and (b) Multiresolution wavelet decomposition that provides a time-efficient and space-efficient approximation of the underlying distribution of the multidimensional point data, especially for semi-infinite range-sum queries. We also show for the first time how a wavelet decomposition of a dense multidimensional array derived from a sparse array through a partial-sum computation can still be computed efficiently using sparse techniques by doing the processing implicitly on the original data. Our method eliminates the drawbacks of the partition-based histogram methods in previous work, and even with very small space allocation it gives excellent cost estimation over a broad range of spatial data distributions and queries.
8 schema:editor N9bb947f796464e74a36ef3e7df82ea6d
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf Naa44645392784880ad76012694811c83
13 schema:name Wavelet-Based Cost Estimation for Spatial Queries
14 schema:pagination 175-193
15 schema:productId N2d191b729c864c3c83ea7e61de5ed74e
16 N61267e66bc9d4f30b1184f8c0dc9ab06
17 N64973a6754694f0485aeac95c3461780
18 schema:publisher N77d087d603b041d6a8ad6620c411e22b
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001500471
20 https://doi.org/10.1007/3-540-47724-1_10
21 schema:sdDatePublished 2019-04-15T11:31
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher N1e41f4ef34214775ab02f7ecbc1238a4
24 schema:url http://link.springer.com/10.1007/3-540-47724-1_10
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N0cda9156c9bc4466ab806963f6bb11e0 schema:familyName Schneider
29 schema:givenName Markus
30 rdf:type schema:Person
31 N1e41f4ef34214775ab02f7ecbc1238a4 schema:name Springer Nature - SN SciGraph project
32 rdf:type schema:Organization
33 N249291004d5e4114ab68834c975d628f rdf:first sg:person.012657435165.75
34 rdf:rest N42ee447fcce24cb8915792a947de677e
35 N2b1852f8581b4851acd3f639aa1d315c rdf:first sg:person.015270452377.19
36 rdf:rest N7d993d1c73064e6db8513b45cd63dcea
37 N2d191b729c864c3c83ea7e61de5ed74e schema:name dimensions_id
38 schema:value pub.1001500471
39 rdf:type schema:PropertyValue
40 N39d0ff462d0d4f65bd7011b2dc7b6099 schema:familyName Seeger
41 schema:givenName Bernhard
42 rdf:type schema:Person
43 N42ee447fcce24cb8915792a947de677e rdf:first sg:person.0613677314.28
44 rdf:rest N2b1852f8581b4851acd3f639aa1d315c
45 N52f9dee54a0a4e2cb3a7e61dbac8c2fa schema:familyName Jensen
46 schema:givenName Christian S.
47 rdf:type schema:Person
48 N61267e66bc9d4f30b1184f8c0dc9ab06 schema:name doi
49 schema:value 10.1007/3-540-47724-1_10
50 rdf:type schema:PropertyValue
51 N64973a6754694f0485aeac95c3461780 schema:name readcube_id
52 schema:value 07259966d22722ec0fc13f7ddfd8e253acdd94b147b8602edb060e36177fab67
53 rdf:type schema:PropertyValue
54 N77d087d603b041d6a8ad6620c411e22b schema:location Berlin, Heidelberg
55 schema:name Springer Berlin Heidelberg
56 rdf:type schema:Organisation
57 N7d993d1c73064e6db8513b45cd63dcea rdf:first sg:person.015175246447.02
58 rdf:rest rdf:nil
59 N9a213d1919534a40a6ec8f4761c1a340 rdf:first N9eeb711b58b34ecb8b6e67ba4bc7da8a
60 rdf:rest rdf:nil
61 N9bb947f796464e74a36ef3e7df82ea6d rdf:first N52f9dee54a0a4e2cb3a7e61dbac8c2fa
62 rdf:rest Ne02eb866b7614242a64c6e77904e0a5d
63 N9eeb711b58b34ecb8b6e67ba4bc7da8a schema:familyName Tsotras
64 schema:givenName Vassilis J.
65 rdf:type schema:Person
66 Naa44645392784880ad76012694811c83 schema:isbn 978-3-540-42301-0
67 978-3-540-47724-2
68 schema:name Advances in Spatial and Temporal Databases
69 rdf:type schema:Book
70 Nab5385c4321542f7b0ff1c910a5cb21d rdf:first N39d0ff462d0d4f65bd7011b2dc7b6099
71 rdf:rest N9a213d1919534a40a6ec8f4761c1a340
72 Ne02eb866b7614242a64c6e77904e0a5d rdf:first N0cda9156c9bc4466ab806963f6bb11e0
73 rdf:rest Nab5385c4321542f7b0ff1c910a5cb21d
74 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
75 schema:name Information and Computing Sciences
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
78 schema:name Information Systems
79 rdf:type schema:DefinedTerm
80 sg:person.012657435165.75 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
81 schema:familyName Wang
82 schema:givenName Min
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012657435165.75
84 rdf:type schema:Person
85 sg:person.015175246447.02 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
86 schema:familyName Padmanabhan
87 schema:givenName Sriram
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015175246447.02
89 rdf:type schema:Person
90 sg:person.015270452377.19 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
91 schema:familyName Lim
92 schema:givenName Lipyeow
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015270452377.19
94 rdf:type schema:Person
95 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
96 schema:familyName Vitter
97 schema:givenName Jeffrey Scott
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
99 rdf:type schema:Person
100 sg:pub.10.1007/bf01231357 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022424524
101 https://doi.org/10.1007/bf01231357
102 rdf:type schema:CreativeWork
103 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
104 schema:name Dept. of Computer Science, Duke University, Durham, NC, 27708-0129
105 rdf:type schema:Organization
106 https://www.grid.ac/institutes/grid.481554.9 schema:alternateName IBM Research – Thomas J. Watson Research Center
107 schema:name IBM T J. Watson Research Center, Hawthorne, NY, 10532
108 rdf:type schema:Organization
 




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


...