The theoretical results pertain to * individuality
validation*.
In classification problems such as * writer, face, finger print*
or * speaker identification*, the number of classes is very large
or unspecified.
To establish the inherent distinctness of the classes,
i.e., validate individuality, we transform the many class problem into
a dichotomy by using a ``distance'' between two samples of the same
class and those of two different classes.
Based on conjectures derived from experimental observations, we
present theorems comparing polychotomy in feature domain and dichotomy
in distance domain from the view point of tractability vs. accuracy.

The practical application issues include * efficient search, writer
identification* and * discovery*.
First, fast nearest-neighbor algorithms for distance measures are
given. We also discuss designing and analyzing an algorithm for *
writer identification* for a known number of writers and its
relationship to * handwritten document image indexing and
retrieval*.
Finally, we present mining a database consisting of writer data and
features obtained from a handwriting sample, statistically
representative of the US population, for feature evaluation and
to determine similarity of a specific group of people.
Tue, 15 May 2001 13:12:09 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-06.ps
%A Chun-Hsi Huang
%T Communication-Efficient Bulk Synchronous Parallel Algorithms
%R 2001-06
%D July 30, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K parallel algorithm
%Y algorithms
%X Communication has been pointed out to be the major bottleneck for the
performance of parallel algorithms. Theoretical parallel models such as
PRAM have long been questioned due to the fact that the theoretical
algorithmic efficiency
does not provide a satisfactory performance prediction when algorithms are
implemented on
commercially available parallel machines. This is mainly because these
models do not provide a reasonable scheme for measuring the communication
overhead. Recently several practical parallel models aiming at achieving
portability and scalability of parallel algorithms have been widely
discussed. Among them, the Bulk Synchronous Parallel (BSP) model has
received much attention as a bridging model for parallel computation, as it
generally better addresses practical concerns like communication and
synchronization.
The BSP model has been used in a number of application areas, primarily in
scientific computing. Yet, very little work has been done on problems
generally considered to be irregularly structured, which usually result
in highly data-dependent communication patterns and make it difficult to
achieve communication efficiency. Typical examples are fundamental problems
in graph
theory and computational geometry, which are important as a vast number of
interesting problems in many fields are defined in terms of them. Thus
practical and communication-efficient parallel algorithms for solving these
problems are important.
In this dissertation, we present scalable parallel algorithms for some
fundamental problems in graph theory and computational geometry. In
addition to the time complexity analysis, we also present some techniques
for worst-case and average-case communication complexity analyses.
Experimental studies have been performed on two different architectures in
order to demonstrate the practical relevance.
Thu, 02 Aug 2001 14:52:25 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-07.prn
%A LUO, Hui
%T KNOWLEDGE-BASED IMAGE UNDERSTANDING AND CLASSIFICATION SYSTEM FOR MEDICAL IMAGE DATABASES
%R 2001-07
%D July 30, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Medical images databases, Knowledge-based, image understanding,
image classification, feature extraction, snake model, object-oriented
representation
%X The understanding of medical images involves the identification of
anatomical structures in images, the establishment of the
relationships among the structures and the matching them with
pre-defined anatomical models. The closer this match, the better the
image is understood. Hence, the development and use of anatomical
knowledge models are critical to the effectiveness of the system. In
this thesis, we will present a new knowledge model for medical image
content analysis based on the object-oriented paradigm. The new model
abstracts common properties from different types of medical images by
using three attributes: description, component, and semantic graph,
and specifies its actions to schedule the detection procedure,
properly deform the model shapes to match the corresponding anatomies
in images, select the best match candidates, and verify the
candidates”Æ spatial relations with the semantic graph defined in the
model. The advantage of the new model includes: 1) It presents a
robust representation ability to represent the object variability, 2)
It provides a tighter bond between features and methods, and 3) It
supports the complex image analysis and works on both normal and
abnormal images. Based on this model, a knowledge-based medical image
classification system is developed. The system assigns each input
image with one or more most similar models by performing a two-stage
processing. The first stage, coarse shape classification, focuses on
the global shape features of objects in the processed images. The
second stage performs a detail matching between extracted image
features and model specified properties. The output match results
imply a set of models which are most possible to be existed in the
processed image. To further confirm them, an evaluation strategy is
used to reject those unreasonable results and inference the high
confidence match models. To improve the detection accuracy, we also
proposed a new region model which combines both region and edge
information into image segmentation, and reformulate the traditional
snake model and level set model with it. As expected, the reformulated
models demonstrate robust ability to deal with the ambiguity in images
and overcome the problem associated with the initialization. The
performance of the system has been tested on different types of
digital radiographs, including chest, pelvis, ankle, elbow and
etc. The experimental results suggest that the system prototype is
applicable and robust, and the accuracy of the system is nearly 70% in
our image databases.
Thu, 02 Aug 2001 14:58:55 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-08.ps
%A Ismail, Haythem O.
%A Shapiro, Stuart C.
%T The Cognitive Clock: A Formal Investigation of the Epistemology of Time
%R 2001-08
%D August 14, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Temporal reasoning, cognitive robotics, knowledge representation
%Y I.2.4
%X We present a formal model of time and time perception. The model is
used to endow a cognitive agent with a personal sense of time. A personal
sense of time is based on a representation of the real-time present that
allows the agent to distinguish it from the past and the future, and is
continuously changing to reflect the progression of time. This is important
for reasoning about, and acting in, dynamic domains and for interacting
with other agents (humans, for example). An agent that interleaves
reasoning and acting while maintaining a sense of the present faces what
has been dubbed {\em the problem of the fleeting now}. A solution to the
problem involves, not only endowing the agent with a sense of temporal
progression, but also with a feel for how much time has passed. In this
paper, we construct a theory of time that allows just that.
Mon, 20 Aug 2001 18:14:24 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-09.tr.pdf
%A Rapaport, William J.
%T Holism, Conceptual-Role Semantics, and Syntactic Semantics
%R 2001-09
%D August 17, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K philosophy of artificial intelligence, cognitive science, SNePS, holism, semantics, knowledge representation
%X This essay continues my investigation of "syntactic semantics": the
theory that, *pace* Searle's Chinese-Room Argument, syntax *does*
suffice for semantics (in particular, for the semantics needed for a
computational cognitive theory of natural-language understanding).
Here, I argue that syntactic semantics (which is internal and
first-person) is what has been called a conceptual-role semantics: The
meaning of any expression is the role that it plays in the complete
system of expressions. Such a "narrow", conceptual-role semantics is
the appropriate sort of semantics to account (from an "internal", or
first-person perspective) for how a cognitive agent understands
language. Some have argued for the primacy of external, or "wide",
semantics, while others have argued for a two-factor analysis.
But, although two factors can be specified---one internal and
first-person, the other only specifiable in an external, third-person
way---only the internal, first-person one is needed for understanding
how someone understands. A truth-conditional semantics can still be
provided, but only from a third-person perspective.
Mon, 20 Aug 2001 18:18:53 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-10.ps
%A Pavan, A.
%T Average-case complexity theory and polynomial-time reductions
%R 2001-10
%D August 26, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K average-case complexity, reasonable distributions, distributionally-hard languages, polynomial-time reducibilities, separating NP-completeness notions
%X This thesis studies average-case complexity
theory and polynomial-time reducibilities. The issues in average-case
complexity arise primarily from Cai and Selman's extension of Levin's
definition of average polynomial time. We study polynomial-time
reductions between distributional problems. Under strong but
reasonable hypotheses we separate ordinary $\NP$-completeness notions.
The average-case complexity of a problem is, in many cases, a more
significant measure than the worst-case complexity.
It is known that some $\NP$-complete problems, such as $k$-coloring and
Hamiltonian cycle, can be solved quickly on average.
This has motivated
the development of the study of average-case analysis of algorithms.
Levin~\cite{Levin86} initiated a general study of average-case complexity by
defining a robust notion of average polynomial time and the notion of
distributional $\NP$-completeness.
Cai and Selman ~\cite{CaiSelman99} gave a general definition of {\em $T$ on aver
age} for arbitrary
time bounds $T$. They observed difficulties with Levin's definition of
average polynomial time when applied to unreasonable input distributions.
Their definition of average polynomial time slightly modifies Levin's
definition to avoid these difficulties.
In this thesis we study reasonable distributions,
distributionally-hard languages, and reductions among distributional
problems.
We prove several results demonstrating that it suffices to restrict
one's attention to reasonable distributions.
This is important because both Levin's definition and
Cai and Selman's definition yield unsatisfactory consequences when we
permit unreasonable distributions. We show that if $\NP$ has a
$\DTIME(2^n)$-bi-immune language, then every $\DistNP$-complete problem must
have a
reasonable distribution. We prove that the class $\ppcomp$, the set of languages
that can be decided in average polynomial time with respect to every
polynomial-time computable distribution, remains
unchanged when restricted to reasonable distributions. We strengthen and
present a simpler proof of a
result of Belanger and Wang~\cite{BelangerWang96}, which shows that Cai and Selm
an's definition of
average-polynomial time is not closed under many-one reductions.
Cai and Selman showed
that every is $\P$-bi-immune language is dis\-tri\-bu\-tionally-hard. We study
the question of whether there exist distributionally-hard languages that are not
$\P$-bi-immune. First we show that such languages exist if and only if $\P$
contains $\P$-printable-immune sets. Then we extend this characterization
significantly to include assertions about several traditional
questions about immunity, about finding witnesses for $\NP$-machines, and
about the existence of one-way functions.
Next we study polynomial-time reducibilities.
Ladner, Lynch, and Selman~\cite{LadnerLynchSelman75}
showed, in the context of worst-case complexity, that various poly\-no\-mi\-al-t
ime
reductions differ in $\E$. We show similar results
for reductions between distributional problems and we show that
most of the completeness notions for $\DistEXP$ are
different.
Finally, we turn our attention to the question
of whether various notions of
$\NP$-completeness are different. Lutz and Mayordomo, under the
hypothesis that the $p$-measure of $\NP$ is not zero, and Ambos-Spies and
Bentzien, under the hypothesis that $\NP$ has a $p$-generic language,
showed that various completeness notions in $\NP$ are different.
We introduce a structural hypothesis not involving stochastic properties
and prove that the existence of a Turing complete language for $\NP$
that is not truth-table complete follows from our hypothesis.
This result is the first to provide evidence that truth-table
completeness for $\NP$ is weaker than Turing completeness for $\NP$.
Tue, 28 Aug 2001 17:20:27 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-11.ps
%A Ismail, Haythem O.
%T Reasoning and Acting in Time
%R 2001-11
%D August 24, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Knowledge representation, cognitive robotics, temporal reasoning
%Y I.2.4
%X This dissertation investigates aspects of the design of an embodied
cognitive agent that interleaves reasoning, acting, and interacting with
other agents while maintaining a record of what has happened and is
happening in its environment. Among other things, such knowledge of its own
history allows the agent to reason more effectively when faced with an
emergency situation such as the failure of one of its acts. Crucial to
distinguishing what has happened from what is happening is a
notion of the present time, or ``now''. There has been much research in
artificial intelligence on issues of time. However, it is typically the
case that, although an agent reasons about time, it is not itself
situated {\em in} time. Once the agent has a concept of ``now'', one that
continuously changes to reflect the progression of time, a different kind
of temporal reasoning problem emerges. For example, given that an agent
could be told anything, how are formal representations of present states
to be distinguished from those of past states, where the former, but not
the latter, are pertinent to the agent's actions? And, given that the
present must be distinguished, how is ``now'' to be modeled so that the
mere passage of time does not result in computationally costly
knowledge-base-editing routines? How can the agent reason about ``now'',
when the very process of reasoning results in ``now'' changing? How can the
agent be endowed with a feel for how much time has passed, which seems
crucial for reasoning about persistence as time passes while the agent
acts?
In this dissertation, the above issues are investigated in detail.
A theory of subjective time is presented, accounting for a cognitive
agent's {\em vague} concept of ``now'', its sense of temporal progression,
and its feel for how much time has passed. An investigation of the impact
of embodiment and time perception on issues of reasoning about persistence
as the agent acts comes out as a natural by-product of the theory. The
theory of subjective time is wrapped around a core logic of objective time
that axiomatizes various aspectual phenomena needed for reasoning, acting,
and natural language interaction. Unlike most theories of linguistic
aspect, the logic of aspect presented here accounts for the agent's
knowledge of states, events, and processes, not only from static
natural language inputs, but also from the dynamic accumulation of
perceptual and proprioceptual information as events unfold in time.
Based on the logical analysis of the notion of telicity (the analysis goes
beyond the standard telic/atelic distinction), a theory of how cognitive
agents may employ reasoning to control the execution of sequences of acts
is presented. The theory proposes a principled way by which agents may
decide when it is time to move on to the next step in a sequence; an issue
that has not been given much attention in the literature. Finally, the
dissertation establishes a framework for interrupt-handling and error
recovery based on a system of context-sensitive priorities among acts.
Wed, 29 Aug 2001 17:12:17 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-12.pdf
%A Song, Yuqing andhang, Aidong
%T Monotonic Tree of Images and Its Application in Image Processing
%R 2001-12
%D August 29, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Image retrieval
%Y Image processing
%X Contour trees have been used in geographic information systems (GIS)
and medical imaging to display scalar data. Contours are only defined for
continuous functions. For an image represented by discrete data,
a continuous function is first defined as an interpolation of the data.
Then the contour tree is defined on this continuous function.
In this paper, we introduce a new concept termed monotonic line,
which is directly defined on discrete data.
All monotonic lines in an image form a tree, called monotonic tree.
As compared with contour trees, monotonic trees avoid the step of
interpolation, thus can be computed more efficiently.
Monotonic tree can be reduced.
The reduced monotonic tree can also be used as a hierarchical
representation of image structures in image processing.
In particular, we demonstrate its application
on image smoothing and texture retrieval.
Experiments show that our smoothing scheme is
successful in both noise reduction and texture retrieval.
Tue, 04 Sep 2001 14:36:20 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-13.pdf
%A Qiao, Chunming
%A Xu, Dahai
%T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part I
%R 2001-13
%D July 10, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K distributed routing and signaling, bandwidth guarantee, sharing, allocation and deallocation,protection
%Y Algorithms
%X This paper describes a novel framework,
called Distributed Partial Information
Management (or DPIM). It addresses several major challenges
in achieving efficient shared path protection under
distributed control
with only partial information, including
(1) how much partial information about existing active and backup paths
(or APs and BPs respectively) is maintained and exchanged;
(2) how to obtain a good estimate of the bandwidth needed by a candidate BP,
called BBW, and subsequently select a pair of AP and BP for a
connection establishment request so as to minimize total bandwidth consumption
and/or maximize revenues;
(3) how to distributively allocate minimal BBW (and de-allocate maximal BBW) via distributed signaling; and
(4) how to update and subsequently exchange the partial information.
A DPIM-based scheme using Integer Linear Programming
is described to illustrate our approach.
In addition, an ultra-fast and efficient heuristic scheme
is described. With about the same amount of partial information,
such a heuristic-based DPIM scheme can achieve almost
as a good performance as the ILP-based DPIM scheme,
and a much better performance than another ILP-based scheme described in
[1].
The paper also presents an elegant method to support
dynamic requests for protected, unprotected, and pre-emptable
connections in the unified DPIM framework.
Tue, 02 Oct 2001 01:22:13 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-14.pdf
%A Xu, Dahai
%A Qiao, Chunming
%T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part II
%R 2001-14
%D July 10, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K bandwidth sharing, distributed routing, on-line heuristic, potential cost
%Y Algorithms
%X A major challenge in shared path protection is to select
a jointly optimized pair of active and backup paths.
While Integer Linear Programming (ILP) based approaches are
notoriously time consuming, existing heuristics such as active path first
(APF) can only achieve sub-optimal results.
In this paper, we propose a novel heuristic called
APF with potential backup cost or APF-PBC under the distributed partial
information management framework described in [1]
for ultra-fast processing of on-line requests.
We show that APF-PBC can outperform
existing schemes based on Integer Linear Programming (ILP)
with exactly the same input (either partial or complete information) and
constraint.
We also show how an intuitive function to compute the potential backup cost
is derived mathematically based on
the statistical analysis of experimental data.
Tue, 02 Oct 2001 01:23:49 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-15.ps
%A Jayaraman, B.
%A Tambay, P.
%T Semantics and Applications of Constrained Objects
%R 2001-15
%D October 12, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Constrained objects, Modeling, Object-oriented, Constraint Logic Programming, Semantics
%Y Languages
%X This paper describes a compositional approach to modeling complex systems.
The building block, called a constrained object, is an object whose internal
state is governed by a set of (declarative) constraints. Especially in the
engineering domain, a constrained object models in a natural manner the internal
state and invariants of an engineering artifact, e.g., a resistor in
a circuit, a joint in a truss, a gear in a gear box, a heat exchanger
in a chemical process plant, etc. When several constrained objects are
aggregated to form a complex object, their internal states might further
have to satisfy interface constraints. The resulting behavior of the
system is obtained by a process of logical inference and constraint satisfaction.
Our work extends previous research by providing a richer modeling language,
with quantified and conditional constraints, as well as preferences.
We show that the paradigm of constrained objects is superior to
both a pure object-oriented language as well as a pure constraint language.
We present several examples in this paper, and also describe the formal
declarative and operational semantics of our language. The declarative
semantics for constrained objects is given in terms of a set-theoetic
approach, and the operational semantics makes use of top-down goal
reduction, constraint solving, and pruning according to preferences.
Wed, 21 Nov 2001 14:48:59 GMT
%U http://www.cse.buffalo.edu/tech-reports/2001-16.ps
%A Mahapatra, Nihar R.
%A Dutt, Shantanu
%T An Efficient Delay-Optimal Distributed Termination Detection Algorithm
%R 2001-16
%D November 27, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Broadcast, detection delay, distributed computation, k-ary n-cubes, message complexity, message passing, termination detection.
%Y F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
%X One of the important issues to be addressed when solving problems on
parallel machines or distributed systems is that of efficient
termination detection. Numerous schemes with different performance
characteristics have been proposed in the past for this purpose. These
schemes, while being efficient with regard to one performance metric,
prove to be inefficient in terms of other metrics. A significant
drawback shared by all previous methods is that they may take as long
as $\Theta(P)$ time to detect and signal termination after its actual
occurrence, where $P$ is the total number of processing elements.
Detection delay is arguably the most important metric to optimize,
since it is directly related to the amount of idling of computing
resources and to the delay in the utilization of results of the
underlying computation. In this paper, we present a novel termination
detection algorithm that is simultaneously optimal or near-optimal with
respect to all relevant performance measures on any topology. In
particular, our algorithm has a best-case detection delay of
$\Theta(1)$ and a finite optimal worst-case detection delay on any
topology equal in order terms to the time for an optimal one-to-all
broadcast on that topology---we derive a general expression for an
optimal one-to-all broadcast on an arbitrary topology, which is an
interesting new result in itself. On $k$-ary $n$-cube tori and meshes,
the worst-case delay is $\Theta(D)$, where $D$ is the diameter of the
architecture. Further, our algorithm has message and computational
complexities of $O(\max(MD,P))$ ($\Theta(\max(M,P))$ on the average for
most applications---the same as other message-efficient algorithms) and
an optimal space complexity of $\Theta(P)$, where $M$ is the total
number of messages used by the underlying computation. We also give a
scheme using counters that greatly reduces the constant associated with
the average message and computational complexities, but does not suffer
from the counter-overflow problems of other schemes. Finally, unlike
some previous schemes, our algorithm does not rely on FIFO ordering for
message communication to work correctly.
Wed, 05 Dec 2001 15:41:47 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-01.ps
%A Anand, Vishal
%A Chauhan, Sunit
%A Qiao, Chunming.
%T Sub-path Protection: A New Framework for Optical Layer Survivability and its Quantitative Evaluation
%R 2002-01
%D January 02, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K WDM networks, lightpath, wavelength routing, wavelength assignment, protection, restoration, path protection, link protection, sub-path protection, time to recover.
%X In wavelength division multiplexed networks (WDM) with 1:1 path
protection, a link-disjoint protection (backup) path is also set up at
the time of setting up a working (primary) path. Hence, the failure of
a single fiber-link does not cause huge data losses.
Typically, past research has considered two survivability paradigms:
(a) path protection/restoration and (b) link protection/restoration.
In path based schemes a backup path (which is link-disjoint with the primary path)
and wavelength is reserved during primary path setup, while in link based schemes,
for every link along the primary path a link disjoint backup for that link is found and reserved.
Each of these schemes have their advanatges and disadvantages in terms of capacity
utilization and restoration times.
In our study here, we introduce a new protection/restoration scheme called Sub-path protection. We show that this scheme has advantages over the traditional link and path based schemes. Also sub-path based schemes have the added advantge that they can survive multiple-link failures. Experimental results show that sub-path protection has interesting trade-off in terms of capacity utilization and recovery times. A network provider can take advantage of such a scheme to optimize his network carrying capacity and survivability.
Wed, 02 Jan 2002 16:09:56 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-02.ps
%A Ngo, Hung Q.
%T P-Species and the q-Mehler Formula
%R 2002-02
%D January 24, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K bijective proof, q-Mehler formula, species, Kibble-Slepian formula
%X In this paper, we present a bijective proof of the $q$-Mehler formula.
The proof is in the same style as Foata's proof of the Mehler formula.
Since Foata's proof was extended to show the Kibble-Slepian formula,
a very general multilinear extension of the Mehler formula,
we hope that the proof provided in this paper helps
find some multilinear extension of the $q$-Mehler formula.
The basic idea to obtain this proof comes from generalizing a result by
Gessel. The generalization leads to the notion of species on permutations and
the $q$-generating series for these species. The bijective proof is then
obtained by applying this new exponential formula to a certain type of
species on permutations and a weight preserving bijection relating this
species to the $q$-Mehler formula.
Some by-products of the $q$-exponential formula shall also be derived.
Thu, 24 Jan 2002 19:00:36 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-03.ps
%A Burhans, Debra T.
%T A Question Answering Interpretation of Resolution Refutation
%R 2002-03
%D January 31, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K theorem proving, question answering
%X Early use of theorem provers for question answering identified the
presence of an answer with the presence of a proof. Later work
recognized other types of answers whose existence was not associated with
proof, including intensional and conditional answers. This work is concerned
with the problem of defining what is meant by answer in the context of
resolution theorem proving. Clauses that are relevant are all identified as
answers, where relevance is determined with respect to a question and knowledge
base: any clause descended from the negated question is deemed relevant. This
definition of relevance is not in and of itself novel; rather, it is the way
in which the set of relevant clauses is partitioned that provides the key
to interpreting clauses as answers. A partition that divides the set of
relevant clauses into three classes, termed specific, generic, and
hypothetical, is proposed. These classes are formally distinguished by
the way in which literals in a clause share variables, with class membership
based on a property termed the closure of variable sharing of a literal. The
best answers are identified with relevant clauses that are, additionally,
informative. The informativeness of a clause is determined with respect to a
set of clauses termed the answer set, where an informative clause
contains information not conveyed by any other clause in the set. The
process of reasoning in search of a proof is recast as the process of
constructing a sequence of answer sets, starting with the empty set,
where each set in the sequence is at least as informative as the
previous set. It is this property that identifies question answering
as an anytime reasoning process. The complete answer set for a given
question and knowledge base is shown to be the fixed point of the
answer set generation function. While this potentially infinite set
may never be realized by a reasoner, the current answer set is
guaranteed to contain the most informative, relevant clauses
available at any point during reasoning. Different control
structures give rise to different answer set sequences, and may be
selectively employed to generate preferred answers as quickly as
possible. The definition of answer sets elucidates the importance of
separating answer search from answer selection, and highlights the
subjectivity of the notion of best answer as defined in many question
answering systems. The complete characterization of resolvents as
answers presented herein provides a framework that accounts for and
expands upon previous work on question answering in a resolution
theorem prover. In addition, it provides a foundation for further
work in question answering by establishing a context-independent
logical pragmatics of question answering.
Thu, 07 Feb 2002 13:46:31 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-04.ps
%A Garg, Ashim
%A Rusu, Adrian
%T Straight-line Drawings of Binary Trees with Linear Area and Good Aspect Ratio
%R 2002-04
%D April 24, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K tree drawing straight-line grid planar aspect ratio area
%X Trees are usually drawn planar, i.e. without any crossings.In this paper,
we investigate the area requirement of (non-upward) planar straight-line
drawings of binary trees. Let $T$ be a binary tree with $n$ vertices.
We show that $T$ admits a planar straight-line grid drawing with area
O(n) and with any prespecified aspect ratio in the range [1,n^\alpha],
where \alpha is a constant such that 0 <= \alpha < 1. We also show that
such a drawing can be constructed in O(nlog n) time.
Wed, 24 Apr 2002 19:34:51 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-05.ps
%A Garg, Ashim
%A Chanda, Amrita
%T Compact Encodings of Planar Orthogonal Drawings
%R 2002-05
%D April 24, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K encoding graph drawing orthogonal planar
%X We present time-efficient algorithms for encoding (and decoding) planar
orthogonal drawings of degree-4 and degree-3 biconnected and triconnected
planar graphs using small number of bits. We also present time-efficient
algorithms for encoding (and decoding) turn-monotone planar orthogonal
drawings.
Wed, 24 Apr 2002 19:34:55 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-08.pdf
%A Wu, Hongyi
%T iCAR : an Integrated Cellular and Ad hoc Relaying System
%R 2002-08
%D May 16, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K iCAR, cellular, ad hoc, wireless, mobile, network, integrated
%X The cellular concept was introduced for wireless communication to
address the problem of having scarce frequency resource. It is
based on the sub-division of geographical area to be covered by
the network into a number of smaller areas called cells. Frequency
reuse in the cells far away from each other increases system's
capacity. But at the same time, the cell boundaries prevent the
channel resource of a system to be fully available for users. No
access to Data Channels (or DCHs) in other cell by the
mobile host (or MH) limits the channel efficiency and
consequently the system capacity.
In this dissertation, we propose a new wireless system
architecture based on the integration of cellular and modern ad
hoc relaying technologies, called iCAR. It can efficiently balance
traffic loads and share channel resource between cells by using
Ad hoc relaying stations (ARSs) to relay traffic from one
cell to another dynamically. This not only increases the system's
capacity cost-effectively, but also reduces transmission power for
mobile hosts and extends system coverage. We analyze the system
performance in terms of the call blocking probability and queuing
delay using multi-dimensional Markov chains for the new call
requests and the call dropping probability for handoff requests,
and verify the analytical results via simulations. Our results
show that with a limited number of ARSs and some increase in the
signaling overhead (as well as hardware complexity), the call
blocking/dropping probability in a congested cell as well as the
overall system can be reduced. We also propose a seed-growing
approach for ARS placement, and discuss the upper bound on the
number of seed ARSs needed in the system. In order to
quantitatively evaluate ARS placement strategies, we introduce the
concept of a new performance metric called quality of (ARS)
coverage (QoC) for the comparison of various ARS placement
strategies, and propose three rules of thumb as guidelines for
cost-effective ARS placement in iCAR. Furthermore, we propose the
signaling and routing protocols for establishing QoS guaranteed
connections for IP traffic in iCAR. In particular, we discuss how
a relaying route between a MH and a BTS in a nearby cell can be
established via ARSs, and evaluate the performance of the
protocols in terms of request rejection rate and signaling
overhead through simulations. In addition, we propose a novel
concept called ``managed mobility" and address the ARS mobility
management in iCAR.
Fri, 17 May 2002 14:51:59 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-07.ps
%A Ngo, Hung Q.
%A Vu, Van H.
%T On Multi-rate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs
%R 2002-07
%D May 10, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multirate Rearrangeability, Clos Networks, Bipartite Graph Edge Coloring
%X Chung and Ross (SIAM J. Comput., \textbf{20}, 1991)
conjectured that the minimum number
$m(n,r)$ of middle-state switches for the symmetric $3$-stage Clos network
$C(n,m(n,r),r)$ to be rearrangeable in the multirate enviroment is
at most $2n-1$.
This problem is equivalent to a generalized version of the bipartite
graph edge coloring problem.
The best bounds known so far on this function $m(n,r)$ is
$11n/9 \leq m(n,r) \leq 41n/16 + O(1)$, for $n, r \geq 2$, derived
by Du-Gao-Hwang-Kim (SIAM J. Comput., \textbf{28}, 1999).
In this paper, we make several contributions. Firstly, we give evidence
to show that even a stronger result might hold.
In particular, we show that $m(n,r) \leq \lceil (r+1)n/2 \rceil$, which implies
$m(n,2) \leq \lceil 3n/2 \rceil$ -
stronger than the conjectured value of $2n-1$.
Secondly, we derive that $m(2,r) = 3$ by an elegant argument.
Lastly, we improve both the best upper and lower bounds given above:
$\lceil 5n/4 \rceil \leq m(n,r) \leq 2n-1+\lceil (r-1)/2 \rceil$,
where the upper bound is an improvement
over $41n/16$ when $r$ is relatively small compared to $n$.
We also conjecture that $m(n,r) \leq \lfloor 2n(1-1/2^r) \rfloor$.
Fri, 24 May 2002 17:54:44 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-09.ps
%A Ngo, Hung Q.
%T A New Routing Algorithm for Multirate Rearrangeable Clos Networks
%R 2002-09
%D May 22, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multirate rearrangeability, Clos Networks, Routing Algorithms
%X In this paper, we study the problem of finding routing algorithms on the
multirate rearrangeable Clos networks which use as few number of
middle-stage switches as possible.
We propose a new routing algorithm called the ``grouping algorithm''.
This is a simple algorithm which uses
fewer middle-stage switches than all known strategies, given that the
number of input-stage switches and output-stage switches are relatively
small compared to the size of input and output switches.
In particular, the grouping algorithm implies that
$m=2n+\lceil\frac{n-1}{2^k}\rceil$ is a sufficient number of middle-stage
switches for the symmetric $3$-stage Clos network $C(n,m,r)$ to
be multirate rearrangeable, where $k$ is any positive integer
and $r \leq n/(2^k-1)$.
Fri, 24 May 2002 17:55:57 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-10.ps
%A Ngo, Hung Q.
%T WDM Split Cross-connects and $3$-stage Clos Networks
%R 2002-10
%D July 09, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K WDM split cross-connects, Clos Networks, Routing Algorithms
%X In this paper, we first show that a
wavelength division multiplexed (WDM) split
cross-connect is strictly, wide-sense, or rearrangeably non-blocking if and
only if a corresponding $3$-stage Clos network is strictly, wide-sense
or rearrangeably non-blocking. This observation implies known results
on strictly non-blocking WDM split cross-connects and gives rise to new
results on wide-sense and rearrangeably non-blocking WDM split cross-connects.
We next introduce a routing algorithm for the Clos networks which show that
there are wide-sense non-blocking Clos networks which are not strictly
non-blocking. Hence, the same holds for the WDM split cross-connects.
We also consider another demand model for WDM split cross-connects and
present associated results. Routing algorithms for WDM split cross-connects
could be viewed as on-line and off-line algorithms to edge-color a class of
bipartite multi-graphs.
Tue, 16 Jul 2002 12:56:43 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-11.pdf
%A Anand, Vishal
%A Qiao, Chunming
%T Effect of Wavelength Conversion in Survivable Wavelength Routed Optical WDM Networks with Alternate Routing
%R 2002-11
%D June 06, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Optical network, Wavelength Division Multiplexing (WDM), Routing and Wavelength assignment (RWA), all-optical networks, wavelength conversion, network survivability, Traffic models, network blocking, alternate routing.
%X This study focuses on the routing and wavelength assignment in
wavelength-routed optical wavelength-divisioned -multiplexed networks
with circuit switching using wavelength conversion. Wavelength
conversion has been proposed for use in such networks to improve the
efficiency. The crucial factors which determine the efficiency of
using wavelength conversion as opposed to not using them, is the
number of wavelengths required to satisfy the network traffic demand
and the blocking of traffic demands by the network. In addition to
considering wavelength conversion, this study investigates the effect
of having multiple paths between each source-destination pair. We
consider the cases where protection is necessary for each of the
primary paths between every source-destination pair and hence a backup
path also has to be established during connection set up, and the case
when no protection is necessary. We study the effect of wavelength
conversion with different protection schemes. By simulating and
analyzing a large number of randomly generated networks we report
results of our study of the above schemes under both incremental and
dynamic traffic conditions. The study shows that utilizing wavelength
conversion has a considerable impact on reducing network blocking
under both incremental and dynamic traffic conditions, on the other
hand we find the difference in wavelength requirements of the various
schemes considered is minimal.
Wed, 07 Aug 2002 18:19:38 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-12.ps
%A Song, Yuqing
%T MONOTONIC TREE AND ITS APPLICATION TO MULTIMEDIA INFORMATION RETRIEVAL
%R 2002-12
%D August 16, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K monotonic tree, information retrieval, image retrieval, semantics
%X Contour trees have been used in geographic information systems (GIS) and
computer imag-ing to display scalar data. Contours are only defined for
continuous functions. For discrete data, a continuous function is first
defined as an interpolation of the data. Then a con-tour tree is defined
on this continuous function. In this dissertation, we first introduce a
new concept termed monotonic line, which models contour lines of discrete
functions. All monotonic lines in a discrete function form a tree, called
monotonic tree. As compared with contour trees, monotonic trees avoid the
step of interpolation, thus can be computed and manipulated more
efficiently. In addition, when used in image processing, monotonic trees
retrieve similar structures as contour trees do while reserving the
discreteness of image data. In computer imaging, the discreteness of
image data is one main factor which makes image processing and
understanding so difficult. The discreteness of image data itself is a
research topic.
Monotonic trees are used as a hierarchical representation of image
structures in content-based multimedia retrieval. Although a variety of
techniques have been developed for content-based image retrieval (CBIR),
automatic image retrieval by semantics still remains a challenging
problem due to the difficulty in object recognition and image understand-
ing. In this dissertation, we present a novel approach to support
semantics-based image retrieval on the basis of monotonic trees. The
structural elements of an image are modeled as branches (or subtrees) of
the monotonic tree. These elements are classified and clustered on the
basis of such properties as color, spatial location, coarseness, and
shape. Each cluster corresponds to some semantic feature. Following these
steps, images can be automatically annotated with category keywords. So
high-level (semantics-based) querying and brows-ing of images can be
supported. This scheme is applied to retrieve scenery features from
images and locate smooth background in images. Comparisons of
experimental results of this approach with conventional techniques using
low-level features demonstrate the effec-tiveness of our approach. In
future work, the monotonic tree model will be extended to general
semantic categories on both images and videos.
This dissertation has two main contributions. The first contribution is
the mathematical theory of monotonic tree, which is the first theory
addressing definitions, properties, and computations of contour
structures directly on discrete functions. The second contribution is
the application of monotonic tree model to semantics-based image retrieval.
The success of this model on scenery features and smooth background
implies its potential in analyzing general semantics of both images and
videos.
Tue, 20 Aug 2002 13:57:34 GMT
%U http://www.cse.buffalo.edu/tech-reports/90-21.ps
%A Shapiro, Stuart C.
%A Rapaport, William J.
%T The SNePS Family
%R 90-21
%D September 1, 1990
%I Department of Computer Science and Engineering, SUNY Buffalo
%K SNePS, semantic networks
%Y I.2 ARTIFICIAL INTELLIGENCE I.2.0 General-Cognitive simulation I.2.0 General-Philosophical foundations I.2.1 Applications and Expert Systems (see also H.4,J)-Natural language interfaces I.2.3 Deduction and Theorem Proving-Deduction (e.g., natural, rule-based) I.2.3 Deduction and Theorem Proving-Nonmonotonic reasoning and belief revision I.2.4 Knowledge Representation Formalisms and Methods I.2.4 Knowledge Representation Formalisms and Methods-Representation languages I.2.4 Knowledge Representation Formalisms and Methods-Semantic networks
%X SNePS, the Semantic Network Processing System, has been designed to be
a system for representing the beliefs of a natural language using
intelligent system (a ``cognitive agent''). It has always been the
intention that a SNePS-based
``knowledge base'' would ultimately be built, not by a programmer or
knowledge engineer entering representations of knowledge in some formal
language or data entry system, but by a human informing it using a
natural language (generally supposed to be English), or by the system
reading books or articles that had been
prepared for human readers.
This document describes the history of SNePS and some recent SNePS
projects.
It has been superseded by:
Shapiro, Stuart C., & Rapaport, William J. (1992), ``The SNePS Family,''
_Computers and Mathematics with Applications_, Vol. 23: 243-275.
Reprinted in Fritz Lehmann (ed.), _Semantic Networks in Artificial
Intelligence_ (Oxford: Pergamon Press, 1992): 243-275.
Mon, 09 Sep 2002 12:52:04 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-15.pdf
%A "Aygun, Ramazan Savas
%A Zhang, Aidong"
%T Rule-based Flexible Synchronization Modeling with Model Checking
%R 2002-15
%D December 05, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multimedia Synchronization, Model Checking, Synchronization Rules, Multimedia Presentations, Linear Temporal Logic.
%X Specification as in SMIL usually considers forward presentation
without considering interactions that change the course of the
presentation like backward and skip. Also, management of the
presentation constraints become harder when the course of the
presentation changes. In this report, we introduce a synchronization
model, termed RuleSync, for management of robust, consistent,
and flexible presentations that include a comprehensive set of
interactions. RuleSync manipulates synchronization rules that are
managed by Receiver-Controller-Actor (RCA) scheme where receivers,
controllers and actors are objects to receive events, to check
conditions and to execute actions, respectively. The correctness of
the model and the presentation is controlled with a technique called
{\it model checking}. Model checker PROMELA/SPIN tool is used for
automatic verification of the correctness of LTL (Linear Temporal
Logic) formulas.
%Z Thu, 05 Dec 2002 19:43:22 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-16.pdf
%A Aygun, Ramazan Savas
%A Yazici, Adnan
%T Modeling and Management of Fuzzy Information in Multimedia Database Applications
%R 2002-16
%D December 05, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multimedia Databases, Object-Oriented Data Model, ExIFO2,FOOD, Fuzziness, Uncertainty
%X In this report, we firstly present a conceptual data model for
multimedia database applications based on ExIFO2 model. The
ExIFO2 data model is chosen as the conceptual model since it
handles complex objects along with their uncertain and imprecise
properties. We enhanced this conceptual model in order to meet the
multimedia data requirements. In addition to uncertain and imprecise
information, we present a way of handling relationships among objects
of multimedia database applications. Events that might be extracted
from video or audio are also considered in this study. Secondly, the
conceptual model is mapped to a logical model, which the fuzzy
object-oriented data (FOOD) model is chosen, for storing and
manipulating the multimedia objects. This mapping is done in a way
that it preserves most of the information represented at the
conceptual level. Finally, in this study videos of football (soccer)
games is selected as the multimedia database application to show how
we handle crisp and fuzzy querying and retrieval of fuzzy and crisp
data from the database.
%Z Thu, 05 Dec 2002 19:43:24 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-17.ps
%A Boxer, Laurence
%T Expected Optimal Selection on the PRAM
%R 2002-17
%D December 03, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%K parallel algorithm, selection, parallel random access machine (PRAM), expected value, variance, Chebyshev's Inequality
%Y F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
%X The Selection Problem is the following: Given
a totally ordered set $S$ of $n$ items
and an integer $k$ such that $0 < k \leq n$, find the
$k$-th smallest member of $S$. A general algorithm
for a PRAM using optimal $\Theta(n)$ cost is not currently
known. In this paper, we show that if the input set $S$ is
uniformly (randomly) distributed on an interval $[a,b]$, then
the Selection Problem may be solved by an algorithm with the
following properties:
a) The expected cost is an optimal $\Theta(n)$.
b) The worst-case cost is $\Theta(n \log^{(2)} n)$, which matches that of
the most efficient algorithm in the literature~\cite{JaJa}.
%Z Thu, 05 Dec 2002 19:49:32 GMT
%U http://www.cse.buffalo.edu/tech-reports/98-08.ps
%A Yu, Dantong
%A Chatterjee, Surojit
%A Sheikholeslami, Gholamhosein
%A Zhang, Aidong
%T Efficiently Detecting Arbitrary Shaped Clusters in Very Large Datasets with High Dimensions
%R 98-08
%D November 1, 1998
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Data clustering, hash table, wavelet transform, very large databases
%X Multimedia databases typically contain data with very high dimensions.
Finding interesting patterns in these databases poses a very challenging
problem because of the scalability,lack of domain knowledge and complex
structures of the embedded clusters. High dimensionality adds severely to
the scalability problem. It has been shown that the wavelet-based
clustering technique, WaveCluster, is very efficient and effective in
detecting arbitrary shape clusters and eliminating noisy data for low
dimensional data. In this paper, we introduce {\it HiperWave}, an approach
to applying wavelet-based techniques for clustering high dimensional data.
Using a hash-based data structure, our approach makes intelligent use of
available resources to discover clusters in the dataset. We demonstrate
that the cost of clustering can be reduced dramatically yet maintaining
all the advantages of wavelet-based clustering. This hash-based data
representation can be applied for any grid-based clustering approaches.
Finally, we introduce a quantitative metric to measure the quality of the
resulting clusters. The experimental results show both effectiveness and
efficiency of our method on high dimensional datasets.
%Z Fri, 17 Jan 2003 13:39:30 GMT
%U http://www.cse.buffalo.edu/tech-reports/98-07.ps
%A Sheikholeslami, Gholamhosein
%A Wang, Wenjie
%A Zhang, Aidong
%T A Model of Image Representation and Indexing in Image Database Systems
%R 98-07
%D July 20, 1998
%I Department of Computer Science, SUNY Buffalo
%K content-based image retrieval, image decomposition
%X Image database systems need to be built to support effective and
efficient access to image data on the basis of content. In this process,
significant features must first be extracted from image data in their pixel
format. These features must then be classified and indexed to assist
efficient retrieval of image content. However, the issues central to
automatic extraction and indexing of image content remain largely an open
problem. In this paper, we investigate effective block-oriented image
decomposition structures to be used as a fundamental data model for
representing image content in large image databases. A hierarchical
structure $S^g$-tree is introduced to decompose database images. Each
decomposition of an image segment generates n subsegments of equal-size that
are uniformly distributed within the image segment. Our analysis illustrates
a special case of S^g-tree, nona-tree decomposition, when n equals 9, is an
effective and efficient block-oriented decomposition structure to facilitate
content-based image retrieval. Using S^g-tree structure to represent image
content in an image database, flexible access to partial contents of each
database image can be provided. Various types of content-based queries and
efficient image retrieval can then be supported through novel indexing and
searching approaches.
%Z Fri, 17 Jan 2003 13:40:20 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-01.pdf
%A "Tambay P.
%A Jayaraman B."
%T The Cob Programmer's Manual
%R 2003-01
%D February 05, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Constrained Objects, Constraints, Logic Programming, Object-Oriented, Modeling
%Y Languages
%X Cob is a programming language and execution environment based on the concept
of constrained objects for compositional and declarative modeling of
engineering structures. A constrained object is an object whose internal
state is governed by a set of (declarative) constraints. When several
constrained objects are aggregated to form a complex object, their internal
states might further have to satisfy interface constraints. The resultant
behavior of the complex object is obtained by logical inference and
constraint satisfaction. For the domain of
engineering modeling, the paradigm of constrained objects is superior to
both a pure object-oriented language as well as a pure constraint language.
While the concept of an object and its attributes
capture the structural aspects of an engineering entity, the concept of
constraint captures its behavioral properties.
Our current prototype includes tools for authoring constrained-object
class diagrams; a compiler that translates class diagrams to CLP(R) code;
and domain-specific visual interfaces for building and testing constrained
objects. This manual describes version 1.0 of the Cob programming language.
%Z Wed, 05 Feb 2003 17:22:05 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-02.ps
%A Glasser, Christian
%A Selman, Alan L.
%A Sengupta, Samik
%A Zhang, Liyu
%T Disjoint NP-Pairs
%R 2003-02
%D February 17, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Disjoint NP-pairs, promise problems, oracles, proof systems, P-separable
%X We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists a disjoint pair
of NP-sets that is NP-hard. We show under reasonable
hypotheses that nonsymmetric disjoint NP-pairs exist,
which provides additional evidence for the existence of
P-inseparable disjoint NP-pairs.
We construct an oracle relative to which the class of
disjoint NP-pairs does not have a complete pair,
an oracle relative to which optimal proof systems exist, hence
complete pairs exist, but no pair is NP-hard, and an oracle
relative to which complete pairs exist, but optimal proof systems do
not exist.
%Z Thu, 20 Feb 2003 14:53:04 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-03.pdf
%A Wu, Yimin
%A Zhang, Aidong
%T Adaptively Discovering Meaningful Patterns in High-Dimensional Nearest Neighbor Search
%R 2003-03
%D April 08, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%Y Database
%X To query high-dimensional databases, similarity search (or k nearest neighbor search) is the most extensively used method. However, since
each attribute of high dimensional data records only contains very small amount of information, the distance of two high-dimensional records may not always correctly reflect their similarity. So, a multi-dimensional
query may have a k-nearest-neighbor set which only contains few
relevant records. To address this issue, we present an adaptive pattern
discovery method to search high dimensional data spaces both effectively and efficiently. With our method, the user is allowed to participate in the database search by labeling the returned records
as relevant or irrelevant. By using user-labeled data records as training samples, our method employs an adaptive pattern discovery technique
to learn the distribution patterns of relevant records in
the data space, and drastically reduces irrelevant data records. From the reduced data set, our approach returns the top-k nearest neighbors of the query to the user -- this interaction between the user and the DBMS
can be repeated multiple times. To achieve the adaptive pattern discovery,
we employ a pattern classification algorithm called random forests, which is a machine learning algorithm with proven good performance on many traditional classification problems.By using a novel two-level resampling method, we adapt the original random forests to an interactive algorithm, which achieves noticeable gains in efficiency over the original algorithm. We empirically compare our method with previously well-known related approaches on large-scaled, high-dimensional and real-world data sets, and report promising results of our method.
%Z Wed, 09 Apr 2003 12:12:30 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-04.ps
%A Glasser, C.
%A Selman, A
%A Sengupta, S.
%T Reductions between Disjoint NP-Pairs
%R 2003-04
%D April 21, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K NP-pairs, reductions, smart reductions, uniformly enumerable, oracle
%X We prove that all of the following assertions are equivalent:
There is a many-one complete disjoint NP-pair;
there is a strongly many-one complete disjoint NP-pair;
there is a Turing complete disjoint NP-pair such that all reductions
are smart reductions;
there is a complete disjoint NP-pair for one-to-one, invertible reductions;
the class of all disjoint NP-pairs is uniformly enumerable.
Let $A$, $B$, $C$, and $D$ be nonempty sets belonging to NP.
A {\em smart} reduction between the disjoint NP-pairs
$(A, B)$ and $(C, D)$ is a Turing reduction with the additional property
that if the input belongs to $A \cup B$, then all queries belong to
$C \cup D$. We prove
under the reasonable assumption
$\mathrm{UP} \cap \mathrm{co}\mbox{-}\mathrm{UP}$ has a
P-bi-immune set that there exist
disjoint NP-pairs $(A, B)$ and $(C, D)$ such that $(A, B)$ is truth-table
reducible to $(C, D)$, but there is no smart reduction between them.
This paper contains several additional separations of reductions between
disjoint NP-pairs.
We exhibit an oracle relative to which DisjNP has a truth-table-complete
disjoint NP-pair, but has no many-one-complete disjoint NP-pair.
%Z Tue, 22 Apr 2003 14:44:06 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-05.pdf
%A Garg, Ashim
%A Rusu, Adrian
%T Area-Efficient Order-Preserving Planar Straight-line Drawings of Ordered Trees
%R 2003-05
%D May 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph drawing, order-preserving, straight-line
%X Ordered trees are generally drawn using order-preserving planar straight-line grid drawings.
We therefore investigate the area-requirements of such drawings, and
present several results:
Let $T$ be an ordered tree with $n$ nodes. Then:
\begin{itemize}
\item $T$ admits an order-preserving planar straight-line grid drawing with $O(n\log n)$ area.
\item
If $T$ is a binary tree, then $T$ admits an order-preserving planar straight-line grid drawing with $O(n\log \log n)$ area.
\item
If $T$ is a binary tree, then $T$ admits an order-preserving {\em upward} planar straight-line grid drawing with {\em optimal} $O(n\log n)$ area.
\end{itemize}
We also study the problem of drawing
binary trees with user-specified arbitrary aspect ratios. We show
that an ordered binary tree $T$ with $n$ nodes admits an order-preserving planar straight-line grid drawing $\Gamma$ with width $O(A+\log n)$, height $O((n/A)\log A)$, and area
$O((A+\log n)(n/A)\log A)=O(n\log n)$, where $2\leq A\leq n$ is any
user-specified number.
Also note that all the drawings mentioned above can be
constructed in $O(n)$ time.
%Z Fri, 16 May 2003 19:44:36 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-14.pdf
%A Garg, Ashim
%A Rusu, Adrian
%T Straight-line Drawings of General Trees with Linear Area and Arbitrary Aspect
Ratio
%R 2002-14
%D May 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph drawing, straight-line, linear area
%X Trees are usually drawn planar, i.e. without any crossings.
In this paper, we investigate the area requirement of (non-upward) planar straight-
line grid
drawings of general trees.
A {\em degree-d tree} is one in which each node has at most $d$ edges incident on it.
Let $T$ be a degree-$d$ tree with $n$ nodes, such that $d =O(n^\delta)$, where $0 \le
\delta < 1/2$ is a constant.
We show that $T$ admits a planar straight-line grid drawing with area
$O(n)$ and with any pre-specified aspect ratio in the range $[n^{-\alpha},n^\alpha]$,
where $\alpha$ is a constant such that $0 \leq \alpha < 1$. We also show that such a
drawing can be
constructed in $O(n\log n)$ time. In particular, our result shows
that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1)
is simultaneously achievable for such drawings.
%Z Mon, 19 May 2003 13:33:10 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-06.ps
%A "Zhang, Huaming
%A He, Xin"
%T Canonical Ordering Tree and Its Applications in Graph Drawing
%R 2003-06
%D May 30, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph, canonical ordering tree, grid embedding, visibility representation
%X We study the properties of Schnyder's realizers and canonical ordering trees of plane graphs. Based on these newly
discovered properties, we obtain compact drawings of two styles for any plane graph G with n vertices. First we show that G has a
visibility representation with height at most 15n/16. This improves the previous best bound of (n-1).
Second, we show that every plane graph G has a straight-line grid embedding on an (n-\Delta_0-1) \times (n-\Delta_0-1) grid, where
\Delta_0 is the number of cyclic faces of G with respect to its minimum realizer. This improves the previous best bound of
(n-1) \times (n-1). We also study the properties of the regular edge labeling of
4-connected plane triangulation. Based on these properties, we show that every such a graph has a canonical
ordering tree with at most (n+1)/2 leaves. This improves the previously known bound of (2n+1)/3.
We show that every 4-connected plane graph has a visibility representation with height at most (3n)/4.
All drawings discussed in this paper can be obtained in linear time.
%Z Tue, 03 Jun 2003 15:02:14 GMT
%U http://www.cse.buffalo.edu/tech-reports/2002-13.ps
%A Zhang, Huaming
%A He, Xin
%T On Even Triangulations of 2-Connected Embedded Graphs
%R 2002-13
%D July 06, 2002
%I Department of Computer Science and Engineering, SUNY Buffalo
%X Recently, Hoffmann and Kriegel proved an important combinatorial
theorem [HK96]: Every 2-connected bipartite plane graph $G$
has a triangulation in which all vertices have even degree
(it's called an even triangulation). Combined with a classical
Whitney's Theorem, this result implies that every such a graph
has a 3-colorable plane triangulation. Using this theorem,
Hoffmann and Kriegel significantly improved the upper bounds of
several art gallery and prison guard problems.
A complicated O(n^2) time algorithm was obtained in
[HK96] for constructing an even triangulation of G.
Hoffmann and Kriegel conjectured that there is an O(n^{3/2})
time algorithm for solving this problem.
In this paper, we develop a simple proof of the above theorem.
Our proof reveals and relies on a natural correspondence between
even triangulations of $G$ and certain orientations of
G. Based on this new proof, we obtain a very simple O(n) time
algorithm for finding an even triangulation of G. We also extend
our proof to show the existence of even triangulations for similar
graphs on high genus surface.
%Z Tue, 03 Jun 2003 15:23:17 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-07.pdf
%A Aygun, Ramazan Savas
%T Spatio-Temporal Browsing of Multimedia Presentations
%R 2003-07
%D May 08, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Multimedia Presentations, Spatial Browsing, Temporal Browsing, Sprite Generation, Multimedia Synchronization
%X Emerging applications like asynchronous distant learning and
collaborative engineering require organization of media streams as
multimedia presentations. The browsing of presentations enables
interactive surfing of the multimedia documents. We propose
spatio-temporal browsing of multimedia presentations in the sense that
browsing can be performed both in the spatial and temporal domain.
The spatial browsing is provided by incorporation of camera controls
like panning, tilting, and zooming. Panoramic images enable a kind of
browsing by storing the image at high resolutions from various angles.
However, the generation of high resolution sprite (mosaic) from
digital video is not an easy task. Since the video data may also
exist in a compressed format, new features like boundaries have to be
extracted from the compressed video. We consider compressed data that
is generated by Discrete Cosine Transform (DCT), which has been used
in MPEG-1, MPEG-2, MPEG-4, and H263.1. Global Motion Estimation (GME)
has been improved for videos where motion does not occur frequently.
Motion sensors, which are sensitive pixels to motion, are proposed to
indicate the existence of motion and yield quick approximation to the
motion. Motion sensors reduce the amount of computations of the
hierarchical evaluation of low-pass filtered images in iterative
descent methods. The generated sprites are usually more blurred than
original frames due to image warping stage and errors in motion
estimation. The temporal integration of images is performed using the
histemporal filter based on the histogram of values within an
interval. The initial frame in the video sequence is registered at a
higher resolution to generate high resolution sprite. Instead of
warping of each frame, the frames are warped into the sprite at
intervals to reduce the blurring in the sprite. We also introduce a
new sprite called conservative sprite where new pixels are
exclusively mapped on the sprite during temporal integration
phase. The sprite pyramid is introduced to handle sprite at
different resolutions. To measure the quality of the sprite, a new
measure called sharpness is used to estimate the blurring in the
sprite. The generated sprite is used for spatial browsing.
On the other hand, temporal browsing is closely related with the
synchronization of different streams. The power of synchronization
models is limited to the synchronization specifications and user
interactions. The proposed synchronization model is an event-based
model that can handle time-based actions while enabling user
interactions like backward and skip. The synchronization model
processes the synchronization rules based on
Event-Condition-Action (ECA) rules. Since the structure of a
synchronization rule is simple, the manipulation of the rules can be
performed easily in existence of user interactions. The
synchronization model uses Receiver-Controller-Actor (RCA) scheme to
execute the rules. In RCA scheme, receivers, controllers, and actors
are objects to receive events, to check conditions, and to execute
actions, respectively. The synchronization rules can easily be
regenerated from SMIL expressions. The deduction of synchronization
rules is based on author's specification. A middle layer between the
specification and the synchronization model assists the
synchronization model to provide user interactions while keeping the
synchronization specification minimal. We call this middle
layer as middle-tier. The middle-tier for multimedia
synchronization handles synchronization rules that can be extracted
explicitly from the user specification and synchronization rules that
can be deduced implicitly from explicit synchronization rules. The
synchronization model also generates a virtual timeline to manage the
user interactions that change the course of the presentation. The
verification and correctness of schedules are also important. The
general methods to check the correctness of a specification are
theoretical verification, simulation, and testing. Model checking is a
technique that automatically detects all the states that a model can
enter and checks the truthness of well-formed formulas. Moreover
model checking can present contradictory examples if the formulas are
not satisfied. PROMELA/SPIN tool has
been used for model checking to check LTL (Linear Temporal Logic)
formulas. These formulas can automatically be generated and verified.
%Z Tue, 03 Jun 2003 18:27:42 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-08.pdf
%A Rusu, Adrian
%T Area-Efficient Grid Drawings of Graphs
%R 2003-08
%D August 16, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Graph Drawing, Planar, Straight-line, Tree, Outerplanar, Area, Aspect Ratio, Information Visualization, Computational Geometry
%Y Algorithms; Theory
%X The visualization of relational information is concerned with the presentation of
abstract information about relationships between various entities.
It has many applications in diverse domains such as software engineering, biology,
civil engineering, and cartography.
Relational information is typically modeled by an abstract graph, where vertices are
entities and edges represent relationships between entities.
The aim of graph drawing is to automatically produce drawings of graphs which clearly
reflect the inherent relational information.
This thesis is primarily concerned with problems related to the automatic generation
of area-efficient grid drawings of trees and outerplanar graphs, which are important
categories of graphs.
The main achievements of this thesis include:
\begin{enumerate}
\item An algorithm for producing planar straight-line grid drawings of binary trees
with optimal linear area and with user-defined arbitrary aspect ratio,
\item An algorithm for producing planar straight-line grid drawings of degree-$d$
trees with $n$ nodes, where $d=O(n^{\delta})$ and $0 \le \delta < 1/2$ is a constant,
with optimal linear area and with user-defined arbitrary aspect ratio,
\item An algorithm which establishes the currently best known upper bound, namely
$O(n \log n)$, on the area of order-preserving planar straight-line grid drawings of
ordered trees,
\item An algorithm which establishes the currently best known upper bound, namely
$O(n \log \log n)$, on the area of order-preserving planar straight-line grid
drawings of ordered binary trees,
\item An algorithm for producing order-preserving upward planar straight-line grid
drawings of ordered binary trees with optimal $O(n \log n)$ area,
\item An algorithm which establishes the trade-off between the area and aspect ratio
of order-preserving planar straight-line grid drawings of ordered binary trees, in
the case when the aspect ratio is arbitrarily defined by the user, and
\item An algorithm for producing planar straight-line grid drawings of outerplanar
graphs with $n$ vertices and degree $d$ in $O(dn^{1.48})$ area. This result shows for
the first time that a large category of outerplanar graphs, namely those with degree
$d=O(n^{\delta})$, where $0 \le \delta < 0.52$ is a constant, can be drawn in sub-
quadratic area.
All our algorithms are time-efficient. More specifically, algorithms 1 and 2 run in
$O(n \log n)$ time each, and algorithms 3, 4, 5, 6, and 7 run in $O(n)$ time each.
%Z Tue, 19 Aug 2003 16:40:25 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-10.pdf
%A Zhang, Huaming
%A He, Xin
%T Improved Visibility Representation of Plane Graphs
%R 2003-10
%D August 27, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Graph; Visibility Representation
%X In a visibility representation (VR for short) of a plane graph $G$,
each vertex of $G$ is represented by a horizontal line segment such
that the line segments representing any two adjacent vertices of $G$
are joined by a vertical line segment. Rosenstiehl and Tarjan \cite{RT86},
Tamassia and Tollis \cite{TT86} independently gave linear time VR
algorithms for 2-connected plane graph.
Using this approach, the height of the VR is bounded by
$(n-1)$, the width is bounded by $(2n-5)$. After that, some work have been
done to find a more compact VR. Kant and He \cite{KH97}
proved that a 4-connected plane graph has a VR with width bounded by $(n-1)$.
Kant \cite{Kant97} reduced the width bound to
$\lfloor \frac{3n-6}{2} \rfloor$ for general plane graphs.
Recently, using a sophisticated greedy algorithm, Lin et. al.
reduced the width bound to
$\lfloor \frac {22n-42} {15} \rfloor$ \cite{LLS03}.
In this paper, we prove that any plane graph $G$ has a VR with width
at most $\lfloor \frac {13n-24}{9} \rfloor$, which can be constructed
by using the simple standard VR algorithm in \cite{RT86,TT86}.
%Z Tue, 02 Sep 2003 18:56:04 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-09.pdf
%A Chinchani, Ramkumar
%A Pramanik, Suranjan
%A Garg, Ashish
%T Handling Failures and DOS Attacks Using Network Device Groups
%R 2003-09
%D July 15, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Fault tolerant networking; Security
%Y Reliability; Security
%X With the growing popularity of the Internet and the falling prices of network
devices, it is not unusual to find multiple network devices in a computer system.
Technologies such as Internet connection sharing and NAT are commonly being used by
end users to make network connectivity more viable. In this paper, we point out that
this implicit redundancy can be used to achieve fault tolerance. It is known that
network devices can be grouped to achieve failover support. However, the focus has
been limited to localized factors and device failures. In the context of the
Internet, security against DOS attacks also becomes an important issue. While the use
of multiple network devices provides a good solution for device failure, it doesn t
guarantee a good defense against DOS attacks. We show that computer systems can
become tolerant to DOS attacks if some external factors are also taken into account.
The main contribution of this paper is a systematic and comprehensive solution that makes a best effort to provide reliable network connectivity even when network
device failures and DOS attacks occur. We have implemented and tested this technique
in Linux and report our findings.
%Z Tue, 02 Sep 2003 19:18:17 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-11.pdf
%A Garg, Ashim
%A Rusu, Adrian
%T Area-Efficient Drawings of Outerplanar Graphs
%R 2003-11
%D September 18, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K graph, outerplanar, area, planar, straight-line
%X It is well-known that a planar graph with $n$ nodes admits a planar
straight-line grid drawing with $O(n^2)$ area, and in the worst
case it requires $\Omega(n^2)$ area. It is also known that a binary tree
with $n$ nodes admits a planar straight-line grid drawing with $O(n)$ area. Thus,
there is wide gap between the $\Theta(n^2)$ area-requirement
of general planar graphs and the $\Theta(n)$ area-requirement of binary
trees. It is therefore important to investigate special categories of
planar graphs to determine if they can be drawn in $o(n^2)$ area.
Outerplanar graphs form an important category of planar graphs. We
investigate the area-requirement of planar straight-line grid drawings
of outerplanar graphs. Currently the best known bound on the
area-requirement of such a drawing of an outerplanar graph with $n$
vertices is $O(n^2)$, which is that same as for general planar graphs.
Hence, a fundamental question arises that can be draw an outerplanar
graph in this fashion in $o(n^2)$ area?
In this paper, we provide a partial answer to this question by proving
that an outerplanar graph with $n$ vertices and degree $d$ can be drawn in
this fashion in area $O(dn^{1.48})$ in $O(n\log n)$ time. This implies
that an outerplanar graph with $n$ vertices and degree $d$, where
$d= o(n^{0.52})$, can be drawn in this fashion in $o(n^2)$ area.
From a broader perspective, our contribution is in showing a
sufficiently large natural category of planar graphs that can be drawn in
$o(n^2)$ area.
%Z Mon, 22 Sep 2003 14:44:07 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-13.pdf
%A Yu, Xiang, Qiao, Chunming , Liu, Yong and Towsley, Don
%T Performance Evaluation of TCP Implementations in OBS Networks
%R 2003-13
%D July 1, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Optical Burst Switching, TCP, Reno, SACK, Performance modeling
%Y Computer Communications Networks, Network Protocol, C.2.2
%X Since TCP traffic is and may remain as the most popular traffic
type in the Internet, it is important to evaluate the performance
of TCP in networks employing optical burst switching (OBS), a
promising paradigm for the next generation Optical Internet. This
work is the first comprehensive study of the TCP performance in
OBS networks. Our results provide valuable insights into the
interactions between the TCP congestion control mechanism and
OBS-specific mechanisms such as burst assembly/disassembly and
buffer-less burst switching. In particular, we identify various
factors that result in TCP throughput gains and penalties, and
determine optimal burst assembly times to be used in OBS networks.
In addition, TCP throughput models are developed for the three
most popular TCP implementations, i.e., SACK, Reno and New-Reno,
and are validated through simulations.
%Z Mon, 12 Jan 2004 20:47:53 GMT
%U http://www.cse.buffalo.edu/tech-reports/2003-12.pdf
%A Garg, Ashim
%A Rusu, Adrian
%T A More Practical Algorithm for Drawing Binary Trees in Linear Area with ArbitraryAspect Ratio
%R 2003-12
%D September 19, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K tree, drawing, area, aspect ratio, straight-line, planar
%X Trees are usually drawn planar, i.e. without any edge-crossings.
It is important to minimize the area of a drawing, so that it
can fit within the given drawing-window. It is also important
to give user some control over the aspect ratio of the drawing,
so that she can display the drawing in a drawing-window with
arbitrary width-to-height ratio. In a grid drawing, each node
is assigned integer coordinates.
In~\cite{gr-sldbt-02}, it was shown that any binary tree with $n$ nodes admits a planar straight-line grid drawing with area
$O(n)$ and with any pre-specified aspect ratio in the range
$[n^{-\epsilon},n^\epsilon]$, where $\epsilon$ is any constant such that
$0 < \epsilon < 1$. It was also shown that such a drawing can be
constructed in $O(n\log n)$ time. In particular, this showed
that optimal area (equal to $O(n)$) and optimal aspect ratio (equal to 1)
is simultaneously achievable for such drawings.
However, the algorithm of~\cite{gr-sldbt-02} is not suitable for practical
use. The main problem is that the constant $c$ hidden in the ``Oh''
notation for area is quite large (for example, it can be as high as 3900).
In this paper, we make several non-trivial practical improvements to
the algorithm, which make it suitable for practical use. We have also
conducted experiments on this newer version of the algorithm for
randomly-generated binary trees with up to 50,000 nodes, and for complete
binary trees with up to $65,535=2^{16}-1$ nodes. Our experiments show that
it constructs area-efficient drawings in practice, with area at most
8 times the number of nodes for complete binary trees, and at most
10 times the number of nodes for randomly-generated binary trees.
%Z Tue, 02 Mar 2004 14:42:54 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-06.pdf
%A Ghosh, Joy
%A Kumar, Vivek
%A Wang, Xin
%A Qiao, Chunming
%T BTSpin - Single Phase Distributed Bluetooth Scatternet Formation
%R 2004-06
%D December 13, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Bluetooth, Wireless Networking, Scatternet formation
%Y algorithm, design
%X The Bluetooth standard specifies the formation of
Piconets but only alludes to the possibility of joining several of
these Piconets to form a Scatternet. In an attempt to formalize
this Scatternet formation process, several schemes have been
suggested. The centralized schemes suggested so far, require all
the nodes to be in the radio range of each other (i.e. single hop)
to ensure the correctness of their algorithm. To address multi
hop scenarios, the distributed schemes suggested so far, usually
require multiple phases to form a Scatternet. In particular, they
need a considerable amount of time and energy in the topology
discovery phase, during which the nodes exchange one hop or
even two hop neighbor information. This also restricts these
schemesĀ? ability to efficiently cope with fully dynamic topology
changes due to nodes joining/leaving. In this work, we propose a
novel and practical approach called BlueToothSpin (BTSpin) to
overcome several of the above mentioned shortcomings. BTSpin
has a single phase, wherein the nodes concurrently form Scatternets
and route data traffic. Our simulations show that BTSpin
has a low Scatternet formation delay, and can form efficient
multi-hop Scatternets when nodes arrive both Incrementally and
En Masse (all at the same time). The total number of Piconets
formed and the average number of roles per node (number of
Piconets a node participates in) are also shown to be lower than
other proposed mesh based protocols.
%Z Mon, 22 Mar 2004 19:01:39 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-03.ps
%A Glasser, Christian
%A Pavan, A.
%A Selman, Alan
%A Sengupta, Samik
%T Properties of NP-Complete Sets
%R 2004-03
%D January 15, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K clossness, immunity, pseudorandom generators, secure one-way permutations, disjoint NP-pairs
%X We study several properties of sets that are complete for NP.
We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse
set, then $L - S$ is $\redm$-hard for NP. We demonstrate existence of
a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$
such that for every $L \in \NP - \P$, $L - S$ is not many-one-hard for NP.
Moreover, we prove for every $L \in \NP - \P$, that there exists a
sparse $S \in \EXP$ such that $L - S$ is not many-one-hard for NP.
Hence, removing sparse information in P from a complete set leaves the
set complete, while removing sparse information in EXP from a complete
set may destroy its completeness. Previously, these properties were known only for exponential time complexity classes.
We use hypotheses about pseudorandom generators and secure one-way permutations to resolve longstanding open questions about whether NP-complete sets are immune. For example, assuming that pseudorandom generators and secure one-way permutations exist,
it follows easily that NP-complete sets are not p-immune.
Assuming only that secure one-way permutations exist, we prove that
no NP-complete set is $\DTIME(2^{n^\epsilon})$-immune. Also, using these
hypotheses we show that no NP-complete set is quasipolynomial-close to P.
We introduce a strong but reasonable hypothesis and infer from it that
disjoint Turing-complete sets for NP are not closed under union. Our hypothesis
asserts existence of a $\UP$-machine $M$ that accepts $0^*$ such
that for some $0 < \epsilon < 1$, no $2^{n^{\epsilon}}$ time-bounded
machine can correctly compute infinitely many accepting
computations of $M$. We show that if
$UP \cap coUP$ contains $\DTIME(2^{n^\epsilon})$-bi-immune sets, then
this hypothesis is true.
%Z Mon, 22 Mar 2004 19:06:47 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-02.pdf
%A Zhao, Dan
%T An Integrated Framework for Concurrent Test and Wireless Control in Complex SoCs
%R 2004-02
%D December 30, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%K SOC test, test cost, resource partitioning, test scheduling, test access, wireless test control
%Y Design; Reliability
%X System-on-chip (SoC) is evolving as a new design style, where an entire system is built by reusing pre-designed, pre-verified IP (intellectual property) cores.
Embedded with numerous heterogeneous and complex IP cores, an SoC can be viewed as an interconnected network of various functional modules. This new design style
shortens time-to-market while meeting various design requirements, such as high performance, low power, and low cost, compared to the traditional system-on-board (SoB) design.
In the meantime, however, embedded core-based SoC test becomes a challenging task due to IP protection. In particular, there are three major issues to be addressed in SoC test:
(1) a test access path needs to be constructed for each core to propagate test stimulus and collect test responses, (2) one needs to partition test resources and schedule IP cores
to achieve maximum parallelism, and (3) a test control network is needed to initialize different test resources used in the test application and observe the corresponding test
results at appropriate instants. In this dissertation, we develop cost-effective SoC test and diagnosis solutions from various crucial aspects, such as test time, test access
architecture, and memory depth on automatic test equipment (ATE). It is the very first work that introduces radio frequency (RF) technology into SoC test control for the
forthcoming billion-transistor era. We mainly address two research issues: integrated testability design and optimization of SoC test solutions, and on-chip wireless test control
network design. We first develop a general test model for SoC testability analysis, test scheduling, and test diagnosis. We then propose several test scheduling algorithms with
the consideration of various test constraints such as resource sharing, power dissipation, and fault coverage, and develop an integrated framework that combines wrapper design,
test access mechanism (TAM) configuration, and test scheduling. More specifically, we propose a fault model oriented test set selection scheme and formulate the test scheduling
as a shortest path problem with the feature of evenly balanced resource usage. We also propose a dynamic test partitioning technique based on the test compatibility graph to
address the power-constrained test scheduling problem. Furthermore, we develop an integrated framework to handle constrained scheduling in a way that constructs core access
paths and distributes TAM bandwidth among cores, and consequently configures the wrapper scan chains for TAM width adaptation. Using the "Radio-on-Chip" technology, we introduce
a novel test control network to transmit control signals chip-wide by RF links. We propose three types of wireless test control architectures, i.e., a miniature wireless local
area network, a multihop wireless test control network, and a distributed multihop wireless test control network. The proposed architectures consist of three basic components, namely the test
scheduler, the resource configurators, and the RF nodes supporting the communication between the scheduler and the IP cores. Under the multilevel tree structure, the system
optimization is performed on control constrained resource partitioning and distribution. Several challenging system design issues such as RF nodes placement, clustering, and
routing, are studied along with integrated resource distribution (including not only the circuit blocks to perform testing, but also the on-chip RF nodes for intra-chip
communication) and test scheduling (concurrent core testing as well as interconnect testing). Cost oriented optimization technique is developed which addresses several highly
interdependent design issues to achieve the minimum overall testing cost.
%Z Mon, 22 Mar 2004 19:06:54 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-04.ps
%A Tambay P. and Jayaraman B.
%T Implementation Techniques for Constrained Objects
%R 2004-04
%D February 29, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K constraints, objects, translation, partial evaluation, debugging, constraint satisfaction
%X This paper presents the implementation of constrained objects.
A constrained object is an object whose attributes are subject to
constraints. When a constrained object aggregates other objects,
it may impose further constraints on the attributes of these objects.
As shown in a recent paper, this programming
paradigm is very useful for modeling various systems,
especially in the engineering domain.
Here, a constraint may be simple,
quantified, conditional, or non-linear. A constrained object (Cob)
program consists of Java-like class definitions except that
methods are replaced by constraints. These
constraints may also refer to user-defined CLP-like predicates.
Hence our implementation is based on a translation from Cob classes
to CLP predicates. Execution of the translated CLP predicates will
not yield adequate performance for large-scale systems. Hence
we develop a partial execution technique for optimized code generation.
This approach also enables developing a visual debugger
for Cob programs and also interfacing with a system such as Maple for
solving non-linear constraints. The paper presents the syntax and
examples of Cob programs, and the scheme for translation and partial
execution. The techniques described in this paper have been
implemented.
%Z Mon, 22 Mar 2004 19:07:02 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-05.ps
%A Raux R.J. and Jayaraman B.
%T Modeling Dynamic Systems with Constrained Objects
%R 2004-05
%D February 29, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K constraints, objects, dynamic system, state change, temporal constraints
%X This paper examines the application of constrained objects for
modeling dynamic systems. A dynamic system is one whose state
changes with time. A constrained object is an object whose internal
state is governed by a set of (declarative) constraints. When
a complex system is modeled as a set of constrained objects, the
resultant behavior is deduced through a process of constraint satisfaction.
In previous research, we explored the paradigm of constrained objects
for modeling the steady-state behavior of systems. In this paper, we
present extensions that allow time-depedent behavior to be modeled
as well. A key feature of our proposed approach is that of a time-series
variable whose values are in accordance with specified constraints.
We provide examples from diverse domains (AC circuits, hydrological
modeling, and sensor networks) to illustrate our approach. We are
developing a prototype that includes a compiler that translates Cob
programs into Sicstus Prolog Objects with CLP(R) constraints.
%Z Mon, 22 Mar 2004 19:07:05 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-01.ps
%A Selman, A.
%A Sengupta, S.
%T Polylogarithmic-round Interactive Proofs for coNP
%R 2004-01
%D September 02, 2003
%I Department of Computer Science and Engineering, SUNY Buffalo
%Z Mon, 22 Mar 2004 19:59:48 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-08.pdf
%A Ghosh, Joy
%A Philip, Sumesh
%A Qiao, Chunming
%T ORBIT Mobility Framework and Orbit Based Routing (OBR) Protocol for MANET
%R 2004-08
%D July 12, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Mobility models, Routing protocol, Ad hoc wireless networks, Performance analysis
%X A major hurdle in evaluating routing protocols for a
Mobile Ad Hoc NETwork (MANET) is the appropriate modeling
of the mobility of wireless nodes. Although the pure random
nature of the Random Waypoint model lends itself for theoretical
study of MANET protocols, it is not suitable for modeling the
movements of mobile nodes in real scenarios. To this end, several
entity, group and scenario based mobility models and frameworks
have been proposed in literature for representing node mobility.
Some of these models cater to only short term applications of ad
hoc networks (e.g., disaster, military), while others are based on
complex scenario parameters (e.g., buildings, pathways).
In this paper, we propose a novel mobility framework called
ORBIT. In addition to generating a more practical mobility
pattern based on sociological movement of users, ORBIT can also
integrate all the work mentioned above into a single framework.
The proposed ORBIT framework is applicable to all kinds of
wireless networks (cellular, ad hoc etc.) and is also capable of
generating different models to suit either short term or long
term network mobility in various scenarios. We also propose
an Orbit Based Routing (OBR) protocol for MANETs, which
takes advantage of the ORBIT framework and outperforms
other routing protocols like Dynamic Source Routing (DSR) and
Location Aided Routing (LAR).
%Z Tue, 13 Jul 2004 18:15:44 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-07.ps
%A Karthik Sundararaman
%T Design For Manufacturability - Fault Model Extensions for RF Circuits with
an Economic Perspective for Manufacturability
%R 2004-07
%D May 18, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K LNA, Cost Modeling, Fault Models, DFT, Reliability
%Y Economics; Reliability; VLSI Testing
%X Design For Manufacturability issues have started escalating the problem of Design and Test in the Deep Submicron era. Two questions posed are
"How good is the quality?" and "How expensive is the product?" To ensure quality one needs to answer the question "To DFT or Not to DFT." New Analog
and RF designs lack good DFT techniques due to inadequate fault models. Using existing test techniques that are largely outdated, one has to and
out if the solutions are economically feasible for the vendor to implement in his designs. The quality issues of RF cores and the economic issues
of mixed signal cores and standalone chipsets are addressed in this thesis from a DFM standpoint. A lot of emphasis has been placed on the test cost
of chips and a variety of models have been proposed in the literature. Existing models are incomplete with the fact that most do not take into account
the costs involved once the chip reaches the market. This thesis focuses on the cost economics of fault tolerant chips and how RF cores fit into the
whole economic model for new designs. New fault models which could help improve the testability of circuits (hence improving quality) are discussed
here. The focus is then moved to an economic cycle where mathematical estimates of the costs for new designs are given. This model will help designers
analyze the need for a fault tolerant system and its feasibility in the industry using the reliability of the system. It will help evaluate the costs
involved during the life cycle of a chip. Design tools - SpectreRF and ASITIC have been used for modeling RF circuits at 0.25u technology. Carafe tool
has been used to perform fault analysis on the layout of the circuit to model realistic faults. Existing fault models for resistors and capacitors
have been verified and a new fault model for inductors has been proposed using these tools. The fault models will help improve the design of RF
circuits by enforcing more constraints on design specific issues. The cost models proposed in this thesis will help designers identify key areas
of cost and help clamp down unnecessary expenses where possible.
%Z Fri, 13 Aug 2004 19:04:00 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-12.ps
%A Srikanth, Munirathnam
%T EXPLOITING QUERY FEATURES IN LANGUAGE MODELING APPROACH\\FOR INFORMATION RETRIEVAL
%R 2004-12
%D August 26, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K information retrieval, statistical language modeling, biterms, concept language model, maximum entropy language models
%X Statistical Language Modeling has recently been applied to the problem of
Information Retrieval~(IR) and appreciable performance improvements have
been achieved over traditional vector space and probabilistic retrieval
models. Most experiments demonstrating the language modeling approach
to text retrieval have been based on smoothed unigram language models that only
exploit the term occurrence statistic in probability estimation. Experiments
with additional features like bigrams have met with limited success. However,
language models incorporating $n$-gram, word-triggers, topic of discourse,
syntactic and semantic features have shown significant improvements in
speech recognition.
The main thrust of this dissertation is to identify the need to {\em design}
language models for IR that satisfy its specific modeling requirements and
demonstrate it by designing language models that (1) incorporate IR-specific
features~(biterm language model), (2) correspond to better document and query
representations~(concept language model) and (3) combine evidence from the
different information sources~(language features) towards modeling the
relevance of a document to a given query~(maximum entropy language models
for IR).
Prior research in incorporating additional features in language models for
information retrieval have adopted models derived for speech
recognition. However, speech recognition and information retrieval have
different language modeling requirements. For example, in speech
recognition the utterances {\em information retrieval} and {\em retrieval of
information} should be distinguished; whereas they should have same
representation for efficient information retrieval. {\em Biterm Language
Models} -- a variant of bigram language models -- are introduced here to
address this problem.
Biterm language models handle the local variation - within 2 words -
in the surface form of words used in the expression of a concept. It is,
however, these concepts that need to be modeled in the queries to improve
retrieval performance. {\em Concept Language Models}~(CLM) that prescribe a
two-layered query model is presented in this dissertation. A user's
information need is modeled as a sequence of concepts and the query is
viewed as an expression of such concepts of interest. It is shown that such
a model provides significant improvements to retrieval performance. CLM
also provide a natural way of incorporating concept synonymy in the language
modeling approach to IR.
Mixture models combine statistical evidence from different sources to
estimate the probability distribution. For example, smoothed unigram
language model for a document combines unigram counts from the document and
corpus. While mixture models are easy to implement, they seem to make
suboptimal use of their components. A natural method of combining
information sources based on the Maximum Entropy Principle has been
shown to contribute significantly to perplexity reduction and hence
better language models for speech recognition. Such a framework is proposed
for information retrieval in the context of document likelihood or relevance
language models. The {\em maximum entropy language model} for information
retrieval provides a better mechanism for incorporating external knowledge
and additional syntactic and semantic features of the language in language
models for IR.
%Z Fri, 27 Aug 2004 19:59:23 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-13.pdf
%A Liu, Jiangjiang
%T INFORMATION PATTERN AWARE DESIGN STRATEGIES FOR NANOMETER-SCALE ADDRESS BUSES
%R 2004-13
%D August 31, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K computer system design, memory system, address bus, power consumption, performance, cost, data compression
%Y Design
%X The growing disparity in processor and memory performance has
forced designers to allocate an increasing fraction of die area to
communication (I/O buffers, pads, pins, on- and off-chip buses)
and storage (registers, caches, main memory) components of the
memory system to enable low-latency and high-bandwidth access to
large amounts of information (addresses, instructions, and data).
Consequently, the memory system has become critical to system
performance, power consumption, and cost.
In this dissertation, we consider three types of redundancies
related to information communicated and stored in the memory
system, with the main focus being on information communicated on
nanometer-scale address buses. They are temporal redundancy ,
information redundancy, and energy redundancy. To take advantage
of these redundancies, we analyze and design information pattern
aware strategies to exploit various patterns in information
communicated and stored in a multi-level memory hierarchy to
derive gains in performance, energy efficiency, and cost. Our
main contributions are as follows. (1) A comprehensive limit study
on the benefits of address, instruction, and data compression at
all levels of the memory system considering a wide variety of
factors. (2) A technique called hardware-only compression (HOC),
in which narrow bus widths are used for underutilized buses to
reduce cost, novel encoding schemes are employed to reduce power
consumption, and concatenation and other methods are applied to
mitigate performance penalty. (3) A detailed analysis of the
performance, energy, and cost trade-offs possible with two
cache-based dynamic address compression schemes. (4) A highly
energy- and performance-efficient dynamic address compression
methodology for nanometer-scale address buses. Many of the
principles underlying this methodology are also applicable to
instruction and data bus compression.
All our analysis and design has been performed in the context of
real-world benchmark suites such as SPEC CPU2000 and using
execution-driven simulators like Shade and SimpleScalar. Our
analysis shows that ample opportunities exist for applying
compression throughout the memory system. Further, we show that
our address compression methods can simultaneously provide
significant improvements in energy efficiency, cost, and latency
compared to an uncompressed bus.
%Z Wed, 01 Sep 2004 13:04:29 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-14.pdf
%A Ghosh, Joy
%A Philip, Sumesh
%A Qiao, Chunming
%T Performance Analysis of Mobility Based Routing Protocols in MANET
%R 2004-14
%D September 16, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Mobility model, Routing protocol, Ad hoc wireless networks, Performance analysis
%X Most routing protocols in MANET adopt the popular
Random Waypoint model for its simplicity and suitability
for theoretical study and analysis. Recently, several entity, group
and scenario based mobility models and frameworks have been
proposed to model much more realistic and practical movements
of mobile nodes in real scenarios. Although some work exists in
evaluating routing protocols based on such specific scenarios, and
some effort in adapting a protocol to suit mobility has been made,
there does not exist any protocol that makes direct use of mobility
information to route packets within a MANET. In this work,
we first develop a practical mobility model that recognizes an
orbital pattern in the sociological movement of mobile users, and
then propose a novel Orbit Based Routing (OBR) protocol, that
leverages the underlying orbital mobility to accurately determine
a set of likely regions containing any node in the MANET. By
forming a distributed location database among acquaintances
and employing a scalable geographic routing to forward packets
among nodes, OBR emerges as a clear choice for MANET routing
in the face of practical mobility. We propose three different
schemes of OBR and compare their performance against an
Acquaintance Based Soft Location Management (ABSoLoM)
protocol.
%Z Fri, 17 Sep 2004 13:50:47 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-09.pdf
%A Aruna Balasubramanian, Sumita Mishra and Ramalingam Sridhar
%T A Hybrid Approach to Key Management for Enhanced Security in Ad Hoc Networks
%R 2004-09
%D July 30, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Ad hoc networks, Security, Key management, Symmetric cryptosystems, Asymmetric cryptosystems, Threshold cryptography, Clustering
%X Key management is one of the most challenging tasks in developing security solutions for wireless ad hoc networks. Most of the security primitives can only be realized if an efficient, robust and secure key generation and management system is developed. Symmetric key cryptosystems are difficult to incorporate in an ad hoc decentralized domain, and are not scalable. A public key cryptosystem is
computationally expensive and a decentralized certification service is essential for its deployment. In this paper, we present a locally symmetric/globally asymmetric key management solution for wireless ad hoc networks that overcomes the limitations of both. The proposed hybrid
approach does not require prior trust assumptions or the presence of a centralized certification authority. Preliminary analysis and results indicate that this approach can achieve a better performance when compared
with the traditional solutions. We show that our approach is scalable, and robust with respect to node failures, topology changes, node speed and loss of connectivity.
%Z Wed, 29 Sep 2004 14:00:58 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-15.pdf
%A Yu, Xiang
%A Thng, Ian
%A Jiang, Yuming
%A Qiao, Chunming
%T Queuing Processes in GPS and PGPS with LRD Traffic Inputs (Extended Version)
%R 2004-15
%D September 29, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K long range dependent, generalized processor sharing
%X Long range dependent (LRD) traffic whose single server queue
process is Weibull Bounded (WB) is first analyzed. Two upper
bounds on the individual session's queue length of LRD traffic
under the generalized processor sharing (GPS) scheduling
discipline are then contributed. It is shown that the index
parameter in the upper bound of one LRD flow may be affected by other
LRD flows. A new concept, called LRD isolation, is subsequently
contributed and accompanying it, a new technique is contributed to
check whether a flow, with a given GPS weight assignment, can be
guaranteed to be LRD isolated. This technique is also
amenable for an online call admission control (CAC)
to determine minimum contract weights of a new flow in
order to guarantee the LRD isolation. The results
are also extended to a PGPS (Packet-based GPS) scheduler and
relevant numerical results are provided to show the usefulness of
our bounds and LRD isolation technique.
%Z Wed, 29 Sep 2004 19:33:49 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-16.pdf
%A Chinchani, Ramkumar
%A Iyer, Anusha
%A Ngo Q., Hung
%A Upadhyaya, Shambhu
%T A Target-Centric Formal Model For Insider Threat And More
%R 2004-16
%D October 12, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Computer Security, Threat Analysis, Insider Threat
%Y Security, Algorithms
%X The diversity of cyber threat has grown over time from network-level attacks and password-cracking to include newer classes such as insider attacks, email worms and social engineering, which are currently recognized as serious security problems. However, attack modeling and threat analy-
sis tools have not evolved at the same rate. Known formal models such as attack graphs perform action-centric vulnerability modeling and analysis. All possible atomic user actions are represented as states, and sequences which lead to the violation of a specified safety property are extracted to
indicate possible exploits. While attack graphs are relevant in the context of network level attacks, they are ill-equipped to address complex threats such as insider attacks. The difficulty mainly lies in the fact that adversaries belonging to this threat class use familiarity of and accessibility
to their computational environment to discover new ways of launching stealthy, damaging attacks. In this paper, we propose a new target-centric model to address this class of security problems and explain the modeling methodology with specific examples. Finally, we perform quantified vulnerability
analyses and prove worst case complexity results on our model.
%Z Tue, 12 Oct 2004 19:55:48 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-17.ps
%A Glasser, Christian
%A Selman, Alan L.
%A Zhang, Liyu
%T Canonical Disjoint NP-Pairs of Propositional Proof Systems
%R 2004-17
%D November 19, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K disjoint NP-pairs, propositional proof systems, canonical pairs, degrees
%Y F.1.3
%X We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to
the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is
identical. Secondly, we show that this degree structure is not superficial: Assuming there exist P-inseparable disjoint pairs, there exist intermediate disjoint NP-pairs. That is, if $(A, B)$ is a P-separable disjoint NP-pair and
$(C, D)$ is a P-inseparable disjoint NP-pair, then there exist P-inseparable, incomparable NP-pairs $(E, F)$ and $(G, H)$ whose degrees lie
strictly between $(A, B)$ and $(C, D)$. Furthermore, between any two disjoint NP-pairs that are comparable and inequivalent, such a diamond exists.
%Z Fri, 19 Nov 2004 19:20:45 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-18.ps
%A Mathew, Sunu
%A Shah, Chintan
%A Upadhyaya, Shambhu
%T An Alert Fusion Framework for Situation Awareness of Coordinated Multistage Attacks
%R 2004-18
%D November 29, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Alert Fusion, Computer Security, Intrusion Detection, Situation Awareness
%X Recent incidents in the cyber world strongly
suggest that coordinated multistage cyber attacks are quite probable
and that effective countermeasures need to be
developed. Attack detection by correlation and fusion of
intrusion alerts has been an active area of current research.
However, most of these research efforts focus on ex post facto
analysis of alert data to uncover related attacks. In this
paper, we present an approach for dynamically calculating
`Scenario Credibilities' based on the state of a live intrusion
alert stream. We also develop a framework for Attack Scenario
representation that facilitates real-time fusion of intrusion
alerts and calculation of the scenario credibility values.
Our approach provides a usable mechanism for detecting,
predicting and reasoning about multistage goal-oriented
attacks in real time. The details of the fusion framework
and a description of multistage attack detection using this framework
are presented in this paper.
%Z Wed, 01 Dec 2004 13:46:20 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-19.ps
%A Girgis, Hani Z.
%A Hegde, Akshay V.
%A Pushpendran, Manu
%A Gestwicki, Paul V.
%A Jayaraman, Bharat
%T Visual Queries for Interactive Execution of Java Programs
%R 2004-19
%D December 13, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K visual query, program execution database, interactive execution, java, jive
%X The behavior of object-oriented programs at runtime can be understood
in terms of object states and the history of interaction between objects.
Runtime behavior can be very complicated, and information visualization
tools are invaluable for program development and debugging.
While there has been considerable work in predicting execution patterns
through slicing and program analysis, comparatively less has been done on analysis of program execution states and histories.
We present a novel technique for visualizing queries over object-oriented program execution. Our technique is built upon the JIVE system of interactive
program visualization, which depicts program state in object diagrams and execution history through sequence diagrams. The queries are posed through the graphical interface, and each view of a program (state, history, source code) provides different querying functionality. Furthermore, the results of the queries are shown in the graphical user-interface by annotating the diagrams or inducing new views. Our design allows for queries over variables, methods, objects, classes, and source code. This paper describes
the domain of these queries as well as their interfaces, briefly outlines their implementation, and also provides a survey of related work and comparisons.
%Z Wed, 15 Dec 2004 19:51:21 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-20.ps
%A Gestwicki, Paul V.
%A Jayaraman, Bharat
%T Methodology and Architecture of JIVE
%R 2004-20
%D December 13, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K interactive execution, object-oriented program visualization, forward and reverse execution, object diagrams, sequence diagrams, java, jive
%X A novel approach to the runtime visualization and analysis of object-oriented programs is presented and illustrated through a prototype system called JIVE: Java Interactive Visualization Environment. The main contributions of JIVE are in its multiple concurrent representations of program state and execution history through an environment that supports forward and reverse execution
along with execution queries. This model facilitates program understanding and interactive debugging. Our graphical representation of runtime states
clarifies the important point that objects are execution environments. The history of object interaction is displayed via sequence diagrams similar to those of the Unified Modeling Language, and in this way we help close the loop between design-time and run-time representations. Interactive execution is made possible by maintaining a runtime history database, which may be
queried for information on variable behavior, method executions, and object interactions. We illustrate the capabilities of this system through examples. JIVE is implemented using the Java Platform Debugger Architecture and supports the Java language and libraries, including multithreaded and GUI applications.
%Z Thu, 16 Dec 2004 13:26:53 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-22.ps
%A Glasser, Christian
%A Ogihara, Mitsunori
%A Pavan, A.
%A Selman, Alan L.
%A Zhang, Liyu
%T Autoreducibility, Mitoticity, and Immunity
%R 2004-22
%D December 21, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K autoreducibility, mitoticity, immunity
%X We show the following results regarding complete sets:
NP-complete sets and PSPACE-complete sets are many-one
autoreducible.
Complete sets of any level of PH, MODPH, or
the Boolean hierarchy over NP are many-one autoreducible.
EXP-complete sets are many-one mitotic.
NEXP-complete sets are weakly many-one mitotic.
PSPACE-complete sets are weakly Turing-mitotic.
If one-way permutations and quick pseudo-random generators exist,
then NP-complete languages are m-mitotic.
If there is a tally language in NP \cap coNP - P, then, for
every \epsilon > 0,
NP-complete sets are not 2^{n(1+\epsilon)}-immune.
These results solve several of the open questions raised by Buhrman and
Torenvliet in their 1994 survey paper on the
structure of complete sets.
%Z Wed, 22 Dec 2004 14:38:38 GMT
%U http://www.cse.buffalo.edu/tech-reports/2004-21.ps
%A Gestwicki, Paul V.
%A Jayaraman, Bharat
%A Garg, Ashim
%T From Class Diagrams to Object Diagrams: An Automated Approach
%R 2004-21
%D December 13, 2004
%I Department of Computer Science and Engineering, SUNY Buffalo
%K class diagram, object diagram, graph drawing, interactive program execution, jive
%X This paper addresses the problem of how to visually depict the object structures that arise during
the execution of object-oriented programs. Such a need arises in systems for run-time visualization of
object-oriented programs. A straightforward approach would be to treat the object structure as a directed
graph and apply traditional graph drawing techniques. However, we show that such an approach results in
suboptimal drawings since important structural information in the class diagram is overlooked. A more
effective approach must utilize properties of the class diagram in guiding a traditional graph-drawing
approach. In particular, objects that are instances of related classes should be drawn in proximity to
one another. The contribution of this paper lies in providing a formal definition of two important
properties that yield predictable object diagrams: recursive cluster and leaf cluster. While the former
commonly occur in structures such as lists, trees, etc., the latter are motivated by the power law
property of object graphs, namely, that there are very few objects with high degree and many with low
degree. This paper shows that these properties can be efficiently detected in the class diagram, and also
efficiently applied to produce aesthetic object diagrams. The techniques described in this paper form the
basis for the rendering of object structures in the JIVE system for interactive visualization of Java programs.
%Z Mon, 03 Jan 2005 15:07:09 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-01.ps
%A Santore, John F.
%T Complete Coded Protocols from PIO Experiment
%R 2005-01
%D January 05, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%X The complete text of all coded transcripts used as data for John Santore's dissertation can be found in this file. Both the coded transcripts and the retrospectives (for the 95% of participants who gave them) are included. The transcripts are organized by the temporary task numbers that they were given during the experiment. Those are:
Task 1: Counting immobile classes in a four room suite wherein each room has a different appearance
Task 2: Counting immobile classes in a four room suite wherein the opposite rooms have the same appreance
Task 3: Counting Mobile robots that all looked alike.
Task 4: Following a robot with randomly moving PIO distractors
Task 5: Counting Mobile robots with 3 being silver-gray and two being red-gold.
Task 6: Following a robot with PIO distractors that followed paths of their own
Task 7: The Control task. Following a person with other people as the distractors.
For more details see John F. Santore's dissertation.
%Z Fri, 07 Jan 2005 15:38:46 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-04.ps
%A Tang, C., Ramanathan, M., Jiang, D., and Zhang, A.
%T A Semi-Supervised Learning Method for Coherent Pattern Detection from Gene-Sample-Time Series Datasets
%R 2005-04
%D March 09, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Gene-sample-time microarray data, semi-supervised learning
%Y Algorithms
%X DNA microarrays provide simultaneous, semi-quantitative measurements of the expression levels of thousands of genes from a single experimental sample.
The availability of such data sets can enhance our understanding of gene function and regulation if the patterns underlying gene expression data can be
identified. In this paper we study the problem of coherent pattern detection from gene-sample-time series expression data sets. These data sets result
from microarray experiments in which a gene expression time series obtained on multiple samples using microarrays; the gene identities represent the first
dimension, the sample properties represent the second dimension and time represents the third dimension. Such Gene-Sample-Time Series (GST) data arise
naturally in microarray experimental designs, e.g., when the pharmacodynamics of gene expression in responder and non-responder groups is investigated.
A new semi-supervise learning method is proposed to search coherent blocks from gene-sample-time series data set. Each block contains a subset of genes
and a subset of samples such that the patterns within the block are coherent along the time series. The coherent blocks may identify the samples
corresponding to some phenotypes (e.g., disease states), and suggest the candidate genes correlated to the phenotypes. We empirically evaluate
the performance of our approaches on a real microarray data of the pharmacodynamics of gene expression in multiple sclerosis patients after interferon
beta treatment.
%Z Thu, 10 Mar 2005 16:34:20 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-05.pdf
%A Chinchani, Ramkumar
%A Ha, Duc
%A Iyer, Anusha
%A Ngo, Hung Q.
%A Upadhyaya, Shambhu
%T On The Hardness of Approximating the Min-Hack Problem
%R 2005-05
%D March 02, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Inapproximability, Computer Security
%X We study the hardness of approximation for the MINIMUM HACKING problem, which roughly
can be described as the problem of finding the best way to compromise some target nodes
given a few initial compromised nodes in a network. We give three reductions to show
that MINIMUM HACKING problem is not approximable to within 2^((logn)^(1-\delta)) where
\delta = 1-1/(loglog^c(n)), for any c < 1/2. In particular, the reductions are from a
PCP, from the MINIMUM LABEL-COVER problem, and from the MINIMUM MONOTONE SATISFYING
ASSIGNMENT problem. We also analyze some heuristics on this problem.
%Z Fri, 11 Mar 2005 16:23:57 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-06.pdf
%A Attias, H. T.
%A Beal, M. J.
%T Tree of Latent Mixtures for Bayesian Modelling and Classification of High Dimensional Data
%R 2005-06
%D January 1, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%Y Algorithms
%X Many domains of interest to machine learning, such as audio and video, computational biology, climate modelling, and quantitative finance,
involve very high dimensional data. Such data are often characterized by statistical structure that includes correlations on multiple scales.
Attempts to model those high dimensional data raise problems that are much less significant in low dimensions. This paper presents a novel approach
to modelling and classification in high dimensions. The approach is based on a graphical model with a tree structure, which performs density
estimation on multiple spatial scales. Exact inference in this model is computationally intractable; two algorithms for approximate inference
using variational techniques are derived and analyzed. We discuss learning and classification using these algorithms, and demonstrate their
performance on a handwritten digit recognition task.
%Z Mon, 21 Mar 2005 16:28:31 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-09.pdf
%A Ghosh, Joy
%A Philip, Sumesh
%A Qiao, Chunming
%T Sociological Orbit Aware Routing in MANET
%R 2005-09
%D March 25, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Mobility models, Routing protocol, Ad hoc wireless networks, Performance analysis
%X Mobility affects routing protocol performance
within a Mobile Ad Hoc NETwork (MANET). Past research on
mobility models and framework was motivated by the need to
provide a simulation platform for evaluating routing protocol
performance via realistic scenarios. Mobility information of
individual nodes has also been used to improve routing decisions
(e.g., choice of next hop, link break prediction) in a MANET.
In this paper, we introduce a novel concept of integrating
macro-mobility information obtained from the sociological movement
pattern of mobile MANET users, into routing. The extraction
of this mobility information is based on our observation
that the movement of a mobile user exhibits a partially repetitive
?orbital? patten involving a set of ?Hubs? in practise. This partially
deterministic movement pattern is both practical and useful in
locating nodes and routing packets to them without the need
for constant tracking or flooding. Leveraging this Hub-based
orbital pattern, we propose a Sociological Orbit Aware Routing
(SOAR) protocol. Through extensive performance analysis we
show that SOAR significantly outperforms conventional routing
protocols like Dynamic Source Routing (DSR) and Location
Aided Routing (LAR) in terms of higher data throughput, lower
control overhead, and lower end-to-end delay.
%Z Wed, 13 Apr 2005 13:53:34 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-08.pdf
%A Shapiro, Stuart C.
%A Anstey, Josephine
%A Pape, David E.
%A Devdas Nayak, Trupti
%A Kandefer, Michael
%A Telhan, Orkan
%T MGLAIR Agents in a Virtual Reality Drama
%R 2005-08
%D March 30, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Virtual Reality Drama; Intelligent Agents; Cognitive Architectures
%X We provide an overview of the use of intelligent agents, implemented in the new
MGLAIR architecture, in a virtual reality drama. For us, a virtual reality drama is a
scripted play in which the computational agents are actors who have copies of the script,
and one human audience member has been drafted to be a participant, but doesn't have a
copy of the script. The computational actors must improvise reactions to the human
partpicipant's actions, but keep the play moving along in as close agreement to the
script as possible. The goal is to provide the human participant with a specific emotional
experience. We explicate this philosophy; outline the previously described GLAIR architecture;
explain the introduction of an organization into modalities that results in the new MGLAIR
architecture; describe our current VR drama, The Trial, The Trail; and discuss the implementation
of our actor-agents. Our discussion of the actor-agents focuses on their abilities to react
to triggers (cues), their performance of contingent actions that are off the main-line arc
of the script, their use of timers to pace the drama, and the organization of the cast of
actor-agents into a multi-agent system.
%Z Wed, 13 Apr 2005 13:53:44 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-07.ps
%A Khan, Asheq
%A Philip, Sumesh J.
%A Qiao, Chunming
%A Tripathi, Satish K.
%T A Framework for Mobile Assisted Localization in Wireless Sensor Networks
%R 2005-07
%D March 25, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Localization, Sensor Network, Algorithm
%X Location tracking has several applications in wireless sensor networks. While GPS
receivers can be used for location awareness in the outdoor environment, it can be
prohibitively expensive in terms of size, cost and power consumption for large scale
deployment. Most of the existing work in network localization has investigated the
problem of computing the locations of all nodes with the help of a limited subset of
{\it seed} nodes, who are already aware of their own locations. In this work, we
introduce the novel concept of mobile seed node assisted localization, in which a
small subset of mobile sensor nodes are used for network localization. specifically,
we consider the case in which the network is localized using only three mobile sensor
nodes. We present efficient algorithms for network localization that optimizes the
localization latency, total battery power and minimizes the maximal power consumption
by any mobile sensor node.
%Z Wed, 13 Apr 2005 19:51:20 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-12.pdf
%A Ghosh, Joy
%A Qiao, Chunming
%A Philip, Sumesh
%A Ngo, Hung
%A Yoon, Seokhoon
%T Sociological Orbit aware Location Approximation and Routing (SOLAR) in DTN
%R 2005-12
%D April 6, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Mobility framework, Routing protocol, Delay
%X Routing in delay tolerant networks poses a challenging
problem compared to a conventional data network due to
the uncertainty and time varying nature of network connectivity.
Initial research in this area has considered algorithms based on
deterministic mobility of the nodes in DTN. While the assumption
of deterministic mobility can lay the groundwork for a theoretical
understanding of DTN, such knowledge may not be applicable
to mobile ad hoc networks. In this work, we introduce a novel
concept of a partially repetitive ?orbital? pattern of mobile users
(nodes) involving a set of ?hubs?, that may be better suited for a
semi-deterministic mobility modeling of DTN users. This partially
deterministic movement pattern is both practical as well as useful
in the sense that the hub list information can be useful for locating
nodes and routing packets to them in a DTN.
%Z Tue, 17 May 2005 19:26:02 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-11.pdf
%A Staworko, Slawomir
%A Chomicki, Jan
%T Priority-Based Conflict Resolution in Inconsistent Relational Databases
%R 2005-11
%D June 15, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K databases, inconsistencies,reparis, preferences
%X We study here the impact of priorities on conflict resolution in inconsistent relational databases. We extend the framework
based on the notions of repair and consistent query answer. We propose a set of postulates that an extended framework should
satisfy and consider two instantiations of the framework: (locally preferred) l-repairs and (globally preferred) g-repairs. We study
the relationships between them and the impact each notion of repair has on the computational complexity of repair checking and consistent
query answers.
%Z Thu, 16 Jun 2005 12:14:40 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-14.ps
%A Huaming Zhang
%A Xin He
%T An Application of Well-Orderly Trees in Graph Drawing
%R 2005-14
%D May 30, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%X Well-orderly trees seem to have the potential of becoming a
powerful technique capable of deriving new results in graph encoding,
graph enumeration and graph generation \cite{BGH03,BGH0302}. Our
application of well-orderly trees in this paper provides new evidence
to their power. We give more compact visibility representation of plane graphs using the properties of well orderly trees.
%Z Fri, 17 Jun 2005 17:44:26 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-15.ps
%A Gestwicki, Paul V.
%T Interactive Visualization of Object-Oriented Languages
%R 2005-15
%D June 15, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K object-oriented programming; program visualization; interactive execution; java
%X We present a novel approach for the interactive visualization of the execution of object-oriented
programs that fulfills several important criteria: (i) visual depiction of the current execution state
as well as the entire history of execution; (ii) support for forward as well as reverse execution stepping;
(iii) enhanced graph-drawing techniques for the current state and history of execution; (iv) support for
run-time queries on the execution state; (v) support for all major features of the Java language and use
of the standard Java compiler and run-time system. Taken together, our approach marks a significant
advance over existing techniques for visualizing object-oriented program execution.
Our proposed notation for expressing Java execution states clarifies the important fact that objects
are environments; that is, a method execution is shown within its object context. By incorporating
diagrams similar to those used during the design phase, we help to close the loop between design and
execution. In particular, an enhanced UML-like object diagram is used for depicting the current state,
and sequence diagrams are used for execution history. Interactive execution is instrumented by
conceptualizing program execution as a database, so that stepping backward or forward through recorded
states involves rolling back or re-committing transactions. Our methodology incorporates a novel technique
for recording minimal state transitions in order to efficiently provide this interactive execution.
Automatically generating object and sequence diagrams requires advanced graph drawing techniques.
The enhanced object diagrams we present are not simple graphs, and special techniques are required to
process them. We illustrate how layered drawing techniques can be used to achieve good drawings of enhanced
object diagrams. Two techniques are presented for automatically drawing sequence diagrams: a stochastic
simulated annealing approach and a fast greedy technique. We show how traditional graph-theoretic approaches
can be combined with program-specific properties in order to produce better automatic drawings.
Specifically, an analysis of the class diagram is used to determine the classes that form logical clusters,
and these clusters are formed in the object diagram generated at runtime. We have implemented our approach
in a prototypical tool called JIVE: Java Interactive Visualization Environment.
%Z Mon, 20 Jun 2005 19:13:48 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-16.pdf
%A Rapaport, William J.
%T Philosophy of Computer Science: An Introductory Course
%R 2005-16
%D June 21, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K philosophy of computer science, philosophy of artificial intelligence, computer ethics
%X There are many branches of philosophy called "the philosophy of X",
where X = disciplines ranging from history to physics. The philosophy
of artificial intelligence has a long history, and there are many
courses and texts with that title. Surprisingly, the philosophy of
computer science is not nearly as well-developed. This article proposes
topics that might constitute the philosophy of computer science and
describes a course covering those topics, along with suggested readings
and assignments. This article is forthcoming in _Teaching Philosophy_, but
without the appendices contained in this technical-report version that contain archived
versions of the course webpages.
%Z Wed, 22 Jun 2005 14:45:09 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-13.ps
%A Santore, John F.
%T Identifying Perceptually Indistinguishable Objects
%R 2005-13
%D January 24, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%X This dissertation reports on an investigation into how Perceptually Indistinguishable
Objects (PIOs) can be identified. An experiment with 68 human participants was performed
to investigate how and how well people identify PIOs. The experiment was designed as a
protocol analysis experiment. Participants performed a video-game like task of counting or
following, both of which entail identifying objects. The analysis of this experiment shows that
the human participants had a marked preference for certain situations that they believed helped
them identify the PIOs more readily. Participants would try, as much as possible, to keep
themselves in these situations.
A cognitively plausible computational model of identifying PIOs is developed from the results
of the human subjects experiment. The cues and strategies that participants in the experiment
went out of their way to use are examined and treated separately. Some participant-preferred
strategies always lead to the correct answer/identification when the participant's background
beliefs are correct. These strategies are generally perceptually based and are called base
cases. The other set of strategies that the participants tried to use are not quite as
perceptually based and are called intermediate cases. These strategies, when correctly used,
lead to the right answer a great deal of the time, but are slightly more prone to failure than the base cases. The knowledge needed for the general case of identifying PIOs is also discussed and an algorithm for the model is included.
Finally, a new simulated cognitive robot is described that includes an implementation of the
computational model of identifying PIOs. The robot was tested in the same environment that
the human participants used for the experiments and on the same tasks. The mistakes that the
robot made fell into a subset of the mistakes that the human participants made in the
experiment.
%Z Mon, 27 Jun 2005 17:33:33 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-17.pdf
%A Ghosh, Joy
%A Yoon, Seokhoon
%A Ngo, Hung
%A Qiao, Chunming
%T Sociological Orbits for Efficient Routing in Intermittently Connected Mobile Ad Hoc Networks
%R 2005-17
%D July 06, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K Mobility framework, Routing protocols, Intermittently Connected Networks, Theoretical model, Performance analysis
%X Routing in Intermittently Connected Networks
(ICN) is a challenging problem due to the uncertainty and
time varying nature of network connectivity. In this work, we
focus on a special class of ICN formed by mobile ad hoc
users called ICMAN. We first consider a new and practical
probabilistic mobility model where the nodes move between a set
of ?hubs? in a partially repetitive and nondeterministic pattern
to form the so-called ?sociological orbits?. Second, to leverage
the sociological orbit based mobility pattern in routing within
ICMAN, we propose a series of multi-path Sociological Orbit
aware Location Approximation and Routing (SOLAR) protocols.
We present theoretical analysis of the mobility model and routing
algorithms under consideration, and show that the proposed
routing algorithms can outperform other conventional routing
approaches in an ICN by taking advantage of the sociological
orbit based mobility pattern.
%Z Mon, 11 Jul 2005 19:08:52 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-18.pdf
%A Glasser, Christian
%A Pavan, A.
%A Selman, Alan L.
%A Zhang, Liyu
%T Redundancy in Complete Sets
%R 2005-18
%D July 07, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K mitotic sets, autoreducibility, complete sets
%X We show that a set is m-autoreducible if and only if it is m-mitotic.
This solves a long standing open question in a surprising way.
As a consequence of this unconditional result and recent work
by Gla{\ss}er et al.,
complete sets for all of the following complexity
classes are m-mitotic:
NP, coNP, $\oplus P$, PSPACE, and NEXP,
as well as all levels of PH, MODPH,
and the Boolean hierarchy overNP.
In the cases of NP PSPACE, NEXP, and PH,
this at once answers several well-studied open questions.
These results tell us that complete sets share a redundancy
that was not known before.
We disprove the equivalence between
autoreducibility and mitoticity for all polynomial-time-bounded
reducibilities between 3-tt-reducibility and Turing-reducibility:
There exists a sparse set in EXP that is
polynomial-time 3-tt-autoreducible,
but not weakly polynomial-time T-mitotic.
In particular, polynomial-time T-autoreducibility does not imply
polynomial-time weak T-mitoticity, which solves an open question
by Buhrman and Torenvliet.
We generalize autoreducibility to define poly-autoreducibility
and give evidence that NP-complete sets are poly-autoreducible.
%Z Mon, 11 Jul 2005 19:18:41 GMT
%U http://www.cse.buffalo.edu/tech-reports/2005-19.pdf
%A Glasser, Christian
%A Selman, Alan L.
%A Zhang, Liyu
%T Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems
%R 2005-19
%D July 07, 2005
%I Department of Computer Science and Engineering, SUNY Buffalo
%K disjoint NP-pairs, propositional proof systems, canonical pairs, degrees
%Y F.1.3
%Z Mon, 11 Jul 2005 19:18:53 GMT