School of Computing

Parallel searching for a first solution

Bozena Bartoszek, Zbigniew Czeck, and Marek Konopka

Technical Report 8-93*, University of Kent, Computing Laboratory, University of Kent, Canterbury, UK, September 1993.

Abstract

A parallel algorithm for conducting a search for a first solution to the problem of generating minimal perfect hash functions is presented. A message-based distributed memory computer is assumed as a model for parallel computations. A data structure, called reverse trie (r-trie), was devised to carry out the search. The algorithm was implemented on a transputer network. The experiments showed that the algorithm exhibits a consistent and almost linear speed-up. The r-trie structure proved to be highly memory efficient.

Download publication 78 kbytes

Bibtex Record

@techreport{97,
author = {Bozena Bartoszek and Zbigniew Czeck and Marek Konopka},
title = {Parallel Searching for a First Solution},
month = {September},
year = {1993},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/1993/97},
    address = {University of Kent, Canterbury, UK},
    hensa_abstractfilename = {pub/misc/ukc.reports/comp.sci/abstracts/8-93},
    hensa_ftpaddress = {unix.hensa.ac.uk},
    hensa_reportfilename = {pub/misc/ukc.reports/comp.sci/reports/8-93.ps.Z},
    institution = {University of Kent, Computing Laboratory},
    number = {8-93*},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014