January 1998
- Mail from mud Zoran's final Imp Stephen Zepp
- Mail from mud Zoran's final Imp coder@ibm.net
- Mail from mud Zoran's final Imp Shawn Halpenny
- Mail from mud Zoran's final Imp JC Lawrence
- Mail from mud Zoran's final Imp Shawn Halpenny
- Happy new year Marian Griffith
- Totally OT... Marian Griffith
- Totally OT... (Or is it?) s001gmu@nova.wright.edu
- Mud-Dev FAQ Ling
- Mud-Dev FAQ Jon A. Lambert
- Mud-Dev FAQ JC Lawrence
- Mud-Dev FAQ Adam Wiggins
- Who's bugging who? : was- Wild West Jon A. Lambert
- my bio (was Mud-Dev FAQ) Mike Sellers
- request for comments (was: Mud-Dev FAQ) Vadim Tkachenko
- request for comments (was: Mud-Dev FAQ) Jon A. Lambert
- request for comments (was: Mud-Dev FAQ) coder@ibm.net
On 05/01/98 at 08:32 AM, Vadim Tkachenko <vadimt@4cs.com> said: >Jon A.
Lambert wrote:
>>
>> Methods of handling coordinate spaces: neighborhoods, tree forms
>> R-Trees, R*-Trees, 3d arrays, Quad/Oct trees
>What are R-Trees and R*-Trees?
--<cut>--
From http://www.cs.cuhk.hk/~drsam/methods.html:
- --<cut>--
What is R-Tree
A R-Tree, proposed by Antonin Guttman[1], is an index structure for point
and spatial data at the same time. Insert, delete and search can be
intermixed without periodic reorganization. It uses a tuple to represent a
spatial data in the database. In order to retrieve the data, each tuple
has a unique identifier, tuple-identifier. At the leaf node of a R-Tree,
it has index record that can reference the spatial data. The index record
is (I, tuple-identifier). I is an n-dimensional rectangle and it is the
bounding rectangle of the spatial data indexed. This rectangle is also
known as minimal bounding rectangle, MBR. and each entry in
tuple-identifier is the upper and lower bounds, [upper, lower], of the
rectangle along the
dimension. Non-leaf nodes contain entries (I, childnode-pointer) where I
is the minimal rectangle bounding all the rectangles in the lower nodes'
entries. Childnode-pointer is the pointer to a lower node in the R-Tree.
Let M and m<=M/2 be the maximum and minimum number of entries can be
filled into one node respectively.
Properties of R-Tree
A R-Tree satisfies the following properties:
A R-Tree is a height balance tree and all leaves are on the same
level.
Root node has at least two children unless it is the leaf node.
Every non-leaf node contains between m and M entries unless it is
the root.
For each entries (I, childnode-pointer) in a non-leaf node, I is
the smallest rectangle that spatially contains all rectangles in
its child nodes.
Every leaf node contains between m and M index records unless it
is the root.
For each index record (I, tuple-identifier) in a leaf node, I is
the smallest rectangle that spatially contains the n-dimensional
data object represented by the indicated tuple.
R*-Tree
The R-tree is based on a heuristic optimization. The optimization
criterion is to minimize the area of each enclosing rectangle in the inner
nodes. R*-Tree which incorporates a combined optimization of area, margin
and overlap of each bounding rectangle in the inner nodes was proposed in
[6]. For slightly higher implementation cost, it outperforms the existing
R-Tree variants.
Minimizing the area covered by a bounding rectangle should
minimize the dead space. This will improve performance since
decisions which paths have to be traversed, can be taken on higher
level
Minimizing the overlap between bounding rectangles decreases the
number of paths to be traversed.
Minimizing the margin of a bounding rectangle will make the
rectangle more quadratic. It is because for fixed area, the object
with the smallest margin is the square. Quadratic rectangles can
be packed easily and thus building a smaller rectangle.
VP-Tree
Conventional spatial index structures divide the multi-dimensional vector
space into partitions which have approximately the same number of data
points as each other. It facilitates in finding the nearest neighbor of a
given query point because it is only necessary to touch a small number of
partitions. Most partitioning methods are based on absolute coordinate
values of the vector space. R-Tree and R*-Tree described before use this
type of partitioning method. The structures partitioned in this way are
useful for queries based on absolute coordinates, like range queries.
However, in general, it does not maintain any distance information, such
as distance between points within a partition and the partition's
boundaries. Since this information is critical in pruning the search space
for
nearest-neighbor search, index structures using partitioning methods based
on absolute coordinate are thus not so useful for
multi-dimensional nearest-neighbor search.
Nearest-neighbor search by definition is to find out one point with
minimum point-to-point distance from a given query point, so it is natural
to use partitioning method based on relative distance rather than absolute
coordinate values. Vantage-Point tree, or VP-Tree, method was proposed by
Peter N.Yianilos. It uses the partitioning method based on relative
distance and aims for handling multi-dimensional nearest neighbor search.
As mentioned before, VP-Tree method bases the partitioning on the relative
distances among the data points, rather than their absolute coordinate
values. It also bases on a particular vantage
point. Actually, vantage point is nothing special but a point selected
from a vector space, or a set of data points. However, the choice of
vantage point plays an important role in the performance of indexing
algorithm.
- --<cut>--
And for QuadTrees:
- --<cut>--
QUADTREE IMAGES by Bob Glickstein
A ``quadtree'' is a means of encoding an image as a tree structure. Each
node of the tree has up to four children. The root node represents the
entire image; its children represent the four quadrants of the entire
image; their children represent the sixteen subquadrants; the children of
those represent the sixty-four sub-subquadrants, and so on.
A leaf node corresponds to a single pixel, and is marked with the color of
that pixel (in this implementation, black or white only). If a non-leaf
node has two or more children of the same color, then that color is stored
in the parent and the children are deleted. Thus, if an entire quadrant
(subquadrant, sub-subquadrant, etc.) of the image is white, that
information can be stored in a single quadtree node, and all of the
children of that node can be removed.
For certain images, this encoding yields enormous savings in storage size.
Such images are typically line drawings or other bitmaps with several
areas of solid black or white. Images with a lot of dithering or
stippling, such as scanned images, tend to yield little or no savings in
space.
An amusing aspect of quadtrees is that they can be displayed according to
a depth-first or a breadth-first traversal of the tree. In a depth-first
traversal, first the prodemonant color of the entire image is displayed;
then the predominant color of the first quadrant is displayed; then the
predominant color of the first subquadrant of the first quadrant, and so
on. The user can watch the quadrants and subquadrants being drawn. A
breadth-first traversal, however, is much more interesting. Since it
displays first the predominant color of the entire image, followed by the
predominant colors of the four major quadrants, followed by the
predominant colors or the sixteen subquadrants, and so on, the effect is
one of a gradually resolving image with finer and finer detail at each
step.
- --<cut>--
--<cut>--
The recent neighborhoods thread is also probably worth reviewing as
another model. I'd also suggest spending working thru the Stony Brook
site:
http://www.cs.sunysb.edu/~algorith/
It is a gold mine.
--
J C Lawrence Internet: claw@null.net
----------(*) Internet: coder@ibm.net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith... - request for comments (was: Mud-Dev FAQ) JC Lawrence
- request for comments (was: Mud-Dev FAQ) s001gmu@nova.wright.edu
- request for comments (was: Mud-Dev FAQ) JC Lawrence
- request for comments (was: Mud-Dev FAQ) Vadim Tkachenko
- OT: Suomi Finland Ola Fosheim Grøstad
- OT: Suomi Finland ##Make Nylander
- Totally OT... (Or is it?) (yes it is ;) Marian Griffith
- Totally OT... (Or is it?) (yes it is ;) Ola Fosheim Grøstad
- Totally OT... (Or is it?) (yes it is ;) Adam Wiggins
- Totally OT... (Or is it?) (yes it is ;) Ola Fosheim Grøstad
- Totally OT... (Or is it?) (yes it is ;) Jon A. Lambert
- Totally OT... (Or is it?) (yes it is ;) Ola Fosheim Grøstad
- Totally OT... (Or is it?) (yes it is ;) JC Lawrence
- Totally OT... (Or is it?) (yes it is ;) Jon A. Lambert
- Totally OT... (Or is it?) (yes it is ;) Mike Sellers
- Totally OT... (Or is it?) (yes it is ;) JC Lawrence
- Totally OT... (Or is it?) (yes it is ;) JC Lawrence
- Journal of MUD Research, Vol. 3, No. 1 [TEXT] coder@ibm.net
- World Seeding (was Task Parsing) Ling
- World Seeding (was Task Parsing) JC Lawrence
- World Seeding (was Task Parsing) Stephen Zepp
- threaded servers (was request for comments Mike Sellers
- MUD Economy Shawn Halpenny
- MUD Economy Adam Wiggins
- MUD Economy Shawn Halpenny
- MUD Economy Ling
- MUD Economy Brandon J. Rickman
- MUD Economy Marian Griffith
- MUD Economy Shawn Halpenny
- MUD Economy Shawn Halpenny
- MUD Economy JC Lawrence
- MUD Economy Koster, Raph
- MUD Economy Matt Chatterley
- MUD Economy JC Lawrence
- MUD Economy Jon A. Lambert
- OT: Jobs available Koster, Raph
- OT: DCOM and RMI Jon A. Lambert
- OT: DCOM and RMI Vadim Tkachenko
- OT: DCOM and RMI Vadim Tkachenko
- OT: DCOM and RMI Miroslav Silovic
- OT: DCOM and RMI Alex Oren
- OT: DCOM and RMI Chris Gray
- request for comments Miroslav Silovic
- request for comments JC Lawrence
- Event handling (was: request for comments) Vadim Tkachenko
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) Vadim Tkachenko
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) Vadim Tkachenko
- Event handling (was: request for comments) JC Lawrence
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) JC Lawrence
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) JC Lawrence
- Event handling (was: request for comments) Matt Chatterley
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) s001gmu@nova.wright.edu
- Event handling (was: request for comments) JC Lawrence
- Event handling (was: request for comments) Vadim Tkachenko
- request for comments JC Lawrence
- Text vs Video; Movies, Books & muds. Nathan Yospe
- Unique items (was: Graphic MUDS/Ultima Online) Vadim Tkachenko
- Unique items (was: Graphic MUDS/Ultima Online) JC Lawrence
- Unique items (was: Graphic MUDS/Ultima Online) Brandon J. Rickman
- Unique items (was: Graphic MUDS/Ultima Online) Adam Wiggins
- Unique items (was: Graphic MUDS/Ultima Online) Brandon J. Rickman
- Unique items (was: Graphic MUDS/Ultima Online) Marian Griffith
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Unique items (was: Graphic MUDS/Ultima Online) Chris Gray
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Unique items (was: Graphic MUDS/Ultima Online) Adam Wiggins
- Unique items (was: Graphic MUDS/Ultima Online) coder@ibm.net
- Delivery Notification: Delivery has failed PMDF e-Mail Interconnect
- Unique items Richard Woolcock
- Unique items Jon A. Lambert
- Unique items Vadim Tkachenko
- Unique items Jon A. Lambert
- Unique items JC Lawrence
- Delivery Notification: Delivery has failed PMDF e-Mail Interconnect
- Delivery Notification: Delivery has failed PMDF e-Mail Interconnect
- Delivery Notification: Delivery has failed PMDF e-Mail Interconnect
- Two Tiers Ling
- MUD Development Digest Dr. Cat
- FAQ Ling
- Clients Matt Chatterley
- Clients JC Lawrence
- Clients Shawn Halpenny
- Clients Matt Chatterley
- Event handling - some definitions Jon A. Lambert
- Event Handling Jon A. Lambert
- Simulations - was: 'A flamewar startingpoint.' Jon A. Lambert
- Formatting apology Stephen Zepp
- OT: Insane Wordwrapping Caliban Tiresias Darklock
- OT: Insane Wordwrapping Alex Oren
- Summary Marian Griffith
- Clients Andrew Wilson
- Vast areas in muds Ling
- Vast areas in muds John G.
- Vast areas in muds Nathan Yospe
- Vast areas in muds Mike Sellers
- Vast areas in muds John G.
- Vast areas in muds Nathan Yospe
- META: Web futures for the list JC Lawrence
- OT: Socket programming - platform specific Jon A. Lambert
- OT: Socket programming - platform specific Chris Gray
- OT: Socket programming - platform specific Jon A. Lambert
- OT: Socket programming - platform specific Caliban Tiresias Darklock
- OT: Socket programming - platform specific Chris Gray
- Graphical mud perspectives Richard Woolcock
- Graphical mud perspectives Nathan Yospe
- Graphical mud perspectives Richard Woolcock
- Graphical mud perspectives Koster, Raph
- Graphical mud perspectives Mike Sellers
- Graphical mud perspectives Koster, Raph
- CORBA, RMI, threads Marc Eyrignoux
- CORBA, RMI, threads Nathan Yospe
- CORBA, RMI, threads Marc Eyrignoux
- CORBA, RMI, threads s001gmu@nova.wright.edu
- CORBA, RMI, threads Brandon Gillespie
- CORBA, RMI, threads Chris Gray
- CORBA, RMI, threads Marc Eyrignoux
- CORBA, RMI, threads Brandon Gillespie
- CORBA, RMI, threads s001gmu@nova.wright.edu
- CORBA, RMI, threads coder@ibm.net
- CORBA, RMI, threads s001gmu@nova.wright.edu
- CORBA, RMI, threads Vadim Tkachenko
- CORBA, RMI, threads Caliban Tiresias Darklock
- CORBA, RMI, threads coder@ibm.net
- Clients based on Netscape 5? Greg Munt
- Clients based on Netscape 5? Chris Gray
- Clients based on Netscape 5? Caliban Tiresias Darklock
- Clients based on Netscape 5? Vadim Tkachenko
- Clients based on Netscape 5? Caliban Tiresias Darklock
- Clients based on Netscape 5? Chris Gray
- Clients based on Netscape 5? Vadim Tkachenko
- Clients based on Netscape 5? Chris Gray
- Clients based on Netscape 5? Vadim Tkachenko
- Clients based on Netscape 5? Chris Gray
- Clients based on Netscape 5? Marian Griffith
- Clients based on Netscape 5? coder@ibm.net
- OT? The impact of the web on muds Mike Sellers
- The Anti-Mac Interface JC Lawrence
- 3D graphics (Was: The impact of the web on muds) Jon Leonard
- 3D graphics (Was: The impact of the web on muds) Caliban Tiresias Darklock
- 3D graphics (Was: The impact of the web on muds) coder@ibm.net
- 3D graphics (Was: The impact of the web on muds) Mike Sellers
- 3D graphics (Was: The impact of the web on muds) Chris Gray
- 3D graphics (Was: The impact of the web on muds) Caliban Tiresias Darklock
- 3D graphics (Was: The impact of the web on muds) coder@ibm.net
- 3D graphics (Was: The impact of the web on muds) coder@ibm.net
- VRML Becomes ISO/IEC International Standard (fwd) Nathan Yospe
- Arctic's Project? Brandon Cline
- Arctic's Project? Adam Wiggins
- Arctic's Project? Brandon Cline
- Arctic's Project? Chris Gray
- FAQ Marc Eyrignoux
- Java and Javascript Greg Munt
- Java and Javascript Chris Gray
- Java and Javascript Matt Chatterley
- Java and Javascript coder@ibm.net
- Java and Javascript Matt Chatterley
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Matt Chatterley
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Chris Gray
- Java and Javascript Jon Leonard
- Java and Javascript Matt Chatterley
- Java and Javascript Jon A. Lambert
- Java and Javascript Ben Greear
- Java and Javascript Jon A. Lambert
- Java and Javascript Ben Greear
- Java and Javascript Jon A. Lambert
- Java and Javascript Ben Greear
- Java and Javascript Jon A. Lambert
- Java and Javascript Mike Sellers
- Java and Javascript J C Lawrence
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Jon A. Lambert
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Jon A. Lambert
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Jon A. Lambert
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Travis Casey
- Java and Javascript Jon A. Lambert
- Java and Javascript Sauron
- Java and Javascript Jon A. Lambert
- Java and Javascript Caliban Tiresias Darklock
- Java and Javascript Alex Oren
- Java and Javascript Chris Gray
- Java and Javascript coder@ibm.net
- Java and Javascript Matt Chatterley
- Java and Javascript coder@ibm.net
- MetaVoice, MetaFont Ling
- MetaVoice, MetaFont Richard Woolcock
- MetaVoice, MetaFont Vadim Tkachenko
- MetaVoice, MetaFont JC Lawrence
- MetaVoice, MetaFont Chris Gray
- The MLI Project Vadim Tkachenko
- The MLI Project Marc Eyrignoux
- The MLI Project Vadim Tkachenko
- The MLI Project coder@ibm.net
- The MLI Project Ling
- The MLI Project coder@ibm.net
- The MLI Project Caliban Tiresias Darklock
- The MLI Project Travis Casey
- The MLI Project Travis Casey
- The MLI Project coder@ibm.net
- The MLI Project s001gmu@nova.wright.edu
- The MLI Project Vadim Tkachenko
- The MLI Project Travis Casey
- The MLI Project Stephen Zepp
- The MLI Project coder@ibm.net
- The MLI Project Travis Casey
- The MLI Project Chris Gray
- The MLI Project Ling
- The MLI Project Andrew C.M. McClintock
- The MLI Project Ling
- The MLI Project Chris Gray
- The MLI Project Caliban Tiresias Darklock
- The MLI Project Chris Gray
- The MLI Project Caliban Tiresias Darklock
- The MLI Project Niklas Elmqvist
- The MLI Project Caliban Tiresias Darklock
- The MLI Project Chris Gray
- The MLI Project Ling
- The MLI Project Caliban Tiresias Darklock
- The MLI Project J C Lawrence
- The MLI Project Chris Gray
- The MLI Project Koster, Raph
- The MLI Project J C Lawrence
- The MLI Project Vadim Tkachenko
- Races and stuff (was: FAQ) Vadim Tkachenko
- Races and stuff (was: FAQ) Marc Eyrignoux
- Races and stuff (was: FAQ) Vadim Tkachenko
- OT: I'm moving again! JC Lawrence
- MUD Development Digest Dr. Cat
- Administrative Responsibilities Greg Munt
- Administrative Responsibilities Jon A. Lambert
- Administrative Responsibilities Greg Munt
- Administrative Responsibilities Jon A. Lambert
- Administrative Responsibilities Mike Sellers
- Administrative Responsibilities Chris Gray
- Administrative Responsibilities Greg Munt
- Administrative Responsibilities coder@ibm.net
- Administrative Responsibilities Jon A. Lambert
- Administrative Responsibilities Greg Munt
- Administrative Responsibilities Jon A. Lambert
- Administrative Responsibilities coder@ibm.net
- Administrative Responsibilities Chris Gray
- Administrative Responsibilities Mike Sellers
- Administrative Responsibilities Mike Sellers
- Administrative Responsibilities Adam Wiggins
- Administrative Responsibilities Greg Munt