Optimal cooperative search in fractional cascaded data structures View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1996-02

AUTHORS

R. Tamassia, J. S. Vitter

ABSTRACT

Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search. More... »

PAGES

154-171

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01941686

DOI

http://dx.doi.org/10.1007/bf01941686

DIMENSIONS

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


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/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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tamassia", 
        "givenName": "R.", 
        "id": "sg:person.0674326220.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Duke University", 
          "id": "https://www.grid.ac/institutes/grid.26009.3d", 
          "name": [
            "Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Vitter", 
        "givenName": "J. S.", 
        "id": "sg:person.0613677314.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1145/357337.357338", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001625512"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840386", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1005703240", 
          "https://doi.org/10.1007/bf01840386"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840440", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014205873", 
          "https://doi.org/10.1007/bf01840440"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840440", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014205873", 
          "https://doi.org/10.1007/bf01840440"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1021021236", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4612-1098-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021021236", 
          "https://doi.org/10.1007/978-1-4612-1098-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(85)80045-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025683794"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0019-9958(85)80045-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025683794"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(89)90032-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043732858"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762118", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048989890", 
          "https://doi.org/10.1007/bf01762118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01762118", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048989890", 
          "https://doi.org/10.1007/bf01762118"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840441", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052525069", 
          "https://doi.org/10.1007/bf01840441"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01840441", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052525069", 
          "https://doi.org/10.1007/bf01840441"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0206043", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841382"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0212002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841682"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0214051", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841840"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0215023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062841885"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842134"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0220045", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842305"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218195992000081", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062960724"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0218195992000287", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062960744"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1996-02", 
    "datePublishedReg": "1996-02-01", 
    "description": "Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01941686", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "15"
      }
    ], 
    "name": "Optimal cooperative search in fractional cascaded data structures", 
    "pagination": "154-171", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "6b51b773cddb5314aae9cfc02f01a7d5da0c1f5d3fac972af11234c9316d1e07"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01941686"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1022526168"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01941686", 
      "https://app.dimensions.ai/details/publication/pub.1022526168"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:24", 
    "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/0000000355_0000000355/records_53014_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01941686"
  }
]
 

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/bf01941686'

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/bf01941686'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01941686'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01941686'


 

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

