Questions tagged [ds.data-structures]

Properties and applications of data structures, such as space lower bounds, or time complexity of insertion and deletion of objects.

Filter by
Sorted by
Tagged with
13
votes
0answers
403 views

Exact nearest neighbor in $d$-dimensional Euclidean space

Suppose that we have $n$ points in $d$-dimensional Euclidean space $\mathbb{R}^d$. We wish to solve the standard exact nearest neighbor problem: build a data structure such that on any query $q\in \...
19
votes
2answers
1k views

A data structure for minimum dot product queries

Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of ...
27
votes
2answers
3k views

I dreamt of a data structure, does it exist?

I haven't managed to find this data structure, but I'm not an expert in the field. The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is ...
3
votes
0answers
354 views

Connected Components over Graph with “colored” edges.

We have an undirected graph $G(V,E)$. Each edge $e \in E$ is associated with a set $C_{e}\neq \emptyset$ of colors, $C_{e} \subseteq C$. The problem is to find all the colored connected components. ...
2
votes
2answers
147 views

Maintaining multiple field dynamic values

This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with ...
8
votes
2answers
776 views

Finding a subset of a set in a collection of sets

What data structures would you recommend that represent a collections of subsets of $\{1, \dots, n\}$ and support the following operations? $insert(S)$: inserts $S$ in the collection. $query(S)$: ...
2
votes
2answers
148 views

Keyed queues with depth queries and delete

I'm interested in a data structure (let's call it a DMV queue, or DMV for short) over keys (say, strings) with the following operations: empty is a DMV containing no keys. enqueue(q,k) adds the key k ...
11
votes
2answers
365 views

Set data structure for efficient repeated insertions

I'm looking for a space-efficient data structure that holds sets (no repetition) of wordsize elements and supports fast insertion (amortized O(1)). By "space-efficient" I mean, ideally, $n + o(n)$ ...
4
votes
2answers
779 views

Encoding of binary trees as a regular language?

There are many ways of representing binary trees as strings. For example, I could encode a tree as either nil or a pair of trees, such as (nil, ((nil, nil), nil)) ...
32
votes
6answers
7k views

Is there a stable heap?

Is there a priority queue data structure that supports the following operations? Insert(x, p): Add a new record x with priority p StableExtractMin(): Return and delete the record with minimum ...
6
votes
1answer
295 views

Simple and cache-oblivious tries on fixed-length strings

Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory ...
-1
votes
1answer
309 views

Amortized Analysis [closed]

I have two questions. My book: "We must ensure that the total amortized cost of a sequence of operations provides an upper bound on the total actual cost of the sequence. This must hold for all ...
8
votes
0answers
105 views

Rank Queries of Uniformly Drawn Order Statistics

Put a uniform distribution on the integers $\{1,\cdots, M\}$. Draw $N$ samples, and sort them as $x_1 \leq \cdots \leq x_N$. A rank query calculates $rank(j) = \mbox{card} \{ i : x_i \leq x_j \}$ for ...
3
votes
1answer
186 views

Prefix Dictionary Problem in External Memory

I'm interested in an external memory data structure able to support the following operations on variable length binary sequences: (1) Insert such a sequence. (2) Given a query sequence, find the ...
0
votes
1answer
171 views

How do I store data with a query that's a approximated ? [closed]

I'm trying to find a way to store my data with fast access (better than O(n)). My database consists of data (4096 byte strings) that represents some information about some items. The problem is, that ...
10
votes
6answers
776 views

A data structure for sets of trees.

Tries allow for efficient storage of lists of elements. The prefixes are shared so it is space efficient. I am looking for a similar way to efficiently store trees. I would like to be able to check ...
2
votes
0answers
304 views

Simple to implement approximate quantile data structure for a stream of integers?

I'm looking for a simple data structure that will let me compute arbitrary approximate quantiles, within a percent or two error, on a stream of 64-bit integers (think of $n$ as being potentially as ...
11
votes
2answers
3k views

Data structure that allow efficient tag based lookups

I am looking for a highly efficient data structure for storage of data similar to the following. Id Tags Order1 Order2 -------------------------- 1 1,2 1 1 2 2,5 2 3 3 ...
9
votes
2answers
510 views

Does there exist a data structure for quick list manipulation and order queries?

We have a set, $L$, of lists of elements from the set $N = \{ 1, 2, 3, ..., n \}$. Each element from $N$ appears in a single list in $L$. I am looking for a data structure which can perform the ...
7
votes
0answers
146 views

Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?

In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
9
votes
1answer
564 views

Deciding if a wildcard string is completely matched by another wildcard string in a set

Here's a problem that has been bugging me for a while. Let's say a string is a sequence of 1s and 0s, and a wildcard string is a sequence of 1, 0, and ?s. All strings and wildcard strings have the ...
17
votes
0answers
282 views

Sequences with sublogarithmic concat and approximate split

