Geek Answers Handbook

Important data structures in the search

I am interested in teaching different data structures, which I know very little now. My plan is to implement several key structures so that I understand how they work. I am looking for suggestions on important data structures to get you started.

First of all, I am interested in data structures that are relevant to search applications (for example, Google / Lucene) and the general compromise between deferred computing and preliminary estimation. I am also interested in distributed data structures - data structures that can scale on hundreds / thousands of servers - and probabilistic data structures - data structures that help you find an approximate answer, but don't have to be correct.

Wikipedia has a list of data structures . I am currently considering:

  • Hash table
  • In + -Tree
  • R-tree
  • KD tree
  • Radix tree
  • Color filter

Are there any better options?

Finally, is there a (main) problem with implementing these structures in a language such as F #?

+7
data-structures search f #
source share
4 answers

Very ambitious. I voted for your question only for its volume.

MIT has online algorithms and data structure structures . companion book is a classic. I'm not sure if this applies to distributed and probabilistic functions, but they will give you an excellent rationale for the basics.

I would add red-black wood, hash tables, patricia trie and skip lists on your agenda.

Good luck.

+5
source share

For searching, algorithms are more important than data structures. When searching in a large search space, you often have to have sophisticated methods to trim your search space.

You can look at the classic search algorithms such as alpha beta, A *, AO *.

Then look at something like an iteratively deepening search.

In search algorithms, things like stacks and linked lists (which really are a stack) and trees are more important than hash tables, B-trees, etc. Of course, you will undoubtedly have hash tables there, but this will not be the basis of the algorithm.

Here is another important search algorithm:

  • B * search
  • returns
  • Beam search
  • best search
  • bidirectional search
  • climbing search
  • simulated annealing
  • IDA *
  • Iterative in-depth depth search
  • search mini max
  • search for the nearest neighbor
  • distribution activation
  • search for the state of space (not a method, just a way to conceptualize the problem).

As for the specific data structures for the search, you really don't need it. Basically, you just need your usual set of data tools - trees, hashes, lists.

+3
source share

If you intend to do this using a functional language, you should take a look at the purely functional data structures of Chris Okasaki. Key lesson: Data structures that you are familiar with for imperative programming may not be the best choice for functional programming. I expect there will be many similar materials for Googled for.

+3
source share

Since you have very little knowledge of DS, I think you should start with lists (Single and Double Linked Lists).

You can then explore the various data structures of the tree.

Also, since you are interested in DS related to search, I think you should study the B-tree + tree and the hash table.

Algorithm Design Guide is a good book to learn more about algorithms.

+2
source share

More articles:


All Articles