De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Yuriy Arbitman , Moni Naor , Gil Segev

ABSTRACT

Cuckoo hashing is a highly practical dynamic dictionary: it provides amortized constant insertion time, worst case constant deletion time and lookup time, and good memory utilization. However, with a noticeable probability during the insertion of n elements some insertion requires Ω(logn) time. Whereas such an amortized guarantee may be suitable for some applications, in other applications (such as high-performance routing) this is highly undesirable.Kirsch and Mitzenmacher (Allerton ’07) proposed a de-amortization of cuckoo hashing using queueing techniques that preserve its attractive properties. They demonstrated a significant improvement to the worst case performance of cuckoo hashing via experimental results, but left open the problem of constructing a scheme with provable properties.In this work we present a de-amortization of cuckoo hashing that provably guarantees constant worst case operations. Specifically, for any sequence of polynomially many operations, with overwhelming probability over the randomness of the initialization phase, each operation is performed in constant time. In addition, we present a general approach for proving that the performance guarantees are preserved when using hash functions with limited independence instead of truly random hash functions. Our approach relies on a recent result of Braverman (CCC ’09) showing that poly-logarithmic independence fools AC0 circuits, and may find additional applications in various similar settings. Our theoretical analysis and experimental results indicate that the scheme is highly efficient, and provides a practical alternative to the only other known approach for constructing dynamic dictionaries with such worst case guarantees, due to Dietzfelbinger and Meyer auf der Heide (ICALP ’90). More... »

PAGES

107-118

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-02927-1_11

DOI

http://dx.doi.org/10.1007/978-3-642-02927-1_11

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "familyName": "Arbitman", 
        "givenName": "Yuriy", 
        "id": "sg:person.016015034417.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016015034417.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Segev", 
        "givenName": "Gil", 
        "id": "sg:person.016423726453.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "Cuckoo hashing is a highly practical dynamic dictionary: it provides amortized constant insertion time, worst case constant deletion time and lookup time, and good memory utilization. However, with a noticeable probability during the insertion of n elements some insertion requires \u03a9(logn) time. Whereas such an amortized guarantee may be suitable for some applications, in other applications (such as high-performance routing) this is highly undesirable.Kirsch and Mitzenmacher (Allerton \u201907) proposed a de-amortization of cuckoo hashing using queueing techniques that preserve its attractive properties. They demonstrated a significant improvement to the worst case performance of cuckoo hashing via experimental results, but left open the problem of constructing a scheme with provable properties.In this work we present a de-amortization of cuckoo hashing that provably guarantees constant worst case operations. Specifically, for any sequence of polynomially many operations, with overwhelming probability over the randomness of the initialization phase, each operation is performed in constant time. In addition, we present a general approach for proving that the performance guarantees are preserved when using hash functions with limited independence instead of truly random hash functions. Our approach relies on a recent result of Braverman (CCC \u201909) showing that poly-logarithmic independence fools AC0 circuits, and may find additional applications in various similar settings. Our theoretical analysis and experimental results indicate that the scheme is highly efficient, and provides a practical alternative to the only other known approach for constructing dynamic dictionaries with such worst case guarantees, due to Dietzfelbinger and Meyer auf der Heide (ICALP\u00a0\u201990).", 
    "editor": [
      {
        "familyName": "Albers", 
        "givenName": "Susanne", 
        "type": "Person"
      }, 
      {
        "familyName": "Marchetti-Spaccamela", 
        "givenName": "Alberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Matias", 
        "givenName": "Yossi", 
        "type": "Person"
      }, 
      {
        "familyName": "Nikoletseas", 
        "givenName": "Sotiris", 
        "type": "Person"
      }, 
      {
        "familyName": "Thomas", 
        "givenName": "Wolfgang", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-02927-1_11", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-02926-4", 
        "978-3-642-02927-1"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "cuckoo hashing", 
      "hash functions", 
      "dynamic dictionary", 
      "better memory utilization", 
      "experimental results", 
      "random hash function", 
      "worst case guarantees", 
      "lookup time", 
      "memory utilization", 
      "worst case performance", 
      "provable properties", 
      "initialization phase", 
      "hashing", 
      "performance guarantees", 
      "Meyer auf", 
      "deletion time", 
      "queueing techniques", 
      "case performance", 
      "overwhelming probability", 
      "constant time", 
      "guarantees", 
      "Worst-Case Performance", 
      "dictionary", 
      "scheme", 
      "general approach", 
      "applications", 
      "limited independence", 
      "theoretical analysis", 
      "performance", 
      "operation", 
      "noticeable probability", 
      "case operation", 
      "attractive properties", 
      "additional applications", 
      "significant improvement", 
      "practical alternative", 
      "randomness", 
      "time", 
      "probability", 
      "Mitzenmacher", 
      "technique", 
      "results", 
      "AC0", 
      "insertion time", 
      "utilization", 
      "cuckoos", 
      "work", 
      "recent results", 
      "Braverman", 
      "improvement", 
      "sequence", 
      "function", 
      "similar settings", 
      "elements", 
      "Kirsch", 
      "alternative", 
      "independence", 
      "setting", 
      "analysis", 
      "addition", 
      "de", 
      "insertion", 
      "properties", 
      "phase", 
      "Heide", 
      "auf", 
      "worst case operation", 
      "problem", 
      "approach", 
      "practical dynamic dictionary", 
      "constant insertion time", 
      "worst case constant deletion time", 
      "case constant deletion time", 
      "constant deletion time", 
      "amortized guarantee", 
      "constant worst case operations", 
      "poly-logarithmic independence fools AC0", 
      "independence fools AC0", 
      "fools AC0", 
      "such worst case guarantees", 
      "case guarantees", 
      "Dietzfelbinger", 
      "Provable Worst-Case Performance"
    ], 
    "name": "De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results", 
    "pagination": "107-118", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1029428297"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-02927-1_11"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-02927-1_11", 
      "https://app.dimensions.ai/details/publication/pub.1029428297"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:28", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_85.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-02927-1_11"
  }
]
 

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/978-3-642-02927-1_11'

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/978-3-642-02927-1_11'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02927-1_11'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02927-1_11'


 

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

