Hello All:
You will be proud to know that MSR has exceeded any previous year in Tech Reports publishing! There are 100 Tech Report numbers issued for 1999, with 74 currently published on our external web at: http://research.M?crosöft.com/scripts/pubdb/trpub.asp
Previous years:
66 published in 1998
28 published in1997
18 published in 1996
36 published in1995
21 published in 1994
19 published in1993
Let's continue the push towards more TR publishing. It is great for M?crosöft, MSR, and the entire industry.
Due to the worm virus in the middle of this year, we had some issues and losses with the TR database, but thanks to Jonathan Simon, we were able to pull everything together. Thanks!
I delayed sending out monthly reports due to the database maintenance, so here are the published reports from August 1999 to December 1999.
Please feel free to ask me any questions or make any suggestions to make Year 2000 even more successful.
Regards,
-kendra smith
Research Analyst, MSR
MS Information Services
DECEMBER
MSR-TR-99-100
Rules of Thumb in Data Engineering
Gray, Jim ; Shenoy, Preshant
December 1999
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=311
This paper reexamines the rules of thumb for the design of data storage systems. Briefly, it looks at storage, processing, and networking costs, ratios, and trends with a particular focus on performance and price/performance. Amdahl’s ratio laws for system design need only slight revision after 35 years-the major change being the increased use of RAM. An analysis also indicates storage should be used to cache both database and web data to save disk bandwidth, network bandwidth, and people’s time. Surprisingly, the 5-minute rule for disk caching becomes a cache-everything rule for web caching.
MSR-TR-99-96
Setting 2 Variables at a Time Yields a New Lower Bound for
Random 3-SAT
Achlioptas, Dimitris
December 1999
18 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=309
You can view abstract at link above.
MSR-TR-99-95
Abstract state machines and computationally complete query
languages
Blass, Andrea ; Gurevich, Yuri ; Van den Bussche, Jan
December 1999
26 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=307
Abstract state machines (ASMs) form a relatively new computation model holding the promise that they can simulate any computational system in lockstep. In particular, an instance of the ASM model has recently been introduced for computing queries to relational databases. This model, to which we refer as the BGS model, provides a powerful query language in which all computable queries can be expressed. In this paper, we show that when one is only interested in polynomial-time computations, BGS is strictly more powerful than both QL and whilenew, two well-known computationally complete query languages. We then show that when a language such as whilenew is extended with a duplicate elimination mechanism, polynomial-time simulations between the language and BGS become possible.
MSR-TR-99-94
Processor Performance of Selection Queries
Ailamaki, Anastassia ; Slutz, Donald
December 1999
20 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=308
We conducted an in-depth analysis of the processor and memory behavior of three commercial database management systems, running simple selection queries. The goal was to find and understand bottlenecks across. In addition, we evaluated vertical partitioning as a technique to reduce data-related memory stall time.
MSR-TR-99-93
Economical Covers with Geometric Applications
Alon, Noga ; Bollobas, Bela ; Kim, Jeong Han ; Vu, Van Ha
December 1999
27 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=314
You can view abstract at link above.
MSR-TR-99-92
Approximating the Independence Number and the Chromatic
Number in Expected Polynomial Time (Extended Abstract)
Krivelevich, Michael ; Vu, Van H.
December 1999
12 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=313
You can view abstract at link above.
MSR-TR-99-91
On the Concentration of Multi-Variate Polynomials with
Small Expectation
Vu, Van H.
December 1999
20 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=315
Let t1,...,tn be independent, but not necessarily identical, {0,1} random variables. We prove a general large deviation bound for multi-variate polynomials (in t1,...,tn) with small expectation (order O(polylog(n))).
MSR-TR-99-90
A Large Deviation Result on the Number of Small Subgraphs
of a Random Graph
Vu, Van H.
December 1999
22 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=316
You can view abstract at link above.
MSR-TR-99-89
Krivelevich, Michael ; Vu, Van H.
December 1999
14 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=312
You can view abstract at link above.
MSR-TR-99-88
Gurevich, Yuri ; Rosenzweig, Dean
December 1999
18 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=306
We look at some sources of insecurity and difficulty in reasoning about partially ordered runs of distributed ASMs, and propose some techniques to facilitate such reasoning. As a case study, we prove in detail correctness and deadlock-freedom for general partially ordered runs of distributed ASM models of Lamport's Bakery Algorithm.
MSR-TR-99-85
Scalability Terminology: Farms, Clones, Partitions, and
Packs: RACS and RAPS
Devlin, Bill ; Gray, Jim ; Laing, Bill ; Spix, George
December 1999
6 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=310
No abstract available.
MSR-TR-99-61
Fair Scheduling in Broadcast Environments
Vaidya, Nitin H. ; Bahl, Paramvir
August 1999 (Revised December 1999)
30 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=317
This report considers the problems of scheduling transmissions in broadcast environments, including, wireless environments. Issues that affect the design of fair scheduling algorithms, and several alternative approaches to implementing fair scheduling in single-hop and multi-hop environments are identified.
NOVEMBER
MSR-TR-99-87
Estimating the Support of a High-Dimensional Distribution
Schölkopf, Bernhard ; Platt, John C. ; Shawe-Taylor, John ; Smola, Alex J. ;
Williamson, Robert C.
November 1999
27 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=304
Suppose you are given some dataset drawn from an underlying probability distribution P and you want to estimate a "simple" subset S of input space such that the probability that a test point drawn from P lies outside of S is bounded by some a priori specified v between 0 and 1.
We propose a method to approach this problem by trying to estimate a function f which is positive on S and negative on the complement. The functional form of f is given by a kernel expansion in terms of a potentially small subset of the training data; it is regularized by controlling the length of the weight vector in an associated feature space. The expansion coefficients are found by solving a quadratic programming problem, which we do by carrying out sequential optimization over pairs of input patterns. We also provide a preliminary theoretical analysis of the statistical performance of our algorithm.
The algorithm is a natural extension of the support vector algorithm to the case of unlabelled data.
MSR-TR-99-86
FEC and Pseudo-ARQ for Receiver-driven Layered Multicast
of Audio and Video
Chou, Philip A. ; Mohr, Alexander E. ; Wang, Albert ; Mehrotra, Sanjeev
November 1999
24 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=320
We consider the problem of joint source/channel coding of real-time sources, such as audio and video, for the purpose of multicasting over the Internet. The sender injects into the network multiple source layers and multiple channel (parity) layers, some of which are delayed relative to the source. Each receiver subscribes to the number of source layers and the number of channel layers that optimizes the source-channel rate allocation for that receiver's available bandwidth and packet loss probability. We augment this layered FEC system with layered ARQ. Although feedback is normally problematic in broadcast situations, ARQ is simulated by having the receivers subscribe and unsubscribe to the delayed channel coding layers to receive missing information. This pseudo-ARQ scheme avoids an implosion of repeat requests at the sender, adn is scalable to an unlimited number of receivers. We show gains of up to 18 dB on channels with 20% loss over systems without error control, and additional gains of up to 13 dB when FEC is augmented by psuedo-ARQ in a hybrid system. The hybrid system is controlled by an optimal policy for a Markov decision process.
MSR-TR-99-83
BMAT - A Binary Matching Tool
Wung, Zheng ; Pierce, Ken ; McFurling, Scott
November 1999
10 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=319
A major challenge of applying profile-based optimization on large real-world applications is how to capture adequate profile information. A large program, with millions of lines of code, may be used in a large variety of ways by different users on different machines. In addition, GUI-based applications can behave differently wiht only the slightest changes of running conditions. To fully characterize this type of program behavior, extensive collection of profile data is required. Unfortunately, in a realistic software production environment, little time is available for extensive profiling. In a large project, many developers and testers need fast access to the latest build without having to wait for extensive profile runs to be completed. To address this dilemma, we would like to be able to reuse profile information from a prior build. In this paper we present BMAT, a tool that matches two versions of a binary program with high success rate. BMAT allows us to propagate profile information from an older, extensively profiled build to a newer build, thus greatly reducing or even eliminating the need for re-profiling. To evaluate the quality of results, we propose two evaluation metrics: the ability of the propagated profile information to perform static branch prediction, and the extent to which propagated code coverage information matches coverage data from the current build. These two metrics show how well the matching algorithm works for the frequently executed core code and across the whole program, respectively. Experiments on a set of large DLLs from M?crosöft Windows 2000 and Internet Explorer show that propagated information using BMAT is typically over 99% and 98% as good on these metrics as fresh profile information. The running time of BMAT is small, under four minutes for a 5.5MB sized program on a Pentium II 200MHz machine.
MSR-TR-99-79
Type Elaboration and Subtype Completion for Java Bytecode
Knoblock, Todd B. ; Rehof, Jakob
November 1999
20 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=305
Java source code is strongly typed, but the translation from Java source to bytecode omits much of the type of information originally contained within methods. Type elaboration is a technique for reconstructing strongly typed programs from incompletely typed bytecode by inferring types for local variables.
There are situations where, technically, there are not enough types in the original type hierarchy to type a bytecode program. Subtype completion is a technique for adding necessary types to an arbitrary type hierarchy to make type elaboration possible for all verifiable Java bytecode.
Type elaboration with subtype completion has been implemented as part of the Marmot Java compiler.
MSR-TR-99-82
Efficient Image Manipulation via Run-time Compilation
Elliott, Conal ; de Moor, Oege ; Finne, Sigbjorn
November 1999
17 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=318
An image manipulation system can be thought of as a domain-specific programming language: by composing and manipulating pictures, the user builds up an expression in such a programming language. Each time the picture is displayed, the expression is evaluated. To gain the required efficiency of display, the expression must be optimized and compiled on the fly. This paper introduces a small language that could form the basis of an image manipulation system, and it describes a preliminary implementation. To compile an expression in the language, we inline all function definitions and use algebraic laws of the primitive operations to optimize composites. We apply a form of code motion to recover (as far as possible) the sharing lost in the inlining phase. Finally, we generate intermediate code that is passed to a JIT compiler.
MSR-TR-99-50
What Next? A Dozen Information-Technology Research Goals
Gray, Jim
June 1999
24 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=321
Charles Babbage's vision of computing has largely been realized. We are on the verge of realizing Vannevar Bush's Memex. But, we are some distance from passing the Turing test. These three visions and their associated problems have provided long-range research goals for many of us. For example, the scalability problem has motivated me for several decades. This talk defines a set of fundamental research problems that broaden the Babbage, Bush, and Turing visions. They extend Babbage's computational goal to include highly-secure, highly-available, self-programming, self-managing, and self-replicating systems. They extend Bush's Memex vision to include a system that automatically organizes, indexes, digests, evaluates, and summarizes information (as well as a human might). Another group of problems extends Turing's vision of intelligent machines to include prosthetic vision, speech, hearing, and other senses. Each problem is simply stated and each is orthogonal from the others, though they share some common core technologies.
OCTOBER
MSR-TR-99-81
Torpid Mixing of the Wang-Swendsen-Kotecky Algorithm
Luczak, Thomas ; Vigoda, Eric
October 1999
7 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=302
You can view abstract at link above.
MSR-TR-99-80
A Warp-Based Feature Tracker
Kang, Thomas ; Gemmell, Jim ; Toyama, Kentaro
October 1999
11 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=303
We present the warp tracker, a new system for tracking features through a sequence of images. Employing an automated multi-resolution lattice deformation technique, the warp tracker performs fairly well on its own, and its hierarchical nature naturally lends itself to being integrated with other tracking algorithms for increased accuracy and robustness. Developed specifically for use in next-generation video teleconferencing systems, a prototype of the warp tracker has already been tested on tracking human eyes with encouraging results.
MSR-TR-99-77
On the Theory of Quantum Secret Sharing
Gottesman, Daniel
October 1999
5 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=300
I present a variety of results on the theory of quantum secret sharing. I show that any mixed state quantum secret sharing scheme can be derived by discarding a share from a pure state scheme, and that the size of each share in a quantum secret sharing scheme must be at least as large as the size of the secret. I show that the only constraints on the existence of quantum secret sharing schemes with general access structures are monotonicity (if a set is authorized, so are larger sets) and the no-cloning theorem. I also discuss some aspects of sharing classical secrets using quantum states. In this situation, the size of each share can sometimes be half the size of the classical secret.
MSR-TR-99-64
A New Implementation of the Icon Language
Proebsting, Todd A. ; Townsend, Gregg M.
October 1999
40 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=295
We describe Jcon, a new, Java-based implementation of the Icon programming language. The implementation includes a compiler and runtime system. The runtime system is novel in its concise and efficient object-oriented implementation of a dynamically typed language, as well as its simple mechanism for realizing Icon generators.
MSR-TR-99-60
MLESAC: A New Robust Estimator with Application to
Estimating Image Geometry
Torr, P.H.S. ; Zisserman, A.
October 1999
5 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=301
A new method is presented for robustly estimating multiple view relations from point correspondences. The method comprises two parts, the first is a new robust estimator MLESAC which is a generalization of the RANSAC estimator. It adopts the same sampling strategy as RANSAC to generate putative solutions, but chooses the solution to maximize the likelihood rather than just the number of inliers. The second part to the algorithm is a general purpose method for automatically parametrizing these relations, using the output of MLESAC. A difficulty with multi view image relations is that there are often non-linear constraints between the parameters, making optimization a difficult task. The parametrization method overcomes the difficulty of non-linear constraints and conducts a constrained optimization. The method is general and its use is illustrated for the estimation of fundamental matrices, image-image homographies and quadratic transformations. Results are given for both synthetic and real images. It is demonstrated that the method gives results equal or superior to previous approaches.
MSR-TR-99-44
How to Couple from the Past Using a Read-Once Source of
Randomness
Wilson, David Bruce
October 1999
28 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=296
We give a new method for generating perfectly random samples from the stationary distribution of a Markov chain. The method is related to coupling from the past (CFTP), but only runs the Markov chain forwards in time, and never restarts it at previous times in the past. The method is also related to an idea known as PASTA (Poisson arrivals see time averages) in the operations research literature. Because the new algorithm can be run using a read-once stream of randomness, we call it read-once CFTP. The memory and time requirements of read-once CFTP are on par with the requirements of the usual form of CFTP, and for a variety of applications the requirements may be noticeably less. Some perfect sampling algorithms for point processes are based on an extension of CFTP known as coupling into and from the past; for completeness, we give a read-once version of coupling into and from the past, but it remains unpractical. For these point process applications, we give an alternative coupling method with which read-once CFTP may be efficiently used.
SEPTEMBER
MSR-TR-99-75
The Effect of Communication Modality on Cooperation in
Online Environments
Jensen, Carlos ; Farnham, Shelly D. ; Drucker, Steven M. ; Kollock, Peter
September 1999
8 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=288
One of the most robust findings in the sociological literature is the positive effect of communication on cooperation and trust. When individuals are able to communicate, cooperation increases significantly. How does the choice of communication modality influence this effect? We adapt the social dilemma research paradigm to quantitatively analyze different modes of communication. Using this method, we compare four forms of communication: no communication, text-chat, text-to-speech, and voice. We found statistically significant differences between the various forms of communication, with the voice condition resulting in the highest levels of cooperation. Our results highlight the importance of striving towards the use of more advanced forms of communication in online environments, especially where trust and cooperation are essential. In addition, our research demonstrates the applicability of the social dilemma paradigm in testing the extent to which communication modalities promote the development of trust and cooperation.
MSR-TR-99-72
Primary Tasks and Peripheral Awareness: A Field Study of
Multiple Monitor Use
Grudin, Jonathan
September 1999
6 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=289
This paper describes a field study of people who use multiple monitors for a variety of tasks. The size of a standard computer display has increased slowly, but the amount of information that we can access has increased dramatically. Two monitors on a single computer is a relatively inexpensive improvement that is available today: operating systems now support the dragging of windows and objects across multiple monitors. Interviewing and observing people who use a variety of configurations for a range of tasks, I conclude that people do not use a second monitor as extra workspace. They use it in different ways, generally for “peripheral awareness” of information that is not their main focus of activity. Secondary monitors often display the status of background tasks, events in the world, and communications from coworkers, family, and friends. The conditions are right for rapid growth in multiple monitor use, providing an opportunity for application developers.
MSR-TR-99-71
Presenting to Local and Remote Audiences: Design and Use
of the TELEP System
Jancke, Gavin ; Grudin, Jonathan ; Gupta, Anoop
September 1999
8 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=290
The current generation of desktop computers and networks are bringing streaming audio and video into widespread use. A small investment allows presentations or lectures to be multicast, enabling passive viewing from offices or rooms. We surveyed experienced viewers of multicast presentations and designed a lightweight system that creates greater awareness in the presentation room of remote viewers and allows remote viewers to interact with the speaker. We report on the design, use, and modification of the system, and discuss design tradeoffs.
MSR-TR-99-69
Designing Presentations for On-Demand Viewing
He, Liwei ; Grudin, Jonathan ; Gupta, Anoop
September 1999
8 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=291
Streaming digital video is becoming increasingly widespread. How should video presentations be designed for web access? How is video accessed and used online? We examined detailed behavior patterns of more than 9000 users of a large corpus of professionally prepared presentations. We find that as many people are accessing the talks on demand as attend live, but online access patterns differ markedly from live attendance. People watch less overall and they utilize the ability to skip to different parts of a talk. In designing presentations that will be viewed later on demand, speakers should emphasize key points early in the talk and early within each slide, use slide titles that are meaningful outside the flow of the talk, and reveal as much structure as possible in the slide titles. The results also provide guidance for those developing tools for on-demand multimedia authoring and use.
MSR-TR-99-68
Comparing Presentation Summaries: Slides vs. Reading vs.
Listening
He, Liwei ; Sanocki, Elizabeth ; Gupta, Anoop ; Grudin, Jonathan
September 1999
9 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=292
As more audio and video technical presentations go online, it becomes imperative to give users effective summarizing and skimming tools so that they can find the presentation they want and browse through it quickly. In a previous study we reported various automated methods for summarizing audio-video of presentations, and user response. An open question remained about how well various text/image only techniques will compare to the audio-video summarizations. This study attempts to fill that gap.
This paper reports a user study that compares four possible ways of allowing a user to skim a presentation: 1) PowerPoint slides used by the speaker during the presentation, 2) the text transcript created by professional transcribers from the presentation, 3) the transcript with important points highlighted by the speaker, and 4) a audio-video summary created by the speaker. Results show that although some text-only conditions can match the audio-video summary, users have a preference for audio-video. Furthermore, different styles of slide-authoring (e.g., detailed vs. big-points only) can have a big impact on their effectiveness as summaries, raising a dilemma for some speakers in authoring for on-demand previewing versus that for live audiences.
MSR-TR-99-67
Browsing Digital Video
Li, Francis ; Sanocki, Elizabeth ; Gupta, Anoop ; He, Liwei ; Rui, Yong
September 1999
9 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=294
Video in digital format coupled with digital/programmable playback devices presents opportunities for significantly enhancing the user’s viewing experience. For example, time compression can shorten the viewing length of a video and shot boundary frames can provide a visual index into the content. Such features have primarily been evaluated in isolation with a narrow set of video content types. We investigated as well as implemented the design of a software video browsing application that combines many such features. In addition, we evaluated its use in watching six different video content types and present the resulting data for analysis and discussion. The participants in the evaluation found the browser to be useful and effective for watching the different types of video in a limited amount of time. Also, the results show that both the experience of using the browser and value of each feature varies depending on the content type.
MSR-TR-99-66
A Framework for Asynchronous Collaboration Around
Multimedia and its Application to On-Demand Training
Bargeron, David M. ; Gupta, Anoop ; Grudin, Jonathan ; Sanocki, Elizabeth ; Li,
Francis
September 1999
8 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=293
Delivering educational content on-demand is increasingly important for universities and corporations, and support for asynchronous collaboration is a key requirement. A multimedia annotation system tightly integrated with email provides a powerful platform to build such functionality. Building on top of our early work on multimedia annotations [2], we present new user-interface and system extensions to support asynchronous collaboration for on-demand training. We report results from a real-world case study on the effectiveness of our system, including student experience, instructor experience, and appropriateness of user interface. Overall, the student experience was very positive: students were delighted to have the flexibility of on-demand delivery, while at the same time they benefited from the collaborative features provided by our interface.
MSR-TR-99-65
For Every Sequential Algorithm There Is an Equivalent
Sequential Abstract Machine
Gurevich, Yuri
September 1999
24 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=287
We formalize the notion of sequential algorithms and prove the theorem in the title.
MSR-TR-99-41
The Scaling Window of the 2-SAT Transition
Bollobas, Bela ; Borgs, Christian ; Chayes, Jennifer T. ; Kim, Jeong Han ;
Wilson, David B.
September 1999
51 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=298
You can view abstract at link above.
AUGUST
MSR-TR-99-63
On Deforming Confoliations
Altschuler, Steven J. ; Wu, Lani F.
August 1999
17 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=284
We introduce a parabolic deformation of one-forms on compact, orientable, odd-dimensional manifolds. Under appropriate initial conditions, the flow produces contact forms. We give applications of these techniques including new results demonstrating the existence of contact forms on products of certain contact manifolds with arbitrary surfaces. In particular, we product contact forms on the product of any three dimensional manifold with any surface.
MSR-TR-99-62
Anisotropic Self-Avoiding Walks
Borgs, C. ; Chayes, J.T. ; King, C. ; Madras, N.
August 1999
22 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=299
We consider a model of self-avoiding walks on the lattice Zd with different weights for steps in each of the 2d lattice directions. We find that the direction-dependent mass for the two-point function of this model has three phases: mass positive in all directions; mass identically - ∞; and masses of different signs in different directions. The final possibility can only occur if the weights are asymmetric, i.e. in at least one coordinate the weight in the positive direction differs from the weight in the negative direction. The boundaries of these phases are determined exactly. We also prove that if the weights are asymmetric then a typical N-step self-avoiding walk has order N distance between its endpoints.
MSR-TR-99-42
Gibbs States of Graphical Representations in the Potts
Model with External Fields
Biskup, M. ; Borgs, C. ; Chayes, J.T. ; Kotecky, R.
August 1999
43 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=297
We consider the ferromagnetic q-state Potts model, with each of the q spin values coupled to an external field. We also introduce a generalized random cluster model, which includes both the Potts model in arbitrary homogeneous external fields and the non-integer q random cluster model as special cases. We establish the FKG property, the finite energy condition, uniqueness of the infinite cluster, and the Gibbsianness of limit states for this generalized model. Furthermore, we develop the theory of Gibbs states for the Edwards-Sokal representation of the Potts model in a field, and relate the phase structure in this representation to those in the spin and random cluster representations. Finally, we characterize the possible color(s) of the infinite cluster(s) and show that the correspondence between Edwards-Sokal Gibbs states and their random cluster marginals is bijective, once the color of the infinite cluster is fixed.
MSR-TR-99-29
M?crosöft TerraServer: A Spatial Data Warehouse
Barclay, Tom ; Gray, Jim ; Slutz, Don
June 1999
16 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=280
M?crosöft® TerraServer stores aerial, satellite, and topographic images of the earth in a SQL database available via the Internet. It is the world’s largest online atlas, combining five terabytes of image data from the United States Geological Survey (USGS) and SPIN-2. Internet browsers provide intuitive spatial and text interfaces to the data. Users need no special hardware, software, or knowledge to locate and browse imagery. This paper describes how terabytes of “Internet unfriendly” geo-spatial images were scrubbed and edited into hundreds of millions of “Internet friendly” image tiles and loaded into a SQL data warehouse. M?crosöft TerraServer demonstrates that general-purpose relational database technology can manage large scale image repositories, and shows that web browsers can be a good geospatial image presentation system.
MSR-TR-99-21
Computing Rectifying Homographies for Stereo Vision
Loops, Charles ; Zhang, Zhengyou
August 1999
12 p.
Download: http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=282
Image rectification is the process of applying a pair of 2 dimensional projective transforms, or homographies, to a pair of images whose epipolar geometry is known so that epipolar lines in the original images map to horizontally aligned lines in the transformed images. We propose a novel technique for image rectification based on geometrically well defined criteria such that image distortion due to rectification is minimized. This is achieved by decomposing each homography into a specialized projective transform, a similarity transform, followed by a shearing transform. The effect of image distortion at each stage is carefully considered.
MSR-TR-99-13
Compressed Data Cubes for OLAP Aggregate Query Approximation on Continuous
Dimensions
Shanmugasundaram, Jayavel ; Fayyad, Usama M. ; Bradley, Paul S.
June 1999
10 p.
Download:
http://research.M?crosöft.com/scripts/pubdb/pubsasp.asp?RecordID=283
Efficiently answering decision support queries is an important problem. Most of the work done in this direction has been in the context of the data cube. Queries are efficiently answered by pre-computing large parts of the cube. Besides having large space requirements, such pre-computation requires that hierarchy along each dimension be fixed (hence dimensions are categorical or pre-discretized). Queries that take advantage of pre-computation can thus only drill-down or roll-up along this fixed hierarchy. Another disadvantage of existing pre-computation techniques is that the target measure, along with the aggregation function of interest, is fixed for each cube. Queries over more than one target measure or using different aggregate functions, along with the aggregation function of interest, is fixed for each cube. Queries over more than one target measure or using different aggregation functions, would require pre-computing larger data cubes. In this paper, we propose a new compressed representation of the data cube that (a) drastically reduces storage requirements, (b) does not require the discretization hierarchy along each query dimension to be fixed beforehand and (c) treats each dimension as a potential target measure and supports multiple aggregation functions without additional storage costs. The tradeoff is approximate, yet relatively accurate, answers to queries. We outline mechanisms to reduce the error in the approximation. Our performance evaluation indicates that our compression technique effectively addresses the limitations of existing approaches.