Softpanorama (slightly skeptical) Open Source Software Educational Society

May the source be with you, but remember the KISS principle ;-)

Searching Algorithms

Searching algorithms are closely related to the concept of dictionaries. Dictionaries are data structures that support search, insert, and delete operations. One of the most effective representations is a hash table. Typically, a simple function is applied to the key to determine its place in the dictionary. Another efficient search algorithms on sorted tables is binary search.

If the dictionary is not sorted then heuristic methods of dynamic reorganization of the dictionary are of great value. One of the simplest are cache-based methods: several recently used keys are stored a special data structure that permits fast search (for example is always sorted). For example keeping the last N recently found values at the top of the table (or list) dramatically improved performance. Other cache-based approach are also possible. In the simplest form the cache can be merged with the dictionary:

• move-to-front method A heuristic that moves the target of a search to the head of a list so it is found faster next time.

• transposition method Search an array or list by checking items one at a time. If the value is found, swap it with its predecessor so it is found faster next time.

In the paper On self-organizing sequential search heuristics, Communications of the ACM, v.19 n.2, p.63-67, Feb. 1976 , R.L. Rivest presents a set of methods for dynamically reordering a sequential list containing N records in order to increase search efficiency. The method Ai (for i between 1 and N) performs the following operation each time that a record R has been successfully retrieved: Move R forward i positions in the list, or to the front of the list if it was in a position less than i. The method A1 is called the transposition method, and the method AN-1 is called the move-to-front method.  See also J. H. Hester , D. S. Hirschberg, Self-organizing linear search, ACM Computing Surveys (CSUR), v.17 n.3, p.295-311, Sept. 1985

Old News ;-)

[May 6, 2008] C Minimal Perfect Hashing Library 0.8 by Davi de Castro Reis

About: C Minimal Perfect Hashing Library is a portable LGPL library to create and to work with minimal perfect hashing functions. The library encapsulates the newest and more efficient algorithms available in the literature in an easy-to-use, production-quality, fast API. The library is designed to work with big entries that cannot fit in the main memory. It has been used successfully for constructing minimal perfect hashing functions for sets with billions of keys.

Changes: This version adds the internal memory bdz algorithm and utility functions to (de)serialize minimal perfect hash functions from mmap'ed memory regions. The new bdz algorithm for minimal perfect hashes requires 2.6 bits per key and is the fastest one currently available in the literature.

Joseph Culberson's Binary Search Tree Research Binary Search Trees

This research is all concerned with the development of an analysis and simulations of the effect of mixed deletions and insertions in binary search trees. Previously it was believed that the average depth of a node in a tree subjected to updates was decreased towards an optimal O(log n) when using the usual algorithms (See e.g. Knuth Vol. 3 [8] ) This was supported to some extent by a complete analysis for trees of only three nodes by Jonassen and Knuth [7] in 1978. Eppinger [6] performed some simulations showing that this was likely false, and conjectured, based on the experimental evidence, that the depth grew as O(log^3 n), but offered no analysis or explanation as to why this should occur. Essentially, this problem concerning one of the most widely used data structures had remained open for 20 years.

Both my MSc [1] and Ph.D. [2] focused on this problem. This research indicates that in fact the depth grows as O(n^{1/2}). A proof under certain simplifying assumptions was given in the theoretical analysis in Algorithmica [3], while a set of simulations was presented together with a less formal analysis of the more general case, in the Computer Journal [4] , intended for a wider audience. A complete analysis for the most general case is still open.

More recently P. Evans [5] has demonstrated that asymmetry may be even more dangerous in smaller doses! Algorithms with only occasional asymmetric moves tend to develop trees with larger skews, although the effects take much longer.

Publications

1. Joseph Culberson. Updating Binary Trees. MSc Thesis, University of Waterloo Department of Computer Science, 1984. (Available as Waterloo Research Report CS-84-08.) Abstract
2. Joseph Culberson. The Effect of Asymmetric Deletions on Binary Search Trees. Ph. D. Thesis University of Waterloo Department of Computer Science, May 1986. (Available as Waterloo Research Report CS-86-15.) Abstract
3. Joseph Culberson J. Ian Munro. Analysis of the standard deletion algorithms in exact fit domain binary search trees. Algorithmica, vol 6, 295-311, 1990. Abstract
4. Joseph Culberson J. Ian Munro. Explaining the behavior of binary search trees under prolonged updates: A model and simulations. The Computer Journal, vol 32(1), 68-75, February 1989. Abstract
5. Joseph C. Culberson and Patricia A. Evans Asymmetry in Binary Search Tree Update Algorithms Technical Report TR94-09

   Other References

6. Jeffery L. Eppinger. An empirical study of insertion and deletion in binary trees. Communications of the ACM vol. 26, September 1983.
7. Arne T. Jonassen and Donald E. Knuth A trivial algorithm whose analysis isn't. Journal of Computer and System Sciences, 16:301-322, 1978.
8. D. E. Knuth Sorting and Searching Volume III, The Art of Computer Programming Addison-Wesley Publishing Company, Inc., Reading, Massachusetts, 1973.

