1995 Graduate Student Research Conference [preliminary] Program (GSRC95)
For a schedule, click here
Yili Yao and Tzi-cker Chiueh
Indexing for Compressed Text
Information explosion of this era poses new requirements on efficient management
of large-scale data storage system. Traditional text indexing scheme suffers
from extra storage space and processing overheard. One innovative approach is
to integrate text indexing with text compression in a way that it significantly
reduces the size of inverted index files and allows direct search through
compressed text.
Urs Kanus & Michael Meissner
Teramac -- A Programmable Supercomputer
Sanjay Padubidri
Efficient Virtual Memory
Ingmar Bitter
The Eyetrack Project
Michael Wynblatt
Control Structures for Multimedia
Lichan Hong, Arie Kaufman, Yi-Chih Wei, Ajay Viswambharan,
Mark Wax, and Zhengrong Liang
3D Virtual
Colonoscopy
We present in this talk a method called 3D virtual colonoscopy, which
is an alternative method to existing procedures of imaging the mucosal
surface of the colon. Using 3D reconstruction of helical CT data and
volume visualization techniques, we generate images of the inner
surface of the colon as if the viewer's eyes were inside the colon. We
also create interactive flythroughs and off-line
automatically-produced animations through the inside of the colon. The
visualization is accomplished with VolVis, which is a comprehensive
system for interactive volume visualization. We are specifically
interested in visualizing colonic polyps larger than one cm since
these have a high probability of containing carcinoma. We present
testing results of our method as applied to two plastic pipe
simulations and to the Visible Human data set.
Claudio Silva, Joseph S.B. Mitchell, and Arie E. Kaufman
Automatic Generation of Triangular
Irregular Networks
We propose a new approach to the automatic generation of triangular
irregular networks from dense terrain models. We have developed and
implemented an algorithm based on the greedy principle used to compute
minimum-link paths in polygons. Our algorithm works by taking greedy
cuts (``bites'') out of a simple closed polygon that bounds the
yet-to-be triangulated region. The algorithm starts with a large
polygon, bounding the whole extent of the terrain to be triangulated,
and works its way inward, performing at each step one of three basic
operations: ear cutting, greedy biting, and edge splitting. We give
experimental evidence that our method is competitive with current
algorithms and has the potential to be faster and to generate many
fewer triangles. Also, it is able to keep the structural terrain
fidelity at almost no extra cost in running time and it requires very
little memory beyond that for the input height array.
Karen Bernstein and Eugene Stark
Do what I mean, not what I say: Debugging
Specifications
Ting Chen
Gene-Finding and Gene Structure Predicction
One of the most difficult problems in science today is learning the language
of human genetics. Many birth defects and thousands of diseases result from
genes containing incorrect instructions. Unfortunately, traditional methods
(the biological experiments) of locating genes within the DNA are quite slow;
to date only some 5% of an estimated 100,000 human genes are identified, and
it can take months or years to locate even a single one.
To speed up that process, the powerful techniques in computer science are
introduced into human biology to develop the Gene Recognition and Analysis
software system that seeks genetic meaning in the billions of DNA bases and
gives the most promising direction quickly.
Recent approaches have involved techniques in Algorithm, Pattern Recognition,
and Statistics. Professor Steve Skiena and I have been studying carefully on
various techniques on recognizing genes, and currently, a joint project--to
predict genes on yeast--with Cold Spring Harbor Lab is considered.
Dmitry Zinoviev
Feasibility of RSFQ-based Data Network Switches
Emerging optical metropolitan area networks (MAN) will provide
enormous data transfer possibilities (>=40Gbps) that cannot be
efficiently used by the traditional semiconductor equipment. On the
other hand, photonics data processing circuits as they appear now are
unreliable, difficult to fabricate and extremely space- and
power-consuming. However, there exists an alternative to both
semiconductor and optical processing elements --- superconductor rapid
single-flux quantum (RSFQ) logic/memory family. The greatest
advantages of the superconductor digital devices are that they are
able to generate, process and transfer picosecond voltage pulses at
the frequency of <=300GHz while consuming negligible power of
0.3 ... 1mW. RSFQ circuits reveal these advantages when
used for synchronous serial data processing. The goal of the talk is
to argue that they may be a natural solution for gigabit digital data
switches.
Mauricio Cortes
Coordination issues in collaborative
applications
Collaborative applications enable two or more end-users to commu-
nicate through shared computational resources. These resources
can be viewed as the composition of some data component ranging
from simple text documents to complex scientific data, and a set
of operations that can manipulate these data. In addition to the
traditional coordination issues that arise in multiuser settings
when update operations are applied to some shared data (e.g. low-
level concurrency control), the development of groupware systems
also need to address other high-level coordination and control
issues, such as group protocols and policies.
A major challenge to develop these systems is the representation
and handling of high-level interaction definitions. These inter-
action rules specify the group environment that collaborators
must follow in order to work together. Rules can be changed dyna-
mically,as it has been observed by many researchers. An instance
of these interaction rules represent a group environment, such
as peer environments and group presentations.
We are developing a coordination language to allow programmers
decouple the computational aspect of a groupware application,
written in some conventional languages (e.g. C), from its group
coordination requirements specified in our scripting language.
Taosong He
Voxel-based Object Simplification
Michael Vernick, Chitra Venkatramani and Tzi-cker Chiueh
Performance Evaluation of the Stony
Brook Video Server
This talk presents the results of a detailed performance evaluation of
the Stony Brook Video Server (SBVS), an Ethernet-based video server
built in the Experimental Computer Systems Lab at Stony Brook. The
SBVS employs only off-the-shelf PC components and is capable of
guaranteeing the real-time delivery of digital video streams from the
server's disk subsystem, through a local area network, and to an end
user's display. To our knowledge, the SBVS is the first
implementation that achieves such end-to-end performance guarantees.
The SBVS integrates a software-based disk array with a Real-Time
Ethernet Protocol, (RETHER), which guarantees the smooth delivery of
multimedia data while allowing non-real-time traffic to coexist on the
same LAN. Two sets of experiments were run under multiple hardware
configurations: 1) experiments that determine the maximum performance
of individual system components such as I/O and network subsystems;
and 2) experiments that evaluate the SBVS in terms of the maximum
number of streams that can be supported for varying stream rates and
disk retrieval sizes. Assuming an average bandwidth rate of 1.5Mbps
per MPEG stream, we show that SBVS-2, a Pentium PC with a four-drive
disk array and 100 Mbps Ethernet, can support up to a maximum of 45
simultaneous video streams. Moreover, our measurements show that the
overall performance of the SBVS is comparable to what can be achieved
by the I/O and network subsystems in isolation, indicating that the
design and implementation of the SBVS use the underlying hardware
resources very efficiently.
Prasad Rao
Optimizations for In-Memory Queries
for Deductive Databases
Bruno Costa & Lucia Darsa
Graphical Object Morphing
Hanspeter Pfister
The Cube-4 Volume Rendering Engine
David Gerstl, Art Bernstein and Phil Lewis
Faster
Transactions-Exploiting Transaction Semantics
Most transaction processing systems use two-phase locking to guarantee
serializability and hence the correct execution of concurrent
transactions. However, two-phase locking often requires that
transactions hold locks for long periods of time and hence can have a
detrimental effect on transaction throughput and response time. The
most common solution is to use the semantics of the operations on the
database to allow transactions to share locks on data. We are
presently extending this approach by examining how the data items are
used by the transaction and using this information to allow
transactions to share locks on data or to release locks entirely. We
have two different methods which each have advantages and
disadvantages. I will discuss one of these two methods and how it can be
used to achieve high throughput in certain application areas. I will explain what types of applications can benefit from this method.
Matthias Bannach and Art Bernstein
Alarm Correlation in Network
Management
The huge size of data networks, even in a single corporation, makes it
difficult to pinpoint failures or performance problems when they
arise. To overcome this, some network devices spontaneously send
alarm messages to a management station when an unusual circumstance is
detected. In addition, the devices monitor their own status in a
local database that can be accessed from the management station.
ACE, an Alarm Correlation Engine, is being developed in cooperation
with Stony Brook Services, a vendor for high end router mamagement
software. The ACE aids the network manager by correlating the alarm
messages and using the information in the local databases to pinpoint
network problems.
The talk will give an introduction to the novel strategies of alarm
correlation and performance monitoring being developed. The complexity
of such a task in a multi-vendor, multi-protocol environment will be
outlined and a direction for our future research shown.
Rui Hu
Distributed XSB
XSB is a well-known system which integrates logical
programming, deductive database (DDB) and non-monotonic
reasoning(NMR). XSB has been installed in about 500 sites
around the world, and used for such purposes as traffic
control in Switzerland, for a system to teach undergraduates
linguistics, and for a series of data cleaning efforts by
the US Treasury Department (including the natural language
system). The essential asynchrony in sequential execution
of XSB makes it natural for distributed execution. Distributed
XSB decomposes the query issued to the database into several
sub-queries and distributing them to corresponding servers,
which can again decompose and distribute the sub-queries
distributed to them. So distributed XSB is running on a
symmetric client/server network, where each node in the network
can be both a client and a server. Besides the communication
and cooperation among the nodes in the network, one of the major
issues in designing and implementing distributed XSB is
distributed termination detection, which involves the detection
of the topology of dynamically-changed underlying computation,
and then the quiescence of the distributed computation.
Distributed XSB can be used as the underlying framework of
distributed heterogeneous database, where different database
management systems on different sites can collaborate through XSB.
Chitra Venkatramani and Tzi-cker Chiueh
RETHER : A Software-based Real-time Ethernet Protocol
Distributed multimedia applications require performance guarantees
from the underlying network subsystem. Ethernet has been the dominant
local area network architecture in the last decade, and we believe
that it will remain popular because of its cost-effectiveness and the
availability of higher-bandwidth Ethernets. We present the design,
implementation and evaluation of a software-based timed-token protocol
called RETHER that provides real-time performance guarantees to
multimedia applications without requiring any modifications to
existing Ethernet hardware. RETHER features a hybrid mode of operation
to reduce the performance impact on non-real-time network traffic, a
race-condition-free distributed admission control mechanism, and an
efficient token-passing scheme that protects the network against token
loss due to node failures or otherwise. Performance measurements from
experiments on a 10 Mbps Ethernet indicate that up to 60% of the raw
bandwidth can be reserved without deteriorating the performance of
non-real-time traffic.
Manish Verma
Low latency communication on an Ethernet
Dimitris Margaritis
The PAMIS system: content-based searching
Hongwei Shi and Theo Pavlidis
Matching Graph Embeddings for Shape Analysis
Past research in shape analysis and OCR has often emphasized graph
matching techniques. We propose to use matching of graph embeddings
because this is what is actually of interest. In this way we obtain
faster and simpler algorithms since most decisions can be made on the
basis of graph labels (the geometry of the embedding) rather than the
topology of the graph. The latter has to examined only in very few
cases. The proposed algorithm consists of four sieves that compare
branches of two embeddings by (normalized), angle, y-position,
x-position, and length. Pairs of graphs that pass all the sieves have
a node correspondence established so the next step compares
degrees. Finally paths are determined using Kleene's algorithm and
compared with prototype arcs.
Abhik Roychoudhury
Design for testability by minimizing
the number of independent clocks
in a synchronous sequential circuit (
a graph theoretic approach )
The problem discussed in this talk has its origin in the domain of VLSI testing and is concerned with the notion of "design for
testability". Since VLSI circuits are notorious as far as the
number of combinational and sequential components are concerned,
the testing itself is not a trivial matter.The basic idea of
design for testability is to make the design amenable to
testing.
It is here that the minimization of the number of independent
clocks come into the picture. Our strategy is to partition the
flip-flops of the circuit into a minimal number of test modes,
where we assign an independent clock for each test mode and enable
only the flip-flops corresponding to that mode.
This however requires the circuit corresponding to each test
mode to be a definite machine. We solve the problem by taking a
derived graph correponding to the circuit and decompose it to a
minimal number of vertex disjoint forests. The results have been
surprisingly good and we are able to get away with as low as 3
test modes in a large class of circuits. In many situations, we
show that testing is possible using only 2 test modes as well.
Apart from the VLSI testing problem, the solution is of
general theoretical interest from the view point of graph
theory as well.
Wai-Hong Leung, Art Bernstein and Phil Lewis
High performance concurrency control using transactional semantic
Conventional concurrency control systems use shared/exclusive locks
to prevent concurrent transactions from interfering with one another.
Such systems do not exploit the semantics of transactions to achieve
a higher degree of concurrency. We use transaction semantics to
define a new lock mode called an assertion lock and combine
shared/exclusive locks
with assertion locks to increase concurrency. An assertion lock
on an item allows certain updates to be done on that item (as long
as they do not invalidate the assertion) while shared/exclusive
locks exclude all updates. We explain the theory of assertion locking,
describe an implementation of the algorithm, and give some examples of
applications that can benefit from this concept.
Return to the GRC home page
If you have problems with this page, please send E-mail to:
evans@cs.sunysb.edu