Sqlite RTree nearest neighbour

classic Classic list List threaded Threaded
8 messages Options
Reply | Threaded
Open this post in threaded view
|

Sqlite RTree nearest neighbour

mailing lists
Hello,

does anybody have any experience with implementing a nearest neighbor search using SQLite's RTree functionality? Is a nearest neighbor search possible?

Regards,
Hartwig


_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

Simon Slavin-3

On 21 Aug 2014, at 10:32pm, skywind mailing lists <[hidden email]> wrote:

> does anybody have any experience with implementing a nearest neighbor search using SQLite's RTree functionality? Is a nearest neighbor search possible?

How much have you read ?  Are you familiar with SpaciaLite ?  Have you tried implementing Nearest Neighbour without RTree ?

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

Carlos Ferreira
I am not an expert in Sqlite R-tree, but it seems that if you want to solve
a nearest neighbor you need not only to search the objects in the leaf
containing the object you testing, but also some adjacent leaves around.

Another option would be to search for objects inside a  centered box or
sphere over the object, starting with a small box containing anything else
other than the object and start increasing the size until you get one or
more objects inside...From there you would just have to select the closest
one...

Probably there is some much easier way and I am not familiar with it...


-----Original Message-----
From: [hidden email]
[mailto:[hidden email]] On Behalf Of Simon Slavin
Sent: quinta-feira, 21 de Agosto de 2014 23:09
To: General Discussion of SQLite Database
Subject: Re: [sqlite] Sqlite RTree nearest neighbour


On 21 Aug 2014, at 10:32pm, skywind mailing lists <[hidden email]>
wrote:

> does anybody have any experience with implementing a nearest neighbor
search using SQLite's RTree functionality? Is a nearest neighbor search
possible?

How much have you read ?  Are you familiar with SpaciaLite ?  Have you tried
implementing Nearest Neighbour without RTree ?

Simon.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

Peter Aronson-3
In reply to this post by mailing lists
According to R-Trees: Theory and Applications by Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos and Yannis Theodoridis, there are a number of algorithms for efficiently determining the nearest neighbor(s) using an R-Tree (an internet search on the two terms will pull up several).  There are two things to keep in mind about this:
        1. You would need to access SQLite's R-Tree "shadow" tables (xx_node, xx_parent, xx_rowid) directly in to perform the traversals required by all of the algorithms -- I don't know if this is officially supported by SQLite's developers, or if these tables are guaranteed not to change;
        2. If your dimension is > 1, the R-Tree alone can't give you a reliable answer about who is closer, you would also need a method to calculate the minimum distance between two indexed objects.
Peter


On Thursday, August 21, 2014 2:32 PM, skywind mailing lists <[hidden email]> wrote:
 

>
>
>Hello,
>
>does anybody have any experience with implementing a nearest neighbor search using SQLite's RTree functionality? Is a nearest neighbor search possible?
>
>Regards,
>Hartwig
>
>
>_______________________________________________
>sqlite-users mailing list
>[hidden email]
>http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
>
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

Richard Hipp-3
On Thu, Aug 21, 2014 at 8:54 PM, Peter Aronson <[hidden email]> wrote:

>         1. You would need to access SQLite's R-Tree "shadow" tables
> (xx_node, xx_parent, xx_rowid) directly in to perform the traversals
> required by all of the algorithms -- I don't know if this is officially
> supported by SQLite's developers, or if these tables are guaranteed not to
> change;
>

The format of the shadow tables will not change in ways that would break
older versions of SQLite.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

mailing lists
Hello,

I hoped that somebody already tried to implement a nearest neighbor algorithm. Is the format of the shadow tables somewhere documented or do I have to analyze the source code?

Regards,
Hartwig

Am 22.08.2014 um 02:58 schrieb Richard Hipp <[hidden email]>:

> On Thu, Aug 21, 2014 at 8:54 PM, Peter Aronson <[hidden email]> wrote:
>
>>        1. You would need to access SQLite's R-Tree "shadow" tables
>> (xx_node, xx_parent, xx_rowid) directly in to perform the traversals
>> required by all of the algorithms -- I don't know if this is officially
>> supported by SQLite's developers, or if these tables are guaranteed not to
>> change;
>>
>
> The format of the shadow tables will not change in ways that would break
> older versions of SQLite.
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