176 TRIPLES      23 PREDICATES      109 URIs      102 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-02927-1_11 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N7d8388fbad184ee180ef0a93c0fdf5bc
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description Cuckoo hashing is a highly practical dynamic dictionary: it provides amortized constant insertion time, worst case constant deletion time and lookup time, and good memory utilization. However, with a noticeable probability during the insertion of n elements some insertion requires Ω(logn) time. Whereas such an amortized guarantee may be suitable for some applications, in other applications (such as high-performance routing) this is highly undesirable.Kirsch and Mitzenmacher (Allerton ’07) proposed a de-amortization of cuckoo hashing using queueing techniques that preserve its attractive properties. They demonstrated a significant improvement to the worst case performance of cuckoo hashing via experimental results, but left open the problem of constructing a scheme with provable properties.In this work we present a de-amortization of cuckoo hashing that provably guarantees constant worst case operations. Specifically, for any sequence of polynomially many operations, with overwhelming probability over the randomness of the initialization phase, each operation is performed in constant time. In addition, we present a general approach for proving that the performance guarantees are preserved when using hash functions with limited independence instead of truly random hash functions. Our approach relies on a recent result of Braverman (CCC ’09) showing that poly-logarithmic independence fools AC0 circuits, and may find additional applications in various similar settings. Our theoretical analysis and experimental results indicate that the scheme is highly efficient, and provides a practical alternative to the only other known approach for constructing dynamic dictionaries with such worst case guarantees, due to Dietzfelbinger and Meyer auf der Heide (ICALP ’90).
7 schema:editor Nb6cf7642bfde47bda3d7d9094b99907e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Ne4dc20373df246ccb074b199b2ba4f45
12 schema:keywords AC0
13 Braverman
14 Dietzfelbinger
15 Heide
16 Kirsch
17 Meyer auf
18 Mitzenmacher
19 Provable Worst-Case Performance
20 Worst-Case Performance
21 addition
22 additional applications
23 alternative
24 amortized guarantee
25 analysis
26 applications
27 approach
28 attractive properties
29 auf
30 better memory utilization
31 case constant deletion time
32 case guarantees
33 case operation
34 case performance
35 constant deletion time
36 constant insertion time
37 constant time
38 constant worst case operations
39 cuckoo hashing
40 cuckoos
41 de
42 deletion time
43 dictionary
44 dynamic dictionary
45 elements
46 experimental results
47 fools AC0
48 function
49 general approach
50 guarantees
51 hash functions
52 hashing
53 improvement
54 independence
55 independence fools AC0
56 initialization phase
57 insertion
58 insertion time
59 limited independence
60 lookup time
61 memory utilization
62 noticeable probability
63 operation
64 overwhelming probability
65 performance
66 performance guarantees
67 phase
68 poly-logarithmic independence fools AC0
69 practical alternative
70 practical dynamic dictionary
71 probability
72 problem
73 properties
74 provable properties
75 queueing techniques
76 random hash function
77 randomness
78 recent results
79 results
80 scheme
81 sequence
82 setting
83 significant improvement
84 similar settings
85 such worst case guarantees
86 technique
87 theoretical analysis
88 time
89 utilization
90 work
91 worst case constant deletion time
92 worst case guarantees
93 worst case operation
94 worst case performance
95 schema:name De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
96 schema:pagination 107-118
97 schema:productId N19ca2d1621ea4cc7aee7361f82d48dc8
98 N2c283618924748b79667853a1d6912ad
99 schema:publisher Nf4e9bb054cc74e7bb5bc5f99b3643b6c
100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029428297
101 https://doi.org/10.1007/978-3-642-02927-1_11
102 schema:sdDatePublished 2022-01-01T19:28
103 schema:sdLicense https://scigraph.springernature.com/explorer/license/
104 schema:sdPublisher N18aa20315f9747b18d6b6ad16cdfd43f
105 schema:url https://doi.org/10.1007/978-3-642-02927-1_11
106 sgo:license sg:explorer/license/
107 sgo:sdDataset chapters
108 rdf:type schema:Chapter
109 N08d37ae7bb024da684f06dccaa1f78c2 schema:familyName Marchetti-Spaccamela
110 schema:givenName Alberto
111 rdf:type schema:Person
112 N08f15d04f5584d2e9aa5e3d19d27c83e rdf:first N08d37ae7bb024da684f06dccaa1f78c2
113 rdf:rest Nce92a259bb0e415e987e3769dfcc03f3
114 N0ed40591013a48678b0a137b4e2a4b4a schema:familyName Nikoletseas
115 schema:givenName Sotiris
116 rdf:type schema:Person
117 N18aa20315f9747b18d6b6ad16cdfd43f schema:name Springer Nature - SN SciGraph project
118 rdf:type schema:Organization
119 N19ca2d1621ea4cc7aee7361f82d48dc8 schema:name doi
120 schema:value 10.1007/978-3-642-02927-1_11
121 rdf:type schema:PropertyValue
122 N1f8d6e4667834b759ea5409d603f83e6 schema:familyName Albers
123 schema:givenName Susanne
124 rdf:type schema:Person
125 N2b9c97831b7f46638fa02e8556a75c38 schema:familyName Matias
126 schema:givenName Yossi
127 rdf:type schema:Person
128 N2c283618924748b79667853a1d6912ad schema:name dimensions_id
129 schema:value pub.1029428297
130 rdf:type schema:PropertyValue
131 N317068e4b364494c9fdaf9c884dc0e46 rdf:first sg:person.016423726453.97
132 rdf:rest rdf:nil
133 N7d8388fbad184ee180ef0a93c0fdf5bc rdf:first sg:person.016015034417.00
134 rdf:rest N863d6507a63f4ea7aa628fab9b13d142
135 N863d6507a63f4ea7aa628fab9b13d142 rdf:first sg:person.07776170271.83
136 rdf:rest N317068e4b364494c9fdaf9c884dc0e46
137 N88bdb71a98ec425591670bc8c9b666b0 schema:familyName Thomas
138 schema:givenName Wolfgang
139 rdf:type schema:Person
140 Nb6cf7642bfde47bda3d7d9094b99907e rdf:first N1f8d6e4667834b759ea5409d603f83e6
141 rdf:rest N08f15d04f5584d2e9aa5e3d19d27c83e
142 Nce92a259bb0e415e987e3769dfcc03f3 rdf:first N2b9c97831b7f46638fa02e8556a75c38
143 rdf:rest Ne464d62e9fe74c1ab7df9c7c7e38b578
144 Ne464d62e9fe74c1ab7df9c7c7e38b578 rdf:first N0ed40591013a48678b0a137b4e2a4b4a
145 rdf:rest Nef4f8c62553a47be9b49f5f64837c558
146 Ne4dc20373df246ccb074b199b2ba4f45 schema:isbn 978-3-642-02926-4
147 978-3-642-02927-1
148 schema:name Automata, Languages and Programming
149 rdf:type schema:Book
150 Nef4f8c62553a47be9b49f5f64837c558 rdf:first N88bdb71a98ec425591670bc8c9b666b0
151 rdf:rest rdf:nil
152 Nf4e9bb054cc74e7bb5bc5f99b3643b6c schema:name Springer Nature
153 rdf:type schema:Organisation
154 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
155 schema:name Information and Computing Sciences
156 rdf:type schema:DefinedTerm
157 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
158 schema:name Computation Theory and Mathematics
159 rdf:type schema:DefinedTerm
160 sg:person.016015034417.00 schema:familyName Arbitman
161 schema:givenName Yuriy
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016015034417.00
163 rdf:type schema:Person
164 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
165 schema:familyName Segev
166 schema:givenName Gil
167 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
168 rdf:type schema:Person
169 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
170 schema:familyName Naor
171 schema:givenName Moni
172 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
173 rdf:type schema:Person
174 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
175 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
176 rdf:type schema:Organization
 




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


...