Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

Filter by
Sorted by
Tagged with
1
vote
0answers
6 views

How do distributed joins work in a distributed relational database system?

I have been looking around for a few days trying to find a clear and concise description of how, at a technical/implementation level, how distributed joins work, but haven't found much. The best so ...
0
votes
0answers
7 views

Algorithm using a trie while calculating edit distance for fuzzy-string autocomplete matching?

In the paper Efficient Error-tolerant Query Autocompletion by Xiao et al., they state: The existing state-of-the-art solutions to the query autocompletion with edit distance constraints adopt the ...
0
votes
0answers
9 views

Concerning websites that have a search box. how prevalent is the use of the minus sign to exclude a term from the search?

I know that in prehistoric times, Lexis/nexis used the minus sign to exclude terms from a search. Today, google uses the same convention. Is it nearly universal, or more like 50%?
0
votes
1answer
38 views

How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
0
votes
0answers
5 views

how do I store 3D rectangle geometric data in kd-tree and check closeness?

There are a bunch of 3D rectangle and I plan to store them in KD-tree for neighborhood search. How to construct such tree and how to check if two rectangle are next to each other?
0
votes
1answer
29 views

what are good data structure algorithm for fast 3D coordinates search?

I want to form data structure for nearby neighbor search for 3D coordinates. What is the best way to do so?
1
vote
1answer
39 views

Find repeated patterns in a string via lossy compression

Description The task is to identify repeated patterns in a string and do lossy compression of the input string using the found patterns. The output is a list containing different ways of encoding the ...
1
vote
0answers
44 views

Algorithm to find maximum sum over weighted overlapping intervals

Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
1
vote
0answers
98 views

Split the given array into K subsets such that maximum sum of all subsets is minimum

Given an array of $N$ elements, $A$, and a number $K$. ($1 \leq K \leq N$) . Partition the given array into $K$ subsets (they must cover all the elements but can be noncontiguous too). The maximum ...
1
vote
1answer
42 views

Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
4
votes
0answers
70 views

Searching a bitonic array with roughly $2\log n$ comparisons

I don't know how to search a bitonic array with roughly $2\log n$ comparisons in the worst case. What I am trying now is to find the maximum integer using roughly $\log n$ comparisons (binary search) —...
1
vote
1answer
22 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
0
votes
1answer
176 views

True/False: If v is a leaf in every spanning tree resulting from DFS(s), then v is a leaf in every spanning tree resulting from BFS(s)

Let $G = (V,E)$ be a connected undirected graph. Let $s \in V$ be a vertex in the graph. True/False: If $v$ is a leaf in every spanning tree resulting from DFS(s), then $v$ is a leaf in every spanning ...
0
votes
0answers
27 views

Data structure for incremental KNN (IKNN) search over high-dimensional vectors

I have a database $D$ of n-dimensional numerical vectors, and I want to do an incremental KNN (IKNN) search over the vectors in $D$. More precisely, given a query vector $v_q \in D$ I need to find $k$ ...
2
votes
0answers
45 views

Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
4
votes
0answers
66 views

How do search engines implement fuzzy search?

Googling "large horse walks into house" also returns results that contain "large horse in a house" and "the house has large horses". How is Google able to return near-...
0
votes
0answers
35 views

In a connected graph, determine all nodes reachable with a "edge-simple" path from node A to node B

I'm asked to write an algorithm which determine all points which appear in a "edge-simple" path connecting node A and node B, i-e a path which doesn't go 2 times in the same edge, but it can ...
0
votes
0answers
134 views

Number of shortest paths between two nodes in undirected unweighted graph

I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't $O(|V| ...
1
vote
1answer
22 views

Is the first distance that gets assigned to a node in BFS always the shortest distance?

Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$. I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct ...
1
vote
1answer
45 views

Algorithm to find the path with minimum bending points on a square grid board

Let's suppose we have a square grid board like the one shown in the picture below: I'm wondering how I can find the path with minimum number of "bending" points (like the ones shown in red) ...
0
votes
0answers
23 views

Finding matches between an input string and a fixed set of strings

I need to compare an input string to multiple strings which I'll refer to as fixed strings, and you can assume the latter won't change. Comparison disregards letters with special characters, only ...
0
votes
0answers
50 views

Finding the Solution out of N possibilities