126 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01941686 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8485b73ad032480ba0596617fc2e537f
4 schema:citation sg:pub.10.1007/978-1-4612-1098-6
5 sg:pub.10.1007/bf01762118
6 sg:pub.10.1007/bf01840386
7 sg:pub.10.1007/bf01840440
8 sg:pub.10.1007/bf01840441
9 https://app.dimensions.ai/details/publication/pub.1021021236
10 https://doi.org/10.1016/0196-6774(89)90032-1
11 https://doi.org/10.1016/s0019-9958(85)80045-0
12 https://doi.org/10.1137/0206043
13 https://doi.org/10.1137/0212002
14 https://doi.org/10.1137/0214051
15 https://doi.org/10.1137/0215023
16 https://doi.org/10.1137/0218035
17 https://doi.org/10.1137/0220045
18 https://doi.org/10.1142/s0218195992000081
19 https://doi.org/10.1142/s0218195992000287
20 https://doi.org/10.1145/357337.357338
21 schema:datePublished 1996-02
22 schema:datePublishedReg 1996-02-01
23 schema:description Fractional cascading is a technique designed to allow efficient sequential search in a graph with catalogs of total sizen. The search consists of locating a key in the catalogs along a path. In this paper we show how to preprocess a variety of fractional cascaded data structures whose underlying graph is a tree so that searching can be done efficiently in parallel. The preprocessing takesO(logn) time withn/logn processors on an EREW PRAM. For a balanced binary tree, cooperative search along root-to-leaf paths can be done inO((logn)/logp) time usingp processors on a CREW PRAM. Both of these time/processor constraints are optimal. The searching in the fractional cascaded data structure can be either explicit, in which the search path is specified before the search starts, or implicit, in which the branching is determined at each node. We apply this technique to a variety of geometric problems, including point location, range search, and segment intersection search.
24 schema:genre research_article
25 schema:inLanguage en
26 schema:isAccessibleForFree true
27 schema:isPartOf N9b20f791d7564cf5980a9b0727f6d9f3
28 Ne8ee19ad453445648c330fb9930a0263
29 sg:journal.1047644
30 schema:name Optimal cooperative search in fractional cascaded data structures
31 schema:pagination 154-171
32 schema:productId N17f7bc5b06ef4ae8a2d9e9f8672a56b5
33 N5fb91a0e770c424db6e782945d38735f
34 N8e5a10880cd54efba13c24f1a7952247
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022526168
36 https://doi.org/10.1007/bf01941686
37 schema:sdDatePublished 2019-04-11T11:24
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Nc9ced50c41bf4adba304658b563746bc
40 schema:url http://link.springer.com/10.1007/BF01941686
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N17f7bc5b06ef4ae8a2d9e9f8672a56b5 schema:name doi
45 schema:value 10.1007/bf01941686
46 rdf:type schema:PropertyValue
47 N5fb91a0e770c424db6e782945d38735f schema:name readcube_id
48 schema:value 6b51b773cddb5314aae9cfc02f01a7d5da0c1f5d3fac972af11234c9316d1e07
49 rdf:type schema:PropertyValue
50 N8485b73ad032480ba0596617fc2e537f rdf:first sg:person.0674326220.33
51 rdf:rest N8f073dc8ba934cd5a0e6e65b4f9a75bf
52 N8e5a10880cd54efba13c24f1a7952247 schema:name dimensions_id
53 schema:value pub.1022526168
54 rdf:type schema:PropertyValue
55 N8f073dc8ba934cd5a0e6e65b4f9a75bf rdf:first sg:person.0613677314.28
56 rdf:rest rdf:nil
57 N9b20f791d7564cf5980a9b0727f6d9f3 schema:volumeNumber 15
58 rdf:type schema:PublicationVolume
59 Nc9ced50c41bf4adba304658b563746bc schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 Ne8ee19ad453445648c330fb9930a0263 schema:issueNumber 2
62 rdf:type schema:PublicationIssue
63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
64 schema:name Information and Computing Sciences
65 rdf:type schema:DefinedTerm
66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
67 schema:name Computation Theory and Mathematics
68 rdf:type schema:DefinedTerm
69 sg:journal.1047644 schema:issn 0178-4617
70 1432-0541
71 schema:name Algorithmica
72 rdf:type schema:Periodical
73 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.26009.3d
74 schema:familyName Vitter
75 schema:givenName J. S.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
77 rdf:type schema:Person
78 sg:person.0674326220.33 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
79 schema:familyName Tamassia
80 schema:givenName R.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0674326220.33
82 rdf:type schema:Person
83 sg:pub.10.1007/978-1-4612-1098-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021021236
84 https://doi.org/10.1007/978-1-4612-1098-6
85 rdf:type schema:CreativeWork
86 sg:pub.10.1007/bf01762118 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048989890
87 https://doi.org/10.1007/bf01762118
88 rdf:type schema:CreativeWork
89 sg:pub.10.1007/bf01840386 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005703240
90 https://doi.org/10.1007/bf01840386
91 rdf:type schema:CreativeWork
92 sg:pub.10.1007/bf01840440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014205873
93 https://doi.org/10.1007/bf01840440
94 rdf:type schema:CreativeWork
95 sg:pub.10.1007/bf01840441 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052525069
96 https://doi.org/10.1007/bf01840441
97 rdf:type schema:CreativeWork
98 https://app.dimensions.ai/details/publication/pub.1021021236 schema:CreativeWork
99 https://doi.org/10.1016/0196-6774(89)90032-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043732858
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1016/s0019-9958(85)80045-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025683794
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1137/0206043 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841382
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1137/0212002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841682
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1137/0214051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841840
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1137/0215023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841885
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1137/0218035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842134
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1137/0220045 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842305
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1142/s0218195992000081 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960724
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1142/s0218195992000287 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062960744
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1145/357337.357338 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001625512
120 rdf:type schema:CreativeWork
121 https://www.grid.ac/institutes/grid.26009.3d schema:alternateName Duke University
122 schema:name Department of Computer Science, Duke University, 27708-0129, Durham, NC, USA
123 rdf:type schema:Organization
124 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
125 schema:name Department of Computer Science, Brown University, 02912-1910, Providence, RI, USA
126 rdf:type schema:Organization
 




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


...