History-Independent Cuckoo Hashing View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008-01-01

AUTHORS

Moni Naor , Gil Segev , Udi Wieder

ABSTRACT

Cuckoo hashing is an efficient and practical dynamic dictionary. It provides expected amortized constant update time, worst case constant lookup time, and good memory utilization. Various experiments demonstrated that cuckoo hashing is highly suitable for modern computer architectures and distributed settings, and offers significant improvements compared to other schemes.In this work we construct a practical history-independent dynamic dictionary based on cuckoo hashing. In a history-independent data structure, the memory representation at any point in time yields no information on the specific sequence of insertions and deletions that led to its current content, other than the content itself. Such a property is significant when preventing unintended leakage of information, and was also found useful in several algorithmic settings.Our construction enjoys most of the attractive properties of cuckoo hashing. In particular, no dynamic memory allocation is required, updates are performed in expected amortized constant time, and membership queries are performed in worst case constant time. Moreover, with high probability, the lookup procedure queries only two memory entries which are independent and can be queried in parallel. The approach underlying our construction is to enforce a canonical memory representation on cuckoo hashing. That is, up to the initial randomness, each set of elements has a unique memory representation. More... »

PAGES

631-642

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_51

DOI

http://dx.doi.org/10.1007/978-3-540-70583-3_51

DIMENSIONS

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


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": "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"
      }, 
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Silicon Valley Campus, 1065 La Avenida, Mountain View, CA 94043", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, Silicon Valley Campus, 1065 La Avenida, Mountain View, CA 94043"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wieder", 
        "givenName": "Udi", 
        "id": "sg:person.014670455446.79", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014670455446.79"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008-01-01", 
    "datePublishedReg": "2008-01-01", 
    "description": "Cuckoo hashing is an efficient and practical dynamic dictionary. It provides expected amortized constant update time, worst case constant lookup time, and good memory utilization. Various experiments demonstrated that cuckoo hashing is highly suitable for modern computer architectures and distributed settings, and offers significant improvements compared to other schemes.In this work we construct a practical history-independent dynamic dictionary based on cuckoo hashing. In a history-independent data structure, the memory representation at any point in time yields no information on the specific sequence of insertions and deletions that led to its current content, other than the content itself. Such a property is significant when preventing unintended leakage of information, and was also found useful in several algorithmic settings.Our construction enjoys most of the attractive properties of cuckoo hashing. In particular, no dynamic memory allocation is required, updates are performed in expected amortized constant time, and membership queries are performed in worst case constant time. Moreover, with high probability, the lookup procedure queries only two memory entries which are independent and can be queried in parallel. The approach underlying our construction is to enforce a canonical memory representation on cuckoo hashing. That is, up to the initial randomness, each set of elements has a unique memory representation.", 
    "editor": [
      {
        "familyName": "Aceto", 
        "givenName": "Luca", 
        "type": "Person"
      }, 
      {
        "familyName": "Damg\u00e5rd", 
        "givenName": "Ivan", 
        "type": "Person"
      }, 
      {
        "familyName": "Goldberg", 
        "givenName": "Leslie Ann", 
        "type": "Person"
      }, 
      {
        "familyName": "Halld\u00f3rsson", 
        "givenName": "Magn\u00fas M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Ing\u00f3lfsd\u00f3ttir", 
        "givenName": "Anna", 
        "type": "Person"
      }, 
      {
        "familyName": "Walukiewicz", 
        "givenName": "Igor", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-70583-3_51", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-70582-6", 
        "978-3-540-70583-3"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "cuckoo hashing", 
      "dynamic dictionary", 
      "modern computer architectures", 
      "better memory utilization", 
      "dynamic memory allocation", 
      "constant lookup time", 
      "constant time", 
      "constant update time", 
      "computer architecture", 
      "memory utilization", 
      "worst case constant time", 
      "memory allocation", 
      "data structure", 
      "lookup time", 
      "hashing", 
      "update time", 
      "algorithmic settings", 
      "membership queries", 
      "lookup procedure", 
      "unintended leakage", 
      "set of elements", 
      "memory entries", 
      "initial randomness", 
      "dictionary", 
      "representation", 
      "queries", 
      "information", 
      "architecture", 
      "high probability", 
      "attractive properties", 
      "scheme", 
      "allocation", 
      "update", 
      "significant improvement", 
      "set", 
      "construction", 
      "randomness", 
      "memory representations", 
      "time", 
      "Current Contents", 
      "utilization", 
      "work", 
      "probability", 
      "experiments", 
      "parallel", 
      "improvement", 
      "setting", 
      "point", 
      "sequence", 
      "content", 
      "elements", 
      "entry", 
      "procedure", 
      "structure", 
      "leakage", 
      "properties", 
      "specific sequences", 
      "insertion", 
      "time yield", 
      "deletion", 
      "yield", 
      "approach", 
      "practical dynamic dictionary", 
      "worst case constant lookup time", 
      "case constant lookup time", 
      "practical history-independent dynamic dictionary", 
      "history-independent dynamic dictionary", 
      "history-independent data structure", 
      "case constant time", 
      "canonical memory representation", 
      "unique memory representation", 
      "History-Independent Cuckoo Hashing"
    ], 
    "name": "History-Independent Cuckoo Hashing", 
    "pagination": "631-642", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011965774"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-70583-3_51"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-70583-3_51", 
      "https://app.dimensions.ai/details/publication/pub.1011965774"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:19", 
    "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_331.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-70583-3_51"
  }
]
 

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-540-70583-3_51'

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-540-70583-3_51'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-70583-3_51'

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-540-70583-3_51'


 

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

