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
2
votes
0answers
69 views

Lower bounds for list/set data structures without delete

I'm interested in lower bounds on the amortized time cost for either of the following dynamic data structure problems, in the cell probe or RAM model, or any model that lets us do operations on words ...
6
votes
2answers
2k views

Improving Bloom filter - can we distinguish elements of a database using less than 2.33275 bits/element?

While we usually use large e.g. 64 bit hashes, there are many techniques to reduce this size, e.g. for savings in storage and transmission. Popular Bloom filter instead of marking just 1 hash ...
2
votes
1answer
95 views

Lower bounds on simple hash table operations?

There are a variety of hash tables that support worst-case O(1)-time lookups and deletions and expected O(1)-time lookups. Is there a known lower-bound on hashing that says that there cannot be a hash ...
0
votes
1answer
55 views

Data structure for getting all matches of a prefix from a large list of strings [closed]

Suppose I have a very long list of strings (millions of them), ordered by importance. For example: ... barracudas oftwalj velasp offso skenep vitriolic offscre ... ...
0
votes
0answers
41 views

Updating set of lists dependent upon a few indices

I'm curious about a data structure for a set of "valid lists", where you have a set of lists of length $i$ $S_i$, have a list $L$ of possible items to append, and a boolean function $f$, and wish to ...
0
votes
1answer
120 views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)?

I'm following course material from the course Advanced Data Structures. The result by Driscoll et al 1989 states the following (wording of the following theorem taken from lec notes, page 4, which ...
11
votes
0answers
332 views

A dynamic data structure to list triangles

Consider an undirected graph with $n$ nodes. Is there an efficient data structure that supports the following operations? Insert an edge into the graph Delete an edge from the graph Given a query ...
3
votes
0answers
62 views

Data structure to report points in the intersection of two circles

The circular range reporting is defined as follow: preprocess $n$ points in the plane so that the points inside a query circle, of any radius, can be reported quickly. This was solved beautifully ...
6
votes
1answer
325 views

Algebra and algebraic data types

Which of the well-known structures of modern algebra (monoids, groups, rings etc) can be expressed as algebraic data types (ADTs)? Presumably a free monoid can be considered to be isomorphic to the ...
9
votes
2answers
352 views

Can three stacks be implemented in one array, with O(1) push/pop time?

Two stacks can be efficiently implemented using one fixed sized array: stack #1 starts from the left end and grows to the right, and stack #2 starts from the right end and grows to the left. Is the ...
1
vote
0answers
25 views

Splay trees as dynamic weight-balanced trees?

Given a collection of keys $x_1 < x_2 < \dots < x_n$ with associated weights $w_1, w_2, \dots, w_n$, a weight-balanced tree for the keys $x_i$ with weights $w_i$ is defined as follows: The ...
7
votes
1answer
80 views

Simple proof that splay trees have the dynamic finger property?

Splay trees are conjectured to be dynamically optimal, and they're known to have a number of nice properties, including the dynamic finger property, which says that the amortized cost of an access in ...
4
votes
0answers
74 views

What degree of hash function independence is needed for Bloom filters?

In the traditional analysis of Bloom filters, it's assumed that the hash functions are truly random functions, meaning that each hash function distributes each key uniformly and independently of each ...
8
votes
0answers
1k views

Data structures for Finite Automata

