<!-- MHonArc v2.4.4 -->
<!--X-Subject: Re: [MUD-Dev] Room-based vs. coordinate-based -->
<!--X-From-R13: pbqreNvoz.arg -->
<!--X-Date: from major.globecomm.net [207.51.48.5] by in10.ibm.net id 866176669.52474-1 Fri Jun 13 04:37:49 1997 CUT -->
<!--X-Message-Id: 199706130437.EAA28162#out1,ibm.net -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 3.0.2.32.19970612125348.00a28374#mail,tenetwork.com -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, Re: [MUD-Dev] Room-based vs. coordinate-based</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:coder#ibm,net">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg01315.html">Previous</a>
| <a href="msg01317.html">Next</a>
]
Thread:
[ <a href="msg01312.html">Previous</a>
| <a href="msg01320.html">Next</a>
]
Index:
[ <A HREF="author.html#01316">Author</A>
| <A HREF="#01316">Date</A>
| <A HREF="thread.html#01316">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>Re: [MUD-Dev] Room-based vs. coordinate-based</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#null,net">mud-dev#null,net</A></LI>
<LI><em>Subject</em>: Re: [MUD-Dev] Room-based vs. coordinate-based</LI>
<LI><em>From</em>: <A HREF="mailto:coder#ibm,net">coder#ibm,net</A></LI>
<LI><em>Date</em>: Thu, 12 Jun 97 21:35:45 -0700</LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
On 12/06/97 at 07:55 PM, Jeff Kesselman <jeffk#tenetwork,com> said:
>At 09:24 AM 6/12/97 PST8PDT, you wrote:
Attributions!
>>I'm working on R-tree based rooms (but I suspect I'll have to move my
>>current R-tree implementation into the driver, since it's both complex
>>and critical).
>Interesting. Care to define an R-Tree, miro? The data structure for
>some reason is pulling up a blank for me.
I posted the following here a whiles back:
- --<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>--
--
J C Lawrence Internet: claw#null,net
----------(*) Internet: coder#ibm,net
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="01312" HREF="msg01312.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
<UL><LI><EM>From:</EM> Jeff Kesselman <jeffk#tenetwork,com></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg01315.html">Re: [MUD-Dev] "From Kansas to Oz"</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg01317.html">Re: [MUD-Dev] "From Kansas to Oz"</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg01312.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg01320.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#01316"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#01316"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>Re: [MUD-Dev] Room-based vs. coordinate-based</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="01271" HREF="msg01271.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Tue 10 Jun 1997, 06:45 GMT
<UL>
<LI><strong><A NAME="01287" HREF="msg01287.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Wed 11 Jun 1997, 12:24 GMT
<UL>
<LI><strong><A NAME="01307" HREF="msg01307.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Miroslav Silovic <a href="mailto:silovic#srce,hr">silovic#srce,hr</a>, Thu 12 Jun 1997, 15:19 GMT
<UL>
<LI><strong><A NAME="01312" HREF="msg01312.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Fri 13 Jun 1997, 02:51 GMT
<UL>
<LI><strong><A NAME="01316" HREF="msg01316.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
coder <a href="mailto:coder#ibm,net">coder#ibm,net</a>, Fri 13 Jun 1997, 11:37 GMT
</LI>
<LI><strong><A NAME="01320" HREF="msg01320.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Miroslav Silovic <a href="mailto:silovic#srce,hr">silovic#srce,hr</a>, Fri 13 Jun 1997, 21:12 GMT
<UL>
<LI><strong><A NAME="01322" HREF="msg01322.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Jeff Kesselman <a href="mailto:jeffk#tenetwork,com">jeffk#tenetwork,com</a>, Sat 14 Jun 1997, 01:12 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="01300" HREF="msg01300.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
Brandon J. Rickman <a href="mailto:ashes#pc4,zennet.com">ashes#pc4,zennet.com</a>, Thu 12 Jun 1997, 08:54 GMT
<UL>
<LI><strong><A NAME="01310" HREF="msg01310.html">Re: [MUD-Dev] Room-based vs. coordinate-based</A></strong>,
clawrenc <a href="mailto:clawrenc#cup,hp.com">clawrenc#cup,hp.com</a>, Fri 13 Jun 1997, 01:44 GMT
</LI>
</UL>
</LI>
</ul>
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>