Problems with Tutorial Example

12 views
Skip to first unread message

Helen

unread,
Mar 11, 2009, 7:52:36 AM3/11/09
to OBSearch-Users
When trying to compile the Tutorial Example on the OBSearch site, I'm
encountering 2 Problems:

TentaclePivotSelectorShort < OBSlice > ps = new
TentaclePivotSelectorShort < OBSlice >(
(short) 10, 32, new AcceptAll< OBSlice >
());
PPTreeShort < OBVectorExample > index =
new PPTreeShort < OBVectorExample > (dbFolder, (short) 30, 9,
ps);

This does not compile. It only works, if I replace <OBSlice> by
<OBVectorExample>. But then I'm getting: OBException:
org.ajmm.obsearch.exception.PivotsUnavailableException

The second Problem is that o contains the 100 shorts, but in
index.search o represents the target number.

I'd be very helpfull if you could have a look at my main:

package nntest;

import com.sleepycat.je.DatabaseException;
import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.Random;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.ajmm.obsearch.example.OBSlice;
import org.ajmm.obsearch.exception.OBException;
import org.ajmm.obsearch.index.PPTreeShort;
import org.ajmm.obsearch.index.pivotselection.AcceptAll;
import
org.ajmm.obsearch.index.pivotselection.TentaclePivotSelectorShort;
import org.ajmm.obsearch.result.OBPriorityQueueShort;
import org.ajmm.obsearch.result.OBResultShort;

