Predecessor Queries in Constant Time? View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Marek Karpinski , Yakov Nekrich

ABSTRACT

In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{{\rm log}n})$\end{document} queries in O(1) time per query and requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{\epsilon\sqrt{{\rm log}n}})$\end{document} space for any ε > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$N = \Omega(n^{\epsilon\sqrt{{\rm log}n}})$\end{document} where N is the size of the universe. We also present a data structure that answers O(log log N) predecessor queries in O(1) time per query and requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{\epsilon{\rm log log} {\it N}})$\end{document} space for any ε > 0. The method of solution relies on a certain way of searching for predecessors of all elements of the query in parallel.In a general case, our approach leads to a data structure that supports p(n) queries in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{{\rm log} n}/p(n))$\end{document} time per query and requires O(n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{p({\it n})}$\end{document}) space for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$p(n) =O(\sqrt{{\rm log}n})$\end{document}, and a data structure that supports p(N) queries in O(log log N/p(N)) time per query and requires O(n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{p({\it N})}$\end{document}) space for any p(N)=O(log log N). More... »

PAGES

238-248

Book

TITLE

Algorithms – ESA 2005

ISBN

978-3-540-29118-3
978-3-540-31951-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11561071_23

DOI

http://dx.doi.org/10.1007/11561071_23

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nekrich", 
        "givenName": "Yakov", 
        "id": "sg:person.014556642366.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{{\\rm log}n})$\\end{document} queries in O(1) time per query and requires \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(n^{\\epsilon\\sqrt{{\\rm log}n}})$\\end{document} space for any \u03b5 > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$N = \\Omega(n^{\\epsilon\\sqrt{{\\rm log}n}})$\\end{document} where N is the size of the universe. We also present a data structure that answers O(log log N) predecessor queries in O(1) time per query and requires \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(n^{\\epsilon{\\rm log log} {\\it N}})$\\end{document} space for any \u03b5 > 0. The method of solution relies on a certain way of searching for predecessors of all elements of the query in parallel.In a general case, our approach leads to a data structure that supports p(n) queries in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(\\sqrt{{\\rm log} n}/p(n))$\\end{document} time per query and requires O(n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$^{p({\\it n})}$\\end{document}) space for any \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$p(n) =O(\\sqrt{{\\rm log}n})$\\end{document}, and a data structure that supports p(N) queries in O(log log N/p(N)) time per query and requires O(n\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$^{p({\\it N})}$\\end{document}) space for any p(N)=O(log log N).", 
    "editor": [
      {
        "familyName": "Brodal", 
        "givenName": "Gerth St\u00f8lting", 
        "type": "Person"
      }, 
      {
        "familyName": "Leonardi", 
        "givenName": "Stefano", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11561071_23", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-29118-3", 
        "978-3-540-31951-1"
      ], 
      "name": "Algorithms \u2013 ESA 2005", 
      "type": "Book"
    }, 
    "keywords": [
      "data structure", 
      "predecessor queries", 
      "static data structures", 
      "time data structures", 
      "queries", 
      "constant time", 
      "space", 
      "general case", 
      "time", 
      "certain way", 
      "solution", 
      "way", 
      "parallel", 
      "method", 
      "predecessors", 
      "structure", 
      "elements", 
      "method of solution", 
      "size", 
      "cases", 
      "universe", 
      "paper", 
      "approach"
    ], 
    "name": "Predecessor Queries in Constant Time?", 
    "pagination": "238-248", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021245417"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11561071_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11561071_23", 
      "https://app.dimensions.ai/details/publication/pub.1021245417"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-12-01T06:52", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/chapter/chapter_350.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11561071_23"
  }
]
 

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/11561071_23'

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/11561071_23'

Turtle is a human-readable linked data format.

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

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

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


 

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

