Nothing Special   »   [go: up one dir, main page]

Liu et al., 2020 - Google Patents

Succinct filters for sets of unknown sizes

Liu et al., 2020

View PDF
Document ID
18428755581106039770
Author
Liu M
Yin Y
Yu H
Publication year
Publication venue
arXiv preprint arXiv:2004.12465

External Links

Snippet

The membership problem asks to maintain a set $ S\subseteq [u] $, supporting insertions and membership queries, ie, testing if a given element is in the set. A data structure that computes exact answers is called a dictionary. When a (small) false positive rate $\epsilon …
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/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/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/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
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/22—Indexing scheme relating to groups G06F7/22 - G06F7/36
    • G06F2207/226—Priority queue, i.e. 1 word in, 1 word out sorter; Output word, i.e. min or max of words in memory
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering

Similar Documents

Publication Publication Date Title
Liu et al. Succinct filters for sets of unknown sizes
US10503716B2 (en) Systems and methods for generating bit matrices for hash functions using fast filtering
Hagerup et al. Deterministic dictionaries
US9223720B2 (en) Systems and methods for rapidly generating suitable pairs of hash functions
Belazzougui et al. Monotone minimal perfect hashing: searching a sorted table with O (1) accesses
US7827218B1 (en) Deterministic lookup using hashed key in a multi-stride compressed trie structure
Raman et al. Succinct dynamic data structures
JP5265378B2 (en) Method and apparatus for high performance regular expression pattern matching
US9244857B2 (en) Systems and methods for implementing low-latency lookup circuits using multiple hash functions
US10489403B2 (en) Embracing and exploiting data skew during a join or groupby
US20150121035A1 (en) Systems and Methods for Implementing Low-Latency Lookup Circuits Using Sparse Hash Functions
CN106326475B (en) Efficient static hash table implementation method and system
US20060184556A1 (en) Compression algorithm for generating compressed databases
US9292554B2 (en) Thin database indexing
Ružić Constructing efficient dictionaries in close to sorting time
Bender et al. Tiny pointers
Nekrich Orthogonal range searching in linear and almost-linear space
Hemenway Falk et al. Alibi: A flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution
Amarilli et al. Dynamic membership for regular languages
Kirsch et al. Simple summaries for hashing with choices
Prezza In-place sparse suffix sorting
Bercea et al. Dynamic dictionaries for multisets and counting filters with constant time operations
US9292553B2 (en) Queries for thin database indexing
Liben-Nowell et al. Finding longest increasing and common subsequences in streaming data
KR20210028576A (en) Network Key Value Indexing Design