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.
354
questions
1
vote
0
answers
44
views
Practical worst-case polylogarithmic dynamic orthogonal range queries?
There are a number of data structures in the literature that solve the dynamic orthogonal range search problem in polylogarithmic time (say, range trees). My understanding is that these structures ...
1
vote
0
answers
44
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 ...
1
vote
0
answers
80
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 ...
1
vote
0
answers
67
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 ...
1
vote
0
answers
144
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 ...
1
vote
0
answers
64
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 ...
1
vote
0
answers
79
views
Best Asymptotic Complexity for Persistent Union Find
In this paper https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf, they claim to have a practically fast persistent union-find data structure for most use-cases, but it's still not polylogarithmic ...
1
vote
0
answers
99
views
What is the name of this data structure? (hash table with a limit on the number of entries)
Denote $[n] \triangleq \{1,2,\ldots,n\}$.
Assume we would like to have a data structure $S$ which kinda works as a dictionary from $[k]$ to $[v]$, and supports add/remove/update/query functionality, ...
1
vote
0
answers
57
views
What should I read to learn about the different models of computation used in algorithm and especially data structure analysis?
Are there any good surveys? Courses? Lecture notes?
I'm especially interested in material with practice exercises, if any is available.
Thanks!
1
vote
0
answers
107
views
What are some examples where the Catalan numbers show up in algorithms/data structures?
For some variants of RMQ data structures, the number of Cartesian trees (i.e. the Catalan numbers) is a part of the running-time analysis. What are some other examples where the Cataln numbers show up ...
1
vote
0
answers
111
views
Binary Search Tree DELETE survey
In helping out @bapi-chatterjee on a BST question , when it came to teasing out the combinatorics of BST_DELETE(i) I ran into a wall where even under the conservative assumption that the parent tree ...
1
vote
0
answers
96
views
Linear time algorithm for computing the labels of leaves in a recursively defined tree [closed]
The original copy of the question on MSE.
Let $S=(s_0, ..., s_{N-1})$ be a sequence of $N=2^p$ numbers. We consider a labelled binary tree of height $p$ as follows:
The root has label $S$,
for each ...
1
vote
0
answers
103
views
What effect would using different types of orders have on a binary search tree?
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
0
votes
1
answer
999
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 ...
0
votes
1
answer
104
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 ...
0
votes
1
answer
2k
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, ...
0
votes
1
answer
176
views
Combining multiple time-based datasources with different periods
I have two time-based data sources (one providing data by month and the other by week) that must be combined to create a third daily source (recognizing that at best we're getting one possible ...
0
votes
3
answers
234
views
Joining lists with some common elements in average case
What are some ways of commutatively combining a pair of lists to produce a list comprised of elements from the pair of inputs, with no duplicates, with time complexity better than $O(n \log(n))$? ...
0
votes
1
answer
172
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 ...
0
votes
1
answer
78
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
1
answer
507
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 ...
0
votes
2
answers
156
views
Mergeable Exact Order Statistics Data Structure
Given $n$ sets of integers $S_1, S_2, \cdots, S_n$, it is guaranteed that
$$
x < y, \text{ for } \forall x \in S_i \text{ and } \forall y \in S_{i+1}
$$
and let's denote this relationship as $S_i &...
0
votes
1
answer
126
views
Formal differences between emulation and simulation?
Recently this question came up, and I've been unable to find a concrete answer.
When I was reading this paper on CRDTs, I was a little perplexed by the notion of emulation here in theorems 3.1 and 3.2....
0
votes
1
answer
201
views
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Let $n$ be a large positive integer. Given a collection $\mathfrak S$ of subsets of $[n] := \{1,2,\ldots,n\}$, and a vector $z=(z_1,\ldots,z_n)\in \{\pm 1\}^n$, define
$$
f_{\mathfrak S}(z) := \sum_{\...
0
votes
1
answer
58
views
How to build the tree with the "most different" solutions of a clustering?
Illustrate the question with an example : we have a similarity matrix for 1000 people, and the similarity represents how much their hobbies are the same (it does not really matter how it's built).
Let'...
0
votes
1
answer
397
views
Graphs-like data structure with weighted vertices
I am searching for literature related to a graph-like data structure where vertices are weighted instead of edges.
Formally, we can define a weighted-(edge)-graph $G=(V,E, w(\cdot))$ as a tuple of ...
0
votes
1
answer
309
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 ...
0
votes
1
answer
194
views
Data structure that allows moving groups of elements into buckets
I'm looking for a data structure that can do the following geometric operation:
Suppose there are a set of buckets $b_0, b_1..., b_n$ each of which contains some elements. Suppose I want to move all ...
0
votes
0
answers
52
views
Data structure for storing set of sets
Let key space $K_n =$ { $1, 2,...,n$ }
Let Data Structure $D$ implementing a set $S$ of sets such that
All sets in $S$ are of same size $l$, $1 \le l \le n$
All sets in $S$ contain keys belonging to $...
0
votes
0
answers
51
views
Deamortization of basic COLA (Cache oblivious lookahead array)
I am reading the paper titled Cache Oblivious Streaming B-trees. I am trying to understand the deamortization technique used for basic COLA.
The paper says that for every level k, for deamortization, ...
0
votes
0
answers
62
views
kd-tree optimality for orthogonal range search
It is known that a kd-tree can be constructed for $n$ points ($k$-dimensional) in $O(n \log n)$ time and searching of any axis-aligned hyperrectangle can be done in time $O(n^{1-1/k} + out)$ time ...
0
votes
0
answers
46
views
Speed networking algorithm
I have 40 people and 10 tables that can accommodate 4 people at a time. The task is to make sure that every person seats with every other person at the same table exactly once, that is every person ...
0
votes
0
answers
71
views
Are there data structures that cannot be serialized / deserialized using a context free grammar?
I understand that deserializing data from a string or binary stream into a data structure is effectively the same parsing. When you deserialize the input string, you use a grammar to create a parse ...
0
votes
0
answers
48
views
What Data Structure storing points in space for fast lookup of stored points "near" a query point?
In NLP a common problem is that you have vector embeddings of large vocabularies, and you do manipulations on these vector embeddings to compute some result vector, and then you want to find which ...
0
votes
0
answers
81
views
How does laziness help functional data structure?
Functional data structures, or immutable data structures, are often achieved by copying old data to new data upon operation. Naively, it looks much less efficient than their imperical counterpart. ...
0
votes
0
answers
45
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
0
answers
47
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 \...
0
votes
0
answers
43
views
Equilvalence among two Scheduling problems
I have two problems for scheduling:
Packets arrive at a router. Router schedules them i.e. router determines which one will go out first and which one last. Here, the problem is which packet to send ...
0
votes
0
answers
38
views
Self-Aggregating Tree
Say I have a finite $n$-ary tree where each node contains state. For the sake of argument, let's say a key-value store. If we are interested in the aggregation of some key(s) at some node, then we ...
0
votes
0
answers
75
views
On a property of random rooted trees with $n$ nodes and of height $h$
I am working on a proof that require the result of the following problem:
Let, $T$ be a rooted directed tree with height $h (\ge \lceil{log_d{n}}\rceil )$ and having $n$ nodes. Each internal node of $...
0
votes
0
answers
124
views
Efficient update of the keys in associative container
I need to maintain a set $\langle(k_1, v_1), (k_2, v_2), \dots, (k_N, v_N)\rangle$ of key-value pairs subject to the following update operation. Given two keys $a < b$ and a "shift" value $C$ as ...
0
votes
2
answers
327
views
Is it possible to convert any tree to a B-tree or an R-tree?
I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an ...
0
votes
1
answer
677
views
Is the running time of Boyer-Moore linear?
With pattern length $M$, text length $N$, and alphabet $\Sigma$,
is the asymptotic running-time of Boyer-Moore $O(N/|\Sigma|)$
(even when $M$ grows larger than $|\Sigma|$)?
Are there any sublinear ...
0
votes
1
answer
76
views
How to automatically generate indexes and preaggregations from queries
This question might be a little ill-specified, but the idea I want to explore is:
User writes a bunch of queries that they want to perform over some data (for concreteness, just consider it a read-...
-1
votes
1
answer
359
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 ...
-1
votes
1
answer
219
views
Alternative to binary search trees: A sorted array with empty spaces
There are many data structures that have O(log(n)) insert, delete and find operations: Self balancing binary search trees, skip lists and others. My question is: Why doesn't the following simple thing ...
-2
votes
1
answer
664
views
Fortunes Algorithm - Beach Line Data Structure [closed]
This is a cross-post from stackoverflow. I did not recieve a good answer, I guess it is because the question is more theoretical.
I have to implement Fortunes algorithm for constructing Voronoi ...
-2
votes
1
answer
291
views
Find all items which are subsets of an item
I have a problem that I think should have been studied. I am looking for algorithms for it.
Each item is a set of key-value pairs.
Let $x$ be an item and $F$ be a set of items.
Each key and each ...
-3
votes
1
answer
324
views
Isn't weakly universal hashing even a stronger than truly random? [closed]
So as far as I know the weakly universal hashing is defined as:
for any $x, y \subset U, Pr(h(x) = h(y)) \le \frac{1}{m}$ where m is a smaller number than the cardinality of $U$, and h are chosen ...
-3
votes
1
answer
95
views
tagging and graph “compression”
I have a question on stack-overflow about "compressing" a graph. Suppose I have tags from a finite set $T$ and objects from a finite set $O$. Moreover there are (uni-directional) links from elements ...