Clemens Ladisch
skywind mailing lists wrote:
> I hoped that somebody already tried to implement a nearest neighbor
> algorithm.

Typically, objects are not axis-aligned rectangles, and the R-tree is
just an index based on the bounding boxes.  Computing the (nearest)
distance would require the actual geometries.

> Is the format of the shadow tables somewhere documented or do I have
> to analyze the source code?

rtree.c says:

** Database Format of R-Tree Tables
** --------------------------------
**
** The data structure for a single virtual r-tree table is stored in three
** native SQLite tables declared as follows. In each case, the '%' character
** in the table name is replaced with the user-supplied name of the r-tree
** table.
**
**   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
**   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
**   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
**
** The data for each node of the r-tree structure is stored in the %_node
** table. For each node that is not the root node of the r-tree, there is
** an entry in the %_parent table associating the node with its parent.
** And for each row of data in the table, there is an entry in the %_rowid
** table that maps from the entries rowid to the id of the node that it
** is stored on.
**
** The root node of an r-tree always exists, even if the r-tree table is
** empty. The nodeno of the root node is always 1. All other nodes in the
** table must be the same size as the root node. The content of each node
** is formatted as follows:
**
**   1. If the node is the root node (node 1), then the first 2 bytes
**      of the node contain the tree depth as a big-endian integer.
**      For non-root nodes, the first 2 bytes are left unused.
**
**   2. The next 2 bytes contain the number of entries currently
**      stored in the node.
**
**   3. The remainder of the node contains the node entries. Each entry
**      consists of a single 8-byte integer followed by an even number
**      of 4-byte coordinates. For leaf nodes the integer is the rowid
**      of a record. For internal nodes it is the node number of a
**      child page.

For a simple search algorithm, see <http://stackoverflow.com/q/25241406>.


Regards,
Clemens
_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: Sqlite RTree nearest neighbour

mailing lists
Hi Clemens,

thanks for the link!

Regards,
Hartwig

Am 22.08.2014 um 22:26 schrieb Clemens Ladisch <[hidden email]>:

> skywind mailing lists wrote:
>> I hoped that somebody already tried to implement a nearest neighbor
>> algorithm.
>
> Typically, objects are not axis-aligned rectangles, and the R-tree is
> just an index based on the bounding boxes.  Computing the (nearest)
> distance would require the actual geometries.
>
>> Is the format of the shadow tables somewhere documented or do I have
>> to analyze the source code?
>
> rtree.c says:
>
> ** Database Format of R-Tree Tables
> ** --------------------------------
> **
> ** The data structure for a single virtual r-tree table is stored in three
> ** native SQLite tables declared as follows. In each case, the '%' character
> ** in the table name is replaced with the user-supplied name of the r-tree
> ** table.
> **
> **   CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
> **   CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
> **   CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)
> **
> ** The data for each node of the r-tree structure is stored in the %_node
> ** table. For each node that is not the root node of the r-tree, there is
> ** an entry in the %_parent table associating the node with its parent.
> ** And for each row of data in the table, there is an entry in the %_rowid
> ** table that maps from the entries rowid to the id of the node that it
> ** is stored on.
> **
> ** The root node of an r-tree always exists, even if the r-tree table is
> ** empty. The nodeno of the root node is always 1. All other nodes in the
> ** table must be the same size as the root node. The content of each node
> ** is formatted as follows:
> **
> **   1. If the node is the root node (node 1), then the first 2 bytes
> **      of the node contain the tree depth as a big-endian integer.
> **      For non-root nodes, the first 2 bytes are left unused.
> **
> **   2. The next 2 bytes contain the number of entries currently
> **      stored in the node.
> **
> **   3. The remainder of the node contains the node entries. Each entry
> **      consists of a single 8-byte integer followed by an even number
> **      of 4-byte coordinates. For leaf nodes the integer is the rowid
> **      of a record. For internal nodes it is the node number of a
> **      child page.
>
> For a simple search algorithm, see <http://stackoverflow.com/q/25241406>.
>
>
> Regards,
> Clemens
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users