Joseph Culberson

Simulations of dynamic sequential search algorithms

In [3], R.L. Rivest presents a set of methods for dynamically reordering a sequential list containing N records in order to increase search efficiency. The method Ai (for i between 1 and N) performs the following operation each time that a record R has been successfully retrieved: Move R forward i positions in the list, or to the front of the list if it was in a position less than i. The method A1 is called the transposition method, and the method AN-1 is called the move-to-front method.

Recommended Links

• Search algorithm - Wikipedia, the free encyclopedia
• NIST Dictionary of Algorithms and Data Structures/search
  • linear search
  • transpose sequential search
  • binary search
  • hash table
• Search Overview -- teaching search algorithms
• FUSE Home Page
• Glimpse home page
  • Feature Gentlemen, start your search engines (Mar. 13, 1997)
• Ternary Search Trees -- Algorithm for search. PDF file and examples in C.

Hashing

• CS453 Lecture 18 Extendible Hashing
• Perfect Hashing
• MD5 Hashing Function - Version 1.0
• Minimal Perfect Hashing
• What Is...hashing (a definition)
• Hashing Hashing. Binary Search Trees and their refinements store and retrieve data by traversing linked
  structures. Since the link sequences are of length log n...
• A Program That Performs Minimal Perfect Hashing Whatever THAT Is
• A Comparison of Hashing Schemes for Address Lookup in Computer Networks
• Zeus Animation of Hashing Algorithms
• UC Davis Computer Science Theory Laboratory

Algorithms/data animations

• Data Structures
• IBM Visualization Data Explorer Programmer's Reference
• Animated Binary Tree
  ... Insert Insert an integer in the binary tree. Node comparisons will appear in the
  bottom panel of the applet.
• Simple Binary Search Tree Applet
  Standard Binary Search Tree. The demo below allows you to perform basic
  operations on a binary search tree. The demo starts you off ...
• Binary Search Tree Demonstration
  Binary Search Tree Program. Nodes are inserted into and removed from a binary
  search tree. Each node contains a key value and a data value.

Linear Search

NIST: Linear search

Linear search - encyclopedia article about Linear search.

Review of Linear Search

In the previous labs we have already dealt with linear search, when we talked about lists. Linear Search in Scheme is probably the simplest example of a storage/retrieval datastructure due to the number of primitive operations on lists that we can use. For instance, creation of the datastructure just requires defining a null list.

There are two types of linear search we will examine. The first is search in an unordered list; we have seen this already in the lab about cockatoos and gorillas. All of the storage retrieval operations are almost trivial: insertion is just a single cons of the element on the front of the list. Search involves recurring down the list, each time checking whether the front of the list is the element we need. Deletion is similar to search, but we cons the elements together as we travel down the list until we find the element, at which point we return the cdr of the list. We also did analysis on these algorithms and deduced that the runtime is O(n).

C++ Examples - Linear Search in a Range

On the Competitiveness of Linear Search

C++ Notes: Algorithms: Linear Search

Move to the front (self-organizing) modification

Linear Search  the Transpose Method

Here the heuristic is slightly different from the Move-To-Front method : once found, the transition is swapped with the immediately preceding one, performing an incremental bubble sort at each access.

Of course, these two techniques provide a sensitive speed-up only if the probabilities for each transition to be accessed are not uniform.

These are the seven representations that caught our attention at first but that set of containers will be broadened when a special need is to be satisfied.
What is obvious here is that each of these structures has advantages and drawbacks, whether on space complexity or on time complexity. All these constraints have to be taken in account in order to construct code adapted to particuliar situations.

Linear Search : the Move-To-Front Method

Self-organizing linear search
... Self-organizing linear search. Full text, pdf formatPdf (1.73 MB). ... ABSTRACT Algorithms
that modify the order of linear search lists are surveyed. ...
portal.acm.org/citation.cfm?id=5507 - Similar pages

Linear search in lists

Binary Search

NIST: binary search

Definition: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Generalization (I am a kind of ...)
dichotomic search.

Aggregate parent (I am a part of or used in ...)
binary insertion sort, ideal merge, suffix array.

Aggregate child (... is a part of or used in me.)
divide and conquer.

See also linear search, interpolation search, Fibonaccian search, jump search.

Note: Run time is O(ln n). The search implementation in C uses 0-based indexing.

Author: PEB

Implementation

search (C) n is the highest index of the 0-based array; possible key indexes, k, are low < k <= high in the loop. (Scheme), Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.

en.wikipedia.org/wiki/Binary_search

Topic #9 Binary search trees

Search Trees

Binary Search Trees

Binary Search Trees http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/niemann/s_bin.htm

Binary Search Tree http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/binarySearchTree.htm

