Browse Prior Art Database

Method for Caching Ordered Data Without Using Unique Keys

IP.com Disclosure Number: IPCOM000029565D
Original Publication Date: 2004-Jul-07
Included in the Prior Art Database: 2004-Jul-07
Document File: 1 page(s) / 29K

Publishing Venue

IBM

Abstract

The Method for Caching Ordered Data Without Using Unique Keys allows ordered data in a database to be cached in memory and retrieval using any key desired. The hash function for the retrieval keys does not map exactly to the keys in the cache. Rather, the hash function is actually a search function to allow any retrieval key to match a key in the cache.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 1

Method for Caching Ordered Data Without Using Unique Keys

In some database tables the rows use ascending timestamps for primary keys. These timestamps represent when a Data Subject consented to a privacy policy. The timestamps need to retrieved quickly for privacy enforcement decisions but the lookup is done with a timestamp that may not match the moment when the Data Subject consented to the privacy policy. For example, a privacy enforcement decision needs to be made immediately so what privacy policy did the Data Subject consent to most recently? Or when the business sent out a mass mailing two months ago, what privacy policy had the Data Subject's consent at that time? The database table needed to be cached because a row will exist for each time a Data Subject consents to a privacy policy and that can be millions of rows.

The cache assumes there is a FUNCTION that allows keys in the cache to be found using a key that may or may not be in the cache. For example, all possible request timestamps to the correct consent record timestamp by requesting the "closest" timestamp in the table less than the may be matched requested timestamp.

The ordered data is stored in memory as a sorted tree. The data structure for a sorted tree and its benefits are well known so I will not describe them here.

Insertion - There are two cases for the insertion process. The empty cache case and the non-empty cache case.

When the cache is empty and the program requests a record from the database, it is retrieved and added to the cache. The first record acts as a seed for...