Is there a data structure for representing sequences that supports the operations: concat takes two sequences of size $m$ and $n$ and produces a new sequence of size $m+n$ by joining them in time $o(\...
2
votes
1answer
339 views

Getting started with Hashing for Information retrieval

I recently finished my bachelors and now work on Cross-lingual language search. I want to get started in hashing and see how they are useful in information retrieval. (Yes, I know what hashing is), ...
3
votes
3answers
584 views

A possibly new representation of DAGs

I had an idea for a way of representing DAGs, it's very easy to explain: Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must ...
5
votes
1answer
368 views

a data structure for partial sequences

We have a set of bit sequences of length $L$ with only $K$ known bits and $L-K$ gaps. We want to store them in a data structure in a way that given a new bit sequence $x$ of length $L$, with $L$ known ...
5
votes
1answer
693 views

Array slice reversing data-structure

Given an array of $n$ elements, $A[n]$ consider a data-structure which supports the following operations: You are allowed a one time $\mathcal{O}(n)$ preprocessing step: $\text{Init}(A)$ And the ...
2
votes
0answers
103 views

Does kd-tree search look at more leaves in L1 than in Lmax ?

Dear theorists and experimenters, I find that kd-tree search looks at many more leaves in $L_1$ than in $L_{max}$ ($L_\infty$). Does anyone else see this ? If so, why ? (An $L_1$ simplex of volume 1 ...
14
votes
3answers
1k views

Lower Bounds for Data Structures

Are results known which rule out the existence of "too-good-to-be-true" data structures? For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz ...
12
votes
0answers
319 views

Applications of an access lemma for dynamic forests?

Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
22
votes
6answers
1k views

Analogs of compressed sensing

In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
14
votes
4answers
2k views

Subrange of a Red and Black Tree

While trying to fix a bug in a library, I searched for papers on finding subranges on red and black trees without success. I'm considering a solution using zippers and something similar to the usual ...
8
votes
1answer
365 views

Functional Sparse-Matrix with good performance?

While writing a Petri Net program, I was faced with a choice about data structures to represent the graph. Adjacency lists (i.e. lists enumerating the arcs into and out of individual places or ...
10
votes
2answers
426 views

Limits on lock-free collections?

David Rodríguez - dribeas wrote in a comment on StackOverflow that "Not all collections can be implemented without locks". I'm not sure if this is true, and I can't find proof either way. This ...
2
votes
3answers
324 views

What is the name of this partition-indexed key-value data structure?

Consider a data structure that holds N elements having M partitions each holding N/M elements where M divides N. Each element has a key that satisfies an equivalence relation so as to index into one ...
2
votes
1answer
213 views

Graph nodes preserving changes to the overall graph

I remember reading about a kind of Graph data structure, where every change to the the graph could be preserved. I don't remember exactly neither the name, neither a good description (if it was the ...
1
vote
3answers
386 views

Is there a common mathematical symbology for collections?

Preface: So, it was suggested in 'Programmers' that I ask this over here. I am being asked to define several of my algorithms in mathematical terms to describe my work to a customer. I trying to ...
-4
votes
1answer
847 views

Compact representation of DAG,

Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that: ...
6
votes
1answer
448 views

Searching nodes in semi-splay tree

If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations. My course also says that if you search for a node and the ...
8
votes
2answers
751 views

What is the initialization time of a link-cut tree?

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
2
votes
1answer
206 views

Union/find structure implemented by bitvectors

I'm having trouble understanding a concept in my book which is about finding a good structure to represent a union-find datastructure. Here we define a structure -referred to as collection- $V$ as ...
12
votes
2answers
2k views

Reversing a list using two queues

This question is inspired by an existing question about whether a stack can be simulated using two queues in amortized $O(1)$ time per stack operation. The answer seems to be unknown. Here is a more ...
16
votes
2answers
829 views

Faster join of treap-like data structures with approximately the same size

Given two AVL trees $T_1$ and $T_2$ and a value $t_r$ such that $\forall x \in T_1, \forall y \in T_2, x < t_r < y$, it is easy to construct a new AVL tree containing $t_r$ and the values in $...
6
votes
1answer
323 views

Optimal Self Balancing Trees with Canonical Form?

Are any efficient [O(log n)] self balancing trees that are canonical? By canonical I mean that for any set of data inserted into the tree, inserting it after any permutation results in the same tree. ...
3
votes
1answer
1k views

Why is the “free store” memory called the “heap”? [closed]

Does it have anything to do with the heap data structure, for example the Buddy blocks implementation, or does it only take the literal English meaning of the word (a big pile)? I know heap memory is ...
5
votes
1answer
429 views

Confluently Persistent String Data Structure

I'm looking for a confluentially persistent data structure for a string - so far I'm looking at finger trees. That is, how would I resolve two edits to the same base tree, and would I be able to ...
2
votes
1answer
169 views

Data-structure for functions of independent sets

Suppose I have a graph $G$, with nodes $\{1,2,\ldots,n\}$, subsets of nodes $\{b_1,\ldots,b_k\}$ and functions $\{f_1,\ldots,f_k\}$ where $f_i$ maps independent subsets of $b_i$ to reals. The ...
9
votes
2answers
877 views

What is the optimal data structure for a tree of maps.

I'm looking for a data structure, that is basically a tree of maps, where the map at each node contains some new elements, as well as the elements in its parent node's map. By map here I mean a ...
4
votes
2answers
729 views

What are the prospects of research in database field?

I have been working with database management systems, and would like to focus on research in this very area some day. I was having a look at the various research labs around the world, ...
22
votes
2answers
806 views

Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?

I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ ...
8
votes
3answers
561 views

Proving skip-lists strongly weight-balanced in expectation

Given a skip list of height $n$, what is its expected length, to within a constant (multiplicative) factor? In section 2.2 of Cache-Oblivious B-Trees, Strongly Weight-Balanced Search Trees are ...