/**
*
* @author helen
*/
public class Main {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try {
// TentaclePivotSelectorShort<OBVectorExample> ps = new
TentaclePivotSelectorShort<OBVectorExample>((short) 10, 32, new
AcceptAll<OBVectorExample>());
TentaclePivotSelectorShort <OBVectorExample> ps = new
TentaclePivotSelectorShort <OBVectorExample>(
(short) 10, 32, new
AcceptAll<OBVectorExample>());

File dbFolder = new File("/Users/helen/NetBeansProjects/
nntest/dbfile/");
PPTreeShort<OBVectorExample> index = new
PPTreeShort<OBVectorExample>(dbFolder, (short) 30, (byte) 9, ps,
OBVectorExample.class);


short[] mydata = new short[100];
Random random = new Random();
for (int i = 0; i < 100; i++) {
mydata[i] = (short) random.nextInt();
}
OBVectorExample o = new OBVectorExample(mydata);
// insert the object
index.insert(o);

index.freeze();

// This result object will hold the result of the search
process.
// note that it is here where you define k

byte k = (byte) 5;
short r = (short) 500;

OBPriorityQueueShort<OBVectorExample> result =
new OBPriorityQueueShort<OBVectorExample>(k);

if (result == null) {
System.err.println("Result is null");
}

// now you can search the closest elements to o within a
range r
// the result will be stored in "result"
OBVectorExample target = new OBVectorExample(new short[]
{0});
index.searchOB(target, r, result);

// You can iterate "result".
Iterator < OBResultShort < OBVectorExample> > iter =
result.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}


} catch (OBException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (IllegalAccessException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (InstantiationException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (DatabaseException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (IOException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
}

}
}


Thank you,
Helen

Arnoldo Muller

unread,
Mar 11, 2009, 8:25:50 AM3/11/09
to obsearc...@googlegroups.com
Dear Helen:

Thank you for writing! After I finished the first version OBSearch in
2007 I have been waiting for my first user.
And here you are! I am very happy!

My name is Arnoldo, I am OBSearch's developer, nice to meet you!

Thank you for pointing out the error in the tutorial. I did not catch
the problem. I will fix it when I write the new, updated tutorial.

The reason you are getting the PivotsUnavailableException is because
you need to add more objects in the database.
Pivots are special objects that are used to avoid distance computations:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.8283

In the constructor of PPTreeShort, you are asking for 30 of them, so
your database needs to be at least 30 in terms of size.
That is why you are getting the error. You might want to add more
objects to the DB by adding an extra loop:

for(int cx = 0; cx < 10000 ; cx++) {
for (int i = 0; i < 100; i++) {
mydata[i] = (short) random.nextInt();
}
OBVectorExample o = new OBVectorExample(mydata);
// insert the object
index.insert(o);
}


Please let me know how it goes with this, and thank you for your interest!

I am preparing a new version of OBSearch that will be *much* faster so
please stay tuned! :)

Arnoldo

Helen

unread,
Mar 11, 2009, 8:54:03 AM3/11/09
to OBSearch-Users
Dear Arnoldo

Thank you for the quick answer. I'm glad you developed a search
library in java, so now I won't need to bring my code to C++ to use
the ANN library. I'll t to use it to quickly find pixels closest in
color in large images.

Unfortunately, increasing the input array or decreasing the pivot
number does not solve the problem. (I chose 30 pivots because that's
what you do in your tutorial). Are you sure it is not caused by
replacing <OBSlice> by <OBVectorExample> as mentioned in my first
post? I'm still getting these errors:

log4j:WARN No appenders could be found for logger
(org.ajmm.obsearch.index.AbstractPivotIndex).
log4j:WARN Please initialize the log4j system properly.
Mar 11, 2009 1:45:05 PM nntest.Main main
SEVERE: null
org.ajmm.obsearch.exception.OBException:
org.ajmm.obsearch.exception.PivotsUnavailableException
at org.ajmm.obsearch.index.AbstractPivotIndex.freeze
(AbstractPivotIndex.java:698)
at nntest.Main.main(Main.java:48)
Caused by: org.ajmm.obsearch.exception.PivotsUnavailableException
at
org.ajmm.obsearch.index.pivotselection.AbstractTentaclePivotSelector.generatePivots
(AbstractTentaclePivotSelector.java:107)
at org.ajmm.obsearch.index.AbstractPivotIndex.prepareFreeze
(AbstractPivotIndex.java:650)
at org.ajmm.obsearch.index.AbstractPivotIndex.freeze
(AbstractPivotIndex.java:695)
... 1 more

Thank you
Helen

Arnoldo Muller

unread,
Mar 11, 2009, 9:07:32 AM3/11/09
to obsearc...@googlegroups.com
Dear Helen:

Great! sounds like you are going to have a lot of fun with images :)

Ok, so let me give you a bit of background:
OBSlice and OBVectorExample are types of objects that you can store
on OBSearch. OBSlice holds trees, with a tree distance function.
OBVectorExample stores points of n dimensions with the L_1 distance.

Now, one question, by input array do you mean the loop:

for (int i = 0; i < 100; i++) {
mydata[i] = (short) random.nextInt();
}

?

AM

Helen

unread,
Mar 11, 2009, 9:37:25 AM3/11/09
to OBSearch-Users
Yes, that's what I meant. I increased mydata to a size of 10000 and
filled it with random numbers.

The PPTreeShort index does not accept a pivot selection strategy that
is typed < OBSlice > ( like in your tutorial), at least that's what my
compiler says.

Thanks,
Helen

Arnoldo Muller

unread,
Mar 11, 2009, 9:52:32 AM3/11/09
to obsearc...@googlegroups.com
Ok so when you increased mydata to a size of 10000 you created a
point of n=10000 dimensions and inserted it into the index.
The index only has one point (a big point by the way! ) so the pivot
selection fails.

You need to call the index.insert() method 30 times or more (with
different objects).
So you would have to create 30 or more mydata arrays and insert them
before calling "freeze".

// this outer loop will insert 10000 points that have 100 dimensions each.
for(int cx = 0; cx < 10000 ; cx++) {
// **** this is your original code
for (int i = 0; i < 100; i++) {
mydata[i] = (short) random.nextInt();
}
OBVectorExample o = new OBVectorExample(mydata);
// insert the object
index.insert(o);
// **** end of your code
}

The pivot selection must be configured to work only on OBVectorExample
objects for safety reasons. If you mix objects of different types,
horrible things could happen :) An index can only handle one type of
object at a time (points, trees, strings).

BTW, in the query code you sent, in the search section you have to
create an object of 100 dimensions or you will get another error
during search time.

OBVectorExample target = new OBVectorExample(new short[]{0}); //
create another random "mydata".

Please let me know how it goes :)

Arnoldo

Helen

