[go: up one dir, main page]

Orlandic et al., 1988 - Google Patents

Compact 0-complete trees: a new method for searching large files

Orlandic et al., 1988

View PDF
Document ID
15811515743335352878
Author
Orlandic R
Pfaltz J
Publication year

External Links

Snippet

In this report, a novel approach to ordered retrieval in very large files is developed. The method employs a B-tree like search algorithm that is independent of key type or key length because all keys in index blocks are encoded by a 1 byte surrogate. The replacement of …
Continue reading at www.osti.gov (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/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
    • G06F17/3033—Hash tables
    • 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/30949—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures hash tables
    • 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
    • G06F17/30327—Trees, e.g. B+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/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/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing 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/30067—File systems; File servers
    • G06F17/30091—File storage and access 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/3074—Audio data retrieval
    • G06F17/30778—Audio database index structures and management thereof
    • 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
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • 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

Similar Documents

Publication Publication Date Title
Whang et al. The Multilevel Grid File-A Dynamic Hierarchical Multidimensional File Structure.
US5930805A (en) Storage and retrieval of ordered sets of keys in a compact 0-complete tree
US5263160A (en) Augmented doubly-linked list search and management method for a system having data stored in a list of data elements in memory
US6757675B2 (en) Method and apparatus for indexing document content and content comparison with World Wide Web search service
US5848416A (en) Method and apparatus for storing and retrieving data and a memory arrangement
US5813000A (en) B tree structure and method
EP1866775B1 (en) Method for indexing in a reduced-redundancy storage system
US6427147B1 (en) Deletion of ordered sets of keys in a compact O-complete tree
AU2004225060B2 (en) A computer implemented compact 0-complete tree dynamic storage structure and method of processing stored data
Ferragina et al. Fast string searching in secondary storage: Theoretical developments and experimental results
Franceschini et al. Optimal worst-case operations for implicit cache-oblivious search trees
Lee et al. A Partitioned Signature File Structure for Multiattribute and Text Retrieval.
US8156126B2 (en) Method for the allocation of data on physical media by a file system that eliminates duplicate data
Orlandic et al. Compact 0-Complete Trees.
Orlandic et al. Compact 0-complete trees: a new method for searching large files
Otoo Linearizing the Directory Grovvth in Order Preserving Extendible Hashing
Chen On the signature trees and balanced signature trees
CN118535539B (en) A data deduplication method and filter
Orlandic et al. Analysis of compact 0-complete trees: A new access method to large databases
Vankreveld et al. Concatenable structures for decomposable problems
Ahn Filtered hashing
Bell et al. Hash trees versus B-trees
Masud et al. A hashing technique using separate binary tree
Krishnamurthy The Multilevel Grid File-A Dynamic Hierarchical Multidimensional File Structure Kyu-Young Whang Center for Artificial Intelligence Research and Computer Science Department Korea Advanced Institute of Science and Technology PO Box 150 Cheong-Ryang Ni, Seoul, Korea
Franceschini et al. Optimal implicit and cache-oblivious dictionaries over unbounded universes