[go: up one dir, main page]

Bercea et al., 2020 - Google Patents

A space-efficient dynamic dictionary for multisets with constant time operations

Bercea et al., 2020

View PDF
Document ID
16301996132872968600
Author
Bercea I
Even G
Publication year
Publication venue
arXiv preprint arXiv:2005.02143

External Links

Snippet

We consider the dynamic dictionary problem for multisets. Given an upper bound $ n $ on the total cardinality of the multiset (ie, including multiplicities) at any point in time, the goal is to design a data structure that supports multiplicity queries and allows insertions and …
Continue reading at arxiv.org (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/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/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30964—Querying
    • G06F17/30979—Query processing
    • G06F17/30985—Query processing by using string matching techniques
    • 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/30386—Retrieval requests
    • G06F17/30424—Query processing
    • G06F17/30477—Query execution
    • G06F17/30483—Query execution of query operations
    • G06F17/30486—Unary operations; data partitioning operations
    • 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/30153—Redundancy elimination performed by the file system using compression, e.g. sparse files
    • 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
    • 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

Similar Documents

Publication Publication Date Title
US5487164A (en) Distribution-based replacement selection sorting system
Pagh et al. An optimal Bloom filter replacement.
Raman et al. Succinct dynamic data structures
KR100886189B1 (en) database
US8356021B2 (en) Method and apparatus for indexing in a reduced-redundancy storage system
EP1866775B1 (en) Method for indexing in a reduced-redundancy storage system
US7099881B2 (en) Method for increasing average storage capacity in a bit-mapped tree-based storage engine by using remappable prefix representations and a run-length encoding scheme that defines multi-length fields to compactly store IP prefixes
Mendelson Analysis of extendible hashing
Müller et al. Retrieval and perfect hashing using fingerprinting
US7162481B2 (en) Method for increasing storage capacity in a multi-bit trie-based hardware storage engine by compressing the representation of single-length prefixes
Bercea et al. Dynamic dictionaries for multisets and counting filters with constant time operations
Conway et al. Optimal hashing in external memory
Bercea et al. A dynamic space-efficient filter with constant time operations
CN116795788B (en) Deep learning data set storage and retrieval method and system
Bercea et al. Fully-dynamic space-efficient dictionaries and filters with constant number of memory accesses
CN116382588A (en) LSM-Tree storage engine read amplification problem optimization method based on learning index
Bercea et al. A space-efficient dynamic dictionary for multisets with constant time operations
Bender et al. Modern hashing made simple
Li et al. Dynamic dictionary with subconstant wasted bits per key
US9292553B2 (en) Queries for thin database indexing
Otoo Linearizing the Directory Grovvth in Order Preserving Extendible Hashing
KR100878142B1 (en) Modified 수정 -tree index construction method for efficient operation on flash memory
Bercea et al. An extendable data structure for incremental stable perfect hashing
Pagh Basic external memory data structures
CN114741388A (en) Novel construction method for integrated circuit layout data index