unread,
Mar 11, 2009, 10:37:03 AM3/11/09
to OBSearch-Users
I'm trying to do what you suggest in your tutorial:
Take 100 points of one dimension, determine L1 distance and find the
three points closest to zero (not to a random number).
But if I create one hundred OBVectorExamples of dimension one, this is
not compatible with what you indicated in the OBVectorExampleClass:
private static final int VECTOR_SIZE = 100;
If I change it to VECTOR_SIZE = 1, I'm getting the pivot exceptions
again. I'm confused now...help...


public static void main(String[] args) {
try {
short[] mydata = new short[1]; //point object with one
dimension
TentaclePivotSelectorShort <OBVectorExample> ps = new
TentaclePivotSelectorShort <OBVectorExample>
((short) 10, 32, new AcceptAll<OBVectorExample>());
File dbFolder = new File("/Users/helen/NetBeansProjects/
nntest/dbfile/");
PPTreeShort<OBVectorExample> index = new
PPTreeShort<OBVectorExample>(dbFolder, (short) 30, (byte) 9, ps,
OBVectorExample.class);

Random random = new Random();

for(int cx = 0; cx < 100 ; cx++) { //add 100 points
mydata[0] = (short) random.nextInt();
OBVectorExample o = new OBVectorExample(mydata);
index.insert(o);
}
index.freeze();


byte k = (byte) 3;
short r = (short) 500;

OBPriorityQueueShort<OBVectorExample> result =
new OBPriorityQueueShort<OBVectorExample>(k);

if (result == null) {
System.err.println("Result is null");
}

OBVectorExample target = new OBVectorExample(new short[]
{0});
index.searchOB(target, r, result);

// You can iterate "result".
Iterator < OBResultShort < OBVectorExample> > iter =
result.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}


} catch (OBException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (IllegalAccessException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (InstantiationException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (DatabaseException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
} catch (IOException ex) {
Logger.getLogger(Main.class.getName()).log(Level.SEVERE,
null, ex);
}

}
}

Thanks,
Helen

Arnoldo Muller

unread,
Mar 11, 2009, 10:50:23 PM3/11/09
to obsearc...@googlegroups.com
Helen,

OK so here is the deal:

Do not touch "private static final int VECTOR_SIZE = 100;"
We are going to match objects of n=100 dimensions, otherwise it is not fun.

Please carefully see the code I sent you. You have in your code:
for(int cx = 0; cx < 100 ; cx++) { //add 100 points
mydata[0] = (short) random.nextInt();
OBVectorExample o = new OBVectorExample(mydata);
index.insert(o);
}

But you want to have:

The important part is this outer loop that will make sure you perform
10000 object insertions
(not only 100). So we will insert 10000 points of 100 dimensions each.
// this outer loop will insert 10000 points that have 100 dimensions each.
for(int cx = 0; cx < 10000 ; cx++) {
// **** this is your original code
for (int i = 0; i < 100; i++) {
mydata[i] = (short) random.nextInt();
}
OBVectorExample o = new OBVectorExample(mydata);
// insert the object
index.insert(o);
// **** end of your code
}


Another thing you might want to do is this:
RandomPivotSelector ps = new RandomPivotSelector() instead of the
TentaclePivotSelector.
Random will always work but the resulting pivots are not going to be that great.
Try with this and tell me how it goes.

Arnoldo

Helen

unread,
Mar 12, 2009, 11:57:02 AM3/12/09
to OBSearch-Users
Arnoldo,

it is working now, though only with the RandomPivotSelector. To be
able to check the results I hardcoded five 3-dimensional points:
index.insert(new OBVectorExample (new short[] {10,10,10}));
index.insert(new OBVectorExample (new short[]
{100,100,100}));
index.insert(new OBVectorExample (new short[]
{200,200,200}));
index.insert(new OBVectorExample (new short[]
{300,300,300}));
index.insert(new OBVectorExample (new short[]
{400,400,400}));

And I'm asking for the three points closest to:
OBVectorExample target = new OBVectorExample(new short[] {5,5,5});
within a radius of 1000:
index.searchOB(target, r, result);

The results I get:
<9538 288>
<1 285>
<0 15>

Now, what is the first one? And if I execute this again, I only get
wrong results or errors (OBException:
org.ajmm.obsearch.exception.OutOfRangeException) or
<4183 146>
<4078 117>
<0 15>

It seems to me that I need to clean up some structures? Which ones? I
already tried to clean the index.
for (int p = 0; p < 5; p++) {
index.delete(index.getObject(p));

Thank you,
Helen


public static void main(String[] args) {
try {
short[] mydata = new short[3]; //point object with three
dimensions
RandomPivotSelector ps = new RandomPivotSelector() ;

File dbFolder = new File("/Users/helen/NetBeansProjects/
nntest/dbfile/");
PPTreeShort<OBVectorExample> index = new
PPTreeShort<OBVectorExample>(dbFolder, (short) 30, (byte) 9, ps,
OBVectorExample.class);

Random random = new Random();

/* for(int cx = 0; cx < 10000 ; cx++) {
// **** this is your original code
for (int i = 0; i < 3; i++) {
mydata[i] = (short) random.nextInt();
}


OBVectorExample o = new OBVectorExample(mydata);
// insert the object
index.insert(o);
// **** end of your code
}*/

index.insert(new OBVectorExample (new short[] {10,10,10}));
index.insert(new OBVectorExample (new short[]
{100,100,100}));
index.insert(new OBVectorExample (new short[]
{200,200,200}));
index.insert(new OBVectorExample (new short[]
{300,300,300}));
index.insert(new OBVectorExample (new short[]
{400,400,400}));



index.freeze();


byte k = (byte) 3;
short r = (short) 1000;

OBPriorityQueueShort<OBVectorExample> result =
new OBPriorityQueueShort<OBVectorExample>(k);

if (result == null) {
System.err.println("Result is null");
}




OBVectorExample target = new OBVectorExample(new short[]
{5,5,5});

index.searchOB(target, r, result);

// You can iterate "result".
Iterator < OBResultShort < OBVectorExample> > iter =
result.iterator();
while (iter.hasNext()) {
System.out.println(iter.next());
}

for (int p = 0; p < 5; p++) {
index.delete(index.getObject(p));

Arnoldo Muller

unread,
Mar 12, 2009, 12:41:27 PM3/12/09
to obsearc...@googlegroups.com
Dear Helen:

OK so now you can freeze data. Regarding your results:

<9538 288> is a very far point. The version of OBsearch you are using
only provides an iterator. This iterator returns the values
in no specific order. Of course, a point at distance 9538 is
impossible, the only thing I can think is that a horrible rounding
(floating point) error just appeared. After I created the vresion of
OBSearch you are using, I implemented the IDistance, a very reliable
index. The P+Tree is prone to some nasty rounding errors. With the
IDistance I think you should be getting the results properly.
If you give me a couple of days I can release a new version with the
IDistance, a different index. (it is in SVN by the way)

Regarding the huge value you are receiving... the OutOfRangeException...
Please do:
mydata[i] = (short) random.nextInt(1000);
The problem is that the random number is generating very big ints the
index only handles shorts so there are some issues regarding this.

Let me know if this quick fix works :)

I will be working on releasing the IDistance, thanks again for your
interest in OBSearch!


Arnoldo.

Helen

unread,
Mar 12, 2009, 12:59:42 PM3/12/09
to OBSearch-Users
Arnoldo,

if you look at my last post, I'm not using any random numbers anymore.
Only 5 hardcoded points with three dimension and one hardcoded point
to compare it with (code is at the bottom of the last post). The
ranges are between 10 and 400. My impression is rather that there are
some leftovers from previous executions in the index or result queu???
Two of the three results are often correct and in right order, but the
more often I execute the code, the more weird results I get.

Thanks,

Helen

Arnoldo Muller

unread,
Mar 12, 2009, 1:10:32 PM3/12/09
to obsearc...@googlegroups.com
Dear Helen:

I am in Japan so because of the timezone thing it might take a couple
of hours for me to answer.
Are you located in Switzerland? Lovely country! sublime mountains! I
love mountains :)

What I will do is to review the code as it was in 2008 (when I
released the last version that I hope you are using) and I will
get back to you soon OK? :) I will send you code that works so that
you can use it as a tutorial.
Thanks to you I can figure it out how to make it easier for people to
use OBSearch.

Thanks again for your interest in OBSearch,

Arnoldo

Helen

unread,
Mar 12, 2009, 1:34:07 PM3/12/09
to OBSearch-Users
Dear Arnoldo:

Yes, I'm using the code from http://obsearch.googlecode.com/files/obsearch-0.9.1b-jar-with-dependencies.jar

Sure, take you time (and sleep). I am based in Switzerland.

If you do all this work mostly for me (and the test users to come),
let me explain what I need your code for. I'm working on texture
generation. In a first step I have a pixel with a certain RGB color
and I try to find the most similar pixel in a 4000 x 4000 pixel image
using L2-distance. I've already coded this, but only brute-force which
is way too slow. So this is why I need your library that can
accelerate the process using indexing techniques.

In a second step besides color every pixel receives additional
characteristics that can receive different priority, so this will be a
complex multi-feature search e.g. find a reddish pixel within a round
shape where round is more important than reddish (I found the MESSIF-
library that says it can do such searches, but the code for multi-
feature searches was not included in the download). So if your library
has anything to offer to combine searches, this would be very
interesting, too.

But I'd already be very thankful, if you can make the tutorial work.
This will then allow me to do complete step one.

Thanks a lot,

Helen

Arnoldo Muller

unread,
Mar 12, 2009, 2:07:39 PM3/12/09
to obsearc...@googlegroups.com
Helen just one more question:

What is your definition of pixel? One integer or float?

Arnoldo Muller

unread,
Mar 12, 2009, 8:28:06 PM3/12/09
to obsearc...@googlegroups.com
I see so a pixel is an RGB point right?

It is a 3 dimensional point?

So your O extends OBFloat will have 3 dimensions and the l2 distance.

Ok I will take this into account for the preparation of the example :)

Helen

unread,
Mar 13, 2009, 4:02:53 AM3/13/09
to OBSearch-Users
Yes, that sounds right. A point with 3 dimensions. I'd rather have
float, then I can use the class also for other characteristics.
Thanks.

Helen


Arnoldo Muller

unread,
Mar 15, 2009, 12:37:16 PM3/15/09
to obsearc...@googlegroups.com
Hello Helen!

I had a pretty busy weekend so I could not move forward in releasing a
new version of OBSearch and I am leaving for the next 3 days.
It will take me a little more than I expected to release what I promised

Regarding your special queries, OBSearch only supports one distance
function at a time. I read a paper on the topic a while ago and what
they did
was to modify the M-Tree. I believe it should be possible to modify
OBSearch to support multiple queries but it needs to be done. Another
option is to design a distance function that holds all the information
(shape, color). The only problem is that the "round is more important
than red" part of the predicate...
A "for the poor" version would be to query with a large k and then
filter the objects that are closer to your objective: "round is more
important than red".

I am sure you have deadlines to commit to and it might take a week or
more before I can get you an updated version of OBSearch (the version
you are using is a bit old). You could try checking out the code from
svn but there are lots of rough edges in the trunk right now.

Since your objects are not high dimensional yet, have you considered
Mysql or Postgre spatial extensions?
For the problem of finding closest 3D points I am sure they are ready
to use. R-trees are still quite effective in 3 dimensions from what I
have heard. For adding the extra information of roundness and the
like, maybe a spatial query combined with a join to other table might
still be good enough, but I can't guarantee anything as I haven't used
them.

Regarding Messif, did you get actually the source code? if so, is it GPL?

Let me know how what do you want to do. In any case, I am planning to
release as soon as possible a copy of OBSearch with a N-d point
tutorial included.

Thanks again for your interest :)

Arnoldo

On Fri, Mar 13, 2009 at 2:34 AM, Helen <helen...@karto.baug.ethz.ch> wrote:
>

Helen

unread,
Mar 16, 2009, 1:13:28 PM3/16/09
to OBSearch-Users
Arnoldo,

I found the Weka-library with a knn-example and different index trees.
The basic example works, though I still need to test its performance.
I think I'll use this library, so that I can go on with my work.

Thanks again.

Helen

Arnoldo Muller

unread,
Mar 18, 2009, 9:15:56 AM3/18/09
to obsearc...@googlegroups.com
Ok great!

I am sorry that OBSearch did not satisfy your needs. I have been
focusing on creating a faster index by using Sketches and
I did not focus on user experience :)

Please subscribe to the announce list so that you can be notified when
a new version of OBSearch is released.

Thanks again for your interest :)

Reply all
Reply to author
Forward
0 new messages