2020-10-31T21:36:45Zhttp://edoc.mpg.de/ac_ft_oai.ploai:edoc.mpg.de:2017952012-09-1987:934
A Framework for Dynamic Connectivity Meshes
Vorsatz, Jens
Seidel, Hans-Peter
Reiners, D.
expertsonly
Implementing algorithms that are based on dynamic triangle meshes
often requires updating internal data-structures as soon as the
connectivity of the mesh changes. The design of a class hierarchy
that is able to deal with such changes is particularly challenging if the
system reaches a certain complexity.
The paper proposes a software design that enables the users to
efficiently implement algorithms that can handle these dynamic
changes while still maintaining a certain encapsulation of the
single components.
Our design is based on a callback mechanism. A client can register at some {\tt
Info}-object and gets informed whenever a change of the connectivity occurs.
This way the client is able to keep internal data up-to-date. Our framework
enables us to write small client classes that cover just a small dedicated
aspect of necessary updates related to the changing connectivity. These small
components can be combined to more complex modules and can often easily be
reused. Moreover, we do not have to store related 'dynamic data' in one central
place, e.g. the mesh, which could lead to a significant memory overhead if an
application uses some modules just for a short time.
We have used and tested this class design extensively for
implementing 'Dynamic Connectivity Meshes and
Applications~\cite{Vorsatz:2003:DRA}'. Additionally, as a
feasibility study, we have implemented and integrated our concept in the
\OM-framework.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201795
OpenSG Symposium 2003, ACM, 49-55 (2003)
en
oai:edoc.mpg.de:2018102010-12-0287:932
Citius altius fortius: Lessons learned from the Theorem Prover WALDMEISTER
Hillenbrand, Thomas
Dahn, Ingo
Vigneron, Laurent
expertsonly
In the last years, the development of automated theorem
provers has been advancing in a so to speak Olympic spirit,
following the motto "faster, higher, stronger"; and the
{Waldmeister} system has been a part of that endeavour. We
will survey the concepts underlying this prover, which
implements Knuth-Bendix completion in its unfailing variant.
The system architecture is based on a strict separation of
active and passive facts, and is realized via specifically
tailored representations for each of the central data
structures: indexing for the active facts, set-based
compression for the passive facts, successor sets for the
conjectures. In order to cope with large search spaces,
specialized redundancy criteria are employed, and the
empirically gained control knowledge is integrated to ease
the use of the system. We conclude with a discussion of
strengths and weaknesses, and a view of future prospects.
Elsevier
2003
Conference-Paper
http://edoc.mpg.de/201810
Proceedings of the 4th International Workshop on First Order Theorem Proving, FTP'03, Elsevier, 1-13 (2003)
en
oai:edoc.mpg.de:2018232010-12-0287:932
The New WALDMEISTER Loop at Work
Gaillourdet, Jean-Marie
Hillenbrand, Thomas
Löchner, Bernd
Spies, Hendrik
Baader, Franz
expertsonly
We present recent developments within the theorem prover \textsc{Waldmeister}.
They rely on a novel organization of the underlying saturation-based proof
procedure into a system architecture. As is known, the saturation process tends
to quickly fill the memory available unless preventive measures are employed.
To overcome this problem, our new ``\textsc{Waldmeister} loop'' features a
highly compact representation of the search state, exploiting its inherent
structure. The implementation just being available, the cost and the benefits
of the concept now can exactly be measured. Indeed are our expectations met
concerning the drastic cut-down of memory usage with only moderate overhead of
time.
In addition it has turned out that the revealed structure of the search state
paves the way to an easily implemented parallelization of the prover with
modest communication requirements and rewarding speed-ups. In order to minimize
communication-related latencies, we discuss some variations of the loop to
maximally profit from multiple processors.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201823
Automated deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 317-321 (2003)
en
oai:edoc.mpg.de:2018342012-09-1987:931
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
Di Battista, Giuseppe
Zwick, Uri
expertsonly
Given the positions of $n$ sites in a radio network
we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201834
urn:ISBN:3-540-20064-9
Algorithms - ESA 2003: 11th Annual European Symposium, Springer, 230-241 (2003)
en
oai:edoc.mpg.de:2018352012-09-1987:931
On the Competitive Ratio for Online Facility Location
Fotakis, Dimitris
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
expertsonly
We consider the problem of Online Facility Location, where demands arrive
online and must be irrevocably assigned to an open facility upon arrival. The
objective is to minimize the sum of facility and assignment costs. We prove
that the competitive ratio for Online Facility Location is $\Theta(\frac{\log
n}{\log\log n})$. On the negative side, we show that no randomized algorithm
can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$
against an oblivious adversary even if the demands lie on a line segment. On
the positive side, we present a deterministic algorithm achieving a competitive
ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a
hierarchical decomposition of the optimal facility locations such that each
component either is relatively well-separated or has a relatively large
diameter, and a potential function argument which distinguishes between the two
kinds of components.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201835
urn:ISBN:3-540-40493-7
Automata, languages and programming : 30th International Colloquium, ICALP 2003, Springer, 637-652 (2003)
en
oai:edoc.mpg.de:2018392012-09-1987:934
Visualization of Volume Data with Quadratic Super Splines
Rössl, Christian
Zeilfelder, Frank
Nürnberger, Günther
Seidel, Hans-Peter
Turk, Greg
van Wijk, Jarke
Moorhead, Robert
expertsonly
We develop a new approach to reconstruct non-discrete models from
gridded volume samples. As a model, we use quadratic trivariate super
splines on a uniform tetrahedral partition . The approximating splines
are determined in a natural and completely symmetric way by averaging
local data samples, such that appropriate smoothness conditions are
automatically satisfied. On each tetrahedron of , the
quasi-interpolating spline is a polynomial of total degree two which
provides several advantages including efficient computation,
evaluation and visualization of the model. We apply Bernstein-B´ezier
techniques well-known in CAGD to compute and evaluate the trivariate
spline and its gradient. With this approach the volume data can be
visualized efficiently e.g. with isosurface raycasting. Along an
arbitrary ray the splines are univariate, piecewise quadratics and
thus the exact intersection for a prescribed isovalue can be easily
determined in an analytic and exact way. Our results confirm the
efficiency of the quasi-interpolating method and demonstrate high
visual quality for rendered isosurfaces.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201839
IEEE Visualization 2003 (VIS-03), IEEE, 393-400 (2003)
en
oai:edoc.mpg.de:2018412011-07-2287:937
Hologrammsynthese und 3D-Analyse in der digitalen Holografie
Petz, Christoph
expertsonly
Die holografische 3D-Visualisierung ist eine gro"se
Herausforderung in der aktuellen Forschung. Neben der
Entwicklung eines entsprechenden Ausgabeger"ats ist
die schnelle Hologrammsynthese eine Voraussetzung f"ur
ein interaktives holografisches Ausgabesystem. In
dieser Arbeit wird ein Algorithmus f"ur die effiziente
Erzeugung digitaler Hologramme mit PC Grafikhardware
vorgestellt. Des Weiteren werden
3D-Rekonstruktionsverfahren von Hologrammen
untersucht, die mit einer CCD-Kamera aufgenommen
werden k"onnen.
Philipps-Universität Marburg
2003
Thesis
http://edoc.mpg.de/201841
de
oai:edoc.mpg.de:2018432012-09-1987:934
Dynamic Remeshing and Applications
Vorsatz, Jens
Rössl, Christian
Seidel, Hans-Peter
Elber, Gershon
Shapiro, Vadim
expertsonly
Triangle meshes are a flexible and generally accepted boundary
representation for complex geometric shapes. In addition to their
geometric qualities and topological simplicity, \emph{intrinsic}
qualities such as the shape of the triangles, their distribution on
the surface and the connectivity are essential for many algorithms
working on them. In this paper we present a flexible and efficient
remeshing framework that improves these intrinsic properties while
keeping the mesh geometrically close to the original surface. We
use a particle system approach and combine it with an incremental
connectivity optimization process to trim the mesh towards the
requirements imposed by the user. The particle system uniformly
distributes the vertices on the mesh, whereas the connectivity
optimization is done by means of \emph{Dynamic Connectivity Meshes},
a combination of local topological operators that lead to a fairly
regular connectivity. A dynamic skeleton ensures that our approach
is able to preserve surface features, which are particularly
important for the visual quality of the mesh. None of the
algorithms requires a global parameterization or patch layouting in
a preprocessing step but uses local parameterizations only. We also
show how this general framework can be put into practice and sketch
several application scenarios. In particular we will show how the
users can adapt the involved algorithms in a way that the resulting
remesh meets their personal requirements.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201843
Proceedings: 8th ACM Symposium on Solid Modeling and Applications (SM-03), ACM, 167-175 (2003)
en
oai:edoc.mpg.de:2018532010-12-0287:932
Superposition modulo a Shostak Theory
Ganzinger, Harald
Hillenbrand, Thomas
Waldmann, Uwe
Baader, Franz
expertsonly
We investigate superposition modulo a Shostak theory $T$ in order to
facilitate reasoning in the amalgamation of $T$ and a free
theory~$F$.
%
Free operators occur naturally e.\,g.\ in program verification
problems when abstracting over subroutines. If their behaviour in
addition can be specified axiomatically, much more of the program
semantics can be captured.
%
Combining the Shostak-style components for deciding the clausal
validity problem with the ordering and saturation techniques
developed for equational reasoning, we derive a refutationally
complete calculus on mixed ground clauses which result for example
from CNF transforming arbitrary universally quantified formulae.
%
The calculus works modulo a Shostak theory in the sense that it
operates on canonizer normalforms. For the Shostak solvers that we
study, coherence comes for free: no coherence pairs need to be
considered.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201853
urn:ISBN:3-540-40559-3
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 182-196 (2003)
en
oai:edoc.mpg.de:2018572012-09-1987:931
Space Efficient Hash Tables with Worst Case Constant Access Time
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul G.
Alt, Helmut
Habib, Michel
expertsonly
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing}
and show how this yields a simple hash table data structure that stores $n$
elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$.
Assuming uniform hashing, accessing or deleting table entries takes at most $d
= O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is
constant. This is the first dictionary that has worst case constant access time
and expected constant update time, works with $(1+\epsilon)\,n$ space, and
supports satellite information. Experiments indicate that $d=4$ choices suffice
for $\epsilon \approx 0.03$. We also describe a hash table data structure using
explicit constant time hash functions, using at most $d=
O(\ln^2\frac{1}{\epsilon})$ probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum
cardinality matchings in a rather natural model of sparse random bipartite
graphs.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201857
urn:ISBN:3-540-00623-0
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003), Springer, 271-282 (2003)
en
oai:edoc.mpg.de:2018692012-09-1987:931
Fast Lightweight Suffix Array Construction and Checking
Burkhardt, Stefan
Kärkkäinen, Juha
Baeza-Yates, R.
Chávez, E.
Crochemore, M.
expertsonly
We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.
Springer
2003
Conference-Paper
http://edoc.mpg.de/201869
urn:ISSN:0302-9743
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003, Springer, 55-69 (2003)
en
oai:edoc.mpg.de:2018722012-09-1987:934
Accuracy of 3D Range Scanners by Measurement of the Slanted Edge Modulation Transfer Function
Goesele, Michael
Fuchs, Christian
Seidel, Hans-Peter
Rioux, Marc
Godin, Guy
Boulanger, Pierre
expertsonly
We estimate the accuracy of a 3D~range scanner in terms of its
spatial frequency response. We determine a scanner's modulation
transfer function (MTF) in order to measure its frequency response.
A slanted edge is scanned from which we derive a superresolution
edge profile. Its Fourier transform is compared to the Fourier
transform of an ideal edge in order to determine the MTF of the
device. This allows us to determine how well small details can be
acquired by the 3D~scanner. We report the results of several
measurements with two scanners under various conditions.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201872
4th International Conference on 3-D Digital Imaging and Modeling, IEEE, 37-44 (2003)
en
oai:edoc.mpg.de:2018942010-12-0287:932
On Using Ground Joinable Equations in Equational Theorem Proving
Avenhaus, Jürgen
Hillenbrand, Thomas
Löchner, Bernd
expertsonly
When rewriting and completion techniques are used for equational
theorem proving, the axiom set is saturated with the aim to get a
rewrite system that is terminating and confluent on ground terms.
To reduce the computational effort it should (1) be powerful for
rewriting and (2) create not too many critical pairs. These problems
become especially important if some operators are associative and
commutative (\AC). We show in this paper how these two goals can be
reached to some extent by using ground joinable equations for
simplification purposes and omitting them from the generation of new
facts.
%
For the special case of \AC-operators we present a simple redundancy
criterion which is easy to implement, efficient, and effective in
practice, leading to significant speed-ups.
2003
Article
http://edoc.mpg.de/201894
urn:ISSN:0747-7171
Journal of Symbolic Computation, v.36, 217-233 (2003)
en
oai:edoc.mpg.de:2018982010-12-0287:932
A Lattice-Theoretic Framework For Circular Assume-Guarantee Reasoning
Maier, Patrick
notspecified
We develop an abstract lattice-theoretic framework within which
we study soundness and other properties of circular assume-
guarantee (A-G) rules constrained by side conditions. We
identify a particular side condition, non-blockingness, which
admits an intelligible inductive proof of the soundness of
circular A-G reasoning. Besides, conditional circular rules
based on non-blockingness turn out to be complete in various
senses and stronger than a large class of sound conditional A-G
rules. In this respect, our framework enlightens the foundations
of circular A-G reasoning.
Due to its abstractness, the framework can be instantiated to
many concrete settings. We show several known circular A-G rules
for compositional verification to be instances of our generic
rules. Thus, we do the circularity-breaking inductive argument
once to establish soundness of our generic rules, which then
implies soundness of all the instances without resorting to
technically complicated circularity-breaking arguments for each
single rule. In this respect, our framework unifies many
approaches to circular A-G reasoning and provides a starting
point for the systematic development of new circular A-G rules.
Universität des Saarlandes
2003
PhD-Thesis
http://edoc.mpg.de/201898
en
oai:edoc.mpg.de:2019492012-09-1987:934
Using Feature Flow Fields for Topological Comparison of Vector Fields
Theisel, Holger
Rössl, Christian
Seidel, Hans-Peter
Ertl, Thomas
Girod, Bernd
Greiner, Günther
Niemann, Heinrich
Seidel, Hans-Peter
Steinbach, Eckehard
Westermann, Rüdiger
expertsonly
In this paper we propose a new topology based metric for 2D vector
fields. This metric is based on the concept of feature flow
fields. We show that it incorporates both the characteristics and
the local distribution of the critical points while keeping the
computing time reasonably small even for topologically complex
vector fields. Finally, we apply the metric to track the
topological behavior in a time-dependent vector field, and to
evaluate a smoothing procedure on a noisy steady vector field.
Akademische Verlagsgesellschaft Aka
2003
Conference-Paper
http://edoc.mpg.de/201949
urn:ISBN:3-89838-048-3
Vision, Modeling and Visualization 2003 (VMV-03) : proceedings, Akademische Verlagsgesellschaft Aka, 521-528 (2003)
en
oai:edoc.mpg.de:2019522012-09-1987:934
Tree-based Triangle Mesh Connectivity Encoding
Rössl, Christian
Ivrissimtzis, Ioannis
Seidel, Hans-Peter
Cohen, Albert
Merrien, Jean-Louis
Schumaker, Larry L.
expertsonly
We present a divide and conquer algorithm for triangle mesh
connectivity encoding. As the algorithm traverses the mesh it
constructs a weighted binary tree that holds all information required for
reconstruction. This representation can be used for compression.We derive a new
iterative single-pass decoding algorithm, and we show how to exploit the tree
data structure
for generating stripifications for efficient rendering that come with a
guaranteed cost saving.
Nashboro Press
2003
Conference-Paper
http://edoc.mpg.de/201952
urn:ISBN:0-9728482-1-5
Curve and Surface Fitting: Saint-Malo 2002, Nashboro Press, 345-354 (2003)
en
oai:edoc.mpg.de:2019702012-09-1987:934
Image-Based Reconstruction of Spatial Appearance and Geometric Detail
Lensch, Hendrik P. A.
Kautz, Jan
Goesele, Michael
Heidrich, Wolfgang
Seidel, Hans-Peter
expertsonly
Real-world objects are usually composed of a number of different materials that
often show subtle changes even within a single material. Photorealistic
rendering of such objects requires accurate measurements of the reflection
properties of each material, as well as the spatially varying effects. We
present an image-based measuring method that robustly detects the different
materials of real objects and fits an average bidirectional reflectance
distribution function (BRDF) to each of them. In order to model local changes
as well, we project the measured data for each surface point into a basis
formed by the recovered BRDFs leading to a truly spatially varying BRDF
representation. Real-world objects often also have fine geometric detail that
is not represented in an acquired mesh. To increase the detail, we derive
normal maps even for non-Lambertian surfaces using our measured BRDFs. A high
quality model of a real object can be generated with relatively little input
data. The generated model allows for rendering under arbitrary viewing and
lighting conditions and realistically reproduces the appearance of the original
object.
Permission to make digital or hard copies of part or all of this work for
personal or classroom use is granted without fee provided that copies are not
made or distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for components
of this work owned by others than ACM must be honored. Abstracting with credit
is permitted. To copy otherwise, to republish, to post on servers or to
redistribute to lists, requires prior specific permission and/or a fee.
2003
Article
http://edoc.mpg.de/201970
ACM Transactions on Graphics, v.22, 234-257 (2003)
en
oai:edoc.mpg.de:2019732012-09-1987:934
Combining Topological Simplification and Topology Preserving Compression for 2D Vector Fields
Theisel, Holger
Rössl, Christian
Seidel, Hans-Peter
Rokne, Jon
Klein, Reinhard
Wang, Wenping
expertsonly
Topological simplification techniques and topology preserving
compression approaches for 2D vector fields have
been developed quite independently of each other. In this
paper we propose a combination of both approaches: a vector
field should be compressed in such a way that its important
topological features (both critical points and separatrices)
are preserved while its unimportant features are allowed
to collapse and disappear. To do so, a number of new
solutions and modifications of pre-existing algorithms are
presented. We apply the approach to a flow data set which,
is both large and topologically complex, and achieve significant
compression ratios there.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201973
11th Pacific Conference on Computer Graphics and Applications (PG-03), IEEE, 419-423 (2003)
en
oai:edoc.mpg.de:2019752012-09-1987:934
Accurate Light Source Acquisition and Rendering
Goesele, Michael
Granier, Xavier
Heidrich, Wolfgang
Seidel, Hans-Peter
Hodgins, Jessica K.
expertsonly
Realistic image synthesis requires both complex and realistic models
of real-world light sources and efficient rendering algorithms to deal
with them. In this paper, we describe a processing pipeline for
dealing with complex light sources from acquisition to global
illumination rendering. We carefully design optical filters to
guarantee high precision measurements of real-world light sources. We
discuss two practically feasible setups that allow us to measure light
sources with different characteristics.
Finally, we introduce an efficient importance sampling
algorithm for our representation that can be used, for example, in
conjunction with Photon Maps.
ACM
2003
Conference-Paper
http://edoc.mpg.de/201975
Proceedings of ACM SIGGRAPH 2003 (SIGGRAPH-03), ACM, 621-630 (2003)
en
oai:edoc.mpg.de:2019792012-09-1987:934
Interactive Visualization of Complex Real-World Light Sources
Granier, Xavier
Goesele, Michael
Heidrich, Wolfgang
Seidel, Hans-Peter
Rokne, Jon
Klein, Reinhard
Wang, Wenping
expertsonly
Interactive visualization of complex, real-world light
sources has so far not been feasible. In this paper, we
present an hardware accelerated direct lighting algorithm
based on a recent high quality light source acquisition technique.
By introducing an approximate reconstruction of the
exact model, a multi-pass rendering approach, and a compact
data representation, we are able to achieve interactive
frame rates. The method is part of the processing pipeline
from light source acquisition to high quality lighting of a
virtual world.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/201979
11th Pacific Conference on Computer Graphics and Applications (PG-03), IEEE, 59-66 (2003)
en
oai:edoc.mpg.de:2019802012-09-1987:931
Randomized Pursuit-Evasion in Graphs
Adler, Micah
Räcke, Harald
Sivadasan, Naveen
Sohler, Christian
Vöcking, Berthold
expertsonly
2003
Article
http://edoc.mpg.de/201980
urn:ISSN:0963-5483
Combinatorics, Probability and Computing, v.12, 225-244 (2003)
en
oai:edoc.mpg.de:2019852012-09-1987:934
Virtualizing Real-World Objects
Lensch, Hendrik P. A.
Kautz, Jan
Goesele, Michael
Lang, Jochen
Seidel, Hans-Peter
expertsonly
IEEE Computer Society
2003
Conference-Paper
http://edoc.mpg.de/201985
Computer Graphics International (CGI 2003), IEEE Computer Society, 134-141 (2003)
en
oai:edoc.mpg.de:2019982012-09-1987:933
Stochastic Gradient Descent Training of Ensembles of DT-CNN Classifiers for Digit Recognition
Merkwirth, Christian
Ogorzalek, Maciej
Wichard, Jörg Daniel
Ogorzalek, Maciej
Galias, Zbigniew
Garda, Bartłomiej
Kadeja, Bartłomiej
expertsonly
We show how to train Discrete Time Cellular Neural Networks
(DT-CNN) successfully by backpropagation to perform pattern
recognition on a data set of handwritten digits. By using concepts
and techniques from Machine Learning, we can outperform Support
Vector Machines (SVM) on this problem.
Faculty of Electrical Engineering, Automatics, Computer Science and Electronics, AGH University of Science and Technology
2003
Conference-Paper
http://edoc.mpg.de/201998
urn:ISBN:83-88309-95-1
Proceedings of the 16th European Conference on Circuit Theory and Design ECCTD'03, Faculty of Electrical Engineering, Automatics, Computer Science and Electronics, AGH University of Science and Technology, 337-341 (2003)
en
oai:edoc.mpg.de:2020192010-12-0287:932
New Directions in Instantiation-Based Theorem Proving
Ganzinger, Harald
Korovin, Konstantin
Kolaitis, Phokion
expertsonly
We consider instantiation-based theorem proving whereby
instances of clauses are generated by certain inferences, and where
inconsistency is detected by propositional tests.
We give a model construction proof of completeness by which restrictive
inference
systems as well as admissible simplification techniques can be
justified. Another contribution of the paper are novel inference
systems that allow one to also employ decision procedures for
first-order fragments more complex than propositional logic.
The decision procedure provides for an approximative consistency test, and the
instance generation inference system is a means of
successively refining the approximation.
IEEE
2003
Conference-Paper
http://edoc.mpg.de/202019
urn:ISBN:0-7695-1884-2
18th Annual IEEE Symposium on Logic in Computer Science (LICS-03), IEEE, 55-64 (2003)
en
oai:edoc.mpg.de:2020262010-12-0287:932
A Representation Theorem and Applications
Jaeger, Manfred
Nielsen, Thomas D.
Zhang, Nevin L.
expertsonly
We introduce a set of transformations on the set of all probability
distributions over a finite state space, and show that these
transformations are the only ones that preserve certain
elementary probabilistic relationships. This result provides
a new perspective on a variety of probabilistic inference
problems in which invariance considerations play a role.
Two particular applications we consider in this paper
are the development of an equivariance-based approach to
the problem of measure selection, and a new justification for
Haldane's prior as the distribution that encodes prior
ignorance about the parameter of a multinomial distribution.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202026
urn:ISBN:3-540-40494-5
Symbolic and Quantitative Approaches to Reasoning with Uncertainty :
7th European Conference, ECSQARU 2003, Springer, 50-61 (2003)
en
oai:edoc.mpg.de:2020272010-12-0287:932
Superposition with Equivalence Reasoning and Delayed Clause Normal Form Transformation
Ganzinger, Harald
Stuber, Jürgen
Baader, Franz
expertsonly
The paper describes a superposition calculus where quantifiers are eliminated
lazily. Superposition and simplification inferences may employ equivalences
that have arbitrary formulas at their smaller side. A closely related calculus
is implemented in the Saturate system and has shown useful on many examples, in
particular in set theory. The paper presents a completeness proof and reports
on practical experience obtained with the Saturate system.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202027
urn:ISBN:3-540-40559-3
Automated Deduction, CADE-19 : 19th International Conference on Automated Deduction, Springer, 335-349 (2003)
en
oai:edoc.mpg.de:2020322010-12-0287:932
Subsumption of Concepts in FL_0 for (Cyclic) Terminologies with Respect to Descriptive Semantics is PSPACE-complete
Kazakov, Yevgeny
de Nivelle, Hans
Calvanese, Diego
De Giacomo, Giuseppe
Franconi, Enrico
expertsonly
We close the gap in the complexity classification of subsumption in the simple
description logic ${\cal FL}_0$, which allows for
conjunctions and universal value restriction only. We prove that the
subsumption problem in ${\cal FL}_0$ is PSPACE-complete for descriptive
semantics when cyclic definitions are allowed. Our proof uses automata theory
and as a by-product we establish the PSPACE-completeness of a certain decision
problem for regular
languages.
CEUR
2003
Conference-Paper
http://edoc.mpg.de/202032
urn:ISSN:1613-0073
2003 International Workshop on Description Logics (DL-03), CEUR, 56-64 (2003)
en
oai:edoc.mpg.de:2020442012-09-1987:931
Smoothed Analysis of Three Combinatorial Problems
Banderier, Cyril
Beier, Rene
Mehlhorn, Kurt
Rovan, Branislav
Vojtáš, Peter
expertsonly
Smoothed analysis combines elements over worst-case and
average case analysis. For an instance $x$, the smoothed complexity is the
average complexity of an instance obtained from $x$ by a perturbation. The
smoothed complexity of a problem is the worst smoothed complexity of any
instance. Spielman and Teng introduced this notion for
continuous problems. We apply the concept to combinatorial problems and study
the smoothed complexity of three classical discrete problems: quicksort,
left-to-right maxima counting, and shortest paths.
Springer
2003
Conference-Paper
http://edoc.mpg.de/202044
urn:ISBN:3-540-40671-9
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003, Springer, 198-207 (2003)
en
oai:edoc.mpg.de:2020462012-09-1987:934
Compression of 2D vector fields under guaranteed topology preservation
Theisel, Holger
Rössl, Christian
Seidel, Hans-Peter
Brunet, Pere
Fellner, Dieter W.
expertsonly
In this paper we introduce a new compression technique for 2D vector fields
which preserves the complete topology, i.e., the critical points and the
connectivity of the separatrices. As the theoretical foundation of the
algorithm, we show in a theorem that for local modifications of a vector field,
it is possible to decide entirely by a local analysis whether or not the global
topology is preserved. This result is applied in a compression algorithm which
is based on a repeated local modification of the vector field - namely a
repeated edge collapse of the underlying piecewise linear domain. We apply the
compression technique to a number of data sets with a complex topology and
obtain significantly improved compression ratios in comparison to pre-existing
topology-preserving techniques.
Blackwell
2003
Conference-Paper
http://edoc.mpg.de/202046
EUROGRAPHICS 2003 (EUROGRAPHICS-03) : the European Association for Computer Graphics, 24th Annual Conference, Blackwell, 333-342 (2003)
en
oai:edoc.mpg.de:2311772012-09-1987:931
Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Albers, Susanne
Radzik, Tomasz
expertsonly
A minimal blocker in a bipartite graph $G$ is a minimal set of edges the
removal of which leaves no perfect matching in $G$. We give an explicit
characterization of the minimal blockers of a bipartite graph $G$. This result
allows us to obtain a polynomial
delay algorithm for finding all minimal blockers of a given bipartite graph.
Equivalently, this gives a polynomial delay algorithm for listing the
anti-vertices of the perfect matching polytope $P(G)=\{x\in
\RR^E~|~Hx=\be,~~x\geq 0\}$, where $H$ is the incidence matrix of $G$. We also
give similar generation algorithms for other related problems, including
generalized perfect matchings in bipartite graphs, and perfect 2-matchings in
general graphs.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231177
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 122-133 (2004)
en
oai:edoc.mpg.de:2311782012-09-1987:931
Enumerating Minimal Dicuts and Strongly Connected Subgraphs and Related Geometric Problems
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Bienstock, Daniel
Nemhauser, George
expertsonly
We consider the problems of enumerating all minimal strongly connected
subgraphs and all minimal dicuts of a given directed graph G=(V,E). We show
that the first of these problems can be solved in incremental polynomial time,
while the second problem is NP-hard: given a collection of minimal dicuts for
G, it is NP-complete to tell whether it can be extended. The latter result
implies, in particular, that for a given set of points , it is NP-hard to
generate all maximal subsets of contained in a closed half-space through the
origin. We also discuss the enumeration of all minimal subsets of whose convex
hull contains the origin as an interior point, and show that this problem
includes as a special case the well-known hypergraph transversal problem.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231178
urn:ISBN:3-540-22113-1
Integer programming and combinatorial optimization : 10th International IPCO Conference, Springer, 152-162 (2004)
en
oai:edoc.mpg.de:2311792012-09-1987:931
Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Farach-Colton, Martin
expertsonly
Given a finite set $V$, and integers $k \geq 1$ and $r \geq 0$,
denote by $\AA(k,r)$ the class of hypergraphs $\cA \subseteq 2^V$
with $(k,r)$-bounded intersections, i.e. in which
the intersection of any $k$ distinct hyperedges has size at most $r$. We
consider the problem $MIS(\cA,\cI)$:
given a hypergraph $\cA$ and a subfamily $\cI \subseteq \In$,
of its maximal independent sets (MIS) $\In$, either extend this subfamily by
constructing a new MIS $I \in \In \setminus \cI$
or prove that there are no more MIS, that is $\cI = \In$.
We show that for hypergraphs $\cA\in\AA(k,r)$ with $k+r\le const$, problem
MIS$(\cA,\cI)$ is NC-reducible to problem MIS$(\cA',\emptyset)$ of generating a
single MIS for
a partial subhypergraph $\cA'$ of $\cA$. In particular, for this class of
hypergraphs, we get an incremental polynomial algorithm for generating all MIS.
Furthermore, combining this result with the currently known algorithms for
finding a single maximal independent set of a hypergraph, we obtain efficient
parallel algorithms for incrementally generating all MIS for hypergraphs in the
classes $\AA(1,c)$, $\AA(c,0)$, and $\AA(2,1)$, where $c$ is a constant. We
also show that,
for $\cA \in \AA(k,r)$, where $k+r\le const$, the problem of
generating all MIS of $\cA$ can be solved in incremental polynomial-time with
space polynomial only in the size of $\cA$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231179
urn:ISBN:3-540-21258-2
LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Springer, 488-498 (2004)
en
oai:edoc.mpg.de:2311802012-09-1987:931
Generating Paths and Cuts in Multi-pole (Di)graphs
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Makino, Kazuhisa
Fiala, Jirí
Koubek, Václav
Kratochvíl, Jan
expertsonly
Let G=(V,E) be a (directed) graph with vertex set V and edge (arc) set E. Given
a set of (source-sink) pairs of vertices of G, an important problem that
arises in the computation of network reliability is the enumeration of minimal
subsets of edges (arcs) that connect/disconnect all/at least one of the given
source-sink pairs of . For undirected graphs, we show that the enumeration
problems for conjunctions of paths and disjunctions of cuts can be solved in
incremental polynomial time. For directed graphs both of these problems are
NP-hard. We also give a polynomial delay algorithm for enumerating minimal sets
of arcs connecting respectively two given nodes s1 and s2 to a given vertex t1,
and each vertex of a given subset of vertices T2.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231180
urn:ISBN:3-540-22823-3
Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004, Springer, 298-309 (2004)
en
oai:edoc.mpg.de:2311812012-09-1987:931
An Efficient Implementation of a Joint Generation Algorithm
Boros, Endre
Elbassioni, Khaled
Gurvich, Vladimir
Khachiyan, Leonid
Ribeiro, Celso C.
Martins, Simone L.
expertsonly
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property
defined over the elements of $\cC$. We consider the problems of incrementally
generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal
subsets satisfying property $\pi$ and all maximal subsets not satisfying
property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle.
Problems of this type arise in many practical applications. It is known that
the above joint generation problem can be solved in incremental
quasi-polynomial time. In this paper, we present an efficient implementation of
this procedure. We present experimental results to evaluate our implementation
for a number of interesting monotone properties $\pi$.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231181
urn:ISBN:3-540-22067-4
Experimental and efficient algorithms : Third International Workshop, WEA 2004, Springer, 114-128 (2004)
en
oai:edoc.mpg.de:2311882012-09-1987:931
Engineering an External Memory Minimum Spanning Tree Algorithm
Dementiev, Roman
Sanders, Peter
Schultes, Dominik
Sibeyn, Jop F.
Lévy, Jean-Jacques
Mayr, Ernst W.
Mitchell, John C.
expertsonly
We develop an external memory algorithm for computing minimum spanning
trees. The algorithm is considerably simpler than previously known
external memory algorithms for this problem and needs a factor of at
least four less I/Os for realistic inputs.
Our implementation indicates that this algorithm processes graphs only
limited by the disk capacity of most current machines in time no more
than a factor 2--5 of a good internal algorithm with sufficient memory
space.
Kluwer
2004
Conference-Paper
http://edoc.mpg.de/231188
urn:ISBN:1-4020-8140-5
3rd IFIP International Conference on Theoretical Computer Science (TSC2004), Kluwer, 195-208 (2004)
en
oai:edoc.mpg.de:2311922012-09-1987:931
Algorithms for recognizing coordinates in two variables over UFD's
El Kahoui, M'hammed
Gutierrez, Jaime
expertsonly
ACM
2004
Conference-Paper
http://edoc.mpg.de/231192
urn:ISBN:1-58113-827-X
Proceedings of the 2004 International Symposium Symbolic and Algebraic Computation (ISSAC-04), ACM, 135-140 (2004)
en
oai:edoc.mpg.de:2311932012-09-1987:931
Scalable Multimedia Disk Scheduling
Elbassioni, Khaled
Mokbel, Mohamed F.
Aref, Walid G.
Kamel, Ibrahim
expertsonly
A new multimedia disk scheduling algorithm, termed Cascaded-SFC, is presented.
The Cascaded-SFC multimedia disk scheduler is applicable in environments where
multimedia data requests arrive with different quality of service (QoS)
requirements such as real-time deadline and user priority. Previous work on
disk scheduling has focused on optimizing the seek times and/or meeting the
real-time deadlines. The Cascaded-SFC disk scheduler provides a unified
framework for multimedia disk scheduling that scales with the number of
scheduling parameters. The general idea is based on modeling the multimedia
disk requests as points in multiple multi-dimensional sub-spaces, where each of
the dimensions represents one of the parameters (e.g., one dimension represents
the request deadline, another represents the disk cylinder number, and a third
dimension represents the priority of the request, etc.). Each multi-dimensional
sub-space represents a subset of the QoS parameters that share some common
scheduling characteristics. Then the multimedia disk scheduling problem reduces
to the problem of finding a linear order to traverse the multi-dimensional
points in each sub-space. Multiple space-filling curves are selected to fit the
scheduling needs of the QoS parameters in each sub-space. The orders in each
sub-space are integrated in a cascaded way to provide a total order for the
whole space. Comprehensive experiments demonstrate the efficiency and
scalability of the Cascaded-SFC disk scheduling algorithm over other disk
schedulers.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231193
urn:ISBN:0-7695-2065-0
20th International Conference on Data Engineering, ICDE 2004, IEEE, 498-509 (2004)
en
oai:edoc.mpg.de:2311942012-09-1987:931
Incremental Algorithms for Facility Location and k-Median
Fotakis, Dimitris
Albers, Susanne
Radzik, Tomasz
expertsonly
In the incremental versions of Facility Location and k-Median, the demand
points arrive one at a time and the algorithm must maintain a good solution by
either adding each new demand to an existing cluster or placing it in a new
singleton cluster. The algorithm can also merge some of the existing clusters
at any point in time. We present the first incremental algorithm for Facility
Location with uniform facility costs which achieves a constant performance
ratio and the first incremental algorithm for k-Median which achieves a
constant performance ratio using O(k) medians.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231194
urn:ISBN:3-540-23025-4
Algorithms – ESA 2004: 12th Annual European Symposium, Springer, 347-358 (2004)
en
oai:edoc.mpg.de:2311992012-09-1987:931
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
Funke, Stefan
Matijevic, Domagoj
Sanders, Peter
expertsonly
We investigate algorithms for computing
energy efficient paths in ad-hoc radio networks.
We demonstrate how advanced data structures from computational
geometry can be employed to preprocess the position of
radio stations in such a way that approximately
energy optimal paths can be retrieved in constant time, i.e.,
independent of the network size.
We put particular emphasis on actual implementations which
demonstrate that large constant factors hidden in the theoretical
analysis are not a big problem in practice.
University of Bologna
2004
Conference-Paper
http://edoc.mpg.de/231199
First International Workshop on Algorithms for Wireless and Mobile Networks, University of Bologna, 97-111 (2004)
en
oai:edoc.mpg.de:2312222012-09-1987:931
A simpler linear time 2/3 - eps approximation for maximum weight matching
Pettie, Seth
Sanders, Peter
expertsonly
2004
Article
http://edoc.mpg.de/231222
Information Processing Letters, v.91, 271-276 (2004)
en
oai:edoc.mpg.de:2312242012-09-1987:931
Online scheduling with bounded migration
Sanders, Peter
Sivadasan, Naveen
Skutella, Martin
Díaz, Josep
Karhumäki, Juhani
Lepistö, Arto
Sannella, Donald
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231224
urn:ISBN:3-540-22849-7
Automata, languages and programming : 31st International Colloquium, ICALP 2004, Springer, 1111-1122 (2004)
en
oai:edoc.mpg.de:2312262012-09-1987:931
Topology matters: Smoothed competitiveness of metrical task systems
Schäfer, Guido
Sivadasan, Naveen
Diekert, Volker
Habib, Michel
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231226
urn:ISBN:3-540-21236-1
21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04), Springer, 489-500 (2004)
en
oai:edoc.mpg.de:2312312012-09-1987:931
Controlled Perturbation for Voronoi Diagrams
Klein, Christian
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231231
en
oai:edoc.mpg.de:2312522010-12-0287:932
Fast Term Indexing with Coded Context Trees
Ganzinger, Harald
Nieuwenhuis, Robert
Nivela, Pilar
expertsonly
Indexing data structures have a crucial impact on
the performance of automated theorem provers. Examples are discrimination
trees, which are like tries where terms are seen as strings and common prefixes
are shared, and substitution trees, where terms keep their tree structure and
all common contexts can be shared. Here we describe a new indexing data
structure, called context trees, where, by means of a limited kind of context
variables, also common subterms can be shared, even if they occur below
different function symbols. Apart from introducing the concept, we also provide
evidence for its practical value. We show how context trees can be implemented
by means of abstract machine instructions. Experiments with matching benchmarks
show that our implementation is competitive with tightly coded current
state-of-the-art implementations of the other main techniques. In particular
space consumption of context trees is significantly less than for other index
structures.
2004
Article
http://edoc.mpg.de/231252
Journal of Automated Reasoning, v.32, 103-120 (2004)
en
oai:edoc.mpg.de:2312582010-12-0287:932
A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded Fragment
Kazakov, Yevgeny
Alferes, José Júlio
Leite, João
expertsonly
We consider a two-variable guarded fragment with number restrictions for binary
relations and give a satisfiability preserving transformation of formulas in
this fragment to the three-variable guarded fragment. The translation can be
computed in polynomial time and produces a formula that is linear in the size
of the initial formula even for the binary coding of number restrictions. This
allows one to reduce reasoning problems for many description logics to the
satisfiability problem for the guarded fragment.
Springer
© Springer-Verlag
2004
Conference-Paper
http://edoc.mpg.de/231258
urn:ISBN:3-540-23242-7
Logics in artificial intelligence : 9th European Conference, JELIA 2004, Springer, 372-384 (2004)
en
oai:edoc.mpg.de:2312652010-12-0287:932
Robust Pole Clustering of Parametric Uncertain Systems Using Interval Methods
Ratschan, Stefan
Vehi, Josep
Bittanti, Sergio
expertsonly
In this paper a new methodology to solve the pole clustering problem for
parametric
uncertain systems is introduced: The problem of clustering the closed loop
poles into
prescribed D-regions in the complex plane is stated as a quantified
constraint problem
that represents bounded uncertain parameters by intervals; and an
engineering-oriented
approach based on interval methods is developed to solve this quantified
constraint
problem. The result is a new, robust, reliable and
design oriented method to deal with parametric uncertain systems.
The methodology presented in this paper allows to find a good
controller that places the closed loop poles in the desired
location in the complex plane. In case there is no solution, the
method allows also to "tune" the problem, either enlarging the pole
locations or reducing the uncertainty domain.
The approach presented in this paper can be used either for linear
or non-linear systems and for any kind of parametric bounded
uncertainty.
Several simple examples illustrate the uses, limits and scope of
the methodology.
Publ. for the International Federation of Automatic Control by Elsevier
2004
Conference-Paper
http://edoc.mpg.de/231265
urn:ISBN:0-08-044012-6
Robust control design 2003 : (ROCOND 2003) ; a proceedings volume from the 4th IFAC symposium, Publ. for the International Federation of Automatic Control by Elsevier, 323-328 (2004)
en
oai:edoc.mpg.de:2312712010-12-0287:932
A Superposition View on Nelson-Oppen
Hillenbrand, Thomas
Sattler, Ulrike
expertsonly
CEUR
2004
Conference-Paper
http://edoc.mpg.de/231271
urn:ISSN:1613-0073
Contributions to the Doctoral Programme of the 2nd International Joint Conference on Automated Reasoning, CEUR, 16-20 (2004)
en
oai:edoc.mpg.de:2312722010-12-0287:932
Instance Generation Methods for Automated Reasoning
Jacobs, Swen
expertsonly
There are several different methods which try to decide unsatisfiability of a
set of clauses by generating an unsatisfiable set of instances of the input
clauses. We consider the \emph{Disconnection Tableau Calculus}, \emph{Primal
Partial Instantiation} and \emph{Resolution-Based Instance-Generation}, all of
which can be seen as refinements of the clause linking approach. We present
these three methods accurately and in a consistent manner. Similarities and
equivalences of the methods will be pointed out and we will show if proofs of
one calculus can be simulated by a different method, generating only instances
from the given proof.
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231272
en
oai:edoc.mpg.de:2313092012-09-1987:934
Interactive {Ray} {Tracing} of {Free-Form} {Surfaces}
Benthin, Carsten
Wald, Ingo
Slusallek, Philipp
van Zijl, Lynette
Marais, Patrick
expertsonly
Even though the speed of software ray tracing has recently been
increased to interactive performance even on standard PCs, these
systems usually only supported triangles as geometric primitives.
Directly handling free-form surfaces such as spline or subdivision
surfaces instead of first tessellating them offers many advantages
such as higher precision results, reduced memory requirements, and
faster preprocessing due to less primitives. However, existing
algorithms for ray tracing free-form surfaces are much too slow for
interactive use.
In this paper we present a simple and generic approach for ray
tracing free-form surfaces together with specific implementations
for cubic B\'ezier and Loop subdivision surfaces. We show that our
approach allows to increase the performance by more than an order of
magnitude, requires only constant memory, and is largely independent
on the total number of free-form primitives in a scene. Examples
demonstrate that even scene with over one hundred thousand free-form
surfaces can be rendered interactively on a single processor at
video resolution.
ACM
2004
Conference-Paper
http://edoc.mpg.de/231309
urn:ISBN:1-58113-863-6
Proceedings AFRIGRAPH 2004 : 3rd International Conference on Virtual Reality, Computer Graphics, Visualisation and Interaction in Africa, ACM, 99-106 (2004)
en
oai:edoc.mpg.de:2313212012-09-1987:934
DISCO - Acquisition of Translucent Objects
Goesele, Michael
Lensch, Hendrik P. A.
Lang, Jochen
Fuchs, Christian
Seidel, Hans-Peter
Marks, Joe
expertsonly
Translucent objects are characterized by diffuse light scattering
beneath the object's surface. Light enters and leaves an object at
possibly distinct surface locations. This paper presents the first
method to acquire this transport behavior for arbitrary
inhomogeneous objects. Individual surface points are illuminated in
our DISCO measurement facility and the object's impulse response is
recorded with a high-dynamic range video camera. The acquired data
is resampled into a hierarchical model of the object's light
scattering properties. Missing values are consistently interpolated
resulting in measurement-based, complete and accurate
representations of real translucent objects which can be rendered
with various algorithms.
2004
Article
http://edoc.mpg.de/231321
urn:ISSN:0730-0301
ACM Transactions on Graphics, v.23, 835-844 (2004)
en
oai:edoc.mpg.de:2313242012-09-1987:934
Realtime Caustics using Distributed Photon Mapping
Günther, Johannes
Wald, Ingo
Slusallek, Philipp
Keller, Alexander
Jensen, Henrik Wann
expertsonly
With the advancements in realtime ray tracing and new global illumination
algorithms we are now able to render the most important illumination effects at
interactive rates. One of the major remaining issues is the fast and efficient
simulation of caustic illumination, such as e.g. the illumination from a car
headlight. The photon mapping algorithm is a simple and robust approach that
generates high-quality results and is the preferred algorithm for computing
caustic illumination. However, photon mapping has a number of properties that
make it rather slow on today s processors. Photon mapping has also been
notoriously difficult to parallelize efficiently.
In this paper, we present a detailed analysis of the performance issues of
photon mapping together with signifi- cant performance improvements for all
aspects of the photon mapping technique. The solution forms a complete
framework for realtime photon mapping that efficiently combines realtime ray
tracing, optimized and improved photon mapping algorithms, and efficient
parallelization across commodity PCs. The presented system achieves realtime
photon mapping performance of up to 22 frames per second on non-trivial scenes,
while still allowing for interactively updating all aspects of the scene,
including lighting, material properties, and geometry.
Eurographics
2004
Conference-Paper
http://edoc.mpg.de/231324
urn:ISBN:3-905673-12-6
Rendering Techniques 2004 : Eurographics Symposium on Rendering, Eurographics, 111-121 (2004)
en
oai:edoc.mpg.de:2313382012-09-1987:934
Differential Coordinates for Interactive Mesh Editing
Lipman, Yaron
Sorkine, Olga
Cohen-Or, Daniel
Levin, David
Rössl, Christian
Seidel, Hans-Peter
Giannini, Franca
Pasko, Alexander
expertsonly
One of the main challenges in editing a mesh is to retain the visual appearance
of the surface after applying various modifications. In this paper we advocate
the use of linear differential coordinates as means to preserve the
high-frequency detail of the surface. The differential coordinates represent
the details and are defined by a linear transformation of the mesh vertices.
This allows the reconstruction of the edited surface by solving a linear system
that satisfies the reconstruction of the local details in least squares sense.
Since the differential coordinates are defined in a global coordinate system
they are not rotation-invariant. To compensate for that, we rotate them to
agree with the rotation of an approximated local frame. We show that the linear
least squares system can be solved fast enough to guarantee interactive
response time thanks to a precomputed factorization of the coefficient matrix.
We demonstrate that our approach enables to edit complex detailed meshes while
keeping the shape of the details in their natural orientation.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231338
urn:ISBN:0-7695-1909-1
Shape Modeling International 2004 (SMI 2004), IEEE, 181-190 (2004)
en
oai:edoc.mpg.de:2313402012-09-1987:934
A Hybrid Hardware-Accelerated Algorithm for High Quality Rendering of Visual Hulls
Li, Ming
Magnor, Marcus
Seidel, Hans-Peter
Heidrich, Wolfgang
Balakrishnan, Ravin
expertsonly
In this paper, a novel hybrid algorithm is presented for the fast construction
and high-quality rendering of visual hulls. We combine the strengths of two
complementary hardware-accelerated approaches: direct constructive solid
geometry (CSG) rendering and texture mapping-based visual cone trimming. The
former approach completely eliminates the aliasing artifacts inherent in the
latter, whereas the rapid speed of the latter approach compensates for the
performance deficiency of the former. Additionally, a new view-dependent
texture mapping method is proposed. This method makes efficient use of graphics
hardware to perform per-fragment blending weight computation, which yields
better rendering quality. Our rendering algorithm is integrated in a
distributed system that is capable of acquiring synchronized video streams and
rendering visual hulls in real time or at interactive frame rates from up to
eight reference views.
Canadian Information Processing Society
2004
Conference-Paper
http://edoc.mpg.de/231340
urn:ISBN:1-56881-227-2
Graphics Interface 2004, Canadian Information Processing Society, 41-48 (2004)
en
oai:edoc.mpg.de:2313422012-09-1987:934
Perception-motivated High Dynamic Range Video Encoding
Mantiuk, Rafal
Krawczyk, Grzegorz
Myszkowski, Karol
Seidel, Hans-Peter
Marks, Joe
expertsonly
Due to rapid technological progress in high dynamic range (HDR)
video capture and display, the efficient storage and
transmission of such data is crucial for the completeness of any HDR
imaging pipeline. We propose a new approach for
inter-frame encoding of HDR video, which is embedded in the
well-established MPEG-4 video compression standard. The key
component of our technique is luminance quantization
that is optimized for the contrast threshold perception in the
human visual system. The quantization
scheme requires only 10--11 bits to encode 12 orders of magnitude of
visible luminance range and does not lead to perceivable contouring
artifacts. Besides video encoding, the proposed quantization
provides perceptually-optimized luminance sampling for fast
implementation of any
global tone mapping operator using a lookup table.
To improve the quality of synthetic video sequences, we introduce
a coding scheme for discrete cosine transform (DCT) blocks with
high contrast. We demonstrate the capabilities of HDR video in
a player, which enables decoding, tone mapping, and applying
post-processing effects in real-time. The tone mapping algorithm as well
as its parameters can be changed interactively while the video is playing.
We can simulate post-processing
effects such as glare, night vision, and motion blur, which appear
very realistic due to the usage of HDR data.
2004
Article
http://edoc.mpg.de/231342
urn:ISSN:0730-0301
ACM Transactions on Graphics, v.23, 733-741 (2004)
en
oai:edoc.mpg.de:2313432012-09-1987:934
Visible Difference Predictor for High Dynamic Range Images
Mantiuk, Rafal
Myszkowski, Karol
Seidel, Hans-Peter
Thissen, Wil
Wieringa, Peter
Pantic, Maja
Ludema, Marcel
expertsonly
Since new imaging and rendering systems commonly use physically
accurate lighting information in the form of High-Dynamic Range
data, there is a need for an automatic visual quality assessment of the
resulting images. In this work we extend the Visual Difference Predictor (VDP)
developed by Daly to handle HDR data. This let us predict if a human observer
is able to perceive differences for a pair of HDR images under the adaptation
conditions corresponding to the real scene observation.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231343
urn:ISBN:0-7803-8567-5
2004 IEEE International Conference on Systems, Man & Cybernetics, IEEE, 2763-2769 (2004)
en
oai:edoc.mpg.de:2313442012-09-1987:934
Fast and {Accurate} {Ray-Voxel} {Intersection} {Techniques} for {Iso-Surface} {Ray} {Tracing}
Marmitt, Gerd
Kleer, Andreas
Friedrich, Heiko
Wald, Ingo
Slusallek, Philipp
Girod, Bernd
Magnor, Marcus
Seidel, Hans-Peter
expertsonly
Visualizing iso-surfaces of volumetric data sets is becoming
increasingly important for many practical applications. One crucial
task in iso-surface ray tracing is to find the correct intersection
of a ray with the trilinear-interpolated implicit surface defined by
the data values at the vertices of a given voxel. Currently
available solutions are either accurate but slow or they provide
fast but only approximate solutions.
In this paper, we analyze the available techniques and present a new
intersection algorithm. We compare and evaluate the new algorithm
against previous approaches using both synthetic test cases and real
world data sets.
The new algorithm is roughly three times faster but provides the
same image quality and better numerical stability as previous
accurate solutions.
Akademische Verlagsgesellschaft Aka
2004
Conference-Paper
http://edoc.mpg.de/231344
urn:ISBN:3-89838-058-0
Vision, modeling, and visualization 2004 (VMV-04), Akademische Verlagsgesellschaft Aka, 429-435 (2004)
en
oai:edoc.mpg.de:2313472012-09-1987:934
Reconstruction of Volume Data with Quadratic Super Splines
Rössl, Christian
Zeilfelder, Frank
Nürnberger, Günther
Seidel, Hans-Peter
expertsonly
We propose a new approach to reconstruct nondiscrete models from gridded volume
samples. As a model, we use quadratic trivariate super splines on a uniform
tetrahedral partition. We discuss the smoothness and approximation properties
of our model and compare to alternative piecewise polynomial constructions. We
observe as a non-standard phenomenon that the derivatives of our splines yield
optimal approximation order for smooth data, while the theoretical error of the
values is nearly optimal due to the averaging rules. Our approach enables
efficient reconstruction and visualization of the data. As the piecewise
polynomials are of the lowest possible total degree two, we can efficiently
determine exact ray intersections with an iso-surface for ray-casting.
Moreover, the optimal approximation properties of the derivatives allow to
simply sample the necessary gradients directly from the polynomial pieces of
the splines. Our results confirm the efficiency of the quasi-interpolating
method and demonstrate high visual quality for rendered isosurfaces.
2004
Article
http://edoc.mpg.de/231347
IEEE Transactions on Visualization and Computer Graphics, v.10, 397-409 (2004)
en
oai:edoc.mpg.de:2313482012-09-1987:934
Spline Approximation of General Volumetric Data
Rössl, Christian
Zeilfelder, Frank
Nürnberger, Günther
Seidel, Hans-Peter
Elber, Gershon
Patrikalakis, Nick
Brunet, Pere
expertsonly
We present an efficient algorithm for approximating huge general
volumetric data sets, i.e.~the data is given over arbitrarily shaped
volumes and consists of up to millions of samples. The method is based
on cubic trivariate splines, i.e.~piecewise polynomials of total
degree three defined w.r.t. uniform type-6 tetrahedral partitions of
the volumetric domain. Similar as in the recent bivariate
approximation approaches, the splines in three variables
are automatically determined from the discrete data as a result of a
two-step method, where local discrete least
squares polynomial approximations of varying degrees are extended by
using natural conditions, i.e.the continuity and smoothness properties
which determine the underlying spline space. The main advantages of
this approach with linear algorithmic complexity are as follows: no
tetrahedral partition of the volume data is needed, only small
linear systems have to be solved, the local variation and
distribution of the data is automatically adapted,
Bernstein-B{\'e}zier techniques well-known in Computer Aided
Geometric Design (CAGD) can be fully exploited, noisy data are
automatically smoothed. Our numerical examples with huge data sets
for synthetic data as well as some real-world data confirm the
efficiency of the methods, show the high quality of the spline
approximation, and illustrate that the rendered iso-surfaces inherit
a visual smooth appearance from the volume approximating splines.
Eurographics
2004
Conference-Paper
http://edoc.mpg.de/231348
urn:ISBN:3-905673-55-X
Proceedings of the 9th ACM Symposium on Solid Modeling and Applications (SM 2004), Eurographics, 71-82 (2004)
en
oai:edoc.mpg.de:2313502012-09-1987:934
Laplacian Surface Editing
Sorkine, Olga
Lipman, Yaron
Cohen-Or, Daniel
Alexa, Marc
Rössl, Christian
Seidel, Hans-Peter
Scopigno, Roberto
Zorin, Denis
Fellner, Dieter
Spencer, Stephen
expertsonly
Surface editing operations commonly require geometric details of the surface to
be preserved as much as possible. We argue that geometric detail is an
intrinsic property of a surface and that, consequently, surface editing is best
performed by operating over an intrinsic surface representation. We provide
such a representation of a surface, based on the Laplacian of the mesh, by
encoding each vertex relative to its neighborhood. The Laplacian of the mesh is
enhanced to be invariant to locally linearized rigid transformations and
scaling. Based on this Laplacian representation, we develop useful editing
operations: interactive free-form deformation in a region of interest based on
the transformation of a handle, transfer and mixing of geometric details
between two surfaces, and transplanting of a partial surface mesh onto another
surface. The main computation involved in all operations is the solution of a
sparse linear system, which can be done at interactive rates. We demonstrate
the effectiveness of our approach in several examples, showing that the editing
operations change the shape while respecting the structural geometric detail.
Eurographics
2004
Conference-Paper
http://edoc.mpg.de/231350
urn:ISBN:3-905673-13-4/1727-8384
SGP 2004 (SGP-04) : Symposium on Geometry Processing, Eurographics, 179-188,274 (2004)
en
oai:edoc.mpg.de:2313542012-09-1987:934
Topology Preserving Thinning of Vector Fields on Triangular Meshes
Theisel, Holger
Rössl, Christian
Seidel, Hans-Peter
Dodgson, Neil A.
Floater, Michael S.
Sabin, Malcom A.
expertsonly
We consider the topology of piecewise linear vector fields whose domain is a
piecewise linear 2-manifold, i.e. a triangular mesh. Such vector fields can
describe simulated 2-dimensional flows, or they may reflect geometric
properties of the underlying mesh. We introduce a thinning technique which
preserves the complete topology of the vector field, i.e. the critical points
and separatrices. As the theoretical foundation, we have shown in an earlier
paper that for local modiØcations of a vector field, it is possible to decide
entirely by a local analysis whether or not the global topology is preserved.
This result is applied in a number of compression algorithms which are based on
a repeated local modification of the vector field, namely a repeated
edge-collapse of the underlying piecewise linear domain.
Springer
2004
InBook
http://edoc.mpg.de/231354
urn:ISBN:3-540-21462-3
Advances in Multiresolution for Geometric Modelling, 353-366 (2004)
en
oai:edoc.mpg.de:2313552012-09-1987:934
Normal Based Estimation of the Curvature Tensor for Triangular Meshes
Theisel, Holger
Rössl, Christian
Zayer, Rhaleb
Seidel, Hans-Peter
Cohen-Or, Daniel
Ko, Hyeong-Seok
Terzopoulos, Demetri
Warren, Joe
expertsonly
We introduce a new technique for estimating the curvature tensor of a
triangular mesh. The input of the algorithm is only a single triangle equipped
with its (exact or estimated) vertex normals. This way we get a smooth function
of the curvature tensor inside each triangle of the mesh. We show that the
error of the new method is comparable with the error of a cubic fitting
approach if the incorporated normals are estimated. If the exact normals of the
underlying surface are available at the vertices, the error drops signifi-
cantly. We demonstrate the applicability of the new estimation at a rather
complex data set.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231355
urn:ISBN:0-7695-2234-3
12th Pacific Conference on Computer Graphics and Applications, PG 2004, IEEE, 288-297 (2004)
en
oai:edoc.mpg.de:2313642012-09-1987:934
An Interactive Out-of-Core Rendering Framework for Visualizing Massively Complex Models
Wald, Ingo
Dietrich, Andreas
Slusallek, Philipp
Keller, Alexander
Jensen, Henrik Wann
expertsonly
With the tremendous advances in both hardware capabilities and
rendering algorithms, rendering performance is steadily increasing.
Even consumer graphics hardware can render many million
triangles per second. However, scene complexity seems to be rising
even faster than rendering performance, with no end to even more
complex models in sight.
In this paper, we are targeting the interactive visualization of the
``Boeing 777'' model, a highly complex model of 350 \emph{million}
individual triangles, which -- due to its sheer size and complex
internal structure -- simply cannot be handled satisfactorily by
today's techniques. To render this model, we use a combination of
real-time ray tracing, a low-level out of core caching and demand
loading strategy, and a hierarchical, hybrid
volumetric/lightfield-like approximation scheme for representing
not-yet-loaded geometry.
%
With this approach, we are able to render the full
777 model at several frames per second even on a single
commodity desktop PC.
Eurographics
2004
Conference-Paper
http://edoc.mpg.de/231364
urn:ISBN:3-905673-12-6
Rendering Techniques 2004 : Eurographics Symposium on Rendering, Eurographics, 81-92 (2004)
en
oai:edoc.mpg.de:2313722012-09-1987:934
Multi-Video Compression in Texture Space
Ziegler, Gernot
Lensch, Hendrik P. A.
Ahmed, Naveed
Magnor, Marcus
Seidel, Hans-Peter
expertsonly
We present a model-based approach to encode multiple synchronized
video streams depicting a dynamic scene from different viewpoints.
With approximate 3D scene geometry available, we compensate for
motion as well as disparity by transforming all video images
to object textures prior to compression.
A two-level hierarchical coding strategy is employed to efficiently
exploit inter-texture coherence as well as to ensure quick random
access during decoding.
Experimental validation shows that attainable compression ratios
range up to 50:1 without subsampling.
The proposed coding scheme is intended for use in conjunction with
Free-Viewpoint Video and 3D-TV applications.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231372
urn:ISBN:0-7803-8555-1
11th IEEE International Conference on Image Processing (ICIP 2004), IEEE, 2467-2470 (2004)
en
oai:edoc.mpg.de:2313912012-09-1987:930
Probabilistic Ranking of Database Query Results
Chaudhuri, Surajit
Das, Gautam
Hristidis, Vagelis
Weikum, Gerhard
Nascimento, Mario A.
Özsu, M. Tamer
Kossmann, Donald
Miller, Renee J.
Blakeley, Jose A.
Schiefer, K. Bernhard
expertsonly
We investigate the problem of ranking answers to a database query when many
tuples are returned. We adapt and apply principles of probabilistic models from
Information Retrieval structured data. Our proposed solution is domain
independent. It leverages data and workload statistics and corelations. Our
ranking functions can be further customized for different applications. We
present results of preliminary experiments which demonstrate the efficiency as
well as the quality of our ranking system.
Morgan Kaufmann
2004
Conference-Paper
http://edoc.mpg.de/231391
urn:ISBN:0-12-088469-0
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB), Morgan Kaufmann, 888-899 (2004)
en
oai:edoc.mpg.de:2313942012-09-1987:930
COMPASS: A Concept-based {Web} Search Engine for {HTML,} {XML,} and {Deep} {Web} {Data}
Graupmann, Jens
Biwer, Michael
Zimmer, Christian
Zimmer, Patrick
Bender, Matthias
Theobald, Martin
Weikum, Gerhard
Nascimento, Mario A.
Özsu, M. Tamer
Kossmann, Donald
Miller, Renee J.
Blakeley, Jose A.
Schiefer, K. Bernhard
expertsonly
Morgan Kaufmann
2004
Conference-Paper
http://edoc.mpg.de/231394
urn:ISBN:0-12-088469-0
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB), Morgan Kaufmann, 1313-1316 (2004)
en
oai:edoc.mpg.de:2313952012-09-1987:930
Concept-Based Search on Semi-structured Data Exploiting Mined Semantic Relations
Graupmann, Jens
Lindner, Wolfgang
Mesiti, Marco
Türker, Can
Tzitzikas, Yannis
Vakali, Athena
notspecified
Springer
2004
Conference-Paper
http://edoc.mpg.de/231395
urn:ISBN:3-540-23305-9
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb, Springer, 34-43 (2004)
en
oai:edoc.mpg.de:2313972012-09-1987:930
Relevance Feedback in XML Retrieval
Pan, Hanglin
Lindner, Wolfgang
Mesiti, Marco
Türker, Can
Tzitzikas, Yannis
Vakali, Athena
expertsonly
Highly heterogeneous XML data collections that do not have a global schema, as
arising, for example, in federations of digital libraries or scientific data
repositories, cannot be effectively queried with XQuery or XPath alone, but
rather require a ranked retrieval approach. As known from ample work in the IR
field, relevance feedback provided by the user that drives automatic query
refinement or expansion can often lead to improved search result quality (e.g.,
precision or recall). In this paper we present a framework for feedback-driven
XML query refinement and address several building blocks including reweighting
of query conditions and ontology-based query expansion.We point out the issues
that arise specifically in the XML context and cannot be simply addressed by
straightforward use of traditional IR techniques, and we present our approaches
towards tackling them.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231397
urn:ISBN:3-540-23305-9
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb, Springer, 187-196 (2004)
en
oai:edoc.mpg.de:2313982012-09-1987:930
Query Refinement by Relevance Feedback in an XML Retrieval System (Demo)
Pan, Hanglin
Theobald, Anja
Schenkel, Ralf
Atzeni, Paolo
Chu, Wesley
Lu, Hongjun
Zhou, Shuigeng
Ling, Tok Wang
expertsonly
Springer
2004
Conference-Paper
http://edoc.mpg.de/231398
urn:ISBN:3-540-23723-2
Conceptual modeling, ER 2004 : 23rd International Conference on Conceptual Modeling, Springer, 854-855 (2004)
en
oai:edoc.mpg.de:2313992012-09-1987:930
An Information System for Material Microstructures
Roberts, Kathrin
Mücklich, Frank
Schenkel, Ralf
Weikum, Gerhard
Hatzopoulos, Michael
Manolopoulos, Yannis
expertsonly
This paper presents an information system that supports a materialographic
laboratory in classifying material samples based on microstructure images. The
system uses database and Web technologies to manage its information and make it
accessible to Internet users. Its core is a classifier, based on support vector
machines, that provides an automatic diagnosis of the material class of a given
sample. The classifier uses texture features from an underlying image analysis,
the so-called Haralick parameters, and stereologic features such as fractal
dimension, Euler parameter, etc. In addition to the classifier, the system
provides a sensitivity analysis that allows the user to understand which
features are most influential for certain classification decisions. The system
is fully operational and can be used on the Web.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231399
urn:ISBN:0-7695-2146-0
16th International Conference on Scientific and Statistical Database Management, SSDBM 2004, IEEE, 329-332 (2004)
en
oai:edoc.mpg.de:2314002012-09-1987:930
FliX: A Flexible Framework for Indexing Complex {XML} Document Collections
Schenkel, Ralf
Lindner, Wolfgang
Mesiti, Marco
Türker, Can
Tzitzikas, Yannis
Vakali, Athena
expertsonly
While there are many proposals for path indexes on XML documents, none of them
is perfectly suited for indexing large-scale collections of interlinked XML
documents. Existing strategies lack support for intra- or inter-document links,
require large amounts of time to build or space to store the index, or cannot
efficiently answer connection queries. This paper presents the {\em FliX}
framework for connection indexing that supports large, heterogeneous document
collections with many links, using the existing path indexes as building
blocks. We introduce some example configurations of the framework that are
appropriate for many important application scenarios. Experiments show the
feasibility of our approach.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231400
urn:ISBN:3-540-23305-9
Current trends in database technology, EDBT 2004 Workshops : EDBT 2004 Workshops PhD, DataX, PIM, P2P&DB, and ClustWeb, Springer, 240-249 (2004)
en
oai:edoc.mpg.de:2314022012-09-1987:930
Restrictive Clustering and Metaclustering for self-organizing Document Collections
Siersdorfer, Stefan
Sizov, Sergej
Järvelin, Kalervo
Allan, James
Bruza, Peter
Sanderson, Mark
expertsonly
This paper addresses the problem of automatically structuring
heterogenous document collections by using clustering
methods. In contrast to traditional clustering, we study
restrictive methods and ensemble-based meta methods that
may decide to leave out some documents rather than assigning
them to inappropriate clusters with low confidence.
These techniques result in higher cluster purity, better overall
accuracy, and make unsupervised self-organization more
robust. Our comprehensive experimental studies on three
different real-world data collections demonstrate these benefits.
The proposed methods seem particularly suitable for
automatically substructuring personal email folders or personal Web directories
that are populated by focused crawlers,
and they can be combined with supervised classification
techniques.
ACM
2004
Conference-Paper
http://edoc.mpg.de/231402
Proceedings of SIGIR 2004: the Twenty-Seventh Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 226-233 (2004)
en
oai:edoc.mpg.de:2314032012-09-1987:930
Goal-oriented Methods and Meta Methods for Document Classification and their Parameter Tuning
Sizov, Sergej
Siersdorfer, Stefan
Weikum, Gerhard
Evans, David A.
Gravano, Luis
Herzog, Otthein
Zhai, ChengXiang
Ronthaler, Marc
expertsonly
Automatic text classification methods come with various
calibration parameters such as thresholds for probabilities in
Bayesian classifiers or for hyperplane distances in SVM
classifiers. In a given application context these parameters
should be set so as to meet the relative importance of various
result quality metrics such as precision versus recall. In this
paper we consider classifiers that can accept a document for a
topic, reject it, or abstain. We aim to meet the application's
goals in terms of accuracy (i.e., avoid false acceptances or
rejections) and loss (i.e., limit the fraction of documents for which no
decision is
made).
To this end we investigate restrictive forms
of Support Vector Machine classifiers and we develop meta
methods that split the training data into subsets for
independently trained classifiers and then combine the results of
these classifiers. These techniques tend to improve accuracy at
the expense of document loss. We develop estimators that help to
predict the accuracy and loss for a given setting of the methods'
tuning parameters, and a methodology for efficiently deriving
a setting that meets the application's goals. Our experiments
confirm the practical viability of the approach.
ACM
2004
Conference-Paper
http://edoc.mpg.de/231403
CIKM 2004 : proceedings of the Thirteenth Conference on Information and Knowledge Management, ACM, 59-68 (2004)
en
oai:edoc.mpg.de:2314042012-09-1987:930
BINGO! and {Daffodil:} {Personalized} Exploration of Digital Libraries and {Web} Sources
Theobald, Martin
Klas, Claus-Peter
expertsonly
LE CENTRE DE HAUTES ETUDES INTERNATIONALES (C.I.D.)
2004
Conference-Paper
http://edoc.mpg.de/231404
urn:ISBN:2 905450-09-6
RIAO 2004, LE CENTRE DE HAUTES ETUDES INTERNATIONALES (C.I.D.), 347-365 (2004)
en
oai:edoc.mpg.de:2314052012-09-1987:930
Top-k Query Evaluation with Probabilistic Guarantees
Theobald, Martin
Weikum, Gerhard
Schenkel, Ralf
Nascimento, Mario A.
Özsu, M. Tamer
Kossmann, Donald
Miller, Renée J.
Blakeley, José A.
Schiefer, K. Bernhard
expertsonly
Top-k queries based on ranking elements of multidimensional datasets are a
fundamental building block for many kinds of information discovery. The best
known general-purpose algo-rithm for evaluating top-k queries is Fagin’s
threshold algorithm (TA). Since the user’s goal behind top-k queries is to
identify one or a few relevant and novel data items, it is intriguing to use
approximative variants of TA to reduce run-time costs. This paper introduces a
family of approximative top-k algorithms based on probabilistic arguments. When
scanning index lists of the underlying multidimensional data space in
descending order of local scores, various forms of convolution and derived
bounds are employed to predict when it is safe, with high probability, to drop
candidate items and to prune the index scans. The precision and the efficiency
of the developed methods are experimentally evaluated based on a large Web
corpus and a structured data collection.
Morgan Kaufmann
2004
Conference-Paper
http://edoc.mpg.de/231405
urn:ISBN:0-12-088469-0
Proceedings 2004 VLDB Conference : The 30th International Conference on Very Large Databases (VLDB), Morgan Kaufmann, 648-659 (2004)
en
oai:edoc.mpg.de:2314082012-09-1987:930
Bookmark-driven Query Routing in Peer-to-Peer Web Search
Bender, Matthias
Michel, Sebastian
Zimmer, Christian
Weikum, Gerhard
Callan, Jamie
Fuhr, Norbert
Nejdl, Wolfgang
expertsonly
We consider the problem of collaborative Web search and query routing
strategies in a peer-to-peer (P2P) environment.
In our architecture every peer has a full-fledged search engine with a
(thematically focused) crawler
and a local index whose contents may be tailored to the user's specific
interest profile.
Peers are autonomous and post meta-information about their bookmarks and index
lists to
a global directory, which is efficiently implemented in a decentralized manner
using
Chord-style distributed hash tables. A query posed by one peer is first
evaluated locally;
if the result is unsatisfactory the query is forwarded to selected peers. These
peers are
chosen based on a benefit/cost measure where benefit reflects the thematic
similarity
of peers' interest profiles, derived from bookmarks, and cost captures
estimated peer load
and response time. The meta-information that is needed for making these query
routing
decisions is efficiently looked up in the global directory; it can also be
cached and
proactively disseminated for higher availability and reduced network load.
Universität Duisburg-Essen
2004
Conference-Paper
http://edoc.mpg.de/231408
Proceedings of the SIGIR Workshop on Peer-to-Peer Information Retrieval : 27th Annual International ACM SIGIR Conference ; SIGIR 2004 P2PIR Workshop, Universität Duisburg-Essen, 1-12 (2004)
en
oai:edoc.mpg.de:2314092012-09-1987:930
XXL @ {INEX} 2003
Schenkel, Ralf
Theobald, Anja
Weikum, Gerhard
Fuhr, Norbert
Lalmas, Mounia
Malik, Saadia
expertsonly
Information retrieval on XML combines retrieval on content data (element and
attribute values) with retrieval on structural data (element and attribute
names). Standard query languages for XML such as XPath or XQuery support
Boolean retrieval: a query result is a (possibly restructured) subset of XML
elements or entire documents that satisfy the search conditions of the query.
Such search conditions consist of regular path expressions including wildcards
for paths of arbitrary length and boolean content conditions.
We developed a flexible XML search language called XXL for probabilistic ranked
retrieval on XML data. XXL offers a special operator '$\sim$' for specifying
semantic similarity search conditions on element names as well as element
values. Ontological knowledge and appropriate index structures are necessary
for semantic similarity search on XML data extracted from the Web, intranets or
other document collections. The XXL Search Engine is a Java--based prototype
implementation that support probabilistic ranked retrieval on a large corpus of
XML data.
This paper outlines the architecture of the XXL system and discusses its
performance in the INEX benchmark.
INEX
2004
Conference-Paper
http://edoc.mpg.de/231409
Proceedings of the Second INEX Workshop, INEX, 59-66 (2004)
en
oai:edoc.mpg.de:2314102012-09-1987:930
Neighborhood-conscious Hypertext Categorization
Angelova, Ralitsa
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231410
en
oai:edoc.mpg.de:2314112012-09-1987:930
Entwurf und Implementierung eines Mobile-Access-Servers
Bautz, Tim
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231411
de
oai:edoc.mpg.de:2314122012-09-1987:930
Time-aware and Trend-based Authority Ranking
Berberich, Klaus
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231412
en
oai:edoc.mpg.de:2314132012-09-1987:930
Advanced Divide-and-Conquer Algorithms for Computing Two-Hop Covers for Large Collections of XML Documents
Broschart, Andreas
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231413
en
oai:edoc.mpg.de:2314142012-09-1987:930
Bootstrapping Ontologies from the Web
Cai, Jun
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231414
en
oai:edoc.mpg.de:2314152012-09-1987:930
Generische Anbindung von Datenhaltungssystemen mit Web Services am Beispiel von SAP R/3
Diesinger, Jörg
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231415
de
oai:edoc.mpg.de:2314162012-09-1987:930
User Profile Management in a Web Search Engine
Eske, Vladimir
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231416
en
oai:edoc.mpg.de:2314172012-09-1987:930
Ein automatisches Annotationswerkzeug für HTML- und XML-Daten unter Verwendung von Hidden Markov Models und Named Entity Recognition
Gerstacker, Miriam
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231417
de
oai:edoc.mpg.de:2314182012-09-1987:930
Implementation and Evaluation of a Path Indexing Framework for Large Collections of Interlinked XML Documents
Khalid, Mahboob Alam
expertsonly
Universität des Saarlandes
2004
Thesis
http://edoc.mpg.de/231418
en
oai:edoc.mpg.de:2314192012-09-1987:930
Query-Log-based Authority Analysis for Web Information Search
Luxenburger, Julia
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231419
en
oai:edoc.mpg.de:2314202012-09-1987:930
Intelligente Informationsorganisation und -suche für ein thematisch fokussiertes Web-Informationsportal
Michels, Thomas
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231420
de
oai:edoc.mpg.de:2314222012-09-1987:930
A light-weight Workflow Management System based on Web Services
Vangala, Saipradeep
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231422
en
oai:edoc.mpg.de:2314232012-09-1987:930
Integrating Web Portals into a concept-based search engine using ontologies
Wang, Xueqiang
expertsonly
Universität des Saarlandes
2005
Thesis
http://edoc.mpg.de/231423
en
oai:edoc.mpg.de:2314242012-09-1987:930
Variability of Packet Round-Trip Times and Passive Bottleneck Bandwidth Estimation
Ohlmann, Michael
expertsonly
Universität des Saarlandes
2005
PhD-Thesis
http://edoc.mpg.de/231424
en
oai:edoc.mpg.de:2314252012-09-1987:930
Die XXL-Suchmaschine zur ontologiebasierten Ähnlichkeitssuche in XML-Dokumenten
Theobald, Anja
expertsonly
In dieser Arbeit wird die XXL-Suchmaschine vorgestellt. Sie wertet Anfragen
aus, die in der XML-Anfragesprache XXL formuliert sind. Eine XXL-Anfrage
umfasst dabei Suchbedingungen an die Struktur und an den Inhalt von
XML-Dokumenten.
Universität des Saarlandes
2005
PhD-Thesis
http://edoc.mpg.de/231425
en
oai:edoc.mpg.de:2318002010-12-0387:937
A Mobile System for Multi-Video Recording
Ahrenberg, Lukas
Ihrke, Ivo
Magnor, Marcus
expertsonly
\begin{abstract}
We present a portable system to record synchronised, multi-video data
for vision applications such as 3D
reconstruction and video-based rendering of dynamic scenes.
The aim of the project is
to gain access to a greater number of scenes than what a static, wired
indoor studio allows for. The portable acquisition system is
constructed from a number of independent modules, each consisting of
a FireWire camera and a laptop. Our software utilises wireless
networking making the system behave
like a tightly coupled unit without requiring the modules to be
physically connected to each other. The scheme also includes an
external calibration method suitable for general scenes.
The system is scalable and
allows for easy transportation and ad-hoc setup and configuration. We present
recent result
s acquired in the field and their use for free-viewpoint video.
\end{abstract}
Institution of Electrical Engineers
2004
Conference-Paper
http://edoc.mpg.de/231800
urn:ISBN:0863413919
1st European Conference on Visual Media Production (CVMP), Institution of Electrical Engineers, 127-132 (2004)
en
oai:edoc.mpg.de:2318012010-12-0387:937
Spacetime-coherent Geometry Reconstruction from Multiple Video Streams
Magnor, Marcus
Goldluecke, Bastian
Aloimonos, Y.
expertsonly
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231801
urn:ISBN:0-7695-2223-8
2nd International Symposium on 3D Data Processing, Visualization, and Transmission, 3DPVT 2004, IEEE, 365-372 (2004)
en
oai:edoc.mpg.de:2318022010-12-0387:937
Cloth Motion from Optical Flow
Scholz, Volker
Magnor, Marcus
Girod, B.
Magnor, M.
Seidel, H.-P.
expertsonly
This paper presents an algorithm for capturing the motion of deformable
surfaces, in particular textured cloth. In a calibrated multi-camera setup, the
optical flow between consecutive video frames is determined and 3D scene flow
is computed. We use a deformable surface model with constraints for vertex
distances and curvature to increase the robustness of the optical flow
measurements. Tracking errors in long video sequences are corrected by a
silhouette matching procedure. We present results for synthetic cloth
simulations and discuss how they can be extended to real-world footage.
Akademische Verlagsgesellschaft Aka
2004
Conference-Paper
http://edoc.mpg.de/231802
urn:ISBN:3-89838-058-0
Vision, modeling, and visualization 2004 (VMV-04), Akademische Verlagsgesellschaft Aka, 117-124 (2004)
en
oai:edoc.mpg.de:2318062010-12-0387:937
Constrained Inverse Volume Rendering for Planetary Nebulae
Magnor, Marcus
Kindlmann, Gordon
Hansen, Charles
Duric, Neb
Rushmeier, Holly
Turk, Greg
van Wijk, Jarke J.
expertsonly
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231806
urn:ISBN:0-7803-8788-0
IEEE Visualization 2004 : VIS 2004, IEEE, 83-90 (2004)
en
oai:edoc.mpg.de:2318102010-12-0387:937
External camera calibration for synchronized multi-video systems
Ihrke, Ivo
Ahrenberg, Lukas
Magnor, Marcus
expertsonly
UNION Agency
2004
Conference-Paper
http://edoc.mpg.de/231810
urn:ISSN:1213-6972
WSCG '2004 : the 12th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision 2004 ; short communication papers proceedings, UNION Agency, 537-544 (2004)
en
oai:edoc.mpg.de:2318132012-09-1987:934
A flexible framework for learning-based Surface Reconstruction
Saleem, Waqar
expertsonly
The problem of Surface Reconstruction arises in many real world situations. We
introduce in detail the problem itself and then take a brief look into its
applications and existing techniques, particularly learning based techniques,
developed for its solution. Having presented the context, we closely examine
one such learning based technique – the Neural Mesh algorithm for Surface
Reconstruction.
Despite being relatively recent, the Neural Mesh algorithm has already
undergone several revisions, thus giving rise to several variants of the
original algorithm. We study the algorithm and each of its variants in detail.
All variants rely in varying
degrees on a specific aspect of the algorithm – a signal counter. We observe
that algorithmic reliance on the signal counter impedes performance and propose
an alternate way of performing the same functionalities – using a list.
Additionally, on the practical side, we identify areas where inhouse
implementations of the algorithms were wanting in efficiency and revise those
areas.
Changing over from the signal counter to the list represents a change in
approach from the exact learning of the original algorithms to a comparative
learning framework. We show empirically that this change in approach does not
produce any significant difference in the quality of the algorithms’ output,
while performance, in terms of running time, increases dramatically.
Universität des Saarlandes
2004
Thesis
http://edoc.mpg.de/231813
en
oai:edoc.mpg.de:2318192010-12-0387:937
Image-Based Tomographic Reconstruction of Flames
Ihrke, Ivo
Magnor, Marcus
Boulic, R.
Pai, D.K.
expertsonly
Eurographics Association
2004
Conference-Paper
http://edoc.mpg.de/231819
urn:ISBN:3-905673-14-2
Computer Animation 2004 : ACM SIGGRAPH / Eurographics Symposium on Computer Animation, Eurographics Association, 367-375 (2004)
en
oai:edoc.mpg.de:2318202010-12-0387:937
Weighted Minimal Hypersurfaces and Their Applications in Computer Vision
Goldluecke, Bastian
Magnor, Marcus
Pajdla, Tomás
Matas, Jirí
expertsonly
Many interesting problems in computer vision can be formulated as a
minimization problem for an {\em energy functional}.
If this functional is given as an integral of a scalar-valued weight function
over an unknown hypersurface, then the minimal surface we are looking for can
be determined as a solution of the functional's Euler-Lagrange equation.
This paper deals with a general class of weight functions
that may depend on the surface point and normal.
By making use of a mathematical tool called {\em the method of the moving
frame},
we are able to derive the Euler-Lagrange equation in arbitrary-dimensional
space and without the need for any surface parameterization.
Our work generalizes existing proofs, and we demonstrate that it
yields the correct evolution equations for a variety of previous
computer vision techniques which can be expressed in terms of our
theoretical framework.
In practical applications, the surface evolution which converges to a
solution of the Euler-Lagrange equation can be implemented using level
set techniques.
The well-known transition to a level set evolution equation,
which we briefly review in this paper, works in the general case as well.
That way, problems involving minimal hypersurfaces in dimensions higher than
three,
which were previously impossible to solve in practice, can now be introduced
and handled by generalized versions of existing algorithms.
As one example, we sketch a novel idea how to reconstruct
temporally coherent geometry from multiple video streams.
Springer
2004
Conference-Paper
http://edoc.mpg.de/231820
urn:ISBN:3-540-21983-8
Computer vision, ECCV 2004 : 8th European Conference on Computer Vision - part II, Springer, 366-378 (2004)
en
oai:edoc.mpg.de:2318212010-12-0387:937
Space-Time Isosurface Evolution for Temporally Coherent 3D Reconstruction
Goldluecke, Bastian
Magnor, Marcus
expertsonly
We model the dynamic geometry of a time-varying scene as a 3D isosurface in
space-time.
The intersection of the isosurface with planes of constant time yields the
geometry at a
single time instant.
An optimal fit of our model to multiple video sequences is
defined as the minimum of an energy functional.
This functional is given by an integral over the entire hypersurface,
which is designed to optimize photo-consistency.
A PDE-based evolution derived from the Euler-Lagrange equation
maximizes consistency with all of the given video data simultaneously.
The result is a 3D model of the scene which varies smoothly over time.
The geometry reconstructed by this scheme
is significantly better than results obtained by space-carving approaches
that do not enforce temporal coherence.
IEEE
2004
Conference-Paper
http://edoc.mpg.de/231821
urn:ISBN:0-7695-2158-4
Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2004, IEEE, 350-355 (2004)
en
ResultSet_b6B2QYIH893_range_100-199