[go: up one dir, main page]

Franceschini et al., 2003 - Google Patents

Optimal cache-oblivious implicit dictionaries

Franceschini et al., 2003

View PDF
Document ID
7735546793607326572
Author
Franceschini G
Grossi R
Publication year
Publication venue
International Colloquium on Automata, Languages, and Programming

External Links

Snippet

We consider the issues of implicitness and cache-obliviousness in the classical dictionary problem for n distinct keys over an unbounded and ordered universe. One finding in this paper is that of closing the longstanding open problem about the existence of an optimal …
Continue reading at pages.di.unipi.it (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G06F17/30625—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30067—File systems; File servers
    • G06F17/30129—Details of further file system functionalities
    • G06F17/3015—Redundancy elimination performed by the file system
    • G06F17/30156—De-duplication implemented within the file system, e.g. based on file segments
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30861—Retrieval from the Internet, e.g. browsers
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
EP1866775B1 (en) Method for indexing in a reduced-redundancy storage system
US8356021B2 (en) Method and apparatus for indexing in a reduced-redundancy storage system
Arge et al. Cache-oblivious priority queue and graph algorithm applications
Demaine Cache-oblivious algorithms and data structures
Kumar et al. Improved algorithms and data structures for solving graph problems in external memory
EP0772836B1 (en) A method for storing and retrieving data and a memory arrangement
Han Deterministic sorting in O (n log log n) time and linear space
US6115716A (en) Method for implementing an associative memory based on a digital trie structure
US6505206B1 (en) Method for implementing an associative memory based on a digital trie structure
US6499032B1 (en) Method for implementing an associative memory based on a digital trie structure
EP0970430A1 (en) Method for implementing an associative memory based on a digital trie structure
Kärkkäinen et al. Engineering a lightweight external memory suffix array construction algorithm
Blandford et al. An experimental analysis of a compact graph representation
Franceschini et al. Optimal worst-case operations for implicit cache-oblivious search trees
Han Improved fast integer sorting in linear space
Franceschini et al. Radix sorting with no extra space
Pibiri et al. Dynamic elias-fano representation
Franceschini et al. Optimal cache-oblivious implicit dictionaries
Kapoor et al. New techniques for exact and approximate dynamic closest-point problems
Katajainen et al. In-place sorting with fewer moves
Dietz et al. A constant update time finger search tree
Franceschini et al. Implicit B-trees: New results for the dictionary problem
Franceschini et al. Implicit dictionaries supporting searches and amortized updates in O (log n log log n) time
Chowdhury et al. External-memory exact and approximate all-pairs shortest-paths in undirected graphs
Franceschini et al. Optimal implicit dictionaries over unbounded universes