[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

Chan et al., 2018 - Google Patents

Selection and sorting in the “restore” model

Chan et al., 2018

Document ID
3317645369419485758
Author
Chan T
Munro J
Raman V
Publication year
Publication venue
ACM Transactions on Algorithms (TALG)

External Links

Snippet

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing thecomputation. Such algorithms are useful for designing space-efficient algorithms, when one encounters subproblems that …
Continue reading at dl.acm.org (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
    • 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/10—Complex mathematical operations
    • G06F17/14—Fourier, Walsh or analogous domain transformations, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms
    • G06F17/141—Discrete Fourier transforms
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • 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
    • H—ELECTRICITY
    • H03—BASIC ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same information or similar information or a subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring

Similar Documents

Publication Publication Date Title
Pagh Low redundancy in static dictionaries with constant query time
Navarro Compact data structures: A practical approach
Wu et al. Optimizing bitmap indices with efficient compression
Barbay et al. Succinct indexes for strings, binary relations and multilabeled trees
Vitter Design and analysis of dynamic Huffman codes
Albers et al. Improved parallel integer sorting without concurrent writing
Chan et al. Selection and sorting in the “restore” model
Van Der Hoeven et al. On the bit-complexity of sparse polynomial and series multiplication
Chan et al. Selection and sorting in the “restore” model
Felner et al. Compressed pattern databases
Boffa et al. A “Learned” Approach to Quicken and Compress Rank/Select Dictionaries∗
Radke The use of quadratic residue research
Baker et al. Efficient quantum circuit decompositions via intermediate qudits
Belazzougui et al. Cache-oblivious peeling of random hypergraphs
Turpin et al. Practical length-limited coding for large alphabets
Prezza In-place sparse suffix sorting
Yu Nearly optimal static Las Vegas succinct dictionary
Poyias et al. Compact dynamic rewritable (CDRW) arrays
Claude et al. Space efficient wavelet tree construction
Chen et al. Using difficulty of prediction to decrease computation: Fast sort, priority queue and convex hull on entropy bounded inputs
Naor String matching with preprocessing of text and pattern
Golin et al. Encoding 2D range maximum queries
Chan Dynamic streaming algorithms for epsilon-kernels
Li et al. The power of the queue
Viola et al. How to store a random walk