I am a Control Engineer and I have been working on Discrete Event Systems and Supervisory Control, based on Finite Automata Theory. My problem is to represent large automata (about $2 \times 10^6$ ...
3
votes
2answers
97 views

Data structure for radial orderings of points on the plane

Assume points are always in general position. For a set of $n$ points $S$ on the plane, a radial ordering with respect to $x\in S$ is a total ordering of the elements in $S-x$. Consider shooting an ...
0
votes
0answers
43 views

Arranging sets in a hierarchy

Suppose you have sets $S_1, \dots S_m$ such that $\sum_i |S_i| = n$. The goal is to arrange all the sets into a (possible unconnected) DAG such that $S_i$ is a parent (or ancestor) of $S_j$ iff $S_j \...
4
votes
0answers
102 views

Is there a history-independent rope data structure?

I'm experimenting with a toy (functional) programming language. One of my ideas is to aggressively hash cons everything, thus representing any data structure as a single integer. In that context, data ...
0
votes
1answer
157 views

Data Strcuture to represent dependencies amongst modules

Consider several software modules $m_1, m_2, ... m_n$. Each module has some inputs and outputs and the inputs to some of the modules are dependent on the outputs of some other modes. For example, in ...
6
votes
0answers
148 views

Immutable Space Model

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence? What is generally known about models of ...
358
votes
93answers
109k views

Algorithms from the Book.

Paul Erdos talked about the "Book" where God keeps the most elegant proof of each mathematical theorem. This even inspired a book (which I believe is now in its 4th edition): Proofs from the Book. If ...
1
vote
0answers
73 views

Points of a finite set wihtin a ball

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...
3
votes
0answers
51 views

Lower bound for reversing a list using queues

How do you prove (or disprove) that a list of length $n$ cannot be reversed in time $o(n \log n)$ using $O(1)$ queues? Each queue is FIFO. Time refers to the number of operations on the queues. ...
5
votes
2answers
391 views

Data structure to determine if sets are disjoint in o(n) time

My initial question was exactly the title of this post, but after feedback from commenters I have formulated a more precise version of the question that attempts to capture its essence. Does there ...
60
votes
10answers
10k views

One Stack, Two Queues

background Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no ...
5
votes
1answer
108 views

Topology/Space of Recursive Algebraic Datatypes

I have a recursive algebraic datatype. I (somewhat arbitrarily) defined one function to compute distance between instances, and am trying to define a function to approximate a "vector" between ...
67
votes
9answers
13k views

Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication ...
7
votes
2answers
753 views

Random sampling data structure with removal

I'd like a data structure with the following operations: create a new instances from an array of floating point weights. randomly sample, returning an item with probability proportionate to its ...
7
votes
1answer
222 views

How fast can we find and disconnect roots in a forest?

Consider a forest of rooted trees. The problem is to support two operations: disconnect(v): if v is the root of some tree in the forest, remove all edges of v; findroot(v): find root of the tree ...
2
votes
2answers
154 views

Suggested approach to cover data structure literature

I am not sure if this question is odd topic or too broad, but I have been wondering about this for a long time, and I would very much appreciate any valuable inputs. As a new grad student working on ...
17
votes
3answers
785 views

Succinct data structures survey?

Fischer's paper this month reminded me how little I know about the art of succinct data structures, and algorithms to use them. For those that don't know about succinct data structures: Given a ...
10
votes
0answers
150 views

Bloom filter variant for constant-time subset/superset queries

Bloom filters make it easy to determine if an element is in a set, within some acceptable margin of error. I'm looking to solve a related problem for which Bloom filters are inadequate, but for which ...
14
votes
2answers
2k views

What is a zipper, and how does it relate to a tree-like structure?

I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers ...
1
vote
0answers
59 views

\alpha-path on Euclidean graphs

Consider the following problem: Suppose we are given a G=(V, E) Euclidean Graph in the plane and a real $\alpha > 0$. For simplicity assume, there exists only one path whose summation of weights ...
34
votes
3answers
1k views

Comparison-based data structure for finding items

Is there a data structure that takes an unordered array of $n$ items, performs preprocessing in $O(n)$ and answers queries: is there some element $x$ on the list, each query in worst time $O(\log n)$? ...
4
votes
1answer
166 views

What is known about computing distinct count range queries?

Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries. In ...
-1
votes
2answers
5k views

Most efficient algorithm to compute set difference?

What is the most efficient algorithm to compute the difference between two set data structures? In particular, the algorithm should efficiently discover elements in the first set that are also in the ...
3
votes
1answer
731 views

How many ephemeral stacks are required to simulate a queue in worst-case $O(1)$ time?

In "Real Time Queue Operations in Pure LISP" (ML implementation), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be ...
0
votes
1answer
441 views

Data Structure to calculate which interval a point lies in? [closed]

I have a list of $n$ non-overlapping intervals, namely $[a_1,a_2],[a_2,a_3],...,[a_n,n_{n+1}], a_i \in \mathbb{N}$. Each of these intervals has a corresponding value $v_i$ corresponding to it. Now ...
12
votes
2answers
766 views

Data structure for dynamic memory allocation

Think of the cell-probe model. Is there a data structure that can allocate contiguous chunks of memory of any length (like e.g. malloc in C), and free them, while avoiding memory segmentation, and ...
3
votes
1answer
105 views

Sublinear finite-precision sampling in a stream

I am looking to sample a single item from a stream such that each item in the stream has an equal probability of being selected. This is a restricted version of the reservoir sampling problem. On a ...
1
vote
0answers
128 views

Information theoretic lower-bound on object graph serialization

This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
0
votes
1answer
98 views

Reachability in Dynamic Line Graph

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position ...
1
vote
0answers
60 views

What is known about data structures for encoding a set while considering approximate Rank queries?

Consider a universe $\mathcal U\triangleq \{1,2,\ldots n\}$, and assume that we are given a set $S\subseteq \mathcal U$. There are many data structures that allow storing $S$ while answering Rank ...
11
votes
2answers
3k views

Any fast algorithm for minimum cost feedback arc set problem?

In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set. If each edge is associated with a weight $w$, the minimum cost ...
15
votes
0answers
315 views

Set Intersection lower bounds

Consider $S_1, ...,S_n \subseteq [U]$ where size of $U$ is polylogarithmic in $n$. We allow infinite time to pre-process these sets and then ask queries of the form $S_i \cap S_j$ is empty or not. We ...
36
votes
4answers
8k views

Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees?

I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally: It uses O(1) space It can be updated to reflect an insertion or deletion in O(...
-1
votes
1answer
843 views

Reachability on DAG (best-known algorithm)

Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, ...
3
votes
3answers
331 views

Pairwise comparison of bit vectors

Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$. I am interested in the following problem: Given $x_1,\dots,x_n \...
5
votes
4answers
581 views

Purely(ish) functional data structure with fast append and forward iteration

I find I have need for a data structure with a specific set of requirements: It represents an immutable sequence of values (fixed sized integers if this matters) Appending a new value to the end (and ...
4
votes
1answer
163 views

Algorithms in preprocessed universe [closed]

In celebrated paper Clustered integer 3SUM via additive combinatorics by TM Chan and M Lewenstein one of the provided algorithms is the one for preprocessed universe. They were able to provide an ...