BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR92-184
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Building Segment Trees in Parallel
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Su, Peter
AUTHOR:: Drysdale, Robert L. Scot
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1992
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR92-184.pdf
ABSTRACT::
	The segment tree is a simple and important data structure in
computational geometry [7,11].  We present an experimental study of
parallel algorithms for building segment trees.  We analyze the
algorithms in the context of both the PRAM (Parallel Random Access
Machine) and hypercube architectures.  In addition, we present
performance data for implementations developed on the Connection
Machine.  We compare two different parallel alforitms, and we also
compare our parallel algorithms to a good sequential algorithm for
doing the same job.  In this way, we evaluate the overall efficiency
of our parallel methods.
	Our performance results illustrates the problems involved in
using popular machine models(PRAM) and analysis techniques (asymptotic
efficiency) to predict the performance of parallel algorithms on real
machines.  We present two different analyses of our algorithms and
show that neither is effective in predicting the actual performance
numbers that we obtained.
END:: ncstrl.dartmouthcs//TR92-184