Suppose there are 10 (4x4) matrices, where the elements in each matrix are dependent on one variable ($\theta$) non-linearly. All the matrices are independent of each other, so there are 10 $\theta$s (...
0
votes
1answer
22 views

In RBFS, why should expanded nodes inherit F-value of their parent, if their f-value (g(n)+h(n)) is less than their parent's F-value

Here https://uk.wikipedia.org/wiki/RBFS and here https://www.eecs.yorku.ca/course_archive/2013-14/F/3401/slides/15b-RBFS.pdf it's said that f[s] ← max(g(s)+h(s) , f[node] ) Why is it so? I can see a ...
1
vote
0answers
18 views

Does this Hamming-like algorithm for solving a permutation of an address space have a name?

I'm working on reverse engineering the bit stream format of an FPGA, in particular regarding the address translation of the BRAM (block RAM), but the algorithm could in general be used for any ...
0
votes
1answer
40 views

Search algorithm for an expensive boolean function

I have the following problem. We have a boolean function $f$ that is expensive to compute for a given input. We need to find the smallest positive integer $n$ such that $f(n)$ is true. We don't know ...
2
votes
1answer
60 views

array empty cell search algorithm

I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid. Here is my scenario: Consider an empty array named ...
1
vote
1answer
40 views

How to search all possible combinations for a product?

I'm looking for the name of the problem stated below or, if available, even the algorithm to solve it. This is a hypothetical idea of mine, I don't actually have the necessary data to implement it. ...
0
votes
1answer
39 views

Best algorithm for Decisional 4-XOR problem?

Decisional 4-XOR Problem: Assume $M>>n$ (e.g. $M=50n$ ). Let $A_1,A_2,A_3,A_4$ be sets consisting of $M$-bit elements. Each set has order exactly $2^n$. Decide whether or not there exists $a_i \...
1
vote
2answers
51 views

Difference Between k-center and k-mean/median

I know that k-mean/median is to find a set $F$ that minimize $$\sum_{i\in C}\min_{j \in F} d(i,j)$$ Where $C$ is set of clients and $F$ set of facilities. (For k-mean you just square the distance). ...
4
votes
0answers
38 views

Using graph symmetries to speed up subgraph enumeration

I have an undirected graph $G$. It has some symmetries in the sense that I know it's automorphism group $\text{Aut}(G)$. I am searching for a specific subgraph defined by some constraints $\phi$ and ...
1
vote
1answer
34 views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

I want to develop LRU key-value data store and in that wanted to get rid of space to store the key itself. Instead wanted to store a 128 bit murmur hash. The structure of data-store that I want to ...
0
votes
0answers
13 views

SMA*+: What if a removed node gets re-generated via another predecessor?

One last question came to me while reading the paper on SMA*+ about setting the $f$-cost of nodes being re-generated. Well, first, it looks like the part of the algorithm where we set the predecessor ...
2
votes
0answers
19 views

SMA*+: Usefulness of culling heuristics

The paper on SMA*+ proposes a very interesting idea of having a culling heuristic different from the full path cost estimation (so called $f$-cost). In the benchmark they use a culling heuristic equal ...
2
votes
0answers
19 views

SMA*+: f-cost estimation of re-generated nodes

I was reading the paper on SMA*+, which is very interesting as it implements most improvements I thought of when reading the paper on SMA*. But I have 3 questions that I think are related to my ...
1
vote
1answer
27 views

Is this a good way to arrange data in a tree?

I was recently learning about Binary Search Trees(BSTs) and thought it could be made even more efficient by making some changes. As binary search trees have numbers greater than the root node on the ...
0
votes
0answers
56 views

Create a data structure with D-SUCCESSOR running in $O(1)$

Given an integer $d$, I need to devise a data structure $S$ with the following actions: BUILD(S): build the data structure $S$ from $n$ elements in $\Theta(n\lg{n})$ INSERT(S, k): insert a new ...
3
votes
0answers
98 views

Remove a subsequence from a string and append it at the end

Consider the following operation on strings: pick a (not necessarily contiguous) subsequence, remove it and then append all the characters in the same order at the end. This operation preserves the ...
0
votes
1answer
39 views

Finding 2 nodes which sum equals twice their common ancestor in RBT in $\Theta(n\lg n)$

I have a red black tree, $T$, and I need to write an algorithm to find 2 nodes $x$ and $y$ so that $key[x] + key[y] = 2 \cdot key[p(x, y)]$, where $p(x, y)$ is the lowest common ancestor of $x$ and $y$...
0
votes
1answer
42 views

List the lengths of all the prefix-suffixes in $O(n^{1+\epsilon})$ time

A proper prefix of a string $s$ that is also equal to a suffix of $s$ is called a PS (prefix-suffix). Given a string $s$ of length $n$ is there an algorithm listing the lengths of all the PSs in $O(n^{...
1
vote
1answer
99 views

Parallel algorithm for finding the maximum in $O(\log \log n)$ time

With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is: If $...
1
vote
0answers
30 views

A beginner's question on programs that can search and calculate in very large sets

I am not in the computer science field and was looking for some guidance on books/papers/programs that allow me to learn how to design algorithms for problems that involve very large number of ...
0
votes
0answers
34 views

How to efficiently search a list of data structures with filtering support

I'm working on a project where I need to create search functionality that can efficiently search a list of data structures like: ...
0
votes
1answer
384 views

Average time complexity of linear search

It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear). I have read ...
1
vote
1answer
97 views

How to do binary search on a path in a binary heap

I am trying to solve this question: Let's say you have a binary heap and an index $i$, design an algorithm that finds if a number $x$ appears in the path between the root of the heap and $heap[i]$ in ...
1
vote
1answer
80 views

How do I solve a search problem on an infinite graph?

I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \...
1
vote
1answer
53 views

Is there a theorem that says when an array of numbers can be searched faster than linearly?

I'm familiar with binary search, but I'm interested in when a collection of numbers can be searched faster than checking them all one by one with any algorithm. Binary search requires sorting to work, ...
1
vote
2answers
106 views

Should your heuristic for an A* search algorithm be the same scale as your actual weights?

I'm a bit confused about the scale of heuristics for implementing A* search. $f(n)$ is the total cost of travelling to a node $n$. It is calculated by $f(n) = g(n) + h(n)$. $g(n)$ is the cost of the ...
-1
votes
1answer
21 views

A very simple question about Admissible Heurisitcs

Given admissible heuristics f(s), g(s), h(s). It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
1
vote
0answers
21 views

Searching for the underyling affine transformation in a ridge function

Quoting from Wikipedia: A ridge function is any function $f:\mathbb{R}^d\rightarrow\mathbb{R}$ that can be written as the composition of a univariate function with an affine transformation, that is: $...

1
2 3 4 5
13