The complexity of hashing with lazy deletion View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1986-11

AUTHORS

Christopher J. Van Wyk, Jeffrey Scott Vitter

ABSTRACT

We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork. More... »

PAGES

17-29

Journal

TITLE

Algorithmica

ISSUE

1-4

VOLUME

1

Author Affiliations

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/1701", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Psychology and Cognitive Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "name": [
            "AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Van Wyk", 
        "givenName": "Christopher J.", 
        "id": "sg:person.014132034275.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014132034275.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Brown University", 
          "id": "https://www.grid.ac/institutes/grid.40263.33", 
          "name": [
            "Department of Computer Science, Brown University, 02912, Providence, RI, USA"
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1109/dac.1983.1585739", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086248715"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1986-11", 
    "datePublishedReg": "1986-11-01", 
    "description": "We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf01840434", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "The complexity of hashing with lazy deletion", 
    "pagination": "17-29", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d6cbf3a4f8091f1dd92a69fdecd2617d599ab00c0b1d36074a84749aeb7b0a7f"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01840434"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045093830"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01840434", 
      "https://app.dimensions.ai/details/publication/pub.1045093830"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T11:04", 
    "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/0000000352_0000000352/records_60367_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007/BF01840434"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

73 TRIPLES      21 PREDICATES      28 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01840434 schema:about anzsrc-for:17
2 anzsrc-for:1701
3 schema:author N85c07ed3bacd459ead62f7c1fe8652ad
4 schema:citation https://doi.org/10.1109/dac.1983.1585739
5 schema:datePublished 1986-11
6 schema:datePublishedReg 1986-11-01
7 schema:description We examine a version of the dynamic dictionary problem in which stored items have expiration times and can be removed from the dictionary once they have expired. We show that under several reasonable assumptions about the distribution of the items, hashing with lazy deletion uses little more space than methods that use eager deletion. The simple algorithm suggested by this observation was used in a program for analyzing integrated circuit artwork.
8 schema:genre research_article
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N23d86121dc014ad6bc42ae9a47fded35
12 N83b884f11d8b4e059acb4806b8f6fa47
13 sg:journal.1047644
14 schema:name The complexity of hashing with lazy deletion
15 schema:pagination 17-29
16 schema:productId N254ca383144346b082dcc8ab0560d69f
17 N2d18c5e8a51e48ab870f5e12338be402
18 Ne573f0d0bb5f4bbea3d5c36c58b3aa38
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045093830
20 https://doi.org/10.1007/bf01840434
21 schema:sdDatePublished 2019-04-11T11:04
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher N748549fc102b4c059a82e63e9803c6cc
24 schema:url http://link.springer.com/10.1007/BF01840434
25 sgo:license sg:explorer/license/
26 sgo:sdDataset articles
27 rdf:type schema:ScholarlyArticle
28 N23d86121dc014ad6bc42ae9a47fded35 schema:issueNumber 1-4
29 rdf:type schema:PublicationIssue
30 N254ca383144346b082dcc8ab0560d69f schema:name dimensions_id
31 schema:value pub.1045093830
32 rdf:type schema:PropertyValue
33 N2d18c5e8a51e48ab870f5e12338be402 schema:name readcube_id
34 schema:value d6cbf3a4f8091f1dd92a69fdecd2617d599ab00c0b1d36074a84749aeb7b0a7f
35 rdf:type schema:PropertyValue
36 N748549fc102b4c059a82e63e9803c6cc schema:name Springer Nature - SN SciGraph project
37 rdf:type schema:Organization
38 N82be151e40044153af86600e953aa3c2 schema:name AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA
39 rdf:type schema:Organization
40 N83b884f11d8b4e059acb4806b8f6fa47 schema:volumeNumber 1
41 rdf:type schema:PublicationVolume
42 N85c07ed3bacd459ead62f7c1fe8652ad rdf:first sg:person.014132034275.24
43 rdf:rest Na29e5ef3db724fe28223516081626f8f
44 Na29e5ef3db724fe28223516081626f8f rdf:first sg:person.0613677314.28
45 rdf:rest rdf:nil
46 Ne573f0d0bb5f4bbea3d5c36c58b3aa38 schema:name doi
47 schema:value 10.1007/bf01840434
48 rdf:type schema:PropertyValue
49 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
50 schema:name Psychology and Cognitive Sciences
51 rdf:type schema:DefinedTerm
52 anzsrc-for:1701 schema:inDefinedTermSet anzsrc-for:
53 schema:name Psychology
54 rdf:type schema:DefinedTerm
55 sg:journal.1047644 schema:issn 0178-4617
56 1432-0541
57 schema:name Algorithmica
58 rdf:type schema:Periodical
59 sg:person.014132034275.24 schema:affiliation N82be151e40044153af86600e953aa3c2
60 schema:familyName Van Wyk
61 schema:givenName Christopher J.
62 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014132034275.24
63 rdf:type schema:Person
64 sg:person.0613677314.28 schema:affiliation https://www.grid.ac/institutes/grid.40263.33
65 schema:familyName Vitter
66 schema:givenName Jeffrey Scott
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0613677314.28
68 rdf:type schema:Person
69 https://doi.org/10.1109/dac.1983.1585739 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086248715
70 rdf:type schema:CreativeWork
71 https://www.grid.ac/institutes/grid.40263.33 schema:alternateName Brown University
72 schema:name Department of Computer Science, Brown University, 02912, Providence, RI, USA
73 rdf:type schema:Organization
 




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


...