Trees

• Trees Author: Glenn W. Rowe -- good
• Report No.50 Eckerle Nurmi Concurrent Perfect Balancing of Binary Search Trees
• Ternary Search Trees -- Algorithm for search. PDF file and examples in C.
• DDJ Ternary Search Trees By Jon Bentley and Bob Sedgewick
• Red-Black Trees

AVL trees

(see also Libraries -- there are a several libraries that implementat AVL trees)

• libavl manual - Introduction to AVL trees
• AVL Trees Tutorial and C++ Implementation
• AVL Trees with Relaxed Balance
• Sizes for AVL Trees
• CS 660 AVL TREES
• AVL Trees
• AVL Tree
• avl-1.3.0 README -- version 1.3 of libavl, a library in ANSI C for manipulation of AVL trees.
  Functions for use with three varieties of AVL tree are included.
• gtk-devel-list Splay trees
• Lecture 9 - Binary Search Trees (Section 8.2)
• Trees on Disk
• CP2001 Tutorial Week 10 -- This tutorial investigates AVL trees and B-trees
• Class 18 & 19 -- AVL trees
• CS631 Reading List
• Abstract No. 6

Fibonacci search

(see The Fibonacci Numbers and Golden section in Nature for information about Fibinacci, who introduced the decimal number system into Europe and first suggested a problem that lead to Fibonacci numbers)

• Algorithm Alley The Fibonacci Heap John Boyer DDJ January 1997
• Fibonacci search (see also Dictionary of Algorithms, Data Structures, and Problems)
• Fibonacci Search
• The Fibonacci Series - Search
• Chapter 5 SINGLE VARIABLE SEARCH TECHNIQUES
• Fibonacci Search in Design and optimization techniques of high-speed VLSI circuits by Marco Delaurenti. PhD Dissertation. Date: December 1999
• Mathematical Programming Glossary - F

  Fibonacci search. This finds the maximum of a unimodal function on an interval, [a, b], by evaluating points placed according to a fibonacci sequence, {F_N}. If there are F_N points in the interval, only N evaluations are needed. In the continuous case, we begin with some interval of uncertainty, [a,b], and we reduce its length to (b-a)/F_N. The ratio, g_n = F_(n-1)/F_n, is the key to the placements.

  Here is the method for the continuous case:

  1. Initialization. Let x = a + (1 - g_N)(b-a) and y = a + g_N(b-a). Evaluate f(x) and f(y) and set n=N.
  2. Iteration. If f(x) < f(y), reduce the interval to (x, b] (i.e., set a=x), decrement n to n-1, and set x = y and y = a + g_n(b-a). If f(x) >= f(y), reduce the interval to [a, y) (i.e., set b=y), decrement n to n-1, and set y = x and x = a + (1-g_n)(b-a).

  The fibonacci search method minimizes the maximum number of evaluations needed to reduce the interval of uncertainty to within the prescribed length. For example, it will reduce the length of a unit interval [0,1] to 1/10946 (= .00009136) with only 20 evaluations. In the case of a finite set, fibonacci search finds the maximum value of a unimodal function on 10,946 points with only 20 evaluations, but this can be improved -- see lattice search.

  For very large N, the placement ratio (g_N) approaches the golden mean, and the method approaches the golden section search. Here is a comparison of interval reduction lengths for fibonacci, golden section and dichotomous search methods. In each case N is the number of evaluations needed to reduce length of the interval of uncertainty to 1/F_N. For example, with 20 evaluations dichotomous search reduces the interval of uncertainty to .0009765 of its original length (with separation value near 0). The most reduction comes from fibonacci search, which is more than an order of magnitude better, at .0000914. Golden section is close (and gets closer as N gets larger).

      Evaluations  Fibonacci      Dichotomous      Golden section
          N          1/F_N        1/2^|_N/2_|      1/(1.618)^(N-1) 
      ============================================================
          5         .125            .25              .146
         10         .0112           .0312            .0131
         15         .00101          .00781           .00118
         20         .0000914        .000976          .000107 
         25         .00000824       .0002441         .0000096 
      =============================================================
        

  Here is a biography of Fibonacci.

  Fibonacci sequence. The numbers satisfying: F_(n+2) = F_(n+1) + F_n, with initial conditions F_0 = F_1 = 1. As shown in the following table, the fibonacci sequence grows rapidly after N=10, and for N > 50, F_N becomes astronomical.

           N    F_N
         ==============
           0      1
           1      1
           2      2
           3      3
           4      5
           5      8
           6     13
           7     21
           8     34
           9     55
          10     89
          20  10946
          50    2.0E10
         100    5.7E20
        ==============     

  Named after the 13th century mathematician who discovered it, this sequence has many interesting properties, notably for an optimal univariate optimization strategy, called fibonacci search

• handout0
• Fibonacci Numbers, the Golden section and the Golden String

Last modified:  November 08, 2008