94 TRIPLES      22 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11561071_23 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N78512a58d4c14984b3eb9aac0edeb808
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{{\rm log}n})$\end{document} queries in O(1) time per query and requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{\epsilon\sqrt{{\rm log}n}})$\end{document} space for any ε > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$N = \Omega(n^{\epsilon\sqrt{{\rm log}n}})$\end{document} where N is the size of the universe. We also present a data structure that answers O(log log N) predecessor queries in O(1) time per query and requires \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(n^{\epsilon{\rm log log} {\it N}})$\end{document} space for any ε > 0. The method of solution relies on a certain way of searching for predecessors of all elements of the query in parallel.In a general case, our approach leads to a data structure that supports p(n) queries in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(\sqrt{{\rm log} n}/p(n))$\end{document} time per query and requires O(n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{p({\it n})}$\end{document}) space for any \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$p(n) =O(\sqrt{{\rm log}n})$\end{document}, and a data structure that supports p(N) queries in O(log log N/p(N)) time per query and requires O(n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$^{p({\it N})}$\end{document}) space for any p(N)=O(log log N).
7 schema:editor N51d96a7f96564bb3ad72a41769e04ba8
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N417e9c9f2cf045479b8b3bd296f2bfa4
11 schema:keywords approach
12 cases
13 certain way
14 constant time
15 data structure
16 elements
17 general case
18 method
19 method of solution
20 paper
21 parallel
22 predecessor queries
23 predecessors
24 queries
25 size
26 solution
27 space
28 static data structures
29 structure
30 time
31 time data structures
32 universe
33 way
34 schema:name Predecessor Queries in Constant Time?
35 schema:pagination 238-248
36 schema:productId N2af02d68ee2541ffb3aa9163eb997318
37 N83caa1a809764fa7a18bdce67005dcb6
38 schema:publisher N6fadf8f8d83f4226ba52a31518effa35
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021245417
40 https://doi.org/10.1007/11561071_23
41 schema:sdDatePublished 2022-12-01T06:52
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N2fb6442c9e0543dcb3f86face6b1ec71
44 schema:url https://doi.org/10.1007/11561071_23
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N2af02d68ee2541ffb3aa9163eb997318 schema:name dimensions_id
49 schema:value pub.1021245417
50 rdf:type schema:PropertyValue
51 N2fb6442c9e0543dcb3f86face6b1ec71 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N417e9c9f2cf045479b8b3bd296f2bfa4 schema:isbn 978-3-540-29118-3
54 978-3-540-31951-1
55 schema:name Algorithms – ESA 2005
56 rdf:type schema:Book
57 N51d96a7f96564bb3ad72a41769e04ba8 rdf:first Nc05c6d43450c432288023c45bc9d2d31
58 rdf:rest N968b1bcc9d0e4f40b88648418282c62d
59 N6fadf8f8d83f4226ba52a31518effa35 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N70264fb367b04d76a09415e91f5ac3d6 schema:familyName Leonardi
62 schema:givenName Stefano
63 rdf:type schema:Person
64 N78512a58d4c14984b3eb9aac0edeb808 rdf:first sg:person.011636042271.02
65 rdf:rest Nbe935b1da5aa45d69021664170694187
66 N83caa1a809764fa7a18bdce67005dcb6 schema:name doi
67 schema:value 10.1007/11561071_23
68 rdf:type schema:PropertyValue
69 N968b1bcc9d0e4f40b88648418282c62d rdf:first N70264fb367b04d76a09415e91f5ac3d6
70 rdf:rest rdf:nil
71 Nbe935b1da5aa45d69021664170694187 rdf:first sg:person.014556642366.63
72 rdf:rest rdf:nil
73 Nc05c6d43450c432288023c45bc9d2d31 schema:familyName Brodal
74 schema:givenName Gerth Stølting
75 rdf:type schema:Person
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
80 schema:name Data Format
81 rdf:type schema:DefinedTerm
82 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
83 schema:familyName Karpinski
84 schema:givenName Marek
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
86 rdf:type schema:Person
87 sg:person.014556642366.63 schema:affiliation grid-institutes:grid.10388.32
88 schema:familyName Nekrich
89 schema:givenName Yakov
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
91 rdf:type schema:Person
92 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn
93 schema:name Dept. of Computer Science, University of Bonn
94 rdf:type schema:Organization
 




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


...