174 TRIPLES      23 PREDICATES      96 URIs      89 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-70583-3_51 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nfe859ac13d3a4f3a8d7d2d31d5446fe6
4 schema:datePublished 2008-01-01
5 schema:datePublishedReg 2008-01-01
6 schema:description Cuckoo hashing is an efficient and practical dynamic dictionary. It provides expected amortized constant update time, worst case constant lookup time, and good memory utilization. Various experiments demonstrated that cuckoo hashing is highly suitable for modern computer architectures and distributed settings, and offers significant improvements compared to other schemes.In this work we construct a practical history-independent dynamic dictionary based on cuckoo hashing. In a history-independent data structure, the memory representation at any point in time yields no information on the specific sequence of insertions and deletions that led to its current content, other than the content itself. Such a property is significant when preventing unintended leakage of information, and was also found useful in several algorithmic settings.Our construction enjoys most of the attractive properties of cuckoo hashing. In particular, no dynamic memory allocation is required, updates are performed in expected amortized constant time, and membership queries are performed in worst case constant time. Moreover, with high probability, the lookup procedure queries only two memory entries which are independent and can be queried in parallel. The approach underlying our construction is to enforce a canonical memory representation on cuckoo hashing. That is, up to the initial randomness, each set of elements has a unique memory representation.
7 schema:editor N5bc5f30f26784076994661f2da6c4e45
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N6bbd963971cc4bf9aa36504fbbaef68e
12 schema:keywords Current Contents
13 History-Independent Cuckoo Hashing
14 algorithmic settings
15 allocation
16 approach
17 architecture
18 attractive properties
19 better memory utilization
20 canonical memory representation
21 case constant lookup time
22 case constant time
23 computer architecture
24 constant lookup time
25 constant time
26 constant update time
27 construction
28 content
29 cuckoo hashing
30 data structure
31 deletion
32 dictionary
33 dynamic dictionary
34 dynamic memory allocation
35 elements
36 entry
37 experiments
38 hashing
39 high probability
40 history-independent data structure
41 history-independent dynamic dictionary
42 improvement
43 information
44 initial randomness
45 insertion
46 leakage
47 lookup procedure
48 lookup time
49 membership queries
50 memory allocation
51 memory entries
52 memory representations
53 memory utilization
54 modern computer architectures
55 parallel
56 point
57 practical dynamic dictionary
58 practical history-independent dynamic dictionary
59 probability
60 procedure
61 properties
62 queries
63 randomness
64 representation
65 scheme
66 sequence
67 set
68 set of elements
69 setting
70 significant improvement
71 specific sequences
72 structure
73 time
74 time yield
75 unintended leakage
76 unique memory representation
77 update
78 update time
79 utilization
80 work
81 worst case constant lookup time
82 worst case constant time
83 yield
84 schema:name History-Independent Cuckoo Hashing
85 schema:pagination 631-642
86 schema:productId N5f1a1bd8df1f4c9281c777ac67bf6bbc
87 Nf11aac0edd7b47c9be24b1eafe7429c4
88 schema:publisher Ne4e18b979e75421f80da1a17c5257ef3
89 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011965774
90 https://doi.org/10.1007/978-3-540-70583-3_51
91 schema:sdDatePublished 2022-01-01T19:19
92 schema:sdLicense https://scigraph.springernature.com/explorer/license/
93 schema:sdPublisher N1985c19ad36847028089571362620ff8
94 schema:url https://doi.org/10.1007/978-3-540-70583-3_51
95 sgo:license sg:explorer/license/
96 sgo:sdDataset chapters
97 rdf:type schema:Chapter
98 N132a04eb924348019831e2feceaecf66 schema:familyName Damgård
99 schema:givenName Ivan
100 rdf:type schema:Person
101 N1985c19ad36847028089571362620ff8 schema:name Springer Nature - SN SciGraph project
102 rdf:type schema:Organization
103 N5bc5f30f26784076994661f2da6c4e45 rdf:first N74ff0a8f94584911941f9d02748c618c
104 rdf:rest Nb4933ccebdac46fb931afb0a4ca907a7
105 N5f1a1bd8df1f4c9281c777ac67bf6bbc schema:name doi
106 schema:value 10.1007/978-3-540-70583-3_51
107 rdf:type schema:PropertyValue
108 N6bbd963971cc4bf9aa36504fbbaef68e schema:isbn 978-3-540-70582-6
109 978-3-540-70583-3
110 schema:name Automata, Languages and Programming
111 rdf:type schema:Book
112 N74ff0a8f94584911941f9d02748c618c schema:familyName Aceto
113 schema:givenName Luca
114 rdf:type schema:Person
115 N7ace5054746940b2985ae87127e601b3 rdf:first sg:person.014670455446.79
116 rdf:rest rdf:nil
117 N8ca894c579394b83b1aada91709316eb rdf:first Na6d800a737b449b283852ebade598b5a
118 rdf:rest Nfc1263d16b324df48b9746302fe2b019
119 N9ea55b60ad86487498304ef5f19e810b rdf:first sg:person.016423726453.97
120 rdf:rest N7ace5054746940b2985ae87127e601b3
121 Na6d800a737b449b283852ebade598b5a schema:familyName Ingólfsdóttir
122 schema:givenName Anna
123 rdf:type schema:Person
124 Nb4933ccebdac46fb931afb0a4ca907a7 rdf:first N132a04eb924348019831e2feceaecf66
125 rdf:rest Nd7a657493e5944eeb9bc19dad70a7713
126 Nbd3c682d19814a1eaed369aa598531e0 schema:familyName Halldórsson
127 schema:givenName Magnús M.
128 rdf:type schema:Person
129 Nc34a60082118492bb3beabb93f8c5efd schema:familyName Goldberg
130 schema:givenName Leslie Ann
131 rdf:type schema:Person
132 Nc5764e798ede452ea349393988c516b4 schema:familyName Walukiewicz
133 schema:givenName Igor
134 rdf:type schema:Person
135 Nd7a657493e5944eeb9bc19dad70a7713 rdf:first Nc34a60082118492bb3beabb93f8c5efd
136 rdf:rest Nfaa7c16bbda946fb8dadedd6945f4001
137 Ne4e18b979e75421f80da1a17c5257ef3 schema:name Springer Nature
138 rdf:type schema:Organisation
139 Nf11aac0edd7b47c9be24b1eafe7429c4 schema:name dimensions_id
140 schema:value pub.1011965774
141 rdf:type schema:PropertyValue
142 Nfaa7c16bbda946fb8dadedd6945f4001 rdf:first Nbd3c682d19814a1eaed369aa598531e0
143 rdf:rest N8ca894c579394b83b1aada91709316eb
144 Nfc1263d16b324df48b9746302fe2b019 rdf:first Nc5764e798ede452ea349393988c516b4
145 rdf:rest rdf:nil
146 Nfe859ac13d3a4f3a8d7d2d31d5446fe6 rdf:first sg:person.07776170271.83
147 rdf:rest N9ea55b60ad86487498304ef5f19e810b
148 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
149 schema:name Information and Computing Sciences
150 rdf:type schema:DefinedTerm
151 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
152 schema:name Data Format
153 rdf:type schema:DefinedTerm
154 sg:person.014670455446.79 schema:affiliation grid-institutes:grid.419815.0
155 schema:familyName Wieder
156 schema:givenName Udi
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014670455446.79
158 rdf:type schema:Person
159 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
160 schema:familyName Segev
161 schema:givenName Gil
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
163 rdf:type schema:Person
164 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
165 schema:familyName Naor
166 schema:givenName Moni
167 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
168 rdf:type schema:Person
169 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
170 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
171 rdf:type schema:Organization
172 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, Silicon Valley Campus, 1065 La Avenida, Mountain View, CA 94043
173 schema:name Microsoft Research, Silicon Valley Campus, 1065 La Avenida, Mountain View, CA 94043
174 rdf:type schema:Organization
 




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


...