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
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 ...
templatetypedef's user avatar
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 ...
templatetypedef's user avatar
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 ...
C.P.'s user avatar
  • 992
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 ...
Armin Mir's user avatar
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 ...
Veksi's user avatar
  • 111
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 ...
R B's user avatar
  • 9,448
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 ...
dspyz's user avatar
  • 916
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, ...
R B's user avatar
  • 9,448
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!
James Shapiro's user avatar
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 ...
James Shapiro's user avatar
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 ...
Chad Brewbaker's user avatar
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 ...
researcher's user avatar
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 ...
DLaw's user avatar
  • 111
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 ...
user3508551's user avatar
  • 1,153
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 ...
fatelasu's user avatar
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, ...
user43464's user avatar
  • 209
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 ...
Jack R-G's user avatar
  • 109
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))$? ...
Harish Kukreja's user avatar
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 ...
Yochai Timmer's user avatar
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 ... ...
Flux's user avatar
  • 109
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 ...
kauray's user avatar
  • 135
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 &...
user avatar
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....
NathanLiitt's user avatar
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_{\...
dohmatob's user avatar
  • 291
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'...
Vincent's user avatar
  • 109
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 ...
karl's user avatar
  • 3
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 ...
Peeyush Kushwaha's user avatar
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 ...
Quanquan Liu's user avatar
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 $...
Yolov4's user avatar
  • 1
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, ...
debasishg's user avatar
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 ...
karmanaut's user avatar
  • 1,177
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 ...
Helen Grey's user avatar
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 ...
bcarlborg's user avatar
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 ...
John_Krampf's user avatar
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. ...
Student's user avatar
  • 127
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 ...
Zach Hunter's user avatar
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 \...
karmanaut's user avatar
  • 1,177
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 ...
ferrer's user avatar
  • 1
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 ...
Xophmeister's user avatar
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 $...
Indranil B's user avatar
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 ...
Nullptr Dev's user avatar
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 ...
user2398029's user avatar
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 ...
daniel pehoushek's user avatar
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-...
Andy's user avatar
  • 1
-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 ...
user avatar
-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 ...
Zur Luria's user avatar
  • 359
-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 ...
Artium's user avatar
  • 97
-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 ...
wroscoe's user avatar
  • 111
-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 ...
Boyu Fang's user avatar
-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 ...
Vasileios Anagnostopoulos's user avatar

1
4 5 6
7
8